Stride Scheduling for Resource Management
Explore the concepts of Stride Scheduling for deterministic proportional-share resource management introduced by Carl A. Waldspurger and William E. Weihl. Learn about its basic algorithm, client variables, and advantages over other scheduling methods such as Lottery Scheduling. Dive into the world of resource allocation and virtualized data centers with Stride Scheduling.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Stride Scheduling: Deterministic Proportional-Share Resource Management Carl A. Waldspurger, William E. Weihl MIT Laboratory for Computer Science Presenter: Dong-hyeon Park EECS 582 W16 1
Background: Proportional-Share Schedulers Lottery and stride scheduling proposed by Carl A. Waldspurger from MIT in 1995 Inspired by rate-based network flow control algorithms Poor adoption as a CPU scheduler Not suitable for interactive workloads Difficult to calculate the correct ticket allocation Success in virtualized data centers Memory resource management on VMWare s ESX Server EECS 582 W16 2
Problems in Lottery Scheduling Allocation Error over Time Client Response Time ? ?? =1 ? ???[??] =1 ? ?2 ? ?? Time (quanta) Growing Error High Variability EECS 582 W16 3
Stride Scheduling Basic Algorithm Client Variables: Tickets Relative resource allocation Strides (??????1/???????) Interval between selection Pass (???? += ??????) Virtual index of next selection Select Client with Minimum Pass Advance Client s Pass by Client s Stride ??????1 - minimum ticket allocation EECS 582 W16 4
Stride Scheduling Basic Algorithm 3:2:1 Allocation - A (stride = 2) - B (stride = 3) - C (stride = 6) Time 1: 2 3 6 +2 Time 2: 4 3 6 EECS 582 W16 5
Stride Scheduling Basic Algorithm 3:2:1 Allocation - A (stride = 2) - B (stride = 3) - C (stride = 6) Time 1: 2 3 6 +2 Time 2: 4 3 6 +3 Time 3: 4 6 6 EECS 582 W16 6
Stride Scheduling Basic Algorithm 3:2:1 Allocation - A (stride = 2) - B (stride = 3) - C (stride = 6) Time 1: 2 3 6 +2 Time 2: 4 3 6 +3 Time 3: 4 6 6 +2 Time 4: 6 6 6 EECS 582 W16 7
Stride Scheduling Basic Algorithm 3:2:1 Allocation - A (stride = 2) - B (stride = 3) - C (stride = 6) Time 1: 2 3 6 +2 Time 2: 4 3 6 +3 Time 3: 4 6 6 +2 Time 4: 6 6 6 EECS 582 W16 8
Dynamic Resource Allocation Dynamic Client Participation Allow clients to join and leave freely, while keeping the schedule fair. Global variables to maintain aggregate information: global_ticket: total ticket sum of all active clients global_pass: current pass for the global scheduler client_leave() Calculate the remain variable of client ?????? = ???? ??????_???? client_join() Updates client s pass to take into account the resources given when it left ???? = ?????? + ??????_???? EECS 582 W16 9
Dynamic Resource Allocation Dynamic Ticket Modification Allow scheduler to change ticket allocation dynamically Scales the client s existing pass to be proportional to the new ticket ??????? ????????? ?????????= ?????????=????????? ????????? ????????? ???????= ??? + ????????? EECS 582 W16 10
Problem with Stride Scheduling Relative throughput error of stride scheduling for any pair of clients is guaranteed to be less than or equal to one quantum BUT Absolute error can be ? ?? in the worst case ex) 101 clients with 100:1:1: :1 allocation: Expected Allocations on A: 100 100 Absolute Error: 100 50 = 50 First 100 allocations can be given to the biggest client A 200= 50 EECS 582 W16 11
Hierarchical Stride Scheduling Combine clients into groups to balance the ticket load Apply the basic stride scheduling algorithm recursively tickets stride pass 18 Initialized with: pass = stride Starting from root, follow the path with smaller pass value. 6 12 Once the client use the resource, traverse up the tree and update the pass. 10 2 5 1 EECS 582 W16 12
Throughput Error Comparison Error is independent of the allocation time in stride scheduling Absolute Error (quanta) Hierarchical stride scheduling has more balance distribution of error between clients. Time (quanta) EECS 582 W16 13
Response-Time Comparison Little to no variability in response time from stride scheduling. Absolute Error (quanta) Hierarchical stride scheduling has slightly worse response time for some clients. Time (quanta) EECS 582 W16 14
Accuracy of Prototype Implementation Lottery Scheduler Stride Scheduler Lottery and Stride Scheduler implemented on real-system. Stride scheduler stayed within 1% of ideal ratio. Low system overhead relative to standard Linux scheduler. EECS 582 W16 15
Stride Scheduler Overview Deterministic, proportional-share scheduler PROS CONS Well-defined response time for each client Throughput error is independent of ?? Relative error do not exceed one quantum Efficient dynamic allocation Absolute error can be ? ?? for worst-case ? log?? for hierarchial Poor performance on interactive jobs EECS 582 W16 16
Stride Scheduler for Operating Systems? Stride scheduling do not work well with I/O-type workloads Do not reward when a process goes to sleep. How to determine ticket assignment? How many tickets should you assign to each application? Works well in environments with well-defined allocation of resource and fairness is important Virtualized data centers EECS 582 W16 17
Questions? EECS 582 W16 18
