Method, apparatus and computer program product for borrowed-virtual-time scheduling
US7065762B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 22, 1999 |
| Grant date | Jun 20, 2006 |
| Priority date | — |
| Expiry date | Mar 22, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/4887
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention includes a scheduling mechanism that fairly allocates a resource to a number of schedulable elements of which some are latency-sensitive. The invention tracks each element's use of the resource by determining the element's virtual time. An active element is selected from the elements that are ready to use the resource by determining the element that has the smallest effective virtual time. The effective virtual time is the element's actual virtual time modified by a borrowed virtual time value. When an element has a short-term need for the resource, it can borrow the privilege to run by borrowing virtual time. As the element uses the resource, it consumes virtual time according to its weight. When the elements are scheduled for the resource, the ready elements having the smallest virtual time is selected. The invention enforces long-term fairness to each element while allowing latency-sensitive elements to be preferably selected.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.