![]() ![]() ![]() ![]() ![]() |
![]() ![]() ![]() |
![]() ![]() |
![]() |
( 4 of 4 ) |
United States Patent | 5,999,963 |
Bruno , et al. | December 7, 1999 |
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.
Inventors: | Bruno; John Louis (Santa Barbara, CA), Gabber; Eran (Summit, NJ), Ozden; Banu (Summit, NJ), Silberschatz; Abraham (Summit, NJ) |
Assignee: |
Lucent Technologies, Inc.
(Murray Hill,
NJ)
|
Appl. No.: | 08/965,934 |
Filed: | November 7, 1997 |
Current U.S. Class: | 718/104 ; 718/102 |
Current International Class: | G06F 9/46 (20060101); G06F 9/48 (20060101); G06F 009/00 () |
Field of Search: | 709/100,102,103,104,105,300 |
3648253 | March 1972 | Mullery et al. |
4286322 | August 1981 | Hoffman et al. |
4318173 | March 1982 | Freedman et al. |
4380063 | April 1983 | Janson et al. |
4475192 | October 1984 | Fernow et al. |
4616359 | October 1986 | Fontenot |
4642756 | February 1987 | Sherrod |
4779194 | October 1988 | Jennings et al. |
4916608 | April 1990 | Shultz |
4954945 | September 1990 | Inoue |
5012409 | April 1991 | Fletcher et al. |
5136708 | August 1992 | Lapourtre et al. |
5155851 | October 1992 | Krishnan |
5168566 | December 1992 | Masaru et al. |
5202987 | April 1993 | Bayer et al. |
5220653 | June 1993 | Miro |
5247675 | September 1993 | Farrell et al. |
5278828 | January 1994 | Chao |
5283639 | February 1994 | Esch et al. |
5287508 | February 1994 | Hejns, Jr. et al. |
5311423 | May 1994 | Clark |
5379428 | January 1995 | Belo |
5394547 | February 1995 | Correnti et al. |
5404521 | April 1995 | Murray |
5422879 | June 1995 | Parsons et al. |
5428789 | June 1995 | Walldron, III |
5434860 | July 1995 | Riddle |
5444707 | August 1995 | Cerna et al. |
5469571 | November 1995 | Bunnell |
5530868 | June 1996 | Record et al. |
5533009 | July 1996 | Chen |
5533020 | July 1996 | Byrn et al. |
5542088 | July 1996 | Jennings, Jr. et al. |
5598535 | January 1997 | Brech et al. |
5608906 | March 1997 | Tonouchi et al. |
5613067 | March 1997 | Brady et al. |
5629928 | May 1997 | Calvignac et al. |
5630128 | May 1997 | Farrell et al. |
5640563 | June 1997 | Carmon |
5650993 | July 1997 | Lakshman et al. |
5673404 | September 1997 | Cousins et al. |
5894560 | April 1999 | Carmichael et al. |
5903752 | May 1999 | Dingwall |
C A. Waldspurger and W. Weihl, Stride scheduling: Deterministic proportional-share resource management. Technical Report TM-528, MIT Laboratory for Computer Science, June 1995. . P. Goyal, X. Guo, and H.M. Vin, "A Hierarchical CPU Scheduler for Multimedia Operating Systems," Proc. USENIX 2.sup.nd Symposium on Operating System Design & Implementation, Seattle, WA, Oct. 1996. . P. Goyal, H. Vin, and H. Chen, "Start-Time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks," Proc. IEEE SIGCOMM '96, August, 1996. . I. Stoica, et al, "A Proportional Share Resource Allocation Algorithm For Real-Time, Time-Shared Systems," Proc. IEEE Real-Time Systems Symposium, December, 1996. . C. mercer, S. Savage, & H. Tokuda, "Processor capacity reserves: Operating system support for multimedia applications. Proc. IEEE Internat. Conference on Multimedia Comp. & Systems, May, 1994.. |
![]() ![]() |
![]() ![]() ![]() |