Deadlock-avoidance in a page-parallel rasterizer

A rasterizer converts a document described in some page-description language into a sequence of full-page bitmaps (pagemaps), which can then be printed or displayed. The page-parallel rasterizer harnesses multiple processors to work on the same document. Any given page, however, is processed by a single processor, hence the name. For performance reasons, it is desirable to permit out-of-order rasterization. However, this can result in deadlock. It is shown how to pace the rasterizer so as to avoid deadlock without being overly restrictive. To do this, previously-proposed deadlock-avoidance schemes are extended to cases that seem to be outside their scope. The approach may also be useful in other applications