29.3. -2.4.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. 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 - KESKITETTY vs TOISINNETTU LIPPUPALVELU

Maanlaajuinen lippupalvelu voidaan toteuttaa käyttäen yhtä keskitettyä palvelinta, johon kaikki lipputoimistot ovat yhteydessä. Mitä rinnakkaisuudesta aiheutuvia ongelmia pitää ottaa huomioon?

Suorituskyvyn parantamiseksi palvelin voidaan toisintaa, ts. otetaan käyttöön toinen palvelin, jossa on täsmälleen samat tiedot. Mitä hyötyä / haittaa toisinnon käyttämisestä koituu?

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) Mitkä kohdat P() ja V()-operaatioiden toteutuksessa vaativat poissulkemista 'alemman tason' menetelmin (ts. on ohjelmoitava kriittisiksi alueiksi)? Miten P/V-rutiinien kriittiset alueet saadaan toteutettua jakamattomina i) yhden prosessorin ja ii) kahden prosessorin koneella?

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

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 asiakkaiden ja autojen 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ä!

L A S K A R I O H J E I T A
Harjoituksista voit saada kaikkiaan 9 pistettä.
Tavalliseen tapaan tehtyjen tehtävien määrän perusteella voit saada 6 pistettä. Kaikkiaan tehtäviä on 30 kappaletta ja pisteitä tehdyistä tehtävistä saa seuraavasti:

          merkattuja tehtäviä           pisteitä
                    6                        1
                   10                        2
                   14                        3
                   18                        4
                   22                        5
                   26                        6
          
 

Tehtävät tehdään etukäteen ja ne käsitellään yhdessä harjoituksissa. Mitä perusteellisemmin olet valmistautunut harjoituksiin tehtäviä tekemällä ja kirjaa lukemalla, sitä hyödyllisempiä harjoitustilaisuudet ovat. Harjoituksissa voit myös kysyä itsellesi epäselviksi jääneitä kohtia.

Tehtäväpisteiden lisäksi aktiivisesta kurssiin osallistumisesta voi saada 3 pistettä. Aktiivinen osallistuminen tarkoittaa sitä, että tuo harjoitustilaisuuteen lyhyen, noin yhden sivun selvityksen siitä, mitä kurssilla on edellisellä viikolla käsitelty eli mitkä ovat olleet tärkeimmät asiat sekä omat kommentit siitä, mitä on ollut helppo oppia ja mikä hankalaa ja erityisesti, mikä on jäänyt epäselväksi. Kyseessä on siis jonkinlainen minimaalinen oppimispäiväkirja. Kukin selvitys tuottaa 1/2 pistettä ja kaikki kuusi yhteensä sen 3 pistettä.

[an error occurred while processing this directive]