ITKA203 Käyttöjärjestelmät, luento 8/14, Ti 14.6.2011 ===================================================== Info: - Materiaalissa luvut 1-4 suurin piirtein valmiina (enää kauniita kuvia vaille) - Alan laittaa Demo 1:n merkintöjä Korppiin huomiseen mennessä; tällä hetkellä 86 palautusta. Oletan että loput 115 opiskelijaa aikovat tehdä demon tällä viikolla. Nyt olisi hyviä sadepäiviä opiskeluun käytettäväksi! - Demo 3 odotettavissa tänään tai huomenna: odotettavissa välipala shell-skriptien muodossa, bonuspiste tenttiin ja pääasiallinen materiaali skripteihin, joista tenttiin tulee 15-25% kokonaispistemäärästä! Eli kannattaa katsella läpi ja tulla kyselemään, jos ei muuten lähde. - Demo 4 muovautumassa; tavoitteena on melko kevyt eli vähätöinen jatko-osa demolle 2. Eli demon 2 asiaan kannattaa paneutua. Tämän päivän toteuma: --------------------- Terminologiaa: - Prosessien välinen kommunikointi, Inter-process communication, IPC. - Kun prosessi on blocked-tilassa, voimme sanoa myös että se on nukkumassa. Käyttöjärjestelmäkutsu sleep() siirtää prosessin tilaan, jossa se odottaa signaalia. Prosessien kommunikointia: signaalit (jatkoa viime viikosta): - katsottiin vielä viime viikon luennon esimerkkiohjelmaa - todettiin, että käyttöjärjestelmän täytyy ilmeisesti pitää yllä prosessikohtaista viestijonoa ja huolehtia, että viestejä saaneet prosessit herätetään käsittelemään saamansa signaalit. (palautettaessa prosessia suoritukseen, siirretään käskyosoitin rekisteröidyn viestinkäsittelijän alkuun ikään kuin olisi tehty aliohjelmakutsu, josta palataan prosessin aiempaan, keskeytyneeseen tilaan. - Signaalin "sisältö" on yksinkertainen lukuarvo, joka kuvaa esim. lopetus- ja odottelupyyntöä tai odottamattomasti syntynyttä virhetilannetta. On myös "käyttäjän määrittelemiä" signaaleja, joilla prosessia voidaan tökätä, ja joilla voi olla ohjelman tekijän määrittelemä merkitys. Prosessien kommunikointia: viestit - Käyttöjärjestelmän tietorakenne: viestijono. - Käyttöjärjestelmäkutsuja: * msgget() pyytää käyttöjärjestelmää valmistelemaan viestijonon * msgsnd() lähettää viestin jonoon * msgrcv() odottaa viestiä saapuvaksi jonosta Prosessien kommunikointia: jaettu muistialue - Käyttöjärjestelmää voi pyytää kartoittamaan fyysisen muistialueen kahden tai useamman prosessin virtuaalimuistin osaksi. Näin muistialueesta tulee prosessien jakama resurssi, johon ne molemmat voivat kirjoittaa ja josta ne voivat lukea. Synkronointi, miksi sitä tarvitaan? Esimerkki poissulkuongelmasta. - Havaitaan että jaetun resurssin käyttöön liittyy helposti ongelmia, jotka pitää ratkaista. Esimerkki jaetun viestikanavan (esimerkin tapauksessa standardiulostulo säikeiden jakamana) synkronoinnista. Häiritsevien yhdenaikaisten tulostusten poissulkeminen on ongelma, jota ohjelma ei voi ratkaista muuten kuin pyytämällä palvelua käyttöjärjestelmältä. (Samalla tämä oli olevinaan alustava, teennäinen ja hassu esimerkki "deadlockista". Otetaan huomenna lyhyesti joku parempi ja realistisempi.) Terminologiaa: - Jaettu resurssi == osa laitteistoa (prosessori, muisti, I/O yhteys, tiedosto, ...) jota useampi prosessi tai säie käyttää ´ yhtäaikaa - Kriittinen alue == osa ohjelmakoodia, joka voi aiheuttaa synkronointiongelman Synkronointiongelmien ratkaisu semaforin avulla: - Mikä on semafori: Simppeli tietorakenne, jossa on kokonaisluku sekä jono prosesseja. - Semaforin käyttö ohjelmoijan näkökulmasta: esimerkkiohjelmassa sem_wait() ja sem_post(), koska siinä käytetään itse asiassa POSIX-säikeitä ja niiden POSIX-semaforia, joiden määrittelyyn tällaiset nimet kuuluvat. (Esimerkkiohjelmassa ei tosiaan käytetä suoraan linuxin semaforia, vaan laajennosta nimeltä NPTL; asiasisältöön tämä ei paljonkaan vaikuta, semafori kuin semafori toimii kyllä samoin (lisätietoja NPTL:stä niille keitä kiinnostaa: http://en.wikipedia.org/wiki/Native_POSIX_Thread_Library ) - kuitenkin siis sem_wait() ja sem_post() ovat POSIX-säiekirjaston ``pthread`` tarjoamia palveluita, joka on tässä tapauksessa vielä kerroksena Linuxin ytimen päällä) Kirjallisuudessa vastaavat käyttöjärjestelmäkutsut on nimetty usein wait() ja signal(), joita tämän tekstin loppuosassa käytetään. Miten semafori ratkaisee poissulkuongelman: - Kriittinen alue kehystetään wait(MUTEX) ja signal(MUTEX) käyttöjärjestelmäkutsuilla, missä semaforin nimi "MUTEX" nyt vain viittaa semaforin käyttötarkoitukseen eli kriittisen alueen suorituksen keskinäiseen poissulkemiseen (mutual exclusion). Miten semaforilla ratkaistaan tuottaja-kuluttaja -ongelma: - Seuraavassa vuodelta 2007 periytyvässä selvityksessä käydään läpi, mikä ylipäätään on "Tuottaja-kuluttaja -ongelma" ja kuinka se voidaan ratkaista käyttämällä semaforeja. Käytetään jonotuspuolelle nimeä wait() ja vapautuspuolelle signal() kuten tyypillistä on. 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, tai keskinäinen nopeus voi vaihdella. - Tällä tavoin saavutetaan mm. modulaarisuutta ohjelmien tekemiseen, jakeluun ja suorittamiseen. - Puolirealistinen esimerkki voisi olla että yksi prosessi/säie tuottaa kuvasarjaa fysiikkasimuloinnin perusteella (tuottamisen nopeus voi vaihdella esimerkiksi animaatiossa näkyvien esineiden määrän perusteella) ja toinen prosessi/säie pakkaa kuvat MP4-videoksi (pakkauksen nopeus voi vaihdella kuhunkin kuvaan sattuvan sisällön perusteella, esim. yksivärinen tai paikallaan pysyvä maisema menee nopeammin kuin erityisen liikkuva "kohtaus"; joka tapauksessa tuottaminen ja kuluttaminen tapahtuvat tässä oletettavasti keskimäärin eri nopeudella). - 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/-säie voi keskeytyä kun elementin kirjoittaminen on puolivalmis, ja myös kuluttaja voi keskeytyä kesken elementin lukemisen. Mitä täytyy pystyä tekemään: - Puskurin täyttyessä pitää pystyä odottamaan, että tilaa vapautuu. Muutoin ei ole mahdollista kirjoittaa uutta tuotosta mihinkään. Tuottajan pitää pystyä odottamaan. - Puskurin ollessa kokonaan käsitelty, pitää pystyä odottamaan että uutta dataa ilmaantuu. Muutoin ei ole mitään kulutettavaa. Kuluttajan 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. Puskurissa olevia tietoalkioita voidaan symboloida vaikkapa kirjaimilla:: |ABCDEFghijklmnopqrstuvwxyz| ^tuottaja tuottaa muistipaikkaan tALKU + ti ^kuluttaja lukee muistipaikasta kALKU + ki Virtuaalimuistin hienous on että sama fyysinen muistipaikka voi näkyä kahdelle eri prosessille (kommunikointi jaetun muistialueen välityksellä):: tALKU != kALKU mutta tALKU[i] == kALKU[i]. 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. Semaforin rakenne ================= Semafori on käyttöjärjestelmän käsittelemä rakenne, jonka avulla voidaan hallita vuorontamista eli sitä, milloin prosessit pääsevät suoritukseen prosessorilaitteelle. 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 sem_post()-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 todelliten ohjelmien tekemisessä 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ä. käsitellään tietoalkio puskurista 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 tai säikeen 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", jotka jätetään tässä maininnan tasolle.