to allow a data transfer to take place. A longer buffer is beneficial
in cases where the execution rates of the producer and consumer vary:
larger variability => longer buffer. If either one is continuosly
faster then using a longer buffer becomes counterproductive (why?).
Yhteisön
keittiössä on iso pata, josta nälkäiset käyvät
noutamassa itselleen ruoka-annoksen. Jos pata on tyhjä, niin
ruokailija herättää kokin ja odottaa, kunnes kokki on
saanut padan täytettyä (pataan mahtuu M annosta).
Asiakkaiden ja kokin käyttäytymistä kuvaavat
prosessit:
process customer[i=1 to n]{ process cook {
while(true){ while(true) {
get serving from the pot; sleep;
eat; put M servingd in the pot;
} }
} }
Kirjoita asiakkaiden ja kokin toimenpiteiden koodien keskeiset osat käyttäen semaforeja ja P/V-operaatioita.
Eräs ratkaisu:
int M = <padan koko>; #amount of servings in a full pot
int servings = 0; #amount of available servings
sem empty = 1; #waiting place for the cook
sem mutex = 0; #the pot is closed until the cook opens it
procedure get_serving() {
P(mutex); #if mutex is open then there is food
servings = servings - 1;
if servings == 0
V(empty); #wakeup the cook, mutex remains closed
#waiting for food will be in mutex
else V(mutex);
}
procedure eat() {
#one serving is available for the customer, not further specified
}
procedure sleep() {
P(empty); #the cook sleeps
} #the cook wakes up, mutex is closed
procedure put_servings() {
#prepares food, not further specified
servings = M;
V(mutex); #the next clients are free to enter
}
Monitoroitu silta [15p]
Kahden kylän A ja
B välissä olevan joen yli kulkee niin kapea silta, että
autot voivat ajaa sitä pitkin vain yhteen suuntaan kerrallaan.
Kun sillalla kulkee autoja A:sta B:hen, niin B:stä A:han
haluavien täytyy odottaa. Silta ei myöskään ole
kovin vankka, joten sillalla saa olla korkeintaan 10 autoa yhdellä
kertaa. Kirjoita koodi sillan käyttöä valvovalle
monitorille Silta. Laadi myös koodit autoprosesseille.
Käytä 'Signal and Continue' -semantiikkaa. Pyri tekemään
ratkaisustasi mahdollisimman reilu. Samalta suunnalta tulevien
autojen tulee päästä sillalle saapumisjärjestyksessä
eikä kumpikaan suunta saisi vallata siltaa vain yhden suunnan
liikenteelle.
Oikein toimivasta ratkaisusta saa maksimissaan 10
p, reiluuden huomioonottaminen tuo lisää 1- 5 p.
Hyvin yksinkertainen ratkaisu , joka vain estää
eri suunnilta tulevia autoja törmäämästä ja
liian montaa autoa menemästä sillalle. Ratkaisussa ei ole
lainkaan huomioitu reiluutta eikä myöskään
toiminnan tehokkuutta.
Jos auto ei heti pääse
sillalle, niin se menee odottamaan. Kaikki odottavat samassa
ehtomuuttujassa ja jokainen sillalta poistuja päästää
kaikki odottajat yrittämään uudestaan ja uudestaan,
kunnes sillalle meno onnistaa (joko silta on tyhjä tai silta on
kyllä käytössä, mutta ajosuunta on sama kuin
itsellä eikä sillalla ole vielä 10 autoa).
Onnistuminen on hyvin sattumanvaraista ja prosessit saattavat joutua
kiertämään kehää (mene odottamaan ->
herää -> mene monitorin jonoon -> testaa pääsetkö
nyt -> mene takaisin odottamaan).
Tämäntyyppinen oikein toimiva ratkaisu => 10 p
monitor Silta {
int ajosuunta = 0; # ajosuunta sillalla A=>B = 1 ja B=>A = 2
int slkm = 0; # autojen lukumäärä sillalla; jos 0 niin silta on vapaa
cond odota_vuoroa; # kaikki autot odottavat samassa ehtomuuttujassa
procedure enter_silta (oma_suunta) {
while (slkm>0 && ajosuunta != oma_suunta || slkm = 10)
wait(odota_vuoroa);
if (slkm =0) ajosuunta = oma_suunta;
slkm ++;
}
procedure exit_silta(oma_suunta) {
slkm --; # tässä vähän suositaan omaa suuntaa, kun ajosuuntaa ei muuteta
signal_all(odota_vuoroa);
}
======================================================== Ratkaisu, jossa aina samaan suuntaan pyrkivät autot pääsevät sillalle saapumisjärjestyksessä (FIFO). Mutta samaan suuntaan etenevät autot pitävät siltaa hallussaan niin kauan kuin autoja riittää eli ei tule niin pitkää väliä, että silta ehtisi tyhjentyä ja suunta voitaisiin muuttaa.
Idea:
Käytetään condition passing -tekniikkaa
samaan suuntaan menevien autojen etuilun estämiseen
monitorissa odottavat myös ne autot, jotka eivät voineet ajaa suoraan sillalle, koska sillalla oli jo täysi kuorma autoja eli se sallittu 10 kappaletta. Näillä autoilla on etuoikeus eli tätä jonoa puretaan ensin
monitor Silta{
cond atob, btoa; # odotetaan oman suunnan vuoroa
int slkm =0;
int ajosuunta = 0; # 0, kun atob; 1, kun btoa
procedure enter_atob() {
if (sklm > 0 && ajosuunta !=0|| !empty(atob) || slkm =10)
# kun silta varattu toiseen suuntaan menijöille tai
# omaan suuntaan menijöitä on jo odottamassa tai sillalla on jo 10 autoa
# mennään odottamaan, mutta vain kerran (if)
{
wait(atob); #odotetaan vuoroa ajaa sillalle
#kun tästä päästään, niin ajosuunta == oma_suunta ja slkm:ää on jo valmiiksi kasvatettu
}
else { # auto pääsee suoraan sillalle ilman odottamista
if (slkm ==0) ajosuunta = oma_suunta; # ensimmäinen muuttaa suunnan varmuuden vuoksi aina
slkm=1;
}
# pura mahdollista odottajien jonoa
if (slkm <10 && !empty (atob)) {
slkm++;
# varataan paikka jo valmiiksi HUOM! FIFO-järjestys ei aivan toimi **
signal(atob);
}
aja sillalle;
}
Vastaavasti procedure enter_btoa()
**)
Jos vapautetttu auto on viimeinen jonottaja, niin joku muu
auto voi saada monitorin ennen sitä ja päästä
ajamaan ensin sillalle, sillä nyt empty(atob) = true. Eli
FIFO-järjestys ei täysin pidä paikkaansa tässä
ratkaisussa.
Mutta vapautettu pääsee varmasti sillalle, kun se saa aikanaan monitorin haltuunsa. Koska vapautetulle autolle on jo valmiiksi varattu paikka, niin ohittajia voi olla vain rajallinen määrä. Vaikka kaikki sillalla olleet 10 autoa ehtisivät poistua, niin laskuri slkm menee nollille vasta, kun tämä auto on ylittänyt sillan.
Sillan käytön tehokkuuden kannalta tämä ratkaisu on hyvä, sillä siinä hyödynnetään sitä luppoaikaa, joka kuluu ennenkuin se vapautettu auto saa monitorin haltuunsa ja pääsee itse sillalle.
procedure exit_atob() {
if (!empty (atob)) {# oman suunnan odottajia on => suositaan oman suunnan odottajia
signal(atob); # HUOM! ei vähennetä slkm-laskuria
}
else {
if (slkm ==1 && !empty (btoa)) {# viimeinen tältä suunnalta ja toisen suunnan odottajia on
ajosuunta = 1;
signal(btoa);
}
else slkm --;
}
}
Vastaavasti procedure exit_btoa()
====================================================
Entä kun halutaan olla reiluja molemmille suunnille? Tarvitaan
vielä joku rajoitus: toisella puolella on paljon odottajia, omia
on mennyt tietty määrä ja toisella puolella on
odottajia.
====================================================
Millaisia virheitä:
Reiluus: vuoro vaihtuu reilusti ja saman suunnan autot pysyvät järjestyksessä
ei vaihdu, vaikka silta on tyhjä ja odottajia toisella puolella olisi, kun vasta 9 autoa tähän suuntaan mennyt. Odotellaan nyt sitä kymmenettä, joka ehkä joskus saapuu!
Pisteitä reiluuden mukaanottamisesta:
5 pistettä, jos reiluus toimii sekä eri suuntien välillä että saman suunnan autojen kesken tai jos ei ihan toimi, niin puutetta sopivasti perusteltu esimerkiksi tehokkuudella.
Parturit ja
asiakkaat käyttäen sanomanvälitystä (15 p)
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; ne 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;
}
========================================================
Tässä vähän turhamkin yksinkertainen ratkaisu, jossa kommunikointi on todella minimissään:
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
}
}
Tehtävän 4
arvostelusta: b)-kohdasta 0-10 pistettä
asiakkaat lukevat kaikki samoja kanavia => viestit sekaantuvat: asiakkaat istuvat toistensa syliin, joku nopea ehtii jo poistua ennenkuin häntä on edes alettu parturoida samoin partureille tarkoitetut viestit sekaantuvat: joku o parturoi, vaikka tuolissa ei ole asiakasta, toinen hakee uuden asiakkaan vaikka edellinen ei ole vielä poistunut jne. -4 p