FCFS schemaläggningsalgoritm: Vad är, exempelprogram
Nathaniel Brooks
⚡ Smart sammanfattning
Först till kvarn-schemaläggning kör processer i exakt den ordning de når klarkön, med hjälp av en enkel icke-förebyggande FIFO-metod som gör den till den enklaste CPU-schemaläggningsalgoritmen för ett operativsystem att implementera.
Vad är först till kvarn-metoden?
Först till kvarn gäller (FCFS) är en schemaläggningsalgoritm för operativsystem som automatiskt exekverar köade förfrågningar och processer i den ordning de anländer. Det är den enklaste och mest använda CPU-schemaläggningsalgoritmen. I den här typen av algoritm får den process som först begär CPU:n CPU-tilldelningen först. Detta hanteras med en FIFO-kö. Den fullständiga formen av FCFS är först till kvarn.
När en process går in i redo-kön länkas dess PCB (processkontrollblock) till köns slut. Så när processorn blir ledig tilldelas den processen i början av kön.
Egenskaper hos FCFS-metoden
De viktigaste egenskaperna hos metoden "först till kvarn" listas nedan:
- Det är ett icke-förebyggande schemaläggningsalgoritm, så en process behåller processorn tills den fullbordar sin burst-tid.
- Jobb utförs alltid enligt först till kvarn-principen.
- Det är lätt att implementera och använda.
- Denna metod har dålig prestanda och den allmänna väntetiden är ganska lång.
Exempel på FCFS-schemaläggning
Ett verkligt exempel på FCFS-metoden är att köpa en biobiljett vid biljettkassan. I denna schemaläggningsalgoritm serveras en person enligt köordningen. Den person som anländer först i kön köper biljetten först, och sedan nästa. Detta fortsätter tills den sista personen i kön köper biljetten. Med denna algoritm fungerar CPU-processen på ett liknande sätt.
Hur fungerar FCFS? Beräknar genomsnittlig väntetid
För att förstå hur algoritmen schemalägger processer, här är ett exempel på fem processer som anländer vid olika tidpunkter. Varje process har en annan burst-tid.
| Behandla | Sprängtid | Ankomst tid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Genom att använda FCFS-schemaläggningsalgoritmen hanteras dessa processer enligt följande.
Steg 1) Processen börjar med P4, som har ankomsttid 0.
Steg 2) Klockan=1 kommer P3. P4 körs fortfarande. Därför hålls P3 i en kö.
Steg 3) Vid tidpunkten = 2 anländer P1 och hålls kvar i kön.
Steg 4) Vid tidpunkten = 3 slutför P4-processen sin exekvering.
Steg 5) Vid tidpunkten=4 startar P3, som är först i kön, exekvering.
Steg 6) Vid tidpunkten = 5 anländer P2 och hålls kvar i en kö.
Steg 7) Vid tidpunkten = 11 slutför P3 sin exekvering.
Steg 8) Vid tidpunkten 11 börjar P1 exekveringen. Den har en bursttid på 6, så den slutför exekveringen vid tidsintervallet 17.
Steg 9) Vid tidpunkten = 17 börjar P5 köras. Den har en bursttid på 4, så den slutför körningen vid tidpunkten = 21.
Steg 10) Vid tidpunkten 21 börjar P2 exekveringen. Den har en bursttid på 2, så den slutför exekveringen vid tidsintervallet 23.
Steg 11) Låt oss nu beräkna den genomsnittliga väntetiden för exemplet ovan.
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
Genomsnittlig väntetid = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8
Fördelar med FCFS
Här är fördelarna och fördelarna med att använda FCFS-schemaläggningsalgoritmen:
- Det är den enklaste formen av en CPU-schemaläggningsalgoritm.
- Det är lätt att programmera.
- Den följer en tydlig ordning efter först till kvarn.
Nackdelar med FCFS
Här är nackdelarna och nackdelarna med att använda FCFS-schemaläggningsalgoritmen:
- Det är en icke-förebyggande CPU-schemaläggningsalgoritm, så när en process har allokerats till CPU:n kommer den aldrig att släppa processorn förrän den är klar med körningen.
- Den genomsnittliga väntetiden är hög.
- Korta processer längst bak i kön måste vänta på att den långa processen längst fram ska slutföras.
- Det är inte en idealisk teknik för tidsdelningssystem.
- På grund av sin enkelhet är FCFS inte särskilt effektivt.
