Requisito previo: algoritmos de programación de disco
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 tiempo de búsqueda más corto primero (SSTF) es un algoritmo de programación de disco .
Tiempo de búsqueda más corto primero (SSTF):
la idea básica es que las pistas que están más cerca de la posición actual del cabezal del disco deben recibir servicio primero para minimizar las operaciones de búsqueda .
Ventajas del tiempo de búsqueda más corto primero (SSTF) –
- Mejor rendimiento que el algoritmo de programación FCFS.
- Proporciona un mejor rendimiento.
- Este algoritmo se utiliza en el sistema de procesamiento por lotes donde el rendimiento es más importante.
- Tiene menos respuesta promedio y tiempo de espera.
Desventajas del tiempo de búsqueda más corto primero (SSTF) –
- El hambre es posible para algunas requests, ya que favorece las requests fáciles de alcanzar e ignora los procesos lejanos.
- Su falta de previsibilidad debido a la alta variación del tiempo de respuesta.
- Cambiar de dirección ralentiza las cosas.
Algoritmo –
- Let Request array representa una array que almacena índices de pistas que se han solicitado. ‘cabeza’ es la posición de la cabeza del disco.
- Encuentre la distancia positiva de todas las pistas en la array de solicitud desde la cabeza.
- Encuentre una pista de la array solicitada a la que aún no se haya accedido/mantenido y que tenga una distancia mínima 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:
secuencia de solicitud = {176, 79, 34, 60, 92, 11, 41, 114}
Posición inicial de la cabeza = 50
El siguiente gráfico muestra la secuencia en la que se atienden las pistas solicitadas mediante SSTF.
Por lo tanto, el conteo total de búsquedas se calcula como:
= (50-41)+(41-34)+(34-11)+(60-11)+(79-60)+(92-79)+(114-92)+(176-114) = 204
Que también se puede calcular directamente como: (50-11)+(176-11)
Implementación:
la implementación de SSTF se proporciona a continuación. Tenga en cuenta que hemos creado una clase de Node que tiene 2 miembros. ‘distancia’ se utiliza para almacenar la distancia entre la cabeza y la posición de la pista. ‘accedido’ es una variable booleana que indica si el cabezal del disco ha accedido/mantenido la pista antes o no.
C++
// C++ program for implementation of
// SSTF disk scheduling
#include <bits/stdc++.h>
using namespace std;
// Calculates difference of each
// track number with the head position
void calculatedifference(int request[], int head,
int diff[][2], int n)
{
for(int i = 0; i < n; i++)
{
diff[i][0] = abs(head - request[i]);
}
}
// Find unaccessed track which is
// at minimum distance from head
int findMIN(int diff[][2], int n)
{
int index = -1;
int minimum = 1e9;
for(int i = 0; i < n; i++)
{
if (!diff[i][1] && minimum > diff[i][0])
{
minimum = diff[i][0];
index = i;
}
}
return index;
}
void shortestSeekTimeFirst(int request[],
int head, int n)
{
if (n == 0)
{
return;
}
// Create array of objects of class node
int diff[n][2] = { { 0, 0 } };
// Count total number of seek operation
int seekcount = 0;
// Stores sequence in which disk access is done
int seeksequence[n + 1] = {0};
for(int i = 0; i < n; i++)
{
seeksequence[i] = head;
calculatedifference(request, head, diff, n);
int index = findMIN(diff, n);
diff[index][1] = 1;
// Increase the total count
seekcount += diff[index][0];
// Accessed track is now new head
head = request[index];
}
seeksequence[n] = head;
cout << "Total number of seek operations = "
<< seekcount << endl;
cout << "Seek sequence is : " << "\n";
// Print the sequence
for(int i = 0; i <= n; i++)
{
cout << seeksequence[i] << "\n";
}
}
// Driver code
int main()
{
int n = 8;
int proc[n] = { 176, 79, 34, 60, 92, 11, 41, 114 };
shortestSeekTimeFirst(proc, 50, n);
return 0;
}
// This code is contributed by manish19je0495
Java
// Java program for implementation of
// SSTF disk scheduling
class node {
// represent difference between
// head position and track number
int distance = 0;
// true if track has been accessed
boolean accessed = false;
}
public class SSTF {
// Calculates difference of each
// track number with the head position
public static void calculateDifference(int queue[],
int head, node diff[])
{
for (int i = 0; i < diff.length; i++)
diff[i].distance = Math.abs(queue[i] - head);
}
// find unaccessed track
// which is at minimum distance from head
public static int findMin(node diff[])
{
int index = -1, minimum = Integer.MAX_VALUE;
for (int i = 0; i < diff.length; i++) {
if (!diff[i].accessed && minimum > diff[i].distance) {
minimum = diff[i].distance;
index = i;
}
}
return index;
}
public static void shortestSeekTimeFirst(int request[],
int head)
{
if (request.length == 0)
return;
// create array of objects of class node
node diff[] = new node[request.length];
// initialize array
for (int i = 0; i < diff.length; i++)
diff[i] = new node();
// count total number of seek operation
int seek_count = 0;
// stores sequence in which disk access is done
int[] seek_sequence = new int[request.length + 1];
for (int i = 0; i < request.length; i++) {
seek_sequence[i] = head;
calculateDifference(request, head, diff);
int index = findMin(diff);
diff[index].accessed = true;
// increase the total count
seek_count += diff[index].distance;
// accessed track is now new head
head = request[index];
}
// for last accessed track
seek_sequence[seek_sequence.length - 1] = head;
System.out.println("Total number of seek operations = "
+ seek_count);
System.out.println("Seek Sequence is");
// print the sequence
for (int i = 0; i < seek_sequence.length; i++)
System.out.println(seek_sequence[i]);
}
public static void main(String[] args)
{
// request array
int arr[] = { 176, 79, 34, 60, 92, 11, 41, 114 };
shortestSeekTimeFirst(arr, 50);
}
}
Python3
# Python3 program for implementation of
# SSTF disk scheduling
# Calculates difference of each
# track number with the head position
def calculateDifference(queue, head, diff):
for i in range(len(diff)):
diff[i][0] = abs(queue[i] - head)
# find unaccessed track which is
# at minimum distance from head
def findMin(diff):
index = -1
minimum = 999999999
for i in range(len(diff)):
if (not diff[i][1] and
minimum > diff[i][0]):
minimum = diff[i][0]
index = i
return index
def shortestSeekTimeFirst(request, head):
if (len(request) == 0):
return
l = len(request)
diff = [0] * l
# initialize array
for i in range(l):
diff[i] = [0, 0]
# count total number of seek operation
seek_count = 0
# stores sequence in which disk
# access is done
seek_sequence = [0] * (l + 1)
for i in range(l):
seek_sequence[i] = head
calculateDifference(request, head, diff)
index = findMin(diff)
diff[index][1] = True
# increase the total count
seek_count += diff[index][0]
# accessed track is now new head
head = request[index]
# for last accessed track
seek_sequence[len(seek_sequence) - 1] = head
print("Total number of seek operations =",
seek_count)
print("Seek Sequence is")
# print the sequence
for i in range(l + 1):
print(seek_sequence[i])
# Driver code
if __name__ =="__main__":
# request array
proc = [176, 79, 34, 60,
92, 11, 41, 114]
shortestSeekTimeFirst(proc, 50)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program for implementation of
// SSTF disk scheduling
using System;
public class node
{
// represent difference between
// head position and track number
public int distance = 0;
// true if track has been accessed
public Boolean accessed = false;
}
public class SSTF
{
// Calculates difference of each
// track number with the head position
public static void calculateDifference(int []queue,
int head, node []diff)
{
for (int i = 0; i < diff.Length; i++)
diff[i].distance = Math.Abs(queue[i] - head);
}
// find unaccessed track
// which is at minimum distance from head
public static int findMin(node []diff)
{
int index = -1, minimum = int.MaxValue;
for (int i = 0; i < diff.Length; i++)
{
if (!diff[i].accessed && minimum > diff[i].distance)
{
minimum = diff[i].distance;
index = i;
}
}
return index;
}
public static void shortestSeekTimeFirst(int []request,
int head)
{
if (request.Length == 0)
return;
// create array of objects of class node
node []diff = new node[request.Length];
// initialize array
for (int i = 0; i < diff.Length; i++)
diff[i] = new node();
// count total number of seek operation
int seek_count = 0;
// stores sequence in which disk access is done
int[] seek_sequence = new int[request.Length + 1];
for (int i = 0; i < request.Length; i++)
{
seek_sequence[i] = head;
calculateDifference(request, head, diff);
int index = findMin(diff);
diff[index].accessed = true;
// increase the total count
seek_count += diff[index].distance;
// accessed track is now new head
head = request[index];
}
// for last accessed track
seek_sequence[seek_sequence.Length - 1] = head;
Console.WriteLine("Total number of seek operations = "
+ seek_count);
Console.WriteLine("Seek Sequence is");
// print the sequence
for (int i = 0; i < seek_sequence.Length; i++)
Console.WriteLine(seek_sequence[i]);
}
// Driver code
public static void Main(String[] args)
{
// request array
int []arr = { 176, 79, 34, 60, 92, 11, 41, 114 };
shortestSeekTimeFirst(arr, 50);
}
}
// This code contributed by Rajput-Ji
Producción:
Total number of seek operations = 204 Seek Sequence is 50 41 34 11 60 79 92 114 176
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwal rawat 1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA