FCFS-planningsalgoritme: wat is, voorbeeldprogramma
Nathaniel Brooks
Wat is de First Come First Serve-methode?
Wie het eerst komt, het eerst maalt (FCFS) is een planningsalgoritme voor besturingssystemen dat automatisch wachtrijverzoeken en processen uitvoert in de volgorde waarin ze binnenkomen. Het is het gemakkelijkste en eenvoudigste CPU-planningsalgoritme. In dit type algoritme krijgen processen die als eerste de CPU aanvragen, als eerste de CPU-toewijzing. Dit wordt beheerd met een FIFO-wachtrij. De volledige vorm van FCFS is First Come First Serve.
Wanneer het proces de gereedstaande wachtrij binnengaat, wordt zijn PCB (Process Control Block) gekoppeld aan de staart van de wachtrij en wanneer de CPU vrijkomt, moet deze worden toegewezen aan het proces aan het begin van de wachtrij.
Kenmerken van de FCFS-methode
- Het ondersteunt niet-preventieve en preventieve planningsalgoritmen.
- Taken worden altijd uitgevoerd op basis van wie het eerst komt, het eerst maalt.
- Het is gemakkelijk te implementeren en te gebruiken.
- Deze methode presteert slecht en de algemene wachttijd is vrij hoog.
Voorbeeld van FCFS-planning
Een praktijkvoorbeeld van de FCFS-methode is het kopen van een bioscoopkaartje aan de kassa. In dit planningsalgoritme wordt een persoon bediend volgens de wachtrijwijze. De persoon die als eerste in de rij arriveert, koopt eerst het kaartje en daarna het volgende. Dit gaat door totdat de laatste persoon in de wachtrij het ticket koopt. Met dit algoritme werkt het CPU-proces op een vergelijkbare manier.
Hoe FCFS werkt? Berekening van de gemiddelde wachttijd
Hier is een voorbeeld van vijf processen die op verschillende tijdstippen arriveren. Elk proces heeft een andere burst-tijd.
| Proces | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Met behulp van het FCFS-planningsalgoritme worden deze processen als volgt afgehandeld.
Stap 1) Het proces begint met P4, die aankomsttijd 0 heeft
Stap 2) Op tijdstip=1 arriveert P3. P4 wordt nog steeds uitgevoerd. Daarom wordt P3 in een wachtrij gehouden.
| Proces | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 3) Op tijdstip= 2 arriveert P1 die in de wachtrij wordt gehouden.
| Proces | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 4) Op tijdstip=3 voltooit het P4-proces de uitvoering ervan.
Stap 5) Op tijdstip=4 begint P3, die als eerste in de wachtrij staat, met de uitvoering.
| Proces | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 6) Op tijdstip =5 arriveert P2, en deze wordt in een wachtrij gehouden.
| Proces | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 7) Op tijdstip 11 voltooit P3 de uitvoering.
Stap 8) Op tijdstip=11 begint P1 met de uitvoering. Het heeft een burst-tijd van 6. Het voltooit de uitvoering op tijdsinterval 17
Stap 9) Op tijdstip=17 begint P5 met de uitvoering. Het heeft een burst-tijd van 4. Het voltooit de uitvoering op tijd = 21
Stap 10) Op tijdstip=21 begint P2 met de uitvoering. Het heeft een burst-tijd van 2. Het voltooit de uitvoering op tijdsinterval 23
Stap 11) Laten we de gemiddelde wachttijd voor bovenstaand voorbeeld berekenen.
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
Gemiddelde wachttijd
= 40/5= 8
Voordelen van FCFS
Hier volgen de voor- en voordelen van het gebruik van het FCFS-planningsalgoritme:
- De eenvoudigste vorm van a CPU-planningsalgoritme
- Eenvoudig te programmeren
- Wie het eerst komt het eerst maalt
Nadelen van FCFS
Hier volgen de nadelen/nadelen van het gebruik van het FCFS-planningsalgoritme:
- Het is een niet-preventief CPU-planningsalgoritme, dus nadat het proces aan de CPU is toegewezen, zal het de CPU nooit vrijgeven totdat de uitvoering is voltooid.
- De gemiddelde wachttijd is hoog.
- Korte processen die achteraan in de wachtrij staan, moeten wachten tot het lange proces vooraan is voltooid.
- Geen ideale techniek voor timesharing-systemen.
- Vanwege zijn eenvoud is FCFS niet erg efficiënt.
Samenvatting
- Definitie: FCFS is een algoritme voor het plannen van besturingssystemen dat automatisch wachtrijverzoeken en -processen uitvoert op volgorde van aankomst.
- Het ondersteunt niet-preventieve en preventieve planning
- algoritme.
- FCFS staat voor First Come First Serve
- Een praktijkvoorbeeld van de FCFS-methode is het kopen van een bioscoopkaartje aan de kassa.
- Het is de eenvoudigste vorm van een CPU-planningsalgoritme
- Het is een niet-preventief CPU-planningsalgoritme, dus nadat het proces aan de CPU is toegewezen, zal het de CPU nooit vrijgeven totdat de uitvoering is voltooid.
