Prosessien synkronointi, tuottaja-kuluttaja -ongelma ==================================================== Idea: - Yksi prosessi/säie tuottaa dataa elementti kerrallaan. Tämä voi olla hidas tai nopea toimenpide, ja dataelementin koko voi olla pieni tai suuri. - Toinen prosessi/säie lukee ja käsittelee (="kuluttaa") tuotettua dataa elementti kerrallaan. Tämä voi olla hidas tai nopea toimenpide, erityisesti se voi olla paljon hitaampaa tai nopeampaa kuin tuottaminen. - Tällä tavoin saavutetaan mm. modulaarisuutta ohjelmien tekemiseen, jakeluun ja suorittamiseen. - Tietotekniikan realiteetit: + Datan siirtopuskuriin (muistialue, tiedosto tai muu) mahtuu vain äärellinen, ennalta päätetty määrä elementtejä. + moniajossa kumpikaan prosessi ei ilman erityistemppuja voi päättää vuorontamisesta; erityisesti tuottajaprosessi voi keskeytyä kun elementin kirjoittaminen on puolivalmis, ja myös kuluttaja voi keskeytyä kesken elementin lukemisen. Mikä tärkeätä: - Puskurin täyttyessä pitää pystyä odottamaan, että tilaa vapautuu. Muutoin ei ole mahdollista kirjoittaa uutta tuotosta mihinkään. Tuottajan pitää pystyä odottamaan. - Puskurin sisällön pitää olla koko ajan järkevä (ei puolivalmista dataa) ja myös täytyy olla järkevät osoittimet eli muistiosoitteet paikkaan, jota kirjoitetaan ja jota luetaan. Esimerkiksi voidaan tuottaa "rengaspuskuriin" prosessien yhteisessä muistissa. Puskurin koko on kiinteä, "N kpl" elementtejä. Kun N:nnäs elementtipaikka on käsitelty, otetaan seuraavaksi taas ensimmäinen elementtipaikka. Siis muistialueen käyttö voitaisiin ajatella renkaaksi. "Kuva": |ABCDEFghijklmnopqrstuvwxyz| ^tuottaja tuottaa muistipaikkaan tALKU+ti ^kuluttaja lukee muistipaikasta kALKU+ki Virtuaalimuistin hienous: tALKU != kALKU eli tuottaja ja kuluttaja voivat olla omia prosessejaan, ne näkevät puskurin alkavan jostain kohtaa omaa virtuaalimuistiavaruuttaan, ja niillä on oma indeksi tällä hetkellä käsittelemäänsä elementtiin. MUTTA viitattu fyysinen muistiosoite fALKU on sama. Muistinhallinnan yhteydessä tutustutaan tarkemmin ns. osoitteenmuodostukseen prosessin virtuaaliosoitteesta todelliseksi, joka menee prosessorista osoiteväylälle. Termistöä ========= Kriittinen alue == kohta ohjelmakoodissa, joka voi aiheuttaa ongelmatilanteen moniohjelmoinnissa (eli kun on useita prosesseja/säikeitä) Poissulku == Ohjelmointikeino, jolla estetään muita prosesseja/säikeitä suorittamasta kriittistä aluetta väärään aikaan (eli ennen kuin se on järkevää toimintalogiikan kannalta) Toimii binäärisellä semaforilla. Synkronointi == Ohjelmointikeino, jolla ohjataan Semaforin rakenne ================= Korostan: Semafori on käyttöjärjestelmän käsittelemä rakenne, ja siis yhdenlainen palvelu, jonka käyttöjärjestelmä tarjoaa rajapintansa kautta. Abstrahoituna: käyttöjärjestelmä virtuaalikoneena ajateltuna tarjoaa rajapinnassaan keinoja allaan olevan tason, eli laitteiston, hallintaan. Semaforin avulla hallitaan osaltaan vuorontamista eli sitä, miten prosessorilaitteelle jaellaan prosessien konteksteja. Yhdessä semaforissa on arvo (value) ja jono prosesseista. Arvo: kokluku Jono: PID 213 -> PID 13 -> PID 678 -> NULL Semaforit pitää voida yksilöidä. Ne ovat saatavilla/käytettävissä KJ-kutsujen kautta. Semaforien yksilöinnin ja yleisen hallinnan lisäksi käyttöjärjestelmä toteuttaa seuraavanlaisen pseudokoodin mukaiset käyttöjärjestlemäkutsut semaforin soveltamiseksi; niiden nimet voisivat olla "wait()" ja "signal()", mutta yhtä hyvin jotakin muuta vastaavaa... Kutsu on sovellusohjelmassa, ja sen parametrina on annettava yksi tietty semafori. wait(Sem): if (Sem.Arvo > 0) Sem.Arvo := Sem.Arvo - 1; else {eli silloin kun Sem.Arvo <= 0} Laita pyytäjäprosessi blocked-tilaan tämän semaforin jonoon. signal(Sem): if (Jono on tyhjä) Sem.Arvo := Sem.Arvo + 1; else Ota jonosta seuraava odotteleva prosessi suoritukseen. Alustava esimerkki: Poissulkeminen (Mutual exclusion, MUTEX) ============================================================ Alkutilanne: semMunMutexi.Arvo: 1 semMunMutexi.Jono: NULL PID 77:n koodia suoritetaan, siellä on kutsu wait(semMunMutexi) -> ohjelmallinen keskeytys, prosessi PID 77 kernel running -tilaan, suoritetaan käyttöjärjestelmän koodista semaforin käsittely wait(). Ks. pseudokoodi yllä. Tässä tapauksessa seuraavaksi tilanne on: semMunMutexi.Arvo: 0 semMunMutexi.Jono: NULL käyttöjärjestelmästä palataan PID 77:n koodin suorittamiseen heti wait()-kutsun jälkeisestä käskystä. Nyt PID 77:llä on yksinoikeus suorittaa semMunMutexi-semaforilla merkittyä kriittistä aluetta. Esim. PID 898 tulisi jossain vaiheessa vuoronnetuksi suoritukseen ennen kuin semMunMutexi olisi signaloitu. Sitten PID 898:n koodi lähestyisi kriittistä aluetta ja siihen kirjoitettu wait() aiheuttaisi seuraavan tilanteen: semMunMutexi.Arvo: 0 semMunMutexi.Jono: PID 898 -> NULL käyttöjärjestelmä siirtäisi prosessin 898 Blocked-tilaan, ja liittäisi sen semMunMutexin jonoon odottamaan signal()-kutsua. Tämä (kuten ylipäätään käyttöjärjestelmäkutsu aina) tapahtuu sovellusohjelmien kannalta "atomisesti" (vai "atomaarisesti") eli mikään käyttäjän prosessi ei pääse suorittumaan ennen kuin käyttöjärjestlmä on tehnyt vaadittavat organisointi- ja kirjanpitotyöt. Useilla prosesseilla voisi olla erilaisia toimenpiteitä semMunMutexilla suojattuun jaettuun resurssiin. Vuorontaja jakelisi prosesseille aikaa ja kaikki tapahtuisi nykyprosessorissa hemmetin nopeasti. Jossain vaiheessa tilanne voisi olla esimerkiksi seuraava: semMunMutexi.Arvo: 0 semMunMutexi.Jono: PID 898 -> PID 341 -> PID 123 -> NULL Jonoon on kertynyt prosesseja. PID 77, joka ehti kutsumaan wait(semMunMutexi) ensimmäisenä, saa lopulta operaationsa valmiiksi jollakin ajovuorollaan, ja jos se on oikeellisesti ohjelmoitu, niin kriittisen alueen lopussa on kutsu signal(semMunMutexi). Jälleen käyttöjärjestelmä atomisesti hoitaa tilanteeksi: semMunMutexi.Arvo: 0 semMunMutexi.Jono: PID 341 -> PID 123 -> NULL PID 898 on siirretty blocked tilasta ready-tilaan, ja se on siirretty semMunMutexin jonosta vuorontajan ready-jonoon. (Tai, sekoittaaksemme päitämme, se voitaisiin ottaa suoraan suoritukseen, jos vuoronnus ja semaforit olisivat sillä tavoin toteutetut...) Semaforin arvo pysyy kuitenkin yhä 0:na, mikä tarkoittaa, että resurssi ei vielä ole vapaa, vaan siellä joku suorittaa kriittistä aluetta, ja mahdollisesti sinne on jo jonoakin päässyt kertymään. Sitten jos uusia jonottajia ei ole wait() -kutsun kautta tullut, ja aiemmat prosessit ovat yksi kerrallaan suorittaneet kriittisen alueensa ja kutsuneet signal(), niin viimeinen signal() tapahtuu esitilanteessa: semMunMutexi.Arvo: 0 semMunMutexi.Jono: NULL Ja signalin jälkeen resurssi vapautuu täysin, sillä tilanne on: semMunMutexi.Arvo: 1 semMunMutexi.Jono: NULL Tämä vastaa esimerkin ihan ensimmäistä tilannetta. Tärkeätä huomata: Ohjelmoija kutsuu käyttöjärjestelmän palveluita sovellusohjelmasta:: Wait(S) // "atominen käsittely", käyttäjän prosessit keskeytettynä. ... kriittinen alue ... Signal(S) // "atominen käsittely" Tuottaja-kuluttaja -probleemin ratkaisu ======================================= Tuottaja-kuluttaja -ongelma eli kahden prosessin välinen tietovirran synkronointi voidaan ratkaista semaforeilla seuraavaksi esitetyllä tavalla. Toinen perinteinen, erilainen ongelma-asettelu on "kirjoittajien ja lukijoiden" ongelma, jossa voi olla useita kirjoittajia ja/tai useita lukijoita (tuottaja-kuluttajassa tasan yksi kumpaistakin). Lisäksi on muita perinteisiä esimerkkiongelmia, ja todellisessa ohjelmistotyössä jokainen yhdenaikaisuutta hyödyntävä sovellus saattaa tarjota uusia vastaavia tai erilaisia ongelmia, jotka on ratkaistava että ohjelma toimisi joka tilanteessa oikeellisesti. Myös ratkaisutapoja on muitakin kuin semaforit. Yksinkertaisuuden vuoksi Käyttöjärjestelmät -kurssilla käydään läpi vain yksi yksinkertainen ongelmatapaus ja yksi yksinkertainen ratkaisu siihen. Tarvittavat semaforit: MUTEX (binäärinen) EMPTY (moniarvoinen) FULL (moniarvoinen) Ohjelmoijan muistettava oikeellinen käyttö. Aluksi alustetaan semaforit seuraavasti: EMPTY.Arvo := puskurin koko // kertoo vapaiden paikkojen määrän FULL.Arvo := 0 // kertoo täytettyjen paikkojen määrän MUTEX.Arvo := 1 // vielä ei tietysti kellään ole lukkoa // kriittiselle alueelle... Tuottajan idea: WHILE(1) // tuotetaan loputtomiin tuota() wait(EMPTY) // esim. jos EMPTY.Arvo == 38 -> 37 // jos taas EMPTY.Arvo == 0 {eli puskurissa ei tilaa} // niin blockataan prosessi siksi kunnes tilaa // vapautuu vähintään yhdelle elementille. wait(MUTEX) // poissulku binäärisellä semaforilla; ks. edell. esim Siirrä tuotettu data puskuriin (vaikkapa megatavu tai muuta hurjaa) signal(MUTEX) signal(FULL) // esim. jos kuluttaja ei ole odottamassa FULLia // ja FULL.Arvo == 16 niin FULL.Arvo := 17 // (eli kerrotaan vaan että puskuria on nyt // täytetty lisää yhden pykälän verran) // tai jos kuluttaja on odottamassa {silloin aina // FULL.Arvo == 0} niin kuluttaja herättyy // blocked-tilasta valmiiksi lukemaan. // ... jolloin FULLin jono tyhjenee. Eli vuoronnuksesta // riippuen tuottaja voi ehtiä monta kertaa suoritukseen // ennen kuluttajaa, ja silloin se ehtii kutsua // signal(FULL) monta kertaa, ja FULL.Arvo voi olla // mitä vaan >= 0 siinä vaiheessa, kun kuluttaja // pääsee apajille. Kuluttajan idea: WHILE(1) wait(FULL) // onko luettavaa vai pitääkö odotella, // esim. FULL.Arvo == 14 -> 13 // tai esim. FULL.Arvo == 0 jolloin kuluttaja blocked // ja jonottamaan // tänne päädytään siis joko heti tai jonotuksen kautta (ehkä // vasta viikon päästä...) jahka tuottaja suorittaa signal(FULL) wait(MUTEX) // tämä taas selvä jo edellisestä esimerkistä. luetaan data puskurista (vaikkapa se megatavu) signal(MUTEX) signal(EMPTY) // Esim. jos EMPTY.Arvo == 37 ja tuottaja ei ole // odottamassa, niin EMPTY.Arvo := 38 // // Tai sitten tuottaja on jonossa // {jolloin EMPTY.Arvo == 0}, missä tapauksessa ihan // normaalisti semaforin toteutuksen mukaisesti // tuottaja pääsee blocked-tilasta ja EMPTYn jonosta // ready-tilaan ja taas valmiiksi suoritukseen. :HUOM 1: Yllä on pari esimerkkiä, mutta asian ymmärtäminen vaatii oletettavasti enemmän kuin vain esimerkkien läpiluvun. Mieti tarkoin, miten semafori toimii kussakin erityistilanteessa käyttöjärjestelmäkutsujen kohdalla, kunnes koet, että ymmärrät, miten ongelma tässä ratkeaa (ja tietenkin että mikä se ongelma lähtökohtaisesti olikaan). :HUOM 2: Tässä oli ratkaisu kahteen pulmaan: resurssin johdonmukaiseen käyttöön poissulkemisen (Mutual exclusion, "MutEx") kautta, ja tasan kahden prosessin yksisuuntaiseen puskuroituun tietovirtaan eli tuottaja-kuluttaja -tilanteeseen. Todelliset IPC-ongelmat voivat olla tällaisia, mutta ne voivat olla monimutkaisempiakin: voi olla useita "tuottajia", useita "kuluttajia", useita eri puskureita ja useita sovellukseen liittyviä toimintoja. Olet nähnyt yksinkertaisia perusperusteita, joista toivottavasti syntyy jonkinlainen pohja ymmärtää monimutkaisempia tilanteita myöhemmin, jos joskus tarvitsee. :HUOM 3: Olet nähnyt semaforiperiaatteen, joka on yksi usein käytetty tapa ratkaista tässä nähdyt perusongelmat. Ota huomioon, että on myös muita tapoja näiden sekä monimutkaisempien ongelmien ratkaisemiseen. (Jälleen, tämä on yksinkertainen ensijohdanto kuten kaikki muukin Käyttöjärjestelmät -kurssilla). Muita tapoja on ainakin viestinvälitys ("send()" ja "receive()") sekä ns. "monitorit". Mutta tähän kohtaan siis vedetään tällä kurssilla rajaus.