Prosessorin ajoitus Algorithms in Operating Systems

Mikä on suorittimen ajoitus?

Prosessorin ajoitus on prosessi, jossa määritetään, mikä prosessi omistaa suorittimen suoritusta varten, kun toinen prosessi on odotustilassa. Suorittimen ajoituksen päätehtävänä on varmistaa, että aina kun suoritin on käyttämättömänä, käyttöjärjestelmä valitsee suoritettavaksi ainakin yhden valmiusjonossa olevista prosesseista. Valintaprosessin suorittaa suorittimen ajoittaja, joka valitsee yhden muistissa olevista suoritusvalmiista prosesseista.

Suorittimen ajoituksen tyypit

Tässä on kaksi aikataulutusmenetelmää:

Ennakoiva ajoitus

Ennakoivassa ajoituksessa tehtäville annetaan useimmiten niiden prioriteetit. Joskus on tärkeää suorittaa korkeamman prioriteetin tehtävä ennen toista, alemman prioriteetin tehtävää, vaikka alemman prioriteetin tehtävä olisikin vielä käynnissä. Alemman prioriteetin tehtävä odottaa jonkin aikaa ja jatkuu, kun korkeamman prioriteetin tehtävä on suorittanut sen loppuun.

Ei-ennakoiva ajoitus

Tällaisessa ajoitusmenetelmässä suoritin allokoidaan tietylle prosessille. Prosessi, joka pitää suorittimen kiireisenä, vapauttaa suorittimen joko vaihtamalla kontekstia tai lopettamalla sen. Tämä on ainoa menetelmä, jota voidaan käyttää eri laitteistoalustoilla, koska se ei vaadi erityistä laitteistoa (esimerkiksi ajastinta) kuten ennakoiva ajoitus.

Milloin aikataulutus on ennaltaehkäisevää tai ei-ennakoivaa?

Jotta voit määrittää, onko ajoitus ennaltaehkäisevää vai ei-ennakoivaa, ota huomioon seuraavat neljä parametria:

1. Prosessi siirtyy käynnissä olevasta odotustilaan.
2. Tietty prosessi siirtyy käynnissä olevasta tilasta valmiustilaan.
3. Tietty prosessi siirtyy odotustilasta valmiustilaan.
4. Prosessi suorittaa suorituksensa loppuun ja päättyy.

Jos vain ehdot 1 ja 4 täyttyvät, aikataulutusta kutsutaan ei-preemptiiviseksi. Kaikki muut aikataulutustilanteet ovat preemptiivisiä.

Tärkeitä suorittimen ajoituksen terminologioita

• Purskeaika/suoritusaika: Prosessin suorittamiseen tarvittava aika. Sitä kutsutaan myös suoritusajaksi.
• Saapumisaika: Aika, jolloin prosessi siirtyy valmiustilaan.
• Loppuaika: Aika, jolloin prosessi valmistuu ja poistuu järjestelmästä.
• Moniohjelmointi: Useita ohjelmia, jotka voivat olla muistissa samanaikaisesti.
• Työpaikat: Ohjelmatyyppi, jossa ei ole minkäänlaista käyttäjän vuorovaikutusta.
• Käyttäjä: Eräänlainen ohjelma, johon liittyy käyttäjän vuorovaikutusta.
• Prosessi: Viite, jota käytetään sekä työlle että käyttäjälle.
• CPU/IO-purskejakso: Kuvaa prosessin suoritusta, jossa vuorottelee suorittimen ja I/O-toiminnan välillä. Suorittimen ajat ovat yleensä lyhyempiä kuin I/O-ajat.

CPU:n ajoituskriteerit

Suorittimen ajoitusalgoritmi yrittää maksimoida ja minimoida seuraavat asiat:

Maksimoida

CPU: n käyttö: Suorittimen käyttöaste on käyttöjärjestelmän päätehtävä, jossa suorittimen käyttöaste pysyy mahdollisimman kuormitettuna. Se voi vaihdella 0:sta 100 prosenttiin. RTOS:ssa se voi kuitenkin vaihdella 40 prosentista matalan tason järjestelmässä 90 prosenttiin korkean tason järjestelmässä.

suoritusteho: Suorituksensa loppuun saattavien prosessien lukumäärää aikayksikköä kohti kutsutaan suoritustehoksi. Joten kun CPU on kiireinen suorittamassa prosessia, työtä tehdään, ja aikayksikköä kohti suoritettua työtä kutsutaan suoritustehoksi.

Minimoida

Odotusaika: Odotusaika on se aika, jonka tietyn prosessin on odotettava valmiusjonossa.

Vasteaika: Se on aika, joka kuluu pyynnön lähettämisestä ensimmäisen vastauksen saamiseen.

Läpimenoaika: Läpimenoaika on tietyn prosessin suorittamiseen kuluva aika. Se on kokonaisaika, joka kuluu odottamiseen muistiin pääsyä, jonossa odottamiseen ja suorittimen suorittamiseen. Prosessin lähettämisajan ja valmistumisajan välinen aika on läpimenoaika.

Intervalliajastin

Ajastinkeskeytys on menetelmä, joka liittyy läheisesti ennaltaehkäisyyn. Kun tietty prosessi saa CPU-allokoinnin, ajastin voidaan asettaa määrätylle aikavälille. Sekä ajastimen keskeytys että ennaltaehkäisy pakottavat prosessin palauttamaan CPU:n ennen kuin sen prosessoripurske on valmis.

Useimmat moniohjelmoidut käyttöjärjestelmät käyttävät jonkinlaista ajastinta estääkseen prosessia sitomasta järjestelmää ikuisesti.

Mikä on Dispatcher?

Lähetin on moduuli, joka tarjoaa prosessille suorittimen hallinnan. Lähettimen tulisi olla nopea, jotta se voi toimia jokaisella kontekstikytkimellä. Lähetyslatenssi on aika, jonka suorittimen ajoitin tarvitsee yhden prosessin pysäyttämiseen ja toisen käynnistämiseen.

Lähettäjän suorittamat toiminnot:

• Kontekstin vaihtaminen.
• Vaihtaminen käyttäjätilaan.
• Siirtyminen oikeaan paikkaan juuri ladatussa ohjelmassa.

Suorittimen ajoituksen tyypit Algorithms

Niitä on pääasiassa kuusi tyyppiä prosessien ajoitusalgoritmit:

1. Ensin tullutta palvella (FCFS)
2. Lyhyin työ ensin (SJF) -aikataulu
3. Lyhin jäljellä oleva aika
4. Ensisijainen ajoitus
5. Kierros Robin -aikataulu
6. Monitasoinen jonon ajoitus

Ajoitus Algorithms

Ensin saapunut ensin -palvelu

FCFS tarkoittaa Ensin saapunut ensin -palveluSe on helpoin ja yksinkertaisin suorittimen ajoitusalgoritmi. Tällaisessa algoritmissa suoritinta pyytävä prosessi saa suorittimen allokoinnin ensin. Tätä ajoitusmenetelmää voidaan hallita FIFO-jonolla.

Kun prosessi siirtyy valmiusjonoon, sen piirilevy (Process Control Block) linkitetään jonon häntään. Joten kun CPU vapautuu, se tulisi osoittaa jonon alussa olevalle prosessille.

FCFS-menetelmän ominaisuudet

• Se on ei-preemptiivinen ajoitusalgoritmi.
• Työt tehdään aina saapumisjärjestyksessä.
• Se on helppo toteuttaa ja käyttää.
• Tämän menetelmän suorituskyky on kuitenkin heikko, ja yleinen odotusaika on melko pitkä.

Lyhin jäljellä oleva aika

SRT:n täydellinen muoto on lyhin jäljellä oleva aika (Shortest Remaining Time). Se tunnetaan myös nimellä SJF preemptive scheduling. Tässä menetelmässä prosessi allokoidaan tehtävälle, joka on lähimpänä sen valmistumista. Tämä menetelmä estää uudempaa valmiustilassa olevaa prosessia viivästyttämästä vanhemman prosessin valmistumista.

SRT-aikataulutusmenetelmän ominaisuudet

• Tätä menetelmää käytetään enimmäkseen eräajoympäristöissä, joissa lyhyille töille on annettava etusija.
• Tämä ei ole ihanteellinen menetelmä toteutettavaksi jaetussa järjestelmässä, jossa vaadittava suorittimen aika on tuntematon.
• Jokainen prosessi on liitetty sen seuraavan CPU-purskeen pituuteen, joten käyttöjärjestelmä käyttää näitä pituuksia prosessin ajoittamiseen lyhyimmällä mahdollisella ajalla.

Priority Based Scheduling

Ensisijainen ajoitus on prosessien aikataulutusmenetelmä prioriteetin perusteella. Tässä menetelmässä ajoittaja valitsee tehtävät niiden prioriteetin mukaan.

Prioriteettiajoitus auttaa myös käyttöjärjestelmää priorisoimaan prosesseja. Korkeamman prioriteetin omaavat prosessit suoritetaan ensin, kun taas yhtä suuren prioriteetin omaavat työt suoritetaan round-robin- tai FCFS-periaatteella. Prioriteetti voidaan määrittää muistivaatimusten, aikavaatimusten ja muiden tekijöiden perusteella.

Round-Robin-aikataulu

Round robin on yksi vanhimmista ja yksinkertaisimmista ajoitusalgoritmeista. Algoritmin nimi tulee round-robin-periaatteesta, jossa jokainen henkilö saa vuorollaan yhtä suuren osan jostakin. Sitä käytetään enimmäkseen moniajojärjestelmien ajoitukseen. Tämä menetelmä auttaa saavuttamaan prosessien suorittamisen ilman nälkiintymistä.

Round-Robin-aikataulutuksen ominaisuudet

• Round robin on hybridimalli, jota ohjataan kellolla.
• Tietylle tehtävälle varatun aikaviipaleen tulisi olla mahdollisimman lyhyt. Se voi kuitenkin vaihdella eri prosessien välillä.
• Se toimii kuin aikajakojärjestelmä, joka vastaa jokaiseen prosessiin tietyn aikarajan sisällä.

Lyhyin työ ensin

SJF (Shortest Job First) on ajoitusalgoritmi, jossa lyhimmän suoritusajan omaava prosessi valitaan seuraavaksi suoritettavaksi. Tämä ajoitusmenetelmä voi olla preemptiivinen tai ei-preemptiivinen. Se lyhentää merkittävästi muiden suoritusta odottavien prosessien keskimääräistä odotusaikaa.

SJF-aikataulutuksen ominaisuudet

• Jokaiseen työhön liittyy tietty suoritettava aikayksikkö.
• Tässä menetelmässä, kun suoritin on käytettävissä, seuraava prosessi tai työ, jolla on lyhin valmistumisaika, suoritetaan ensin.
• Se toteutetaan ei-ennaltaehkäisevällä käytännöllä.
• Tämä algoritmi on hyödyllinen eräajotyyppisessä käsittelyssä, jossa töiden valmistumisen odottaminen ei ole kriittistä.
• Se parantaa työtulosta suorittamalla ensin lyhyempiä töitä, joilla on useimmiten lyhyempi läpimenoaika.

Monitasoisten jonojen ajoitus

Tämä algoritmi erottelee valmiusjonon useisiin erillisiin jonoihin. Tässä menetelmässä prosessit osoitetaan jonoon prosessin tietyn ominaisuuden, kuten prosessin prioriteetin, muistin koon jne., perusteella.

Tämä ei kuitenkaan ole itsenäinen ajoitusalgoritmi, koska sen on käytettävä muuntyyppisiä algoritmeja töiden ajoittamiseen.

Monitasoisten jonojen aikataulutuksen ominaisuudet

• Useita jonoja tulisi ylläpitää prosesseille, joilla on yhteisiä ominaisuuksia.
• Jokaisella jonolla voi olla oma erillinen ajoitusalgoritminsa.
• Jokaiselle jonolle on määritetty prioriteetit.

Aikataulutusalgoritmin tarkoitus

Tässä ovat syyt ajoitusalgoritmin käyttöön:

• CPU käyttää ajoitusta tehokkuuden parantamiseksi.
• Se auttaa sinua jakamaan resursseja kilpailevien prosessien kesken.
• CPU:n maksimikäyttöaste saadaan aikaan moniohjelmoinnilla.
• Suoritettavat prosessit pidetään valmiusjonossa.

UKK