OStrich: Fair Scheduling for Multiple Submissions

Abstract : Campaign Scheduling is characterized by multiple job submissions 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 fairness. 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 completion 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 guarantees 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 unloaded 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 different user profiles. This is done to demonstrate how OStrich benefits both types of users, in contrast to FCFS.
Type de document :
Communication dans un congrès
PPAM'2013, 2013, Warsaw, Poland. Springer, 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00918374
Contributeur : Arnaud Legrand <>
Soumis le : mardi 17 décembre 2013 - 13:11:36
Dernière modification le : mercredi 7 octobre 2015 - 01:15:41
Document(s) archivé(s) le : lundi 17 mars 2014 - 22:08:03

Fichier

ostrich-ppam2013.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00918374, version 1

Collections

Citation

Joseph Emeras, Vinicius Pinheiro, Krzysztof Rzadca, Denis Trystram. OStrich: Fair Scheduling for Multiple Submissions. PPAM'2013, 2013, Warsaw, Poland. Springer, 2013. <hal-00918374>

Partager

Métriques

Consultations de
la notice

242

Téléchargements du document

129