8.-12.11.2004

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

A) Tarkastellaan seuraavia kolmea lausetta

    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;

B) Tarkastellaan seuraavaa ohjelmaa

    int x = 0, y = 10;
    co  while (x != y)  x = x + 1;
    //  while (x != y)  y = y - 1;
    oc

Päättyykö ohjelman suoritus aina / joskus / ei koskaan? Selitä!

2 - OHJELMAKOODIN LUKEMISTA

a) Selvitä, miten luentokalvossa 1-50 ja kurssikirjassa sivulla 25 koodina annetut worker-prosessit oikein toimivat.
b) Worker-prosessit kommunikoivat coordinator-prosessin kanssa. Kirjoita tämän coordinator-prosessin koodi.

3 - AVAIN TODELLISUUTEEN ON LUKOSSA

a) 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.

b) Voitaisiinko LOCK- ja UNLOCK-operaatiot toteuttaa vain estämällä keskeytykset kriittisen alueen suorittamisen ajaksi?

c) P()- ja V()-operaatiot ovat käyttöjärjetelmän ohjelmoijille tarjoamia palveluja. Mitkä toiminnot P()- ja V()-operaatioiden toteutuksessa (katso kalvo 2-25 tai kalvo 2-26) 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?

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

4 - SEMAFOREJA KÄYTÄNNÖN ELÄMÄSSÄ??

a) 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.

b) 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.

[älä suotta anna hienon sanan 'semafori' hämätä. Kyse on loppujen lopuksi aika yksinkertaisesta ja ymmärrettävästä käsitteestä!]

5 - 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:          sleep(random(1000*museo_time));
   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:          sleep(random(1000*ride_time));
   19:          V(passenger_released);
   20:     }
   21: }

Toimiiko tämä ratkaisu oikein? Aina? Joskus? Selitä!

[an error occurred while processing this directive]