Kortaste jobb först (SJF): Förebyggande, icke-förebyggande exempel
Nathaniel Brooks
Vad är Shortest Job First Scheduling?
Kortaste jobbet först (SJF) är en algoritm där den process som har den minsta exekveringstiden väljs för nästa exekvering. 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å exekvering. 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
Egenskaper för SJF Schemaläggning
- Det är kopplat till varje jobb som en tidsenhet att slutföra.
- Denna algoritmmetod är användbar för bearbetning av batch-typ, där det inte är avgörande 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, vilket kan ha en kort handläggningstid.
- Det förbättrar arbetsresultatet genom att erbjuda kortare jobb, som bör utföras först, som oftast har en kortare handläggningstid.
Icke-förebyggande SJF
I icke-förebyggande schemaläggning, när CPU-cykeln är allokerad till process, håller processen den tills den når ett vänteläge eller avslutas.
Betrakta följande fem processer som var och en har sin egen unika skurtid och ankomsttid.
| Processkö | Sprängtid | Ankomst tid |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 0) Vid tid = 0 kommer P4 och startar exekvering.
Steg 1) Vid tidpunkten = 1 anländer Process P3. Men P4 behöver fortfarande 2 exekveringsenheter att slutföra. Det kommer att fortsätta att utföras.
Steg 2) Vid tidpunkten =2 anländer process P1 och läggs till i väntekön. P4 kommer att fortsätta köra.
Steg 3) Vid tidpunkten = 3 kommer process P4 att avsluta sin exekvering. Bursttiden för P3 och P1 jämförs. Process P1 exekveras eftersom dess skurtid är kortare jämfört med P3.
Steg 4) Vid tidpunkten = 4 anländer process P5 och läggs till i väntekön. P1 kommer att fortsätta köra.
Steg 5) Vid tidpunkten = 5 anländer process P2 och läggs till i väntekön. P1 kommer att fortsätta köra.
Steg 6) Vid tidpunkten = 9 kommer process P1 att avsluta sin exekvering. Bursttiden för P3, P5 och P2 jämförs. Process P2 exekveras eftersom dess skurtid är den lägsta.
Steg 7) Vid tidpunkten=10 exekveras P2 och P3 och P5 står i väntekön.
Steg 8) Vid tidpunkten = 11 kommer process P2 att avsluta sin exekvering. Bursttiden för P3 och P5 jämförs. Process P5 exekveras eftersom dess skurtid är lägre.
Steg 9) Vid tidpunkten = 15 kommer process P5 att avsluta sin exekvering.
Steg 10) Vid tidpunkten = 23 kommer process P3 att avsluta sin exekvering.
Steg 11) Låt oss beräkna den genomsnittliga väntetiden för ovanstående exempel.
Wait time P4= 0-0=0 P1= 3-2=1 P2= 9-5=4 P5= 11-4=7 P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Förebyggande SJF
I Preemptive SJF Scheduling läggs jobb i färdigkön när de kommer. En process med kortast skurtid börjar köras. Om en process med ännu kortare skurtid anländer, tas den aktuella processen bort eller förhindras från exekvering, och det kortare jobbet tilldelas CPU-cykel.
Tänk på följande fem processer:
| Processkö | Sprängtid | Ankomst tid |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 0) Vid tid = 0 kommer P4 och startar exekvering.
| Processkö | Sprängtid | Ankomst tid |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 1) Vid tidpunkten = 1 anländer Process P3. Men, P4 har en kortare sprängtid. Det kommer att fortsätta att utföras.
Steg 2) Vid tidpunkt = 2 anländer process Pl med skurtid = 1. Skurtiden är mer än P6. Därför kommer P4 att fortsätta körningen.
Steg 3) Vid tidpunkten = 3 kommer process P4 att avsluta sin exekvering. Bursttiden för P3 och P1 jämförs. Process P1 exekveras eftersom dess skurtid är lägre.
Steg 4) Vid tidpunkten = 4 kommer process P5 att anlända. Bursttiden för P3, P5 och P1 jämförs. Process P5 exekveras eftersom dess skurtid är lägst. Process P1 är förebyggd.
| Processkö | Sprängtid | Ankomst tid |
|---|---|---|
| P1 | 5 av 6 är kvar | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Steg 5) Vid tidpunkten = 5 kommer process P2 att anlända. Bursttiden för P1, P2, P3 och P5 jämförs. Process P2 exekveras eftersom dess skurtid är minst. Process P5 är förebyggd.
| Processkö | Sprängtid | Ankomst tid |
|---|---|---|
| P1 | 5 av 6 är kvar | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 av 4 är kvar | 4 |
Steg 6) Vid tidpunkten =6 exekveras P2.
Steg 7) Vid tiden =7 avslutar P2 sin exekvering. Bursttiden för P1, P3 och P5 jämförs. Process P5 exekveras eftersom dess skurtid är kortare.
| Processkö | Sprängtid | Ankomst tid |
|---|---|---|
| P1 | 5 av 6 är kvar | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 av 4 är kvar | 4 |
Steg 8) Vid tiden =10 kommer P5 att avsluta sin exekvering. Bursttiden för P1 och P3 jämförs. Process P1 exekveras eftersom dess skurtid är kortare.
Steg 9) Vid tiden =15 avslutar P1 sin exekvering. P3 är den enda processen kvar. Det kommer att börja köras.
Steg 10) Vid tiden =23 avslutar P3 sin exekvering.
Steg 11) Låt oss beräkna den genomsnittliga väntetiden för ovanstående exempel.
Wait time P4= 0-0=0 P1= (3-2) + 6 =7 P2= 5-5 = 0 P5= 4-4+2 =2 P3= 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ångsiktig schemaläggning.
- Det minskar den genomsnittliga väntetiden över FIFO-algoritmen (First in First Out).
- SJF-metoden ger den lägsta genomsnittliga väntetiden för en specifik uppsättning processer.
- Det är lämpligt för de jobb som körs i batch, där körtiderna är kända i förväg.
- För batchsystemet för långsiktig schemaläggning kan en sprängtidsuppskattning erhållas från arbetsbeskrivningen.
- För kortsiktig schemaläggning måste vi förutsäga värdet av nästa skurtid.
- Förmodligen optimalt med hänsyn till genomsnittlig handläggningstid.
Nackdelar/nackdelar med SJF
Här är några nackdelar/nackdelar med SJF-algoritmen:
- Tiden för slutförande av jobb måste vara känd tidigare, men det är svårt att förutse.
- 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-skuren.
- Denna algoritm kan orsaka mycket långa handläggningstider eller svält.
- Kräver kunskap om hur länge en process eller ett jobb kommer att pågå.
- Det leder till svälten som inte minskar den genomsnittliga handläggningstiden.
- Det är svårt att veta längden på den kommande CPU-förfrågan.
- Förfluten tid bör registreras, vilket resulterar i mer overhead på processorn.
Sammanfattning
- SJF är en algoritm där den process som har den minsta exekveringstiden väljs för nästa exekvering.
- SJF Schemaläggning är kopplat till varje jobb som en tidsenhet att slutföra.
- Denna algoritmmetod är användbar för bearbetning av batch-typ, där det inte är avgörande 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 är allokerad till process, håller processen den tills den når ett vänteläge eller avslutas.
- I Preemptive SJF Scheduling läggs jobb i färdigkön när de kommer.
- Även om en process med kort skurtid börjar, tas den aktuella processen bort eller förhindras från exekvering, och jobbet som är kortare exekveras först.
- SJF används ofta för långsiktig schemaläggning.
- Det minskar den genomsnittliga väntetiden över FIFO-algoritmen (First in First Out).
- I SJF-schemaläggning måste slutförandetiden för jobb vara känd tidigare, men det är svårt att förutse.
- 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-skuren.
