lauantai 6. helmikuuta 2010

Rinnakkaisuus.

tilasiirtymäjärjestelmiä käytetään usein erilaisten abstraktien reaktiivisten koneiden mallina. Olen puhunut näistä joskus aiemminkin. Semantiikka on näissä yhteyksissä oikeastaan vain kuvaus joltakin esitystavalta toiselle. Esimerkiksi tietokoneohjelman semantiikka voidaan antaa operationaalisena, so, kertomalla, minkälaisia tilasiirtymiä "syntyy" kun ohjelmassa esiintyy tiettyjä komentoja.

Rinnakkaisjärjestelmän prosessien keskinäistä kommunikointia voidaan mallintaa monella eri tavalla. Yksi näistä on viestinvälitys. Viestinvälitys voi tapahtua synkronisesti tai asynkronisesti; tällä viitataan siihen, täytyykö viestiä lähettävän prosessin odottaa vastaanottaja vai ei. Jos synkroninen viestinvälitys on ainoa kommunikointikeino, rinnakkaisjärjestelmä voidaan mallintaa kokoelmana tilasiirtymäjärjestelmiä, joista jokainen kuvaa yhtä prosessia.

Koko järjestelmä voidaan tällöin esittää rinnankytkentänä. Yksinkertaisimmillaan tämä tapahtuu niin, että tilasiirtymillä on "nimi" ja eri prosessien samannimisten siirtymien tulee tapahtua samalla. Esimerkikkinä järjestelmä jossa on kaksi komponenttia P: a -> b -> P ja Q: a-> c->Q. Näiden rinnankytkentä P||Q suorittaa ensin tapahtuman "a", sitten se voi suorittaa tapahtumat "b" ja "c" mielivaltaisessa järjestyksessä ja palaa alkutilaansa.

Kombinatorinen räjähdys seuraa, kun rinnankytkennässä prosesseilla on vähän tai ei lainkaan synkronisuutta: Prosessien tilojen yhdistelmien määrä kasvaa eksponentiaalisesti komponenttien määrän kasvaessa.

Malleja ei kuitenkaan rakenneta pelkästään huvin vuoksi. Yleensä malli rakennetaan, koska siitä halutaan saada vastaus johonkin tiettyyn kysymykseen. Esimerkiksi halutaan tietää, voiko järjestelmä lukkiutua. Tai halutaan tietää, voiko jokin viesti jäädä kokonaan vaille vastausta. Tämän tyyppiset kysymykset kuuluvat - laajasti ymmärrettynä - mallintarkastuksen piiriin. Mallintarkastus rinnankytkennän yhteydessä tapahtuu useimmiten niin, että laadimme jonkin ehdon sille, miten tunnistamme tilan tai tapahtumasekvenssin, joka on virheellinen. Sitten rakennamme rinnankytkennän ja etsimme siitä tilannetta, jossa ehto toteutuu.

Olen tällä viikolla rakennellut rinnankytkentää Pythonilla. Rinnankytkennästä ei tyypillisesti tarvitse tutkia kaikkia tiloja; kombinatorinen räjähdys voidaan osittain välttää. Yksi keino on käyttää itsepäisiä joukkoja, jonka jo kuvailemaani formulaatiota olen tutkinut tällä viikolla.

Itsepäisen joukon generoimiseksi rinnankytkennän jossakin tilassa on olemassa verraten yksinkertainen algoritmi. Se approksimoi, so. se generoi joukon, joka voi olla tarpeettoman suuri, eli saattaa johtaa tarpeettoman monien tilojen tutkimiseen. Kunkin prosessin omat tapahtumat johtavat eri tulevaisuuksiin, mutta prosessien välillä on riippumattomuutta, jota voi hyödyntää. Algoritmia voidaan parantaa, jos kunkin prosessin "tulevaisuudesta" on enemmän tietoa. Esimerkiksi tieto siitä, että jotkin tapahtumat eivät voi olla yhtä aikaa tarjolla, on usein hyödyllinen.

4 kommenttia:

Tiedemies kirjoitti...

Jaahas, rinnankytkentä toimii näköjään nyt. Rakennelmasta tuli raskas, mutta tämä onkin vain koekäyttöön.

Seuraava vaihe on itsepäisen joukon laskeminen, joka on ei-triviaali tehtävä.

Jukka Aakula kirjoitti...

Nyt muistelenkin että joskus kauan sitten piirtelin Petri-verkkoja.
Protokollia tutkiittiin jotenkin niin että tietoliikenteen kaksi päätä A ja B olivat tilakoneita ja ihmeteltiin meneekö homma jotenkin lukkoon. Kun sitten koodasin jonkun oman protokollan en muista että olisin ymmärtänyt miten tuota teoreettista tietoa sitten olisi kannattanut soveltaa.

Sen sijaan sen muistan hyvin miten NSN:ssä kehitimme kielelle X kääntäjän. Ekasta kääntäjästä tuli paska. Teimme toisen version ja siinä yhteydessä mietimme kielen formaalin semantiikan tarkasti. Tai ei se oikeastaan mikään oikea kääntäkä ollut vaan koodin generaattori.

Tietokantaihmisenä olen tutustunut tietysti SQL:n semantiikkaan. Koska perus-SQL periaatteessa määritellään formaalisti relaatioalgebran avulla formaali semantiikka ei ole perus-SQL:n tapauksessa mitään rakettitiedettä. Niin kuin ei ole operationaalinenkaan semantiikka. Kyselyn optimointi kai liittyy operationaalisen semantiikkkaan relaatiotietokantojen osalta.

Nykyään en noin hienoja hommia tee. Koodailen C:llä, C#:lla, Javalla, C++:lla, PHP:lla jotain pientä näpertelyä. Sen sijaan en ole mikään maailmaa syleilevä konsultti ...

Tiedemies kirjoitti...

Itse tykkään näistä jutuista lähinnä niiden elegantin ja mielenkiintoisen rakenteen vuoksi. Graafialgoritmeissa on jotain ylimaallista, lähes hengellistä. En osaa selittää sitä.

Tiedemies kirjoitti...

Rakensin muuten taannoin petriverkkojen merkintä-avaruuden tutkimiseen soveltuvan ohjelman, kun harjoittelin pitkästä aikaa koodaamaan C/C++:lla.

Törmäsin silloin hauskaan tilanteeseen siitä, miten ainakin g++:n varoitukset toimivat "hieman" epäintuitiivisesti.

Esimerkiksi etumerkillisen ja etumerkittömän kokonaisluvun vertailu tuottaa oletusarvoisesti varoituksen, mutta non-void funktion (tässä tapauksessa se oli pointteri erääseen struct- tyyppiin) rungosta puuttuva return-statement (vahingossa pois kommentoitu) ei tuottanut varoitusta.

Kun kyseisen funktion piti palauttaa transition laukaisemisen seurauksena saatava merkintä, niin lopputulos oli, sanoisinko "mielenkiintoinen". Hulluinta oli se, että pienehköillä esimerkeillä ohjelma toimi jopa välillä oikein, mutta kaatuili yllättävästi.