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)

   int tcount = 0;
   sem tmutex = 1;
    01: process Tyttö[i=1 to M]
    02: {
    03:    while (true) {
    04:       P(tmutex);
    05:       tcount++;
    06:       if (tcount = = 1) P(proceed);
    07:       V(tmutex);
    08:
    09:       käytä_kylppäriä();
    10:
    11:       P(tmutex);
    12:       tcount--;
    13:       if (tcount = = 0) V(proceed);
    14:       V(tmutex);
    15:    }
    16: }
   

   Tytöillä on oma laskuri tcount, joka laskee tyttöjen lukumäärää. Tytöillä on myös oma semafori tmutex, joka vahtii, että vain yksi tyttö kerrallaan saa päivittää muuttujaa tcount. Tyttöjen ja poikien suihkuvuoroja säätelee yhteinen semafori proceed. Aina poikien tai tyttöjen ensimmäinen varaa (tai yrittää varata) semaforin proceed ja viimeiseksi suihkusta poistuva tyttö tai poika vapauttaa sen.

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)

   Ensimmäinen poika (poika1) jää poikien mutexin sisällä odottamaan tyttöjen poistumista semaforiin proceed (P(proceed)), joka on varattuna tytöille. Muut myöhemmin tulevat pojat (poika2 ja poika3) jäävät odottamaan semaforiin mutex (P(mutex), jonka ensimmäinen poika on varannut.

   Aikanaan viimeisenä poistuva tyttö vapauttaa kylpyhuoneen (V(proceed)) proceed- semaforissa odottavalle ensimmäiseksi tulleelle pojalle (poika1), joka pääsee etenemään ja vapauttamaan semaforin mutex (V(mutex)) seuraavalle pojalle (poika2), joka puolestaan päästää (V(mutex)) seuraavan pojan (poika3) etenemään kohti suihkua. (Tätä poikien suihkuun pääsemistä ei kyllä tehtävässä pyydetty.)

3. Muuta ratkaisua siten, että kylpyhuoneessa voi olla korkeintaan 5 tyttöä tai poikaa kerrallaan. Selitä miksi ratkaisusi toimii oikein. (5 p)

   Lisätään semafori mahtuu, joka päästää kylpyhuoneeseen korkeintaan 5 henkilöä. Ennen kylpyhuoneeseen menoa varmistetaan, että sinne mahtuu (P(mahtuu)), ja poistuttaessa vapautetaan tilaa seuraavalle (V(mahtuu)). Semafori ei vaikuta muuhun kuin kylpyhuoneen käyttöön.

   int tcount = 0;
   sem tmutex = 1;
   sem mahtuu= 5;
    01: process Tyttö[i=1 to M]
    02: {
    03:    while (true) {
    04:       P(tmutex);
    05:       tcount++;
    06:       if (tcount = = 1) P(proceed);
    07:       V(tmutex);
    08:       P(mahtuu);
    09:       käytä_kylppäriä();
    10:       V(mahtuu);
    11:       P(tmutex);
    12:       tcount--;
    13:       if (tcount = = 0) V(proceed);
    14:       V(tmutex);
    15:   
    16: }
   
   =======================================================================
   

1. 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)
2. Muuta monitorisi toimimaan siten, että nostopyynnöt hoidetaan saapumisjärjestyksessä (FIFO) (tai laadi jo a)-kohdan monitorisi tällaisena). (5 p)

a) Yksinkertaisimmillaan tässä voi käyttää 'covering condition' -tekniikkaa, jossa kaikki odottavat herätetään tarkastamaan, riittääkö saldo heidän nostoonsa. Välttämättä se ei riitä kenenkään odottajan tarpeisiin (A odottaa 100 euron nostoa ja B 120 euron, mutta herättäjä laittaa tilille vain 10 euroa, jolloin saldoksi tulee 80 euroa). Joku voi onnistua saamaan tarvitsemansa summan tai sitten uudet nostajat vievät rahan odottajien nenän edestä.

monitor Pankkitili {
cond riittää;   # odotettava, että tilille tulee lisää rahaa
int saldo = 0;    # tilin saldo

procedure nosto (int määrä)
{
    while (määrä < saldo) wait (riittää);
    saldo = saldo -määrä;

}


procedure pano(int määrä)
{
     saldo = saldo + määrä;
     signal_all(riittää);    
#  tai    if (!empty(riittää) signal_all (riittää)
}


process Henkilö[i = 1 to N] {
int raha = 0;   # rahamäärä
boolean on_rahaa = false,       # onko ylimääräistä rahaa
        tarvii_rahaa = false;  # onko tarvetta saada rahaa tililtä
while (true)
{
       tee  jotain josta joko tulee rahaa tai syntyy rahan tarvetta;
        if (on_rahaa) call Pankkitili.pano(raha);
        if (tarvii_rahaa) call Pankkitili.nosto (raha);
}

1. uudet pyynnöt eivät ohita jo odottavia;
2. eivät edes niitä prosesseja, jotka sillä hetkellä eivät enää ole jonossa, vaan odottavat vuoroaan päästäkseen monitoriin ja voidakseen lopulta tehdä nostonsa
3. eivät edes, vaikka ehtomuuttujan jono sillä hetkellä olisi tyhjä ja se ainoa odottaja odottaisi pääsyä monitoriin

monitor Pankkitili {
  int nostojono [i=0 to n-1];
  int eka = 0,     # ensimmäinen jonossa oleva  nostosumma
      seur = 0,     # seuraava tyhjä paikka jonossa
      lkm = 0;      # odottavien nostojen määrä
  cond odota_vuoroa;     # odotettava,kunnes oma vuoro tulee ja  nosto voidaan suorittaa
  int saldo = 0;   # tilin saldo

procedure nosto (int summa) {
    if (summa > saldo || !empty (odota_vuoroa) )   # saldo ei riitä tai on jo odottajia 
     #talletetaan oma summa nostojonoon  ja mennään itse ehtomuuttujan jonoon odottamaan
          if ( lkm <  n )      # taulukkoon  vielä mahtuu HUOM! Oletus on, että aina mahtuu 
          {   
              nostojono[seur] = summa; # vie summa nostojonoon (FIFO-järjestys)
              seur = (seur +1) mod n;  # päivitä taulukkomuuttajat
              lkm++;       
              wait (odota_vuoroa);  #mene odottamaan vuoroa; herätys FIFO-järjestyksessä
                                  # kun pääsee jatkamaan, niin herättäjä on jo kirjannut noston 
         } 
       else saldo = saldo – summa;  # jos kukaan ei odota ja saldoa riittää, niin tee oma nostosi
}


procedure pano (int summa) {
     saldo = saldo + summa;  # voidaanko  nostoja nyt suorittaa?
     # tässä ratkaisussa herättäjä käsittelee kaikki ne nostot, joihin
     #saldo riittää, siksi while 
     while (!empty(odota_vuoroa)&&saldo > nostojono[eka] )   
     

     {     # jonossa on odottajia ja  saldo riittää ensimmäiselle odottajalle
           signal(odota_vuoroa); # vapauta seuraava odottaja 
            saldo = saldo –nostojono[eka];  #  kirjaa  odottajan nosto ja päivitä saldo
            eka = (eka + 1) mod n;
            lkm --; 
}

=======================================================================
 

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

a) Tässä piti selittää, miten asiakkaat ja parturit toimivat ja kommunikoivat. Useimmat olivat sen osanneet.

b) Tässä on hyvin yksinkertainen ratkaisu, jossa parturin ja asiakkan viestintä on minimaalista

   type kind = enum(haircut, shaving, ... );
   chan  service_queue(int id, kind op),#one queue for all customers
       goodbye[M]();			#one"reply"-channel for each customer
 
 process client C[i = 0 to M-1] {
     ...
     op = "haircut";       #specify the operation
     send service_queue(i,op);	     #inform the barber and ...
     receive goodbye[i];             #... wait for a reply 
                                     #(operation has been executed)
     ...
   }
   

   process barber[j = 0 to N-1]  {
     while(true) {
       receive service_queue(client,operation);  #wait for the next customer
       execute(client, operation);		 #service execution
       send goodbye[client]();			 #confirm
     }
   }  

Tässä vähän pidempi ratkaisu, jossa asikas ja parturi kommunikoivat enemmän keskenään:

chan uusiasiakas (int id, string viesti); # kanava, johon asiakkaat ilmoittautuvat
chan asiakkaat [M](int id, string viesti); # kullakin asikkaalla oma kanava
chan parturit[N](string viesti); # kullakin parturilla oma kanava

process asiakas [i= 1 to M] {
     int i, j;
     string sanoma;
     while (true) {
          anna tukan kasvaa;
         #  mene parturiin 
         send uusiasiakas(i,“tukanleikkuu”); # ilmoittaudu 
         receive asiakkaat[i] (j, sanoma);  # odottele vapaan parturin  vastausta omassa kanavassa                                      
          # j on ko. parturin tunnus, itse viestillä ei ole tässä  merkitytsä 
         istu parturin j tuoliin;
         send parturit [j] (“pelkkälyhennys”);   #  ilmoita parturille, että voi aloittaa
         receive asiakkaat[i](j,sanoma);  # odottele kunnes valmista ja  voit poistua
         poistu parturista;
         send parturit[j](“maksoinjo!”);  # ilmoita parturille, että tämä voi
                                          # ottaa seuraavan asiakkaan 
    }
}
  

process parturi[j=1 to N] {
     int i, j;
     string sanoma;
     while (true) {
         receive uusiasiakas(i,sanoma);   # odottele uusia asiakkaita torkkuen; 
                                          # i = asiakkaan tunnus
         send asiakas [i](j, “istutuoliin”); # ilmoitetaan oman kanavan tunnus j
         receive parturit[j](sanoma);   #  odotellaan, kunnes asiakas on tuolissa
         suoritetaan sanoman kertoma tehtävä;
         send asiakas[i](j, “20euroa”);  # ilmoitetaan asiakkaalle valmistumisesta
         receive parturit[j](sanoma);  #odotetaan, että asiakas maksaa ja poistuu
      }
}
 

         

  asiakkaan koodi
     ..............
    send asiakkaat[i ](i, “pelkkä lyhennys”);   # ilmoita parturille, että voi aloittaa
    receive asiakkaat[i](j,sanoma);  # odottele kunnes valmista ja  voit poistua

======================================================================

1. 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)
2. Selitä ns. pankkiirin algoritmin (banker's algorithm) toimintaidea.(3 p)
3. Laske pankkiirin algoritmia käyttäen seuraava esimerkki.
4. 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)

   a) Lukkiutumisen välttämättömät ehdot

   1. mutual exclusion
      resurssia voi kulloinkin käyttää vain yksi pyritään lisäämään resurssien yhteiskäyttöisyyttä (ei kovin helppoa esim. haarukka, jolla kaksi voi samanaikaisesti syödä) tai hankitaan lisää resursseja.

   2. hold and wait
      Prosessi pitää halussaan jo varaamiaan resursseja, vaikka ei voikaan niitä vielä käyttää, koska osa resursseista puuttuu. Sallitaan resurssien varaus vain, jos samalla kertaa saa haltuunsaa kaikki tarvitsemansa resurssit. (Filosofin on saatava molemmat haarukat.)

   3. no preemption resursseja
      eli ei voi ottaa toiselta pois 'väkisin'. a philosopher is not allowed to take the neighbor's fork by force; Esim. Resurssien valvoja tai korkeamman prioriteetin prosessi voisi 'riistää' resurssit alhaisemman prioriteetin prosessilta. Sovelluksesta riippuu, onko keino hyödyllinen.

   4. circular wait prosessit
      odottavat resursseja, jotka ovat toisten odottavien prosessien hallussa. Muutetaan rersurssien varausjärjestystä, esim. kaikki resurssit varattava tietyssä järjestyksessä. (yksi filosofeista varaakin ensin vasemman puolkeisen haarukan, kun kaikki muut ottvat oikean puoleisen ensin).

      Arvostelusta: 1 p itse ehdosta ja 1 p sen toteutumisen estämisestä.

   b) Pankiirin algoritmi varmistaa ettei resurssin luovuttamien aiheuta lukkiintumista, vaan kaikki prosessit pystytään suorittamaan loppuun vaikka kukin prosessi tarvitsisi maksimaalisen määrän resursseja (pahin tapaus) eli löyttyy jokin suoritusjärjetys, jossa prosessit jossakin järjestyksessä pystytään suorittamaan. Resurssi luovutetaan vasta kun on todettu, ettei se aiheuta minkään prosessien lukkiutumista.

   Arvostelusta:

   • käytetään lukkiutumisen välttämiseen => 1 p
   • kaikki prosessit voidaan suorittaa loppuun resurssin luovuttamisenkin jälkeen => 1 p
   • pahimmassa mahdollisessa tilanteessa eli jokainen tarvitsee maksimimäärän resursseja => 1 p

   c) Prosessin P2 pyyntöön voidaan suostua. Vaikka suostumisen jälkeen olisi vapaana vain 1 kappale resurssia B, niin se riittäisi prosessille P3. P3 voidaan suorittaa loppuun, sillä se maksimissaan tarvitsee lisää vain yhden B-resurssin. P3:lta taas vapautuis resursseja niin, että ne riittävät P1:n ja P2:n maksimitarpeisiin. Suostuminen ei aiheuta lukkiutumista, joten P2 saa tarvitsemansa yhden C- resurssin.

   Arvostelusta:

   • oikea vastaus ja riittävät perustelut => 4 p
   • lasku- ja huolimattonuus virhe => -1 p
   • ymmärretty asia jotenkin väärin “voidaan antaa, mutta vasta myöhemmin” => 2 p
   • voidaan antaa, koska resursseja riittää => 1 p