We study three models of job scheduling in a distributed server system.
For each of them we suggest scheduling algorithms that are computationally efficient and provably achieve a performance objective related to the model. For this we consider jobs to be an abstraction of executable programs that request specific resources e.g. memory, CPU. Resources need to be reserved in one of the servers for the duration the programs run, which is unknown.
The first model considers queue-based scheduling algorithms, in which jobs belong to a finite set of types and each type has a separate queue. The scheduling objective under this formulation is to keep the size of all queues bounded, which translates to bounded queuing delay. The two families of algorithms for this model can achieve the objective for the maximum theoretical workload. Most importantly they follow vastly different paradigms and are both viable alternatives depending on what other trade-offs the scheduling has to achieve.
The second model considers that resource requirements of jobs come from an unknown distribution. Jobs are queued and the objective is again to keep the number of jobs in the queue bounded and consequently the queuing delay. In this harder formulation there is no previous characterization of the maximum workload that can achieve the objective. We provide such a characterization and algorithms that achieve at least 2/3 of that maximum.
Lastly, we consider a model without queues in which jobs are admitted or rejected on arrival, with the goal to maximize the total utility of the jobs that run. Algorithms of this model were proven to achieve at least 1/2 of the maximum, but further analysis suggests that this limit can be as high as 1 − e (exponent -1). In all models we made simplifying assumptions that allow us to prove the desired properties of the system, but despite the theoretical nature of this work, we also discuss how the algorithms can be applied and tailored to the needs of different cloud applications. We hope they will eventually inspire improvements to existing cloud infrastructure management deployments.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/d8-rjc2-7g07 |
| Date | January 2020 |
| Creators | Psychas, Konstantinos |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0017 seconds