Odgovori na ispitna pitanja iz UOAR2

• NE

  A	NE(A)
  1	0
  0	1

• I

  A	B	I(A, B)
  1	1	1
  1	0	0
  0	1	0
  0	0	0

• ILI

  A	B	ILI(A, B)
  1	1	1
  1	0	1
  0	1	1
  0	0	0

• NI (NAND)

  A	B	NI(A, B)
  1	1	0
  1	0	1
  0	1	1
  0	0	1

• NILI (NOR)

  A	B	NILI(A, B)
  1	1	0
  1	0	0
  0	1	0
  0	0	1

• EILI (XOR)

  A	B	EILI(A, B)
  1	1	0
  1	0	1
  0	1	1
  0	0	0

• Preko KNF-a (A ili ne(B)) i (ne(A) ili B)

Navesti osnovne zakone algebre logike

Algebra logike je uređena šestorka \((S, \cdot, +, \bar{}, 1, 0)\)

• \(S\) - neprazan skup
• \(\cdot, +\) - binarne operacije
• \(\bar{}\) - unarna operacija

• \(1, 0\) - izdvojeni elementi skupa \(S\)

  Osnovni zakoni:

  1. Asocijativnost
     • \((x \cdot y) \cdot z = x \cdot (y \cdot z)\)
     • \((x + y) + z = x + (y + z)\)
  2. Neutral
     • \(x \cdot 1 = x\)
     • \(x + 0 = x\)
  3. Komplementarnost
     • \(x \cdot \bar{x} = 0\)
     • \(x + \bar{x} = 1\)
  4. Komutativnost
     • \(x \cdot y = y \cdot x\)
     • \(x + y = y + x\)
  5. Distributivnost
     • \(x \cdot (y + z) = x \cdot y + x \cdot z\)
     • \(x + (y \cdot z) = (x + y) \cdot (x + z)\)

Zbog čega se algebra logike koristi kao osnova savremenih računara?

Iz razloga što je mnogo jednostavnije, stabilnije i jeftinije napraviti fizički uređaj koji ima dva diskretna stanja nego više njih. Takođe, aritmetičke operacije nad binarnim brojevima je jednostavno opisati pomoću algebre logike i samim tim implementirati pomoću logičkih kola.

Šta znači da su dva logička izraza ekvivalentna?

Znači da su im vrednosti pri istim valuacijama promenljivih iste odnosno da za istu kombinaciju vrednosti “ulaznih” promenljivih daju isti “izlaz”

• Literal je logički izraz koji je ili logička promenljiva ili negacija logičke promenljive (eg. \(x, \bar{y}\))
• Elementarna konjunkcija je logički izraz koji se sastoji iz konjunkcije literala (eg. \(x\bar{y}z\bar{p}\))
  • Savršena elementarna konjunkcija sadrži tačno jedan literal za svaku logičku promenljivu (eg. \(P = \{x, y, z\}, S = \bar{x} \cdot y \cdot z\))
• DNF je logički izraz koji se sastoji od disjunkcije elementarnih konjunkcija (eg. \(x\bar{y} + \bar{x} + xyz\))
  • Savršena DNF se sastoji od disjunkcije savršenih elementarnih konjunkcija (eg. \(P = \{x, y, z\}, SDNF = x\bar{y}z + \bar{x}yz + xyz\))

• Literal je logički izraz koji je ili logička promenljiva ili negacija logičke promenljive (eg. \(x, \bar{y}\))
• Elementarna disjunkcija je logički izraz koji se sastoji iz disjunkcije literala (eg. \(x + \bar{y} + z\bar{p}\))
  • Savršena elementarna disjunkcija sadrži tačno jedan literal za svaku logičku promenljivu (eg. \(P = \{x, y, z\}, \bar{x} + y + z\))
• KNF je logički izraz koji se sastoji od konjunkcije elementarnih disjunkcija (eg. \((x + \bar{y}) \cdot (\bar{x} + y) \cdot (x + y + z)\))
  • Savršena KNF se sastoji od konjunkcije savršenih elementarnih disjunkcija (eg. \(P = \{x, y, z\}, SKNF = (x + \bar{y} + z) \cdot (\bar{x} + y + z) \cdot (x + y + z)\))

1. Eleminisanje logičkih konstanti - primena veznika nad 0 i 1 sve dok se izraz ne svede na 0 ili 1 ili ostane bez konstanti
2. De Morganovi zakoni i dupla negacija
3. Distributivnost \(\cdot\) prema \(+\) - nakon ovog koraka dobijamo DNF
   • Za svođenje na KNF važe prethodna dva koraka, dok je treći distributivnost \(+\) prema \(\cdot\)
4. Idempotentnost, neutral, apsorpcija - primenom ovih (i drugih zakona) moguće je dodatno minimizovati DNF

Šta je logička funkcija i koliko ima funkcija reda \(n\)?

Logička funkcija je svako preslikavanje \(f: \{0, 1\}^{n} \rightarrow \{0, 1\}\) koja logičke vrednosti \((x_{1}, x_{2}, ..., x_{n})\) slika u logičku vrednost \(y \in \{0, 1\}\). Kardinalnost domena logičkih funkcija reda \(n\) je \(2^{n}\), dok je kodomena \(2\), dakle, pošto se svaka funkcija iz domena može slikati u dve vrednosti u kodomenu, postoji \(2^{2^{n}}\) funkcija reda \(n\)

Šta je potpun sistem veznika? Navesti bar tri primera potpunih sistema logičkih veznika

Potpun sistem veznika predstavlja skup veznika pomoću kojeg je moguće predstaviti svaku logičku funkciju. Primeri:

1. I, ILI, NE
2. I, NE
3. ILI, NE
4. NI (Šeferov veznik: \(\uparrow\))
5. NILI (Pirsov/Lukašijevičev veznik: \(\downarrow\))

• NE(x) = NI(x, x)
• I(a, b) = NE(NI(a, b)) = NI(NI(a, b), NI(a, b))
• ILI(a, b) = NE(I(NE(a), NE(b))) = …

Ukratko objasniti kako se proizvoljna logička funkcija može izraziti u obliku izraza u savršenoj DNF

Čitajući tablicu logičke funkcije, ako je izlaz za neku valuaciju 1, onda na našu savršenu DNF formulu dodajemo novi konjunkt koji se sastoji iz konjunkcije literala koji za tu valuaciju daju vrednost 1.

Šta je minimizacija logičkih izraza i zbog čega nam je značajna?

Minimizovati logički izraz znači pronaći logički ekvivalentan izraz koji sadrži najmanji mogući broj veznika.

Najčešće nam koristi pri dizajnu logičkih kola kako bismo smanjili cenu proizvodnje, ali suštinski može da služi za rešavanje mnogo šire grupe problema koji se mogu mapirati u SAT problem.

Na primeru objasniti metod algebarskih transformacija za minimizaciju logičkih izraza.

Koristimo dva pravila:

1. Grupisanje: \[ K_{1} = x \cdot K' \\ K_{2} = \bar{x} \cdot K' \\ \downarrow \\ K = K'(x + \bar{x}) = K' \\ \]
2. Udvajanje:
   • U slučaju da imamo konjunkte \(K_{1}, K_{2}\) nad kojima bismo mogli da primenimo grupisanje sa \(K\), onda dupliramo \(K\) da bismo mogli da grupišemo sa oba

Primer:

\[F(x, y, z) = x\bar{y}z + \bar{x}\bar{y}z + x\bar{y}\bar{z}\]

Možemo grupisati prvi i drugi kao i prvi i treći, tako da ćemo primeniti prvo udvajanje pa tek onda grupisanje

\[F(x, y, z) = x\bar{y}z + \bar{x}\bar{y}z + x\bar{y}z + x\bar{y}\bar{z}\] \[F(x, y, z) = \bar{y}z(x + \bar{x}) + x\bar{y}(z + \bar{z})\] \[F(x, y, z) = \bar{y}z(x + \bar{x}) + x\bar{y}(z + \bar{z})\] \[F(x, y, z) = \bar{y}z + x\bar{y}\]

Objasniti način upotrebe Karnoovih mapa za minimizaciju logičkih izraza. Primer.

Karnoove mape predstavljaju grafički metod za minimizaciju logičkih izraza koji funkcioniše po principu grupisanja. Nakon što nacrtamo tabelu gde se susendna polja (susedstvo se gleda kao da je tabela zapravo površina torusa) razlikuju za jednu vrednost (Grejov kod) popunimo mesta koja u tabeli daju \(1\) kao rezultat. Minimizujemo tako što prvo pokušamo da obuhvatimo sve \(1\) u pravougaonik od \(16\) elemenata, zatim redom \(8\), \(4\), \(2\), \(1\). Posmatramo promenljive u okviru jednog pravougaonika koje se nisu promenile i njih stavljamo u finalnu minimizovanu DNF formulu.

Objasniti metodu Kvin-Meklaskog za minimizaciju logičkih izraza. Primer.

Metoda Kvin-Meklaskog je metoda minimiacije logičkih izraza koja je pogodna za implementaciju na računaru.

1. Na ulazu dobijamo funkciju u SDNF. Sortiramo rastuće savršene konjunkcije po broju neinvertovanih literala i izdelimo ih u klase, gde \(i\) -ta klasa sadrži SK koji imaju \(i\) neinvertovanih literala.
2. Vršimo grupisanje elemenata iz \(i\) -te sa elementima iz \(i + 1\) -ve klase, i rezultat čuvamo za sledeću iteraciju. Grupisanje je moguće ako se elementi koji se porede razlikuju samo na jednom mestu. Ovo radimo sve dok je moguće grupisati.
3. Formiramo tabelu prostih implikanata (vidi primer). Identifikujemo bitne proste implikante.

Kako se upotrebljavaju Karnoove mape u prisustvu nebitnih vrednosti? Primer.

Kada imamo nebitne (don’t care) vrednost, njih možemo da tretiramo onako kako nama odgovara, odnosno ako nam omogućavaju da zaokružimo veću površinu tretiramo ih kao \(1\), u suprotnom nema potrebe da ih zaokružimo.

Kako se metod Kvin-Meklaskog koristi u prisustvu nebitnih vrednosti? Primer.

U prvoj fazi algoritma se nebitne vrednosti tretiraju kao \(1\), odnosno učestvuju u grupisanju.

U drugoj fazi algoritma se nebitne vrednosti tretiraju kao \(0\), tj. ne navode se u tabeli prostih implikanata.

Šta je Petrikov metod i koja je njegova uloga u okviru metode Kvin-Mekalskog? Primer.

Petrikov metod je metod koji se koristi za pronalaženje najmanjeg podskupa preostalih prostih implikanata u slučaju da neka kolona ostane “nepokrivena” u metodi Kvin-Mekalskog.

Elementarna logička kola (gejtovi) i njihove šematske oznake.

Nacrtati simbol i objasniti funkciju NMOS tranzistora.

NMOS tranzistor ima 3 ulaza:

1. Source - povezan sa negativan napon
2. Drain - povezan na pozitivan napon
3. Gate - odredjuje da li će struja proticati
   • Ako je napon u zoni logičke nule onda je izlaz vrednost visoke impendanse
   • Ako je napon u zoni logičke jedinice onda je izlaz 1

NMOS tranzistor ima ulogu u donjoj mreži (pulldown network) prekidača da poveže masu (ground) sa izlazom da bi u slučaju niske voltaže na izlazu bila 0

Nacrtati simbol i objasniti funkciju PMOS tranzistora.

PMOS tranzistor ima 3 ulaza:

1. Source - povezan sa pozitivan napon
2. Drain - povezan na negativan napon
3. Gate - odredjuje da li će struja proticati
   • Ako je napon u zoni logičke nule onda je izlaz 1
   • Ako je napon u zoni logičke jedinice onda je izlaz vrednost visoke impendanse

PMOS tranzistor ima ulogu u gornjoj mreži (pullup network) prekidača da poveže napajanje (supply) sa izlazom da bi u slučaju visoke voltaže na izlazu bila 1

Implementacija NE kola u CMOS-u

• Ako je ulaz 0 samo iz PMOS-a tranzistora će izlaziti struja koja predstavlja 1
• Ako je ulaz 1 samo iz NMOS-a tranzistora će izlaziti struja koja predstavlja 0
• Dakle, biće upaljen samo tranzistor koji je potreban, čime se postiže ušteda u potrošnji i smanjuje grejanje komponenti.

Implementacija NI i I kola u CMOS-u

Donja mreža se implementira rednim povezivanjem dva NMOS tranzistora čime se postiže da se 0 dobije samo kada su oba ulaza 1

Gornja mreža se implementira paralelnim povezivanjem dva PMOS tranzistora čime se postiže da se 1 dobija samo kada je barem jedan od ulaza 0 (čime se takođe osigurava da pri ulazu 1 1 pušta samo donja mreža “da radi”)

I se dobija tako što se na NI nadoveže NE

Implementacija NILI i ILI kola u CMOS-u

NILI se implementira po istom principu kao NI, s tim što su ovde NMOS tranzistori povezani paralelno, dok su PMOS povezani redno.

Gornja mreža se implementira rednim povezivanjem dva PMOS tranzistora čime se postiže da se 1 dobije samo kada su oba ulaza 0

Donja mreža se implementira paralelnim povezivanjem dva NMOS tranzistora čime se postiže da se 0 dobija samo kada je barem jedan od ulaza 1 (čime se takođe osigurava da pri ulazu 0 0 pušta samo gornja mreža “da radi”)

ILI se dobija tako što se na NILI nadoveže NE

Implementacija EILI kola u CMOS-u

Donja mreža se implementira pomoću 4 redno-paralelna NMOS tranzistora čiji ulazi su \(X\) i \(Y\) s leve i \(\bar{X}\) i \(\bar{Y}\) s desne strane čime se 0 dobija samo akko su \(X\) i \(Y\) isti

Gornja mreža se implementira pomoću 4 redno-paralelna PMOS tranzistora čiji ulazi su \(X\) i \(\bar{Y}\) s leve i \(\bar{X}\) i \(Y\) s desne strane čime se 1 dobijamo samo akko su \(X\) i \(Y\) različiti

Propusni tranzistori i prenosne kapije. Funkcija i uloga.

Propusne tranzistore koristimo u slučaju da nam je potrebno uslovno propuštanje nekog signala. Ako koristimo samo NMOS tranzistor imaćemo problem sa propuštanjem signala 1 jer neće postojati velika razliku u naponu između source-a i gate-a. Analogno za samo PMOS i signal 0.

Da bismo to rešili, koristimo prenosne kapije koje su spoj ova dva propusna tranzistora. Često se koriste i za realizaciju bafera sa 3 stanja.

Šta je bafer sa tri stanja i čemu služi?

Bafer sa 3 stanja je kombinatorno logičko kolo koje služi za pojačavanje stanja i uslovno/kontrolno propuštanje signala.

Implementacija bafera sa tri stanja u CMOS-u.

Implementacija zavisi od toga šta nam je potrebno, i koje signale imamo na raspolaganju. U slučaju da nam nije potrebno pojačavanje signala neće nam trebati dvostruki inverter. Povezujemo ulazni signal, kontrolni signal i njegovu negaciju sa prenosnom kapijom čime i implementiramo bafer sa tri stanja.

Šta je vrednost visoke impendanse i koja je njena uloga u logičkim kolima?

Vrednost visoke impendanse odgovara tipu NULL u nekim višim programskim jezicima, odnosno predstavlja odsustvo vrednosti. Označavamo je sa \(Z\) i koristimo je na primer u slučaju da imamo dva kola koja se povezuju na isti ulaz, kako ne bismo imali vrednosti u konfliktu, jedna od njih ima vrednost visoke impendanse.

Šta je kombinatorno kolo?

Kombinatorno kolo je logičko kolo čije vrednosti na izlazima se mogu sračunati u bilo kom trenutku u zavisnosti od ulaznih vrednosti odnosno prethodne ulazne vrednosti ne utiču na novu izlaznu vrednost.

• Multipleksori (Mux) i demultipleksori (DeMux)
• Koderi i dekoderi
• Komparatori
• Pomerači
• Sabirači i oduzimači

Šta je sekvencijalno kolo? Po čemu se sekvencijalna kola razlikuju od kombinatornih kola?

Sekvencijalno kolo je logičko kolo koje daje izlaz na osnovu trenutnog ulaza i prethodnih izlaza.

Za razliku od sekvencijalnih, kombinatorna kola nemaju interno stanje koje se čuva u memoriji, stoga za isti ulaz uvek daju isti izlaz, što nije slučaj sa sekvencijalnim kolima.

Nacrtati konceptualni dijagram sekvencijalnog kola i objasniti osnovni princip rada.

• \(G\) je kombinatorno kolo koje po principu povratne sprege održava stanje \(S\) (\(G\) se može posmatrati kao vektorska funkcija \(G: X \times S \rightarrow S\), za \(X\) skup svih ulaza i \(S\) skup svih stanja)
  • \(S\) se neće promeniti sve dok se \(X\) ne promeni
• \(F\) je kombinatorno kolo koje transformiše stanje \(S\) u izlaz \(Y\) (\(F\) se može posmatrati kao vektorska funkcija \(F: S \rightarrow Y\) za \(S\) skup svih stanja i \(Y\) skup svih izlaza)

• Nestabilnost sekvencijalnog kola je pojava oscilovanja kola između različitih stanja
• Nederminističnost sekvencijalnog kola je pojava odlaženja u neko “nasumično” stabilno stanje u zavisnosti od fizičkih faktora
• Metastabilnost sekvencijalnog kola je pojava stabilizacije u nekom nevalidnom međustanju

Šta je funkcija (tablica) prelaska sekvencijalnog kola? Navesti primer.

To je vektorska logička funkcija koja deterministički definiše prelaz sa jednog stabilnog stanja u drugo stabilno stanje na osnovu prethodnog stanja i novog ulaza.

Funkcija prelaska za SR reze:

• - označava bilo koju vrednost
• ? označava nedefinisanu vrednost

Objasniti ulogu časovnika. Na koji način časovnik omogućava sinhronizaciju sekvencijalnih kola?

Časovnik istom frekvencijom izbacuje naizmenično signale 0 i 1 što se koristi za sinhronizaciju sekvencijalnih kola. Postavljanjem frekvencije časovnika na dovoljnu tako da najsporije sekvencijalno kolo uspe da se dovede u stabilno stanje, omogućava da se vreme posmatra diskretno, što olakšava rezonovanje o sekvencijalnim kolima i omogućava jednostavnu sinhronizaciju. Svako kolo povezano na časovnik prima njegov signal, i svoje promene vrši isključivo kad signal časovnika to dozvoli.

Objasniti razliku između sinhronih i asinhronih sekvencijalnih kola.

Sinhrona sekvencijalna kola zavise od zajedničkog signala odnosno časovnika, koji svima diktira kada je moguće izvršiti promene stanja, dok asinhrona moraju eksplicitno da naprave komplikovane međusobne veze kako bi uskladile kada je dozvoljeno kojem kolu da izvrši promene stanja.

• Elementi ciklusa časovnika:
  • Pozitivan deo ciklusa = vreme trajanja \(1\)
  • Negativan deo ciklusa = vreme trajanja \(0\)
• Tipovi časovnika:
  • Simetrični = pozitivan deo ciklusa traje isto koliko i negativan
  • Asimetrični = različito traju pozitivan i negativan deo ciklusa
• Frekvencija časovnika = broj ciklusa u jednoj sekundi

• Arhitektura računara je apstraktni model koji opisuje računar iz ugla programera kog zanima koje instrukcije postoje, načini adresiranja, kako se predstavljaju podaci i sl.
  • Odgovara na pitanje Šta radi računar?
• Organizacija računara je implementacija arhitekture gde se posmatraju veze između komponenti, low-level opis kako se određene operacije obavljaju
  • Odgovara na pitanje Kako radi računar?

Šta obuhvata ISA (instruction set architecture)?

ISA obuhvata:

• koje instrukcije postoje
• koji načini upravljanja memorijom hardver podržava (načine adresiranja, virtuelna memorija, konzistentnost memorije)
• kako se predstavljaju podaci

Šta su troadresni procesori? Primer instrukcija i koda. Karakteristike.

Troadresni procesor je procesor koji u instrukciji može da ima tri adrese. Programi na troadresnom računaru su kompaktni, ali same instrukcije mogu da budu glomazne zbog zahteva za čuvanjem 3 operanda.

    ADD C, A, B
    MUL C, A, B

Šta su dvoadresni procesori? Primer instrukcija i koda. Karakteristike.

Dvoadresni procesori su procesori koji mogu da imaju maksimalno dve adrese u instrukciji. Rezultat operacije se upisuje u neku privremenu lokaciju ili u lokaciju jednog od operanada. Smanjuje se dužina programa, ubrzava izvršavanje, ali se ponekad koristi dodatna memorija.

    LOAD T, A ; T = A
    ADD B, T  ; B += T

Šta su jednoadresni procesori? Primer instrukcija i koda. Karakteristike.

Jednoadresni procesori su procesori koji imaju jednu adresu u instrukciji. Operacije koje zahtevaju dva operanda se razrešavaju tako što je druga adresa implicitna. Ovi računari se često obraćaju memoriji za upis i čitanje međurezultata. Programi su dosta dugački i izvršavanje je relativno sporo. Koriste se u situacijama kada je memorija dosta skupa.

    LOAD A  ; učitaj A u akumulator
    ADD B   ; acc += B
    STORE A ; A = acc

Šta su nuloadresni procesori? Primer instrukcija i koda. Karakteristike.

Nuloadresni procesori su procesori gde je maksimalan broj adresa u instrukciji \(0\) osim kod instrukcija PUSH i POP. Takvi procesori implicitno adresiraju svoje operande (često stavljajući ih na stek), što predstavlja veliko ograničenje, pa se koriste samo u specijalnim slučajevima.

    PUSH A
    PUSH B
    ADD
    POP

Objasniti odnos performansi i broja adresa.

Instrukcije sa većim brojem adresa su moćnije, programi kompaktniji i veća je brzina izvršavanja. S povećanjem broja adresa raste i složenost instrukcije što otežava konstrukciju procesora i produžava vreme potrebno za prepoznavanje operacionog koda.

Šta je LOAD/STORE arhitektura? Objasniti.

Sve operacije se izvršavaju isključivo nad registrima procesora. Samo operacije LOAD i STORE mogu da pristupaju memoriji. RISC i vektorski procesori često koriste ovakvu arhitekturu. Prednost je smanjenje složenosti dekodiranja zbog manjeg broja instrukcija.

Karakteristike CISC arhitekture.

Ciljevi:

• složena arhitektura skupa instrukcija
• raznovrsnost operacija
• raznovrsnost načina adresiranja itd.

Posledice:

• Iz velikog skupa instrukcija se koristi oko 20%, dok se ostale ređe koriste
• Otežano dekodiranje zbog velikog broja instrukcija i načina adresiranja

Karakteristike RISC arhitekture.

Ciljevi:

• jednostavna arhitektura skupa instrukcija
• obezbeđivanje minimalnog skupa instrukcija i načina adresiranja
• povećan broj registara koji se mogu koristiti za računanje

Posledice:

• stalniji skup instrukcija
• jednostavno dekodiranje
• kraće trajanje izvršavanja
• jednostavnija implementacija procesora

Odnos RISC i CISC arhitektura.

Danas procesori najčešće predstavljaju hibride ove dve arhitekture.

RISC > CISC:

• jednostavnija konstrukcija zbog manjeg broja instrukcija
• manje vremena je potrebno za izradu samog procesora
• bolje performanse jer je lakše definisati prevodioce koji formiraju optimalniji kod nego CISC procesori

CISC > RISC:

• veća količina softvera je napisana za CISC arhitekturu

• strukturu čine:
  1. operacioni kod
  2. operandi
• format instrukcije određuje način kodiranja ranijepomenutih komponenti u binarnom obliku (implicitno određuje i dužinu instrukcije)

1. Registarski
2. Memorijski
3. Neposredni (konstante)

Objasniti direktno adresiranje memorijskih operanada.

Stvarna adresa se direktno uključuje u instrukciju. Adrese koje se javljaju u ovom načinu adresiranja se još nazivaju i apsolutne adrese. Ovaj način adresiranja je relativno jednostavan jer nema izračunavanja adrese, a prenos operanada zahteva samo jedno referisanje memorije.

Objasniti indirektno adresiranje memorijskih operanada.

Kod indirektnog adresiranja je poznata samo adresa lokacije na kojoj se nalazi adresa operanda, pa se do te adrese dolazi indirektno, tj. instrukcija sadrži binarni kod regista procesora čija se vrednost koristi kao adresa memorijskog operanda. Ovaj način adresiranja zahteva dva ciklusa, jedan za čitanje adrese, drugi za čitanje samog operanda.

• Bazno indeksno adresiranje:
  • Instrukcija sadrži binarne kodove dva registra čije se vrednosti sabiraju i tako dobijamo adresu memorijskog operanda. Obično je vrednost jednog registra fiksirana, a drugi predstavlja indeks koji se pomera i koji je moguće množiti konstantom (npr. \(4\) ili \(8\)) pre sabiranja sa baznim registrom. Korisno je za pristup elementima niza.
• Apsolutno indeksno adresiranje:

  • Bazna adresa ne mora biti u registru, već može biti zadata kao apsolutna adresa na koju se dodaje vrednost indeksnog registra (uz eventualno prethodno skaliranje)

        add eax, table[4 * esi] ; table je niz koji se nalazi u data segmentu
    

Objasniti relativno adresiranje memorijskih operanada.

U ovom načinu za adresiranje se koristi brojač instrukcija (PC program counter) čiji sadržaj se uzima kao početna adresa. U adresni deo instrukcije se upisuje ceo broj koji predstavlja udaljenje od početne adrese. Relativno adresiranje se koristi kada znamo da je ciljana adresa negde u okolini tekuće.

Objasniti načine adresiranja na x86-64 arhitekturi.

Načini adresiranja opisuju kako se određuje operand instrukcije.

• Neposredno za konstante:

      mov rax, 42
  

• Registarsko:

      mov rax, rdi
  

• Memorijsko:

  • Direktno

    .data
        value dw 42
    ...
    f:
        add eax, value
    

  • Indirektno

        ; rdi je pokazivač na prvi element niza
        add eax, [rdi]
    

  • Indeksno

        ; rdi je pokazivač na prvi element niza
        mov rsi, 3
        add eax, [rdi + 4 * rsi]
    

Objasniti načine adresiranja na ARM arhitekturi.

Načini adresiranja opisuju kako se određuje operand instrukcije.

• Neposredno za konstante:

      mov r0, r0, 42
  

• Registarsko:

  • Direktno

        mov r0, r1
    

  • Indirektno

        ; r1 je pokazivač na prvi element niza
        ldr r0, [r1]
    

  • Indeksno

    • Prefiksno bez update-a

          ; r1 je pokazivač na prvi element niza
          mov r2, #3
          ldr r0, [r1, r2, lsl #2] ; r0 = *(r1 + 4 * r2)
      

    • Prefiksno sa update-om

          ; r1 je pokazivač na prvi element niza
          mov r2, #3
          ldr r0, [r1, r2, lsl #2]! ; r1 = r1 + 4 * r2; r0 = *r1;
      

    • Postfiksno sa update-om

          ; r1 je pokazivač na prvi element niza
          mov r2, #3
          ldr r0, [r1], #4 ; r0 = *r1; r1 = r1 + 4;
      

• x86-64
  • mov, movzx, movsx
    • dest
      • registar
      • memorija
    • src
      • konstanta
      • registar

      • memorija

            mov dest, src ; kopira iz src u dest
        
            movzx dest, src ; kopira iz src u dest i proširuje 0
        
            movsx dest, src ; kopira iz src u dest i proširaje znakom
        

  • lea
    • dest
      • registar
    • src
      • konstanta
      • registar

      • memorija

            lea dest, src ; kopira adresu od src u dest
        

• ARM
  • ldr/str
    • ldr: Učitava vrednost sa adrese u registar
    • str: Čuva vrednost registra na adresi
    • op{<cond>}{<size>} Rn, <adress>
      • <cond> = {eq: =, gt: >, ge: >=, lt: <, le: <=}
      • <size> = {'': word, b: byte, h: halfword}
  • ldm/stm
    • ldm: Učitava vrednosti u više registara počevši od adrese
    • stm: Čuva vrednosti više registara počevši od adrese
    • op{<adrr_mode>}{<cond>} Rn{!}, <reg_list>
      • <adrr_mode> = {IA: increment_after, DB: decrement_before}
      • <cond> = {eq: =, gt: >, ge: >=, lt: <, le: <=}
      • ! updateuje Rn za \(\pm 4 \cdot len(reg\_list)\) u zavisnosti od <adrr_mode>
      • <reg_list> je lista registara navedena između { } koja ne sme da sadrži Rn

Aritmetičko-logičke instrukcije. (x86-64, ARM)

Instrukcije bezuslovnog skoka. (x86-64, ARM)

• Postavljaju se nakon određenih operacija

  • Kod x86-64 se to radi automatski, npr.

        cmp eax, edi ; biće updateovani O, S i Z flegovi
        add eax, esi ; biće updateovani O, Z, C flegovi PROVERI
    

  • Kod ARM se to radi tako što se dodaje sufiks s na operacije kojima to po default-u nije tako

        cmp r0, r1 ; biće updateovani O, S i Z flegovi
        adds r0, r2 ; biće updateovani O, Z, C flegovi PROVERI
    

• O (overflow) - prekoračenje kod označenih operatora
  • govori da li je došlo do prekoračenja
• S (sign) - najveći bit rezultata
  • govori da li je broj negativan ili nenegativan (\(x < 0 \ \lor x \leq 0\))
• Z (zero)
  • govori da li je rezultat prethodne operacije \(0\)
• C (carry)
  • govori da li je došlo do prenosa na bitu najveće težine

Instrukcije poređenja i njihova uloga u realizaciji uslovnih skokova. (x86-64, ARM)

Instrukcije uslovnog skoka. (x86-64, ARM)

• jl: \(S \oplus O\)
• jb: \(C\)

Objasniti pozivanje procedura i vraćanje iz njih korišćenjem steka za čuvanje povratne adrese. Prednosti i mane.

Pre pozivanja procedure na stek se čuva povratna adresa. Kada se procedura izvrši, instrukcija povratka uzima vrednost povratne adrese sa steka kako bi povratila kontrolu instrukciji koja sledi nakon zvanja procedure.

Mane:

• sporije nego čuvanje u registrima

Prednosti:

• nemamo ograničen broj parametara koji možemo čuvati na steku što je pogodno za rekurzivne procedure

Objasniti pozivanje procedura i vraćanje iz njih korišćenjem registara za čuvanje povratne adrese. Prednosti i mane.

Pre pozivanja procedure u poseban registar se čuva povratna adresa. Kada se procedura izvrši, instrukcija povratka uzima vrednost povratna adrese iz tog registra kako bi povratila kontrolu instrukciji koja sledi nakon zvanja procedure.

Mane:

• imamo ograničen broj parametara koji možemo čuvati zbog ograničenog broja registara

Prednosti:

• brže nego čuvanje na steku

Objasniti prenos argumenata procedure korišćenjem steka. Prednosti i mane.

Parametri se postavljaju na stek i pozvana procedura mora da ih vrati.

Mane:

• sporije nego registarski

Prednosti:

• nemamo ograničen broj parametara, što je pogodno za rekurzivne procedure

Objasniti prenos argumenata procedure korišćenjem registra procesora. Prednosti i mane.

Pre pozivanja procedure vrednosti koje bi trebalo da joj prosledimo stavljamo u registre koje će koristiti pozvana procedura

Mane:

• imamo ograničen broj parametara zbog ograničenog broja registara

Prednosti:

• brže nego čuvanje na steku

Na koji način pozvana funkcija može vratiti vrednost pozivajućoj funkciji?

Putem steka i registara.

Objasniti pozivanje funkcija na x86-64 arhitekturi. Kako se prenosi adresa povratka, argumenti, kao i povratna vrednost?

Prvih 6 argumenata se prosleđuju redom u registre:

1. rdi
2. rsi
3. rdx
4. rcx
5. r8

6. r9

   U slučaju da nam je potrebno više od 6 argumenata, postavljamo ih na stek zdesna ulevo.

   Povratna vrednost se čuva u registru rax.

        mov edi, 42
        mov esi, 7
        call f
        add r10d, eax ; sum += eax
   

   Instrukcija call postavlja adresu sledeće instrukcije na stek kao adresu povratka.

Objasniti pozivanje funkcija na ARM arhitekturi. Kako se prenosi adresa povratka, argumenti, kao i povratna vrednost?

Prvih 4 argumenata se prosleđuju redom u registre:

1. r0
2. r1
3. r2

4. r3

   U slučaju da nam je potrebno više od 4 argumenata, postavljamo ih na stek zdesna ulevo.

   Povratna vrednost se čuva u registru r0.

       mov r0, 42
       mov r1, 7
       bl f
       add r4, r0 ; sum += eax
   

Instrukcija bl postavlja adresu sledeće instrukcije u lr (link register) kao adresu povratka.

• ALU - Aritmetičko logička jedinica
  • zadužena je za aritmetičke i logičke operacije nad podacima
  • kombinatorno kolo
  • obradu podataka vrši isključivo nad registrima
  • danas se ne implementira kao jedinstvena komponenta, već iz nekoliko specijalizovanih podjedinica
• CU - Kontrolna jedinica
  • zadužena je za kontrolu redosleda izvršavanja operacija u ALU i kontrolu prenosa podataka i instrukcija iz i u procesor.
  • sekvencijalno kolo
• Registri
  • služe za privremeno čuvanje i obradu podataka i adresa
  • implementiraju se pomoću statičke memorije
  • delimo ih na:
    • registre opšte namene
      • dostupni su programeru da sa njima radi
    • registre specijalne namene
      • nisu dostupni programeru jer ih procesor koristi za svog čuvanje stanja itd.

• ALU - Aritmetičko logička jedinica
  • zadužena je za aritmetičke i logičke operacije nad podacima
  • kombinatorno kolo
  • ALU obradu podataka vrši isključivo nad registrima
  • danas se ne implementira kao jedinstvena komponenta, već iz nekoliko specijalizovanih podjedinica

Šta su registri opšte namene i čemu služe?

Registri opšte namene su procesorski registri kojima programer ima pristup, nad kojima je moguće vršiti računanje i privremeno čuvanje podataka.

Čemu služi instrukcioni registar IR?

IR sadrži instrukciju koja se trenutno izvršava ili dekodira.

Spada u registre specijalne namene, odnosno nije registar opšte namene.

Čemu služi programski brojač PC?

PC sadrži adresu naredne instrukcije koja treba da se izvrši.

Spada u registre specijalne namene, odnosno nije registar opšte namene.

Čemu služi statusni registar PSW?

PSW = Program Status Word

PSW sadrži informacije o trenutnom stanju (state) procesora, odnosno flegove.

Spada u registre specijalne namene, odnosno nije registar opšte namene.

Čemu služi registar memorijskih adresa MAR?

MAR = memory adress register

MAR sadrži memorijsku adresu sledećeg podataka ili instrukcije koji će procesor da obradi ili da sačuva na to mesto.

Predstavlja medijum komunikacije između procesora i adresne magistrale.

Spada u registre specijalne namene, odnosno nije registar opšte namene.

Čemu služi registar memorijskih podataka MDR?

MDR = memory data register

MDR sadrži vrednost sledećeg podataka koji će procesor da obradi ili da sačuva negde u memoriji

Predstavlja medijum komunikacije između procesora i data magistrale.

Spada u registre specijalne namene, odnosno nije registar opšte namene.

Šta je putanja podataka (datapath) i iz čega se sastoji?

Datapath je deo procesora koji se sastoji iz registara, ALU-a i internih magistrala koje ih međusobno povezuju koji je zadužen za transformisanje podataka.

Nacrtati uopštenu shemu putanje podataka sa tri interne magistrale. Primer izvršavanja operacije.

Nacrtati uopštenu shemu putanje podataka sa dve interne magistrale. Primer izvršavanja operacije.

Nacrtati uopštenu shemu putanje podataka sa jednom internom magistralom. Primer izvršavanja operacije.

Šta je kontrolna jedinica (CU)? Šta je ulaz, a šta izlaz kontrolne jedinice?

Kontrolna jedinica je komponenta procesora koja pomoću kontrolnih signala govori datapath-u šta da uradi sa podacima

Uloga CU je:

• koordinacija podataka iz, u i među procesorskim podjedinicama
• interpretiranje instrukcija
• kontrola toka podataka u procesoru
• generisanje kontrolnih signala na osnovu instrukcija

Ulazu u CU se obavlja prihvatanjem podataka iz prihvatnog registra u dekoder, dok je izlaz od CU zapravo izlaz iz dekodera koji je spojen sa ulazom ALU-a.

Opisati osnovne faze pri izvršavanju instrukcija procesora.

Program čini skup instrukcija koje su smeštene u memoriji. Procesor čita redom instrukcije iz memorije, zatim ih izvršava pa prihvata narednu. Proces se ponavlja sve dok je računar upaljen. Ovaj ciklus je poznat kao pribavi-dekodiraj-izvrši (fetch-decode-execute).

1. Adresa zapisana u PC se kopira u MAR, nakon čega se PC inkrementira.
2. Kopira se vrednost iz adrese koja je sačuvana u MAR i smešta se u MDR

3. Eventualno, vrednost iz MDR se kopira u IR nakon čega je faza dohvatanja gotova

   Pseudo-asembler kod

       mov mar, pc
       inc pc
       mov mdr, [mar]
       mov ir, mdr
   

1. Kodirana instrukcija u IR se dekodira
2. Zajedno sa upravljačkim signalima, dekodirana instrukcija se šalje dalje na ALU za obradu

1. Na ulaze se dovode operandi, dok se na upravljačke linije dovodi kod operacije
2. Kao izlaz dobijamo obrađene podatke

1. Hardverski
   • implementira se kroz upotrebu sekvencijalnih logičkih jedinica, zbog čega se dobija komplikovanija struktura sa povećanjem instrukcija
   • koriste se u RISC arhiterkturi
   • rade velikom brzinom, ali broj instrukcija koje mogu da implementiraju je ograničen
   • skuplja izrada
2. Mikroprogramski
   • jednostavnija struktura
   • koriste se u CISC arhitekturi
   • rade sporije u odnosu na hardverski zbog dodatnog sloja apstrakcije u vidu mikroinstrukcija, ali je lakše izmeniti same instrukcije
   • jeftinija izrada

• implementira se kroz upotrebu sekvencijalnih logičkih jedinica, zbog čega se dobija komplikovanija struktura sa povećanjem instrukcija
• koriste se u RISC arhiterkturi
• rade velikom brzinom, ali broj instrukcija koje mogu da implementiraju je ograničen
• skuplja izrada
• danas se retko koriste

Objasniti mikroprogramsku (softversku) implementaciju CU

• jednostavnija struktura
• koriste se u CISC arhitekturi
• rade sporije u odnosu na hardverski zbog dodatnog sloja apstrakcije između hardvera i mašinskih instrukcija, no lakše je izmeniti instrukcije
• jeftinija izrada
• danas se praktično uvek koriste

Mikroprogram, koji se sastoji iz mikroinstrukcija sačuvan je u posebnoj ROM ili PLA memoriji CU-a. Izvršavanje mikroinstrukcija generiše skup kontrolnih signala.

Šta je mikroinstrukcija? Struktura mikroinstrukcije

Mikroinstrukcija je najmanja celina mikrokoda koji predstavlja programibilni sloj apstrakcije između hardvera i mašinskog koda. Struktura mikroinstrukcije može biti horizontalna i vertikalna

Šta je mikroprogram? Objasniti način izvršavanja mikroprograma.

Mikroprogram je niz mikroinstrukcija. Ideja mikroprogama je da se mašinske instrukcije pretvore u mikrorutine (niz mikroinstrukcija koji odgovara jednoj mašinskoj instrukciji) čije mikroinstrukcije se čuvaju u ROM ili PLA memoriji, čije izvršavanje generiše odgovarajuće kontrolne signale.

Mikroprogram se izvršava od strane mikroprogramskog kontrolera.

• adress generator - dobija instrukciju od \(IR\) i flegove na osnovu kojih generiše adresu odgovarajuće mikroinstrukcije (adresa u control store-u)
• \(\mu PC\) - slično kao \(PC\) (čuva sledeću mikroinstrukciju koju treba izvršiti)
• control store - ROM ili PLA memorija gde se nalaze same mikroinstrukcije

Objasniti horizontalni format mikroinstrukcija procesora.

Horizontalni format:

• svakom signalu odgovara po jedan bit
  • samim tim, nije potrebno nikakvo dekodiranje jer možemo direktno pročitati vrednost
• Prednosti:
  • moguće je navođenje velikog broja signala u jednoj instrukciji, zbog čega nam je potrebno manje ciklusa za izvršavanje instrukcija
• Mane:
  • veličina mikroinstrukcije (npr. 90 bitova)

Objasniti vertikalni format mikroinstrukcija procesora.

Vertikalni format:

• Na dužini mikroinstrukcije je moguće uštedeti ako bismo umesto npr. 64 bita za kontrolisanje 32 registra (kontrolni signali za ulaz i izlaz svakog) koje bismo koristili u horizontalnom formatu, koristili 5 za identifikovanje registra i 1 za izbor signala (ulaz ili izlaz)
• Prednost
  • kraće mikroinstrukcije
• Mane
  • u jednom ciklusu je moguće navesti samo jedan registar, zbog čega nam je potrebno više ciklusa za izvršavanje instrukcija

• kapacitet
• adresivost
• performanse
• trajnost (postojanost) zapisa
• mogućnost promene sadržaja
• promenljivost zapisa
• cena
• fizički tip medijuma

• sekvencijalni
• direktni (neposredni)
• proizvoljni (slučajni)
• asocijativni

Objasniti sekvencijalni pristup memoriji

Podaci su organizovani u jedinice koje nazivamo slogovi koji su međusobno razdvojeni kontrolnim informacijama (npr. dužina sloga) koje se koriste pri pristupanju određenom slogu.

Podaci se upisuju po redosledu unošenja, a čitaju po istom ili obrnutom redosledu.

Da bi se pristupilo \(i\) -tom slogu potrebno je proći kroz svih prethodnih \(i - 1\) slogova, što znači da je ovaj način dosta spor.

Primer: magnetna traka

Objasniti direktni (neposredni) pristup memoriji (semi-random)

Kod ovog načina pristupa postoji veza između adrese podatka i pozicije njegovog sloga na medijumu. Na osnovu adrese se pristupa lokaciji sloga ili njegovoj okolini. Vreme pristupa je promenljivo i zavisi od pozicije na medijumu.

Primer: magnetni disk

Objasniti proizvoljni (slučajni) pristup memoriji (Random Access Memory)

Kod ovakvog načina pristupa moguće je u konstantnom vremenu pristupiti bilo kojoj adresibilnoj lokaciji nezavisno od toga gde se fizički nalazi.

Primer: glavna memorija (RAM)

Objasniti asocijativni pristup memoriji (Content Adressable Memory)

Ovo je podtip proizvoljnog pristupa memoriji koji omogućava pretragu cele memorije na osnovu dela sadržaja (reči) umesto pomoću adrese.

Primer: koristi se kod specijalizovanih baza podataka

Šta je kapacitet memorije i u kojim jedinicama se izražava?

Kapacitet predstavlja količinu podataka koji se mogu sačuvati u memoriji.

Obično se izražava u KiB, MiB, GiB, TiB

• Privremena
  • gube zapis s nestankom napajanja
• Stalna
  • čuvaju zapis sve dok ne dođe do namerne promene (ignorišemo fizičko degradiranje materijala itd.)

• promenljive
  • memorija koja se koristi za implementaciju registara i RAM
• polu-promenljive
  • PROM, EPROM, EEPROM
• nepromenljive
  • ROM

Kako se izražava brzina memorije? Koji faktori najviše utiču na brzinu memorije?

Izražava se u količini obrađenih podataka po jedinici vremena. Kod RAM memorija se često izražava u \(MHz\).

Najviše utiču:

• način adresiranja
• tehnologija izrade

Objasniti hijerarhiju memorija

Smara, stvarno treba da se ranim ako ne budem znao ovo.

Šta je ROM? Kakve vrste postoje? Gde se koristi?

ROM je read-only memorija čiji sadržaj je stalan i ne može se menjati (u klasičnom smislu). Implementira se kao kombinatorno kolo jer vrednosti na izlazu zavise isključivo od vrednosti na ulazu.

Najčešće se koristi za smeštanje low-level programa i mikrokoda koji su potrebni za pokretanje računara.

Vrste:

• ROM: Read Only Memory
• PROM: Programmable Read Only Memory
• EPROM: Erasable Programmable Read Only Memory
• EEPROM: Electrically Erasable Programmable Read Only Memory
• Flash (jako slično EEPROM-u s tim što dozvoljava brisanje više bajtova odjednom)

Šta je RAM? Kakve vrste postoje?

RAM (Random Access Memory) je memorija sa slučajnim pristupom.

Sadržaj memorije se gubi bez napajanja. Moguće je proizvoljan broj puta čitati i pisati iz iste memorije.

Vrste:

• statički
• dinamički

Šta je statički RAM i koje su njegove osnovne karakteristike? Gde se koristi?

SRAM je vrsta RAM-a koja se najčešće koristi za implementaciju keš memorije i registara procesora.

Najčešće se implementiraju pomoću D-flip-flopova i nekih drugih kombinatornih kola.

Karakteriše ga velika brzina čitanja i pisanja, ali takođe i velika cena izrade, zbog čega se i rezervisano koriste.

Šta je dinamički RAM i koje su njegove osnovne karakteristike? Gde se koristi?

DRAM je vrsta RAM-a koja se najčešće koristi za implementaciju glavne memorije u računaru (u “narodnom” shvatanju RAM).

Jedna memorijska jedinica je sačinjena od jednog tranizstora i kondenzatora, što ga čini dosta jeftinim za proizvodnju, kao i kompaktnim za ređanje velikog broja memorijskih ćelija na malom prostoru.

Mana DRAM-a je što je potrebno relativno često ažurirati vrednosti jer se vremenom gube iz kondenzatora. Takođe, pri čitanju se vrednost uništava, pa ju je potrebno opet upisati nakon čitanja.

Šta su isprepletane memorije? Objasniti.

To je jedna od tehnika koja se koristi za smanjenje kašnjenja prilikom pristupa susednim memorijskim adresama.

Ideja je da se memorija izdeli na nekoliko manjih uzastopnih memorijskih jedinica koje nazivamo bankama. Ulazne adrese izdelimo u dva dela \(m\) (viši bitovi) i \(k\) (niži bitovi), tako da \(k\) služi da identifikuje banku, dok \(m\) služi da identifikuje adresu u toj banci. Na taj način možemo paralelno pristupati različitim bankama i da smanjimo vreme koje nam je potrebno za pristupanje memoriji.

Koje vrste preslikavanja memorijskih adresa razlikujemo? Objasniti.

Preslikavanje adresa je postupak kojim mapiramo fizičku memoriju u adresnom prostoru računara.

Preslikavanje može biti puno i delimično

Objasniti puno preslikavanje memorijskih adresa.

Puno preslikavanje memorijskih adresa je 1-1 preslikavanje (za svaku memorijsku lokaciju postoji najviše jedna adresa koja joj odgovara)

Objasniti delimično preslikavanje memorijskih adresa

Puno preslikavanje memorijskih adresa nije 1-1 preslikavanje (za svaku memorijsku lokaciju postoji više adresa koje joj odgovaraju)

Objasniti poravnanje podataka (memorija).

Procesori čitaju podatke u rečima. Ako imamo poravnate podatke to znači da je moguće samo u jednom ciklusu pročitati reč u kojoj se nalazi naš podatak. Kada ne bismo imali poravnate podatke, uštedeli bismo malo na memoriji, ali bismo dosta izgubili na performansama, ne samo zbog većeg broj utrošenih ciklusa za čitanje već i zbog promašaja u kešu.

Navesti osnovne vrste spoljašnjih memorija i navesti njihove karakteristike

Spoljašnja memorija trajno sadrži podatke i programe koji se ne koriste aktivno (nije joj potrebno napajanje za očuvanje sadržaja). Dosta je sporija od unutrašnje memorije, ali ima veći kapacitet.

Primeri:

• magnetna traka
• magnetni diskovi (floppy, HDD)
• optički diskovi (CD, DVD, BlueRay)
• flash drive, SSD

Objasniti namenu i osnovni princip rada keša.

Keš memorija predstavlja malu količinu brze memorije koja u memorijskoj hijerarhiji stoji između procesorskih registara i glavne memorije i služi da ublaži razliku u brzini između procesora i glavne memorije.

Implemenitraju se preko SRAM-a. Funkcionišu tako što unapred dobave podatke ili instrukcije za koje se smatra da postoji velika verovatnoća da će procesoru trebati, zbog čega se u slučajevima kada se pogodi, dosta smanjuje vreme potrebno za neku operaciju.

Objasniti princip lokalnosti. Šta je prostorna a šta vremenska lokalnost? Primeri.

Prostorna lokalnost je tendencija naših programa da se podacima i instrukcija pristupa sekvencijalno.

Primeri:

• u C-u niz predstavlja uzastopni blok memorije, te on zadovoljava princip prostorne lokalnosti
• instrukcije najčešće se izvršavaju sekvencijalno, osim ako imamo skokove

Vremenska lokalnost je tendencija naših programa da ponovno koriste iste instrukcije ili podatke.

Primer:

• ako imamo program koji računa sumu niza, onda se promenljiva koja čuva sumu može staviti u keš zajedno sa instrukcijama u petlji

Na koji način keš koristi principe prostorne i vremenske lokalnosti?

Keš memorije koriste princip prostorne lokalnosti tako što kopiraju celu okolinu nekog podatka/instrukcije iz glavne memorije iako je samo jedan podatak tražen jer se očekuje da će i susedni podaci biti uskoro korišćeni.

Princip vremenske lokalnosti ostvaruje se tako što se podaci/instruckije koji su nedavno korišćeni nalaze u kešu, jer je pretpostavka da će uskoro biti ponovo korišćeni.

Objasniti čitanje keša u slučaju pogotka

Čitanje keša u slučaju pogotka znači da smo podatak koji smo tražili od glavne memorije našli u kešu. Magistrale za adrese i podatke se blokiraju i razmena podataka se dešava direktno između procesora i keša. Na ovaj način čitanje je dosta brže.

Objasniti čitanje keša u slučaju promašaja

Ako se traženi podaci ne nalaze u kešu, onda se čitaju iz memorije i istovremeno upisuju u keš. Magistrale za adrese i podatke su aktivne, što znači da se odvija uobičajeno čitanje iz memorije sa dodatnim upisom u keš što ovaj slučaj čini sporijim nego čitanje iz memorije bez prisutva keša.

Objasniti pisanje keša u slučaju pogotka

U slučaju pogodtka postoje dve mogućnosti za pisanje:

• samo u kešu
• i u kešu i u glavnoj memoriji

Objasniti pisanje keša u slučaju promašaja

U slučaju promašaja podaci se upisuju samo u memoriju zato što ne postoje u kešu.

Šta je preslikavanje adresa keša i koje vrste preslikavanja postoje?

blok = uzastopni komad memorije

Preslikavanje adrese keša je mapiranje između blokova iz glavne memorije i keš linija.

Vrste:

• neposredno
• set-asocijativno
• asocijativno

Objasniti neposredno preslikavanje adresa keša i dati primer.

• Svaki blok se mapira u tačno jednu liniju keša
  • \(M\) - količina glavne memorije
  • \(m\) - količina keš memorije
  • \(B\) - veličina jednog bloka memorije (ujedno i veličina jedne linije keša)
  • \(A\) - dužina adrese (npr. 32 ili 64 bita)
  • \(C = m \ / \ B\) - broj keš linija
  • \(c_{i} = i \ mod \ C\) - \(i\) -ti blok memorije se mapira u \(c_{i}\) -tu keš liniju
• Lako je za implementaciju, ali je takođe lako dobiti najgori mogući slučaj

Primer:

• \(M = 64\)
• \(m = 16\)
• \(B = 4\)
• \(A = 32\)

• \(C = m \ / \ B = 4\)

  i	ci
  0	0
  1	1
  2	2
  3	3
  4	0
  5	1
  6	2
  7	3
  8	0
  9	1
  10	2
  11	3
  12	0
  13	1
  14	2
  15	3

Svaka adresa iz memorije se deli u 3 dela:

• offset
  • služi da odredi koji bajt iz linije tražimo
  • zauzima \(b = log_{2}(B)\) bitova
• keš linija id
  • moduliramo ovaj uzastopni podniz bitova da bismo dobili na koju liniju keša mapiramo dati blok
  • zauzima \(c = log_{2}(C)\) bitova
• keš tag
  • služi za čuvanje u kešu kako bi keš znao koji blok memorije je u pitanju (pošto se više blokova memorije mogu mapirati u istu keš liniju)
  • zauzima \(t = A - b - c\) bitova

U liniji keša čuva se:

• keš podatak
  • podaci kopirani iz mapiranog bloka memorije
• keš tag
  • pošto se više blokova memorije mogu mapirati u istu keš liniju, koristimo keš tag da ih razlikujemo
• validan bit
  • govori da li keš linija sadrži validne podatke (na početku je nego đubre, pa na ovaj način to naznačavamo)

• Kada želimo da proverimo da li se blok nalazi u kešu potrebno je:

  1. naći “id” keš linije, odonosno \(c_{i}\)
  2. ako je validan bit jednak \(0\) onda je promašaj
  3. ako se keš tag i trenutni tag razlikuju onda je promašaj
  4. u suprotnom nađen je

  Slično važi i za upis, koji je dodatno vezan za polisu upisa.

Objasniti asocijativno preslikavanje adresa keša i dati primer.

• Svaki blok je moguće mapirati u bilo koju keš liniju
  • Ako koristimo FIFO alokaciju, onda se faktički novi blok upisuje u prvu sledeću slobodnu liniju. Kada se popuni keš izbacujemo ih redom kojim smo ih uneli.
  • \(M\) - količina glavne memorije
  • \(m\) - količina keš memorije
  • \(B\) - veličina jednog bloka memorije (ujedno i veličina jedne linije keša)
  • \(A\) - dužina adrese (npr. 32 ili 64 bita)
  • \(C = m \ / \ B\) - broj keš linija

Svaka adresa iz memorije se deli u 2 dela:

• offset
  • služi da odredi koji bajt iz linije tražimo
  • zauzima \(b = log_{2}(B)\) bitova
• keš tag
  • služi za čuvanje u kešu kako bi keš znao koji blok memorije je u pitanju (pošto se više blokova memorije mogu mapirati u istu keš liniju)
  • zauzima \(t = A - b\) bitova

U liniji keša čuva se:

• keš podatak
  • podaci kopirani iz mapiranog bloka memorije
• keš tag
  • pošto se više blokova memorije mogu mapirati u istu keš liniju, koristimo keš tag da ih razlikujemo
• validan bit
  • govori da li keš linija sadrži validne podatke (na početku je nego đubre, pa na ovaj način to naznačavamo)

• Kada želimo da proverimo da li se blok nalazi u kešu potrebno je:
  1. sve linije koje imaju validan bit jednak \(1\) se uzimaju u obzir
  2. porede se keš tagovi i trenutni tag, ako se ne nađu onda imamo promašaj
  3. u suprotnom nađen je
• Problem nije veća količina memorije odvojena za keš tag, već činjenica da jedan blok može da bude u bilo kojoj keš liniji, zbog čega nam je potreban \(C\) komparatora što ga čini dosta skupim (komparator za svaku keš liniju).

Objasniti skup-asocijativno preslikavanje adresa keša i dati primer.

Skup-asocijativno preslikavanje prestavlja kompromis između neposrednog i asocijativnog preslikavanja i kombinaciju tih ideja.

• \(M\) - količina glavne memorije
• \(m\) - količina keš memorije
• \(B\) - veličina jednog bloka memorije (ujedno i veličina jedne linije keša)
• \(A\) - dužina adrese (npr. 32 ili 64 bita)
• \(C = m \ / \ B\) - broj keš linija
• \(S \in \{ 2, 4, 8 \}\) - broj disjunktnih skupova
• \(s_{i} = i \ mod \ S\) - \(i\) -ti blok memorije se mapira u \(s_{i}\) -ti skup keš linija

• Izdelimo keš linije u disjunktne skupove, kojima pristupamo metodom sličnom kao kod neposrednog preslikavanja.

  • Unutar samih skupova unosimo na proizvoljne keš linije kao kod asocijativnog preslikavanja

  Svaka adresa iz memorije se deli u 3 dela:

  keš tag

  skup id

  offset

• offset
  • služi da odredi koji bajt iz linije tražimo
  • zauzima \(b = log_{2}(B)\) bitova
• skup id
  • moduliramo ovaj uzastopni podniz bitova da bismo dobili na u koji skup mapiramo dati blok
  • zauzima \(s = log_{2}(S)\) bitova
• keš tag
  • služi za čuvanje u kešu kako bi keš znao koji blok memorije je u pitanju (pošto se više blokova memorije mogu mapirati u istu keš liniju)
  • zauzima \(t = A - b - s\) bitova

U liniji keša čuva se:

• keš podatak
  • podaci kopirani iz mapiranog bloka memorije
• keš tag
  • pošto se više blokova memorije mogu mapirati u istu keš liniju, koristimo keš tag da ih razlikujemo
• validan bit
  • govori da li keš linija sadrži validne podatke (na početku je nego đubre, pa na ovaj način to naznačavamo)

• Kada želimo da proverimo da li se blok nalazi u kešu potrebno je:
  1. pronaći id skupa u kojem se nalazi blok
  2. sve linije koje imaju validan bit jednak \(1\) se uzimaju u obzir
  3. porede se keš tagovi i trenutni tag, ako se ne nađu onda imamo promašaj
  4. u suprotnom nađen je

Šta su i čemu služe politike zamenjivanja keša? Nabrojati ih.

• Politika zamenjivanja sa primenjuje radi odabira keš linije čiji sadržaj će biti zamenjen sadržajem novog memorijskog bloka.
• Zavisi od primenjenog preslikavanja
  • U slučaju neposrednog preslikavanja nema politike zamene jer nema izbora

Najčešće se koriste:

• LRU
• pseudo-LRU
• FIFO
• LFU
• random

Objasniti politiku zamenjivanja najduže nekorišćene linije keša (LRU). Dobre i loše strane.

LRU = Least Recently Used

Predviđanje zasniva na principu vremenske lokalnosti. Zamenjuje sadržaj one linije keša koja najduže nije bila korišćena.

Prednosti:

• najbolji rezultati

Mane:

• za \(n\) linija potrebno mu je \(n!\) stanja koja je moguće predstaviti kao konačni automat, ali je memorijska složenost prevelika da bi se realizovalo u asocijativnom mapiranju
• moguće je realizovati za \(2\) ili \(4\) keš linije, zbog čege se i koristi u skup-asocijativnom mapiranju

Objasniti politiku zamenjivanja pseudo-najduže nekorišćene linije keša (pseudo-LRU). Dobre i loše strane.

pseudo-LRU = pseudo Least Recently Used

Predstavlja aproksimaciju LRU politike. Keš linije se dele u dve grupe, gde se pomoću jednog bita označava linija keša koja je grupa najskorije korišćena. Delimo dalje u podskupove sve dok ne dođemo do jedne linije keša.

Prednosti:

• dosta manja memorijska složenost, što se najviše ogleda u situacijama kada imamo više od \(4\) keš linije u jednom skupu

Mane:

• smanjena preciznost u odnosu na LRU

Objasniti FIFO politiku zamenjivanja linije keša.

Zamenjuje se ona linija keša koja je prva pročitana, tj. ona koja je najduže u kešu.

Relativno jednostavna implementacija:

• skup linija keša se ponaša kao kružni bafer
• za svaki skup je potreban po jedan kružni brojač koji označava koja linija je poslednje popunjena

Retko se koristi

Koje politike pisanja keša postoje i u čemu se razlikuju

Kada se podaci menjaju, mora se uzeti u obzir da postoje dve kopije podataka (u kešu i glavnoj memoriji)

Dve osnovne politike:

1. Pisanje sa propuštanjem (write-through) - pisanje se odvija i u kešu i u memoriji
2. Pisanje sa prepisivanjem (write-back) - samo keš

Objasniti politiku pisanja keša sa propuštanjem (write-through). Dobre i loše strane

Svaki put kada se vrši upis u keš, vrši se i u memoriji.

Prednosti:

• jednostavna implementacija

Mane:

• relativno sporo

Objasniti politiku pisanja keša sa prepisivanjem (write-back). Dobre i loše strane

Ažuriramo isključivo u kešu, dok se pisanje u memoriju odvija pri zameni u kešu. Koristimo update bit koji nam govori da li je keš linija koju treba zameniti bila ažurirana, tj. da li treba ažurirati u glavnoj memoriji. Na ovaj način poboljšavamo performanse zamene linije keša, koja bi bez update bit-a i write-back politikom bila duplo sporija.

Razdvojeni i unifikovani keš. Poređenje.

Kod razdvojenog keša postoji poseban keš za podatke i instrukcije, dok je kod unifikovanog sve u jednom.

Prednost razdvojenog keša je što omogućava drugačije načine korišćenja principa lokalnosti čime povećava performanse. Takođe olakšava implementaciju jer keš za instrukcije samo čita.

Nedostatak razdvojenog keša je u tome što je nemoguće dinamički menjati količinu keša odvojenu za podatke i instrukcije.

Objasniti arhitekture višestepenog keša i način njihovog funkcionisanja.

Organizacija keša hijerarhijski u više nivoa može biti:

• Inkluzivna - svaki sledeći nivo sadrži podatke iz prethodnog, ali i neke dodatne
• Ekskluzivna - ne sadrži iste podatke, već isključivo nove

Prednost inkluzivnog pristupa je u tome što veće keš memorije mogu imati veće linije, dok kod ekskluzivnog sve keš memorije moraju da imaju linije iste veličine

Podaci se prvo traže u najbližem kešu, pa ako ih tu nema onda u sledećem itd. dok se ne nađe ili ode do memorije.

Danas se najčešće organizuje u 3 nivoa:

• L1 - nalazi se na samom čipu procesora, najbliže samom procesoru
• L2 - uglavnom se nalazi na samom čipu procesora
• L3 - obično je znatno veći i zajednički za sva jezgra na istom procesoru

Objasniti odnos veličine keša i performansi.

Povećanjem keša do određene granice dobijamo bolje performanse, ali se u nekom trenutku taj rast performansi usporava i postaje beznačajan.

Ovo se može objasniti time da određenom veličinom keša procenat pogodtka postane blizak \(100%\) nakon čega dalje povećanje nema uticaja

Objasniti odnos veličine linije keša i performansi.

Povećanjem linije keša do neke mere se poboljšavaju performanse, ali se u nekom trenutku te performanse počinju kvariti.

Za premale linije keša slabo se koristi princip prostorne lokalnosti, dok se za velike smanjuje preciznost.

Objasniti odnos asocijativnosti i performansi.

Povećanjem stepena asocijativnosti se povećava procenat pogotka keša. Potpuno asocijativni keš je u tom smislu najbolji, ali je njegova implementacija teška, pa se dizajneri češće odlučuju za skup-asocijativno mapiranje, uz izbor većih skupova kad je to moguće.

Šta je magistrala i čemu služi?

Magistrala je komunikacioni sistem koji prenosi podatke/instrukcije između komponenti računara ili eksternih uređaja.

Kako se ostvaruje deljenje magistrale? Na koji način se sprečava kolizija signala? Objasniti.

Da bismo povezali više uređaja na magistralu, potrebno je sprečiti istovremeno puštanje signala od strane različitih uređaja. Ovo se obično postiže nadovezivanjem bafera sa tri stanja (tri-state buffer) na svakom od uređaja čime pomoću kontrolnog signala možemo određivati koji uređaj sme da šalje signal.

• Transakcija predstavlja niz operacija potrebnih za izvršanje jasno definisane akcije.
• Operacija predstavlja čitanje/pisanje memorije, čitanje I/O uređaja, “rafalno” čitanje itd.
• Protokol magistrale predstavlja skup pravila kojima se reguliše komunikacija između komponenti

Šta su serijske, a šta paralelne magistrale? Poređenje.

Prema načinu transfera, magistrale je moguće podeliti na:

• serijske
  • sastoje se iz jedne linije preko koje se podaci prenose bit po bit
• paralelne
  • sastoje se iz više linija preko kojih se podaci prenose reč po reč

Naizgled paralelne magistrale deluju kao bolji izbor, ali se ispostavilo da je u većini slučajeva bolje koristiti serijske.

Problemi paralelnih magistrala:

• zbog različitih dužina i provodljivosti ne stižu svi bitovi u isto vreme što znatno otežava ispravno čitanje
• pri velikim frekvencijama dolazi do elektromagnetne indukcije što znači da je moguće da odvojeni signali utiču jedni na druge, a.k.a. interferencija

Serijske ne samo što nemaju ove probleme, takođe su jeftinije i jednostavnije za izradu jer je potrebno manje delova. Serijske jesu sporije, ali dozvoljavaju da se poveća frekvencija čime se anulira taj faktor.

Zbog toga se danass umesto ranijih paralelnih (PCI, PATA...) koriste serijske magistrale (PCI-Express, SATA, USB). Izuzetak je memorijska magistrala koja povezuje procesor sa glavnom memorijom.

Koja je razlika između multipleksiranih i razdvojenih magistrala? Poređenje.

Paralelne magistrale mogu biti:

• razdvojene (dedicated)
  • odvojene linije se koriste za adrese i podatke (tzv. data magistrala, adresna magistrala)
  • Memorijska magistrala je primer odvojene paralelne magistrale
• multipleksirane (multiplexed)
  • iste linije se koriste i za adrese i za podatke tako što se prenose naizmenično u različitim ciklusima
  • PCI magistrala je primer multipleksirane paralelne magistrale

Prednosti multipleksiranih magistrala u odnosu na odvojene je u jeftinijoj implementaciji, a mana je u manjoj brzini prenosa (jer je potrebno više ciklusa za obavljanje transakcije)

Šta je širina magistrale?

Širina magistrale određuje veličinu podataka i adresa koji se prenose magistralom. Osnovna motivacija za proširivanje je podizanje propustnosti (throughput) a time i performansi. Sužavanje se radi u slučajevima da nam je potrebno da smanjimo složenost, samim tim i cenu.

Primer: Širina adresne magistrale nam određuje veličinu adresnog prostora. Sa sistemom sa \(n\) linija adresne magistrale možemo adresirati \(2^{n}\) bajtova.

Objasniti i predstaviti vremenskim dijagramom izvršavanje operacije čitanja u slučaju sinhrone magistrale.

Objasniti i predstaviti vremenskim dijagramom izvršavanje operacije pisanja u slučaju sinhrone magistrale.

Šta je stanje čekanja? Kada se i kako upotrebljava? Objasniti operaciju čitanja sa stanjem čekanja.

Imajući u vidu da je procesor često dosta brži od memorije, potrebno je na neki način mu reći da sačeka. Za to se koristi stanje čekanja i kontroni signal ready.

1. procesor želi da pročita određenu adresu u memoriji, stoga tu adresu postavlja na adresnu magistralu.
2. pošto je procesor brži od memorije, kontrolni signal ready se postavlja na \(1\) za koje vreme procesor čeka
3. kada je ready na \(0\) onda procesor uzima podatke sa magistrale podataka

Šta je “prenošenje blokova podataka”? Kada se i za šta upotrebljava?

Prenošenje blokova podrazumeva da se jednom složenom operacijom prenosi više uzastopnih reči jer se ispostavilo da je efikasnije pri istoj transakciji pročitati više reči nego u više uzastopnih operacija pojedinačno.

Koristi se često za popunjavanje keš memorije (zbog čega je i često veličina blokovnog prenosa ista kao i veličina keš linija).

Šta je “read-modify-write” transakcija i za šta se upotrebljava?

Ova transakcija je pogodna za realizaciju ekskluzivnog pristupa zajedničkim podacima/kodu (a.k.a. critical section) kod multiprocesorskih sistema.

Predstavlja atomičku operaciju što znači da tokom njenog trajanja nije moguće da se izvrši bilo koja druga operacija nad istom magistralom.

Kako se sinhronizuje rad na asinhronoj magistrali? Objasniti signale i tok aktivnosti (četvorofazno rukovanje)

Sinhronizuje se pomoću protokola za eksplicitnu sinhronizaciju kao što je četvorofazno rukovanje.

Pošto asinhrone magistrale nemaju zajednički časovnik, uređaji reaguju odmah na pristigle signale. Kod četvorofaznog rukovanja uvode se dva kontrolna signala MSYN (master synchronization) i SSYN (slave synchronization).

Tok aktivnosti:

1. master postavilja sve podatke na magistralu i “pali” MSYN signal kako bi slave-u stavio do znanja da započinje transakciju
2. slave obavlja transakciju i “pali” SSYN signal kako bi javio master-u da je završena transakcija
3. master “gasi” MSYN
4. slave “gasi” SSYN

Prednosti i mane asinhronih magistrala u odnosu na sinhrone.

Prednosti:

• Brži transfer jer se brzina može prilagoditi brzini uređaja sa kojim komunicira

Mane:

• Teža implementacija u odnosu na sinhrone

Šta je arbitraža magistrale? Objasniti razliku između centralizovane i distribuirane arbitraže.

Postojanje više master-a (npr. CPU i DMA kontroler) za jednu magistralu se rešava pomoću arbitraže magistrale.

Uloga arbitrže magistrale je da na osnovu politike dodeljivanja i politike oslobađanja odredi kom master-u će dodeliti upravljanje nad magistralom.

Kod centralizovanih arbitraža jedan centralni arbitar dobija zahteve od svih master-a i određuje kome dodeljuje magistralu. Kod distribuiranih arbitraža hardver je distribuiran među master-ima koji međusobno komuniciraju i određuju kome ide magistrala.

• Politike fiksnih prioriteta
  • svaki master ima fiksiran prioritet i na osnovu toga se i određuje ko će dobiti magistralu
• Politike rotirajućih prioriteta
  • prioritet nije fiksiran i može se na različite načine implementirati kao:
    • funkcija vremena čekanja za dodelu magistrale
    • kružna politika odnosno onaj koji je poslednji dobio pristup magistrali dobija najniži prioritet
• Hibridna politika
  • kombinacija prethodne dve politike

• Politika bez preuzimanja
  • oslobađa se magistrala tek kada trenutni master dozvoli
    • jedna varijanta je da uređaj oslobodi čim završi transakciju
    • druga varijanta je da uređaj oslobodi kad završi transakciju i drugi master je zahteva
• Politika sa preuzimanjem
  • magistralu je moguće osloboditi u slučaju da je zahteva master višeg prioriteta iako se trenutna transakcija možda nije obavila do kraja

Objasniti detaljno mehanizam ulančavanja kod centralizovane arbitraže.

Signal za zahtev se formira kao disjunkcija zahteva pojedinačnih master-a na zajedničkoj magistrali.

Signal za dodelu se prosleđuje redom od jednog do drugog master-a. Ako neku uređaj nije tražio pristup magistrali onda on prosleđuje sledećem sve dok ne dođe do prvog po prioritetu koji je zatražio pristup magistrali.

Veoma je jednostavan za implementaciju, ali mu je mana što omogućava samo fiksni prioritet politike dodele.

Objasniti detaljno mehanizam nezavisnih zahteva kod centralizovane arbitraže.

Svaki master je povezan sa arbitrom preko zasebnih magistrala za zahtev (REQ) i dodelu (GNT).

Omogućava da se implementiraju komplikovanije politike dodele jer postoji odvojena komunikacija sa svakim master-om.

Bolje toleriše u odnosu na ulančavnje slučaj kada se neki od mastera pokvari zato što to ne utiče na ostale.

Komplikovaniji je za implementaciju.

Električne karakteristike serijskih magistrala

• RZ (return-to-zero)
• NRZ (non-return-to-zero)
• NRZI (non-return-to-zero-inverted)

Koja je osnovna prednost, a koja mana NRZ kodiranja u odnosu na RZ kodiranje?

Objasniti NRZI kodiranje.

Ukratko objasniti 8b/10b kodiranje? Koji je razlog za korišćenje ovog načina kodiranja?

• PCI
  • multipleksirana
  • širina 32/64bit
  • sinhrona
  • služi sa povezivanje sa periferijskim uređajima (mrežne kartice, audio kartice i sl.)
• Memorijska magistrala
  • razdvojena
  • širina 16/32/64bit
  • služi za komunikaciju glavne memorije i procesora
• PATA
  • širina 16bit
  • služi za povezivanje sa sekundarnom memorijom (HDD, CD i sl.)

• PCI Express
  • naslednik PCI
  • dosta brži prenos podataka
• USB
  • plug and play
  • služi za povezivanje eksternih uređaja
• SATA
  • naslednik PATA
  • hot swapping
  • dosta brži prenos podataka

Šta je sistem prekida i koja mu je uloga?

Sistem prekida je mehanizam izmene kontrole toka programa.

Osnovna uloga mu je da omogući procesoru da reaguje na događaje koji zahtevaju hitnu obradu koji mogu ali ne moraju biti unapred programirani da se dese.

Primeri:

• pritiskanje tastera na tastaturi (hardverski)
• čitanje/pisanje u fajl (softverski)
• deljenje sa 0 (izuzetak)

• Hardverski a.k.a. asinhroni
  • generišu ih hardverski uređaji koji su povezani sa procesorom
  • dele se na:
    • maskirajuće
    • nemaskirajuće
• Softverski a.k.a. sinhroni
  • izazivaju ih posebne instrukcije u procesoru
    • kod Intel Pentium procesora je to int <interrupt_code>
• Izuzeci (Exceptions)
  • faktički predstavljaju softverske prekide koji se koriste kada dođe do greške u samim instrukcijama (npr. deljenje sa 0, overflow itd.)

Objasniti hardverske prekide. Šta su maskirajući, a šta nemaskirajući prekidi?

Hardverski prekidi su generisani od strane hardverskih uređaja, najčešće zbog I/O (input/output) tako što procesor ima jedan ili više priključaka na koje se može dovesti signal kojim se izaziva prekid.

Zovu se i asinhroni prekidi, jer se mogu dogoditi u bilo kom trenutku (nisu programirani odnosno planirani)

• Maskirajući (maskable): procesor ima mogućnost da privremeno ignoriše prekide pa da se pozabavi njima kasnije
• Nemaskirajući (non-maskable): procesor mora odmah da reaguje na njih

Objasniti softverske prekide. Koja je tipična uloga softverskih prekida?

Softverske prekide izazivaju posebne instrukcije. Kod Intel Pentium procesora je to int <interrupt_code>, gde je <interrupt_code> \(\in [0, 255]\)

Zovu se i sinhroni prekidi, jer se mogu dogoditi u unapred određenom trenutku.

Tipično se koriste za dobijanje ulaza od korisnika ili za ispisivanje na ekran itd.

Šta su izuzeci (u kontekstu sistema prekida) i čemu služe?

Izuzeci su prekidi koji funkcionišu jako slično kao softverski prekidi, s tim što nastaju kao posledica grešaka u izvršavanju instrukcija.

Služe da prekinu nevalidno izvršavanje programa.

Primeri:

• deljenje sa 0
• overflow / underflow

Šta je vektor prekida? Šta je deskriptor prekida? Gde se nalazi tabela deskriptora prekida?

Vektorski prekidi predstavljaju metod pozivanja handler-a prekida.

Svakom prekidu se dodeljuje broj \(c \in [0, 255]\) koji se koristi za indeksiranje u tabeli deskriptora prekida.

Vektor prekida (a.k.a. deskriptor prekida) predstavlja jedno polje u tabeli deskriptora prekida u kojoj se za svaki prekid čuva adresa njegovog handler-a.

Tabela deskriptora prekida (TDP) može da se nalazi bilo gde u memoriji. Lokacija je sačuvana pomoću 48-bitnog registra za TDP koji čuva 32-bitnu adresu TDP-a i 16-bitnu vrednost veličine TDP-a.

Objasniti detaljno način pozivanja rukovaoca (handler) prekidom u slučaju vektorskih prekida.

Tabela deskriptora prekida = TDP

1. Svakom prekidu se dodeljuje broj \(c \in [0, 255]\) koji se koristi za indeksiranje u TDP.
2. Imajući u vidu da se u TDP čuvaju 64-bitne adrese handler-a za svaki prekid, potrebno je skalirati \(c\) sa \(8\) odnosno \(i = c * 8\) pomoću čega dobijamo pravi indeks za TDP
3. Uzimamo adresu \(a = TDP[i]\) i kontrolu predajemo handler-u na toj adresi
4. Nakon što je handler završio svoje vraćamo kontrolu programu koji se izvršavao pre prekida

Objasniti komponente i rad kontrolora prekida PIC 8259 (/Programmable Interrupt Controller)

PIC služi da upravlja sa više uređaja koji mogu slati signale prekida.

Moguće je povezati 8 uređaja koji se povezuju pomoću magistrala IRQ0 … IRQ7 kojima BIOS dodeljuje prioritet

Kada neki uređaj želi da izazove prekid, on kontroleru putem svoje ulazne magistrale šalje signal nakon čega na osnovu prioriteta kontroler određuje da li će uslužiti taj uređaj.

Komunicira sa procesorom putem donjih 8 bitova data magistrale putem kojih i šalje indeks za vektor prekida.

Šta su ulazno/izlazni uređaji?

Ulazno/izlazni uređaji predstavljaju sredstvo pomoću kojeg računar komunicira sa spoljašnjim svetom odnosno sa čovekom i drugim uređajima.

Šta su ulazno/izlazni kontroleri i koja je njihova uloga?

I/O = Ulazno/izlazni

I/O kontroler je komponenta pomoću koje procesor komunicira sa I/O uređajem. Kontroler se sa jedne strane povezuje sa I/O uređajem, dok se sa druge povezuje na sistemsku magistralu pomoću koje komunicira sa procesorom.

Vrši low-level komunikaciju sa I/O uređajem, dok procesoru daje unifikovan interfejs za komunikaciju sa I/O uređajem.

Šta podrazumeva upotreba I/O uređaja putem memorijskog mapiranja?

I/O port = adresa internih registara I/O kontrolera (najčešće status, data, command registri)

Podrazumeva mapiranje I/O portova i adresa u glavnoj memoriji u isti adresni prostor.

Posledica toga je da procesor pristupa pomoću istih instrukcija nasumičnoj adresi u glavnoj memoriji i internom registru I/O kontrolera.

I/O kontroleri kada primete na adresnoj magistrali I/O port, šalju odgovarajuće podatke na data magistralu.

Šta podrazumeva upotreba I/O uređaja putem izolovanog ulaza i izlaza?

I/O port = adresa internih registara I/O kontrolera (najčešće status, data, command registri)

Podrazumeva mapiranje I/O portova i adresa u glavnoj memoriji u različite adresne prostore.

Posledica toga je da procesor pristupa pomoću različitih instrukcija nasumičnoj adresi u glavnoj memoriji i internom registru I/O kontrolera.

Kod Intel Pentium procesora koriste se instrukcije in i out za pristup I/O portovima

Objasniti tehniku programiranog I/O

polling = periodično proveravanje vrednosti

Funkcioniše tako što procesor poll-uje status registar I/O kontrolera i time proverava da li je I/O uređaj slobodan. Ako jeste u data registar upisuje podatke koje želi da obradi, nakon čega command registar upisuje odgovarajući kod u zavisnosti od čitanja ili pisanja. U suprotnom procesor zapitkuje I/O kontroler sve dok ne bude slobodan (“beskonačna petlja”).

Analogija: Šef da zadatak radniku, pa ga na svakih 5min pita da li je uradio, gubeći vreme na taj način

Mana ovog pristupa je to što je procesor sve vreme u upotrebi.

Objasniti tehniku I/O vođenog prekidima

Ideja je slična programiranom I/O, s tim što procesor delegira posao drugom kontroleru (npr. DMAC) koji je zadužen za transfer, dok procesor obavlja druge instrukcije. Kada se transfer završi, kontroler obaveštava procesor pomoću signala prekida.

Analogija: Šef da zadatak radniku i kaže mu da ga obavesti kada završi, dok će on u međuvremenu završavati ostale poslove

Objasniti direktan pristup memoriji (DMA). Kontroler DMA. Koraci pri realizaciji DMA pristupa

DMAC = DMA kontroler

DMA predstavlja rešenje za preopterećenje procesora kod programiranog I/O (“beskonačnu petlju”) tako što se posao organizovanja transfera delegira na DMAC

1. Procesor šalje DMAC-u \((id, adr, size, op)\)
   • \(id\) - broj koji identifikuje I/O uređaj
   • \(adr\) - adresa gde treba čitati/pisati u memoriji
   • \(size\) - broj bajtova
   • \(op\) - definiše da li je u pitanju čitanje ili pisanje
2. DMAC zahteva pristup sistemskoj magistrali
3. Nakon što arbitar odobri pristup
   • na adresnu magistralu se postavlja \(adr\)
   • šalju se kontrolni signali u \(id\), nakon čega se obezbeđuje da se podatak prenese preko data magistrale
4. Šalje se signal za prekid procesoru, kako bi se obavestio da je transfer završen

Šta je virtuelna memorija i zbog čega se koristi?

Virtuelna memorija predstavlja tehniku upravljanja memorijom koja omogućava da svaki program ima idealizovan pogled na memoriju.

Idealizovan pogled:

• programu memorija izgleda nefragmentisano i kao da je sam u memoriji, zbog čega individualni programi ne moraju da brinu o upravljanju memorije
• svaki program ima sopstveni virtuelni adresni prostor koji je veći nego količina fizički dostupne memorije pomoću tehnike paging-a (delovi memorije koji se najređe koriste se stavljaju na storage odnosno SSD/HDD i “uvoze” u RAM po potrebi)

U instrukcijama se koriste virtuelne adrese koje MMU (Memory Management Unit) u procesoru prevodi u fizičke adrese

Koristi se jer apstrakuje ručno upravljanje memorije (programer ne mora da razmišlja da li ima dovoljno memorije, gde će se ona nalaziti i da li drugi programi mogu da joj pristupe / da je korumpiraju)

Objasniti koncept stranica virtuelne memorije. Šta su stranice, a šta okvir stranica?

• Stranice (pages) predstavljaju virtuelne memorijske blokove fiksne veličine.
• Okviri (frames) predstavljaju fizičke memorijske blokove fiksne veličine.

Stranice predstavljaju najmanju jedinicu podataka za upravljanje virtuelnom memorijom. Čuvamo ih i u glavnoj memoriji (RAM) i pomoćnoj memoriji (npr. SSD).

Mapiranje page-ova u frame-ove i njihova automatska zamena iz pomoćne u glavnu memoriju (i obrnuto) od strane OS se naziva paging (na srpskom straničenje, fuj).

Paging nam omogućava da imamo naizgled neograničenu memoriju (iz perspektive programa).

Objasniti preslikavanje adresa virtuelne memorije. Primer.

Virtuelnu memoriju možemo posmatrati kao preslikavanje većeg virtuelnog adresnog prostora u manji fizički adresni prostor.

Koristimo MMU (Memory Management Unit) za preslikavanje virtuelnih u fizičke adrese. MMU se implementira pomoću tablice stranica (page table) koja koristi softverski implementirano asocijativno mapiranje, što znači da svaku stranicu možemo mapirati u svaki okvir.

Primer: \(32bit \rightarrow 24bit\)

Slikamo iz 32-bitnog u 24-bitni adresni prostor. Neka je veličina stranice \(4KiB = 2^{2} \cdot 2^{10}B = 2^{12}B\)

• Struktura virtuelne adrese:

  broj stranice (20bit)

  pomeraj (12bit)

• Struktura fizičke adrese:

  broj okvira (12bit)

  pomeraj (12bit)

• Pomerajem određujemo indeks u samoj stranici ili okviru. On se pri preslikavanju ne menja
• Gornjih 20 bitova virtuelne adrese se preslikava u gornjih 12 bitova fizičke adrese pomoću MMU.

Preslikavanje adresa na više nivoa. Zbog čega se koristi? Primer.

Kada imamo veliki virtuelni adresni prostor imaćemo i veliki broj stranica u tablici što zauzima dosta uzastopnog prostora u memoriji. Preslikavanje na više nivoa koristimo kako bismo izdelili samu tablicu u nekoliko manjih tablica, čime bismo rešili ranijepomenuti problem.

Primer:

• Neka naš sistem koristi 40-bitni adresni prostor sa stranicama koje mogu da smeste 4KiB stavki, gde je svaka stavka 4B
  • veličina adresnog prostora: \(A = 40b\)
  • broj stavki u jednoj stranici: \(P = 4KiB = 2^{12}B\)
  • veličina jedne stavke u stranici: \(s = 4B\)
  • broj adresa: \(cnt = 2^{A} = 2^{40}\)
  • broj stranica: \(p_{1} = \frac{cnt}{P} = 2^{28}\)
• Ukupna memorija koju bi naša tablica zauzimala:
  • \(M_{1} = s * p_{1} = 2^{30} = 1GiB\)
• Pošto je to previše da bismo alocirali uzastopno u memoriji, izdelimo stranice u manje tablice na koje povežemo tablicu koju nazivamo direktorijum. Pristupamo manjim tablicama pomoću broja tablice (BT) kojim indeksiramo direktorijum.
  • broj stavki u jednoj stranici: \(P = 4KiB = 2^{12}B\) (ostaje isti)
  • veličina jedne stavke u stranici: \(s = 4B\) (ostaje ista)
  • broj stranica: \(p_{2} = \frac{p_{1}}{P} = \frac{2^{30}}{2^{12}} = 2^{18}\)
• Memorija koju bi jedna naša tablica drugog nivoa zauzimala (imamo ih \(2^{10}\) komada):
  • \(M_{2} = s * p_{2} = 2^{20} = 1MiB\)
• Nakon što pomoću BT pristupimo direktorijumu da bismo dobili tablicu stranica, koristimo broj stranice (BS) da bismo u tablici stranica pristupilii okviru za stranicu koju smo tražili. Virtuelna adresa ima oblik:

Prednost je u tome što ne moramo čuvati celu tablicu u memoriji već samo njen direktorijum (tablicu stranica drugog nivoa) i po potrebi možemo učitavati sa diska.

Mana je što se smanjuje efikasnost pri prevođenju adresa.

Šta su i kada se koriste politike zamene stranica?

Politike zamene predstavljaju algoritme koje koristimo za određivanje koju stranicu bi trebalo sačuvati na pomoćnoj memoriji (npr. SSD) kada nam se glavna memorija (RAM) popuni stranicama a potrebno je da učitamo novu stranicu.

• FIFO = First In First Out
  • izbacuje se ona stranica koja je prva ubačena, nevezano da li se koristi često
  • jednostavno za implementaciju ali neefikasno
• Second Chance
  • predstavlja blago unapređenu FIFO politiku
  • svakoj stranici se pridružuje jedan bit koji govori da li je korišćena od kada u memoriji, i izbacuje se ona stranica koja je najduže a nije nijednom referisana
  • jednostavno za implementaciju ali neefikasno (efikasnije od FIFO)
• NFU = Not Frequently Used
  • brojimo koliko puta je neka stranica korišćena (imamo brojač za svaku), i menjamo onu koja je najmanje puta izbrojana
  • relativno jednostavno za implementaciju, ali i dalje nedovoljno efikasno
• pseudo LRU = pseudo Least Recently Used
  • predviđanje zasniva na principu vremenske lokalnosti. Zamenjuje onu stranicu koja najduže nije bila korišćena.
  • za svaku stranicu čuvamo masku veličine \(1B\) gde su svi bitovi postavljeni na 1 (\(mask = 0x255\))
    • ako koristimo trenutnu stranicu, masku shiftujemo ulevo, u suprotnom udesno
    • ako nam je maska jednaka \(0\), to znači da je nismo koristili u 8 ciklusa, dok maska \(mask = 0b00111111\) znači da je skoro korišćena stranica
    • što nam je veći broj bitova kojim predstavljamo masku to nam je bolja aproksimacija LRU-a

Objasniti značaj veličine stranice virtuelne memorije i navesti primer.

• Male > Velike stranice:
  • smanjenje interne fragmentacije odnosno povećanje iskorišćenosti stranica
    • veličina podataka, programa i steka nije ceo broj stranica, pa je prosečno pola stranice neupotrebljeno (ovo se naziva interna fragmentacija)
  • bolje pogađanje
    • što je veća stranica, to će pri njenom učitavanju u glavnu memoriju zastupljenost nepotrebnih sadržaja biti veća
• Velike > Male stranice:
  • manje tablice
    • što su stranice veće, biće ih manje, pa su i tablice manje
  • efikasniji pristup disku
    • vreme pristupa disku je mnogo veće nego sam transfer, pa je za manje vreme moguće pročitati manju količinu većih podataka nego veću količinu malih podataka (jer se broj pristupa disku redukuje)
      • Čitanje 100 stranica od 4KiB traje \(100 \cdot (10ms+ \frac{4}{100}ms) = 10.04s\)
      • Čittanje 25 stranica od 16KiB traje \(25 \cdot (10ms + \frac{16}{100}ms) = 2.54s\)

Primer veličine stranice:

• Intel x86: stranice su uobičajeno 4KiB, a podržane su i stranice veličine 2/4MiB

Šta su tablice, a šta direktorijumi stranica virtuelne memorije? Objasniti.

Tablice stranica predstavljaju asocijativnu strukturu (mapu) pomoću koje prevodimo stranice u okvire.

Koristimo broj stranice (BS) za indeksni pristup tablici stranica. U tom polju (stavki) između ostalog će nam se nalaziti okvir za stranicu čijim BS-om smo pristupili.

Direktorijum stranica predstavlja asocijativnu strukturu (mapu) pomoću koje pristupamo tablici stranica.

Umesto da imamo jednu veliku neprekidnu tablicu, izdelimo stranice u manje tablice i na koje povežemo tablicu koju nazivamo direktorijum. Pristupamo manjoj tablici gde nam se tražena stranica nalazi pomoću broja tablice (BT) kojim indeksiramo direktorijum.

Možemo imati nekoliko nivoa direktorijuma.

Čuvanjem početne adrese master (početnog) direktorijuma u posebnom registru praktično dobijamo \(n\) -arno stablo koje nam služi za prevođenje stranica u okvire.

Što nam je veća dubina stabla, to nam je prevođenje neefikasnije.

BT i BS “izvlačimo” kao uzastopne podnizove iz virtuelne adrese. Broj bitova koji je potreban za njih zavisi od veličine stranice i veličine adresnog prostora.

Redosled “izvlačenja” iz virtuelne adrese

Gde je \(k\) dubina stabla.

Šta sadrže stavke u tablici stranica virtuelne memorije? Objasniti.

Sadržaj:

• broj okvira
  • lokacija date stranice u glavnoj memoriji
  • vodi se za stranice koje postoje u glavnoj memoriji
• adresa stranice na disku
  • lokacija date stranice na disku
  • vodi se za sve stranice
• valid bit
  • označava da li je stranica u memoriji ili ne
• dirty bit
  • označava da li je sadržaj stranice menjan
  • ako je menjana, stranica se pri uklanjanju iz glavne memorije zapisuje na disku
• reference bit
  • koristi se za implementaciju pseudo-LRU algoritma
  • OS povremeno postavlja sve bitove referisanja na 0
  • pri pristupanju stranici bit se postavlja na 1
• informacija o vlasniku
  • OS mora da zna kom procesu pripada stranica
• bitovi zaštite
  • označavaju tip pristupa koji vlasnik ostvaruje (read, write, execute)

Šta je bafer tablice stranica virtuelne memorije (TLB) i čemu služi?

TLB = Translation Lookaside Buffer

TLB je asocijativni keš koji čuva poslednje korišćene stavke iz tabele stranica (između ostalog fizičke adrese).

Da njega nema, za svako prevođenje bila bi potrebna dva pristupa memoriji, jedan za pronalaženje okvira (koje može biti dosta sporo kada imamo nekoliko slojeva direktorijuma stranica), i drugi za pristupanje samoj vrednosti.

Korišćenjem TLB dovoljno često eliminišemo potrebu za pronalaženjem okvira čime znatno poboljšavamo performanse.

Objasniti princip preklapanja instrukcija u modernim procesorima

Princip preklapanja instrukcija se bazira na tome što se svaka faza izvršavanja (fetch, decode, execute) odvija u različitim komponentama procesora.

Ideja je da se sve tri faze odvijaju paralelno za različite instrukcije čime se značajno povećava količina obrađenih instrukcija po jedinici vremena.

Ovaj mehanizam podseca na pokretnu traku u fabrici.

Koji su osnovni uzroci zaustavljanja “pokretne trake” kod preklapanja instrukcija u savremenim procesorima? Koje se tehnike koriste za rešavanje ovakvih problema?

• resursni problem
  • događa se kada dve instrukcije na “pokretnoj traci” žele da pristupe istom resursu (npr. ALU), zbog čega može da dođe do serijalizovanog izvršavanje, čime se gubi na performansama
• data problem
  • događa se kada ulaz jedne instrukcije zavisi od izlaza druge, a obe se nalaze u “pokretnoj traci”
• kontrolni problem
  • događa se kada zbog grananja moramo da odbacimo neke rezultate koje smo računali posle grananja

Najčešće korišene tehnike za rešavanje su:

• tehnika prethodnog dohvatanja (prefetching)
• tehnika izvršavanja van redosleda (out-of-order execution)

Objasniti tehniku izvršavanja van redosleda (out-of-order execution)

Izvršavanje van redosleda je tehnika koja se koristi kod procesora visokih performansi da bi se iskoristili instrukcijski ciklusi koji bi inače bili neiskorišćeni zbog određenog kašnjenja.

Procesor izvršava instrukcije u redosledu koji određuje dostupnost ulaznih podataka, umesto njihovog originalnog redosleda u programu.

(fun fact Spectre i Meltdown greške su exploitovale ovu osobinu modernih procesora)

Objasniti tehniku predikcije grananja (branch prediction)

Ideja branch prediction-a je da prilikom dohvatanja instrukcije skoka predvidi da li će biti skoka ili ne, i u zavisnosti od toga da dohvati odgovarajuće instrukcije.

Predikcije grananja delimo na:

• Fiksno
  • unapred programiramo da li ćemo uvek da kažemo da će doći do skoka ili ne
• Statičko
  • unapred programiramo da li ćemo uvek da kažemo da će doći do skoka ili ne, u zavisnosti od toga koja vrsta skoka je u pitanju (da li je skok kod petlje ili vraćanje na kraju funkcije itd.)
• Dinamičko
  • na osnovu istorije poslednjih \(n\) grananja radimo ono što je se najviše radilo do sad
  • ispostavilo se kao najbolja tehnika

Šta su superskalarni procesori?

Superskalarni procesori su procesori koji implentiraju instrukcioni paralelizam tako što se sastoje od većeg broja funkcionalnih jedinica poput ALU-a zbog čega mogu da odrade više instrukcija po jedinici vremena nego skalarni procesori (oni koji mogu najviše jednu instrukciju po ciklusu).