Tietokoneen toiminta, Syksy 2004, Harjoitus 4 (23-26.11.2004)

1. Hamming koodi. Hamming koodin avulla on mahdollista havaita ja korjata yksittäisen bitin muuttuminen. (Tehtävässä bitit numeroidaan oikealta vasemmalle kuten luentokalvoissa ja Stalligsin kirjassa.)
   1. Näytä, miten virheenkorjaava Hamming koodi havaitsee ja korjaa virheen kun 7-bittisessä datassa "011 0100" kolmas bitti vasemmalta lukien muuttuu virheelliseksi dataksi "010 0100".
      Näissä 7 bitissä on mukana sekä varsinainen data että tarkistusbitit.
   2. Entä mitä tapahtuu, jos joku tarkistusbiteistä muuttuu.
   3. Kuinka monta tarkistusbittiä tarvitaan, jos Hamming koodia käytettäessä databittejä on 8, 16, 32, 64, 128, 256, 512 tai 1024. Entä kuinka monta prosenttia bittien määrän lisäys on verrattuna databittien määrään kussakin tapauksessa.
   4. Miksi Hamming-koodin käyttö ei ole hyvä ratkaisu paikallisverkkojen tiedonsiirron turvaamiseen?
      
      
2. Välimuisti. Oletetaan, että tiedon saantiaika (1 sana) välimuistista on 2 ns ja tavallisesta muistista 10 ns. Välimuistin lohkon (rivin) koko on neljä sanaa. Oletetaan, että välimuistia käytettäessä 97% muistiviitteistä löytyy välimuistista. Voit (epärealistisesti) olettaa, että välimuistista löytyy aina tilaa uudelle lohkolle ja että tiedon siirtoaika MBR:stä rekisteriin on nolla.
   1. Jos välimuistia ei käytetä, niin kauanko keskimääräisesti kestää datan (1 sana) lukeminen rekisteriin?
   2. Jos välimuistia käytetään, niin kauanko keskimääräisesti kestää datan (1 sana) lukeminen rekisteriin?
   3. Miten prosessi tietää, löytyikö tieto välimuistista vai ei?
   4. Miten sovelluksen käyttäjä (ihminen) tietää, löytyikö tieto välimuistista vai ei?
   5. Miten käyttäjä (ohjelmoija) voi vaikuttaa välimuistin tehokkuuteen?

3. Prosessi.
   1. Mitä tapahtuu, jos Ready-to-Run jono on tyhjä?
   2. Voiko samasta ohjelmasta olla monta prosessia yhtä aikaa Ready-to-Run jonossa? Miten tai miksi ei?
   3. Kumpi kestää kauemmin, aliohjelman kutsu vai prosessin vaihto? Miksi?
   4. Kuuluuko välimuistin sisältö prosessin suoritinympäristöön vai ei? Miksi?
   5. Kuuluvatko MAR ja MBR prosessin suoritinympäristöön vai ei? Miksi
      
      
4. Oletetaan, että TTK-91 -koneelle on tehty käyttöjärjestelmä. Käyttöjärjestelmään kuuluu yhtenä osa-alueena prosessien hallinta. Oletetaan, että kellolaitekeskeytyksen takia ollaan päädytty tilanteeseen, jossa suoritusvuorossa olevaa prosessia vaihdetaan.
1. Miten ja mihin aikaisemmin suorituksessa olleen prosessin tiedot talletetaan? Mitkä tiedot täytyy ottaa talteen?
2. Miten ja mistä uuden prosessin tiedot saadaan suorittimelle? Mistä käskystä uuden prosessin suoritus alkaa? Miten suoritusvuoro vaihtuu uudelle prosessille?
3. Mikä on suorittimen tila (käyttäjä, etuoikeutettu) alkaen juuri ennen kellolaitekeskeytyshetkeä siihen asti kun uuden prosessin ensimmäisen käsky suoritetaan?
   
   
5. [2 htp] Jump table. Pitkät valintalauseet (switch-lauseet) voivat hidastaa ohjelman suoritusta huomattavasti, jos usein suoritettavassa silmukassa joka kerta valitaan yksi kerrallaan oikea case-tapaus esimerkiksi 60 eri mahdollisuuden joukosta. Tähän menee keskimäärin 30 vertailua ja kuhunkin vertailuun ainakin 2 konekäskyä!

   Jos valinta-arvot ovat kokonaislukuarvoisia, nollasta alkavia ja muodostavat (liki) yhtenäisen arvoalueen, niin usean if-then-else -vertailun asemesta voidaan käyttää hyppytaulua (jump table). Hyppytaulun avulla päästää oikeaan case-tapaukseen aina suoraan muutamalla konekäskyllä. Hyppytaulu sisältää monta hyppykäskyä (yksi per case-tapaus), joista valintamuuttujan perusteella valitaan indeksoitua osoitusmoodia käyttäen oikea hyppykäsky. Esimerkiksi, jos rekisteri R3 sisältää valinta-arvon ja hyppytaulun osoite on JTBL, niin oikeaan case-tapaukseen (siihen liittyvään hyppykäskyyn) päästään konekäskyn "JUMP JTBL(R3)" avulla.

   1. Anna (Titokoneessa suorituskelpoinen) ttk-91 esimerkki hyppytaulun käytöstä, kun case-tapauksia on 10.
   2. Miten em. valintalause toteutetaan, jos hyppytaulussa onkin hyppykäskyjen asemesta ainoastaan case-tapausten osoitteet? Anna toteutus samalle esimerkille kuin kohdassa (a).
   3. Milloin toteutustapa (a) on parempi kuin (b)? Miksi?
   4. Milloin toteutustapa (b) on parempi kuin (a)? Miksi?
   5. Jos kukin case-tapaus vaatii 10 konekäskyä ja case-tapauksia on 60, niin kuinka paljon (%) hyppytaulun käyttö nopettaa valintalauseen suoritusta (verrattuna usean peräkkäisen vertailun toteutukseen)? Eroavatko em. toteutustavat (kohdat a ja b) tässä suhteessa? Käytä nopeusmittana suoritettujen käskyjen lukumäärää.