Abstract
CPU schedulers are usually designed to allocate resources fairly among processes. This paper describes Share, a scheduler that allocates resources so that users get their fair machine share over a long period. Also describes a hierarchical form of Share that supports sharing, not only between individual users, but also between groups of users while ensuring that each group is allocated its defined machine share in the long term.
Background
Unix provides a fairly typical scheduler (Bach, 1986). It was inadequate in our environment for a number of reasons:
CPU schedulers are usually designed to allocate resources fairly among processes. This paper describes Share, a scheduler that allocates resources so that users get their fair machine share over a long period. Also describes a hierarchical form of Share that supports sharing, not only between individual users, but also between groups of users while ensuring that each group is allocated its defined machine share in the long term.
Background
Unix provides a fairly typical scheduler (Bach, 1986). It was inadequate in our environment for a number of reasons:
- it gave more of the machine to users with more processes, which meant that a user could easily increase their share of the machine simply by creating more processes;
- it took no account of the long term history of a user’s activity so that a student who used the machine heavily for, say, two hours, had the same machine share as a student who had not used the machine for some time;
- when one class had an assignment due, and all the students in that class wanted to work very hard, everyone, including other students and staff, suffered with poor response, and
- if someone needed good response for activities like practical examinations or project demonstrations, it was difficult to ensure that they could get that response without denying all other users access to the machine.
On many systems, these problems are partially addressed by the charging mechanism. Typically, charging systems involve allocation of a budget to each user and as users consume resources, they are charged for them. We might call this the fixed-budget model, in that each user has a fixed size budget allotted to them. Then, as they use resources, the budget is reduced and when it is empty, they cannot use the machine at all. A process can get a better machine share if the user who owns it is prepared to pay more for the resources used by that process. The fixed-budget model can be refined so that each user has several budgets, each associated with different resources.
Motivation
The Share scheduler was developed to control the consumption of the CPU as a resource. To date, Share has been used exclusively to allocate CPU time, though it takes account of the consumption of all resources as we describe below. We consider that Share is applicable to the scheduling of resources other than CPU, but for simplicity, this paper is written in terms of CPU scheduling.
Goals
Many systems link charging and scheduling only in that a user can specify processes for which they are prepared to be charged more in return for being given preference in scheduling. Indeed, Unix offers a mechanism rather like this in nice, a number in the range zero to nineteen, an attribute of a process that a user can adjust to alter its scheduling priority. When users assign a non-zero nice value to a process, they indicate that poorer response is acceptable. The larger the nice value, the poorer the response.
The way that this affects charging is another administrative decision: the name, nice, suggests that users who do not need fast response for a process might be kind enough to use nice and get poorer response just out of generosity. In our environment, we felt that it was worthwhile to give users some incentive to use nice. So, we reduced the costs charged for processes with larger nice values. In a non-bureau environment, this approach is adequate. However, a more natural approach is to regard each user as having an entitlement to a fair share of the machine, relative to other users. Then the task of the scheduling and charging systems is to ensure that:
Motivation
The Share scheduler was developed to control the consumption of the CPU as a resource. To date, Share has been used exclusively to allocate CPU time, though it takes account of the consumption of all resources as we describe below. We consider that Share is applicable to the scheduling of resources other than CPU, but for simplicity, this paper is written in terms of CPU scheduling.
Goals
Many systems link charging and scheduling only in that a user can specify processes for which they are prepared to be charged more in return for being given preference in scheduling. Indeed, Unix offers a mechanism rather like this in nice, a number in the range zero to nineteen, an attribute of a process that a user can adjust to alter its scheduling priority. When users assign a non-zero nice value to a process, they indicate that poorer response is acceptable. The larger the nice value, the poorer the response.
The way that this affects charging is another administrative decision: the name, nice, suggests that users who do not need fast response for a process might be kind enough to use nice and get poorer response just out of generosity. In our environment, we felt that it was worthwhile to give users some incentive to use nice. So, we reduced the costs charged for processes with larger nice values. In a non-bureau environment, this approach is adequate. However, a more natural approach is to regard each user as having an entitlement to a fair share of the machine, relative to other users. Then the task of the scheduling and charging systems is to ensure that:
- no individual can get more than their fair share of the machine in the long term, and
- that the machine can be well utilised.
In addition, we extended the notion of fair shares to cover groups of individuals so that Share can allow the sharing of a machine between independent organizations. To achieve fair sharing and be practicable, the objectives for Share were that at the level of the individual and independent groups which share the machine, it should:
- seem fair;
- be understandable;
- be predictable;
- accommodate special needs: where a user needs excellent response for a short time, it should permit that with minimum disruption to other users;
- deal well with peak loads;
- encourage load spreading;
- give interactive users reasonable response;
- give some resources to each process so that no process is postponed indefinitely;
- be very cheap to run.
Contributions
The aspect that is essential to Share is that it shares resources fairly between users, rather than just processes. Other aspects can be altered within the Share framework.
The aspect that is essential to Share is that it shares resources fairly between users, rather than just processes. Other aspects can be altered within the Share framework.
- Several parameters are defined by administrative decisions and need to be set according to the particular requirements of each machine.
- In our experience, it seems best to have fixed costs at particular times of day so that users can plan their work in terms of these. In other situations, it may be appropriate to take some other approach: one could dynamically alter costs on the basis of load so that the machine becomes more costly to use at peak times whenever they happen to occur, or one could have fixed costs at all times. Such changes should be taken with care. For example, the suggestions that costs change dynamically may, at first glance, seem attractive and sensible. However, it violates the principle of predictability, a sacrifice that should not be taken lightly.
Conclusion
Users perceive the scheduler as fair in practice, and tend to blame poor response more on their past usage, rather than on system overloading. The strengths of Share are that it:
Users perceive the scheduler as fair in practice, and tend to blame poor response more on their past usage, rather than on system overloading. The strengths of Share are that it:
- is fair to users and to groups in that users cannot cheat the system and groups of users are protected from each other,
- gives a good prediction of the response that a user might expect,
- gives meaningful feedback to users on the cost of various services,
- helps spread load.
