Harjoitus 3 s2005

Tässä on neljä hieman erilaista ratkaisua harjoitusten 3 tehtävään 3. Jos ratkaisuissa on painovirheitä tai muita vakavampia puutteita, niin kertokaan niistä Liisa Marttiselle.
Ratkaisuissa 3 ja 4 on Antti Miettunen jo havainnut joukon melko fataaleja virheitä: - Ratkaisu 3: jos tuottajassa while-silmukkaan ei jouduta, tilaa-semaforia ei koskaan varata. Kuitenkin se lopuksi vapautetaan. (Sama juttu dataa-semaforin kanssa kuluttajassa.) => ongelmia

Ratkaisu 4: liian löysä poissulkeminen päästää kuluttajan lukemaan, vaikka dataa ei olisi vielä ehditty kirjoittaa. ( count kasvatettiin 1:een, kaikki mutex:it jäivät auki, puskuriin ei vielä ehditty kirjoittaa mitään)
Voitte lähettää korjausehdotuksia ja myös lähettää omia ratkaisuja.

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

= = = = = = = = = = = = = == = = = = = == = = = = = == = = = = = == = = = = = == = = = = =

Ratkaisu 1: Selkeä ja toimiva, mutta turhan paljon rinnakkaisuutta rajoittava ratkaisu:

• puskuria käsittelee kerrallaan vain yksi prosessi, vaikka tuottaja ja kuluttaja voisivat käsitellä puskuria rinnakkain
• Puskuria käsitellyt prosessi antaa luvan seuraavalle prosessille edetä:
• tuottaja
  • varmistaa ensin, että puskurissa on tilaa ja odottaa sitten puskurin käsittelyvuoroa
  • kirjoittaa puskuriin ja kasvattaa laskuria
  • jos kirjoitti tyhjään puskuriin => antaa luvan yhdelle kuluttajalle lukea
  • jos vielätyhjää tilaa puskurissa => antaa yhdelle tuottajalle luvan kirjoittaa
• kuluttaja
  • varmistaa ensin, että puskurissa on dataa ja odottaa puskurin käsittelyvuoroa
  • lukee datan puskurista ja vähentää laskuria
  • jos luki tyhjästä puskurista => antaa luvan yhdelle tuottajille kirjoittaa
  • jos puskurissa on vielädataa => antaa luvan yhdelle kuluttajalle edetä

typeT buf[n];     /* n:n alkion kokoinen puskuri, johon talletetaan jotakin tyyppiä olevaa dataa*/
int front = 0,     /* puskurin alkio, josta seuraavaksi otetaan data  */
     rear  =  0;       /* se puskurin alkio, johon seuraavaksi talletetaan data */
int count = 0;  /* puskurissa olevien ('käyttämättömien') data-alkioiden määrä*/
sem dataa = 0, /* tyhjään puskuriin on nyt  talletettu dataa  eli sieltä voi ottaa dataa*/
sem  tilaa = 1; /*täydestäpuskurista otettu dataa  eli sinne mahtuu taas*/
sem mutex = 1;         /* tuottajien ja kuluttajien yhteisten muuttujien (=count) päivityksen*/
                       /* poissulkemiseen*/
    

process Producer [i=1 to M] {
     while(true) {
               .....
              produce data ..
              /*  mennään tallettamaan data puskuriin */
              /* Onko puskurissa tilaa?*/
              P(tilaa);  /*  tässä odotetaan, kunnes tilaa taas on  ja vuoro tulee*/
              P(mutex);  /*talletus sekä laskurin käsittely kaikki muut poissuljettuna! */
              buf[rear] = data;   rear = (rear+1) %n;
              count++;  /*laskurin kasvatus*/
              if (count = = 1) V(dataa); /* lisätty dataa tyhjään puskuriin => kuluttaja voi lukea*/
              if (count < n) V(tilaa);  /* vieläon tilaa => seuraava tuottaja saa tallettaa. */
              V(mutex);
         }
      }

process Consumer [i=1 to N] {
     while(true) {
               .....
               /*  mennään hakemaan  data puskurista */
               /* onko puskurissa uutta ('lukematomta') dataa?*/
               P(dataa);  /* Jos puskuri on tyhjä odotetaan tässä, kunnes dataa taas on */
               P(mutex); /* datan luku  sekä laskurin käsittely kaikki muut poissuljettuna! */
               data= buf[front];   front = (front+1) %n; 
               count --;  /* laskurin vähennys */
               if (count = = n-1) V(tilaa);  /* poistettu täydestäpuskurista => tuottaja voi tallettaa */
               if (count > 0) V(dataa);  /*vieläon dataa => seuraava kuluttaja  saa lukea */
               V(mutex);
               consume  data;
           }
       }
       
 ===================================================================================================================      

jokuType buf[n];  # puskuri, käyttö renkaana
int count = 0,    # montako alkiota puskurissa
    front = 0, 	  # alusta poistettavan indeksi (FCFS!)
    rear  = 0;	  # loppuun lisättävän indeksi
sem tilaa   = 1,   # auki  => tuottajat saa edetä
    dataa   = 0,   # kiinni => kuluttajat ei saa edetä
    mutex = 1, 	   # auki => saa käsitelläcount-laskuria

process Producer[i=1 to M]
{    jokuType data;  # kullakin ikioma (omasta pinosta!)
     while (true) {    
               ........   
              data = tuota_tuote();
              P(tilaa);	   # odota, ettäon tilaa ja oma vuoro edetä
	      # tilaa on binääri semafori => vain yksi tuottaja  voi olla toiminnassa kerrallaaan 
              buf[rear] = data; rear = (rear + 1) % n;
	      P(mutex);    # vain yksi  prosessi laskurin kimpussa
 	      count++;
              if (count < n) V(tilaa);   # jos tilaa, seuraava kuluttaja saa edetä	  
              if (count = = 1) V(dataa); #jos kirjoitti tyhjään puskuriin, lupa kuluttajille edetä
              V(mutex);
    }
}

process Consumer[i=1 to N] {
    jokuType data;

     while (true) {
	P(dataa);	# odota, ettäon dataa ja oma vuoro 
	# binäärisemafori dataa päästäävain yhden kuluttajan etenemään
           data = buf[front]; front = (front + 1) % n;

	P(mutex);
 	count--;
        if (count > 0) V(dataa); # jos on vielädataa, niin lupa seuraavalle  kuluttajalle edetä      	
        if (count = = n-1) V(tilaa);  #  luki täydestäpuskurista => lupa tuottajille edetä
        V(mutex);
        consume data 
     }
}

Ratkaisu 3: Ehtosynkronointia (condition synchronization) käyttävä ratkaisu. Tutkitaan ensin ehtoa (laskurin arvoa) ja sen perusteella mennään odottamaan puskurin käyttöä.
tuottaja : puskuri on täynnä (count = = n)
kuluttaja: puskuri on tyhjä (count = = 0)

Tässäon varottava, ettei jää odottamaan kriittisen alueen sisällä!

Prosessit herätetään jatkamaan aina kun mahdollista, mutta niille ei anneta mitään erityistä lupaa edetä yksinoikeudella (ei siis baton passing-tekniikka käytössä), vaan ne kilpailevat päivitykseen pääsystä. Kun ne uudestaan pääsevät jatkamaan, on varmistettava, että ehto on edelleen voimassa. Joku muu prosessihan on voinut jo ehtiä muuttaa ehtomuuttujaa! On siis tarpeen käyttää while-silmukkaa.

Rinnakkaisuuden rajoittamisessa samanlainen kuin ratkaisu 1.

   typeT buf[n];		# n puskurin alkioiden  lukumäärä
   int count = 0;		# laskuri täysien lukumäärälle
   sem mutex = 1,		# auki => saa käsitellälaskuria 
   sem dataa = 0,       # auki => saa kuluttaa
   sem tilaa = 1;       # auki => saa tuottaa

   process Producer[i = 1 to M]
   {
     while (true) {
        ...
        P(mutex);
        while (count == n ) {  
           V(mutex); 	# äLäodota kriittisen alueen sisällä!
	     P(tilaa); 	# odota kunnes tyhjiäpuskureita
	     P(mutex);	# varaa laskuri taas omaan käyttöön
        } 

	# HUOM: while tarpeen: toinen tuottaja saattaa ehtiäpaikalle
	# ennenkuin tämäon päässyt jatkamaan (mutex oli auki!)

        buf[rear] = data; rear = (rear + 1) % n;

        count = count + 1;
        if (count == 1) V(dataa);
        if (count < n) V(tilaa);
        V(mutex);
     }

   process Consumer[i = 1 to N]
   {
     while (true) {
        ...
        P(mutex);
        while (count == 0 ) {  
           V(mutex);	# älä odota kriittisen alueen sisällä!
	     P(dataa); 	# odota kunnes joku on täyttänyt puskurin
           P(mutex);   # tarvitaan taas yksinoikeus count-muuttujan tutkimiseen
        }
        result = buf[front]; front = (front + 1) % n;
        V(mutex);
        P(mutex);
        count = count - 1;
	  if (count == n - 1) V(tilaa);
        if (count > 1) V(dataa);
        V(mutex);
     }



===================================================================

Vapauttava jättää mutex-semafori kiinni, jolloin vapautettu pääsee heti jatkamaan yhteisellä kriittisellä alueella. Koska mutex jää kiinni, täytyy varmistaa, ettäj oku prosessi on todella odottamassa ja aikanaan avaa mutex-semaforin. Muuten seuraa lukkiutuminen eli kriittinen alue jää 'ikuisiksi ajoiksi' kiinni. Jotta voidaan olla varmoja, tarvitaan laskurit odottaville.

typeT buf[n];     /* n:n alkion kokoinen puskuri, johon talletetaan jotakin tyyppiäolevaa dataa*/
int front = 0,     /* puskurin alkio, josta seuraavaksi otetaan data  */
     rear  =  0;       /* se puskurin alkio, johon seuraavaksi talletetaan data */
int count = 0;   /*  puskurissa olevien ('käyttämättömien') data-alkioiden määrä*/
int crtwp=0;     /* odottavien tuottajien  lukumäärä*/
int nrwc = 0;    /* odottavien kuluttujajien lukumäärä*/
sem dataa = 0,  /*  tyhjään puskuriin on nyt  talletettu dataa  eli sieltä voi ottaa dataa*/
sem  tilaa = 0; /* täydestäpuskurista otettu dataa  eli sinne mahtuu taas*/
sem mutexD = 1,           /* tuottajien talletusten poissulkemiseen */
        mutexF = 1,       /*kuluttajien ottojen poissulkemiseen */
        mutex = 1;       /*tuottajien ja kuluttajien yhteisten muuttujien (=count) päivityksen*/
                          /*poissulkemiseen*/
    
process Producer [i=1 to M] {
     while(true) {
               .....
               produce data;
               /*  mennään tallettamaan data puskuriin */
               /* mahtuuko puskuriin?*/
               P(mutex);
               if (count = = n)  {               
                   nrwp ++;   /*yksi odottava lisää*/ 
                   V(mutex);
                   P(tilaa);    /*jos puskuri on täynnä, mennään odottamaan, että tulee taas tilaa */
                                /* huom! tässä mutex on yhä kiinni vapauttavan kuluttajan jäljiltä! */
                   nrwp --;  /*yksi odottava vähemmän */
               }
               count ++;  /* varataan  tila puskurista*/
               V(mutex); /* kriittinen alue auki */
                         /* ja sitten  talletetaan data puskuriin */
               P(mutexD);
               buf[rear] = data; 
               rear = (rear+1) %n;
               V(mutexD);
      /* oliko tämä ensimmäinen talletus tyhjään puskuriin ja onko odottavia kuluttajia*/
              P(mutex);
              if (count = = 1  AND  nrwc> 0) V(dataa);  /* ilmoitetaan, että puskuriin on tullut */
                                            /* taa dataa; mutex jää kiinni*/
               else V(mutex);   


process Consumer [i=1 to N] {
     while(true) {
               .....
             

               /*  mennään kuluttamaan  data puskurista */
               /* onko puskurissa dataa?*/
               P(mutex);
               if (count = = 0)  {
                    nrwc ++;   /*yksi odottava  kuluttaja lisää*/ 
                    V(mutex);
                    P (dataa);    /* jos puskuri on tyhjä, mennään odottamaan uutta dataa */
                     /* huom! tässä oltava mutex päällä ja laskuri jo kasvatettu*/
                      nrwc --;  /* yksi odottava vähemmän */
               }
               else  count --;  /* varataan data  puskurista*/
               V(mutex);      /* ja sitten otetaan data puskurista*/
               P(mutexF);
               data= buf[front]; 
               front = (front+1) %n;
               V(mutexF);
              /* tuliko täyteen puskuriin tyhjä tila ja onko odottavia tuottajia*/
                P(mutex);
               if (count = = n -1  AND  nrwp> 0) V(tilaa);  /* ilmoitetaan, että puskuriin on tullut taas tilaa;  
	                                                       /* mutex jää kiinni! */
               else V(mutex);  
               consume data;
    }
 }


======================================================================