Online scheduling algorithms for average flow time and its variants

Im, Sungjin

Permalink

https://hdl.handle.net/2142/34274 Copy

Description

Title

Online scheduling algorithms for average flow time and its variants

Author(s)

Im, Sungjin

Issue Date

2012-09-18T21:08:59Z

Director of Research (if dissertation) or Advisor (if thesis)

Chekuri, Chandra S.

Doctoral Committee Chair(s)

Chekuri, Chandra S.

Committee Member(s)

• Erickson, Jeff G.
• Bansal, Nikhil
• Vaidya, Nitin H.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• online scheduling
• average flow time
• scalable

Abstract

This dissertation focuses on scheduling problems that are found in a client-server setting where multiple clients and one server (or multiple servers) are the participating entities. Clients send their requests to the server(s) over time, and the server needs to satisfy the requests using its resources. This setting is prevalent in many applications including multiuser operating systems, web servers, database servers, and so on. A natural objective for each client is to minimize the flow time (or equivalently response time) of her request, which is defined as its completion time minus its release time. The server, with multiple requests to serve in its queue, has to prioritize the requests for scheduling. Inherently, the server needs a global scheduling objective to optimize. We mainly study the scheduling objective of minimizing $\ell_k$-norms of flow time of all requests, where $1 \leq k < \infty$. These objectives can be used to balance average performance and fairness. A popular performance measure for online scheduling algorithms is competitive ratio. An algorithm is said to be $c$-competitive if its objective is within a multiplicative factor $c$ of the optimal scheduler's objective for any sequence of requests. Roughly speaking, an algorithm with a small competitive ratio performs well compared to the optimal scheduler even on a worst case input. However, for some problems, competitive ratio could be large for any online algorithm. In such cases, a popular relaxation is resource augmentation where the algorithm is run on a faster machine and compared to the optimal scheduler with one speed. In particular, a scheduling algorithm is said to be scalable if it has a small competitive ratio with any amount of speed augmentation. For problems that have a large lower bound on the achievable competitive ratio, a scalable algorithm is essentially the best one can hope for, in the worst case analysis framework. We give the first scalable algorithms in several scheduling settings for the $\ell_1$ norm or $\ell_k$ norms of flow time ($k \geq 2)$. These settings include broadcast scheduling, scheduling jobs of different parallelizability, and scheduling on heterogeneous machines, and are described below: - Broadcast scheduling: There is a server that stores pages that contain useful data. Each request arrives over time asking for a specific page. When the server broadcasts a page $p$, all outstanding requests for the same page are satisfied simultaneously. This is the main difference from standard scheduling settings where the server must process each request separately. The broadcast model is motivated by several applications such as multicast systems and wireless and LAN networks. - Scheduling jobs of different parallelizability: In this model, jobs have varying degrees of parallelizability (that is, some jobs may be sped up considerably when simultaneously run on multiple processors, while other jobs may be sped up by very little) on a multiprocessor system. The most obvious settings where this problem arises are scheduling multi-threaded processes on a chip with multiple cores/processors, and scheduling multi-process applications in a server farm. - Scheduling on heterogeneous machines: In this dissertation, two cases are mainly considered: related machines and unrelated machines. In the related machines setting, machines may have different speeds. In the more general unrelated machines setting, jobs may have completely different processing times depending on the machines they are assigned to. In all the above models, the online algorithm and the optimal scheduler may have to do different amount of work to complete the same set of requests. This makes it challenging to design and analyze scheduling algorithms. The results presented in this dissertation are enabled by the development of novel analysis techniques.

Graduation Semester

2012-08

Permalink

http://hdl.handle.net/2142/34274

Copyright and License Information

Copyright 2012 Sungjin Im

Owning Collections