Mikä on lyhin työn ensimmäinen aikataulu?
Lyhin työ ensin (SJF) on algoritmi, jossa seuraavaan suoritukseen valitaan prosessi, jolla on pienin suoritusaika. Tämä ajoitusmenetelmä voi olla ennakoiva tai ei-ennaltaehkäisevä. Se lyhentää merkittävästi muiden suoritusta odottavien prosessien keskimääräistä odotusaikaa. SJF: n koko muoto on lyhin työ ensin.
SJF-menetelmiä on periaatteessa kahta tyyppiä:
- Ei-ennaltaehkäisevä SJF
- Ennakoiva SJF
Tässä käyttöjärjestelmän opetusohjelmassa opit:
- Mikä on lyhin työn ensimmäinen aikataulu?
- SJF-aikataulutuksen ominaisuudet
- Ei-ennaltaehkäisevä SJF
- Ennakoiva SJF
- SJF: n edut
- SJF: n haitat / haitat
SJF-aikataulutuksen ominaisuudet
- Se liittyy jokaiseen työhön suoritettavana aikayksikkönä.
- Tämä algoritmimenetelmä on hyödyllinen erätyyppisessä prosessoinnissa, jossa töiden odottaminen ei ole kriittistä.
- Se voi parantaa prosessin läpäisykykyä varmistamalla, että lyhyemmät työt suoritetaan ensin, jolloin niiden läpimenoaika on mahdollisesti lyhyt.
- Se parantaa työn tuottoa tarjoamalla lyhyempiä työpaikkoja, jotka tulisi suorittaa ensin, joiden läpimenoaika on yleensä lyhyempi.
Ei-ennaltaehkäisevä SJF
Ei-ennakoivassa ajoituksessa, kun CPU-sykli on varattu prosessille, prosessi pitää sitä, kunnes se saavuttaa odotustilan tai päättyy.
Harkitse seuraavia viittä prosessia, joilla kullakin on oma ainutlaatuinen purske- ja saapumisaikansa.
| Prosessijono | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 0) Aikana = 0 P4 saapuu ja aloittaa suorituksen.
Vaihe 1) Aikana = 1, prosessi P3 saapuu. Mutta P4 tarvitsee vielä 2 suoritusyksikköä suoritettavaksi. Se jatkaa toteuttamista.
Vaihe 2) Kun aika = 2, prosessi P1 saapuu ja lisätään odotusjonoon. P4 jatkaa suoritusta.
Vaihe 3) Ajanhetkellä = 3 prosessi P4 suorittaa suorituksensa loppuun. P3: n ja P1: n purskeaikaa verrataan. Prosessi P1 suoritetaan, koska sen purskeaika on pienempi kuin P3.
Vaihe 4) Kun aika = 4, prosessi P5 saapuu ja lisätään odotusjonoon. P1 jatkaa suoritusta.
Vaihe 5) Kun aika = 5, prosessi P2 saapuu ja lisätään odotusjonoon. P1 jatkaa suoritusta.
Vaihe 6) Aikana = 9 prosessi P1 suorittaa suorituksensa loppuun. P3: n, P5: n ja P2: n purskeaikaa verrataan. Prosessi P2 suoritetaan, koska sen purskeaika on pienin.
Vaihe 7) Aikana = 10 P2 suorittaa ja P3 ja P5 ovat odotusjonossa.
Vaihe 8) Ajanhetkellä = 11 prosessi P2 suorittaa suorituksensa loppuun. P3: n ja P5: n purskeaikaa verrataan. Prosessi P5 suoritetaan, koska sen purskeaika on pienempi.
Vaihe 9) Ajanhetkellä = 15 prosessi P5 suorittaa suorituksensa loppuun.
Vaihe 10) Ajanhetkellä = 23 prosessi P3 suorittaa suorituksensa loppuun.
Vaihe 11) Laske keskimääräinen odotusaika yllä olevalle esimerkille.
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
Ennakoiva SJF
Ennakoivassa SJF-ajoituksessa työpaikat asetetaan valmiiksi jonoon niiden tullessa. Lyhyimmän purskeajan omaava prosessi alkaa. Jos prosessi, jolla on jopa lyhyempi purskeaika, saapuu, nykyinen prosessi poistetaan tai estetään suorittamasta ja lyhyemmälle työlle osoitetaan suorittimen jakso.
Harkitse seuraavaa viittä prosessia:
| Prosessijono | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 0) Aikana = 0 P4 saapuu ja aloittaa suorituksen.
| Prosessijono | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 1) Aikana = 1, prosessi P3 saapuu. Mutta P4: llä on lyhyempi purskeaika. Se jatkaa toteuttamista.
Vaihe 2) Aikana = 2, prosessi P1 saapuu purskeajalla = 6. Purskeaika on enemmän kuin P4: n. Siksi P4 jatkaa suoritusta.
Vaihe 3) Ajanhetkellä = 3 prosessi P4 suorittaa suorituksensa loppuun. P3: n ja P1: n purskeaikaa verrataan. Prosessi P1 suoritetaan, koska sen purskeaika on pienempi.
Vaihe 4) Aikana = 4, prosessi P5 saapuu. P3: n, P5: n ja P1: n purskeaikaa verrataan. Prosessi P5 suoritetaan, koska sen purskeaika on pienin. Prosessi P1 on estetty.
| Prosessijono | Sarjaaika | Saapumisaika |
| P1 | 5/6 on jäljellä | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 5) Aikana = 5, prosessi P2 saapuu. Verrataan P1: n, P2: n, P3: n ja P5: n purskeaikaa. Prosessi P2 suoritetaan, koska sen purskeaika on pienin. Prosessi P5 on estetty.
| Prosessijono | Sarjaaika | Saapumisaika |
| P1 | 5/6 on jäljellä | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3/4 on jäljellä | 4 |
Vaihe 6) Aikana = 6 P2 suorittaa.
Vaihe 7) Aikana = 7, P2 suorittaa suorituksensa loppuun. Pl: n, P3: n ja P5: n purskeaikaa verrataan. Prosessi P5 suoritetaan, koska sen purskeaika on lyhyempi.
| Prosessijono | Sarjaaika | Saapumisaika |
| P1 | 5/6 on jäljellä | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3/4 on jäljellä | 4 |
Vaihe 8) Ajanhetkellä = 10 P5 suorittaa suorituksensa. P1: n ja P3: n purskeaikaa verrataan. Prosessi P1 suoritetaan, koska sen purskeaika on lyhyempi.
Vaihe 9) Aikana = 15, P1 suorittaa suorituksensa loppuun. P3 on ainoa jäljellä oleva prosessi. Se alkaa suorittaa.
Vaihe 10) Aikana = 23, P3 suorittaa suorituksensa.
Vaihe 11) Laske keskimääräinen odotusaika yllä olevalle esimerkille.
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
SJF: n edut
Tässä ovat SJF-menetelmän käytön edut / edut:
- SJF: ää käytetään usein pitkän aikavälin aikatauluun.
- Se vähentää keskimääräistä odotusaikaa FIFO (First in First Out) -algoritmilla.
- SJF-menetelmä antaa pienimmän keskimääräisen odotusajan tietylle prosessisarjalle.
- Se sopii erissä suoritettaville töille, joissa ajoajat tiedetään etukäteen.
- Pitkäaikaisen aikataulutuksen eräjärjestelmälle purskeaikaestimaatti voidaan saada työn kuvauksesta.
- Lyhytaikaista ajoitusta varten meidän on ennustettava seuraavan purskeajan arvo.
- Todennäköisesti optimaalinen keskimääräisen läpimenoajan suhteen.
SJF: n haitat / haitat
Tässä on joitain SJF-algoritmin haittoja / haittoja:
- Työn valmistumisaika on tiedettävä aikaisemmin, mutta sitä on vaikea ennustaa.
- Sitä käytetään usein eräajojärjestelmässä pitkän aikavälin aikataulutukseen.
- SJF: ää ei voida toteuttaa prosessorin ajoitusta varten lyhyellä aikavälillä. Se johtuu siitä, että tulevan CPU-purskeen pituuden ennustamiseksi ei ole olemassa erityistä menetelmää.
- Tämä algoritmi voi aiheuttaa erittäin pitkiä läpimenoaikoja tai nälkää.
- Edellyttää tietoa prosessin tai työn kestosta.
- Se johtaa nälkään, joka ei lyhennä keskimääräistä läpimenoaikaa.
- On vaikea tietää tulevan CPU-pyynnön pituutta.
- Kulunut aika on kirjattava, mikä lisää prosessorin lisäkustannuksia.
Yhteenveto
- SJF on algoritmi, jossa seuraavaan suoritukseen valitaan prosessi, jolla on pienin suoritusaika.
- SJF-ajoitus liittyy jokaiseen työhön suoritettavana aikayksikkönä.
- Tämä algoritmimenetelmä on hyödyllinen erätyyppisessä prosessoinnissa, jossa töiden odottaminen ei ole kriittistä.
- SJF-menetelmiä on periaatteessa kahta tyyppiä: 1) ei-ennaltaehkäisevä SJF ja 2) ennalta ehkäisevä SJF-menetelmä.
- Ei-ennakoivassa ajoituksessa, kun CPU-sykli on varattu prosessille, prosessi pitää sitä, kunnes se saavuttaa odotustilan tai päättyy.
- Ennakoivassa SJF-ajoituksessa työpaikat asetetaan valmiiksi jonoon niiden tullessa.
- Vaikka prosessi, jolla on lyhyt purskeaika, alkaa, nykyinen prosessi poistetaan tai estetään suorittamasta, ja lyhyempi työ suoritetaan ensimmäisenä.
- SJF: ää käytetään usein pitkän aikavälin aikatauluun.
- Se vähentää keskimääräistä odotusaikaa FIFO (First in First Out) -algoritmilla.
- SJF-aikataulutuksessa työn valmistumisaika on tiedettävä aikaisemmin, mutta sitä on vaikea ennustaa.
- SJF: ää ei voida toteuttaa prosessorin ajoitusta varten lyhyellä aikavälillä. Se johtuu siitä, että tulevan CPU-purskeen pituuden ennustamiseksi ei ole olemassa erityistä menetelmää.