Requisito previo: algoritmos de programación de disco y algoritmo de programación de disco SCAN
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 utiliza un algoritmo de programación de disco C-SCAN.
Algoritmo de programación de disco C-SCAN (ascensor circular)
El algoritmo de programación SCAN circular (C-SCAN) es una versión modificada del algoritmo de programación de disco SCAN que se ocupa de la ineficiencia del algoritmo SCAN al atender las requests de manera más uniforme. Al igual que SCAN (algoritmo de elevador), C-SCAN mueve la cabeza de un extremo atendiendo todas las requests al otro extremo. Sin embargo, tan pronto como la cabeza llega al otro extremo, regresa inmediatamente al principio del disco sin atender ninguna solicitud en el viaje de regreso (consulte el cuadro a continuación) y comienza a atender nuevamente una vez que llega al principio. Esto también se conoce como el «algoritmo del elevador circular», ya que esencialmente trata a los cilindros como una lista circular que va desde el último cilindro hasta el primero.
Ventajas del algoritmo de programación de disco C-SCAN (ascensor circular):
- Funciona bien con cargas moderadas a pesadas.
- Proporciona un mejor tiempo de respuesta y un tiempo de espera uniforme.
Desventajas del algoritmo de programación de disco C-SCAN (ascensor circular):
- Puede que no sea justo atender las requests de pistas en el extremo final.
- Tiene más movimientos de búsqueda en comparación con el algoritmo SCAN.
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.
- Los servicios de la cabeza solo en la dirección correcta desde 0 hasta el tamaño del disco.
- Mientras se mueve en la dirección izquierda, no dé servicio a ninguna de las vías.
- Cuando lleguemos al principio (extremo izquierdo) invierta la dirección.
- Mientras se mueve en la dirección correcta, da servicio a todas las pistas una por una.
- Mientras se mueve en la dirección correcta, 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.
- Ir al paso 6 hasta llegar al extremo derecho del disco.
- Si llegamos al extremo derecho del disco, invierta la dirección y vaya al paso 3 hasta que no se hayan atendido todas las pistas en la array de solicitud.
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 = 389
Seek Sequence is
60
79
92
114
176
199
0
11
34
41
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:
= (60-50)+(79-60)+(92-79)
+(114-92)+(176-114)+(199-176)+(199-0)
+(11-0)+(34-11)+(41-34)
= 389
Implementación:
La implementación del algoritmo C-SCAN 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
// C-SCAN Disk Scheduling algorithm
#include <bits/stdc++.h>
using namespace std;
// Code by Vikram Chaurasia
int size = 8;
int disk_size = 200;
void CSCAN(int arr[], int head)
{
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
left.push_back(0);
right.push_back(disk_size - 1);
// tracks on the left of the
// head will be serviced when
// once the head comes back
// to the beginning (left end).
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());
// first service the requests
// on the right side of the
// head.
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;
}
// once reached the right end
// jump to the beginning.
head = 0;
// adding seek count for head returning from 199 to 0
seek_count += (disk_size - 1);
// Now service the requests again
// which are left.
for (int i = 0; i < left.size(); 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;
}
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;
cout << "Initial position of head: " << head << endl;
CSCAN(arr, head);
return 0;
}
Java
// Java program to demonstrate
// C-SCAN Disk Scheduling algorithm
import java.util.*;
class GFG {
static int size = 8;
static int disk_size = 200;
public static void CSCAN(int arr[], int head)
{
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 end values which has
// to be visited before reversing
// the direction
left.add(0);
right.add(disk_size - 1);
// Tracks on the left of the
// head will be serviced when
// once the head comes back
// to the beggining (left end).
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);
// First service the requests
// on the right side of the
// head.
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;
}
// Once reached the right end
// jump to the beggining.
head = 0;
// adding seek count for head returning from 199 to
// 0
seek_count += (disk_size - 1);
// Now service the requests again
// which are left.
for (int i = 0; i < left.size(); 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;
}
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;
System.out.println("Initial position of head: "
+ head);
CSCAN(arr, head);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program to demonstrate
# C-SCAN Disk Scheduling algorithm
size = 8
disk_size = 200
def CSCAN(arr, head):
seek_count = 0
distance = 0
cur_track = 0
left = []
right = []
seek_sequence = []
# Appending end values
# which has to be visited
# before reversing the direction
left.append(0)
right.append(disk_size - 1)
# Tracks on the left of the
# head will be serviced when
# once the head comes back
# to the beggining (left end).
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()
# First service the requests
# on the right side of the
# head.
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
# Once reached the right end
# jump to the beggining.
head = 0
# adding seek count for head returning from 199 to 0
seek_count += (disk_size - 1)
# Now service the requests again
# which are left.
for i in range(len(left)):
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
print("Total number of seek operations =",
seek_count)
print("Seek Sequence is")
print(*seek_sequence, sep="\n")
# Driver code
# request array
arr = [176, 79, 34, 60,
92, 11, 41, 114]
head = 50
print("Initial position of head:", head)
CSCAN(arr, head)
# This code is contributed by rag2127
C#
// C# program to demonstrate
// C-SCAN Disk Scheduling algorithm
using System;
using System.Collections.Generic;
class GFG {
static int size = 8;
static int disk_size = 200;
static void CSCAN(int[] arr, int head)
{
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 end values which has
// to be visited before reversing
// the direction
left.Add(0);
right.Add(disk_size - 1);
// Tracks on the left of the
// head will be serviced when
// once the head comes back
// to the beggining (left end).
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();
// First service the requests
// on the right side of the
// head.
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;
}
// Once reached the right end
// jump to the beggining.
head = 0;
// adding seek count for head returning from 199 to
// 0
seek_count += (disk_size - 1);
// Now service the requests again
// which are left.
for (int i = 0; i < left.Count; 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;
}
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;
Console.WriteLine("Initial position of head: "
+ head);
CSCAN(arr, head);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to demonstrate
// C-SCAN Disk Scheduling algorithm
let size = 8;
let disk_size = 200;
function CSCAN(arr, head)
{
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
left.push(0);
right.push(disk_size - 1);
// tracks on the left of the
// head will be serviced when
// once the head comes back
// to the beggining (left end).
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});
// first service the requests
// on the right side of the
// head.
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;
}
// once reached the right end
// jump to the beggining.
head = 0;
// adding seek count for head returning from 199 to 0
seek_count += (disk_size - 1);
// Now service the requests again
// which are left.
for (let i = 0; i < left.length; 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;
}
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;
document.write("Initial position of head: " + head + "</br>");
CSCAN(arr, head);
// This code is contributed by mukesh07.
</script>
Producción
Initial position of head: 50 Total number of seek operations = 389 Seek Sequence is 60 79 92 114 176 199 0 11 34 41