Competitive analysis of on-line disk scheduling
Journal
Theory of Computing Systems
Journal Volume
31
Journal Issue
5
Pages
491-506
Date Issued
1998
Author(s)
Abstract
In this paper we study three popular on-line disk scheduling algorithms, FCFS, SSTF, and LOOK, using competitive analysis. Our results show that, in a competitive sense, the performance of LOOK is better than those of SSTF and FCFS. As a by-product, our analysis also reveals quantitatively the role played by the size of the window, which in our model is a waiting buffer that holds a fixed number of requests waiting to be serviced next. The window, in some sense, offers the lookahead ability which is mentioned in several on-line problems.
Type
journal article