SCAN Disk Scheduling Algorithm

Advantages of SCAN(Elevator) Algorithm

The advantages of the SCAN Algorithm are-

1. The main advantage of the SCAN Algorithm is that it reverses its direction after reaching at the end which states that any dynamic request can be handled at the run time. 
2. It provides low variance in response time and waiting time.
3. It is simple and easy to implement.
4. Its performance is very good.

Disadvantages of SCAN(Elevator) Algorithm

The disadvantages of the SCAN Algorithm are-

1. Even if there are no requests to be served, it causes the head to move to the end of the disc.
2. It results in a long waiting time for the cylinders that have just been visited by the head.
3. When SCAN Algorithm reverses its direction it won’t be able to get back at the prior direction which can lead to starvation. Although, mostly we’ve given the static requests which totally get executed. 
    

Related articles- SCAN v/s C-SCAN Algorithms

How the SCAN Disk Scheduling Algorithm Works

To understand the SCAN Algorithm, let us assume a disc queue with requests for I/O. ‘head’ is the position of the disc head. We will now apply the SCAN  algorithm-

1. Arrange all the I/O requests in ascending order.
2. The head will start moving in the right direction, i.e. from 0 to the size of the block.
3. As soon as a request is encountered, head movement is calculated as the current request - the previous request.
4. This process is repeated until the head reaches the end of the disc and the head movements are added.
5. As the end is reached, the direction of the head is reversed, and now the head will process the requests in the opposite direction, i.e. in the left direction.
6. This process is completed as soon as all the requests are processed and we get total head movement.

Example of SCAN Disk Scheduling Algorithm

Example 1: Consider a disc queue with requests for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67. The head is initially at cylinder number 53, moving towards a larger number of cylinders. We will now use the SCAN algorithm to serve these I/O requests.

Input: I/O requests - { 98, 183, 37, 122, 14, 124, 65, 67 }

Initial head position - 53

Direction - towards the larger number of cylinders

Output: 

1. Arranging all the requests in ascending order, we get - { 14, 37, 65, 67, 98, 122, 124, 183 }.
2. The Head starts moving in the right direction. So, the head will move from 53 (current position) and will stop at 65 (next request). Head movement = 65 - 53 = 12.
3. Then the head moves from 65 to 67, and head movement becomes 12 + (67 - 65) = 14.
4. Similarly, the head will go from 67 to 98, and head movement becomes 14 + (98 - 67) = 45.
5. Similarly, the head will go from 98 to 122 and head movement becomes 45 + (122 - 98) = 69.
6. Similarly, the head will go from 122 to 124, and head movement becomes 69 + (124 - 122) = 71.
7. Similarly, the head will go from 124 to 183, and head movement becomes 71 + (183 - 124) = 130.
8. Similarly, the head will go from 183 to 199 (end of the disc), and head movement becomes 130 + (199 - 183) = 146.
9. Now the head will reverse its direction and will go from 199 to 37, and the head movement will become 146 + (199 - 37) = 308.
10.  Now, the head will go from 37 to 14, and head movement becomes 308 + (37 - 14) = 331.
11. Since 14 was the last request, the process will stop. We get the total head movement as 331.

The following chart shows the sequence in which requests are served using SCAN.

Thus, the order in which requests are served is- 65, 67, 98, 122, 124, 183, 199, 37, 14 with a total head movement of 331.

Now, let us consider one more example. 

Example 2: Consider a disc queue with requests for I/O to blocks on cylinders 95, 180, 34, 119, 11, 123, 62, 64. The head is initially at cylinder number 50, moving towards a larger number of cylinders. We will now use the SCAN algorithm to serve these I/O requests.

Input: I/O requests - { 95, 180, 34, 119, 11, 123, 62, 64 }

Initial head position - 50

Direction - towards the larger number of cylinders

Output: 

1. Arranging all the requests in ascending order, we get - { 11, 34, 62, 64, 95, 119, 123, 180 }.
2. Head will start moving from 50 and process the requests in the right direction in the sequence - 62, 64, 95, 119, 123, 180, 199 (end of the disc).
3. Now the head will reverse its direction.
4. Now the head will process the requests in the left direction in the sequence - 34, 11.

The total head movement is calculated as: 

= (62 - 50) + (64 - 62) + (95 - 64) + (119 - 95) + (123 - 119) + (180 - 123) + (199 - 180) + (199 - 34) + (34 - 11)

= 12 + 2 + 31 + 24 + 4 + 57 + 19 + 165  + 23

= 337

The following chart shows the sequence in which requests are served using the SCAN algorithm.

Thus, the order in which requests are served is- 62, 64, 95, 119, 123, 180, 199, 34, 11 with a total head movement of 337. 

Let us consider one more example.

Example 3: Consider a disc queue with requests for I/O to blocks on cylinders 19, 80, 134, 11, 110, 23, 162, 64. The head is initially at cylinder number 50, moving towards a larger number of cylinders. We will now use the SCAN algorithm to serve these I/O requests.

Input: I/O requests - { 19, 80, 134, 11, 110, 23, 162, 64 }

Initial head position - 50

Direction - towards the larger number of cylinders

Output: 

1. Arranging all the requests in ascending order, we get - { 11, 19, 23, 64, 80, 110, 134, 162 }.
2. The Head will start moving from 50 and will process the requests in the right direction in the sequence - 64, 80, 110, 134, 162, 199 (end of the disc).
3. Now the head will reverse its direction.
4. Now the head will process the requests in the left direction in the sequence - 23, 19, 11.

The total head movement is calculated as: 

= (64 - 50) + (80 - 64) + (110 - 80) + (134 - 110) + (162 - 134) + (199 - 162) + (199 - 23) + (23 - 19) + (19 - 11)

= 14 + 16 + 30 + 24 + 28 + 37 + 176 + 4 + 8

= 337

The following chart shows the sequence in which requests are served using SCAN.

Thus, the order in which requests are served is- 64, 80, 110, 134, 162, 199, 23, 19, 11 with a total head movement of 337. 

You can also read about the Multilevel Feedback Queue Scheduling.

Implementation 

To implement the SCAN disk scheduling algorithm, the disk head moves in a particular direction, servicing requests along the way until it reaches the end of the disk. Then, it reverses direction and continues servicing requests in the opposite direction, which ensures efficient disk access and minimizes seek time.

• C++
• Java
• Python
• Javascript

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100005;

int n, head, tail;
vector<int> q;

void scan(int start, int direction) {
  int i;
  if (direction == 1) {
    for (i = start; i < n; i++) {
      if (find(q.begin(), q.end(), i) != q.end()) {
        cout << "Serving " << i << endl;
        q.erase(remove(q.begin(), q.end(), i), q.end());
      }
    }
    for (i = n - 1; i >= 0; i--) {
      if (find(q.begin(), q.end(), i) != q.end()) {
        cout << "Serving " << i << endl;
        q.erase(remove(q.begin(), q.end(), i), q.end());
      }
    }
  } else {
    for (i = start; i >= 0; i--) {
      if (find(q.begin(), q.end(), i) != q.end()) {
        cout << "Serving " << i << endl;
        q.erase(remove(q.begin(), q.end(), i), q.end());
      }
    }
    for (i = 0; i < n; i++) {
      if (find(q.begin(), q.end(), i) != q.end()) {
        cout << "Serving " << i << endl;
        q.erase(remove(q.begin(), q.end(), i), q.end());
      }
    }
  }
}

int main() {
  cin >> n >> head >> tail;
  int x;
  for (int i = 0; i < n; i++) {
    cin >> x;
    q.push_back(x);
  }

  int direction = (head < tail) ? 1 : -1;
  scan(head, direction);

  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.ArrayList;
import java.util.Scanner;

public class SCANAlgorithm {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 100005;
        int n = scanner.nextInt();
        int head = scanner.nextInt();
        int tail = scanner.nextInt();
        ArrayList<Integer> q = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            q.add(x);
        }

        int direction = (head < tail) ? 1 : -1;
        scan(q, n, head, direction);
    }

    static void scan(ArrayList<Integer> q, int n, int start, int direction) {
        int i;
        if (direction == 1) {
            for (i = start; i < n; i++) {
                if (q.contains(i)) {
                    System.out.println("Serving " + i);
                    q.remove(Integer.valueOf(i));
                }
            }
            for (i = n - 1; i >= 0; i--) {
                if (q.contains(i)) {
                    System.out.println("Serving " + i);
                    q.remove(Integer.valueOf(i));
                }
            }
        } else {
            for (i = start; i >= 0; i--) {
                if (q.contains(i)) {
                    System.out.println("Serving " + i);
                    q.remove(Integer.valueOf(i));
                }
            }
            for (i = 0; i < n; i++) {
                if (q.contains(i)) {
                    System.out.println("Serving " + i);
                    q.remove(Integer.valueOf(i));
                }
            }
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

N = 100005

def scan(q, n, start, direction):
    if direction == 1:
        for i in range(start, n):
            if i in q:
                print("Serving", i)
                q.remove(i)
        for i in range(n - 1, -1, -1):
            if i in q:
                print("Serving", i)
                q.remove(i)
    else:
        for i in range(start, -1, -1):
            if i in q:
                print("Serving", i)
                q.remove(i)
        for i in range(0, n):
            if i in q:
                print("Serving", i)
                q.remove(i)

if __name__ == "__main__":
    n, head, tail = map(int, input().split())
    q = []
    for _ in range(n):
        q.append(int(input()))

    direction = 1 if head < tail else -1
    scan(q, n, head, direction)

You can also try this code with Online Python Compiler

Run Code

Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const N = 100005;
let q = [];

function scan(q, n, start, direction) {
    if (direction == 1) {
        for (let i = start; i < n; i++) {
            if (q.includes(i)) {
                console.log("Serving " + i);
                q.splice(q.indexOf(i), 1);
            }
        }
        for (let i = n - 1; i >= 0; i--) {
            if (q.includes(i)) {
                console.log("Serving " + i);
                q.splice(q.indexOf(i), 1);
            }
        }
    } else {
        for (let i = start; i >= 0; i--) {
            if (q.includes(i)) {
                console.log("Serving " + i);
                q.splice(q.indexOf(i), 1);
            }
        }
        for (let i = 0; i < n; i++) {
            if (q.includes(i)) {
                console.log("Serving " + i);
                q.splice(q.indexOf(i), 1);
            }
        }
    }
}

rl.question('', (input) => {
    const inputs = input.split(' ').map(Number);
    const n = inputs[0];
    const head = inputs[1];
    const tail = inputs[2];

    rl.question('', (data) => {
        const dataArray = data.split(' ').map(Number);
        q = dataArray;

        const direction = (head < tail) ? 1 : -1;
        scan(q, n, head, direction);

        rl.close();
    });
});

You can also try this code with Online Javascript Compiler

Run Code

Example Input 

n: 5
head: 20
tail: 10
Disk requests (sequence of inputs): 18, 20, 22, 15, 17

Example Output

Serving 20
Serving 18
Serving 17
Serving 15
Serving 22

Frequently Asked Questions  

What is SCAN in disk scheduling algorithm?

SCAN (Elevator Algorithm) moves the disk arm in one direction, servicing requests sequentially, then reverses direction, improving seek time efficiency.

What is SCAN operation in DBMS?

In DBMS, a SCAN operation sequentially reads all records in a table or index, often used in full-table scans when no index is available.

What is the disk scheduling algorithm?

A disk scheduling algorithm manages read/write requests in an optimized order to minimize seek time. Examples include FCFS, SSTF, SCAN, and C-SCAN.

Conclusion

In this article, we have discussed SCAN (Elevator) Disk Scheduling Algorithms. These algorithms offer efficient data retrieval by mimicking elevator mechanisms. By prioritizing accessibility and optimizing disk access, SCAN algorithms contribute significantly to system performance and resource utilization in modern computing environments.

Recommended Reading:

• SSTF Disk Scheduling Algorithm
• C-SCAN Algorithm
• Difference between FCFS and SCAN Disk Scheduling Algorithms
• LOOK and C-LOOK Algorithms
• Difference between LOOK and C-LOOK Algorithms
• FCFS Scheduling
• Free Space Management in OS