Lottery scheduling is a randomized resource allocation mechanism that uses a "ticket" system. It allocates resources to clients in proportion to the number of tickets they have, although due to the randomized nature of the scheduling, this ratio is not always spot-on. Clients can transfer their tickets back and forth explicitly, or individual clients can take advantage of "ticket inflation," that is, making more tickets for themselves. The latter sounds like a poor idea in the general case, as it only works with mutually trusting clients.
Clients that do not consume all of their allocated time slots are given "compensation tickets" which increase their chances of gaining access to resources and hence keep the allocation ratios accurate. The authors determined that the lottery scheduling kernel ran comparably to the unmodified Mach kernel for the Dhrystone benchmark, but that lottery scheduling ran a little faster than the unmodified kernel for a multithreaded database server, possibly due to better caching because the Mach kernel only uses round-robin scheduling.
No comments:
Post a Comment