Method for distributing resources in a time-shared system

• US 4,481,583 A
• Filed: 10/30/1981
• Issued: 11/06/1984
• Est. Priority Date: 10/30/1981
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Mueller, Mark W.
• Primary Examiner(s): Chan, Eddie P.
• Application Number:
  US06/316,878
• Time in Patent Office: 1,103 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 710/244
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

A method is disclosed for distributing processing resources among a plurality of users of a time-shared system wherein resources are divided among various user accounts; each user assigning specific weights to the various programs (processes) in his account. A program is selected for processing in accordance with its assigned weight, the resources allocated to the account containing the process, and its recent processing rate. Programs are executed through a series of processing intervals; after each interval the priority of the executing program is lowered in proportion to the resources consumed. Priorities are recalculated after each processing interval for all programs competing for access to the resources.

Claims

1. A method for time sharing the resources of a processing machine among a plurality of accounts, each account containing processes competing for access to said resources including the periodic use of specific hardware associated with the processing machine, comprising the machine performed steps of:

assigning a separate processing rate entitlement to each account in response to performance requirements selected by each separate user, said processing rate entitlement being a measure of entitlement to access the resources of said processing machine;

allocating a share of the processing rate entitlement to the various processes within each account;

measuring the time periods during which each specific hardware is used by each process;

multiplying said time periods during which specific hardware is used with weight factors associated with each specific hardware to determine the resources consumed by each process;

calculating a processing rate for each process by dividing the resources consumed by a predetermined time interval;

calculating a priority for each process by dividing the allocated processing rate entitlement by the processing rate; and

executing the process having the highest priority.

2. The method of claim 1 wherein each process executes in a series of processing intervals, during one of said processing intervals one or more items of specific hardware are used, and after said one of said processing intervals priority is recalculated for each of the processes by repeating the steps of claim 1.

3. The method of claim 2 wherein the recalculation of processing rate further includes the step of multiplying the existing value of the calculated processing rate by a number less than unity.

4. In a system having at least one account, a method for scheduling processes for execution by a processing machine, each process being associated with an account and having an initial value of priority, each process utilizing one or more particular resources during execution, each account being assigned a processing rate entitlement in response to user selected performance requirements, and each process in the account being assigned a weight factor in response to user selected performance requirements, comprising the machine performed steps of:

apportioning the processing rate entitlement among the processes in each account in accordance with their assigned weight factors;

measuring the time interval during which a particular resource is used by each of said processes;

multiplying the time interval during which a particular resource is used and a separate numerical quantity associated with each particular resource to determine resource consumption for each process;

calculating a resource consumption rate for each process by dividing the resources consumed by a predetermined time interval;

dividing the apportioned processing rate entitlement by the resource consumption rate to determine a value of priority for each process; and

executing the process having the highest priority.

5. The method of claim 4 wherein processes are executed in discrete processing intervals, the value of priority being recalculated for each of the processes after each processing interval by repeating the steps of claim 4.

6. The method of claim 5 wherein the recalculation of resource consumption rate further includes the step of:

multiplying the magnitude of the previously calculated resource consumption rate by a number whose magnitude is less than unity.

7. The method of claim 4 further including the steps of:

calculating an average resource consumption rate as the summation of the individual resource consumption rates of all processes divided by the number of processes; and

constraining the values of priority for the various processes to a predetermined range by multiplying the values of priority by a scaling factor, said scaling factor being proportional to the average resource consumption rate of said processes.