Opiskeltava alue: Andrews 2.1-2.5 (mm. Atomic actions and Await statements), 3.1-3.2 (Critical section problem, Spin locks), 4.1-4.2 (Semaphores), 6.3 (Implementing semaphores in kernel). Ks. myös Stallings 5.1, 5.3-5.4 (Principles of concurrency, Mutual exclusion: hardware support, Semaphores).
Tehtävien tavoitteena on saada tuntumaa tavanomaisimpiin rinnakkaisten järjestelmien ongelmakohtiin ja tutustua semaforien käyttöön poisulkemisessa ja synkronoinnissa.

1. SYNTAKSIA JA SPESIFIOINTIA: RINNAKKAINEN SUORITUS
   Tarkastellaan seuraavaa ohjelmaa:

       S1:  x = x + y;
       S2:  y = x - y;
       S3:  x = x - y;
       S4:  print x,y

   Oletetaan, että muuttujien alkuarvot ovat x == 2 ja y == 5. Missä järjestyksessä lauseet suoritetaan ja mitkä ovat muuttujien arvot seuraavien lauseiden suoritusten jälkeen? Selitä miksi!

       
       a) S1; S2; S3; S4;
       b) co <S1;> // <S2;> // <S3;> oc; S4;
       c) co <await (x>y) S1; S2; > // <S3;> oc; S4;

2. PÄÄTTYYKÖ SUORITUS?
   Tarkastellaan seuraavaa ohjelmaa:

     
       co  <await (x > 0)   x = x - 1;>   /*S1*/
       //  <await (x < 0)   x = x + 2;>   /*S2*/
       //  <await (x == 0)  x = x + 5;>   /*S3*/  
       oc
   

   Millä x:n alkuarvoilla ohjelma päättyy eli sen kaikki haarat saadaan suoritettua? Mitkä ovat vastaavat x:n arvot tällöin? Perustele vastauksesi.

3. PROSESSIEN TAHDISTUSTA
   Semaforeilla voidaan tahdistaa prosessit toimimaan halutussa järjestyksessä. Näytä kuinka seuraavat kolme tulostavaa prosessia voidaan semaforeilla pakottaa toimimaan sellaisessa järjestyksessä, että ne yhdessä tulostavat lauseen:Ihminen, joka ei tee virheitä, ei tavallisesti tee muutakaan.

       P1                                P2                           P3
      .....                            ......                       .......
   write("tee virheitä, ");         write("joka ei ");          write("Ihminen, ");  
      .....                         write("ei tavallisesti ");       ..... 
   write("tee muutakaan.");            .......   
     .......  
   

4. AVAIN TODELLISUUTEEN ON LUKOSSA
   1. Mitä ongelmia syntyy operaatioiden LOCK / UNLOCK käytöstä, jos KJ käyttää prosessorin vuorottamisessa prioriteetteja? Tarkastele tilannetta i) yhden prosessorin ja ii) kahden prosessorin koneella.
   2. Voitaisiinko LOCK- ja UNLOCK-operaatiot toteuttaa vain estämällä keskeytykset kriittisen alueen suorittamisen ajaksi?
   3. P()- ja V()-operaatiot ovat käyttöjärjetelmän ohjelmoijille tarjoamia palveluja. Mitkä toiminnot P()- ja V()-operaatioiden toteutuksessa (katso kalvo 2-29 tai kalvo 2-30) vaativat poissulkemista 'alemman tason' menetelmin (ts. niiden koodit on ohjelmoitava kriittisiksi alueiksi)? Selitä, miten P/V-rutiinien kriittiset alueet saadaan toteutettua jakamamattomina (atomisesti) i) yhden prosessorin ja ii) kahden prosessorin koneella?
   4. Mitä hyötyä / haittaa olisi siitä, että P() ja V() -operaatioiden toteutus tehtäisiin poissulkemisen osalta mahdollisimman hienojakoiseksi (ts. vain minimikäskyt kriittisen alueen sisään) sen sijaan, että koko operaatiot suljettaisiin kriittiseksi alueeksi? Kuinka vähän keskeneräisten kutsujen rinnakkaisuutta rajoittaviksi P/V-rutiinien toteutus ylipäätään voidaan saada, jos kutsut kohdistuvat i) samaan semaforiin tai ii) eri semaforeihin?

5. SEMAFOREJA KÄYTÄNNÖN ELÄMÄSSÄ??
   1. Ulkoilmaravintolaan otetaan korkeintaan 25 henkilöä kerrallaan. Kun terassi on täynnä, ei sinne päästetä lisää janoisia. Asiakkaiden pääsyä terassille valvoo semafori Portsari, jolta asiakas hankkii sisäänpääsyluvan. Poistuessaan asiakas ilmoittaa paikan vapautumisesta semaforille Portsari. Kirjoita asiakkaiden koodi (asiakkaita on X kappaletta). Selitä toiminta myös sanallisesti.
      
   2. Pienellä hiekkakuopalla on töissä yksi kaivuri ja useita kuormureita. Selvästikään kaivuripappa ei saa mättää kuormaa, ellei kuopalla ole kuortsikkaa, eikä kuortsikkakuski saa ajaa kuopan pohjalle, ellei kaivuri ole vapaa mättelemään (kuopalle sopii vain yksi auto kerrallaan). Toisaalta kuormuri ei saa poistua kuopalta ellei kuorma ole valmis. Esitä sekä kaivuriprosessin että kuormuriprosessin koodi (vapaamuotoisesti). Käytä semaforeja synkronointiin.

6. SYNKRONOINTIA JURASSIC PARKISSA Jurassic Park eläinpuistossa on dinosaurusmuseo ja puisto, jossa voi tehdä safariajelua autoilla. Asiakkaat (M kpl) ohjataan ensin museoon, jossa satunnaisen ajan vietettyään he menevät safariautoille (N kpl). Jos paikalla on vapaa auto, yksi asiakas pääsee autoon ja lähtee ajelulle. Ajelun pituus vaihtelee, sillä asiakas voi pysäyttää auton välillä. Jos kaikki n autoa ovat safarilla, uusien asiakkaiden on odotettava museon luona. Jos auto palaa museolle, mutta yhtään asiakasta ei ole paikalla, jää auto odottamaan. Alla on semaforeja käyttävä ehdotus asiakas- ja autoprosessien synkronoimiseksi:

      01: sem car_avail = 0, car_taken = 0, car_filled = 0, 
      02:     passenger_released=0;
      03:
      04: process passenger[i=1 to M]
      05: {
      06:     while (true) do {
      07:          ...
      08:          kuluta satunnainen aika museossa;
      09:          P(car_avail); V(car_taken); P(car_filled);
      10:          P(passenger_released);
      11:     }
      12: }
      13:
      14: process car[i=1 to N]
      15: {
      16:     while (true) {
      17:          V(car_avail); P(car_taken); V(car_filled);
      18:          kuljeta asiakasta safariparkissa;
      19:          V(passenger_released);
      20:     }
      21: }

   Selitä, mihin semaforeja car_avail, car_taken, car_filled ja passenger_released käytetään, sekä miten niillä toteutetaan passenger- ja car-prosessien toiminnan tahdistus. Toimiiko tämä ratkaisu oikein? Aina? Joskus? Selitä!

   Oppimisen salaisuus on uteliaisuudessa.