Bottom half in English

Rinnakkaisohjelmointi, kurssikuulustelu 15.12.2006
Concurrent programming, Course examination 15.12.2006

Kirjoita jokaiseen vastauspaperiin: oma nimi, henkilötunnus, kurssin nimi, nimikirjoitus ja sivunumero.

1. [10 p] Saariston lossi liikennöi pienen salmen ylitse jatkuvasti. Lossiin mahtuu 8 henkilöautoa. Lossi lähtee heti kun se on täysi tai sitä odottaneet autot ovat ajaneet lossiin. Autot odottavat lossia ja ajavat lossiin sen saavuttua rantaan tilan salliessa.
   1. [5 p] Anna semaforeihin perustuva ratkaisu lossin käyttämiseen: semaforit, yhteiset muuttujat, alustukset, lossin lastaus (yhdessä päässä) ja auton kuljettajien lossin lastaamisessa noudattamat algoritmit.
   2. [5 p] Muokkaa algoritmia siten, että siinä on mukana myös linja-autot. Linja-auto vie 3 henkilöauton paikan ja linja-autoilla on tilan salliessa etuajo-oikeus lossiin.
       
2. [10 p] Monitori ja suojatut oliot
   1. Mikä on monitori? Mihin ongelmaan se on ratkaisu?
   2. Mikä on monitorin ehtomuuttuja ja mihin sitä käytetään?
   3. Mitä monitorin signalointisemantiikka tarkoittaa? Mikä on "Signal and Continue" signalointisemantiikka?
   4. Mikä ongelma liittyy monitorin "Signal and Continue" signalointisemantiikkaan? Anna ongelmasta konkreettinen esimerkki.
   5. Miksei suojatuissa olioissa ole em. ongelmaa?
       
3. [10 p] Lukkiutuminen
   1. [2 p] Anna Aterioivien filosofien ongelmaan semaforeihin perustuva ratkaisu, jossa on lukkiutumisongelma. Anna lukkiutuva skenario.
   2. [8 p] Lukkiutuminen voi tapahtua ainoastaan tiettyjen ehtojen vallitessa. Mainitse nämä ehdot ja anna selitä kunkin ehdonkohdalla kuinka a-kohdan ratkaisua tulisi muuttaa, jossa lukkiutuminen estetään juuri kyseinen ehto rikkomalla.
       
4. [10 p] Hajautettu kriittinen vaihe. Tarkastellaan Ricart-Agrawalan kiertävään kolikkoon perustuvaa algoritmia (kääntöpuolella). Oletetaan, että kaksi prosessia (A ja B) eri solmuissa haluavat yhtäaikaa kriittiseen vaiheeseen, joka on vapaa. Oletetaan, että kolikko on kolmannella solmulla C. Muita tähän kriittiseen vaiheeseen liittyviä prosesseja ei ole.
   1. Mihin perustuu päätös, jolla seuraava kriittiseen vaiheeseen pääsevä prosessi valitaan? Kumpi se on, A vai B? Miksi?
   2. Oletetaan nyt, että C on tällä hetkellä kriittisessä vaiheessa ja että kaikki A'n ja B'n lähettämät viestit ovat saapuneet perille. Kumpi pääsee seuraavaksi, A vai B? Perustelut?
   3. Jatkoa edelliseen kohtaan. Voiko prosessi C päästä kriittiseen vaiheeseen uudelleen ennen kuin sekä A että B ovat päässeet sinne? Perustelut?
   4. Main ja Receive -prosessien sisällä täytyy olla kriittisiä vaiheita, jotta algoritmi toimisi oikein. Mitkä ne ovat?
   5. Mitä etua Rigart-Agrawalan kiertävään kolikkoon perustuvalla algoritmilla on tavalliseen Ricart-Agrawala -algoritmiin nähden?

Write in each answer sheet your name, signature, id-number, course name, and page nr/total nr of pages.

1. [10 p] A ferry operates continuously across a small strait. It can take 8 cars. A ferry departs once it is full, or once all cars waiting have been loaded. Cars will wait for the ferry to arrive, and drive into it if there is space available.
   1. [5 p] Give a semaphore based solution for using the ferry: semaphores, shared variables, initial values, ferry loading algorithms for ferry operator and for car drivers.
   2. [5 p] Modify the algorithm to consider also busses. Each bus takes equal space to 3 cars and has priority over cars.
       
2. [10 p] Monitor and protected objects
   1. What is a monitor? What problem does it solve ?
   2. What is a monitor condition variable and what is it used for?
   3. What is monitor "signaling semantics" What is "Signal and Continue" signaling semantics?
   4. What is the problem associated with monitor "Signal and Continue" signaling semantics? Give a concretic example.
   5. Why there is no similar problem in protected objects?
       
3. [10 p] Deadlocks
   1. [2 p] Give a semaphore based solution to Dining Philosophers problem, that is vulnerable to deadlock. Give a deadlock scenario.
   2. [8 p] Deadlock can occur only when certain conditions are met. Describe these conditions and, for each of them, describe how you would modify your previous answer (in part a) such way that it avoids deadlock by breaking just this condition.
       
4. [10 p] Distributed mutual exclusion. Look at the token-passing Ricart-Agrawala algorithm (reverse side). Assume, that two processes A and B in different nodes want to enter the critical section, which is available. Assume also, that another node C has the token. There are no other processes sharing this critical section.
   1. On what basis is the decision made on who will enter the critical section next? Is it A or B? Why?
   2. Assume also, that C is now in critical section and that all messages sent by A and B have reached their destinations. Which one will get into critical section first, A or B? Why?
   3. Continuation for previous question. Can process C get into critical section 2nd time before both A and B have done it? Explain.
   4. Main and Receive must have their own critical sections for the algorithm to work correctly. What are they?
   5. What advantage does token-passing Ricart-Agrawala algorithm have as compared to ordinary Ricart-Agrawala algorithm?