| 581331 Rinnakkaisohjelmistot (2 ov) / Kokeissa kysyttyjä (Häkkinen 2004) |
VASTAA LYHYESTI
Mitä tarkoittaa "puomisynkronointi" (barrier synchronization)? Miten se eroaa tavallisesta "P/V-synkronoinnista"?
Mitä hyötyä on puskurin käytöstä tuottaja-kuluttaja -rakenteen toteutuksessa? Miten puskurin pituus vaikuttaa suorituskykyyn?
KUKA ODOTTAA KETÄ?
Miten kuluttajan odottaminen toteutuu, jos ratkaisu perustuu 1) semaforien, 2) monitorin, 3) sanoman välitystä käyttävän puskurimanagerin, 4) etäproseduurin käyttöön?
Siis kuka/mikä odottaa? Missä odottaa? Mitä odottaa? (Käytä ko. menetelmän käsitteistöä, käyttöjärjestelmän sisälle ei pidä mennä.)
LUKKIUMIA JA MUITA ONGELMIA
Mitkä ovat ne ehdot, joiden vallitessa saattaa syntyä lukkiutumistilanne? Miten kukin näistä ehdoista täyttyy aterioivien filosofien ongelmassa? Miten filosofien tapauksessa lukkiutuminen voitaisiin estää muuttamalla haarukoiden käyttösääntöjä siten, että jokin em. ehdoista ei täyty. Tarkastele kutakin sääntöä erikseen.
Anna paikanvarausjärjestelmään liittyvä esimerkki kustakin rinnakkaisten järjestelmien neljästä perusongelmasta: poissulkeminen, synkronointi, lukkiutuminen ja nälkiintyminen.
RINNAKKAISLASKENNAN HAVAINNOLLISTAMINEN
Olet tekemässä oppimateriaalia ja tarkoituksena on havainnollistaa rinnakkaislaskentaa.
Anna opintorekisterin käyttöön liittyviä esimerkkejä siitä,
- mitä voidaan rinnakkaistaa (ja miten ko. rinnakkaisuus saadaan aikaan)
- mitä ei voida rinnakkaistaa
- mitä hyötyä rinnakkaistamisesta on (mainitsemissasi esimerkeissä) ja
- mitä haittaa rinnakkaistamisesta on (mainitsemissasi esimerkeissä).LUKKIUTUMISTILANTEITA
Mitkä ovat lukkiutumistilanteen neljä välttämätöntä ja riittävää ehtoa? Selitä, mitä kukin tarkoittaa resurssien jakelussa.
Ryhmäkommunikoinnissa syntyy toisinaan lukkiutumistilanne: kaikki odottavat sanomaa joltakulta toiselta (receive-käskyssä). Miten em. neljä ehtoa toteutuvat tässä tilanteessa?
JOKI JA NOSTOSILTA
Joen yli on rakennettu nostosilta, jota pitkin autot voivat ylittää joen. Laivuri ajaa edestakaisin joella ja voi pyytää siltavahtia nostamaan sillan ylös. Laivalla on aina etuajo-oikeus, joten kun laivuri on pyytänyt siltaa nostettavaksi, ei siltavahti päästä enää uusia autoja sillalle. Kun laiva on ohittanut sillan, laivuri ilmoittaa siitä siltavahdille. Siltavahti laskee sillan alas ja sallii autojen taas käyttää siltaa.
Esitä semaforeja käytävä toteutus, jolla laivuriprosessi, autoprosessit ja siltavahtiprosessi saadaan synkronoitua.
MEHILÄISPARVI JA KARHU
Mehiläisparvi ruokkii loukkuun joutunutta karhua keräämällä sille hunajaa. Karhun elämä loukussa 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 purkin, se päästää mehiläiset taas töihin ja käy itse nukkumaan.
Ohjelmoi purnukan käyttöä synkronoivat osat monitoriin, sekä esitä niiden lisäksi mehiläisprosessien (N kpl) ja karhuprosessin koodi.
MUISTINHALLINTA MONITORISSA
Muistinhallinta toteutetaan monitorina, jossa on kaksi käyttäjän operaatiota: request(amount) ja release(amount), missä amount on kokonaisluku. Kun prosessi kutsuu proseduuria request(), se joutuu odottamaan, kunnes sille voidaan antaa amount-parametrin ilmoittama määrä sivutiloja. Prosessi vapauttaa sivutiloja kutsumalla operaatiota release(). Muistin jakelussa noudatetaan "pienin pyyntö ensin" -periaatetta (odottajia palvellaan pyyntöjen suuruusjärjestyksessä).
Kirjoita muistinhallinnan toteuttavien operaatioiden request() ja release() koodit. Ratkaisun tulee sisältää muistinhallinnan teknisestä toteutuksesta vain sen verran, mitä tarvitaan odotuksen toteuttamiseen ja päätöksentekoon. Signal-operaatio on tyyppiä "signal and wait".
PANKKIIRIN ALGORITMI
Järjestelmässä on kolmea resurssityyppiä A, B ja C. Resurssia A on 9 yksikköä, resurssia B 3 yksikköä ja resurssia C 6 yksikköä. Suoritettavana on 4 prosessia. Tiedossa olevat prosessien maksimitarpeet ovat P1: (3, 2, 2), P2: (6,1,3), P3: (3,1,4) ja P4: (4,2,2). Tietyllä hetkellä varaustilanne on P1:(1,0,0), P2:(5,1,1), P3:(2,1,1), P4: (0,0,2)
a) Prosessi P2 pyytää saada lisää yhden A-resurssin ja yhden C-resurssin. Voidaanko ne myöntää? Ratkaise tehtävä pankkiirin algoritmia käyttäen. Perustele vastauksesi esittämällä pankkiirin algoritmin suoritusvaiheet riittävällä tarkkuudella. Mitä tapahtuu pankkiirin algoritmin suorituksen jälkeen?
b) Entä, jos ko. pyynnön olisikin esittänyt P1?
REITITIN
Tietoliikenneverkon reitittimen ohjelmiston perusrakenne voisi olla seuraavanlainen:
- m säiettä odottaa sanomia, kukin omalta kanavaltaan
- m säiettä kirjoittaa sanomia, kukin omalle kanavalleen
- jokaisella kirjoittavalla säikeellä on yhden sanoman mittainen puskuri
- kun lukeva säie on saanut sanoman, se vie sanoman (reititystaulun määrittelemän) kirjoittajan puskuriin; jos puskuri on täynnä, lukija odottaa.
Kirjoita tämän toiminnallisuuden toteuttava koodi. Ratkaisun ei tarvitse sisältää osoitteen määrittämiseen liittyviä yksityiskohtia.
Tähän tehtävään ei kuulu se, miten sanoma siirtyy send-operaation näkemästä kanavasta receive-operaation näkemään kanavaan. Voit olettaa, että siirrettävänä voi olla enintään yksi sanoma kerrallaan ja että siirto on aina virheetön.
NUKKUVA PARTURI
Esitä nukkuvan parturin ongelman ratkaisu käyttäen semaforeja. Partureita on täsmälleen yksi, mutta odotushuone on iso (aina mahtuu vielä yksi odottaja). Parturoinnin aikana asiakas nukkuu, mutta parturin täytyy tietää, ketä parturoi (asiakasprosessit ovat client[i=1 to N] ja "tukanleikkuu" koskee ko prosessin tietorakenteisiin).
Ratkaisun tulee olla mahdollisimman yksinkertainen.
SILTA YLI VIRRAN
Joen yli johtaa kapea silta, jonka autot voivat ylittää vain yhteen suuntaan kerrallaan. Mallita autot prosesseina ja liikenteenvalvoja monisäikeisenä prosessina. Kirjoita sillankäyttöongelman ratkaisu käyttäen semaforeja.
Ratkaisun täytyy sallia sillan riittävän tehokas käyttö (eli sillalla täytyy voida olla useita autoja kerrallaan), mutta sen ei tarvitse olla reilu (odotusajat saavat muodostua pitkiksi).
Perustele lyhyesti se, että ratkaisusi toimii.
TUOTTAJA - PUSKURI - KULUTTAJA
Esitä monitoriin perustuva tuottajat / kuluttajat -ratkaisu, jossa tuottajilla ja kuluttajilla on käytettävissä yhteinen, rajallisen kokoinen puskuri (N alkiota). Esitä myös tuottajaprosessien ja kuluttajaprosessien koodit s.e. niistä käy selkeästi ilmi kuinka prosessit vievät tietoa puskuriin ja kuinka prosessit noutavat tietoa puskureista.
Selvitä vielä sanallisesti missä tilanteissa tällä kertaa tarvitaan poissulkemista ja synkronointia sekä selitä kuinka ne on hoidettu ratkaisussasi.
YHTEINEN KYLPYHUONE
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: }a) Kirjoita vastaava koodi tyttöprosesseille, esittele ratkaisun muuttujat ja selitä niiden käyttötarkoitukset (Mihin käytetään? Miksi tarpeen?).
b) 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ä().
c) Muuta ratkaisua s.e. kylpyhuoneessa voi olla korkeintaan 4 tyttöä tai poikaa kerrallaan. Selitä miksi ratkaisusi toimii oikein.
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.
|
Kuinka saatoit epäonnistua kokeessa? Helposti - osallistuin. |