Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35
Matfiz : Principy Počítačů / Řešené Otázky
Pokus o setřídění otázek ze všech možný písemek a doplnění o správné odpovědi (přispějte, můžete-li).
Historie a základy
Q:Význam Charlese Babbage.
A: Precetl jsem si o nem neco v Encyklopedii Brittanice a vychazi mi z toho tohle:
Charles Babbage predbehl svou dobu temer o stoleti navrhy dvou stroju – Difference Engine a Analytical Engine.
Difference Engine byla konstrukci vyrazne jednodussi, mela slouzit k pocitani hodnot polynomu, ale byla prvnim strojem uvadejicim koncept “pameti”, kam se ukladala data. Jinak mela vzdy k rychlemu opakovanemu provadeni jedne operace.
Analytical Engine mela byt prvnim skutecnym modernim pocitacem s jeho typickou architekturou – obsahovala cast ridici, pocitaci, vstupni a vystupni. Data a hlavně i instrukce měly být vkládány na děrovaných štítcích, takže stroj byl programovatelný. Poslední důležitou věcí pak byla instrukce skoku, dovolující rozhodovat o výkonu programu podle dat v paměti.
Bohužel ani jeden ze strojů nebyl dostavěn, první proto, že Babbage mezitím napadl druhý a druhý proto, že na postavení nebyly ani zdroje ani technické prostředky ;)
S Babbagovým vynálezem Analytical Engine vlastně vznikl pojem programování (přestože pak byl na dalších téměř sto let prakticky zapomenut). – h.
Q:Nakreslete graf Turingova stroje, který výstupem dorovnává vstup na lichou paritu.
A: Myslím, že by to mělo být takhle, jestli to chápu:
(Tohle je v první řadě hodně špatně zadaný. Jenom teď vidím už tři možnosti, jak si to vyložit, a to jsem se ani moc nesnažil vymýšlet další. /MZ? )
No, to souhlasím. Ale beru to tak, že sekvence [všechno, co bylo na vstupu; bit, co je teď na výstupu] má mít lichou paritu – aby bylo jasné, co ten můj graf vlastně ilustruje. Jinak příklad grafu jiného Turingova stroje najdete na slajdu 02-historie1.pdf. — Adam,
A: a já sem si říkal, proč ty body z Wikipedie nedat rovnou sem, když je to správná odpověď:
5 funkčních jednotek – řídící jednotka, aritmeticko-logická jednotka, paměť, vstupní zařízení, výstupní zařízení
Struktura je nezávislá od zpracovávaných problémů, na řešení problému se musí zvenčí zavést návod na zpracování, program a musí se uložit do paměti, bez tohoto programu není stroj schopen práce
Programy, data, mezivýsledky a konečné výsledky se ukládají do téže paměti
Paměť je rozdělená na stejně velké buňky, které jsou průběžně očíslované, přes číslo buňky (adresu) se dá přečíst nebo změnit obsah buňky
Po sobě jdoucí instrukce programu se uloží do paměťových buněk jdoucích po sobě, přístup k následující instrukci se uskuteční z řídící jednotky zvýšením instrukční adresy o 1
Instrukcemi skoku se dá odklonit od zpracování instrukcí v uloženém pořadí
Existují alespoň – aritmetické instrukce (sčítání, násobení, ukládání konstant,…), logické instrukce (porovnání, not, and, or,…), instrukce přenosu (z paměti do řídící jednotky a na vstup/výstup), podmíněné skoky, ostatní (posunutí, přerušení, čekání,…)
Všechna data (instrukce, adresy,…) jsou binárně kódované, správné dekódování zabezpečují vhodné logické obvody v řídící jednotce
ale je pravda, že se to skoro dá shrnout na: 1) oddělení programu a počítače, 2) jedna paměť pro instrukce a data, 3) sekvenční zpracování, 4) paměť, řadič, ALU, vstup a výstup
Reprezentace celých čísel
Q:(3x) Sečíst čísla 4310 -5210 (resp 41 a -45, 37 a -48) ve dvojkovém doplňku. Vysvětlit vytvoření doplňku.
A: Pokud jsem to dobře pochopil, tak je to úplně jednoduché, tzn. dělá se to takhle:
Převedeme obě čísla do binárního tvaru.
Záporné číslo nahradíme jeho dvojkovým doplňkem:
všechny bity čísla znegujeme
k výsledku přičteme 1
Nyní obě čísla sečteme. Při sčítání výsledek přeteče a po odříznutí tohoto přetečení dostaneme správný výsledek. – h.
Ještě k tomu dvojkovému doplňku: dvojkový doplněk k číslu A při reprezentaci n bity je číslo B, které po sečtení s původním číslem dá 2^n. Potom A je vlastně to samé jako 2^n – B a tudíž C – A = C – 2^n + B. No a protože 2^n se nám ořízne na nulu, tak C – A = C + B. Zjednodušeně: Odečítat číslo ve dvojkovém doplňku je jako přičítat dvojkový doplněk tohoto čísla. A na tom je přesně postavena reprezentace celých čísel ve dvojkovém doplňku. Čestmír
Q:Jaké jsou možnosti zápisu celých čísel? Na stejném čísle všechny demonstrujte.
A:
Ke všem způsobům je potřeba ovládat převod do binární soustavy, ale ten je na Obdržálkovejch slajdech docela názorně vidět.
Pro příklad zapíšeme všemi způsoby hodnotu -5.
Se znaménkovým bitem. První bit značí znaménko, další bity obsahují absolutní hodnotu čísla. V našem případě zapíšeme do prvního bitu jedničku (jako minus) a do dalších tří 101 (což je binárně pět), čímž dostaneme reprezentaci 1101.
Doplněk. Číslo nejdřív převedu do dvojkové soustavy a potom, pokud je záporné, z něj udělám doplněk – zneguju všechny bity a pak přičtu hodnotu jedna (tzn. sečtu to s číslem 00...001). V našem případě nejdřív napíšu binárně 5, tedy 0101 a pak, protože chci reprezentovat zápornou pětku, upravím na doplněk: nejdřív zneguju (dostanu 1010) a pak přičtu jedničku (a dostávám 1011).
S posunem. Určíme si nějaký interval a řekneme, že zápis 000...000 reprezentuje nejnižší číslo z toho intervalu a zápis 1111...1111 reprezentuje nejvyšší číslo z toho intervalu. V našem případě třeba máme k dispozici čtyři bity, tedy umíme reprezentovat 2^4 = 16 hodnot. Rozhodneme se reprezentovat hodnoty -7 až 8. Kdybychom tedy chtěli zapsat číslo -7, zapíšeme ho jako 0000, naopak číslo 8 jako 1111. Jakékoliv jiné číslo budeme reprezentovat tak, že od něj odečteme nejnižší reprezentovatelnou hodnotu (tedy v našem případě odečteme -7, rozumějte přičtěme 7) a získané číslo už běžně převedeme do dvojkové soustavy. Chceme-li reprezentovat třeba našch -5, zapíšeme je jako (-5+7) = 2 v dvojkové soustavě, tedy 0010.
Kdybyste dumali nad tím, jaký zvolit posun a jaké vyjdou u různých reprezentací rozsahy, tak vězte, že jako posun se volí liché číslo (tak to píše v předchozím příkladu i Martin? a je to tak i u exponentů podle IEEE 754), takže rozsah kladných hodnot je pak o jednu větší, než záporných (u dvojkového doplňku je naopak větší rozsah záporných hodnot). Obdržálek má ale ve svých slajdech sudý posun, takže mu posun a doplňek dávají stejné rozsahy. Symetrické rozsahy má reprezentace se znaménkem, ale zase v ní je i «záporná nula». — Adam
BCD (Binary Coded Decimal). Číslo reprezentujeme tak, že binárně přepíšeme každou číslici jeho desítkového zápisu. Na minus pětce by to bylo vidět špatně, pojďme zapsat třeba 123. To zapíšeme tak, že zapíšeme binárně číslo 1, pak binárně číslo 2 a pak binárně číslo 3, přičemž na každé z nich spotřebujeme čtyři bity (protože čtyři bity jsou nejmenší délka, na které můžeme reprezentovat všechna čísla 0..9). Takže 123 bychom zakódovali jako 0001 0010 0011. Pozor: pomocí BCD se zobrazují přirozená čísla, ne celá, u celých bychom ještě potřebovali nějaké to znaménko. – h.
Reprezentace čísel s plovoucí řádovou čárkou (IEEE 754)
Q:diskusia k zobrazeniu cisel podla IEEE754
A: Jak se číslo podle IEEE754 chová, když je v normalizovaném tvaru lze zjistit podle odpovědi na následující otázku (je potřeba jen nějaké to reverse engineering ;)), tady zmíním jaké všechny případy mohou nastat:
Pokud exponent je 0 (00...00) a mantisa také 0, je to reprezentace nuly (±0 podle znamínkového bitu).
Pokud exponent je 0 a mantisa je nenulová, pak je číslo ve formátu 0.mantisa x minimální exponent.
Pokud v exponentu nejsou samé nuly nebo samé jedničky, tak je reprezentováno číslo v normalizovaném tvaru.
Pokud jsou v exponentu samé jedničky (pokud jsem to dobře pochopil) a mantisa je 0, je to reprezentace ±nekonečna (zase podle znaménkového bitu).
Pokud jsou v exponentu samé jedničky a mantisa je nenulová, reprezentuje to NaN = “not a number”. – h.
Q: //Zápis dle normy
Zapiste cislo 0,118 v zaznamu pro plovouci radovou carku ve dvojkove soustave podle normy IEEE-754, pokud by pripoustela nasledujici parametry: exponent s posunem o 63, mantisa 8 bitu.
Zapište 0,121 do binární soustavy. Výsledek normalizujte a zapište podle IEEE-754 s parametry: exponent s posunem o 63, mantisa 8 bitů.
zapsat 3,5 podle IEEE 754
Zapište číslo 0.4645 ve tvaru s plovoucí desetinou čárkou. Zapište binárně exponent s decimálním základem. Zvolte vhodný tvar mantisy a zapište výsledek binárně.//
A: Obecně se takováhle úloha řeší takhle:
Vyrobíme znaménko: 0 pokud je číslo kladné, 1 pokud je záporné.
Převedeme číslo do binární soustavy (celou část postupně dělíme dvěma a zapisujeme od jednotkového bitu výše jedničky pro nenulové zbytky, nuly pro nulové; zlomkovou část násobíme dvěma a děláme to samé, tvoříme tak dlouho, dokud číslo není dost dlouhé do mantisy).
Normalizujeme mantisu – ořízneme ze začátku mantisy první jedničku a následující nuly, zapamatujeme si exponent (tj. ± počet bitů mezi číslicí za původní řádovou čárkou a první číslicí po oříznutí, nenormalizovaná mantisa nám nejspíš nehrozí, to by čislo muselo být hodně malé).
Převedeme exponent do dvojkové soustavy a přičteme k němu posun (nebo raději v obráceném pořadí, to většina lidí zvládá rychleji;) — Adam)
Složíme číslo: znaménko,exponent,mantisa (délka exponentu je log2(posun+1)+1 — Karl.. Jj. např. log2(127+1)+1 = 7+1 = 8. Lidi, kteří úplně nezblbli z Matfyzu, se ale na nějaké logaritmy vykašlou a řeknou si: posun je 127, rozsah musí být asi dvakrát tolik, takže 256 hodnot, a na 256 hodnot potřebuju 8 bitů, ne? — Adam)
Poznámka: Tímhle postupem se vlastně (řekl bych) původní číslo může zaokrouhlit směrem k nule, nezískáme tedy vždy nejbližší možnou hodnotu v IEEE 754. To podle mě není chyba, ale je dobré to vědět. — Adam
Blbostička na závěr: Správnost vašeho přepisu do IEEE-754 si můžete ověřit, pokud vlastníte C++ kompilátor. Rozdělte si binární zápis čísla ve formátu s posunem o 127 a mantissou 23 bitů na čtveřice bitů a převeďte je do hexadecimální soustavy. No a potom zapište tyhle čtveřice jako hodnotu proměnné i v následujícím programu. Tak třeba 3.5 je reprezentováno jako 0100 0000 0110 a 5x 0000, takže 0100 je 4, 0000 je 0 a 0110 je 6. To nám dává v hexadecimální soustavě 0x40600000. No a tenhle prográmek v C++ by vám měl (pokud se řídí IEEE-754 a pokud mají float i int 32 bitů – tzn. pokud jedete na «neexotické» architektuře) vypsat původní hodnotu toho čísla, tj. 3.5. Čestmír
Nebo kratší a správnější (chybí Ti tam return a vhodnější je unsigned, protože čísla >=1<<31 (záporné floaty) se do 32bitového intu nevejdou (resp. neměly by)) program v C:
Deprecated: Assigning the return value of new by reference is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/highlight/java.php on line 5
#include <stdio.h>
int main(){
unsigned hex = 0x40600000; /* hex cislo sem */
printf("%f\n", *(float*)&hex);
/* (void) getchar(); nema-li to z nejakeho duvodu skoncit */return 0;
}
Ufff, no převádět si výsledek do hexa jenom abych si to mohl zkontrolovat.. ;) Pokud jde jenom o to vidět bitovou reprezentaci floatu: MZ?
Deprecated: Assigning the return value of new by reference is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/highlight/java.php on line 5
int main()
{
float f; scanf("%f", &f); getchar();
unsigned __int32 n = *((unsigned __int32*)(&f));
for (int i = 31; i >= 0; i--)
{
std::cout << (((n & (1 << i)) > 0) ? 1 : 0);
if (i == 31 || i == 23) std::cout << " ";
}
getchar(); return 0;
}
Vypište možné chyby vzniklé ve formátu IEEE.
(Předpokládám, že je to špatně formulovaný a myslí se přetečení, podtečení, dělení nulou, chyby při zaokrouhlování atd. – jestli je to opravdu tohle, tak viz druhý a třetí slide od konce na 06_data. MZ?)
Q:Jak vznikají NaN a SNaN a jaký to má vliv na průběh programu?
A: Tahle «ne-čísla» (NaN = Not a Number) vznikají, když dojde k pokusu o nějakou nepovolenou aritmetickou operaci, například druhou odmocninu ze záporného čísla. Jsou podle normy IEEE754 reprezentovány samými jedničkami v exponentu a libovolnou mantisou. Liší se v prvním bitu mantisy a ve způsobu, jak je na ně reagováno. Co se týče toho bitu, nula znamená SNaN (signalling NaN) a jednička qNaN (tiché, tzn. normální, NaN). V reakci je rozdíl v tom, že jakmile vznikne nějaké SNaN, je obvykle volána výjimka, aby se s ním vypořádala (ve zbytku mantisy mohou ale nemusí být informace o vzniku SNaN, které vypořádávání usnadní) a pak je SNaN převedeno na qNaN. S qNaN se nic zvláštního neděje, prostě «probublává» operacemi dál (většina operací s NaN na jednom ze vstupů produkuje také NaN). – h.
implicitní, např. když se výsledky všech aritmetických operací ukládají do akumulátoru
Podle funkce registrů:
řídící registr (to má být asi conditional register, který určuje, jak se budou provádět určité instrukce)
registr operandu (to může být datový registr, adresový registr, “general purpose register” – registr pro obecné účely, takový mohu využít, pro data i adresy).
Pozn.: Tohle vypadá trochu jako vytažený z jeho slajdů, tj. «vysvětlení registrového modelu» to není. Pokud byste měli někdo obecný popis, sem s ním prosím ;) – h.
Q:Co je to modalita instrukcí, základní rozdělení.
A:
Doslovná Obdržálkova verze: operačního kódu (jak, např. směr rotace), operandů (co, kam, např. velikost a umístění), ochrany paměti (kdo, např. úroveň procesu potřebná k vykonání určité instrukce [třeba nastavení obsluhy přerušení nebo úrovně procesu])
Verze, která věc vysvětluje ;) :
Modalita operandů znamená, že instrukce je schopná fungovat nad operandama různejch velikostí a typů. Takže třeba příklad modality je, když má člověk stejnou instrukci na sčítání shortintu, intu a longintu. Kdyby měl na sčítání shortintu jednu instrukci, na sčítání intu jinou instrukci a na sčítání longintu ještě jinou instrukci, tak je to příklad NEmodální instrukce.
Modalita operačního kódu je například tohle: Chceš mít třeba instrukce na bitovej posun doprava a bitovej posun doleva. Můžeš udělat dvě různý instrukce – to je případ NEmodálních instrukcí. Nebo můžeš mít jednu a tu samou a nějakým bitem ji přepínat, jestli má rotovat doleva, nebo doprava, to je příklad, jak to udělat modálně. /MZ?
Modalita ochrany je podle mě třeba, že instrukci, kterou se nastavují obslužné rutiny přerušení, může vykonat jen supervisor, což je typicky operační systém. Nebo třeba instrukce, která nastavuje režim, ve kterém běží proces (zda běží jako supervisor). Takováhle modalita samozřejmě nejde nějak přepínat ani nebudou stejné instrukce lišící se jen modalitou (taková ochrana by byla k ničemu). Pokud na tom ale bude běžet nějaký OS, který na to kašle, tak třeba všechny procesy budou běžet v režimu supervisor. («Supervisor» říkám, protože takhle se tomu říká u Motoroly 68k, o které jsem kdysi něco četl, ale všeobecně jde prostě o nějakou privilegovanou úroveň procesu.) — Adam
Nepřímá adresace s preindexací – vysvětlete a ukažte použití.
Jestli je tím míněna preinkrementace, tak to znamená, že instrukce zná adresu ukazatele, ten nejdříve zvýší, a pak pracuje s daty, na který ukazatel ukazuje.
indirect registr adresace s postincrementaci (nejsem si jisty) + priklad instrukce, ktera to vyuziva
V instrukci je dán registr v němž je adresa. Nejdříve zpracuji cílová data, poté ukazatel (tedy obsah registru) zvýším. Typicky nějaká instrukce pro procházení pole (podobně jako to minulé).
Q:Uvedte zakladni metody reseni problemu skoku pri pouziti pipeline.
A:
Zpoždění skoku (počkám si, jak to dopadne, zatím udělám něco neškodného)
Pozn.: Já jsem přemejšlel, co by tohle mohlo znamenat a podle mně to je, že se nejdřív vyřídí všechny instrukce, které už jsou načaté a nejsou na skoku závislé, pak se pipeline vysype a provede se skok. – h.
Řek bych, že je to takhle: Provádí se dál jedna až dvě instrukce po instrukci skoku a kompilátor se musí postarat o to, aby byly neškodné, například nedestruktivní operace (přesun z paměti, aritmetika s obsahy jiných registrů) s výsledkem v registru, který pak cíl skoku kdyžtak stejně přepíše. — Adam
Predikce skoku (vím, jak to většinou dopadne, tak to risknu)
Paměť skoku (vím, jak to dopadlo minule, tak snad to bude stejně)
Multiple streams (projdu si všechny možnosti a pak holt použiju jen jednu) TH
Q:Vysvetlit funkci dispatch and reorder bufferu a napsat co ho muze ovlivnit
A: Dispatch a reorder buffer jsou jednotky out-of-order execution procesoru (tj. procesoru, který vykonává instrukce v jiném pořadí než v tom, ve kterém přicházejí). Dispatch buffer je fronta instrukcí, které již «přišly» a čekají na vykonání. Z dispatch bufferu putují na vykonávání tehdy, když jsou připravená všechna jejich vstupní data. Re-order buffer je starší název pro frontu, ve které naopak čekají výsledky vykonaných instrukcí. Tyto výsledky mohou být zapsány do registrů teprve tehdy, když už byly zapsány všechny předchozí výsledky. – h.
Přerušení
Q:Jake muzou byt priciny preruseni a jak se takove preruseni vykona?
A: Príčiny prerušenia:
Vonkajšie: význačné stavy vstupno-výstupných zariadení, chyby (napr. delenie nulou a pod.), zásahy užívateľa, poruchy HW
Vnútorné: inštrukcia na prerušenie (INT n, kde n je 0..255), výpadok stránky, segmentu, volanie slúžieb OS...
Q:Jak probíhá přerušení (podrobně od vzniku až po vyřízení)?
A: Priebeh prerušenia:
• Vznik
• Rozhodnutie o prijatí/neprijatí prerušenia (maskovateľné/nemaskovateľné)
• Identifikácia zdroja
• Určenie adresy obslužného programu
• Uloženie aktuálneho stavu CPU
• Vykonanie obslužného programu prerušenia
• Obnovenie stavu CPU a návrat do prerušeného programu
Paměť
princip prevodu virtualnej adresy na fyzicku, popisat pri ktorych krokoch sa zucastnuje cpu, mmu, os...
Způsoby přidělování paměti.
Q:popisat priklad statickej a dynamickej bunky pamate plus funkcie
A:Tohle má být jako např. stránky a segmenty?
Q:Jake jsou zakladni parametry pametove jednotky?
A: Podle slajdů jsou to:
kapacita – objem informace uchovatelný v jedné paměťové jednotce (obvykle ve slovech/bytech)
velikost “slova” – velikost (v bitech) přirozené jednotky paměti
přenosová jednotka – objem (v bitech), který lze přenést v jednom kroku
přenosová rychlost – rychlost, kterou mohou být data přenášena z/do paměti (špičková vs. zaručená)
vybavovací doba – čas, za který je paměť schopná vyřídit požadavek
cyklus paměti – doba mezi bezprostředně za sebou jdoucími požadavky
Q:Jak se deli pameti podle zpusobu pristupu. U kazdeho uvedte priklad vhodneho pouziti v pocitaci.
A: Obdržálek je ve svých slajdech dělí takto:
RAM (Random Access Memory) = paměť s náhodným přístupem, tzn. všechna paměťová místa mají svou adresu a doba přístupu k paměti nezávisí na adrese předchozího přístupu (je konstantní). primární paměť
SAM (Sequential Access Memory) = paměť se sekvenčním přístupem, tzn. paměťová místa nemusí nutně mít svou adresu a doba přístupu závisí na vzdálenosti od počátku. pevný disk (sekundární paměť)
DAM (Direct Access Memory) = kombinace předchozích dvou přístupů, paměťová místa mají adresy, ale přistupuje se k nim kombinací «náhodného» a sekvenčního přístupu. ?CDčka?
AAM (Associative Access Memory) = paměť s asociativním přístupem = to podle mě musí být paměť, ve které se místa adresují pomocí klíčů, pomocí kterých se pak v ní opět vyhledává. cache
CAM (Contents-Addressable Memory) = paměť, ke které se přistupuje podle části obsahu, obvykle s paralelním prohledáváním. ?taky cache? – h.
Cache
Q:popisat plnoasociativne mapovanie v cache-i
A: Je to takové mapování, při kterém je možné jakýkoliv záznam z paměti cachovat v libovolném místě cache, jeho opakem je přímé mapování:
Q:Vysvetlete princip primeho mapovani v cache a jeho vyhody a nevyhody.
A: Přímé mapování znamená, že pro každé místo v paměti existuje jenom jedno místo v cache, kde může být záznam z tohoto místa v paměti cacheován. Například může být část adresy z paměti klíčem, který toto místo v cache určuje. Výhodou je rychlost takové cache, protože MMU okamžitě ví, kam do cache sáhnout. Nevýhodou je, že zatímco plně asociativní mapování dovoluje vyhazovat z cache nejdéle nepoužité záznamy, u přímého mapování je něco takového nemožné. Je vždy potřeba vyhodit záznam na místě, kam patří nový záznam, čímž se sníží počet «cache hitů».
Q:Jaké jsou možnosti optimalizace cache?
A:Např. “exclusive cache” – to znamená, že data, která jsou v L1 cache nejsou už v L2. Pokud vím, tak toto využívá na svých procesorech AMD, narozdíl od Intelu, který data v L1 ukládá i do L2.
Q:zpusoby vyhledavani v cache
A: Počítám, že se asi jedná o:
přímý přístup bez vyhledávání – v případě cache s přímým mapováním
postupné procházení s porovnáváním klíče (u cache s asociativním mapováním)
paralelní prohledávání – klíč je porovnáván se všemi záznamy najednou – omezené vysokou cenou implementace
(Řešení: Od Obdržálka nešel třeba rozdíl přímého a asociativního mapování moc pochopit, přitom na Wikipedii to je pochopitelný za minutu. /MZ?)
Q:Vysvetlit a co je to CLOCK (tim se myslí jako takovou tu věc s pamětí, co Obdržálek vysvětloval pomocí ciferníku, ne hodinový signál).
A: CLOCK je (alespoň podle slajdů) algoritmus na výměnu záznamů v cachi. Pro každý záznam zavádí proměnnou (bit) A. Pracuje tak, že při přidání záznamu do cache nastaví jeho A na 1 a pokud je potřeba vyměnit stránku, provádí následující:
pokud je A = 1, nastaví A na 0, posune se o jeden záznam dále a pokračuje znovu tímto krokem
pokud je A = 0, vymění tento záznam za nový a končí
Tímto způsobem se z cache vyhazují záznamy až tehdy, pokud po dvou průchodech celého seznamu nebyly potřeba. – h.
Sběrnice
popisat prenos dat po zbernici bez ucasti procesora, rozdelenie plus popis
Q:rizeni sbernice bez ucasti CPU – princip, vyhody a nevyhody
A:Je to prenos dát, ktorý nie je riadený inštrukciami procesora, ale zvláštnym radičom. Poznáme tri režimy, a to dávkový režim, režim kradnutia cyklov a transparentný režim.
Dávkový režim:
• procesor “povie” radiču: čo chce preniesť, koľko a kam
• Radič procesoru: hold (som pripravený)
• Procesor radiču: HLDA (Hold Acknowledge) (ok, vykonaj prenos, zbernicu nepotrebujem)
• Samotný prenos
• Radič procesoru: /hold (hotovo)
• Procesor radiču: /HLDA (beriem na vedomie...)
Kradnutie cyklov:
• Radič uspí procesor, vykoná prenos dát, zobudí procesor. Má to nevýhodu, že takto sa nedá uspať procesor na dlho...a je to technicky náročnejšie na implementáciu.
Transparentný režim:
• Radič spozná, keď procesor zbernicu nepoužíva a vtedy vykoná prenos, toto nijako nezdržuje procesor pri práci, akurát sa takto nedajú robiť väčšie prenosy naraz...
Použitie DMA (direct memory access)
Priamy prístup do pamäti je schopnosť zbernice posielať dáta bez účasti procesora. K tomu slúži radič DMA, ktorý tento prenos zaisťuje, a to priamo medzi vstupno-výstupnými zariadeniami a pamäťou. CPU iba dá podnet na začatie prenosu, o čo sa postará DMA a on si zatiaľ vykonáva iné operácie. Keď sa prenos skonči, CPU dostane signál od DMA, že prenos sa vykonal. Typicky DMA kopíruje bloky pamäte zo systémovej RAM to alebo z buffera na I/O zariadení. Hlavná výhoda teda je, že procesor nemusí čakať na dokončenie prenosu, ale môže vykonávať dôležitejšie úlohy.
Výrazy
Q:Uvedte zpusoby zaznamu vyrazu a na vzdy stejnem vyrazu demonstrujte. Pak uvedte jejich vyhody a nevyhody.
A: Spôsoby záznamu výrazov poznáme:
• Infix – typicky takto zapisujeme výrazy v matematike, musíme určiť priority operátorov, prípadne to riešiť zátvorkami, pre počítače najmenej vhodný zápis
• Prefix (alebo poľský zápis) – operátory sú pred operandmi, výraz nepotrebuje určovať priority, netreba zátvorky, vyhodnotenie je dané samotným zápisom.
• Postfix (reverzný poľský zápis) – operátory sú za operandmi, taktiež netreba zátvorky, priority...oproti infixu má miernu výhodu, že jeho vyhodnotenie je striktne zľava doprava (napr. pomocou zásobníka), čo je ešte jednoduhšie pre vyhodnotenie na počítači.
• Príklad na zápis (zo slajdov):
• Infix: (A-B) / (C + D*E)
• Prefix: /-AB+C*DE
• Postfix: AB-CDE*+/
Q:Zapište v postfixu: (7+5)/9–2*( (3/9)+(2/(6–1/4) ) )
A: 7 5 + 9 2 – / 3 9 / 2 6 1 – 4 / / +
vysvetlit vyhodnocovani postfixu, prevest 1-(4–2)*(3–4/(5–3)) a vyhodnotit jako postfix s vypisy zasobniku (pri vysvetlovani chce, ze kdyz prijde operator, vyzvedne se POTREBNY pocet operandu ze zasobniku, ne automaticky dva)
Spolehlivost, dostupnost
Q:Definujte dostupnost systému.
A: Dostupnosť A(t) je pravdepodobnosť správneho chodu v čase t. Zaoberá sa tým, ako dlho je systém v stave schopnosť pracovať a je meradlom, ako často je systém v poriadku.
Operational availability (z pohľadu užívateľa)
A = MTBM/(MTBM+MDT) = MTBM/(MTBM+CM+PM+DT)
Inherent availability (z pohľadu maintenance personnel, nezahŕňa preventívnu údržbu, poruchy, oneskorenia v dodávkach materiálu a administratívne oneskorenia.)
A = MTTF/(MTFF+MTTR)
Achieved availability (dosiahnutá dostupnosť, z pohľadu maintenance department, zahŕňa opravy a preventívnu údržbu, ale nezahŕňa oneskorenie v dodávke materiálu a administratívne oneskorenia)
A = MTBM/(MTBM+MAMT)
Vysvetlivky:
MTBM = Mean Time Between Maintenance
MDT = Mean Down Time
CM = ? (ak viete, doplňte)
PM = ? (ak viete, doplňte)
DT = žeby Downtime?
MTTF = Mean Time To Failure
MTTR = Mean Time To Repair
MAMT = Mean Active Maintenance Time
MTBF = MTTF + MTTR
NON = Number of Nines, napr. 6NON => A(t) = 0.999999
Q:Vysvetlete pojem spolehlivost.
A: spoľahlivosť R(t) je pravdepodobnosť správneho chodu do času t.
FIT = Failures in time (počet zlyhaní za 10^9 hodín)
Q:napisat rozdelenie podla zotavenia z chyb
A: Dělíme na
Backward Error Recovery = při výskytu chyby se vracíme do místa před tím, než se chyba stala a odtud znovu začnem (zpomalení a složitější návrh, ale malá degradace dat)
Forward Error Recovery = při výskytu chyby pokračujeme dále a řešíme chybu «za běhu» (odstraní zpomalení a je jednodušší na návrh, ale dražší na HW a data mohou degradovat) – h.
Q: Byla zadána sedmice bitů 1111101, o které se vědělo, že jsou to čtyři bity dat obalené v Hammingově kódu 7–4, a měla se z ní získat a opravit čtveřice přenesených bitů.
Pozn.: Jak jsem tak na ten odkaz koukal, tak jsem zjistil, že podle wikipedie se ten kód píše opačným směrem, než ho píše Obdržálek, tak to je asi dobré mít na paměti ;) (to řešení o řádek výš s tím počítá)
Q:Jaké jsou typické problémy fault-tolerating systémů?
Q:Vysvětlete synchronní a asynchronní přenos a srovnejte.
A: Synchrónny prenos je riadený hodinovým signálom. To znamená, že každá udalosť, ktorá môže pri prenose vzniknúť, je podmienená «príchodom» hodinového signálu. Pri asynchrónnom prenose sú tie udalosti riadené nejakou predchádzajúcou udalosťou.
02-historie1.pdf. — Adam,
von Neumanovy architektury.
TH