Previous [1] [2] [3] 4 [5 ] [6 ] [7 ] [8 ]

Journal of Inforamtion Science and Engineering, Vol.8 No.2, pp.223-242 (June 1992)
Amortized Analysis of Disk Scheduling Algorithm V(R)*

Tung-Shou Chen and Wei-Pang Yang+
Institute of Insormation Science
Department of Computer Science and Information Engineering
National Chio Tung University
Hsinchu, Taiwan, Republic of China
+ Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan, Republic of China

A continuum of disk scheduling algorithms, V(R), was designed by Geist and Daniel in 1987. Most of the disk scheduling algorithms are special cases of V(R), such as SSTF, which is the case V(0) and SCAN, which is the case V(1). We are, therefore, interested in the performance of V(R). This paper provides an amortized analysis on V(R). The amortized analysis promoted by Tarjan considers the worst-case of a sequence of operations. According to our analysis, the best case of V(R) appears when JISE, where Q+1 is the total number of cylinders. This result shows that SCAN (i.e., V(1)) is better than SSTF (i.e., V(0)). Moreover, we also show that SCAN is optimal in the amortized sense. Researchers have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained from SCAN. Our result, therefore, matches their conclusion.

Keywords: amortized analysis, disk scheduling, on-line problem C.R. categories: F.2.2, D.4.2

Received May 20, 1991; revised January 13, 1992.
Communicated by Chin-Chen Chang.
* This research was supported by the national Science Council, Taiwan, R.O.C., under contract: NSC80-0408-E009-11.