Support for User-centric Modular Real-Time Resource Management in the Rialto Operating Syst

Modular Real-Time Resource Management

in the Rialto Operating System

Michael B. Jones, Paul J. Leach, Richard P. Draves, Joseph S. Barrera, III

Microsoft Research, Microsoft Corporation

One Microsoft Way, Building 9S/1

Redmond, WA 98052

mbj@microsoft.com, paulle@microsoft.com, richdr@microsoft.com, joebar@microsoft.com

Abstract. This paper describes ongoing investigations into algorithms foruser-centric modular distributed real-time resource management. Theseinvestigations are being conducted in the context of the Rialto operating system– an object-based real-time kernel and programming environment currentlybeing developed within Microsoft Research.

A primary goal of this research is to develop appropriate real-timeprogramming abstractions to allow multiple independent real-time programs todynamically coexist and share resources on the same hardware platforms. Useof these abstractions is intended both to allow individual applications to reasonabout their own resource requirements and for per-machine system resourceplanner applications to reason about and control resource allocations betweenpotentially competing applications. The set of resources being managed isdynamically extensible, and may include remote resources in distributedenvironments. The local planner conducts resource negotiations withindividual applications on behalf of the user, with the goal of maximizing theuser’s perceived utility of the set of running applications with respect toresource allocations for those applications.

1.The Need for User-Centric Modular Real-Time Resource

Management

One of our major research goals for the Rialto operating system is to investigateprogramming abstractions that make it possible for multiple independent real-timeapplications to dynamically coexist and share resources on the same hardwareplatforms. In particular, just as it is possible to today to purchase or write time-sharing applications that successfully coexist with other time-sharing applications, weare researching a real-time software architecture that is intended to make it possible topurchase or write real-time applications that can successfully coexist both with otherreal-time applications and time-sharing applications. Furthermore, the techniques weare developing are designed to be applicable not just for single-machine applications,but also to distributed applications that make use of remote resources through remoteobject invocations.

To be usable in a tractable fashion, it is our belief that resource managementmust be modular. By this, we mean that it should be possible to write and usesoftware components (classes, modules, libraries, etc.) that have real-time resourcerequirements as components of larger real-time modules or programs without havingto understand their implementations in order to reason about their real-time resourcerequirements. This allows the traditional benefits of modularity (abstract interfaces,information hiding, the ability to reimplement, etc.) to be carried forward into real-time programming.

As well as applying to software components, we believe that this kind ofmodularity of resource requirements must also extend to entire real-time applications.This allows a system resource planner application to reason about and participate inoverall resource allocations between applications, just as an application can reasonabout its own internal resource requirements. The planner makes resource allocationdecisions between applications on behalf of the user with the goal of maximizing theuser’s perceived utility of the set of running applications with respect to resourceallocations for those applications.

2.The Problem Being Solved

This paper focuses on one aspect of the real-time programming model provided byand used within the Rialto operating system. This aspect is:

• An extensible modular distributed real-time resource-management scheme. Thisscheme allows programs to reason about their own real-time resource needs andnegotiate for resource reservations based on those needs. It also allows a systemresource planner to arbitrate between applications’ resource requests on behalf ofthe user.

2.1Research Context

This research is being conducted in a larger context of real-time systems work. Whilenot the focus of this paper, it is nonetheless useful to have an overview of this largersystems context so as be able to better understand our resource management strategy.Other features integral to the programming model are:

• A constraint-based real-time scheduler. Time constraints contain a deadline, atime estimate, and an earliest start time. The scheduler notifies the application ifa constraint is unlikely to be met, providing for proactive load shedding in casesof transient overload. Actual time taken is reported back to the application,providing the basis for a realistic real-time feedback mechanism. This is asimplification of the mechanism described in [Jones 93].

• An object invocation mechanism that propagates a thread’s real-time schedulingconstraints to remote object invocations, both to remote processes and to remotemachines. (The object invocation mechanism is a real-time implementation ofthe Component Object Model (COM), the invocation mechanism used by OLE2[Microsoft 94].) Taken together, these three facilities enable a consistent end-to-end treatment to be applied to real-time scheduling decisions.

• An I/O system that also schedules I/O operations using the same real-timescheduling constraints.

• A set of I/O and RPC abstractions designed to avoid data copies whentransmitting and operating on large quantities of data. This mechanism isderived from Fbufs [Druschel & Peterson 93].

2.2The Rialto Approach

Resource management can be viewed as a generalization of admission control.Unlike CPU or I/O scheduling decisions, resource management decisions occurinfrequently – typically at program startup, exit, or mode change. Programs negotiatefor the resources needed to operate on an ongoing basis in a given mode, and thenoperate in that mode until either exiting or changing modes.

The Rialto programming model is designed to permit incremental developmentand refinement of the resource management code used by real-time programs. First,the application can be developed (or ported) and its gross real-time resource needsdetermined. Next, resource management calls can be added to cover the gross real-time resource requirements of the application, which is still a relatively non-invasivechange. Finally, real-time scheduling constraints can be added to fine-tune thebehavior of critical sections of code in the application.

The model carefully separates mechanisms and policies. This allows varied ordynamic resource management policies to be used without modifying applications.

We intend to use this flexibility to implement user-centric, rather thanapplication-centric, resource management policies. By user-centric, we mean thatthey attempt to dynamically maximize the user’s perceived utility of the entiresystem, rather than the performance of any particular application. We expect this tolead to policies which focus on maximizing expected normal-case resourceutilization, rather than always limiting resource allocations to account for worst-casebehavior.

3.Resource Management Design

This section describes our approach to modular real-time resource management,giving examples to help clarify how it would be used in practice.

3.1Resource Management Abstractions

The following abstractions are used by our approach to real-time resourcemanagement:

•Resource: A limited hardware or software quantity provided by a specificmachine. Individual resources might include CPU time, memory, I/O busbandwidth, network bandwidth, devices such as video frame buffers and soundcards, or higher-level software-defined resources, which may themselves manageor use other resources.

• Resource Amount: An abstraction representing a quantity of a specificresource. This is represented by a number between zero and one, with onerepresenting 100% of a particular resource. Resource amounts are derived byresource providers (see below) from interface-specific quality-of-servicespecifications supplied by interface clients.

• Resource Set: A set of (resource, resource amount) pairs.

•Activity: The abstraction to which resources are allocated and against whichresources usage is charged. Normally each distinct executing program orapplication would be associated with a separate activity. Activities may spanaddress spaces and machines and may have multiple threads of control associatedwith them. Threads execute with rights granted by secured user credentialsassociated with their activity. Examples of tasks that might be executed asdistinct activities are playing a studio-quality video stream, recording andtransmitting video for a video-conferencing application, and recording voiceinput for a speech recognition system.

• Resource Provider: The object that manages a particular resource. Operationsinclude allocating amounts of the resource to activities, performing resourceaccounting as the resource is used by activities, and notifying the resourceplanner of activities exceeding their resource allocations. The resource providerobject would typically be implemented by the device driver that manages thephysical resource, by the scheduler (which manages the CPU resource), by otherparts of the system software (which manages other physical resources, such asmemory), or by the module that implements software-defined resources.

• Resource Planner: A server that arbitrates access to the resources of a machineamong different activities. Rather than reserving resources directly from thespecific resource providers, applications negotiate for resources with the resourceplanner. The planner, at the conclusion of a successful resource negotiation, inturn contacts the resource providers to grant specific resource amounts to therequested activity, which can then use up to that amount.

The planner’s job is to implement the resource arbitration policy betweencompeting activities. The expected policy goal is to maximize the user’sperceived utility of the system as a whole – the policy is user-centric rather thanapplication-centric. The planner makes all resource allocation policy decisionsbetween activities (on behalf of the user); this allows for a clean separationbetween mechanism and policy.

•Preferences: Input from the user to the resource planner as to the desiredbehavior of the system and of particular applications. Preferences may be eitherretrieved from a database, or in extraordinary cases, obtained by directlyquerying the user. Example preferences include statements that a video-phonecall should pause a movie unless it's being recorded and that video should bedegraded before audio when all desired resources are not available.

These abstractions are designed to make it possible to reason about application andoverall system behavior.

Abstractions

ActivityThreadsResource Providers

IResource

IFileSys

IResource

INetwork

IPlanner

ResourcePlanner

File SysNetwork

IResource

IAtmCard

IResource

IScsiDisk

IResource

IIOBus

Scsi DiskI/O BusATM Adapter

Figure 3-1: Resource Management Scenario

Figure 3-1 shows an activity that uses a set of abstract resources (file system,network) which themselves use other physical resources (SCSI Disk, I/O Bus, ATMAdapter). Exported interfaces are depicted as labeled circles. Note that softwaremodules export both their usual functional interfaces, as well as resource managerinterfaces. Also shown is the resource planner service. This scenario will be used toillustrate several aspects of resource management in later figures.

3.2Modules and Resource Interfaces

Within our resource management framework, software components (classes,modules, libraries, etc.) that have real-time resource requirements provide interfacesexposing those requirements to clients of those components. This allows clients toquery the module about the resources needed to perform the operations they will use,so that the client modules can, in turn, make their resource needs known to theirclients.

For example, consider a module M which implements a network read operation.As well as exporting the network read operation, M would also export an operationfor determining the resources needed to perform the network read on an ongoingbasis. In particular, it would allow client modules C to ask M questions of the form:“What resources are needed to read N bytes every T time units” with the responsebeing a resource set S enumerating the needed resources. In this instance, S mightindicate an amount of CPU time, an amount of network bandwidth, an amount of busbandwidth, and an amount of memory.

Note that resource queries are in terms of operations exported by the modules,and may contain whatever qualifications are necessary to sufficiently specify theoperations being asked about. For instance, to accurately quantify the resourcesneeded for a series of network reads, M might also need to know the source addressfrom which the data would be read and might need to know acceptable jitter bounds.

If so, the corresponding resource query operation would accept this qualifyinginformation as parameters.

Also, note that C, in general, does not (and need not) understand the contents ofthe resource set S. To determine their own resource requirements, client modules justadd together the resources required by each of the modules (such as M) that they use,and add in any resources required for operations directly implemented in the client.Indeed, it is the fact that clients do not need to understand what resources are in a setreturned from a resource query that makes the resource management schememodular. Implementations may change to use different resources without requiringchanges in clients.

This gives us a modular algebra for reasoning within a program about theprogram’s resource requirements. As a starting point, resource providers are aware ofand understand the resources needed to do their jobs. Client modules subsequentlydetermine their own resource requirements in terms of those of the modules they use.Finally, this permits a program to determine its own resource requirements for thevarious modes of behavior which the program might choose to exhibit.

This ability for a program to reason about its own resource requirements forms abasis for it to negotiate for the these resources.

Translating Application Requirements to Resource Sets

IPlannerActivity(Bandwidth, ...)IResourceIFileSysResourcePlanner(Bandwidth, ...)IResourceINetworkFile SysNetworkIResourceIAtmCardIResourceIScsiDiskIResourceIIOBusScsi DiskI/O BusATM AdapterFigure 3-2: Resource QueriesFigure 3-2 shows resource queries being made by the program to its resourceproviders. Note that some of the providers themselves make queries to other resourceproviders as part of this process. Resource sets are returned in response to thesequeries.

3.3Resource Negotiation

Once an application has determined what resources it will need (either throughresource queries, as described above, or by consulting a database of cached resource

requirements taken from past runs) it negotiates for those resources with the localresource planner. If the requested resource reservation is granted by the planner, theplanner in turn contacts the resource providers on behalf of the program’s activity andmakes the actual resource reservations. At this point, the application is free to use atleast the reserved amounts of the requested resources until such point as it is notifiedto the contrary by the resource planner.

If, however, the requested resource reservation cannot be granted, either due toconflicts with other programs or because of insufficient capacity, the planner willnotify the application of this fact, telling it what quantities of the requested resourcesthe program could successfully acquire. Then, the program either makes a modifiedresource request (probably based on reasoning about its own resource requirementsfor running in a different mode than originally negotiated for) or it may decide thatthere are insufficient resources to function in any mode, and will shut itself down.Activity(IResource, 0.4)(IResource, 0.3)(IResource, 0.6)...IPlannerResourcePlannerIResourceIFileSysIResourceINetworkFile Sys(Activity, 0.4)Network(Activity, 0.6)IResourceIAtmCard(Activity, 0.3)IResourceIResourceIScsiDiskScsi DiskIIOBusI/O BusATM AdapterFigure 3-3: Resource Reservation

Figure 3-3 shows a program requesting a resource reservation from the resourceplanner and the planner in turn contacting the individual resources to make the actualresource reservations.

Unlike simple first-come first-served admission control schemes, our schemedoes not have the property that once a resource is reserved for an application that theapplication is guaranteed at least that resource amount until it explicitly relinquishesit. We view this as an application-centric policy. Instead, we have opted for a user-centric policy – ideally the resource planner allocates resources among the competingapplications in the way that provides the most perceived value to the user. (Ofcourse, the planner can implement irrevocable reservation for some resources orsome applications if it is deemed appropriate, but this is merely a special case of moreflexible policies.) Design and implementation of these policies is an important area offuture work.

Under our scheme, there are several different scenarios where resource re-negotiation may occur. First, a program may modify its own behavior or enter a new

mode, causing its resource needs to change. In this case, the program contacts theresource planner to request that its resource reservations be revised.

Second, another program may have been started, may have exited, or may havechanged its resource usage pattern. In this case, the planner may contact runningprograms, requesting that they modify their resource usage in specific ways (ornotifying them that they may request more resources if they choose to do so).

Third, a resource provider may detect a persistent overload condition, at whichpoint the resource provider would contact the resource planner making it aware of theactivities that are exceeding their reservations.

AnotherActivityReserve!ActivityNegotiateIPlannerResourcePlannerIResourceIFileSysIResourceINetworkFile SysNetworkPersistentOverload!IResourceIAtmCardIResourceIScsiDiskIResourceIIOBusScsi DiskI/O BusATM AdapterFigure 3-4: Resource Negotiation

Figure 3-4 depicts several scenarios under which resource re-negotiation mayoccur. First, a program may modify its own behavior or enter a new mode, causingits resource needs to change. Second, another program may have been started, atwhich point resources may be reallocated by the planner among existing activities.Third, a resource provider may detect a persistent overload condition, at which pointit would contact the resource planner making it aware of the activities that areexceeding their reservations.

3.4Distributed Resource Management

In our scheme, each resource is represented by a resource object that is registeredwith a resource planner that is (typically) running on the machine where the resourceresides. Resource queries for locally implemented objects return references to localresource objects and resource reservation is done via the local resource planner.Thus, most resource management decisions require only local object invocations.

However, resource queries to remotely implemented objects will cause remoteobject invocations and will consequently return references to the remote resourceobjects needed to implement the requested service. Applications in general are notaware of which resources are local or remote, but the local resource planner is. If areservation request is made to the local planner for remote resources, the plannerforwards this portion of the request to the remote planner. Because the plannerscooperate to transparently manage remote resource reservations, application resourcemanagement code is resource-location-independent.

3.5Simplifying Assumptions

A number of simplifying assumptions underlie our resource management model.This section describes and motivates these assumptions.

• Linearity of resource amounts – For most resources this should be a reasonableapproximation to reality when not close to overload. This assumption permitsthe resource planner to manage resource allocations without deep understandingof individual resources.

• Independence of resources – Like linearity, we believe this to be reasonably truefor many resources. Where not true (for instance, reading from disk causesDMA, which can reduce effective processor speed) we may need to handle this atthe resource provider level by explicitly modeling interdependencies (forinstance, by also reserving some “CPU” time for DMA transfers). Thisassumption permits the resource planner to manage allocations of differentresource independently (even though resource providers and consumers may beaware of the interdependencies).

• Application resource self-awareness – We believe that cost in complexity ofhaving applications be aware of their own resource requirements and usage isreasonable in comparison to the benefits gained. This self-awareness permitsapplications to reason about their own behavior in the presence of differentresource allocations. Note also that an incremental approach can be taken,adding refinements of resource awareness to a program on an as-needed basis.One of the research goals of this work is identifying which simplifyingassumptions yield reasonable results, and under what circumstances they hold.

4.Related Work

This section examines the relationships between this work and other related work.

Mercer [Mercer et al. 94] has advocated a “temporal protection” scheme inwhich enforcement of CPU and possibly other resource reservations is providedbetween competing programs. Our resource management strategy is largelyindependent of whether hard enforcement of resource usage is provided, but iscompatible with it. Indeed, if both are present, resource amounts derived fromresource negotiation would be used to choose the values used for resourceenforcement.

Unlike Mercer, Compton and Tennenhouse believe that resource protection isinappropriate and that applications should dynamically and cooperatively shed loadwhen necessary [Compton & Tennenhouse 93], but they bemoan the crude measures

available for deciding when to shed load. Rather than shedding load reactively, ourwork provides a means for programs to cooperatively reason about their resources inadvance, proactively avoiding most dynamic load shedding situations.

A number of mechanisms are currently being proposed for reserving networkbandwidth and related resources such as RSVP [Zhang et al. 93] and a number ofATM-specific schemes. This work is complementary to such mechanisms. Indeed,one result of distributed resource negotiation can be using these mechanisms toallocate any network resources needed by the activity.

Anderson described a system for trading off buffer space and variabilities innetwork latency when delivering continuous media streams [Anderson 93]. Theapplication resource self-awareness needed to analyze these tradeoffs is an exampleof the kind of self-awareness needed to be able to negotiate for and make tradeoffsamong resources in our more general setting.

One important aspect of this work is that it provides a more flexible admissioncontrol scheme than the first-come first-served or priority schemes that are commontoday. Admission policy is controlled by the resource planner, which is able toredistribute resources among both existing applications and new applications in auser-centric rather than application-centric manner.

Finally, it should be stated that this work is intended to be complimentary to, andnot a replacement for, algorithms which provide fine-grained CPU scheduling,whether classical priority-based schemes or more flexible schemes, such as thoseemployed by Northcutt [Northcutt et al. 90, Wall et al. 92]. Even given sufficientresources, fine-grained scheduling decisions still must be made correctly to ensurethat application deadlines are met.

5.Status

The Rialto operating system kernel, including its real-time constraint-basedscheduler, has been implemented and is in use as a research testbed for a number ofkinds of real-time applications. The implementation of resource management isunder way. We expect to report initial results at the workshop.

6.Conclusions

This paper presents a design for modular resource management within and betweenapplications. The set of resources managed is dynamically extensible and mayinclude remote resources in distributed environments. The design carefully separatesmechanisms and policies, allowing varied or dynamic resource management policiesto be used without modifying applications. We intend to use this flexibility toimplement user-centric, rather than application-centric, resource managementpolicies.

While ambitious, we believe that the goals of this research are both attainableand practical. We believe that dynamic resource management will allowcombinations of independently authored real-time applications to nonetheless coexistand be concurrently executed on the same platform. Resource management can be anenabling technology for a free market in independently authored real-timecomponents and applications for widely available home multi-media informationplatforms.

References

[Anderson 93] D. P. Anderson. Metascheduling for Continuous Media. In ACM

Transactions on Computer Systems, 11(3):226-252, August, 1993.

[Compton & Tennenhouse 93] Charles L. Compton and David L. Tennenhouse.

Collaborative Load Shedding. In Proceedings of the Workshop on theRole of Real-Time in Multimedia/Interactive Computing Systems. IEEEComputer Society, Raleigh-Durham, NC, November 1993.

[Druschel & Peterson 93] Peter Druschel and Larry L. Peterson. Fbufs: A High-Bandwidth Cross-Domain Transfer Facility. In Proceedings of the 14thACM Symposium on Operating Systems Principles. December, 1993.

[Jones 93]Michael B. Jones. Adaptive Real-Time Resource Management

Supporting Modular Composition of Digital Multimedia Services. InProceedings of the Fourth International Workshop on Network andOperating System Support for Digital Audio and Video, pages 11-18.Lancaster, U.K., November, 1993.

[Mercer et al. 94] Clifford W. Mercer, Stefan Savage, Hideyuki Tokuda. Processor

Capacity Reserves: Operating System Support for MultimediaApplications. In Proceedings of the IEEE International Conference onMultimedia Computing and Systems (ICMCS), May 1994.

[Microsoft 94] OLE2 Programmer’s Reference, Volume One. Microsoft Press, 1994.[Northcutt et al. 90] J. D. Northcutt, R. K. Clark, D. P. Maynard, and J. E. Trull.

Decentralized Real-Time Scheduling. Final Technical Report to RADC,RADC-TR-90-182, School of Computer Science, Carnegie-MellonUniversity, August, 1990.

[Wall et al. 92] Gerald A. Wall, James G. Hanko, and J. Duane Northcutt. Bus

Bandwidth Management in a High Resolution Video Workstation. InProceedings of the Third International Workshop on Network andOperating System Support for Digital Audio and Video, pages 236-250.IEEE Computer Society, San Diego, CA, November, 1992.

[Zhang et al. 93] Lixia Zhang, Steve Deering, Deborah Estrin, Scott Shenker, and

Daniel Zappala. RSVP: A New Resource ReSerVation Protocol. IEEENetwork 7(5), Sept., 1993.