Monday, October 5, 2009

Lottery Scheduling: Flexible Proportional-Share Resource Management

Lottery Scheduling: Flexible Proportional-Share Resource Management
Carl A. Waldspurger and William E. Weihl
I implemented lottery scheduling in my CS162 project. Lottery scheduling is a really simple and elegant idea. The ability to support a great deal of threads created a need for a better proportional-share/priority scheduling algorithm. Lottery scheduling works as follows: give each job some number of lottery tickets, on each time slice randomly pick a winning ticket, CPU time is proportional to number of tickets given to each job (on average). Lottery scheduling is probabilistically fair and behaves gracefully as load changes. Increasing the number of tickets also reduces the mean waiting times for each thread and gets closer to ideal fairness. There is even a form of priority donation that is accomplished by transferring a number of tickets to a client that that is blocking. The lottery scheduling mechanism achieves this fairness with relatively little overhead. A tree based lottery only needs to generate a random number and perform log(n) additions and comparisons to select a winner among n clients. Lotteries can also be used to manage many diverse resources: processor time, I/O bandwidth, and access locks. Lottery scheduling can even be used for scheduling communication resources.

Analysis: Lottery scheduling offers probabilistic guarantees for throughput and response time. This results in increased expected error (variability) in as the number of allocations increases. The Lottery Scheduling authors responded with Stride Scheduling to limit the variability and make the error independent of the number of allocations. Stride scheduling still uses tickets to determine proportional throughput among clients.

10 comments:

  1. Lotto Leader Review Everyone has to work to earn money but working to earn money is not the most fun way. Lotto Leader UK

    ReplyDelete
  2. The Ohio Lottery offers a wide variety of draw games and instant games, plus KENO at over 8500 licensed retailer locations across the State of Ohio. euromillions.ws

    ReplyDelete
  3. Thankfulness to my dad who informed me relating to this blog, this website is really amazing. data center

    ReplyDelete
  4. I almost visit this site, it’s just because your awe-inspiring blogs compel me to come again and again.
    payday loans

    ReplyDelete
  5. Your website is terribly informative and your articles are wonderful.online payday

    ReplyDelete
  6. Amazing! I felt this site as a better option to select the blog so I came here. automobile insurance

    ReplyDelete
  7. Nobody can reject the info you have given in the blogs, this is actually a great work.whole life insurance quotes

    ReplyDelete
  8. The stuff in this blog is in not only incredible but also providing the great knowledge to the people.hacking tutorials

    ReplyDelete
  9. I agree. You have made the nice blogs with the great info in the contents.convertible term life insurance policy

    ReplyDelete
  10. Here at this site really the fastidious material collection so that everybody can enjoy a lot.Entrepreneur Mark Curry

    ReplyDelete