FCFS-planlægningsalgoritme: Hvad er, eksempelprogram
Nathaniel Brooks
⚡ Smart opsummering
Først til mølle, først tjene-planlægning kører processer i den nøjagtige rækkefølge, de når klarkøen, ved hjælp af en simpel ikke-præemptiv FIFO-tilgang, der gør den til den nemmeste CPU-planlægningsalgoritme for et operativsystem at implementere.
Hvad er først til mølle-metoden?
Først til mølle (FCFS) er en planlægningsalgoritme i et operativsystem, der automatisk udfører anmodninger og processer i kø i den rækkefølge, de ankommer. Det er den nemmeste og enkleste CPU-planlægningsalgoritme. I denne type algoritme får den proces, der anmoder om CPU'en først, CPU-allokeringen først. Dette styres med en FIFO-kø. Den fulde form af FCFS er først til mølle.
Når en proces går ind i klarkøen, forbindes dens PCB (proceskontrolblok) med køens ende. Så når CPU'en bliver ledig, tildeles den processen i starten af køen.
Karakteristika for FCFS-metoden
De vigtigste karakteristika ved "først til mølle"-metoden er anført nedenfor:
- Det er et ikke-præemptiv planlægningsalgoritme, så en proces holder CPU'en, indtil den fuldfører sin burst-tid.
- Opgaver udføres altid efter først-til-mølle-princippet.
- Det er nemt at implementere og bruge.
- Denne metode er dårlig i ydeevne, og den generelle ventetid er ret høj.
Eksempel på FCFS-planlægning
Et eksempel på FCFS-metoden fra det virkelige liv er ved at købe en biografbillet ved billetlugen. I denne planlægningsalgoritme bliver en person betjent i henhold til kørækkefølgen. Den person, der ankommer først i køen, køber billetten først, og derefter den næste. Dette fortsætter, indtil den sidste person i køen køber billetten. Ved hjælp af denne algoritme fungerer CPU-processen på en lignende måde.
Hvordan fungerer FCFS? Beregning af gennemsnitlig ventetid
For at forstå, hvordan algoritmen planlægger processer, er her et eksempel på fem processer, der ankommer på forskellige tidspunkter. Hver proces har en forskellig burst-tid.
| Proces | Burst tid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Ved at bruge FCFS-planlægningsalgoritmen håndteres disse processer som følger.
Trin 1) Processen begynder med P4, som har ankomsttid 0.
Trin 2) På tidspunktet=1 ankommer P3. P4 kører stadig. Derfor holdes P3 i en kø.
Trin 3) Ved tidspunktet = 2 ankommer P1 og holdes i køen.
Trin 4) Ved tidspunktet = 3 fuldfører P4-processen sin udførelse.
Trin 5) Ved time=4 starter P3, som er først i køen, eksekveringen.
Trin 6) Ved tidspunktet = 5 ankommer P2 og holdes i kø.
Trin 7) Ved tidspunktet = 11 fuldfører P3 sin udførelse.
Trin 8) Ved tid = 11 starter P1 udførelsen. Den har en burst-tid på 6, så den fuldfører udførelsen ved tidsinterval 17.
Trin 9) Ved tidspunktet = 17 starter P5 udførelsen. Den har en burst-tid på 4, så den fuldfører udførelsen ved tidspunktet = 21.
Trin 10) Ved tid = 21 starter P2 udførelsen. Den har en burst-tid på 2, så den fuldfører udførelsen ved tidsinterval 23.
Trin 11) Lad os nu beregne den gennemsnitlige ventetid for ovenstående eksempel.
Waiting time = Start time - Arrival time
P4 = 0 – 0 = 0
P3 = 3 – 1 = 2
P1 = 11 – 2 = 9
P5 = 17 – 4 = 13
P2 = 21 – 5 = 16
Gennemsnitlig ventetid = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8
Fordele ved FCFS
Her er fordelene og ulemperne ved at bruge FCFS-planlægningsalgoritmen:
- Det er den enkleste form for en CPU-planlægningsalgoritme.
- Det er nemt at programmere.
- Det følger en simpel først til mølle-rækkefølge.
Ulemper ved FCFS
Her er ulemperne og ulemperne ved at bruge FCFS-planlægningsalgoritmen:
- Det er en ikke-præemptiv CPU-planlægningsalgoritme, så når en proces er blevet allokeret til CPU'en, frigiver den aldrig CPU'en, før den er færdig med at udføre.
- Den gennemsnitlige ventetid er høj.
- Korte processer bagerst i køen skal vente på, at den lange proces forrest afsluttes.
- Det er ikke en ideel teknik til tidsdelingssystemer.
- På grund af sin enkelhed er FCFS ikke særlig effektiv.
