Implémenter l'algorithme d'ordonnancement Round Robin

Introduction

Dans ce laboratoire, nous allons apprendre à implémenter l'algorithme d'ordonnancement Round Robin en C++. L'algorithme d'ordonnancement Round Robin est un algorithme préemptif dans lequel un processus est exécuté pendant un intervalle de temps fixe appelé quantum de temps. Si le processus termine son exécution dans le quantum de temps, il est terminé. Sinon, il est déplacé à la fin de la file d'attente des processus prêts.

Skills Graph

Créer un nouveau fichier C++

Tout d'abord, créez un nouveau fichier C++ dans le répertoire ~/project. Vous pouvez le nommer round_robin.cpp.

$ cd ~/project
$ touch round_robin.cpp

Inclure les bibliothèques nécessaires

Incluez les bibliothèques nécessaires dans le fichier round_robin.cpp.

#include <iostream>
using namespace std;

Définir la fonction main()

Définissez la fonction main() et initialisez les identifiants de processus (process IDs), les temps d'exécution (burst times), le quantum de temps et le nombre de processus.

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;
}

Implémenter la fonction pour trouver le temps d'attente

La fonction findWaitingTime() est utilisée pour trouver le temps d'attente pour tous les processus. Cette fonction est définie pour parcourir les processus de manière tourniquet (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;
    }
}

Implémenter la fonction pour trouver le temps de réponse

La fonction findTurnAroundTime() est utilisée pour trouver le temps de réponse (turn around time) pour tous les processus.

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];
}

Implémenter la fonction pour calculer le temps moyen

La fonction findavgTime() est utilisée pour calculer le temps d'attente moyen et le temps de réponse (turn around time) moyen pour tous les processus.

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;
}

Appeler la fonction findavgTime()

Appelez la fonction findavgTime() pour calculer le temps d'attente moyen et le temps de réponse (turn around time) moyen pour les processus.

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;
}

Pour exécuter le code dans un terminal, exécutez la commande suivante depuis le répertoire ~/project.

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

Résumé

Dans ce laboratoire, nous avons appris à implémenter l'algorithme d'ordonnancement Round Robin en C++. Cet algorithme est utilisé pour ordonnancer les processus dans un système d'exploitation pour une tranche de temps appelée quantum de temps (time quantum). Nous avons également vu comment calculer le temps d'attente moyen et le temps de réponse (turn around time) moyen pour un ensemble de processus.