Lottery Scheduling for Efficient Resource Allocation
"Explore the concept of Lottery Scheduling, a random allocation method, for multi-threaded systems. Learn about its implementation, benefits, experimentation findings, and comparison with other scheduling algorithms."
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
Lottery Scheduling Ish Baid
Outline Problem What is it? Implementation Benefits Experimentation Findings Other Scheduling Algorithms Conclusion
Problem Scheduling computations in multi-threaded systems is complex, and challenging problem. Resources are scarce and must be allocated well Scheduling based on priority can be absolute, arbitrary, and inadequate for insulating resource allocation policies Overall...limits throughput and response time
What is it? Random, uniform way to allocate resources Select ticket and allocate resource to client with winning ticket Use various techniques to change ticket proportions throughout
Implementation Select random lottery number n, traverse using: List Tree Currencies Only active as long as thread is on run queue Can be used encapsulated rights for a resource Client-server computation Client task will often transfer tickets to server task
Module Resource Management Ticket transfers Used to unblock threads Inflation Violates modularity Useful among trusted clients Can be valuable if a task doesn t need its tickets Provides adjusted resource allocation without explicit communication Compensation tickets Ensures fairness
Benefits Fairness Prevents typical starvation Flexible Control over resource allocation Allow dynamic adjusting of resource allocation in relation to ticket proportions Module Resource Management Encapsulates resource rights Low overhead
Experimentation Fairness Testing if tasks use resources in relation to their allocation Very accurate for the most part Flexible Control Multimedia applications How tasks adjust to account for error
Comments I don't see how it is impossible for starvation to occur. Though increasingly unlikely, it seems that it is still possible. Figure 5 clearly demonstrates that fairness varies quite a bit. This can have a detrimental effect on latency-sensitive applications
Other Scheduling Algorithms Weighted Fair Queue Data packet Scheduling Algorithm Allows for specification of capacity that will be given Each flow is protected from one another Calculates departure date for packet -> uses that date to decide which packet to emit Stride Scheduling Improved version of Lottery scheduling More accurate allocation of resources based on proportions Lower response time
Conclusion Lottery scheduling provides Fairness Flexible Control Modular Resource Management Other scheduling algorithms WFQ Flexible scheduling for network packets Stride Improved lottery scheduling
