Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


osu1164826017.pdf (4.74 MB)

ETD Abstract Container

Abstract Header

Unfairness in parallel job scheduling

Sabin, Gerald M.
http://rave.ohiolink.edu/etdc/view?acc_num=osu1164826017

Abstract Details

2006, Doctor of Philosophy, Ohio State University, Computer and Information Science.
Job scheduling has been an active area of research for many years. Most modern schedulers implement a form of space shared scheduling known as backfilling. Backfilling is a technique used to allow jobs to start out of order, which results in higher utilization and lower average turnaround times. An area that has not been addressed is the impact of these backfilling schemes on the fairness of jobs and users. It is of interest to quantify and study the impact of backfilling on various fairness metrics. Sociology, computer networking and operations research provide evidence of the importance of fairness in queuing disciplines. Currently, there is no accepted model for characterizing fairness in parallel job scheduling. We introduce two types of fairness metrics intended for parallel job schedulers, both of which are based on models from sociology, networking, and/or operations research. The first metric type is motivated by social justice, where serving using in arrival order is considered fair. Therefore, the metric attempts to measure the deviation from arrival order. The second metric type is based on resource equality and compares the resources consumed by a job with the resources deserved by the job. These metrics are orthogonal to traditional metrics, such as turnaround time and utilization. To this end, we develop and introduce fairness metrics which are as independent as possible from current metrics such as utilization and turnaround time. The intent of the fairness metrics is to evaluate how fairly jobs or users are treated, in contrast to the quality of the generated schedule. Further, we plan to use these metrics to study the unfairness of backfilling strategies that have been proposed (and possibly implemented) by past job scheduling research and (where feasible) suggest changes to these strategies to improve fairness. The metrics are used to investigate a new moldable scheduler. An iterative moldable scheduler is introduced and compared to other moldable scheduling algorithms. The metrics are also used to evaluate the Ross/CPlant supercomputer from Sandia National Laboratory. The metrics provide insight to scheduling policy that would provide acceptable fairness to the community.
P. Sadayappan (Advisor)
417 p.
Computer Science
Parallel Job Scheduling; Backfilling; User Estimation; Moldability; Fairness

Recommended Citations

Citations

  • Sabin, G. M. (2006). Unfairness in parallel job scheduling [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1164826017

    APA Style (7th edition)

  • Sabin, Gerald. Unfairness in parallel job scheduling. 2006. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1164826017.

    MLA Style (8th edition)

  • Sabin, Gerald. "Unfairness in parallel job scheduling." Doctoral dissertation, Ohio State University, 2006. http://rave.ohiolink.edu/etdc/view?acc_num=osu1164826017

    Chicago Manual of Style (17th edition)

osu1164826017
1,348
© 2006, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.