Vad är den kortaste schemaläggningen för första jobbet?
Shortest Job First (SJF) är en algoritm där processen med den minsta exekveringstiden väljs för nästa körning. Denna schemaläggningsmetod kan vara förebyggande eller icke förebyggande. Det minskar avsevärt den genomsnittliga väntetiden för andra processer som väntar på körning. Den fullständiga formen av SJF är Shortest Job First.
Det finns i princip två typer av SJF-metoder:
- Icke-förebyggande SJF
- Förebyggande SJF
I denna handledning för operativsystem lär du dig:
- Vad är den kortaste schemaläggningen för första jobbet?
- Egenskaper för SJF Scheduling
- Icke-förebyggande SJF
- Förebyggande SJF
- Fördelar med SJF
- Nackdelar / nackdelar med SJF
Egenskaper för SJF Scheduling
- Det är associerat med varje jobb som en tidsenhet att slutföra.
- Den här algoritmmetoden är användbar för batch-bearbetning, där det inte är viktigt att vänta på att jobb ska slutföras.
- Det kan förbättra processgenomströmningen genom att se till att kortare jobb utförs först och därmed möjligen ha en kort behandlingstid.
- Det förbättrar jobbutdata genom att erbjuda kortare jobb, som bör utföras först, vilket oftast har en kortare behandlingstid.
Icke-förebyggande SJF
I icke-förebyggande schemaläggning, när CPU-cykeln har allokerats för att bearbeta, håller processen den tills den når ett vänteläge eller avslutas.
Tänk på följande fem processer som alla har sin egen unika bursttid och ankomsttid.
| Processkö | Bursttid | Ankomst tid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 0) Vid tid = 0 anländer P4 och startar körningen.
Steg 1) Vid tid = 1 anländer process P3. Men P4 behöver fortfarande två exekveringsenheter för att slutföra. Det kommer att fortsätta körningen.
Steg 2) Vid tid = 2 anländer process P1 och läggs till i väntekön. P4 fortsätter körningen.
Steg 3) Vid tid = 3 kommer processen P4 att slutföra körningen. Bursttiden för P3 och P1 jämförs. Process P1 körs eftersom dess burst-tid är mindre jämfört med P3.
Steg 4) Vid tid = 4 anländer process P5 och läggs till i väntekön. P1 fortsätter körningen.
Steg 5) Vid tid = 5 anländer process P2 och läggs till i väntekön. P1 fortsätter körningen.
Steg 6) Vid tid = 9 kommer processen P1 att slutföra körningen. Bursttiden för P3, P5 och P2 jämförs. Process P2 körs eftersom dess burst-tid är den lägsta.
Steg 7) Vid tid = 10 kör P2 och P3 och P5 står i väntekön.
Steg 8) Vid tid = 11 kommer processen P2 att slutföra körningen. Bursttiden för P3 och P5 jämförs. Process P5 körs eftersom dess burst-tid är lägre.
Steg 9) Vid tid = 15 kommer processen P5 att slutföra körningen.
Steg 10) Vid tid = 23 kommer processen P3 att slutföra körningen.
Steg 11) Låt oss beräkna den genomsnittliga väntetiden för ovanstående exempel.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Förebyggande SJF
I Preemptive SJF Scheduling placeras jobb i den färdiga kön när de kommer. En process med kortast bursttid börjar körning. Om en process med ännu kortare bursttid anländer tas den aktuella processen bort eller förhindras från körning och det kortare jobbet tilldelas CPU-cykel.
Tänk på följande fem processer:
| Processkö | Bursttid | Ankomst tid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 0) Vid tid = 0 anländer P4 och startar körningen.
| Processkö | Bursttid | Ankomst tid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 1) Vid tid = 1 anländer process P3. Men P4 har en kortare bursttid. Det kommer att fortsätta körningen.
Steg 2) Vid tid = 2 anländer process P1 med bursttid = 6. Bursttiden är mer än P4. Därför fortsätter P4 körningen.
Steg 3) Vid tid = 3 kommer processen P4 att slutföra körningen. Bursttiden för P3 och P1 jämförs. Process P1 körs eftersom dess burst-tid är lägre.
Steg 4) Vid tid = 4 kommer process P5 fram. Bursttiden för P3, P5 och P1 jämförs. Process P5 körs eftersom dess bursttid är lägst. Process P1 är förhindrad.
| Processkö | Bursttid | Ankomst tid |
| P1 | 5 av 6 återstår | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 5) Vid tid = 5 kommer process P2 att anlända. Bursttiden för P1, P2, P3 och P5 jämförs. Process P2 körs eftersom dess burst-tid är minst. Process P5 är förhindrad.
| Processkö | Bursttid | Ankomst tid |
| P1 | 5 av 6 återstår | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 av 4 återstår | 4 |
Steg 6) Vid tid = 6 kör P2.
Steg 7) Vid tid = 7 avslutar P2 körningen. Bursttiden för P1, P3 och P5 jämförs. Process P5 körs eftersom dess burst-tid är mindre.
| Processkö | Bursttid | Ankomst tid |
| P1 | 5 av 6 återstår | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 av 4 återstår | 4 |
Steg 8) Vid tid = 10 kommer P5 att slutföra körningen. Bursttiden för P1 och P3 jämförs. Process P1 körs eftersom dess burst-tid är kortare.
Steg 9) Vid tid = 15 avslutar P1 körningen. P3 är den enda processen kvar. Det kommer att starta körningen.
Steg 10) Vid tid = 23 avslutar P3 körningen.
Steg 11) Låt oss beräkna den genomsnittliga väntetiden för ovanstående exempel.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Fördelar med SJF
Här är fördelarna / fördelarna med att använda SJF-metoden:
- SJF används ofta för långtidsplanering.
- Det minskar den genomsnittliga väntetiden över algoritmen FIFO (First in First Out).
- SJF-metoden ger den lägsta genomsnittliga väntetiden för en viss uppsättning processer.
- Det är lämpligt för jobb som körs i batch, där körtider är kända i förväg.
- För batch-systemet för långsiktig schemaläggning kan en burst-uppskattning erhållas från jobbet.
- För korttidsplanering måste vi förutsäga värdet på nästa bursttid.
- Förmodligen optimalt med avseende på genomsnittlig vändtid.
Nackdelar / nackdelar med SJF
Här är några nackdelar / nackdelar med SJF-algoritmen:
- Tid för slutförande av jobb måste vara känd tidigare, men det är svårt att förutsäga.
- Det används ofta i ett batchsystem för långsiktig schemaläggning.
- SJF kan inte implementeras för CPU-schemaläggning på kort sikt. Det beror på att det inte finns någon specifik metod för att förutsäga längden på den kommande CPU-burst.
- Denna algoritm kan orsaka mycket långa behandlingstider eller svält.
- Kräver kunskap om hur länge en process eller ett jobb kommer att köras.
- Det leder till svält som inte minskar genomsnittlig vändtid.
- Det är svårt att veta längden på den kommande CPU-begäran.
- Förfluten tid bör registreras, vilket resulterar i mer omkostnader på processorn.
Sammanfattning
- SJF är en algoritm där processen med den minsta exekveringstiden väljs för nästa körning.
- SJF-schemaläggning är kopplad till varje jobb som en tidsenhet att slutföra.
- Den här algoritmmetoden är användbar för batch-bearbetning, där det inte är viktigt att vänta på att jobb ska slutföras.
- Det finns i princip två typer av SJF-metoder 1) Icke-förebyggande SJF och 2) Förebyggande SJF.
- I icke-förebyggande schemaläggning, när CPU-cykeln har allokerats för att bearbeta, håller processen den tills den når ett vänteläge eller avslutas.
- I Preemptive SJF Scheduling placeras jobb i den färdiga kön när de kommer.
- Även om en process med kort bursttid börjar, tas den aktuella processen bort eller förhindras från körning och jobbet som är kortare utförs första.
- SJF används ofta för långtidsplanering.
- Det minskar den genomsnittliga väntetiden över algoritmen FIFO (First in First Out).
- I SJF-schemaläggning måste jobbet vara klart tidigare, men det är svårt att förutsäga.
- SJF kan inte implementeras för CPU-schemaläggning på kort sikt. Det beror på att det inte finns någon specifik metod för att förutsäga längden på den kommande CPU-burst.