581332-8 Rinnakkaisohjelmistot

Erilliskuulustelu 1.4.2005
Kirjoita jokaiseen vastauspaperiisi nimikirjoituksesi ja nimen selvennys sekä kokeen nimi ja päivämäärä.

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.

• Käytä kurssikirjan 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.

• Piirrä kuvia ja kaavioita, vaikka niitä ei erikseen pyydetä.

1. Tuottajat ja kuluttajat odottelemassa [15p]

   1. Miksi tuottajan ja kuluttajan väliin kannattaa laittaa puskuri? Miten puskurin koko vaikuttaa järjestelmän suorituskykyyn? (3 p)

   2. Tuottajien ja kuluttajien toiminnan tahdistus eli synkronointi voidaan toteuttaa 1) semaforeilla, 2) monitorilla, 3) sanomanvälitystä käyttävällä puskurin valvojalla tai 4) etäproseduureilla. Miten näissä eri tavoissa on toteutettu odottaminen eli missä tilanteissa prosessi odottaa, mitä se odottaa ja missä se odottaa? Käytä vastauksessasi kunkin menetelmän omia käsitteitä ja termejä.(12 p)

2. Muistinhallintaa semaforeilla [15 p]
   Muistinhallinta on toteutettu siten, että käyttäjillä on käytössä operaatiot request(amount) ja release(amount), missä amount on kokonaisluku. Kun prosessi kutsuu proseduuria request(), se joutuu odottamaan, kunnes sille voidaan antaa amount-parametrin ilmoittama määrä sivutiloja. Prosessi vapauttaa sivutiloja kutsumalla operaatiota release(). Muistin jakelussa noudatetaan "pienin pyyntö ensin" -periaatetta (odottajia palvellaan pyyntöjen suuruusjärjestyksessä).

3. Monitoroitu nostosilta [15 p]
   Joen yli on rakennettu nostosilta, jota pitkin autot voivat ylittää joen. Laivuri ajaa edestakaisin joella ja voi pyytää siltavahtia nostamaan sillan ylös. Laivalla on aina etuajo-oikeus, joten kun laivuri on pyytänyt siltaa nostettavaksi, siltavahti ei päästä enää uusia autoja sillalle. Kun laiva on ohittanut sillan, laivuri ilmoittaa siitä siltavahdille. Siltavahti laskee sillan alas ja sallii autojen taas käyttää siltaa.
   Kirjoita koodi sillan käyttöä valvovalle monitorille Silta sekä koodit laivuriprosessille, autoprosesseille ja siltavahtiprosessille.

4. Tietojen vaihtoa sanomanvälityksellä [15 p]
   Tietokoneverkossa on N samanlaista konetta, jotka on numeroitu 1-N. Koneiden kuormitusta pyritään tasaamaan siten, että uudet työt aloitetaan vähiten kuormitetuissa koneissa. Kukin koneen i valvojaprosessi Vi tietää oman koneensa kuorman Ki, jonka se osaa laskea sovitulla algoritmilla. Lisäksi sen tulee tietää, mitkä kaksi konetta ovat vähiten kuormitettu ja kuinka suuri niiden kuorma on.
   Valvojaprosessit kommunikoivat keskenään sanomanvälitystä käyttäen ja kommunikoinnin päätteeksi kaikki valvojaprosessit tietävät kahden vähiten kuormitetun koneen numerot ja kuormat.

   1. Miten tietojenvaihto valvojaprosessien välillä tapahtuu? Esitä kaaviokuvana tai muuten riittävän selkeästi valvojaprosessien keskinäinen kommunikointi, jonka tuloksena kaikilla on tieto kahdesta vähiten kuormitetusta koneesta.(5 p)

   2. Laadi tarvittava koodi valvojaprosessien kommunikointia varten. (10 p)

581332-8 Concurrent Systems

Separate examination 1.4.2005
Please, write on each paper the date and the name of the course as well as your name and signature.

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.

1. Producers and consumers waiting [15 p]

   1. What is the use of having a buffer between a producer and a consumer? How does the length of the buffer affect the performance of the system? (3 p)

   2. The syncronization of producers and consumers can be implemented using 1) semaphores, 2) a monitor, 3) a buffer manager using message passing, 4) remote procedures. How does each of these implement customer waiting? In which situations a process has to wait, what does it wait for and where does it wait? In your answer, use the concepts and terms of each method.

2. Memory management with semaphores [15 p]
   Memory management is implemented so that users can use two operations: request(amount) and release(amount), where amount is an integer. When a process calls request(), it delays until amount pages can be allocated to it. A process returns amount pages to the free pool by calling release(). The memory allocation is based on the "smallest request first" policy (the delayed processes are served in the order defined by the size of the memory request).
   Write the code for the operations request() and release(), which implement the memory management. However, only the parts related with delaying the processes and decision making are required, other administration of the memory allocation management need not be considered in detail.

3. A monitored lift bridge [15 p]
   Across a river there is lift bridge that lets cars cross the river. A skipper with his boat is moving up and down the river and can ask the bridge guard to lift the bridge. The boat has always the priority. When the skipper has asked the bridge to be lifted up, the bridge guard does not allow any more cars to enter the bridge. When the boat has passed the bridge, the skipper informs the bridge guard. The bridge guard lowers the bridge and lets the cars use the bridge.
   Write the code for the monitor Bridge that controls the usage of the lift bridge and also codes for the Skipper and the Guard and the Car processes.

4. Data exchange using messahe passing [15 p]
   In a computer network there are N similar computers numbered from 1 to n. The aim is to balance the load of the computers so that new jobs are started in the less loaded computers. A controlling process Ci in each computer i knows the load Li of its own computer as it can calculate the load using certain algorithm. Each controlling process should also know the two least loaded machines and their loads. The controlling processes communicate using message passing and after each communication phase they all know the numbers and loads of the two least loaded computers. (5 p)

   1. How do the controlling processes exchance information with each other so that they all learn about the two least loaded computers? Draw a diagram or explain clearly enough their communication. (5 p)

   2. Develop the needed code for the communication of the controlling processes. (10 p)