01: process Poika[i=1 to M] 02: { 03: while (true) { 04: P(mutex); 05: count++; 06: if (count = = 1) P(proceed); 07: V(mutex); 08: 09: käytä_kylppäriä(); 10: 11: P(mutex); 12: count--; 13: if (count = = 0) V(proceed); 14: V(mutex); 15: } 16: }
int tcount = 0; sem tmutex = 1; 01: process Tyttö[i=1 to M] 02: { 03: while (true) { 04: P(tmutex); 05: tcount++; 06: if (tcount = = 1) P(proceed); 07: V(tmutex); 08: 09: käytä_kylppäriä(); 10: 11: P(tmutex); 12: tcount--; 13: if (tcount = = 0) V(proceed); 14: V(tmutex); 15: } 16: }Tytöillä on oma laskuri tcount, joka laskee tyttöjen lukumäärää. Tytöillä on myös oma semafori tmutex, joka vahtii, että vain yksi tyttö kerrallaan saa päivittää muuttujaa tcount. Tyttöjen ja poikien suihkuvuoroja säätelee yhteinen semafori proceed. Aina poikien tai tyttöjen ensimmäinen varaa (tai yrittää varata) semaforin proceed ja viimeiseksi suihkusta poistuva tyttö tai poika vapauttaa sen.
Ensimmäinen poika (poika1) jää poikien mutexin sisällä odottamaan tyttöjen poistumista semaforiin proceed (P(proceed)), joka on varattuna tytöille. Muut myöhemmin tulevat pojat (poika2 ja poika3) jäävät odottamaan semaforiin mutex (P(mutex), jonka ensimmäinen poika on varannut.
Aikanaan viimeisenä poistuva tyttö vapauttaa kylpyhuoneen (V(proceed)) proceed- semaforissa odottavalle ensimmäiseksi tulleelle pojalle (poika1), joka pääsee etenemään ja vapauttamaan semaforin mutex (V(mutex)) seuraavalle pojalle (poika2), joka puolestaan päästää (V(mutex)) seuraavan pojan (poika3) etenemään kohti suihkua. (Tätä poikien suihkuun pääsemistä ei kyllä tehtävässä pyydetty.)
Lisätään semafori mahtuu, joka päästää kylpyhuoneeseen korkeintaan 5 henkilöä. Ennen kylpyhuoneeseen menoa varmistetaan, että sinne mahtuu (P(mahtuu)), ja poistuttaessa vapautetaan tilaa seuraavalle (V(mahtuu)). Semafori ei vaikuta muuhun kuin kylpyhuoneen käyttöön.
int tcount = 0; sem tmutex = 1; sem mahtuu= 5; 01: process Tyttö[i=1 to M] 02: { 03: while (true) { 04: P(tmutex); 05: tcount++; 06: if (tcount = = 1) P(proceed); 07: V(tmutex); 08: P(mahtuu); 09: käytä_kylppäriä(); 10: V(mahtuu); 11: P(tmutex); 12: tcount--; 13: if (tcount = = 0) V(proceed); 14: V(tmutex); 15: 16: } =======================================================================
a) Yksinkertaisimmillaan tässä voi käyttää 'covering condition' -tekniikkaa, jossa kaikki odottavat herätetään tarkastamaan, riittääkö saldo heidän nostoonsa. Välttämättä se ei riitä kenenkään odottajan tarpeisiin (A odottaa 100 euron nostoa ja B 120 euron, mutta herättäjä laittaa tilille vain 10 euroa, jolloin saldoksi tulee 80 euroa). Joku voi onnistua saamaan tarvitsemansa summan tai sitten uudet nostajat vievät rahan odottajien nenän edestä.
Raskas tekniikka, mutta toimiva.monitor Pankkitili { cond riittää; # odotettava, että tilille tulee lisää rahaa int saldo = 0; # tilin saldo procedure nosto (int määrä) { while (määrä < saldo) wait (riittää); saldo = saldo -määrä; } procedure pano(int määrä) { saldo = saldo + määrä; signal_all(riittää); # tai if (!empty(riittää) signal_all (riittää) } process Henkilö[i = 1 to N] { int raha = 0; # rahamäärä boolean on_rahaa = false, # onko ylimääräistä rahaa tarvii_rahaa = false; # onko tarvetta saada rahaa tililtä while (true) { tee jotain josta joko tulee rahaa tai syntyy rahan tarvetta; if (on_rahaa) call Pankkitili.pano(raha); if (tarvii_rahaa) call Pankkitili.nosto (raha); }b) Nostopyyntöjen käsittely niiden saapumisjärjestyksessä edellyttää, että
monitor Pankkitili { int nostojono [i=0 to n-1]; int eka = 0, # ensimmäinen jonossa oleva nostosumma seur = 0, # seuraava tyhjä paikka jonossa lkm = 0; # odottavien nostojen määrä cond odota_vuoroa; # odotettava,kunnes oma vuoro tulee ja nosto voidaan suorittaa int saldo = 0; # tilin saldo procedure nosto (int summa) { if (summa > saldo || !empty (odota_vuoroa) ) # saldo ei riitä tai on jo odottajia #talletetaan oma summa nostojonoon ja mennään itse ehtomuuttujan jonoon odottamaan if ( lkm < n ) # taulukkoon vielä mahtuu HUOM! Oletus on, että aina mahtuu { nostojono[seur] = summa; # vie summa nostojonoon (FIFO-järjestys) seur = (seur +1) mod n; # päivitä taulukkomuuttajat lkm++; wait (odota_vuoroa); #mene odottamaan vuoroa; herätys FIFO-järjestyksessä # kun pääsee jatkamaan, niin herättäjä on jo kirjannut noston } else saldo = saldo – summa; # jos kukaan ei odota ja saldoa riittää, niin tee oma nostosi } procedure pano (int summa) { saldo = saldo + summa; # voidaanko nostoja nyt suorittaa? # tässä ratkaisussa herättäjä käsittelee kaikki ne nostot, joihin #saldo riittää, siksi while while (!empty(odota_vuoroa)&&saldo > nostojono[eka] ) { # jonossa on odottajia ja saldo riittää ensimmäiselle odottajalle signal(odota_vuoroa); # vapauta seuraava odottaja saldo = saldo –nostojono[eka]; # kirjaa odottajan nosto ja päivitä saldo eka = (eka + 1) mod n; lkm --; }Voidaan myös toteuttaa siten, että pano-proseduurissa käsitellään korkeintaan yksi odottava nosto ja nosto-proseduurissa odottamasta herätetty tutkii ja tarvittaessa käsittelee aina seuraavan mahdollisen noston. Tällöin while:n tilalla on if ja nosto-proseduurissa on samanlainen toiminto.
=======================================================================
a) Tässä piti selittää, miten asiakkaat ja parturit toimivat ja kommunikoivat. Useimmat olivat sen osanneet.
b) Tässä on hyvin yksinkertainen ratkaisu, jossa parturin ja asiakkan viestintä on minimaalista
type kind = enum(haircut, shaving, ... ); chan service_queue(int id, kind op),#one queue for all customers goodbye[M](); #one"reply"-channel for each customer process client C[i = 0 to M-1] { ... op = "haircut"; #specify the operation send service_queue(i,op); #inform the barber and ... receive goodbye[i]; #... wait for a reply #(operation has been executed) ... } process barber[j = 0 to N-1] { while(true) { receive service_queue(client,operation); #wait for the next customer execute(client, operation); #service execution send goodbye[client](); #confirm } }
Tässä vähän pidempi ratkaisu, jossa asikas ja parturi kommunikoivat enemmän keskenään:
chan uusiasiakas (int id, string viesti); # kanava, johon asiakkaat ilmoittautuvat chan asiakkaat [M](int id, string viesti); # kullakin asikkaalla oma kanava chan parturit[N](string viesti); # kullakin parturilla oma kanava process asiakas [i= 1 to M] { int i, j; string sanoma; while (true) { anna tukan kasvaa; # mene parturiin send uusiasiakas(i,“tukanleikkuu”); # ilmoittaudu receive asiakkaat[i] (j, sanoma); # odottele vapaan parturin vastausta omassa kanavassa # j on ko. parturin tunnus, itse viestillä ei ole tässä merkitytsä istu parturin j tuoliin; send parturit [j] (“pelkkälyhennys”); # ilmoita parturille, että voi aloittaa receive asiakkaat[i](j,sanoma); # odottele kunnes valmista ja voit poistua poistu parturista; send parturit[j](“maksoinjo!”); # ilmoita parturille, että tämä voi # ottaa seuraavan asiakkaan } } process parturi[j=1 to N] { int i, j; string sanoma; while (true) { receive uusiasiakas(i,sanoma); # odottele uusia asiakkaita torkkuen; # i = asiakkaan tunnus send asiakas [i](j, “istutuoliin”); # ilmoitetaan oman kanavan tunnus j receive parturit[j](sanoma); # odotellaan, kunnes asiakas on tuolissa suoritetaan sanoman kertoma tehtävä; send asiakas[i](j, “20euroa”); # ilmoitetaan asiakkaalle valmistumisesta receive parturit[j](sanoma); #odotetaan, että asiakas maksaa ja poistuu } }Huomaa:
asiakkaan koodi .............. send asiakkaat[i ](i, “pelkkä lyhennys”); # ilmoita parturille, että voi aloittaa receive asiakkaat[i](j,sanoma); # odottele kunnes valmista ja voit poistuanopea asiakas lukisi kanavasta oman viestinsä ja tulkitsisi sen parturin valmis-ilmoitukseksi.
======================================================================
prosessille prosessin prosessi varattu maksimitarve A B C A B C P1 0 0 1 2 2 2 P2 4 1 0 5 1 1 P3 2 2 2 2 3 2Prosessi P2 pyytää saada lisää yhden C-resurssin. Voidaanko se myöntää? Perustele vastauksesi. (4 p)
a) Lukkiutumisen välttämättömät ehdot
Arvostelusta: 1 p itse ehdosta ja 1 p sen toteutumisen estämisestä.
Arvostelusta:
c) Prosessin P2 pyyntöön voidaan suostua. Vaikka suostumisen jälkeen olisi vapaana vain 1 kappale resurssia B, niin se riittäisi prosessille P3. P3 voidaan suorittaa loppuun, sillä se maksimissaan tarvitsee lisää vain yhden B-resurssin. P3:lta taas vapautuis resursseja niin, että ne riittävät P1:n ja P2:n maksimitarpeisiin. Suostuminen ei aiheuta lukkiutumista, joten P2 saa tarvitsemansa yhden C- resurssin.
Arvostelusta: