Linuxin vuorontimen soveltuvuus ja säätäminen pelikäyttöön
Tomi Leppänen
Pro gradu -tutkielma
Tietojenkäsittelytieteen laitos Tietojenkäsittelytiede
Toukokuu 2018
ITÄ-SUOMEN YLIOPISTO, Luonnontieteiden ja metsätieteiden tiedekunta, Joensuu Tietojenkäsittelytieteen laitos
Tietojenkäsittelytiede
Opiskelija, Tomi Leppänen: Linuxin vuorontimen soveltuvuus ja säätäminen pe- likäyttöön
Pro gradu -tutkielma, 50 s.
Pro gradu -tutkielman ohjaajat: FT Simo Juvaste Toukokuu 2018
Tiivistelmä: Linuxin vuoronnin on kehitetty toimimaan hyvin tavanomaisissa työpöy- dän ja palvelimen kuormissa. Tässä tutkielmassa Linuxin vuorontimen toimintaa tutki- taan pelikäytön näkökulmasta. Tutkielmassa kerrotaan yleisemmin prosessien vuoron- tamisesta ja käydään läpi Linuxin oman vuorontimen (CFS) sekä Linuxille kehitetyn vaihtoehtoisen (muQSS) vuorontimen toimintaa. Lisäksi käsitellään pelien rakennetta säikeistyksen ja samanaikaisen suorituksen näkökulmasta sekä pelien reaaliaikaises- ta luonteesta johtuvia erityisiä vaatimuksia vuoronnukselle. Tutkielman kokeellisessa osassa vuorontimien toimintaa ja eroavaisuuksia selvitetään mittaamalla vuorontimien suoritustehoa, suoritinkäyttöä ja säikeiden siirtymistä suoritinytimien välillä. Mittauk- sista todetaan, että vuorontimen vaihtamisella tai sen tavanomaisimmilla asetuksilla on hyvin vähän käytännön vaikutusta pelien suorituskykyyn mittauksissa käytetyllä lait- teistolla. Lisäksi vuorontimien toimintaa tutkivissa erillisissä mittauksissa todetaan, et- tä vuorontimien toiminnassa on eroa sekä ohjelmien prosessien pysyvyydessä samalla suoritinytimellä että suorittimen kuormassa ja näitä eroja voidaan havaita mittaamalla.
Linuxin CFS-vuoronnin pystyy säilyttämään prosessit samalla ytimellä paremmin kuin muQSS-vuoronnin. Prosessin prioriteetin muuttamisesta ei myöskään ole merkittävää hyötyä pelien suoritustehon nostamiseksi.
Avainsanat: Linux, pelit, suorituskykymittaukset, vuoronnin, vuoronnus ACM-luokat (ACM Computing Classification System, 2012 version):
• Software and its engineering~Scheduling
• Applied computing~Computer games
• Theory of computation~Scheduling algorithms
• Software and its engineering~Multiprocessing / multiprogramming / multitas- king
UNIVERSITY OF EASTERN FINLAND, Faculty of Science and Forestry, Joensuu School of Computing
Computer Science
Student, Tomi Leppänen: Suitability and configuration of Linux’s scheduler for gaming
Master’s Thesis, 50 p.
Supervisors of the Master’s Thesis: PhD Simo Juvaste May 2018
Abstract: The scheduler of Linux is designed to work well on typical desktop and ser- ver workloads. On this thesis the behavior of the scheduler is investigated on gaming tasks. Thesis discusses more generally about process scheduling and describes Linux’s scheduler (CFS) and an alternative scheduler (muQSS). In addition the composition of games is discussed from the point of threading and concurrent computing. Also special requirements for scheduling due to real-time nature of games are discussed.
In the experimental part of the thesis, the behavior and differences of the schedulers are examined by measuring the performance, CPU utilization and movement of tasks between cores. The result is that switching schedulers or their typical parameters have very little effect on game performance with the hardware used in the tests. In addition the results from separate measurements tell that there are differences between the sche- dulers in their ability to keep tasks on same cores and in observed CPU load and these differences can be measured. CFS scheduler of Linux can keep processes on the same core more often than muQSS scheduler. Changing process priorities do not give any significant advantage to game performance.
Keywords: benchmarking, games, Linux, scheduler, scheduling
CR Categories (ACM Computing Classification System, 2012 version):
• Software and its engineering~Scheduling
• Applied computing~Computer games
• Theory of computation~Scheduling algorithms
• Software and its engineering~Multiprocessing / multiprogramming / multitas- king
Lyhenneluettelo
CCX AMD:n käyttämä nimitys suoritinydinten ryhmästä Ryzen-prosessoreissa.
CFS Completely Fair Scheduler, Linuxin oletusvuoronnin.
FIFO First In First Out, vuoronnusmenetelmä sekä tietorakenne, jota kutsutaan myös jonoksi.
muQSS Multiple Queue Skiplist Scheduler, vaihtoehtoinen vuoronnin Linuxille.
NUMA Non-Unified Memory Architecture.
PTS Phoronix Test Suite.
SMP Symmetrinen moniprosessointi.
SMT Symmetrinen monisäikeistys.
Sisältö
1 Johdanto 1
2 Vuoronnin 5
2.1 Prosessien vuorontaminen . . . 5
2.2 Linuxin vuorontimet . . . 11
2.2.1 CFS . . . 12
2.2.2 muQSS ja BFS . . . 15
2.2.3 Reaaliaikavuorontimet . . . 17
2.3 Suorittimen rakenteen vaikutus . . . 18
3 Pelikäytön vaatimukset 22 4 Mittaukset 28 4.1 Suorituskykytestit ja mittaukset . . . 28
4.2 Testiympäristö . . . 33
4.3 Tulokset . . . 35
5 Johtopäätökset 44
Viitteet 48
1 Johdanto
Tietokoneissa on laitteisto ja ohjelmisto. Ohjelmiston keskeisin osa on käyttöjärjes- telmä, joka huolehtii varusohjelmien ja laitteiston välisestä yhteistoiminnasta. Kaikki tietokoneen ohjelmistot koostuvat käskyistä. Laitteiston keskeisimpiä osia on suoritin, joka suorittaa näitä käskyjä mahdollistaen tietokoneen toiminnan.
Nykyaikaiset käyttöjärjestelmät pystyvät suorittamaan samanaikaisesti ohjelmia sa- malla suoritinytimellä vaihtamalla kulloinkin suoritettavaa ohjelmaa nopeasti. Ohjel- man valinta tehdään läpinäkyvästi niin, ettei käyttäjä huomaa sitä, ja suoritettava oh- jelma voikin vaihtua jopa satoja kertoja sekunnissa. Suoritettavan ohjelman valintaa ja sen vaihtamista kutsutaan ajoittamiseksi ja vuorontamiseksi. Näistä tehtävistä vastaa tietokoneen käyttöjärjestelmän vuorontimeksi kutsuttu osa. Ajoittamista voidaan käsi- tellä myös muissa yhteyksissä kuin tietokoneiden käyttöjärjestelmän toiminnasta pu- huttaessa. Tässä tutkielmassa ajoittamiseen ja vuorontamiseen perehdytään kuitenkin ainoastaan tietokoneen ohjelmien näkökulmasta.
Suorittimissa on nykyään tyypillisesti kaksi tai useampia suoritinytimiä, jolloin jokai- nen suoritinydin pystyy toisistaan riippumatta suorittamaan eri tehtävää. Tätä kutsutaan symmetriseksi moniprosessoinniksi (englanniksi symmetric multiprocessing, lyhenne- tään SMP). (Hennessy & Patterson, 2012) Tätä termiä käytetään myös tilanteessa, jos- sa tietokoneessa on useita erillisiä prosessoreja, jotka pystyvät toimimaan toisistaan riippumatta, vaikka niistä jokaisessa olisi vain yksi ydin.
Suoritinydinten välistä kommunikointia varten suorittimessa on väyliä. Suorittimen ra- kenteesta riippuen yhteydet eri ytimien välillä voivat olla samanlaisia, tai niissä voi olla eroja kaistan tai viiveiden suhteen. Kaista ratkaisee sen, paljonko tietoa väylä voi siirtää aikayksikköä kohden, ja viive sen, kuinka nopeasti mitään tietoa voidaan siirtää väylän yli. Tietokoneissa on myös keskusmuisti, jossa suoritettavat ohjelmat ja käytössä oleva data säilytetään käytön aikana. Suoritin kytkeytyy keskusmuistiin muistiväylällä. Myös kaistanleveys ja viive muistiin tai sen osiin voi olla erilainen eri suoritinytimillä. Täl- laiset hierarkkiset rakenteet ovat vielä verrattain harvinaisia kotitietokoneissa, vaikka ne ovatkin tavallisia palvelimissa ja sitä suuremmissa tietokoneissa. Koska muistiväylä on hitaampi kuin suorittimen sisäiset väylät, suorittimissa on eri tasoisia välimuisteja, jotka pyrkivät piilottamaan muistin hitauden. Kaikki nämä laitteistosta johtuvat erot lisäävät vuoronnuksen haasteita ja vaikuttavat ohjelmien suorituskykyyn.
Yhtä ainoaa oikeaa tapaa tehdä vuoronnus ei ole, vaan vuorontimen on otettava huo- mioon sekä laitteisto että ohjelmisto, jotta se voisi toimia optimaalisesti. Sekä laitteis- ton että ohjelmiston suunnittelu vaikuttaa siihen, millainen vuoronnusalgorimi tuottaa optimaalisimman tuloksen. Erilaisista lähestymistavoista johtuen vuorontimien välillä voi olla eroa siinä, kuinka tehokkaasti ne hyödyntävät suorittimen resursseja ja kuinka ne ohjaavat säikeitä eri suoritinytimille. Jotkin vuorontimet saattavat pyrkiä ohjaamaan säikeitä uudestaan samoille ytimille, jotta suorittimen välimuistien hyödyntäminen oli- si mahdollisimman tehokasta. Tämä voi vaikuttaa positiivisella tai negatiivisella taval- la suorittimen kapasiteetin hyödyntämiseen ja siten ohjelman suorituksen nopeuteen.
Vuorontimet voivat myös vaihtaa suoritettavaa tehtävää eri nopeudella, mikä vaikuttaa vasteaikaan.
Tietokoneita käytetään monenlaisiin tehtäviin, joista viihdekäyttö on yksi tavallisim- pia. Viihdekäytön alalajina pelikäyttö on saanut jatkuvasti lisääntyvää suosiota jo pian kotitietokoneiden markkinoille tulon jälkeen. Pelikäytössä tietokoneilla suoritetaan eri- tyisiä ohjelmia, pelejä, joiden tehtävänä on tyypillisesti viihdyttää käyttäjäänsä. Nykyi- sin pelejä pelataan myös ammattimaisissa kilpailuissa rahapalkintoja vastaan, ja täl- löin puhutaan elektronisesta urheilusta. Pelejä on monenlaisia, ja monet niistä eroa- vat useimmista muista ohjelmista siinä, miten ne hyödyntävät tietokoneen laitteistoa ja millaisia vaatimuksia ne asettavat tietokoneen laitteistoille tai muille ohjelmistoille esimerkiksi reaaliaikaisuusvaatimusten osalta. Tässä tutkielmassa perehdytään siihen, millaisia nämä vaatimukset ovat ja kuinka vuorontimet ottavat ne huomioon.
Linux on käyttöjärjestelmäydin, jonka ympärille on rakennettu lukuisia käyttöjärjes- telmiä. Näitä Linux-käyttöjärjestelmiä käytetään erityisesti palvelimissa, mutta niillä on käyttökohteensa myös työasemissa sekä kotikäyttäjän työpöydällä. Yksi viimeisim- mistä Linuxin käyttökohteista on pelikäyttö, jossa Linux on ollut hyvin marginaalisessa roolissa kotitietokoneissa enemmän käytettyjen käyttöjärjestelmien rinnalla. Nykyään Linux-käyttöjärjestelmille julkaistaan huomattavan paljon enemmän pelejä kuin ennen.
Koska Linuxin ensisijaiset käyttökohteet ovat tyypillisesti palvelimissa, ja Linuxin on tarpeen skaalautua niinkin suuriin järjestelmiin kuin kymmeniä tuhansia suoritinytimiä sisältävät supertietokoneet, voidaan kysyä, soveltuuko Linux optimaalisesti kotitieto- koneella tapahtuvaan pelikäyttöön. Yhtä lailla, koska vuorontimien tulee toimia usei- den eri ohjelmien kanssa, ne eivät voi olla täydellisen optimoituja yhteen käyttötar- koitukseen, vaan on tehtävä kompromisseja. Tässä tutkielmassa on tarkoitus selvittää, kuinka hyvin Linuxin vuoronnin pystyy vastaamaan pelikäytön tarpeisiin.
Avoimen lähdekoodin kehitystyön malliesimerkkinä, Linux soveltuu hyvin tutkimus- kohteeksi, sillä sen toiminnasta ja kehityksestä on saatavilla huomattavasti tietoa. Li- nuxin lähdekoodi ja dokumentaatio ovat vapaasti saatavilla, ja juuri lähdekoodin saata- vuus mahdollistaa Linuxin vuorontimeen tehtävät muutokset, jotka ovat edellytyksenä tässä tutkielmassa tehtäville testeille.
Tutkimuskysymyksistä
Tämä tutkielma perustuu kirjallisiin lähteisiin sekä tekemiini mittauksiin Linuxin vuo- rontimen toiminnasta. Tutkielman tutkimuskysymykset käsittelevät Linuxin vuoron- timen toimintaa sekä käytetyn testilaitteiston arkkitehtuurin mahdollisia vaikutuksia vuoronnukselle. Linuxin joustavuus mahdollistaa myös vuorontimen vaihtamisen, ja yhtenä tutkielman tavoitteena onkin selvittää, eroaako vaihtoehtoisen vuorontimen toi- minta Linuxin oletusvuorontimesta esimerkiksi säikeiden jakamisen, vuoronnuksen viiveiden tai suorittimen resurssien hyödyntämisen osalta ja mitä merkitystä näillä eroilla on pelikäytölle.
Tutkielman kokeellisessa osassa tarkoitus on mittaamisen lisäksi testata, voidaanko vuorontimen tyypillisimpiä parametreja muuttamalla parantaa suorittimen resurssien hyödyntämistä. Esimerkiksi taustaprosesseille annettavan suoritinajan suhdetta suori- tuksessa olevan ohjelman suoritusaikaan voidaan muuttaa. Lisäksi mitataan vuoronti- men toimintaa erilaisilla kuormilla, kuten erilaisilla määrillä suoritettavia prosesseja, mikä saattaa muuttaa suorittimen käyttöä. Vuorontimissa on myös muita vuoronnin- kohtaisia säätömahdollisuuksia, joiden vaikutusta tutkitaan.
Kokeellisesti tutkittavien asioiden lisäksi selvitetään, miten suorittimen rakenteelliset ominaisuudet, kuten välimuistien ja väylien kytkentä suoritinytimien kesken, vaikutta- vat vuorontamiseen. Näillä asioilla voi olla merkitystä sille, kuinka nopeasti eri ytimillä suoritettavat ohjelmat voivat kommunikoida keskenään. Jotta ohjelmat toimisivat mah- dollisimman tehokkaasti, on vuorontimen osattava ottaa myös tämä huomioon. Siksi sen selvittäminen on hyödyllistä vuorontimen optimaalisen toiminnan varmistamisek- si.
Terminologiasta
Vuoronnuksesta ei ole kirjoitettu paljoa suomeksi eikä siinä käytetty suomenkielinen termistö ole vakiintunut. Tutkielman lähdemateriaalina käytetyt teokset ovat englan- ninkielisiä. Tästä syystä tutkielmassa käytettyä termistöä on etsitty vaihtelevista läh-
teistä sekä tarvittaessa keksitty itse. Suomennoksien lähteinä on käytetty vaihtelevissa määrin Tampereen teknillisen yliopiston luentomateriaaleja (Tut 2017a; Tut 2017b) se- kä Internet-sanakirjoja ja -tietokirjoja. Tutkielmassa käytetyt käsitteet määritellään nii- tä ensimmäistä kertaa käytettäessä, ja niille mainitaan myös kirjallisuudessa esiintyvä englanninkielinen vastine.
Tutkielmassa esiintyvät luvut pyritään esittämään käyttäen ISO/IEC 80000 -standardin mukaisia kertoimia, jotka perustuvat SI-järjestelmään. SI-järjestelmä määrittelee esi- merkiksi, että kilo tarkoittaa tuhatta (103) eli kilotavu on tuhat tavua ja lyhennetään kB.
Koska SI-järjestelmässä ei määritellä binäärisiä kertoimia, niille käytetään ISO/IEC 80000 -standardin erikseen määrittelemiä kertoimia. Ne erottuvat kymmenkantaisista etuliitteistä lyhenteeseen lisätyllä i-kirjaimella. Esimerkiksi kibi on etuliite kertoimelle 210, jolloin kibitavu on 1024 tavua ja lyhennetään kiB. Binäärisiä kertoimia käytetään erityisesti muistin määrään viitatessa.
Tutkielmassa on seuraavana luku, jossa kerrotaan ajoittamisesta, Linuxin eri vuoron- timista sekä käytetyn suorittimen vaikutuksesta vuorontamiseen. Kolmantena on luku pelikäytöstä ja sen vaatimuksista vuorontamiselle. Toiseksi viimeisessä luvussa ker- rotaan tehdyistä mittauksista sekä niistä saaduista tuloksista, ja lopuksi viidennessä luvussa käydään läpi tutkielman johtopäätökset.
2 Vuoronnin
Vuoronnuksen perusyksiköitä ovat työt, käyttäjät ja resurssit. Tietokoneiden tapaukses- sa vuoronnuksessa käyttäjät ovat tietokoneohjelmia, töitä kutsutaan näiden ohjelmien prosesseiksi ja resurssit ovat suoritinaikaa. Tietokoneohjelmassa on yksi tai useampi prosessi. Prosessin käsite määritellään tarkemmin myöhemmin kohdassa 2.1. Vuoron- nuksessa näille prosesseille jaetaan suoritinaikaa eli sitä, minkä verran kutakin pro- sessia suoritetaan. Yksi sekunti suoritinaikaa tarkoittaa, että prosessia suoritetaan tai on suoritettu yhdellä ytimellä yksi sekunti. Käyttöjärjestelmän vuoronnin pitää kirjaa prosesseista ja pyrkii huolehtimaan siitä, että tietokoneen ohjelmat ja näiden prosessit saavat tarvitsemansa suoritinajan.
Tässä luvussa kerrotaan vuorontimen toiminnasta, siis ajoituksesta ja vuorontamises- ta. Lisäksi esitellään Linuxin oletusvuoronnin ja vaihtoehtoiset vuorontimet, joita Li- nuxissa voidaan käyttää. Samalla perehdytään niiden eroavaisuuksiin ja siihen, mil- laiseen käyttöön ne ovat alkujaan suunniteltu. Lisäksi käsitellään sitä, kuinka käytetty suoritin voi vaikuttaa vuorontamiseen.
2.1 Prosessien vuorontaminen
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 tulosta, vaan pyrkivät säästämään aikaa tuottaen 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äikeistystä 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ä suoritinytimellä 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-Dusseau, 2015)
Suorituksessa Valmiina
Odottaa aloitetaanI/O
valmisI/O Ajoitus
Irroitus
Kuva 1: Prosessien tilanvaihdokset. Kuva suomennettu Arpaci-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 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-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 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-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-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 ohjelma, 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).
2.2 Linuxin vuorontimet
Linuxin vuoronnin on uudistunut useaan kertaan. Linuxin versiossa 1.2 se oli yksin- kertainen Round-Robin-menetelmään perustuva vuoronnin, joka oli hyvin nopea. Ver- siossa 2.2 vuorontimeen lisättiin SMP-tuki moniprosessorikoneille. Suurempi uudis-
tus tehtiin versiossa 2.4, jonka uusi vuoronnin kävi kaikki prosessit läpi, valitakseen optimaalisimman vaihtoehdon seuraavaksi suoritettavaksi prosessiksi. Tämä ratkaisu oli tehoton, eikä skaalautunut hyvin prosessien määrän mukaan. Lisäksi se ei osannut hyödyntää moniprosessorikoneita tehokkaasti. Versiossa 2.6 vuoronnin päivitettiin ver- sioon, joka valitsee suoritettavan tehtävän vakioajassa, mikä teki siitä tehokaan aika- vaativuuden näkökulmasta. Siinä oli mukana heuristiikka tunnistamaan, onko tehtävä suorittimen vai IO:n rajoittama. Monimutkaiset heuristiikat tekivät tästä vuorontimesta kookkaan ja hankalan ylläpidettävän. (Jones, 2009)
Linux sai viimeisimmän vuorontimensa, nimeltään Completely Fair Scheduler (lyhyes- ti CFS), vuonna 2007 ja samalla modulaarisen vuoronninarkkitehtuurin. Modulaarinen arkkitehtuuri tarkoittaa sitä, että Linuxiin on mahdollista ottaa käyttöön eri vuoronnus- menetelmiä samanaikaisesti tai vaihtaa vuoronninta tarvittaessa. Ohjelma voidaan siir- tää vuorontimelta toiselle ajonaikaisesti, ja vuorontimien prioriteetteja eli sitä, missä järjestyksessä vuorontimet saavat vuorontaa, voidaan vaihtaa käännönaikaisesti. Mo- dulaarista arkkitehtuuria on vastustettu aiemmin, sillä se on monimutkaistanut ohjel- makoodia ja siten vaikeuttanut ylläpidettävyyttä. (Corbet, 2007) Modulaarinen vuo- ronninarkkitehtuuri mahdollistaa myös tässä tutkielmassa tehtävät vertailut Linuxin eri vuorontimien välillä. Huomattavaa on, että vuorontimia voidaan vaihtaa käytön aikana ja eri prosessit voidaan määrittää vuoronnettavaksi käyttäen eri toimintatapaa (Linux man-pages, 2018) (sched(7)-man-sivu). Seuraavaksi käsitellään Linuxissa käytettäviä vuorontimia.
2.2.1 CFS
Completely Fair Scheduler on Linuxin ollut Linuxin oletusvuoronnin versiosta 2.6.23 alkaen (Linux, 2018, ks.Documentation/scheduler/sched-design-CFS.txt) ja se perus- tuu Con Kolivasin ja Ingo Molnarin työhön. Nimensä mukaisesti tämä vuoronnin pyr- kii jakamaan prosessoriaikaa tasaisesti eri prosessien kesken. Yksinkertaisimmillaan se tarkoittaa sitä, että kulloinkin vähiten reilusti kohdeltu prosessi saa seuraavaksi suoritinaikaa. (Jones, 2009) Linuxin dokumentaatiossa määritellään käsite virtuaali- nen suoritusaika (virtual runtime), joka on määritelty käyttäen mallina ideaalista mo- nisuorittavaa prosessoria, mutta on käytännössä määriteltävissä prosessien suoritusai- kana normalisoituna suoritettavien prosessien summalla. Tätä arvoa käytetään suoritet- tavan prosessin valinnassa. (Linux, 2018, ks.Documentation/scheduler/sched-design-
CFS.txt) CFS käyttää prosessien prioriteetteja ohjaamaan virtuaalisen suoritusajan van- henemista. Korkeamman prioriteetin ohjelmat säilyttävät virtuaalisen suoritusaikansa kauemmin ja siten pystyvät saamaan enemmän myös todellista suoritinaikaa. (Jones, 2009)
Tämä vuoronnin pitää kirjaa prosesseista käyttäen puna-mustaa puuta, jossa prosessit ovat järjestetty niiden saaman suoritusajan mukaan. Suorituksen loputtua tehtävän saa- maa suoritusaikaa kasvatetaan ja se sijoitetaan takaisin puuhun, jolloin se siirtyy puus- sa oikeammalle aiempaan sijaintiin nähden ja siten myöhemmäksi vuoronnusjärjestyk- sessä. Seuraavaksi suoritettavaksi prosessiksi valitaan puun vasemmanpuolimmaisim- man alkion prosessi. (Jones, 2009) Puna-mustassa puussa nämä molemmat operaatiot voidaan tehdä tehokkaasti logaritmisessa ajassa alkioiden, eli tässä prosessien, mää- rään nähden, mikä ei ole yhtä tehokasta kuin vakioaikainen valinta, mutta kuitenkin paljon tehokkaampaa kuin lineaarisessa ajassa tehtävä valinta, jollaista Linuxin aiempi vuoronnin käytti.
CFS-vuoronnin huomioi myös prosessien odotusajan. Jos prosessi ei pysty hyödyn- tämään sille annettua suoritinaikaa, vaan irrottaa itsensä, se saa tämän suoritusajan käyttöönsä myöhemmin. Tällöin tämäkin prosessi saa tasapuolisesti prosessoriaikaa käyttöönsä. (Jones, 2009) Tästä toiminnosta käytetään englanniksi nimitystä sleeper fairness, jonka voisi suomentaa reiluudeksi nukkujia kohtaan.
CFS-vuorontimen uusi ominaisuus on ryhmissä vuorontaminen, jonka tavoitteena on tehdä vuorontamisesta reilumpaa. Tähän käytetään Linuxissa olevia cgroups-ryhmiä.
Koska prosessit ovat aina toisen prosessin käynnistämiä, ne muodostavat hierarkki- sen kokonaisuuden. Vuorontamalla näille prosessien ryhmille tasaisesti suoritinaikaa, ei yksittäinen paljon lapsiprosesseja luova ohjelma saa enemmän suoritinaikaa, kuin yksittäistä prosessia käyttävä ohjelma, jolloin reiluus ohjelmien välillä säilyy. Näitä prosessien hierarkioita voidaan myös muokata, ja siten muuttaa tapaa, jolla suoritin- aikaa jaetaan. (Jones, 2009) Muokkaamalla on ehkä mahdollista parantaa käyttäjälle tärkeiden tehtävien suoritustehoa jakamalla suoritinaika paremmin näiden tehtävien ja taustalla toimivien prosessien kesken. Ryhmien avulla voidaan esimerkiksi antaa oh- jelman prosesseille suurempi prioriteetti.
Hierarkkiseen vuoronnukseen perustuu myös autogroup-ominaisuus, jossa käyttäjän ohjelmille luodaan omat ryhmänsä niiden käynnistyessä ja kaikki ohjelman prosessit sijoitetaan kyseiseen ryhmään. Sillä pyritään estämään taustalla toimivaa monisäikeis-
50 %
lapsi- prosessi
12,5 %
lapsi- prosessi
12,5 %
lapsi- prosessi
12,5 %
Ohjelma A
prosessi
12,5 % 50 %
Ohjelma B
prosessi
50 %
Ohjelma A:n ryhmä Ohjelma B:n ryhmä
Kuva 2: Prosessien hierarkia ja suoritinajan jakautuminen yksinkertaistettuna.
tä ohjelmaa hidastamasta käyttäjälle näkyviä ohjelmia ja siten parantamaan käyttöko- kemusta. Autogroup-ryhmille voidaan myös määritellä oma prioriteetti, jolla voidaan muuttaa ryhmien välistä suoritinajan jakoa. Cgroup-ryhmien määrittely ohittaa au- togroups-ryhmät. (Linux, 2018, ks. Documentation/scheduler/sched-design-CFS.txt) Tämä ryhmittely eroaa aiemmin mainitusta cgroups-ryhmistä siinä, että tällä on tar- koitus parantaa työpöytäkäytössä responsiivisuutta ja toiminta on automaattista.
CFS-vuoronnin on suunniteltu käytettäväksi myös kotitietokoneissa ja työasemissa, joissa responsiivisuus on tärkeää eli tietokoneen on vastattava viivyttelemättä käyttä- jän syötteisiin. Tässä suhteessa se on myös parempi kuin Linuxin edellinen vuoronnin, jolloin suorittamalla sopivaa ohjelmaa oli mahdollista estää käyttäjää käyttämästä tie- tokonettaan (Molnar, 2007). Koska CFS pyrkii kohtelemaan ohjelmia reilusti, on mah- dollista, että se ei pysty hyödyntämään suoritinaikaa optimaalisimmalla tavalla suori- tustehon näkökulmasta.
Suoritinydinten hierarkia huomioidaan jakamalla ne luokkiin (englanniksi domain), jotka muodostavat hierarkkisen kokonaisuuden. Suoritettavat prosessit kuuluvat ai- na tiettyyn luokkaan, jonka mukaisella suoritinytimellä niitä suoritetaan. Luokille lasketaan niiden kuorma, ja tarvittaessa suoritetaan kuormien tasaus. Tällöin pro- sesseja voidaan siirtää suoritinytimeltä tai suorittimelta toiselle. (Linux, 2018, ks.
Documentation/scheduler/sched-domains.txt)
CFS-vuoronnin ei käytä tiettyä aikaviipaleen pituutta, vaan se lasketaan suorituksen aikana sen mukaan, paljonko prosessilla on virtuaalista suoritusaikaa jäljellä. CFS ei siis välttämättä vaihda tehtävää jokaisella keskeytyksellään. Vuoronnuksen hienojakoi- suutta (englanniksi granularity) voidaan säätää proc-tiedostojärjestelmän kautta. (Li- nux, 2018, ks.Documentation/scheduler/sched-design-CFS.txt)
CFS-vuorontimen tavallinen, yllä kuvattu vuoronnustapa on nimeltään
SCHED_NORMAL. Sen lisäksi on olemassa SCHED_IDLE ja SCHED_BATCH, jotka muuttavat CFS:n parametreja. SCHED_IDLE:n avulla on mahdollista hyödyn- tää muutoin käyttämätöntä suoritinaikaa. Sitä käyttäviä prosesseja ajetaan lähinnä silloin, kun muut prosessit eivät tarvitse vuoronninaikaa. SCHED_BATCH vähentää irrotusten lukumäärää, jolloin tehtäviä suoritetaan pidempään ja välimuisteja voidaan hyödyntää paremmin. Tämä on nimensä mukaisesti tehty batch-tyyppisille tehtäville ja heikentää responsiivisuutta. (Linux, 2018, ks. Documentation/scheduler/sched- design-CFS.txt) SCHED_BATCH:n ja SCHED_IDLE:n vaikutusta peleihin ei testata tässä tutkielmassa, sillä ne eivät sovellu tähän käyttötarkoitukseen.
2.2.2 muQSS ja BFS
The Multiple Queue Skiplist Scheduler (lyhyesti muQSS) ja BFS vuorontimet on kehit- tänyt Con Kolivas, joka oli myös mukana kehittämässä CFS-vuorontimen ideaa. BFS- vuoronnin on suunniteltu alusta alkaen työpöytäkäyttöä varten. MuQSS on sen seuraa- ja ja parantaa BFS-vuorontimen toimintaa käyttämällä useita suoritusjonoja ja erilaista tietorakennetta niiden tallentamiseen. MuQSS vuorontimen koodi perustuu BFS-vuo- rontimeen. (Hussein, 2017)
BFS-vuorontimessa ei ole ohjausryhmiä hierarkkista vuorontamista varten, sillä nii- tä ei Kolivaksen mukaan tarvita tällaisessa käytössä. Lisäksi siitä on poistettu suurin osa säädettävistä parametreista. BFS:ssä ei ole suoritinkohtaisia jonoja tehtäville, vaan tehtävät ovat yhdessä globaalissa jonossa. Tehtävät pyritään ajoittamaan samalle suo- ritinytimelle kuin millä ne suoritettiin aiemmin. Jos se ei onnistu, tehtävät ajoitetaan lähimmälle mahdolliselle suoritinytimelle edelliseen nähden. Erityisesti BFS:n seuraa- jana muQSS-vuorontimen tapauksessa huomioon otetaan myös loogiset ytimet, jolloin SMT-ympäristössä tehtävät pyritään vuorontamaan samalle fyysiselle ytimelle. (Hus- sein, 2017) Tässä läheisyys tarkoittaa sitä, kuinka tehokkaasti ydin pystyy hakemaan prosessin aiemmin käyttämiä tietoja, mistä kerrotaan enemmän kohdassa 2.3.
Sekä muQSS että BFS vuorontavat prosesseja käyttäen aikaisimman ensimmäisen so- pivan virtuaalisen aikarajan menetelmää (englanniksi earliest eligible virtual deadline first, lyhyesti EEVDF), joka on sukua aikaisimman aikarajan menetelmälle. Aikarajo- jen laskemiseen käytetään yleisesti määriteltyä aikaviipaleen pituutta ja prosessin prio- riteettia, jolloin suuremman prioriteetin omaava prosessi saa enemmän suoritinaikaa ja saatetaan myös vuorontaa useita kertoja uudestaan ennen pienemmän prioriteetin pro-
sessia. Aikaviipaleen oletuspituus on kuusi millisekuntia, ja käyttäjän on mahdollista muuttaa sitä. (Hussein, 2017)
Kolivas kehitti muQSS-vuorontimen BFS:n pohjalta ja pyrki korjaamaan joitakin sen huonoja puolia. MuQSS:ssä ei ole enää yhtä tehtäväjonoa, vaan jokaisella suoritin- ytimellä on oma jononsa. Tällä pyritään eroon skaalautuvuusongelmista, jossa suo- ritinytimien ja prosessien määrän lisääminen hidastaa tehtävän valintaa. Lisäksi suo- ritinytimen kilpailivat samasta lukosta, joten BFS-vuorontimella näyttää olevan skaa- lautumisongelmia yli kuudentoista suorittimen kokoonpanoissa. MuQSS-vuorontimes- sa tämä on viety niin pitkälle, ettei suoritinkohtaisen tehtäväjonon lukkoa lukita en- nen kuin sopiva prosessi on löydetty ja se ajoitetaan. Myös linkitetyn listan selaami- sessa on suorituskykyä heikentäviä ongelmia, sillä se ei ole välimuistiystävällistä, ja muQSS käyttääkin toisenlaista tietorakennetta tehtävien tallennukseen. (Kolivas, 2017, ks.Documentation/scheduler/sched-MuQSS.txt)
MuQSS:n tehtäväjonoille käyttämä rakenne on nimeltään skip list. Niistä käyte- tään muQSS:n tarpeisiin sovitettua versiota. Tehtävät tallennetaan järjestyksessä, kuten CFS-vuorontimessa, ja tehtävälistoista tarkastellaan vain ensimmäistä alkio- ta, jolloin seuraavaksi suoritettavan tehtävän hakeminen on vakioaikaista. Tehtä- vän lisäyksen aikavaativuus on logaritminen tehtävien määrään nähden aina 256 tehtävään suoritinta kohti asti. Tämä on parannus BFS-vuorontimeen nähden, sil- lä siinä aikavaativuus oli lineaarinen tehtävien määrään nähden. (Kolivas, 2017, ks.
Documentation/scheduler/sched-MuQSS.txt) Huomattavaa on myös, että CFS-vuoron- timen tehtävän hakemisen aikavaativuus on logaritminen, joten teoriassa muQSS on tässä suhteessa parempi. Toisaalta työpöytäkäyttäjän prosessien määrillä tämä tuskin on merkittävä ero, sillä logaritmifunktio kasvu hidastuu suuremmilla luvuilla ja kasvaa kokonaisuudessaan hitaasti.
Käyttäjän on mahdollista valita, haetaanko seuraava suoritettava tehtävä ensisijaises- ti saman suorittimen tehtäväjonosta vai haetaanko sitä kaikkien suoritinytimien teh- täväjonoista (Hussein, 2017). Tällä voidaan vaikuttaa järjestelmän responsiivisuuteen, mutta toisaalta väärä asetus voi haitata välimuistien toimintaa. MuQSS-vuorontimessa on myös toiminto, joka huomioi SMT-ympäristössä tehtävien prioriteetit ja jakaa sa- malla fyysisellä suorittimella olevien tehtävien suoritinajan suhteessa prioriteetteihin (Hussein, 2017). Tällä voisi joissakin erityisissä tilanteissa saavuttaa suorituskykyetua suuremman prioriteetin prosessin hyväksi.
Koska muQSS sijoittaa tehtäviä suoritinytimille eri tavalla kuin CFS, pitäisi tämän käy- töksen näkyä testituloksissa. Tästä asiasta kerrotaan lisää kohdassa 4.3, jossa on mit- taustuloksia MuQSS-vuorontimen toiminnasta. BFS-vuoronninta ei testata tässä tut- kielmassa. On mahdollista, että jossain tilanteissa prosessien pitäminen samalla yti- mellä tai siirtäminen toiselle ytimelle vaikuttaa suoritustehoon, mitä pohditaan lisää kohdassa 2.3.
MuQSS-vuoronninta käytettäessä on mahdollista asettaa ohjelman vuoronnuksen toi- mintatavaksi SCHED_ISO. Tällöin ohjelma vuoronnetaan reaaliaikavuoronnuksella määrättyyn suorittimen käyttöasteeseen asti ja se saa muita suuremman osan suori- tinajasta, vaikka järjestelmässä olisi muutakin kuormaa. Jos kyseisen tehtävän suo- ritusaika ylittää tämän käyttöasteen rajan, se vuoronnetaan kuten muutkin prosessit.
Mikäli SCHED_ISO vuoronnettuja tehtäviä on useampia, ne vuoronnetaan keskenään Round-Robin-algoritmilla. Usean suoritinytimen järjestelmässä on mahdollista, että tällöin SCHED_ISO menetelmällä vuoronnettu prosessi varaa kokonaisia ytimiä itsel- leen. (Kolivas, 2017, ks. Documentation/scheduler/sched-MuQSS.txt) SCHED_ISO- vuoronnuksen vaikutusta on mitattu testiohjelmalla, mistä kerrotaan lisää kohdassa 4.3.
2.2.3 Reaaliaikavuorontimet
Linuxin vuoronnin on kehitetty vuorontamaan myös reaaliaikatehtäviä. Reaaliaikavuo- ronnuksessa tehtäviä suoritetaan tyypillisesti määrätyin väliajoin pyydetty ajanjakso tai kunnes tehtävä antaa vuoron seuraavalle. Reaaliaikatehtäville kehitetyt vuoronnustavat (SCHED_RR, SCHED_FIFO ja SCHED_DEADLINE) vaativat kuitenkin ohjelmalta erityisten rajapintojen käyttöä, eivätkä siksi sovellu yleiseen käyttöön. Näistä uusin ja kehittynein on Linuxin versiossa 3.14 lisätty SCHED_DEADLINE, joka pyrkii pitä- mään ohjelmien suoritusajan tasaisena. Uusin versio pystyy myös joustamaan, mikäli ohjelman käyttämä suoritinaika vaihtelee ja se tarvitsee satunnaisesti enemmän suori- tinaikaa kuin on pyydetty.
Näitä vuoronnustapoja ei testata tässä esitelmässä johtuen siitä, etteivät ne sovellu pe- lien vuorontamiseen. Vaikka pelit ovat luonteeltaan reaaliaikaisia, niitä ei ole ohjel- moitu reaaliaikavuorontimilla vuoronnettaviksi. Erityisesti pelit eivät itse aseta reaa- liaikavuorontimien vaatimia aikarajoja.
2.3 Suorittimen rakenteen vaikutus
Tietokoneen suorittimilla on erilaisia rakenteita. Ne voivat sisältää vaihtelevia määriä suoritinytimiä ja välimuisteja. Myös välimuistien koot vaihtelevat ja erilaiset väylät muistien ja suoritinytimien välillä vaihtelevat ominaisuuksiltaan. Kaikilla näillä teki- jöillä voi olla vaikutusta vuoronnuksen toimintaan ja tehokkuuteen.
Välimuisteilla, kuten kaikilla muillakin muisteilla, on laitteiston määrittämä kaistanle- veys ja viive. Välimuistit ovat jaettu tasoihin siten, että ylimmän eli ykköstason väli- muistit ovat fyysisesti lähimpänä suorittimen rekistereitä. Välimuisteista kooltaan pie- nimmän ykköstason välimuistin kaistanleveys on suurin ja viive pienin. Välimuistin koko ja viive kasvaa sekä muistikaista pienenee siirryttäessä välimuistin alemmille ta- soille. Nykyaikaisessa suorittimessa on tyypillisesti kolme tasoa välimuisteja rekiste- rien ja keskusmuistin välissä. Näitä kutsutaan L1, L2 ja L3 välimuisteiksi eli ensim- mäisen, toisen ja kolmannen tason välimuisteiksi. (Hennessy & Patterson, 2012) Kun suoritettava prosessi hakee muistista tietoa suorittimen rekistereihin, tarkistetaan ensin, löytyykö sitä ensimmäisen tason välimuistista. Jos sitä ei löydy ensimmäiseltä tasolta, haetaan se sinne järjestyksessä seuraavilta tasoilta ja lopulta keskusmuistista siten, että etsintä lopetetaan sillä tasolla, jolta tieto löytyi. Tämän jälkeen tieto voidaan ladata rekisteriin. (Hennessy & Patterson, 2012) Välimuisteja käytetään piilottamaan keskusmuistin hitautta. Tiedon hakeminen keskusmuistista on verrattain hidasta, joten kulloinkin käsiteltävänä oleva tieto pyritään pitämään välimuisteissa. Koska välimuis- tin koko on rajallinen verrattuna keskusmuistiin, tieto ei mahdu kaikissa tilanteissa vä- limuistiin. Suoritustehon kannalta on hyödyllistä, että tieto pyritään pitämään välimuis- teissa eikä sitä tarvitse hakea keskusmuistista, mihin kuluu suorittimen mittakaavassa paljon aikaa.
Suorittimen tai järjestelmän rakenne voi olla hierarkkinen sillä tavalla, että jonkin tason välimuisti tai keskusmuisti on jaettu osiin, joihin eri suoritinytimillä on erilaiset hakua- jat ja muistikaista. Uusissa x86-suorittimissa on ydinkohtaisia ja jaettuja välimuisteja.
L1-välimuisti on suoritinydinkohtainen eli jokaisella ytimellä on oma L1-välimuistin- sa, joihin muilla ytimillä ei ole pääsyä. Vastaavasti L2 ja L3 välimuistit voivat olla jaet- tu jopa kaikkien ytimien kesken. Joskus L2-välimuisti on jaettu kahden ytimen kesken.
Yleisintä on jakaa L3-välimuisti kaikkien suoritinytimien kesken, jolloin kaikilla yti- millä on pääsy yhteiseen välimuistiin. Harvinaisempi ratkaisu on jakaa L3-välimuisti useampaan osaan siten, että yksi suoritinytimien ryhmä käyttää yhtä osaa välimuistis-
ta. (Fog, 2017) Rakenteesta riippuen muilla ydinryhmillä voi olla pääsy toisten ryh- mien välimuistiin tai omasta välimuistista puuttuva tieto haetaan aina keskusmuistista asti. Jaettu välimuisti mahdollistaa tiedon jakamisen suoritinydinten kesken siirtämät- tä tietoa välillä keskusmuistiin, mikä voi teoriassa nopeuttaa vuoronnuksen toimintaa tapauksessa, jossa prosessin käyttämä tieto mahtuu välimuistiin.
Kun uusi prosessi vuoronnetaan suoritinytimelle, välimuistin kaikilla tasoilla on edel- lisen prosessin tietoja. Uusi prosessi ei yleensä tarvitse näitä tietoja vaan muistista haetaan uutta tietoa välimuisteihin ja lopulta rekistereihin aina tarvittaessa. Jos tämän jälkeen vanha prosessi vuoronnetaan uudestaan, voi sen aiemmin käyttämiä tietoja löy- tyä edelleen joltain välimuistin tasolta. Näin erityisesti, jos vuoronnus tehdään samalle suoritinytimelle, jolla prosessia suoritettiin aiemmin. Tähän vaikuttaa sekä prosessien käyttämän tiedon määrä että suorittimen välimuistien rakenne ja koko. Mikäli välillä suoritettu prosessi kuitenkin käyttää tietoa enemmän kuin välimuisteihin on mahdollis- ta sisällyttää, kirjoitetaan välimuistin sisältö kokonaan uudelleen, ja uudelleenvuoron- nettua prosessia suoritettaessa suoritin joutuu hakemaan kaiken tarvitsemansa tiedon keskusmuistista.
Hennessy & Patterson (2012) käyttää esimerkkinä nykyaikaisesta suorittimesta neliy- timistä Intel Core i7 -suoritinta, joka toimii 3,2 GHz kellotaajuudella. Tällainen suori- tin voi hakea tietoa parhaimmillaan 409,6 GB/s kaistanleveydellä. Lukuun on laskettu sekä datan muistihakujen että käskyjen hakujen maksimikaistanleveys. Kuitenkin kes- kusmuistikaistaa on vain 25 GB/s, eli tämä suurin kaistanleveys voidaan saavuttaa vain välimuisteihin ja keskusmuistin muistikaista on vain murto-osa siiitä.
Välimuistit ovat x86-suorittimissa liian pieniä pystyäkseen säilyttämään useimpia pro- sessien tietoja pitkiä aikoja. Välimuisteista suurin eli L3-välimuisti on tämän hetken suorituskyvyltään parhaimmissakin suorittimissa kooltaan vain 8-16 MiB ja L2-väli- muistia taas on 256-512 KiB (Fog, 2017). Yllä käytetyn esimerkin mukaisella 25 GB/s kaistanleveydellä 16 mebitavun siirtämiseen kuluu aikaa 640 mikrosekuntia ja vastaa- vasti 512 kibitavun täyttäminen kestää vain 21,5 mikrosekuntia. Luvut eivät muutu suuruusluokaltaan merkittävästi, vaikka muistikaista tuplattaisiin. Lisäksi on huomat- tava, että useampi kuin yksi suoritinydin saattaa haluta käyttää keskusmuistia saman- aikaisesti eli nämä nopeudet saavutetaan vain, jos ainoastaan yksi ydin on tekemässä muistihakua. Kuitenkin vuorontimen jakamat aikaviipaleet ovat pienimmilläänkin mil- lisekuntien suuruisia, joten näitä lukuja niihin verratessa nähdään, että prosessi pystyy hyvinkin täyttämään suorittimen molemmat välimuistit yhden aikaviipaleen aikana.
Koska viiveet ovat huomattavan pieniä tiedon siirtämisen aikaan nähden, niiden huo- mioiminen laskuissa ei vaikuta tuloksiin merkittävällä tavalla.
Jotkin yksinkertaista laskentaa tekevät ohjelmat ovat ytimeltään niin pieniä, että ne mahtuvat välimuisteihin. Käytännössä tällaisia voisivat olla suorituskykymittauksia te- kevät ohjelmat. Peleissä käytetty tietomäärä voidaan olettaa tavallisesti tätä suurem- maksi, eikä se siis mahdu välimuisteihin kokonaisuudessaan. Luvussa 3 kerrotaan tar- kemmin siitä, mitä pelit erityisesti vaativat vuorontimelta ja laitteistolta.
Symmetristä monisäikeistystä käyttävissä suorittimissa samalla fyysisellä ytimellä toi- mivat loogiset ytimet jakavat saman välimuistin. Tällöin kyseinen välimuisti on yhtä paikallinen molemmille loogisille ytimille. Silloin prosessia siirrettäessä samalla fyy- sisellä ytimellä toimivalta loogiselta ytimeltä toiselle, prosessin tarvitsema tieto on jo valmiiksi saatavissa, eikä tästä periaatteessa synny yleisrasitetta keskusmuistista tehtä- vistä ylimääräisistä muistihauista. Sama tapahtuu, mikäli fyysiset ytimet jakavat saman välimuistin. Vuoronnin voi hyödyntää tätä SMT-ympäristön ominaisuutta toiminnas- saan pyrkimällä ajoittamaan tehtäviä samalle fyysiselle ytimelle kuin aiemmin, mikä- li se ei haittaa vuorontimen tavoitteita. Aiemmin mainituista Linuxin vuorontimista muQSS pyrkii tekemään näin, mikäli ytimellä ei ole vuoronnettuna toista prosessia.
Välimuisteja käytetään laitteistossa myös eri tavoin. Ne voivat olla sisällyttäviä (englanniksi inclusive) tai poissulkevia (englanniksi exclusive). Tämä tarkoittaa sitä löytyykö ylemmän tason välimuistin sisältö myös alemman tason välimuistista vai ei.
Sisällyttävä välimuistirakenne hyötyy teoriassa enemmän välimuistin koon kasvatta- misesta. (Shimpi, 2003) Lisäksi on olemassa hieman monimutkaisempi uhrivälimuisti (englanniksi victim cache), jossa ylemmän tason välimuistista poistettu tieto siirretään alemman tason välimuistiin, mutta tietoa ei haeta suoraan tämän tason välimuistiin.
Tällöin alemmat tasot eivät aina sisällä ylemmän tason välimuistin tietoa. Tällaista rat- kaisua käytetään Ryzen ja Skylake-X suorittimien L3-välimuistissa. (Cutress, 2017a;
Cutress, 2017b) Kaikissa tapauksissa keskusmuisti sisältää kaiken välimuistien sisäl- tämän tiedon siinä vaiheessa, kun käsiteltyihin tietoihin tehdyt muutokset ovat tallen- nettu.
Uhrivälimuistin käytöllä pyritään säästämään L3-välimuistin koossa verrattuna sisäl- lyttävään rakenteeseen ja välttämään poissulkevan välimuistin huonoja puolia tilan- teessa, jossa tietoa tarvitaan uudestaan. Vuoronnuksen näkökulmasta on mahdollista, että, vaihdettaessa suoritettavaa prosessia, alempien tasojen välimuistien tieto säilyy
kolmostason välimuistissa tarpeeksi kauan. Tällöin prosessia vuoronnettaessa uudes- taan, tietoa ei tarvitse hakea keskusmuistista asti, sillä se on edelleen L3-välimuistissa, ja tiedon hakemiseen ei käytetä suoritinaikaa. Koska tietoa ei haeta suoraan uhriväli- muistiin, se voidaan kirjoittaa yli ainoastaan, jos ylemmillä tasoilla olevaa tietoa pois- tetaan.
NUMA-järjestelmät (Non-Uniform Memory Access) vievät hierarkkisuuden vielä vä- limuisteja pidemmälle. Niissä myös keskusmuistin eri osiin on erilainen viive ja kais- tanleveys riippuen siitä, mistä suoritinytimestä muistia käsitellään. (Hennessy & Patter- son, 2012) Näitä suoritinytimien ja keskusmuistin kokonaisuuksia kutsutaan NUMA- solmuiksi. Käytännössä NUMA-järjestelmät tarvitsevat niille optimoidut ohjelmistot, jotka osaavat käyttää osiin jaettua keskusmuistia oikein, jotta ne toimisivat tehokkaasti.
Tässä tutkielmassa ei kuitenkaan käsitellä NUMA-järjestelmiä, sillä ne ovat pelikäy- tössä harvinaisia, eikä pelejä ole optimoitu NUMA-järjestelmille. Aiemmin mainituis- ta vuorontimista muQSS pyrkii vuorontamaan prosessin saman NUMA-solmun suori- tinytimelle kuin aiemmin, mutta voi tarvittaessa vuorontaa sen myös ytimelle toisesta NUMA-solmusta. CFS taas vuorontaa samaan NUMA-solmuun, mutta prosesseja voi- daan siirtää NUMA-solmujen välillä, mikäli solmujen kuormat ovat epätasapainossa.
Välimuistin toiminnan tehokkuutta vuoronnuksessa on haasteellista arvioida, sillä sii- hen vaikuttavat monet laitteiston optimoinnit. Haettaessa tietoa rekistereihin, suoritin ei hae välimuistiin vain rekisterin koon verran tietoa, vaan sinne ladataan myös muiden muistiosoitteiden tietoa hyödyntäen tiedon paikallisuutta (englanniksi locality) (Hen- nessy & Patterson, 2012). Tällä pyritään siihen, ettei jokainen tiedon haku rekisteriin aiheuta hakua keskusmuistista asti ja että suoritin toimii tehokkaammin. Lisäksi suo- rittimissa on muitakin pieniä optimointeja, jotka pyrkivät optimoimaan välimuistin toi- mintaa (Hennessy & Patterson, 2012).
Lisäksi nykyaikaisen suorittimen toimintaan vaikuttaa virransäästö, joka tyypillises- ti ohjaa suorittimen kellotaajuutta ja jännitteitä, mutta voi myös tarvittaessa poistaa käytöstä suorittimen osia silloin, kun niitä ei käytetä. Yleensä käyttöjärjestelmä hoitaa suorittimen kellotaajuuden säätämisen, jolloin sitä voidaan kontrolloida myös käyttä- jän tarpeiden mukaan, mutta uusimmissa suorittimissa myös suoritin muuttaa kellotaa- juutta itsekseen. Mittauksia tehdessä kellotaajuuden dynaaminen säätö voi aiheuttaa tuloksiin epätoivottua vaihtelua. Tästä kerrotaan lisää kohdassa 4.2.
3 Pelikäytön vaatimukset
Monilla nopeatempoisilla verkkopeleillä on suuret reaaliaikavaatimukset eli tehtävät on suoritettava tietyn aikaikkunan kuluessa. Tästä syystä pelit ovat vuorontimen näkö- kulmasta jonkin verran erilaisia kuin tyypilliset työpöytä- tai palvelinkäytön ohjelmat.
Pelit ja pelaaminen ovat muuttuneet viime vuosikymmeninä, ja useat nykyiset pelit ovat graafisesti näyttäviä ja sisältävät paljon laskentaa. Tässä luvussa kerrotaan pelien historiasta, niiden vaatimuksista vuoronnukselle ja laitteistolle sekä siitä, miten vuo- rontimet pystyvät vastaamaan näihin vaatimuksiin.
Pelien historiasta
Pelit ovat muuttuneet paljon tietokoneiden historian aikana. Kun kotitietokoneissa oli vain yksi suoritin, ei ollut tarvetta monimutkaiselle pelin rakenteelle. Nykymittapuulla vaatimaton laitteisto rajoitti paljon sitä, mitä voitiin tehdä, mutta taitavalla ohjelmoin- nilla laitteistosta saatiin irti enemmän kuin laitteiston suunnittelija oli ajatellut. Nyky- ään pelit ovat graafisesti paljon näyttävämpiä, millä on yhteys siihen, että kotitietoko- neet ovat muuttuneet paljon suorituskykyisemmiksi ja niissä on nykyään nopean suorit- timen lisäksi usein yleiseen laskentaan pystyvä näytönohjain, joka voi tehdä useampia laskutoimituksia sekunnissa kuin tietokoneen pääsuoritin. Kehitys ei kuitenkaan ole muuttanut sitä asiaa, että monet pelit pyrkivät hyödyntämään laitteistoa tehokkaasti maksimaalisen suorituskyvyn saavuttamiseksi. Näin ei kuitenkaan ole kaikkien pelien kohdalla ja erityisesti moniydinsuorittimien hyödyntämisessä on usein puutteita.
Suorittimien muuttuminen moniytimisiksi ja suorittimen kellotaajuuden kasvun hidas- tuminen on pakottanut pelienkin kehittäjät miettimään ratkaisuja säikeistyksen toteut- tamiseen eli siihen, kuinka useampia suoritinytimiä voidaan hyödyntää. Viime vuosina suoritinten suorituskyky on kasvanut eniten useampien suoritinydinten ansiosta, eikä yksittäisen ytimen suorituskyky ole kasvanut samassa suhteessa.
Nykyiset pelit ovat aiempaa graafisesti näyttävämpiä. Näytönohjainten kyvyt ja tieto- koneen muistit ovat kasvaneet paljon. Tämä mahdollistaa vaativamman renderöinnin ja suuremmat tekstuurit. Nykyaikaisen näytönohjaimen muisti useiden gigatavujen ko- koisena on verrattain suuri – jopa 8 GiB näyttömuisti ei ole harvinainen. Pelit lataavat tähän muistiin tekstuureja myös pelin aikana ja näytönohjaimelle annetaan jatkuvasti piirtokomentoja, jotka molemmat vaativat suorittimen toimintaa. Toisaalta myös näyt- töjen pikselimäärä ja koko on kasvanut. 1080p-tarkkuuden näyttö on yleinen, mutta
usein käytetään myös 1440p tai sitä tarkempia näyttötarkkuuksia. Suurempi näyttö- tarkkuus vaatii enemmän laskentatehoa.
Pelaaminenkin on muuttunut. Toisaalta on menty paljon arkisen mobiilipelaamisen suuntaan, mutta kotitietokoneilla pelaamisesta on joissakin tapauksissa tullut jopa am- mattimaisempaa. Lisäksi aivan viimeisimpänä muutoksena ovat tulleet virtuaalitodel- lisuuspelit, jotka kuitenkin ovat edelleen harvojen pelaajien käytössä. Näillä ryhmillä on omat erilliset kohderyhmänsä ja pelit ovat hyvin erilaisia. Ammattimaista pelaamis- ta kutsutaan elektroniseksi urheiluksi, ja siinä käytettävät pelit ovat tyypillisesti nopea- tempoisia ja vaativat keskittymistä sekä pelin sujuvaa toimintaa eli sitä, että ruudunpäi- vitys on tasainen ja käyttäjän syötteisiin reagoidaan nopeasti. Tämän avain on tarpeeksi tehokas laitteisto, mutta myös käyttöjärjestelmällä on tärkeä rooli. Käytettyjen ajurei- den tulee olla hyvin toteutetut ja pelille optimoidut. Tässä luvussa pohditaan kuitenkin sitä, mikä rooli käyttöjärjestelmän vuorontimella on pelin sujuvaan toimintaan.
Lisäksi nykyään pelaajien vaatimukset pelien ruudunpäivitysnopeudelle ovat kasva- neet. Siinä missä aikoinaan nykyisin melko matalanakin pidetyt ruudunpäivitysnopeu- det olivat hyväksyttyjä, pyritään nykyään vähintään joko 30 tai 60 ruutua/sekunti no- peuksiin. Usein vaaditaan jopa 120 tai 144 ruutua/sekunti nopeuksia. Näin on erityises- ti silloin, kun kyse on e-urheilusta tai virtuaalitodellisuudesta, joissa lyhyt viive toimin- nan esittämiselle ja nopea reagointi siihen on välttämätöntä. Silloin nopean ruudunpäi- vityksen lisäksi käyttäjän syötteiden prosessointi mahdollisimman pienellä viiveellä on tärkeää. E-urheilussa nopeus on tärkeää kilpailukyvyn säilyttämiseksi, ja virtuaali- todellisuudessa sillä voidaan välttää pelaajan pahoinvointia, joka johtuu toiminnan ja koetun ympäristön epäsuhdasta.
Pelien rakenne ja erityspiirteet
Pelejä on erilaisia ja tässä keskitytään erityisesti peleihin, joilla on vahvat reaaliaikai- suusvaatimukset. Pelien keskiössä on niin kutsuttu pelimoottori, joka toteuttaa pelin keskeisimmät tehtävät. Erilaiset pelit voivat käyttää samaa pelimoottoria. Pelimootto- reilla on paljon tehtäviä, jotka on suoritettava niin, että ne näyttävät käyttäjän näkökul- masta reaaliaikaisilta.
Pelimoottorit käsittelevät dataa eri tavoin, esimerkiksi maaston, geometrian ja tekstuu- rien luontiin, pelimaailmaan fysiikan mallinnukseen, animointiin, tekoälyjen toimin- taan ja äänen käsittelyyn. Toisaalta pelimoottorien tehtäviin voi kuulua esimerkiksi
renderöinti, fysiikka, käyttöliittymä, verkkotoiminnot, syötteet, ääni, tekoäly ja IO-toi- minnot. Pelimoottorin toiminta voidaan jakaa säikeisiin kummalla tavalla tahansa tai niitä yhdistellen, eli käytetyn datan tai pelin tehtävien mukaan, kunhan huomioidaan se etteivät osien toiminta tai käyttämä data ole päällekkäisiä. (Damon, 2011) Peleissä on kuitenkin paljon tehtäviä, jotka ovat riippuvaisia toisistaan, sillä ne tarvitsevat tois- tensa tuottamaa dataa. Esimerkiksi fysiikan laskeminen tarvitsee käyttäjän syötteitä ja mahdollisen tekoälyn päätöksiä, jotta se voi mallintaa pelaajan ja muiden hahmojen toimintaa oikein.
Vanhemmissa peleissä on tavallista, että peli on toteutettu peräkkäisesti yhdessä säi- keessä toimivana ohjelmana, eikä se osaa hyödyntää useampia suoritinytimiä. (Tulip
& al. 2006) Yksisäikeisen pelin vuorontaminen moniytimisellä prosessorilla on suh- teellisen yksinkertaista, koska käytännössä yksi ydin voidaan varata pelin käyttöön ja vuorontaa muut tehtävät lopuille ytimille.
Uudemmat pelimoottorit osaavat käyttää useita suoritinytimiä. Pelin tehtävät pitäisi ja- kaa suorittimen eri ytimille niin, että eri ytimien kuorma on tasainen, mikä ei ole aina helppoa. (Tulip & al. 2006) Useita prosesseja käytettäessä vuoronnus on monimutkai- sempaa: pelin eri säikeiden välillä voi olla riippuvuuksia ja lisäksi taustalla toimivat ohjelmat saattavat tarvita suoritinaikaa. Osa näistä taustalla toimivista ohjelmista voi- vat olla tärkeitä pelin suorituksen kannalta. Esimerkiksi näytönohjaimen käyttäjätilan ajuri saattaa käyttää suoritinaikaa pelin varjostinkoodin kääntämiseen näytönohjaimen konekielelle.
Yksinkertaisimpia tapoja säikeistää pelimoottori on käyttää kääntäjän ominaisuuksia kuten OpenMP-osioita. OpenMP:n avulla voidaan määritellä osia koodista suoritet- tavaksi omissa säikeissään. Tällä voidaan tehdä helposti funktionaalinen jako vaihte- levalle, mutta rajoitetulle määrälle suorittimia. (Andrews, 2012) OpenMP:ä voidaan käyttää myös silmukoiden säikeistämiseksi, mikä on yksinkertainen tapa toteuttaa ja- ko käytetyn tiedon mukaan. (Damon, 2011) Näillä tavoilla pelin tehtäviä saadaan kyllä siirrettyä suoritettavaksi useammille ytimille, mutta ratkaisut ovat melko joustamatto- mia. Ensimmäinen rajoittaa hyödynnettävien suoritinydinten määrää ja jälkimmäinen soveltuu vain tiettyihin tehtäviin.
Monimutkaisemman ja paremmin erilaisia kokoonpanoja hyödyntävän pelin säikeis- tyksen voi tehdä jakamalla pelin tehtävät osiin ja suorittamalla näitä pelin omissa työ- säikeissä. Työsäikeitä luodaan yksi jokaiselle suoritinytimelle ja ne ottavat aina uuden
tehtävän jonosta edellisen valmistuttua. Teoriassa tällaista ratkaisua käyttävä pelimoot- tori on mahdollista rinnakkaistaa kaikille suoritinytimille niiden määrästä riippumatta.
(Andrews, 2015) Tässä ratkaisussa yksittäisten tehtävien käyttämiä säikeitä ei tarvitse valita valmiiksi, sillä töiden jako tapahtuu automaattisesti. Käytännössä peli toteuttaa myös osan käyttöjärjestelmän vuorontimen tehtävästä ja vuorontimelle jää pelin osalta tehtäväksi ainoastaan huolehtia siitä, että peli saa kaiken mahdollisen suoritinajan.
Tällä tavalla säikeistettäessä pelin yksi prosessi ohjaa muita prosesseja jakaen niille tehtäviä suoritettavaksi. Säikeiden tehtävien ajoitus kohdistetaan kelloon, joka voi olla synkronoitu esimerkiksi ruudun piirtoon. Tämä kello voi toimia kiinteällä aikajaksol- la tai ajoittua vaihtelevasti. Pääprosessi myös kertoo työsäikeille muuttuneesta datasta sekä ottaa vastaan niiden töiden tulokset, ja syklien välillä säikeet päivittävät tietonsa pääsäikeeltä. Koska datasta siirretään vain osa, pääsäikeen on ylläpidettävä kirjanpitoa muutoksista. Mikäli eri osat voivat päivittää samaa dataa yhtä aikaa, tehtävä on moni- mutkaisempi, sillä silloin täytyy valita peruste, joka määrittää ajantasaisimman tiedon.
(Andrews, 2015)
Pelin kannattaa luoda yhtä monta säiettä kuin järjestelmässä on loogisia ytimiä, ei- kä sen kannata kiinnittää tehtäviä tiettyihin säikeisiin, sillä niiden suoritusajat vaih- televat erilaisten järjestelmien välillä. Pelimoottori voi huomioida välimuistit tehos- taakseen toimintaansa. Tehtävien suoritusjärjestyksen kääntäminen joka aikajaksolla auttaa hyödyntämään välimuisteja tehokkaammin, sillä mitä vähemmän aikaa on kulu- nut tehtävän suorituksesta, sitä todennäköisemmin sen tiedot ovat edelleen välimuistis- sa. Lisäksi samankaltaiset alitehtävät kannattaa sijoittaa ytimille, jotka jakavat saman välimuistin, koska ne todennäköisimmin käyttävät samaa tietoa. Tällöin on suurempi todennäköisyys sille, että kyseiset ytimet pystyvät hyödyntämään jaettua välimuistia.
(Andrews, 2015)
Pelin tehtävistä valtaosa on reaaliaikaisia. Enimmäkseen vain ennen pelin alkua ta- pahtuvat toiminnot, kuten pelimaailman lataus ja muu pelin valmistelu, eivät sisäl- lä mitään reaaliaikaisuusvaatimuksia. Mahdollista pelin aikana tapahtuvaa lataamista voidaan tehdä taustalla niin, ettei sitä tarvitse synkronoida reaaliaikaisiin tehtäviin, jo- ten senkään ei tarvitse olla reaaliaikaista. Joissain reaaliaikaisissa tehtävissä on ehkä mahdollista suorittaa ne esimerkiksi vain joka toisella aikajaksolla tai useamman aika- jakson aikana (Andrews, 2015). Tällaisesta esimerkkinä voisi olla vaikkapa tekoälyn toiminta.
Kun pelin toimintaa mitataan ja pyritään parantamaan, voidaan mitata ruudunpäivitys- nopeutta tai kuvan päivittämiseen käytettyä aikaa. Ruudunpäivitysnopeus, eli monta- ko kuvaa sekunnissa esitetään, antaa lukeman, joka kertoo selkeästi, kuinka käytetty laitteisto ja ohjelmisto suoriutuivat tehtävästään. Se esitetään yleensä keskiarvona ruu- dunpäivitysnopeuksista koko suorituksen ajalta, jolloin yksityiskohdat jäävät piiloon.
Kuvan päivittämiseen käytetty aika tallennetaan tavallisesti kaikista kuvista erikseen, ja tätä tarkastelemalla nähdään esimerkiksi se, onko jonkin yksittäisen kuvan piirtämi- seen käytetty liikaa aikaa. Odotettavissa on, että erityisesti yksittäisten ruutujen piirtoa- joissa on enemmän eroa kuin keskimääräisissä ruudunpäivitysnopeuksissa eri vuoron- timien välillä. Tasainen aika on parempi kuin vaihteleva, vaikka se johtaisi hieman hei- kompaan keskimääräiseen ruudunpäivitysnopeuteen, sillä pelaajan näkökulmasta peli toimii silloin paremmin. Erityisesti on syytä välttää sitä, että yksittäisen ruudun esit- tämiseen kuluu paljon aikaa, jolloin peli näyttää pysähtyvän tai ainakin takeltelevan, mitä kutsutaan pelaajien keskuudessalagaamiseksi.
Vuorontimien soveltuvuus
Reilusti vuorontavat vuorontimet eivät välttämättä anna monisäikeiselle pelille niin paljoa suoritusaikaa kuin mahdollista, sillä ne pyrkivät varmistamaan kaikkien ohjel- mien tasapuolisen kohtelun. Pelikäytössä voi olla parempi, että pelille ja muille tär- keämmille prosesseille annetaan enemmän suoritusaikaa kuin taustalla toimiville oh- jelmille. Tämä voidaan muuttaa esimerkiksi prosessin tai prosessien ryhmien priori- teettia säätämällä.
Useimmat muut tehtävät eivät vaadi samanlaista suorituksen tasaisuutta kuin pelit. Esi- merkiksi tieteellisessä laskennassa tai nettisivuja tarjoiltaessa pienet vaihtelut viiveissä eivät haittaa. Vuoronnin voi edesauttaa pelin tasaista ruudunpäivitystä vuorontamalla muille kuin pelin prosesseille aikaa lyhyissä viipaleissa ja palauttamalla pelin suorituk- seen tarpeeksi pian. Mikäli vuoronnin pystyy välttämään tarpeettomia kontekstin vaih- toja, vuoronnuksesta syntyy vähemmän yleisrasitetta ja suoritustehon pitäisi kasvaa.
Mikäli se lisää ruudunpäivityksen vaihtelevuutta, voi sillä kuitenkin olla se haittapuoli, että reaaliaikaisuus kärsii ja kokemus on käyttäjän näkökulmasta huonompi.
Hierarkkisen vuoronnuksen vuoksi CFS-vuoronnin saattaa rajoittaa tarpeettomasti mo- nisäikeisten pelien suorituskykyä antamalla taustaprosesseille enemmän suoritinaikaa kuin on tarpeellista. Toisaalta CFS-vuorontimen autogroups-toiminto pyrkii vuoron- tamaan käyttäjälle näkyvät prosessit tasaisesti, jotta reaaliaikaisiksi tarkoitetut käyt-
