On the Expected Performance of Scanning Disks

Abstract

This paper describes and analyzes the SCAN policy, used to schedule read/write requests at a moving-arm disk device, when fast response over the entire disk area is at a premium. An analysis is presented which handles precisely the dependence structure between queues accumulated at different cylinders. The arrival process of requests to each cylinder is assumed Poisson and homogeneous in time. A relatively efficient algorithm for evaluating numerically the mean waiting time at each cylinder is presented and its complexity analyzed. We discuss further extensions intended to capture additional details of realistic situations. These include distributed record lengths, skipping unreferenced cylinders and letting successive arrivals’ target cylinders be dependent variables.