Rinnakkaisohjelmistot s 2004
Kurssikokeen 10.12.2004 arvostelusta
-------------------------------------------------------------------------------- Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 1 /Riikka Kaven ----------------------------------------------------------------------------------1. Vastaa seuraaviin kysymyksiin. [12 p]
-------------------------------------------------------------------------------- Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 2 /Sini Ruohomaa ----------------------------------------------------------------------------------2.Sekoilua semaforeilla? [14 p]
Oheinen ratkaisu tuottaja-kuluttaja-ongelmaan ei toimi oikein. Mitä virheitä ratkaisussa on ja mitä toimintaongelmia nämä virheet aiheuttavat? Onko mahdollista lisätä tuottajien ja kuluttajien rinnakkaisuutta? Jos on, niin miten? Korjaa koodi oikein toimivaksi tai kirjoita aivan oma ratkaisusi. Muista liittää kommentteja omaan koodiisi, vaikka annetussa koodissa ei niitä olekaan!
char buffer[n]; int start = 0, end = 0; sem empties = n, fulls =1, turn = 0; process Producer[i=1 to M] { char data; .... while (true) { ..... produce data; P(empties); P(turn); buffer[end] = data; end = (end + 1) % n; V(fulls); V(turn); } } process Consumer[i=1 to N] { char result; ..... while (true) { ..... P(turn); P(fulls); result= buffer[start]; start= (start + 1) % n; V(turn); V(empties); use result; } }
------------------------------------------------------------------------------ Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 3 /Avrll ------------------------------------------------------------------------------3. Spagettia monitorissa [13 p]
Eräs ratkaisu:
-------------------------------------------------------------------------------------- process filosofi[i=1 to N] { while (true) { ajattele, kunnes tulet nälkäiseksi; nappaa haarukka ja lautanen; call Spagettia.ota_lautasellinen(); syö lautasellinen spagettia; } } process apupoika { while (true) { call Spagettia.valmista_kulhollinen(); syö jämät kattilan pohjalta; } } monitor Spagettia { int lautasellisia = 0; cont kulho_tyhjä; # ehtomuuttuja, jossa apupoika odottaa, # että kulho tyhjenee cond kulho_täynnä; # ehtomuuttuja, jossa filosofit odottavat, # että kulho täyttyy procedure ota_lautasellinen() { # jos kulho tyhjä, jää odottamaan while (lautasellisia == 0) wait(kulho_täynnä); lautasellisia--; # jos otit viimeisen annoksen, herätä apupoika if (lautasellisia == 0) signal(kulho_tyhjä); } procedure valmista_kulhollinen() { if (lautasellisia > 0) wait(kulho_tyhjä); valmista spagetti, täytä kulho ja vie pöytään; lautasellisia = M; signal_all(kulho_täynnä); # herätä KAIKKI odottavat } }Arvosteluperusteita:
4:n miinuspisteen mokia:
Pikkupisteille pääsi aina, jos oli selvästi oikeansuuntainen ja ymmärrettävä idea, vaikka seassa olikin paljon ym. virheitä. Tavallisin virhe oli while-lauseen tai if-lauseen puuttuminen wait()-operaation yhteydessä.
Huomaa, että syöminen tulee sijoittaa monitorin ulkopuolella (rinnakkaisuus!). Tuosta ei pistemenetyksiä, sillä monet eivät olleet kirjanneet syömistä lainkaan näkyviin. Mutta, jos ratkaisun rakenne oli sellainen, että syöminen väkisinkin jäi monitorin puolelle, siitä menetti 1p.
Ratkaisun ei tarvinnut olla reilu, ts. aiemmin paikalle tulleilla ei oletusarvoisesti "etuajo-oikeutta".
o-o-o-o-oAllaoleva ratkaisu huolehtii myös siitä, että uusi paikalle tuleva filosofi ei pääse etuilemaan. Perustuu Condition passing -tekniikkaan.
monitor Spagettia { int lautasellisia = 0; boolean odottajia_jonossa = false; cont kulho_tyhjä; cond saa_ottaa; procedure ota_lautasellinen() { # jos kulho on tyhjä, tai joku odottaa kulhon täyttymistä, jää odottamaan if (lautasellisia == 0 OR odottajia_jonossa) wait (saa_ottaa); spagettia --; if (lautasellisia == 0) signal(kulho_tyhjä); elif (!empty(saa_ottaa) signal(saa_ottaa); # herätä SEURAAVA odottava else odottajia_jonossa=false; # uusi tulija pääsee ottamaan } procedure valmista_kulhollinen() { if (lautasellisia > 0) wait(kulho_tyhjä); valmista spagetti, täytä kulho ja vie pöytään; lautasellisia = M; # jos joku odottamassa jonossa, päästä etenemään if (!empty(saa_ottaa) { signal(saa_ottaa); # herätä jonon ENSIMMÄINEN odottajia_jonossa = true; # estä uutta tulijaa etuilemasta } } } ------------------------------------------------------------------------------ Rinnakkaisohjelmistot, kurssikoe 10.12.2004, tehtävä 4 / Liisa Marttinen --------------------------------------------------------------------------------4. Sanomanvälitystä Korvatunturilla [12 p]
------------------------------------------------------------------------------------------- Eräs ratkaisu: # käytettyjen kanavien määrittelyt chan paikalla( char), # poroilta Petterille tieto poron saapumisesta kaikkivalmiina( ), # Petteriltä Pukille tieto pukilta[N](char); # pukki ilmoittaa (lähtiessä 'MENOKSI', päättyessä 'KIITOS') # prosessien määrittelyt process Pettteri { # tässä ratkaisussa yksi vetoporoista, Petteri, toimii koordinaattorina while (true) { kuljeskele siellä sun täällä Lapissa; joulun lähestyessä saavu Korvatunturille; # jotenkin vetoporot aistivat tämän for [i=1 to N-1 ] receive paikalla( ); # vastaanota saapumisilmoitus N-1:ltä porolta send kaikkivalmiina( ); # ilmoita pukille porojen olevan valmiina receive pukilta[0]( ); # odota pukin lähtökäskyä ('MENOKSI') # Lahjojen jakamisen toteutus voidaan tehdä eri tavoin: # Tässä ratkaisussa poroilla on valmis rutiini, jonka ne toteuttavat vedä taikarekeä se tavallinen joululenkki; # joulukierroksen toteuttaminen # Voidaan myös käyttää pukilta-kanavia pukin tarkempien ohjauskomentojen antamiseen: # 'Nyt lennetään Villen luo!', 'Nyt suunta takaisin kotiin!' jne. # Tai kukin poroprosessi käynnistää suuren määrän rinnakkaisia porosäikeitä, jotka Internetin # välityksellä hyvin nopeasti leviävät eri puolille maapalloa suorittamaan jakelutehtäviä. Itse # prosessi vaipuu unihorteeseen, josta pukin KIITOS sen herättää. # Myös Pukki ja lahjareki monistuvat jotenkin eri puolilla maapalloa sijaitseviin lähtöpisteisiin. # (Tässä ehkä tapahtuuu Kiina-ilmiö eli kiinalaisilla alihankkijoilla voi olla sormensa pelissä.) # Lähtöpisteistä lahjojen jako aloitetaan siinä määrin kuin mahdollista rinnakkaisesti. # Vain rinnakkaisuuden avulla pystytään näin valtaisasta jakelutehtävästä suoriutumaan # riittävän nopeasti. receive pukilta[0]( ); # homma on hoidettu, pukki kiittää ('KIITOS') } } process vetoporo[i= 1 to N-1] { while (true) { kuljeskele siellä sun täällä Lapissa joulun lähestyessä saavu Korvatunturille; send paikalla( ); # ilmoita Petterille olevasi valmis receive pukiltaporoille[i]( ); # vastaanota Pukin lähtökäsky # tässä porot lumoutuvat ja muuttuvat lentäviksi poroiksi, jotka kuin unessa vetävät # taikarekeä valonnopeutta suuremmalla vauhdilla vedä taikarekeä tavallinen joululenkki; # joulukierroksen toteuttaminen receive pukiltaporoille[i] ( ); # homma on hoidettu, otetaan vastaan kiitokset } } process Pukki { while (true) { tee sitä sun tätä siellä sun täällä; valvo lahjojen valmistusta; lepää ennen joulun ponnistuksia; receive kaikkivalmiina( ); # ota vastaanPetterin ilmoitus porojen saapumisesta valjasta porot lahjareen eteen; # tässäkin riittäisi lähettää N sanomaa yhteiseen kanavaan, mutta ratkaisussa jokaisella # porolla on oma kanavansa, johon Pukki voisi lähettää juuri tälle porolle tarkoitetun viestin # (MATKAAN 'i'.) # Ratkaisussa kaikille lähetetään sama viesti, jonka sisällöllä ei ole toiminnan kannalta väliä for [i = 0 to N-1] send pukiltaporoille[i]('MATKAAN'); # anna lähtökäsky jaa lahjoja kunnes kierros lopussa ja kaikille kilteille on lahjat jaettu; for [i = 0 to N-1] send pukiltaporoille[i]('KIITOS'); # kiitä ja vapauta porot nauti joulusta; } } -------------------------------------------------------------------------------------------------------
Ratkaisussa sanomia käytetään tahdistamaan toimintaa. Niiden sisällöllä ei tässä ratkaisussa ole merkitystä. Porot voivat ilmoittaa tunnuksensa, mutta sillä ei ole mitään käyttöä. Tarvitaan vain N-1 ilmoitusta, jotta tiedetään, että kaikki vetoporot ovat koollla. Lisäksi poroprosessit on numeroitu 0:sta N-1:een, joten kullekin osataan lähettää sen omaan kanavaan.
Arvostelusta:
Tehtävä
oli osattu melkoisen hyvin; lähes 1/3 sai tehtävästä
täydet pisteet.
Petterin
tulee ilmoittaa porojen saapumisesta ja Petteri voi myös toimia
välittäjänä kaikessa Pukin ja muiden porojen välisessä viestinnässä.
Tärkeintä on prosessien välinen
tahdistus ja viestintä sanomanvälitystä käyttäen.
Lahjojen
jakamista maailman lapsille tai muuta kommunikointiin liittymätöntä toimintaa, ei tarvitse tarkemmin selvittää.
Arvostelun painopiste oli kanavissa ja niiden käytössä sanomien välitykseen.