Primero en llegar, primero en servir: programación de CPU | (No preventivo)

Programación FCFS:

El algoritmo de programación de CPU más simple que programa de acuerdo con los tiempos de llegada de los procesos. El algoritmo de programación por orden de llegada establece que el proceso que solicita la CPU primero recibe la CPU primero. Se implementa utilizando la cola FIFO . Cuando un proceso ingresa a la cola de procesos listos, su PCB se vincula al final de la cola. Cuando la CPU está libre, se asigna al proceso que está al principio de la cola. A continuación, el proceso en ejecución se elimina de la cola. FCFS es un algoritmo de programación no preventivo.

Características de FCFS:

• FCFS es compatible con el algoritmo de programación de CPU preventivo y no preventivo.
• Las tareas siempre se ejecutan según el concepto de orden de llegada.
• FCFS es fácil de implementar y usar.
• Este algoritmo no es muy eficiente en rendimiento y el tiempo de espera es bastante alto.

¿Cómo funciona el algoritmo de programación de CPU por orden de llegada?

• El tiempo de espera para el primer proceso es 0 ya que se ejecuta primero.
• El tiempo de espera para el próximo proceso se puede calcular mediante: 
   

peso[i] = ( en[i – 1] + bt[i – 1] + peso[i – 1] ) – en[i]

dónde 

• wt[i] = tiempo de espera del proceso actual 
• at[i-1] = hora de llegada del proceso anterior 
• bt[i-1] = tiempo de ráfaga del proceso anterior 
• wt[i-1] = tiempo de espera del proceso anterior 
• at[i] = hora de llegada del proceso actual 

• El tiempo medio de espera se puede calcular mediante: 
   

Tiempo promedio de espera = (suma de todos los tiempos de espera)/(Número de procesos)

Ejemplos para mostrar el funcionamiento del algoritmo de programación de CPU por orden de llegada no preventivo:

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 por orden de llegada funcionará según los pasos que se mencionan a continuación:

Paso 0: En el tiempo = 0,

• El proceso comienza con P1 
• Como tiene hora de llegada 0

Paso 1: En el tiempo = 1,

• Llega el proceso P2
• Pero el proceso P1 sigue ejecutándose, 
• Así, P2 se mantuvo en una mesa de espera y aguardó su ejecución.

Paso 3: En el tiempo = 2,

• El proceso P3 llega y se mantiene en cola de espera 
• Mientras que el proceso P1 aún se está ejecutando, su tiempo de ráfaga es 4.

Paso 4: En el tiempo = 3,

• El proceso P4 llega y se mantiene en cola de espera 
• Mientras el proceso P1 aún se está ejecutando, su tiempo de ráfaga es 4

Paso 5: En el tiempo = 4,

• El proceso P1 completa su ejecución  .
• El proceso P5 llega a la cola de espera mientras el proceso P2 comienza a ejecutarse

Paso 6: En el tiempo = 5,

• El proceso P2 completa su ejecución 

Paso 7: En el tiempo = 7,

• El proceso P3 comienza a ejecutarse, tiene un tiempo de ráfaga de 1, por lo tanto, completa la ejecución en el intervalo de tiempo 8

Paso 8: En el tiempo 8,

• El proceso de P3 culmina su ejecución 
• El proceso P4 comienza a ejecutarse, tiene un tiempo de ráfaga de 2, por lo tanto, completa la ejecución en el intervalo de tiempo 10.

Paso 9: En el tiempo 10,

• El proceso P4 completa su ejecución 
• El proceso P5 comienza a ejecutarse, tiene un tiempo de ráfaga de 5, por lo tanto, completa la ejecución en el intervalo de tiempo 15.

Paso 10: En el tiempo 15,

• El proceso P5 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 la programación por orden de llegada

Tiempo de espera = Hora de inicio – Hora de llegada

P1 = 0 – 0 = 0
P2 = 4 – 1 = 3
P3 = 7 – 2 = 5
P4 = 8 – 3 = 5
P5 = 10 – 4 = 6

Tiempo medio de espera = 0 + 3 + 5 + 5+ 6/5 = 19/5 = 3,8 

Programa para el algoritmo First Come First Serve:

// C++ program to Calculate Waiting
// Time for given Processes
#include <iostream>
using namespace std;
 
// Function to Calculate waiting time
// and average waiting time
void CalculateWaitingTime(int at[],
                          int bt[], int N)
{
 
    // Declare the array for waiting
    // time
    int wt[N];
 
    // Waiting time for first process
    // is 0
    wt[0] = 0;
 
    // Print waiting time process 1
    cout << "PN\t\tAT\t\t"
         << "BT\t\tWT\n\n";
    cout << "1"
         << "\t\t" << at[0] << "\t\t"
         << bt[0] << "\t\t" << wt[0] << endl;
 
    // Calculating waiting time for
    // each process from the given
    // formula
    for (int i = 1; i < 5; i++) {
        wt[i] = (at[i - 1] + bt[i - 1]
                 + wt[i - 1]) - at[i];
 
        // Print the waiting time for
        // each process
        cout << i + 1 << "\t\t" << at[i]
             << "\t\t" << bt[i] << "\t\t"
             << wt[i] << endl;
    }
 
    // Declare variable to calculate
    // average
    float average;
    float sum = 0;
 
    // Loop to calculate sum of all
    // waiting time
    for (int i = 0; i < 5; i++) {
        sum = sum + wt[i];
    }
 
    // Find average waiting time
    // by dividing it by no. of process
    average = sum / 5;
 
    // Print Average Waiting Time
    cout << "\nAverage waiting time = "
         << average;
}
 
// Driver code
int main()
{
    // Number of process
    int N = 5;
 
    // Array for Arrival time
    int at[] = { 0, 1, 2, 3, 4 };
 
    // Array for Burst Time
    int bt[] = { 4, 3, 1, 2, 5 };
 
    // Function call to find
    // waiting time
    CalculateWaitingTime(at, bt, N);
    return 0;
}

// Java program to Calculate Waiting
// Time for given Processes
class GFG
{
  
// Function to Calculate waiting time
// and average waiting time
static void CalculateWaitingTime(int at[],
                          int bt[], int N)
{
  
    // Declare the array for waiting
    // time
    int []wt = new int[N];
  
    // Waiting time for first process
    // is 0
    wt[0] = 0;
  
    // Print waiting time process 1
    System.out.print("P.No.\tArrival Time\t"
        + "Burst Time\tWaiting Time\n");
    System.out.print("1"
        + "\t\t" +  at[0]+ "\t\t"
         + bt[0]+ "\t\t" +  wt[0] +"\n");
  
    // Calculating waiting time for
    // each process from the given
    // formula
    for (int i = 1; i < 5; i++) {
        wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];
  
        // Print the waiting time for
        // each process
        System.out.print(i + 1+ "\t\t" +  at[i]
            + "\t\t" +  bt[i]+ "\t\t"
             + wt[i] +"\n");
    }
  
    // Declare variable to calculate
    // average
    float average;
    float sum = 0;
  
    // Loop to calculate sum of all
    // waiting time
    for (int i = 0; i < 5; i++) {
        sum = sum + wt[i];
    }
  
    // Find average waiting time
    // by dividing it by no. of process
    average = sum / 5;
  
    // Print Average Waiting Time
    System.out.print("Average waiting time = "
         + average);
}
  
// Driver code
public static void main(String[] args)
{
    // Number of process
    int N = 5;
  
    // Array for Arrival time
    int at[] = { 0, 1, 2, 3, 4 };
  
    // Array for Burst Time
    int bt[] = { 4, 3, 1, 2, 5 };
  
    // Function call to find
    // waiting time
    CalculateWaitingTime(at, bt, N);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to Calculate Waiting
# Time for given Processes
 
# Function to Calculate waiting time
# and average waiting time
def CalculateWaitingTime(at, bt, N):
 
    # Declare the array for waiting
    # time
    wt = [0]*N;
 
    # Waiting time for first process
    # is 0
    wt[0] = 0;
 
    # Print waiting time process 1
    print("P.No.\tArrival Time\t" , "Burst Time\tWaiting Time");
    print("1" , "\t\t" , at[0] , "\t\t" , bt[0] , "\t\t" , wt[0]);
 
    # Calculating waiting time for
    # each process from the given
    # formula
    for i in range(1,5):
        wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];
 
        # Print the waiting time for
        # each process
        print(i + 1 , "\t\t" , at[i] , "\t\t" , bt[i] , "\t\t" , wt[i]);
     
 
    # Declare variable to calculate
    # average
    average = 0.0;
    sum = 0;
 
    # Loop to calculate sum of all
    # waiting time
    for i in range(5):
        sum = sum + wt[i];
     
    # Find average waiting time
    # by dividing it by no. of process
    average = sum / 5;
 
    # Print Average Waiting Time
    print("Average waiting time = " , average);
 
 
# Driver code
if __name__ == '__main__':
    # Number of process
    N = 5;
 
    # Array for Arrival time
    at = [ 0, 1, 2, 3, 4 ];
 
    # Array for Burst Time
    bt = [ 4, 3, 1, 2, 5 ];
 
    # Function call to find
    # waiting time
    CalculateWaitingTime(at, bt, N);
 
# This code is contributed by 29AjayKumar

// C# program to Calculate Waiting
// Time for given Processes
using System;
 
class GFG
{
   
// Function to Calculate waiting time
// and average waiting time
static void CalculateWaitingTime(int []at,
                          int []bt, int N)
{
   
    // Declare the array for waiting
    // time
    int []wt = new int[N];
   
    // Waiting time for first process
    // is 0
    wt[0] = 0;
   
    // Print waiting time process 1
    Console.Write("P.No.\tArrival Time\t"
        + "Burst Time\tWaiting Time\n");
    Console.Write("1"
        + "\t\t" +  at[0]+ "\t\t"
         + bt[0]+ "\t\t" +  wt[0] +"\n");
   
    // Calculating waiting time for
    // each process from the given
    // formula
    for (int i = 1; i < 5; i++) {
        wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];
   
        // Print the waiting time for
        // each process
        Console.Write(i + 1+ "\t\t" +  at[i]
            + "\t\t" +  bt[i]+ "\t\t"
             + wt[i] +"\n");
    }
   
    // Declare variable to calculate
    // average
    float average;
    float sum = 0;
   
    // Loop to calculate sum of all
    // waiting time
    for (int i = 0; i < 5; i++) {
        sum = sum + wt[i];
    }
   
    // Find average waiting time
    // by dividing it by no. of process
    average = sum / 5;
   
    // Print Average Waiting Time
    Console.Write("Average waiting time = "
         + average);
}
   
// Driver code
public static void Main(String[] args)
{
    // Number of process
    int N = 5;
   
    // Array for Arrival time
    int []at = { 0, 1, 2, 3, 4 };
   
    // Array for Burst Time
    int []bt = { 4, 3, 1, 2, 5 };
   
    // Function call to find
    // waiting time
    CalculateWaitingTime(at, bt, N);
}
}
 
// This code is contributed by 29AjayKumar

PN        AT        BT        WT

1        0        4        0
2        1        3        3
3        2        1        5
4        3        2        5
5        4        5        6

Average waiting time = 3.8

Análisis de Complejidad:

• Complejidad de tiempo: O(N)
• Espacio Auxiliar: O(N)

Ventajas de FCFS:

• La forma más simple y básica del algoritmo de programación de CPU
• Fácil de implementar
• Método por orden de llegada

Desventajas de FCFS:

• Como es un algoritmo de programación de CPU no preventivo, se ejecutará hasta que finalice la ejecución.
• El tiempo medio de espera en el FCFS es muy superior al de los demás
• Poco eficiente debido a su sencillez.
• Los procesos que están al final de la cola, tienen que esperar más tiempo para terminar.