Implementar el algoritmo de planificación Round Robin

Introducción

En este laboratorio, aprenderemos cómo implementar el Algoritmo de Planificación Round Robin en C++. El algoritmo de planificación Round Robin es un algoritmo preemptivo en el que un proceso se ejecuta durante un segmento de tiempo fijo conocido como quantum de tiempo. Si el proceso completa su ejecución dentro del quantum de tiempo, se termina; de lo contrario, se mueve al final de la cola de listos.

Skills Graph

Crear un nuevo archivo C++

Primero, crea un nuevo archivo C++ en el directorio ~/project. Puedes nombrarlo round_robin.cpp.

$ cd ~/project
$ touch round_robin.cpp

Incluir las bibliotecas necesarias

Incluye las bibliotecas necesarias en el archivo round_robin.cpp.

#include <iostream>
using namespace std;

Definir la función main()

Define la función main() e inicializa los identificadores de proceso (process IDs), los tiempos de ráfaga (burst times), el quantum y el número de procesos.

int main()
{
    // Process IDs
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    return 0;
}

Implementar la función para encontrar el tiempo de espera

La función findWaitingTime() se utiliza para encontrar el tiempo de espera (waiting time) de todos los procesos. Esta función está definida para iterar sobre los procesos de manera round-robin.

void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum)
{
    // Make a copy of burst times bt[] to store remaining
    // burst times.
    int rem_bt[n];
    for (int i = 0; i < n; i++)
        rem_bt[i] = bt[i];

    int t = 0; // Current time

    // Keep traversing processes in round-robin manner
    // until all of them are not done.
    while (1) {
        bool done = true;

        // Traverse all processes one by one repeatedly
        for (int i = 0; i < n; i++) {
            // If burst time of a process is greater than 0
            // then only need to process further
            if (rem_bt[i] > 0) {
                done = false; // There is a pending process

                /* If remaining burst time is greater than
                quantum then decrease the time slice
                from remaining burst time */
                if (rem_bt[i] > quantum) {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += quantum;

                    // Decrease the burst_time of current process
                    // by quantum
                    rem_bt[i] -= quantum;
                }
                /* If remaining burst time is smaller than
                or equal to quantum then the remaining
                burst time for this process is 0.*/
                else {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += rem_bt[i];

                    // Waiting time is current time minus time
                    // used by this process
                    wt[i] = t - bt[i];

                    // As the process gets fully executed
                    // make its remaining burst time = 0
                    rem_bt[i] = 0;
                }
            }
        }

        // If all processes are done
        if (done == true)
            break;
    }
}

Implementar la función para encontrar el tiempo de retorno

La función findTurnAroundTime() se utiliza para encontrar el tiempo de retorno (turn around time) de todos los procesos.

void findTurnAroundTime(int processes[], int n,
                         int bt[], int wt[], int tat[])
{
    // calculating turnaround time by adding
    // bt[i] + wt[i]
    for (int i = 0; i < n; i++)
        tat[i] = bt[i] + wt[i];
}

Implementar la función para calcular el tiempo promedio

La función findavgTime() se utiliza para calcular el tiempo de espera promedio (average waiting time) y el tiempo de retorno promedio (average turn around time) de todos los procesos.

void findavgTime(int processes[], int n, int bt[],
                                                 int quantum)
{
    int wt[n], tat[n], total_wt = 0, total_tat = 0;

    // Function to find waiting time of all processes
    findWaitingTime(processes, n, bt, wt, quantum);

    // Function to find turn around time for all processes
    findTurnAroundTime(processes, n, bt, wt, tat);

    // Display processes along with all details
    cout << "Processes "
         << " Burst time "
         << " Waiting time "
         << " Turn around time\n";

    // Calculate total waiting time and total turn
    // around time
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << i + 1 << "\t\t" << bt[i] << "\t "
             << wt[i] << "\t\t " << tat[i] << endl;
    }

    cout << "Average waiting time = "
         << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "
         << (float)total_tat / (float)n;
}

Llamar a la función findavgTime()

Llama a la función findavgTime() para calcular el tiempo de espera promedio (average waiting time) y el tiempo de retorno promedio (average turn around time) de los procesos.

int main()
{
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    // Function to find average time
    findavgTime(processes, n, burst_time, quantum);

    return 0;
}

Para ejecutar el código en una terminal, ejecuta el siguiente comando desde el directorio ~/project.

$ g++ round_robin.cpp -o round_robin &&./round_robin

Resumen

En este laboratorio, aprendimos cómo implementar el algoritmo de planificación Round Robin en C++. Este algoritmo se utiliza para programar procesos en un sistema operativo durante un intervalo de tiempo conocido como quantum (cuanto de tiempo). También vimos cómo calcular el tiempo de espera promedio (average waiting time) y el tiempo de retorno promedio (average turn around time) para un conjunto de procesos.