Tik-76.166 Rinnakkaisohjelmointi, Tentti 1.3.1999 (Open book) hsa

1. Ratkaise kriittisen sektion ongelma mielivaltaiselle määrälle prosessoreja käyttäen atomista operaatiota swap(x,y), joka vaihtaa normaalien muistipaikkojen x ja y arvot keskenään. Todista ratkaisusi turvallisuus ja lukkiutumattomuus invarianssia käyttäen. Onko ratkaisusi reilu? Voiko se aiheuttaa livelockin? (6p)
   
   
2. Parturisalongissa toimii joukko partureita. Parturin asiakas ja parturi noudattavat seuraavia protokollia:
   

   asiakas:              parturi:
   
   enter_saloon;         wait_for_customer;
   "tukan leikkuu"       "leikkaa tukka"
   exit_saloon;          collect_bill;
   

   Muodosta monitori, jonka proseduureja ovat: enter_saloon, wait_for_customer, exit_saloon, collect_bill ja joka pitää huolta siitä, että jokaista asiakasta kohti on yksi "leikkaa tukka" -tilassa oleva parturi ja kääntäen. Monitorin on huolehdittava myös siitä, että tukan leikkuita voi olla käynnissä kerrallaan korkeintaan N kappaletta. Esitä toimiva koodi sekä monitorin speksi, eli siis monitorin invarianssi I, odotusehdot Bi ja turhan odotuksen poissulkemisen osoittava predikaatti J. Onko monitorisi reilu (sen ei tarvitse olla)? (10p)
   
   
3. Stop-and-copy kerääjän rinnakkaistaminen. Analysoi ongelmia, joita syntyy, kun stop-and-copy -kerääjän rinnalla toimii sovelluksen suhteen asynkroninen roskankerääjä. Esitä ja perustele ratkaisuja niihin. (6p)
   
   
4. Monisteessa on esitetty useampia ratkaisuja kriittisen sektion ongelmaan hajautetussa järjestelmässä. Analysoi niiden vikasietoisuutta ja esitä niihin tässä suhteessa parannusehdotuksia. (6p)