TIES343 - Miten TChan toimii?

Mikä on TChan?

Jos teemme rinnakkaisia prosesseja ohjelmiimme, niin meidän täytyy keksiä keino kommunikoida niiden välillä. Usein yksi prosessi hoitaa useista lähteistä tulevia pyyntöjä, mikä aiheuttaa viivettä. Usein pyynnön lähettävä prosessi jää odottamaan vastausta, mutta lähes yhtä usein prosessi voidaan muotoilla sellaiseksi, että vastausta ei tarvitse joko ollenkaan, tai riittää, että sen voi lukea myöhemmin.

Rinnakkaisturvallinen jono on erinomainen abstraktio tähän tarkoitukseen. Palveleva prosessi lukee pyyntöjä tulojonostaan ja muut prosessit lisäävät pyyntönsä jonoihin sitä mukaa kun niitä tulee. Tälläinen ‘mikroarkkitehtuuri’ on myös siitä syystä erinomainen, että se pakottaa ohjelmoijan minimoimaan rajapinnan prosessien välillä - kaikenhan täytyy kulkea yksinkertaisen jonon läpi. Tämä vähentää ohjelman osien yhteensitoutumista ja lisää modulaarisuutta.

Transaktiomuuttujat

Rinnakkaisten prosessien ikävin puoli on se, että emme voi hoitaa kommunikaatiota oikeiden muuttujien kautta, vaan meidän pitää sen sijaan luoda ohjelman tilaa esittäviä ‘viite-olioita’, joiden tila molemmat prosessit voivat joko muuttaa tai tarkastella. Toisinsanoen, olemme oikeastaan ensimmäistä kertaa haskell-ohjelmoinnin kanssa tekemisissä ohjelman tilan kanssa ja on huomattava, että tilamuuttujat tai ‘viite-oliot’ voivat tosiaan sisältää eri tietoa eri aikoina ohjelman suoritusta. Haskellin transaktiomuistissa näitä kutsutaan TVareiksi ja ne ovat arvoja, jotka voivat sisältää viitteen minkä tahansa tyyppiseen haskell-arvoon:

TVar joka sisältää viitteen merkkijonoon “kissa”

Arvon voi lukea TVar muuttujasta vain STM-monadissa, toiminnolla readTVar. Samaten TVar:n sisältämää viitettä voidaan myös muuttaa komennolla writeTVar. Esimerkiksi edellisessä tilanteessa komennon writeTVar x "koira" suorituksen jälkee viitteen tila on seuraava:

TVar joka sisältää viitteen merkkijonoon “koira”

Jono

Jokaisessa jonossa on kaksi olennaista paikkaa, ensimmäinen paikka ja viimeinen paikka. Edelliseltä pääsee poistumaan jonosta ja jälkimmäiseltä taas liittymään jonoon. Tässä tapauksessa lienee hyvä mallintaa myös rinnakkainen, muuttuva, jono siten, että pidämme yllä viitteitä jonon ensimmäiseen ja viimeiseen paikkaan:

> data TChan a = TChan {alku  :: TVar (Runko a)
>                      ,loppu :: TVar (Runko a)} 

TChan sisältää viitteet jonon ensimmäiseen ja viimeiseen alkioon

Mutta mistä itse jonon runko koostuu? Ensinnäkin meillä voi olla tyhjiä jonoja, joissa alku ja loppuviitteet osoittavat samaa tyhjään paikkaan:

Tyhjä TChan

Tämän lisäksi haluaisimme myös epätyhjiä jonoja, joten Runko tyyppi voisi näyttää tältä:

data Runko a = Tyhjä | a `Ja` (Runko a)

Toisinsanoen, jonomme on isomorfinen tavallisen haskell-listan kanssa. Esimerkiksi jono 1,2,3 näyttäisi rakenteessamme tältä:

Listan kanssa isomorfinen TChan

Tässä tapauksessa alku- ja loppu viitteet osoittavat kyllä oikeisiin paikkoihin ja niiden lukeminen on helppoa, mutta alkio lisääminen tai poistaminen jonosta ei ole. Lisätäksemme alkion jonoon, meidän täytyy käytännössä luoda uusi Runko arvo, jossa uusi alkio esiintyy. Tämän lisäksi, joudumme muuttamaan sekä alku, että loppu viitteitä, mikä aiheuttaa sen, että jonoon ei voi lisätä ja siitä ei voi ottaa alkiota samanaikaisesti. Jonon rakennetta pitäisi siis pystyä muuttamaan ilman, että koko jono korvataan.

Onneksi tässä palapelissä on vain yksi pala, sillä käytetyistä rakenteista vain TVar voi muuttaa tilaansa. Eli rakennamme jonon rungon viitteistä arvojen sijaan:

type Runko a = TVar (TRunko a)
data TRunko a = Tyhjä | a `Ja` (Runko a)

Tällöin tyhjä jono näyttää tälle:

Tyhjä viitteistä koostettu TChan

ja esimerkin 1,2,3-jono tälle:

Kolmen alkion TChan

Tämän idean jälkeen itse toteutuksen kirjoittaminen on helppoa. Esimerkiksi arvon lisääminen jonoon tapahtuisi näin:

1. Luetaan TVar loppu, jolloin saadaan rungon viimeinen viite-alkio (häntä)
2. Muutetaan rungon häntä viittaamaan arvoon, jossa on lisättävä kohde ja uusi Tyhjän sisältävä TVar
3. Asetetaan loppu viittaamaan tähän uuteen TVariin.

Ja koodiksi muutettuna näin:

> writeTChan :: TChan a -> a -> STM ()
> writeTChan (TChan _ loppu) a = do
>     rungon_häntä <- readTVar write
>     uusi_häntä   <- newTVar TNil
>     writeTVar rungon_häntä (a `Ja` uusi_häntä)
>     writeTVar loppu uusi_häntä

Operaation writeTChan jono 4 suorittamisen jälkeen esimerkkijonomme tila näyttää tälle:

Alkion lisääminen jonoon. Muutetut ja uudet viitteet punaisella ja poistuneet kohteet katkoviivalla ja harmaalla

Vastaavasti alkion ottaminen jonosta tapahtuu niin, että,

1. Luetaan viitteestä alku jonon ensimmäinen pala
2. Mikäli pala on Tyhjä, kokeillaan myöhemmin uudestaan.
3. Mikäli pala ei ole tyhjä, vaan siinä on arvo ja viite seuraavaan runkoon niin asetetaan viite alku viittaamaan tuohon seuraavaan runkoon.
4. Palautetaan arvo.

Tämä prosessi kääntyy Haskell koodiksi lähes suoraan:

> readTChan :: TChan a -> STM a
> readTChan ( TChan alku _) = do
>     eka_pala <- readTVar alku
>     a <- readTVar eka_pala
>     case a of
>         Tyhjä -> retry
>         x `Ja` seuraava -> do
>             writeTVar alku seuraava
>             return x

Operaation readTChan jono jälkeen esimerkkijonon tila näyttää tälle:

Alkion ottaminen jonosta

Yhteenveto

Transaktiomuuttujia käyttäen emme joudu miettimään rinnakkaisuutta jonon toteutuksessa ja se on käytännössä aivan yhtä helppo toteuttaa kuin peräkkäisesti suoritettava jono ensimmäisen vuoden Algoritmit ja Tietorakenteet kurssilla. Ainoa merkittävä ero toteutuksessa on se, että joudumme eksplisiittisesti kirjoittamaan ja lukemaan viitteet, toisin kuin Algoritmit kurssin imperatiivisissa kielissä.