Vuoronnus

Vuoronnus eli skedulointi (engl. scheduling) tarkoittaa tietotekniikassa seuraavaksi suoritettavan työn, prosessin tai säikeen valintaa. Valinnan tekee vuorontaja eli skeduleri (engl. scheduler).

Vuoronnuksen eri tasoja

Vuoronnus tapahtuu varsinkin isoissa järjestelmissä usealla eri tasolla. Ylin taso, jota henkilökohtaisissa järjestelmissä ei yleensä ole tai sitä ei käytetä, on työn valinta ajoon. Työ (engl. job) tarkoittaa tässä ennalta valmisteltua ohjelman ajoa. Tällöin käyttäjä ei ohjaa ohjelman toimintaa, vaan ohjelma käynnistetään automaattisesti joko haluttuna aikana tai koneen kuormituksen sen salliessa. Ohjelman lähtötiedot annetaan työn kuvauksessa, samoin ohje siitä, minne tulokset talletetaan. Tämäntyyppisiä ohjelmia käytetään nykyään lähinnä ajastettuina ohjelmina, jolloin haluttu toiminto (esimerkiksi varmuuskopion otto massamuisteilta) halutaan tapahtuvan automaattisesti aina tiettynä aikana. Suurteholaskennassa voidaan käyttää myös kuormituksen perusteella tapahtuvaa jonon purkamista.

Kun käyttäjä käynnistää ohjelman tai työ on valittu ajoon, siitä tulee prosessi. Prosessien (tai säikeiden) vuorontaminen on se vuoronnustaso, johon tavallisesti viitataan. Tämäkin taso voidaan jakaa osiin siten, että käyttöjärjestelmän ytimessä on algoritmi, joka päättää, mikä on seuraava ajettava prosessi, mutta toinen, harvemmin ajettava prosessi voi muuttaa ajossa olevien prosessien prioriteetteja jonkin algoritmin mukaan. Tyypillisesti järjestelmässä on tällöin prosesseja, joiden prioriteetti on vakio, ja niitä, joiden prioriteettia voidaan muuttaa. Esimerkiksi laiteajurit ja prioriteetinlaskentaohjelma ovat sellaisia, joiden prioriteetin muutos voisi sekoittaa koko järjestelmän.

Säikeiden vuoronnus voidaan hoitaa joko käyttäjän tai käyttöjärjestelmän tasolla. Mikäli säikeitä vuoronnetaan käyttäjän tasolla, käyttöjärjestelmä vuorontaa prosesseja, ja prosessin sisällä oleva rutiini vuorontaa sen sisäisiä säikeitä. Tämän tavan varjopuolena on mm. se, että jos yksikin säie jää odottamaan oheislaitetta, koko prosessi jää odottamaan sitä, jolloin mikään säie ei pääse jatkamaan, ennen kuin oheislaite on vastannut. Toisaalta, jos prosessin sisäinen vuoronnus ei ole irrottavaa (engl. pre-emptive), tällä tavalla voidaan välttää monia rinnakkaisuuden tuomia ongelmia kuten poissulkeminen ja lukkiutuminen. Jos säikeitä vuoronnetaan käyttöjärjestelmän tasolla, ei prosesseja enää vuoronneta, vaan jokaisen prosessin sisällä on vähintään yksi säie. Tässä vaihtoehdossa säikeen tekemä oheislaitekutsu ei pysäytä koko prosessia. On myös mahdollista käyttää molempia tapoja yhtä aikaa.

Näiden lisäksi vuoronnukseen vaikuttaa se, miten muistinhallinta toimii.

Vuoronnusmenetelmiä

Jatkossa prosessilla viitataan pienimpään vuoronnettavaan yksikköön, joka monissa nykyjärjestelmissä on säie.

Vuoronnusmenetelmä voi olla joko irrottava (engl. pre-emptive) tai ei-irrottava. Irrottava vuoronnusmenetelmä tarkoittaa sitä, että käyttöjärjestelmä voi milloin tahansa vaihtaa ajossa olevan prosessin tilalle toisen. Jos järjestelmä ei ole irrottava, prosessi voi vaihtua vain ajossa olevan prosessin myötävaikutuksella. Käytännössä tämä tarkoittaa sitä, että prosessi tekee sellaisen käyttöjärjestelmäpyynnön, jota sen on jäätävä odottamaan tai että se kutsuu erityistä käyttöjärjestelmän palvelua (esimerkiksi engl. yield), jolla se ilmoittaa antavansa vuoron toiselle prosessille.

Toinen pääluokitustapa on vuoronnuksen dynaamisuus (engl. dynamic scheduling) ja staattisuus (engl. static scheduling). Dynaaminen vuoronnus tarkoittaa ajoaikana tehtävää vuoronnusta. Tällöin prosesseista ei tarvita yleensä muuta tietoa kuin mitä ajoaikana on voitu kerätä ja prioriteetilla on osoitettu. Staattinen vuoronnus tehdään etukäteen, ja sen tekemiseen tarvitaan tarkkoja tietoja prosessien käyttäytymisestä. Sen avulla voidaan kuitenkin osoittaa järjestelmän täyttävän ajoitukselle asetetut vaatimukset.

Menetelmien yhteydessä mainittu prioriteetti (engl. priority) eli etuoikeus ilmaistaan tavallisesti kokonaislukuna, mutta järjestelmästä riippuu, onko suuri arvo iso vain pieni prioriteetti. Esimerkiksi Unix-tyyppisissä järjestelmissä prosessien suurimmat prioriteetit ovat lukuarvoltaan negatiivisia.

Kiinteän prioriteetin menetelmät

Kiinteän prioriteetin (engl. fixed priority) menetelmässä jokaiselle prosessille on asetettu prioriteetti, jota ei ajon aikana muuteta.

Kiinteän prioriteetin menetelmässä ajossa on aina se prosessi, jonka prioriteetti valintavaiheessa on ollut korkein. Mikäli kyseessä on irrottavaa vuoronnusta käyttävä järjestelmä (engl. fixed priority pre-emptive scheduling, FPPE), ajossa olevan prosessin prioriteetti on aina suurin, sillä korkeamman prioriteetin prosessin herätessä käyttöjärjestelmä irrottaa alempiprioriteettisen prosessin ja antaa vuoron korkeimman prioriteetin prosessille.

Kiinteän prioriteetin menetelmä toimii hyvin pienissä järjestelmissä, joissa prosessit tunnetaan etukäteen. Erityisesti irrottavana se on yleisin reaaliaikainen vuoronnusmenetelmä sulautetuissa järjestelmissä. Se on myös helppo toteuttaa teknisesti.

Järjestelmän varjopuolena on se, että se ei ole tasapuolinen. Toisin sanoen jokin prosessi voi jäädä kokonaan ilman suoritinaikaa, ja syntyy niin sanottu nälkiintymistilanne. Menetelmä ei myöskään sovi kovin hyvin interaktiiviseen toimintaan.

Vaihtuvan prioriteetin menetelmät

Vaihtuvan prioriteetin (engl. dynamic priority) menetelmissä prosessien prioriteetteja muutetaan niiden käyttäytymisen mukaan.

Esimerkki: Unix-sukuisissa käyttöjärjestelmissä prosessin prioriteetti lasketaan sen perusteella, miten paljon se kuluttaa suoritinaikaa. Mitä enemmän aikaa kuluu, sitä pienempi prioriteetti. Tämä toimii hyvin interaktiivisessa toiminnassa, jossa suuri osa ajasta kuluu käyttäjän toimenpiteitä odottaessa, mikä tarkoittaa prioriteetin pysyvän korkeana. Näin käyttömukavuus kasvaa, kun vastaus tulee nopeasti. Pitkien laskenta-ajojen prioriteettia taas lasketaan, jotta muut toiminnot toimisivat häiriöttä. Järjestelmä on myös tasapuolinen, sillä jos prosessi ei saa aikaa, sen prioriteetti nousee automaattisesti, kunnes se taas alkaa saada aikaa.

Vaihtuvan prioriteetin järjestelmä ei sovi reaaliaikajärjestelmien vuoronnukseen, koska vasteaikoja ei voida taata prioriteettien muuttuessa.

Tämän takia joissain järjestelmissä korkeimmat prioriteettitasot ajetaan kiinteän prioriteetin vuoronnuksella, ja yksi näistä korkeaprioriteettisista prosesseista muuttaa tarvittaessa alemmalla prioriteetilla olevien ohjelmien prioriteetteja. Tällainen vuoronnus on esimerkiksi Windows NT -järjestelmässä ja sen jälkeläisissä.

Tyypillisesti vaihtuvan prioriteetin menetelmissä prioriteetit lasketaan uudestaan säännöllisin väliajoin. Näiden laskentojen välissä järjestelmä toimii kuin kiinteäprioriteettinen vuoronnus.

Jono- ja kiertovuorottelumenetelmät

Jonomenetelmässä (engl. first in, first out, FIFO, myös engl. first come, first served, FCFS) vuoron saa se prosessi, joka on odottanut pisimpään eli tullut jonoon ensimmäisenä. Saatuaan vuoron prosessia ajetaan, kunnes se itse luovuttaa vuoron pois (ei-irrottava vuoronnus).

Kiertovuorottelumenetelmässä (engl. round robin, RR) valinta tapahtuu samalla tavalla kuin jonomenetelmässä, mutta prosessi voi käyttää aikaa enintään jonkin tietyn aikaviipaleen verran. Sen jälkeen prosessia vaihdetaan, ja ajossa ollut prosessi laitetaan jonon viimeiseksi. Käytännössä se on jonomenetelmästä tehty irrottavaa vuoronnusta toteuttava menetelmä.

Kumpikaan järjestelmistä ei sovi reaaliaikakäyttöön. Jonomenetelmässä yksi prosessi voi viedä kaiken ajan, mutta ennen pitkää muutkin saavat vuoronsa. Kiertovuorottelu on tasapuolisempi, mutta senkin vasteajat ovat melko huonoja.

Nämä järjestelmät ovat helppoja toteuttaa mutta harvinaisia käytännössä. Niitä käytetään kuitenkin esimerkiksi prioriteettijärjestelmien kanssa ratkaisemaan, mikä samaprioriteettisista ohjelmista otetaan ajoon.

Ajoaikaan perustuvat menetelmät

Lyhyin tehtävä ensin (engl. shortest remaining time, SRT) -menetelmässä valitaan ajoon aina se työ, jonka arvioitu jäljellä oleva ajoaika on lyhin. Teoreettisesti menetelmä on hyvä, jos mittapuuna on suoritettujen töiden määrä aikayksikössä. Varjopuolena on se, että joka työstä tulisi tietää sen kesto. Sitä taas ei voi päätellä itse ohjelmasta, vaan käyttäjän pitää antaa aika-arvio. Menetelmä ei ole tasapuolinen, sillä pitkä työ voi jäädä aina lyhyempien töiden jalkoihin.

Menetelmää on vaikea soveltaa prosesseihin, ellei kyseessä ole pieni järjestelmä, jonka prosessit tunnetaan hyvin. Menetelmää käytetään yleensä töiden (eräajojen) vuoronnuksessa. Tällöin lyhyet työt on ajettu ensin, minkä jälkeen vuoro annetaan pitkille töille. Jotta käyttäjälle ei tulisi kiusausta laittaa ajoajaksi aina lyhyttä arviota, menetelmästä on versioita, jotka katkaisevat työn arvioidun ajan jälkeen.

Määräaikaan perustuvat menetelmät

Lähin määräaika ensin (engl. earliest deadline first, EDF) -menetelmässä ajoon valitaan se prosessi, jonka (seuraava) määräaika on lähinnä. Tarkoituksena on näin huolehtia siitä, että reaaliaikaisuus saadaan toteutettua. Tällaista vuoronnusta käyttävät järjestelmät ovat harvinaisia, vaikka menetelmä on teoriassa optimaalinen yksisuoritinjärjestelmissä.

Säännölliset, toistuvat työt

Mikäli järjestelmässä on vain periodisia (engl. periodic) eli sellaisia prosesseja, jotka toistuvat säännöllisin väliajoin ja joiden ajoaika tunnetaan, voidaan käyttää säännöllisiin, toistuviin tehtäviin perustuvaa menetelmää (engl. Rate-monotonic scheduling, RMS). Menetelmän yhteydessä ei saa käyttää rinnakkaisissa järjestelmissä käytettyjä prosessien välisiä synkronointimenetelmiä tai poissulkemista, jonka takia menetelmää sovelletaan yleensä ei-irrottavana. Menetelmää käytetään reaaliaikaisten, sulautettujen järjestelmien vuoronnusmenetelmänä.

Menetelmä sallii joitain satunnaisia töitä (engl. sporadic), kunhan niiden kokonaismäärä pysyy tarpeeksi alhaisena. RMS takaa vuoronnettavuuden, mikäli suorittimen käyttöaste reaaliaikaisten prosessien osalta jää alle 69 prosentin.

Menetelmää käytetään staattisen vuoronnuksen menetelmänä, jolloin voidaan etukäteen laskea, täyttääkö järjestelmä annetut reaaliaikavaatimukset.

Menetelmien käytöstä

Vain osa vuoronnusmenetelmistä sopii reaaliaikaiseen vuoronnukseen (engl. real-time scheduling). Menetelmiä myös yhdistetään toisiinsa esimerkiksi niin, että jokin menetelmä toimii päävalintana, ja jos se ei tuota yksikäsitteistä tulosta, käytetään toista menetelmää apuna.

Töiden vuoronnuksessa käytetään yleensä joko jonomenetelmää, kiinteää prioriteettia, lyhintä tehtävää ensin, lähin määräaika ensin tai näiden yhdistelmiä (esimerkiksi jonottava kiinteä prioriteetti, jolloin päävalinta tehdään prioriteetin mukaan ja samaprioriteettisen osalta jonottamalla).

Katso myös

• Moniajo