Requisito previo: algoritmos de programación de discos.
Dada una array de números de pista de disco y la posición inicial del cabezal, 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 SCAN.
Algoritmo SCAN (ascensor)
En el algoritmo de programación de disco SCAN, la cabeza comienza desde un extremo del disco y se mueve hacia el otro extremo, atendiendo las requests en el medio una por una y llegando al otro extremo. Luego, la dirección de la cabeza se invierte y el proceso continúa mientras la cabeza escanea continuamente hacia adelante y hacia atrás para acceder al disco. Entonces, este algoritmo funciona como un ascensor y, por lo tanto, también se conoce como el algoritmo del ascensor . Como resultado, las requests en el rango medio se atienden más y las que llegan detrás del brazo del disco tendrán que esperar.
Ventajas del algoritmo SCAN (Ascensor)
- Este algoritmo es simple y fácil de entender.
- El algoritmo SCAN no tiene hambre.
- Este algoritmo es mejor que el algoritmo de programación FCFS.
Desventajas del algoritmo SCAN (Ascensor)
- Algoritmo más complejo de implementar.
- Este algoritmo no es justo porque provoca largos tiempos de espera para los cilindros recién visitados por la cabeza.
- Hace que la cabeza se mueva hasta el final del disco, de esta manera, las requests que lleguen antes de la posición del brazo obtendrán un servicio inmediato, pero algunas otras requests que lleguen detrás de la posición del brazo tendrán que esperar a que se complete la solicitud.
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.
- Let direction representa si la cabeza se mueve hacia la izquierda o hacia la derecha.
- En la dirección en la que se mueve el cabezal de servicio todas las pistas una a una.
- Calcular 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.
- Ir al paso 3 hasta llegar a uno de los extremos del disco.
- Si llegamos al final del disco, invierta la dirección y vaya al paso 2 hasta que no se hayan atendido todas las pistas en la array de solicitud.
Ejemplo:
Input:
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = left (We are moving from right to left)
Output:
Total number of seek operations = 226
Seek Sequence is
41
34
11
0
60
79
92
114
176
El siguiente gráfico muestra la secuencia en la que se atienden las pistas solicitadas mediante SCAN.
Por lo tanto, el conteo total de búsquedas se calcula como:
= (50-41)+(41-34)+(34-11) +(11-0)+(60-0)+(79-60) +(92-79)+(114-92)+(176-114) = 226
Implementación:
La implementación de SCAN se proporciona a continuación. Tenga en cuenta que la distancia se utiliza para almacenar la distancia absoluta entre el cabezal 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
// SCAN Disk Scheduling algorithm
#include <bits/stdc++.h>
using namespace std;
int size = 8;
int disk_size = 200;
void SCAN(int arr[], int head, string direction)
{
int seek_count = 0;
int distance, cur_track;
vector<int> left, right;
vector<int> seek_sequence;
// appending end values
// which has to be visited
// before reversing the direction
if (direction == "left")
left.push_back(0);
else if (direction == "right")
right.push_back(disk_size - 1);
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
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 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;
}
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;
}
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 = "left";
SCAN(arr, head, direction);
return 0;
}
Java
// Java program to demonstrate
// SCAN Disk Scheduling algorithm
import java.util.*;
class GFG
{
static int size = 8;
static int disk_size = 200;
static void SCAN(int arr[], int head, String direction)
{
int seek_count = 0;
int distance, cur_track;
Vector<Integer> left = new Vector<Integer>(),
right = new Vector<Integer>();
Vector<Integer> seek_sequence = new Vector<Integer>();
// appending end values
// which has to be visited
// before reversing the direction
if (direction == "left")
left.add(0);
else if (direction == "right")
right.add(disk_size - 1);
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
Collections.sort(left);
Collections.sort(right);
// run the while loop two times.
// one by one scanning right
// and left 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;
}
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;
}
direction = "left";
}
}
System.out.print("Total number of seek operations = "
+ seek_count + "\n");
System.out.print("Seek Sequence is" + "\n");
for (int i = 0; i < seek_sequence.size(); i++)
{
System.out.print(seek_sequence.get(i) + "\n");
}
}
// Driver code
public static void main(String[] args)
{
// request array
int arr[] = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
String direction = "left";
SCAN(arr, head, direction);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to demonstrate
# SCAN Disk Scheduling algorithm
size = 8
disk_size = 200
def SCAN(arr, head, direction):
seek_count = 0
distance, cur_track = 0, 0
left = []
right = []
seek_sequence = []
# Appending end values
# which has to be visited
# before reversing the direction
if (direction == "left"):
left.append(0)
elif (direction == "right"):
right.append(disk_size - 1)
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
left.sort()
right.sort()
# Run the while loop two times.
# one by one scanning right
# and left of the head
run = 2
while (run != 0):
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
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
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 = "left"
SCAN(arr, head, direction)
# This code is contributed by divyesh072019
C#
// C# program to demonstrate
// SCAN Disk Scheduling algorithm
using System;
using System.Collections.Generic;
class GFG
{
static int size = 8;
static int disk_size = 200;
static void SCAN(int []arr, int head, String direction)
{
int seek_count = 0;
int distance, cur_track;
List<int> left = new List<int>(),
right = new List<int>();
List<int> seek_sequence = new List<int>();
// appending end values
// which has to be visited
// before reversing the direction
if (direction == "left")
left.Add(0);
else if (direction == "right")
right.Add(disk_size - 1);
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
left.Sort();
right.Sort();
// run the while loop two times.
// one by one scanning right
// and left 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;
}
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;
}
direction = "left";
}
}
Console.Write("Total number of seek operations = "
+ seek_count + "\n");
Console.Write("Seek Sequence is" + "\n");
for (int i = 0; i < seek_sequence.Count; i++)
{
Console.Write(seek_sequence[i] + "\n");
}
}
// Driver code
public static void Main(String[] args)
{
// request array
int []arr = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
String direction = "left";
SCAN(arr, head, direction);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to demonstrate
// SCAN Disk Scheduling algorithm
let size = 8;
let disk_size = 200;
function SCAN(arr, head, direction)
{
let seek_count = 0;
let distance, cur_track;
let left = [], right = [];
let seek_sequence = [];
// appending end values
// which has to be visited
// before reversing the direction
if (direction == "left")
left.push(0);
else if (direction == "right")
right.push(disk_size - 1);
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
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 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;
}
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;
}
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 = "left";
SCAN(arr, head, direction);
</script>
Producción:
Total number of seek operations = 226 Seek Sequence is 41 34 11 0 60 79 92 114 176
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)