Käyttöjärjestelmät, välikoe 1, 26.2.2014                      Other side in English

Kirjoita jokaiseen vastauspaperiisi kurssin nimi, pvm, oma nimi, nimikirjoitus ja opiskelijanumero.
Kuhunkin tehtävään riittää 1-2 sivun vastaus.

HUOM: Palauta jokainen tehtävä omalla konseptiarkillaan oikeaan pinoon!

1. [6 p] Säikeet
1. [3 p] Miten ytimen tason säikeet (KLT) ja käyttäjätason säikeet (ULT) eroavat toisistaan?
   Mitä etuja on KLT:llä verrattuna ULT:hin? Mitä haittoja?
2. [2 p] Anna esimerkki tilanteesta, jossa ULT T:n suoritustilana voi olla "suorituksessa", mutta säikeen konekäskyjä ei silti ole suorituksessa suorittimella tällä hetkellä. Milloin säie T pääsee oikeasti suoritukseen?
3. [1 p] Mikä ongelma liittyy ULT:den blokkautuvaan I/O:hon ja monisäikeisten sovellusten suoritusnopeuteen? Miksi sama ongelma ei liity KLT:iin?


2. [6 p] Lukkiutuminen
1. [2 p] Mikä on lukkiutumisongelma? Anna konkreettinen pseudokoodinen esimerkki Aterioivien filosofien ongelman avulla.
2. [3 p] Millä tavoin lukkiutuminen voidaa ennakolta estää (prevent)? Mitä etua lukkiutumisen estämisellä on verrattuna saman ongelman ratkaisuun lukkiutumisen välttämisellä (esim. Pankkiirin algoritmilla) tai lukkiutumisen havaitsemisella (esim. DDA:lla)?
3. [1 p] Anna konkreettinen esimerkki lukkiutumisen estämisestä liittyen Aterioivien filosofien ongelmaan. Perustele, miksi ratkaisusi varmasti estää lukkiutumiset?
   


3. [6 p] Editori, näppäimistön ajuri ja semaforit. Tekstieditori TE lukee merkkipuskurista B merkkejä yksi merkki kerrallaan ja tekee sen vaatimat muutokset editoitavaan tiedostoon. Näppäimistön laiteajuri DD lukee näppäimistön painallukset (yksi kerrallaan) ja kirjoittaa niitä vastaavat merkit merkkipuskuriin B.
1. [2 p] Kuvaile TE:n ja DD:n välinen synkronointi- ja kommunikointiongelma. Kuka odottaa ketä ja milloin? Miten tieto siirtyy?
2. [4 p] Anna tämän synkronointi- ja kommunikointiongelman ratkaisu semaforien ja yhteisessä muistissa olevan puskurin (B) avulla. Esitä ratkaisu TE:n ja DD:n pseudokoodien avulla. Määrittele selkeästi kaikki käyttämäsi semaforit ja muut synkronointiin tarvittavat tietorakenteet alkuarvoineen. Selitä, miksi ratkaisusi on oikein.


4. [6 p] Juoksurata ja monitori. Juoksurata on 400m pitkä. Ann ja hänen ystävänsä Bill ja Charlie tulevat sinne usein ja juoksevat 4000m. Ann on sosiaalinen ja haluaa odottaa ystäviään eri tavoin eri päivinä. Ratkaise syntyvä synkronointiongelma monitorilla Synch, jossa on metodi jokaiselle juoksijalle. Anna monitorin Synch pseudokoodi. Määrittele monitorin ehtomuuttujat ja muut tietorakenteet alkuarvoineen. Käytä Signal and wait (Hoare) signalointisemantiikkaa. Tee ratkaisustasi mahdollisimman yksinkertainen. Juoksijoiden pseudokoodi on seuraavanlainen:

              Ann:                Bill:               Charlie:
              for (i=1 to 10)     for (i=1 to 10)     for (i=1 to 10)
                 <run lap>           <run lap>           <run lap>
                 Synch.AnnLap        Synch.BillLap       Synch.CharlieLap

   1. [3 p] Ann odottaa joka kierroksen jälkeen kunnes sekä Bill että Charlie ovat saavuttaneet hänet (samalla kierroksella). Jos Bill ja Charlie ovat molemmat jo hänen edellään, niin Ann ei pysähdy odottamaan. Bill ja Charlie eivät pysähdy odottamaan ketään.
   2. [3 p] Ann odottaa joka kierroksen jälkeen kunnes joko Bill tai Charlie (tai molemmat) on saavuttanut hänet (samalla kierroksella). Jos Bill tai Charlie on jo hänen edellään, niin Ann ei pysähdy odottamaan. Bill ja Charlie eivät pysähdy odottamaan ketään.