semaforimuuttujan arvo oli nolla, niin prosessi pistetään BLOCKED-jonoon odottamaan resurssin vapautumista. Kun prosessi vapauttaa semaforin, niin semaforimuuttujaa lisätään yhdellä ja tätä tapahtumaa odottavat prosessit herätetään / herätetään ensimmäinen jonossa. Lukkomuuttuuja on myös KJ:n ylläpitämä palvelu, mutta siinä tiettyä muuttujaa luetaan busy-silmukassa atomisella test-and-set -tyyppisellä operaatiolla kunnes muuttuja on halutussa arvossa (esim. 1).
* Semafori on suositeltavampi, koska se kuormittaa vähemmän järjestelmän laskentaresursseja sekä muistiväylää (erityisesti moniprosessorijärjestelmät!)
* Monitorit toteuttavat semaforeja korkeamman abstraktiotason poissulkemis- ja synkronointipalvelun. Monitorit ovat jonkin abstraktin objektin ilmentymä, johon liittyy sekä dataa että operaatioita. Monitori takaa poissulkemisominaisuuden implisiittisesti, koska vain yksi monitori-instanssin operaatioista on suorituksessa kerrallaan.
Pistejakauma:
0 xx
1
2
3 x
4 x
5 xxxx
6 xxxxx
7 xxxxxxxxxxxxxxxxx
8 xxxxxxxxxxxxxx
9 xxxxxxxxxxxxxxxxxxxx
Keskiarvo 7.3 pistettä eli noin 81 % maksimipisteitä
============================================================
Tehtävä 2 (Liisa Marttinen)
=============================================================
Ratkaistaan tehtävä vähitellen tarkentamalla:
Kuka odottaa ja mitä eli mitä cond-jonoja tarvitaan:
kuormuri odottaa
kuoppa vapaa => cond saa_ajaa
boolean varattu (koska aina ei tarvitse jonottaa, vaaan pääsee suoraan jatkamaan)
kuorma valmistunut => cond saa_poistua (tässä aina odotus)
kaivuri odottaa
kuopalla lastattava auto => cond saa_kauhoa
=> boolean autovalmis (tässä auto voi olla ensin tai sitten kaivuri odottaa)
Miten kuormuri toimii:
jos kuoppa varattu jää odottamaan, muuten aja suoraan kuoppalle
ilmoita tulostasi kaivurille
odota, että kuorma valmis
aja pois kuopalta ja päästä seuraava kuormuri (condition passing eli tulojärjestyksessä)
Miten kaivuri toimii:
odottele, kunnes kuopalle tulee lastattava auto
kauho kuormuri täyteen
anna kuormurille poistumislupa
Kuormurin tarkemmin koodattuna:
-------------------------------
if (varattu) wait (saa_ajaa) # jos kuoppa varattu jää odottamaan,
else varattu = true; # muuten varaa kuoppa
aja kuopalle; # aja suoraan kuoppalle
autovalmis = true; # ilmoita tulostasi kaivurille: 'jätä merkki'
signal (saa_kauhoa); # herätä jo odotteleva kaivuri
wait (saa_poistua); # odota, että kuorma valmis
aja pois kuopasta; # aja pois kuopalta
if (!empty (saa_ajaa)) signal (saa_ajaa) # ja päästä seraava: ensin odottava kuormuri
else varattu = false; # muuten uusi tulija
kaivurin koodi tarkennettuna:
-----------------------------
if (!autovalmis) wait (saa_kauhoa); # odottele, kunnes kuopalle tulee lastattava auto
autovalmis = false; # ettei täytä useaan kertaan!
kauho kuormuri täyteen; # kauho kuormuri täyteen
signal (saa_poistua); # anna kuormurille poistumislupa
Monitori + prosessit
===================
monitor Kuoppa {}
procedure Teekuorma( ) {}
}
process Kuormuri( )[i=1 to n)] {}
}
process Kaivuri( ) {}
Ratkaisussa kuopalle ajo ja sieltä poistuminen sekä kuorman täyttö ovat monitorin sisällä, vaikka monitorin sisällä tulee olla aivan välttämättömän ajan. Tässä tehtävässä siitä ei tosin ole paljoakaan haittaa, koska varsinaine homma etenee vain sen yhden kaivurin tahdissa ja kaivurin on ensin saatava auto kuopalle, täytetävä se ja auton on poistuttava ennenkuin seuraava auto voi tulla.
Kuitenkin monitorin varattuna pitäminen voi aiheuttaa jonoa monitoriin ja vapautuneen kaivurin on odotettava monitoriin jonottavien kuormurien uuteen jonoon menoa ennenkuin se puolestaan pääsee monitoriin ja voi ruveta täyttämään seuraavaa kuormuria.
Ratkaisu, jossa mnitorissa ei turhaan viivytellä
================================================
Ratkaisu saadaan yksinkertaisesti jakamalla kuormurin ja kaivurin proseduurit pienempiin osiin.
monitor Kuoppa {}
procedure Onkuopalla( ) {}
procedure Poiskuopalta ( ) {}
procedure Odottaakuormuria( ) {}
procedure Kuormurihoidettu ( ) {}
}
process Kuormuri ( ) [i=1 to n] {}
}
process Kaivuri ( ) {}
}
Arvostelusta:
============
Kaikkiaan 12 pistettää: monitorista 9 p ja prosesseista 3 p
toimintavirheitä:
autoja pääsee kuopalle kuinka paljon tahansa -3 p
kuopalle voi päästä kaksi autoa kerrallaan -2 p (if ja ei condition passing)
lukkiutumistilanne eli kaikki odottavat -2 p
kaivuri täyttää jo täyden kuormurin uudestaan -1 p
Kuormuri-prosessissa odotellaan silmukassa kunnes kuorma on täynnä -2 p
cond ? jonomuuttajat puuttuvat kokonaan -2p
call M.proseduuri puuttuu -1 p, call puuttuu -1/2 p tai monitorin nimi puuttuu -1/2 p
vain yksi kuormuri prosessi -1
signal ja wait tunnettu +2 p
cond muuttujia määritelty +1 p
näiden järkevä käyttö +1 p
Ei edellytetty FCFS-järjestystä
Pistejakauma:
0 xxxxxxxxx
1 xx
2 xxxxx
3 x
4 xxxx
5 xxx
6 xx
7 xxxx
8 xxxxxxxx
9 xxxx
10 xxxxxxxxxxx
11 xxxxxxxxx
12 xx
Tehtävän keskiarvo 6.5 pistettä eli noin 54 % maksimipisteitä.
===========================================
Tehtävä 3
============================================
/* Example answer / Sini Ruohomaa
*
* Points where we must wait:
* Customers:
* - wait outside until the guide starts the tour
* (- wait for the tour to finish)
* The guide:
* - wait for at least 10 people to show up for the group
* (- wait for the customers to notice that a tour has started)
* (- after the tour, wait for the customers to leave)
*
* The parts in parentheses are not necessary since they were not mentioned
* in the task formulation, so we leave them out.
*
* This is an example of barrier synchronization. You might compare it
* with the bees, the trapped bear and the honeypot, or the carousel.
*/
int waiting_customers = 0;
/* Synchronization:
ready_group_prepared -- there are enough people in the group.
tour_has_begun -- the guide has noted this and is ready to go.
The first semaphor allows the guide to continue, the second
allows the customers to continue.
*/
sem ready_group_prepared = 0;
sem tour_has_begun = 0;
/* Mutual exclusion:
* mutex -- protect the waiting_customers variable in two ways:
* - only 1 process at a time is allowed to change it, and
* - when the tour is just about to begin ("the guide is counting the
* customers"), new customers should not enter the yard. See the
* guide code for details.
*/
sem mutex = 1;
process customer[i = 1 to N] {}
}
process guide {}
}
/*************************************************************************
* Common errors and their effect on scoring (total 15 p):
*
* - unnecessary code which does not work as expected, but "otherwise"
* the program fulfills requirements - not considered an error -0p
* - group size alway