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

1. [8 p] Prosessit ja säikeet.
1. [2 p] Miten prosessit ja säikeet suhtautuvat toisiinsa? Mitä niillä on yhteistä? Miten ne eroavat toisistaan?
2. [2 p] Mitä ovat ytimen tason säikeet (KLT) ja käyttäjätason säikeet (ULT)? Anna konkreettiset esimerkit.
3. [1 p] Milloin olisi parempi käyttää ULT:tä KLT:den asemesta? Anna konkreettinen esimerkki.
4. [1 p] Milloin olisi parempi käyttää KLT:tä ULT:den asemesta? Anna konkreettinen esimerkki.
5. [1 p] Onko mahdollista, että prosessi on odotustilassa, mutta siihen kuuluva säie suoritustilassa? Selitä.
6. [1 p] Onko mahdollista, että prosessi on suoritustilassa, mutta siihen kuuluva säie odotustilassa? Selitä.



2. [8 p] Yksisuuntainen silta semaforeilla. Kahden kylän A ja B välissä olevan joen yli kulkee niin kapea silta, että autot voivat ajaa sitä pitkin vain yhteen suuntaan (itään tai länteen) kerrallaan. Kun sillalla kulkee autoja A:sta B:hen, niin B:stä A:han haluavien täytyy odottaa. Auto-prosessit kutsuvat rutiinia enter_bridge_direction ennen sillalle ajoa ja rutiinia exit_bridge_direction sillalta poistuessaan.

     Process auto[i = 1 to N] {
       .....
       enter_bridge_west()
          drive over the bridge westbound
       exit_bridge_west()
       ......
       enter_bridge_east()
          drive over the bridge eastbound
       exit_bridge_east()
       ......
       }

1. [6 p] Kirjoita tämän synkronointiongelman semaforeilla ratkaiseva koodi. Siinä on neljä kutsuttavaa rutiinia autojen synkronointia varten: enter_bridge_west, exit_bridge_west, enter_bridge_east, exit_bridge_east. Muista määritellä kaikki semaforit ja muut muuttujat alkuarvoineen.
2. [2 p] Muokkaa (a-kohdan) ratkaisuasi sillä tavoin, että länteen päin menevillä autoilla on prioriteetti. Kun ensimmäinen länteen päin menevä auto saapuu sillalle, sen jälkeen tulevat itään päin menevät autot jäävät odottamaan kunnes kaikki länteen päin menevät ovat ylittäneet sillan.
    
3. [8 p] Lukkiutuminen. Meillä on kolme säiettä (A, B ja C) ja neljä resurssityyppiä (r, s, t ja u). Kutakin resurssia voi käyttää kerrallaan vain yksi säie. Resursseja r, s ja t on yksi kappale ja resurssia u kaksi kappaletta. Säikeet eivät voi "varastaa" resursseja muilta säikeiltä ja ne varaavat käyttämänsä resurssit jossain järjestyksessä, yhden kappaleen kutakin. Säie A käyttää resursseja r ja s, säie B käyttää resursseja s, t ja u, ja säie C käyttää resursseja r, t ja u.
1. [2 p] Anna lukkiutumiseen johtava resurssien varaamisskenaario. Perustele, miksi lukkiutumistilanne vallitsee skenaariosi lopputilanteessa.
2. [3 p] Miten Dijkstran algoritmi pääpiirteittäin toimii ja kuinka se havaitsee lukkiutumisen kohdan (a) skenaariossasi? Mitä sitten tehdään, kun lukkiutuma on havaittu?
3. [3 p] Pankkiirin algoritmia ei tässä järjestelmässä voi käyttää, mutta lukkiutumisen voi silti estää ennakolta, kun siihen osataan varautua. Millä periaatteella lukkiutuminen voidaan tässä tapauksessa ennakolta estää ja mitä muutoksia resurssien varauskoodiin tulisi tämän periaatteen mukaisesti tehdä? Selitä, miksi lukkiutuminen on nyt teoreettisesti mahdotonta. Selitä, miten lukkiutumisen estäminen toimii käytännössä kohdan (a) skenaariossasi.