Programme d'ordonnancement FCFS en C++ : Implémenter l'algorithme Premier arrivé, premier servi

Introduction

Dans ce laboratoire, nous allons implémenter l'algorithme d'ordonnancement First Come First Serve (FCFS) en utilisant le langage C++. Le FCFS est l'algorithme d'ordonnancement de CPU le plus simple, qui alloue le CPU aux processus dans l'ordre où ils le demandent. Le processus qui arrive en premier dans la file d'attente prête est servi en premier.

Cet algorithme est facile à comprendre et à implémenter, mais il peut ne pas offrir des performances optimales en termes de temps d'attente moyen. À la fin de ce laboratoire, vous comprendrez le fonctionnement de l'algorithme FCFS et serez capable de calculer des métriques importantes telles que le temps d'attente et le temps de réponse des processus.

Comprendre l'algorithme FCFS et créer la structure du programme

First Come First Serve (FCFS) est un algorithme d'ordonnancement non préemptif où les processus sont exécutés dans l'ordre où ils arrivent dans la file d'attente prête. Dans cette étape, nous allons créer notre fichier de programme et configurer la structure de base.

Commençons par créer un nouveau fichier C++ :

Ouvrez l'interface WebIDE et accédez au panneau de l'explorateur de fichiers.
Cliquez avec le bouton droit dans le panneau de l'explorateur et sélectionnez "Nouveau fichier".
Nommez le fichier fcfs.cpp et appuyez sur Entrée.

Maintenant, ajoutons les fichiers d'en-tête nécessaires et la déclaration de l'espace de noms à notre programme :

#include <iostream>
#include <iomanip> // Pour la sortie formatée

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    return 0;
}

Ce code configure la structure de base de notre programme avec :

#include <iostream> - Pour les opérations d'entrée/sortie
#include <iomanip> - Pour formater le tableau de sortie
using namespace std; - Pour utiliser l'espace de noms standard
Une fonction main() avec l'affichage d'un titre

Compilons et exécutons le programme pour nous assurer que tout est configuré correctement :

g++ fcfs.cpp -o fcfs
./fcfs

Vous devriez voir la sortie suivante :

FCFS Scheduling Algorithm Implementation
----------------------------------------

Cela confirme que la structure de base de notre programme fonctionne correctement. Dans l'étape suivante, nous allons implémenter la fonctionnalité pour saisir les détails des processus.

Implémentation de la fonctionnalité d'entrée des processus

Dans cette étape, nous allons implémenter la fonctionnalité permettant de collecter des informations sur les processus à ordonnancer. Pour l'ordonnancement FCFS, nous devons connaître :

Le nombre de processus
Le temps d'exécution (burst time) de chaque processus (le temps d'exécution requis par chaque processus)

Modifions notre fichier fcfs.cpp pour inclure cette fonctionnalité :

#include <iostream>
#include <iomanip> // Pour la sortie formatée

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Déclaration des variables
    int n;                  // Nombre de processus
    int burst_time[20];     // Tableau pour stocker le temps d'exécution de chaque processus

    // Obtenir le nombre de processus de l'utilisateur
    cout << "\nEntrez le nombre de processus (maximum 20) : ";
    cin >> n;

    // Validation de l'entrée
    if (n <= 0 || n > 20) {
        cout << "Nombre de processus invalide. Veuillez entrer une valeur entre 1 et 20." << endl;
        return 1;
    }

    // Obtenir le temps d'exécution de chaque processus
    cout << "\nEntrez le temps d'exécution (Burst Time) de chaque processus :" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Processus P" << i + 1 << " : ";
        cin >> burst_time[i];

        // Validation de l'entrée pour le temps d'exécution
        if (burst_time[i] <= 0) {
            cout << "Le temps d'exécution doit être un entier positif. Veuillez redémarrer le programme." << endl;
            return 1;
        }
    }

    // Afficher les données saisies
    cout << "\nProcessus\tTemps d'exécution" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

Voyons ce que nous avons ajouté :

Des variables pour stocker le nombre de processus (n) et le temps d'exécution de chaque processus (burst_time[20]).
Des invites d'entrée pour collecter le nombre de processus et le temps d'exécution de chaque processus.
Une validation de l'entrée pour s'assurer que le nombre de processus est dans une plage raisonnable (1 - 20) et que les temps d'exécution sont positifs.
Un affichage sous forme de tableau pour montrer les données saisies à des fins de vérification.

Compilons et exécutons notre programme mis à jour :

g++ fcfs.cpp -o fcfs
./fcfs

Lorsque vous exécutez le programme, vous serez invité à entrer le nombre de processus et leurs temps d'exécution. Essayez d'entrer les données suivantes :

Cela représente 3 processus avec des temps d'exécution de 5, 9 et 4 unités de temps respectivement. Vous devriez voir une sortie similaire à :

FCFS Scheduling Algorithm Implementation
----------------------------------------

Entrez le nombre de processus (maximum 20) : 3

Entrez le temps d'exécution (Burst Time) de chaque processus :
Processus P1 : 5
Processus P2 : 9
Processus P3 : 4

Processus Temps d'exécution
--------------------
P1      5
P2      9
P3      4

Cela confirme que notre fonctionnalité d'entrée fonctionne correctement. Dans l'étape suivante, nous allons calculer le temps d'attente et le temps de réponse de chaque processus.

Calcul du temps d'attente et du temps de réponse

Dans cette étape, nous allons calculer deux métriques importantes pour chaque processus :

Temps d'attente (WT - Waiting Time) : Le temps pendant lequel un processus attend dans la file d'attente prête avant d'obtenir le temps CPU.
Temps de réponse (TAT - Turnaround Time) : Le temps total écoulé entre la soumission et la complétion d'un processus.

Comprenons comment ces métriques sont calculées dans le FCFS :

Pour le premier processus (P1), le temps d'attente est toujours de 0 (il démarre immédiatement).
Pour les processus suivants, le temps d'attente est la somme des temps d'exécution (burst time) de tous les processus précédents.
Le temps de réponse de chaque processus est la somme de son temps d'exécution et de son temps d'attente.

Maintenant, modifions notre fichier fcfs.cpp pour ajouter ces calculs :

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    return 0;
}

Comprenons ce que nous avons ajouté :

Deux nouveaux tableaux : waiting_time[20] et turnaround_time[20] pour stocker le temps d'attente et le temps de réponse de chaque processus.
Des variables pour suivre le temps d'attente total et le temps de réponse total.
Des calculs pour le temps d'attente :
- Le premier processus a un temps d'attente de 0.
- Pour chaque processus suivant, le temps d'attente est la somme des temps d'exécution de tous les processus précédents.
Des calculs pour le temps de réponse :
- Pour chaque processus, le temps de réponse = temps d'exécution + temps d'attente.
Un tableau formaté pour afficher les résultats.

Compilons et exécutons notre programme mis à jour :

g++ fcfs.cpp -o fcfs
./fcfs

Essayez d'entrer les mêmes données que précédemment :

Vous devriez voir une sortie similaire à :

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Analysons les résultats :

P1 : Temps d'attente = 0, Temps de réponse = 5 (son temps d'exécution)
P2 : Temps d'attente = 5 (temps d'exécution de P1), Temps de réponse = 14 (5 + 9)
P3 : Temps d'attente = 14 (somme des temps d'exécution de P1 et P2), Temps de réponse = 18 (14 + 4)

Cela confirme que nos calculs de temps d'attente et de temps de réponse fonctionnent correctement. Dans l'étape suivante, nous allons calculer les temps moyens et afficher les résultats finaux.

Calcul des temps moyens et affichage des résultats finaux

Dans cette étape finale, nous allons calculer le temps d'attente moyen et le temps de réponse moyen pour tous les processus. Ces moyennes sont des métriques importantes pour évaluer l'efficacité d'un algorithme d'ordonnancement.

Modifions notre fichier fcfs.cpp pour ajouter ces calculs et terminer notre programme :

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    float avg_waiting_time = 0.0;
    float avg_turnaround_time = 0.0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    // Calculate average waiting time and average turnaround time
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;

    // Display the results with two decimal places
    cout << fixed << setprecision(2);
    cout << "\nAverage Waiting Time: " << avg_waiting_time << " time units" << endl;
    cout << "Average Turnaround Time: " << avg_turnaround_time << " time units" << endl;

    // Visual representation of the FCFS schedule (Gantt chart in text)
    cout << "\nGantt Chart:" << endl;
    cout << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }
    cout << endl << "|";

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "P" << i + 1;
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "|";
    }

    cout << endl << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }

    cout << endl;
    cout << "0";
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += burst_time[i];
        for (int j = 0; j < burst_time[i] * 2 - 1; j++) {
            cout << " ";
        }
        if (current_time < 10) cout << " ";
        cout << current_time;
    }
    cout << endl;

    return 0;
}

Comprenons ce que nous avons ajouté :

Deux nouvelles variables : avg_waiting_time et avg_turnaround_time pour stocker les temps moyens.
Des calculs pour les temps moyens :
- Temps d'attente moyen = Temps d'attente total / Nombre de processus
- Temps de réponse moyen = Temps de réponse total / Nombre de processus
Une sortie formatée pour afficher les temps moyens avec deux décimales.
Un simple diagramme de Gantt basé sur du texte pour visualiser l'ordonnancement FCFS :
- Chaque processus est représenté par son identifiant (P1, P2, etc.)
- La largeur de chaque bloc de processus est proportionnelle à son temps d'exécution
- Des marqueurs de temps sont affichés en bas

Compilons et exécutons notre programme final :

g++ fcfs.cpp -o fcfs
./fcfs

Essayez d'entrer les mêmes données que précédemment :

Vous devriez voir une sortie similaire à :

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Average Waiting Time: 6.33 time units
Average Turnaround Time: 12.33 time units

Gantt Chart:
 --------------------
|   P1    |    P2    |  P3  |
 --------------------
0         5         14     18

En examinant les résultats :

Temps d'attente moyen : (0 + 5 + 14) / 3 = 6,33 unités de temps
Temps de réponse moyen : (5 + 14 + 18) / 3 = 12,33 unités de temps

Le diagramme de Gantt représente visuellement comment les processus sont ordonnancés au fil du temps :

P1 s'exécute de 0 à 5
P2 s'exécute de 5 à 14
P3 s'exécute de 14 à 18

Cela termine notre implémentation de l'algorithme d'ordonnancement FCFS. Vous pouvez expérimenter avec différents nombres de processus et temps d'exécution pour voir comment cela affecte le temps d'attente moyen et le temps de réponse moyen.

Résumé

Dans ce laboratoire, nous avons réussi à implémenter l'algorithme d'ordonnancement CPU First Come First Serve (FCFS - Premier arrivé, premier servi) en utilisant le langage C++. Voici les concepts clés et les compétences que vous avez acquises :

Principes de base de l'algorithme FCFS : Comprendre comment les processus sont ordonnancés dans l'ordre d'arrivée.
Calcul des métriques de performance :
- Temps d'attente : Le temps pendant lequel un processus attend avant le début de son exécution.
- Temps de réponse : Le temps total écoulé entre la soumission et la complétion d'un processus.
- Temps d'attente moyen et temps de réponse moyen : Indicateurs clés de performance pour les algorithmes d'ordonnancement.
Concepts de programmation en C++ :
- Utilisation de tableaux pour stocker les informations sur les processus.
- Utilisation de boucles pour les calculs itératifs.
- Opérations d'entrée/sortie avec validation.
- Sortie formatée pour une meilleure présentation des données.
Techniques de visualisation : Création d'un diagramme de Gantt basé sur du texte pour visualiser le calendrier d'ordonnancement.

L'algorithme FCFS est simple à comprendre et à implémenter, mais il ne fournit pas toujours des performances optimales. Il peut entraîner l'"effet convoi" où les processus courts sont bloqués en attente derrière les processus longs, augmentant ainsi le temps d'attente moyen.

Cette implémentation sert de base pour comprendre des algorithmes d'ordonnancement plus complexes tels que le Shortest Job First (SJF - Plus court job d'abord), l'ordonnancement par priorité et le Round Robin (RR - Tourniquet) qui visent à optimiser différents aspects de l'ordonnancement des processus.

Programme C++ pour l'algorithme d'ordonnancement FCFS