581332-8 Rinnakkaisohjelmistot

Erilliskuulustelu 28.1.2005
Kirjoita jokaiseen vastauspaperiisi nimikirjoituksesi ja nimen selvennys sekä kokeen nimi että päivämäärä.

Vastausohjeita:

Lue tehtävä kunnolla - ymmärrä tehtävä oikein. Mitä oikeastaan kysytään?
Mitä algoritmin halutaan tekevän? Jos tehtävän voi mielestäsi ymmärtää monin tavoin, selitä oma tulkintasi.
Vastaa selkeästi annettuun tehtävään ja perustele sanottavasi.
Käytä kurssikirjan syntaksimerkintöjä. Käytä kuvaavia muuttujien tunnuksia.
Kommentoi aina synkronointiin ja poisulkemiseen liittyvät kohdat: muuttujien käyttötarkoitus, sekä kohdat, joissa on synkronointia / poissulkemista.
Piirrä kuvia ja kaavioita, vaikka niitä ei erikseen pyydetä.

Tytöt ja pojat ja semaforit suihkussa (15 p)
Opiskelija-asuntolassa on yksi kylpyhuone, jota käyttävät sekä tytöt että pojat. Samaan aikaan kylpyhuoneessa voi kuitenkin olla vain joko tyttöjä tai vain poikia. Ohessa on annettu koodi poikaprosesseille:
```
  01: process Poika[i=1 to M]
  02: {
  03:    while (true) {
  04:       P(mutex);
  05:       count++;
  06:       if (count = = 1) P(proceed);
  07:       V(mutex);
  08:
  09:       käytä_kylppäriä();
  10:
  11:       P(mutex);
  12:       count--;
  13:       if (count = = 0) V(proceed);
  14:       V(mutex);
  15:    }
  16: }
```
1. Kirjoita vastaava koodi tyttöprosesseille, esittele ratkaisun muuttujat ja selitä niiden käyttötarkoitukset (Mihin käytetään? Miksi tarpeen?). (5 p)
2. Oleta, että kylpyhuone on varattu tytöille ja paikalle saapuu 3 poikaa. Selitä kuinka ratkaisu estää näitä poikaprosesseja pääsemästä kohtaan käytä_kylppäriä(). (5 p)
3. Muuta ratkaisua siten, että kylpyhuoneessa voi olla korkeintaan 5 tyttöä tai poikaa kerrallaan. Selitä miksi ratkaisusi toimii oikein. (5 p)
Pankkitilin yhteiskäyttö monitorin avulla (15 p)
Pankkitili on N:n henkilön yhteiskäytössä. Jokainen henkilöistä voi tallettaa tilille tai nostaa tililtä rahaa. Tili ei saa koskaan mennä negatiiviseksi. Jos tilillä ei ole tarpeeksi rahaa, niin nostopyyntöä viivytetään.

Kirjoita tilin käytöstä huolehtivan monitorin koodi. Laadi koodi myös henkilöprosesseille, jotka voivat pyytää joko jonkun rahasumman talletusta tai rahasumman nostoa. Voit olettaa, että rahasumman oikeellisuus (ei ole negatiivinen, on järkevissä rajoissa) on varmistettu jo jossain aikaisemmin. (10 p)
Muuta monitorisi toimimaan siten, että nostopyynnöt hoidetaan saapumisjärjestyksessä (FIFO) (tai laadi jo a)-kohdan monitorisi tällaisena). (5 p)
Parturit ja asiakkaat käyttäen sanomanvälitystä (15 p)
Esitä "nukkuvan parturin ongelman" ratkaisu käyttäen sanomanvälitystä. Partureita oletetaan olevan useita.

Esitä ensin sanallisesti tai selkeänä kaaviokuvana, miten parturit ja asiakkaat toimivat. (5 p)
Kirjoita ratkaisu, jossa parturi- ja asiakasprosessit viestivät sanomanvälitystä käyttäen. (10 p)
Lukkiutumisesta ja sen estämisestä (15 p)

Mitkä ovat lukkiutumiselle (deadlock) välttämättömät ehdot? Selvitä kunkin ehdon osalta, mitä mahdollisuuksia on estää ehdon toteutuminen ja näin välttyä lukkiutumiselta. (8 p)
Selitä ns. pankkiirin algoritmin (banker's algorithm) toimintaidea.(3 p)
Laske pankkiirin algoritmia käyttäen seuraava esimerkki.
Järjestelmässä on kolmea resurssityyppiä A, B ja C. Resurssia A on 6 yksikköä, resurssia B on 4 yksikköä ja resurssia C samoin 4 yksikköä. Tietyllä hetkellä varaustilanne on seuraavanlainen:
prosessille prosessin prosessi varattu maksimitarve A B C A B C P1 0 0 1 2 2 2 P2 4 1 0 5 1 1 P3 2 2 2 2 3 2
Prosessi P2 pyytää saada lisää yhden C-resurssin. Voidaanko se myöntää? Perustele vastauksesi. (4 p)

581332-8 Concurrent Systems

Separate examination 28.1.2005
Please, write on each paper the date and the name of the course as well as your name and signature.

Advise for good answers:

Read the question and figure out what it is that you are really asked to do. What the algorithm is required to do?

If, in your opinion, the question can be understood in different ways, explain your interpretation.

Give a clear answer to the given task. Give reasons.

Use the syntax given in the course book. Give your variables descriptive names.

Always comment points related to synchronization and mutual exclusion: explain for what variables are used, point out where synchronization or mutual exclusion is needed.

Draw diagrams and pictures, even when not specially asked to do that.

Boys and girls and semaphores in the shower (15 p)
A student residential home has only one bathroom, which is used by both boys and girls. At a time it can be used only either by boys or by girls. The code for Boy processes is given below:
```
  01: process Boy [i=1 to M]
  02: {
  03:    while (true) {
  04:       P(mutex);
  05:       count++;
  06:       if (count = = 1) P(proceed);
  07:       V(mutex);
  08:
  09:       use_ the _bathroom();
  10:
  11:       P(mutex);
  12:       count--;
  13:       if (count = = 0) V(proceed);
  14:       V(mutex);
  15:    }
  16: }
```
1. Write the corresponding code for Girl processes. Give declarations for the variables used in the solution and explain their usage (For what are they used? Why are they necessary?) (5 p)
2. Suppose that while the bathroom is reserved for girls, three boys arrive. Explain how the solution prohibits the Boy processes from entering the line 9: use_the_bathroom(). (5 p)
3. Change the solution so that there cannot be more than 5 boys or 5 girls in the bathroom. (5 p)
A shared savings account using monitor (15 p)
A savings account is shared by several people. Each person may deposit or withdraw funds from the account. The balance of the account must never become negative. If there is not enough money on the account, the withdrawal has to wait until there are enough funds.
Barbers and their clients using message passing (15 p)
Give a solution for the "sleeping barbers" problem using message passing. Assume that there are several barbers working in the barbershop.

Explain with words or with clear diagrams how barbers and client behave.(5 p)
Write a solution where barber and client processes communicate using message passing. (10 p)
About deadlocks and their prevention (15 p)

Which are the necessary conditions for a deadlock? Explain for each condition what possibilities there are to prevent the condition and thus avoid the deadlock. (8 p)
Explain the ideas of the banker's algorithm. (3 p)
Use the banker's algorithm to solve the following resource allocation problem. The system contains three different types of resources: A, B, and C. There are 6 units of A, 4 units of B, and 4 units of C. The system is in the following state:
allocated maximum demands process for processes of processes A B C A B C P1 0 0 1 2 2 2 P2 4 1 0 5 1 1 P3 2 2 2 2 3 2
The process P2 requests for one additional unit of C. Can it be granted? Give your reasons. (4 p)