Wat is de methode wie het eerst komt, het eerst maalt?
First Come First Serve (FCFS) is een planningsalgoritme van het besturingssysteem dat verzoeken en processen in de wachtrij automatisch uitvoert op volgorde van binnenkomst. Het is het gemakkelijkste en eenvoudigste CPU-planningsalgoritme. In dit type algoritme krijgen processen die eerst de CPU verzoeken eerst de CPU-toewijzing. Dit wordt beheerd met een FIFO-wachtrij. De volledige vorm van FCFS is wie het eerst komt, het eerst maalt.
Wanneer het proces de gereedstaande wachtrij binnengaat, wordt de PCB (Process Control Block) ervan verbonden met de staart van de wachtrij en, wanneer de CPU vrij komt, moet deze aan het begin van de wachtrij worden toegewezen aan het proces.
In deze handleiding voor het besturingssysteem leert u:
- Wat is de methode wie het eerst komt, het eerst maalt?
- Kenmerken van de FCFS-methode
- Voorbeeld van FCFS-planning
- Hoe FCFS werkt? Berekenen van gemiddelde wachttijd
- Voordelen van FCFS
- Nadelen van FCFS
Kenmerken van de FCFS-methode
- Het ondersteunt niet-preventieve en preventieve planningsalgoritmen.
- Jobs 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 realistisch voorbeeld van de FCFS-methode is het kopen van een bioscoopkaartje aan de kassa. In dit planningsalgoritme wordt een persoon bediend volgens de wachtrijmanier. De persoon die als eerste in de wachtrij arriveert, koopt eerst het kaartje en dan de volgende. Dit gaat door totdat de laatste persoon in de wachtrij het kaartje koopt. Met behulp van dit algoritme werkt het CPU-proces op een vergelijkbare manier.
Hoe FCFS werkt? Berekenen van gemiddelde wachttijd
Hier is een voorbeeld van vijf processen die op verschillende tijdstippen aankomen. Elk proces heeft een andere burst-tijd.
| Werkwijze | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Met behulp van het FCFS-planningsalgoritme worden deze processen als volgt afgehandeld.
Stap 0) Het proces begint met P4 die aankomsttijd 0 heeft
Stap 1) Op tijd = 1 arriveert P3. P4 wordt nog uitgevoerd. Daarom wordt P3 in een wachtrij gehouden.
| Werkwijze | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 2) Op tijd = 2 arriveert P1 die in de wachtrij wordt gehouden.
| Werkwijze | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 3) Op tijd = 3 voltooit het P4-proces zijn uitvoering.
Stap 4) Op tijd = 4 begint P3, die als eerste in de wachtrij staat, met de uitvoering.
| Werkwijze | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 5) Op tijd = 5 komt P2 aan en wordt in een wachtrij gehouden.
| Werkwijze | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 6) Op tijdstip 11 voltooit P3 zijn uitvoering.
Stap 7) Op tijd = 11 begint P1 met de uitvoering. Het heeft een burst-tijd van 6. Het voltooit de uitvoering in tijdsinterval 17
Stap 8) Op tijd = 17 begint P5 met de uitvoering. Het heeft een burst-tijd van 4. De uitvoering is voltooid op tijd = 21
Stap 9) Op tijd = 21 begint P2 met de uitvoering. Het heeft een burst-tijd van 2. Het voltooit de uitvoering met tijdsinterval 23
Stap 10) 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 zijn de voor- / voordelen van het gebruik van het FCFS-planningsalgoritme:
- De eenvoudigste vorm van een CPU-planningsalgoritme
- Makkelijk te programmeren
- Wie het eerst komt het eerst maalt
Nadelen van FCFS
Hier zijn 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 aan de voorkant is afgelopen.
- Geen ideale techniek voor timesharing-systemen.
- Vanwege zijn eenvoud is FCFS niet erg efficiënt.
Overzicht:
- Definitie: FCFS is een planningsalgoritme van het besturingssysteem dat verzoeken en processen in de wachtrij automatisch uitvoert op volgorde van binnenkomst
- Het ondersteunt niet-preventieve en preventieve planning
- algoritme.
- FCFS staat voor First Come First Serve
- Een realistisch voorbeeld 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.