581332-8 Rinnakkaisohjelmistot

Kurssikoe 10.12.2004

  1. Vastaa seuraaviin kysymyksiin. [12 p]
    1. Mitä tarkoittaa, että tietty toimenpidesarja on suoritettava "atomisena"? Käytä esimerkkinä toimenpidesarjaa < x =x+1; y = y+1; >. (4 p)
    2. Mitä tarkoitetaan lukkiutumisella (deadlock), elolukkiutumisella (livelock) ja nälkiintymisellä (starvation)? (3 p)
    3. Miten etäproseduuri eroaa tavallisesta proseduurista? Mitä etäproseduuria kutsuttaessa tapahtuu kutsuvalle prosessille ja kutsutulle proseduurille? (3 p)
    4. Mikä on kriittinen alue (critical section)? (2 p)

  2. Sekoilua semaforeilla? [14 p]
    Oheinen ratkaisu tuottaja-kuluttaja-ongelmaan ei toimi oikein. Mitä virheitä ratkaisussa on ja mitä toimintaongelmia nämä virheet aiheuttavat? Onko mahdollista lisätä tuottajien ja kuluttajien rinnakkaisuutta? Jos on, niin miten? Korjaa koodi oikein toimivaksi tai kirjoita aivan oma ratkaisusi. Muista liittää kommentteja omaan koodiisi, vaikka annetussa koodissa ei niitä olekaan! 
    	    
	    char buffer[n];
            int  start = 0,  end = 0;
	    sem  empties = n, fulls =1, turn = 0;
   
            process Producer[i=1 to M] {
                char data;
                 ....
                while (true) {
                   .....
                   produce data;
                   P(empties);
                   P(turn);
                   buffer[end] = data; 
                   end = (end + 1) % n;     
                   V(fulls);
                   V(turn);
              }
         }

         process Consumer[i=1 to N] {
             char result;
             .....
             while (true) {
                .....
                P(turn);
                P(fulls);
                result=buffer[start]; 
                start= (start + 1) % n;
                V(turn);
                V(empties);
               use result;
           }
       }
  3. Spagettia monitorissa [13 p]
    Pitkän pohdinnan jälkeen aterioivat filosofit (N kappaletta) olivat viimein oivaltaneet, että yhdelläkin haarukalla on mahdollista syödä spagettia ja jonkun aikaa harjoiteltuaan olivat oppineet käteviksi yhdellä haarukalla syöjiksi. Nyt kaikki pääsivät vaikka yhtä aikaa syömään eikä kenenkään tarvinnut odotella nälkäisenä. Tästä tosin syntyi uusi ongelma, sillä pöydällä oleva spagettikulho oli melkein aina typötyhjä. Tähänkin keksittiin ratkaisu: otettiin apupoika ruokapalkalla (spagettia!) huolehtimaan ruuanvalmistuksesta. Aina kun kulho on tyhjä, poika valmistaa lisää spagettia, täyttää filosofien ruokakulhon kukkuroilleen (M lautasellista) ja vie sen pöydälle. Sitten poika syö keittiössä kattilan pohjalta ja jää odottetelemaan kulhon tyhjenemistä. Filosofit pääsevät taas normaalirutiiniinsa: syömään spagettia ja syömisen jälkeen ajattelemaan. Jokainen filosofi ottaa yhdellä syöntikerralla yhden lautasellisen. Kun kulho aikanaan tyhjenee, filosofit herättävät pojan valmistamaan lisää spagettia. Toteuta filosofit ja apupoika prosesseina, joiden toiminta synkronoidaan monitoria käyttäen. Kirjoita monitorin koodi sekä koodit filosofiprosesseille sekä apupoikaprosessille.

  4. Sanomanvälitystä Korvatunturilla [12 p]
    Lähes koko vuoden Pukin vetoporot vaeltavat Lapin tuntureilla ja syövät jäkälää muiden porojen kanssa. Jouluaaton lähestyessä vetoporot kokoontuvat Korvatunturille Pukin pajan läheisyyteen. Kun kaikki N vetoporoa ovat saapuneet paikalle, vetoporoista Petteri Punakuono ilmoittaa tästä Pukille. Pukki valjastaa porot lahjareen eteen ja niin lähdetään matkaan lahjoja jakamaan. Kun Pukki on saanut jaettua lahjat kaikille maailman lapsille, porot kiidättävät Pukin taikareen takaisin Korvatunturille, jossa Pukki kiittää poroja ja vapauttaa ne vaeltamaan muiden porojen kanssa. Toteuta Pukki ja porot prosesseina, jotka kommunikoivat sanomanvälitystä käyttäen. Piirrä kaaviokuva, josta selviää Pukin ja porojen välinen kommunikointi. Kirjoita Pukki-ja Petteri-prosessin ja muiden poroprosessien koodit.

Vastausohjeita:
Lue tehtävä kunnolla - ymmärrä tehtävä oikein. Mitä oikeastaan kysytään?
Mitä algoritmin halutaan tekevän? Jos tehtävän voi mielestäsi ymmärtää monin tavoin, selitä oma tulkintasi.
Vastaa selkeästi annettuun tehtävään ja perustele sanottavasi.
syntaksimerkintöjä. Käytä kuvaavia muuttujien tunnuksia.
Kommentoi aina synkronointiin ja poisulkemiseen liittyvät kohdat: muuttujien käyttötarkoitus, sekä kohdat, joissa on synkronointia / poissulkemista.

581332-8 Concurrent Programming

Course Examination 10.12.2004

  1. Answer the following questions.[12 p]
    1. What does it mean that a sequence of actions must be executed "atomically"? Use the sequence < x = x+1; y =y+1; > as an example. (4 p)
    2. What is meant by deadlock, livelock and starvation? (3 p)
    3. How does a remote procedure differ from a normal procedure? What happens, during a remote procedure call, to the calling process and to the called procedure? (3 p)
    4. What is a critical section? (2 p)

  2. Mixed up with semaphores? [14 p]
    The solution to the producer-consumer problem given below does not work correctly. What errors there are in the solution and what functional problems do these errors cause? Is it possible to increase parallelism for producers and consumers? If it is, then explain how. Fix the given code to work correctly or write your own solution. Remember to add comments to your code though the code given does not include any comments! 
    	    
	    char buffer[n];
            int  start = 0,  end = 0;
	    sem  empties = n, fulls =1, turn = 0;
   
            process Producer[i=1 to M] {
                char data;
                 ....
                while (true) {
                   .....
                   produce data;
                   P(empties);
                   P(turn);
                   buffer[end] = data; 
                   end = (end + 1) % n;     
                   V(fulls);
                   V(turn);
              }
         }

         process Consumer[i=1 to N] {
             char result;
             .....
             while (true) {
                .....
                P(turn);
                P(fulls);
                result=buffer[start]; 
                start= (start + 1) % n;
                V(turn);
                V(empties);
               use result;
           }
       }
  3. Spaghetti in a monitor [13 p]
    As a result of hard thinking the dining philosophers (N persons) had at last realized that it is really possible to eat spaghetti with only one fork and after having practiced for awhile had become very efficient eaters with one fork. Now they could eat even all at the same time and no one had to wait hungry for others to finish. But this caused a new problem as the spaghetti bowl at their table was almost always empty. The solution for this was to hire a help boy to make spaghetti. The philosophers can again return their normal routine of eating spaghetti and thinking.
    The boy makes more spaghetti, fills the bowl with it (M portions) and carries it to the table. Then the boy eats spaghetti in the kitchen (that is his salary) and falls asleep. Each philosopher when eating takes one portion of spaghetti. When the bowl is empty, the philosophers will wake up the boy to make more spaghetti.
    Represent the philosophers and the help boy as processes and use a monitor for their synchronization. Write code for the monitor and for the processes that simulate the actions of the philosophers and the help boy.

  4. Message Passing at Korvatunturi [12 p]
    Almost all the year the flying reindeers that draw the sleigh of Santa Claus in the Christmas Eve spend their time wandering around in Lappland with other reindeers. Nearby Christmas they start gathering to Korvatunturi where Santa Claus has his Christmas present factory. When all the N flying reindeers have arrived, the leader of the team, Rudolf the Rednose, informs Santa. Santa harnesses the reindeers and the sleigh full of presents starts its journey.
    When Santa has delivered all the presents to children around the world, they return to Korvatunturi. There Santa thanks the reindeers and unharnesses them to wander free with the other reindeers.
    Represent Santa Claus and the flying reindeers as processes, that communicate using message passing. Draw a diagram showing the communication between Santa and the reindeers. Write code for Santa, Rudolf and other reindeers.

    Advise for good answers:
    Read the question and figure out what it is that you are really asked to do.What the algorithm is required to do?
    If, in your opinion, the question can be understood in different ways, explain your interpretation.
    Give a clear answer to the given task. Give reasons.
    Use the syntax given in the course book. Give your variables descriptive names.
    Always comment points related to synchronization and mutual exclusion: explain for what variables are used, point out where synchronization or mutual exclusion is needed.
    Draw diagrams and pictures , even when not specially asked to do that.