FCFS plánovací algoritmus: Co je, příklad programu

Co je metoda kdo dřív přijde, je dřív na řadě?

Kdo dřív přijde, ten dřív mele (FCFS) je plánovací algoritmus operačního systému, který automaticky provádí požadavky a procesy ve frontě v pořadí jejich příchodu. Je to nejjednodušší a nejjednodušší plánovací algoritmus CPU. V tomto typu algoritmu dostanou nejprve přidělení CPU procesy, které požadují CPU jako první. To je spravováno pomocí fronty FIFO. Plná forma FCFS je kdo dřív přijde, ten dřív mele.

Jakmile proces vstoupí do fronty připravenosti, jeho PCB (Process Control Block) je propojen s koncem fronty, a když se CPU uvolní, měl by být přiřazen k procesu na začátku fronty.

Charakteristika metody FCFS

Podporuje nepreemptivní a preemptivní plánovací algoritmus.
Úkoly jsou vždy prováděny podle zásady „kdo dřív přijde, je dřív na řadě“.
Snadno se implementuje a používá.
Tato metoda má nízký výkon a obecná čekací doba je poměrně vysoká.

Příklad plánování FCFS

Skutečným příkladem metody FCFS je nákup lístku do kina na pokladně. V tomto plánovacím algoritmu je osoba obsluhována způsobem fronty. Ten, kdo přijde jako první do fronty, si nejprve koupí lístek a až poté další. Toto bude pokračovat, dokud si lístek nekoupí poslední osoba ve frontě. Pomocí tohoto algoritmu funguje proces CPU podobným způsobem.

Jak FCFS funguje? 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 prasknutí.

Proces	Čas prasknutí	Čas příjezdu
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Pomocí plánovacího algoritmu FCFS jsou tyto procesy řešeny následovně.

Krok 1) Proces začíná P4, který má čas příjezdu 0

Krok 2) V čase=1 přichází P3. P4 stále probíhá. P3 je tedy držen ve frontě.

Proces	Čas prasknutí	Čas příjezdu
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Krok 3) V čase = 2 přichází P1, který je držen ve frontě.

Proces	Čas prasknutí	Čas příjezdu
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Krok 4) V čase=3 proces P4 dokončí své provádění.

Krok 5) V čase=4 zahájí provádění P3, který je první ve frontě.

Proces	Čas prasknutí	Čas příjezdu
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Krok 6) V čase =5 dorazí P2 a je držen ve frontě.

Proces	Čas prasknutí	Čas příjezdu
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Krok 7) V čase 11 dokončí P3 své provádění.

Krok 8) V čase=11 zahájí provádění P1. Má dobu shluku 6. Spuštění dokončí v časovém intervalu 17

Krok 9) V čase=17 zahájí P5 provádění. Má dobu shluku 4. Spuštění dokončí v čase=21

Krok 10) V čase=21 zahájí provádění P2. Má dobu shluku 2. Spuštění dokončí v časovém intervalu 23

Krok 11) Vypočítejme průměrnou dobu čekání 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žití plánovacího algoritmu FCFS:

Nejjednodušší forma a CPU plánovací algoritmus
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:

Je to nepreemptivní plánovací algoritmus CPU, takže poté, co byl proces přidělen CPU, nikdy neuvolní 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.
Kvůli své jednoduchosti není FCFS příliš efektivní.

Shrnutí

Definice: FCFS je plánovací algoritmus operačního systému, který automaticky provádí požadavky a procesy ve frontě podle pořadí jejich příchodu.
Podporuje nepreemptivní a preemptivní plánování
algoritmus.
FCFS je zkratka pro First Come First Serve
Skutečným příkladem metody FCFS je nákup lístku do kina na pokladně.
Je to nejjednodušší forma plánovacího algoritmu CPU
Je to nepreemptivní plánovací algoritmus CPU, takže poté, co byl proces přidělen CPU, nikdy neuvolní CPU, dokud nedokončí provádění.