Tietokoneen toiminta - Kevät 2004

Harjoitus 4, viikko 17, 20.4.-23.4.

Varaudu esittämään kaikki koksiin liittyvät tehtävät mikrotietokoneella harjoitustilaisuudessa. Tallenna siksi ratkaisusi joko levykkeelle tai fs-verkkolevylle. Ota mukaan myös tuloste ratkaisuistasi.

• Tehtävä 1: Hamming koodi
  Ennakkoon palautettava tehtävä ! Tehtävästä saa yhden koepistettä vastaavan pisteen.

  Hamming koodin avulla on mahdollista havaita ja korjata yksittäisen bitin muuttuminen. (Tässä tehtävässä bitit numeroidaan oikealta vasemmalle kuten luentomonisteessa ja Stallingsin kirjassa.)

  1. Näytä, miten tallennat Hamming koodausta käyttäen 4 databittiä 1001. Kuinka monta tarkistusbittiä tarvitset? Kuinka voit tarkistaa, että bitit eivät ole muuttuneet?
  2. Onko Hamming koodatussa bittijonossa 100 1101 (4 databittiä ja 3 tarkistusbittiä, numerointi oikealta) virheitä, jos niin millaisia ja miten ne korjataan?
  3. Entä bittijonossa 100 1100? Tämähän on vain yhdellä bitillä muuttunut edellisestä kohdasta. Millainen korjaus tähän tulee?

  Laadi selvityksesi tavallisena tekstitiedostona, jossa ei ole mitään erityisiä muotoiluja. Älä siis turhaan käytä tekstinkäsittelyohjelman muotoiluja.

  Palauta laatimasi tekstitiedosto www-sivun http://db.cs.helsinki.fi/~tuohinie/tito/ kautta.

  Palautus pitää tehdä viimeistään 24 tuntia ennen ryhmän alkua. Myöhemmin palautus ei ole mahdollista eikä myöhästyneitä palautusyrityksiä oteta huomioon.

  ---

   

• Tehtävä 2: Hamming koodi pidemmille jonoille
  1. Kuinka muuttumattomuuden tarkistus tapahtuu 16-bittiselle datalle 01010011 01010101? Tässä ryhmässä ei siis vielä ole mukana tarkistusbittejä.
  2. Montako lisäkanavaa (johdinta, bittiä) tarvitaan 32-bittisen dataväylän turvaamiseksi virheenkorjaavaa Hamming-koodia käyttäen?
     (Haluamme siis siirtää kerralla 32 bittiä todellista dataa tarkistusbittien lisäksi.)
  3. Miksi Hamming-koodin käyttö ei ole hyvä ratkaisu paikallisverkkojen tiedonsiirron turvaamiseen?

   

• Tehtävä 3: 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. Voiko prosessi havaita, löytyikö tieto välimuistista vai ei? Miksi?
  4. Tarvitseeko sovelluksen käyttäjän (ihminen) tietää, löytyikö tieto välimuistista vai ei? Miksi?

   

• Tehtävä 4: Prosessi.
  1. Mitä tapahtuu, jos Ready-to-Run jono on tyhjä? Milloin näin voi olla?
  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?

   

• Tehtävä 5: Prosessin vaihto

  Oletetaan, että TTK-91 -koneelle on juuri laadittu käyttöjärjestelmä, joka sallii usean samanaikaisen prosessin suorittamisen koneella. Käyttöjärjestelmään kuuluu yhtenä osa-alueena prosessien hallinta. Oletetaan, että kellolaitekeskeytyksen takia ollaan päädytty tilanteeseen, jossa suoritusvuorossa olevaa prosessia vaihdetaan. Käyttöjärjestelmän suunnittelijan ja toteuttajan on täytynyt ottaa kantaa mm. seuraaviin kysymyksiin. Millaisiin ratkaisuihin hän on todennäköisesti päätynyt TTK-91 -koneessa?

  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?

   

• Tehtävä 6: Taulukkoparametri

  Määrittele kuusialkioinen taulukko Taulu[0..5] pääohjelmatasolla. Toteuta sitten seuraavat tehtävät TTK-91 koneen symbolisella konekielellä ja suorita ohjelmasi Koksissa.

  1. Tee aliohjelma Init(Arr, Dim, Val), joka alustaa parametrina annetun taulukon Arr siten, että kunkin alkion Arr[i] arvoksi tulee luku Val+i+1000. Parametri Arr on alustettava taulukko, Dim on k.o. taulukon alkioiden lukumäärä ja Val on kokonaisluku. Arr on viiteparametri. Dim ja Val ovat arvoparametreja.
     (Huomaa, että viiteparametrina annetun taulukon käyttö on vähän vaikeata, koska et voi käyttää tavallista indeksoitua osoitusmuotoa taulukon alkioiden yhteydessä. Taulukon välittäminen arvoparametrina ei kuitenkaan ole mahdollista, koska aliohjelman alustuksen halutaan näkyvän pääohjelmalle.)
  2. Alusta taulukko Taulu aliohjelmaa Init käyttäen (Val = 100).
  3. Tulosta taulukon Taulu alkion Taulu[4] arvo ja osoite.
  Noudata luennolla ja harjoituksissa esitettyjen suositusten mukaista aliohjelmien (funktioiden) toteutustapaa ja kutsumekanismia.

  ---

  Tiina.Niklander@cs.helsinki.fi