System and method for scheduling use of system resources among a plurality of limited users

• US 6,438,704 B1
• Filed: 03/25/1999
• Issued: 08/20/2002
• Est. Priority Date: 03/25/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Harris, John F., Lorenc, Mark J.
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Mai, RiJue
• Application Number:
  US09/276,525
• Time in Patent Office: 1,244 Days
• Field of Search: 713/502, 713/501, 713/503, 713/400, 713/401, 713/650, 713/601, 713/600, 712/28, 712/203, 709/101, 709/102, 709/103, 709/104, 709/107, 710/58
• US Class Current: 713/502
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A computer system allocates processor time to multiple users. A systems operator or other administrator specifies to the computer a share of processor time for each user. A particular user'"'"'s CPU usage is limited to an absolute value in a ‘dispatch driven’ multiprocessing system through the use of a monitor built into an active wait routine. The mechanism used is a list of users whose CPU resource must be limited so that their consumption does not exceed the limit value. The limit list is active wait monitored to determine when a user should be removed from the list in a low load situation and thus deliver the maximum CPU usage to the user if it is available.

Claims

1. A method for scheduling use of system resources by a user, comprising the steps of:

maintaining a first clock;

maintaining a second clock;

during a dispatch process,

if there is work to do, scheduling use of system resources to said user in dispatch priority order with other users only when said user is not in wait status;

otherwise

advancing said first clock by user time; and

advancing said second clock by user time and wait time; and

during a wait process,

if there is work to do, calling said dispatch process;

otherwise,

timing wait time; and

if there is a CPU in active wait status upon said wait time exceeding a predetermined value, incrementing said first clock by said wait time and calling said dispatch process.

2. The method of claim 1, further comprising the steps of:

during a scheduler process,

determining a user share for said user;

if said uses share exceeds a predefined maximum allowed share, calculating a user offset based on said user share and a time slice adjusted for any overrun on a previous time slice;

calculating a new dispatch priority for said user equal to a current dispatch priority plus said user offset;

if said new dispatch priority exceeds said first clock by a function of said user offset, placing said user in wait status and calling said dispatch process;

otherwise, calling said dispatch process; and

during said dispatch process, upon said user completing a time slice, calling said scheduler process.

3. The method of claim 2, further comprising the steps of:

further during said dispatch process,

if said user is in wait status with a limit priority within one time slice of said second clock, removing said user from limit status.

4. A method for scheduling use of system resources among a plurality of limited users, comprising the steps:

maintaining first time of day clock;

maintaining a second time of day clock;

executing a dispatch routine;

executing an active wait routine;

executing a priority recalculation routine;

said priority recalculation routine including the steps of;

calculating a user share for a first user;

if said user share exceeds a predefined maximum allowed share, calculating a user offset based on said user share and the size of a minor time slice adjusted for any overrun on a previous minor time slice;

calculating a user dispatch priority equal to an old priority plus said offset;

if said user dispatch priority exceeds a maxfall value equal to said first clock plus a function of said user offset, and this is a limited user, and this user is being scheduled at its maximum share, then adding said user to a limit list;

otherwise, reordering said user onto a dispatch list in priority order; and

executing said dispatcher routine;

said dispatcher routine including the steps of;

if there is no work to dispatch, then executing said active wait routine;

otherwise running any priority system work; and

then

if a said user'"'"'s minor time slice just ended, executing said scheduler routine;

otherwise,

advancing said first time of day clock with user time;

advancing a second time of day clock with user time and wait time;

if a user on said limit list is within one minor time slice of said second time of daw clock, removing said user from said limit list; and

dispatching users based on dispatch list priority; and

said active wait routine including the steps;

if there is new work to run, then executing said dispatcher routine;

otherwise,

if there are users on said limit list and active wait processing has exceeded a predetermined limit, then

adding wait time to said first time of day clock; and

executing said dispatcher routine;

whereby users are added to said limit list not too early and removed from said limit list not too late.

5. A method of scheduling system resources, comprising the steps of:

prioritizing users for processor usage within boundaries defined by user minimum share assignment, a first artificial time of day clock which advances when users are consuming system resources, a high dispatch priority limit, and a low dispatch priority limit;

limiting central processor unit consumption by users to specified absolute values within said boundaries by establishing user maximum limited share assignments assigned to selected users, providing a limit list, and providing a second artificial time of day clock which advances when a user is consuming system resource and when said system resource is waiting;

determining limit list priority and when to remove from said limit list based on advancement of said second artificial time of day clock;

providing an active wait interactive continuous monitor of incoming tasks when said CPU is idle;

assigning priority to users based on maximum usage share;

placing users on said limit list when said low dispatch priority limit is exceeded;

converting time of said first artificial time of day clock to time of said second artificial time of day clock to determine duration of stay on said limit list;

recognizing when limit share users are competing for CPU resource;

recognizing when said system resource has been in a continuously active wait status for a defined interval of real time and responsive thereto updating said first artificial time of day clock and said second artificial time of day clock by wait time; and

,

removing users from said limit list for which said second artificial time of day clock value exceeds said limit list priority with substantially all of said wait time included in said second artificial time of day clock under low load conditions.

6. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for scheduling use of system resources by a user, said method steps comprising:

maintaining a first clock;

maintaining a second clock;

during a dispatch process,

if there is work to do, scheduling use of system resources to said user in dispatch priority order with other users only when said user is not in wait status;

otherwise

advancing said first clock by user time; and

advancing said second clock by user time and wait time; and

during a wait process,

if there is work to do, calling said dispatch process;

otherwise,

timing wait time; and

if there is a CPU in active wait status upon said wait time exceeding a predetermined value, incrementing said first clock by said wait time and calling said dispatch process.

7. An article of manufacture comprising:

a computer useable medium having computer readable program code means embodied therein for scheduling use of system resources by a user, the computer readable program means in said article of manufacture comprising;

computer readable program code means for causing a computer to effect maintaining a first clock;

computer readable program code means for causing a computer to effect maintaining a second clock;

computer readable program code means for causing a computer to effect during a dispatch process,

if there is work to do, scheduling use of system resources to said user in dispatch priority order with other users only when said user is not in wait status;

otherwise

advancing said first clock by user time; and

advancing said second clock by user time and wait time; and

computer readable program code means for causing a computer to effect during a wait process,

if there is work to do, calling said dispatch process;

otherwise,

timing wait time; and

if there is a user in wait status upon said wait time exceeding a predetermined value, incrementing said first clock by said wait time and calling said dispatch process.

8. A system for scheduling use of system resources by a user, comprising:

a first clock;

a second clock;

a dispatch process for;

if there is work to do, scheduling use of system resources to said user in dispatch priority order with other users only when said user is not in wait status;

otherwise

advancing said first clock by user time; and

advancing said second clock by user time and wait time; and

a wait process for;

if there is work to do, calling said dispatch process;

otherwise,

timing wait time; and

if there is a user in wait status upon said wait time exceeding a predetermined value, incrementing said first clock by said wait time and calling said dispatch process.

9. The system of claim 8, further comprising:

a scheduler process for;

determining a user share for said user;

if said user share exceeds a predefined maximum allowed share, calculating a user offset based on said user share and a time slice adjusted for any overrun on a previous time slice;

calculating a new dispatch priority for said user equal to a current dispatch priority plus said user offset;

if said new dispatch priority exceeds said first clock by a function of said user offset, placing said user in wait status and calling said dispatch process;

otherwise, calling said dispatch process; and

said dispatch process, upon said user completing a time slice, calling said scheduler process.

10. The system of claim 9, further comprising:

said dispatch process further for;

if said user is in wait status with a limit priority within one time slice of said second clock, removing said user from limit status.

11. A method for scheduling use of system resources by a user, comprising the steps of:

maintaining a first clock;

maintaining a second clock;

during a dispatch process,

if there is work to do, scheduling use of system resources to said user in dispatch priority order with other users only when said user is not in wait status;

otherwise

advancing said first clock by user time; and

advancing said second clock by user time and wait time;

during a wait process,

if there is work to do, calling said dispatch process;

otherwise,

timing wait time; and

if there is a CPU in active wait status upon said wait time exceeding a predetermined value, incrementing said first clock by said wait time and calling said dispatch process;

during a scheduler process,

determining a user share for said user;

if said user share exceeds a predefined maximum allowed share, calculating a user offset based on said user share and a time slice adjusted for any overrun on a previous time slice;

calculating a new dispatch priority for said user equal to a current dispatch priority plus said user offset;

if said new dispatch priority exceeds said first clock by a function of said user offset, placing said user in wait status and calling said dispatch process;

otherwise, calling said dispatch process; and

during said dispatch process, upon said user completing a time slice, calling said scheduler process.

12. The method of claim 11, further comprising the steps of:

further during said dispatch process,

if said user is in wait status with a limit priority within one time slice of said second clock, removing said user from limit status.

13. A system for scheduling use of system resources by a user, comprising:

a first clock;

a second clock;

a dispatch process for;

if there is work to do, scheduling use of system resources to said user in dispatch priority order with other users only when said user is not in wait status;

otherwise

advancing said first clock by user time; and

advancing said second clock by user time and wait time; and

a wait process for;

if there is work to do, calling said dispatch process;

otherwise,

timing wait time;

if there is a user in wait status upon said wait time exceeding a predetermined value, incrementing said first clock by said wait time and calling said dispatch process;

a scheduler process for;

determining a user share for said user;

if said user share exceeds a predefined maximum allowed share, calculating a user offset based on said user share and a time slice adjusted for any overrun on a previous time slice;

calculating a new dispatch priority for said user equal to a current dispatch priority plus said user offset;

if said new dispatch priority exceeds said first clock by a function of said user offset, placing said user in wait status and calling said dispatch process;

otherwise, calling said dispatch process; and

said dispatch process, upon said user completing a time slice, calling said scheduler process.

14. The system of claim 13, further comprising:

said dispatch process further for;

if said user is in wait status with a limit priority within one time slice of said second clock, removing said user from limit status.