Opiskeltava alue: Andrews: 4 Semaphores, Stallings 6.1-6.6: Concurrency - Deadlock and Starvation.

Harjoituksissa käytetään semaforeja poissulkemisessa ja synkronoinnissa, sekä pohditaan lukkiutumisongelmia. Harjoituksissa tulee esiin "Baton passing" -tekniikan käyttö ja siitä saadut hyödyt.

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

2 - TUNNELI, YKSISUUNTAINEN LIIKENNE JA "SEMAFORIVALOT"

Vuoren läpi on kaivettu etelä-pohjoissuunnassa tunneli, jossa autot voivat ajaa vain yhteen suuntaan kerrallaan. Tunnelia käyttävät autoprosessit kutsuvat proseduureja enter_tunnel(suunta) ja exit_tunnel(suunta) pyrkiessään tunneliin ja poistuessaan tunnelista. Suunta tarkoittaa auton etenemissuuntaa (etelään tai pohjoiseen). Autoprosessien koodi on:

   process car[1 to N] {
	...
	enter_tunnel(suunta);
	aja_tunnelissaa();
	exit_tunnel(suunta);
   }

Esitä proseduurien enter_tunnel() ja exit_tunnel() koodi. Ratkaisun täytyy sallia tunnelin tehokas käyttö, eli tunnelissa täytyy voida olla useita autoja kerrallaan. Sen ei tarvitse olla reilu, ts. odotusajat saavat muodostua pitkiksi. Perustele lyhyesti se, että ratkaisusi toimii.

[Vihje: tarvitset omat semaforit ja laskurit eri suuntiin ajaville autoille.]

3 - HUVIPUISTON KARUSELLI

Huvipuistossa on N asiakasprosessia ja yksi karuselliprosessi. Asiakkaat ajelevat kerta toisensa jälkeen karusellissa, johon mahtuu kerrallaan C asiakasta (C on pienempi kuin N). Karuselli käynnistyy kuitenkin vasta, kun se on täynnä. Kunkin ajokerran jälkeen kaikki asiakkaat poistuvat karusellista muihin puuhiin (kenties palatakseen karuselliin myöhemmin).

Kirjoita asiakkaiden ja karusellin koodien keskeiset osat. Karusellissa istuminen on asiakkaan koodissa pelkkää odotusta.

4 - ATERIOIVAT FILOSOFIT

a) Aterioivat filosofit on kirjallisuuden klassikko, mutta millaisia tietojenkäsittelyyn liittyviä tilanteita filosofien ongelma oikeastaan pyrkii havainnollistamaan? Mitä tällöin ovat filosofit, haarukat, spagetit ja mahdolliset sihteerit, jotka voisivat jaella haarukoita pyytäjille?

b) Lukkiutumisriskin syntymiselle on kolme edellytystä. Miten kukin näistä täyttyy aterioivien filosofien ongelmassa?

Voidaanko filosofien tapauksessa lukkiutuminen estää muuttamalla haarukoiden käyttösääntöjä siten, että jokin em. ehdoista ei täyty. Tarkastele kutakin sääntöä erikseen.

c) Filosofit toteavat, että vain kaksi heistä voi olla yhtäaikaa syömässä. He heittävät yhden haarukan menemään ja sopivat, että jokainen saa käyttää mitä tahansa kahta haarukkaa. Haarukoista huolehtimaan palkataan tarjoilija ja tiskaaja. Kun filosofille tulee nälkä, hän istahtaa omalle paikalleen pöytään ja pyytää tarjoilijalta haarukat. Filosofi odottaa, että saa tarjoilijalta kaksi haarukkaa. Kun filosofi on syönyt, hän palauttaa haarukat tiskaajalle. Ohessa filosofien koodi:

   process filosofi[i=1 to 5] 
   {
      while (true) {
        ajattele();
        V(pyydä_haarukat);
        P(saa_aloittaa);   
        syö();
        V(vapauta_haarukat);
      }
   }

Kirjoita tarjoilija- ja tiskaajaprosessien koodit. [Huomaa: Tässä odotetaan kahta erillista tapahtumaa: haarukoiden pyytämistä ja palauttamista. Se hoituu parhaiten s.e. kumpaakin varten on oma prosessi!]

5 - PANKKIIRIN ALGORITMI

Laske ns. pankkiirin algoritmia käyttäen seuraava esimerkki. Järjestelmässä on kolmea resurssityyppiä A, B ja C. Resurssia A on 9 yksikköä, resurssia B 3 yksikköä ja resurssia C 6 yksikköä. Tietyllä hetkellä varaustilanne on seuraavanlainen:

prosessi     varattu   pyytänyt    maxtarve
              A B C     A B C       A B C
   p1         1 0 0     0 0 0       3 2 2
   p2         5 1 1     1 0 1       6 1 3
   p3         2 1 1     0 0 0       3 1 4
   p4         0 0 2     0 0 0       4 2 2

Prosessi P2 pyytää saada lisää yhden A-resurssin ja yhden C-resurssin. Voidaanko se myöntää? Mitä tapahtuu pankkiirin algoritmin suorituksen jälkeen? Perustele vastauksesi esittämällä pankkiirin algoritmin suoritusvaiheet.

Entä, jos ko. pyynnön olisikin esittänyt P1?

Se tietää vähän, joka kertoo kaiken tietämänsä.