Requisito previo: Algoritmos de programación de disco
Dada una array de números de pista de disco y la posición inicial de la cabeza, nuestra tarea es encontrar el número total de operaciones de búsqueda realizadas para acceder a todas las pistas solicitadas si se usa el algoritmo de programación de disco LOOK . Además, escriba un programa para encontrar la secuencia de búsqueda usando el algoritmo de programación de disco LOOK .
Algoritmo de programación de disco LOOK:
LOOK es la versión avanzada del algoritmo de programación de disco SCAN (elevador) que brinda un tiempo de búsqueda ligeramente mejor que cualquier otro algoritmo en la jerarquía (FCFS->SRTF->SCAN->C-SCAN->LOOK) . Los servicios del algoritmo LOOK solicitan de manera similar al algoritmo SCAN, mientras que también «mira» hacia adelante como si hubiera más pistas que necesitan servicio en la misma dirección. Si no hay requests pendientes en la dirección de movimiento, el cabezal invierte la dirección y comienza a atender las requests en la dirección opuesta.
La razón principal detrás del mejor rendimiento del algoritmo LOOK en comparación con SCAN es que en este algoritmo la cabeza no puede moverse hasta el final del disco.
Algoritmo:
- Let Request array representa una array que almacena índices de pistas que se han solicitado en orden ascendente de su hora de llegada. ‘cabeza’ es la posición de la cabeza del disco.
- Se da la dirección inicial en la que se mueve la cabeza y sirve en la misma dirección.
- El cabezal atiende todas las requests una por una en la dirección en que se mueve el cabezal.
- La cabeza continúa moviéndose en la misma dirección hasta que se completan todas las requests en esta dirección.
- Mientras se mueve en esta dirección, calcule la distancia absoluta de la pista desde la cabeza.
- Incremente el conteo total de búsqueda con esta distancia.
- La posición de la pista actualmente revisada ahora se convierte en la nueva posición principal.
- Vaya al paso 5 hasta que lleguemos a la última solicitud en esta dirección.
- Si llegamos a donde no se necesitan requests para atender en esta dirección, invierta la dirección y vaya al paso 3 hasta que no se hayan atendido todas las pistas en la array de requests.
Ejemplos:
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 is
60
79
92
114
176
41
34
11
El siguiente gráfico muestra la secuencia en la que se atienden las pistas solicitadas utilizando LOOK.
Por lo tanto, el conteo total de búsquedas se calcula como:
= (60-50)+(79-60)+(92-79)
+(114-92)+(176-114)
+(176-41)+(41-34)+(34-11)
Implementación:
La implementación del algoritmo LOOK se proporciona a continuación.
Nota: La variable de distancia se usa para almacenar la distancia absoluta entre la cabeza y la posición actual de la pista. disk_size es el tamaño del disco. Los vectores izquierdo y derecho almacenan todas las pistas de solicitud en el lado izquierdo y el lado derecho de la posición inicial de la cabeza, respectivamente.
C++
// C++ program to demonstrate
// LOOK Disk Scheduling algorithm
int size = 8;
#include <bits/stdc++.h>
using namespace std;
// Code by Vikram Chaurasia
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;
// appending values which are
// currently at left and right
// direction from the head.
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]);
}
// sorting left and right vectors
// for servicing tracks in the
// correct sequence.
std::sort(left.begin(), left.end());
std::sort(right.begin(), right.end());
// run the while loop two times.
// one by one scanning right
// and left side of the head
int run = 2;
while (run--) {
if (direction == "left") {
for (int i = left.size() - 1; i >= 0; i--) {
cur_track = left[i];
// appending current track to seek sequence
seek_sequence.push_back(cur_track);
// calculate absolute distance
distance = 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 == "right") {
for (int i = 0; i < right.size(); i++) {
cur_track = right[i];
// appending current track to seek sequence
seek_sequence.push_back(cur_track);
// calculate absolute distance
distance = abs(cur_track - head);
// increase the total count
seek_count += distance;
// accessed track is now new head
head = cur_track;
}
// reversing the direction
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;
}
}
// Driver code
int main()
{
// request array
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
// Java program to demonstrate
// LOOK Disk Scheduling algorithm
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>();
// Appending values which are
// currently at left and right
// direction from the head.
for(int i = 0; i < size; i++)
{
if (arr[i] < head)
left.add(arr[i]);
if (arr[i] > head)
right.add(arr[i]);
}
// Sorting left and right vectors
// for servicing tracks in the
// correct sequence.
Collections.sort(left);
Collections.sort(right);
// Run the while loop two times.
// one by one scanning right
// and left side of the head
int run = 2;
while (run-- > 0)
{
if (direction == "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 == "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 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) throws Exception
{
// Request array
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);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program to demonstrate
# LOOK Disk Scheduling algorithm
size = 8
disk_size = 200
def LOOK(arr, head, direction):
seek_count = 0
distance = 0
cur_track = 0
left = []
right = []
seek_sequence = []
# Appending values which are
# currently at left and right
# direction from the head.
for i in range(size):
if (arr[i] < head):
left.append(arr[i])
if (arr[i] > head):
right.append(arr[i])
# Sorting left and right vectors
# for servicing tracks in the
# correct sequence.
left.sort()
right.sort()
# Run the while loop two times.
# one by one scanning right
# and left side of the head
run = 2
while (run):
if (direction == "left"):
for i in range(len(left) - 1, -1, -1):
cur_track = left[i]
# Appending current track to
# seek sequence
seek_sequence.append(cur_track)
# Calculate absolute distance
distance = 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"
elif (direction == "right"):
for i in range(len(right)):
cur_track = right[i]
# Appending current track to
# seek sequence
seek_sequence.append(cur_track)
# Calculate absolute distance
distance = abs(cur_track - head)
# Increase the total count
seek_count += distance
# Accessed track is now new head
head = cur_track
# Reversing the direction
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])
# Driver code
# Request array
arr = [ 176, 79, 34, 60, 92, 11, 41, 114 ]
head = 50
direction = "right"
print("Initial position of head:", head)
LOOK(arr, head, direction)
# This code is contributed by rag2127
C#
// C# program to demonstrate
// LOOK Disk Scheduling algorithm
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>();
// Appending values which are
// currently at left and right
// direction from the head.
for(int i = 0; i < size; i++)
{
if (arr[i] < head)
left.Add(arr[i]);
if (arr[i] > head)
right.Add(arr[i]);
}
// Sorting left and right vectors
// for servicing tracks in the
// correct sequence.
left.Sort();
right.Sort();
// Run the while loop two times.
// one by one scanning right
// and left side of the head
int run = 2;
while (run-- > 0)
{
if (direction == "left")
{
for(int i = left.Count - 1; i >= 0; i--)
{
cur_track = left[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 == "right")
{
for(int i = 0; i < right.Count; i++)
{
cur_track = right[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 new head
head = cur_track;
}
// Reversing the direction
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]);
}
}
// Driver code
static void Main()
{
// Request array
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);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to demonstrate
// LOOK Disk Scheduling algorithm
let size = 8;
function LOOK(arr, head, direction)
{
let seek_count = 0;
let distance, cur_track;
let left = [];
let right = [];
let seek_sequence = [];
// Appending values which are
// currently at left and right
// direction from the head.
for(let i = 0; i < size; i++)
{
if (arr[i] < head)
left.push(arr[i]);
if (arr[i] > head)
right.push(arr[i]);
}
// Sorting left and right vectors
// for servicing tracks in the
// correct sequence.
left.sort(function(a, b){return a - b});
right.sort(function(a, b){return a - b});
// Run the while loop two times.
// one by one scanning right
// and left side of the head
let run = 2;
while (run-- > 0)
{
if (direction == "left")
{
for(let i = left.length - 1; i >= 0; i--)
{
cur_track = left[i];
// Appending current track to
// seek sequence
seek_sequence.push(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 == "right")
{
for(let i = 0; i < right.length; i++)
{
cur_track = right[i];
// Appending current track to
// seek sequence
seek_sequence.push(cur_track);
// Calculate absolute distance
distance = Math.abs(cur_track - head);
// Increase the total count
seek_count += distance;
// Accessed track is now new head
head = cur_track;
}
// Reversing the direction
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>");
}
}
// Request array
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>
Producción:
Initial position of head: 50 Total number of seek operations = 291 Seek Sequence is 60 79 92 114 176 41 34 11