Reiluus

Reiluus (engl. fairness) viittaa rinnakkaisten järjestelmien teoriassa suunnilleen sitä, että järjestelmän mallissa otetaan huomioon vain sellaiset äärettömät suoritukset, joissa kaikki komponentit etenevät jossain vaiheessa. Esimerkiksi, jos meillä on kaksi toimijaa, jotka tahtovat käyttää jotain jaettua resurssia (esimerkiksi tulostin, jolla kahdelta eri koneelta tulostetaan) jatkuvasti, niin järjestelmä on reilu, jos molemmat pääsevät halutessaan lopulta tulostamaan.

Käsite on intuitiivisesti ensialkuun selkeä, mutta analysoitaessa tarkemmin, se hajoaa käsiin. Käytetään esimerkkiä jossa kahdelta eri tietokoneelta tulostetaan samalla tulostimella.  Protokolla on seuraavanlainen: Koneelta tulee yksi pyyntö kerrallaan tulostaa paperi. Tulostin valitsee jomman kumman pyynnön ja palvelee sitä. Toinen pyyntö jää voimaan ja tulostamisen jälkeen tulostin valitsee uudelleen. On kuitenkin mahdollista, että ensimmäinen kone on tällä aikaa päättänyt pyytää uuden paperin tulostamista, ja tulostin valitsee sen jäälleen. Toisen koneen pyyntö on koko ajan voimassa, mutta sitä ei koskaan toteuteta. Niin sanottu heikko reiluus sanoo, että jos jokin toiminto on koko ajan mahdollinen, järjestelmä lopulta todella suorittaa sen, eli että järjestelmässä ei ole sellaista ääretöntä suoritusta, jossa pyyntö olisi koko ajan (teoriassa) mahdollista toteuttaa, mutta sitä ei toteuteta.


Todellisuudessa kuitenkin pyyntö menee tulostimen jonoon. Tulostin ottaa jonosta pyynnön ja tulostaa sen. Jos jono toimii niin, että sinne mahtuu "paljon" pyyntöjä, ja ne käsitellään aina järjestyksessä, ongelmaa ei juurikaan ole. Mutta oletetaan että jonoon mahtuukin vain yksi pyyntö (tai jokin pieni määrä). Jos jonossa on yksi pyyntö, tulostin ottaa sen käsittelyyn ja jono tyhjenee (tai sinne mahtuu yksi lisää).  Nyt kuitenkin ensimmäinen kone ehtii tulla takaisin pyytämään ja laittaa oman pyyntönsä jonoon ennen kuin toinen ehtii sitä esittää. 


Nyt siis pyynnön esittäminen ei ole mahdollista silloin, kun jono on täynnä.  Vaikka jokainen todella esitetty pyyntö tulee käsitellyksi, toinen koneista ei pääse esittämään pyyntöään koska se ei ole mahdollista välillä. Järjestelmä ei intuitiivisesti katsottuna ole reilu, mutta heikko reiluus ei tätä mahdollisuutta tavoita. Vahva reiluus taas sanoo, että jos jokin tapahtuma on äärettömän usein mahdollinen (vaikka se välillä olisikin mahdoton), niin se lopulta tapahtuu. Eli vaikka jono välillä on täynnä eikä pyyntöjä voi esittää, vahvasti reilu järjestelmä takaa että toinenkin kone lopulta pääsee esittämään pyyntönsä.

Reiluuden ongelmana on, että se on erittäin hankala mallintaa, ja se on kiusallinen laskennallisesti, verrattuna sellaisiin ominaisuuksiin kuten turvallisuus ja lukkiumat. Turvallisuus viittaa siihen, että esimerkiksi pyynnöt eivät mene sekaisin, eli ei tapahdu tilannetta jossa molemmat koneet kuvittelevat tulostavansa samanaikaisesti (ja esimerkiksi sivulle tulisi kahta eri tekstiä päällekäin tms). Turvallisuusrikkomus voidaan havaita jos järjestelmä päätyy tilaan jossa molemmat koneet kuvittelevat tulostavansa.

Myös lukkiumat ovat helppo todeta; lukkiuma on järjestelmän tila, jossa se ei pääse lainkaan etenemään. Jos esimerkiksi tulostimen ja koneiden välinen jono menee rikki niin, että kumpikin kone näkee jonon olevan täynnä (ja näin jää odottamaan että saisi laittaa sinne pyynnön), ja tulostin kuvittelee että jono on tyhjä (ja näin odottaa pyyntöjä), järjestelmä lukkiutuu. 

Ajatellaan nyt protokollaa joka hoitaa jonkin tällaisen järjestelmän toimintaa. Siinä ei ole jonoa, mutta siinä on eräänlainen "odotushuone". Jokainen joka haluaa päästä tulostamaan -- nimitetään tätä asiakkaaksi -- ilmaisee halunsa tulostaa laittamalla "lipun" päälle. Kummallekin asiakkaalle on oma lippunsa.  Kun asiakas on laittanut lipun päälle, tämä menee "välitilaan"  kirjoittamaan "nimikirjaan" toisen asiakkaan nimen. Tämä tapahtuu riippumatta siitä, mitä nimikirjassa luki. Tämän jälkeen asiakas menee odottamaan. Odottaessaan asiakas tarkastaa, onko nimikirjassa tämän oma nimi vai joku muu. Jos kirjassa on oma nimi, niin asiakas pääsee tulostamaan. Jos siinä ei ole omaa nimeä, asiakas tarkastaa onko kenelläkään lippu päällä. Jos lippuja ei ole päällä, asiakas pääsee myös tulostamaan. Tulostettuaan asiakas laittaa lipun alas.

Tässä järjestelmässä asiakas ei voi "etuilla" muita. Jos joku muu on esittänyt pyynnön, niin kun asiakas esittää pyynnön (eli laittaa lipun päälle), hän samalla antaa vuoron toiselle. Asiakkaat eivät voi estää toisiaan laittamasta lippuja päälle. He voivat viivästyttää toista ainoastaan jäämällä välitilaan jossa lippu on laitettu päälle mutta nimikirjaan ei ole kirjoitettu mitään.  Järjestelmä ei kuitenkaan vaadi edes heikkoa reiluutta, ainoastaan oletuksen, että kumpikaan ei vapaaehtoisesti pysähdy välitilaan, odottamaan, tai tulostamaan.

Me tiedämme että tämä järjestelmä toimii ilman reiluusoletuksia. Vaan entä jos järjestelmä onkin rikki?

Kuvitallaan että asiakas ei tarkastakaan toisen lippua, vaan jää vain odottamaan, että toinen asiakas antaa vuoron. Tällöin asiakas jää odottamaan kunnes toinen asiakas on antanut vuoron ja siirtynyt itse odottamaan. On selvää, että tällainen järjestelmä ei toimi kunnolla -- kuvittele järjestelmä jossa voit tulostaa ainoastaan jos joku muu yrittää myös tulostaa.  Jos kuitenkin mallinnamme järjestelmän niin, että kukaan ei jää odottamaan minnekään, se näyttää toimivan oikein, koska kumpikin yrittää tulostaa uudelleen ja uudelleen. Me toki tiedämme että jos sallimme asiakkaan jäädä paikoilleen alkutilaan, niin virhe paljastuu.

Yleisemmin, ominaisuus joka tässä yleensä tarkastetaan on, että lopulta pyyntöön vastataan. Mutta tämä rikkinäinen järjestelmämme näyttää oikealta jos emme osaa huomioida sitä, että asiakas saattaa alkutilassa jäädä paikoilleen.  Heikko reiluuskaan ei auta suoraan, mutta me voimme saada virheen kiinni, jos laitamme alkutilaan silmukan, jossa asiakkaan on lupa junnata paikallaan. Tällöin saamme aikaan äärettömän suorituksen, jossa pyyntö on esitetty, mutta siihen ei ole mahdollista vastata (koska toinen asiakas pyörii loputtomiin eikä koskaan pyydä mitään), ja olettamalla että reiluus koskee vain välitilaa, odotusta, ja tulostamista. Tämä on kuitenkin varsin hankala mallintajalle, koska mallintajan täytyy ikään kuin tietää missä tilassa virhe voi syntyä ennen kuin hän edes sitä lähtee etsimään.

Ongelma tässä on se, että järjestelmän alkuperäinen malli näyttää oikealta, koska asiakkaalle ei olla mallinnettu muuta mahdollisuutta kuin se, että tämä jatkuvasti esittää pyyntöjä. Huomattavasti luontevampi malli olisi sellainen, jossa asiakas voi todeta että "olen saanut tarpeekseni" tulostettuaan, ja tämä siirtyy tilaan jossa ei enää voida tehdä mitään. Tällöin toki järjestelmä saattaa lukkiutua, mutta lukkiutumisen kohdalla riittää spesifioida erikseen se, onko lukkiuma sallittu vai ei. Eli, jos annamme asiakkaalle mahdollisuuden päättää "nyt loppui" ja parkkeerata itsensä, meidän pitää sallia sellainen lukkiuma (ja vain sellainen) jossa kaikki asiakkaat ovat lopettaneet tyytyväisinä.

Tämä siksi, että on intuitiivisesti selvää ettei asiakkaan pyyntöihin vastaamisen ehtona pitäisi olla se, että toinenkin asiakas pyytää jotain. Jos teemme näin, niin huomaamme, että kun toinen asiakas lopettaa tyytyväisenä, toinen on tuomittu jumittamaan odotustilaan; löydämme lukkiuman joka ei ole sallittu ja virhe paljastuu. Alkuperäisessä järjestelmässä näin ei käy, koska odottava asiakas näkee että toisen asiakkaan lippu on alhaalla, ja pääsee tulostamaan kaikessa rauhassa.

Kun tutkimme jonkin pyynnön toteutumista, nimitämme tällaista ominaisuutta ei-pakotetuksi pyynnöksi (unforced request). Se tarkoittaa, että asikkaalla tulisi olla mahdollisuus kieltäytyä esittämästä pyyntöjä, ja järjestelmän oikeellisuus tulisi säilyä. Pääsemme näin eroon reiluudesta ainakin tässä nimenomaisessa tapauksessa.

Kuvitellaan nyt että rikomme jo rikkonaista protokollaa lisäksi niin, että asiakas ei muistakaan kirjoittaa mitään nimikirjaan. Tällöin siis asiakas vain laittaa lipun päälle ja menee tarkastamaan onko nimikirjassa oma nimi. Nimikirjassa on jonkun nimi, ja tämä joku pääsee loputtomiin käsiksi resurssiin, mutta koska kukaan ei sitä muuta, toinen asiakas puolestaan jää odottamaan loputtomiin.  Huomaisimme tässä kyllä virheen, mutta tehdään lisäoletus: Kun asiakas päättää ettei se enää halua palvelua, se parkkeeraa itsensä, ja vasta sitten kirjoittaa nimikirjaan toisen asiakkaan nimen.

Tällöin käy niin, että niin kauan kun kumpikin asiakas haluaa resurssia, ensimmäinen saa sen käyttöönsä loputtomiin kun taas toinen ei saa sitä lainkaan. Vasta kun ensimmäinen lopettaa, toinen saa vuoron. Tässä kohtaa emme saa virhettä kiinni pelkästään lukkiumia ja turvallisuusominaisuuksia tarkastelemalla, mutta järjestelmällä on kuitenkin ääretön suoritus jossa toinen prosessi odottaa. Reiluutta ei kuitenkaan tarvita mihinkään, ainoastaan oletus että kumpikaan asiakas ei odota loputtomiin.

Nimitämme tällaista ominaisuutta englanninkielisellä ilmaisulla eventual access (en keksinyt hyvää suomennosta). Se tarkoittaa että spesifioimme tilapredikaatteja jotka eivät saa olla voimassa äärettömässä suorituksessa. Emme siis oleta mitään reiluudesta tässä kohtaa, vaan yksinkertaisesti sanomme että "ei ole lupa jättää asiakasta odottamaan äärettömästi". Tämä on hieman samanlaista kuin reiluus, mutta se on eri roolissa; Reiluus on oletus joka tehdään jotta voidaan erottaa aidot virheet silmukoiden alispesifioinnin tuottamista "artefakteista".

Rikkinäisessä järjestelmässä on eventual-access rikkomus, sillä niin kauan kun ensimmäinen asiakas hakee palvelua, tämä saa sitä loputtomiin ja toinen asiakas ei saa mitään. Vasta kun ensimmäinen lopettaa, toinen pääsee resurssiin. Käytännössä tämä näkyy niin, että järjestelmällä on silmukka jossa toinen asiakas odottaa.

Jos siis spesifioimme että järjestelmälle on spesifioitu sallitut lukkiumat, turvallisuus (eli se, ettei resurssia käytetä yhtä aikaa) sekä eventual access- ominaisuus ja varmistamme että mallinnoksessa on huomioitu unforced request, niin voimme saada kaikki em. virheet kiinni ilman mitään erillisiä reiluusoletuksia.

Tämä artikkeli on nyt kirjoituksen alla.