OStrich: Fair Scheduling for Multiple Submissions, in "PPAM’2013

Abstract. Campaign Scheduling is characterized by multiple job sub-missions issued from multiple users over time. This model perfectly suits today’s systems since most available parallel environments have multiple users sharing a common infrastructure. When scheduling individually the jobs submitted by various users, one crucial issue is to ensure fair-ness. This work presents a new fair scheduling algorithm called OStrich whose principle is to maintain a virtual time-sharing schedule in which the same amount of processors is assigned to each user. The comple-tion times in the virtual schedule determine the execution order on the physical processors. Then, the campaigns are interleaved in a fair way by OStrich. For independent sequential jobs, we show that OStrich guar-antees the stretch of a campaign to be proportional to campaign’s size and the total number of users. The stretch is used for measuring by what factor a workload is slowed down relative to the time it takes on an un-loaded system. The theoretical performance of our solution is assessed by simulating OStrich compared to the classical FCFS algorithm, issued from synthetic workload traces generated by two di↵erent user profiles. This is done to demonstrate how OStrich benefits both types of users, in contrast to FCFS