Korteste job først (SJF): Forebyggende, ikke-forebyggende eksempel

Hvad er Shortest Job First Scheduling?

Korteste job først (SJF) er en algoritme, hvor den proces, der har den mindste udførelsestid, vælges til den næste udførelse. Denne planlægningsmetode kan være forebyggende eller ikke-forebyggende. Det reducerer den gennemsnitlige ventetid markant for andre processer, der afventer eksekvering. Den fulde form for SJF er Shortest Job First.

Der er grundlæggende to typer SJF-metoder:

• Ikke-forebyggende SJF
• Forebyggende SJF

Karakteristika for SJF-planlægning

• Det er knyttet til hvert job som en tidsenhed, der skal udføres.
• Denne algoritmemetode er nyttig til batch-typebehandling, hvor det ikke er kritisk at vente på, at opgaver fuldføres.
• Det kan forbedre procesgennemstrømningen ved at sikre, at kortere job udføres først, og dermed muligvis have en kort ekspeditionstid.
• Det forbedrer joboutputtet ved at tilbyde kortere job, som bør udføres først, og som for det meste har en kortere ekspeditionstid.

Ikke-forebyggende SJF

I ikke-præemptiv planlægning, når CPU-cyklussen er allokeret til en proces, holder processen den, indtil den når en ventetilstand eller afsluttes.

Overvej de følgende fem processer, der hver har sin egen unikke burst-tid og ankomsttid.

Proceskø	Burst tid	Ankomsttid
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trin 0) Ved tidspunktet = 0 ankommer P4 og starter udførelsen.

Trin 1) Ved tidspunktet = 1 ankommer proces P3. Men P4 mangler stadig 2 udførelsesenheder for at blive fuldført. Den vil fortsætte udførelsen.

Trin 2) Ved tid = 2 ankommer proces P1 og føjes til ventekøen. P4 vil fortsætte med at udføre.

Trin 3) Ved tidspunkt = 3 vil proces P4 afslutte sin udførelse. Bursttiden for P3 og P1 sammenlignes. Proces P1 udføres, fordi dens bursttid er mindre sammenlignet med P3.

Trin 4) Ved tid = 4 ankommer proces P5 og føjes til ventekøen. P1 vil fortsætte med at udføre.

Trin 5) Ved tid = 5 ankommer proces P2 og føjes til ventekøen. P1 vil fortsætte med at udføre.

Trin 6) Ved tidspunktet = 9 vil proces P1 afslutte sin udførelse. Bursttiden for P3, P5 og P2 sammenlignes. Proces P2 udføres, fordi dens bursttid er den laveste.

Trin 7) Ved tidspunktet = 10 udfører P2 processen, og P3 og P5 står i ventekøen.

Trin 8) Ved tid = 11 vil proces P2 afslutte sin udførelse. Bursttiden for P3 og P5 sammenlignes. Proces P5 udføres, fordi dens bursttid er lavere.

Trin 9) Ved tid = 15 vil proces P5 afslutte sin udførelse.

Trin 10) Ved tid = 23 vil proces P3 afslutte sin udførelse.

Trin 11) Lad os beregne den gennemsnitlige ventetid for ovenstående eksempel.

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

Forebyggende SJF

I præemptiv SJF-planlægning sættes job i klarkøen, efterhånden som de kommer. En proces med den korteste bursttid begynder at udføres. Hvis en proces med en endnu kortere bursttid ankommer, fjernes eller forhindres den aktuelle proces i at udføres, og det kortere job tildeles en CPU-cyklus.

Overvej følgende fem processer:

Proceskø	Burst tid	Ankomsttid
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trin 0) Ved tidspunktet = 0 ankommer P4 og starter udførelsen.

Proceskø	Burst tid	Ankomsttid
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trin 1) Ved tidspunkt = 1 ankommer proces P3. Men P4 har en kortere burst-tid. Den vil fortsætte udførelsen.

Trin 2) Ved tidspunkt = 2 ankommer proces P1 med bursttid = 6. Bursttiden er mere end P4. Derfor vil P4 fortsætte eksekveringen.

Trin 3) Ved tid = 3 vil proces P4 afslutte sin udførelse. Bursttiden for P3 og P1 sammenlignes. Proces P1 udføres, fordi dens bursttid er lavere.

Trin 4) Ved tid = 4 ankommer proces P5. Bursttiden for P3, P5 og P1 sammenlignes. Proces P5 udføres, fordi dens bursttid er lavest. Proces P1 er foregrebet.

Proceskø	Burst tid	Ankomsttid
P1	5 ud af 6 er tilbage	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trin 5) Ved tidspunkt = 5 ankommer proces P2. Bursttiden for P1, P2, P3 og P5 sammenlignes. Proces P2 udføres, fordi dens bursttid er kortest. Proces P5 er forudgået.

Proceskø	Burst tid	Ankomsttid
P1	5 ud af 6 er tilbage	2
P2	2	5
P3	8	1
P4	3	0
P5	3 ud af 4 er tilbage	4

Trin 6) Ved tidspunktet = 6 udføres P2.

Trin 7) Ved tidspunktet = 7 afslutter P2 sin udførelse. Bursttiden for P1, P3 og P5 sammenlignes. Processen P5 udføres, fordi dens bursttid er kortere.

Proceskø	Burst tid	Ankomsttid
P1	5 ud af 6 er tilbage	2
P2	2	5
P3	8	1
P4	3	0
P5	3 ud af 4 er tilbage	4

Trin 8) Ved tidspunktet = 10 vil P5 afslutte sin udførelse. Bursttiden for P1 og P3 sammenlignes. Processen P1 udføres, fordi dens bursttid er kortere.

Trin 9) Ved tidspunktet = 15 afslutter P1 sin udførelse. P3 er den eneste proces, der er tilbage. Den vil starte udførelsen.

Trin 10) Ved tidspunktet = 23 afslutter P3 sin udførelse.

Trin 11) Lad os beregne den gennemsnitlige ventetid for ovenstående eksempel.

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

Fordele ved SJF

Her er fordelene/fordelene ved at bruge SJF-metoden:

• SJF bruges ofte til langsigtet planlægning.
• Det reducerer den gennemsnitlige ventetid i forhold til FIFO (First In First Out) algoritmen.
• SJF-metoden giver den laveste gennemsnitlige ventetid for et specifikt sæt af processer.
• Det er velegnet til de job, der kører i batch, hvor køretider er kendt på forhånd.
• For batchsystemet med langsigtet planlægning kan et estimat for eksplosionstid fås fra jobbeskrivelsen.
• For kortsigtet planlægning skal vi forudsige værdien af ​​den næste burst-tid.
• Det er sandsynligvis optimalt med hensyn til den gennemsnitlige ekspeditionstid.

Ulemper/ulemper ved SJF

Her er nogle ulemper/ulemper ved SJF-algoritmen:

• Jobafslutningstid skal kendes tidligere, men det er svært at forudsige.
• Det bruges ofte i et batchsystem til langsigtet planlægning.
• SJF kan ikke implementeres for CPU-planlægning på kort sigt. Det er fordi der ikke er nogen specifik metode til at forudsige længden af ​​det kommende CPU burst.
• Denne algoritme kan forårsage meget lange behandlingstider eller sult.
• Kræver viden om, hvor længe en proces eller opgave vil løbe.
• Det fører til sult, der ikke reducerer den gennemsnitlige behandlingstid.
• Det er svært at vide længden af ​​den kommende CPU-anmodning.
• Forløbet tid bør registreres, hvilket resulterer i mere overhead på processoren.

Ofte Stillede Spørgsmål