Move-to-rear list scheduling
First Claim
1. Apparatus for providing a desired quality of service to a plurality of processes by at least one server comprisingan admission control element for assigning to each process, Pj, of selected ones of said plurality of processes a respective initial value for a time, leftj ≧
- 0, for use of each of said servers,a memory storing for each server an ordered list of entries, said list having a front and a back, each said entry corresponding to a respective one, Pj, of said selected ones of said processes, said entries for said selected ones of said processes comprising information about the status of said selected processes and an indication of the time remaining of the time assigned to said each of said selected processes, anda process control element granting the services of a server to Pj when Pj has an entry in said list comprising an indication that said process has a first status, and which entry is nearer to the front of said ordered list than an entry in said list corresponding to any other process having said first status, said granting of said services being for a period not greater than said time remaining.
10 Assignments
0 Petitions
Accused Products
Abstract
A new scheduling method and policy for shared (server) resources, such as the CPU or disk memory of a multiprogrammed data processor. The scheduling is referred to as Move-To-Rear List Scheduling and it provides a cumulative service guarantee and well as more traditional guarantees such as fairness (proportional sharing) and bounded delay. In typical operation, a list is maintained for a server of processes seeking service from the server. Processes are admitted to the list only when maximum capacity constraints are not violated, and once on the list, are served in a front-to-back order. After receiving service, or upon the occurrence of other events, the position of the process on the list may be changed.
-
Citations
32 Claims
-
1. Apparatus for providing a desired quality of service to a plurality of processes by at least one server comprising
an admission control element for assigning to each process, Pj, of selected ones of said plurality of processes a respective initial value for a time, leftj ≧ - 0, for use of each of said servers,
a memory storing for each server an ordered list of entries, said list having a front and a back, each said entry corresponding to a respective one, Pj, of said selected ones of said processes, said entries for said selected ones of said processes comprising information about the status of said selected processes and an indication of the time remaining of the time assigned to said each of said selected processes, and a process control element granting the services of a server to Pj when Pj has an entry in said list comprising an indication that said process has a first status, and which entry is nearer to the front of said ordered list than an entry in said list corresponding to any other process having said first status, said granting of said services being for a period not greater than said time remaining. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
- 0, for use of each of said servers,
-
14. A method for providing a desired quality of service to a plurality of processes by at least one server comprising
assigning to each of selected ones Pj of said plurality of processes an initial value for a time leftj ≧ - 0 for use of each of said servers,
storing for each server an ordered list of entries having a front and a back, said entries each corresponding to respective ones of selected ones of said processes, said entries comprising information about the status of said selected processes and an indication of the time remaining of the time assigned to said each of said selected processes, and granting the services of a server to a process, which process has a corresponding entry comprising an indication that said process has a first status, and which corresponding entry is nearer to the front of said ordered list than an entry corresponding to any other process, said granting of said services being for a period not greater than said time remaining. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
- 0 for use of each of said servers,
-
29. A method for assuring a specified cumulative quality of service for a plurality of processes seeking service by one or more servers comprising the steps of
receiving, for each said process, service fraction signals reflecting the fraction of the services of each of said servers required by each said process, selecting a set of said processes which, when granted service by servers in accordance with said received service fractions, do not cause the sum of service fractions for each server to exceed unity, said sum being determined without regard to conflicting requests by said processes, granting services to each of said selected processes by said services in accordance with said service fractions.
Specification