Look Disk Scheduling

When Do We Use It?

The LOOK disk scheduling algorithm is particularly useful in systems where there is a need for balancing the time taken for disk operations and the overall system performance. It is beneficial in scenarios where:

• The workload on the disk involves frequent read-write operations.
   
• There is a need to reduce the average seek time, which is critical for systems that require fast data retrieval and storage.
   
• The system aims to avoid the starvation of disk requests, a common problem in simpler algorithms like FCFS.
   
• This algorithm is most effective in environments where disk I/O operations are a significant bottleneck and where the pattern of requests is not uniform across the disk's surface.

Explanation of the LOOK Disk Scheduling Algorithm

The LOOK algorithm operates on a simple yet effective principle. It focuses on the direction in which the disk head is moving and services only those requests that are in its path. The key steps in the algorithm's operation are as follows:

• Initialization: The disk head starts at a certain position, and a queue of requests is established. The initial direction of the disk head's movement is set, either towards the higher track numbers or the lower ones.
   
• Servicing Requests: The disk head moves in the set direction, servicing all the requests it encounters along the way. Each request is for the disk head to move to a specific track on the disk.
   
• Direction Change: When the disk head reaches the furthest request in its current direction, or there are no more requests in that direction, it 'looks' in the opposite direction.
   
• Continuation: The disk head then starts moving in the new direction, servicing requests as it goes. This process continues, with the disk head changing direction each time it runs out of requests to service or reaches the end of the disk.
   
• Completion: The algorithm concludes when all requests have been serviced.

The LOOK algorithm is efficient because it reduces the disk head's movement. Unlike algorithms that make the disk head move back and forth across the entire disk (like FCFS), LOOK focuses only on the active part of the disk where requests are pending. This optimization leads to faster average seek times.

Steps Involved in the LOOK Algorithm

To understand the LOOK algorithm in action, let's consider an example. Assume the disk head starts at track 50, and we have a queue of requests: [40, 10, 35, 70, 20, 75]. Let's also assume the initial direction is towards the higher track numbers.

• Starting Point: Disk head is at track 50.
   
• Move Towards Higher Tracks: The disk head moves towards higher numbers, servicing requests at 70 and 75.
   
• Change Direction: After servicing the highest request (75), the disk head reverses direction.
   
• Service Lower Tracks: As it moves back, the disk head services requests at 40, 35, 20, and finally 10.
   
• Completion: All requests are serviced, and the algorithm ends.

This example demonstrates how the LOOK algorithm works step by step, servicing requests efficiently by changing direction only when necessary.

Advantages of the LOOK Disk Scheduling Algorithm

The LOOK disk scheduling algorithm offers several advantages that make it a preferred choice in many scenarios:

• Reduced Seek Time: By servicing only the requests in its current path, the disk head movement is minimized, leading to a reduction in the average seek time compared to simpler algorithms like FCFS.
   
• Efficiency in Handling Requests: LOOK is more efficient in servicing requests as it avoids unnecessary travel to the end of the disk if there are no requests in that direction. This efficiency is particularly noticeable in systems with a high number of disk operations.
   
• Fairness and Avoidance of Starvation: Unlike SSTF, which may cause starvation of certain requests, the LOOK algorithm ensures that all requests are eventually serviced as the disk head reverses its direction at the end of each sweep.
   
• Balanced Approach: LOOK strikes a balance between servicing requests quickly (like in SSTF) and ensuring that all requests are serviced fairly (unlike in algorithms like C-SCAN where outer tracks might get less priority).
   
• Scalability: This algorithm scales well with an increasing number of disk requests, maintaining a consistent performance level.

Disadvantages of the LOOK Disk Scheduling Algorithm

Despite its advantages, the LOOK algorithm has certain limitations:

• Variable Response Time: The time taken to service a request can vary significantly, especially if a request is just missed by the disk head in its current sweep.
   
• Complexity in Implementation: Implementing the LOOK algorithm is more complex than simpler algorithms like FCFS or SSTF, requiring more sophisticated control logic in the disk controller.
   
• Not Optimal for Sparse Requests: In situations where disk requests are sparse and spread out, the algorithm may not offer significant improvements over simpler methods.
   
• Potential for Inefficiency in Heavy Loads: Under heavy loads with requests distributed across the entire disk, the LOOK algorithm might still incur considerable seek times.

Algorithm for LOOK Disk Scheduling

The LOOK disk scheduling algorithm can be broken down into a series of steps. Let's walk through these steps with an example for clarity:

Initialize Variables: Start with the current head position and a list of disk requests. For example, let's say the head starts at position 50 and the request queue is [40, 10, 35, 70, 20, 75].

• Sort Requests: Arrange the requests in ascending order: [10, 20, 35, 40, 70, 75].
   
• Determine Direction: Decide the initial direction of head movement (towards higher or lower track numbers). Let's assume it's towards the higher numbers.
   
• Service Requests in Direction: Move the head towards the higher numbers and service each request on the way. In our example, the requests 70 and 75 are serviced.
   
• Reverse Direction: Once the last request in the direction is serviced, or there are no more requests in that direction, reverse the head's direction.
   
• Service Requests in Opposite Direction: Now service the requests in the opposite direction. In our example, the head services 40, 35, 20, and finally 10.
   
• Repeat: Continue this process until all requests are serviced.
   
• Terminate: The algorithm terminates when all requests have been serviced.

Implementation of LOOK Disk Scheduling Algorithm

Let's implement this algorithm in different programming languages. We will start with Java.

• Java
• C++
• Python
• Javascript

Java

import java.util.ArrayList;
import java.util.Collections;
public class LookDiskScheduling {
    static void LOOK(int arr[], int head, String direction) {
        int seek_count = 0;
        int distance, cur_track;
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        ArrayList<Integer> seek_sequence = new ArrayList<>();

        // Appending values to the right and left of the head
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < head) left.add(arr[i]);
            if (arr[i] > head) right.add(arr[i]);
        }
        // Sorting left and right lists
        Collections.sort(left);
        Collections.sort(right);

        // Run the while loop two times, one for left and one for right
        int run = 2;
        while (run-- > 0) {
            if (direction.equals("left")) {
                for (int i = left.size() - 1; i >= 0; i--) {
                    cur_track = left.get(i);

                    // Appending current track to seek sequence
                    seek_sequence.add(cur_track);

                    // Calculate absolute distance
                    distance = Math.abs(cur_track - head);

                    // Increase the total count
                    seek_count += distance;

                    // Accessed track is now the new head
                    head = cur_track;
                }
                // Reversing the direction
                direction = "right";
            }
            else if (direction.equals("right")) {
                for (int i = 0; i < right.size(); i++) {
                    cur_track = right.get(i);

                    // Appending current track to seek sequence
                    seek_sequence.add(cur_track);

                    // Calculate absolute distance
                    distance = Math.abs(cur_track - head);

                    // Increase the total count
                    seek_count += distance;

                    // Accessed track is now the new head
                    head = cur_track;
                }
                // Reversing the direction
                direction = "left";
            }
        }

        System.out.println("Total number of seek operations = " + seek_count);
        System.out.println("Seek Sequence is");
        for (int i = 0; i < seek_sequence.size(); i++) {
            System.out.println(seek_sequence.get(i));
        }
    }

    // Driver code
    public static void main(String[] args) {
        // Request array
        int arr[] = {40, 10, 35, 70, 20, 75};
        int head = 50;

        String direction = "right";

        LOOK(arr, head, direction);
    }
}

You can also try this code with Online Java Compiler

Run Code

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void LOOK(int arr[], int n, int head, string direction) {
    int seek_count = 0;
    int distance, cur_track;
    vector<int> left, right;
    vector<int> seek_sequence;

    // Appending end values to left and right vectors
    for (int i = 0; i < n; i++) {
        if (arr[i] < head)
            left.push_back(arr[i]);
        if (arr[i] > head)
            right.push_back(arr[i]);
    }

    // Sorting the vectors
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    // Running the algorithm twice
    for (int i = 0; i < 2; i++) {
        if (direction == "left") {
            for (int j = left.size() - 1; j >= 0; j--) {
                cur_track = left[j];
                seek_sequence.push_back(cur_track);

                // Calculating the seek count
                seek_count += abs(cur_track - head);
                head = cur_track;
            }
            direction = "right";
        }
        else if (direction == "right") {
            for (int j = 0; j < right.size(); j++) {
                cur_track = right[j];
                seek_sequence.push_back(cur_track);

                // Calculating the seek count
                seek_count += abs(cur_track - head);
                head = cur_track;
            }
            direction = "left";
        }
    }

    cout << "Total number of seek operations = " << seek_count << endl;
    cout << "Seek Sequence is: " << endl;

    for (int i = 0; i < seek_sequence.size(); i++) {
        cout << seek_sequence[i] << endl;
    }
}

int main() {
    int arr[] = {40, 10, 35, 70, 20, 75};
    int head = 50;
    string direction = "right";

    LOOK(arr, sizeof(arr) / sizeof(arr[0]), head, direction);

    return 0;
}

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

Run Code

Python

def LOOK(arr, head, direction):
    seek_count = 0
    distance = 0
    cur_track = 0
    left = []
    right = []
    seek_sequence = []

    for i in range(len(arr)):
        if arr[i] < head:
            left.append(arr[i])
        if arr[i] > head:
            right.append(arr[i])

    left.sort()
    right.sort()

    run = 2
    while run:
        if direction == "left":
            for i in reversed(left):
                cur_track = i
                seek_sequence.append(cur_track)
                distance = abs(cur_track - head)
                seek_count += distance
                head = cur_track
            direction = "right"
        elif direction == "right":
            for i in right:
                cur_track = i
                seek_sequence.append(cur_track)
                distance = abs(cur_track - head)
                seek_count += distance
                head = cur_track
            direction = "left"
        run -= 1

    print("Total number of seek operations =", seek_count)
    print("Seek Sequence is")
    print(seek_sequence)

# Example usage
arr = [40, 10, 35, 70, 20, 75]
head = 50
direction = "right"
LOOK(arr, head, direction)

You can also try this code with Online Python Compiler

Run Code

Javascript

function LOOK(arr, head, direction) {
    let seek_count = 0;
    let distance, cur_track;
    let left = [], right = [];
    let seek_sequence = [];

    arr.forEach((track) => {
        if (track < head) left.push(track);
        if (track > head) right.push(track);
    });

    left.sort((a, b) => a - b);
    right.sort((a, b) => a - b);

    let run = 2;
    while (run) {
        if (direction === "left") {
            for (let i = left.length - 1; i >= 0; i--) {
                cur_track = left[i];
                seek_sequence.push(cur_track);
                distance = Math.abs(cur_track - head);
                seek_count += distance;
                head = cur_track;
            }
            direction = "right";
        } else if (direction === "right") {
            right.forEach((track) => {
                cur_track = track;
                seek_sequence.push(cur_track);
                distance = Math.abs(cur_track - head);
                seek_count += distance;
                head = cur_track;
            });
            direction = "left";
        }
        run--;
    }

    console.log("Total number of seek operations =", seek_count);
    console.log("Seek Sequence is", seek_sequence);
}

// Example usage
let arr = [40, 10, 35, 70, 20, 75];
let head = 50;
let direction = "right";
LOOK(arr, head, direction);

You can also try this code with Online Javascript Compiler

Run Code

Output

• In this Java example, we start with a disk head at position 50 and a set of requests. The program sorts these requests and then services them in the order dictated by the LOOK algorithm, first in the 'right' direction and then 'left'.
   
• In the C++ example, the algorithm follows a similar approach as the Java implementation. It sorts the requests, then processes them in the given direction, changing direction after processing all requests in one sweep.
   
• In the Python implementation, the algorithm services requests based on the current direction of the disk head and switches direction after servicing the requests in one path.
   
• In the JavaScript implementation, the functionality remains consistent with the previous examples, demonstrating how the LOOK algorithm works in a web-based programming context.

See More, Demand Paging in OS

Also Read, Multiprocessing in Operating System

Check this out, pcb in operating system

Frequently Asked Questions

How does the LOOK algorithm work?

The LOOK algorithm in disk scheduling optimizes read/write head movement on a disk. It moves the head towards the nearest end while servicing all requests in its path, then reverses direction upon reaching the end or the nearest request, effectively 'looking' for the closest request in its current direction. This reduces the total head movement, improving efficiency compared to algorithms like FCFS (First Come First Serve) or SSTF (Shortest Seek Time First)

What is the difference between SCAN and look disk scheduling?

The key difference between SCAN and LOOK disk scheduling algorithms lies in their handling of disk arm movement. In SCAN, the disk arm moves to the very end of the disk, regardless of requests. In contrast, LOOK stops the arm's movement as soon as the furthest request in that direction has been serviced, potentially reducing unnecessary travel.

How does the LOOK algorithm prevent the starvation of disk requests?

Starvation occurs when certain requests are perpetually overlooked in favor of others. The LOOK algorithm services requests in the direction of the disk head's movement and then reverses direction, ensuring that requests in both directions are eventually serviced. This method prevents the starvation of requests, as all pending requests are addressed during the disk head's sweep back and forth.

Can the LOOK algorithm be used for both SSDs and HDDs?

While the LOOK algorithm is primarily designed for use with HDDs (Hard Disk Drives), where the physical movement of the disk head is a significant factor in read/write speeds, it can technically be applied to SSDs (Solid State Drives) as well. However, the benefits may not be as pronounced in SSDs since they don't have moving parts and access time is more uniform across the storage.

Conclusion

The LOOK disk scheduling algorithm presents a significant improvement over simpler algorithms like FCFS, especially in environments with heavy disk usage. Its method of servicing requests in the direction of movement and then reversing reduces the average seek time, leading to more efficient disk operations. The implementations in Java, C++, Python, and JavaScript highlight its versatility across different programming languages and environments.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. 

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.