Algoritmo de programación de disco C-LOOK

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 utiliza el algoritmo de programación de disco C-LOOK . Además, escriba un programa para encontrar la secuencia de búsqueda usando el algoritmo de programación de disco C-LOOK .

Algoritmo de programación de disco C-LOOK (LOOK circular):  
C-LOOK es una versión mejorada de los algoritmos de programación de disco SCAN y LOOK . Este algoritmo también usa la idea de envolver las pistas como un cilindro circular como el algoritmo C-SCAN pero el tiempo de búsqueda es mejor que el algoritmo C-SCAN. Sabemos que C-SCAN se usa para evitar el hambre y atender todas las requests de manera más uniforme, lo mismo ocurre con C-LOOK. 
En este algoritmo, el encabezado atiende las requests solo en una dirección (ya sea hacia la izquierda o hacia la derecha) hasta que no se atienden todas las requests en esta dirección y luego vuelve a la solicitud más lejana en la otra dirección y atiende las requests restantes, lo que brinda un mejor uniforme servicio y evita perder el tiempo de búsqueda para ir hasta el final del disco.

Algoritmo- 

1. Let Request array representa una array que almacena índices de las pistas que se han solicitado en orden ascendente de su hora de llegada y head es la posición de la cabeza del disco.
2. Se da la dirección inicial en la que se mueve la cabeza y sirve en la misma dirección.
3. El jefe atiende todas las requests una por una en la dirección en que se mueve.
4. El cabezal continúa moviéndose en la misma dirección hasta que se hayan atendido todas las requests en esta dirección.
5. Mientras se mueve en esta dirección, calcule la distancia absoluta de las huellas desde la cabeza.
6. Incremente el conteo total de búsqueda con esta distancia.
7. La posición de la pista actualmente revisada ahora se convierte en la nueva posición principal.
8. Vaya al paso 5 hasta que lleguemos a la última solicitud en esta dirección.
9. Si llegamos a la última solicitud en la dirección actual, invierta la dirección y mueva el cabezal en esta dirección hasta llegar a la última solicitud que se necesita atender en esta dirección sin atender las requests intermedias.
10. Invierta la dirección y vaya al paso 3 hasta que no se hayan atendido todas las requests.

Ejemplos: 

Entrada: 
Secuencia de solicitud = {176, 79, 34, 60, 92, 11, 41, 114} 
Posición inicial del cabezal = 50 
Dirección = derecha (moviéndose de izquierda a derecha) 
Salida: 
Posición inicial del cabezal: 50 
Número total de operaciones de búsqueda = 156 
La secuencia de búsqueda es 
60 
79 
92 
114 
176 
11 
34 
41 
 

El siguiente gráfico muestra la secuencia en la que se atienden las pistas solicitadas utilizando C-LOOK. 

Por lo tanto, el recuento de búsqueda total = (60 – 50) + (79 – 60) + (92 – 79) + (114 – 92) + (176 – 114) + (176 – 11) + (34 – 11) + ( 41 – 34) = 321

Implementación: 
La implementación del algoritmo C-LOOK se proporciona a continuación. Tenga en cuenta que la variable de 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++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int size = 8;
int disk_size = 200;
 
// Function to perform C-LOOK on the request
// array starting from the given head
void CLOOK(int arr[], int head)
{
    int seek_count = 0;
    int distance, cur_track;
    vector<int> left, right;
    vector<int> seek_sequence;
 
    // 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 last track that
    // is needed to be serviced in
    // left direction
    seek_count += abs(head - left[0]);
    head = left[0];
 
    // 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;
 
    CLOOK(arr, head);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG{
  
static int size = 8;
static int disk_size = 200;
   
// Function to perform C-LOOK on the request
// array starting from the given head
public static void CLOOK(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>();
   
    // 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.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 last track that
    // is needed to be serviced in
    // left direction
    seek_count += Math.abs(head - left.get(0));
    head = left.get(0);
   
    // 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)
{
     
    // Request array
    int arr[] = { 176, 79, 34, 60,
                  92, 11, 41, 114 };
    int head = 50;
   
    System.out.println("Initial position of head: " +
                       head);
   
    CLOOK(arr, head);
}
}
 
// This code is contributed by divyesh072019

# Python3 implementation of the approach
size = 8
disk_size = 200
 
# Function to perform C-LOOK on the request
# array starting from the given head
def CLOOK(arr, head):
     
    seek_count = 0
    distance = 0
    cur_track = 0
 
    left = []
    right = []
 
    seek_sequence = []
 
    # Tracks on the left of the
    # head will be serviced when
    # once the head comes back
    # to the beginning (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
        # 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 last track that
    # is needed to be serviced in
    # left direction
    seek_count += abs(head - left[0])
    head = left[0]
 
    # 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")
 
    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
 
print("Initial position of head:", head)
 
CLOOK(arr, head)
 
# This code is contributed by rag2127

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
     
static int size = 8;
    
// Function to perform C-LOOK on the request
// array starting from the given head
static void CLOOK(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>();
    
    // 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.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 last track that
    // is needed to be serviced in
    // left direction
    seek_count += Math.Abs(head - left[0]);
    head = left[0];
    
    // 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);
    
    CLOOK(arr, head);
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
    // Javascript implementation of the approach
     
    let size = 8;
     
    // Function to perform C-LOOK on the request
    // array starting from the given head
    function CLOOK(arr, head)
    {
        let seek_count = 0;
        let distance, cur_track;
 
        let left = [];
        let right = [];
        let seek_sequence = [];
 
        // Tracks on the left of the
        // head will be serviced when
        // once the head comes back
        // to the beginning (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 last track that
        // is needed to be serviced in
        // left direction
        seek_count += Math.abs(head - left[0]);
        head = left[0];
 
        // 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>");
     
    CLOOK(arr, head);
     
</script>

Initial position of head: 50
Total number of seek operations = 321
Seek Sequence is
60
79
92
114
176
11
34
41