NSWI120 Principy počítačů (ZS 2012/2013)

Informace o předmětu

Náplň přednášek

• 1. přednáška (1. paralelka: 2.10.2012 & 2. paralelka: 4.10.2012)
  Stručný obsah:
  Požadavky na zkoušku • doporučená literatura - viz dole na stránce ♦ počítač a jeho architektura • Harvardská vs. von Neumannovská architektura • (mikro)procesor (CPU [Central Processing Unit]) • operační paměť • kódová vs. datová paměť • samomodifikujcí se kód • řadič (controller) • řadič paměti • periférie • I/O (Input/Output) • sběrnice (bus) ♦ desktop (PC [Personal Computer]) uvnitř • zdroj a požadavky na napájení počítače • potřeba chlazení počítače • problém throttlingu • základní deska (motherboard) • základní periferie a typické řadiče • northbridge vs. southbridge • procesorová cache a její výhody a problémy ♦ komunikace se zařízeními: PIO (Programmed Input/Output) vs. DMA (Direct Memory Access)
  Materiály:
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 2. přednáška (1. paralelka: 9.10.2012 & 2. paralelka: 11.10.2012)
  Stručný obsah:
  Tištěné spoje a SMD (Surface-Mount Device) • proces výroby integrovaných obvodů • typické prvky: odpor, dioda, tranzistor, kondenzátor • silicon wafer ♦ analogový vs. digitální (číslicový) přenos (reprezentace) dat - vlastnosti, výhody a nevýhody • hodinový signál (clock) • sériový vs. paralelní přenos • bit (b) vs. byte (bajt, B) vs. oktet • kB/MB/GB vs. KiB/MiB/GiB • "typické" mocniny dvojky: 2, 4, 8, 16 = 2^4, 32, 64, 128, 256 = 2^8, 512, 1024 = 2^10, 2048, 4096 = 4 k, 8192, ..., 65536 = 2^16, ~4200000000 = 2^32 • slovo (word) vs. dvojslovo (doubleword, dword, případně longword) vs. čtyřslovo (quadword, qword) • koncept N-bitového počítače (procesoru) • vývoj Intel 4004 → 8008 → 8080 → 8086/88 • platforma x86 • platforma IBM PC (Personal Computer) ♦ přehled architektury počítače Atari 800 XE (8-bit, mikroprocesor MOC 6502, paměť a její řadič, řadič periferií, koprocesor [grafický čip] ANTIC) ♦ operační paměť jako volatile paměť • programovací jazyk BASIC • program v paměti počítače (příkaz LIST z BASICu) • start/boot/restart/reboot počítače • studený (hard reboot/cold reboot/restart) vs. teplý (soft[ware] reboot/warm reboot/restart) restart počítače • př. klávesa RESET na počítači Atari 800 XE, nebo klávesová kombinace Ctrl+Alt+Del(ete) na IBM PC ♦ operační pamět = RAM (Random Access Memory) • načtení programu/dat do paměti - příklady vstupních zařízení: klávesnice, pevný disk, magnetofonová kazeta (není "RAM") • ROM (Read-Only Memory) • příkaz CLOAD z Atari BASICu
  Materiály:
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 3. přednáška (1. paralelka: 16.10.2012 & 2. paralelka: 18.10.2012)
  Stručný obsah:
  Adresový prostor (address space) • adresa (address) → ukazatel (pointer) • adresová vs. datová sběrnice a jejich šířka • příklady: 6502 vs. 8086 vs. 8088 vs. 80386DX vs. 80386SX vs. Pentium vs. Pentium Pro • zarovnání dat (data alignment vs. data padding)/přístupů k paměti • zarovnání na velikost dat (na adresu dělitelnou velikostí dat) - výhody a problémy s přístupem k nezarovnaným datům (misaligned data access) ♦ mapování částí adresového prostoru (a řadič paměti) • příkazy PEEK a POKE v BASICu • paměťové banky (bank) a mechanizmus přepínání bank (bank switching) • ukázka bank switchingu na Atari 130 XE (128 kB RAM vs. 16-bit adresový prostor 6502): PORTB na adrese 54017 ♦ komunikace z periferiemi/jejich řadiči • registr/port řadiče/zařízení • port-mapped I/O a oddělený adresový prostor • memory-mapped I/O (MM I/O, paměťově mapovaná zařízení) • video paměť grafické karty a přístup k ní pomocí MM I/O
  Materiály:
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 4. přednáška (1. paralelka: 23.10.2012 & 2. paralelka: 25.10.2012)
  Stručný obsah:
  Paměti ROM (PROM vs. EPROM vs. EEPROM vs. Flash [ROM] - non-volatile) vs. RAM (SRAM vs. DRAM - volatile) ♦ FAQ: proč je u 32-bit procesoru položka v adresovém prostoru 1 byte a ne 4 byty (přece by se ušetřilo/naadresovalo více dat)? ♦ desktop (PC) vs. server (mainframe) vs. cluster vs. cloud (Amazon, Google, Microsoft Azure, privátní) • víceprocesorové systémy • NUMA • embedded systémy, SoC [System on Chip] (ARM, nVidia Tegra) • jednočipy (microcontrollers) - Microchip (PIC), Atmel (AVR) • Harvardská architektura • firmware • vlastnosti a výhody jednotlivých typů počítačů ♦ provádění programu ve vyšším programovacím jazyce • Pascal/C/C++ → assembler • překladač (compiler) • instrukce/instruční sada (instruction set) • čísla v šestnáctkové soustavě (hexadecimální) • hexa editor • strojový kód (machine code) • disassembler • cross-compiler
  Materiály:
  • http://www.pspad.com/ - PSPad: volně šiřitelný textový editor pro Windows s možností editace (např. binárních dat) v hexa režimu
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 5. přednáška (1. paralelka: 30.10.2012 & 2. paralelka: 1.11.2012)
  Stručný obsah:
  Příklady jednočipových počítačů (datasheet) • běh programu v BASICu na Atari → interpret BASICu • překladač vs. interpret (anglicky interpreter): výhody a nevýhody • princip jednoduchého interpretu ♦ jak vypadá instrukční soubor • základní druhy instrukcí • kalkulačka vs. počítač → podmíněný skok (historická odbočka: Charles Babbage & Analytical Engine & Ada Lovelace [ejda lavlejs] - koncept moderního počítače a programování) ♦ program counter (PC)/instruction pointer (IP) • registr (obecné a specializované) • registr vs. cache vs. RAM • příklad: registry procesoru 6502 (8-bit procesor, 16-bit adresový prostor: A [a X, Y, SR, S] → 8b, PC → 16-bit) • accumulator • struktura instrukce: opcode + argumenty (typické: registr, immediate, adresa) • varianty instrukce (různý opcode, délka) • symbolická jména registrů ♦ program pro sečtení 13 a 29 (instrukce ADC, LDA, STA u 6502) • ukládání vícebytových hodnot v paměti: little vs. big endian (vs. bi-endian) • výhoda little endian • volání podprogramu (instrukce JSR u 6502) a návrat z podprogramu (instrukce RTS u 6502) ♦ předání kontroly nad procesorem: interpret BASICu → strojový kód → interpret BASICu (příkaz USR v Atari BASICu)
  Materiály:
  • 05_40139e.pdf - datasheet k jednočipovým počítačům Microchip PIC12C5XX (příklad velmi omezené RAM [v řádu desítek bytů], oddělené programové paměti typu EPROM, a permanentní [non-volatile] datové paměti typu EEPROM [v řádu jednotek bytů]) (zdroj: http://ww1.microchip.com/downloads/en/devicedoc/40139e.pdf)
  • 05_InterpretBasicu.zip - interpret jednoduché varianty jazyka BASIC (projekt pro Lazarus) [případně jen samotný zdrojový soubor v Pascalu: 05_InterpretBasicu.pas]
  • Popis instrukční sady procesoru 6502 (google: 6502 instruction set)
    • http://www.obelisk.demon.co.uk/6502/instructions.html - 6502 Instructions: přehled instrukcí procesoru 6502 (použito na přednášce)
    • http://www.6502.buss.hk/6502-instruction-set - 6502 - Assembly, Computers & Technologies: alternativní přehled instrukcí procesoru 6502 (obsahuje příklady strojového kódu pro každou variantu [opcode] nějaké instrukce)
  • 05_Secteni13a29.asm.txt - (pod)program pro sečtení čísel 13 a 29 v assembleru pro 6502 (výsledek se ukládá na adresu 4096)
  • 05_Secteni13a29-StrojovyKod.asm.txt - přepis programu (viz výše) do strojového kódu 6502 (hodnoty jednotlivých bytů jsou zapsány ve desítkové soustavě)
  • 05_Secteni13a29-ZavadecDoPameti.bas.txt - program (zavaděč) v Atari BASICu pro nahrání programu ve strojovém kódu (viz výše) do paměti na adresy 5000 až 5008
  • 05_Secteni13a29-ZavolaniZBasicu.bas.txt - příkazy Atari BASICu pro spuštění zavaděče (viz výše), předání řízení do strojového kódu, a ověření výsledků (obsah paměti na adrese 4096 by se měl změnit z počátační hodnoty na hodnotu 42)
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 6. přednáška (1. paralelka: 6.11.2012 & 2. paralelka: 8.11.2012)
  Stručný obsah:
  Typické formy instrukcí (X:=Y, X:=opY, X:=YopZ) • implicitní vs. explicitní operandy (typické varianty: př. MIPS = 3 expl., x86 = 2 expl., 6502 = 1 expl.) - důvody a výhody/nevýhody • př. 6502 → x86: LDA/STA → MOV, ADC → ADD, JSR → CALL, RTS → RET ♦ typy registrů • akumulátorová architektura → obecné registry • př. evoluce 8086 → 80386 ♦ inline assembler ♦ argumenty instrukcí: registr / immediate (konstanta) / (přímá) adresa • nepřímé adresování ♦ debugger - princip fungování a implementace ♦ load/store architektura • CISC vs. RISC
  Materiály:
  • 06_CppInlineAssembler.zip - ukázka použití inline assembleru x86 v C/C++ zdrojovém kódu pro Microsoft C++ Compiler (projekt pro Visual Studio 2010 • hlavní zdrojový soubor je "Program.cpp")
  • 06_PascalInlineAssembler.zip - ukázka použití inline assembleru x86 v Pascal zdrojovém kódu pro překladač Free Pascal • (projekt pro Lazarus)
  • 06_SimulatorProcesoru6502.zip - jednoduchý simulátor procesoru 6502 vzniklý úpravou interpretu BASICu z předchozí přednášky (simuluje pouze instrukce LDA, STA, ADC, RTS, které jsme používali na předchozí přednášce) (projekt pro Lazarus - poznámka: samotný zdrojový kód je v textové podobě uložen v souboru s příponou .lpr)
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 7. přednáška (1. paralelka: 13.11.2012 & 2. paralelka: 15.11.2012)
  Stručný obsah:
  Bitové operace - příklady a výhody použití • posun (shift, SHR, SHL) • aritmetický posun • rotace (rotation, ROR, ROL) • and (clear/reset), or (set), xor (flip) • příznak (flag) ♦ příklad struktury opcode ♦ kódování znaků a znakové sady (kódové stránky/code page) • ASCII a rozšíření, speciální znaky ♦ Unicode - výhody/nevýhody • 32-bit vs. 8-bit (UTF-8) vs. 16-bit (UTF-16) • surrogates • combining characters • možné různé reprezentace jednoho "znaku" (grafému) ♦ reprezentace znakových řetězců (s explicitní délkou, s nulou na konci) ♦ skok (jump) vs. podmíněný skok (conditional jump/branch) • příznakový registr (flags) • instrukce compare vs. subtract • příznak zero (equals) • příznak carry
  Materiály:
  • 07_SimulatorProcesoru6502OrShift.zip - původní 06_SimulatorProcesoru6502.zip, kde je u načítání 16-bitové little endian hodnoty nahrazeno sčítání a násobení operacemi or a posun doleva (projekt pro Lazarus • Poznámka: samotný zdrojový kód je v textové podobě uložen v souboru s příponou .lpr)
  • Zobecnení simulátoru procesoru 6502 - využití bitových operací pro zkoumání vnitřní struktury opcode → zjednodušení samotného simulátoru + zjednodušení budoucího přidávání dalších instrukcí a adresních režimů:
    • 07_SimulatorProcesoru6502RozborOpcode.zip - zobecněná a zjednodušená implementace simulátoru 6502 (projekt pro Lazarus)
    • http://www.llx.com/~nparker/a2/opcodes.html - The 6502/65C02/65C816 Instruction Set Decoded: přehled struktury opcode u instrukční sady procesorů řady 6502 (zde zavedená jmená konvence tří skupin bitů AAABBBCC v opcode je použita v přechozím příkladu vylepšeného simulátoru) (zdroj google: 6502 opcode decode)
  • 07_EmulatorPocitaceAtari130XE.zip - emulátor počítače Atari 130 XE: rozšíření poslední verze simulátoru procesoru 6502 o simulaci zařízení/řadičů obsažených v počítači Atari 130 XE (MMU/EMMU = řadič paměti [implementována je simulace základní i rozšířené paměti RAM a mechanismu bank switching], GTIA - čip starající se o zobrazení barvy [jako příklad je implementována simulace jednoho HW registru pro změnu barvy]) (projekt pro Lazarus)
  • 07_EmulatorPocitaceAtari130XE-ANTIC.zip - rozšíření emulátoru o simulaci "grafické karty/čipu" ANTIC (ANTIC pomocí DMA čte z "obrazové paměti" informace o znacích, které se mají zobrazit na obrazovce - u Atari je "obrazová paměť" oblast paměti RAM začínající na adrese 40000)
  • Oprava chyby v simulaci grafického čipu ANTIC (přemapování znaků do kódování ASCII):
    • 07_EmulatorPocitaceAtari130XE-ANTIC-SpravnaSimulace.zip - emulátor Atari 130 XE zahrnující simulaci 6502, MMU, GTIA, ANTIC (projekt pro Lazarus)
    • http://www.atariarchives.org/mapping/appendix10.php - ATASCII And Internal Character Code Values: mapování znaků mezi kódy ATASCII a Atari Internal Code
    • http://www.atariarchives.org/c3ba/page004.php - Reading the Keyboard Codes: článek popisující různá kódování znaků používaná na počítačích Atari (zde uvedený algoritmus pro převod z Atari Internal Code do ATASCII je použit v opravené verzi emulátoru)
  • 07_PrekladIfACyklu.zip - příklad překladu If-Then-Else podmínky a For-While cyklu do strojového kódu x86 (projekt pro Visual Studio 2010 • výstup z disassembleru v průběhu ladění programu je zde: 07_PrekladIfACyklu-VypisDisassembleru.txt • hlavní zdrojový soubor je "Program.cpp")
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 8. přednáška (1. paralelka: 20.11.2012 & 2. paralelka: 22.11.2012)
  Stručný obsah:
  Překlad příkazů if-then-else • překlad příkazů cyklu • relativní adresa - př. u instrukcí JMP/JGE (x86), BEQ (6502) ♦ reprezentace (záporných) celých čísel v počítači • unsigned (bezznaménkové) vs. sign bit (znaménkový bit) vs. bias (s posunem) vs. one's complement (jedničkový doplněk) vs. two's complement (dvojkový doplněk) - výhody a nevýhody ♦ reálná čísla ve dvojkové soustavě • reprezentace reálných čísel s pevnou desetinnou čárkou (fixed point) vs. s pohyblivou desetinnou čárkou (floating point) - výhody/nevýhody • exponent, matisa, normalizovaná mantisa • standard IEEE 754 • speciální hodnoty nekonečno (infinity), NaN (Not-a-Number) ♦ taktovací frekvence procesoru (hodinový signál/clock) • základní přehled fází zpracování instrukce v procesoru • doba zpracování instrukce v taktech/cyklech
  Materiály:
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 9. přednáška (1. paralelka: 27.11.2012 & 2. paralelka: 6.12.2012)
  Stručný obsah:
  Emulátor Atari 8-bit jako virtual machine (VM) • př. DOSBox (x86 PC na x86 PC) - důvody použítí a výhody • VMware Player (Workstation)/Microsoft VirtualPC - výhody, srovnání s interpretovaným kódem • příklad implementace vs. implementace debuggeru • relokace kódu ♦ ASLR (Address Space Layout Randomization) - důvody použití ♦ překlad složitějších výrazů do strojového kódu • výpočet hodnot parametrů při volání podprogramu • problém s omezeným počtem registrů • připomenutí hierarchie paměti • srovnání rychlosti/velikosti: registr vs. cache (různé úrovně: L1/L2, případně L3) vs. paměť (RAM) • problém s velikostí cache (možné rozdíly v reálné výkonnosti např. O(n) vs. O(n*n) algoritmů) ♦ intermediate language (IL)/bytecode (cíle/výhody/nevýhody) • Java/.NET jako VM • Just-in-Time (JIT) compiler • VM jako sandbox ♦ zásobníkový stroj (architektura) • koncept registrového zásobníku • typické instrukce - př. .NET IL/Java bytecode/x86(x87) floating-point registers (st)
  Materiály:
  • http://atari800.sourceforge.net/ - emulátor počítačů Atari 800/130 XE (vstup do konfigurace pomocí F1) • na stránce je třeba si stáhnou kromě samotného emulátoru i obrazy pamětí ROM a nakopírovat je do adresáře s rozbaleným emulátorem
  • http://www.dosbox.com/ - emulátor počítače "IBM PC" z 90. let: s procesorem 80386, grafickou kartou VGA, zvukovu kartou Sound Blaster + implemementace operačního systému kompatibilního s MS-DOS
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 10. přednáška (1. paralelka: 4.12.2012 & 2. paralelka: 13.12.2012)
  Stručný obsah:
  Operační systém (OS, operating system) • základní funkce (spuštění a běh programů nezávisle na [konfiguraci] počítači) • API (Application Programming Interface) • příklady API funkcí OS • API funkce různých OS a problém s přenositelností ♦ funkce (vyššího) programovacího jazyka • funkce běhového prostředí (runtime) a standardní knihovny jazyka (standard library [stdlib], runtime library [RTL]) • obcházení funkcí prog. jazyka (př. tvorba UI [User Interface] - Windows/Linux), resp. funkcí OS (př. zvuk MS-DOS) - problémy s přenositelností • externí knihovny jako nástroj přenositelnosti (př. UI: knihovna Qt pro Windows/Linux) • př. Pascal → Windows → HW vs. Pascal → Linux → HW vs. Java → Android → Linux → HW ♦ spustitelný soubor ([spustitelná] binárka, executable) • jako obraz paměti (memory dump) [Atari 8-bit] • OS jako zavaděč programů (program loader) • relokace programu (relocation) • základní struktura spustitelného souboru (př. Windows - .exe [PE {Portable Executable}/COFF], Linux - ELF [Executable and Linkable Format]): kód (text), data, relokační tabulka (relocation table), vstupní bod programu (entry point, main) ♦ spuštění počítače • první instrukce zpracovaná CPU • OS v ROM (Atari 8-bit) vs. program v ROM bez OS (jednočipy) vs. v ROM zavaděč OS (firmware a jeho funkce) • př. boot PC: BIOS (Basic Input Output System) vs. (U)EFI ({Unified} Extensible Firmware Interface) ♦ paměť přidělená programu: kód, data (globální proměnné, konstanty), halda (heap), zásobník (call stack) • příklady umístnění zásobníku (platforma x86, 6502) • registr adresy vrcholu zásobníku (stack poiter (SP)) • práce se zásobníkem na úrovni strojového kódu (př. PUSH [x86] / PHA [6502], POP [x86] / PLA [6502]) • realizace volání podprogramu (funkce/procedury) (př. CALL [x86] / JSR [6502], RET [x86] / RTS [6502]) • přetečení a podtečení zásobníku (stack overflow/underflow)
  Materiály:
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 11. přednáška (1. paralelka: 11.12.2012 & 2. paralelka: 20.12.2012)
  Stručný obsah:
  Organizace paměťového prostoru aplikace • organizace spustitelných souborů (sekce debug symbolů [symbol table], velikost zásobníku, stripped binary) ♦ moduly a statické linkování • object file • příklady Windows (PE [COFF], .obj), Linux (ELF) • linkování k různým verzím standardní knihovny programovacího jazyka (přenositelnost) ♦ dynamicky linkované knihovny (DLL) • tabulky importů a exportů ♦ volání API funkcí jádra (kernel) OS (pevná adresa [Atari], standardní dynamicky linkovaná knihovna [Windows, příklad kernel32.dll]) ♦ předávání parametrů a návratových hodnot funkcí/procedur • volací konvence (calling convention) • rámec zásobníků (stack frame) • lokální proměnné • koncept bázové adresy (registru) pro odkaz na lokální proměnné a parametry • typické volací konvence na platformě x86 (Pascal, C (cdecl), stdcall, fastcall)
  Materiály:
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 12. přednáška (1. paralelka: 18.12.2012 & 2. paralelka: 3.1.2013)
  Stručný obsah:
  Připomenutí call stacku • ukládání dočasných proměnných mimo registry • prolog/epilog funkcí/procedur • naked funkce/procedury ♦ důvody pro specifikaci ABI (Application Binary Interface) • ABI vs. API • příklady Posix (Linux, Cygwin), Win32 (Windows, Wine) ♦ vlákno [thread] a jeho stav • multithreading • proces a paměť procesu sdílená vlánky • kooperativní přepínání kontextu (context switch) a jeho implementace • plánovač (scheduler) • vzdání se procesoru (yield) • kvantum (quantum, time slice) ♦ implementace Delay • aktivní vs. pasivní čekání • stavy vlákna a přechody mezi nimi (running, ready-to-run, sleeping/waiting) ♦ round-robin plánovač • idle thread • prioritní plánovač • priority boost
  Materiály:
  • 12_NakedFunkce.zip
  • 12_PrepinaniZasobniku.zip
  • 12_PrepinaniZasobnikuJednaProcedura.zip
  • 12_VlaknySdilenePromenneKooperativni.zip
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 13. přednáška (1. paralelka: 8.1.2013 & 2. paralelka: 10.1.2013)
  Stručný obsah:
  Stav vlákna terminated • způsoby ukončení vlákna (kill) ♦ podmínky pro probuzení vláken (př. uplynutí zpoždění [sleep], dokončení I/O operace [možno implicitně], ukončení vlákna [join]) ♦ tabulka otevřených souborů • stav procesu • přepínání kontextu procesu (multitasking) ♦ polling vs. hardwarová přerušení (HW interrupts) (asynchronní) • obsluha přerušení • maskování přerušení • tabulka přerušení (vektory přerušení) • IRQ • nemaskovatelná přerušení (NMI) ♦ synchronní přerušení • traps (faults, exceptions), příklady • softwarová přerušení ([nepřímé] volání API funkcí jádra OS, breakpoint) ♦ UNIXové signály jako obdoba (SW implementace mechanizmu) přerušení (paralela s Windows kernel APC [Asynchronous Procedure Call]) ♦ vynucení yield v obsluze přerušení časovače • preemptivní přepínání vláken • (ne)reentrantnost kódu
  Materiály:
  • 13_VlastniBreakpoint.zip - ukázka breakpointů jako softwarového přerušení (používá inline assembler pro platformu x86 • ukazuje dvě varianty instrukcí SW přerušení) (projekt pro Visual Studio 2010, hlavní zdrojový soubor je "Program.cpp)"
  • 13_VlaknySdilenePromennePreemptivni.zip - ukázka vícevláknové aplikace pro systém s preemtivním přepínáním vláken • vlákna spolu sdílí 2 proměnné (projekt pro Lazarus využívající API funkce Windows)
  • 13_VlaknySdilenePromennePreemptivniSWriteLn.zip - rozšíření přechozí aplikace o ladící výpisy pomocí funkce WriteLn → ilustrace problému s nereentrantností kódu (nereentrantní volání WriteLn) (projekt pro Lazarus využívající API funkce Windows)
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  
• 14. přednáška (1. paralelka: 15.1.2013 & 2. paralelka: 16.1.2013)
  Stručný obsah:
  Víceprocesorové systémy a vlákna • symetrické vs. asymetrické (procesory Cell, CPU + GPU, apod.) víceprocesory - vlastnosti a výhody (SMP [Symmetric Multiprocessing] vs. AMP [Asymmetric Multiprocessing] vs. NUMA [Non-Uniform Memory Access]) • vícejádrový systém (multicore) • start a běh víceprocesorového systému • meziprocesorová přerušení • afinita vlákna/procesu (thread affinity) - potřeba v AMP/SMP • problém s koherencí cacheí (cache coherence) → problém rychlostí vláken sdílejících data na SMP ♦ problémy s vícevláknovým zpracováním a sdílenými daty • příklad s dvousměrně vázaným seznamem • race condition ♦ kritická sekce (critial section) • atomické (atomic) operace • vzájemné vyloučení (mutual exclusion) • Petersonův (Peterson's) algoritmus ♦ zámek (lock/mutex) a jeho implementace • potřeba atomicky prováděných instrukcí • Test and Set • Compare and Swap (CAS), resp. Compare and Exchange • zámek s pasivním čekáním ♦ další synchronizační primitiva a jejich vzájemná převoditelnost • semafor (semaphore) • randez vous (bariéra/barrier) • monitor ♦ problémy se zámky a jejich řešení • deadlock (uváznutí) • Coffmanovy podmínky • livelock • problém dining philosophers • priority inversion • convoying (lock convoys) • co se známky při předčasném ukončení vlákna: uvonění → porušení invariantů vs. držení → deadlock • granularita zámků, problém producent/konzument ♦ real-time systémy a jejich problémy ♦ lock-free vs. wait-free algoritmy/datové struktury • možné problémy s nezarovnanými zápisy z více vláken • memory model • paměťová bariéra (memory barrier) • memory model a procesor vs. programovací jazyk • problém s volatile• optimistic concurrency • lock-free implementace zásobníku a její problémy • pozor na mezivýpočty • ABA problém
  ♦ Ochrana aplikací a samotného kernelu jako funkce OS • privilegované instrukce (privileged instructions), příklady • uživatelský režim (user mode) vs. režim jádra (kernel mode/supervisor mode/privileged mode ♦ ochrana paměti • fyzický vs. virtuální adresový prostor • princip mapování mezi adresovými prostory ♦ segmentace - adresa jako segment + offset • tabulka segmentů a bázová adresa a limit segmentu • typy segmentů a jejich ochrana • systémové segmenty • sdílení segmentů • segmentation fault ♦ stránkování (paging) • stánkovací tabulky a jejich hierarchie • page fault (výpadek stránky) • (process) working set • swap file ♦ potřeba komunikace mezi procesy: IPC (Inter-Process Communication) • sdílená paměť (shared memory), semafor (semaphore), roura (pipe), signal ♦ monolithic kernel vs. microkernel
  Materiály:
  • 14_ParalelniMaximumZaklad.zip - počítání maxima posloupnosti ve více vláknech (ukázka zrychlení na víceprocesorovém/vícejádrovém systému) (aplikace v C++ s použitím Windows API pro Visual Studio 2010)
  • 14_ParalelniMaximumGlobalni.zip - rozšíření implementace o počítání globálního maxima (ukázka zpomalení na víceprocesorovém/vícejádrovém systému) (aplikace v C++ s použitím Windows API pro Visual Studio 2010)
  • 14_ParalelniMaximumGlobalni-Kontrola.zip - ověření nesprávnosti implementace v předchozím příkladu (test, že dochází k race condition) (aplikace v C++ s použitím Windows API pro Visual Studio 2010)
  • 14_ParalelniMaximum.zip - správná implementace pomocí zámků (aplikace v C++ s použitím Windows API pro Visual Studio 2010)
  • 14_ParalelniMaximum-CompareExchange.zip - správná lock-free implementace s použitím CAS operace (a ukázka zrychlení) (aplikace v C++ s použitím Windows API pro Visual Studio 2010)
  • 14_LockFreeZasobnik.zip - ukázka lock-free datové struktury (zásobník pomocí jednosměrně vázaného seznamu) • pozor: tato implementace není správná (může zde vznikat několik race conditions, mimo jiné ilustruje i ABA problém) (projekt pro Lazarus)
  • 14_LockFreeZasobnik-Verze2.zip - vylepšení implementace lock-free zásobníku z předchozího příkladu (opravení jedné race condition) • pozor: ve Free Pascalu tato implementace stále není správná (ilustrace ABA problému) (projekt pro Lazarus)
  • 14_SdilenaPametServer.zip - ukázka fungování sdílené paměti (využívá Windows API) • aplikace vytvoří sdílenou pamět a poté sleduje její změny (projekt pro Lazarus)
  • 14_SdilenaPametKlient.zip - aplikace očekává, že bude spuštěna, pokud již beží aplikace "SdilenaPametServer" a zapisuje do jí vytvořené sdílené paměti (projekt pro Lazarus)
  • Kopie tabule na konci přednášky (pozor: po mazání, připisování a přepisování v průběhu, tj. nemusí dávat bez kontextu smysl):

    1. paralelka		2. paralelka

  
  

Zkouška

Doporučená literatura

Loňské stránky předmětu