N-Step-SCAN Disk Scheduling Algorithm – with Example

N-step-SCAN is a disk scheduling algorithm that scans N number of disk request queues at a time. This queue is fragmented into sub-queues, which are processed by using a SCAN algorithm. Each sub-queue is of length N where N = 1, 2, 3…, n. During the processing of a queue, if some new requests arrive, then they must be placed in some other queue.

At the completion of a SCAN, if the requests that are less than N are left, then they must be processed with the other scan. If the value of N is large i.e., a large number of requests occur in a sub-queue, then the performance of the N-step-SCAN algorithm becomes similar to the SCAN algorithm. If the value of N is 1, then FIFO algorithm is used for processing the requests.

Example for N-step-SCAN Scheduling Algorithm :

Let the requested tracks from a moving head disk with 200 tracks, which are numbered from 0 to 199 be in the order, 122, 90, 160, 24, 102, 89, 143, 18, 67. For N = 2, the requested tracks are divided into the following subqueues.

  • subqueue 1 = {122, 90}
  • subqueue 2 = {160, 24}
  • subqueue 3 = {102, 89}
  • subqueue 4 = {143, 18}
  • subqueue 5 = {67}

Using the N-step-SCAN algorithm, the tracks are processed as shown in the following figure.

N-Step-SCAN Disk Scheduling Algorithm

Initially, sub-queue 1 containing the request tracks 122 and 90 is chosen for disk scheduling. As track 90 is near to 0, it is processed first. After processing track 90, track 122 is processed.

Now, the disk head is located at track 122. A track that is nearer to 122 from the sub-queue 2 is selected for processing. Hence, track 160 is selected. As there are no more tracks to be processed between 160 and 199, the head moves to the last track i.e., 199, and changes its direction so as to continue with the processing of the request for track 24.

Then, the sub-queue 3 will be processed, which contains the request tracks 102 and 89. As 89 is nearer to 24, it is processed first followed by 102. Similarly, the requests in sub-queue 4 and sub-queue 5 are processed. The throughput of the N-step-SCAN disk scheduling algorithm is high and it has low mean response time.

Leave a Comment