US006785889B1

(12)

United States Patent
Williams

(10) Patent N0.: US 6 9 785 9 889 B1 (45) Date of Patent: Aug. 31, 2004

(54)

SYSTEM AND METHOD FOR SCHEDULING
BANDWIDTH RESOURCES USINGA KALMAN ESTIMATOR WITH ACTIVE
FEEDBACK

6,003,062 A * 12/1999 Greenberg et a1. ........ .. 709/104
6,105,053 A * 6,189,022 B1 *
6,263,358 B1 *

8/2000 Kimmel et a1. ..... .. 2/2001 Binns ............. ..
7/2001 Lee et a1. .... ..

709/105 709/100
.. 709/100

Inventor:

Peter Williams,

* Cited

examiner

(73) Assignee: Aurema, Inc., Cupertino, CA (US)
_ _ _ _ Primary Examiner—Jack B. Harvey

( * ) Notice:

SubJect to any disclaimer,~ the term of this Patent 15 extended or adlusted under 35 U'S'C' 154(k)) by 816 days‘

Assistant Examiner_Hai V_ Nguyen (74) Attorney, Agent, or Firm—Michael Hetherington; Nick Ulman; Woodside IP Group

(21) Appl. N0.: 09/596,026
(22) Filed: (51) Int C17
(52) U
' '

(57)
G06F 9/00
709040
’ ’ 718/106’

ABSTRACT

Jun. 15, 2000

A community of collaborative software agents Works together in a domain to provide functionality such as pro vision of communications services or control of a chemical process. A scheduler is built into each collaborative agent

Ci """"""""""""
' """"""""""" "

(58)
(56)

Field of Search

"""""""""
’

709/104 229 718/104; 106’
’

Which schedules tasks allocated to that particular agent and tasks sub-allocated by the agent. The scheduler has a mecha nism for over-booking tasks for any one agent. It can also

References Cited
U.S. PATENT DOCUMENTS
5,881,238 A * 3/1999 Aman et al. .............. .. 709/226

make tentative booking Which can be overWritten of timed out. 7 Claims, 11 Drawing Sheets

11 D2

Scheduling Process: / Running, sleeping, blocked wailing,

j

etc.
Accounting Entiilv Tracking
1 1 U4

4}

\
. ,

4
Calculate Entity

ussgsgrgitecgiam based on emily moving avg model per entity for

Hierarchy Resource
Usage
~

1 1 Us
1 11 2

calculating usage metrlc 1105

|-_a %

2
Set entity priorities i

\- Calcuate Desired Emity Usage Rates based on Allocation Policies for Entities! Group Hierarchy Shares and

run queue

1c“,

111U

Ertltlernents

ita
'

/
~

a?
(ll 2:

Recalculate entity relative priority based on usage ratesl usage metric and allocated resource

&
'_‘ I

entitlements

Feedback Factor

The Kalman Loop

U.S. Patent

Aug. 31, 2004

Sheet 1 0f 11

US 6,785,889 B1

Process State Transitions

(high level) select create

Runnable ilexmm gil

wakeup

Sleeping

Fig 1

U.S. Patent

Aug. 31, 2004

Sheet 2 0f 11

US 6,785,889 B1

Process 1 Demand
P1
Running [_ —' — '

Runnable

. sleeplng _. . . . .

I
_ _ ,. . . , _ . , . , . , . , . , . , . I . _ . _ . I . _ ._

time 5
Exits

- = Passes quickly through

Runnable State

Fig 2

U.S. Patent

Aug. 31, 2004

Sheet 3 0f 11

US 6,785,889 B1

Process 1 and 2 States
- = Passes quickly through

Running;
Sleeping

81

P1 Delayed

Runnable State

Runnable

Runnable Running; L
P2

(CPU Idle

KL

P2 Delayed until P1 is

Preempted

Fig 3

U.S. Patent

Aug. 31, 2004

Sheet 4 0f 11

US 6,785,889 B1

CPU Activity State Transitions

(high level) ream tion

w

Running ‘ Scheduling a Process ’

resume

Fig 4

U.S. Patent

Aug. 31, 2004

Sheet 5 0f 11

US 6,785,889 B1

Accounting Entity Hierarchies (a) (b)

UIG = User in Group

UIA = User using Application

UIGZA = User in Group using Application

Fig 5

U.S. Patent

Aug. 31, 2004

Sheet 6 0f 11

US 6,785,889 B1

Seven Processes - Two Users - Two Groups

Users:
RUEs: /

u1;e1
Procs: P1 U1 G1 P2 U1 G1

U2:G1
P3 U2 G1

FU1:G2
P4 u1 G2 P5 u2 G2 P6 U2 G2 P7 U2 G2

U.S. Patent

Aug. 31, 2004

Sheet 7 0f 11

US 6,785,889 B1

Process State Trajectories

created

h'gh

/

Running

exit

U.S. Patent

Aug. 31, 2004

Sheet 8 0f 11

US 6,785,889 B1

Scheduling Feedback Loop run rate measurements pom“,r

Cuntnlled System:
Prueesses - running, C??trlJlIBr.

sleeping, waiting to run.

Scheduler

control alterations to match observed run rates to those

specified by the policy

Fig 8

U.S. Patent

Aug. 31, 2004

Sheet 9 0f 11

US 6,785,889 B1

19

21

25

25

2'?

29

58

:15

58

Fig 9

U.S. Patent

Aug. 31, 2004

Sheet 10 0f 11

US 6,785,889 B1

1IDDE 1004

WEIZ

Fig 10

U.S. Patent

Aug. 31, 2004

Sheet 11 0f 11

US 6,785,889 B1

1 1 I12

Scheduling Process:

If

Running, sleeping, blocked waiting, —7l.—— -——)‘ etc.

}

Accounting Entitiy Tracking
1 1 U4

Usage Predictor based on entity

Estimator:

Hierarchy Resource
Usage
-

_Calculate Entity

/ moyingentitymodel avg for per
1 1 Us calculating usage metric
C 3

1 1 U6

1112
% 3
Set entity priorities ir run queue P g

\\ Calcuate Desired
Entity Usage Rates based on Allocation

Policies for Entities! Group Hierarchy Shares and
11 1 El
Entitlements _

e %

O m

/ to allocated resource

e (D

5
:o

Recalculate entity relative _) priority based on usage rates, usage metric and entitlements 9,

Feedback Factor

The Kalman Loop

Fig. 11

US 6,785,889 B1
1
SYSTEM AND METHOD FOR SCHEDULING BANDWIDTH RESOURCES USING A KALMAN ESTIMATOR WITH ACTIVE FEEDBACK
REFERENCE TO COMPUTER PROGRAM LISTING APPENDIX

2 particular virtual processor and the scheduling characteris tics are resultants of the scheduling of the virtual processor.

The OS community has developed many optimal sched uling algorithms, but all algorithms are optimal only for certain Workloads. There is currently no single solution that

?ts every system need. General-purpose operating systems face the problem of developing schedulers that are general enough to solve most needs, yet extensible enough to handle

speci?c Workloads.
There are many different algorithms for choosing the next
10

The following computer program listing including Uni

versal Modeling Language (UML) diagrams shoWing instructions, regulation of Work ?oW, the detailed design of the scheduler and relationships betWeen objects in the com puter program is submitted on a compact disc and is incor

process to run. TWo of the most common scheduler algo

rithms are First-In-First-Out (FIFO) and Round Robin (RR).
FIFO runs each process until its completion and then loads the next process in the queue. FIFO can have negative affects on systems When processes run for an extended time, squeeZe critical resources that otherWise keep the system stable to the point of no return, and then crash the system or initiate a sequence of events to crash the system. Round Robin schedulers alloW each process at a given priority to run for a predetermined amount of time called a quantum. When the process has run for the allotted time

porated herein by reference:
15

NAME

CREATION DATE

SIZE (bytes)

Appendix A

Dec. 30, 2003

4.46 MB

quantum, or if a higher priority process becomes runnable, the scheduler halts the process and saves its state. It is then placed at the end of the process queue and the next process

BACKGROUND OF THE INVENTION

1. Field of the Invention The ?eld of the invention relates in general to a scheduler

25

for allocating digital device bandWidth resources. More particularly, the ?eld of the invention relates to a system and

is started. This may be the most optimal solution if the time quantum is longer than the average runtime of a process and the only resource needed is CPU bandWidth. These are very unlikely to be the case in the typical process load mix and therefore the need for a better algorithm to ?ll all require ments and to smooth out the Workload over available

method for allocating and scheduling digital device band
Width resources among users and groups of users by using an active feedback estimator Which guarantees a system

resources. Also, context sWitching betWeen different pro cesses has a price and We much consider the overhead in

bandWidth requirement among competing users and aggre gate user groups.

context sWitching time of changing processes in conjunction With the more complex scheduling algorithms. OS developers have created multilevel queue scheduling to meet the needs for different algorithms at different times.
35

2. Background Computer Operating Systems are groWing in complexity.
Most neW computers and devices using computational devices are performing many different tasks simultaneously. This sharing of resources affects machine performance and user satisfaction. Typically the operating system (OS) is responsible for scheduling When each process runs. When a process has reached its allotted time slice, or blocks for some reason, the OS saves its state and runs the next runnable

Multilevel queue systems have several algorithms used simultaneously. Each queue is assigned a priority over the next queue. The scheduler starts at the highest priority queue, implements the queue’s algorithm until no runnable processes remain, and then proceeds to the next priority queue. One queue could use FIFO With another uses RR.

40

When implementing a conventional real-time scheduler, a

inheritance protocol. A process that “oWns” a resource runs Which handle even more processes simultaneously. This in 45 at the priority of the highest priority process that is aWaiting turn requires more programs demanding more system that resource requested by a higher priority process. When

process in the process queue. This gives the appearance of many different programs running simultaneously on a single processor. This is currently extended to multiple processors,

problem knoWn as priority inversion frequently arises. This occurs When a higher priority process is blocked Waiting for a resource locked by a loWer priority process. This problem

has only partial solutions. One is by implementing a priority

resources running simultaneously.

the lock is released, the higher priority process becomes runnable and pre-empts the current process. This means that

The tWo main process scheduling classes are real-time and time-sharing. Current process schedulers have a basic

the algorithm selected can affect the performance of the

overall goal; to make the “system” more productive. The

application, and choosing the right algorithm can improve the system performance. What is needed is a system for setting priorities and quanta Which are more likely to be the ones needed for the type of job mixes, users and applications Which are presently emerging; and Which Will provide higher performance and more consistant service.

achievement of that goal requires the balancing of the

folloWing different requirements: allocate a fair share of CPU time to each process;

keep the CPU busy 100 percent of the time; minimiZe the response time for time sensitive processes;
55

minimiZe total job completion time; maximiZe total number of jobs per time unit.
To achieve this balance, schedulers make some assump tions about the type of processes that are running. The

Whatever algorithm is used, changing the scheduling class of a server application, can guarantee that the server

application Will run before other applications and thus

improve responsiveness for that particular application.
HoWever, this does nothing to guarantee that a particular application Will only consume a speci?ed portion of the

default system scheduler may frequently not be adequate to

suit the application. Many scheduling algorithms and their implementations have been developed over the years to shore up de?ciencies in attempts to build better schedulers. Some operating systems use a tWo-level thread implementation, Where threads Within a process are ?rst 65 scheduled to a virtual processor Which in turn are scheduled on the physical processors. Thus, the threads are bound to a

CPU load, only that the application Will be treated prefer entially in allocating resources. What is needed is a Way to track historic usage of an application or group of applica tions and guarantee that over a certain time period, the use of bandWidth resources is precisely that Which Was set initially, unless there is an available abundance of bandWidth, and no such constraints need be applied.

US 6,785,889 B1
3
Process Schedule Con?guration
The general purpose OS Will not function if the scheduler is not con?gurable or even modi?able. Most OS vendors

4 the eXtreme case, there may be no users because everyone Who Wants to use the machine has an empty budget. For an

have compensated for this problem in several Ways. Some provide utilities to vieW the default scheduling classes and alloW changing the process priorities and quanta. In UNIX, these types of utilities have names like “nice”, “schedi setscheduler” or “priocntl”. Special privileges are generally needed to run a process at a higher priority or change the scheduler for a process from the real-time class or the
10

in-house machine, this does not make sense. Worse still, this conventional method can generate substantial administrative overhead as users seek eXtra allocations. The number of shares allocated to a user is, essentially, an administrative

time-sharing class. These generally manipulate the real-time dispatcher parameter table or time-sharing dispatcher parameter table. Servers and computers in general have groWn bigger and more poWerful.
Conventional solutions have thus groWn disadvanta
15

decision. HoWever, in a situation Where independent orga niZations share a machine, the shares that should be allo cated to individual users depend both upon the entitlement that their organiZation has and on the individual’s entitle ment Within the organiZation.

Additionally, charges in Fair Share (FS) are de?ned by the relative costs of different resources. For eXample, FS asso

ciates a charge With memory occupancy, another charge With systems calls, another With CPU use and so on. This is

geously larger in granularity and they lack the precision to handle the large resources that they command. The granu

another difference betWeen FS and conventional schedulers

larity of the changes can very often make precise goal achievement impossible With these solutions. What is needed are methods to alloW users increased access to and

Which de?ne a process’s scheduling priority only on the process’s consumption of CPU time. In FS, CPU scheduling priority is affected by total resource consumption.
There are three types of activity at the process level: activity associated With the activation of a neW process;

more precise control over the allocation of CPU resources

than is provided by the conventional “nice” and “priocntl” mechanisms. What is also needed are CPU and resource

the regular and frequent adjustment of the priority of the current process, and

bandWidth scheduling utilities, applying the extension of the concept of share allocation doWn to threads and processes, thereby enabling users more precise control over the allo cation of CPU access to these entities than is provided by the
25

the regular, but less frequent decaying of the priorities of all processes. The ?rst activity occurs When a process relinquishes control of the CPU, or When the active process is interrupted for some reason, and at the regular times that the scheduler usurps the currently active process to hand control to the highest priority process that is ready to run. Next is the adjustment to the priority of the current process, Which de?nes the resolution of the scheduler. This ensures that the CPU use of the current process decreases (Worsens) its

conventional “nice” and “priocntl” mechanisms.
Rescheduling is done to optimiZe resources and to increase performance for a particular job load miX or to

improve the performance for a particular application. The changes are often done at the eXpense of other jobs in the miX, as they often take Whatever resources are not being

used by the preferentially treated application. As stated

above, selecting the right scheduling algorithm for the particular situation is critical in satisfying competing needs and objectives. Managing resources fairly With overly con stricting requirements, is a dynamic function currently done
With static methods. What is needed is a Way to improve control of the scheduler to manage bandWidth resources and
35

priority. Finally, there is the regular decaying of all process priorities, Which must be done frequently compared to the user-level scheduler, but at a larger time interval than the scheduler’s resolution.

Priority Adjustment in FS
40

provide precise mechanisms Which are capable of more

closely tracking load requirements.
Fair Share Schedulers

At the ?nest resolution of the scheduler, the current process has its priority increased by the usage and active process count of the user Who oWns the process. Typically,

schedulers increase the priority by a constant. Intuitively, one might vieW the difference betWeen FS and typical schedulers as folloWs:
45

Fair Share schedulers emerged in the 1980’s to provide a more equitable approach to dispensing system resources to a miX of users and groups of users. This led to several

A typical scheduler adjusts the priority of the current process by pushing it doWn the queue of processes by a constant amount. In contrast, FS pushes the current process doWn the queue by an amount proportional to the usage and number of active processes of the process’s oWner, and

changes in approach to Time Sharing (TS) schedulers.
While it is the norm for schedulers to use decayed CPU

usages, Fair Share’s application of decayed resource usage in charging Was a departure from traditional approaches. When a machine Was solely for in-house use, the only need for a raW (undecayed) resource consumption tally is in

inversely proportional to the square of that user’s shares.

Thus, processes belonging to higher usage (more active) users are pushed further doWn the queue than processes

monitoring machine performance and throughput and to observe patterns of user behaviour. The decayed usage is also normaliZed by the user’s shares. One might vieW this as making the machine relatively cheaper to users With more shares. In essence, Fair Share schedulers attempt to keep the actual machine share de?ned by normaliZed usage the same as the machine entitlement de?ned by shares. From the user’s point of vieW, Fair Share gives a decreased response to those Who have utiliZed more than their fair share of resources. Thus, users see that as their normaliZed usage
55

belonging to loWer usage (less active) users. This means that a process belonging to a user With high usage takes longer to drift back up to the front of the queue. The priority needs longer to decay to the point that it is the loWest.
FS also needed users to be able to Work at a rate

proportional to their shares. This means that the charges they incur must be alloWed to increase in proportion to the square of the shares (Which gives a derivative, or rate of Work done,

proportional to the shares). This static formula approach also takes account of the number of active processes (processes on the priority queue) for the user Who oWns the current process. This Was necessary since a priority increment that

increases, their response becomes Worse. (This assumes

alloWance is made for machine load.) This approach con trasts With conventional charging and scheduling systems that schedule processes equally. In the ?Xed-budget model, the users Who consume their fair share, by emptying their budgets, get no resources, even if resources are available. In

involved just usage and shares Would push a single process
65

doWn the queue far enough to ensure that the user gets no more that their fair share. If the user has more than one active process, FS needed to penaliZe each user to ensure

US 6,785,889 B1
5
that the user’s share is spread between them and We do this

6 demand equivalent of a larger less compact computing system employing a less ef?cient scheduler or loosely

by multiplying the priority increment by the active process count. This is the crux of the Share mechanism for making long term usage, over all resources that attract charges, affect the user’s response and rate of Work.

coupled schedulers.
SUMMARY OF THE INVENTION

Depending on the priority queue length, FS process priorities can be small integers and so cannot be used

An aspect of the invention provides an implementation of a digital device resource scheduler Which determines the

directly. Such process priorities need to be normaliZed into a priority range that is appropriate for real process priorities. In addition, Where the range in priority values is quite small,
FS must ensure that the normaliZation procedure does not

relative priority to be used When allocating resource service time to resource using entities.
10

alloW a single very large Share priority value to reduce all other normaliZed priorities to Zero. To avoid this, FS de?nes a bound on the Share priority. This is calculated in the

process-level scheduler. The FS priority bound does, some What unfairly, favor very heavy users. HoWever, the heavy users suffer the effects of their sloWly decaying large usage and they are treated more severely than everyone else.

15

The priorities produced by the scheduler can be used to increase the usage of entities that are receiving less than their entitlement and to decrease the usage of entities that are getting more than their entitlement. Provided that entities have suf?cient demand to use their entitlement, the sched uler distributes resources fairly among entities according to

their entitlement. An entity’s usage may be calculated using Kalman ?lter techniques. Separate evaluations may be made depending on Whether the entity has been receiving units of the resource. In this case, the decay and groWth terms are

The Fair share schedulers try to apply “fairness” by assigning priorities on historical usage of a process. The

totally independent of each other. The only information that may need to be retained for each entity is the value of the usage metric for that entity and the time at Which it Was last updated. Shares may be allocated to oWners of the entities as Well as the entities themselves. Thus, an entity’s effective shares are adjusted by the ratio of the number of shares held by the oWner that are allocated to that entity, to the total number of shares held by that oWner. The shares allocated to individual entity are noW effectively draWn from a separate pool of shares for each oWner. Shares may be allocated to groups of oWners, With or Without the allocation of shares to individual oWners.

problem is that those Fair share schedulers employ less than robust methods in using the measured historical usage and therefore err considerably in the setting of process priorities.
What is therefore needed is the use of a resource usage rate measure model the can estimate future usage and compare

that directly With entitlements based on reservations and shares.

25

Recent market changes, advances in general computa tional devices and groWth in market applications have also created the folloWing needs Which are not adequately met by conventional schedulers: Guarantees must be provided to consumers When it is desired to ensure that resource use is fairly shared among

An aspect of the invention also provides the ability to dynamically monitor and control a computer’s critical sys tem bandWidth resources such as CPU, Real & Virtual
35

clients according to the level of service that they have

purchased.
NeW Wireless applications and increased use of time based and bandWidth resources demand a greater level of system control over bandWidth resource allocation.

Memory, BandWidth Allocation,or the like. Unlike passive systems, the invention scheduler continually and automati cally compensates for changes in system usage/misuse in real time. An aspect of the invention directly alters the behavior of the Operating System to actively manage and change, rather than passively monitor and report, the precise

Therefore, What is needed is an improved system and method for balancing the foregoing additional needs in a scheduling process for managing resource usage. Preferably, such a scheduling system Would alloW the sharing of system bandWidth type resources on modern computer servers in neW market applications Which demand dedicated resources

40

allocation of CPU and other resources to de?ned users,

collections of users, and applications.
BRIEF DESCRIPTION OF THE DRAWINGS

Without robbing other system users. What is also needed is such that the increased granularity of control can provide a

These and other features and advantages of the present

an increased level of system control over resource allocation 45 invention Will become more apparent to those skilled in the

more equitable distribution of designated bandWidth resources to processes across users and groups of users.

Preferably, such implementations Will be Well de?ned and have a Well behaved mathematical basis.

art from the folloWing detailed description in conjunction With the appended draWings in Which: FIG. 1 shoWs a typical computer operating system process state transition diagram according to an aspect of the inven

tion;
FIG. 2 shoWs the unobstructed state transitions timing diagram for a process in accordance With an aspect of the

Although computing devices are becoming more poWer ful and need to managed differently betWeen user groups, as

With most operating systems and schedulers, bandWidth resource Waste occurs if the job mix is not in tune With the

invention;
55

scheduling algorithm. What is needed is a Way to set priorities to satisfy demand in a manner Which Will not starve other processes and Will not Waste CPU cycles or other bandWidth resources.

FIG. 3 shoWs a possible timeline for process P1 and P2 in competition for a CPU according to an aspect of the inven

tion;
FIG. 4 is a high level diagram of the CPU activity of the state transitions; FIG. 5 is a simpli?ed block diagram illustrating the

With the increase in computing poWer also comes shrink ing hardWare demands With the need to support larger more

complex applications and application combinations. For example, the merging of PDAs With cell phones, GPS, locators, music, radio, Wireless apps, TDMA/CDMA, or the like. These trends demand more ef?cient usage of sophisti cated applications Working in tandem. What is needed is a method to generate more usage out of a computing system 65

structure policy hierarchies;
FIG. 6 is a simpli?ed diagram illustrating a simple

accounting entity hierarchies example;
FIG. 7 is a simpli?ed diagram example illustrating the possible state trajectories to and from the scheduler run queue;

With various bandWidth resources, thereby providing a Way for a smaller, more compact computing system to meet the

FIG. 8 is a high level block diagram illustrating the

scheduling feedback loop;

US 6,785,889 B1
7
FIG. 9 is graphical representation illustrating process run rates parametrically;
FIG. 10 is a usage metric curve chart shoWing a family of

8
The type of high level entities among Which fair sharing could be implemented is quite diverse and includes users, projects, processes and entity groups. In another aspect, as currently envisaged, it concerns a method of determining the relative priority to be used When allocating schedulable resources to an oWner’s share holding entity, by calculating:
(1) an entity’s usage as the number of the resources

moving averages made With calculations using an aspect of

the invention;
FIG. 11 shoWs the Kalman active feedback loop that an aspect of the invention scheduler uses to calculate the relative priorities of run queue entities.
DESCRIPTION

indivisible units (ticks) that the entity is receiving per unit of time, that is a number betWeen Zero and the number of indivisible units that are available for con

The invention is concerned With the component of a “bandwidth” resource scheduler that queues the “direct” consumers of that resource for access to it. BandWidth

sumption at each indivisible instant of time, (2) the entity’s entitlement as a ratio of the product of the number of indivisible units that are available for con

resources are typi?ed by a resource management mechanism that grants exclusive access to the resource for some period 15 of time to “direct” resource consumers. There are tWo types of resource consumer. “Direct” resources consumers and “indirect” resource consumers.

sumption at each indivisible instant of time and the number of shares held by that entity at that time, to the total number of shares held by all live entities at that time, that is a number betWeen Zero and the number of indivisible units that are available for consumption at

When applied to CPU cycles, threads, or processes depend ing on the system, are “direct” consumers of CPU cycles. Users are an example of “indirect”, via their threads and processes, consumers of CPU cycles. An aspect of the invention alloWs fair sharing of access to the resource amongst “indirect” consumers as Well as
20

each indivisible instant of time, and (3) the entity’s priority, at instants of time When there are more active entities than there are units available for

consumption, in ascending order of their ratio of usage to entitlement, at that time.
Context
A typical computer system contains of one or more

“direct” consumers. It does this by controlling the ordering of the consumer queue and in some cases, the length of access granted on each occasion.

In this context, fair sharing does not necessarily mean

processors (CPUs), netWork bandWidth, main memory, other resources and one or more processes. At any moment in time
30

equal sharing but incorporates the concepts of “reservations” and “shares”. A “reservation” alloWs the allocation of ?xed proportions of the resource to high level, indirect, consum ers. “Shares” are used to allocate the remaining resource, after “reservations” to other consumers on a proportional basis. “Shares” may be allocated to consumers at all levels and are hierarchically nested ie a “direct” consumer’s shares entitle it to a proportion of its immediate oWner’s 35 shares and so on.

a CPU can only be performing Work by executing the instructions of a particular process. Each instruction takes a

?nite duration to perform. It requires an overhead elapse of time to change from having a CPU Work for one process to

Working for another process, therefore it is normal to alloW a process to use a CPU for a continuous run of instructions

so that the scheduling overhead is small compared to the

useful Work performed.
In a TS computer system, there can be many more

As the resources are generally ephemeral in nature and

valuable, When an entity is not generating suf?cient demand to use its “reservation” or “share” the unWanted resource

access is distributed amongst other entities in proportion to their “reservations” or “shares” so that there is no Wastage of the resource.

40

processes than CPUs, and yet it is desired that all processes should be able to make steady progress through their intended Workloads. One factor, Which assists in solving the

problem of competition of the processes for CPUs, is that sometimes processes need to Wait for an external event. Some examples of this are: delivery of a result to or from
45

An Embodiment of the Scheduler

The folloWing embodiments of the invention are generic, and gloss over certain details of integration into speci?c operating systems. The invention scheduler has been inte

another process, human action at a keyboard or other input device, the elapse of an intended time delay, the arrival of a speci?c date and time, the transmittal of data to or from an

external destination (screen, netWork, disk). A second factor involves perception: if a process is alloWed to make progress in a rapid sequence of short bursts then this can appear to be continuous progress provided We don’t look too closely and just regard the average rate of progress over a suf?ciently

grated into several such operating systems and tested With excellent results. Aspects of the invention scheduler have proven to be superior to the existing schedulers in the areas for Which they Were designed to excel. For purposes of the
50

folloWing invention embodiments hoWever, applications are ignored. Threads, also knoWn as lightWeight processes
(LWPs), as the schedulable entities are likeWise ignored in

long interval. Processes undergo state changes in their managed progression over the course of performing their primary objective While in a particular hardWare environ
55

the description of the folloWing invention embodiments, but it should be noted that the Workings Would be similar and their application as part and parcel in the invention provide a higher granularity of controlling processes, Which is not possible in some existing schedulers. In all the arrangements described the basic fair sharing is done at the entity level rather than the oWner level and, if it

ment. These typical high level state transitions are shoWn in FIG. 1. A process, Which never needs to Wait, is said to be

CPU-bound, it exhibits a demand of 1.0, and if given unobstructed access to a CPU it Would use that CPU at 100%

capacity continuously.
60

is required, fair sharing amongst higher level entities is achieved by modifying the entity level fair sharing. The resulting scheduler is very ?exible, alloWing different types of sharing to be achieved by a single scheduler. Additionally, fair sharing amongst high level entities can be short term, long term or both. The selection betWeen Which type of fair sharing is in force can be made on a running system.
65

A process Which sometimes Waits (sleeps) for events exhibits a demand, Which ranges from 0.0 to 1.0 depending on the frequency, regularity, and duration of those Waits. Consider the occupation CPU by such a process: instantaneously, While it is running it has a demand of 1.0 and While sleeping a demand of 0.0; suppose, for example it

does a perfectly regular cycle of running for 68 mS alter nated With a sleep of 32 mS, if We inspect the run/sleep state

US 6,785,889 B1
10
enough times during any continuous 100 mS We Will con clude that process has an average demand of about 0.68

(equally spaced or randomly selected sample points Will give, statistically, the same result) and from the information given it can also be said that the 100 mS-average demand in this case is exactly 0.68. The same 0.68 demand Will also be

interrupted process hoWever it is often counted as Running time for that process. We can mostly neglect the Interrupt state except that it is the means by Which preemptions are

performed.
FIG. 2 shoWs the unobstructed state transitions timing diagram for a process, P1. Demand is either 1 or 0. This timeline shoW the demand curve for process P1. Notice that P1 has an unusually long burst of continuous demand at one

found if any sufficiently long duration of cycles is sampled
(equally or randomly)—provided the duration is sufficient that any discrepancy due the partial ?rst and last cycles sampled is dominated by the number of complete cycles betWeen them. If multiple processes are alloWed to compete for use the same CPU, as in a TS system, there is an opportunity for each process to run While other processes are sleeping.

point. This simple timeline for one process basically shoWs
10

the demand load as a process sWitches from non-running to

running states. This process changes dramatically as other processes, “the mix”, are added to the run queue, the

“runnable state”. The delays Which are introduced by the

scheduler to produce equable sharing among runnable pro cesses are also instrumental in distributing Work among processes and available resources. These delays can come in

HoWever, it is not usually the case that the run/sleep cycles Will mesh perfectly—at times they Will all be sleeping and the CPU is idle, at other times multiple processes may become ready to run (runnable) but each runnable process cannot resume running immediately if the CPU is already

the form of interrupts, sleep request, i/o requests or quantum expiration state changes. SWitching processes among the states also carries a system burden and therefore system cost. Some available resource bandWidth Will be Wasted thru under utiliZation While others Will not be able to service demand fast enough. It can be appreciated that a scheduler

occupied they Will be delayed and hence Will only complete their Work at a sloWer average rate than if unobstructed.

Unless special action is taken, any CPU-bound processes or

processes Which have appreciably long bursts of continuous

running can greatly impair the provision of steady progress to other processes.

that can anticipate the myriad of factors to keep processes serviced and running Without thrashing around betWeen resources and processes Will produce a system Which is
25 more efficient and more responsive.

TS systems address this problem by imposing some upper limit (the time slice quantum, it may vary depending on circumstances) such that a process is preempted, and removed from control of a CPU if it runs continuously for more than a quantum so that other runnable processes (if

FIG. 3 shoWs a possible timeline for process P1 and P2 in competition for a CPU. It could be that P2 created P1. During a time When P1 in running, P2 also become runnable

any) may also have up to a quantum duration of running.

but is delayed until P1 can be preempted. As shoWn by the previous demand curve in FIG. 2, P1 Would continue running but is noW delayed While P2 has a turn. Once P2

the event that P1 has exited, When P1 exits P2 is again made processes Which one Will be given a quantum next, the more important processes may receive CPU at a rate averaging 35 runnable, runs and exits. closer to their unobstructed demand than loWer importance CPUs processes. Conventional scheduling can be vieWed in the context of CPU function. FIG. 4 is a high level diagram of the CPU Processes or Schedulable Entities
Aprocess is a collection of memory containing data and instructions for operating upon that data. A process has a lifecycle: it is initially created by the actions of usually some other process, it then alternately runs and sleeps, until eventually it exits. The exit may be volun tary because all Work for this process is complete, due to an error condition caused by the process, or by the action of another process. The process is usually created in a runnable state. When a CPU is available it Will be selected to run. While running
40

TS systems usually also associate an importance rating (niceness) With processes so that by varying the quantum and/or by making biased choices from among runnable

goes to sleep, P1 completes the long burst of usage then continues normally. MeanWhile P2 is Waiting, perhaps for

activity of the state transitions. For this simple embodiment, interrupt states are not shoWn. When certain events occur, a

scheduling decision must be made: for example, in the Running a Process state, the current process using the CPU may go to sleep, or yield the CPU. Alternatively, control of the CPU may be preempted. From the Idle state, one or more
45

processes are made runnable during interrupt processing. Scheduling examines the state of the previously running process (if any) and any currently runnable processes. The scheduler then does the folloWing: continues running the previous process, return to the Idle state, or sWitches control of the CPU to a different process to run. This is the standard

the process may yield use of the CPU by exiting (upon request, or demand) or may go to sleep. While sleeping, some external event triggers the Wakeup, Which is transition to the runnable state. The process generally cycles around

approach. An embodiment of the invention Which is described in greater detail beloW takes a different approach in deciding Which process Will run next.

from Running to Sleeping to Runnable spending time mainly Running or Sleeping, or delayed in the Runnable state if another process currently has the CPU. The Inter rupted state is transient: While a process is running it may be necessary for the system to temporarily use the CPU for a feW moments to do actions such as updating a timer or

Dispatcher
In a TS system, the dispatcher is responsible managing the details of giving processes control of CPUs; for monitoring the duration of time spent running; for Wresting the CPU from CPU bound processes at the end of a time slice

completing a disk i/o; although the execution of process instructions is suspended they Will be resumed as soon as the

quantum; and for selecting Which runnable process Will be run on a CPU When it becomes available. The dispatcher is

interrupt is completed, unless an additional decision is taken to preempt—the process is removed from the CPU but since it Would continue running if it could, it is returned directly to the Runnable state. Interrupts may be nested, hoWever it

also responsible for implementing any CPU af?nity bindings, that is, in a multi-CPU system there may be constraints about Which processes may or may not use Which CPUs—When selecting a next process for a CPU it is just a
65

is alWays the originally interrupted process, Which continues running unless the preemption is done. The Work performed during Interrupt state need not be related to the Work of the

matter of ignoring runnable processes Which are ineligible due to af?nity even if other data Would indicate they are most deserving to be run next.

US 6,785,889 B1
11
The dispatcher has involvement With each process state transition to or from the running state; and interacts With the scheduler in a cooperative manner to inform it of these events and to be in?uenced in the control actions that it

12
Scheduler

Although some implementations do not alWays make a

clear division, it is possible to identify part of the overall dispatching and scheduling scheme Which We term the

makes.
Selecting a Process to Run and Giving it a CPU

Scheduler—it is involved With high level policy. The policy “controls” the dispatcher, but indirectly, mainly through the priorities assigned to runnable processes and also through timeslice lengths and preemption decisions to achieve a desired distribution of CPU availability to the competing
10

The set of runnable processes is usually managed as a

priority ordered, “run queue” (most Unix systems) or as an unordered list With an associated priority calculation func

tion (Linux). In both cases, it is the scheduler, Which provides the priority value. The Linux method means that there is less lag betWeen When the priority is calculated and When it is used but it is unclear if this makes a practical difference or What the ef?ciency tradeoff is betWeen repeated recalculation of a priority Which may Well have the same result and a lagged value; most schedulers also do an update scan of processes on the run queue to prevent marooning. Even Linux schedulers include an update, Which adjusts one

processes. In?uencing selection of a process to run:

The scheduler in?uences the dispatcher selection of Which process to run next through priority values assigned to the runnable processes. This assignment is either

dynamic (e. g. in Linux calculated during the dispatcher selection scan(s)) or relies on a priority assigned When ever the process is placed on the run queue (eg at

process creation, Wakeup, or preemption); usually assigned With a regular loW frequency update scan to

of the inputs to the priority calculation function. Adecision about hoW long the process Will be alloWed to run before preemption is usually made When the process is given a CPU. The dispatcher Will either ask the scheduler for a time slice length and arrange for a preemption interrupt at that future point in time, or notify the scheduler that a time slice is beginning alloW the scheduler to determine the

avoid marooning.
When a process is selected to run:

A decision about hoW long the process Will be alloWed to run before preemption is usually made When the pro cess is given a CPU. The dispatcher Will either ask the scheduler for a time slice length and arrange for a

interrupt.
If no eligible process can be found to be run then the

preemption interrupt at that future point in time, or by notifying the scheduler that a time slice is beginning
3O

dispatcher Will either loop continuously looking for a process, use a specialiZed instruction to pause the CPU, Which is still able to service interrupts, or give control to a dedicated loWest priority “idle” process. When some process becomes runnable due to an event noti?ed via an interrupt,

alloW the scheduler to determine an interrupt. Dealing With a process creation: The scheduler plays a part in process creation so that it becomes aWare of the neW process (child) and the

relationship of it to the parent process, Which spaWned the neW process. Some scheduler related characteristics of processes are inherited from parent to child. The

or by actions of another CPU, the idle CPU Will be prompted to make another scan for runnable processes, ?nd one, and

select it. In the event of a process termination, the dispatcher Will notify the scheduler of the exit and initiate deletion of any data structures involved in keeping track of the process lifetime. Since the CPU that Was running the process that exits becomes available, the dispatcher Will then search to select another process.

scheduler must assign an initial priority to the runnable child and for memory performance reasons is usually expected to in?uence Whether the parent or child runs

?rst immediately after the spaWn.
40

Monitoring Process CPU Usage
As mentioned above, some systems may use interval 45 timing and an end of time slice interrupt to preempt a running process. The majority of systems use a more fre

Dealing With a process exit: Delete any data structures involved in keeping track of the process lifetime. If accounting for usage, it may also be appropriate for the scheduler to accrue the partial

timeslice, Which ends With the exit. Monitoring process CPU usage:
As mentioned above, some systems may use interval timing and an end of timeslice interrupt to preempt a running process. The majority of systems use a more

quent clock interrupt (often 100 times per second, a “tick”) to sample the running state of the interrupted process; this mechanism involves noti?cation to the scheduler that the

frequent clock interrupt (often 100 times per second, a “tick”) to sample the running state of the interrupted process; this mechanism involves noti?cation to the scheduler that the interrupted process Was found to be

interrupted process Was found to be running. By counting the tick reports the dispatcher or scheduler can arrange to

preempt the process if it doesn’t yield soon enough.

running. By counting the-tick reports the scheduler can arrange to preempt the process if it doesn’t yield soon
55

Preemption
The need to preempt a process arises When the process is observed to have reached the end of a time slice or the

enough.
Dealing With a process that yields: The dispatcher noti?es the scheduler that the process is going to sleep. The scheduler may use this moment as a convenient point in time to account for the early end of the time slice, Which the process Was part Way

scheduler may provoke an earlier preemption because it knoWs a higher priority process has just rejoined the run queue. The process to be preempted is subjected to a forced interrupt so that dispatcher code can remove it from the CPU, make a fresh selection scan, and set the neWly selected

through. Preemption:
The need to preempt a process arises When the process is observed to have reached the end of a time slice or the

process running in a neWly started time slice. It is possible that the preempted process and the neWly continued process are the same; When they are not the same, the still runnable 65 preempted process is returned to the run queue With a

scheduler may provoke an earlier preemption because it knoWs a higher priority process has just rejoined the run queue. The process preempted is subjected to a

recalculated priority.

US 6,785,889 B1
13
forced interrupt and once removed from the CPU Will be replaced in the run queue. When noti?ed of the preemption, the scheduler can use this as the actual moment at Which the process time slice ends.

14 that there are seven processes oWned by tWo users acting in

Wakeup:
When a process Wakes, it must be ?rst returned to the run

tWo groups, and using classi?cation hierarchy (a) as de?ned in FIG. 5 above. The folloWing entity hierarchy serves to illustrate an eXample of scheduler’s operation in managing the process of sharing resources among entities and the need for and aspect of the invention. First, in the case When all processes have CPU-bound demand, under normal TS, the system Will distribute CPU capacity, in time slice quanta, in rotation, betWeen the seven processes. This results in 14.3% of capacity used by each process if they all have equal niceness; under the same assumptions if the number of such processes increases or decreases the available CPU capacity is divided equally betWeen N processes each receives (100/N) %. If processes are given non-default niceness then they receive more or less than an equal portion in a Way Which is dif?cult to calculate or describe here as it is outside the scope of this embodi ment. It can be said that processes competing at equal niceness Will receive equal portions. There is no bias to the distribution of CPU based on classi?cation. Under a sharing TS scheduler, We Wish to control the

queue and this implies the need for a priority calcula tion to position the process correctly among other runnable processes.

Sharing:
A key feature of the present invention scheduler that differentiates it from other fair share schedulers is that basic fair sharing is done at the process level rather than the user

10

level and that, if it is required, fair sharing among higher level entities is achieved by modifying the process level fair

sharing. The principal bene?t provided by this con?guration is that the resulting scheduler is very ?exible, alloWing different types of sharing to be achieved by a single sched uler. Additionally, fair sharing among high level entities can be short term, long term or both. The selection betWeen Which type of fair sharing is in force can be made on a

15

running system. The type of high level entities among Which fair sharing could be implemented is diverse and includes users, projects, groups and process groups. In contrast to conventional TS schedulers, an aspect of the invention considers the aggregate demand of multiple pro cesses and enables a hierarchical approach to scheduling. Aggregation implies a need to classify processes so that those Which have the same classi?cation can be counted

20

portion of CPU given to each process classi?cation, based
25

on some policy Which vieWs the different classi?cations as

being more or less important or deserving of receiving a portion of the scarce resource: CPU capacity. This is some

together as an aggregate entity

If multiple classi?ca
30

times termed Fair Sharing although it is meant to signify

tions are made, then the processes can be aggregated in a

equal sharing.
Suppose, in the above Seven Process scenario of FIG. 6, the policy provides as a ?rst consideration, that each U is equally entitled to CPU, neXt that each RUE of a U is equally entitled to share in that U’s share, and ?nally that each process of a RUE is equally entitled to share in that RUE’s share. For the given miX of processes and their classi?cations, local entitlements can be calculated for each User, RUE and Process—each local entitlement is the frac tion of the entitlement above it Which eachAE deserves. The CPU Share, Which devolves to each process, is the product of the local entitlements above it. These are all tabulated and shoWn in Table 1.
TABLE 1
User U entitlement RUE G entitlement Process P entitlement 50 CPU Share U1 0.5 U1:G1 0.5 P1 P2 0.5 0.5 0.125 0.125 U1:G2 0.5 P4 1 0.250 U2:G1 0.5 P3 1 0.250 U2 0.5 U2:G2 0.5 P5 P6 P7 0.33 0.33 0.33 0.083 0.083 0.083

nested hierarchy of AE types. The data used for classi?ca tion can be any of: the observed behavior of processes,

observable attributes of the process, requests from the pro cess or other sources to deem a particular classi?cation for

a given process(es), inheritance of classi?cation from a process to processes that it creates, combinations of these

methods including rule-based approaches.
Classi?cation may be determined dynamically, from time to time in response to particular events, or set once upon ?rst

35

discovery of the process. Thus an aspect of the invention

provides the advantage of creating accounting entity hier archies Which are used to provide a mechanism for dynamic classi?cation at a ?ner granularity.

40

FIG. 5 is a simpli?ed block diagram illustrating the structure of various accounting entity hierarchies. In (a) and
(b), We suppose that each process can be regarded as being oWned by a particular user; and that users may act Within one 45 or more groups a process can also be regarded a member of

a group. Thus, each process belongs to a particular “UzG”

classi?cation (a RUE)—the set of possible RUEs is the cross product of the set of Users and the set of Groups. RUEs can

in turn be aggregated according to User (as in (a)) or Group

(as in
Hierarchy (c) shoWs a more complete possibility, here each process may use a number of threads to perform Work

(Threads are thus the real consumers of CPU capacity)—a thread belongs to the process Wherein it Was started; and

additionally an Application classi?cation applied to pro cesses leads to a three-Way cross product for the set of

55

If a process is removed from contention, then according to the policy there is only a localiZed rebalance of entitle ments. In Table 2 therefore, P7 is removed Which increases the portion due to P5 and P6:
TABLE 2

possible RUEs. Hierarchy (a) is sufficient for explanation of hoW An aspect of the invention scheduling Works: the loW level AEs,
Processes, are the CPU capacity consumers; above Pro cesses are RUEs—each RUE is the collection of processes
60 User U entitlement RUE G entitlement Process P entitlement CPU Share

U1 0.5 U1:G1 0.5 P1 P2 0.5 0.5 0.125 0.125 U1:G2 0.5 P4 1 0.250 U2:G1 0.5 P3 1 0.250

U2 0.5 U2:G2 0.5 P5 P6 0.5 0.5 0.125 0.125

With a particular classi?cation of User and Group; the high level AEs represent RUEs aggregated by User—each User
AE is the collection of processes of a User regardless of

Group classi?cation.
FIG. 6 is a simpli?ed diagram illustrating a simple

65

accounting entity hierarchy’s eXample. In FIG. 6 is shoWn

US 6,785,889 B1
15
The rebalance is more Widespread When the last process of a RUE, e.g. P3 is shown removed in Table 3 below.
TABLE 3
User U entitlement RUE G entitlement Process P entitlement CPU Share U1 U2 User U entitlement RUE G entitlement Process P entitlement CPU Share

TABLE 6
U1 0.3333 U1:G1 0.6667 P1 P2 0.5 0.5 0.111 0.111 U2 0.6667 U2:G2 0.3333 P5 P6 P7 0.333 0.333 0.333 0.074 0.074 0.074

0.5
U1:G1 U2:G1

0.5
0.5 P4
U2:G2 1 P6

0.5
P1 P2 0.5 0.5 0.125 0.125

1 0.250

P5 0.5 0.5 0.250 0.250

U1:G2 0.3333 P4 1 0.111

U2:G1 0.6667 P3 1 0.444

10

Likewise, When the last process of a User is removed, the local U entitlement of all remaining Users rises, and con sequently so does the CPU Share of each remaining process. Conversely, if processes are added to the mix or existing processes change from one classi?cation to another corre

15

Shares The use of Shares to express entitlement policy has been used in a number of Fair Share schedulers and is also used in an aspect of the invention as Well. The difference With the use of shares in an aspect of the invention and previous schedulers is that shares are also used at the process level and therefore distinguished here as a marked improvement.
Shares are a convenient Way to express policy about pro

sponding reassignments of the local entitlements according to the policy, leads to a corresponding allocation of CPU

portioning of entitlement betWeen entities. The local entitle
20

portions for the processes.
Since processes are the CPU consumers, it is alWays

ment of an entity among a set of sharing peers is the ratio of the shares for the entity to the sum of shares for the set of

necessary to have some policy for allocating CPU portions betWeen them. HoWever, it is not necessary to apply the above hierarchical entitlement scheme at all levels or uni formly across a level, even if full classi?cation is still

sharing peers. For example, the policy represented in the entitlements in the scenario above can also be represented by shares. Note that share numbers shoWn in Table 7 beloW only need be commensurate among each set of sharing peers.
TABLE 7

performed for accounting purposes. If the RUE basis for

User U Shares RUE

U1 100 U1:G1 U1:G2 U2:G1

U2 200 U2:G2

G Shares
Process P Shares CPU Portions P1 10 0.111

66
P2 10 0.111

33
P4 1 0.111

2
P3 1000 0.444

1
P5 P6 P7 200 200 200 0.074 0.074 0.074

sharing is removed from the policy statement We get the results found in Table 4 beloW.
40

Provided additional processes, RUEs, or Users are

assigned equivalent numbers of shares When they are added to the above scenario, the sharing policy is preserved.
LikeWise if processes and their shares are removed along With those of any resulting process-less RUEs or Users.

TABLE 4
User U entitlement U1 0.5 U2 0.5

Usage Measurement and Feedback to Priority
U2:G2 P6 45
P7

RUE Process

U1:G1 P1 P2

U1:G2 P4

U2:G1 P3

FIG. 7 is a simpli?ed diagram example illustrating the possible state trajectories to and from the scheduler run queue. The runnable state 709 for a process has ?ner detail Which is the position or priority of the process or entity While it is delayed on the run queue 709, before the dispatcher selects it to run. Depending on the scheduler, a neWly created process may ?rst join the run queue 709 at potentially any level. The number of priority levels may be any convenient number, and typically an even number.

P5

P entitlement

0.33

0.33

0.33

0.25

0.25

0.25

0.25

CPU Share

0.165 0.165

0.165

0.125

0.125 0.125 0.125

_

_

50

If the policy only excludes RUE sharing for U2, We get the results shoWn in Table 5 beloW.
TABLE 5
User U entitlement RUE G entitlement Process P entitlement CPU Share U1 0.5
U1:G1 0.5 P1 P2 0.5 0.5 0.125 0.125 U1:G2 0.5 P4 1 0.250 U2:G1

Until it eventually exits 703, the process circulates from the run queue, to running state 701, then back to the run
U2 0.5
U2:G2

55

queue 709 With a possible sojourn in the sleeping state 705 for this simple embodiment. While delayed in the run queue and depending on scheduler actions, the process may move up or doWn the priority levels until it is selected to run. The

P3 0.25 0.125

P5 P6 P7 0.25 0.25 0.25 0.125 0.125 0.125

60

priority at Which the process rejoins the run queue and the priority it has When selected to run may be anyWhere in the

Thus, one may state a policy saying that U2 is tWice as deserving as U1 and that any G2 use is half as important as

priority range. The trajectories 707 Will vary depending on many factors and some of the complexity in ascertaining the optimal trajectories and the possible scenarios are included

as further aspects of the scheduler according to the invention G1 use; but again With the full hierarchy operative and still 65 Which are covered in more detail beloW. equal sharing betWeen processes of identical classi?cation. While a process is delayed in the run queue, most sched ulers Will increase the process priority over time so that it

This leads to the Table 6 results beloW.