Korteste job først (SJF): Forebyggende, ikke-forebyggende eksempel
Nathaniel Brooks
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 joboutput ved at tilbyde kortere job, som skal udføres først, som for det meste har en kortere ekspeditionstid.
Ikke-forebyggende SJF
I ikke-forebyggende planlægning, når CPU-cyklussen er allokeret til behandling, 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 tid=0 ankommer P4 og starter udførelse.
Trin 1) Ved tidspunkt = 1 ankommer proces P3. Men P4 mangler stadig 2 udførelsesenheder for at fuldføre. Det vil fortsætte udførelsen.
Trin 2) På tidspunktet =2 ankommer proces P1 og føjes til ventekøen. P4 fortsætter eksekveringen.
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) På tidspunktet=10 udføres P2, og P3 og P5 er 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 Preemptive SJF Scheduling sættes job i klarkøen, efterhånden som de kommer. En proces med korteste bursttid begynder at udføre. Hvis en proces med endnu en kortere burst-tid ankommer, fjernes eller forhindres den aktuelle proces fra udførelse, og det kortere job tildeles 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 tid=0 ankommer P4 og starter udførelse.
| 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 bursttid. Det 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 tid = 5 ankommer proces P2. Bursttiden for P1, P2, P3 og P5 sammenlignes. Proces P2 udføres, fordi dens bursttid er mindst. Proces P5 er foregrebet.
| 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) På tidspunktet =6 udføres P2.
Trin 7) Til tiden =7 afslutter P2 sin udførelse. Bursttiden for P1, P3 og P5 sammenlignes. Proces 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 tiden =10 vil P5 afslutte sin udførelse. Bursttiden for P1 og P3 sammenlignes. Proces P1 udføres, fordi dens bursttid er kortere.
Trin 9) Ved tiden =15 afslutter P1 sin udførelse. P3 er den eneste proces tilbage. Det vil begynde at udføre.
Trin 10) Til tiden =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/fordele ved at bruge SJF-metoden:
- SJF bruges ofte til langsigtet planlægning.
- Det reducerer den gennemsnitlige ventetid over FIFO-algoritmen (First in First Out).
- SJF-metoden giver den laveste gennemsnitlige ventetid for et bestemt 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.
- Formentlig optimalt med hensyn til gennemsnitlig 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 sulten, der ikke reducerer den gennemsnitlige ekspeditionstid.
- 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.
Resumé
- SJF er en algoritme, hvor den proces, der har den mindste eksekveringstid, vælges til næste eksekvering.
- SJF Scheduling er knyttet til hvert job som en tidsenhed, der skal fuldføres.
- Denne algoritmemetode er nyttig til batch-typebehandling, hvor det ikke er kritisk at vente på, at opgaver fuldføres.
- Der er grundlæggende to typer SJF-metoder 1) Ikke-præemptiv SJF og 2) Præemptiv SJF.
- I ikke-forebyggende planlægning, når CPU-cyklussen er allokeret til behandling, holder processen den, indtil den når en ventetilstand eller afsluttes.
- I Preemptive SJF Scheduling sættes job i klarkøen, efterhånden som de kommer.
- Selvom en proces med kort burst-tid begynder, fjernes eller forhindres den aktuelle proces fra udførelse, og jobbet, der er kortere, udføres første gang.
- SJF bruges ofte til langsigtet planlægning.
- Det reducerer den gennemsnitlige ventetid over FIFO-algoritmen (First in First Out).
- I SJF-planlægning skal jobafslutningstiden kendes tidligere, men det er svært at forudsige.
- SJF kan ikke implementeres til 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.
