Čo je metóda „Prvý príde prvý, ktorý slúži“?
FCFS (First Come First Serve) je plánovací algoritmus operačného systému, ktorý automaticky vykonáva požiadavky a procesy vo fronte v poradí podľa ich príchodu. Je to najjednoduchší a najjednoduchší algoritmus plánovania procesora. V tomto type algoritmu dostanú procesy, ktoré najskôr požiadajú o CPU, najskôr pridelenie CPU. Spravuje sa to pomocou frontu FIFO. Plná forma FCFS je First Come First Serve.
Keď proces vstupuje do frontu pripravených, jeho PCB (Process Control Block) je prepojený s chvostom frontu a keď sa CPU uvoľní, mal by byť procesu priradený na začiatku frontu.
V tomto výučbe operačného systému sa dozviete:
- Čo je metóda „Prvý príde prvý, ktorý slúži“?
- Charakteristika metódy FCFS
- Príklad plánovania FCFS
- Ako funguje FCFS? Výpočet priemernej čakacej doby
- Výhody FCFS
- Nevýhody FCFS
Charakteristika metódy FCFS
- Podporuje nepreventívny a preventívny plánovací algoritmus.
- Úlohy sa vždy vykonávajú podľa princípu „kto skôr príde“.
- Ľahko sa implementuje a používa.
- Táto metóda nemá dobrý výkon a celková doba čakania je pomerne vysoká.
Príklad plánovania FCFS
Reálnym príkladom metódy FCFS je zakúpenie lístka do kina na pulte lístka. V tomto plánovacom algoritme je osobe obsluhované spôsobom fronty. Osoba, ktorá príde na rad ako prvá, si najskôr kúpi lístok a až potom ďalší. Bude to pokračovať, kým si lístok zakúpi posledná osoba vo fronte. Použitím tohto algoritmu proces CPU pracuje podobným spôsobom.
Ako funguje FCFS? Výpočet priemernej čakacej doby
Tu je príklad piatich procesov prichádzajúcich v rôznych časoch. Každý proces má inú dobu prasknutia.
| Proces | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Pomocou plánovacieho algoritmu FCFS sa s týmito procesmi zaobchádza nasledovne.
Krok 0) Proces začína P4, ktorý má čas príchodu 0
Krok 1) V čase = 1 dorazí P3. P4 sa stále vykonáva. Preto je P3 vedený v rade.
| Proces | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 2) V čase = 2 dorazí P1, ktorý je zaradený do poradia.
| Proces | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 3) V čase = 3 proces P4 dokončí svoje vykonávanie.
Krok 4) V čase = 4 začne P3, ktoré je vo fronte prvé, vykonávanie.
| Proces | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 5) V čase = 5 dorazí P2 a je zaradený do poradia.
| Proces | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 6) V čase 11 P3 dokončí svoje vykonávanie.
Krok 7) V čase = 11 začne P1 vykonávanie. Má čas roztrhnutia 6. Dokončuje vykonávanie v časovom intervale 17
Krok 8) V čase = 17 začne P5 vykonávanie. Má čas roztrhnutia 4. Dokončuje vykonávanie v čase = 21
Krok 9) V čase = 21 začne P2 vykonávanie. Má čas roztrhnutia 2. Dokončuje vykonávanie v časovom intervale 23
Krok 10) Vypočítajme priemernú dobu čakania pre vyššie uvedený príklad.
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
Priemerná doba čakania
= 40/5 = 8
Výhody FCFS
Tu sú výhody a výhody použitia plánovacieho algoritmu FCFS:
- Najjednoduchšia forma plánovacieho algoritmu CPU
- Ľahko programovateľné
- Kto skôr príde, bude skôr obslúžený
Nevýhody FCFS
Tu sú nevýhody / nevýhody používania plánovacieho algoritmu FCFS:
- Jedná sa o nepreventívny plánovací algoritmus CPU, takže po pridelení procesu CPU nikdy procesor neuvoľní, kým nedokončí vykonávanie.
- Priemerná doba čakania je vysoká.
- Krátke procesy, ktoré sa nachádzajú v zadnej časti frontu, musia čakať na ukončenie dlhého procesu v prednej časti.
- Nie je to ideálna technika pre systémy zdieľania času.
- Pre svoju jednoduchosť nie je FCFS veľmi efektívny.
Zhrnutie:
- Definícia: FCFS je algoritmus plánovania operačného systému, ktorý automaticky vykonáva požiadavky a procesy vo fronte podľa poradia ich príchodu
- Podporuje nepreventívne a preventívne plánovanie
- algoritmus.
- FCFS je skratka slova First Come First Serve
- Reálnym príkladom metódy FCFS je zakúpenie lístka do kina na pulte lístka.
- Je to najjednoduchšia forma plánovacieho algoritmu CPU
- Jedná sa o nepreventívny plánovací algoritmus CPU, takže po pridelení procesu CPU nikdy procesor neuvoľní, kým nedokončí vykonávanie.