1、1,Using Hierarchical Scheduling to Support Soft Real-Time Applications in General-Purpose Operating Systems,John Regehr March 20, 2001,2,Outline,Motivation and Approach Guarantees HLS Design Augmented Reservations Conclusions and Demo,3,Overview of Contributions,A general hierarchy of soft real-time

2、 schedulers can provide guaranteed scheduling behavior The Hierarchical Loadable Scheduler (HLS) architecture Can be efficiently implemented in a general-purpose OS Increases application performance compared to case where scheduler and apps are mismatched Augmented CPU reservations increase predicta

3、bility when the OS steals CPU time from real-time applications,4,Motivation,People use general-purpose OSs (GPOSs) for many kinds of tasks e.g. Unix, Windows, MacOS variants Compatibility, commodity, convenience Applications have diverse scheduling requirements Time-sharing Soft real-time Isolation

4、Co-scheduling between processors or machines,5,The Problem,One size does not fit all Supporting evidence: companies sell scheduler extensions Ensim: ServerXchange Sun: Solaris Resource Manager Aurema: Active Resource Management TimeSys: Linux/RT,6,Motivating Data: Unfair CPU Allocation Between Users

5、,User 1 gets little CPU time when User 2 creates many threads,7,Approach,Allow a hierarchy of CPU schedulers to control processor allocation Thesis Statement: It is useful and feasible to extend a GPOS with a general, heterogeneous scheduling hierarchy. A heterogeneous hierarchy employs different sc

6、hedulers A general hierarchy does not impose a fixed scheduling model,8,Example Hierarchy,Voice Recognition,J,Video Player,Word Processor,H,L,9,Time Scales,Long: System is used in a particular way Duration: usually uptime of a system or longer Medium: Applications start, end, and change requirements

7、 Duration: seconds, minutes, or longer Short: Individual scheduling decisions made by schedulers within the hierarchy Duration: milliseconds or 10s of ms,10,What Microsoft Should Do,Put HLS into consumer Windows! By default Support interactive, batch, and multimedia applications for a single user Ho

8、wever, also include Library of useful schedulers and API for composing them API for implementing new schedulers,11,Reminder,HLS is an architecture for flexibly composing schedulers,12,Outline,Motivation and Approach Guarantees HLS Design Augmented Reservations Conclusions and Demo,13,Guarantee,Defin

9、ition: Ongoing lower (and possibly upper) bound on CPU allocation Goals: Describe the scheduling behavior required and provided by schedulers, and required by applications Permit these behaviors to be reasoned about Syntax: TYPE p1 p2 ,14,Example Guarantees,100% of a CPU: ALL Strictly best-effort sc

10、heduling: NULL Proportional share: PS s PSBE s CPU Reservations: RESBS x y, RESBH x y RESCS x y, RESCH x y,15,CPU Reservation Guarantees,Hard / Soft: “Hard CPU reservation” hard real-time Soft reservations guarantee a lower bound Hard reservations also guarantee an upper bound Basic / Continuous:,16

11、,Guarantee Conversion by Schedulers,Schedulers require and provide guarantees SFQ: PSBE PSBE+ Rez: ALL RESBH+ Schedulers determine if specific guarantees can be provided ALL RESBH 5 10, RESBH 25 100 EDF-based reservation scheduler Nave rate monotonic reservation scheduler,17,Selected Conversions by

12、Schedulers,Full table contains 23 schedulers,18,Guarantee Conversion by Rewrite Rules,Guarantees can be converted without a scheduler, using rewrite rules Trivial examples: PSBE s PS s RESBH x y RESBS x y Non-trivial examples: RESBS x y RESCS x (2y-x+c) for any c 0 RESCS x y PSBE (x/y) x/y (y-x),19,

13、Partial Rewrite Rule Table,T = rewrite rule exists F = rewrite rule does not exist,20,Another View of Some Rewrite Rules,RESCH,RESBH,RESBS,PSBE,PS,RESCS,21,Guarantees in Action,J,Video Player,Voice Recognition,ALL,NULL,ALL,RESBH 5 33,*,RESBH 10 20,*,RESBS 10 20 ,Word Processor,PSBE 0.1 15,PSBE 0.3 3

14、5,PSBE 0.5 10,22,Related Work for Hierarchical Guarantees,Hierarchical start-time fair queuing Goyal et al. 96 Uniformly slower processors Open environment for real-time applications Deng et al. 99 BSS-I and PShED Lipari et al. 00,23,Guarantee Contributions,Created a framework for reasoning about co

15、mposition of schedulers Derived rewrite rules Integrated more than 20 schedulers Guarantees provide a model of soft real-time CPU allocation Independent of particular scheduling algorithms Developers can program to Users can ensure that application requirements are met,24,Outline,Motivation and Appr

16、oach Guarantees HLS Design Augmented Reservations Conclusions and Demo,25,Inside a Non-Hierarchical CPU Scheduler,Scheduling decisions are made in response to timers and thread state changes,T1,T2,T3,T4,T5,CPU,W,W,R,W,SCHEDULER,26,Inside a Hierarchical CPU Scheduler,Distinguishing feature of hierarc

17、hical schedulers: revocation,VP2,VP3,VP4,VP5,VP6,VP1,W,W,R,W,R,R,SCHEDULER,child virtual processors,parent virtual processor,27,Hierarchical Scheduler Infrastructure (HSI) Design,Schedulers are implemented by code libraries loaded into the kernel Scheduler instances are active entities in the hierar

18、chy Virtual Processors Represent potential for physical processor allocation Used to notify schedulers,28,Scheduler Notifications,Hierarchical infrastructure notifies a scheduler whenever: A child VP requests or releases a processor A parent VP grants or revokes a processor A timer expires Threads i

19、mplicitly notify schedulers when they block and unblock Notifications are cheap: virtual function calls,29,HSI and Scheduler Implementation,HSI runs in Windows 2000 kernel Serialized by a spinlock Added 3100 lines of code Loadable schedulers: Time sharing / fixed priority, CPU reservation, proportio

20、nal share, join A representative set of schedulers, but not a complete one Implemented Rez in about two days, PS scheduler in a few hours,30,Performance,Test machine is a 500MHz Pentium III Most mode change operations run in less than 40s Create / destroy scheduler instance, begin / end CPU reservat

21、ion, etc. Median context switch time Unmodified Windows 2000: 7.1s HLS time-sharing scheduler: 11.7s Cost of each extra level in the scheduling hierarchy is 0.96s Many opportunities for optimization,31,Performance Data:Isolating Resource Principals,32,Scheduling a Real-Time, CPU-Bound Application,Sy

22、nthetic test application Represents a virtual environment or game Must provide 1 frame per 33ms (30 FPS) 10ms of CPU time for each frame More frames are acceptable and desirable Machine also runs background work Goals Application should never miss a deadline Non-real-time work should make progress,3

23、3,Performance Data: CPU Bound Real-Time Application,30-second runs,34,Related Work for HSI,Scheduler activations Anderson et al. 91 CPU inheritance scheduling Ford and Susarla 96 Vassal Candea and Jones 98,35,Contributions,Virtual processors are a novel extension of scheduler activations Anderson et

24、 al. 91 Permit a wide range of schedulers to dynamically create a scheduling hierarchy in kernel of a GPOS First system to do this Simplifies scheduling programming model by hiding OS and hardware complexities,36,Outline,Motivation and Approach Guarantees HLS Design Augmented Reservations Conclusion

25、s and Demo,37,Problem: Stolen Time,We have assumed until now that the OS does not interfere with guarantees However, while processing asynchronous data the OS may steal CPU time from applications Time used by bottom-half mechanisms is not accounted for correctly A solution: Augmented CPU reservation

26、s,38,Time Stolen by Network Receive Processing,39,Augmented Reservations,Strategy: accurately measure stolen time in order to compensate threads Rez-C: avoid “charging” threads for stolen time Rez-FB: use a feedback loop to assign a larger CPU reservation so requirements are met even when time is st

27、olen Implemented as HLS schedulers,40,Augmented Reservation Performance,41,OS Design Rule,Mechanisms that will be used often must be lightweight Interrupts very lightweight non-preemptible, scheduled in hardware DPCs and bottom-half handlers high priority, simple scheduler, non-preemptive, no thread

28、 context Threads least lightweight,42,Related Work for Augmented Reservations,Scheduling bottom-half activity Mach Rashid et al. 89 Nemesis Leslie et al. 96 Scheduling bottom-half activity in a GPOS FreeBSD Jeffay et al. 98 Feedback-based scheduling FC-EDF Lu et al. 99 Moving code into scheduled con

29、texts Soft modems Jones and Saroiu 01,43,Augmented Reservation Contributions,Rez-C and Rez-FB 6% over-reservation to eliminate most deadline misses vs. 24% over-reservation for plain Rez Quantified severity of stolen time Windows 2000 + Rez and Linux/RT Network, disk, software modem, USB,44,Outline,Motivation and Approach Guarantees HLS Design Augmented Reservations Conclusions and Demo,45,Conclusions,HLS is feasible: Composition of soft real-time schedulers can be reasoned about Implemented and performs well HLS is useful: Permits