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 - 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?

2 -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.

3 - 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"?

4 - 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.

5 - MUISTINHALLINTAA, PALVELUJÄRJESTYS

Luennolla on käsitelty yleistä resurssien hallintaa käyttäen esimerkkeinä muistinhallintarutiineja (ks. kohta Muistinhallinta 4: kalvot 3-37 ja 3-38)). Tarkastellaan siis tilannetta, jossa prosessi voi varata useita sivuja yhdellä pyynnöllä.

1. Selitä ratkaisurungossa käytettyjen semaforien (mutex, RQ[*].sem) tehtävät. Tee uskottavaksi, että 1) rutiinit toteuttavat poissulkemisehdot (safety properties, liveness properties) eikä kukaan nälkiinny (ts. resursseja annetaan, jos niitä on ja että 2) asiakkaita palvellaan FCFS-periaatteella.
   Selvitä erityisesti, mitä tapahtuu, jos prosessi menettää prosessorin GET-rutiinissa operaation V(mutex) jälkeen ja prosessorin saanut toinen prosessi aloittaa GET-rutiinin suorituksen. Vastaavasti, selitä mitä tapahtuu, jos REL-rutiinin suorituksessa V(RQ[i].sem) aiheuttaa prosessorin menetyksen.
2. Kirjoita täsmällisempi koodi kohtiin "request can not be satisfied", "take nbr_of_units for this process", "return units into pagepool" sekä tarkenna palvelua odottavien jonotus (~ indeksien päivitys). Oleta, että toteutuksen taulukko on riittävän suuri (QSIZE alkiota)!

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