FCFS-Planungsalgorithmus: Was ist ein Beispielprogramm?
Nathaniel Brooks
Was ist die „Wer zuerst kommt, mahlt zuerst“-Methode?
Wer zuerst kommt, mahlt zuerst (FCFS) ist ein Planungsalgorithmus des Betriebssystems, der in die Warteschlange gestellte Anfragen und Prozesse automatisch in der Reihenfolge ihres Eintreffens ausführt. Es ist der einfachste und simpelste CPU-Planungsalgorithmus. Bei diesem Algorithmustyp erhalten Prozesse, die zuerst die CPU anfordern, zuerst die CPU-Zuteilung. Dies wird mit einer FIFO-Warteschlange verwaltet. Die Langform von FCFS ist First Come First Serve.
Wenn der Prozess in die Bereitschaftswarteschlange eintritt, wird sein PCB (Process Control Block) mit dem Ende der Warteschlange verbunden und sollte, wenn die CPU frei wird, dem Prozess am Anfang der Warteschlange zugewiesen werden.
Merkmale der FCFS-Methode
- Es unterstützt nicht-präventive und präemptive Planungsalgorithmen.
- Aufträge werden immer nach dem Prinzip „Wer zuerst kommt, mahlt zuerst“ ausgeführt.
- Es ist einfach zu implementieren und zu verwenden.
- Diese Methode ist leistungsschwach und die allgemeine Wartezeit ist recht hoch.
Beispiel für FCFS-Planung
Ein reales Beispiel für die FCFS-Methode ist der Kauf einer Kinokarte am Ticketschalter. Bei diesem Planungsalgorithmus wird eine Person entsprechend der Warteschlangenweise bedient. Die Person, die zuerst in der Warteschlange ankommt, kauft zuerst das Ticket und dann das nächste. Dies wird so lange fortgesetzt, bis die letzte Person in der Warteschlange das Ticket kauft. Mit diesem Algorithmus funktioniert der CPU-Prozess auf ähnliche Weise.
Wie funktioniert FCFS? Berechnung der durchschnittlichen Wartezeit
Hier ist ein Beispiel für fünf Prozesse, die zu unterschiedlichen Zeiten eintreffen. Jeder Prozess hat eine andere Burst-Zeit.
| Prozess | Burst-Zeit | Ankunftszeit |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Mithilfe des FCFS-Planungsalgorithmus werden diese Prozesse wie folgt gehandhabt.
Schritt 1) Der Prozess beginnt mit P4, dessen Ankunftszeit 0 ist
Schritt 2) Zum Zeitpunkt = 1 kommt P3 an. P4 wird noch ausgeführt. Daher wird P3 in einer Warteschlange gehalten.
| Prozess | Burst-Zeit | Ankunftszeit |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 3) Zum Zeitpunkt = 2 trifft P1 ein und wird in der Warteschlange gehalten.
| Prozess | Burst-Zeit | Ankunftszeit |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 4) Zum Zeitpunkt = 3 schließt der P4-Prozess seine Ausführung ab.
Schritt 5) Zum Zeitpunkt = 4 beginnt P3, der erste in der Warteschlange, mit der Ausführung.
| Prozess | Burst-Zeit | Ankunftszeit |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 6) Zum Zeitpunkt =5 kommt P2 an und wird in einer Warteschlange gehalten.
| Prozess | Burst-Zeit | Ankunftszeit |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Schritt 7) Zum Zeitpunkt 11 schließt P3 seine Ausführung ab.
Schritt 8) Zum Zeitpunkt = 11 beginnt P1 mit der Ausführung. Die Burst-Zeit beträgt 6. Die Ausführung wird im Zeitintervall 17 abgeschlossen
Schritt 9) Zum Zeitpunkt = 17 beginnt P5 mit der Ausführung. Es hat eine Burst-Zeit von 4. Die Ausführung wird zum Zeitpunkt = 21 abgeschlossen
Schritt 10) Zum Zeitpunkt = 21 beginnt P2 mit der Ausführung. Die Burst-Zeit beträgt 2. Die Ausführung wird im Zeitintervall 23 abgeschlossen
Schritt 11) Berechnen wir die durchschnittliche Wartezeit für das obige Beispiel.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
Durchschnittliche Wartezeit
= 40 / 5 = 8
Vorteile von FCFS
Hier sind die Vorteile/Vorteile der Verwendung des FCFS-Planungsalgorithmus:
- Die einfachste Form von a CPU-Planungsalgorithmus
- Einfach zu programmieren
- Wer zuerst kommt, mahlt zuerst
Nachteile von FCFS
Hier sind die Vor- und Nachteile der Verwendung des FCFS-Planungsalgorithmus:
- Es handelt sich um einen nicht präemptiven CPU-Planungsalgorithmus. Nachdem der Prozess der CPU zugewiesen wurde, wird die CPU daher erst dann freigegeben, wenn die Ausführung abgeschlossen ist.
- Die durchschnittliche Wartezeit ist hoch.
- Kurze Prozesse, die sich ganz hinten in der Warteschlange befinden, müssen warten, bis der lange Prozess ganz vorne abgeschlossen ist.
- Keine ideale Technik für Time-Sharing-Systeme.
- Aufgrund seiner Einfachheit ist FCFS nicht sehr effizient.
Zusammenfassung
- Definition: FCFS ist ein Planungsalgorithmus für Betriebssysteme, der in die Warteschlange gestellte Anfragen und Prozesse automatisch in der Reihenfolge ihres Eintreffens ausführt.
- Es unterstützt nicht-präventive und präventive Planung
- Algorithmus.
- FCFS steht für First Come First Serve
- Ein reales Beispiel für die FCFS-Methode ist der Kauf einer Kinokarte am Ticketschalter.
- Es handelt sich um die einfachste Form eines CPU-Planungsalgorithmus
- Es handelt sich um einen nicht präemptiven CPU-Planungsalgorithmus. Nachdem der Prozess der CPU zugewiesen wurde, wird die CPU daher erst dann freigegeben, wenn die Ausführung abgeschlossen ist.
