Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1994-06-02
2002-08-06
Oberley, Alvin (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06430592
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to computer systems, and deals more particularly with sharing of processing time of one or more processors by multiple users.
Often in a computer system, many programs or users require execution concurrently. There may be one or more processors available to execute the multiple programs. Any one processor can only execute one program or transaction at any one time. If two or more programs request execution at the same time, and there is only one processor or fewer processors than the number of programs requiring execution, the operating system must determine which program can use the one or each processor at any one time. Typically this decision is based on a relative priority of each of the programs. Typically also, programs which are in a wait state, such as those waiting for a slow I/O operation to complete, are “suspended” and therefore not eligible to compete for the processor regardless of their priority.
In addition to deciding which program can utilize the one or each processor at a particular time, the operating system must also determine how long the selected program can utilize the respective processor after it begins to execute so that other programs of equal (or perhaps lower) priority can get their turn. There are several known techniques for determining how long each program should be permitted to utilize a processor after it begins to execute. In the simplest technique, the highest priority program maintains its use of the processor until completion (or suspension). However, this may permit this program to “hog” the processor, and “starve” the other programs. In another known technique, each program which is selected for execution is given a share or “slice” of the total processor time. The shares of the programs can be equal or preferably weighted based on various factors. One known technique to weight the shares is as follows. Some of programs are defined to command an “absolute” or definite share of the total processor time, and others are defined to command a “relative” share of the remaining processor time. The absolute shares are “taken off the top” and the relative shares divide the remainder in proportion to their relative shares. For example, a first program is defined with a forty percent absolute share, a second program is defined with a one hundred relative share and a third program is defined with a three hundred relative share. In this scenario, the first program will command forty percent of the total processor time, the second program will command fifteen percent of the total processor time and the third program will command forty five percent of the total processor time.
A program may not need its entire absolute or relative share. A known technique to allocate the excess in this absolute/relative share environment is to give all the excess to the program with the highest absolute or relative share. If the excess were a small percentage of the total processor time, this known technique would suffice. However, in many cases, the excess is substantial, such as one half of the total processor time, and it may not be optimum to allocate all the excess to one program.
Accordingly, a general object of the present invention is to provide an improved system for allocating excess processor time to multiple programs or users.
SUMMARY OF THE INVENTION
The present invention resides in a computer system for allocating processor time to multiple users. A systems operator or a user specifies to the computer a share of processor time for each user. The share can be absolute or relative. The system executes users which are I/O bound with processor time less than their respective, specified share(s) by not using significant processor time on users which are waiting for an I/O operation to complete but expediting allocation of a processor to users after their respective I/O operations complete. The system executes users which are CPU bound with processor time greater than their respective, specified share(s) based on their respective shares in relation to a sum of shares of other CPU bound users but excluding shares of I/O bound users.
In accordance with another feature of the present invention, for each user there is also a specified “soft limit”, “hard limit” or “no limit”. When any hard limit user reaches its hard limit, no further allocation is made. When any soft limit user reaches its soft limit, no further allocation is made to this soft limit user if any other soft limit user has yet to reach its soft limit or any other hard limit user has yet to reach its hard limit or if there are any unlimited users. The other soft limit and hard limit users who have not yet reached their limits continue to receive extra shares until they also reach their respective limits. When all other soft limit users have reached their soft limits and all hard limit users have reached their hard limits and if there are no unlimited users, then the soft limit user with the greatest absolute share or relative share (computed as if there was no unused processing time) receives all the remaining unused processing time.
The share allocation technique of the present invention is implemented by re-positioning or offsetting each user downward in the dispatch list after the user completes each time slice. The amount of offset for a user is based on the magnitude of the absolute or relative share of the user and the current position of the user. After completing each time slice for a user located in a bottom part of the dispatch list, the user is repositioned later in the dispatch list by an offset based on a magnitude of the user's share in relation to the shares of other users located in the bottom part of the dispatch list. However, after completing each time slice for a user located in a top part of the dispatch list, the user is repositioned later in the dispatch list by an offset based on the magnitude of the user's share in relation to other users throughout the dispatch list.
The soft and hard users are limited in accordance with their specified limits by establishing a significant, minimum offset when they reach their limits. Moreover, the hard limited users are taken off a run list when they exceed their limits.
REFERENCES:
patent: 4388688 (1983-06-01), Curlee, III et al.
patent: 4481583 (1984-11-01), Mueller
patent: 4631674 (1986-12-01), Blandy
patent: 4736318 (1988-04-01), Delyani et al.
patent: 4989133 (1991-01-01), May et al.
patent: 5193187 (1993-03-01), Strout, II et al.
patent: 5291599 (1994-03-01), Cohen et al.
patent: 5325525 (1994-06-01), Shan et al.
patent: 5339425 (1994-08-01), Vanderah et al.
patent: 5448735 (1995-09-01), Anderson et al.
patent: 2236880 (1991-04-01), None
Lehoceky et al, An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems, Real Time Systems, 1995 Symp. pp 110-123.*
Sprunt et al., Exploiting Unused Periodic Time for Aperiodic Sevice Using the Extended Priority Exchange Algorithm, Real Time Systems, 1998 Symp. pp 251-258.*
Ku et al, Relative scheduling Under Timing Constraints, Design Automation conf., 1990 ACM/IEEE Conf. pp. 59-64.*
Shen et al, Resource Reclaiming in Multiprocessor Real-Time Systems, IEEE Trans. on Parallel & Distributed Syst. Apr. 1993 V:4 Issue 4 pp. 382-397.*
Tokuda et al, An Integrated Time-Driven Scheduler for the Arts Kernel, Comps. & Comm., 1989 Int'l Phoenix Conf., 1989, pp. 486-496.
Lao Sue
Oberley Alvin
Samodovitz Arthur J.
LandOfFree
System for sharing CPU time amongst multiple users does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for sharing CPU time amongst multiple users, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for sharing CPU time amongst multiple users will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2911906