Competitive online scheduling with fixed number of queues - Chua, Richard Bryann L. (2008)
One of the complex parts of an operating system design is CPU scheduling, where the OS schedules a sequence of arriving jobs to use the CPU, without knowledge of the time and number of arriving jobs and their execution times. One of the measures of performance of a scheduling algorithm is the average flow time ? the average time it takes for a job to be completed. For a long time, most major operating systems, like Windows and UNIX used a scheduling algorithm based on the Multilevel Feedback scheduling algorithm. Kalyanasundaram and Pruhs proposed the Randomized Multilevel Feedback (RMLF) algorithm, which is based on the MLF, and showed that it achieves a competitive ration of 0(log n log log n) in terms of minimizing the flow time against an online adaptive adversary. In this research, we present the Randomized Multilevel Feedback 2 (RMLF2) scheduling algorithm, which is a version of RMLF but we fix the number of queues. In RMLF2, we have l queues and RMLF2 always run the job that is in the lowest nonempty queue until the total processed time of the job reaches the target of that job for that particular queue. The job is then moved to the next higher queue, except if the job is already in the highest queue, where it is moved to the back of the queue. The RMLF2 is more similar to MLF used in practice than RMLF, since the MLF that is used in most OS utilizes a fixed number of queues. We show that RMLF2 has a competitive ration of 0(In n) in terms of minimizing flow time against an online adaptive adversary, which leads us to obtain a competitive ratio of 0(In n) for RMLF. Since this obtains the log n lower bound for any randomized scheduling algorithm, RMLF2 and RMLF have a tight competitive ratio of In n.