Hva er den første timeplanlegging?
Shortest Job First (SJF) er en algoritme der prosessen som har den minste utførelsestiden velges for neste utførelse. Denne planleggingsmetoden kan være forebyggende eller ikke forebyggende. Det reduserer gjennomsnittlig ventetid for andre prosesser som venter på utførelse. Den fulle formen for SJF er Shortest Job First.
Det er i utgangspunktet to typer SJF-metoder:
- Ikke-forebyggende SJF
- Forebyggende SJF
I denne opplæringen om operativsystem vil du lære:
- Hva er den første timeplanlegging?
- Kjennetegn ved SJF-planlegging
- Ikke-forebyggende SJF
- Forebyggende SJF
- Fordeler med SJF
- Ulemper / ulemper med SJF
Kjennetegn ved SJF-planlegging
- Det er knyttet til hver jobb som en tidsenhet å fullføre.
- Denne algoritmemetoden er nyttig for batch-behandling, der det ikke er viktig å vente på at jobber skal fullføres.
- Det kan forbedre prosessgjennomstrømningen ved å sørge for at kortere jobber utføres først, og dermed muligens ha en kort behandlingstid.
- Det forbedrer jobbutgangen ved å tilby kortere jobber, som skal utføres først, som for det meste har kortere behandlingstid.
Ikke-forebyggende SJF
I ikke-forebyggende planlegging, når CPU-syklusen er allokert til prosess, holder prosessen den til den når en ventetilstand eller avsluttes.
Tenk på følgende fem prosesser som hver har sin egen unike bursttid og ankomsttid.
| Prosesskø | Bursttid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Trinn 0) På tidspunktet = 0 ankommer P4 og starter utførelsen.
Trinn 1) Ved tid = 1, kommer prosess P3. Men P4 trenger fortsatt to utførelsesenheter for å fullføre. Det vil fortsette utførelsen.
Trinn 2) Ved tid = 2 ankommer prosess P1 og legges til ventekøen. P4 vil fortsette utførelsen.
Trinn 3) Ved tid = 3 vil prosess P4 fullføre utførelsen. Sprengningstiden for P3 og P1 sammenlignes. Prosess P1 utføres fordi burst-tiden er mindre sammenlignet med P3.
Trinn 4) Ved tid = 4 ankommer prosess P5 og legges til ventekøen. P1 vil fortsette utførelsen.
Trinn 5) Ved tid = 5 ankommer prosess P2 og legges til ventekøen. P1 vil fortsette utførelsen.
Trinn 6) Ved tid = 9 vil prosess P1 fullføre utførelsen. Sprengningstiden til P3, P5 og P2 sammenlignes. Prosess P2 utføres fordi bursttiden er lavest.
Trinn 7) Ved tid = 10 kjører P2 og P3 og P5 står i ventekøen.
Trinn 8) Ved tid = 11 vil prosess P2 fullføre utførelsen. Sprengningstiden for P3 og P5 sammenlignes. Prosess P5 utføres fordi burst-tiden er lavere.
Trinn 9) Ved tid = 15 vil prosess P5 fullføre utførelsen.
Trinn 10) Ved tid = 23 vil prosess P3 fullføre utførelsen.
Trinn 11) La oss beregne gjennomsnittlig ventetid for eksemplet ovenfor.
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 Preemptive SJF Scheduling blir jobber satt i klar kø når de kommer. En prosess med kortest bursttid begynner utførelsen. Hvis en prosess med enda kortere bursttid ankommer, blir den nåværende prosessen fjernet eller forhindret fra utføring, og den kortere jobben tildeles CPU-syklus.
Tenk på følgende fem prosesser:
| Prosesskø | Bursttid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Trinn 0) På tidspunktet = 0 ankommer P4 og starter utførelsen.
| Prosesskø | Bursttid | Ankomsttid |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Trinn 1) Ved tid = 1, kommer prosess P3. Men P4 har kortere bursttid. Det vil fortsette utførelsen.
Trinn 2) Ved tid = 2, kommer prosess P1 med bursttid = 6. Bursttiden er mer enn P4. Derfor vil P4 fortsette kjøringen.
Trinn 3) Ved tid = 3 vil prosess P4 fullføre utførelsen. Sprengningstiden for P3 og P1 sammenlignes. Prosess P1 utføres fordi burst-tiden er lavere.
Trinn 4) Ved tid = 4 vil prosess P5 ankomme. Sprengningstiden for P3, P5 og P1 sammenlignes. Prosess P5 utføres fordi bursttiden er lavest. Prosess P1 er forhindret.
| Prosesskø | Bursttid | Ankomsttid |
| P1 | 5 av 6 er igjen | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Trinn 5) Ved tid = 5 vil prosess P2 ankomme. Sprengningstiden for P1, P2, P3 og P5 sammenlignes. Prosess P2 utføres fordi bursttiden er minst. Prosess P5 er forhindret.
| Prosesskø | Bursttid | Ankomsttid |
| P1 | 5 av 6 er igjen | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 av 4 er igjen | 4 |
Trinn 6) Ved tid = 6 kjører P2.
Trinn 7) På tidspunktet = 7 fullfører P2 utførelsen. Sprengningstiden for P1, P3 og P5 sammenlignes. Prosess P5 utføres fordi burst-tiden er mindre.
| Prosesskø | Bursttid | Ankomsttid |
| P1 | 5 av 6 er igjen | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 av 4 er igjen | 4 |
Trinn 8) Ved tid = 10 vil P5 fullføre utførelsen. Sprengningstiden for P1 og P3 sammenlignes. Prosess P1 kjøres fordi burst-tiden er kortere.
Trinn 9) Ved tid = 15 fullfører P1 kjøringen. P3 er den eneste prosessen som er igjen. Det vil starte utførelsen.
Trinn 10) Ved tid = 23 avslutter P3 kjøringen.
Trinn 11) La oss beregne gjennomsnittlig ventetid for eksemplet ovenfor.
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
Fordeler med SJF
Her er fordelene / fordelene ved å bruke SJF-metoden:
- SJF brukes ofte til planlegging på lang sikt.
- Det reduserer gjennomsnittlig ventetid over FIFO (First in First Out) algoritme.
- SJF-metoden gir den laveste gjennomsnittlige ventetiden for et bestemt sett med prosesser.
- Det er hensiktsmessig for jobbene som kjøres i batch, hvor kjøretider er kjent på forhånd.
- For batch-systemet for langsiktig planlegging kan du få et estimat for burst-tid fra stillingsbeskrivelsen.
- For kortsiktig planlegging må vi forutsi verdien av neste burst-tid.
- Sannsynligvis optimal med tanke på gjennomsnittlig behandlingstid.
Ulemper / ulemper med SJF
Her er noen ulemper / ulemper med SJF-algoritmen:
- Gjennomføringstid må være kjent tidligere, men det er vanskelig å forutsi.
- Det brukes ofte i et batch-system for langsiktig planlegging.
- SJF kan ikke implementeres for CPU-planlegging på kort sikt. Det er fordi det ikke er noen spesifikk metode for å forutsi lengden på den kommende CPU-burst.
- Denne algoritmen kan føre til svært lange behandlingstider eller sult.
- Krever kunnskap om hvor lenge en prosess eller jobb vil gå.
- Det fører til sult som ikke reduserer gjennomsnittlig leveringstid.
- Det er vanskelig å vite lengden på den kommende CPU-forespørselen.
- Forløpt tid bør registreres, noe som resulterer i mer overhead på prosessoren.
Sammendrag
- SJF er en algoritme der prosessen som har den minste utførelsestiden velges for neste utførelse.
- SJF-planlegging er knyttet til hver jobb som en tidsenhet å fullføre.
- Denne algoritmemetoden er nyttig for batch-behandling, der det ikke er viktig å vente på at jobber skal fullføres.
- Det er i utgangspunktet to typer SJF-metoder 1) Ikke-forebyggende SJF og 2) Forebyggende SJF.
- I ikke-forebyggende planlegging, når prosesssyklusen er allokert til prosess, holder prosessen den til den når en ventetilstand eller avsluttes.
- I Preemptive SJF Scheduling blir jobber satt i klar kø når de kommer.
- Selv om en prosess med kort bursttid begynner, blir den nåværende prosessen fjernet eller forhindret fra utførelse, og jobben som er kortere blir utført første.
- SJF brukes ofte til planlegging på lang sikt.
- Det reduserer gjennomsnittlig ventetid over FIFO (First in First Out) algoritme.
- I SJF-planlegging må jobbens fullføringstid være kjent tidligere, men det er vanskelig å forutsi.
- SJF kan ikke implementeres for CPU-planlegging på kort sikt. Det er fordi det ikke er noen spesifikk metode for å forutsi lengden på den kommende CPU-burst.