logo

Lyhyin työ ensin (SJF) -aikataulu

Tähän asti olemme ajoittaneet prosessit niiden saapumisajan mukaan (FCFS-aikataulutuksessa). SJF-ajoitusalgoritmi kuitenkin ajoittaa prosessit niiden purskeajan mukaan.

SJF-ajoituksessa seuraavaksi ajoitetaan prosessi, jolla on pienin purskeaika valmiusjonossa olevien prosessien luettelosta.

On kuitenkin erittäin vaikea ennustaa prosessiin tarvittavaa purskeaikaa, joten tämä algoritmi on erittäin vaikea toteuttaa järjestelmässä.

SJF:n edut

  1. Suurin suorituskyky
  2. Minimi keskimääräinen odotus- ja läpimenoaika

SJF:n haitat

  1. Voi kärsiä nälkäongelmasta
  2. Se ei ole toteutettavissa, koska prosessin tarkkaa purskeaikaa ei voida tietää etukäteen.

Käytettävissä on erilaisia ​​tekniikoita, joilla prosessin suorittimen purskeaika voidaan määrittää. Keskustelemme niistä myöhemmin yksityiskohtaisesti.

Esimerkki

Seuraavassa esimerkissä on viisi työtä nimeltä P1, P2, P3, P4 ja P5. Niiden saapumisaika ja sarjakuvausaika on esitetty alla olevassa taulukossa.

PID Saapumisaika Burst Time Valmistumisaika Kääntymisaika Odotusaika
1 1 7 8 7 0
2 3 3 13 10 7
3 6 2 10 4 2
4 7 10 31 24 14
5 9 8 kaksikymmentäyksi 12 4

Koska, Ei prosessia saapuu aikaan 0, joten; tulee tyhjä paikka Gantt-kaavio ajasta 0 - 1 (aika, jolloin ensimmäinen prosessi saapuu).

hashset java

Algoritmin mukaan käyttöjärjestelmä aikatauluttaa prosessin, jolla on pienin purskeaika valmiusjonon käytettävissä olevista prosesseista.

Toistaiseksi meillä on vain yksi prosessi valmiusjonossa, joten ajoittaja ajoittaa tämän prosessorille riippumatta sen purskeajasta.

Tämä suoritetaan 8 aikayksikköön asti. Siihen asti meillä on valmiusjonossa vielä kolme prosessia, joten ajoittaja valitsee prosessin, jolla on pienin purskeaika.

abstrakteja menetelmiä

Taulukossa annetuista prosesseista P3 suoritetaan seuraavaksi, koska sillä on pienin purskeaika kaikista käytettävissä olevista prosesseista.

Joten näin menettely etenee lyhin työ ensin (SJF) aikataulutusalgoritmi.

os SJF-aikataulutusalgoritmi

Keskimääräinen odotusaika = 27/5