Co je metoda „kdo dřív přijde?“
FCFS (First Come First Serve) je plánovací algoritmus operačního systému, který automaticky spouští žádosti a procesy ve frontě v pořadí podle jejich příchodu. Je to nejjednodušší a nejjednodušší algoritmus plánování CPU. V tomto typu algoritmu získávají procesy, které nejprve vyžadují CPU, nejprve přidělení CPU. To je spravováno pomocí fronty FIFO. Plná forma FCFS je First Come First Serve.
Když proces vstupuje do připravené fronty, její PCB (Process Control Block) je spojen s ocasem fronty a když se CPU uvolní, měl by být přiřazen procesu na začátku fronty.
V tomto kurzu operačního systému se naučíte:
- Co je metoda „kdo dřív přijde?“
- Charakteristika metody FCFS
- Příklad plánování FCFS
- Jak funguje FCFS? Výpočet průměrné čekací doby
- Výhody FCFS
- Nevýhody FCFS
Charakteristika metody FCFS
- Podporuje preventivní a preventivní plánovací algoritmus.
- Úlohy se vždy provádějí podle zásady „kdo dřív přijde, je dřív na řadě“.
- Je snadné jej implementovat a používat.
- Tato metoda má špatný výkon a obecná čekací doba je poměrně vysoká.
Příklad plánování FCFS
Reálným příkladem metody FCFS je nákup lístku do kina na přepážce lístků. V tomto plánovacím algoritmu je osobě obsluhováno způsobem fronty. Osoba, která dorazí jako první ve frontě, si nejprve zakoupí lístek a poté další. To bude pokračovat, dokud si lístek nezakoupí poslední osoba ve frontě. Pomocí tohoto algoritmu proces CPU pracuje podobným způsobem.
Jak funguje FCFS? Výpočet průměrné čekací doby
Zde je příklad pěti procesů přicházejících v různých časech. Každý proces má jinou dobu roztržení.
| Proces | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Pomocí plánovacího algoritmu FCFS jsou tyto procesy zpracovány následujícím způsobem.
Krok 0) Proces začíná P4, který má čas příjezdu 0
Krok 1) V čase = 1 dorazí P3. P4 stále probíhá. Proto je P3 veden ve frontě.
| Proces | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 2) V čase = 2 dorazí P1, který je udržován ve frontě.
| Proces | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 3) V čase = 3 proces P4 dokončí své provedení.
Krok 4) V čase = 4 zahájí provádění P3, který je ve frontě první.
| Proces | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 5) V čase = 5 dorazí P2 a je udržován ve frontě.
| Proces | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 6) V čase 11 P3 dokončí své provedení.
Krok 7) V čase = 11, P1 zahájí provádění. Má čas shluku 6. Dokončí provedení v časovém intervalu 17
Krok 8) V čase = 17 zahájí P5 provádění. Má čas shluku 4. Dokončí provádění v čase = 21
Krok 9) V čase = 21 začne P2 provádění. Má čas shluku 2. Dokončí provedení v časovém intervalu 23
Krok 10) Vypočítáme průměrnou čekací dobu pro výše uvedený pří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
Průměrná čekací doba
= 40/5 = 8
Výhody FCFS
Zde jsou výhody / výhody používání plánovacího algoritmu FCFS:
- Nejjednodušší forma plánovacího algoritmu CPU
- Snadné programování
- Kdo dřív přijde, ten dřív mele
Nevýhody FCFS
Zde jsou nevýhody / nevýhody použití plánovacího algoritmu FCFS:
- Jedná se o nepreventivní plánovací algoritmus CPU, takže po přidělení procesu CPU nikdy nevydá CPU, dokud nedokončí provádění.
- Průměrná čekací doba je vysoká.
- Krátké procesy, které jsou v zadní části fronty, musí čekat na dokončení dlouhého procesu v přední části.
- Není to ideální technika pro systémy sdílení času.
- Díky své jednoduchosti není FCFS příliš efektivní.
Souhrn:
- Definice: FCFS je algoritmus plánování operačního systému, který automaticky spouští žádosti a procesy ve frontě podle pořadí jejich příchodu
- Podporuje nepreventivní a preventivní plánování
- algoritmus.
- FCFS znamená First Come First Serve
- Reálným příkladem metody FCFS je nákup lístku do kina na přepážce lístků.
- Je to nejjednodušší forma plánovacího algoritmu CPU
- Jedná se o nepreventivní plánovací algoritmus CPU, takže po přidělení procesu CPU nikdy nevydá CPU, dokud nedokončí provádění.