a2) United States Patent
`US 6,282,561 B1
`(10) Patent No.:
`*Aug. 28, 2001
`(45) Date of Patent:
`Jones et al.
`
`US006282561B1
`
`(54) METHOD AND SYSTEM FOR RESOURCE
`MANAGEMENTWITH INDEPENDENT
`REAL-TIME APPLICATIONS ON A
`COMMONSET OF MACHINES
`
`(75)
`
`Inventors: Michael B. Jones, Redmond; Paul J.
`Leach; Richard P. Draves, Jr., both of
`Seattle, all of WA (US); Joseph S.
`Barrera, III, Belmont, CA (US)
`
`(73) Assignee: Microsoft Corporation, Redmond, WA
`(US)
`
`(*) Notice:
`
`This patent issued on a continued pros-
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent
`term provisions of 35 USC.
`154(a)(2).
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 08/568,578
`
`(22)
`
`Filed:
`
`Dec. 7, 1995
`
`(SV)
`
`Tints C07 eeeeeeeeeescceseeenseneneeeeceececennenneneess G06F 9/00
`
`(52) US. Cd. eee eecesscetesssesnesennes 709/104; 709/315
`
`(58) Field of Search 0.00... 395/673, 674,
`395/675, 200.56, 200.57, 200.58, 200.59,
`200.33, 200.34; 709/104, 103, 105, 203-204,
`227-229; 717/10
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,481,583 * 11/1984 Mucller wees eeeeeeees 364/300
`
`4,890,227 * 12/1989 Watanabeetal. ....
`.... 364/300
`
`5,303,369 *
`4/1994 Borcherding et al. «0.0... 395/650
`
`OTHER PUBLICATIONS
`
`J. Huang, et al “Resource Management for Continuous
`Multimedia Database Applications’,
`IEEE onDisc, pp.
`46-54, 1994.*
`D, Anderson et al, “Support for Continuous Media in the
`DASHSystem”, IEEE onDisc, pp. 54-61, 1990.*
`D. Anderson, “Metascheduling for Continuous Media”,
`ACM Transac. Computer Systems, vol. 11, No. 3, Aug.
`1993.*
`
`(List continued on next page.)
`
`Primary Examiner—Mayjid A. Banankhah
`Assistant Examiner—Sue Lao
`(74) Attorney, Agent, or Firm—Lee & Iayes, PLLC
`
`(57)
`
`ABSTRACT
`
`A resource management mechanism is provided to ensure
`that real-time application programs running on a single
`machineor set of machines exhibit predictable behavior. The
`resource management mechanism employs the abstraction
`of an activity which servesas the basis for granting resource
`reservations and for accounting. An activity submits a
`request for resources in specified amounts to a resource
`planner. Theactivity is resource self-awareso that it is aware
`of its resource requirements. The activity may query
`resource providers to obtain resource requirements for par-
`ticular operations. The resource planner determines whether
`the activity should be granted the requested reservation by
`employing an internal policy. Policy is separated by mecha-
`nism so that the resource planner may implement any of a
`number of policies. The resource planner may choose to
`grant the reservation to an activily or deny the request by an
`activity. When denying a request, the resource planner may
`inform the activity of what quantity of the requested
`resources are currently available so that the activity may
`submit a modified request.
`‘The
`resource management
`mechanism includes a dynamic feedback mechanism for
`initiating renegotiation of resource reservations when appro-
`priate.
`
`(List continued on next page.)
`
`15 Claims, 12 Drawing Sheets
`
`Activity
`
`IPlanner
`
`82
`
`59B
`
`
`
`
`
`(Bandwidth, ...)
`
`)
`
`[Resource
`
`
`
`50
`
`
`
`IFileSys
`File System
`INetwork_|
`59C
`
`
`© IResource
`[Resource
`
`
`— 52
`
`
`Scsi Disk
`IScsiDisk
`llOBus
`
`
`
`V/O Bus
`
`7 54
`
`Resource Planner
`
`
`
`(Bandwidth, ...)
`
`IResource
`7 56
`
`Network
`t
`5oF —~ /
`y
`/
`
`lAtmCard
`
`
`
`
`
`
`
`
`© IResource
`-— 58
`
`ATM Adapter
`
`
`
`Google Exhibit 1041
`Google Exhibit 1041
`Google v. Valtrus
`Googlev. Valtrus
`
`

`

`US 6,282,561 BI
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`“Distributed Operating Systems, The Logiz Design’,
`Andrizej Goscinski, Addison—Wesley Publishing Company,
`1992, pp. 437—-464.*
`for Resource Sharing On Spice
`“A Butler Process
`Machines”, ACM Transactions on Office Information Sys-
`tem, vol. 3, No. 3 Jul. 1985.*
`M. Jones, “Adaptive Real-Time Resource Management
`Supporting Composition of Independently Authored Time-
`Critical Services”, IEEE, pp. 135-139, 1993.*
`M. Sylor, et al, “Applying Network Management Stardards
`to System Management; the case for the Common Agent”,
`IEEE, pp. 110-117, 1994.*
`* cited by examiner
`
`7/1994
`8/1994
`5/1995
`12/1996
`5/1997
`9/1997
`4/1998
`5/1998
`8/1998
`9/1998
`12/1999
`
`SHO eeessceescseseseetesseeseees 395/650
`
`Doragh oo.eee 395/700
`Camillone et al. oe 395/650
`
`. 395/200.06
`..
`Baugheret al.
`Allran et al.
`...cceeseeeeees 395/670
`
`Hooperet al. wee eee 370/468
`STOMA weeeecseeeeeeeeeeee 395/200.56
`
`MclInemey et al. «0... 395/701
`Lichtman et al.
`.
`395/200.56
`
`....
`Jones et al.
`w. 395/674
`
`Joneset al.
`w. 709/104
`
`
`* * * *
`
`*
`
`5,333,319
`5,341,499
`5,421,011
`5,581,703
`5,630,132
`5,671,225
`5,742,772
`5,758,160
`5,793,979
`5,812,844
`6,003,061
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 1 of 12
`
`US 6,282,561 BI
`
`0¢
`
`oe
`
`yomanebe101S
`91Ayepuoses
`
`OMON Ja\depy
`
`
`
`tuayshgJeyndwoe5
`
`8cch
`BdlAaonendo
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 2 of 12
`
`US 6,282,561 BI
`
`
`
`ysanbadpasnasyiwiqnsalAPAOY
`
`
`
`
`
`
`
`seoinoselaqe|leae
`
`
`
`GOINOSAB|Ge|IEAeJy
`
`é914e}d900e
`
`oF
`
`
`
`SS
`
`Nw
`
`T
`
`
`
`
`
`
`
`JoAWADSUUOJU!J@UUe|dBosINOSeY
`
`
`
`
`
`7,S00iN0Selpoysonbs
`
`s90iunosel
`
`
`
`
`
`re!S8ouNOSalJEUMSOUIWElapAPANOY
`
`
`
`soynuenbdpuespeeu
`
`
`
`9¢
`
`
`
`
`
`901NOSsaljeoo}YMSeyenoBeuAWAY
`
`
`
`UOIJEAIOSSJBOUNOSOI104JOUUe|d
`
` ge
`
`
`
`795Alayoese0q
`
`pevjeselos
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 3 of 12
`
`US 6,282,561 BI
`
`c909
`
`JOUUB|d|
`
`AWAY
`
`
`
`JOuUe|gaounosey
`
`(-"‘yypympueg)
`
`a6
`
`
`
`(-*‘ujpimpueg)W6S
`
` 9S0S
`
`
`
`sounosey|901nosey|
`
`
`
`MOMONwaysksallySAS@lAI
`
`06S
`
`9S
`
`eoinosey|CO
`
`cG
`
`aoinosey|
`
`JaydepyWLY
`
`gshE
`
`PIEQUIYVIASICISIS|
`
`
`
`
`
`YS!Isog
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 4 of 12
`
`US 6,282,561 BI
`
`
`
`
`
`49UlSIOPIAOIGBOiNOSEJSeWaNbAPAOY
`
`
`
`
`
`99
`
`
`
`
`
`9JeS8|NpOWJosjusWeJINbassounosey
`
`JOOJIP0}poppepuepowuuns
`
`
`
`UOIYSe]Je|NpOW
`
`
`
`
`
`s]uawalInbeseounoselSuole1edo
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 5 of 12
`
`US 6,282,561 BI
`
`Jauue
`
`
`
`idl(¢'9‘eounosoy])
`
`on7
`
`(po‘e0snosoy])
`
`radepyWily—|PAPOAVsngO/|sngO
`
`deleoinosay|©
`ggvg
`
`©soinosey|O(9°0‘AHAOY)nt
`
`OllXSIQIS9S¥SIQISIS|
`
`OO
`
`
`
`Jouuejgsoinosey
`
`
`
`0(9°9‘eounosay])
`
`9S
`
`YIOMIONOMION|©
`
`a2
`
`VoL
`
`DEL
`
`sonosay|
`
`(eo‘AAnoY)
`
`(v0‘AANOY)
`
`gz
`
`ZS
`
`aoinosay|O
`
`GSOE
`
`09
`
`AYAHOY
`
`
`
`0S
`
`eoinosey]_O
`
`wi}shs9I4skgel!4|
`
`O
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 6 of 12
`
`US 6,282,561 BI
`
`
`
`
`
`
`
`bLJO}JsenbalSoAI9oasJOUURIdBOINOSeY
`
`c8
`
`
`
`}SOMO|WO}[29}S
`
`
`
`Ayagoeaoueyodull
`
`
`
`s90inosaljuei6pue
`
`
`
`é£5uisnsamayoe
`
`
`
`ysonbosAany
`
`—_——
`
`we
`
`
`
`
`2QUBLIOCUIJAMO]AUROy s90unosel
`
`ssoJnoseal
`
`
`
`Eal|qeeaesaoinosalaly
`
`ye
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 7 of 12
`
`US 6,282,561 BI
`
`$1N99O
`
`}NOSUI|62GZ
`
`
`
`Jauuejdsdinosay
`
`
`
`AVAoeSOyHoU
`
`L8
`
`
`
`Jauue|daoinosey
`
`
`
`g]jeoAyosauip
`
`
`
`SJapIAoidsounoseal
`
`
`
`LLsylwiqnsadAyAnoy
`
`
`
`UO|ICAJOSOJMOU
`
`ysoenbel
`
`9bE
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 8 of 12
`
`US 6,282,561 BI
`
`98
`
`
`
`
`
`afueydspeeuaounosalAVIANOY
`
`
`
`
`
`a9uonenobeualsysanbauAWAIOY
`
`
`
`Jauue|daounosalYIM
`
`
`
`
`
`06aleSUONCAIISS]SDINOSOY
`
`pejenobouel
`
`pLOL
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 9 of 12
`
`US 6,282,561 BI
`
`
`
`26JoujoUe0}eAnejasSUOTOY
`
`
`
`eBesneoiunosesebueyoweiboid
`
`
`
`
`
`
`
`
`
`96BIESUOIEAIOSS/SOINOSOY
`
`poyenobouel
`
`
`
`abesnsoJnosalJO
`
`
`
`
`
`+6s]OR]U09JoUUR|dsounosey
`
`
`
`
`
`uoieoyipowBunsenbsaAyAjoe
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 10 of 12
`
`US 6,282,561 BI
`
`
`
`OOLS]OB]UODJApIAOIdeoINOSeYy
`
`
`
`
`
`JOWOJU!0}JaUUR|dVoJNOSal
`
`
`
`DEOLSAOJUaISISIOd
`
`
`
`PEOLSAOJUalsisiod
`
`
`
`
`
`ZOLoJe2SUOIPEAISSS]GDINOSOY
`
`peyenoBbsuel
`
`86
`
`
`
`
`
`sjoajapJeplaoidaounosey
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 11 of 12
`
`US 6,282,561 BI
`
`vOL
`
`
`
`wia\sksJeyndwoy
`
`901/
`
`
`
`Jeuue|geonosey
`
`80lSS
`
`
`
`
`
`SI@PIAOldBdINOSeyY
`
`yOl—”
`
`
`
`Waj}shgJajndwoy
`
`901S
`
`
`
`Jouue}gsoinosey
`
`B01/
`
`
`
`SIOPIADIgeoINosey
`
`vol—”
`
`
`
`Wwia}shgJajndwog
`
`901—”
`
`
`
`
`
`Jouue|qsounosey
`
`801S
`
`
`
`
`
`SIOPIADIgBdINOSaY
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2001
`
`Sheet 12 of 12
`
`US 6,282,561 BI
`
`
`
`OLLJO,uoljeAsasaysenbesAWAQOY
`
`
`
`
`
`
`
`80JNOSS]BJOWS
`
`
`
`
`
`
`
`
`
`
`9dINOSOs9JOWSs0}Jsonba.
`
`
`
`ohhSpJeMIO}JoUUe|dBo/NOSAl[2007
`
`sauueld
`
`
`
`
`
`
`
`
`@ONOSal[200]0}asuodse
`
`
`
`btspuasJouueldeounosass}OWOY
`
`Sbb
`
`
`
`SunjelJeuUR;dadunosai|B007
`
`
`
`
`
`AAO0}esuodsel
`
`Jauueyd
`
`
`
`
`
`
`
`

`

`US 6,282,561 B1
`
`1
`METHOD AND SYSTEM FOR RESOURCE
`MANAGEMENT WITH INDEPENDENT
`REAL-TIME APPLICATIONS ON A
`COMMONSET OF MACHINES
`
`TECHNICAL FIELD
`
`The present invention relates generally to computer sys-
`tems and more particularly to resource management of
`independent real-time application programs on a common
`machine or set of machines.
`
`BACKGROUND OF THE INVENTION
`
`Conventional resource management strategies for real-
`time application programshave been unsatisfactory. A “real-
`time application program” is an application program that
`must execute in a predictable and timely fashion in order to
`operate properly. Many current efforts to provide resource
`managementfor real-time application programs may only
`managea static set of resources. In other words, the resource
`set may not change during the course of operation of the
`system. Another limitation of many conventional resource
`management Strategies is that they only accommodate one
`type of resource(i.e., the resources must be homogeneous).
`An additional limitation of many conventional resource
`managementstrategies is that they rely upon the resource or
`the application program to determine which application
`program should be allocated a resource and what quantity of
`the resource should be allocated. Another conventional
`
`approach has been to rely upon humanexperts to correctly
`assign priorities to tasks within the system. Unfortunately,
`such humanexperts typically cannot accurately assign pri-
`orities for a dynamic mix ofreal-time application programs.
`
`SUMMARY OF THE INVENTION
`
`The present invention overcomes many ofthe limitations
`of conventional resource management schemesforreal-time
`application programs. A computer system includes a number
`of local resources that a program may use. A resource
`planner is provided in the computer system for planning
`resource allocation. The resource planner includes a policy
`module for implementing a policy for arbitrating amongst
`requests to reserve resources and an independent planning
`engine that
`is separate from the policy module but that
`implements the policy of the module. A request is received
`at the resource planner for a program to reserve a resource,
`and the resource planner is used to determine whether to
`grant the request or not. The policy module of the resource
`planoer may be replaced so as to implement another policy.
`In accordance with another aspect of the present
`invention, multiple real-time application programs are con-
`currently run on a computer system. The real-time applica-
`tion programs require that at
`least some of the local
`resources be allocated to them in order to run properly. A
`resource planner is provided for programs to contact to
`reserve the local resources. The resource planner imple-
`ments a universal policyfor arbitrating amongst requests for
`the local resources. The resource planner receives requests
`for at least some of the local resources from the real-time
`application programs that are running on the computer
`system. The resource planner then arbitrates amongst the
`requests to grant or deny reservationsforat least some of the
`local resources to the real-time application programs that
`submitted the request.
`In accordance with a further aspect of the present
`invention, a resource planner is provided for granting res-
`
`10
`
`15
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`ervations of shares of local resources of a computer system
`in responseto a request. A requestis receivedat the resource
`planner from a first program to reserve a first share of a
`selected one of the resources. A request from a second
`program to reserve a second share of the selected resource
`is received at the resource planner. The second program is
`not awarc of the first program. The resource planner grants
`the first program a reservation for the first share of the
`selected resource and grants the second program a reserva-
`tion for the second share of the selected resource so that the
`
`programs may share the selected resource.
`In accordance with yet another aspect of the present
`invention, a resource planner is provided in a computer
`system for granting reservations of shares of resources in the
`computer system. A request for an activity to reserve a share
`of at least one of the resources is received at the resource
`planner. The activity includes at least a portion of multiple
`processes that are running on the computer system. The
`request is processed with the resource planner and granted
`so that the share of the requested resource is reserved for use
`by the activity.
`In accordance with a further aspect of the present
`invention, a resource planner is provided for granting res-
`ervations for a share of the resources. An activity that is
`aware of its resource requirements is run on the computer
`system. The activity submits a request
`to the resource
`planner to obtain a reservation for a share of at least one of
`the resources wherethe requestreflects the resource require-
`ments of the activity. The request
`is processed by the
`resource planner to grant or deny the request.
`In accordance with a still further aspect of the present
`invention, an activity submits a request for a reservation of
`asct of resources in specific amounts to the resource planner.
`The request is processed and it is determinedthat the request
`may not be granted to the activity. The resource planner
`returns a list of amounts of the set of resources that are
`
`currently available to the activity back to the activity.
`In accordance with another aspect of the present
`invention, a negotiation is performed between a resource
`plannerandactivities to reserve shares of resources with the
`resource planner on behalf of the activities. In view of
`changing resource usage requirements, a renegotiation takes
`place between the resource planner and the activities to
`change reservations of resources on behalf of the activities
`to reflect the changing resource usage or requirements.
`In accordance with an additional aspect of the present
`invention, allocation of an initial set of resources by activi-
`lies is managed bya resource planner. The resourcesthat are
`in the computer system are altered. In response, a resource
`planner adapts to manage allocation of the new set of
`resources in the computer system without interruption of
`operation of the resource planner.
`In accordance with an additional aspect of the present
`invention,a first resource provider that manages access to a
`resource is queried. Thisfirst resource provider is called by
`an activity to perform an operation on behalf of the activity.
`The activity queries the first resource provider to determine
`a first set of resource requirements to perform the operation
`on behalf ofthe activity. The first resource provider, in turn,
`queries a second resource provider thatis called by the first
`resource provider to complete the operation on behalf of the
`activity. The querying is used to determine a second set of
`resource requirements for the second resource provider to
`perform its role in the operation that is performed on behalf
`of the activity. The first set of resource requirements is
`determined to be a sum of the second set of resource
`
`

`

`US 6,282,561 B1
`
`3
`requirements and any additional resource requirements for
`actions directly performed bythe first resource provider to
`complete operation on behalf of the activity. The resource
`requirements of the activity are determined to be a sum of
`the first set of resource requirements and any additional
`resource requirements of the activity.
`In accordance with a further aspect of the present
`invention, a method is practiced in a distributed system that
`has computer systems connected by network connections.
`Each computer system performs activities and has local
`resources as well as a local resource planner that allocates
`reservations of sharcs ofthe local resourcesto the activitics.
`A request for a reservation of a share of a remote resource
`that is present at a selected one of the computer systems is
`received from an activity at a local resource planner of one
`of the computcr systems. The request is forwarded to the
`local resource planner at the selected computer system and
`processed to generate a response. The response is returned to
`the activity that initiated the request.
`In accordance with another aspect of the present
`invention, the computer system includes resourcesand real-
`time programs that require the use of at least some of the
`resources. The computer system also includes a resource
`plannerthatis independentofthe real-time programs and the
`resources. The resource planner issues reservations to the
`real-time programs to use shares of at least some of the
`resources in response to the requests for reservations by the
`real-time programs.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A preferred embodiment of the present invention will be
`described belowrelative to the following drawings.
`FIG. 1 is a block diagram of a computer system that is
`suitable for practicing the preferred embodiment of the
`present invention.
`FIG. 2 is a flowchart illustrating the steps that are per-
`formed to negotiate resources in accordance with the pre-
`ferred embodimentof the present invention.
`FIG. 3 is a block diagram illustrating an example of an
`activity querying resource providers to determine resource
`requirements in accordance with the preferred embodiment
`of the present invention.
`FIG. 4 is a flowchart illustrating the steps that are per-
`formed by an activity to determineits resource requirements.
`FIG. 5 is a block diagram illustrating the submission of a
`resource set in a reservation request to a resource planner
`and the resulting reservation calls when the request
`is
`granted in accordance with the preferred embodimentofthe
`present invention.
`illustrating the steps that arc
`FIG. 6A is a flowchart
`performed bythe resource planner to implementthe policy
`of the preferred embodimentof the present invention.
`FIG. 6B is a flowchartillustrating the sub-steps that are
`performed to perform step 82 of FIG. 6A.
`FIG. 7A is a flowchart
`illustrating the steps that are
`performedto realize renegotiation when the resource needs
`of an activity change.
`illustrating the steps that are
`FIG. 7B is a flowchart
`performedto realize a renegotiation of resource reservations
`when the actions of another program warrant a renegotia-
`tion.
`
`illustrating the steps that are
`FIG. 7C is a flowchart
`performed to realize a renegotiation when a resource pro-
`vider detects a persistent overload condition.
`FIG. 8 is a block diagram illustrating an example of a
`distributed system thatis suitable for practicing one embodi-
`ment of the present invention.
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 9 is a flowchart illustrating the steps that are per-
`formed to process a request for resource reservations tor a
`remote resource in accordance with the preferred embodi-
`ment of the present invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`The preferred embodiment of the present invention pro-
`vides a resource management mechanism for arbitrating
`resource requests and resource usage among independent
`real-time application programsthat run simultaneously on a
`single machine or set of machines. The resource manage-
`ment mechanism is adaptable to installation on a distributed
`system having separate computer systems by installing the
`mechanism on each of the computer systems within the
`distributed system. The resource management mechanism
`utilizes dynamic feedback to adapt to changing resource
`availability and resource requirements.
`In addition,
`the
`resource management mechanism is extensible so that the
`resource management employed in the system accounts for
`new resourcesthat are added to the system and for resources
`that are removed from the system. The resource manage-
`ment mechanism separates resource management policy
`from resource management mechanism suchthat the mecha-
`nism is independent of the policy. The mechanism for
`implementing policy is generalized so as to facilitate any
`one of a number of different policies.
`In the preferred
`embodimentof the present invention, real-time application
`programsare resource self-aware in that they are aware of
`what resources they require and what quantity of those
`resources they require. The applications negotiate with the
`resource Management mechanism to reserve resources and
`ensure predictable performance.
`A “resource,” as used herein, refers to a limited hardware
`or software quantity that
`is provided by a machine.
`Examples of resources include CPU time, memory capacity,
`I/O bus bandwidth, network bandwidth, and devices, such as
`video frame buffers and sound cards. Resources may also
`encompass higher level software-defined resources that
`manage other resources. Resources are represented in the
`preferred embodiment of the present invention by objects
`that manage the resources. These objects are referred to as
`“resource providers.” As will be described in more detail
`below, resource providers support operations such as allo-
`cating amounts of the resources, performing resource
`accounting, and providing notifications.
`The preferred embodimentof the present invention also
`employs the notion of an “activily.” An “activity” is an
`abstraction that serves as a generalization of a running
`program andis the unit of abstraction to which resources are
`allocated and against which resource usage is charged. Each
`activity is modeled by an activity object.
`It should be
`appreciated that an activity may span thread or process
`boundaries. Further, an activity may span address spaces and
`machines and may have multiple threads of control associ-
`ated with it. Typically, however, each activity is associated
`with a single distinct executing program or application. For
`example,
`the operation of playing a video stream may
`constitute an activity. Similarly, the operation of recording
`and transmitting video for a video teleconferencing appli-
`cation may constitute an activity.
`A “resource planner”is a program that arbitrates access to
`the resources of a machine amongst different activities. The
`resource plannertells an activity what amountof a resource,
`if any, is reserved for use by the activity. The resource
`planner is knowledgeable about all local resources. Each
`
`

`

`US 6,282,561 B1
`
`10
`
`15
`
`30
`
`35
`
`40
`
`5
`local resource is registered with the local resource planner.
`The resource planner monitors whatactivities are allowed to
`gain access to a resource and how muchofthe resource may
`be granted to each activity. The resource planner may
`manage multiple resources, and the resources it manages
`may be of different types. The set of resources managed by
`the resource planner may change over time. The resource
`planner, like other components of the resource management
`mechanismof the preferred embodiment, is implemented as
`an object.
`In general, an activity seeks to reserve resources that it
`needs before it uses those resources. An activity reserves
`resources by requesting the reservation of a number of
`resources from the resource planner. The activity specifies
`the quantity of each resource il wishes to reserve. The
`resource planner applies a policy to the request and deter-
`mines whether the resources should be granted or not in
`view of pending reservations. If the resources are granted to
`the activity, the activity may proceedto use the resources.In
`such a case, the reservationsare utilized in the scheduling of ,,
`resources. The scheduling of the resources described in more
`detail in copending application Ser. No. 08/568,577, now
`US. Pat. No. 5,812,844 entitled “Method and System for
`Scheduling the Execution of Threads Using Optional Time-
`Specific Scheduling Constraints”, which wasfiled or even ,
`date herewith and which is assigned to a commonassignee
`with the present application. If the request is not granted, the
`activity should not use the resource because the activity
`cannot be assured that adequate amountsof the resource will
`be available for the activity to run predictably.
`FIG. 1 is a block diagram depicting a computer system 10
`that is suitable for practicing the preferred embodiment of
`the present invention. The computer system 10 includes a
`central processing unit (CPU) 12 that has accessto a primary
`memory 14 and a secondary storage 16. The primary
`memory 14 holds a copy of an operating system 18 that is
`well adapted for running real-time application programs 20
`and 22. The operating system 18 provides an object-oriented
`environment and supports the Microsoft OLE 2.01 protocol.
`The operating system 18 also includes support for creating
`a resource planner 24. The primary memory 14 additionally
`holds a number of resource providers 26 corresponding to
`the local resources of the computer system 10. The computer
`system 10 may further include an input/output (I/O) device
`28 and a network adapter 30 that connects the computer
`system 10 with a computer network 32, suchas the Internet.
`Although FIG. 1 depicts a single processor computer
`system for practicing the preferred embodiment
`to the
`present invention, those skilled in the art will appreciate that
`the present invention may also be practiced in distributed
`environments. Moreover, the present invention maybe prac-
`ticed in computer systems that have configurations that
`differ from that depicted in FIG. 1. The depiction in FIG. 1
`of the computer system 10 is intended to be merely illus-
`trative and not
`limiting of the present
`invention. For
`example, more than two real-time application programs may
`be concurrently running on the computer system in some
`alternative embodiments.
`
`45
`
`50
`
`55
`
`As was mentioned above, in the preferred embodiment of
`the present invention real-time application programs are
`resource self-aware. The application programs 20 and 22
`know what resources, as well as how much of those
`resources, they need to have to run properly andpredictably.
`FIG. 2 is a flowchart illustrating the steps that are performed
`when an activity that
`is associated with an application
`program seeks to reserve resources. Initially, the activity
`determines whatresourcesit needs (step 34 in FIG. 2). This
`
`60
`
`65
`
`6
`determination involves an information gathering process. In
`the preferred embodiment of the present
`invention,
`the
`activity queries resource providers to determine what
`resources the activity needs. The activity is aware of what
`resource providers it uses, and the activity queries the
`resource providers it uses to determine what resources are,
`in turn, needed by those resource providers to perform their
`job and what quantities of resources are required for the
`resource providers to perform their job.
`In order to more fully understand the information gath-
`ering process, it is helpful to understand how the resource
`providers are logically organized. First, it should be appre-
`ciated that the resource providers are modularized. Resource
`providers may be components of larger modules. An
`example helpsto illustrate this modularity. FIG. 3 depicts an
`example where an activity 60 needs to exploit disk band-
`width and network bandwidth to perform a network write
`operation. The activity knowsthat it must use the file system
`and the network to perform such a write operation. Thefile
`system has an associated file system resource provider 50,
`and the network has an associated network resource provider
`56. In performing the disk read operation, the file system
`resource provider 50 recognizes that it must call upon the
`SCSI disk resource provider 52 and the I/O bus resource
`provider 54 to perform the disk read operation. The network
`resource provider similarly recognizes that it must call upon
`the I/O bus resource provider 54 and the asynchronous
`transfer mode (AI'M) adapter 58 to perform the network
`write operation. Thus, the activity 60 realizes it must use
`disk bandwidth and network bandwidth, but the activity 60
`relies upon the file system resource provider 50 and the
`network resource provider 56 to determine what additional
`resources are required to obtain the disk bandwidth and
`network bandwidth, respectively.
`Software components that have real-time resource
`requirements provide interfaces that expose those require-
`ments to their clients. ‘This allows the clients to query the
`components about the resources that are needed to perform
`operations that the client will use. In other words, resource
`providers support
`interfaces that allow clients of the
`resource providers to determine what resources are required
`for particular operations. An interface, as used herein, is a
`Microsoft OLE 2.01 interface and refers to a named group
`of semantically related methods. Objects that implementthe
`code for all of the methods in an interface are said to
`
`“support”the interface. Examples of interfaces supported by
`resource providers that may be queried to obtain resource
`requirements are the IFileSys, IScsiDisk,OBus, INetwork
`and IAtmCard interfaces shownin FIG. 3.
`
`FIG. 4 is a flowchart that illustrates the steps that are
`performed to determine what resources an activity necds
`(step 34 in FIG. 2). The activity queries the resource
`providers in a modular fashion (step 64 in FIG. 4). The
`queries are represented in FIG. 3 by arrows 59A, 59B, 59C,
`59D, 59E and 59F. The queries are implementedas calls to
`methods in interfaces supported by the resource providers.
`The activity 60 sums the resources required by each of the
`resource providers it calls and adds any resources required
`by operationsthat it directly implements. Thus, for example
`in FIG. 3, the file system resource provider 50 is a client of
`the SCSI disk resource provider 52 and the I/O bus resource
`provider 54. The resource requirements of the file system
`resource provider 60 to perform the network read operation
`requested by the activity 60 includes the resource require-
`ments of both the SCSI disk resource provider to perform its
`role in the operation, the resource requirements of the I/O
`bus resource provider 54 to perform its role, and the separate
`
`

`

`7
`resource requirements of the file system resource provider
`50. ‘he resource requirements of the activity 60 are the
`cumulative resource requirementsofthefile system resource
`[in] RESOURCE_AMOUNT Amount,
`provider 50 and the network resource provider 56 in per-
`[out] [ResourceSet **pResSetResult);
`// Adds a resource and its amountto the set. Adds the resource
`forming the network read operation. The resource require-
`// to the set if necessary, otherwise adjusts the amount.
`ments of the file system resource provider 50 and_the
`// Returns a new resource set with the addition included;
`network resource provider 56 reflect resource requirements
`// original is unmodified.
`of the modular componentsthat are called by those resource
`SCODE GetAmount([in] [Resource *Resource,
`providers. Thus, in step 66 of FIG. 4, the resources require-
`[out] RESOURCE_AMOUNT *Amount);
`// Gets the amountof a particular resource in the set.
`ments of the modules are summed along with the direct
`// Returns 0.0 as the amountif the resource is not in the set.
`resource requirements to determine the cumulative resource
`SCODE Add({in] IResourceSet *Addend,
`requirements for the activity.
`[out] [ResourceSet **Result);
`// Adds the contents of the specified set to this set and returns
`Another alternative for determining resource require-
`// the result. Resource amounts are added if present in both
`mentsis to empirically determine what resources are used by
`// sets. Returns a new resource set with the addition included;
`an activity and to use the empirical determination as the
`// original is unmodified.
`SCODESubtract([In] [ResourceSet *Subtrahend,
`basis for the resource requirements that are later requested.
`[out] [ResourceSet **Result);
`Such empirical estimates may be cached by an activity 60,
`// Subtracts the contents of the subtrahend from this set. Used
`by the operating system 18 or even by the resource planner
`// e.g. to figure out what amountof a set of resources must
`62. This alternative has the benefit of using less mechanism
`// become available to satisfy a request. Returns a new
`// resource set with the modification included; original is
`by clients because the alternative does not require the
`// unmodified.
`querying that is used in the above-described approach.
`SCODEEnumerate([out] [EnumResourceSet **ppenm);
`// Returns enumerator for this resource set.
`The above discussion has assumedthat an activity knows
`SCODECheckFree( );
`how to determine whatresourcesit needs. It may be helpful,
`// Returns S_TRUE if enough of each resource in the setis
`in someinstances, to provide system supportfor assisting an
`// free