581332-8 Rinnakkaisohjelmointi
Erilliskuulustelu
3.2.2006
Kirjoita jokaiseen vastauspaperiisi nimikirjoituksesi ja nimen selvennys sekä kokeen nimi että päivämäärä.
Prosessi p1 pyytää saada lisää yhden A-resurssin ja yhden B-resurssin. Voidaanko se myöntää? Perustele vastauksesi esittämällä pankkiirin algoritmin suoritusvaiheet. Mitä tapahtuu, jos prosessille ei voida myöntää sen tarvitsemia resursseja? Mihin pankkiirin algoritmia oikein tarvitaan? ( 8 p)
"Signal and Wait": herätetty prosessi jää aktiiviseksi monitoriin ja sen herättänyt poistuu monitorista. Signal_all(cv) aiheuttaa ongelmia, mikä herätetyistä prosesseista saa monitorin?
"Signal and Continue": herätyssignaalin antanut prosessi jatkaa aktiivisena monitorissa ja herätetty siirtyy monitorin 'jonoon' odottamaan monitoriin pääsyä (monitorin lukkoa).( => Koska herätetty ei välttämättä pääse heti seuraavaksi monitoriin, herätetyn on tarkastettava mahdollinen ehto uudestaan ja se voi joutua takaisin odotustilaan, jos ehto ei olekaan enää voimassa. Tai sitten on käytetävä
"contition passing"-tekniikkaa.)
"Signal and Continue" on yleisempi tapa.
(Anrewsin kirja s 208-209)
Kutsuva prosessi jää odottamaan, kunnes kutsuttu proseduuri on suoritettu ja sen tulokset palautettu.
Kutsun tuloksena koneessa, jossa kutsuttu proseduuri sijaitsee käynnistetään prosessi, joka suorittaa ko. proseduurin ja palauttaa sen tulokset ja sen jälkeen lopettaa toimintansa.
Sekä kutsuva että käynnistetty prosessi toimivat kuin ne kutsuisivat ja suorittaisivat paikallista proseduuria. Tässä tarvitaan molemmissa järjestelmissä käyttöjärjestelmä- ja tietoliikennepalveluja sekä töpöt ('stubit').
prosessi varattu pyytänyt maxtarve
A B C A B C A B C
p1 1 1 1 1 1 0 4 3 2
p2 2 0 1 0 2 0 2 2 1
p3 1 1 0 0 0 1 1 2 1
prosessi varattu pyytänyt maxtarve puuttuu
A B C A B C A B C A B C
p1 1 1 1 1 1 0 4 3 2 3 2 1
p2 2 0 1 0 2 0 2 2 1 0 2 0
p3 1 1 0 0 0 1 1 2 1 0 1 1
varattu 4 2 2
kaikkiaan 4 4 3
vapaana 0 2 1
Näillä arvoilla prosessille p1 ei voida antaa sen pyytämiä resursseja, koska resurssia A ei ole yhtään vapaana.
Prosessi joutuu odottamaan kunnes jompikumpi prosesseista p2 tai p3 vapauttaa varaamiaan A-resursseja.
Jos A-resurssia olisi ollut 5 kappaletta (näin tehtävässä olikin tarkoitus olla!), niin vapaana olisi resurssia A 1, resurssia B 2 ja resurssia C 3 kappaletta. Voidaanko p1:lle nyt luovuttaa sen pyytämät resurssit?
Katsotaan tilannetta, jos p1:lle annettaisiin sen haluamat resurssit:
prosessi varattu pyytänyt maxtarve puuttuu
A B C A B C A B C A B C
p1 2 2 1 0 0 0 4 3 2 3 2 1
p2 2 0 1 0 2 0 2 2 1 0 2 0
p3 1 1 0 0 0 1 1 2 1 0 1 1
varattu 5 3 2
kaikkiaan 5 4 3
vapaana 0 1 1
Lukkiutuuko tilanne?
Pankkiirin algoritmia käytetään välttämään lukkiutuminen.
Aina, kun prosessi pyytää resursseja, niin varmistetaan ensin, ettei pyyntöön suostuminen voi pahimmassakaan tilanteessa (= kun prosessien loppuunsuorittaminen edellyttää sitä, että prosessien on saatava käyttöönsä ilmoittamansa maksimimäärä resursseja) johtaa prosessien lukkiutumiseen. Prosessi saa pyytämänsä resurssit vain, jos lukkiutumiusta ei pääse syntymään.
Jos prosessille ei voida myöntää sen pyytämiä resursseja, prosessi joutuu odottamaan, kunnes resurssit voidaan myöntää eli kunnes tilanne ei enää johda lukkiutumiseen.
Arvostelusta
Eri kohdista on saanut pisteitä sen mukaan, miten paljon on oikeaa asiaa kirjoittanut.
Kohdassa c) 8 pistettä jakautui siten, että sai maksimissaan 4 pistettä itse pankkiirin algoritmin osaamisesta ja 4 vastauksista esitettyihin kysymyksiin.
Paviaanit ylittävät rotkon heilauttamalla itsensä köyden avulla rotkon toiselle puolen. Yhdessä köydessä voi roikkua korkeintaan 5 paviaania. Tätä raskaampi kuorma katkaisee köyden ja syöksee paviaanit rotkoon. Ylityskohta on niin kapea, että rotkon voi samanaikaisesti ylittää vain yhteen suuntaa, muuten ylittäjät törmäävät ja taas putoavat rotkoon.
Käytetään semaforeja koordinoimaan paviaanien rotkon ylitystä. Kirjoita koodi eri suuntiin rotkon ylitse haluaville paviaaneille (paviaaniprosesseille). Ratkaisun ei tarvitse olla reilu, ts. paviaanien virta yhteen suuntaan voi pakottaa toiseen suuntaan haluavat odottamaan pitkiäkin aikoja, mutta samalla rotkon reunalla odottavat päästetään jatkamaan saapumisjärjestyksessä.
rotko
| |
vasen | | oikea
puoli | | puoli
| |
# Ratkaisu, jossa paviaanit siirtyvät rotkon yli aina viiden paviaanin ryppäinä. Viides ylittämään haluava heilauttaa köyden toiselle puolelle.
# Aikaisemmin tulleet jäävät roikkumaan köyteen ja odottavat, kunnes heidät on heilautettu rotkon
# toiselle puolelle ja he voivat irrottaa köydestä.
# Koska molemmilla puolilla on oma köysi, täytyy varmistaa, että vain yhdellä köydellä kerrallaan ylitetään rotkoa.
ylita_rotko(int puoli) { # puoli kertoo kummalla puolella rotkoa paviaani on
sem vasen = 1, # köysissä roikkujien lukumäärän päivityksen suoja
oikea = 1; # oma köysi kummallakin puolella
ilmatila = 1; # ilmatilan vartija: vain yksi porukka kerrallaan voi ylittää rotkon
vexit = 0, # näissä odotetaan, kunnes saa irrottaa köydestä
oexit = 0; #
int vnarussa =0, # köysissä roikkujien lukumäärä
onarussa =0;
if (puoli = = 0){ # ollaan rotkon vasemmalle puolella ja halutaan päästä toiselle puolelle
P(vasen);
vnarussa++;
if(vnarussa == 5) # narussa täysi kuorma
{
P(ilmatila); # varaa ilmatila
heilauta köysi toiselle puolelle();
V(ilmatila); # vapauta ilmatila
V(vexit); # vapauta yksi köydessä roikkuja (ensimmäinen, jos FIFO-semafori)
}
else V(vasen); # jos kuorma ei ole täynnä, avataan mutex vasen uusille tulijoille
P(vexit); # tässä odotetaan kunnes ilmalento on päättynyt ja köydestä voi irroitta
# vain yksi kerrallaan pääsee irroittautumaan köydestä ja mutex vasen on suljettu
vnarussa--; # vain yksi on päivittämässä muuttujaa
if (vnarussa == 0) { # viimeinen
palauta köysi toiselle puolelle;
V(vasen); # päästää uudet ylittäjät köyteen eli avaa mutexin vasen
}
else V(vexit); # muut päästävät aina seuraavan irrottautumaan köydestä
}
else { # ollaan oikealla puolella
P(oikea); # yksi kerrallaan kiinni köyteen
onarussa++;
if(onarussa == 5) {
P(ilmatila);
heilauta köysi toiselle puolelle ();
V(ilmatila);
V(oexit);
}
else V(oikea); # päästä seuraava tarttumaan köyteen
P(oexit); # odota, kunnes voi irrottaa
onarussa--;
if (onarussa == 0) {
palauta köysi toiselle puolelle;
V(oikea); # päästä uudet ylittämään rotko oikealta
}
else V(exit); # päästä seuraava irrottautumaan köydestä
}
process paviaani[i=1 to N] {
int puoli; # kummalla puolella rotkoa paviaani on: 0 = vasen , 1 = oikea
puoli = ....; # aluksi jollakin puolella
while (true) {
puuhaile kaikenlaista;
ylita_rotko(puoli);
if (puoli == 1) puoli=0 # vaihda puolta
else puoli=1;
}
}
========================================================================================
Entä, jos ei haluta odottaa, että aina on viisi kasassa ennenkuin siirrytään toiselle puolelle?
Voidaan esimerkiksi pitää kirjaa myös odottajien määrästä. Jos ei ole yhtään odottajaa, niin hypätään rotkon yli vaikka yksin.
Tarvitaan pari semaforia ja pari laskuria lisää:
sem vwait=1, #mutexit odottajalaskureiden suojaksi
owait=1;
int vodottajia, # laskurit odottajia varten
oodottajia;
Ja koodia pitää hieman muuttaa:
if (puoli = = 0){ # ollaan rotkon vasemmalle puolella ja halutaan päästä toiselle puolelle
P(vwait);
vodottajia++;
V(vwait);
P(vasen); # odotetaan, että päästään kiinni naruun
vnarussa++;
P(vwait);
vodottajia--;
if(vodottajia ==0 OR vnarussa == 5) # narussa täysi kuorma
{
V(vwait);
P(ilmatila); # varaa ilmatila
heilauta köysi toiselle puolelle();
V(ilmatila); # vapauta ilmatila
V(vexit); # vapauta yksi köydessä roikkuja (ensimmäinen, jos FIFO-semafori)
}
else { # kun kuorma ei ole täynnä,
V(vasen); # avataan mutex vasen odottaville
V(vwait); # myös uudet tulijat pääsevät ilmoittautumaan odottajiksi
}
P(vexit); # tässä odotetaan kunnes ilmalento on päättynyt ja köydestä voi irroitta
# vain yksi kerrallaan pääsee irroittautumaan köydestä ja mutex vasen on suljettu
vnarussa--; # vain yksi on päivittämässä muuttujaa
if (vnarussa == 0) { # viimeinen
palauta köysi toiselle puolelle;
V(vasen); # päästää uudet ylittäjät köyteen eli avaa mutexin vasen
}
else V(vexit); # muut päästävät aina seuraavan irrottautumaan köydestä
}
Ja samalla tavoin toisella puolella.
Tehtävän 2 arvostelusta
Tehtävää ei ole arvosteltu, jos se on toteutettu muilla kuin semaforeilla => 0 p.
Yhteisön keittiössä on iso pata, josta yhteisön asukkaat käyvät noutamassa itselleen ruoka-annoksia. Jos pata on tyhjä, niin asukas herättää kokin ja odottaa, kunnes kokki on saanut padan täytettyä ruualla (pataan mahtuu M annosta).
Asukkaiden ja kokin käyttäytymistä kuvaavat prosessit:
process asukas[1:n] {
while (true) {ota annos padasta; syö; kuluta kalorit;}
}
process kokki{
while (true) {laita M annosta pataan; nuku}
}
Toteuta tarvittava synkronointi ja poissulkeminen monitoria käyttäen sekä esitä asukasprosessien (N kpl) ja kokkiprosessin koodit. Selvitä vielä sanallisesti, missä tilanteissa tarvitaan poissulkemista ja synkronointia ja kuinka ne toteutuvat ratkaisussasi.
monitor pata {
cond ruokaa;
cond herätys;
int annoksia =0; # tässä aluksi pata on tyhjä
procedure ota_annos ( ) {
while (annoksia = = 0) wait(ruokaa);
annoksia --;
if (annoksia = = 0) signal(herätys); # padan tyhjentänyt herättää kokin
}
procedure täytä_pata ( ) {
annoksia = M;
signal_all (ruokaa); # tieto mahdollisesti jo odottaville
wait (herätys); # jää odottamaan (' nukkumaan') monitoriin
}
process asukas[i=1 to N] {
while (true) {
call pata.ota_annos( );
syö;
kuluta kalorit;
}
}
process kokki { # tämä kokki on koko ajan valmiina kokkaamaan
while (true) {
kokkaa padallinen jotain ruokaa; # aluksi valmistetaan ruoka ja täytetään pata
call pata.täytä_pata();
}
}
Tehtävän 3 arvostelusta
(monitorista 8 pistettä, prosesseista 4 pistettä ja sanallisesta selityksestä 3 pistettä)
Esitä "nukkuvan parturin ongelman" ratkaisu käyttäen sanomanvälitystä. Partureita oletetaan olevan useita.
typeT kind = enum (parranajo, hiustenleikkaus, viiksien tasoitus, .. );
chan palvelu (int aid, kind tyyppi); # palvelunpyytämiseen: asiakkaat lähettävät, parturit kuuntelevat ja vastaanottavat
chan parturi[M] (int aid, string fraasi); # kunkin parturin oma kanava, jota kuuntelee
chan asiakas[N](int pid, string fraasi); # kunkin asiakkaan oma kanava, jota kuuntelee
# fraasit ovat sinänsä täysin turhia eikä niitä ei mitenkään käytetä ohjelmassa => voisi jättää kokonaan pois
process asiakas[i=1 to N] ( ) {
kind pyynto;
int pid; # parturin tunniste
string fraasi; # merkkijono
while (true) {
tee mitä teet;
pyynto = mitätehdään();
send palvelu(i, pyyntö); # pyydä palvelua: ilmoita oma tunnus ja haluamasi palvelu
receive asiakas[i](pid, fraasi); #odota omassa kanasvassa vastausta joltakin parturilta
istu parturin pid tuoliin tuoli[pid]; # istu vastanneen parturin tuoliin
send parturi[pid] (i, "voi aloittaa"); # ja ilmoita itsestäsi tälle parturille
receive asiakas[i](pid, "valmista on"); # odota kunnes parturi ilmoittaa saaneensa työnsä valmiiksi
nouse tuolista, maksa ja poistu;
send parturi[pid](i, "kiitos ja näkemiin"); # ilmoita parturille, että olet poistunut
}
process parturi[j=1 to M] ( ) {
kind pyynto;
int aid; # asiakkaan tunniste
string fraasi; # merkkijono
tule työpaikalle
while (työpäivää kestää) {
receive palvelu(aid, fraasi); # odota palvelupyyntöä
send asiakas[aid](j, "Olkaa hyvä"); # ilmoittaudu odottavalle asiakkaalle
receive parturi[j] (aid, "Voi aloittaa"); # odota, kunnes asiakas on istuutunut tuoliisi
suorita asiakkaalle toimenpide[pyynto];
send asiakas[aid](j, "Valmista on"); # ilmoita asiakkaalle, että toimenpide on suoritettu
receive parturi[j](aid, "kiitos ja näkemiin"); # odota, etta asiakas on poistunut
}
lähde kotiin;
}
Tehtävän 4 arvostelusta:
a)-kohdasta on saanut pisteitä 0-5
b)-kohdasta 0-10; pisteitä o