Opiskeltava alue: Andrews: 4.1-4.2 Semaphores: Basic Problems and Techniques, 4.4 Readers and Writers, 4.5 Resource allocation and scheduling. Ks. myös Stallings 5.4 Semaphores.

Tehtävissä harjoitellaan semaforien käyttöä poissulkemisessa ja synkronoinnissa. Lisäksi otetaan kantaa prosessien suoritusjärjestykseen eli vuorottamiseen.

1 - TERMEJÄ
Mitä tarkoitetaan seuraavilla termeillä:

1. Puomisynkronointi (barrier synchronization)
2. Halkaistu binäärisemafori (split binary semaphore)
3. Viestikapulan välitys (baton passing)?

2 - TUOTTAJA - PUSKURI - KULUTTAJA

1. Osoita, että luennolla esitetty tuottaja-kuluttaja -ongelman semaforipohjainen ratkaisu (Andrews kuva 4.5) toimii oikein eli toteuttaa tähän yhteyteen liittyvät poissulkemisehdot ja synkronointivaatimukset (ts. milloin prosessin on odotettava? milloin odotus päättyy?).
   Selvitä mitä tapahtuu, jos tuottajan operaatioiden P(empty) ja P(mutexD) suorituksen välillä toimii i) usea muu tuottaja, ii) usea kuluttaja.
2. Ratkaisussa on käytetty kahta poissulkemissemaforia (mutexD, mutexF). Mitä vaikutusta olisi sillä, että nämä korvattaisiin yhdellä ainoalla semaforilla (mutex)?
3. Miten algoritmin toimintaan vaikuttaisi, jos operaatiot P(empty) ja P(mutexD) vaihtaisivat paikkaa? Entä jos operaatiot V(mutexD) ja V(full) vaihtavat paikkaa? Entä jos mutexD ja mutexF on korvattu yhdellä semaforilla mutex, ja operaatiot P(mutex) ja P(full) vaihtavat paikkaa?

3 -SYNKRONOINTIA
Toteuta tuottaja-kuluttaja -algoritmi käyttäen binäärisemaforeja, ts. käyttäen sellaisia semaforioperaatioita P() ja V(), joiden toteutuksessa arvokenttä voi saada vain arvot 0 ja 1.

Vihje: Koska nyt ei semafori voi toimia laskurina, tarvitset oman laskurin, joka sisältää puskurissa olevien yksiköiden lukumäärän. Aseta binäärisemaforit vastaamaan järjestelmän kahta mielenkiintoista tilanmuutosta: "tyhjä puskuri" -> "puskuri ei tyhjä" ja "täysi puskuri" -> "puskuri ei täysi". Tarvitset siis kaksi binäärisemaforia: toisen estämään tuottajaa kirjoittamasta täyteen puskuriin, toisen estämään kuluttajaa lukemasta tyhjästä puskurista. Lisäksi on varmistettava yhteisten muuttujien käyttö atomiseksi.

4 - KARHU, PURNUKKA JA MEHILÄISET
Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukossa on vain syömistä ja odottelua. Mehiläiset kuljettavat hunajaa purnukkaan annos kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen annoksen tuonut mehiläinen herättää karhun, ja mehiläiset jäävät odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purnukan, se päästää mehiläiset töihin ja käy itse nukkumaan:

   process mehiläinen[i=1 to N] {
       while (true) {
          kerää_hunajaa();
          talleta_purnukkaan();  # vie hunaja-annos purnukkaan
       }
   }

   process karhu {
      while (true) {
          sleep();               # odota, että purnukka täysi
          tyhjennä_purnukka();   # syö hunajat pois purnukasta
      }
   }

Kirjoita rutiinit talleta_purnukkaan(), tyhjennä_purnukka() ja sleep() käyttäen semaforeja ja P/V-operaatioita. Osoita, että ratkaisusi toimii oikein (ts. selitä sanallisesti)? Mitä tässä yhteydessä tarkoittaa "oikein"?

5 - JOSKUS ON TILAA NELJÄLLE
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?).
2. Oleta, että kylppäri on varattu tytöille ja paikalle saapuu 3 poikaa. Selitä kuinka ratkaisu estää näitä poikaprosesseja pääsemästä kohtaan käytä_kylppäriä().
3. Muuta ratkaisua s.e. kylpyhuoneessa voi olla korkeintaan 4 tyttöä tai poikaa kerrallaan. Selitä miksi ratkaisusi toimii oikein.

6 - ERÄS sleep() JA wakeup()

Eräs käyttöjärjestelmä tarjoaa sovellusohjelmien käyttöön synkronointioperaatiot sleep() and wakeup(). Rutiinin sleep() kutsu pysäyttää kutsuvan prosessin. Rutiinin wakeup() kutsu herättää kaikki prosessit, jotka wakeup()-kutsun suoritushetkellä nukkuvat (ovat aiemmin kutsuneet sleep()-operaatiota ja kirjanneet itsensä nukkuvaksi). Molemmat operaatiot on tarkoitettu ko. järjestelmässä atomisiksi.

Rutiinien toteutuksen voi rakentaa kahdella eri periaatteella
a) kaikkien odottajien herätys tapahtuu wakeup()-rutiinissa
b) wakeup() herättää ensimmäisen sleep()-operaatiossa nukkuvan ja kukin herätetty herättää seuraavan (baton passing).

Ohessa on annettu ratkaisuehdotus kohtaan a).

  01: int sleepers = 0;
  02: sem mutex = 1;
  03: sem alarm = 0;
  04:
  05: procedure sleep()
  06: {
  07:   P(mutex);
  08:   sleepers++;
  09:   V(mutex);
  10:   P(alarm);
  11: }
  12:
  13: procedure wakeup()
  14: {
  15:    P(mutex);
  16:    while (sleepers > 0) { 
  17:      V(alarm);
  18:      sleepers--;
  19:    }
  20:    V(mutex);
  21: }

Annettu ratkaisu ei kuitenkaan toimi oikein. Selitä miksei!

Kirjoita baton-passing tekniikkaan perustuva oikein toimiva ratkaisu.

Minusta olisi voinut tulla kokki, mutta minulta jäi kana kynimättä.