Kortaste jobb först (SJF): Förebyggande, icke-förebyggande exempel

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 möjligen ger en kort handläggningstid.
• Det förbättrar jobbutgången genom att erbjuda kortare jobb, som bör utföras först, och som oftast har en kortare handläggningstid.

Icke-förebyggande SJF

Vid icke-preemptiv schemaläggning, när CPU-cykeln har allokerats till en 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 bursttid 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 tidpunkten 0 anländer P4 och påbörjar exekveringen.

Steg 1) Vid tidpunkt 1 anländer process P3. Men P4 behöver fortfarande 2 exekveringsenheter för att slutföras. Den kommer att fortsätta exekveringen.

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 körs 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 exemplet ovan.

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 preemptiv SJF-schemaläggning placeras jobb i redokön allt eftersom de kommer. En process med den kortaste bursttiden börjar köras. Om en process med en ännu kortare bursttid anländer, tas den aktuella processen bort eller förhindras från körning, och det kortare jobbet tilldelas en CPU-cykel.

Betrakta 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 tidpunkten 0 anländer P4 och påbörjar exekveringen.

Processkö	Sprängtid	Ankomst tid
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Steg 1) Vid tidpunkt 1 anländer process P3. Men P4 har en kortare bursttid. Den kommer att fortsätta exekveringen.

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 tidpunkt = 5 anländer process P2. Bursttiden för P1, P2, P3 och P5 jämförs. Process P2 exekveras eftersom dess bursttid är kortast. Process P5 är preempted.

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 körs P2.

Steg 7) Vid tidpunkten 7 avslutar P2 sin exekvering. Bursttiden för P1, P3 och P5 jämförs. Process P5 exekveras eftersom dess bursttid ä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 tidpunkten 10 avslutar P5 sin exekvering. Bursttiden för P1 och P3 jämförs. Process P1 exekveras eftersom dess bursttid är kortare.

Steg 9) Vid tidpunkten 15 avslutar P1 sin exekvering. P3 är den enda processen som återstår. Den kommer att starta exekveringen.

Steg 10) Vid tidpunkten 23 avslutar P3 sin exekvering.

Steg 11) Låt oss beräkna den genomsnittliga väntetiden för exemplet ovan.

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 jämfört med FIFO-algoritmen (först in, först ut).
• 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.
• Det är förmodligen optimalt med tanke på 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ält 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 för processorn.

Vanliga frågor