Requisito previo: algoritmos de programación de discos.
Dada una array de números de pista de disco y la posición inicial del encabezado, 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 First Come First Serve (FCFS) .
First Come First Serve (FCFS) FCFS es el algoritmo de programación de disco
más simple . Como sugiere el nombre, este algoritmo recibe las requests en el orden en que llegan a la cola del disco. El algoritmo parece muy justo y no hay inanición (todas las requests se atienden secuencialmente) pero, en general, no proporciona el servicio más rápido.
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.
- Tomemos las pistas una por una en el orden predeterminado y calculemos 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 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
Output:
Total number of seek operations = 510
Seek Sequence is
176
79
34
60
92
11
41
114
El siguiente gráfico muestra la secuencia en la que se atienden las pistas solicitadas mediante FCFS.
Por lo tanto, el conteo total de búsquedas se calcula como:
= (176-50)+(176-79)+(79-34)+(60-34)+(92-60)+(92-11)+(41-11)+(114-41) = 510
Implementación:
La implementación de FCFS 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.
C++
// C++ program to demonstrate
// FCFS Disk Scheduling algorithm
#include <bits/stdc++.h>
using namespace std;
int size = 8;
void FCFS(int arr[], int head)
{
int seek_count = 0;
int distance, cur_track;
for (int i = 0; i < size; i++) {
cur_track = arr[i];
// calculate absolute distance
distance = abs(cur_track - head);
// increase the total count
seek_count += distance;
// accessed track is now new head
head = cur_track;
}
cout << "Total number of seek operations = "
<< seek_count << endl;
// Seek sequence would be the same
// as request array sequence
cout << "Seek Sequence is" << endl;
for (int i = 0; i < size; i++) {
cout << arr[i] << endl;
}
}
// Driver code
int main()
{
// request array
int arr[size] = { 176, 79, 34, 60, 92, 11, 41, 114 };
int head = 50;
FCFS(arr, head);
return 0;
}
Java
// Java program to demonstrate
// FCFS Disk Scheduling algorithm
class GFG
{
static int size = 8;
static void FCFS(int arr[], int head)
{
int seek_count = 0;
int distance, cur_track;
for (int i = 0; i < size; i++)
{
cur_track = arr[i];
// 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;
}
System.out.println("Total number of " +
"seek operations = " +
seek_count);
// Seek sequence would be the same
// as request array sequence
System.out.println("Seek Sequence is");
for (int i = 0; i < size; i++)
{
System.out.println(arr[i]);
}
}
// Driver code
public static void main(String[] args)
{
// request array
int arr[] = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
FCFS(arr, head);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to demonstrate
# FCFS Disk Scheduling algorithm
size = 8;
def FCFS(arr, head):
seek_count = 0;
distance, cur_track = 0, 0;
for i in range(size):
cur_track = arr[i];
# calculate absolute distance
distance = abs(cur_track - head);
# increase the total count
seek_count += distance;
# accessed track is now new head
head = cur_track;
print("Total number of seek operations = ",
seek_count);
# Seek sequence would be the same
# as request array sequence
print("Seek Sequence is");
for i in range(size):
print(arr[i]);
# Driver code
if __name__ == '__main__':
# request array
arr = [ 176, 79, 34, 60,
92, 11, 41, 114 ];
head = 50;
FCFS(arr, head);
# This code contributed by Rajput-Ji
C#
// C# program to demonstrate
// FCFS Disk Scheduling algorithm
using System;
class GFG
{
static int size = 8;
static void FCFS(int []arr, int head)
{
int seek_count = 0;
int distance, cur_track;
for (int i = 0; i < size; i++)
{
cur_track = arr[i];
// 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;
}
Console.WriteLine("Total number of " +
"seek operations = " +
seek_count);
// Seek sequence would be the same
// as request array sequence
Console.WriteLine("Seek Sequence is");
for (int i = 0; i < size; i++)
{
Console.WriteLine(arr[i]);
}
}
// Driver code
public static void Main(String[] args)
{
// request array
int []arr = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
FCFS(arr, head);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to demonstrate
// FCFS Disk Scheduling algorithm
var size = 8;
function FCFS(arr, head)
{
var seek_count = 0;
var distance, cur_track;
for(var i = 0; i < size; i++)
{
cur_track = arr[i];
// 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;
}
document.write("Total number of " +
"seek operations = " +
seek_count);
// Seek sequence would be the same
// as request array sequence
document.write("<br>Seek Sequence is");
for(var i = 0; i < size; i++)
{
document.write("<br>" + arr[i]);
}
}
// Driver code
// request array
var arr = [ 176, 79, 34, 60,
92, 11, 41, 114 ];
var head = 50;
FCFS(arr, head);
// This code is contributed by Amit Katiyar
</script>
Producción:
Total number of seek operations = 510 Seek Sequence is 176 79 34 60 92 11 41 114