C++-Programm für den FCFS-Scheduling-Algorithmus

C++C++Beginner
Jetzt üben

💡 Dieser Artikel wurde von AI-Assistenten übersetzt. Um die englische Version anzuzeigen, können Sie hier klicken

Einführung

In diesem Lab werden wir den First Come First Serve (FCFS) Scheduling-Algorithmus mit C++ implementieren. FCFS ist der einfachste CPU-Scheduling-Algorithmus, der die CPU den Prozessen in der Reihenfolge zuweist, in der sie sie anfordern. Der Prozess, der zuerst in die Warteschlange eintritt, wird zuerst bedient.

Dieser Algorithmus ist einfach zu verstehen und zu implementieren, bietet jedoch möglicherweise nicht die optimale Leistung in Bezug auf die durchschnittliche Wartezeit. Am Ende dieses Labs werden Sie verstehen, wie der FCFS-Algorithmus funktioniert und können wichtige Metriken wie die Wartezeit und die Durchlaufzeit für Prozesse berechnen.


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/BasicsGroup(["Basics"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp/BasicsGroup -.-> cpp/variables("Variables") cpp/BasicsGroup -.-> cpp/arrays("Arrays") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/user_input("User Input") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") subgraph Lab Skills cpp/variables -.-> lab-96161{{"C++-Programm für den FCFS-Scheduling-Algorithmus"}} cpp/arrays -.-> lab-96161{{"C++-Programm für den FCFS-Scheduling-Algorithmus"}} cpp/output -.-> lab-96161{{"C++-Programm für den FCFS-Scheduling-Algorithmus"}} cpp/user_input -.-> lab-96161{{"C++-Programm für den FCFS-Scheduling-Algorithmus"}} cpp/files -.-> lab-96161{{"C++-Programm für den FCFS-Scheduling-Algorithmus"}} end

Verständnis von FCFS und Erstellung der Programmstruktur

First Come First Serve (FCFS) ist ein nicht-präemptiver Scheduling-Algorithmus, bei dem Prozesse in der Reihenfolge ausgeführt werden, in der sie in die Warteschlange eintreten. In diesem Schritt werden wir unsere Programmdatei erstellen und die Grundstruktur einrichten.

Beginnen wir damit, eine neue C++-Datei zu erstellen:

  1. Öffnen Sie die WebIDE-Schnittstelle und navigieren Sie zum Dateiexplorer-Panel.
  2. Klicken Sie mit der rechten Maustaste im Explorer-Panel und wählen Sie "Neue Datei".
  3. Benennen Sie die Datei fcfs.cpp und drücken Sie die Eingabetaste.

Fügen wir nun die erforderlichen Header-Dateien und die Namespace-Deklaration zu unserem Programm hinzu:

#include <iostream>
#include <iomanip> // Für formatierte Ausgabe

using namespace std;

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

    return 0;
}

Dieser Code richtet die Grundstruktur unseres Programms ein mit:

  • #include <iostream> - Für Ein- und Ausgabeoperationen
  • #include <iomanip> - Zum Formatieren der Ausgabetabelle
  • using namespace std; - Um den Standard-Namespace zu verwenden
  • Eine main()-Funktion mit Anzeige eines Titels

Lassen Sie uns das Programm kompilieren und ausführen, um sicherzustellen, dass alles korrekt eingerichtet ist:

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

Sie sollten die folgende Ausgabe sehen:

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

Dies bestätigt, dass unsere Grundprogrammstruktur korrekt funktioniert. Im nächsten Schritt werden wir die Funktionalität zur Eingabe von Prozessdetails implementieren.

Implementierung der Prozess-Eingabefunktionalität

In diesem Schritt werden wir die Funktionalität implementieren, um Informationen über die zu planenden Prozesse zu sammeln. Für die FCFS-Scheduling benötigen wir folgende Informationen:

  1. Die Anzahl der Prozesse
  2. Die Burst-Zeit (Ausführungszeit) für jeden Prozess

Ändern wir unsere fcfs.cpp-Datei, um diese Funktionalität hinzuzufügen:

#include <iostream>
#include <iomanip> // Für formatierte Ausgabe

using namespace std;

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

    // Variablendeklaration
    int n;                  // Anzahl der Prozesse
    int burst_time[20];     // Array zur Speicherung der Burst-Zeit jedes Prozesses

    // Anzahl der Prozesse vom Benutzer abfragen
    cout << "\nGeben Sie die Anzahl der Prozesse (maximal 20) ein: ";
    cin >> n;

    // Eingabevalidierung
    if (n <= 0 || n > 20) {
        cout << "Ungültige Anzahl von Prozessen. Bitte geben Sie einen Wert zwischen 1 und 20 ein." << endl;
        return 1;
    }

    // Burst-Zeit für jeden Prozess abfragen
    cout << "\nGeben Sie die Burst-Zeit für jeden Prozess ein:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Prozess P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Eingabevalidierung für die Burst-Zeit
        if (burst_time[i] <= 0) {
            cout << "Die Burst-Zeit muss eine positive Ganzzahl sein. Bitte starten Sie das Programm neu." << endl;
            return 1;
        }
    }

    // Die eingegebenen Daten anzeigen
    cout << "\nProzess\tBurst-Zeit" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

Schauen wir uns an, was wir hinzugefügt haben:

  1. Variablen zur Speicherung der Anzahl der Prozesse (n) und der Burst-Zeit für jeden Prozess (burst_time[20]).
  2. Eingabeaufforderungen, um die Anzahl der Prozesse und die Burst-Zeit für jeden Prozess zu sammeln.
  3. Eingabevalidierung, um sicherzustellen, dass die Anzahl der Prozesse in einem vernünftigen Bereich (1 - 20) liegt und die Burst-Zeiten positiv sind.
  4. Eine Tabellenanzeige, um die eingegebenen Daten zur Überprüfung anzuzeigen.

Kompilieren und führen wir unser aktualisiertes Programm aus:

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

Wenn Sie das Programm ausführen, werden Sie aufgefordert, die Anzahl der Prozesse und ihre Burst-Zeiten einzugeben. Versuchen Sie, die folgenden Daten einzugeben:

3
5
9
4

Dies repräsentiert 3 Prozesse mit Burst-Zeiten von 5, 9 und 4 Zeiteinheiten. Sie sollten eine Ausgabe ähnlich der folgenden sehen:

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

Geben Sie die Anzahl der Prozesse (maximal 20) ein: 3

Geben Sie die Burst-Zeit für jeden Prozess ein:
Prozess P1: 5
Prozess P2: 9
Prozess P3: 4

Prozess Burst-Zeit
--------------------
P1      5
P2      9
P3      4

Dies bestätigt, dass unsere Eingabefunktionalität korrekt funktioniert. Im nächsten Schritt werden wir die Wartezeit und die Durchlaufzeit für jeden Prozess berechnen.

Berechnung der Wartezeit und der Durchlaufzeit

In diesem Schritt werden wir zwei wichtige Metriken für jeden Prozess berechnen:

  1. Wartezeit (WT): Die Zeit, die ein Prozess in der Warteschlange wartet, bevor er CPU-Zeit erhält.
  2. Durchlaufzeit (TAT): Die gesamte Zeit, die von der Einreichung eines Prozesses bis zu seiner Beendigung vergeht.

Lassen Sie uns verstehen, wie diese in FCFS berechnet werden:

  • Für den ersten Prozess (P1) ist die Wartezeit immer 0 (er beginnt sofort).
  • Für nachfolgende Prozesse ist die Wartezeit die Summe der Burst-Zeiten aller vorherigen Prozesse.
  • Die Durchlaufzeit für jeden Prozess ist die Summe seiner Burst-Zeit und Wartezeit.

Ändern wir nun unsere fcfs.cpp-Datei, um diese Berechnungen hinzuzufügen:

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

Lassen Sie uns verstehen, was wir hinzugefügt haben:

  1. Zwei neue Arrays: waiting_time[20] und turnaround_time[20], um die Warte- und Durchlaufzeiten für jeden Prozess zu speichern.
  2. Variablen, um die Gesamtwartezeit und die Gesamtdurchlaufzeit zu verfolgen.
  3. Berechnungen für die Wartezeit:
    • Der erste Prozess hat eine Wartezeit von 0.
    • Für jeden nachfolgenden Prozess ist die Wartezeit die Summe der Burst-Zeiten aller vorherigen Prozesse.
  4. Berechnungen für die Durchlaufzeit:
    • Für jeden Prozess gilt: Durchlaufzeit = Burst-Zeit + Wartezeit.
  5. Eine formatierte Tabelle, um die Ergebnisse anzuzeigen.

Kompilieren und führen wir unser aktualisiertes Programm aus:

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

Versuchen Sie, die gleichen Daten wie zuvor einzugeben:

3
5
9
4

Sie sollten eine Ausgabe ähnlich der folgenden sehen:

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

Analysieren wir die Ergebnisse:

  • P1: Wartezeit = 0, Durchlaufzeit = 5 (seine Burst-Zeit)
  • P2: Wartezeit = 5 (P1's Burst-Zeit), Durchlaufzeit = 14 (5 + 9)
  • P3: Wartezeit = 14 (P1 + P2's Burst-Zeiten), Durchlaufzeit = 18 (14 + 4)

Dies bestätigt, dass unsere Berechnungen für die Warte- und Durchlaufzeiten korrekt funktionieren. Im nächsten Schritt werden wir die durchschnittlichen Zeiten berechnen und die endgültigen Ergebnisse anzeigen.

Berechnung der durchschnittlichen Zeiten und Anzeige der endgültigen Ergebnisse

In diesem letzten Schritt werden wir die durchschnittliche Wartezeit und die durchschnittliche Durchlaufzeit für alle Prozesse berechnen. Diese Durchschnittswerte sind wichtige Metriken zur Bewertung der Effizienz eines Scheduling-Algorithmus.

Ändern wir unsere fcfs.cpp-Datei, um diese Berechnungen hinzuzufügen und unser Programm abzuschließen:

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

Lassen Sie uns verstehen, was wir hinzugefügt haben:

  1. Zwei neue Variablen: avg_waiting_time und avg_turnaround_time, um die durchschnittlichen Zeiten zu speichern.
  2. Berechnungen für die durchschnittlichen Zeiten:
    • Durchschnittliche Wartezeit = Gesamtwartezeit / Anzahl der Prozesse
    • Durchschnittliche Durchlaufzeit = Gesamtdurchlaufzeit / Anzahl der Prozesse
  3. Formatierte Ausgabe, um die durchschnittlichen Zeiten mit zwei Dezimalstellen anzuzeigen.
  4. Ein einfaches textbasiertes Gantt-Diagramm, um das FCFS-Scheduling zu visualisieren:
    • Jeder Prozess wird durch seine ID (P1, P2, etc.) repräsentiert.
    • Die Breite jedes Prozessblocks ist proportional zu seiner Burst-Zeit.
    • Zeitmarkierungen werden unten angezeigt.

Kompilieren und führen wir unser finales Programm aus:

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

Versuchen Sie, die gleichen Daten wie zuvor einzugeben:

3
5
9
4

Sie sollten eine Ausgabe ähnlich der folgenden sehen:

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

Betrachten wir die Ergebnisse:

  • Durchschnittliche Wartezeit: (0 + 5 + 14) / 3 = 6,33 Zeiteinheiten
  • Durchschnittliche Durchlaufzeit: (5 + 14 + 18) / 3 = 12,33 Zeiteinheiten

Das Gantt-Diagramm zeigt visuell, wie die Prozesse im Laufe der Zeit geplant werden:

  • P1 läuft von Zeit 0 bis 5.
  • P2 läuft von Zeit 5 bis 14.
  • P3 läuft von Zeit 14 bis 18.

Dies schließt unsere Implementierung des FCFS-Scheduling-Algorithmus ab. Sie können mit verschiedenen Anzahlen von Prozessen und Burst-Zeiten experimentieren, um zu sehen, wie sich dies auf die durchschnittliche Wartezeit und Durchlaufzeit auswirkt.

Zusammenfassung

In diesem Lab haben wir erfolgreich den First Come First Serve (FCFS)-CPU-Scheduling-Algorithmus mit C++ implementiert. Hier sind die wichtigsten Konzepte und Fähigkeiten, die Sie gelernt haben:

  1. Grundlagen des FCFS-Algorithmus: Verständnis, wie Prozesse in der Reihenfolge ihrer Ankunft geplant werden.

  2. Berechnung von Leistungsmetriken:

    • Wartezeit: Die Zeit, die ein Prozess wartet, bevor die Ausführung beginnt.
    • Durchlaufzeit: Die gesamte Zeit von der Einreichung bis zur Beendigung.
    • Durchschnittliche Wartezeit und durchschnittliche Durchlaufzeit: Schlüsselindikatoren für die Leistung von Scheduling-Algorithmen.
  3. C++-Programmierkonzepte:

    • Arrays zur Speicherung von Prozessinformationen.
    • Schleifen für iterative Berechnungen.
    • Eingabe-/Ausgabe-Operationen mit Validierung.
    • Formatierte Ausgabe für eine bessere Datenpräsentation.
  4. Visualisierungstechniken: Erstellung eines textbasierten Gantt-Diagramms zur Visualisierung des Scheduling-Zeitplans.

Der FCFS-Algorithmus ist einfach zu verstehen und zu implementieren, bietet aber möglicherweise nicht immer die optimale Leistung. Er kann zum "Konvoi-Effekt" führen, bei dem kurze Prozesse hinter langen Prozessen hängen bleiben und die durchschnittliche Wartezeit erhöhen.

Diese Implementierung bildet die Grundlage für das Verständnis von komplexeren Scheduling-Algorithmen wie Shortest Job First (SJF), Priority Scheduling und Round Robin (RR), die darauf abzielen, verschiedene Aspekte des Prozesschedulings zu optimieren.