UL/FRI/UNI-RI/ARS1/Izpiti/Ustni

Iz E-študij, proste zakladnice študentskega znanja

< UL | FRI | UNI-RI | ARS1 | Izpiti
Skoči na: navigacija, iskanje

PREPIŠI/UREDI IZ UL/FRI/UNI-RI/ARS1/Izpiti/Ustni2 in označi za IZBRIS

Vsebina

Von Neumannov računalniški model

Stroj mora izpolnjevati naslednje pogoje:

  • sestavljajo ga trije osnovni deli: CPE, glavni pomnilnik in V/I sistem
  • ima program, shranjen v glavnem pomnilniku, ki vodi delovanje stroja
  • CPE jemlje ukaze iz glavnega pomnilnika, kamor kaže PC – strojni ukazi (FETCH) in jih izvršuje enega za drugim in povečuje PC – register, ki vsebuje naslov naslednjega ukaza (EXECUTE)

CPE – skoraj vse dogajanje se odvija pod njeno kontrolo. Razdelimo jo lahko na kontrolno enoto in podatkovno enoto (aritmetično logična + registri). Registri so programsko dostopni (niso nujno potrebni a omogočajo hitrejše delovanje) in programsko nedostopni(jih ima vsaka CPE).

Glavni pomnilnik – v njem so ukazi in operandi, ki jih uporablja CPE. Sestavljen je iz več pomnilniških besed, katerih vsaka ima enoličen naslov. Pri tem modelu računalnik ne loči med ukazi in operandi.

V/I sistem – namenjen je prenosu informacij v/iz zunanjega sveta. Sestavljen je iz V/I naprav. Nekatere izmed njih služijo tudi kot pomožni pomnilnik. Fizično največji del računalnika.

Delovanje računalnika popolnoma določajo ukazi, v dveh korakih: fetch in execute. PC – PC +1. Do izjeme pride le pri prekinitvah, pasteh in skokih. PC – PC + n.

Obstajati mora mehanizem, ki na začetku ukaze naloži v glavni pomnilnik – bootstrap loader.

Von Neumannov model je ukazno pretokovni, obstajajo pa še podatkovno pretokovni modeli.

DMA krmilnik, V/I procesorji

Vsaka V/I naprava je priključena preko krmilnika, ki omogoča prenos iz/v njo. Videti je kot določeno število registrov, s tem da branje ali pisanje v njih sproži določeno akcijo v napravi.

DMA (Direct Memmory Access) označuje neposredno komunikacijo med glavnim pomnilnikom in V/I sistemom (nasprotje od programskega V/I, ko z V/I napravo komunicira le CPE – računalnik lahko uporablja oba). Prenos je realiziran s posebno enoto DMA krmilnikom, ki je sposoben sam komunicirati z glavnim pomnilnikom. Posebna izvedba te vrste prenosa je z vhodno/izhodnimi procesorji, ki pa je še veliko dražja. Služijo tudi pri brisanju ali branju v registre V/I naprav, ki so v posebnem naslovnem prostoru. CPE sporoča svoje zahteve V/I procesorjem, ostalo pa opravijo sami. To rešitev uporabljajo samo večji računalniki.

Pomnilniško preslikan V/I

Memory Mapped I/O – registri krmilnikov (glej 2) so kar v pomnilniškem naslovnem prostoru in so iz CPE videti kot pomnilniške besede. Za branje/pisanje lahko uporabljamo kar navadne ukaze za dostop do pomnilnika, tako da posebni V/I ukazi niso potrebni.

Lokalnost pomnilniških dostopov

Lokalnost pomnilniških dostopov opisuje pojav, da programi večkrat uporabijo iste ukaze in operande, ki so v pomnilniku blizu trenutno uporabljenim. Omogoča uporabnost predpomnilnikov v pomnilniški hierarhiji. Povzroča jo način pisanja programov in že samo delovanje Von Neumannovih računalnikov (ukazi si zaporedno sledijo). Razdelimo jo lahko na:

  • prostorsko lokalnost – po pojavu naslova bo njegov naslednji po lokaciji v pomnilniku blizu prejšnjega … če ni skoka se ukazi jemljejo zaporedno, v programih nastopajo strukture kot so polja, program je razdeljen na podprograme in procedure, ki so večinoma kratke.
  • časovna lokalnost – program ob času t tvori naslove, ki jih je tvoril malo pred t in ki jih bo nekoliko po t - zanke (isto zaporedje ukazov se ponovi velikokrat) in začasne spremenljivke, zaradi katerih se naslovi določenih operandov pojavljajo večkrat.

Lokalnost lahko razložimo še s pojmom delovne množice (Working Set) – V(t,T), ki je veliko manjša od N (število dostopov) v istem intervalu. Vsebina zaporedno si sledečih množic se spreminja počasi – prekrivanje.

Amdahlov zakon

Pove nam, za koliko lahko pohitrimo računalnik s paraleliziranjem določenih delov programa. Če za faktor N pohitrimo delovanje pri vseh operacijah, razen pri f-tem deležu, je delovanje N-krat hitrejše (1-f)-ti del časa, torej je povečanje hitrosti računalnika enaka:

Če torej hočemo doseči pohitritev, je boljše da imamo en hiter procesor, kot pa več počasnejših, razen seveda v posebnih primerih, ko je stopnja paralelnosti (1-f) visoka.


Skupaj s sodelavcem R.P. Case-om, je Amdahl razvil še dve t.i. Case-Amdahlovi pravili:

  • velikost glavnega pomnilnika v bajtih mora biti najmanj enaka številu ukazov, ki jih v sekundi izvede CPE
  • zmogljivost V/I sistema v bitih na sekundo mora biti najmanj enaka številu ukazov, ki jih v sekundi izvede CPE

Če računalnik ustreza tem pravilom, rečemo da je uravnotežen (izkoriščen).

Numerični operandi v fiksni vejici

Vejica je fiksna. Številke na levi strani predstavljajo celo število, na desni pa ulomek. Vsaka številka ima svojo težo glede na pozicijo – pozicijska notacija. Uporablja se baza r=2. Najenostavneje je, da damo vejico čisto na desno in imamo samo cela števila. V glavnem se uporablja dvojiška predstavitev (desetiška se uporablja izključno za poslovne obdelave – banke).

Predstavitev predznačenih števil:

  • predznak in velikost: najbolj levi bit predstavlja predznak 0 pozitivno in 1 negativno. Pri seštevanju in odštevanju je treba predznak obravnavati drugače kot ostale bite. Imamo dve ničli za kateri velja +0>-0. Dobro za množenje in deljenje. Vrednost tako predstavljenega števila je
  • predstavitev z odmikom: k številu se najprej prišteje konstanto, da se zagotovi, da so vsa števila pozitivna. Če so vsi biti 0 je to najbolj negativno število, odmik je treba zmeraj popravljati (pri seštevanju odštevati in pri odštevanju prištevati.
  • eniški komplement: pozitivna števila so predstavljena enako kot pri "predznak in velikost". Predstavitev negativnega števila dobimo tako, da najprej zapišemo pozitivnega, zatem pa vse bite invertiramo. Invertiranje bitov je ekvivalentno odštevanju števila od 2n − 1. Prednost je v tem, da vse bite obravnavamo enako. Pri prenosu iz n-1. mesta moramo k rezultatu prišteti 1. Imamo dve ničli.
  • dvojiški komplement: kot eniški, le da pri invertiranju prištejemo ena. Pri prenosu ni treba prištevati enke. Imamo samo eno ničlo. Najbolj pogosto uporabljen.

Glavna prednost komplementov: pri seštevanju in odštevanju bit za predznak upoštevamo povsem enako kot ostale bite. Pri dvojiškem kompl. pa poleg tega nimamo dveh predstavitev za ničlo, in ker logiki ni potrebno testirati predznaka (ker je seštevanje ekvivalentno odštevanju dvojiško komplementiranega števila) je implementacija lažja in cenejša.

Pri vsaki predstavitvi števil obstaja največje in najmanjše še predstavljivo število.

Do prenosa pride pri prekoračitvi obsega nepredznačenih števil: x < 0 ali x > 2n − 1

Do preliva pride pri prekoračitvi obsega predznačenih števil: x < − 2n − 1 ali x > 2n − 1 − 1

Numerični operandi v plavajoči vejici

Predstavimo lahko tudi ulomke. Število razbijemo na tri dele: mantiso m, eksponent e in bazo r. Eksponent pove na katerem mestu je decimalna vejica, ki plava. Ta števila so predstavljena s fiksno vejico. Zaradi praktičnih razlogov za bazo uporabljamo samo 2 ali 10. Ker je baza konstantna lahko rečemo, da je število v plavajoči vejici predstavljeno s parom (m,e).

Zaželeno je, da so vsa števila predstavljena na enolično definiran način. Takim številom rečemo normalizirana števila. Število je v plavajoči vejici normalizirano takrat, ko je najbolj leva številka mantise različna od 0. Prvi bit normalizirane mantise je torej vedno enak 1 in se imenuje normalni bit. Ker je vedno 1, ga zato ni potrebno predstavljati, ampak ga vseeno upoštevamo pri računanju. Temu pravimo implicitna predstavitev normalnega bita.

Številom, ki niso normalizirana pravimo denormalizirana. V normalizirana jih lahko pretvorimo s premikanjem mantise in zmanjševanjem eksponenta. To pa lahko počnemo dokler eksponent ne doseže najmanjše možne vrednosti. Tu lahko pride do podliva:

Podliv: števila, ki so premajhna za predstavitev, tudi če jih denormaliziramo.

Preliv: glej 6.

Ponavadi sta dva formata za predstavitev: enojna in dvojna natančnost. Prva je ponavadi 32-bitna, druga pa 64.

Standard IEEE 754

  • baza = 2
  • eksponent je predstavljen z odmikom … če je 0 je število najbližje 0
  • mantisa je predstavljena s predznakom in velikostjo
  • uporablja implicitno predstavitev normalnega bita
  • več formatov: 32 bitni(enojna natančnost), 64 bitni (dvojna) in 80 bitni (samo za interno računanje)
  • obstaja predstavitev za ∞, -∞ in NaN
  • dovoljeno je računanje z denormaliziranimi števili (ena vrednost eksponenta je rezervirana)


IEEE standard določa predstavitev petih vrst števil:

1. Normalizirana števila - večina števil, eksponent E nima vseh bitov enakih 0 ali enakih 1

2. Denormalizirana števila - eksponent E ima vse bite 0, mantisa m je različna od 0

3. Ničli (+0 in -0) - eksponent E in mantisa m imata vse bite 0

4. Neskončnosti (+∞ in -∞) - eksponent E ima vse bite 1, mantisa pa vse 0

5. Neveljavna števila (NaN) - eksponent ima vse bite 1, mantisa pa je različna od 0


Zaokroževanje

Zaokrožujemo k matematično točni vrednosti k najbližjemu še predstavljivemu številu - to se nanaša na velikost mantise - 23 bitov pri 32 bitnem IEEE 754. Če smo ravno med dvema številoma, torej je oddaljenost do obeh enaka, zaokrožimo k sodemu.


Realizacija: Za takšno zaokroževanje zadošča če mantiso podaljšamo za dodatne 3 bite: varovalni (guard), zaokroževalni (round) in zaradi pravila zaokroževanja k sodemu številu še lepljivi (sticky) bit. Ta se postavi na 1 takoj ko pri pomikanju mantise pade ven od 0 različna številka. Po končanem računanju se ti biti odvržejo.

Zaradi implicitne predpostavke, da je na voljo mat. točna vrednost sta definirana še 2 razširjena formata: razširjena enojna ter razširjena dvojna natančnost

Zaokroževalni Varovalni Lepljivi 

Število +0000001001000110100 odvisno 101111011111

Enojna, dvojna natančnost

Enojna natančnost:

  • predznak S
  • 8-bitni eksponent E z odmikom 127
  • 23-bitna mantisa m
  • vrednost: ( − 1)S(1,m)2E − 127

Dvojna natančnost:

  • predznak S
  • 11 bitni eksponent E z odmikom 1023
  • 52-bitna mantisa m
  • vrednost: ( − 1)S(1,m)2E − 1023

Načini shranjevanja operandov v CPE

Ni nujno, da obstaja možnost shranjevanja operandov v CPE. Kljub temu imajo vsi današnji računalniki v CPE majhen pomnilnik, v katerega je možno shraniti enega ali več operandov – programsko dostopni registri. Omogoča večjo hitrost in krajše ukaze. Razlikujemo tri možnosti za shranjevanje operandov v CPE:

  • Akumulator: imamo en sam (ali mogoče dva) register, v katerega lahko shranimo en operand. Preprostost, staro. V ukazih ga ni treba eksplicitno navajati. Vmesne rezultate je treba prenašati nazaj v pomnilnik. Posledica: počasnost, promet med CPE in gl. pom.
  • Sklad: pomnilnik je podoben akumulatorskemu, saj je pri obeh direktno dostopen samo en operand, a vendar je promet med CPE in gl.pom manjši. Sklad je ponavadi narejen tako, da se nadaljuje v glavnem pomnilniku. Take računalnike imenujemo skladovne. So brezoperandni in imajo pomnilnik v CPE realiziran v obliki sklada. Njihova prednost je v računanju matematičnih izrazov v postfiksni obliki, slabost pa v tem, da je takih izrazov malo – več je prireditev. Primer: računalniki firme Burroughs.
  • Množica registrov: število je od 8 do 100. Zelo splošna možnost. Ločimo dve rešitvi, glede na svobodo pri uporabi registrov: vsi so ekvivalentni – splošnonamenski registri. Lahko jih pa razdelimo v dve skupini: ena za aritmetično logične operande, ena pa za računanje z naslovi. Druga rešitev je bolj toga, vendar omogoča prihranke pri gradnji CPE.

Ta rešitev je pomembna za cevovodne računalnike (registri morajo shranjevati vmesne rezultate).

Število eksplicitnih operandov

Manjše število pomeni krajše ukaze in tudi manjšo moč ukazov. Večje število zahteva bolj zapleteno CPE. Na število eksplicitnih operandov vpliva tudi tip operacij, ki jih bo računalnik opravljal. Računalnike z m eksplicitnimi ukazi imenujemo m-operandni ali m-naslovni, kar ne pomeni, da imajo vsi ukazi m operandov, najpomembnejši ukazi (ALE) imajo m operandov. Imamo pet skupin:

  • 3+1 - operandni (glej 12)
  • 3 - operandni: po letu 1980 praktično vsi, ki imajo operande v registrih. OP3 <– OP2 operacija OP1. Imenujemo jih tudi load/store računalniki., saj imajo operande ponavadi le v registrih.
  • 2 - operandni: OP2 <– OP1 operacija OP2, preprostost. OP1 in OP2 sta lahko v enem izmed registrov ali v pomnilniku. 1 ½ naslovni računalniki – en operand v registru en v pomnilniku. Do 1980 najpogostejša vrsta.
  • 1 - operandni: AC <– AC op. OP1. Računalniki, ki imajo v CPE en ali dva akumulatorja. Taki so bili računalniki v 70' letih, danes pa so zelo razširjeni v izdelkih za množično uporabo
  • brez-operandni (skladovni) računalniki. Pomnilnik v CPE imajo narejen v obliki sklada. SKLAD(vrh) <– SKLAD(vrh) operacija SKLAD(vrh-1). Operandov ni treba eksplicitno navajati.

3+1 - operandni računalnik

Takih računalnikov danes ni več. EDVAC je en primer. Imajo 4 operande. Oznaka +1 pomeni, da je poleg eksplicitnih operandov v ukazu kot operand tudi naslov naslednjega ukaza. Delovanje lahko simbolično opišemo kot:

OP3 OP2 operacija OP1

PC OP4

Ti računalniki niso imeli pomnilnika za shranjevanje operandov v CPE. Četrti operand določa lokacijo naslednjega ukaza. Taki računalniki so uporabljali pomnilnik s krožnim dostopom (magnetni boben, zakasnilna linija).

Lokacija operandov

Problem lokacije se pojavi večinoma samo pri ALE ukazih, saj pri drugih ukazih že sama narava ukaza določa izbiro. Poleg tega je ta problem omejen skoraj samo na 2 in 3-operandne računalnike, vendar je ravno teh največ. Operandi so lahko shranjeni v CPE, v gl. pom ali v V/I krmilnikih. Uporabljata se samo prvi dve možnosti. Ločimo torej tri variante:

  • Registrsko – registrski računalniki: vsi operandi ALE ukazov so v registrih CPE. Imenujemo jih tudi LOAD/STORE računalniki, ker je treba vsak operand prenesti iz in nazaj v pomnilnik. Imajo kratke, preproste ukaze. Čas izvrševanja ALE ukazov je vedno enak, vnaprej ga lahko določimo (dobro za paralelizem). Slabost je v tem, da je za rešitev istega problema potrebnih več ukazov, kot pri tistih računalnikih, ki imajo ALE operande lahko tudi v pomnilniku. To uporabljajo 3-operandni.
  • Registrsko – pomnilniški računalniki: eden je v registru ali v pomnilniku, drugi pa so vedno registrih. V to množico spadajo računalniki, ki imajo enega ali dva akumulatorja in registrsko-registrskih ukazov nimajo – akumulatorski računalniki. Pri ALE lahko uporabljamo pomnilniške operande, ne da bi jih prej prenesli v registre. Ukazi so daljši, vendar jih je potrebno manj. Časa za izvajanje ne moremo naprej predvideti, saj je odvisen od lokacije operandov. To uporabljajo 2-operandni.
  • Pomnilniško – pomnilniški računalniki: vsak operand je lahko ali v pomnilniku ali v registru. So najbolj splošni in omogočajo veliko število rešitev pri istem problemu. Lahko delamo tudi brez uporabe registrov, vendar je to slabo. Ukazi so zapleteni. CISC – VAX.

Načini naslavljanja

Način naslavljanja je način podajanja operandov v pomnilniku. Lahko jih razdelimo v tri osnovne skupine:

  • Takojšnje naslavljanje: operand je podan kar z vrednostjo, operand je del ukaza – dodatni dostop do pomnilnika ni potreben. Temu operandu pravimo takojšnji ali literal. Običajno se označuje z znakom #. Korist je največja pri primerjavah in v ukazih za prenos podatkov. Če takojšnjega naslavljanja ni, moramo konstante shraniti v glavnem pomnilniku v tabelo literalov.
  • Neposredno naslavljanje: operand je podan z naslovom (direktno, absolutno naslavljanje). Imamo registrsko naslavljanje - operand je podan z naslovom registra. Operand pa je lahko podan tudi z absolutnim pomnilniškim naslovo. Ker je naslov del ukaza, se ne spreminja in ga zato imenujemo tudi absoluten. Uporablja se samo za spremenljivke na fiksnem naslovu. Zahteva tudi dolge ukaze (če je pomnilnik dolg). Če želimo pomnilniški prostor povečati, ni kompatibilnosti. Naslov je lahko podan tudi samo z delom naslova.
  • Posredno naslavljanje: naslov pomnilniškega operanda v ukazu je podan preko neke druge vrednosti – ta je lahko v pomnilniku – pomnilniško posredno n. ali v registrih – registrsko posredno naslavljanje. Pri slednjem je to odmik, naslov izračunamo tako, da seštejemo vsebino registra in odmik. Pri pomnilniškem je potreben dodaten dostop do pomnilnika, poleg tega pa imamo v ukazu spet absoluten naslov. Zato se v večini uporablja samo registrsko, ki ga lahko razdelimo v več skupin:
    • bazno naslavljanje: v ukazu sta podana naslov registra in odmik. Dolžina registra je daljša ali enaka dolžini pomnilniškega naslova. Imenujemo ga bazni register. Dolžina odmika je variabilna. Naslov operanda se izračuna kot vsoto baznega registra in odmika.
    • Če je dolžina odmika enaka dolžini pomnilniškega naslova, to imenujemo indeksno naslavljanje. Običajno se odmik tu podaja z dvema registroma. Spreminjamo bazni register in ne odmik.
    • Pred-dekrementno naslavljanje je lahko bazno ali indeksno in avtomatsko zmanjšuje indeks, po-inkrementno pa avtomatsko zvečuje indeks. Skupaj lahko tvorita strukturo sklad. Velikostno indeksno naslavljanje namesto prištevanja(odštevanja) odmika uporablja množenje z odmikom.

Pozicijsko neodvisno naslavljanje: omogoča delovanje programa neodvisno od pozicije v pomnilniku na kateri je, kar pa lahko rešimo tudi v okviru navideznega pomnilnika. Glavno pri tem je, da program ne vsebuje ukazov, ki vsebujejo absolutne naslove. To je pri posrednem in neposrednem pomnilniškem naslavljanju. Spreminjati moramo program. Če program uporablja samo takojšnje in relativno (naslov je določen z vsebino najmanj enega registra) naslavljanje, lahko pozicijsko neodvisnost naredimo tako, da na začetku delovanja spremenimo samo začetno vsebino prvega registra (indeksnega ali baznega). Nekateri računalniki omogočajo PC-relativno naslavljanje – bazni register je kar PC.

Vrsta in dolžina operandov

Najpogostejše vrste:

  • 1. Bit - enobitnih operandov v večini višjih prog. jezikih ni
  • 2. Znak - dolžina 8 bitov, predstavljeni so v ASCII ali EBDDIC abecedi
  • 3. Celo število - dolžina 16 ali 32 bitov, predstavljeni kot predznačena števila v fiksni vejici (dvojiški komplement)
  • 4. Realno število - števila v plavajoči vejici - IEEE 754, 32 bitov al 64, nekje tudi 128
  • 5. Desetiško število - kot niz 8 bitnih znakov: v pakirani obliki z dvema BCD številkama v vsakem 8 bitnem znaku ali nepakirani z enim ASCII ali EBCDIC znakom v vsakem 8 bitnem znaku.

Sestavljeni operandi so sestavljeni iz več pomnilniških besed. Potrebno je pravilo, ki pove, na katero od večih besed kaže naslov. Uporabljata se pravilo debelega konca (Big Endian Rule) - pri njem je naslov sestavljenega operanda enak naslovu besede, ki vsebuje najtežji del operanda. Pri pravilu tankega konca (Little Endian) pa je obratno.

Problem poravnanosti

Problem se pojavi pri dostopu do sestavljenih operandov (so iz več pomnilniških besed). Da problema pri dostopu ni, mora biti naslov operanda A deljiv s številom besed s iz katerih je sestavljen. Operandom, za katere to velja, pravimo poravnani operandi. Če to ne velja, je za dostop do takega operanda potrebnih več pomnilniških dostopov, kar upočasni delovanje. Pri nekaterih računalnikih morajo naslovi biti obvezno poravnani.

Zgradba ukazov

Polju, ki določa operacijo pravimo operacijska koda. Število polj, ki sledijo, njihova belikost in pomen pa določa format ukaza, odvisen pa je od:

  • 1. Dolžine pomnilniške besede - ukazi so večkratniki le-teh.
  • 2. Števila eksplicitnih operandov v ukazu
  • 3. Vrste in števila registrov v CPE
  • 4. Dolžina pomnilniškega naslova


Glede na zgradbo ukazov so trije tipični načini:

  • 1. Spremenljiva dolžina - poljubno število operandov, veliko načinov naslavljanja. Z uporabo kratkih formatov za pogoste ukaze se poskuša doseči da so programi kratki. Pri 80x86 so ukazi dolgi od 1 do 15 bajtov.
  • 2. Fiksna dolžina - število operandov je vedno enako, način naslavljanja pa je vsebovan v operacijski kodi in jih ni dosti. Ukaz dolg recimo 32 bitov (npr. HIP, ARM,...)
  • 3. Hibridni način - teh je veliko, npr. IBM 370

Ortogonalnost ukazov

Ortogonalnost ukazov pomeni medsebojno neodvisnost parametrov, ki jih ukaz vsebuje. Torej: informacija o operandih je neodvisna od informacije o operaciji in informacija o enem operandu je neodvisna od informacije o ostalih operandih – če spremenimo en operand, to ne vpliva na informacijo, ki podaja ostale in tudi ne na operacijsko kodo. Za vsak operand lahko uporabimo vse načine naslavljanja in vse dolžine operandov (pri istem ukazu).

Dobra lastnost je lažje programiranje, po drugi strani pa odstopanje od ortogonalnosti poenostavi zgradbo CPE in jo naredi hitrejšo. Pri RISC računalnikih je ortogonalnost ukazov izgubila svoj pomen. Zakaj? Ker so tipično tipa registrsko-registrski in so vsi operandi v registrih, zato obstaja le ena možnost za njihovo podajanje.

CISC – RISC dilema

V 80' letih so se pojavile debate o tem, ali so boljši računalniki z velikim številom ukazov - CISC, ali pa z manjšim - RISC. Dejstvo je, da se je število ukazov stalno povečevalo, velik del pa se jih je uporabljalo zelo redko, prav tako glede načinov naslavljanja.

Razlogi za večanje število ukazov:

  • 1. Semantični prepad - razlika med računalnikom kot ga vidi programer v višjem programskem jeziku in tistim, ki ga vidi programer v strojnem jeziku. To so hoteli zmanjšati z dodajanjem ukazov, ki se pojavljajo v višjih programski jezikih.
  • 2. Mikroprogramiranje
  • 3. Razmerje med hitrostjo glavnega pomnilnika in CPE - dodajanje kompleksnih ukazov je bilo v 60' in 70' smiselno, saj je bil dostop do glavnega pomnilnika dosti počasnejši

Razlogi za zmanjševanje števila:

  • 1. Težave pri uporai kompleksnih ukazov v prevajalnikih
  • 2. Spremenjeno razmerje med hitrostjo glavnega pomnilnika in CPE
  • 3. Uvajanje paralelizma v CPE - realizacija cevovoda je pri preprostejših ukazih lažja


Za RISC računalnike velja:

  • večina ukazov se mora izvršiti v eni urini periodi
  • registrsko-registrski (load/store arhitektura)
  • ukazi so realizirani s trdo ožičeno logiko (in ne mikroprogramsko)
  • malo ukazov in malo načinov naslavljanja
  • vsi ukazi so enako dolgi
  • dobri prevajalniki (spreminjanje vrstnega reda)


Pri RISC računalnikih torej ne gre le za manjše število ukazov, ampak za drugo filozofijo gradnje računalnikov. Ker so ukazi preprostejši, je na njih za rešitev problema potrebnih več ukazov kot na CISC.

Meritve so pokazale, da so pri približno enaki ceni, RISC-i veliko hitrejši od CISC-ov. CPI je pri RISC veliko manjši. Poleg tega je na RISC računalniku realizacija paralelnega procesiranja veliko lažja.

Večina računalnikov po letu 90' je RISC. To pa ne pomeni, da CISC niso več razširjeni - to so vsa Intelova 80x86 arhitektura.

IBM 370 ukazi

To so računalniki, ki so se pod oznako IBM System/360 začeli proizvajati leta 1964 in so do danes doživeli več izboljšav.

Serija spada v skupino 2-operandnih registrsko-pomnilniških računalnikov. Uporablja bazno in indeksno naslavljanje, takojšnje(z uporabo baznega).

Obstajata dva nivoja priviligiranosti: nadzorni in problemski. Uporabljajo se v multiprogramskem okolju.

Prvotno so bili ukazi razdeljeni na 5 formatov z 8-bitno operacijsko kodo. Sedaj je formatov 14. Sprva so imeli 143 ukazov, kasneje se je povečalo na 208. Ne spada med RISCe pa tudi med ekstremne CISCe ne.

Kanalski ukazi so ukazi za upravljanje V/I procesorjev.

Koraki pri izvrševanju ukaza

Jemanje ukaza iz pomnilnika (fetch), naslov je shranjen v PC Izvrševanje v prejšnjem koraku prevzetega ukaza (execution) - izvršilni cikel. Vsebuje dekodiranje ukaza, prenos operandov v CPE, izvedbo z ukazom določene operacije in shranjevanje rezultata. Po izvedbi se PC poveča za dolžino ukaza razen pri skočnih ukazih, s katerimi lahko v PC vpišem poljubni naslov.

Vsakega od zgornjih korakov lahko razdelimo na več elementarnih. Najmanjše trajanje le-teh je ena urina perioda (časovni interval med prehodom iz nizkega v visoko stanje urinega signala in iz visokega spet v nizko). Ti koraki pa so:

  • prevzem ukaza (IF): vsebina PC se preko multiplekserja prenese na pomnilniške naslovne signale. Nato se iz pomnilnika prebere operacijska koda ukaza v IR. Če je zadetek v predpomnilniku se prenese v 1 up, sicer je zgrešitvena kazen. Če zahteva stopnja EX (skok) ali WB, PC = NewPC, sicer PC = PC+4.
  • dekodiranje ukaza (ID): poleg dekodiranja ukaza se v vmesna registra A,B preneseta izvorna registra, ki ju ukaz določa.
  • izvrševanje operacije (EX): izračuna se dejanski naslov ali pa se izvede ALE operacija. Med registri IR, A in B se določi katera dva bosta šla na vodili S1 in S2. Določi se tudi operacija, ki se bo opravila in rezultat se da na vodilo D in se zapiše v register, ki ga kontrolna enota določi iz operacijske kode.
  • dostop do pomnilnika (MEM): ta korak je potreben samo pri ukazih LOAD (MDR – M[MAR]), STORE (M[MAR] – MDR) in TRAP.
  • shranjevanje rezultata: samo pri ukazih CALL, LOAD, ALE, MOVER in TRAP

Rd C

Prekinitve

Prekinitev označuje dogodek, ki povzroči, da CPE začasno preneha izvajati tekoči program ter začne izvajati prekinitveno servisni program. Zahteva za prekinitev pride od zunaj. Prekinitve omogočajo, da drugi deli računalnika pridejo do uslug CPE.

Posebne vrste prekinitev so pasti, ki jo zahteva CPE sama ali na zahtevo programerja. Pasti pridejo od znotraj, poleg tega pa so sinhronske na program, prekinitve niso.

CPE odreagira na prekinitveno zahtevo šele potem, ko dokonča izvajanje trenutnega ukaza. Takojšnja reakcija je veliko kompleksnejša za realizacijo in se uporablja le, če drugače ne gre.

Za kaj je potrebno poskrbeti pri izvedbi prekinitev:

  • Prekinitve morajo biti omogočene. Programer lahko omogoči/onemogoči nekatere prekinitve – jih maskira. Po vklopu so prekinitve vedno onemogočene.
  • Zagotoviti je treba tudi nevidnost prekinitev – izvajanje PSP mora biti za uporabnika nevidno. Vse registre, ki se trenutno uporabljajo je treba shraniti (na sklad ali v registre) in jih zatem obnoviti. Med PSP so prekinitve onemogočene, kasneje se morajo omogočiti.
  • Potrebno je dobiti tudi naslov PSP, prepoznati je treba napravo, ki je poslala prekinitveno zahtevo. Imamo več rešitev:
    • programsko izpraševanje (polling) – pregledajo se registri vseh naprav (v nekem vrstnem redu glede na prioriteto) v katerih eden od bitov pove ali je zahtevala prekinitev, Ta rešitev je počasna.
    • Lahko se v CPE pošlje informacija, iz katere ta prepozna izvor zahteve. Med najbolj znanimi načini so tako imenovane vektorske prekinitve (glej 20).
  • Treba je ugotoviti prioriteto (katera od prekinitev se bo izvedla prva). Poleg tega je na nekaterih računalnikih dovoljeno, da prekinitev z višjo prioriteto prekine prekinitev z nižjo – vgnezdene prekinitve. CPE ima register, s katerim je določen trenutni prioritetni nivo. Odzove se samo na tiste prekinitve, ki imajo višjo prioriteto od lastne. S pomočjo dodatnega elementa – prekinitvenega krmilnika, lahko to vgradimo tudi v CPE, ki ima samo en bit za omogočanje prekinitev. Če je na en prekinitveni vhod priključenih več naprav, lahko problem prioritet rešimo s pollingom ali pa z marjetično verigo.
  • Prekinitev je potrebno potrditi, da naprava umakne svojo zahtevo. Lahko se naredi programsko (PSP bere ali piše v nek register krmilnika naprave), ali strojno (CPE s posebnim kontrolnim signalom obvesti napravo, da je upoštevana).

Vektorske prekinitve

Vektorske prekinitve so skupno ime za vse načine prepoznavanja prekinjajoče naprave, pri kateri naprava pošlje v CPE informacijo o naslovu njenega PSP. To pošiljanje se naredi v prekinitvenem prevzemnem ciklu, s katerim CPE pove napravam naj pošlje informacijo o izvoru. Gledano iz CPE je to posebna vrsta branja. Od drugih branj ga loči kombinacija kontrolnih signalov.

Pri nekaterih računalnikih je informacija kar naslov, v glavnem pa je samo del naslova PSP. Naslovu, kjer je shranjen naslov PSP pravimo prekinitveni vektor ali vektorski naslov. Uporablja se kot kazalec v tabelo, ki vsebuje naslove PSP. Torej je del naslova številka vektorja. V principu je možno, da ima ista naprava več PSP-jev. Vektorske prekinitve so tipične za večino po letu 1980 razvitih računalnikov.

Realizacija prekinitev pri IBM 370

CPE razlikuje štiri skupine prekinitev in dve skupini pasti. CPE ima štiri prekinitvene vhode, preko katerih prihajajo zahteve za naslednje skupine prekinitev: strojna napaka, eksterna prekinitev, V/I prekinitev, Restart.

Najvišjo prioriteto ima strojna napaka, najnižjo pa Restart. Restart ni mogoče onemogočiti. Za iste vrste prekinitev se uporablja marjetična veriga. Prepoznavanje je strojno, vendar ne na vektorski način. Potrjevanje je strojno. Prekinitve lahko maskiramo v registru PSW (če je določen bit 1 je določena p. omogočena). Ob prekinitvi se PSW shrani, vanj pa se shrani nova vsebina prenesena iz enega od šestih naslovov (odvisno od vrste prekinitve/pasti). Z zamenjavo PSW se naredi skok v PSP, hkrati pa se na fiksne naslove shrani opis prekinitve iz katerega je razviden vzrok prekinitve. Iz PSP se nazaj v program vrnemo z ukazom LPSW (load PSW), ki vanj vrne staro vrednost.

Strojna napaka se aktivira, kadar pride pri delovanju računalnika do napak.

Eksterna prekinitev pride iz ure realnega časa, tipke Interrupt in še 6 virov.

V/I prekinitve pridejo iz V/I procesorjev – kanalov, na katere so priključeni krmilniki, na katere so priključene naprave. Razdeljene so v 8 podrazredov, vsak ima v kontrolnem registru svoj bit, s katerim lahko prekinitve maskiramo. Za programerja so vidni samo podkanali. Vsak ima številko podrazreda, s katero vidimo v katerega spada. Lahko jo spreminjamo. PSP mora ugotoviti iz katerega podkanala je prišla IRQ.

IBM 370 nima veliko podpore za vgnezdene prekinitve. Vsi V/I procesorji uporabljajo isti PSP. Vgnezdene prekinitve je možno narediti z ustreznim maskiranjem podkanalov in programsko realiziranim skladom za shranjevanje starega PSW, vendar to ni potrebno, saj vse podrobnosti pri komuniciranju z V/I napravam opravijo V/I procesorji – prekinitve se uporabljajo predvsem za obveščanje programov da je izvajanje V/I operacij končano, oziroma da je prišlo do napake.

Pasti so razdeljene v dve skupini. Supervisor Call za klic sistemskih programov in za preklop med dvema nivojema privilegiranosti in Program Interruptions, ki se sprožijo ob deljenju z nič, nedefiniranim ukazom …

Prekinitve pri Cyber

Razviti so bili predvsem za numerične obdelave v okoljih, ki ne zahtevajo hitrega odzivanja na zunanje zahteve. CPU dobiva prekinitvene zahteve iz V/I procesorjev imenovanih PPU – Peripheral Processing Unit. Zaradi posebne realizacije le-teh, ki uporablja strojno časovno dodeljevanje skupne logike, lahko v vsaki urini periodi zahteva prekinitev zgolj en procesor. Vsak od njih lahko prekine CPE, ki nima možnosti za onemogočenje prekinitev. Izvrši ukaz EXN (exchange jump), CPE dobi signal za prekinitev in odreagira:

dokonča vse ukaze v besedi na katero kaže PC, v eni besedi so lahko do 4 ukazi iz 16 60-bitnih besed dolgega področja v gl.pom., ki je določeno za naslovom v registru V/I procesorja se prenese v CPE nova vsebina vseh registrov, istočasno pa se trenutna vsebina shrani na to področje. Prepoznavanje izvora se doseže avtomatsko. Potrjevanje ni potrebno, ker do prekinitve zagotovo pride. Transparentnost je zagotovljena avtomatsko. Iz PSP se je mogoče vrniti z ukazom XJ ali EXN, ki ga izvede V/I procesor. V CPE se vrnejo stare vrednosti. Bistvo teh IRQ je v preklapljanju enega uporabniškega programa na drugega in ne v servisiranju zahtev V/I naprav. Možne so tudi vgnezdene prekinitve, če le vsak V/I procesor uporablja drugo področje v glavnem pomnilniku. V/I naprave ne morejo prekinjati V/I procesorjev.

Pasti delujejo podobno le da jih sproži CPE. Naslov pomnilniškega področja za izmenjavo je naslov najnižje lokacije v pomnilniku, ki je dodeljen tekočem programu. Ta naslov je vedno v registru RA v CPE. Past se sproži ob nedovoljenem naslovu, prelivu (za FLOAT), uporabi nedef operanda (NaN). Možno jih je onemogočiti.

Cevovodno procesiranje

Razlog: v zadnjih desetih letih se je najvišja hitrost logičnih elementov povečala za 10X, število elementov na istem čipu pa za 5000X.

Cevovod je način izkoriščanja paralelizma na nivoju ukazov. Z besedo cevovod se označuje realizacija CPE, ki naenkrat izvršuje več ukazov, tako da se posamezni koraki izvrševanja prekrivajo. Je Podoben je tekočemu traku. Izvrševanja ukaza se razdeli na manjše podoperacije – stopnje, segmente cevovoda. Pomik iz ene v drugo se dela naenkrat. Podoperacije morajo biti uravnotežene. Pospešitev idealnega cevovoda bi bila N-kratna, pri čemer je N stopnja cevovoda, a vendar stopnja ne presega 10, saj z večanjem stopnje cevovodne nevarnosti izničijo pridobitve in je lahko cevovod še slabši kot bi bil, če bi bila stopnja manjša. Cevovod je mogoče narediti na način, ki je za programerja neviden.

Vrste nevarnosti v cevovodu

Veliko prednosti cevovodnega procesiranja se zmanjša zaradi cevovodnih nevarnosti, zato jih moramo na nek način odpraviti. Prvi RISC-i so jih odpravljali večinoma programsko (vstavljanje NOP-ov). Tako odpravljanje bistveno poenostavi delovanje CPE, a povzroči nekompatibilnost programov na različnih računalnikih in upočasni delovanje.

Poznamo tri vrste nevarnosti:

  • Strukturne nevarnosti so kadar dve ali več stopenj cevovoda v isti urini periodi potrebujeta enoto, ki je sposobna delati samo eno operacijo naenkrat (registri, ALE, pomnilnik) ali če hočeta dva ukaza pisati naenkrat v svoj programsko dostopni register. Do teh nevarnostih pride tudi pri ukazih za operacije, ki trajajo več urinih period. Če imamo take operacije v stopnji EX in imamo samo eno tako stopnjo, morajo kasnejši ukazi čakati na to stopnjo.

Mogoče jih je odpraviti z zmogljivejšim predpomnilnikom in tako, da vgradimo dovolj veliko število enot (stopnja EX se lahko naredi v obliki cevovoda).

  • Podatkovne nevarnosti lahko imenujemo tudi operandne nevarnosti. Do njih pride, če nek ukaz potrebuje operand, ki še ni dostopen. Odpravimo jih lahko tako, da se stopnja ID ukaza, ki potrebuje nedostopen operand ustavi, dokler le-ta ni dostopen (cevovodna zaklenitev ≠ cevovodna ustavitev). Vstavljamo mehurčke v vse stopnje, ki so levo od tam, kjer se je cevovod zaklenil. Rešimo jih lahko tudi s premoščanjem, ki je boljša rešitev. Logika za premoščanje omogoča, da dobimo operand iz vmesnih registrov cevovoda, ampak tudi premoščanje ne odpravi vseh nevarnosti, zato je v nekaterih primerih potrebno vstavljanje mehurčkov. Tretji način za odpravljanje podatkovnih nevarnosti, je s spreminjanjem vrstnega reda – cevovodno razvrščanje.

Podatkovne nevarnosti lahko razdelimo v tri vrste: RAW, WAR, WAW.

  • Kontrolne nevarnosti povzročajo v večini bistveno večjo izgubo kot strukturne in podatkovne nevarnosti. Do njih pride pri operacijah, ki spremenijo vsebino PC drugače kot običajno – pri kontrolnih ukazih (pogojni skoki, brezpogojni skoki, klici in vrnitve – SKOKI). Kadar stopnja EX spremeni vsebino PC sta vsebini stopenj IF in ID neveljavni - v teh dveh stopnjah sta ukaza, ki sledita skoku in se ne smeta izvesti. Najpreprostejši način je, da se namesto vsebine IF in ID vstavita mehurčka. Ta rešitev deluje brez čakanja, če pogoj za skok ni izpolnjen – cevovod predpostavlja neizpolnjen pogoj. CPI zaradi tega občutno naraste, zato je treba izgubo zmanjšati. Pri zasnovi cevovoda upoštevamo dve stvari: preverjanje pogoja za skok in izračun skočnega naslova naj se izvaja čim bližje prvi stopnji cevovoda.

Kontrolne nevarnosti lahko odpravljamo tudi s predikcijo. Delimo jo v dve skupini: statično in dinamično - glej naprej.

Statična predikcija z zakasnjenimi skoki

Pri tej rešitvi sodeluje prevajalnik, ki skuša za pogojne skoke napovedati čim bolj verjeten rezultat pogoja za skok, še preden se program začne izvajati, tako da se napoved med izvajanjem ne spreminja – zato je statična.

Pomemben je pojem skočnih rež. Ukazi, ki so v programu takoj za skokom, so v skočnih režah - njihovo število je enako številu stopenj cevovoda, ki so pred stopnjo v kateri se prenese skočni naslov v PC. Pri HIP je to stopnja EX.

Statična predikcija uporablja zakasnjene skoke - ne glede na izpolnjenost pogoja se vedno izvršijo vsi prevzeti ukazi. Tudi pri izpolnjenem pogoju za skok se ukaza v skočnih režah ne nadomestita z mehurčki. Ker se ta dva ukaza vedno izvršita, moramo skočni ukaz prestaviti za število skočnih rež ukazov nazaj (pri HIP za 2) oz. z drugimi besedami. Videti je, da se skočni ukazi izvedejo z zakasnitvijo, zato ime zakasnjeni skoki. V skočne reže moramo vstaviti ukaze če se da, drugače pa NOP-e.

Cevovod z zakasnjenimi skoki lahko izboljšamo z uvedbo razveljavitvenih skokov. Običajna napoved je, da skok bo. Če je ta napoved napačna, se ukazi, ki so v skočnih režah razveljavijo. S tem lahko skočne reže skoraj vedno zapolnimo.

Zakasnjeni in razveljavitveni skoki občutno prispevajo k zmanjšanju škode. Tudi njihova vključitev je preprosta. Slabost je v tem, da je potrebno drugačno programiranje in da so programi nezdružljivi z drugimi računalniki. Poleg tega je uspešnost statične predikcije pri cevovodih z veliko stopnjami, z velikimi skočnimi režami veliko slabša. Zato se po letu 1990 vse bolj uporablja dinamična predikcija.

Dinamična predikcija

Napovedovanje izpolnjenosti pogoja se spreminja med izvajanjem programa. Prilagaja se dogajanju v programu, zato je tudi boljša od statične predikcije.

Najpreprostejša vrsta te predikcije je prediktorska tabela. To je majhen pomnilnik, do katerega se dostopa pri pogojnih skočnih ukazih, s spodnjimi biti naslova na katerem je ta ukaz. V najenostavnejši izvedbi so njene vrednosti 1-bitne. Če je bil pogoj pri skoku izpolnjen se v tabelo vpiše 1, sicer 0. Pri stopnji IF se bere tudi iz te tabele. Če v IF ni pogojnega skoka, se branje ignorira, sicer se uporabi za napoved skoka. Naslednji ukaz se prevzame iz naslova v skočnem predpomnilniku, ki ga napoveduje bit. Če se v stopnji EX izkaže, da je bila napoved napačna, se stanje bita spremeni, prevzeti ukazi pa se spremenijo v mehurčke.

1-bitna tabela ima slabo natančnost napovedovanja (pri vgnezdenih zankah bo napoved skoraj vedno dvakrat napačna – ob zadnjem (se ne da izogniti) in ob prvem obhodu).Ta pomankljivost se lahko odpravi z 2-bitno tabelo. Pri njej imamo 4 vrednosti. Če je pogoj izpolnjen se prišteje 1 (če je 3 ostane 3), sicer se odšteje 1 (0-1=0). Če je 2 ali 3 se vzame izpolnjen pogoj, sicer neizpolnjen. Ob prvem obhodu zanke bo napoved pravilna, torej je napačna le 1 napoved, v primerjavi z dvema pri 1-bitni. 2-bitne so skoraj enako natančne kot n-bitne.

Natančnost napovedi je približno 93%. Čeprav je to veliko, se da še izboljšati: upoštevamo tudi preteklost drugih pogojnih skokov in ne samo trenutnega. Prediktorji, ki to upoštevajo se imenujejo korelacijski prediktorji. (m,n) korelacijski prediktor uporablja obnašanje zadnjih m skokov, da izbere eno od običajnih prediktorskih tabel velikosti n, v kateri se izbere vrednost na lokaciji, ki jo določimo s spodnjimi biti naslova ukaza. Za vsak skok potrebujemo 2^m tabel. Podatki o zadnjih m skokih se označuje kot globalna zgodovina pogojnih skokov. 2-bitna prediktorska tabela je v bistvu (0,2) korelacijski prediktor

Turnirski prediktor - paralelno delujeta lokalni in globalni prediktor (podoben korelacijskemu). Na osnovi prejšnje uspešnosti se pri vsakem skoku izbere tistega, ki je bil bolj natančen - med sabo v bistvu "tekmujeta" zato ime turnirski.

Skočni predpomnilnik - ne glede na vrsto uporabljenega prediktorja tudi ob pravilni napovedi izgubimo 1 urino periodo. To želimo zmanjšati na nič. Razlog za izgubo je, da skočnega naslova v prvi stopnji cevovoda ni možno izračunati, ker še ni znano za kakšen ukaz gre. Skočni predpomnilnik vsebuje skočne naslove zadnjih skokov, pri katerih je bil pogoj za skok izpolnjen. Skočni naslovi se v predpomnilnik shranijo v stopnji EX, če je bil pogoj za skok izpolnjen. V stopnji IF se dela tudi dostop do skočnega predpomnilnika - če je v njem zadetek, se skočni naslov zapiše v PC. To pomeni, da pri pravilni napovedi ni treba čakati 1 urine periode. Če napoved ni bila pravilna ali pa skočni naslov ni bil pravilen, se ukaza v stopnjah ID in IF zamenjata z mehurčki.


Običajno je realiziran skupaj s prediktorskimi tabelami, tako da sta oba del skočne enote. Pri zadetku se iz skočnega predpomnilnika naloži vrednost v IR. Če je pogoj izpolnjen se ta vrednost prenese iz IR v PC. V vsakem primeru se skočni ukaz izvaja naprej. Ko pride v EX se preveri izpolnjenost pogoja za skok in enakost napovedanega skočnega naslova – zaradi t.i. indirektnih skokov, pri katerih je skočni naslov določen s vsebino določenih registrov, ki pa se lahko med izvajanjem spreminjajo. Lahko imamo proceduro, ki se kliče iz več mest. To lahko rešimo s skladom. Če je skočni pogoj ob preverjanju neizpolnjen, se naslov izbriše iz skočnega predpomnilnika. Skočnemu ukazu, ki je sedaj v stopnji EX, se dovoli, da v PC v stopnji IF prenese izračunani skočni naslov (PC-PC2+4). Če je skočni pogoj izpolnjen, napovedani naslov pa ni enak izračunanemu, se izračunani zapiše v skočni predpomnilnik. Skočni ukaz v PC prenese izračunani skočni naslov: PC-PC2+4+razR.

Kako doseči CPI<1

Cevovod omogoči da se CPI približa 1. Če želimo CPI zmanjšati pod 1, moramo v eni urini periodi prevzeti več kot 1 ukaz – več-izstavitveni procesorji. Te procesorje lahko razdelimo v superskalarne in VLIW procesorje. Razlika je v načinu prevzemanja in izstavljanja ukazov. Prevzemanje ukazov in njihovo izstavljanje sta operaciji, ki ju je mogoče izvajati statično ali dinamično.

Statično razvrščanje: procesor prevzema ukaze v natanko takem vrstnem redu, kot so v programu – inorder. Spreminjanje vrstnega reda lahko opravlja prevajalnik. Ni potrebno imeti logike, ki spreminja vrstni red prevzemanja. Slabost je, da ne pridejo v istočasno izvrševanje ukazi, za katere se med izvajanjem programa pokaže da bi lahko prišli, vendar prevajalnik tega ne more ugotoviti in zato ne razvrsti ukazov.

Dinamično razvrščanje: procesor prevzema ukaze po vrstnem redu, ki je drugačen od tistega v programu – out of order. Spreminjanje vrstnega reda opravlja procesor. Kadar je ena od enot procesorja prosta išče ukaze, ki jih je mogoče poslati vanjo. Prednost se pokaže pri zgrešitvah v predpomnilniku, med čakanjem lahko izvrši nek drug ukaz. To je mogoče narediti samo pri neblokirajočem pomnilniku. Pri iskanju ukazov moramo uporabljati dinamično predikcijo skokov. Ker predikcija ni vedno pravilna, ni zanesljivo, da bo tako prevzet ukaz v resnici potreben, zato se tako izvrševanje imenuje špekulativno.

Statično izstavljanje: je način pri katerem je vrstni red izstavljanja ukazov v stopnjo EX določen že pri prevzemu ukaza. Procesor glede tega ne odloča o ničemer. Taki procesorji imajo običajno tudi statično razvrščanje.

Dinamično izstavljanje: vrstni red izstavljanja določa logika v procesorju. Pregleduje ukaze, ki se izvršujejo in išče take, ki niso odvisni od trenutno izvršujočih. Če takega najde, ga izstavi v izvrševanje. Pri špekulativnem izvrševanju se rezultati ukazov ne smejo shraniti v programsko dostopne registre ali pomnilnik tako dolgo, dokler ni gotovo, da je bila predikcija skokov, s katero so bili prevzeti pravilna.


Za računalnik, ki uporablja špekulativno izvrševanje ukazov je značilno, da uporablja: dinamično predikcijo skokov, dinamično razvrščanje ukazov.

Superskalarni procesorji - procesor, ki dinamično določa kateri in koliko ukazov se v isti urini periodi izstavlja v izvrševanje. Po letu 1995 je začelo prevladovati tudi dinamično razvrščanje. Videti je kot da imamo več cevovodov.

Pri VLIW procesorjih imamo dolge ukaze, ki se prevzemajo enako kot pri drugih računalnikih. V vsakem dolgem ukazu je neko število običajnih ukazov, ki se izvršujejo paralelno - predstavljamo si, da vsak od običajnih ukazov pomeni operacijo za eno izmed funkcijskih enot.

Načini dostopa do glavnega pomnilnika

Poznamo dva načina glede na način dostopanja do pomnilniški besed: s podajanjem naslova in s podajanjem vsebine besede (asociativni predpomnilniki). Navadne pomnilnike delimo še glede na vrstni red naslovov do katerih dostopa:

Naključni dostop: čas dostopa do besede je neodvisen od naslova pred tem naslovljenih besed – je konstanten. To so DRAM pomnilniki, ki imajo tudi page mode način, ki pa ni naključni; dostopamo do zaporednih bitov, ki so v prebrani vrstici. Ta način pokaže svoje prednosti pri uporabi predpomnilnika, saj se vanj vedno prenese cela vrstica (ena ali več).

Zaporedni dostop: čas za dostop je odvisen od naslova besede, do katerega smo dostopali prej. Izvršiti moramo dostop do vseh vmesnih besed. Magnetni trak, pomikalni reguister.

Krožni dostop: posebna vrsta zaporednega dostopa – magnetni diski s fiksnimi glavami. Predstavljamo si ga lahko kot zlepljen magnetni trak.

Direktni dostop: kombinacija krožnega in zaporednega dostopa (najprej se glava premakne na pravo sled (zaporedni), potem pa se sled vrti, dokler glava ne doseže želenega naslova (krožni) ) – magnetni disk.

Organizacija glavnega pomnilnika

Vidik CPE nad pomnilnikom imenujemo organizacija pomnilnika. Glavni pomnilnik je videti kot enodimenzionalno zaporedje pomnilniških besed, vsaka pa ima svoj naslov. Osnovna parametra vsakega pomnilnika sta:

  • Pomnilniška beseda je najmanjše število bitov s svojim naslovom.
  • Pomnilniški naslov je število, ki enolično določa neko pomnilniško besedo. Z n bitnim naslovom lahko naslovimo 2^n besed – dolžina določa maksimalno velikost pomnilniškega prostora. Obstaja ena sama napaka, ki jo je pri kasnejšem razvoju računalnika težko popraviti – premajhno število bitov za pomnilniški naslov.


Ločimo signale preko katerih se naslavlja (naslovni), signale preko katerih se prenašajo (podatkovni) iz/v pomnilnik ter kontrolne (nadzor nad smerjo prenosa...).

Dolžina besede določa tudi dolžino registrov (mnogokratnik dolžine besede) - posredno. Največji izkoristek je, če je dolžina besede 1, vendar to povzroči veliko bolj zapleteno in počasno CPE.


Iz pomnilnika lahko prenašamo več besed naenkrat (page mode dostop) – odvisno od širine poti.

Problem poravnanosti se pojavi, če je širina poti večja od ene besede in če je operand, ki ga želimo prebrati, na naslovu ki ni deljiv s širino poti. Potem moramo opraviti dve branji in ju združiti v en operand. Če dovolimo neporavnanost, je prostor bolj izkoriščen, porabi pa se več časa in pot med CPE in pomnilnikom je bolj zasedena.

Metabiti (označevalni biti)

To so biti pomnilniške besede, ki opisujejo pomen ostalih bitov. Večina računalnikov jih nima ali pa uporablja samo bite za detekcijo/korekcijo napak – paritetne bite (SECDED). Vendar pri pojmu metabiti mislimo na bite, ki povejo kaj dana beseda vsebuje. Z njimi dosežemo to, da se CPE začne zavedati zgradbe programa, kar povzroči:

  • manjše število ukazov (če ni ortogonalnosti)
  • avtomatska pretvorba operandov
  • avtomatsko računanje in preverjanje indeksov
  • avtomatsko vzpostavljanje klicnih parametrov
  • ugotavljanje nesmiselnih operacij
  • ugotavljanje nedefiniranih operandov

Glavna prednost je lažje programiranje v zbirnem jeziku. Semantični prepad je manjši. Ker se na tem področju ne programira veliko, je upadlo tudi zanimanje za metabite. Slabost je tudi v bolj kompleksni CPE, kar povzroči težjo realizacijo paralelnosti.

Zaščita glavnega pomnilnika

Nevarnosti: programer sesuje operacijski sistem s spreminjanjem le-tega, programi lahko posegajo v pomnilniški prostor drugega pri multiprogramskih sistemih. Prvi računalniki niso imeli nobene zaščite, saj so se uporabljalo na enouporabniški način. Za zagonske in nekatere druge programe so uporabljali bralni pomnilnik. Možnosti za zaščito so:

  • Najpreprostejši pravi način za zaščito je par registrov, ki vsebuje spodnjo in zgornjo mejo naslova, ki pripada programu. Lahko imamo tudi samo začetni naslov in dovoljeno dolžino programa. Slabost je v tem, da mora program biti zvezen, poleg tega pa so vse besede zaščitene na enak način.
  • Vsaka beseda ima metabite, ki povejo, kateremu programu pripada ta beseda. Pri tem je velika potrata pomnilnika in časa.
  • Rešitev, ki se uporablja danes je z zaščitnimi ključi blokov: glavni pomnilnik je razdeljen na dele določene velikosti, ki so vsak zase zaščiteni. Tem delom pravimo bloki ali strani (ki pa niso strani v smislu navideznega pomn.!!). Vsakemu programu je dodeljen pomnilniški prostor, ki je enak celemu številu strani. Vsaka stran ima svoje zaščitne metabite – zaščitni ključ, ki se shrani v poseben pomnilnik, do katerega ne moremo dostopati s pomnilniškimi ukazi. Metabitov je pri tej rešitvi dosti manj kot pri prejšnji.

Zaščita glavnega pomnilnika pri IBM 370

Glavni pomn. je razdeljen na bloke velikosti 4096 besed. Vsak blok ima svoj zaščitni ključ, ki je dolg 7 bitov. Ključ določa, kateremu programu pripada blok (biti 0-3) in kako naj deluje zaščita (bit 4 - če je 0 deluje samo pri pisanju, sicer tudi pri branju). Pri vsakem dostopu, se biti 0-3 ključa primerjajo z biti 8-11 v PSW, oziroma če dostopa V/I naprava z biti 0-3 v drugi besedi ORB bloka. Dostop je dovoljen samo če so ti biti enaki, drugače se sproži past zaščite.

Zaščitni ključi so v posebnem pomnilniku in jih lahko spreminjamo z SET STORAGE KEY in berem z INSERT STORAGE KEY – privilegirana ukaza. Programi, ki delujejo v nadzornem načinu delovanja, lahko spreminjajo ključe in obidejo zaščito, zato je treba zagotoviti, da navaden uporabnik ne more delovati v nadzornem načinu (SUPERVISOR CALL).

Predpomnilnik

Predpomnilnik izrablja lokalnost pomnilniških dostopov: je majhen in hiter. Na zunaj deluje, kot da je velik. Zgrajen je iz SRAMov in je običajno na istem vezju kot CPE. Služi kot premoščanje vrzeli med hitrostjo DRAMov in hitrostjo CPE. Vrzel se zmanjša iz 750X na 15X. Da je učinkovitejši, ga razdelimo na dva dela (nehomogen - Harvardski predpomnilnik) – enega za operande in enega za ukaze, tako da se lahko v isti urini periodi dostopa do obeh. Uporabimo tudi širše podatkovne poti iz CPE do predpomnilnika in iz predpomnilnika do glavnega pomnilnika. Dodamo lahko tudi drugi, tretji, … nivo predpomnilnika. Vsak naslednji nivo je večji in počasnejši. Z uporabo več nivojev predpomnilnika lahko popolnoma premostimo vrzel med hitrostjo CPE in glavnega pomnilnika.

Predpomnilnik imamo lahko tudi v V/I procesorjih ali napravah. Je podmnožica glavnega pomnilnika.

Predpomnilnik tipično predstavlja manj kot 1% glavnega. Ker je delovna množica veliko manjša od velikosti glavnega pomnilnika, ima lahko predpomnilnik majhno velikost.

Uspešnost delovanja merimo z verjetnostjo zadetka H. Ko je naslov, do katerega se dostopa, v predpomnilniku, je to zadetek. Če pa ga ni, je to zgrešitev in je potrebno podatke prenesti iz glavnega oziroma iz L2. Verjetnost zadetka je tipično večja od 0,95.

Zgrešitvena kazen je število urinih period, ki se pri zgrešitvi prištejejo k času dostopa. To je običajno med 10 in 100.

Predpomnilnik je sestavljen iz dveh delov: pomnilniški del in kontrolni del:

  • Pomnilniški del je razdeljen v enote, ki jim pravimo bloki. To je 2^b sosednjih pomnilniških besed. Ponavadi so veliki 8-256 pomnilniških besed. Pri dostopu spodnjih b bitov naslova določa besedo v bloku, zgornjih n-b pa naslov bloka.
  • Kontrolni del vsebuje informacijo, ki enolično opisuje vsak blok. Ta vsebuje vsaj naslov bloka, običajno pa tudi veljavni bit in umazani bit. Naslovi blokov povejo, katera podmnožica glavnega pomnilnika je trenutno v predpomnilniku.

Delovanje predpomnilnika

Pri vsakem dostopu imamo n-bitni naslov. Zgornjih n-b bitov se v predpomnilniku primerja z naslovi v kontrolni informaciji vseh blokov. Če obstaja nekje enakost, je beseda, do katere je zahtevan dostop, v predpomnilniku. To je zadetek in vrši se dostop do vsebine v tem bloku. Dostop se naredi samo, če ima blok veljavni bit = 1. Če pri primerjavi ni enakosti pri nobenem bloku, imamo zgrešitev in potreben je dostop do glavnega pomnilnika. Od tam se blok prenese v enega od blokov predpomnilnika. Če so vsi zasedeni in veljavni, bo nov blok zamenjal enega od njih. Temu pravimo zamenjava bloka. Ob zamenjavi bloka se mora vsebina bloka najprej prenesti nazaj v glavni pomnilnik. Veljavni bit V je zato, ker vsebina včasih ni veljavna - ob vklopu, recimo.

Primerjava zgornjih n-b bitov mora biti hitra - ker je blokov veliko, je to problem. Da ga rešimo, uprabimo omejitve pri preslikovanju. Glede na to poznamo: asociativne, set-asociativne in direktne predpomnilnike.

Predpomnilniki glede na omejitve pri preslikavi

Problem je v primerjavi naslova, ki ga da CPE z zgornjimi n-b biti v kontrolnem delu bloka. Primerjavo je treba opraviti z vsemi bloki v eni urini periodi. Zato uvedemo določene omejitve pri preslikavi.

1. Problem primerjave lahko rešimo z uporabo čistega asociativnega pomnilnika. Potrebujemo toliko primerjalnikov, kot je število predpomnilniških blokov. Rečemo mu asociativni, ker je kontrolni del pravzaprav asociativni pomnilnik - pri njem poteka dostop preko vsebine, to pa je tukaj naslov bloka. Tu ni pri preslikovanju nobenih omejitev - vsak blok predp. lahko sprejme vsak blok iz glavnega pomnilnika. Pomnilnik je zato popolnoma izkoriščen. Problem pa je v tem, da potrebujemo zelo veliko število n-b bitnih primerjalnikov, kar je drago. Zadosti velikih asociativnih predpomnilnikov z današnjo tehnologijo ni mogoče narediti (dosegajo velikosti do nekaj 100 blokov).

2. Velik predpomnilnik lahko naredimo le z vpeljavo omejitev pri preslikovanj naslovov. Predpomnilnik razbijemo na več setov S=2^s, vsak set pa je majhen asociativni pomnilnik. Dobimo set-asociativni predpomnilnik. Število blokov v setu imenujemo stopnja asociativnosti ali asociativnost E=2^e in je tipična med 1 in 16. To je velikost asociativnega pomnilnika v setu - enaka je številu primerjalnikov, ki jih predpomnilnik potrebuje. Sedaj je za vsako besedo glavnega pomnilnika vnaprej določeno v kateri set se bo preslikala. Za nek naslov Ai velja da se lahko preslika v enega izmed blokov seta, ki ga določa enačba Si=Ai(b:n-1) (mod2^s). Ai(b:n-1) je zgornjih n-b bitov pomnilniškega naslova. Če je stopnja asociativnosti enaka številu blokov imamo čisti asociativni predpomnilnik - imamo 1 set.

3. Če je stopnja asociativnosti E=1, dobimo t.i. direktni predpomnilnik, pri kateremu so omejitve pri preslikavi najhujše. Za vsako besedo je vnaprej določeno v katerega izmed blokov(=setov) se bo preslikala. Je preprostejši od set asociativnega in cenejši.

4. Četrta možnost je pseudo asociativni predpomnilnik. Poskuša združiti prednosti direktnega in set-asociativnega pomnilnika. Če imamo zadetek deluje identično kot direktni predpomnilnik. Sicer se namesto dostopa do višjega nivoja dela dostop do pseudo bloka. Dostop do tega bloka je nekoliko daljši. Obstaja nevarnost, da so vsi zadetki v pseudo bloku. Če se zgodi to, preprosto zamenjamo vsebino blokov.


Z zmanjševanjem stopnje asociativnosti se zmanjšuje tudi cena in verjetnost zadetka.

Predpomnilniško pravilo 2:1

V zvezi z direktnim predpomnilnikom velja naslednje (empirično) pravilo: verjetnost zgrešitve direktnega predpomnilnika velikosti M je približno enaka verjetnosti zgrešitve set asociativnega predpomnilnika s stopnjo asociativnosti 2 in velikosti M/2.

Kakšna naj bo velikost bloka

Predpomnilnik lahko povečujemo tako, da povečujemo stopnjo asociativnosti, število setov ali velikost bloka(najlažje in najceneje ker ima vsak blok svojo kontrolno informacijo, to pa je najbolj zapleten del).

S povečevanjem bloka se ustvarjajo pogoji za boljšo izkoriščenost prostorske lokalnosti, ker pa se s povečevanjem pri isti velikosti predpomnilnika zmanjšuje število blokov, se s tem slabšajo pogoji za izkoriščanje časovne lokalnosti. Iz meritev lahko ugotovimo, da so pri večjih predpomnilnikih boljši večji bloki in obratno za manjše. Če je velikost blokov premajhna, se le-ti stalno zamenjujejo in verjetnost zadetka je majhna. Velikost števila blokov vedno izboljša verjetnost zadetka

Na velikost bloka vpliva tudi zgrešitvena kazen, ki je lahko večja s povečevanjem velikosti bloka. Tako pri neki točki velikosti bloka velika zgrešitvena kazen odtehta veliko verjetnost zadetka in povzroči poslabšanje delovanja.

Kateri blok naj se zamenja ob zgrešitvi

Pri direktnih predpomnilnikih je ta izbira preprosta, saj imamo samo eno možnost - zamenja se blok, v katerega se preslika beseda, pri kateri je prišlo do zgrešitve.

Drugače je pri čistih in set asociativnih predpomnilnikih. Novi blok se lahko da v katerikoli blok, ki jih vsebuje set. Ko je predpomnilnik še prazen to ni problem, kasneje pa. Za določanje blokov se uporabljata dve zamenjevalni strategiji:

  • Naključna strategija: blok se izbere naključno, prednost je v enostavnosti logike
  • LRU: Least Recently Used strategija beleži uporabo blokov in zamenja tistega, do katerega najdlje ni bil narejen dostop. Izkorišča časovno lokalnost.

Pri LRU za asociativnost ≥ 4 postane logika težka za realizacijo. Lahko se naredi samo na približno. Pri večjih stopnjah asociativnosti se uporablja naključna strategija. Če je pomnilnik velik in je tudi asociativnost velika, med strategijama sploh ni več razlike.

Pisanje v predpomnilnik

Ker je veliko več dostopov do pomnilnika bralnih, je dobro da ga optimiziramo za branje. A vendar moramo zaradi Amdahlovega zakona realizirati tudi hitro pisanje. Imamo dve strategiji pisanja:

  • Pisanje skozi: vedno se piše tako v predpomnilnik kot tudi v glavnega.
  • Pisanje nazaj: piše se samo v predpomnilnik, torej je vsebina v njem lahko drugačna kot v glavnem pomnilniku. Pri zamenjavi je treba spremenjeni blok zapisati nazaj v glavni pomn. Ponavadi imajo umazani bit v kontrolni informaciji, ki se postavi na 1, če pride do pisanja v ta blok. V glavni pomnilnik je torej treba zapisati le take, ki imajo umazani bit enak 1.

Prednost pisanja nazaj je v tem, da pisanje poteka s hitrostjo, ki jo ima predpomnilnik. Pri več pisanjih v isti blok je potrebno samo eno pisanje v glavni pomnilnik. Ob prenosu bloka nazaj se lahko izkoristi maksimalna hitrost prenosa.

Prednost pisanja skozi je enostavnost in vsebinska skladnost. Ker je pisanje v glavni pomnilnik počasnejše od pisanja v predpomnilnik potrebujemo poseben vmesni pomnilnik - pisalni izravnalnik. Namesto v glavni pomnilnik se piše vanj, tako lahko CPE nadaljuje z delom brez čakanja. Izravnalnik nato poskrbi, da se njegova vsebina prenese tudi v gl. pomn. Sicer ima prostor za več pisanj (8-16), ampak se lahko napolni, tako da mora CPE vseeno čakati. Pisalni izravnalnik je realiziran kot čisti asociativni pomnilnik.


Pisanje v 1 urini periodi: Najprej ločimo kontrolni in podatkovni del pri predpomnilniku, da se lahko primerjanje naslovov in pisanje v PP izvršita v isti urini periodi. Potem vgradimo shranjevalni register - pri pisanjih se ugotavlja zadetek, podatek pa se skupaj z naslovom zapiše v shranjevalni register. Ob zgrešitvi se ob koncu urine periode vsebina registra razveljavi. Ob naslednjem pisanju se veljaven podatek iz shranjevalnega registra zapiše na naslov, ki je v shranjevalnem registru. Istočasno se vanj zapiše že nov podatek z naslovom. Gre v bistvu za cevovodni način pisanja v predpomnilnik.


Pisalne zgrešitve - do njih pride, ko želimo na nek naslov pisati, tega bloka pa ni v predpomnilniku. Pri pisalnih zgrešitvah se uporabljata dve rešitvi:

  • Pisalna zamenjava: pisalne zgrešitve se obravnavajo enako kot bralne. V predpomnilnik se prenese nov blok, ki mu sledi dostop do predpomnilnika. Ta način se lahko uporablja pri obeh strategijah pisanja.
  • Pisanje naokrog: blok se spremeni samo v glavnem pomnilniku

Vrste zgrešitev pri predpomnilniku

  • Obvezne: ob prvem dostopu do neke besede, ker te seveda ni v predpomnilniku. Če bi imeli večje bloke, bi bilo teh zgrešitev manj, vendar s tem povečamo zgrešitveno kazen – ni vredno.
  • Velikostne: ker je predpomnilnik končne velikosti, slej ko prej v njem zmanjka prostora – ne more vsebovati vseh blokov, ki jih med izvajanjem potrebuje. Zato se vršijo zamenjave blokov. Edina rešitev je, da predpomnilnik zvečamo.
  • Konfliktne: pojavijo se samo pri set asociativnih in direktnih predpomnilnikih, ko je v predpomnilniku sicer še dovolj prostora, a ima blok določeno preslikavo na že zaseden set. Teh zgrešitev ne bi bilo, če bi bil predpomnilnik čisti asociativen. Zmanjšamo jih lahko s povečanjem stopnje asociativnosti.

Problem skladnosti v predpomnilniku

Skladnost označuje pojav, da je vsebina nekega bloka v predpomnilniku enaka vsebini istega bloka v glavnem pomnilniku. Ta problem se pojavlja predvsem pri pisanju nazaj, v neki meri pa tudi pri pisanju skozi. Neskladnost povzroča napačno delovanje zaradi prenosov med V/I napravami in glavnim pomnilnikom in zaradi shranjevanja podatkov iz glavnega pomnilnika na disk. Problem neskladnosti, ki ga povzroča V/I naprave lahko rešimo tako:

  • 1. priključimo jih tako da grejo prenosi skozi predpomnilnik: zapletena rešitev, verjetnost zadetka se občutno poslabša – počasnejše delovanje rač.
  • 2. Programska rešitev: pred izvrševanjem V/I prenosov se razveljavi vsebina predpomnilnika ali pa se vsi umazani bloki prenesejo. To je programski način in ne zahteva dodatne logike. To deluje, ker so V/I prenosi redki.
  • 3. Strojne rešitve: z dodatno logiko naredimo mehanizem, ki selektivno razveljavlja ali prazni predpomnilnik – za računalnike, ki imajo V/I procesorje ali več CPE. Nadzor nad prenosi ni več pod kontrolo CPE zato programska rešitev ni možna. Dve rešitvi:
a) Centralni imenik: informacija o naslovih vseh blokov, ki so trenutno v enem od predpomnilnikov je shranjena v centralnem imeniku, ki je vgrajen v krmilnik pomnilnika. Če pride do pisanja v blok, se to registrira v imeniku. Če je ta blok še v drugih predpomnilnikih, krmilnik poskrbi, da se blok zamenja/razveljavi.
b) Vohunjenje (snooping): uporablja se kadar so procesorji in glavni pomnilnik priključeni na isto vodilo, po katerem grejo vsi dostopi do njega. Vsi procesorji znajo vohuniti na vodilu. Procesor, ki spremeni besedo v svojem predpomnilniku pošlje na vodilo njen naslov skupaj z vsebino in signalom. Tako vsi ostali procesorji ugotovijo, če je bila spremenjena beseda, ki se nahaja v njihovem predpomnilniku. Tako jo spremenijo ali pa razveljavijo. Če je bilo samo branje in je bila prebrana ista spremenjena beseda, potem lahko procesor obvesti procesor ki bere, naj opusti branje, zapiše spremenjeni blok v glavni pomnilnik in ga obvesti da naj ponovi branje.


S problemom skladnosti se ukvarjajo tudi skladnostni protokoli, ki določajo kaj naj se zgodi z bloki v predpomnilniku ob dostopu do njih. Med njimi je danes najbolj znan MESI (Modified, Exclusive, Shared, Invalid). Njegovo ime je okrajšava za 4 stanja bloka, ki jih predvideva. Zasnovan je na osnovi vohunjenja. Za programerja je neviden in deluje avtomatsko. Uporablja se v L2 in v operandnem predpomnilniku.

Zmanjševanje verjetnosti zgrešitve

Zmanjšamo jo lahko z večjim predpomnilnikom, z večjo stopnjo asociativnosti, s pravilno izbiro velikosti bloka in dobro zamenjevalno strategijo.

Zmanjševanje zgrešitvene kazni

Zmanjšamo jo lahko z večjim s pametnim vrstnim redom prenašanja besed v bloku in z več nivoji predpomnilnika. Poleg tega imamo še dve zelo pomembni rešitvi:

  • 1. Vnaprejšnji prevzem bloka: velika verjetnost je da bo poleg bloka, ki ga prevzamemo potreben tudi naslednji višji (zaradi zaporedne lokalnosti). Prebere se še višji blok in se shrani v bralni izravnalnik. To je učinkovito, le če je prenos dveh blokov približno enako hiter kot prenos enega.
  • 2. Neblokirajoči predpomnilnik: ob zgrešitvi se CPE ne ustavi, ampak medtem ko se vrši zamenjava bloka vnaprej ali špekulativno izvršuje druge ukaze. Špekulativno zato, ker je možno da se lahko rezultati tako izvedenih ukazov smiselno uporabijo. Smiseln je samo, če povezava med CPE in gl. pom. omogoča, da se prenaša več blokov naenkrat.

Pomnilniško prepletanje

Ne glede na to kakšen predpomnilnik uporablamo ima zmanjševanje št. dostopov do glavnega pomnilnika spodnjo mejo, saj je enkrat treba dostopati do njega. Page mode način do neke mere pomaga. Preostane pa nam še to, da povečamo število naenkrat prenesenih besed. To lahko naredimo s:

  • 1. Širšimi podatkovnimi potmi do glavnega pomnilnika – naenkrat se dostopa do 8,16,32... sosednjih pomnilniških besed. Tu govorimo o širini pomnilnika. Če je enaka velikosti bloka, se 1 blok lahko prenese v enem dostopu. Za izvedbo potrebujemo multiplekser med CPE in predpomnilnikom, kar lahko poveča čas dostopa pri zadetku.
  • 2. Pomnilniškim prepletanjem: glavni pomnilnik razdelimo na m samostojnih delov – modulov. Imamo m-kratno prepletanje. Vsak modul je neodvisen pomnilnik. To pomeni da lahko poteka največ m dostopov istočasno. Pri branju se vsako urino periodo enemu modulu pošlje naslov, moduli shranijo naslov in opravijo branje in vsako urino periodo se podatek posreduje CPE.

Veliki računalniki uporabljajo dostop do modulov po širokih podatkovnih poteh. Ti 2 opciji pa ne moreta zmanjšati začetne zakasnitve (latence), ki je značilnost DRAM pomnilnikov. Z njima pa vseeno lahko dosežemo, da se v enakem času prenese daljši predpomnilniški blok.


Pomnilniško prepletanje je koristno tudi, ker omogoča istočasne dostope do glavnega pomnilnika na računalnikih, ki imajo več CPE / V/I procesorje. Pomembno nalogo ima tukaj krmilnik pomnilnika, ki iz pomnilniških naslovov, ki jih dajo procesorji ugotovi na kateri modul se nanašajo. Dostop se opravi takoj, ko postane modul prost. Če želi dostopati prej, imenujemo to konfliktni dostop.

Pomembno je, da zagotovimo da so podatki po modulih čimbolj enakomerno razporejeni.

Najpogostejše prepletanje je spodnje prepletanje, pri katerem je modul določen s spodnjimi biti pomnilniškega naslova. To prepletanje omogoča izkoristiti zaporedno (prostorsko) lokalnost. Verjetnost, da se bodo zaporedni naslovi nanašali na različne module je precejšnja. Pri takem prepletanju in pri m modulih je v povprečju možno √m istočasnih dostopov. Temu ustrezno se poveča tudi hitrost prenosa informacije v/iz glavnega pomnilnika.

Vrste navideznega pomnilnika

Ostranjevanje

Je najstarejša vrsta navideznega pomnilnika – računalnik Atlas (prvi skladovni). Pomožni pomnilnik je razdeljen na bloke s fiksno dolžino – strani. Vse strani skupaj sestavljajo pomožni pomnilnik. Podobno je razdeljen tudi glavni pomnilnik – na okvire strani. Vsako stran je mogoče prenesti v poljuben okvir. Tipične velikosti strani danes so od 4KB do 16KB. Vsak program zaseda določeno število strani. Ker je velikost programa redko večkratnik velikosti strani, je v povprečju neizkoriščene pol strani na program – tej neizkoriščenosti pravimo NOTRANJA FRAGMENTACIJA. Preslikovalna funkcija je pri ostranjevanju definirana s pomočjo posebne tabele – tabele strani.

Vsaki strani pripada ena polje – deskriptor strani. Fizični naslov določimo s pomočjo navideznega tako, da ga razbijemo na dva dela. Spodnji del (p bitov) določa naslov besede znotraj strani. Zgornjih n-p bitov določa številko strani. Do deskriptorja pridemo tako, da seštejemo številko strani z registrom tabele strani, ki vsebuje njen naslov. Informacijo v deskriptorju sestavljajo:

  • Veljavni bit V: če je 1, so parametri v deksriptorju veljavni
  • Prisotni bit P: če je 1, je stran v enem od okvirov v glavnem pomnilniku – stran je aktivna. Imamo zadetek, sicer imamo zgrešitev – napako strani.
  • Zaščitni ključ RWX je oblika zaščite strani (tudi segmentov). Sestavljen je iz več bitov, ki povejo kakšna vrsta dostopa je dovoljena in od koga.
  • Umazani bit C je vedno 0, ko se stran prenese v okvir. Če pride med izvajanjem do spremembe v strani se postavi na 1.
  • Številka okvira FN podaja številko okvira, v katerem je stran. Veljavna je samo, če je P=1. Pri dovoljenem dostopu se k FN X 2^p prišteje naslov znotraj strani, ki jih določa zadnjih p bitov navideznega naslova. Dobljena vsota je fizični naslov besede, do katere je zahtevan dostop.

Tako preslikovanje imenujemo linearno preslikovanje – naslovi se širijo brez omejitev pri prehodu iz enega na drugega. Naslovni prostor je linearen oz. raven - flat. Delitev na strani je za uporabnike nevidna.

Tako preslikovanje se v resnici uporablja v bolj zapleteni obliki, ki vsebuje več nivojev tabel strani. Šele preslikovanje v tabeli strani nivoja 1 da kot rezultat fizični naslov. Prednost večnivojskega preslikovanja je v zmanjšanju prosora, ki ga zasedajo tabele strani.

Dobra lastnost ostranjevanja je njegova preprostost, a ne uporablja zelo dobrih načinov za zaščito. Več programov si ne more deliti istega prostora. Vsebina blokov nima svojega pomena! – delitev na bloke je povsem mehanična.

Premetavanje strani - stanje, ko se zaradi stalnega velikega števila napak strani koristno delovanje računalnika (gledano iz oči uporabnika) skoraj ustavi. Večji del časa se le prenašajo strani, uporabniški programi pa praktično stojijo, saj se le prenašajo informacije med pomožnim in glavnim pomnilnikom. Do tega lahko pride pri vseh navideznih pomnilnikih!


Segmentacija

Pomnilniški prostor je razdeljen na segmente. Za razliko od strani, so segmenti različno veliki - dolžina ni fiksna. Druga razlika je, da ima vsak segment svoj pomen. Število in velikost segmenta se med izvajanjem programov lahko spreminjata. Tudi to je razlika z ostranjevanjem. Tu nimamo ničesar, kar bi ustrezalo tabeli strani, saj so različno dolgi. Namesto tega se vsak segment lahko prenese na poljuben naslov v glavnem pomnilniku.

Pomen segmentov za program: Program si lahko predstavljamo koz zbirko modulov, ki so sestavleni iz seznamov, polj, podprogramov. Prevajanje pretvori tak modul v strojni modul, ki se ga da povezati z drugimi, naložiti v pomnilnik in izvajati. Tak modul pa je ravno segment. Program je tu videti kot zbirka med seboj povezanih segmentov. Pri prehajanju iz enega segmenta v drugega so običajno predpisane omejitve. Segment ne more dostopati do podatkov v drugem tako, kot dostopa do lastnih. To lahko naredi le na predpisan način, ki ima tudi veliko vrsto preverjanj. To pomeni, da lahko na vsak segment gledamo kot na svoj pomnilniški prostor, ki je sicer povezan z drugimi, ampak je od njih neodvisen. Zato se segmentacija označuje tudi kot večdimenzionalni navidezni pomnilnik. Vsak segment ima svoje simbolično ime – simbolična segmentacija.

Drugače kot pri ostranjevanju, so za programerja segmenti vidni - imajo svoj pomen.

Največja velikost segmenta in največje število le-teh sta zaradi praktičnih razlogov omejena.

Preslikovalna funkcija je realizirana preko tabele segmentov. Velikost tabele ni znana vnaprej. Običajno ima lahko vsak program svojo tabelo segmentov. Vsak segment ima v tabeli svoj deskriptor. Kot pri ostranjevanju spodnjih s bitov določa naslov besede znotraj segmenta zgornjih n-s bitov pa številko segmenta. Do naslova segmenta pridemo tako, da številko segmenta seštejemo z vsebino v registru tabele segmenta (naslov tabele) in tako pridemo do naslova segmenta. K temu naslovu se prišteje še relativni naslov besede (ne doda kot pri ostranjevanju).

Parametri v deskriptorju so podobni kot pri ostranjevanju:

  • Prisotni bit P: če je segment v glavnem pomnilniku je 1
  • Zaščitni ključ RWX: enako kot pri ostranjevanju, vendar je zaščita popolnejša, ker vemo kaj je v segmentu. Določene dele programa lahko zaščitimo tudi pred samim seboj.
  • Umazani bit C se postavi na 1, če je prišlo do spreminjanja segmenta medtem, ko je bil v glavnem pomnilniku.
  • Velikost segmenta L vsebuje trenutno velikost merjeno v številu besed. Največja velikost je 2^s besed, zato mora biti parameter L dolg s bitov. Pri vsakem dostopu se s-bitni naslov znotraj segmenta primerja z L, če je večji imamo napako – sproži se past.
  • Naslov segmenta SA vsebuje fizični naslov segmenta v glavnem pomnilniku.
  • lahko imamo tudi deskriptor G, ki pove ali je segment lokalen(pripada samo enemu programu) ali globalen(do njega lahko dostopajo vsi programi).

Segmente vseh programov, ki se trenutno izvajajo imenujemo obstoječi segmenti. Običajno imamo v okviru OS tabelo obstoječih segmentov. Več programov lahko uproblja isti segment.

Tudi pri segmentaciji lahko pride do premetavanja, vendar je tu drugače. Vsak segment se mora prenesti v dovolj velik zvezen prostor. V večini primerov, ta prostor ne bo točno tako velik kot segment. V pomnilniku bodo nastale luknje, katerih vsota je lahko velika za nov segment. Temu pojavu pravimo ZUNANJA FRAGMENTACIJA. Pri ostranjevanju je ni, ker so strani enako velike. Tukaj pa ni notranje, saj so segmenti enako veliki kot programski moduli. Problem je v tem, da pri notranji fragmentacija poznamo njeno povprečno in tudi največjo velikost, zunanja pa se stalno spreminja in jo je zato težko nadzorovati. Imamo pa tri algoritme, s katerimi poskušamo rešiti problem zunanje fragmentacije:

  • Najboljše ujemanje – poiščemo najmanjšo luknjo v katero bi šel naš segment
  • Najslabše ujemanje – poiščemo največjo luknjo in vanjo damo segment
  • Prvo ujemanje – segment damo v prvo luknjo, ki je dovolj velika

Ne glede na to, bo pomnilniški prostor zelo fragmentiran po nekem času, zato bo potrebno opraviti strnjevanje pomnilnika. S tem strnemo vse luknje v en prazen prostor. Zaradi teh težav in zato, ker je potrebno prenesti cel segment tudi ko se uporabi samo nek del, se segmentacija v čisti obliki ne uporablja dosti.

Segmentacija z ostranjevanjem

Z njo želimo izkoristiti prednosti segmentacije, vendar brez zunanje fragmentacije. Vsak segment razdelimo na strani, kar imenujemo linearna segmentacija. Ta rešitev je boljša, saj ni več potrebno, da je glavnem pomnilniku vedno cel segment – v njem so samo tiste strani, ki se trenutno uporabljajo.

Glavni pomnilnik je razdeljen na okvire strani. Navidezni naslov je sestavljen iz treh delov: številke segmenta, številke strani in naslova besede znotraj strani. Najprej se seštejeta vsebina registra tabele segmenta (naslov tabele segmenta) in (n-s) bitna številka segmenta iz virtualnega naslova. V deskriptorju segmenta se vzame naslov tabele strani (PTA) in se sešteje s (s-p) bitno številko strani v segmentu. Poleg tega se preveri, če je številka strani ta številka primerja z dolžino segmenta, ki je v kontrolnih bitih deskriptorja segmenta (bit L). Če je Številka večja, se sproži past. Sicer dostopamo do elementa tabele strani segmenta, do deskriptorja naše strani v segmentu, kjer je poleg kontrolnih bitov tudi FN (številka okvirja). To številko pomnožimo z 2^p in jo prištejemo zadnjim p bitom iz navideznega naslova – naslovu besede znotraj strani.

Notranja in zunanja fragmentacija

Glej Ostranjevanje in Segmentacija

Kako pospešiti preslikovanje (TLB)

Pri vsakem dostopu (tudi če podatek ni v fizičnem pomnilniku) je potrebno narediti preslikavo navideznega naslova v fizični naslov. To pomeni, da sta pri vsakem pomnilniškem dostopu potrebna najmanj dva dostopa:

  • dostop do tabele strani v glavnem pomnilniku in
  • dostop do fizičnega naslova kjerkoli že je

Če imamo segmentacijo z ostranjevanjem ali večnivojske tabele se to poveča na 3 ali 4 dostope. Zaradi tega imajo računalniki z navideznim pomnilnikom v CPE vgrajen mehanizem, ki skrajša čas za preslikovanje – majhen predpomnilnik, ki vsebuje nazadnje uporabljene deskriptorje.

Pravimo mu preslikovalni predpomnilnik (TLB - Translation Lookaside Buffer). Ne smemo ga zamenjati z navadnim predpomnilnikom. Imajo ga vsi računalniki z navideznim pomnilnikom, saj bi bil sicer prepočasen. V njem so vedno deskriptorji - podmnožica le teh iz tabele strani in ne ukazi ali operandi. Dolžina bloka je običajno enaka 1 - vsak blok vsebuje 1 deskriptor.

Pri segmentaciji z ostranjevanjem imamo običajno dva TLB-ja. Eden vsebuje deskriptorje segmentov, eden pa deskriptorje strani. Če je preslikava večnivojska je dovolj, da se v TLB prenese samo deskriptor najnižjega nivoja.

TLB ima naslednje lastnosti:

  • velikost 32 do 2048 deskriptorjev
  • 1 do 2 deskriptorja na blok (vsak 4-8 bajtov)
  • 0,5 do 1 urina perioda za dostop
  • 10 do 100 period zgrešitvene kazni
  • od 99 do 99,9% verjetnost zadetka

Dostop do TLB in preslikovanje tečeta paralelno z dostopom do predpomnilnika. Če imamo ločen operandni in ukazni predpomnilnik moramo imeti tudi dva TLB-ja. Brez obeh ne bi bilo mogoče istočasno dostopati do dveh predpomnilnikov.


Pri dostopu do navideznega naslova torej lahko pride do treh vrst zgrešitev: v TLB, v predpomnilniku in v glavnem pomnilniku (napaka strani ali segmenta).

Serviranje napake strani / segmenta

Zgrešitev v TLB pomeni eno od dveh možnosti:

1. Stran ali segment je v glavnem pomnilniku, v TLB se prenese iz tabele strani/segmentov nov deskriptor in naredi se dostop do strani
2. Strani ali segmenta ni v glavnem pomnilniku. Sproži se past in operacijski sistem poskrbi za prenos strani/segmenta z diska in za spremembo deskriptorja te strani v tabeli strani

Kdaj katera? Če je bil bit P v deskriptorju enak 1, vemo da se je zgodila prva možnost, sicer druga.

Ukaz, ki ga trenutno izvajamo moramo prekiniti s pastjo - med izvajanjem ukaza in ne po saj se ukaz ne more izvesti! Imamo dve možnosti. Lahko obnovimo stanje, lahko pa ponovimo ukaz, s tem da moramo paziti da resetiramo vse kot je bilo prej. Na RISCih uporabljamo ponovitev, na CISCih pa je na nekaterih ukazih celo ne smemo uporabiti, ker bi bilo potem delovanje napačno. To je mogoče rešiti tako, da CPE pri tistih ukazih, ki bi pri ponovitvi povzročili napako preveri, če bo prišlo do napake strani.

Servisni program mora najprej shraniti stanje programa, nato mora ugotoviti navidezni naslov na katerem je prišlo do napake. Če je bila napaka pri ukazu, je ta naslov shranjen v PC, če je bila pri operandu se lahko določi z analizo ukaza. Ko pozna naslov z uporabo številke strani, ki je v njem, dostopa do tabele (strani) in dobi naslov te strani na disku. Določi kateri od okvirov v glavnem pomnilniku se bo zamenjal. Če je umazani bit v tem okviru postavljen, se mora shraniti nazaj na disk. Stran se prenese z diska nazaj v izbrani okvir. Vsebina deskriptorja v tabeli strani se spremeni.

V tem času (več deset milijonov urinih period) CPE ne stoji. Izvajati se začne nek drug program. Ko je prvoten program spet sposoben za nadaljevanje se lahko začne izvajati naprej, lahko pa počaka da pride do napake v trenutnem programu.

Načini za zmanjševanje prostora za tabele strani/segmentov

Prostor, ki ga zasedajo tabele ni mogoče uporabiti za programe – prostor je neizkoriščen (okoli 64MB pri 36-bitnem navideznem naslovu, 32-bitnih deskriptorjih in 4kB velikosti strani). Potrebujemo pametnejšo organizacijo tabel, in sicer več možnosti:

  • 1. Večnivojske tabele strani, katerih vsak del je lahko v svojem delu pomnilnika (ali celo v pomožnem pomnilniku). Tudi če bi bili vsi njeni deli v glavnem pomnilniku, bi bila izkoriščenost veliko večja. (80x86, Motorola 680xx, DEC Alpha)
  • 2. Uporaba invertirane tabele strani, kar pomeni da imamo v tabeli samo tiste strani, ki so trenutno v glavnem pomnilniku. Problem je v tem, da iz številke strani ni razvidno, ali in kje stran v glavnem pomnilniku je, zato moramo uporabit razprševalno/hash funkcijo. Ta preslika številko strani v št. okvira. Če za neko številko strani preslikava obstaja, se dobljena št. okvira uporabi kot indeks za tabelo strani, sicer imamo napako strani. (Power PC)
  • 3. Tabele lahko shranjujemo v navideznem pomnilniškem prostoru. Če zagotovimo, da so nekateri programi in nekatere tabele vedno v glavnem pomnilniku (del OS), je večina tabel strani lahko v navideznem pomnilnku. Ta rešitev se uporablja skupaj z večnivojskimi tabelami. Število napak strani se sicer nekoliko poveča, vendar se ta rešitev vseeno veliko uporablja.

Izbira velikosti strani

Pri čisti segmentaciji se to vprašanje ne pojavlja. Drugače pa je vprašanje podobno vprašanju kako velik naj bo predpomnilniški blok. Na odločitev o velikosti strani vplivajo:

  • 1. Velikost sektorja na magnetnem disku: pri prenosu z diska se vedno prenese najmanj en sektor (512 bajtov). To pomeni, da je izkoristek najboljši, če je velikost strani večkratnik velikosti sektorja.
  • 2. Izkoriščenost pomnilnika: nekatere dele pomnilnika uporabnik nikoli ne more uporabiti za svoje programe. Mednje spadajo deli strani, ki jih ne zapolni program, ker je njegova dolžina le malokdaj večkratnik velikosti strani - notranja fragmentacija, zaradi katere bo del pomnilnika povprečno v velikosti polovice strani neizkoriščen. Z zmanjševanjem strani se zmanjšuje tudi notranja fragmentacija, vendar se istočasno povečuje velikost tabel.

Torej bo v povprečju pomnilniški prostor, ki ga ni mogoče uporabiti odvisen od velikosti segmenta (programa).

Vzemimo da je velikost segmenta Ss, velikost strani pa Sp. Pri vsakem segmentu je torej neizkoriščenih N besed: N = Sp / 2 + c * Ss / Sp, pri čemer je c velikost deskriptorja. Prvi člen predstavlja notranjo fragmentacijo, drugi pa prostor, ki ga zaseda tabela strani. Torej lahko definiramo izkoristek segmenta: u = Ss / (N + Ss) = 2SsSp / (Sp2 + 2Ss(c + Sp)). Odvajamo po Sp, pri maksimumu mora biti odvod enak 0. Iz tega dobimo, da mora biti optimalna velikost strani enaka .

Ekstrem je zelo neizrazit, zato lahko kar precej odstopimo od njega, pa bo izkoristek še vedno dokaj optimalen.

  • 3. Število napak strani - je najpomembnejši parameter zaradi premetavanja – delovanje računalnika se lahko zreducira na menjanje strani v fizičnem naslovnem prostoru. Lahko ga samo ocenimo z analizo dogajanja med delovanjem računalnika. Opazujemo dva zaporedna naslova A(i) in A(i+1). Imamo tri možnosti:
1. Če sta oba naslova ukazov in je A(i+1)=A(i)+d, je d v večini primerov zelo majhen
2. Če sta oba naslova operandov je analogno 1.
3. Če je A(i) ukaz, A(i+1) pa operand ali obratno je d velika številka. Razlog je v načinu programiranja – podatki so na enem koncu ukazi pa na drugem.

Če se stran povečuje zajame prvo točko, verjetnost zgrešitve za ta dva primera bo večja, obenem pa bo v tretji točko zgrešitev naraščala, saj se število strani zmanjšuje, kar pa zajame manjšo časovno lokalnost. Torej bo do neke mere povečevanje strani dobro, potem pa se bodo zgrešitve začele pojavljati pogosteje. Najpomembneje je torej, da čimbolj zmanjšamo število napak strani.

Omeniti moramo še to, da je čas za prenos večjega bloka zanemarljivo večji od časa za prenos manjšega (pri predpomnilniku temu ni tako).

Strategije pri uporabi navideznega pomnilnika

Operacijski sistem igra pri navideznem pomnilniku pomembno vlogo. Omogočiti mora, da se dana množica programov izvrši čim hitreje. Ubadati se mora z naslednjimi problemi:

1. Koliko okvirov strani v glavnem pomnilniku naj ima nek program,
2. Kdaj, katere in koliko strani naj se prenese iz pomožnega v glavni pomnilnik
3. Katere strani naj se prenesejo iz glavnega nazaj v pomožni pomnilnik

Ta pravila imenujemo dodeljevalna, polnilna in zamenjevalna strategija. Strategije se nekoliko razlikuje od tistih pri predpomnilniku, saj je tam osnovni cilj povečati verjetnost zadetka, tu pa moramo povečati izkoriščenost računalnika. Poleg tega se pri navideznem pomnilniku uporabljajo programsko realizirane strategije, saj je časa veliko več. Označujemo jih kot strategije za upravljanje s pomnilnikom.

V danem trenutku je stopnja multiprogramiranja d (število aktivnih programov). Vsakemu programu pripada določeno število okvirov v glavnem pomnilniku – okviri so v t.i. rezidenčni množici. Pri uporabi dodeljevanje strategije fiksna razdelitev je število okvirov, ki so dodeljeni programu fiksno in se med izvajanjem ne spreminja. Boljši način je spremenljiva razdelitev, ki ta prostor dinamično spreminja. Poleg tega lahko razdelitev razdelimo še na globalno in lokalno. Medtem ko lokalna pri odločanju upošteva samo trenutne lastnosti rezidenčne množice programa, v katerem je prišlo do napake, globalna upošteva zgodovino rezidenčnih množic vseh programov.

Pri polnjenju okvirov imamo dve strategiji: polnjenje na zahtevo prenese stran v okvir, ko pride do zgrešitve (kot pri predpomnilniku), vnaprejšnje polnjenje pa prenese poleg nje še sosednje strani, za katere predvideva, da se bodo v bližnji prihodnosti uporabljali.

Pri izbiri ustreznega algoritma moramo najprej analizirati dogajanje med izvajanjem programa. Stopnja lokalnosti ni konstantna, ampak jo lahko razdelimo na faze, v katerih se delovna množica (Working Set) spreminja počasi, saj je stopnja lokalnosti visoka in na prehode, za katere je značilna hitra sprememba delovne množice. Ker je čas v fazah veliko daljši, kot prehodih, predstavlja število napak v prehodih njihovo večino. Torej je vnaprejšnje polnjenje boljše.

Za napovedovanje kako algoritmi za dodeljevanje, polnjenje in zamenjevanje vplivajo na število napak strani je koristna funkcija frekvence napak strani, ki podaja število napak strani na enoto navideznega časa (čas, ki teče samo takrat, ko ni zamenjevanja strani). Ugotovimo lahko, da bo najboljši agoritem tisti, ki da najmanjšo vrednost f za določeno velikost gl. pomn. Namesto funkcije f se veliko uporablja tudi t.i. življenjska funkcija e, ki podaja povprečen navidezen čas med dvema napakama strani za poljuben program in je enaka 1/f.

Poseben primer pri dodeljevanju pomnilnika je izbira stopnje multiprogramiranja d. Če je d premajhen je računalnik neizkoriščen, če je prevelik se število okvirov za program zmanjša in število napak strani se zato močno poveča. Problem izbire pravega d je znan kot problem optimalnega obremenjevanja.

Če je L(d) povprečni navidezni čas med dvema napakama strani, pri stopnji multiprogramiranja d in je L(d) = tb (tb – čas za prenos ene strani), pride do premetavanja. Naslednja napaka se zgodi še preden je bila servisirana prejšnja. Ta pojav je odvisen od velikosti glavnega pomnilnika M. Pri velikem M je področje stopnje d lahko veliko večje kot pri majhnem . Povečevanje glavnega pomnilnika je smiselno do velikosti, ko se izkoristek približa 1. Izkoristek računalnika bo največji, če se bo d prilagajala spremembam v trajanju povprečnega časa med dvema napakama tako, da je čas L(d) nekoliko večji kot tb – L=tb kriterij.

Algoritmi za optimalno uporabo navideznega pomnilnika

Algoritem mora upoštevati ugotovitve iz prejšnjega poglavja. Najpreprosteje je narediti dober polnilni algoritem: stran, pri kateri je prišlo do napake, je potrebno vedno prenesti v glavni pomnilnik, lahko tudi sosednje strani. Dodeljevalne in zamenjevalne strategije s fiksno dodelitvijo in lokalnim delovanjem se zaradi slabosti ne uporabljajo.

Zagotoviti moramo da se stopnja multiprogramiranja d dinamično prilaga spremembam lokalnosti. Ko je ta visoka, ima lahko program malo okvirov strani in ni veliko napak. Pri prehodih med fazami potrebuje program za isto število napak veliko okvirov strani. Pri d aktivnih programih je velika verjetnost, da zmanjšanje stopnje lokalnosti nekaterih programov sovpada s povečanjem lokalnosti drugih. Torej mora algoritem delovati tako, da vzame okvire programom, ki imajo visoko lokalnost in jo da tistim z nizko. Algoritem mora čimbolj uspešno preprečiti premetavanje – z zmanjšanjem d, vendar d ne sme biti prenizka, ker zaradi tega trpi izkoristek računalnika.

Dva znana algoritma za dodeljevanje in zamenjevanje vse to upoštevata (pri polnjenju je rešitev preprosta – OBL algoritem, ki se uporablja v kombinaciji s sledečima):

  • WS (Working Set) algoritem - uporablja pojem delovne množice strani W(t,T), ki je definirana kot množica tistih strani, ki jih je program naslovil v časovnem intervalu (t-T,t), pri čemer je t navidezni čas, T pa parameter. Sestavljajo jo številke strani. Algoritem se aktivira za vsak program, ko je intervala konec. Ob prvem aktiviranju dodeli programu fiksno število strani. Kasneje dodeljuje programu toliko strani, kot je okvirov v delovni množici. Če je razpoložljivo število okvirov premajhno, se program izloči iz množice aktivnih (d <= d-1). Ko število prostih okvirov preseže določeno vrednost se d poveča. Torej algoritem upošteva spremembe v lokalnosti, zato daje zelo dobre rezultate, vendar je njegova realizacija nerodna, saj ga je treba aktivirati vsakič, ko za nek program preteče čas T; za vsak program teče t drugače. Aktiviranje poleg tega običajno ne bo sovpadlo z napako strani. Močno bi poenostavili realizacijo, če bi algoritem zagnali ob napakah strani, ko je prenos vedno potreben. Algoritem, ki deluje na ta način je:
  • PFF (Page Fault Frequency), ki je v bistvu poenostavljen WS algoritem. Še vedno imamo parameter T, vendar se algoritem aktivira samo ob napakah. Ob vsaki napaki strani se v glavni pomnilnik prenese potrebna stran. Število okvirov programa se poveča za 1. Če pri tem zmanjka prostih okvirov, se program izloči iz množice aktivnih. Potem se navidezni čas od prejšnje napake strani se primerja s trenutnim časom in če je manjši od T algoritem ne naredi ničesar drugega, sicer se programu dodeli toliko okvirov strani, kot jih je v delovni množici programa. Vrednost 1/T lahko razumemo kot največjo frekvenco napak strani. Če je frekvenca večja, se število okvirov prilagaja delovni množici ob vsaki napaki. T služi kot varnostni prag, da se število okvirov ne bi prehitro zmanjševalo.
Vzpostavljeno iz »http://www.e-studij.si/UL/FRI/UNI-RI/ARS1/Izpiti/Ustni«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja