Browse Prior Art Database

Original Publication Date: 2001-Apr-26
Included in the Prior Art Database: 2003-Jun-19

Publishing Venue



When more than one process is runnable in a computer system, the operating system (or some such entity) must decide which process to run first. This decision is made by a process "scheduler" and the algorithm is called the "scheduling algorithm." Since this scheduling is typically performed in software, the algorithm used is a fairly simple mechanism. Using one which is too complicated and the benefits of scheduling outweigh the overhead used to implement them. Another coincident difficulty here is the general static nature of a "scheduling algorithm" implies the algorithm cannot ideally adapt to processes with different run time dynamics. Ideally what is needed is a mechanism which can schedule processes with fine granularity; one which can be can be configured and adapted to specific process' behavioral dynamics and which requires little operating system overhead. It would also allow specific processes to have individual processor access contracts. This way, access to a processor can be allocated on a per process basis rather than through the use of a "catch all" static algorithm. Proposed is a mechanism with which every process has its own "quantum contract". This contract includes such parameters as: (1) Average Quantum Rate [AQR], (2) Maximum Quantum Rate [MQR], (3) Maximum Quantum Burst Rate [MQBR] and (4) Maximum Quantum Burst Length [MQBL]. Using these four parameters, the resource requirements of a process can be closely matched to availability of those resources to achieve optimal usage. The resources include, among others: memory, I/O, process time and cache usage. The way this process scheduling is achieved is very similar to the ATM Cell Scheduler of [2] which schedules ATM cells to be transmitted onto a network. This method uses a "timing wheel" approach which gives very fine temporal granularity when choosing a task to perform while avoiding the overhead problem of scanning the "ready" list for every change in the list. In the ATM network world, cells are transmitted by being inserted onto an outgoing "link" or "wire". By creating the concept of "cell wide slots" (a cell slot is the time it takes to transmit one cell), ATM network connections can be set to transmit a cell during predetermined cell slots in the outgoing link. This cell slot is then, in effect, a transmission opportunity which is either used by a particular network connection to transmit one of its queued data cells out the link or it goes unused. The timing wheel does all the necessary administration to schedule cells according to a "traffic contract" using parameters similar to the ones enumerated above. An ATM connection, represented by a Logical Channel Descriptor or LCD, is associated with a particular cell slot which is often in the future. Cells are transmitted in each cell slot (given that other connections want to send cells too) until this particular cell slot is encountered. A data cell is taken from the connections and transmitted using that cell slot. The connection is then "rescheduled" according to its traffic contract by moving it to another future cell slot, time is advanced by one slot and the whole process continues. This mechanism gives a high degree of control. For instance if 10% of the available bandwidth is required for a connection then the connection would be (re)scheduled and given a transmission opportunity, or cell slot, every 10 slots. More complicated contracts can be realized using the other parameters.