CS 736 - Spring 2007 - Paper Discussion

Summary:

The paper presents a "lottery scheduling", a randomized resource allocation algorithm which allocates resources (CPU in scheduling) with a probability proportional to the number of "lottery tickets" held by a process. A "currency" abstraction is provided to isolate scheduling within trust boundaries.

Problem:

Priority-based scheduling did not provide the encapsulation and modularity properties required for large software systems. It is noted that resource rights do not vary smoothly with priority. A better scheduling algorithm which has the properties of microeconomic and fair share schedulers without their overhead was seen necessary.

Contributions:

Lottery scheduling is probabilistically fair and the mean variance in scheduling of a process is under the control of the OS despite the randomness. Over long running processes the amortization ensures "fair" scheduling based on priorities assigned by tickets.
"Ticket Currencies" provide useful abstraction for isolating trust boundaries. Within a trust boundary the currencies can be inflated/deflated, dynamically reassigned, etc. The internal policing of the trust boundary does not affect the scheduling of other processes running on the system.
Compensation Tickets are a mechanism for achieving true processor fairness. (This might be undesirable for heavily I/O bounded processes.)
Ticket transfers offer quick scheduling of blocking threads which get more tickets and have higher chances of being scheduled.
Flexibility as demonstrated in the Monte-Carlo method is very useful.
Generalization of the "lottery" idea to other resource constraints - mutexes, I/O, memory space, etc.

Flaws:

- Pathologically bad cases : Guarantees hard to offer in such a probabilistic framework, can be worked outside of the lottery scheme.
- Probabilistic fairness valid for long running processes - For short processes with not enough tickets scheduled, there might be problems - The flexibility in the framework can handle this but the "managers" associated with the processes become complex - maybe even for the common case.
- Motivation for randomization could use better explanation. (The lightweight nature is clear, yet how bad were the microeconomic methods?)
- The paper talks of how priorities are coarse, and then benchmarks everything to coarse priority ratios. This made the whole paper weak to me.

Performance:

The system overhead is shown to be small, while optimization was discussed, so the running time of scheduling itself seems acceptable. The performance of the system was made predictable in terms of the ratio of tickets assigned. The RPC and the mutex case (where tickets are transferred) offer performance gains over a regular system. (But traditional systems could work with hints in such predictable cases).

SUMMARY
In "Lottery scheduling: flexible proportional-share resource management" Waldspurger et al. present a proportional-share randomized resource allocation and scheduling algorithm.

PROBLEM
Develop a scheduling mechanism that is flexible (supports many policies), responsive (changes to policy can be enacted quickly), modular (components can
be isolated from each other), robust (e.g. no priority inversion, no starvation), fine grained (scheduling decisions can be computer often), low-overhead, and conceptually simple (so that the algorithm can be easily understood).

CONTRIBUTIONS
* A clean an easy to understand scheduling model.

* Abstracting resource access rights through tickets

* Using tickets instead of priorities makes the system easier to understand.

* Ticket transfer is a conceptually clean mechanism for donating rights to a resource

* Ticket inflation is another straight-forward way where mutually trusting applications can adjust their own priorities.

* Use of ticket currency abstraction for trust domain isolation

* Compensation tickets can improve fairness

* Nice evaluation

FLAWS

* The lottery scheduling can approximate of be equivalent to other scheduling mechanisms under certain restrictions and assumptions. I would be interested in a more detailed analysis in this area.

* Probabilistic guarantees may not mean much in practice if the universe of tickets is very small (e.g. random number generator artifacts may come up) or very large (if a process owns a negligibly small fraction of all tickets it may "effectively starve" because of a very long wait).

* Resigning your fate to whims of probability, regardless of how useful in practice, is an implicit admission of intellectual inadequacy. There is
something sad in sacrificing the quest for optimal solution for the sake of something that will work usually work OK. However, this is more of an
observation than a flaw of this work.

PERFORMANCE
Scheduling overhead, fairness, conceptual simplicity, implementation simplicity, predictability, robustness, flexibility.

Summary
This paper presents a techniques which they call lotterly scheduling which the authors claim "provides efficient, responsive control over the relative rate of computations."

Problem
The problem addressed here is that scheduling techniques that existed before this technique do not support "flexible, responsive control over service rates" and the authors claim that existing priority systems are implemented ad-hoc and the effects of priority changes are poorly understood. Aditionally they claim that other "fair" schedulers have assumptions ad overheads that only allow them "relatively course control over long-running computations." It is necessary to be able to balance short-running interactive applications and long-running scientific computations alike.

Contributions
The primary contribution of this paper is the lottery scheduling technique which is a randomized scheduling technique which uses proportional shares for competing computations. This technique can also be used for efficient management of other resources. They also demonstrate that this system avoids starvation and priority-inversion problems.

Another contribution is the ticket and currency mechanisms to allow processes and their children to transfer their allocated tickets around, allowing processes to give their shares to whoever is blocking them.

Flaws
More evaluation of the effect upon application performance would have been good. What they did was good but i would have liked to see more total execution time benchmarks.

Summary
This paper discusses a scheduling algorithm that uses probabilities to do scheduling, where the chance that a process is scheduled for some resource is proportional to the number of "lottery tickets" it has.

Problem
The authors were trying to come up with a scheduling algorithm that was very flexible in its allocation. They wanted to be more flexible than just the priorities that most OSs use but which they say is very poorly understood.

Contributions
* The idea (?) of doing a random assignment of resources, with the probability of individual processes getting the resource based upon the proportion of tickets that it has.

* Their move-to-front heuristic for sorting the list of token holders is a nifty idea. It does seem like that sort of thing would help out; I wonder how much.

* I thought they did a pretty good job at the evaluation. For instance, in section 5.4 they present a reason why the observed behavior deviated from the expected ratios due to the X server.

Flaws
Their scheduler isn't really appropriate when the sort of variations that a random scheduler produces are not a good idea. Of course, I'm not sure if it is really any more unpredictable than any other scheduler that would be used.

I also wonder if rapidly changing work loads (work a short quantum then a long quantum for instance) would mess up their compensation tokens. It seems like it would, but it's not obvious that it would always lead to fairness without being exploitable; my first reaction was that it seems that just keeping the compensation token around for one quantum wasn't enough, but I'm not sure that this is true. I think they could have spent a little more time on the theory behind this.

They don't really consider in the inverse lottery section how much of a resource a process is using. It might converge to close to being fair faster if they took an approach like what VMware used and based it on the ratio of Tickets/Current Allocation or something like that. More of a "future work" idea than a flaw though...

It's not "Experience with Processes and Monitors in Mesa". ;-)

Performance
The authors were interested in fairness, though over enough time to allow the randomness to converge; short response time to resource requirement changes; and isolation between non-cooperating processes (while still allowing cooperating processes to vary their workloads).

Summary
This work proposes a randomized scheduling mechanism for the allocation of diverse resources. The mechanism is based on an economic model allocating shares of a currency to each resource and running lotteries to determine the scheduling order.

Problems Addressed
Traditional general purpose schedulers were either inflexible, hard to control and offered no dynamic behavior or had a lot of overhead to provide these abilities and ran slowly. The authors address this problem by offering a solution that is both flexible and adapts to current operating conditions while at the same time requiring little overhead to perform the scheduling.

Contributions
Lottery scheduling works by holding a lottery among all the clients that hold shares or tickets for a particular resource. The number of shares any particular client holds in relation to the total number of shares determines probabilistically how much of the time that client will be allowed to use the resource. Since random selection is used any client is not guaranteed a certain proportion of the resource but it is usually close and as the total number of shares increases the difference between the actual and the ideal allocation becomes smaller. Starvation, a common problem in scheduling, is avoided since as long as a client holds a ticket it statistically should eventually win the lottery and obtain access to the resource. Tickets can be transferred to other processes so that the priority of the receiving process is inflated for example in the case of a client waiting on a server. This reduces the priority inversion problem associated with other scheduling mechanisms. Tickets are allowed to be represented in different currencies and are related to other tickets using an exchange rate that expresses all currencies in terms of a base currency. Multiple currencies allows for a group of trusting processes to adjust resource allocation among themselves by inflating or deflating the currency that trusting processes share.

Flaw
The implementation of the work used a list based lottery system, which was made out to be the more time consuming method of running a lottery. A tree based approach was also presented but not implemented or evaluated. For comparison it would have been interesting to see such a study. Also it was mentioned that the disparity between the actual proportion of a resource that is assigned to a client and the ideal proportion decreases as the number of shares in the system increases. It would be interesting to understand if there is an ideal or minimum number of shares that should exist. For example a system where a total of 10 shares are used I assume will have more unpredictable behavior then a system using 100 total shares.

Performance
A big objective of schedulers in general is to maintain fairness and this work attempts to improve the ability of schedulers to maintain fairness while maintaining flexibility. This has been accomplished through the use of a fast random scheduler which selects clients based on a rating of that clients priority in relation to all the other clients vieing for a resource.

Summary

In this paper, the idea of probabilistically fair scheduling scheme for resource management called lottery scheduling is proposed which provides efficient, responsive control over the relative execution rates of computations. Lottery scheduling algorithm is quite generalized and can be used to manage diverse resources like I/O bandwidth, memory, and access to locks.

Problem Description

Accurate control to manage resources between computations to ensure quality of service is quite desirable across a wide spectrum of systems. The authors claim that a very few schemes even come close to supporting flexible, responsive control over service rates. In this paper, the authors provide a mechanism that provides responsive control over relative execution rates of computations by allocating lottery tickets to each computation. Resource consumption rates of active computations are proportional to the tickets allocated to them.

Summary of Resources

The authors present a novel mechanism to manage resources among computations. The basic idea is to have accurate responsive control over relative execution rates of computations. This is important in order to ensure the quality of service metric associated to computations. For example, incase of scientific computations, the consumption of computation resources shared among users and applications of varying importance must be regulated. For interactive computations, ability to rapidly focus resources on tasks that are currently important is needed.
Time quantum of scheduling a lottery can be adjusted. This has two main advantages. Firstly, when there are very few applications need resources, the quantum can be increased to avoid the unnecessary overhead involved in the lottery scheduling algorithm. Secondly, the scheduling quantum can be increased to smaller values as the computation power of the processors increase. This means that the lottery algorithm can survive the rapid changes in processor technology.
The authors also introduce the idea of ticket currencies to denominate tickets within each trust boundary. This currency abstraction is useful for flexibly naming, sharing, and protecting resource rights.
In order to maintain proportional sharing and to permit I/O bound tasks that use few processor cycles to start quickly, compensation tickets are introduced. If an application consumes only a fraction of its allocated time quantum, it is issued a compensation ticket so that it can get an early start next time. This also helps in avoiding starvation.

Flaws

Even though the lottery algorithm provides accurate responsive control over relative execution rates of computations, the authors do not evaluate how the algorithm affects the execution time a computation as compared to some other scheduling algorithm. It would have been quite interesting to see if the applications achieve some performance improvements or degradations when lottery algorithm is used.

Performance Relevance

This paper tries to improve the performance in the following two domains.
1. Fairness
2. Predictability

Lottery algorithm is probabilistically fair. This means that each application is probabilistically guaranteed to get its share of the resource. Secondly, using the lottery algorithm, the relative execution time rates of the computations is controlled. This results in a predictable behavior of the overall system.

Summary:
This paper proposes a random-based fair, responsive, and flexible scheduling algorithm called Lottery Scheduling. Lottery Scheduling uses the randomness and ticket-based weight flexibility of the Lottery and also provides more flexibility and protection control by creating a hierarchy structured hit rate control using currency.

Problem:
Services and applications such as database and multi-media applications requires straight forward algorithm that provides flexible and dynamic differential of priority using the resources. But existing scheduling algorithms does not fulfill all of those requirements.

Contributions:
The mechanism of the lottery is straight forward and the usage of ticket and hierarchy is easy to understand. The mechanism of lottery it self is simple and easy to implement, and that means easy to customize. The possession of ticket means any kind of job could have chance that will avoid starvation and also the Idea of Compensation Ticket covers the problem of unfairness to I/O bound jobs and provides fairness.
The idea of Currency, the easiness of controlling the rate of lottery, and the small overhead enables a high speed response and flexible hit rate control including the protection control for shared resource.
This idea can be used not only for process scheduling but also for other environments such as network queuing scheduling and memory allocation scheduling (choosing which to drop).
Responsiveness, Simplicity, Flexibility and Expandability all together is powerful.

Flaw:
It the amount of tickets is acceptable number, it seems to work efficiently. But if there is very small number of tasks, the randomness does not mean for fairness because there is a possibility of choosing same task repeatedly. Also if there is too many tickets provided for many kinds of tasks, it will increase the cost of holding the array and going through to choose the winner or victim.

Performance:
The small overhead and simple and easy flexibility enables more responsive scheduling and this means that system that contains many process or tasks that changes the requirement of resource and it seems to match current desktop environment too. Also the simple structure and mechanism makes easy to understand and easy for programmers to touch too.

Summary
Lottery Scheduling uses random selection to achieve fine-grained control over CPU allocation in the Mach operating system with minimal overhead.

Problem
The current priority system does not provide enough control over execution for certain applications. It is desirable to have the ability to assign computations a share of the processing power.

Contributions
Entities are allocated a number of lottery tickets. After a set quantum or once a computation gives up the processor a random number is selected to determine which task gets the processor next. In order to avoid overhead the random number generation is extremely quick. In the long run an entity will receive the processor an amount equal to the share of lottery tickets it holds. Fairness is not guaranteed in the short term.

Entities are able to create currencies in able to allocate their processor share among their children, such that a child holding 50% of the currency will receive 50% of its parent's processor share in the long run. In the case a client is blocked on another client, the blocked client is able to transfer its tickets to the running client. This speeds up the running client and avoids priority inversion. The analysis section showed long run fairness and a number of applications that can benefit from Lottery Scheduling.

Possible Improvements
It would have been nice to see further explanation of the mechanism details. As entities become inactive and active I would expect the number of lottery tickets in the system to fluctuate. Also it would be interesting to see how the tickets are handled on other machines in the distributed system. The paper mentioned a few other high-priority threads were allowed to remain. What does a normal priority thread do if it cannot tolerate the possibility of an unlucky streak?

After completing the paper I did not get a good sense of how the tickets will be allocated. The article presented a number of interfaces to assign tickets, but a process left to allocate its own tickets will allocate as many as it can.

Finally since the selection overhead is proportional to log of the client list length, it seems like a malicious user could create an arbitrary long client list. This would increase the overhead each switch. Allowing one use to adversely affect another.

Performance
Predictability is improved with Lottery Scheduling, because the algorithm a task to be assigned a percentage of the processor. Starvation is no longer a worry. Depending how one looks at it fairness among processes is also improved, because in the long run everyone will get a share.

Paper Review: Lottery Scheduling: Flexible Proportional-Share Resource Management [Waldspurger & Weihl]

Summary:

This paper extends the metaphor of lotteries to form a scheduling
algorithm that assigns tickets to schedulable entities, and randomly
chooses lottery winners so that those tasks are scheduled and are
allowed to run proportionately to the number of tickets they hold.

Problem:

The problem was that existing scheduling mechanisms either didn't
provide a clear interface enabling proportional sharing, and others that
are proposed are not easily dynamically changed and taking longer times
to converge to the selected behavior.

Contributions:

* This proposal mostly just requires just a random number
generation and a search for the winning ticket to be required at each
scheduling opportunity. The authors propose that this scheduling
would not introduce too much overhead even if run about every 1000
RISC instructions, so it can react rapidly.

* The lottery scheduling avoids process starvation and priority
inversion problems that can happen with lesser scheduling systems.
(Well, it defers the starvation issue to policy - to be sure each
task has at least one ticket.)

* This proposal seperates policy from mechanism by leaving the initial
ticket allocations and currency configurations separate from the base
scheduler that they describe, which can then focus on rapidly making
decisions within this lottery paradigm.

* The ticket transfer mechanism is clever. Servers don't necessarily
need any tickets at all. Instead, transfers pass your tickets to a
server to do work on your behalf *and* also to do the pending work
(of others) so that the server can get to your request.

Flaws:

* The ticket and currency abstractions are a bit stretched. The reader
must realize that the tickets are not "spent" (meaning you don't turn
them in when you win) and also that currencies are a container sort
of tool, to differentiate scheduling amongst tasks, rather than some
base currency that controls the value of tickets. (In fact, the
currency is backed by tickets rather than the other way around.)
Also, ticket transfers aren't really transfers, because they are just
deleted by the receiver (server), and the sender (client) keeps them
for when the receiver is done.

Performance Relevance:

Generally the existing more "primitive" scheduling, like in Unix, seems
to be sufficient for most application workloads. Many applications just
need to be able to do something while blocking on I/O, and threads
provide a solution to that problem. Also, workloads can be seperated to
different machines (virtual or otherwise) so that tasks of wildly
differing priorities don't have to be run on one machine with an exotic
scheduling algorithm.