Hvad er den korteste planlægning af job?
Shortest Job First (SJF) er en algoritme, hvor processen med 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 for andre processer, der afventer udførelse, betydeligt. Den fulde form for SJF er kortest job først.
Der er grundlæggende to typer SJF-metoder:
- Ikke-forebyggende SJF
- Forebyggende SJF
I denne operativsystemvejledning lærer du:
- Hvad er den korteste planlægning af job?
- Karakteristika ved SJF-planlægning
- Ikke-forebyggende SJF
- Forebyggende SJF
- Fordele ved SJF
- Ulemper / ulemper ved SJF
Karakteristika ved SJF-planlægning
- Det er forbundet med hvert job som en tidsenhed, der skal gennemføres.
- Denne algoritmemetode er nyttig til batch-behandling, hvor det ikke er kritisk at vente på, at job er afsluttet.
- Det kan forbedre procesgennemstrømningen ved at sikre, at kortere job udføres først og dermed muligvis have en kort leveringstid.
- Det forbedrer joboutput ved at tilbyde kortere job, som skal udføres først, som for det meste har en kortere leveringstid.
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 følgende fem processer, der hver har sin egen unikke bursttid og ankomsttid.
| Processkø | Bursttid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Trin 0) På tidspunktet = 0 ankommer P4 og starter udførelsen.
Trin 1) På tidspunktet = 1 ankommer proces P3. Men P4 har stadig brug for 2 udførelsesenheder for at fuldføre. Det vil fortsætte udførelsen.
Trin 2) Ved tid = 2 ankommer proces P1 og føjes til ventekøen. P4 fortsætter udførelsen.
Trin 3) På tidspunktet = 3 afslutter proces P4 dens udførelse. Bursttiden for P3 og P1 sammenlignes. Process 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 fortsætter udførelsen.
Trin 5) På tidspunktet = 5 ankommer proces P2 og føjes til ventekøen. P1 fortsætter udførelsen.
Trin 6) Ved tid = 9 afslutter proces P1 dens udførelse. Bursttiden for P3, P5 og P2 sammenlignes. Process P2 udføres, fordi dens bursttid er den laveste.
Trin 7) På tidspunktet = 10 udfører P2, og P3 og P5 står i ventekøen.
Trin 8) På tidspunktet = 11 afslutter proces P2 dens udførelse. Bursttiden for P3 og P5 sammenlignes. Process P5 udføres, fordi dens bursttid er lavere.
Trin 9) På tidspunktet = 15 afslutter proces P5 sin udførelse.
Trin 10) På tidspunktet = 23 afslutter proces P3 sin udførelse.
Trin 11) Lad os beregne den gennemsnitlige ventetid for ovenstående eksempel.
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
Forebyggende SJF
I præemptiv SJF-planlægning placeres job i den klare kø, når de kommer. En proces med den korteste bursttid begynder udførelsen. Hvis en proces med endnu en kortere bursttid ankommer, fjernes den aktuelle proces eller forhindres i udførelse, og det kortere job tildeles CPU-cyklus.
Overvej følgende fem proces:
| Processkø | Bursttid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Trin 0) På tidspunktet = 0 ankommer P4 og starter udførelsen.
| Processkø | Bursttid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Trin 1) På tidspunktet = 1 ankommer proces P3. Men P4 har en kortere bursttid. Det vil fortsætte udførelsen.
Trin 2) Ved tid = 2 ankommer proces P1 med bursttid = 6. Bursttiden er mere end P4. Derfor fortsætter P4 udførelsen.
Trin 3) På tidspunktet = 3 afslutter proces P4 dens udførelse. Bursttiden for P3 og P1 sammenlignes. Process P1 udføres, fordi dens bursttid er lavere.
Trin 4) Ved tid = 4 ankommer proces P5. Bursttiden for P3, P5 og P1 sammenlignes. Process P5 udføres, fordi dens bursttid er lavest. Process P1 er forhindret.
| Processkø | Bursttid | 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. Process P2 udføres, fordi dens bursttid er mindst. Process P5 er forhindret.
| Processkø | Bursttid | 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ører P2.
Trin 7) På tidspunktet = 7 afslutter P2 sin udførelse. Bursttiden for P1, P3 og P5 sammenlignes. Process P5 udføres, fordi dens bursttid er kortere.
| Processkø | Bursttid | 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) På tidspunktet = 10 afslutter P5 sin udførelse. Bursttiden for P1 og P3 sammenlignes. Process P1 udføres, fordi dens bursttid er kortere.
Trin 9) På tidspunktet = 15 afslutter P1 sin udførelse. P3 er den eneste proces tilbage. Det starter udførelsen.
Trin 10) På tidspunktet = 23 afslutter P3 sin udførelse.
Trin 11) Lad os beregne den gennemsnitlige ventetid for ovenstående eksempel.
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
Fordele ved SJF
Her er fordelene / fordelene ved at bruge SJF-metoden:
- SJF bruges ofte til langsigtet planlægning.
- Det reducerer den gennemsnitlige ventetid over FIFO (First in First Out) algoritme.
- SJF-metoden giver den laveste gennemsnitlige ventetid for et specifikt sæt processer.
- Det er passende for de job, der kører i batch, hvor kørselstider er kendt på forhånd.
- For batchsystemet til langsigtet planlægning kan der opnås et estimat for burst-tid fra jobbeskrivelsen.
- For kortvarig planlægning er vi nødt til at forudsige værdien af den næste burst-tid.
- Sandsynligvis optimal med hensyn til gennemsnitlig leveringstid.
Ulemper / ulemper ved SJF
Her er nogle ulemper / ulemper ved SJF-algoritme:
- Afslutningstid for job skal være kendt tidligere, men det er svært at forudsige.
- Det bruges ofte i et batch-system til langsigtet planlægning.
- 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 den kommende CPU-burst.
- Denne algoritme kan forårsage meget lange behandlingstider eller sult.
- Kræver viden om, hvor længe en proces eller et job vil køre.
- Det fører til sult, der ikke reducerer den gennemsnitlige leveringstid.
- Det er svært at kende længden af den kommende CPU-anmodning.
- Forløbet tid skal registreres, hvilket resulterer i mere omkostninger på processoren.
Resumé
- SJF er en algoritme, hvor processen med den mindste udførelsestid vælges til den næste udførelse.
- SJF-planlægning er knyttet til hvert job som en tidsenhed, der skal gennemføres.
- Denne algoritmemetode er nyttig til batch-behandling, hvor det ikke er kritisk at vente på, at job er afsluttet.
- Der er grundlæggende to typer SJF-metoder 1) Ikke-præemptiv SJF og 2) Preemptive 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 præemptiv SJF-planlægning placeres job i den klare kø, når de kommer.
- Selvom en proces med kort bursttid begynder, fjernes den aktuelle proces eller forhindres i udførelse, og det kortere job udføres første.
- SJF bruges ofte til langsigtet planlægning.
- Det reducerer den gennemsnitlige ventetid over FIFO (First in First Out) algoritme.
- I SJF-planlægning skal jobafslutningstid være kendt 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 den kommende CPU-burst.