FCFS-planleggingsalgoritme: Hva er, eksempelprogram
Nathaniel Brooks
⚡ Smart oppsummering
Først til mølla-planlegging kjører prosesser i den nøyaktige rekkefølgen de når klarkøen, ved hjelp av en enkel ikke-preemptiv FIFO-tilnærming som gjør den til den enkleste CPU-planleggingsalgoritmen for et operativsystem å implementere.
Hva er førstemann til mølla-metoden?
Førstemann til mølla (FCFS) er en planleggingsalgoritme for operativsystemer som automatisk utfører forespørsler og prosesser i kø i den rekkefølgen de ankommer. Det er den enkleste og enkleste CPU-planleggingsalgoritmen. I denne typen algoritme får prosessen som først ber om CPU-en CPU-tildelingen først. Dette håndteres med en FIFO-kø. Den fulle formen for FCFS er først til mølla.
Når en prosess går inn i klarkøen, kobles dens PCB (prosesskontrollblokk) til den ene siden av køen. Så når CPU-en blir ledig, tilordnes den prosessen i begynnelsen av køen.
Kjennetegn ved FCFS-metoden
De viktigste egenskapene til «førstemann til mølla»-metoden er listet opp nedenfor:
- Det er en ikke-preemptiv planleggingsalgoritme, slik at en prosess beholder CPU-en til den fullfører burst-tiden.
- Jobbene utføres alltid etter førstemann-til-mølla-prinsippet.
- Det er enkelt å implementere og bruke.
- Denne metoden har dårlig ytelse, og den generelle ventetiden er ganske høy.
Eksempel på FCFS-planlegging
Et eksempel på FCFS-metoden fra virkeligheten er å kjøpe en kinobillett i billettluken. I denne planleggingsalgoritmen blir en person betjent i henhold til kørekkefølgen. Personen som kommer først i køen kjøper billetten først, og deretter den neste. Dette fortsetter til den siste personen i køen kjøper billetten. Ved å bruke denne algoritmen fungerer CPU-prosessen på en lignende måte.
Hvordan fungerer FCFS? Beregner gjennomsnittlig ventetid
For å forstå hvordan algoritmen planlegger prosesser, er her et eksempel på fem prosesser som ankommer til forskjellige tidspunkter. Hver prosess har en ulik burst-tid.
| Prosess | Sprengtid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Ved å bruke FCFS-planleggingsalgoritmen håndteres disse prosessene som følger.
Trinn 1) Prosessen begynner med P4, som har ankomsttid 0.
Trinn 2) Ved tid=1 kommer P3. P4 kjører fortsatt. Derfor holdes P3 i en kø.
Trinn 3) Ved tid = 2 ankommer P1 og blir holdt i køen.
Trinn 4) Ved tid=3 fullfører P4-prosessen utførelsen.
Trinn 5) Ved tid=4 starter P3, som er først i køen, kjøringen.
Trinn 6) Ved tid = 5 ankommer P2 og blir holdt i kø.
Trinn 7) Ved tid=11 fullfører P3 utførelsen.
Trinn 8) Ved tid = 11 starter P1 utførelsen. Den har en burst-tid på 6, så den fullfører utførelsen ved tidsintervall 17.
Trinn 9) Ved tid = 17 starter P5 utførelsen. Den har en burst-tid på 4, så den fullfører utførelsen ved tid = 21.
Trinn 10) Ved tid = 21 starter P2 utførelsen. Den har en burst-tid på 2, så den fullfører utførelsen ved tidsintervall 23.
Trinn 11) La oss nå beregne den gjennomsnittlige ventetiden for eksemplet ovenfor.
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
Gjennomsnittlig ventetid = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8
Fordeler med FCFS
Her er fordelene og fordelene ved å bruke FCFS-planleggingsalgoritmen:
- Det er den enkleste formen for en CPU-planleggingsalgoritme.
- Det er enkelt å programmere.
- Den følger en enkel «førstemann til mølla»-rekkefølge.
Ulemper med FCFS
Her er ulempene og ulempene ved å bruke FCFS-planleggingsalgoritmen:
- Det er en ikke-preemptiv CPU-planleggingsalgoritme, så når en prosess har blitt tildelt CPU-en, vil den aldri frigjøre CPU-en før den er ferdig med å kjøre.
- Den gjennomsnittlige ventetiden er høy.
- Korte prosesser bakerst i køen må vente til den lange prosessen foran er ferdig.
- Det er ikke en ideell teknikk for tidsdelingssystemer.
- På grunn av sin enkelhet er ikke FCFS veldig effektiv.
