Move-to-rear list scheduling

• US 5,999,963 A
• Filed: 11/07/1997
• Issued: 12/07/1999
• Est. Priority Date: 11/07/1997
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Gabber, Eran, Bruno, John Louis, Ozden, Banu, Silberschatz, Abraham
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/965,934
• Time in Patent Office: 760 Days
• Field of Search: 709/100, 709/102, 709/103, 709/104, 709/105, 709/300
• US Class Current: 718/104
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

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.

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, P_j, of selected ones of said plurality of processes a respective initial value for a time, left_j ≧

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, P_j, 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 P_j when P_j 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.

2. The apparatus of claim 1 wherein said admission control element comprises

means for receiving for each of said plurality of processes a request for a service fraction 0≧

α

_sj ≧

1 of the services of each server to said plurality of processes, and wherein

said assigning by said admission control element to each of said selected processes of an initial time left_j for use of each of said servers is based on the respective ones of said requested service fractions.

3. The apparatus of claim 1, wherein said stored information about the status of said selected processes comprises information relating to the readiness of each of said selected processes to currently use the services of each of said servers.

4. The apparatus of claim 1 wherein said admission control element further comprises

means for receiving for each of said plurality of processes a request for a service fraction of the services of each server to said plurality of processes, and

means for selecting said selected ones of said selected processes only if the sum of all service fractions for all of said selected processes is less than unity for each of said servers.

5. The apparatus of claim 2, wherein said assigning by said admission control element of said left_j is based on the respective one of said requested service fractions.

6. The apparatus of claim 1 further comprising means for decrementing left_j for use of a server by the amount of time said process used the services of said server.

7. The apparatus of claim 1, wherein said process control element places the entry for a process Pj at the end of the list for a server s when left_j has a value equal to zero.

8. The apparatus of claim 1 wherein at least one of said servers is a central processing unit.

9. The apparatus of claim 1, wherein at least one of said servers is a memory unit.

10. The apparatus of claim 1 wherein each server s has a respective preemption interval Δ

t_s ≧

0, and wherein said initial time left_j for each server is at least equal to Δ

t_s.

11. The apparatus of claim 1, wherein each of said plurality of processes corresponds to a respective collection of received data signals, each collection of data signals including address information about a respective output to which said collection of data signals is to be delivered.

12. The apparatus of claim 11, wherein each collection of data signals comprises at least one packet, and said address information comprises an address field in said at least one packet.

13. The apparatus of claim 11, wherein each collection of data signals comprises at least one cell, and said address information comprises an address field in said at least one cell.

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 P_j of said plurality of processes an initial value for a time left_j ≧

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.

15. The method of claim 14 further comprising the step of

receiving for each of said plurality of processes a request for a service fraction 0≧

α

_sj ≧

1 of the services of each server to said plurality of processes, wherein

said assigning to each of said selected processes a time for use of each of said servers is based on said requested service fraction.

16. The method of claim 14 wherein said information about the status of said selected processes comprises information about the readiness of each of said selected processes to currently use the services of each of said servers.

17. The method of claim 14 further comprising the steps of

receiving for each of said plurality of processes a request for a service fraction 0≧

α

_sj ≧

1 of the services that can be provided by each server to said plurality of processes, wherein

selecting said selected ones of said processes only if the sum of all service fractions for all of said selected processes is less than unity for each of said servers.

18. The method of claim 17 wherein said assigning to each of said selected processes of a time, left_j ≧

0, for each server s is based on said requested service fraction, α

_sj.

19. The method of claim 14, further comprising decrementing left_j by an amount reflecting the use by process P_j of server s.

20. The method of claim 19, further comprising the steps of, when left_j is equal to zero, placing Pj at the end of the list for server s and setting the value of left_j to a non-zero value not greater than the initial value for left_j.

21. The method of claim 14, wherein at least one of said servers is a central processing unit.

22. The method of claim 14, wherein at least one of said servers is a memory unit.

23. The method of claim 14, wherein each of said servers has a preemption interval Δ

t_s ≧

0, and said granting of said services is for a period not less than Δ

t_s.

24. The method of claim 14, wherein each of said plurality of processes corresponds to a respective collection of received data signals, each collection of data signals including address information about a respective destination to which said collection of data signals is to be delivered.

25. The method of claim 24, wherein each collection of data signals comprises at least one packet, and said address information comprises an address field in said at least one packet.

26. The method of claim 24, wherein each collection of data signals comprises at least one cell, and said address information comprises an address field in said at least one cell.

27. The method of claim 14, wherein access to said server by a process, P_j, to which access has been granted is preempted if another process, P_i, has an entry which appears in said list in a position nearer the front of said list than the entry for P_j.

28. The method of claim 14, wherein a process, P_j, to which access to a server has been granted is preempted if another process, P_i, has an entry in a position nearer the front of said list than the entry for P_j assumes said first status.

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.

30. The method of claim 29, wherein at least one of said servers has a preemption interval during which service by said at least one server cannot be preempted in the course of providing service to one of said processes.

31. The method of claim 29 wherein the order of said granting of services is in accordance with proximity to the front of a list of entries, each of which entries corresponds to one of said processes, said entries each including a field indicating the status of said corresponding process.

32. The method of claim 31 wherein said field indicating status indicates the runability of said corresponding process.