Prosessien vuoronnus ei ole täydellistä. Vuoronnus on optimointiongelma, jossa pyri-tään ottamaan huomioon halutut tavoitteet ja löytämään niihin ratkaisu, joka on mah-dollisimman lähellä optimaalista annetuilla rajoitteilla. (Robert & Vivien, 2010) Opti-maalinen ratkaisu on se, joka minimoi tai maksimoi halutun tavoitteen mukaisen met-riikan. Erilaisilla vuoronnusalgoritmeilla on erilaisia tavoitteita ja rajoituksia. Vuoron-timen on myös vaikea tietää, minkä prosessien suorittaminen näkyy käyttäjälle eniten ja saa tietokoneen toiminnan vaikuttamaan tehokkaammalta. Toisaalta vuorontamiseen liittyy paljon heuristisia algoritmeja, jotka eivät välttämättä tuota aina optimaalisin-ta tulosoptimaalisin-ta, vaan pyrkivät säästämään aikaa tuotoptimaalisin-taen riittävän hyvän tuloksen. Tällöin vuoronnin ei voi myöskään tietää, kuinka lähellä saatu ratkaisu on optimaalista.
Vuorontimella ei ole tietoa siitä, kuinka kauan työn suoritus kestää ja mitä töitä sen tar-vitsee ajoittaa myöhemmin. Työn suorituksen pituus selviää vasta, kun työ on valmis.
Vuoronnin tietää siis ainoastaan kullakin hetkellä olemassa olevat prosessit ja niiden tilan. (Albers, S. 2010) Tätä varten uutta prosessia luodessa vuoronnin lisää sen
kir-janpitoonsa. Tavallisesti vuoronnus toimii niin, että ohjelmille jaetaan aikaa viipaleina, joiden loputtua tarkastellaan uudestaan, mikä prosessi tulisi ajoittaa seuraavaksi vuo-rontimen tavoitteiden täyttämiseksi.
Aikaviipaleita varten käyttöjärjestelmällä on ajastin, joka antaa suorittimelle keskey-tyksen halutuin väliajoin. Keskeytys pysäyttää sitä käsittelevässä suoritinytimessä muun toiminnan ja alkaa suorittamaan käyttöjärjestelmän keskeytysten käsittelijää. Tä-mä osa tekee keskeytykseen liittyvät toiminnot, kuten vuoronnuksen. (Arpaci-Dusseau
& Arpaci-Dusseau, 2015) Keskeytykset aiheuttavat yleisrasitetta hidasten suoritusta, joten niiden tiheyden eli aikaviipaleen pituuden valinta on kompromissi vuoronnuksen responsiivisyyden ja suoritustehon välillä.
Vuoronnus voi olla irrottavaa (englanniksi pre-emptive), mikä tarkoittaa sitä, että pro-sessien vaihtaminen kesken niiden suorituksen on sallittua. Jos vuoronnus on ei-irrot-tavaa, niin suorituksen alettua prosessia ei vaihdeta toiseen, ennen kuin sen aikavii-pale on päättynyt. (Arpaci-Dusseau & Arpaci-Dusseau, 2015) Kumpikin vuoronnin ja suoritettava prosessi voivat erikseen päättää suoritettavan prosessin irrottamisesta. Pro-sessin vaihtamiseen liittyy aina yleisrasitetta, joka hidastaa suoritusta kokonaisuutena.
Prosessin vaihtamista käsitellään tarkemmin vähän myöhempänä.
Tavallisessa tietokoneen suorittimessa ytimiä voi olla esimerkiksi neljä kappaletta. Sen lisäksi, että suoritin sisältää useita ytimiä, siinä voi olla myös symmetrinen monisäi-keistys (englanniksi symmetric multithreading, lyhennetään SMT). Silloin samalle yti-melle voidaan ajoittaa useampi kuin yksi työ kerrallaan ja ydin voi suorittaa molem-piin töihin kuuluvia käskyjä samanaikaisesti. Käyttöjärjestelmän näkökulmasta mo-nisäikeistys näkyy useampana loogisena ytimenä, joista kullekin ajoitetaan yksi työ.
(Hennessy & Patterson, 2012) Tällöin jokainen looginen ydin voi yhden sekunnin ai-kana tarjota yhden sekunnin suoritinaikaa. Neliytimisessä kahden säikeen symmetris-tä monisäikeistyssymmetris-tä tukevassa suorittimessa voi suoritin yhden sekunnin aikana tarjota yhteensä kahdeksan sekuntia suoritinaikaa. Lisäksi on huomattava, että symmetrisessä monisäikeistyksessä työt jakavat ytimen resurssit keskenään, ja siksi samalla fyysisel-lä suoritinytimelfyysisel-lä suoritettavat työt eivät välttämättä edisty yhtä aikaa suoritettuina samalla nopeudella kuin peräkkäin suoritettuna. Kuitenkin jos työt ajoitettaisiin peräk-käin, niiden valmistumiseen saattaisi kulua kauemmin, sillä symmetrisen monisäikeis-tyksen ansiosta suoritin voi hyödyntää resurssinsa tehokkaammin.
Prosesseista
Tietokoneohjelmat ovat tietoa massamuistilla siihen asti, että käyttöjärjestelmä lataa ne keskusmuistiin ja luo niistä prosesseja, joita voidaan suorittaa. Prosessilla on oma osoiteavaruutensa, joka kertoo, mitä keskusmuistin alueita se pystyy käyttämään, se-kä tila. Prosessit myös säilyttävät tiedot tarpeellisista prosessorin rekisterien arvoista silloin, kun prosessia ei suoriteta. (Arpaci-Dusseau & Arpaci-Dusseau, 2015)
Prosessit mahdollistavat sen, että käyttöjärjestelmä pystyy vaihtamaan suoritettavaa ohjelmaa. Prosessit voivat olla kolmessa eri tilassa: valmiina suoritettavaksi, suorituk-sessa tai odottamassa. Kun prosessi on valmiina suoritettavaksi, vuoronnin voi ajoittaa sen halutessaan. Jos prosessi on suorituksessa, se on ajoitettuna ja voidaan irrottaa.
Prosessi voi olla myös odottamassa jotain tapahtuvan, kuten odottamassa levyltä tule-vaa tietoa. Vuoronnin voi vaihtaa prosessin tilaa näiden kolmen välillä siten, että suo-rituksessa olevasta prosessista voi tulla joko valmiina tai odottamassa oleva prosessi, valmiina olevasta prosessista suorituksessa oleva tai odottamassa olevasta prosessista valmiina oleva. Suorittimella on aina yksi prosessi suoritustilassa, joten vaihdettaessa pois tästä tilasta ajoitetaan suorittimelle jokin muu valmiina oleva prosessi. (Arpaci-Dusseau & Arpaci-(Arpaci-Dusseau, 2015)
Suorituksessa Valmiina
Odottaa aloitetaanI/O
valmisI/O Ajoitus
Irroitus
Kuva 1: Prosessien tilanvaihdokset. Kuva suomennettu Dusseau & Arpaci-Dusseau (2015) -kirjasta.
Kun prosessi vaihtaa suorituksesta toiseen tilaan, tehdään kontekstin vaihto
(englannik-si context switch). Tällöin nykyiset suorittimen rekisterit ja pinon osoite tallennetaan.
Niitä kutsutaan kontekstiksi. Koska tämän perään ajoitetaan toinen prosessi, palaute-taan sen jälkeen tämän toisen prosessin konteksti eli tallennetut arvot, jotta sen suoritus voi jatkua. (Arpaci-Dusseau & Arpaci-Dusseau, 2015)
Jo aiemmin todettiin, että yhdessä ohjelmassa on yksi tai useampi prosessi. Ohjelmat pystyvät luomaan – käyttöjärjestelmän avustuksella – itselleen lapsiprosesseja. Lapsi-prosessi voi olla saman ohjelman osa tai uuden ohjelman Lapsi-prosessi. Tästä muodostuu prosessien hierarkia, jota jotkin vuorontimet hyödyntävät toiminnassaan.
Joissain käyttötarkoituksissa prosessin sijaan puhutaan säikeistä. (Arpaci-Dusseau &
Arpaci-Dusseau, 2015) Säie on samankaltainen kuin prosessi, mutta yksinkertaisem-pi. Säikeet kuuluvat aina yhdelle prosessille, ne suoritetaan omilla suoritinytimillään ja ne jakavat osoiteavaruuden prosessinsa kanssa. Säikeiden avulla voidaan siis tehdä useampia ytimiä hyödyntäviä ohjelmia luomatta useita prosesseja. Linuxissa vuoron-nin kohtelee säikeitä ja prosesseja samalla tavalla (Jones, 2009).
Vuoronnuksen suureita
Jotta vuorontimen tavoitteita voitaisiin kuvata, on tarpeellista määritellä suureita. Täl-lainen suure on esimerkiksi jo aiemmin mainittu suoritinaika. Lisäksi nämä suureet ovat tarpeellisia myös vuorontimen ja laitteiston toimintaa mitattaessa. Siksi käytet-tävät suureet on valittava siten, että ne tukevat tutkittavia ominaisuuksia. Jo aiemmin kerrottiin suorittimen kapasiteetin hyödyntämisestä sekä erilaisista viiveistä.
Suorittimen kapasiteetin hyödyntämistä voidaan mitata esimerkiksi suoritustehon ja käyttöasteen avulla. Suoritusteho (englanniksi throughput) on kaikkien suoritettujen töiden volyymi (Albers, 2010). Prosessien vuoronnuksessa tämä voidaan määritellä ohjelmassa suoritettujen operaatioiden määränä aikayksikköä kohden. Käyttöaste tar-koittaa sitä, kuinka suuri osa käytettävissä olevasta suoritinajasta käytetään prosessien suoritukseen aikayksikköä kohti, eli käytännössä sitä, kuinka tarkkaan suorittimen ka-pasiteetti on käytössä. Käyttöaste ilmaistaan yleensä prosentteina. Käyttöasteen kaltai-nen suure on myös järjestelmän kuorma, joka mitataan suoritinaikaa tarvitsevien pro-sessien määränä mittausvälillä. Jos mittausvälillä on ollut jatkuvasti kaksi jatkuvasti suoritinaikaa tarvitsevaa prosessia sekä kolmas puolet ajasta, kuorma on kaksi ja puoli (2,5).
Ajoituksen hukkateho on vuorontimen käyttämän suoritinajan suhde töiden
suoritinai-kojen summaan. Tämä on tarpeellinen suure, sillä ajoitukseen käytetty suoritusaika on pois ohjelmille käytettävissä olevasta suoritusajasta. Käyttöaste ja ajoituksen hukka-teho kertovat yhdessä sen, kuinka hyvin vuoronnin pystyy hyödyntämään suorittimen laskentakapasiteetin.
Vuoronnuksen yksinkertaisimpia suureita on valmistumisaika (englanniksi turnaround time), joka tarkoittaa sitä, kuinka kauan työn suorituksen alusta työn valmistumiseen kului. Tällä voidaan mitata vuorontimen suorituskykyä. Kun vuoronnin saa ajoitetta-vakseen prosessin, joka voi olla uusi ajoitettava tai jo aiemmin ajoitettu muttei vielä valmistunut prosessi, kestää jonkin aikaa ennen kuin prosessia suoritetaan seuraavan kerran. Tätä aikaa kutsutaan vasteajaksi (englanniksi response time). (Arpaci-Dusseau
& Arpaci-Dusseau, 2015) Vasteaika on suure, jonka jotkin vuorontimet pyrkivät mi-nimoimaan saadakseen järjestelmän vastaamaan nopeammin käyttäjän tai ohjelmien toimintoihin. Jotkin reaaliaikavuorontimet pyrkivät optimoimaan näitä suureita.
Suorittimen toimintaan liittyy käsite kommunikaatioviive (englanniksi communication delay), joka tarkoittaa tiedonsiirron viivettä eri suoritinytimien välillä, kun yksi työ tarvitsee tietoa toisella ytimellä suoritettavalta prosessilta. Tällöin odottava työ ei voi jatkaa suoritustaan ennen toisen prosessin valmistumista, eli ennen kuin se saa tar-vitsemansa tiedon. (Köning & Girouddeau, 2010) Nämä viiveet voivat olla erilaisia eri suoritinytimien kesken riippuen suorittimen rakenteesta. Tästä kerrotaan enemmän kohdassa 2.3.
Jos prosessi ei ole suorituksessa, se odottaa. Tällöin prosessille kertyy odotusaikaa (englanniksi wait time). Toisinaan prosessin tarvitsee hakea tietoa esimerkiksi levyltä, eikä se pysty suorittamaan muuta toimintaa samaan aikaan. Tällöin ei tapahdu lasken-taa, joten levytoiminnan odottaminen on suoritustehon näkökulmasta haitallista. Siksi vuorontimet pyrkivät hyödyntämään päällekkäisyyttä (englanniksi overlap) eli siirtävät suorituksessa olevan prosessin odottamaan ja ajoittavat tilalle toisen prosessin, joka ei odota levytoimintaa, jolloin myös tämä suoritinaika saadaan hyödynnettyä. (Arpaci-Dusseau & Arpaci-(Arpaci-Dusseau, 2015) Yleensä odotusaikaa ei lasketa suorittimen käyttö-asteeseen, sillä kyseinen aika voidaan välttää päällekkäisyydellä. Joskus se kuitenkin lasketaan mukaan ja tässä tutkielmassa siitä käytetään nimitystä suorittimen kuorma.
Vuoronnuksen menetelmät
Vuoronnusta voidaan tehdä eri tavoin. Tavallisesti pyritään käyttämään hyvin
tunnettu-ja menetelmiä, jotka pystyvät toimimaan hyvin tilanteissa, jossa päätökset on tehtävä välittömästi ilman tietoa tulevaisuudesta. Käytännössä vuorontimet yhdistelevät näi-tä menetelmiä saavuttaakseen omien tavoitteidensa mukaisen tuloksen. Esittelen näi-tässä muutamia käytössä olevia menetelmiä, joita kohdassa 2.2 esiteltävät vuorontimet hyö-dyntävät.
Algoritmit perustuvat usein tietorakenteiden käyttöön. Vuoronnuksessa tarpeellisia tie-torakenteita ovat esimerkiksi jonot ja puut. Tietorakenteissa on tallennettuna alkioita, jotka tässä tapauksessa ovat tyypillisesti töitä eli prosesseja. Tietorakenne mahdollistaa näiden alkioiden lisäämisen ja poistamisen. Tietorakenteesta riippuen, ne voivat tarjota erilaisen aikavaativuuden, joka on yleensä kompromissi tarjottavien ominaisuuksien ja eri operaatioiden tehokkuuden välillä.
Vuoronnuksessa tarvitaan rakenteita, joihin alkiot voidaan tallentaa järjestyksessä, jos-sa ne tulevat suoritetuksi. Tällaista rakennetta kutsutaan usein prioriteettijonoksi, ja se voidaan toteuttaa useilla tavoilla. Yksi tapa on käyttää tasapainotettua puuta, johon al-kiot talletetaan järjestyksessä. Tasapainotetut puut ovat hakurakenteita, jossa haku ja lisäys tapahtuvat logaritmisessa ajassa puun alkioiden määrään nähden. Tällainen on esimerkiksi myöhemmin mainittava puna-musta puu.
Eräs yksinkertainen vuoronnusmenetelmä on nimeltään Round-Robin. Arpaci-Dusseau & Arpaci-Arpaci-Dusseaun (2015) mukaan Kleinrock (1964) oli yksi ensimmäisistä, joka määritteli tämän menetelmän. Round-Robin-menetelmää voidaan käyttää proses-sien ajoittamisen lisäksi muissa ajoitustehtävissä. Round-Robinissa resurssit jaetaan jaksoihin ja jokainen työ saa vuoron perään käyttöönsä yhden jakson. Mikäli työ ei valmistu jakson aikana se laitetaan jonon perälle ja ajoitetaan uudestaan muiden töi-den jälkeen. Jos työ valmistuu, sitä ei tarvitse ajoittaa enää uudelleen. Tätä toistetaan kunnes kaikki työt ovat valmistuneet. Round-Robin minimoi keskimääräisen vasteajan, mutta liian usein tehtävät kontekstinvaihdot voivat hidastaa suoritusta. Tätä vuoronnus-menetelmää on käytetty myös alakohdassa 2.2.2 esiteltävässä muQSS-vuorontimessa.
Toinen vielä yksinkertaisempi vuoronnusmenetelmä on jonovuoronnus (alkuperäiseltä nimeltään First In, First Out, lyhennetään FIFO). Siinä työt laitetaan jonoon luomisjär-jestyksessään ja ne suoritetaan jonosta poistettaessa kokonaan ilman irrotusta. (Arpaci-Dusseau & Arpaci-(Arpaci-Dusseau, 2015) Tämä ei ole prosessien vuoronnuksessa yleensä järkevä vuoronnustapa, sillä muut prosessit joutuvat odottamaan vuoroaan jopa pitkiä aikoja eli vasteaika on huono, mutta sitä käytetään osana yksinkertaisia vuorontimia
esimerkiksi reaaliaikavuoronnuksessa.
Vuoronnuksessa on käsite reiluus (englanniksi fairness), jolla tarkoitetaan sitä, kuinka tasapuolisesti vuoronnus toimii eri töitä kohtaan. Jos vuoronnuksessa on useita tavoit-teita, reiluudelle ei ole vain yhtä hyväksyttyä määritelmää, vaan se voidaan määritellä useilla tavoilla. (Dutot& al., 2010) Vuorontimen on tehtävä kompromisseja reiluuden ja suorituskyvyn välillä: suorituskyvyn suosiminen voi johtaa reiluuden vähenemiseen.
Round-Robin on reilu vuoronnusmenetelmä, koska se valitsee aina vähemmän suori-tinaikaa saaneen prosessin ja siten jakaa suoritinajan tasaisesti. Samalla se kuitenkin hukkaa suoritustehoa usein tapahtuvien kontekstinvaihtojen vuoksi. (Arpaci-Dusseau
& Arpaci-Dusseau, 2015)
Perusidea reilussa vuorontamisessa on käyttää sellaista metriikkaa, jolla uutta proses-sia ajoitettaessa pyritään joka kerta aiempaa reilumpaan tilanteeseen. Aina uutta työtä valitessa valitaan se prosessi, jota on tähän mennessä metriikan mukaan vuoronnettu kaikkein vähiten reilusti. Tällöin seuraavalla kerralla kyseinen prosessi ei ole enää se, jota on vuoronnettu vähiten reilusti. Tämä ei kuitenkaan riitä tekemään kaikesta vuo-ronnuksesta reilua. Tilanteessa, jossa yksi ohjelma luo monia prosesseja, kyseinen oh-jelma saisi enemmän prosessoriaikaa kuin ohoh-jelma, jolla on vain yksi prosessi. Tämän ongelman ratkaisemisesta kerrotaan tarkemmin CFS-vuorontimen yhteydessä alakoh-dassa 2.2.1.
Erityisesti reaaliaikavuoronnuksessa käytetään aikaisimman aikarajan algoritmia (englanniksi earliest deadline first, lyhyesti EDF). Aikaraja tarkoittaa aikaa, johon mennessä tehtävän tulisi valmistua. Tehtävät vuoronnetaan järjestyksessä aikarajojen mukaan niin, että aina vuoronnetaan se prosessi, jonka aikaraja täyttyy seuraavana.
EDF-algoritmin toiminnan edellytyksenä on, että suorittien käyttöaste on korkeintaan täysi. Jos optimaalisuus määritellään vuorontimen pystyvyytenä vuorontamaan tehtä-vät annettuja vaatimuksia rikkomatta, EDF on optimaalinen. (Liu & Layland, 1973;
Linux, 2018, ks.Documentation/scheduler/sched-deadline.txt).