Tiempo restante más corto primero (SJF preventivo) Algoritmo de programación – Part 1

En publicaciones anteriores, hemos discutido el Conjunto 1 de SJF, es decir, no preventivo. En esta publicación, analizaremos la versión preventiva de SJF conocida como Shortest Remaining Time First (SRTF).

En el algoritmo de programación Shortest Remaining Time First (SRTF) , se selecciona para ejecutar el proceso con la menor cantidad de tiempo restante hasta la finalización. Dado que el proceso que se está ejecutando actualmente es el que tiene la menor cantidad de tiempo restante por definición, y dado que ese tiempo solo debe reducirse a medida que avanza la ejecución, los procesos siempre se ejecutarán hasta que se completen o se agregue un nuevo proceso que requiera una menor cantidad de tiempo.

Ejemplos para mostrar el funcionamiento del algoritmo de programación de CPU Preemptive Shortest Job First:

Ejemplo-1: Considere la siguiente tabla de tiempo de llegada y tiempo de ráfaga para cinco procesos P1, P2, P3, P4 y P5 . 

El algoritmo de programación de CPU de trabajo más corto primero funcionará sobre la base de los pasos que se mencionan a continuación:

En el tiempo = 0,

• El proceso P4 llega y comienza a ejecutarse

A la hora= 1, 

• Llega el proceso P3. 
• Pero, como P4 tiene un tiempo de ráfaga más corto. Continuará la ejecución.
• Por lo tanto, P3 esperará hasta que se ejecute P4.

En el tiempo = 2, 

• El proceso P1 llega con tiempo de ráfaga = 6
• Como el tiempo de ráfaga de P1 es mayor que el de P4 
• Así, P4 continuará su ejecución.

En el tiempo = 3, 

• El proceso P4 terminará su ejecución. 
• Luego, se compara el tiempo de ráfaga de P3 y P1. 
• El proceso P1 se ejecuta porque su tiempo de ráfaga es menor en comparación con P3.

En el tiempo = 4, 

• Llega el proceso P5.
• Luego se compara el tiempo de ráfaga de P3, P5 y P1. 
• El proceso P5 se ejecuta primero entre ellos porque su tiempo de ráfaga es el más bajo y el proceso P1 se adelanta .

En el tiempo = 5, 

• Llega el proceso P2.
• Se compara el tiempo de ráfaga de todos los procesos, 
• El proceso P2 se ejecuta ya que su tiempo de ráfaga es el más bajo de todos. 
• El proceso P5 se adelanta.

En el tiempo = 6, 

• El proceso P2 seguirá ejecutándose.
• Se ejecutará hasta el tiempo = 8 ya que el tiempo de ráfaga de P2 es de 2 ms

A la hora=7, 

• El proceso P2 termina su ejecución.
• Luego se compara nuevamente el tiempo de ráfaga de todos los procesos restantes. 
• El Proceso P5 se ejecuta porque su tiempo de ráfaga es menor que los demás.

En el tiempo = 10, 

• El proceso P5 terminará su ejecución. 
• Luego se compara el tiempo de ráfaga de los procesos restantes P1 y P3. 
• Por lo tanto, el proceso P1 se ejecuta porque su tiempo de ráfaga es menor que P3

En el tiempo = 15,

• El proceso P1 termina su ejecución y P3 es el único proceso que queda. 
• P3 comenzará a ejecutarse.

En el tiempo = 23, 

• El proceso P3 terminará su ejecución.
• La ejecución global de los procesos será como se muestra a continuación:

Diagrama de Gantt para la ejecución anterior:

Diagrama de Gantt para SRTF

Ahora, calculemos el tiempo de espera promedio y el tiempo de respuesta :

Como la conocemos,

• Tiempo de vuelta = tiempo de finalización – tiempo de llegada
• Tiempo de espera = tiempo de respuesta – tiempo de ráfaga

Ahora, 

• Tiempo medio de respuesta = (13 + 2 + 22 + 3 + 6)/5 = 9,2
• Tiempo medio de espera = (7 + 0 + 14 + 0 + 2)/5 = 23/5 = 4,6

Implementación del Algoritmo SRTF: 

Acercarse:

• Atraviese hasta que todo el proceso se ejecute por completo.
  • Encuentre el proceso con el tiempo restante mínimo en cada vuelta de tiempo.
  • Reduce su tiempo en 1.
  • Compruebe si su tiempo restante se convierte en 0 
  • Incrementa el contador de finalización del proceso.
  • Tiempo de finalización del proceso actual = tiempo_actual + 1;
  • Calcule el tiempo de espera para cada proceso completado.
    •  wt[i]= tiempo de finalización – tiempo_de_llegada-tiempo_de_ráfaga
  • Incrementa el tiempo de vuelta en uno.
• Encuentre el tiempo de respuesta (waiting_time + burst_time).

 Programa para implementar el tiempo restante más corto primero:

// C++ program to implement Shortest Remaining Time First
// Shortest Remaining Time First (SRTF)
  
#include <bits/stdc++.h>
using namespace std;
  
struct Process {
    int pid; // Process ID
    int bt; // Burst Time
    int art; // Arrival Time
};
  
// Function to find the waiting time for all
// processes
void findWaitingTime(Process proc[], int n,
                                int wt[])
{
    int rt[n];
  
    // Copy the burst time into rt[]
    for (int i = 0; i < n; i++)
        rt[i] = proc[i].bt;
  
    int complete = 0, t = 0, minm = INT_MAX;
    int shortest = 0, finish_time;
    bool check = false;
  
    // Process until all processes gets
    // completed
    while (complete != n) {
  
        // Find process with minimum
        // remaining time among the
        // processes that arrives till the
        // current time`
        for (int j = 0; j < n; j++) {
            if ((proc[j].art <= t) &&
            (rt[j] < minm) && rt[j] > 0) {
                minm = rt[j];
                shortest = j;
                check = true;
            }
        }
  
        if (check == false) {
            t++;
            continue;
        }
  
        // Reduce remaining time by one
        rt[shortest]--;
  
        // Update minimum
        minm = rt[shortest];
        if (minm == 0)
            minm = INT_MAX;
  
        // If a process gets completely
        // executed
        if (rt[shortest] == 0) {
  
            // Increment complete
            complete++;
            check = false;
  
            // Find finish time of current
            // process
            finish_time = t + 1;
  
            // Calculate waiting time
            wt[shortest] = finish_time -
                        proc[shortest].bt -
                        proc[shortest].art;
  
            if (wt[shortest] < 0)
                wt[shortest] = 0;
        }
        // Increment time
        t++;
    }
}
  
// Function to calculate turn around time
void findTurnAroundTime(Process proc[], int n,
                        int wt[], int tat[])
{
    // calculating turnaround time by adding
    // bt[i] + wt[i]
    for (int i = 0; i < n; i++)
        tat[i] = proc[i].bt + wt[i];
}
  
// Function to calculate average time
void findavgTime(Process proc[], int n)
{
    int wt[n], tat[n], total_wt = 0,
                    total_tat = 0;
  
    // Function to find waiting time of all
    // processes
    findWaitingTime(proc, n, wt);
  
    // Function to find turn around time for
    // all processes
    findTurnAroundTime(proc, n, wt, tat);
  
    // Display processes along with all
    // details
    cout << " P\t\t"
        << "BT\t\t"
        << "WT\t\t"
        << "TAT\t\t\n";
  
    // Calculate total waiting time and
    // total turnaround time
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << proc[i].pid << "\t\t"
            << proc[i].bt << "\t\t " << wt[i]
            << "\t\t " << tat[i] << endl;
    }
  
    cout << "\nAverage waiting time = "
        << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "
        << (float)total_tat / (float)n;
}
  
// Driver code
int main()
{
    Process proc[] = { { 1, 6, 2 }, { 2, 2, 5 },
                    { 3, 8, 1 }, { 4, 3, 0}, {5, 4, 4} };
    int n = sizeof(proc) / sizeof(proc[0]);
  
    findavgTime(proc, n);
    return 0;
}

// Java program to implement Shortest Remaining Time First
// Shortest Remaining Time First (SRTF)
  
class Process
{
    int pid; // Process ID
    int bt; // Burst Time
    int art; // Arrival Time
      
    public Process(int pid, int bt, int art)
    {
        this.pid = pid;
        this.bt = bt;
        this.art = art;
    }
}
  
public class GFG 
{
    // Method to find the waiting time for all
    // processes
    static void findWaitingTime(Process proc[], int n,
                                     int wt[])
    {
        int rt[] = new int[n];
       
        // Copy the burst time into rt[]
        for (int i = 0; i < n; i++)
            rt[i] = proc[i].bt;
       
        int complete = 0, t = 0, minm = Integer.MAX_VALUE;
        int shortest = 0, finish_time;
        boolean check = false;
       
        // Process until all processes gets
        // completed
        while (complete != n) {
       
            // Find process with minimum
            // remaining time among the
            // processes that arrives till the
            // current time`
            for (int j = 0; j < n; j++) 
            {
                if ((proc[j].art <= t) &&
                  (rt[j] < minm) && rt[j] > 0) {
                    minm = rt[j];
                    shortest = j;
                    check = true;
                }
            }
       
            if (check == false) {
                t++;
                continue;
            }
       
            // Reduce remaining time by one
            rt[shortest]--;
       
            // Update minimum
            minm = rt[shortest];
            if (minm == 0)
                minm = Integer.MAX_VALUE;
       
            // If a process gets completely
            // executed
            if (rt[shortest] == 0) {
       
                // Increment complete
                complete++;
                check = false;
       
                // Find finish time of current
                // process
                finish_time = t + 1;
       
                // Calculate waiting time
                wt[shortest] = finish_time -
                             proc[shortest].bt -
                             proc[shortest].art;
       
                if (wt[shortest] < 0)
                    wt[shortest] = 0;
            }
            // Increment time
            t++;
        }
    }
       
    // Method to calculate turn around time
    static void findTurnAroundTime(Process proc[], int n,
                            int wt[], int tat[])
    {
        // calculating turnaround time by adding
        // bt[i] + wt[i]
        for (int i = 0; i < n; i++)
            tat[i] = proc[i].bt + wt[i];
    }
       
    // Method to calculate average time
    static void findavgTime(Process proc[], int n)
    {
        int wt[] = new int[n], tat[] = new int[n];
        int  total_wt = 0, total_tat = 0;
       
        // Function to find waiting time of all
        // processes
        findWaitingTime(proc, n, wt);
       
        // Function to find turn around time for
        // all processes
        findTurnAroundTime(proc, n, wt, tat);
       
        // Display processes along with all
        // details
        System.out.println("Processes " +
                           " Burst time " +
                           " Waiting time " +
                           " Turn around time");
       
        // Calculate total waiting time and
        // total turnaround time
        for (int i = 0; i < n; i++) {
            total_wt = total_wt + wt[i];
            total_tat = total_tat + tat[i];
            System.out.println(" " + proc[i].pid + "\t\t"
                             + proc[i].bt + "\t\t " + wt[i]
                             + "\t\t" + tat[i]);
        }
       
        System.out.println("Average waiting time = " +
                          (float)total_wt / (float)n);
        System.out.println("Average turn around time = " +
                           (float)total_tat / (float)n);
    }
      
    // Driver Method
    public static void main(String[] args)
    {
         Process proc[] = { new Process(1, 6, 1), 
                            new Process(2, 8, 1),
                            new Process(3, 7, 2), 
                            new Process(4, 3, 3)};
          
         findavgTime(proc, proc.length);
    }
}

# Python3 program to implement Shortest Remaining Time First
# Shortest Remaining Time First (SRTF)
  
# Function to find the waiting time 
# for all processes 
def findWaitingTime(processes, n, wt): 
    rt = [0] * n
  
    # Copy the burst time into rt[] 
    for i in range(n): 
        rt[i] = processes[i][1]
    complete = 0
    t = 0
    minm = 999999999
    short = 0
    check = False
  
    # Process until all processes gets 
    # completed 
    while (complete != n):
          
        # Find process with minimum remaining 
        # time among the processes that 
        # arrives till the current time`
        for j in range(n):
            if ((processes[j][2] <= t) and 
                (rt[j] < minm) and rt[j] > 0):
                minm = rt[j]
                short = j
                check = True
        if (check == False):
            t += 1
            continue
              
        # Reduce remaining time by one 
        rt[short] -= 1
  
        # Update minimum 
        minm = rt[short] 
        if (minm == 0): 
            minm = 999999999
  
        # If a process gets completely 
        # executed 
        if (rt[short] == 0): 
  
            # Increment complete 
            complete += 1
            check = False
  
            # Find finish time of current 
            # process 
            fint = t + 1
  
            # Calculate waiting time 
            wt[short] = (fint - proc[short][1] -    
                                proc[short][2])
  
            if (wt[short] < 0):
                wt[short] = 0
          
        # Increment time 
        t += 1
  
# Function to calculate turn around time 
def findTurnAroundTime(processes, n, wt, tat): 
      
    # Calculating turnaround time 
    for i in range(n):
        tat[i] = processes[i][1] + wt[i] 
  
# Function to calculate average waiting 
# and turn-around times. 
def findavgTime(processes, n): 
    wt = [0] * n
    tat = [0] * n 
  
    # Function to find waiting time 
    # of all processes 
    findWaitingTime(processes, n, wt) 
  
    # Function to find turn around time
    # for all processes 
    findTurnAroundTime(processes, n, wt, tat) 
  
    # Display processes along with all details 
    print("Processes    Burst Time     Waiting", 
                    "Time     Turn-Around Time")
    total_wt = 0
    total_tat = 0
    for i in range(n):
  
        total_wt = total_wt + wt[i] 
        total_tat = total_tat + tat[i] 
        print(" ", processes[i][0], "\t\t", 
                   processes[i][1], "\t\t", 
                   wt[i], "\t\t", tat[i])
  
    print("\nAverage waiting time = %.5f "%(total_wt /n) )
    print("Average turn around time = ", total_tat / n) 
      
# Driver code 
if __name__ =="__main__":
      
    # Process id's 
    proc = [[1, 6, 1], [2, 8, 1],
            [3, 7, 2], [4, 3, 3]]
    n = 4
    findavgTime(proc, n)
      
# This code is contributed
# Shubham Singh(SHUBHAMSINGH10)

// C# program to implement Shortest Remaining Time First
// Shortest Remaining Time First (SRTF)
  
using System;
  
public class Process
{
    public int pid; // Process ID
    public int bt; // Burst Time
    public int art; // Arrival Time
      
    public Process(int pid, int bt, int art)
    {
        this.pid = pid;
        this.bt = bt;
        this.art = art;
    }
}
  
public class GFG 
{
    // Method to find the waiting 
    // time for all processes
    static void findWaitingTime(Process []proc, int n,
                                    int []wt)
    {
        int []rt = new int[n];
      
        // Copy the burst time into rt[]
        for (int i = 0; i < n; i++)
            rt[i] = proc[i].bt;
      
        int complete = 0, t = 0, minm = int.MaxValue;
        int shortest = 0, finish_time;
        bool check = false;
      
        // Process until all processes gets
        // completed
        while (complete != n) 
        {
      
            // Find process with minimum
            // remaining time among the
            // processes that arrives till the
            // current time`
            for (int j = 0; j < n; j++) 
            {
                if ((proc[j].art <= t) &&
                (rt[j] < minm) && rt[j] > 0) 
                {
                    minm = rt[j];
                    shortest = j;
                    check = true;
                }
            }
      
            if (check == false) 
            {
                t++;
                continue;
            }
      
            // Reduce remaining time by one
            rt[shortest]--;
      
            // Update minimum
            minm = rt[shortest];
            if (minm == 0)
                minm = int.MaxValue;
      
            // If a process gets completely
            // executed
            if (rt[shortest] == 0) 
            {
      
                // Increment complete
                complete++;
                check = false;
      
                // Find finish time of current
                // process
                finish_time = t + 1;
      
                // Calculate waiting time
                wt[shortest] = finish_time -
                            proc[shortest].bt -
                            proc[shortest].art;
      
                if (wt[shortest] < 0)
                    wt[shortest] = 0;
            }
            // Increment time
            t++;
        }
    }
      
    // Method to calculate turn around time
    static void findTurnAroundTime(Process []proc, int n,
                            int []wt, int []tat)
    {
        // calculating turnaround time by adding
        // bt[i] + wt[i]
        for (int i = 0; i < n; i++)
            tat[i] = proc[i].bt + wt[i];
    }
      
    // Method to calculate average time
    static void findavgTime(Process []proc, int n)
    {
        int []wt = new int[n];int []tat = new int[n];
        int total_wt = 0, total_tat = 0;
      
        // Function to find waiting time of all
        // processes
        findWaitingTime(proc, n, wt);
      
        // Function to find turn around time for
        // all processes
        findTurnAroundTime(proc, n, wt, tat);
      
        // Display processes along with all
        // details
        Console.WriteLine("Processes " +
                        " Burst time " +
                        " Waiting time " +
                        " Turn around time");
      
        // Calculate total waiting time and
        // total turnaround time
        for (int i = 0; i < n; i++) 
        {
            total_wt = total_wt + wt[i];
            total_tat = total_tat + tat[i];
            Console.WriteLine(" " + proc[i].pid + "\t\t"
                            + proc[i].bt + "\t\t " + wt[i]
                            + "\t\t" + tat[i]);
        }
      
        Console.WriteLine("Average waiting time = " +
                        (float)total_wt / (float)n);
        Console.WriteLine("Average turn around time = " +
                        (float)total_tat / (float)n);
    }
      
    // Driver Method
    public static void Main(String[] args)
    {
        Process []proc = { new Process(1, 6, 1), 
                            new Process(2, 8, 1),
                            new Process(3, 7, 2), 
                            new Process(4, 3, 3)};
          
        findavgTime(proc, proc.Length);
    }
}
  
// This code has been contributed by 29AjayKumar

<script>
// Javascript program to implement 
// Shortest Remaining Time First
// Shortest Remaining Time First (SRTF)
  
class Process
{
    constructor(pid,bt,art)
    {
        this.pid = pid;    // Process ID
        this.bt = bt;    // Burst Time
        this.art = art;    // Arrival Time
    }
}
  
// Method to find the waiting time for all
    // processes
function findWaitingTime( proc,n,wt)
{
    let rt = new Array(n);
         
        // Copy the burst time into rt[]
        for (let i = 0; i < n; i++)
            rt[i] = proc[i].bt;
         
        let complete = 0, t = 0, minm = Number.MAX_VALUE;
        let shortest = 0, finish_time;
        let check = false;
         
        // Process until all processes gets
        // completed
        while (complete != n) {
         
            // Find process with minimum
            // remaining time among the
            // processes that arrives till the
            // current time`
            for (let j = 0; j < n; j++) 
            {
                if ((proc[j].art <= t) &&
                  (rt[j] < minm) && rt[j] > 0) {
                    minm = rt[j];
                    shortest = j;
                    check = true;
                }
            }
         
            if (check == false) {
                t++;
                continue;
            }
         
            // Reduce remaining time by one
            rt[shortest]--;
         
            // Update minimum
            minm = rt[shortest];
            if (minm == 0)
                minm = Number.MAX_VALUE;
         
            // If a process gets completely
            // executed
            if (rt[shortest] == 0) {
         
                // Increment complete
                complete++;
                check = false;
         
                // Find finish time of current
                // process
                finish_time = t + 1;
         
                // Calculate waiting time
                wt[shortest] = finish_time -
                             proc[shortest].bt -
                             proc[shortest].art;
         
                if (wt[shortest] < 0)
                    wt[shortest] = 0;
            }
            // Increment time
            t++;
        }
}
  
// Method to calculate turn around time
function findTurnAroundTime(proc,n,wt,tat)
{
     // calculating turnaround time by adding
        // bt[i] + wt[i]
        for (let i = 0; i < n; i++)
            tat[i] = proc[i].bt + wt[i];
}
  
// Method to calculate average time
function findavgTime(proc,n)
{
    let wt = new Array(n), tat = new Array(n);
        let  total_wt = 0, total_tat = 0;
         
        // Function to find waiting time of all
        // processes
        findWaitingTime(proc, n, wt);
         
        // Function to find turn around time for
        // all processes
        findTurnAroundTime(proc, n, wt, tat);
         
        // Display processes along with all
        // details
        document.write("Processes " +
                           " Burst time " +
                           " Waiting time " +
                           " Turn around time<br>");
         
        // Calculate total waiting time and
        // total turnaround time
        for (let i = 0; i < n; i++) {
            total_wt = total_wt + wt[i];
            total_tat = total_tat + tat[i];
            document.write(" " + proc[i].pid + 
            "      "
            + proc[i].bt + "    " + wt[i]
            + "    " + tat[i]+"<br>");
        }
         
        document.write("Average waiting time = " +
                          total_wt / n+"<br>");
        document.write("Average turn around time = " +
                           total_tat / n+"<br>");
}
  
// Driver Method
let proc=[new Process(1, 6, 1), 
                            new Process(2, 8, 1),
                            new Process(3, 7, 2), 
                            new Process(4, 3, 3)];
findavgTime(proc, proc.length);
  
  
// This code is contributed by rag2127
  
</script>

 P        BT        WT        TAT        
 1        6         7         13
 2        2         0         2
 3        8         14         22
 4        3         0         3
 5        4         2         6

Average waiting time = 4.6
Average turn around time = 9.2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

ventajas: 

• Los procesos cortos se manejan muy rápidamente. 
• El sistema también requiere muy poca sobrecarga ya que solo toma una decisión cuando se completa un proceso o se agrega un nuevo proceso. 
• Cuando se agrega un nuevo proceso, el algoritmo solo necesita comparar el proceso que se está ejecutando actualmente con el nuevo proceso, ignorando todos los demás procesos que están esperando para ejecutarse.

Desventajas: 

• Al igual que el trabajo más corto primero, tiene el potencial de inanición del proceso. 
• Los procesos largos pueden retrasarse indefinidamente si se agregan continuamente procesos cortos. 

Fuente: Wiki
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.