SYNTAKSIA JA SPESIFIOINTIA: RINNAKKAINEN SUORITUS
Tarkastellaan seuraavaa ohjelmaa:

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

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

  
    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.

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

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

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.

   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ä!

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?

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.

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

  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.

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.

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

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.

1. 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?
2. Lukkiutumisriskin syntymiselle on kolme staattista 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.
3. 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!]

1. Kerro, miten monitori Bathroom toimii ja mihin sen muuttujia käytetään?
2. Toimiiko monitori kaikissa tilanteissa moitteettomasti? Jos ei toimi, niin mitä puutteita siinä on? Miten koodia pitäisi muuttaa, jotta monitori toimisi oikein?
3. Kirjoita koodit Girl- ja Boy-prosesseille, jotka käyttävät monitoria Bathroom kylpyhuoneen jakamiseen.

   monitor Bathroom {
   cond  bath_free;
   int girls = 0;
   int boys = 0;
   
   procedure Enter_Boy (){
         if (girls !=0) wait (Bath_free);
         boys ++;
       }
   
   procedure Enter_girl(){
        if (boys!=0) wait(Bath_free);
        girls++;
      }
   
   procedure Exit_boy(){
        boys --;
        if (boys==0)  signal_all(Bath_free);
      }
   procedure Exit_girl (){
        girls--;
        if (girls==0) signal_all(Bath_free);
      }
   }
   

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 ennenkuin poistuu paikalta. Seuraavat paikalle saapuvat mehiläiset jäävät odottamaan purnukan tyhjenemistä. Kun karhu on tyhjentänyt purkin, se päästää mehiläiset töihin ja käy itse nukkumaan.

Ohjelmoi purnukan täyttö ja tyhjentäminen monitoriin Honey_pot ja esitä mehiläisprosessien (N kpl) ja karhuprosessin koodi. Selvitä vielä sanallisesti missä tilanteissa tarvitaan poissulkemista ja synkronointia ja kuinka ne toteutuvat ratkaisussasi.

1. Alla oleva monitorin koodi ei toimi joka tilanteessa oikein. Selvitä, mitä ongelmia ohjelmassa on. Tutki esimerkiksi, mitä tapahtuu, kun potilaat ja lääkäri pääsevät monitoriin järjestyksessä:

         i) potilas1, lääkäri, potilas2;
         ii) potilas1, potilas2, lääkäri;
         iii) lääkäri, potilas1, potilas2; 
   

2. Korjaa koodi oikein toimivaksi ja varmista lisäksi, että potilaat pääsevät tutkimukseen saapumisjärjestyksessä.

       monitor Vastaanotto {
       cond sisään;
       cond ulos;
       cond tutki;
       boolean varattu  =  false;
          
      procedure Tulevastaanotolle ( ) {    # potilaan koodi
         if (varattu) wait(sisään);        # odota sisäänkutsua  
         varattu = true;        # merkitse varatuksi      
         mene tutkimushuoneeseen
         signal(tutki);    # ilmoita lääkärille
         ole tutkittavana
         wait(ulos);     #  jää odottamaan poistumismerkkiä
         poistu tutkimushuoneesta  
      }
     
      procedure Tutkipotilas ( ) {   # lääkärin koodi
         signal(sisään); # kutsu potilas sisään
         wait(tutki); # odotetaan potilasta   
         tutki potilas 
         signal(ulos);   # anna poistumissignaali
         varattu =false; # vapauta tutkimushuone    
         }
      }
                                                                                                                                                
     process Potilas(  )[i = 1 to n]  {
         while (true) {
            tee mitä ikinä teet
            tuntuu sairaalta
            call  Vastaanotto.Tulevastaanotolle ( );
           
         }
      }
   
      process Lääkäri(  ) {
         while (true)  call Vastaanotto.Tutkipotilas( );
       }
   
   

1. Esitä parturiongelmalle yksinkertaisin mahdollinen perusratkaisu ts. oleta signal-and-continue -semantiikka, ja että partureita ja tuoleja on vain yksi.
2. Laajenna parturiliikettä: yleistä ratkaisua siten, että parturiliikkeessä toimii useita partureita samaan aikaan.

   process customer[1:n] {
      while (true) {
         get serving from the pot; 
         eat; 
      }
   }

   process cook {
      while (true) {
         sleep; 
         put M servings in the pot; 
      }
   }

   {tee jotain muualla}; 
   {mene odotushuoneeseen}; 
   {kulje museossa}

ja oppaan

   {laske ryhmä museoon}; 
   {kulje museossa}

    * järjestelmässä on vain yksi monitori
    * monitorin condition-muuttujat esitellään vektorina c[n], jonka elementin tyyppi on "jono", ja
    * tyyppiin "jono" liittyy kaksi operaatiota: "insert" ja "remove". 

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