Encuentre el orden de ejecución de N procesos dados en la programación Round Robin

En este artículo, aprenderá cómo encontrar el orden de ejecución para los N procesos dados en el algoritmo de programación Round Robin. Pero antes de comenzar con el código, comprendamos un poco cómo funciona este algoritmo.

Round Robin Scheduling es un algoritmo de programación de CPU popular que se utiliza en sistemas operativos para asignar tiempo de CPU a múltiples procesos de manera justa y eficiente. En este blog, exploraremos cómo funciona la programación por turnos, sus ventajas y desventajas, y brindaremos un ejemplo para ayudarlo a comprender mejor el concepto.

¿Qué es la programación Round Robin?

La programación Round Robin es un algoritmo de programación preventiva en el que a cada proceso se le asigna un intervalo de tiempo fijo o un cuanto para ejecutar. El programador de la CPU asigna el tiempo de la CPU a los procesos en un orden circular, de ahí el nombre "round robin". Una vez que un proceso ha agotado su intervalo de tiempo, se adelanta y se agrega al final de la cola lista. Al siguiente proceso en la cola se le asigna la CPU para su intervalo de tiempo.

El intervalo de tiempo o cuanto de cada proceso es generalmente pequeño, normalmente entre 10 y 100 milisegundos. La ventaja de un intervalo de tiempo pequeño es que cada proceso obtiene una buena cantidad de tiempo de CPU y la CPU se utiliza de manera eficiente al cambiar entre procesos con frecuencia.

Guión

Para comprender cómo funciona la programación por turnos, consideremos un ejemplo. Supongamos que tenemos cuatro procesos que deben ejecutarse:

• Proceso 1: requiere 6 unidades de tiempo de CPU

• Proceso 2: Requiere 4 unidades de tiempo de CPU

• Proceso 3: requiere 2 unidades de tiempo de CPU

• Proceso 4: Requiere 8 unidades de tiempo de CPU

Supondremos que el cuanto de tiempo para el algoritmo de programación Round Robin está establecido en 3 unidades de tiempo. Al inicio del proceso de programación, los cuatro procesos se agregan a la cola de listos en el orden en que llegaron:

Ready queue: [Process 1, Process 2, Process 3, Process 4]

Luego, el algoritmo de programación comienza a ejecutar los procesos de manera cíclica, dando a cada proceso un cuanto de tiempo de 3 unidades:

• Tiempo 0: el proceso 1 comienza a ejecutarse (requiere 3 unidades de tiempo de CPU)

• Tiempo 3: el proceso 2 comienza a ejecutarse (requiere 3 unidades de tiempo de CPU)

• Tiempo 6: el proceso 3 comienza a ejecutarse (requiere 2 unidades de tiempo de CPU)

• Tiempo 8: el proceso 1 reanuda la ejecución (requiere 3 unidades de tiempo de CPU)

• Hora 11: el proceso 4 comienza a ejecutarse (requiere 3 unidades de tiempo de CPU)

• Tiempo 14: el proceso 2 reanuda la ejecución (requiere 1 unidad de tiempo de CPU)

• Tiempo 15: El proceso 1 termina de ejecutarse

• Tiempo 15: el proceso 3 reanuda la ejecución (requiere 1 unidad de tiempo de CPU)

• Tiempo 16: El proceso 2 termina de ejecutarse

• Tiempo 16: el proceso 4 reanuda la ejecución (requiere 3 unidades de tiempo de CPU)

• Tiempo 19: El proceso 3 termina de ejecutarse

• Tiempo 19: el proceso 4 reanuda la ejecución (requiere 2 unidades de tiempo de CPU)

• Tiempo 21: El proceso 4 termina de ejecutarse

Process Queue: P1 P2 P3 P1 P4 P2 P1 P3 P2 P4 P3 P4 P4

Como puede ver en el ejemplo, a cada proceso se le asigna un cuanto de tiempo de 3 unidades, independientemente de cuánto tiempo de CPU requiera para completarse. Una vez que un proceso ha completado su cuanto de tiempo, se adelanta y se mueve al final de la cola de listos, donde espera hasta que sea su turno para ejecutarse nuevamente.

Pseudocódigo

Echemos un vistazo al pseudocódigo para implementar la programación por turnos. Aquí hemos creado una función llamada round_robin() y variables como "tiempo_de_espera", "tiempo_de_vuelta", "restante", "actual", "orden_de_ejecución" y "cola_preparada" son inicializadas por la función. Una vez realizadas todas las operaciones se inicia un bucle.

• La función agrega todos los procesos que han llegado en el momento actual a la cola lista durante cada iteración del ciclo. Luego, el primer proceso en la cola listo se ejecuta durante el cuanto de tiempo o hasta que se complete, lo que ocurra primero.

• Si el proceso no finaliza dentro del período de tiempo, se vuelve a agregar a la cola de listos. Si finaliza, se calcula su tiempo de espera y tiempo de respuesta.

• Una vez ejecutados todos los procesos, la función calcula el tiempo de espera promedio y el tiempo de respuesta y devuelve el orden de ejecución como una matriz.

function round_robin(processes, quantum):
   //Initialize variables
   n = length of processes
   waiting_time = an array of n elements, initialized to 0
   turnaround_time = an array of n elements, initialized to 0
   remaining_time = an array of n elements, initialized to the CPU burst time of each process
   current_time = 0
   order_of_execution = an empty array
   ready_queue = an empty array
   index = 0
   //Loop until all processes are executed
  while true:
   //Add all processes that have arrived at the current time to the ready queue
   for i from index to n-1:
      if processes[i].arrival_time <= current_time:
         add i to ready_queue
            increment index
        
      //Break the loop if all processes have been executed
        if the ready_queue is empty and the sum of remaining_time is 0:
            break
        
        // Execute the first process in the ready queue
        if the ready_queue is not empty:
            process_index = the first element in ready_queue
            remove the first element from ready_queue
            add process_index to order_of_execution
            if remaining_time[process_index] > quantum:
                increment current_time by quantum
                decrement remaining_time[process_index] by quantum
                add process_index to ready_queue
            else:
                increment current_time by remaining_time[process_index]
                set waiting_time[process_index] to current_time - processes[process_index].burst_time
                set remaining_time[process_index] to 0
                set turnaround_time[process_index] to current_time - processes[process_index].arrival_time
        else:
            increment current_time by 1
    
    // Calculate average waiting time and turnaround time
    avg_waiting_time = sum of waiting_time divided by n
    avg_turnaround_time = sum of turnaround_time divided by n
    
    // Return the order of execution and average waiting/turnaround time
    return order_of_execution, avg_waiting_time, avg_turnaround_time

Implementación

Aquí puede encontrar la implementación del pseudocódigo anterior en Python y Java.

Ejemplo de Python

def round_robin(processes, quantum):
    # Initialize variables
    n = len(processes)
    waiting_time = [0] * n
    turnaround_time = [0] * n
    remaining_time = [processes[i][1] for i in range(n)]
    current_time = 0
    order_of_execution = []
    ready_queue = []
    index = 0
   
    # Loop until all processes are executed
    while True:
        # Add all processes that have arrived at the current time to the ready queue
        for i in range(index, n):
            if processes[i][0] <= current_time:
                ready_queue.append(i)
                index += 1
       
        # Break the loop if all processes have been executed
        if not ready_queue and sum(remaining_time) == 0:
            break
       
        # Execute the first process in the ready queue
        if ready_queue:
            process_index = ready_queue.pop(0)
            order_of_execution.append(process_index)
            if remaining_time[process_index] > quantum:
                current_time += quantum
                remaining_time[process_index] -= quantum
                ready_queue.append(process_index)
            else:
                current_time += remaining_time[process_index]
                waiting_time[process_index] = current_time - processes[process_index][1]
                remaining_time[process_index] = 0
                turnaround_time[process_index] = current_time - processes[process_index][0]
        else:
            current_time += 1
   
    # Calculate average waiting time and turnaround time
    avg_waiting_time = sum(waiting_time) / n
    avg_turnaround_time = sum(turnaround_time) / n
   
    return order_of_execution, avg_waiting_time, avg_turnaround_time
processes = [(0, 5), (1, 3), (2, 8), (3, 6)]
time_quantum = 2
order_of_execution, avg_waiting_time, avg_turnaround_time = round_robin(processes, time_quantum)
print("Order of execution:", order_of_execution)
print("Average waiting time:", avg_waiting_time)
print("Average turnaround time:", avg_turnaround_time)

Producción

Este código generará el orden de ejecución de los procesos, junto con el tiempo de espera promedio y el tiempo de respuesta promedio para el algoritmo de programación Round Robin con el cuanto de tiempo dado. Tenga en cuenta que esto es solo una implementación de ejemplo y es posible que deba modificarse para diferentes casos de uso o requisitos.

Order of execution: [0, 0, 1, 2, 0, 3, 1, 2, 3, 2, 3, 2]
Average waiting time: 10.25
Average turnaround time: 14.25

Ejemplo de Java

import java.util.*;
class Process {
    int pid; // process ID
    int arrival_time; // arrival time of process
    int burst_time; // CPU burst time of process
   
    Process(int pid, int arrival_time, int burst_time) {
        this.pid = pid;
        this.arrival_time = arrival_time;
        this.burst_time = burst_time;
    }
}
public class RoundRobinScheduling {
   //Driver method
    public static void main(String[] args) {
        Process[] processes = new Process[] {
            new Process(1, 0, 10),
            new Process(2, 3, 5),
            new Process(3, 5, 8),
            new Process(4, 6, 3),
            new Process(5, 8, 6)
        };       
        // Time quantum
        int quantum = 2;
       
        // Run Round Robin Scheduling algorithm
        int[] order_of_execution = round_robin(processes, quantum);
       
        // Print order of execution
        System.out.println("Order of Execution: " + Arrays.toString(order_of_execution));
    }
   //method to implement round-robin cpu scheduling
    public static int[] round_robin(Process[] processes, int quantum) {
        // Initialize variables
        int n = processes.length;
        int[] waiting_time = new int[n];
        int[] turnaround_time = new int[n];
        int[] remaining_time = new int[n];
        for (int i = 0; i < n; i++) {
            remaining_time[i] = processes[i].burst_time;
        }
        int current_time = 0;
        List<Integer> order_of_execution = new ArrayList<Integer>();
        Queue<Integer> ready_queue = new LinkedList<Integer>();
        int index = 0;
       
        // Loop until all processes are executed
        while (true) {
            // Add all processes that have arrived at the current time to the ready queue
            for (int i = index; i < n; i++) {
                if (processes[i].arrival_time <= current_time) {
                    ready_queue.add(i);
                    index++;
                }
            }
           
            // Break the loop if all processes have been executed
            if (ready_queue.isEmpty() && Arrays.stream(remaining_time).sum() == 0) {
                break;
            }
           
            // Execute the first process in the ready queue
            if (!ready_queue.isEmpty()) {
                int process_index = ready_queue.remove();
                order_of_execution.add(process_index);
                if (remaining_time[process_index] > quantum) {
                    current_time += quantum;
                    remaining_time[process_index] -= quantum;
                    ready_queue.add(process_index);
                } else {
                    current_time += remaining_time[process_index];
                    waiting_time[process_index] = current_time - processes[process_index].burst_time - processes[process_index].arrival_time;
                    remaining_time[process_index] = 0;
                    turnaround_time[process_index] = current_time - processes[process_index].arrival_time;
                }
            } else {
                current_time++;
            }
        }
       
        // Convert order of execution from list to array
        int[] order_of_execution_arr = new int[order_of_execution.size()];
        for (int i = 0; i < order_of_execution.size(); i++) {
            order_of_execution_arr[i] = order_of_execution.get(i);
        }
       
        // Print average waiting time and turnaround time
        float avg_waiting_time = Arrays.stream(waiting_time).sum() / (float) n;
        float avg_turnaround_time = Arrays.stream(turnaround_time).sum() / (float) n;
        System.out.println("Average Waiting Time: " + avg_waiting_time);
        System.out.println("Average Turnaround Time: " + avg_turnaround_time);
        // Return order of execution
        return order_of_execution_arr;
    }
}

Producción

Average Waiting Time: 15.0
Average Turnaround Time: 21.4
Order of Execution: [0, 0, 0, 1, 0, 2, 3, 1, 4, 0, 2, 3, 1, 4, 2, 4, 2]

Conclusión

Round Robin Scheduling es un algoritmo de programación de CPU popular que se utiliza en sistemas operativos para asignar tiempo de CPU a múltiples procesos de manera justa y eficiente. Es un algoritmo de programación preventiva en el que a cada proceso se le asigna un intervalo de tiempo fijo o un cuanto para ejecutar.

La programación Round Robin garantiza que cada proceso obtenga una parte justa del tiempo de CPU y que la CPU se utilice de manera eficiente al cambiar entre procesos con frecuencia. Sin embargo, la programación Round Robin puede causar cierta sobrecarga debido al cambio frecuente de contexto entre procesos y puede resultar en tiempos de espera más prolongados para algunos procesos.