Rinnakkaisohjelmistot
kuulustelu 23.8.2002


1. Kuvaa täsmällisesti seuraavat prosessien hallintaan liittyvät käsitteet:
   a) kriittinen alue (a critical section)
   b) synkronointi
   c) kohtaaminen (rendezvous).
   Havainnollista kutakin käsitettä käyttäen esimerkkinä tapausta, jossa 
   yksi prosessi kirjoittaa (monipaikkaiseen) puskuriin ja kaksi lukee siitä.
   (Algoritmia ei tarvitse kirjoittaa - mutta kyllä sen kirjoittaakin saa,
   jos se selittämistä  helpottaa.)
 
2. Esitä "nukkuvan parturin ongelman" ratkaisu käyttäen monitor-rakennetta.
   Signal-operaatio on tyyppiä "signal and continue" ja skeduloija antaa 
   signal-operaation vapauttamalle prosessille korkeamman prioriteetin kuin 
   monitor-kutsua vasta esittävälle prosessille (siis "entry"-jonossa ovat 
   "vapautetut" aina ennen "uusia"). 
   Tee ratkaisusta mahdollisimman yksinkertainen: varaudutaan vain yhteen 
   parturiin, ei tehdä tarpeettomia ehtojen tarkistuksia eikä tarpeettomia
   wait-signal -tahdistuksia. 
   Perustele lyhyesti ratkaisusi toimivuus.  
   (Kirjan ratkaisu on tarpeettoman monimutkainen, sen moitteettomasta
    toistamisesta saa n. 8 pistettä.)

3. Joen yli johtaa kapea silta, jonka autot voivat ylittää vain yhteen suun-
   taan kerrallaan. Mallita autot prosesseina ja liikenteenvalvoja monisäikei-
   senä prosessina. Kirjoita sillankäyttöongelman ratkaisu käyttäen etäprose-
   duurikutsuja (etäproseduurin suorittaa kutsun käynnistämä säie). Ratkaisun 
   täytyy sallia sillan riittävän tehokas käyttö (eli sillalla täytyy voida 
   olla useita autoja kerrallaan), mutta sen ei tarvitse olla reilu (odotusajat 
   saavat muodostua pitkiksi).
   
4. Lukkiutumisen välttämiseen (deadlock avoidance) voidaan käyttää ns pankkii-
   rin algoritmia: ennen resurssiyksikön myöntämistä jakelija tarkistaa aina 
   ensin, että jakelu ei voi johtaa lukkiutumiseen.
   a) Selitä algoritmin toimintaperiaate. 
   b) Laske algoritmia käyttäen seuraava esimerkki. Järjestelmässä on kolmea 
   resurssityyppiä A, B ja C. Resurssia A on 9 yksikköä, resurssia B 3 yksik-
   köä ja resurssia C 6 yksikköä. Tietyllä hetkellä varaustilanne on seuraavan-
   lainen:
      	prosessi	prosessille 	prosessin 
   			varattu		maksimitarve
      			A B C		A B C
   	P1		1 0 0		3 2 2
   	P2		5 1 1		6 1 3
   	P3		2 1 1		3 1 4
   	P4		0 0 2		4 2 2
   Prosessi P2 pyytää saada lisää yhden A-resurssin ja yhden C-resurssin.
   Voidaanko ne myöntää? Entä, jos ko pyynnön olisikin esittänyt P1? 

Kukin tehtävä: 15 p.