AFair ShareScheduler.J. KayP. LauderUniversity of SydneyABSTRACTCPU schedulers are usually designed to allocate resources fairly among processes.Inthis paper,wede-scribe Share, a scheduler that allocates resources so that users get their fair machine share overalong peri-od.We also describe an hierarchical form of Share that supports sharing, not only between individual users, butalso between groups of users. In particular,itsupports the sharing of a machine between organisationalgroups who are independently funded and have contributed a proportion of the machine cost. The hierar-chical Share ensures that each group is allocated its defined machine share in the long term.Ke ywords: scheduling, charging, resource allocation, fair sharing1. IntroductionOne of the critical requirements of a scheduler is that is be fair.Traditionally,this has been interpreted inthe context of processes,and it has meant that schedulers were designed to share resources fairly betweenprocesses. More recently,ithas become clear that schedulers need to be fair to users rather than justprocesses. This is reflected in work such as Larmouth (1975, 1978), Newbury (1982), Henry (1984) andWoodside (1986).The context for developing Share was that of the main teaching machine in a computer science department.We had a large user community,dominated by 1000 undergraduates in several classes as well as a staffofabout 100. Our load was almost exclusively interactive and had frequent, extreme peaks when a majorassignment was due. On a typical day,there were 60-85 active terminals, mainly engaged in editing,compiling and (occasionally) running small to medium Pascal programs. All this activity was supported bya DEC VAX 11/780 running AUSAM,alocal version of Unix that is oriented towards a student environment.Unix provides a fairly typical scheduler (Bach, 1986). It was inadequate in our environment for a numberof reasons:1. it gave more of the machine to users with more processes, which meant that a user could easilyincrease their share of the machine simply by creating more processes;2. it took no account of the long term history of a user’sactivity so that a student who used themachine heavily for,say,two hours, had the same machine share as a student who had not used themachine for some time;3. when one class had an assignment due, and all the students in that class wanted to work very hard,ev eryone, including other students and staff, suffered with poor response, and4. if someone needed good response for activities likepractical examinations or projectdemonstrations, it was difficult to ensure that theycould get that response without denying all otherusers access to the machine.The first three of these are manifestations of unfairness in the way that the process scheduler affects users.On manysystems, these problems are partially addressed by the charging mechanism (Nielsen 1970,McKell et al. 1979). Typically,charging systems involveallocation of a budget to each user and as usersconsume resources, theyare charged for them. We might call this the fixed-budget model, in that each user-2-has a fixed size budget allotted to them. Then, as theyuse resources, the budget is reduced and when it isempty,theycannot use the machine at all. Aprocess can get a better machine share if the user who owns itis prepared to pay more for the resources used by that process. The fixed-budget model can be refined sothat each user has several budgets, each associated with different resources.We control allocation of some resources with a fixed-budget charging mechanism. In particular,weuse thisapproach in these cases:1. for resources likedisc space, each user has a limit;12. resources likeprinter pages are allocated to each user as a budget that has a tight upper bound and isupdated each day;23. daily connect limits are available to prevent individuals from hogging the machine within a singleday;4. weekly connect limits are sometimes used to prevent students from spending too much time oncomputing (compared to other subjects) and to encourage students to work steadily on assignmentsfrom the first week theyare set, right through to the last week (but this commonly has the effect ofdenying students anymachine access near the assignment deadline, eventhough the machine islightly loaded and the students would likemore machine access to finish and improve theirprograms).There are also other utilities to help allocate resources, including a terminal booking program that allowsstudents to reserveaterminal at particular times each week.All these measures helped control consumption of resources but did not deal with the problems of CPUallocation we described earlier.Itwas for these that we developed the Share scheduler.Although Sharewasmotivated by our particular problems in a student environment, it equally well serves the needs of anyuser community that shares a machine which is not run as a commercial bureau operating to makeafinancial profit. Indeed, Share has been implemented in a research environment with manyusers fromdifferent organisations that have chosen to share the capital and running costs of a machine.3To date, Share has been used exclusively to allocate CPU time, though it takes account of the consumptionof all resources as we describe below. Weconsider that Share is applicable to the scheduling of resourcesother than CPU,but for simplicity,this paper is written in terms of CPU scheduling.We describe our work in terms of its design objectives. First we state those objectivesand the underlyingprinciples needed for a qualitative understanding of Share. Then we describe the Share scheduler,startingwith the user’sviewofasingle-levelShare. This is followed by the detailed implementation. From there,we describe the motivation for the hierarchical Share and its implementation. The remainder of the paper isdevoted to the evaluation of Share, including a description of the tools available for users andadministrators to monitor the performance of Share.2. Objectives of ShareManysystems link charging and scheduling only in that a user can specify processes for which theyareprepared to be charged more in return for being givenpreference in scheduling. Indeed, Unix offers amechanism rather likethis in nice,anattribute of a process that a user can adjust to alter its schedulingpriority.Inanon-bureau environment, this approach is adequate. However, a more natural approach is toregard each user as having an entitlement to a fair share of