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

Amortized Analysis of Disk Scheduling Algorithm V(R)

**Tung-Shou Chen and Wei-Pang Yang ^{+}**

Department of Computer Science and Information Engineering

National Chio Tung University

Hsinchu, Taiwan, Republic of China

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 , 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.