581332-8 Rinnakkaisohjelmistot
Erilliskuulustelun 1.4.2005 arvostelusta
HUOM! Jos ratkaisuissa näyttää olevan jotain kummallisuuksia, niin kerro niistä Liisa Marttiselle ( liisa.marttinen@cs.helsinki.fi).
Ilman puskuria tuottajan ja kuluttajan on täytyisi synkronoitua tiedon välitystä varten. Puskuri poistaa tämän rajoituksen. Puskurin pituudesta on hyötyä, jos tuottaja ja kuluttaja toimivat vaihtelevilla nopeuksilla: mitä enemmän vaihtelua sitä suurempi puskuri.
Jos toinen on jatkuvasti nopeampi kuin toinen, niin puskurin pituudesta on vain haittaa. Jos tuottaja on nopeampi, niin tuottaja täyttää puskurin ja sen jälkeen joutuu tahdistamaan toimintansa kuluttajan toimintaan. Ongelmana tässä on jonotus, mitä suurempi puskuri, sitä pidempi jonotus. Monet hommat 'mätänevät' jonossa. Jos kuluttaja on nopeampi, se joutuu aina odottamaan ja puskuri on täysin turha. Mitä isompi sitä enemmän vie turhaan resursseja.
Arvostelusta: Jaossa 3 pistettä:
Toiminnot on synkronoitava: kuluttajan odotettava, että puskuriin tulee kulutettavaa, tuottajan, että puskuriin taas mahtuu laittamaan. Tarvitaan myös poissulkemista: puskurin käsittelyyn liittyviä yhteisiä muuttujia saa käsitellä vain yksi prosessi kerrallaan, jolloin muut joutuvat odottamaan
Semafori:
Prosessit odottavat semaforeissa: kuluttajaprosessi odottaa jonkun
tuottajaprosessin vapauttavan sen V-operaatiolla ja vastaavasti
tuottajaprosessi odottaa jonkun kuluttajaprosessin tekevän V-operaation.
Kaikki prosessit odottavat 'mutex':ssa pääsyä vuorollaan käsittelemään yhteisiä muuttujia.
Monitori:
Tahdistus ehtomuuttujien avulla: kuluttajaprosessi ja tuottajaprosessi
odottavat ehtomuuttujissa, että pääsevät jatkamaan toimintaansa.
Poissulkemisen monitor hoitaa itse: monitoriin pääsee vain yksi kerrallaan =>
muut joutuvat odottamaan monitorin jonossa.
Manager (Tässä manageri + kanavat toimivat puskurina)
Kuluttajaprosessi odottaa receive-käskyssä (blocking) sanomaa managerilta.
Tuottaja ei välttämättä odottele mitään, lähettelee (non blocking send) vain
tuotoksiaan kanavaan, josta manager niitä lukee (receive), kun ehtii (oletetaan
periaatteessa ääretön kanava eli ääretön puskuri).
Poissulkeminen ei ole ohjelmoijan ongelma, sillä kanava huolehtii siitä.
Kanavaan pääsee kirjoittamaan vain yksi kerrallaan => muut odottelevat
vuoroaan.
Etäproseduuri
Tuottajat ja kuluttajat odottavat etäproseduurikutsusta paluuta (itse asiassa
prosessi on suorittamassa tynkäkoodia ja odottaa siellä semaforissa sanoman
palauuttamista.
Etäproseduurin suorittajaprosessi odottaa paikallisessa semaforissa, että kutsun
toteuttava paikallinen prosessi ilmoittaa hoitaneensa tehtävän eli tekee V-
operaation.
Arvostelusta: jaossa oli 12 pistettä
semafori 0- 4 p,
Tämän tyyppistä tehtävää on käsitelty kurssikirjan sivuilla 180-184: Shortest -Job-Next Allocation.
list
Lista, johon talletetaan odottavat muistisivupyynnöt eli pyynnöt, joita pyyntöhetkellä ei pystytty heti täyttämään. Lista on järjestetty pyydetyn sivumäärän amount mukaan nousevaaan järjestykseen ja se sisältää sivumäärän lisäksi pyytävän prosessin tunnuksen eli pareja (amount, id).
Oletetaan, että listan käsittelyyn on käytössä ainakin funktiot: (näitä ei tarvitse kirjoittaa)
List list; # tarkempia listan list määrittelyjä ei tässä tarvitse antaa int avail = M; # muistia kaikkiaan M sivua int amount, # sivujen, pyydettyjen tai vapautettujen, lukumäärä id, # prosessin tunnus (1-n) next; # seuraavan herätettävän prosessin tunnus sem mutex = 1, # poissulkemissemafori b[n] = ([n], 0); # kullakin prosessilla oma semafori, jossa odottaa muistisivuja request(amount, id): P(mutex); if (amount > avail) { # ei tarpeeksi vapaita muistisivuja insert(amount, id, list); # vie prosessin tunnus ja määrä list-listaan oikealle paikalle V(mutex); # vapautetaan, jotta muut pääsevät käsittelemään P(b[id]); # jäädään odottamaan omaan yksityiseen semaforiin } # Kun tähän tulee jonosta, niin edellinen prosessi on jo tarkistanut, että muistia riittää. # Kun tulee suoraan, niin joko lista on tyhjä tai sen ensimmäisen pyyntö on suurempi kuin # vapaa määrä! (jos ei olisi, niin se olisi jo päässyt jonottamasta.) anna prosessille id amount määrä muistia; # tässä käyttöjärjestelmä tekee kaikenlaista avail = avail -amount; # vähennetään vapaata muistia if (notempty(list) & (amount=firstamount(list)) <= avail) { # riittääkö myös seuraavalle next=firstid(list); # herätettävän prosessin tunnus talteen remfirst(list); # poistetaan alkio listasta V(b[next]); # herätetään prosessi } else V(mutex); # vapautetaan mutex uusille prosesseille vasta, kun listan ensimmäisen # muistipyyntöä ei voida täyttää # HUOM! Tässä mutex-semafori säilyy suljettuna, ja herätetty prosessi pääsee heti # jatkamaan toimintaansa eli vähentämään vapaiden sivutilojen määrää omalla varaukseen ja # taas katsomaan, vieläkö seuraavakin prosessi voisi jatkaa. # MUTTA onko tämä oikein? Jollakin mutexia odottavalla prosessilla voi olla # pienempi pyyntö. Pitäisikö sen päästä ennen jo jonossa olevia? # Jos taas aina tutkitaan ensin uudet pyynnöt ja sijoitellaan niitä jatkuvasti listaan oikeaan # paikkaan, niin kaikki muistia odottavat prosessit joutuvat ihan turhaan odottelemaan eikä # mikään prosessi pääse etenemään! # Katsotaan siis, että mutexissa odottavat eivät ole vielä mukana kilpailemassa sivutiloista! release(amount): P(mutex); avail = avail + amount; if (notempty(list) & (amount=firstamount(list)) <= avail) { # riiittääkö myös seuraavalle next=firstid(list); # herätettävän prosessin tunnus talteen remfirst(list); # poistetaan alkio vielä listasta V(b[next]); # herätetään prosessi } else V(mutex); # vapautetaan mutex uusille prosesseille vasta, kun listan ensimmäisen # muistipyyntöä ei voida täyttääArvostelusta :
tämä vielä puuttuu
Ratkaisu, jossa kaikki synkronointiin liittyvät toiminnot on toteutettu omina proseduureina monitorissa.
monitor Silta { int lkm = 0; # autojen lukumäärä sillalla, jotta tiedetään, milloin silta tyhjä boolean stop = false, # saako sillalle ajaa boat_waiting = false; # onko laivuri jo odottamassa sillan nostoa cond put_up, # silta nostettava ylös put_down, # sillan saa laskea alas is_up, # silta on ylhäällä is_down, # silta alhaalla ja autot voivat mennä sillalle is_empty; # sillalla ei ole autoja procedure nosta_silta ( ) { # laivuri pyytää sillan nostamista signal(put_up); # pyydetään sillan nostamista boat_waiting = true; # jos vaikka vahti ei olisi vielä vahtimassa monitorissa wait(is_up) # odota, että silta on ylhäällä } procedure laske_silta( ) { # laivuri antaa luvan laskea silta signal(down); # ilmoita, että sillan saa laskea } procedure aja_sillalle ( ) { # auto pyrkii sillalle while (stop) wait (is_down); # jos stop palaa, jää odottamaan sillan laskemista lkm ++; # kasvata sillalla olevien autojen lukumäärää } procedure poistu_sillalta ( ) { # auto poistuu sillalta lkm -- # yksi auto vähemmän if (lkm = = 0) signal(is_empty) # jos viimeinen, niin ilmoita mahdollisesti odottavalle vahdille } procedure vahdi_siltaa ( ) { # vahti odottelee monitorissa nostopyyntöä if (! boat_waiting) wait(put_up); # odota nostopyyntöä, jos sitä ei ole vielä annettu boat_waiting = false; # varmuuden vuoksi merkataan pyyntö käsitellyksi stop = true # estä autojen meneminen sillalle if (lkm >0) wait(is_empty); # odota kunnes kaikki autot poistuneet sillalta } procedure nostettu ( ) { # vahti on nostanut sillan signal(is_up) # ilmoitus odottavalle laivurille wait(down) # odotellaan, kunnes sillan saa laskea } procedure laskettu ( ) { # vahti on laskenut sillan stop = false; # sillalle ajo sallittua signal_all (is_down) # tieto kaikille odottaville autoille } } # ja tässä ne prosessit process Vahti ( ) { # siltavahti while(true) { # tai niin kauan kun työpäivää kestää call Silta.vahdi_siltaa nosta silta; # jotta autot voivat valmiiksi mennä monitoriin odottamaan call Silta.nostettu( ) laske silta; call Silta.laskettu( ) } } process Laivuri ( ){ # laivuri while (true) { ajele, kunnes tarvii mennä sillan toiselle puolelle; call Silta.nosta_silta #pyydä sillan nostamista mene sillan toiselle puolelle call Silta.laske_silta # sillan saa laskea } } process Auto[i = 1 to N] ( ) { # autot while (true) ajele, missä ajelet, kunnes tarpeen ylittää silta; call Silta.aja_sillalle; ylitä silta; call Silta. poistu_sillalta; }Laivurin sillan alituksen voisi myös toteuttaa yhdessä proseduurissa, koska sinä aikana millään muulla prosessilla ei ole mitään järkevää tekemistä monitorissa:
procedure alita_silta ( ) { # laivuri pyytää päästä sillan toiselle puolelle signal(put_up); # pyydetään sillan nostamista boat_waiting = true; # jos vaikka vahti ei olisi vielä vahtimassa monitorissa wait(is_up) # odota, että silta on ylhäällä alita silta; signal(down); # ilmoita, että sillan saa laskea } process Laivuri ( ){ while (true) { ajele, kunnes tarvii mennä sillan toiselle puolelle; call Silta.alita_silta # pyydä pääsyä sillan toiselle puolelle } }Samoin siltavahdin sillan nostaminen ja laskeminen voitaisiin tehdä yhdessä proseduurissa: autot voivat odottaa monitoriin pääsyä ja nostossa laivuri on jo odottamassa monitorissa ja laskussa puksuttelemassa omia teitään.
procedure vahdi_siltaa ( ) { # vahti odottelee monitorissa nostopyyntöä if (! boat_waiting) wait(put_up); # odota nostopyyntöä, jos sitä ei ole vielä annettu boat_waiting = false; # varmuuden vuoksi merkataan pyyntö käsitellyksi stop = true # estä autojen meneminen sillalle if (lkm >0) wait(is_empty); # odota kunnes kaikki autot poistuneet sillalta nosta silta; signal(is_up) # ilmoitus odottavalle laivurille wait(down) # odotellaan, kunnes sillan saa laskea stop = false; # sillalle ajo sallittua signal_all (is_down) # tieto kaikille jo monitorissa odottaville autoille } process Vahti ( ) { while (true) call Silta.vahdi_siltaa; }Arvostelusta:
Vakavia ja vähemmän vakavia virheitä:
On useita eri tapoja toteuttaa kontrollisprosessien kommunikointi:
Arvostelusta: Esitetystä ratkaisusta on saanut 1-5 ratkaisun toimivuudesta riippuen. Yleensä ne, jotka ovat jotain a-kohtaan vastanneet ovat saaneet 3-5 pistettä. Monet ovat esittäneet useita tapoja, mutta yksikin ratkaisu on riittänyt
Valitaan toteutettavaksi vaihtoehto 1, joka on lyhyin kirjoittaa, vaikka harvoin järkevin toteuttaa. Jos prosesseja on paljon, niin joudutaan lähettämään hyvin runsaasti sanomia: tässä ratkaisussa n*n, koska kaikki lähettävät kaikille (myös itselleen).
chan load[j=1 to n] (int is_number, float is_load); # jokaisella oma kanava process P[i= 1 to n] { # kaikki prosessit toimivat samalla tavoin float myload, newload, first=9999999, second= 9999999; # suuret arvot int j, number, number1, number2; myload = selvitä_oma_kuorma(); #sovitulla tavalla for [j=1 to n] send load[j] (i, myload); # lähetetään oma kuorma kaikille (myös itselle) for [j=1 to n] { receive load[i](number, newload); # luetaan itselle tulleet n sanomaa omasta kanavasta # haetaan niistä ne pienimmät kuormat # tämän voi myös esittää 'sanallisesti' if (newload < second) { if (newload < first) { # löytyi kaikkein pienin second = first; number2=number1; first = newload; number1= number } else { # löytyi vain toiseksi pienin second = newload; number2=number; } } } }
Arvostelusta:
Voidaan toteuttaa myös Keskitetty ratkaisu, jossa on hieman enemmän kirjoittamista.
chan loads (int my_number, float my_load), results[n]( int first, double first_load, int second, float second_load); process P[1] { # koordinoiva prosessi float my_load, new, smallest, second; # kuormia int number1=1, number2, newnumber; #koneiden numeroita smallest = myload( ); # oma kuormitus pienimmäksi receive loads(newnumber, new); #luetaan eka kuormitus toisilta # laitetaan oma ja eka kuormitus järjestykseen if (new < smallest) { second = smallest; number2 = number; smallest = new; number1 =newnumber; } else { second = new; number2 = newnumber; } # ja sitten luetaan muut ja tutkitaan löytyykö pienempiä for [i =3 to n] { receive loads(newnumber, new); if (new < smallest) { second = smallest; number2 = number; smallest = new; number1 =newnumber; } else if (new < second)){ second = new; number2 = newnumber; } } # lopuksi lähetetään muille tiedot for [i =2 to n] send results[i]( number1, smallest, number2, second) } process P[i= 2 to n] { # ne muut prosessit float myload, smallest, second; int number1, number2; laske oma kuormitus; # sovitulla tavalla send loads (i, myload); # lähetä koordinoijalle receive results[i](number1, smallest, number2, second); # tiedot vähiten kuormitetuista }