Tik-76.166 Rinnakkaisohjelmointi

Tentti 17.12.1997

1. Analysoi kolmen päättymättömän prosessin X, Y, Z ohjelmaa (alussa x=y=z=1, atomiset operaatiot merkitään hakasilla: < > ):

loop <x:=z+y> end || loop <y:=x> end || loop <z:=y> end

Osoita, että se ylläpitää invarianssia: P { z+y >= x >= y >= z }.

2. Jaa edellisen tehtävän atomiset operaatiot jaetun muistin atomisiksi LOAD- ja STORE-tason operaatioiksi. Pitääkö P vielä paikkansa? Voimmeko vetää tästä sen yleisemmän johtopäätöksen, että jos ohjelman jokaista muuttujaa muuttaa vain yksi prosessi ja kaikki tilamuutokset tapahtuvat yksinkertaisina sijoituksina x:=E, voidaan näitä sijoituksia aina tarkastella atomisina ?

3. Seuraavassa on yleinen CS-algoritmi, joka sisältää vain 4 viittausta yhteisiin muuttujiin ei-kilpailutilanteessa.

repeat

do x<>0 -> skip od; (alussa x=0)

x:=i;

delay;
until x=i;
CS;
x:=0;

Millä edellytyksillä (erityisesti viiveen delay suhteen) ratkaisu toimii ?

4. "Kirjoitusaikomus"-lukolla tietokantaa päivittävä prosessi lukee dataa ennen varsinaista kirjoitusta, jonka alkaessa prosessi pyrkii muuttamaan lukon varsinaiseksi kirjoituslukoksi. Kirjoitusaikomus voi olla käynnissä yhtäaikaa varsinaisten lukujen kanssa, mutta ei yhtäaikaa kirjoitusten tai toisten kirjoitusaikomusten kanssa. Toteuta vaadittavat synkronointioperaatiot monitorina. Anna monitorin invarianssi ja ehtomuuttujien laukaisuehdot ja osoita, ettei monitori aiheuta turhaa odotusta.

5. Vastaa vain jompaan kumpaan:
a) Stop-and-copy roskankerääjän rinnakkaistaminen ?
b) Snapshot-algoritmin soveltaminen hajautetun järjestelmän varajärjestelmän lämmitykseen ?