Shortest Job First (SJF): Preemptive, Non-Preemptive Eksempel

⚡ Smart oppsummering

Shortest Job First (SJF) er en CPU-planleggingsalgoritme som velger prosessen med kortest utførelsestid til neste kjøring. Den kan være preemptiv eller ikke-preemptiv og reduserer den gjennomsnittlige ventetiden for prosesser betydelig.

️ Definisjon: Prosessen med kortest burst-tid velges for neste utførelse.
🔀 To typer: SJF kan være ikke-preemptiv eller preemptiv (Shortest Remaining Time First).
📉 Hovedfordel: Det gir den laveste gjennomsnittlige ventetiden for et gitt sett med prosesser.
🏭 Beste bruk: Ideelt for batchsystemer der jobbkjøretider er kjent på forhånd.
❓ Hovedbegrensning: Sprengningstidspunktet må vites på forhånd, noe som er vanskelig å forutsi.
⚠️ Fare: Lange prosesser kan sulte ut hvis korte jobber fortsetter å dukke opp.

Les mer

Hva er Shortest Job First Scheduling?

Korteste jobb først (SJF) er en algoritme der prosessen med den minste utførelsestiden velges for neste utførelse. Denne planleggingsmetoden kan være forebyggende eller ikke-forebyggende. Det reduserer den gjennomsnittlige ventetiden betydelig for andre prosesser som venter på utførelse. Den fullstendige formen for SJF er Shortest Job First.

Det er i hovedsak to typer SJF-metoder:

Ikke-forebyggende SJF
Forebyggende SJF

Kjennetegn ved SJF-planlegging

Det er knyttet til hver jobb som en tidsenhet for å fullføre.
Denne algoritmemetoden er nyttig for batch-behandling, der det ikke er kritisk å vente på at jobbene 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 jobbutbyttet ved å tilby kortere jobber, som bør utføres først, og som stort sett har kortere behandlingstid.

Ikke-forebyggende SJF

I ikke-preemptiv planlegging, når CPU-syklusen er tildelt en prosess, holder prosessen den til den når en ventetilstand eller avsluttes.

Tenk på de følgende fem prosessene, som hver har sin egen unike burst-tid og ankomsttid.

Prosesskø	Sprengtid	Ankomsttid
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trinn 0) Ved tid = 0 ankommer P4 og starter utførelsen.

Trinn 1) Ved tid = 1 ankommer prosess P3. Men P4 trenger fortsatt 2 utførelsesenheter for å fullføres. Den vil fortsette utførelse.

Trinn 2) Ved tid = 2 kommer prosess P1 og legges til ventekøen. P4 vil fortsette kjøringen.

Trinn 3) Ved tid = 3 vil prosess P4 fullføre utførelsen. Bursttiden til P3 og P1 sammenlignes. Prosess P1 utføres fordi eksplosjonstiden er kortere sammenlignet med P3.

Trinn 4) Ved tid = 4 kommer prosess P5 og legges til ventekøen. P1 vil fortsette kjøringen.

Trinn 5) Ved tid = 5 kommer prosess P2 og legges til ventekøen. P1 vil fortsette kjøringen.

Trinn 6) Ved tid = 9 vil prosess P1 fullføre utførelsen. Bursttiden til P3, P5 og P2 sammenlignes. Prosess P2 utføres fordi eksplosjonstiden er den laveste.

Trinn 7) Ved tidspunktet = 10 utfører P2 prosessen, og P3 og P5 står i ventekøen.

Trinn 8) Ved tid = 11 vil prosess P2 fullføre utførelsen. Bursttiden til P3 og P5 sammenlignes. Prosess P5 utføres fordi eksplosjonstiden er kortere.

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 den gjennomsnittlige ventetiden for eksemplet ovenfor.

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-planlegging settes jobber i klarkøen etter hvert som de kommer. En prosess med kortest burst-tid starter kjøringen. Hvis en prosess med en enda kortere burst-tid kommer, fjernes eller forhindres kjøring av den gjeldende prosessen, og den kortere jobben tildeles en CPU-syklus.

Tenk på følgende fem prosesser:

Prosesskø	Sprengtid	Ankomsttid
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trinn 0) Ved tid = 0 ankommer P4 og starter utførelsen.

Prosesskø	Sprengtid	Ankomsttid
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trinn 1) Ved tid = 1 ankommer prosess P3. Men P4 har en kortere burst-tid. Den vil fortsette utførelsen.

Trinn 2) Ved tid = 2 kommer prosess P1 med bruddtid = 6. Bursttiden er mer enn P4. Derfor vil P4 fortsette kjøringen.

Trinn 3) Ved tid = 3 vil prosess P4 fullføre utførelsen. Bursttiden til P3 og P1 sammenlignes. Prosess P1 utføres fordi eksplosjonstiden er kortere.

Trinn 4) Ved tid = 4 kommer prosess P5. Bursttiden til P3, P5 og P1 sammenlignes. Prosess P5 utføres fordi eksplosjonstiden er lavest. Prosess P1 er forhåndsaktivert.

Prosesskø	Sprengtid	Ankomsttid
P1	5 av 6 gjenstår	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Trinn 5) Ved tid = 5 vil prosess P2 ankomme. Bursttiden til P1, P2, P3 og P5 sammenlignes. Prosess P2 utføres fordi bursttiden er kortest. Prosess P5 er preempted.

Prosesskø	Sprengtid	Ankomsttid
P1	5 av 6 gjenstår	2
P2	2	5
P3	8	1
P4	3	0
P5	3 av 4 gjenstår	4

Trinn 6) Ved tid = 6 utføres P2.

Trinn 7) Ved tid = 7 fullfører P2 utførelsen. Bursttiden til P1, P3 og P5 sammenlignes. Prosess P5 utføres fordi bursttiden er kortere.

Prosesskø	Sprengtid	Ankomsttid
P1	5 av 6 gjenstår	2
P2	2	5
P3	8	1
P4	3	0
P5	3 av 4 gjenstår	4

Trinn 8) Ved tid = 10 vil P5 fullføre utførelsen. Bursttiden til P1 og P3 sammenlignes. Prosess P1 utføres fordi bursttiden er kortere.

Trinn 9) Ved tid = 15 fullfører P1 utførelsen. P3 er den eneste prosessen som er igjen. Den vil starte utførelsen.

Trinn 10) Ved tid = 23 fullfører P3 utførelsen.

Trinn 11) La oss beregne den gjennomsnittlige ventetiden for eksemplet ovenfor.

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

Fordeler med SJF

Her er fordelene/profesjonene ved å bruke SJF-metoden:

SJF brukes ofte til langsiktig planlegging.
Det reduserer den gjennomsnittlige ventetiden i forhold til FIFO-algoritmen (først inn, først ut).
SJF-metoden gir den laveste gjennomsnittlige ventetiden for et spesifikt sett med prosesser.
Det er hensiktsmessig for jobbene som kjøres i batch, hvor kjøretider er kjent på forhånd.
For batchsystemet for langsiktig planlegging kan et estimat for sprengningstid fås fra stillingsbeskrivelsen.
For kortsiktig planlegging må vi forutsi verdien av neste bruddtid.
Det er sannsynligvis optimalt med tanke på gjennomsnittlig behandlingstid.

Ulemper/ulemper med SJF

Her er noen ulemper/ulemper med SJF-algoritmen:

Tidspunkt for gjennomføring av jobb må være kjent tidligere, men det er vanskelig å forutsi.
Det brukes ofte i et batchsystem 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å det kommende CPU-utbruddet.
Denne algoritmen kan forårsake svært lange behandlingstider eller sult.
Krever kunnskap om hvor lenge en prosess eller jobb vil pågå.
Det fører til sult som ikke reduserer gjennomsnittlig behandlingstid.
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.

Spørsmål og svar

SRTF (Shortest Remaining Time First) er rett og slett den preemptive versjonen av SJF. I SJF fullføres en pågående jobb før den neste velges. I SRTF kan en nylig ankommet jobb med kortere gjenværende tid preemptive den pågående prosessen.

SJF favoriserer alltid den korteste jobben. Hvis korte prosesser stadig vekk ankommer, kan det hende at en lang prosess aldri får CPU-en og venter på ubestemt tid. Dette er sult. Aldring, som sakte hever prioriteten til en ventende jobb, brukes til å forhindre det.

Ja. SJF er beviselig optimal fordi den produserer den minste mulige gjennomsnittlige ventetiden for et gitt sett med prosesser. Dette er imidlertid bare sant hvis burst-tidene er kjent på forhånd, noe som sjelden er mulig i praksis.

AI og maskinlæring kan analysere en prosess historikk, kodefunksjoner og tidligere kjøringer for å estimere CPU-bursttiden. Bedre prediksjoner gjør SJF mer nøyaktig, og reduserer ventetiden sammenlignet med tradisjonelle eksponentielle gjennomsnittsestimater.

Potensielt. SJF sliter med kortsiktig planlegging fordi burst-tider er ukjente. AI som forutsier bursts i sanntid kan gjøre SJF brukbar, men prediksjonsoverhead og feil må holdes lave nok til at planleggingsbeslutningen er verdt å ta.