Method for process scheduling in a processor based system

• US 5,894,572 A
• Filed: 06/07/1995
• Issued: 04/13/1999
• Est. Priority Date: 12/04/1992
• Status: Expired due to Fees

• Current Assignee: Network Computing Devices Incorporated
• Original Assignee: Network Computing Devices Incorporated
• Inventors: Martin, Kevin
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/487,866
• Time in Patent Office: 1,406 Days
• Field of Search: 395/650, 395/200, 395/672, 395/674, 395/680, 395/684, 395/670, 364/300
• US Class Current: 718/104
• CPC Class Codes: G06T 15/405 using Z-buffer
• CPC Class Codes: G09G 5/393 Arrangements for updating the contents of the bit-mapped memory

Abstract

A method for rendering of three dimensional images on a video subsystem which does not include clearing of the Z buffer at each frame includes establishment of a Z buffer and a sequence number in memory, where the sequence number is incremented with each successive frame rendered and the Z buffer is cleared when the sequence number reaches a predetermined value; the Z buffer is thus recycled a number of times between clears. In a more elaborate implementation, the precision of the Z buffer is adjusted to permit clearing of the Z buffer to occur either as the result of the sequence number reaching a predetermined value or as the result of the accrual of a predetermined amount of time allocated for clearing, referred to as scheduling. The scheduling method can be applied to a wide range of accounting tasks within a system. In addition, a related method for recycling the image buffer is also disclosed in which multiple colormap ID'"'"'s are used to distinguish data included in a current frame from data in a prior frame, where the colormap ID'"'"'s associated with the prior frames all map to the background color, leaving to be displayed only the data of the current frame.

Claims

1. In a processor based system in which a plurality of calls can contend for access to the processor, a method of scheduling access comprising the steps of:

identifying a plurality of calls each contending for access to the processor,

accruing a value for at least some of such plurality of calls proportional to the amount of time spent waiting for access to the processor,

providing access to the processor to the call having the greatest accrued value, and

decreasing the value for each process which was provided access to the processor.

2. A method as recited in claim 1 wherein the step of decreasing the value for each process decreases the value by an amount proportional to the elapsed time of the access.

3. A method as recited in claim 1 further comprising the steps of:

measuring an amount of time which elapses during a first processor access of a first call, and

providing a second processor access to the first call when the measured amount of time becomes less than a predetermined percentage of the elapsed time since the first processor access of the first call.

4. In a processor based system in which a plurality of calls contend for access to the processor, a method of scheduling processor access comprising the steps, performed by the processor, of:

providing a queue for calls waiting for processor access,

accruing a value for each call in the queue proportional to the amount of time spent waiting for processor access,

providing processor access to the call in the queue having the greatest accrued value,

decreasing the value for the call provided processor access by an amount proportional to the elapsed time of the access, and

allowing the call provided processor access to return to the queue.

5. A method as recited in claim 4 wherein the step of providing access to the processor provides access to the call with the greatest accrued value.

6. A method as recited in claim 4 further comprising the steps of:

measuring an amount of time which elapses during a first processor access of a first call, and

providing a second processor access to the first call when the measured amount of time becomes less than a predetermined percentage of the elapsed time since the first processor access of the first call.