-
SYNTAKSIA JA SPESIFIOINTIA:
RINNAKKAINEN SUORITUS
Tarkastellaan seuraavaa ohjelmaa:
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.
Missä järjestyksessä lauseet suoritetaan ja 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;
-
PÄÄTTYYKÖ SUORITUS?
Tarkastellaan seuraavaa ohjelmaa:
co <await (x > 0) x = x - 1;> /*S1*/
// <await (x < 0) x = x + 2;> /*S2*/
// <await (x == 0) x = x + 5;> /*S3*/
oc
Millä x:n alkuarvoilla ohjelma päättyy eli sen kaikki haarat saadaan suoritettua? Mitkä ovat vastaavat x:n arvot tällöin? Perustele vastauksesi.
-
PROSESSIEN TAHDISTUSTA
Semaforeilla voidaan tahdistaa prosessit toimimaan halutussa järjestyksessä. Näytä kuinka seuraavat kolme tulostavaa prosessia voidaan semaforeilla pakottaa toimimaan sellaisessa järjestyksessä, että ne yhdessä tulostavat lauseen:Ihminen, joka ei tee virheitä, ei tavallisesti tee muutakaan.
P1 P2 P3
..... ...... .......
write("tee virheitä, "); write("joka ei "); write("Ihminen, ");
..... write("ei tavallisesti "); .....
write("tee muutakaan."); .......
.......
-
AVAIN TODELLISUUTEEN ON LUKOSSA
- 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.
- Voitaisiinko LOCK- ja UNLOCK-operaatiot toteuttaa vain estämällä keskeytykset
kriittisen alueen suorittamisen ajaksi?
- P()- ja V()-operaatiot ovat käyttöjärjetelmän ohjelmoijille tarjoamia palveluja.
Mitkä toiminnot P()- ja V()-operaatioiden toteutuksessa
vaativat poissulkemista 'alemman tason' menetelmin (ts. niiden koodit on
ohjelmoitava kriittisiksi alueiksi)? Selitä, miten P/V-rutiinien kriittiset
alueet saadaan toteutettua jakamamattomina (atomisesti) i) yhden prosessorin ja ii)
kahden prosessorin koneella?
-
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?
- SEMAFOREJA KÄYTÄNNÖN
ELÄMÄSSÄ??
- 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). Selitä toiminta myös sanallisesti.
- 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.
-
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
asiakas- ja autoprosessien 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: kuluta satunnainen aika museossa;
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: kuljeta asiakasta safariparkissa;
19: V(passenger_released);
20: }
21: }
Selitä, mihin semaforeja car_avail, car_taken, car_filled ja passenger_released käytetään, sekä miten niillä toteutetaan passenger- ja car-prosessien toiminnan tahdistus.
Toimiiko tämä ratkaisu oikein? Aina? Joskus? Selitä!
-
TUOTTAJA - PUSKURI - KULUTTAJA
- Osoita, että luennolla esitetty tuottaja-kuluttaja -ongelman
semaforipohjainen ratkaisu (Andrews kuva 4.5) toimii oikein eli
toteuttaa tähän yhteyteen liittyvät poissulkemisehdot ja
synkronointivaatimukset (ts. milloin prosessin on odotettava? milloin
odotus päättyy?).
Selvitä mitä tapahtuu, jos tuottajan operaatioiden P(empty) ja
P(mutexD) suorituksen välillä toimii i) usea muu tuottaja, ii) usea
kuluttaja.
- Ratkaisussa on käytetty kahta poissulkemissemaforia (mutexD,
mutexF). Mitä vaikutusta olisi sillä, että nämä korvattaisiin yhdellä
ainoalla semaforilla (mutex)?
- Miten algoritmin toimintaan vaikuttaisi, jos operaatiot P(empty)
ja P(mutexD) vaihtaisivat paikkaa? Entä jos operaatiot V(mutexD) ja
V(full) vaihtavat paikkaa? Entä jos mutexD ja mutexF on korvattu yhdellä
semaforilla mutex, ja operaatiot P(mutex) ja P(full) vaihtavat paikkaa?
-
SYNKRONOINTIA
Toteuta tuottaja-kuluttaja -algoritmi käyttäen binäärisemaforeja, ts.
käyttäen sellaisia semaforioperaatioita P() ja V(), joiden toteutuksessa
arvokenttä voi saada vain arvot 0 ja 1.
Vihje: Koska nyt ei semafori voi toimia laskurina, tarvitset oman
laskurin, joka sisältää puskurissa olevien yksiköiden lukumäärän. Aseta
binäärisemaforit vastaamaan järjestelmän kahta mielenkiintoista
tilanmuutosta: "tyhjä puskuri" -> "puskuri ei tyhjä" ja "täysi puskuri"
-> "puskuri ei täysi". Tarvitset siis kaksi binäärisemaforia: toisen estämään
tuottajaa kirjoittamasta
täyteen puskuriin, toisen estämään kuluttajaa lukemasta tyhjästä puskurista.
Lisäksi on varmistettava yhteisten muuttujien käyttö atomiseksi.
-
KARHU, PURNUKKA JA MEHILÄISET
Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille
hunajaa. Karhun elämä loukossa on vain syömistä ja odottelua.
Mehiläiset kuljettavat hunajaa purnukkaan annos kerrallaan. Kun
purnukka on täynnä (H annosta), viimeisen annoksen tuonut mehiläinen
herättää karhun, ja mehiläiset jäävät odottamaan purnukan tyhjenemistä.
Kun karhu on tyhjentänyt purnukan, se päästää mehiläiset töihin ja käy
itse nukkumaan:
process mehiläinen[i=1 to N] {
while (true) {
kerää_hunajaa();
talleta_purnukkaan(); # vie hunaja-annos purnukkaan
}
}
process karhu {
while (true) {
sleep(); # odota, että purnukka täysi
tyhjennä_purnukka(); # syö hunajat pois purnukasta
}
}
Kirjoita rutiinit talleta_purnukkaan(), tyhjennä_purnukka() ja
sleep() käyttäen semaforeja ja P/V-operaatioita. Osoita, että
ratkaisusi toimii oikein (ts. selitä sanallisesti)? Mitä tässä
yhteydessä tarkoittaa "oikein"?
-
JOSKUS ON TILAA NELJÄLLE
Opiskelija-asuntolassa on yksi kylpyhuone, jota käyttävät sekä tytöt
että pojat. Samaan aikaan kylpyhuoneessa voi kuitenkin olla vain joko
tyttöjä tai vain poikia. Ohessa on annettu koodi poikaprosesseille:
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: }
- Kirjoita vastaava koodi tyttöprosesseille, esittele ratkaisun
muuttujat ja selitä niiden käyttötarkoitukset (Mihin käytetään? Miksi
tarpeen?).
- Oleta, että kylppäri on varattu tytöille ja paikalle saapuu 3
poikaa. Selitä kuinka ratkaisu estää näitä poikaprosesseja pääsemästä
kohtaan käytä_kylppäriä().
- Muuta ratkaisua s.e. kylpyhuoneessa voi olla korkeintaan 4 tyttöä
tai poikaa kerrallaan. Selitä miksi ratkaisusi toimii oikein.
-
ERÄS sleep() JA wakeup()
Eräs käyttöjärjestelmä tarjoaa sovellusohjelmien käyttöön
synkronointioperaatiot sleep() and wakeup(). Rutiinin
sleep() kutsu pysäyttää kutsuvan prosessin. Rutiinin wakeup() kutsu
herättää kaikki prosessit, jotka wakeup()-kutsun suoritushetkellä
nukkuvat (ovat aiemmin kutsuneet sleep()-operaatiota ja kirjanneet
itsensä nukkuvaksi). Molemmat operaatiot on tarkoitettu ko.
järjestelmässä atomisiksi.
Rutiinien toteutuksen voi rakentaa kahdella eri periaatteella
a) kaikkien odottajien herätys tapahtuu wakeup()-rutiinissa
b) wakeup() herättää ensimmäisen sleep()-operaatiossa nukkuvan ja
kukin herätetty herättää seuraavan (baton passing).
Ohessa on annettu ratkaisuehdotus kohtaan a).
01: int sleepers = 0;
02: sem mutex = 1;
03: sem alarm = 0;
04:
05: procedure sleep()
06: {
07: P(mutex);
08: sleepers++;
09: V(mutex);
10: P(alarm);
11: }
12:
13: procedure wakeup()
14: {
15: P(mutex);
16: while (sleepers > 0) {
17: V(alarm);
18: sleepers--;
19: }
20: V(mutex);
21: }
Annettu ratkaisu ei kuitenkaan toimi oikein. Selitä miksei!
Kirjoita baton-passing tekniikkaan perustuva oikein toimiva ratkaisu.
-
TUNNELI, YKSISUUNTAINEN LIIKENNE JA "SEMAFORIVALOT"
Vuoren läpi on kaivettu etelä-pohjoissuunnassa tunneli, jossa autot
voivat ajaa vain yhteen suuntaan kerrallaan. Tunnelia käyttävät
autoprosessit kutsuvat proseduureja enter_tunnel(suunta) ja
exit_tunnel(suunta) pyrkiessään tunneliin ja poistuessaan
tunnelista. Suunta tarkoittaa auton etenemissuuntaa (etelään tai
pohjoiseen). Autoprosessien koodi on:
process car[1 to N] {
...
enter_tunnel(suunta);
aja_tunnelissaa();
exit_tunnel(suunta);
}
Esitä proseduurien enter_tunnel() ja exit_tunnel()
koodi. Ratkaisun täytyy sallia tunnelin tehokas käyttö, eli tunnelissa
täytyy voida olla useita autoja kerrallaan. Sen ei tarvitse olla reilu,
ts. odotusajat saavat muodostua pitkiksi. Perustele lyhyesti se, että
ratkaisusi toimii.
[Vihje: tarvitset omat semaforit ja laskurit eri suuntiin ajaville
autoille.]
-
HUVIPUISTON KARUSELLI
Huvipuistossa on N asiakasprosessia ja yksi karuselliprosessi.
Asiakkaat ajelevat kerta toisensa jälkeen karusellissa, johon mahtuu
kerrallaan C asiakasta (C on pienempi kuin N). Karuselli käynnistyy kuitenkin vasta,
kun se on täynnä. Kunkin ajokerran jälkeen kaikki asiakkaat poistuvat
karusellista muihin puuhiin (kenties palatakseen karuselliin myöhemmin).
Kirjoita asiakkaiden ja karusellin koodien keskeiset osat.
Karusellissa istuminen on asiakkaan koodissa pelkkää odotusta.
-
ATERIOIVAT FILOSOFIT
- Aterioivat filosofit on kirjallisuuden klassikko, mutta millaisia
tietojenkäsittelyyn liittyviä tilanteita filosofien ongelma oikeastaan
pyrkii havainnollistamaan? Mitä tällöin ovat filosofit, haarukat,
spagetit ja mahdolliset sihteerit, jotka voisivat jaella haarukoita
pyytäjille?
- Lukkiutumisriskin syntymiselle on kolme staattista edellytystä. Miten kukin
näistä täyttyy aterioivien filosofien ongelmassa?
Voidaanko filosofien tapauksessa lukkiutuminen estää muuttamalla
haarukoiden käyttösääntöjä siten, että jokin em. ehdoista ei täyty.
Tarkastele kutakin sääntöä erikseen.
- Filosofit toteavat, että vain kaksi heistä voi olla yhtäaikaa
syömässä. He heittävät yhden haarukan menemään ja sopivat, että
jokainen saa käyttää mitä tahansa kahta haarukkaa. Haarukoista
huolehtimaan palkataan tarjoilija ja tiskaaja. Kun filosofille tulee
nälkä, hän istahtaa omalle paikalleen pöytään ja pyytää tarjoilijalta
haarukat. Filosofi odottaa, että saa tarjoilijalta kaksi haarukkaa.
Kun filosofi on syönyt, hän palauttaa haarukat tiskaajalle. Ohessa
filosofien koodi:
process filosofi[i=1 to 5]
{
while (true) {
ajattele();
V(pyydä_haarukat);
P(saa_aloittaa);
syö();
V(vapauta_haarukat);
}
}
Kirjoita tarjoilija- ja tiskaajaprosessien koodit. [Huomaa: Tässä
odotetaan kahta erillista tapahtumaa: haarukoiden pyytämistä ja
palauttamista. Se hoituu parhaiten s.e. kumpaakin varten on oma
prosessi!]
-
MONITORIKYLPYJÄ
- Kerro, miten monitori Bathroom toimii ja mihin sen muuttujia käytetään?
- Toimiiko monitori kaikissa tilanteissa moitteettomasti? Jos ei toimi, niin mitä puutteita siinä on?
Miten koodia pitäisi muuttaa, jotta monitori toimisi oikein?
- Kirjoita koodit Girl- ja Boy-prosesseille, jotka käyttävät monitoria Bathroom kylpyhuoneen
jakamiseen.
monitor Bathroom {
cond bath_free;
int girls = 0;
int boys = 0;
procedure Enter_Boy (){
if (girls !=0) wait (Bath_free);
boys ++;
}
procedure Enter_girl(){
if (boys!=0) wait(Bath_free);
girls++;
}
procedure Exit_boy(){
boys --;
if (boys==0) signal_all(Bath_free);
}
procedure Exit_girl (){
girls--;
if (girls==0) signal_all(Bath_free);
}
}
- PURNUKAN KÄYTTÖ MONITORIIN
Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä
sille hunajaa. Karhun elämä loukossa on vain syömistä
ja odottelua. Mehiläiset kuljettavat hunajaa purnukkaan annos
kerrallaan. Kun purnukka on täynnä (H annosta), viimeisen
annoksen tuonut mehiläinen herättää karhun
ennenkuin poistuu paikalta. Seuraavat paikalle saapuvat mehiläiset
jäävät odottamaan purnukan tyhjenemistä. Kun
karhu on tyhjentänyt purkin, se päästää
mehiläiset töihin ja käy itse nukkumaan.
Ohjelmoi purnukan täyttö ja tyhjentäminen
monitoriin Honey_pot ja esitä mehiläisprosessien (N kpl) ja
karhuprosessin koodi. Selvitä vielä sanallisesti missä
tilanteissa tarvitaan poissulkemista ja synkronointia ja kuinka ne
toteutuvat ratkaisussasi.
- MONITORI TOIMIVAKSI
-
Alla oleva monitorin koodi ei toimi joka tilanteessa oikein. Selvitä, mitä ongelmia ohjelmassa on.
Tutki esimerkiksi, mitä tapahtuu, kun potilaat ja lääkäri pääsevät monitoriin järjestyksessä:
i) potilas1, lääkäri, potilas2;
ii) potilas1, potilas2, lääkäri;
iii) lääkäri, potilas1, potilas2;
-
Korjaa koodi oikein toimivaksi ja varmista lisäksi, että potilaat pääsevät tutkimukseen saapumisjärjestyksessä.
monitor Vastaanotto {
cond sisään;
cond ulos;
cond tutki;
boolean varattu = false;
procedure Tulevastaanotolle ( ) { # potilaan koodi
if (varattu) wait(sisään); # odota sisäänkutsua
varattu = true; # merkitse varatuksi
mene tutkimushuoneeseen
signal(tutki); # ilmoita lääkärille
ole tutkittavana
wait(ulos); # jää odottamaan poistumismerkkiä
poistu tutkimushuoneesta
}
procedure Tutkipotilas ( ) { # lääkärin koodi
signal(sisään); # kutsu potilas sisään
wait(tutki); # odotetaan potilasta
tutki potilas
signal(ulos); # anna poistumissignaali
varattu =false; # vapauta tutkimushuone
}
}
process Potilas( )[i = 1 to n] {
while (true) {
tee mitä ikinä teet
tuntuu sairaalta
call Vastaanotto.Tulevastaanotolle ( );
}
}
process Lääkäri( ) {
while (true) call Vastaanotto.Tutkipotilas( );
}
- NUKKUVA PARTURI MONITORIIN
- Esitä parturiongelmalle yksinkertaisin mahdollinen
perusratkaisu ts. oleta signal-and-continue -semantiikka, ja että
partureita ja tuoleja on vain yksi.
- Laajenna parturiliikettä: yleistä
ratkaisua siten, että parturiliikkeessä toimii useita
partureita samaan aikaan.
-
PROSESSIEN TAHDISTUS
SANOMANVÄLITYKSELLÄ
Laskenta on jaettu rinnakkaisuuden saavuttamiseksi N:lle eri
prosessille. Niihin on ohjelmoitu vikasietoisuutta varten joukko
tahdistuspisteitä: jos jotain menee pieleen, voidaan myöhemmin
jatkaa jostain tahdistuspisteestaä.
Aina kun prosessin suoritus saapuu tahdistuspisteeseen, se
tallettaa sen hetkiset tilatietonsa levylle. Tallettamisensa se saa
tehdä vasta kun, kaikki muutkin prosessit ovat saaneet
tahdistusta edeltävät vaiheet valmiiksi ja päässeet
omaan tahdoistuspisteeseensä. Suoritus saa jatkua laskennan
seuraavaan vaiheeseen vasta, kun kaikki ovat saaneet tallettamisensa
valmiiksi. Prosessien välinen kommunikointi perustuu
sanomanvälitykseen.
Esittele kommunikoinnissa tarvittavat kanavat ja kirjoita
tahdistukseen tarvittavat koodin osat.
- SANOMANVÄLITYSTÄ KORVATUNTURILLA
Lähes koko vuoden Pukin vetoporot vaeltavat Lapin tuntureilla ja syövät jäkälää muiden porojen kanssa.
Jouluaaton lähestyessä vetoporot kokoontuvat Korvatunturille Pukin pajan läheisyyteen. Kun kaikki N vetoporoa
ovat saapuneet paikalle, vetoporoista Petteri Punakuono ilmoittaa tästä Pukille. Pukki valjastaa porot lahjareen
eteen ja niin lähdetään matkaan lahjoja jakamaan.
Kun Pukki on saanut jaettua lahjat kaikille maailman lapsille, porot kiidättävät Pukin taikareen takaisin Korvatunturille,
jossa Pukki kiittää poroja ja vapauttaa ne vaeltamaan muiden porojen kanssa.
Toteuta Pukki ja porot prosesseina, jotka kommunikoivat sanomanvälitystä käyttäen. Piirrä kaaviokuva, josta selviää Pukin ja
porojen välinen kommunikointi. Kirjoita Pukki-ja Petteri-prosessin ja muiden poroprosessien koodit.
- PANKKITILIN YHTEISKÄYTTÖ
Pankkitili on usean henkilön käytössä, joista jokainen voi tallettaa tilille tai nostaa tililtä rahaa.
Tili ei saa koskaan mennä negatiiviseksi. Koodaa palvelin, joka huolehtii tilin käytöstä. Asiakkaat
voivat pyytää joko jonkun rahasumman talletusta tai rahasumman nostoa. Jos tilillä ei ole
tarpeeksi rahaa, niin pyyntöä viivytetään. Asiakkaat ja palvelin käyttävät sanomanvälitystä
kommunikointiin.
-
TIETOKANTAPALVELIN
Toteutetaan lukijat/kirjoittajat -ongelmalle sellainen ratkaisu,
jossa varsinaiset lukija- ja kirjoittajaprosessit eivät
pääsekään suoraan käsiksi tietokantaan, vaan
esittävät luku- ja kirjoituspyyntönsä tietokannan
kirjoittamisesta ja lukemisesta huolehtiville palvelijaprosesseille
(n kappaletta). Valvottava tietokanta on omassa erillisessä
palvelimessaan ja vain palvelijaprosesseilla on pääsy
tietokantaan. Asiakkaiden (lukijat ja kirjoittajat) ja palvelijoiden
välinen kommunikointi perustuu asynkroniseen sanomanvälitykseen.
Piirrä kuva tilanteesta. Mitä kommunikointikanavia
tarvitaan? Millaisia ovat niissä kulkevat sanomat? Miten
asiakkaat pyytävät luku- tai kirjoituspalvelua? Hahmottele
palvelijaprosessien koodi.
Vihje: Koska yhteistä tietokantaa käyttäviä
palvelijaprosesseja on monta, niin ratkaisussa on varmistettava, että
vain yksi prosessi kerrallaan on kirjoittamassa eikä kukaan ole
tällöin lukemassa. Lukuja voidaan tehdä useita
samanaikaisesti. Palvelijaprosessit voivat käyttää
monitoria luku-
ja kirjoitustoimintojen synkronointiin.
-
YHTEISÖN KEITTIÖ
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[1:n] {
while (true) {
get serving from the pot;
eat;
}
}
process cook {
while (true) {
sleep;
put M servings in the pot;
}
}
Kirjoita asiakkaiden ja kokin toimenpiteiden koodien keskeiset osat käyttäen semaforeja ja P/V-operaatioita.
-
KIERTOKÄYNTI MUSEOSSA
Museossa järjestetään vain opastettuja kiertokäyntejä. Vierailijat saapuvat odotushuoneeseen, josta opas heidät sitten noutaa. Vieraan algoritmi on rakenteeltaan seuraavan näköinen:
{tee jotain muualla};
{mene odotushuoneeseen};
{kulje museossa}
ja oppaan
{laske ryhmä museoon};
{kulje museossa}
Pari hallinnollista huomautusta: Ryhmän siirtyessä museon puolelle odotushuoneen ulko-ovi on kiinni ja jos ryhmän koko on alle 10, niin opas jää odottamaan lisää asiakkaita.
Mallita opas ja vierailijat prosesseina. Synkronointi toteutetaan monitorilla, jossa on rutiinit "mene odotushuoneeseen" ja "laske ryhmä museoon". Kirjoita monitorin koodi. Signal-operaatio on tyyppiä signal_and_continue. Miten ohjelmasi toimisi, jos signal-operaation tyyppi olisikin signal_and_wait?
-
HUVIPUISTON KARUSELLI
Huvipuistossa on N asiakasprosessia ja yksi karuselliprosessi. Asiakkaat ajelevat kerta toisensa jälkeen karusellissa, johon mahtuu C asiakasta (C < N). Karuselli käynnistyy kuitenkin vasta, kun se on täynnä. Kunkin ajokerran jälkeen kaikki asiakkaat poistuvat karusellista muihin puuhiin (jonottaakseen karuselliin myöhemmin).
Toteuta tarvittava synkronointi ja poissulkeminen monitoria käyttäen, esitä prosessien koodi.
Selvitä missä tilanteissa tarvittiin synkronointia ja missä tilanteissa tarvittiin poissulkemista ja kuinka ratkaisusi hoitaa nuo tilanteet.
-
WAIT ja SIGNAL SEMAFORIEN AVULLA
Miten monitorin operaatiot "wait" ja "signal" ("signal and continue") voidaan toteuttaa semaforien avulla? Kirjoita tarvittavat koodit.
Yksinkertaisuuden vuoksi oletetaan, että
* järjestelmässä on vain yksi monitori
* monitorin condition-muuttujat esitellään vektorina c[n], jonka elementin tyyppi on "jono", ja
* tyyppiin "jono" liittyy kaksi operaatiota: "insert" ja "remove".
Vihje: wait-operaation suorittava prosessi on syytä panna odottamaan yksityiseen semaforiin. Miksi?
-
TUNNELI JA "SEMAFORIVALOT"
Vuoren läpi on kaivettu etelä-pohjoissuunnassa tunneli, jossa autot voivat ajaa vain yhteen suuntaan kerrallaan. Tunnelia käyttävät autoprosessit kutsuvat proseduureja enter_tunnel(suunta) ja exit_tunnel(suunta) pyrkiessään tunneliin ja poistuessaan tunnelista. Suunta tarkoittaa auton etenemissuuntaa (etelään tai pohjoiseen). Autoprosessien koodi on:
process car[1 to N] {
...
enter_tunnel(suunta);
aja_tunnelissaa();
exit_tunnel(suunta);
}
Esitä proseduurien enter_tunnel() ja exit_tunnel() koodi. Ratkaisun täytyy sallia tunnelin tehokas käyttö, eli tunnelissa täytyy voida olla useita autoja kerrallaan. Sen ei tarvitse olla reilu, ts. odotusajat saavat muodostua pitkiksi. Mutta tunnelin päässä odottavat autot on päästettävä etenemään FCFS-järjestyksessä.
-
PYSÄKÖINTIHALLI
Pysäköintihalliin on useita erillisiä sisäänkäyntejä. Kullakin sisäänkäynnillä on itsenäisesti toimiva tietokone, jossa pyörii kaksi prosessia (~ajuria): anturiprosessi havaitsee auton saapumisen ja auton poistumisen, ja valotauluprosessi huolehtii mm. kameravalvonnasta ja tekstin näyttämisestä valotaululla.
Kokonaisuutta ohjaa valvomossa oleva tietokone, jossa on mm.
- yksi oviprosessi kutakin sisäänkäyntiä kohden ja
- yksi valvontaprosessi ovilla olevien valotaulujen keskitettyä ohjausta varten.
Anturiprosessin ja oviprosessin välinen kommunikointi perustuu sanomanvälitykseen: anturilta tuleva sanoma ilmoittaa auton saapumisen/poistumisen. Oviprosessit ylläpitävät yhteistä laskuria, joka ilmaisee vapaiden paikkojen lukumäärän.
Kun hallissa on tilaa, valotaululla palaa teksti "TILAA". Kun halli täyttyy, valotauluille syttyy teksti "TÄYNNÄ". Myös valvontaprosessin ja valotauluprosessien välinen kommunikointi perustuu sanomanvälitykseen: valvontaprosessi lähettää valotauluille näytettäväksi uuden tekstin aina, kun tilanne vaihtuu.
Oviprosessien ja valvontaprosessin välinen kommunikointi perustuu tehokkuussyistä yhteisen muistin käyttöön.
Esitä oviprosessien ja valvontaprosessin koodi. Anturiprosesseista ja valotauluprosesseista ei tarvitse välittää ts. ei tarvitse esittää kuinka anturiprosessi lähettää sanoman tai kuinka valotauluprosessi vastaanottaa infoa näytettäväksi.
-
SÄÄENNUSTUSTA
Eräs sääennustuslaskenta on toteutettu rinnakkaisena. Ennustettavan alueen ilmatila on jaettu kuutioihin ja kunkin kuution ennustuksesta huolehtii yksi solmukone. Laskenta etenee vaiheittain:
* alkuarvoista lähtien kukin solmu laskee kuutiolleen ensimmäisen ennusteen (esimerkiksi säätila tunnin kuluttua)
* kun ennuste on valmistunut, niin solmu ilmoittaa ennustetun tilan naapureilleen
* saatuaan kaikilta naapureiltaan niiden ennusteet solmu aloittaa seuraavan vaiheen ja laskee seuraavan ennusteeen (esim. säätila kuutiossa seuraavan tunnin kuluttua).
Näin jatketaan, kunnes ennusteet on saatu halutulle aikavälille (esim. viikon ennuste).
Kommunikointi perustuu sanomanvälitykseen, jossa käytetään (globaaleja) kanavia.
Kirjoita yhden solmun laskenta-algoritmin "normaalivaiheen" toimintaa ohjaavan ohjelman oleelliset osat (sovelluksen käynnistys- ja lopetusvaiheista ei tarvitse välittää). Esittele kanavat, täsmennä send/receive-rutiinien synkronointisemantiikka ("blocking" vai "non-blocking").
-
PARTURIT JA YHTEINEN KASSA
Parturiliikkeessä on 5 parturia, jotka palvelevat asiakkaita saapumisjärjestyksessä sitä mukaa kuin ehtivät. Oletetaan, että liikkeeseen sopii korkeintaan N asiakasta kerrallaan. Jos asiakkaita ei ole, parturit odottavat. Kun asiakas tulee paikalle, joku parturi palvelee häntä tai asiakas joutuu odottamaan parturin vapautumista. Kun asiakas on parturoitavana, hän odottaa parturilta ilmoitusta, että työ on valmis ja maksaa. Parturi ei voi ottaa uutta asiakasta ennen kuin on saanut maksun (X euroa) ja lisännyt sen partureiden yhteisen kassan saldoon.
Käytä asiakasprosessin ja parturiprosessin väliseen kommunikointiin sanomanvälitystä ja muussa kommunikoinnissa semaforeja. Määrittele sanomanvälityksessä tarvittavat kanavat ja ratkaisun muut muuttujat sekä esitä asiakas- ja parturiprosessien koodit.
Vihje: Varaa joku parturi ~ parturit lukevat palvelupyyntöjä yhteisestä kanavasta, se palvelee kuka ehtii ensin.
-
PUSKURIPALVELIJA
Tuottaja ja kuluttaja toimivat asynkronisesti, eri koneissa. Kommunikointiin niillä on käytettävissä vain etäproseduurikutsu. Niinpä asynkronisuus on toteutettu sijoittamalla puskuri erityiseen puskuripalvelijaan. Kirjoita koodit tuottajan, kuluttajan ja puskuripalvelijan kommunikointiin.
Ratkaisussa voidaan rajoittua yhden tuottajan ja yhden kuluttajan tapaukseen; toisaalta puskuriin mahtuu useita tietoyksiköitä. Yksityiskohtaisuuden taso: etäproseduurien keskeiset osat, etäproseduurikutsun muoto, puskurin hallinta.
-
TAHDISTUS SANOMILLA
Laskenta on jaettu rinnakkaisuuden saavuttamiseksi N:lle eri prosessille. Niihin on ohjelmoitu vikasietoisuutta varten joukko tahdistuspisteitä: jos jotain mene pieleen, voidaan jatkaa myöhemmin jostain tahdistuspisteestä. Aina kun prosessin suoritus saapuu tahdistuspisteeseen, se tallettaa sen hetkiset tilatietonsa levylle. Tallettamisensa se saa tehdä vasta, kun kaikki muutkin prosessit ovat saaneet tahdistusta edeltävät vaiheet valmiiksi ja päässeet omaan tahdistuspisteeseen. Suoritus saa jatkua laskennan seuraavaan vaiheeseen vasta, kun kaikki ovat saaneet tallettamisensa valmiiksi.
Prosessien välinen kommunikointi perustuu sanomanvälitykseen. Esittele kommunikoinnissa tarvittavat kanavat ja kirjoita tahdistukseen tarvittavat koodin osat.
-
PROBE-ECHO -ALGORITMI
Verkon kuormitustilanteen kartoittamiseen voidaan käyttää esimerkiksi ns. "probe-echo" -algoritmia. Algoritmin idea on yksinkertainen: verkko käsitellään binääripuuna, jonka juurisolmu kysyy kummankin alipuunsa kuormitustiedot ko. alipuun juurelta, nämä toimivat vastaavasti ja tiedot saatuaan palauttavat ne kysyjälle (lisäten mukaan omat tietonsa). Kommunikointiin käytetään sanomanvälitystä globaalien kanavien kautta.
Kirjoita kunkin solmun koodin oleelliset osat. Koodista tulee näkyä prosessirakenne ja kanavien käyttö. Suorituskykysyistä ratkaisussa on hyödynnettävä rinnakkaisuutta niin paljon kuin mahdollista.