LOOK Disk Scheduling Algorithm
Last Updated :
06 Sep, 2023
The LOOK Disk Scheduling Algorithm is the advanced version of the SCAN (elevator) disk scheduling algorithm which gives slightly better seek time than any other algorithm in the hierarchy (FCFS->SRTF->SCAN->C-SCAN->LOOK). It is used to reduce the amount of time it takes to access data on a hard disk drive by minimizing the seek time between read/write operations. The LOOK algorithm operates by scanning the disk in a specific direction, but instead of going all the way to the end of the disk before reversing direction like the SCAN algorithm, it reverses direction as soon as it reaches the last request in the current direction.
The LOOK algorithm services request similarly to the SCAN Algorithm meanwhile it also “looks” ahead as if there are more tracks that are needed to be serviced in the same direction. The main reason behind the better performance of the LOOK algorithm in comparison to SCAN is that in this algorithm the head is not allowed to move till the end of the disk.
Steps Involved in the LOOK Algorithm
- Determine the initial direction of disk head movement.
- Sort the pending disk requests in the order in which they will be serviced.
- Scan the disk in the chosen direction, servicing requests as they are encountered.
- When the last request in the current direction has been serviced, reverse the direction and continue scanning until all requests have been serviced.
Advantages of the LOOK Disk Scheduling Algorithm
- It can provide better performance than the FCFS (first-come, first-served) and SSTF (shortest-seek-time-first) algorithms because it reduces the number of head movements required to access data on the disk.
- It is relatively simple to implement and does not require a large amount of memory or processing power.
- It is efficient in terms of disk usage because it scans only the areas of the disk where data is located.
Disadvantages of the LOOK Disk Scheduling Algorithm
- It may not be optimal in situations where there are large amounts of data to be read or written in one direction, as it could lead to a large number of requests being queued up in the opposite direction.
- It may not be suitable for real-time systems where fast response times are critical, as it does not prioritize requests based on their urgency or importance.
- It may lead to starvation of requests that are located far away from the current position of the disk head.
- Given an array of disk track numbers and initial head position, our task is to find the total number of seek operations to access all the requested tracks if the LOOK disk scheduling algorithm is used. Also, write a program to find the seek sequence using the LOOK disk scheduling algorithm.
Algorithm for LOOK Disk Scheduling
Step 1: Let the Request array represents an array storing indexes of tracks that have been requested in ascending order of their time of arrival. ‘head’ is the position of the disk head.
Step 2: The initial direction in which the head is moving is given and it services in the same direction.
Step 3: The head services all the requests one by one in the direction head is moving.
Step 4: The head continues to move in the same direction until all the requests in this direction are finished.
Step 5: While moving in this direction calculate the absolute distance of the track from the head.
Step 6: Increment the total seek count with this distance.
Step 7: Currently serviced track position now becomes the new head position.
Step 8: Go to step 5 until we reach at last request in this direction.
Step 9: If we reach where no requests are needed to be serviced in this direction reverse the direction and go to step 3 until all tracks in the request array have not been serviced.
Example
Input:
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = right (We are moving from left to right)
Output:
Initial position of head: 50
Total number of seek operations = 291
Seek Sequence: 60, 79, 92, 114, 176, 41, 34, 11
The following chart shows the sequence in which requested tracks are serviced using LOOK.
LOOK Disk Scheduling Algorithm
Therefore, the total seek count is calculated as
Total Seek Time = (60-50) + (79-60) + (92-79) + (114-92) + (176-114) + (176-41) + (41-34) + (34-11)
= 291
Implementation of LOOK Disk Scheduling Algorithm
Implementation of the LOOK Algorithm is given below.
Note: The distance variable is used to store the absolute distance between the head and the current track position. disk_size is the size of the disk. Vectors left and right store all the request tracks on the left-hand side and the right-hand side of the initial head position respectively.
C++
int size = 8;
#include <bits/stdc++.h>
using namespace std;
int disk_size = 200;
void LOOK(int arr[], int head, string direction)
{
int seek_count = 0;
int distance, cur_track;
vector<int> left, right;
vector<int> seek_sequence;
for (int i = 0; i < size; i++) {
if (arr[i] < head)
left.push_back(arr[i]);
if (arr[i] > head)
right.push_back(arr[i]);
}
std::sort(left.begin(), left.end());
std::sort(right.begin(), right.end());
int run = 2;
while (run--) {
if (direction == "left") {
for (int i = left.size() - 1; i >= 0; i--) {
cur_track = left[i];
seek_sequence.push_back(cur_track);
distance = abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
direction = "right";
}
else if (direction == "right") {
for (int i = 0; i < right.size(); i++) {
cur_track = right[i];
seek_sequence.push_back(cur_track);
distance = abs(cur_track - head);
seek_count += distance;
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[size] = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
string direction = "right";
cout << "Initial position of head: "
<< head << endl;
LOOK(arr, head, direction);
return 0;
}
|
Java
import java.util.*;
class GFG{
static int size = 8;
static int disk_size = 200;
public static void LOOK(int arr[], int head,
String direction)
{
int seek_count = 0;
int distance, cur_track;
Vector<Integer> left = new Vector<Integer>();
Vector<Integer> right = new Vector<Integer>();
Vector<Integer> seek_sequence = new Vector<Integer>();
for(int i = 0; i < size; i++)
{
if (arr[i] < head)
left.add(arr[i]);
if (arr[i] > head)
right.add(arr[i]);
}
Collections.sort(left);
Collections.sort(right);
int run = 2;
while (run-- > 0)
{
if (direction == "left")
{
for(int i = left.size() - 1;
i >= 0; i--)
{
cur_track = left.get(i);
seek_sequence.add(cur_track);
distance = Math.abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
direction = "right";
}
else if (direction == "right")
{
for(int i = 0; i < right.size(); i++)
{
cur_track = right.get(i);
seek_sequence.add(cur_track);
distance = Math.abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
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));
}
}
public static void main(String[] args) throws Exception
{
int arr[] = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
String direction = "right";
System.out.println("Initial position of head: " +
head);
LOOK(arr, head, direction);
}
}
|
Python3
size = 8
disk_size = 200
def LOOK(arr, head, direction):
seek_count = 0
distance = 0
cur_track = 0
left = []
right = []
seek_sequence = []
for i in range(size):
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 range(len(left) - 1, -1, -1):
cur_track = left[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 range(len(right)):
cur_track = right[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")
for i in range(len(seek_sequence)):
print(seek_sequence[i])
arr = [ 176, 79, 34, 60, 92, 11, 41, 114 ]
head = 50
direction = "right"
print("Initial position of head:", head)
LOOK(arr, head, direction)
|
C#
using System;
using System.Collections.Generic;
class GFG{
static int size = 8;
static void LOOK(int[] arr, int head,
string direction)
{
int seek_count = 0;
int distance, cur_track;
List<int> left = new List<int>();
List<int> right = new List<int>();
List<int> seek_sequence = new List<int>();
for(int i = 0; i < size; i++)
{
if (arr[i] < head)
left.Add(arr[i]);
if (arr[i] > head)
right.Add(arr[i]);
}
left.Sort();
right.Sort();
int run = 2;
while (run-- > 0)
{
if (direction == "left")
{
for(int i = left.Count - 1; i >= 0; i--)
{
cur_track = left[i];
seek_sequence.Add(cur_track);
distance = Math.Abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
direction = "right";
}
else if (direction == "right")
{
for(int i = 0; i < right.Count; i++)
{
cur_track = right[i];
seek_sequence.Add(cur_track);
distance = Math.Abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
direction = "left";
}
}
Console.WriteLine("Total number of seek " +
"operations = " + seek_count);
Console.WriteLine("Seek Sequence is");
for(int i = 0; i < seek_sequence.Count; i++)
{
Console.WriteLine(seek_sequence[i]);
}
}
static void Main()
{
int[] arr = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
string direction = "right";
Console.WriteLine("Initial position of head: " +
head);
LOOK(arr, head, direction);
}
}
|
Javascript
<script>
let size = 8;
function LOOK(arr, head, direction)
{
let seek_count = 0;
let distance, cur_track;
let left = [];
let right = [];
let seek_sequence = [];
for(let i = 0; i < size; i++)
{
if (arr[i] < head)
left.push(arr[i]);
if (arr[i] > head)
right.push(arr[i]);
}
left.sort(function(a, b){return a - b});
right.sort(function(a, b){return a - b});
let run = 2;
while (run-- > 0)
{
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")
{
for(let i = 0; i < right.length; i++)
{
cur_track = right[i];
seek_sequence.push(cur_track);
distance = Math.abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
direction = "left";
}
}
document.write("Total number of seek " +
"operations = " + seek_count + "</br>");
document.write("Seek Sequence is" + "</br>");
for(let i = 0; i < seek_sequence.length; i++)
{
document.write(seek_sequence[i] + "</br>");
}
}
let arr = [176, 79, 34, 60, 92, 11, 41, 114];
let head = 50;
let direction = "right";
document.write("Initial position of head: " + head + "</br>");
LOOK(arr, head, direction);
</script>
|
Output
Initial position of head: 50
Total number of seek operations = 291
Seek Sequence: 60, 79, 92, 114, 176, 41, 34, 11
Similar Reads
Disk Scheduling Algorithms
Disk scheduling algorithms are crucial in managing how data is read from and written to a computer's hard disk. These algorithms help determine the order in which disk read and write requests are processed, significantly impacting the speed and efficiency of data access. Common disk scheduling metho
12 min read
FCFS Disk Scheduling Algorithms
Prerequisite: Disk scheduling algorithms.Given an array of disk track numbers and initial head position, our task is to find the total number of seek operations done to access all the requested tracks if First Come First Serve (FCFS) disk scheduling algorithm is used. First Come First Serve (FCFS) F
6 min read
FScan disk scheduling algorithm
Fixed period SCAN (FSCAN) disk scheduling algorithm mainly focuses on handling high variance in shortest seek time first (SSTF). SCAN algorithm is also proposed to handle above mentioned situation but using SCAN algorithm causes long delay while handling requests which are at extremes of disk. FSCAN
3 min read
C-SCAN Disk Scheduling Algorithm
Given an array of disk track numbers and initial head position, our task is to find the total number of seek operations to access all the requested tracks if a C-SCAN Disk Scheduling algorithm is used. The Circular SCAN (C-SCAN) Scheduling Algorithm is a modified version of the SCAN Disk Scheduling
12 min read
SCAN (Elevator) Disk Scheduling Algorithms
In the SCAN Disk Scheduling Algorithm, the head starts from one end of the disk and moves towards the other end, servicing requests in between one by one and reaching the other end. Then the direction of the head is reversed and the process continues as the head continuously scans back and forth to
12 min read
Program for SSTF Disk Scheduling Algorithm
Given an array of disk track numbers and initial head position, our task is to find the total number of seek operations done to access all the requested tracks if Shortest Seek Time First (SSTF) is a disk scheduling algorithm is used. The basic idea is the tracks that are closer to the current disk
10 min read
Program for HRRN CPU Scheduling Algorithm
The Highest Response Ratio Next (HRRN) scheduling algorithm is a non-preemptive scheduling technique used in operating systems to manage the execution of processes. It is designed to improve upon simpler algorithms like First-Come-First-Serve (FCFS) and Shortest Job Next (SJN) by balancing both the
15 min read
Longest Job First (LJF) CPU Scheduling Algorithm
Longest Job First (LJF) is a non-preemptive scheduling algorithm. This algorithm is based on the burst time of the processes. The processes are put into the ready queue based on their burst times i.e., in descending order of the burst times. As the name suggests this algorithm is based on the fact t
5 min read
Difference between SSTF and LOOK disk scheduling algorithm
Disk scheduling algorithms are used by operating systems to decide the order in which disk I/O requests are processed. Since disk access time is relatively slow, these algorithms aim to reduce the time it takes to read/write data by optimizing the movement of the disk arm. SSTF(Shortest Seek Time Fi
3 min read
Difference between SCAN and LOOK Disk scheduling algorithms
SCAN disk scheduling algorithm: In SCAN disk scheduling algorithm, head starts from one end of the disk and moves towards the other end, servicing requests in between one by one and reach the other end. Then the direction of the head is reversed and the process continues as head continuously scan ba
4 min read