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.
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 TVar
eiksi ja ne ovat arvoja, jotka voivat sisältää viitteen minkä tahansa tyyppiseen haskell-arvoon:
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:
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)}
Mutta mistä itse jonon runko koostuu? Ensinnäkin meillä voi olla tyhjiä jonoja, joissa alku ja loppuviitteet osoittavat samaa tyhjään paikkaan:
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ä:
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:
ja esimerkin 1,2,3-jono tälle:
Tämän idean jälkeen itse toteutuksen kirjoittaminen on helppoa. Esimerkiksi arvon lisääminen jonoon tapahtuisi näin:
TVar
loppu, jolloin saadaan rungon viimeinen viite-alkio (häntä)Tyhjä
n sisältävä TVar
loppu
viittaamaan tähän uuteen TVar
iin.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:
Vastaavasti alkion ottaminen jonosta tapahtuu niin, että,
alku
jonon ensimmäinen palaTyhjä
, kokeillaan myöhemmin uudestaan.alku
viittaamaan tuohon seuraavaan runkoon.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:
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ä.
blog comments powered by Disqus