Základy operačních systémů

  • definice OS - v podstatě neexistuje, jen 2 pohledy na jeho úlohu: "extended machine" / "resource manager" ( ∀ OS by měl splnit ) a abstrakce HW ( prostředků pro software, který běží nad OS ).
  • prostředky - procesor, paměť, tiskárna - hmotné, synchronizační primitiva - nehmotné (tj. pro OS jako resource manager).

    • Historie

  • 40's - 50's žádný OS, elektronky, programy přímo ve stroj. kódu, vstup - děrné štítky, ∀ PC je unikát.
  • 50's - 60's - tranzistory, dávkové systémy - programy čekají ve frontě - už náznak jednoduchých OS. 1. vyšší pg. jazyk - Fortran.
  • '65 - '80 : integrované obvody nízké integrace, IBM 360 - velký pokrok - první univerzální PC. konfigurovatelný HW, multitasking - přidělování procesoru, spooling - sdílení zařízení, interaktivní uživatelé - terminály: obraz & klávesnice, zaručení přiměřené doby odezvy. virtuální paměť; zač. spojování počítačů (přímá linka), real-time: reakce na urč. událost, deadline: soft, hard.
  • lidi okolo PC: 3 kasty : opravář, systémový programátor, aplikační programátor; OS měl veřejné zdrojáky, upravovaly se přímo.
  • 80's - dnes : obvody s vysokou integrací, stolní PC. nejdřív 8-bity na hraní & PDP, 1. seriózní OS: Unix, potom Win, MacOS.
  • síťový OS - přístup k prostř. jiných PC, viditelný pro ost. uživatele - je jasné, co s kým sdílím. distribuovaný OS - skupina PC spojených sítí, prostředky sdílené tak, že nevím, kde se nachází (už se ale moc nepoužívá).
  • user-friendly SW - okna, hot-plug; další sorta lidí - "uživatelé"
  • '95 - dnes - "chytrá přenosná zařízení" - PalmOS, Symbian, WinCE - chovají se trochu jinak než ost. OS, jednodušší, umí i něco navíc.

    • Zákl. pojmy

  • systémové volání - rozhraní pro využívání fcí OS - mezi OS & programy - WinAPI, Unix - Syscall, definováno na úrovni pg. jazyka i instrukcí procesoru. procesory - běh ve 2 úrovních: uživ. app. a systémová (k dispozici jsou všechny prostředky) - přecházení z úrovně na úroveň.
  • program - přeložený zdroják, spustitelná věc
  • proces - program aktuálně běžící v paměti
  • soubor - "perzistentní" data - přežijí vypnutí PC.

    • Architektury OS

    klasická struktura - monolitická

  • nejstarší, už IBM 360, Unix, Win., všechny služby uvnitř, prováděny ve chráněném módy, jádro poměrně velké, "údajně" nejrychlejší.
  • program zavolá službu OS, přes tabulku se zjistí adresa přísl. fce, ta se zavolá a vrátí výsledek.
  • nevýhoda: horší údržba - je-li v programu chyba, může poškodit zbývající části systému, rozšiřování za běhu je komplikované.

    • Virtuální stroje

  • původní nápad : Virtual Machine pro IBM360 - jde oddělit multitasking od OS jako ext. stroj.
  • nad HW - další vrstva - "Virtual Machine" - měla plánovat, vyrábí pro procesy iluzi holého HW; dneska např. VMWare dělá to samé.
  • pro IBM360 - dalo se použít v kombinaci s CMS (jednoúlohový) i původního OS360 (rychlejší než OS360 na holém HW).
  • dnes: definuji abstraktní stroj, pro něj překládám programy ( .NET, Java ) -> přenositelnost, kompatibilita (IBM AS400 - desítky let), problém - pomalé.

    • Mikrojádro

  • snaha aby část běžící v kernel módu byla co nejmenší ( ~ 10 KB ), nejnovější, experimentální, často pro Distribuované OS (dnes už nepoužívané), hodně procesů & komunikace (klient/server), mikrojádro řeší jenom komunikaci.
  • filesystém apod. - procesy - aplikace posílají přes jádro požadavky
  • jediný komerční OS - Chorus (ústředny)
  • výhoda: když něco spadne, nepoškodí to zbytek, moduly jdou měnit za běhu, komunikace jde snadno rozšířit na komunikaci po síti.

    • Architektura WinNT

  • jádro poměrně malé (~1MB), schopné (pro vyšší vrstvy jsou některé schopnosti skryté), na vzniku se podíleli schopní Unixáři. snaha o malou velikost, přenositelnost
  • jádro neutrální vzhledem k vyšším vrstvám, nad ním lze vybudovat různé systémy (Windows subsystém, POSIX, OS/2)
  • WinAPI, nad tím - DLL, mezi kernelem a HW: "hardware abstraction layer" - lze jednoduše upravit pro jiné architektury (Alpha, IA-64)
  • grafické drivery jediné mají přímý přístup k HW; části API (USER, GDI) - v jádře, přechod user/kernel - ntdll.dll - ∀ programy využívají
  • služby/aplikace běží v app. módu nad jádrem

    • Architektura Linuxu

  • na úrovni SW - přenositelnost; abstrakce HW.
  • nad HW - kernel, nad ním systémová volání, hodně podobné Windows.

    • Procesy a plánování

  • dříve: 1 proces = 1 vlákno; dnes procesy používají více vláken = míst, kde se aktuálně vykonávají instrukce uvnitř 1 procesu. Vždy 1 vlákno je počáteční - začíná buď na nějaké dané adrese, nebo je def. v kódu, vytvoří všechny ost. vlákna.
  • proces sdružuje sdílené prostředky vláken, hlavně paměť, i např. soubory.
  • v linuxu - trochu jinak - vlákna "nejsou", jen procesy, které ale mohou sdílet paměť (dobastlené)
  • kontext procesoru - informace nutná pro přepínání mezi vlákny - musí být možné uložit a obnovit, závisí na konkrétním CPU, obs. registry, další interní věci (neviditelné třeba ani z OS - Motorola 68xxx)
  • multiprocessing - přepínání procesů na 1 procesoru, t.ž. zdánlivě běží paralelně
  • vlákno připuštěné k procesoru - mohou nastat 3 situace: konec, volání operace která trvá dlouho, násilné odstavení od procesoru oper. systémem.
  • procesy nesmí vědět, že se na CPU střídají - OS musí umět uložit kontext procesoru.
  • přerušení - z pohledu OS obsluha synchronní (vyjímka procesoru - souvisí s kódem pg.)/asynchronní (nesouvisí přímo- stisk klávesy) události
  • proces - sdílí prostředky, ev. práva (vlákna nemívají spec. práva), na některých OS celá hierarchie procesů - po skončení procesu musí být ukončeny synovské (Unix, ne Windows), ∀ proces má PID - pomocí něj lze killnout, debugovat
  • vlákno - implementace na 3 úrovních:
    a) uživ. prostor - OS o tom nic neví (knihovna spouští vlákna), nutné zajistit asynchronní signály o čase (pro přidělování prostoru vláknům) (starší)
    b) jádro - zabudování přímo do systémů (jako první: Solaris)
    c) hybrid - např. webservery - jádro má s přiliš mnoha vlákny problémy => knihovna pustí pár jaderných vláken, nad nimi řídí uživ. vlákna; nutné opět RTC. poměr jaderných x aplikačních vláken se v čase mění, někdy je i víc jaderných
  • prostředky : proces - adres. prostor, práva, signály, asynchronní události, ost. HW; vlákno - program counter, registry CPU, pár tajných věcí = kontext, zásobník (víc vláken = víc zásobníků).
  • stavy procesu/vlákna : blokován / běží / připraven (&přechody mezi nimi). po spuštění - "připraven" - nic kromě OS nebrání výpočtu; předán k běhu po naplánování, rozběhne se tam kde má kontext. pokud běží moc dlouho, OS odstaví od procesoru, pokud se rozhodne požádat o službu co trvá dlouho, OS mezitím zablokuje & nechá běžet jiný proces. některé OS - více stavů (př. Unix - Zombie)

    • Přerušení

  • umožňuje odstavit proces od CPU.
  • synchronní - souvisí se zpracovávanými instrukcemi: instrukce "TRAP" (teoretická) - na různých platformách různá - přechod do kernel módu, pomocí ní se implementuje i volání OS (IA-32 - "int" ); výjimky procesoru - problémy odstranitelné/neodstanitelné (ochrana paměti, výpadek stránky)
  • asynchronní - čtení z disku; OS může dát CPU jinému procesu, postará se o načtení dat & proces nastaví na "připraven". dřív - v okamžiku přerušení disku OS načítal softwarově - pomalé, dnes - DMA - disk & řadič vyřeší sami, pak vyvolají přerušení.
  • řadič DMA - přepne se do režimu "Bus Master", přenese data & vypne se. technika scatter-gather - v rámci jednoho přenosu víc kusů dat - "scatter" : DMA řadič v rámci 1 přenosu uloží z 1 místa na několik různých (např hlavičky TCP/IP - jinak zbytečné kopírování), "gather" - např. při stránkování paměti - načítání stránek, které fyzicky na disku nemusí být u sebe, složení na 1 místo do paměti.
  • polling - některá zařízení neumí tento systém (př. LPT) => kontrola stavu zařízení - jednou za čas OS kontroluje stav. BIOS - např. čtení z disku zajišťuje pollingem - tj. furt se používá.

    • Obsluha přerušení

  • HW jen rozpozná typ přerušení a zavolá správnou adresu obslužné rutiny ( buď danou natvrdo - IA-64, nebo pomocí tabulky vektorů přerušení - IA-32) - mezi 2 instrukcemi.
  • 1. akce - uložt kontext procesu (aby program přerušení nepoznal), 2. zjistit typ přerušení ( některá zařízení sdílí IRQ), 3. vyvolat obslužnou rutinu, 4. obnovit kontext / přeplánovat.

    • Plánování

  • úkol OS - přidělovat procesor - vytváří iluzi multitaskingu, pracuje s plánovacími entitami - buď vlákno nebo proces (podle toho jestli jádro rozpozná vlákno), stará se o to scheduler / plánovač.
  • 2 hlavní druhy : preemptivní / nepreemptivní - preemptivní: pro velké OS - i kdyby procesy chtěly uzurpovat procesor, nemůžou; nepreempt. - malé, staré OS: záleží na ochotě procesů sdílet procesor, OS sám od sebe proces neodstaví od CPU - "kooperativní multitasking" - aplikace musí "často" volat systémová volání, nebo specif. fci OS, díky které se vzdá CPU.
  • OS využívá přerušení k odstavení procesu od CPU. aspoň 1 přerušení - časovač - nastává pořád. obsluha časovače = přeplánování; lze k tomu využít ale lib. přerušení. nepreemptivní OS buď nemaj časovač, nebo ho nevyužívají, pokud proces volá API - jiné přerušení, pak mohou přeplánovat taky.

    • cíle plánování

  • občas protichůdné
  • spravedlnost - ∀ proces dostane CPU ( složitější - priority, i s nejnižší prioritou by se ale proces měl k CPU dostat )
  • efektivnost - co nejvíc CPU využito, co nejmenší režie - samotné plánování má být rychlé
  • doba odpovědi - interaktivní uživatelé musí mít odezvu => interaktivní procesy musí mít přednost ( není těžké, většinou moc CPU nepotřebují )
  • průchodnost - co nejvíc spočítaných věcí za jednotku času - co nejrychlejší konec výpočtů na pozadí
  • min. režie systému - souvisí s efektivitou
  • dnes navíc plánovače musí zvládat multiprocesory - vytížení VŠECH CPU.

    • kritéria

  • údaje, které OS při plánování pomáhají (zjišťuje si je)
  • vázanost na CPU x I/O - zda proces převážně počítá, nebo čeká na I/O - dá se zjistit snadno - kontrolou stavu při časovači (chce CPU x čeká), může se v čase měnit!
  • dávkový x interaktivní - dnes už nejde poznat, u starých OS to bývalo explicite uvedeno.
  • priorita - čím důležitější, tím větší má přednost
  • výpadky stránek - podle počtu výpadků (tj. v podstatě vázanosti na I/O) se dá rozhodovat
  • skutečný čas CPU - kolik se reálně počítá
  • i další

    • priority

  • znamená důležitost procesu (vznikly na vojenských PC)
  • dneska - priorita má 2 části: statickou (daná předem) x dynamickou (mění se s časem - cílem je spravedlnost plánování - aby i nedůležité procesy dostaly CPU)
  • OS vybírá procesy s nejvyšší prioritou (součet statická&dynamická), procesy se stejnou se střídají
  • k nižším prioritám se postupně přičítá dynamická => časem se dostanou k CPU, pak dostanou zpět statickou - "stárnutí".

    • algoritmy plánování

  • FIFO - nepreempivní plánovací alg., procesy v 1 frontě, kdo se zařadí první, první počítá, nemá priority (lze zavést setříděním fronty)
  • Round Robin - preemptivní, časová kvanta (timeslice), stejné jako FIFO, ale OS ví, kolik dal procesu času, po tu dobu má nárok na CPU, potom : konec, zablokování se, běží dál - proces který měl procesor jde na konec fronty - bez priorit (opět lze doplnit). problém - jaké zvolit kvantum (menší: lepší iluze multitaskingu, větší: menší režie), dnes ~ 100ms., další: přesnost časovačů (dnes ~ 1ms, menší kvantum nelze), kvanta můžou být různá podle priorit.
  • Víc front se zpětnou vazbou - chytřejší, pozná I/O x CPU - vázané procesy. N front, (N-1) - FIFO, poslední je Round Robin, I/O vázané procesy skončí v nejvyšší (krátké čas. kvantum), CPU-vázané v nejnižší (dlouhá kvanta). po spuštění je proces na konci nejvyšší fronty. plánování - hledá se nejvyšší neprázdná fronta. 3 případy vypršení kvanta : konec procesu, zablokování => přesun o frontu výš, počítá furt => níž. většinou docela funguje, úrovní nebývá hodně.
  • SMP - symetrický multiprocesor - plánování na víc procesorech (OS s tím musí počítat). fronta procesů, proti ní fronta volných CPU. je-li volný procesor & připravený proces => přiřadí se, problém dřív: procesory, nemaj-li co dělat čekaj ve smyčče - spotřeba energie. dnes: pasivní čekání (spec. instrukce/přerušení) - OS musí umět, jinak zpomaluje. dnes typicky sdílená cache, procesory si z ní tahaj data - problém naplánování procesu pokaždé na jiný CPU - zpomalení (koherence cache&RAM - ∃ mechanismy)- "cache crashing/ping-pong" - řešení - pro multi-threadové věci min. sdílené paměti, privátní data by měla být v jiných cache-linech (min. jednotka pro práci s cache) - ex. tzv. afinita procesu k procesoru - mohu říct, že chci, aby urč. proces byl přednostně plánován na stejný CPU, nebo: vlákna 1 procesu na stejný CPU.
  • Real-Time - jiná třída plánování - systém, který čeká na události, po nastání událsti musí do dané doby splnit úkol (deadline). plánování tohoto je NP-úplné, ex. jen heuristiky. Real-Time soft x hard - propásnutí = vážný problém. HW větš. předimenzováno. použití - často v telef. ústřednách.

    • Plánování - Windows

  • na úrovni vláken, plánovač není 1 modul - po celém jádře na různých místech.
  • důvody k přeplánování: připravenost vlákna k běhu, změna priority, konec běhu, změna vázanosti na CPU
  • 32 priorit, ∀ 1 fronta; 32-bit maska neprázdných, multiprocesor - 32bit maska volných CPU => 32 CPU MAX!! (64-bit: 64), 16 real-time (kernel), 15 normálních, 1 systémová (nulování stránek paměti). normal = 8.
  • bere se vždy nejvyšší neprázdná fronta, čas. kvanta (záleží na CPU/HAL ~ 10/15 ms). na zač. ∀ vlákno 6 jedn(32- server), ∀ časovač: -3 (-12), při zablokování -1!.
  • boost priority - na 1 čas. kvantum zvýším o několik tříd (5?) při urč. události: ukončení I/O, semafor, aktivace okna, zpráva oknu, ochrana před nenaplánováním (300 jedn. bez naplánování -> přidá se priorita)
  • přeplánování: chtěné - zablokování -> po probuzení čas kvantum -= 1, nechtěné - preempce - na zač. fronty své priority, -= 3. (vyčerpání kvanta => na konec fronty)
  • multiprocesor: ∀ vlákno 2 čísla: ideální CPU, poslední CPU. plánování: 1.) ideální, 2.)poslední, 3.)aktuální, 4.)libovolný CPU. není-li volný CPU, může okamžitě odstavit vlákna s nižší prioritou (1.)ideální, 2.)poslední, 3.)nejvyšší z možných čísel CPU)

    • Plánování - Linux

  • od jádra 2.6 s konst. složitostí (dřív lineární), multiprocesor optimalizován pro 1-2 procesy na 1 CPU (ale rozumné i pro víc), afinita procesů k procesorům, interaktivní procesy, spravedlivý.
  • multiprocesor: ∀ CPU fronta - runqueue, 2 prioritní fronty ( "aktivní", "vyčerpané" ), 140 priorit, vybírá z aktivních, po doběhnutí přepočítá timeslice (pro 1 proces - dřív pro všechny najednou), hodí proces do vyčerpaných, po vyčerpání všech se fronty prohodí.
  • vybírá z 1. neprázdné priority (fronty), poč. statická priorita ∈ < -20, 19 >, dynamická ∈ < -5, 5 > (heuristika podle info o procesu )
  • vyvažování front na multiprocesoru - když je někde úplně prázdná nebo ∀ 1 ms, pokud není co na práci, ∀ 200 ms při vytížení. hledá nejdlelší frontu, hledá kam přesunout (vždy do vyčerpaných), opakuje dokud není vyváženo.

    • Meziprocesová komunikace a synchronizace

  • problém: race conditions - pokud běží víc úloh (pseudo)paralelně a sdílejí nějaké prostředky, zajistit domluvu na způsobu sdílení, jinak toto nastane - výsledek situace přístupu ke sdílenému prostředku závisí na plánování - př. spooler => nedeterminismus !!
  • operaci se sdíleným prostředkem nesmí provádět víc procesů najednou - vzájemné vyloučení = mutual exclusion.
  • lok. data ∀ vlákna - bez problémů, sdílená: glob. proměnné, heap - problémy => nutná identifikace kritických sekcí kódu, kde se pracuje se sdílenými prostředky. navíc často vlákna sdílí různé prostředky s jinými různými vlákny, tj. krit. sekce ∀ prostředek zvlášť.
  • pro čtení není problém, jen zápis (při něm se musí zastavit i čtení). nutné najít krit. sekci (občas problém - cizí knihovny) & zajistit synchronizaci.
  • podmínky synchronizace : ∀ synchronizační kód musí dodržovat:
    1) žádná 2 vlákna nesmí být najednou v krit. sekci
    2) nelze předpokládat nic o počtu / rychlosti CPU
    3) žádný proces mimo krit. sekci nesmí blokovat jiný proces ve vstupu do ní
    4) žádný proces nesmí zůstat nekonečně dlouho v krit. sekci (požadavek pro procesy samotné!)
  • synchronizační primitivum : metoda, kterou nabízí OS/compiler, která dovolí dosáhnout vzájemného vyloučení. 2 druhy: aktivní - aktivní čekání: spotřebovává čas CPU, jednodušší, test přístupu rychlý. pasivní - pokud proces nemůže do krit. sekce, uspí se, dokud ho něco neprobere => šetří CPU (je ale potřeba zásah OS - složitější primitiva), pomalejší, pro časté přístupy nevhodné - velká režie.

    • Aktivní čekání

  • zakázání přerušení : zakáže vyvolat časovač, nebude možné přeplánovat (to ale nesmí dělat běžný proces, lze jen v kernel-módu - jinak zneužitelné), funguje jen na 1 CPU (jinak časovače jiných CPU, která si ještě posílají přerušení navzájem)
  • zámky - nefungují!!! ( while ( lock ) {}; lock = 1; critical; lock = 0; ) - pokud se přeplánuje mezi koncem testování a nastavením zámku, dojde k chybě (zámek je sám o sobě sdílený prostředek).
  • důsledné střídání - ( while ( turn ≠ myTurn ){}; critical; turn = nextTurn; ) - vlákna se střídají o sdílený prostředek - funguje, ale je pomalé, pokud nejsou krit. sekce stejně dlouhé - vlákna na sebe čekají => nepoužívat!
  • Petersonovo řešení - vylepšení důsledného střídání, krit. sekce obalí voláním enter_region(), leave_region(). sdílené proměnné int turn, interested[2];. enter_region( int process_no ){ interested[ process_no ] = true; turn = process_no; while( turn == process_no && interested[ 1-process_no ] ) {} }; leave_region( int process_no ){ interested[ process_no ] = false; }; do proměnné turn zapisuji paralelně, ale nejdřív zapisuju, pak testuju. pořadí volání - důležité. tohle funguje jen pro 2 procesy, ale jde rozšířit??
  • instrukce TSL (spin-lock) - "test and set lock" - nutné mít takovou instrukci na daném procesoru - otestuje kus paměti & pokud zjistí že obs. danou hodnotu, uloží tam jinou (danou) - celé musí probíhat atomicky na úrovni HW. - enter_region: mov eax, 1; xchg eax, [lock]; test eax,0; jnz enter_region; ret. leave_region: mov [lock], 0; ret;. (např IA-32 má xchg "compare-exchange", na P4-HT pomalé (virt.procesory vytížené), instrukce "pause" (P4) není AMD-kompatibilní)

    • Pasivní čekání

  • sleep / wakeup - nefunguje!! ATOMICKÉ fce implementované OS; sleep uspí sama sebe, wakeup probudí daný proces. nefunguje - př. klasické synchronizační problémy : producent-konzument - sklad na cestě mezi producentem a konzumentem, nutné zajistit, aby producent přestal vyrábět, když je plný, aby konzument přestal odebírat když je prázdný (běžně víc prod.&konz. - spooler). problém stejný jako zámky : mezi testem podmínky ( if ( sklad_count == sklad_max ) ) a např. uspáním se může stav změnit! (mohou usnout producent i konzument a zastavit se !!!).
  • semafory - synchronizační primitivum, běžně OS, jde i uživatelsky, ale složité. fronta (množina) uspaných procesů & čítač (celočíselný, větší rozsah), na něm ATOMICKÉ operace down/up ("p"/"v" - Dijkstra), 2 možnosti - jen nezáporné/ i záporné hodnoty; spec. případ - jen binární semafor. down - čítač > 0 : čítač--, pokračuje; čítač == 0 : uspí se, přidá se do fronty; up - neprázdná fronta - vezme proces z fronty a probudí za down; prázdná fronta - čítač++; pro záporné počty down vždy sníží hodnotu (ale při ≤ 0 uspí), up vždy zvětší čítač o 1, při < 0 odblokuje 1 proces za down. (tj. záp. hodnota udává počet čekajících procesů). nutné dát pozor na pořadí up/down, aby se vše nezablokovalo (př. producent&konzument)
  • monitory - pokus ulehčit práci s tímto; větš. věc compileru - třídy (např. Java): ∀ proměnné privátní, někt. fce veřejné. ozn. třídu jako monitor, uvnitř 1 instance kódu monitoru (na jeho veřejných metodách) je (OS) zajištěno vzáj. vyloučení threadů. problém - když thread na něco čeká uvnitř monitoru - zablokuje se; pro umožnění vstupu jiných k monitoru -> "podmíněné proměnné" - fronta zablok. procesů & na nich operace wait a signal. wait(podm_prom) zablokuje proces a umožní jinému přístup k monitoru (čeká než podm_prom == true); signal - probudí proces z fronty zablokovaných (nastaví podm_prom = true): problém - jsou pak 2 procesy v monitoru - 2 řeš.: a) kdo probouzel se atomicky hned uspí b) kdo probouzel, hned (atomicky) vypadne z monitoru.
  • zprávy - data předávaná mezi odesílatelem & příjemcem, strukturovaná/ne, OS rozumí/ne. i odeslání prázdné zprávy je informace; implementováno typicky OS; podobá se síť. komunikaci => oblíbené v distrib. OS; (dnes: Win - RPC, LPC). 2 atomické fce: send (odešle zprávu, neblokuje se, odblokuje příjemce, pokud na zprávu čeká), receive (přijímá zprávu, pokud není žádná dostupná, zablokuje se). skladování a adresace zpráv - 2 možnosti: 1) ∀ PID ex. fronta zpráv (autom. vytvořená OS) - problém: zjišťění PID, přetékání schránek. 2) mailboxy : centrální skladiště, send i receive používají číslo mailboxu; příjemců i odesílatelů může být víc. v praxi - odesílatel se při plné schránce příjemce zablokuje!.
  • rendez-vous (randezvous :) ) - schránka velikosti 0 - odesílatel čeká na příjemce nebo naopak, po předání zprávy jsou oba odblokovány - potkají se na 1 místě (kódu) v 1 čase.
  • ekvivalence primitiv - většina převodů jednoduchá - monitor/semafor - přímočaré. jediný problém - semafor pomocí zpráv. řešení - 3. strana - spec. proces - správce semaforu - pro up/down se správci pošle žádost o operaci, pak je proces POVINNEN čekat na výsledek. správce pošle odpověď, když je semafor volný. po up sice není nutné čekat, ale pro zachování symetrie se to dělá.
  • v praxi používané : spin-lock - ∀ procesor má dnes něco jako instrukci TSL, aktivní čekání, tj. vyžaduje krátké krit. sekce, málo čekání; kritické sekce - enter_critical(), leave_critical() - blokovací primitivum OS, pomalé, ale bývá rychlejší než semafory. semafory - OS, čekání typicky delší dobu ( na nějakou událost )

    • Synchronizační problémy

  • producent-konzument - viz výše
  • obědvající filosofové - N filozofů u kulatého stolu, jedí & přemýšlí. problém - k jídlu potřebují 2 vidličky, ∀ má jednu => chtějí brát sousedovi. (tj. k prostředků sdílených N procesy, snaha aby pracovalo co nejvíc). for( ;; ){ think(); take_fork(i); take_fork((i+1)%N); eat(); put_fork(i); put_fork((i+1)%N); }. take_fork() blokovací - problém: co když všichni vezmou 1 vidličku. možnost: vezmu levou, zkusím vzít pravou, když to nejde, položím obě -> furt zkouší zvedat, blokují se. řešení - velké zámky - není moc pěkné.
  • ospalý holič - má 1 křeslo, čekárnu s N křesly. přijde do práce, nemá zákazníky => spí. přijde zákazník -> vzbudí holiče, ten pracuje, další zákazníci lezou do čekárny. když je plná jdou jinam, holič holí, dokud má lidi, pak se uspí. typicky - server s konečnou frontou požadavků & klienti.

    • Vyšší synchronizační primitiva

  • RWL - read-write-lock: dovolím na urč. prostředku víc paralelních četení, ale zápis chci exkluzivní. write-lock: když nikdo nečte a chci zapsat, vpustím, ostatní čekají; jinak čekám já. read-lock: pokud je zámek pro čtení, mohu číst; pro zápis - čekám. často má write přednost, nutné ale řešit hladovění čtecích procesů.
  • bariéra - hl. vlákno pustí pomocná, ta počítají; chce počkat na výsledky od všech vláken => pomocná vlákna : přihlášení & odhlášení se od bariéry, hl. vlákno čeká na její uvolnění.
  • reentrantní zámky fce co lezou do krit. sekce se volají navzájem => může se zablokovat -> reentrantní zámek zjistí, který proces zámek provedl& pokud je to můj vlastní, pustí mě. (dá se implementovat jinými, občas dělá problémy; lze řešit jinak: napsat neblokovací varianty fcí ).
  • uzamčené operace - dost procesorů nabízí uzamčení aritmetické oprace (sčítání, ++) - pro vytvoření unikátního čítače; např. pro generování unikátních ID. lze udělat i spin-lockem, ale je složitější, dost knihoven umí samo.

    • Praxe

  • Windows - sjednocení všech synchr. volání - čekání na objekt; jednotný typ - HANDLE, jednotná fce na čekání na 1/víc objektů (2 možnosti - and/or <-- or na Unixu moc nejde ), je timeout; ∀ primitivum má definováno kdy je volné; semafor: volný při > 0, event - binární událost- autoreset nebo manuální; kritické sekce; zamčený jednosměrný spoják, uzamčená operace <-- zajištěna i přenositelnost
  • Unix - OS má semafor, zbytek je implementován knihovnou PTHREAD - je tam všechno: podm. proměnné, mutex, RWL, spin-lock ...

    • Prostředky & zablokování

  • prostředek je cokoliv, k čemu je potřeba dávat pozor na přístup - exkluzivita, iluze sdílení.
  • odnímatelné prostředky - dají se odebrat bez následků, neodnímatelné - nelze bez nebezpečí selhání výpočtu. práce - žádost->používání->odevzdání
  • zablokování - množina procesů je zablokovaná, pokud každý z nich čeká na událost, kterou může způsobit jen jiný proces z množiny.
  • Coffmanovy podmínky :
    1) vzájemné vyloučení (prostředek najednou vlastní ≤ proces)
    2) drž a čekej (proces drží získané prostředky a čeká na získání dalších)
    3) neodnímatelnost (zámky nejde odebírat)
    4) čekání do kruhu
    když platí, může vzniknout (a vzniká) zablokování.
  • modelování zablokování - orientovaný graf, 2 typy uzlů: prostředky a procesy (šipky: k prostředku - žádost; od něj: vlastnění, procesy kulatě, prostř. hranatě).

    • Řešení zablokování

  • pštrosí algoritmus - kill -9
  • detekce a zotavení - hledá kružnice v orient. grafu, odebrání prostředků, zabíjení procesů z cyklu/ mimo cyklus, pokud vlastní identický prostředek. rollback - uložení stavu procesu.
  • vyhýbání se - bezpečný stav : je k dispozici tolik prostředků, že procesy spouštěné postupně v urč. pořadí jsou schopny dokončit práci (vezmu proces který je s počtem prostředků nejblíž maximu kolik potřebuje (musím vědět předem!), je-li dost prostředků aby max. dosáhnul, může skončit-> dostanu další prostředky, pokračuju ). Bankéřův algoritmus - nedostat se do nebezpečného stavu. (problém: oznámení počtu prostředků, různé druhy prostředků; už se nepoužívá)
  • prevence - napadnutí 1 z Coffman. podm.:
    - vzáj. vyloučení: spooling, multiplex (nezachovává data, rovnou je tiskárna/síťovka použije), jeden proces vlastnící prostředek vyrobí další virtuální
    - drž a čekej (nešikovné)- žádat o prostř. před startem procesu; nejprv vše uvolnit a pak znovu žádat o vše najednou (hrozba vyhladovění)
    - neodnímatelnost - vede k chaosu
    - čekání do kruhu - zabránění vzniku kruhu: nejvíc 1 prostředek (nerozumné), všechny procesy mohou žádat o prostředky jen ve vzest. pořadí pid; problémy s Plug&Play, není max. paralelismus
  • 2-fázové zamykání : často v databázích/distribuovaných algoritmech - nejdřív všechno zamykám, když něco nejde, odemknu vše a čekám, pak pracuji, pak vše odemknu (nesmím mezitím už zamykat) používané, fční; nutné - schopnost restartu transakce. (furt hrozba vyhladovění)

    • Správa paměti

  • hierarchie: 
     
 |  registry         ^ (roste cena, rychlost) 
 |  cache            | 
 |  hl. paměť        | přímá adresace CPU 
 ------------------------------- 
 |  pomocná paměť    | nejde přímý přístup  
 |  zálohovací paměť | z CPU 
 v(roste velikost)
  • registry CPU - 10ky - 100vky bajtů (IA-32: obecné registy pár 10tek), IA-64 - až kB (extrém), stejně rychlé jako CPU.
  • cache - z pohledu aplikací není přímo adresovatelná; dnes řádově MB, rozdělení podle účelu, několik vrstev. L1 cache (~10ky kB) - dělené instrukce/data; L2 (~MB) sdílené instr&data, běží na rychlosti CPU (dřív bývala pomalejší), servery - L3 (~10MB). vyrovnává rozdíl rychlosti CPU a RAM. využívá lokality programů - cyklení na místě; sekvenčního přístupu k datům. pokud nenajdu co chci v cache - cache-miss - načítá se potřebné z RAM (po blocích), jinak - (95-7% čtení) - cache-hit
  • hlavní paměť - přímo adresovatelná procesorem, 100MB - GB; pomalejší než CPU; CAS - doba přístupu na urč. místo - nejvíc zdržuje (v 1 sloupci už čte rychle, dat. tok dostatečný), další - latence - doba než data dotečou do CPU - hraje roli vzdálenost (AMD- integrovaný řadič v CPU)
  • pomocná paměť - není přímo adresovatelná, typicky HDD; náh. přístup, ale pomalejší. ~100GB, různé druhy - IDE, SATA, SCSI; nejvíc zdržuje přístupová doba (čas seeku) ~ 2-10ms; obvykle sektor - 512 B ; roli hraje i rychlost otáčení (4200 - 15000 RPM) - taky řádově ms.
  • zálohovací paměť - nejpomalejší, z teorie největší, dnes ale neplatí; typicky - pásky; pro větší kapacitu - autoloadery ; sekvenční přístup; dnes - kvůli rychlosti často zálohování RAIDem.

    • Správce paměti (memory manager)

  • část OS; musí udržovat info o volné paměti, přidělovat paměť - hledat správné volné místo; navíc při nedostatku paměti - replacement - odebírání a vracení kusů RAM- virtuální paměť
  • adresování - několik možností kdy spočítat adresy:
    1) při překladu - program může běžet jen na konkrétní adrese (typicky 0) - Linux, Win
    2) při zavádění - nutná spolupráce linkeru (vytv. relativních adres & jejich označení) a zavaděče (loaderu) - ten mj. upraví adresy na absolutní (typicky DLL) (při zavádění programu - staticky linkované knihovny?, DLL se zavádí klidně i za běhu)
    3) za běhu - nutná HW podpora - relokační registr , který CPU ke všem adresám přičítá (dnešní CPU neumí, např. IBM360).

    • metody přidělování paměti

  • overlay - např. BC++3.1; pro možnost použití víc paměti - na úrovni programátora aplikace - ten rozdělí program do "fází", určí, kdy budou potřeba které knihovny - rozdělení na overlaye - nezávislé části (potom se přehazují - celé!), při špatném rozvržení / velké závisloti overlayí - pomalé
  • swapping - na úrovni OS, ten sám odstraňuje CELÉ obrazy procesů, při potřebě zas natahuje do paměti - pomalé!
  • překlad adres

    • překlad adres

  • proces sám pracuje s logickým / virtuálním adresovýn prostorem, OS se stará o překlad adresy na fyzickou, kterou se už skutečně adresuje RAM.
  • spojité přidělování - nejjednodušší - 1 paměťový oddíl, v něm je někde OS (na 0/na konci paměti/oboje), zbytek má uživatel, lin. prostor (MS-DOS (nebyla žádná ochrana horního limitu paměti), staré počítače)
  • pro víc procesů - IBM - rozdělení paměti na PEVNÉ oddíly (dáno kompilací OS), proces musí PŘED SPUŠTĚNÍM prohlásit, kolik chce paměti; ∀ blok má frontu procesů co na něj čeká, nepřeřazuje se => nevyužití někt. bloků; vylepšení - 1 fronta => zabrání velkých bloků malými programy. typicky 2-4 oddíly; nutný relokační a limitní registr (ochrana paměti)
  • dnes - přiděluje kusy paměti se spojitým rozsahem adres, když si proces řekne; vylepšení - není napevno; programy kusy získávají & uvolňují; časem - fragmentace paměti. dnes dělá malloc(), new na vlastním heapu. nutné držet info o volné paměti: buď bitmapa - ∀ jednotku (sektor/blok) mám 1 bit; neobs. info o vlastníkovi, nebo spoják - v paměti mám začátek, ∀ blok velikost, ukazatel na další. při uvolňování - nutné spojit se sousedy z obou stran.

    • přidělování volného bloku paměti

  • first-fit - alg., který najde první blok kam se věc vejde - rychlý, způsobuje fragmentaci
  • next-fit - mírné vylepšení - pamatuje si kde skončil posledně, hledá odtud.
  • best-fit - snaží se minimalizovat fragmentaci - hledá nejmenší větší kus paměti. vytváří tak malé kousky volné, že je nikdo nechce; pomalý (prohledá vždy celý spoják)
  • worst-fit - vezme vždy naopak největší kus paměti; pomalý, rozděluje velké bloky - nepoužívá se; ost. 3 - vhodnost závisí na chování programu
  • fragmentace paměti
    1) vnitřní - nevyužití posledního přiděleného bloku (protože po bajtech se paměť nepřiděluje) - čím větší bloky přiděluji, tím větší
    2) vnější - vznikání nepoužitelně malých kousků volné paměti; v praxi - zhruba 50% po nějaké době běhu ("pravidlo 50%"); naalokovanou paměť nelze sesypávat (můžou v ní být adresy) - jen v někt. jazycích kde nejsou přímo pointry/znám typ dat (Java, C# - nepoužívá se kvůli rychlosti)
  • buddy-systém - novější, často používaný (MSVS.NET, GCC); rozdělení paměti na bloky velikosti 2n, pole indexované exponentem 2 (konst. velké), volné bloky velikosti 2x ve spojácích, které začínají v poli. při přidělování - zaokrouhlit na nejbližší vyšší mocninu 2, pokud je v poli volný blok této velikosti, OK, jinak rozdělit větší. při uvolňování - slepovat (proto nutné aby adresy byly zaokrouhlené na svoji velikost) <= malloc() konst., free() lin. složitost (lze zrychlit - ukládání velikosti bloku, stromy)

    • Virtuální paměť

  • procesy pracují s VA. převod VA -> FA nemusí vždy existovat - část virt. paměti je uložena v pomocné paměti. => iluze větší paměti, dnes ale hlavně kvůli ochraně paměti.
  • převod VA -> FA vždy dělá HW (kvůli rychlosti), pokud nenajde převod, informuje OS, ten se stará.
  • velikost FAP vs. VAP - naprosto nezávislé (např. IA-32 - 232 VAP, 236 max. FAP)
  • 2 možnosti správy - stránkování - "velké" CPU, OS - lineární VAP, programy vůbec nepoznají že virt. paměť existuje; segmentace - dnes jen IA-32, je víc práce - 2rozměrný VAP - segment, offset; programy vědí, že běží se segmentací.

    • stránkování

  • VAP rozdělen na stránky velikosti 2n, FAP - stejně velké rámce . převod - pomocí stránkovacích tabulek - pole indexované číslem stránky, v něm fyz. adresa & příznak existence mapování (neex.-li - výpadek stránky).
  • část adresy - číslo stránky, část- posunutí, to se během převodu nemění
  • jde o nespojité přidělování paměti - ve VAP předstírám spojitý blok paměti, ale každá stránka může být jinde.
  • ∀ proces může mít svůj vlastní VAP ( multiple address space )- stejné VA pro 2 procesy jsou jinde ve FAP. OS zajišťuje sdílení paměti - proces požádá o vytvoření sdílené paměti, ost. procesy se mohou připojit (nemusí být na stejném místě VAP => nutné používat offsety v pointerech). založeno na souhlasu procesů => bezpečné. moderní 64bity - single address space - ?? 1 paměťová mapa sdílená všemi procesy -> sdílenou paměť otevřu v SAS => pak u pointrů netřeba offsety. bezpečnost SAS - ∀ úsek má číslo/barvu, proces má seznam úseků kam může (v registrech - OS/CPU mohou kontrolovat)
  • víceúrovňové stránkování - tabulky jsou v RAM kvůli rychlosti, jsou dost velké => více úrovní, 1. část adresy - 1. úroveň, ta ukazuje do tabulky 2. úrovně, posunutí = index v tabulce. mapování na 1. úrovni už nemusí existovat -> ušetřím paměť (můžu navíc 2.úroveň odswapovat). zpomaluje ale ještě víc. (i víc úrovní - P IV, SPARC - 3, AMD64 - 4, 68xxx - 5 (ale programovatelné))
  • TLB - translation localside buffer - asociativní paměť - kvůli urychlení přístupu; využívá lokality programů - program nepotřebuje moc různých stránek najednou. asociativní pole, návr. hodnota buď "klíč chybí", nebo "klíč existuje, hodnota je...". buď plně asociativní - hledání ve všech políčkách najednou, nebo jen n-cestně asociativní ?? - ořízne pár bitů klíče, můžou být různé na stejném místě --> takové nelze cacheovat najednou => horší efektivita. běžně - TLB předsazená stránkování; při existenci mapování, které není v TLB ho uložím (předp.že program bude chtít adresu znova). úspěšnost cca 95%. může obsahovat i např. povolení přístupu ke stránce; 386 - sdílené TLB pro všechny procesy => po přeplánování se musí mazat => ex. globální stránky - dá se říct že nějaké mapování je společné pro ∀ procesy, potom se nevyhazuje z TLB při přeplánování; tagovaná TLB - klíč má 2 části, 1. - tag - ID adresového prostoru, není tak třeba vůbec čistit.
  • nulaúrovňové stránkování - používají "chytré" 64-bity (IA-64,UltraSparcIII) (problém : k adresaci všeho v 64bitech by bylo potřeba ~ 6 úrovní) => HW podpora jen pro TLB, zbytek je na OS, ten je také zodpovědný za úpravu TLB. OS může pro stránkování použít lib. strukturu, navíc ho může odswapovat, CPU je jednodušší.
  • inverzní stránkovací tabulky - taky nové 64-bity. VAP > FAP. VA se hashuje nějakou ne moc složitou fcí do tabulky (velikost odp. potřebám fyz. paměti), z ní spojáky [stránka|rámec]. počet přístupů do paměti odpovídá přibližně víceúrovň. stránkování. umí to IA-64.
  • výpadek stránky - vyjímka procesoru -> uloží se kontext, octnu se v handleru; zjistím VAP (podle PID procesu), kde nastal výpadek (větš. z registrů CPU), zkontroluji platnost adresy & práva - OS musí držet mapu paměti ( AAAA-BBBB RW, R, X (instrukce), S (systém) ), pokud nesouhlasí práva/neex. adresa => kill process. potom nalezení volného rámce v paměti, není-li, vyhodím jiný (zápis na disk/chytřejší si pamatují, zda byl změněn) - do tabulky stránek můžu přímo napsat místo na disku (stačí 1bit = mapování neex., zbytek volný). zápis na disk -pomalý => může běžet něco jiného; potom - načtení stránky do rámce (zase čekání, rámec - spec. stav: není volný & nelze vyhodit), zavedu mapování, proces = připraven.

    • algoritmy výměny stránek

  • širší použití (např. i v TLB)
  • náhodná strategie - random oběť, dodnes na Win2000 na multiprocesoru, není kupodivu zas tak špatné.
  • optimální stránka - ideální teoretický algoritmus, vyberu vždy stránku kterou budu potřebovat nejpozději - nelze implementovat; pokusy s testy chování programů - funguje jen na typické případy, jen pro 1 proces; ostatní alg. se snaží dosáhnout.
  • NRU - Not Recently Used - stránka, která nebyla nedávno použita. ∀ str. 2 příznaky: Accesed, Dirty (čteno/zapsáno), v ideálním případě nastavuje CPU, lze simulovat (pokud CPU umí aspoň příznak read-only: nenamapuju, zapamatuju si že bych měl, čekám až CPU přistoupí, pak namapuju read-only, nastavím A. při pokusu o zápis - výpadek stránky; pokud je ve skut. RW, poznamenám si D a nastavím RW). jednou za čas projdu tabulky a zruším nastavení A (nebo mapování u hloupých CPU). při výpadku: třídy podle A,D: 1. 0,0; 2. 0,1; 3. 1,0; 4. 1,1 - vyberu z nejnižší neprázdné. rušení A - málo často ~ sekundy. příznaky se zapisují nejdřív do TLB, odtud teprv do tabulky stránek.
  • FIFO - stránky ve frontě; Belladyho anomálie - zvětšením fyz. paměti se může zvětšit počet výpadků (pro některé průběhy potřeb stránek), vylepšení: v případě, že má stránka příznak A, hodím ji jen na konec fronty a A := 0 - už tím netrpí - druhá šance.
  • hodiny - upravená 2.šance. reálně se používá (Win2000, Linux). 1 ručička ukazuje kandidáta na obět, když nemá A, vyberu ho, jinak A := 0; pohnu ručičkou; příp. zkouším dalšího. mám 2 ručičky pro zrychlení, svírají konst. úhel, 1. nuluje A, 2. vybírá (nenuluje) => garance nejh. případu.
  • LRU - Least Recently Used - chováním nejblíž optimu; implementace SW málo přesná, složitá. HW jde dobře jen někde (pro RAM obtížné, cache, TLB OK); občas se ale používá. podobné NRU, přesnější dělení - podle program. čítače - ukládám jeho hodnotu u každé stránky při přístupu, hledám stránku s nejnižším čítačem. 2. možnost matice n x n, při použití rámce k nastavím řádek k na 1 & vynuluju k-tý sloupec, vybírám řádek s nejnižší bin. hodnotou (to samé jako nejmenší počet jedniček). problém - skladování čítače (64bit - 32 je málo)/ tabulky (zvětšuje se s 2.mocninou počtu stránek!)=> v RAM se nepoužívá, v TLB lze dobře.
  • NFU - Not Frequently Used - SW simulace LRU, ne tak přesné. ∀ stránku čítač (16bit), jednou za čas projdu, vynuluju A; zvětším čítač stránkám co měly A. potom vybírám stránku s nejnižším čítačem. problém - když program dlouho používá 1 stránku, ta dostane moc bodů a pak nejde vyhodit => ageing = jednou za čas se čítače projdou a zmenší (typicky dělení 2). další problém : stránka má po načtení 0 => může být rychle vyhozená => dává se bonus do začátku. časově náročný (hledání nejmenšího čítače).

    • alokační strategie

  • globální - když pracuji s rámci, pracuji se všemi; potom NFU musí procháze vše => pomalé
  • lokální ∀ proces dostane max. počet rámců a v nich si swapuje. - problém - nespravedlnost; některé procesy potřebují víc => pracovní množina : na zač. dám konst. počet rámců, sleduji výpadky/čas, při překročení daných mezních hodnot zvětším/zmenším prac. množinu. zrychlí alg. výměny stránek. funguje ve Windows.

    • problémy stránkování

  • znovuspuštění instrukce - je potřeba aby procesor po výpadku zkusil přístup do paměti znova. dnes umí všechny CPU, např. 68xxx - problémy (přerušení v půlce instrukce)
  • sdílení stránek - jednomu rámci odp. víc stránek => pokud s ním něco dělám, týká se to všech stránek! => musím vše ost. odmapovat. musím si pamatovat mapování ∀ rámec - obrácené tabulky.
  • odstranění položky z TLB při rušení mapování - nestačí změnit tabulky, musí se vyhodit i z TLB (kde to může, ale nemusí být). problém - u multiprocesorů má ∀ CPU vlastní TLB, tabulky jsou sdílené => CPU při rušení mapování musí poslat interrupt s rozkazem ke smazání všem (i sobě), počkat na potvrzení akce od všech.

    • segmentace

  • podporuje dnes už jen IA-32 => OS už neumí
  • program rozdělen programátorem & compilerem na segmenty - úseky co patří k sobě (kód, konstanty, data ...) (dnes už dělá jen compiler), mají různé délky, mohou měnit velikost za běhu (stack, heap) - na rozdíl od stránkování
  • program si je vědom, že běží se segmentací. virtuální adresa = dvojice segment&offset, fyzická = lineární. převod - tabulka segmentů, podobně jako stránkování (jen se offset k výstupu z tabulky segmentu přičte, ne přilepí)
  • ∀ úsek fyz. paměti je SOUVISLÝ (u stránkování rámce nejdou za sebou). v segm. tabulce - další příznaky - R/W, velikost - kontroluje se proti offsetu, jinak error; velikosti - přesnost až na bajty.
  • adresový prostor vypadá jako u spojitého přidělování (pro umístění segmentů: First-Fit apod.) - jsou v paměti celé a spojité! => problém : výměna velkých segmentů při výpadku trvá dlouho.
  • výhoda : můžu sesypávat segmenty (programy mají číslo segmentu, neví kde začíná ve FAP), ale stojí čas.
  • problém : nelze mít větší segment než FAP.

    • segmentace a stránkování dohromady

  • řeší problémy segmentace. programy pracují se segmenty, ale ty se tváří že jsou furt namapované, tj. výpadek segmentu nenastane (krom spec. příp. - práva, horní limit)
  • z VA se segmentačním algoritmem dostane lineání adresa - mezistupeň VA a FA - jednorozměrný prostor do kterého se mapují segmenty, v něm - stránkování => získám FA.
  • segmenty mohu stránkovat po částech, navíc můžu mít větší segment než FAP. segmenty nevyměnuji, jen stránky
  • reálně na IA-32 - segmentaci nelze vypnout, jen zneviditelnit - 2 segmenty (4GB) pro kód a data, překrývají se (což není zakázané), oba začínají na 0, čísla offsetů 32bit; segment není třeba v kódu uvádět. Takto funguje ve Win & Linuxu - CPU s tím pracuje, ale programy to nevidí.
  • AMD 64 - segmentace funguje tak napůl. ex. 1 segmentační registr, čistě kvůli Thread Local Storage na Windows.

    • Filesystémy

  • důvody pro existenci - potřeba více paměti než se vejde do RAM (např. ve Win i Linuxu max. 3GB), perzistence dat - zachování i po ukončení procesu/ pádu/vypnutí PC, sdílení informací mezi 2 procesy (starší vynález než sdílená paměť), přístup více procesů k datům najednou
  • soubor - pojmenovaná množina (jméno nemusí být nutně human-readable) souvisejících informací, která (typicky) leží v hlavní paměti. jiná možnost: abstrakce OS, umožnující uložení/načtení dat (práci s diskem) - dá se rozšířit např. na síťové disky; ∀ soubor má jméno/identifikátor, atributy, strukturu (někde), typ (buď zabudovaný, nebo se dá nějak zjistit - přípony)
  • pojmenování souborů - na většině OS lidsky čitelné, usnadňuje práci, zvyšuje abstrakci. pravidla určuje OS (case sensitivity, spec. znaky ... )
  • atributy - určují vlastnosti souborů, některé OS - mají i jméno jako atribut; ochrana, umístění, velikost, vlastník, čas ... liší se pro různé OS.
  • struktura - soubor = sekvence bajtů ( Win, Unix ) - žádná; jiné OS : soubor = sekvence záznamů, jejichž typ znám (někdy úpravy - např. B-Stromy) - např. kontakty v mobilech, nebo úkoly, poznámky.
  • typ - běžné - filesystém větš. nerozumí; adresáře - spec. typ souboru, udržuje seznam jmen & odkazů na soubory, FS rozumí, normální čtení/zápis větš. nejde., spec. soubory - např. /dev na Unixu - soubory, které jsou de facto odkazy na zařízení - konvence pojmenovávání prostředků, nebo: soft-linky.

    • přístup k souborům

  • sekvenční - nejjednodušší, nejstarší: lze otevřít, číst, návrat možný běžně jen na začátek (mag. pásky), dnes OS pro toto optimalizuje: bufferování; v C - rewind();
  • přímý (náhodný) přístup - od dob pevných disků, v souboru navíc ukazovátko - virt. pozice čtení, všechny operace s ním hýbou. navíc mám operaci seek.

    • paměťové mapování

  • nové, využívá stránkování; dřív v paměti větš. věci co neodpovídají souborům na disku, část ve swapfilu; Sun: vyhrazení paměti přímo pro urč. data z disku, nezálohovaná swapem. při přístupu: výpadek stránky & načtení z HDD. proces požádá o mapování, dostane adresu ve VAP, kde je soubor => když vím pozici v souboru, najdu stránku, při výpadku OS načte ze souboru, při zápisu opět uloží. výhoda : zrychlení, stejná práce jako s RAM, odpadá kopírování paměti
  • fread() - lze číst 1 bajt, OS si čtení cacheuje, C-runtime library taky => pro načtení bajtu se data zkopírují 3x: HDD -> OS -> CRT -> proces. (paměťové mapování toto řeší)
  • problém: přesná velikost souboru - min. jednotka práce s pamětí je 1 stránka : musím při zápisech volat spec. fci měnící velikost souboru => program s tím musí počítat. navíc při zvětšování přes stránky nemusí být místo; OS typicky nechá trochu místa, když nestačí, zvětšování SELŽE! (přesouváním by mi zneplatnil ukazatele, v někt. OS mohu předem říct kolik má být rezerva)
  • pro soubory větší než dostupná virt. paměť: 2 úrovně volání - namapování = jen oznámení OS, že budu mapovat; otevření okna = teprve vytvoření mapování (jen urč. části souboru); oken může být víc, OS si pamatuje offsety, okna mohu posouvat. 64bit procesory - zvládnou mapování i bez oken -> jeden z mála dobrých důvodů zavedení.

    • operace se soubory

  • operace se jménem - převod jméno <--> strojová podoba (id) - fce create, delete, open (někdy = create); převod jméno <--> id pomalý => další operace pracují s id -> už rychlejší.
  • id == FILE * v Unixu pčítání otevřených souborů ∀ proces, ve Win - globální.
  • adresáře - spec. typ pro udržení organizace (třídění, stejná jména); má neviditelnou vnitřní strukturu (FAT - 16B záznamy, smazání: přepsání jména neplatným znakem, problém: procházení lineární => pomalé, dnešní FS (NTFS, EXT2/3) - B-Stromy), mohou odkazovat na jiné adresáře => hierarchie; ∀ filesystém: kořenový adresář. operace: hledání jména souboru, dirlist, přejmenování, smazání, vytvoření souboru.
  • cesty - pojmenování souboru v rámci celého FS, odp. hierarchii adresářů. různé konvence, ale podobné. akt. adresář (vlastnost procesu!) - spousta aplikací chce pracovat nezávisle na umístění => relativní cesty nezač. kořenem, hledají se od akt. adresáře. spec. pojmenování akt. adresáře/otce ".","..". abs. cesta - je od kořene.
  • linky - dnes běžně 2 typy (hard, soft = symbolic). hard link přímo adresáře odkazují na stejné binární ID souboru, navenek není vidět; soft link - spec. typ souboru, který v sobě obsahuje jméno => rovnou se přeskočí na toto jméno při otvírání & práci.
  • hierarchická struktura - nejstarší: strom, výhoda - JEDNOZNAČNÉ pojmenování souborů (FAT). další - DAG (orientovaný acyklický graf) - pro 1 soubor už víc jmen. dnes - obecný graf: problém - zacyklení při prohledávání (př. find - musí řešit).

    • implementace filesystémů

  • musí splňovat 3 věci: správu souborů (kde jsou, jak velké), správu adresářů (převod jméno <--> id) (někdy to dělá jiný prostředek, dnes větš. umí FS sám), správa volného místa. někdy mohou být i další (odolnost proti výpadkům)
  • velikost bloků - blok = nejmenší jednotka pro práci s diskem; disk pracuje s min. 1 sektorem (typicky 512 B) - někdy by pak bylo moc bloků => OS sdruží několik sektorů lineáně vedle sebe = 1 blok. velikost: velké = rychlejší práce, ale vnitřní fragmentace (∅ soubor~ pár KB), malé = malá vnitřní fragmentace, větší režie na info o volném místě/ umístění souboru (zabírá víc bloků!), navíc fragmentace souborů -> zpomalení. dnes blok ~ 2-4KB.

    • uložení souboru

  • jak si pamatovat kde leží soubor
  • souvislá alokace soubor jako souvislý sled bloků - stačí znát jen začátek, jednoduchý přístup k souborům, problém - hledání volného místa, zvětšování souborů => už se nepoužívá
  • spojovaná alokace - FAT; spoják bloků, tvořený rovnou bloky - ∀ blok má u sebe ukazatel na další. při seeku musím číst ∀ blok informaci -> pomalé. další : ztratím výhodu velikosti mocnin 2 - zpomaluje při paměť. mapování. FAT - vylepšené: spoják je vedle - pole o stejné velikosti jako počet bloků & z nich odkazy. v adresáři je odkaz na 1. blok souboru. zároveň slouží i jako info o volném místě.
  • pův. FAT - integery v poli (16bit) - omezen počet bloků na 64K, celá FAT měla 128K => dnes lze strčit do paměti, spoják - jednosměrný => seek dozadu je pomalý; už pro desítky MB hodně velké bloky!. FAT32 - vylepšené - mnohem víc bloků, ale tabulka už se těžko vejde do paměti.
  • indexová alokace - Unix, typicky ve spec. oblasti - dat. struktura: i-node, v nich jsou uloženy sdílené bin. informace o ∀ 1 souboru & prostor přímo pro čísla bloků odkazující na 1 soubor.
  • dnes - EXT2: 12 položek na přímé bloky (z 15), větší soubory: posl. 3 odkazy odkazují na další i-nodové bloky - odkazy na další. 13: 1-úrovňové, 14: 2-úrovňové, 15: 3-úrovňové; funguje ale bez cacheování se dost zpomaluje => nutné zajisit.
  • adresáře: obs. různé věci: FAT - jméno, atributy, velikost, datum, 1.blok (<- atributy leží jinde než soubor: nelze udělat hard-link); novější: v adresáři je jen jméno & odkaz na nějakou dat. strukturu (Unix - i-node, ten obs. práva, atributy atp.), když ve 2 adresářích nastavím stejné číslo i-nodu, mám hard link. to samé umí i NTFS.
  • volné místo: podobně jako v paměti: spoják volných bloků (pův. Unix 1970, EXT1 (EXT2 už ne)), bitmapa bloků: NTFS, HPFS , dnešní FS.

    • NTFS

  • nástupce FAT, ale mnohem vyspělejší. 64bit ukazatele na bloky (512B - 4KB) => velká max. velikost; počet souborů max. 264 = fakticky ∞. jména - UCS-2 (podvarianta Unicode, 16bitů), max. 255 znaků; atributy souborů závisí na ovladačích nad tím - libovolné
  • vícenásobné streamy; všechno vč. dat = atributy souborů, kterých může být libovolně; sparse files - při skokách v zápisech se nuly neukládají fyzicky na disk (šetří místo)
  • NTFS5 (WinXP,2003Server) - šifrování dat => u přenesených disků bez hesla ani s admin. právy nepřečtu data, sym-linky (hard-linky umí už starší verze)
  • komprese (není moc vidět), automatická fault tolerance (snaha o konzistenci i po pádu) - žurnálování - v žurnálu jsou zapsané transakce, po pádu se dodělá, co se nestačilo; transkace - buď se operace provede celá, nebo vůbec.
  • adresáře - B-stromy s odkazy na soubory (umožňuje hard-linky)
  • MFT - (Master File Table) řídící struktura - spec. soubor; natvrdo rozdělený po 1 KB blocích; záznamy o souborech: odkazy na soubory v adresářích jsou čísla záznamů v MFT. 1. 16 záznamů - special: $MFT (odkaz na sebe), $MFTMirror (záložní kopie 1.16 záznamů - na disku uprostřed), $LogFile (žurnál), $AttrDef (std. atributy), $Volume (info o systému), $. (root dir), $Bitmap (volné místo). 1 záznam - počet odkazů, zákl. příznaky (adresář?), seznam atributů (streamy, jméno, typ ... ), data = stream s názvem ":$Data" - přístup: "file:stream", "file::$Data".
  • data atributů - rezidentní - přímo v MFT, nerezidentní - v datových blocích. malé soubory mají data přímo v MFT!. pokud pro popis nestačí 1 záznam, připojí se další (1 z atributů jsou i informace kde leží soubor - 1KB nemusí stačit)
  • info o umístění: souvislá a spojovaná alokace zároveň - seznam runů - souvislých úseků bloků (setříděný podle pozice v souboru). run - VCN (virtual cluster n.) - vzhledem k souboru, LCN (logical cl. n.) - od zač. FS (& velikost runu , odkaz na další). cíl defragu - ∀ soubor jen 1 run. očíslování VCN nemusí být souvislé => sparse fily zadarmo
  • prealokace

    • EXT2/3

  • max. velikost FS - 4 TB; jména: záznamy bajtů, max 255 zn., rezervace místa pro roota
  • prealokace : FS si při zápisu do souboru vyhrazuje rezervu 8 bloků za místem kam píše, při zavření souboru vrací.
  • hard i sym linky
  • Ext3 - žurnálování - soubor. systém rozumí transakci, žurnálování funguje ale z venku; transakce cacheovány => složené transakce.
  • disk: boot block (info o FS), block groups : ∀ obs. superblock, group description, block bitmap, inode bitmap, inode table (týká se jen inodů z mé skupiny), data blocks.
  • 10 rezervovaných inodů, 11=volný (v kernelu, nedá se k nim moc dostat)
  • ∀ inode: několik pevných atributů: UID, GID, velikost, časy, počet odkazů. 12 odkazů na bloky, jeden nepřímý, 1 2úrovňový, 1 3úrovňový.
  • žurnál = běžný soubor.

    • WinFS

  • myšlenka: ukládat data do SQL
  • adresáře - tabluky, data : LOB (large binary object). vyhledávání probíhá rychleji, práce se soubory není o moc pomalejší. fault toleranci umí databáze dávno
  • bude možné uživatelsky vyrábět atributy a podle nich hledat; problém: žere paměť (ale cache zadarmo).

    • I/O Systémy

  • OS vytváří "abstraktní stroj" - v aplikacích se chci vyhnout přímému přístupu ke konkrétním HW.
  • řadič zařízení/ adaptér = přímo HW -> ∀ řadič potřebuje ovladač.
  • přístup k zařízení - přes port - spec. adresový prostor CPU (SPARC, IA-32 - omezená práce, jen čtení/ zápis), paměťové mapování - zařízení poslouchá adresovou sběrnici procesoru, je nastavené že odpovídá na urč. rozsahu adres (FAP!). tváří se jako paměť, lze provádět operace jako ||, && ... . čísla adres & portů - dřív jumpery, dnes ve spolupráci s PCI, PCI-Express: dynamické přidělování - sběrnice rozhoduje, pamatuje si adresy.

    • dělení zařízení

  • blokové x znakové - podle nejmenší jednotky práce (blokové: síťovka, CD, disk, znakové: COM, myš, klávesnice)
  • sekvenční x náhodný přístup - sekvenční - páska (stejně se chovají i myš, klávesnice), náhodný - disk.
  • synchronní x asynchronní komunikace : synchro - provádí akce jen na povel (HDD), asynchro - poskytuje i nevyžádaná data (hl. čtení) - síťovka: zápis synchronní, čtení asynchronní (není spec. operace "začni číst ze síťovky" - když přijde paket: přerušení)
  • sdílení - sdílené : vypadaj "skoro jako sdílené", ale nejde úplně. hned na nízké úrovni mají multiplex (OS nad ovladačem), zajišťující víc logických zařízení (síťovka, HDD), vyhrazené (tradičně) - např. tiskárna, dá se obejít spoolingem (reálně se rozdíly stírají)
  • rychlost něco moc pomalé, něco až moc rychlé (FireWire, síť), směr dat - read only, r/w, write-only (starší tiskárny).

    • cíle OS pro I/O

  • nezávislost zařízení - abstrakce by měla být vysoko, aby programy nepoznaly např. kde je soubor, se kterým pracují; někdy jde, někdy ne
  • jednotné pojmenování zařízení (Unix: /dev - práce jako se soubory; u Windows - není dotažené do konce, není vidět)
  • stavovost zařízení - připojení - mount, inicializace & odhlášení (kvůli konzistenci - např. u FS, výměnná média);
  • korekce chyb: diskety mají sériová čísla=> nutné testovat mezi cacheováním & zápisem, neplatné pakety: ignorace; disky: S.M.A.R.T. - OS může chránit data přenosem jinam. (často se vyřeší bez vědomí uživatele)

    • I/O

  • přenos dat - různé přístupy : polling - ovladač aktivně čeká, to je občas problém - trvá dlouho, data přenáší CPU; přerušení - když zařízení pracuje, nezatěžuje CPU, pomocí přerušení oznamuje konec práce, data se pořád přenášej přes CPU. DMA - buď zařízení samo, nebo arbitr řídí sběrnici, přenos dat přímo, nezatěžuje CPU.
  • software - několik vrstev: uživ. software -> I/O nezávislý subsystém -> Ovladač -> Obsluha přerušení -> HW.
  • obsluha přerušení - součást ovladače, uloží kontext CPU, potvrdí příjem signálu, obsluha ovladačem: rozhodnutí co dál (další přenos, plánování), komunikuje s řadičem;
  • ovladač - kus softwaru, co rozumí přesně danému řadiči HW. vytváří v rámci třídy zařízení jednotné obecné rozhraní pro vyšší vrstvy; větš. jen výrobce zná ovládání -> vyrábí ovladače (problém v linuxu)
  • nezávislý subsystém - poskytuje ještě vyšší abstrakci, vhodnou pro aplikace, maskuje rozdíly zařízení - např. filesystémy; další úkoly: alokace paměti, cacheování, hlášení chyb
  • vyrovnávací paměti - vyrovnání rychlosti aplikace & zařízení (sériový port, síťovka), někdy aplikace stíhá (a moc rychle), někdy ne (2 směry cachí), u síťovky atp. - po překročení velikosti cache se zahazuje.

    • Disky

  • ∀ disk má 3 hl. časy, ovlivňující rychlost: seek - nastavení mechanismu čtení na správnou kružnici (disk: 5-10ms, CD: 100ms), latency - zpoždění otáčení: disk ∅ 4ms/7200rpm, CD 3-6ms/10000rpm (52x) - různá rychlost na různých místech; transfer - média--> řadič, různé rychlosti podle protokolu: UltraSCSI 320, SATA-150,300 - dnes už na tom nezáleží, nebrzdí vůbec.
  • plánování pohybu hlav na disku - snaha o minimalizaci seeku: zkrácení vzdálenosti cesty hlavy; dřív implementace v OS (př. Novell), dnes už disky umí samy. First-Come First-Served - žádná strategie, žádná režie, používá se při malé zátěži. Shortest Seek-Time First -spočte min. vzdálenost seeku z fronty a tem se vydá; při velké zátěži problém: požadavky na krajích zůstávaj viset. LOOK (výtah), C-LOOK - circular LOOK - funguje jako alg. výtahu - jede furt stejným směrem (pamatuje si), hledá čísla sektorů co jsou po cestě, když tím směrem není žádost, otočí se; C-LOOK - jednodušší, jezdí jen 1 směrem, na kraji seek na nejmenší. (pro dobrou fci lepší kombinace 2 strategií)

    • RAID

  • redundant array of independent/inexpensive disks; spojení disků při nedostatečné kapacitě, nebo zvětšení spolehlivosti: zálohování velkých objemů; zrychlení (dnes ale často i zpomaluje)
  • uvažuje 2 časy mean time between failure (~ ∅ 1 mil. hodin), mean time to repair - než obsluha opraví, u RAIDu: zjištění závady, vložení nového disku, synchronizace pole (~i dny)
  • většinou jsou nutné disky stejné velikost (jinak se pracuje s nejmenší), spare disky - nejsou zapojené do pole, čekají vedle, kvůli zkrácení mean time to repair; hot-plug - disky se musí dát měnit za běhu; array-rebuild - synchronizace RAIDu na pozadí.
  • RAID Just Bunch Of Disks - jsou spojené za sebe, vytváří iluzi velkého disku; jedině tady lze používat disky různé velikosti; rychlost stejná jako rychlost ∀ disku; spolehlivost KLESÁ - k pádu všeho stačí, aby exnul jeden.
  • RAID 0 - striping - žádná redundance, kapacita tolik co je disků; spolehlivost MENŠÍ (jako předch.), stripy - zvýšení rychlosti: ~ 32 KB - 1 MB bloky, na discích na střídačku za sebou, kontinuální požadavek rozdělím na víc disků; volba velikosti stripů - podle druhu souborů
  • RAID 1 - mirroring - 1 disk - data, 2. disk - kopie; kapacita = velikost jednoho; 50% redundance; čtení z 1 disku, zápis na oba současně (pomalejší), vydrží výpadek 1 disku; lze taky spojovat do větších- spojí 2jice, z nichž 1 může vypadnout. obnova: kopie na nový.
  • RAID 0+1/10 - oboje dohoromady - 2 a 2 disky, vydrží výpadek "těch správných" 2 disků, jeden vždy; i víc než 2 dvojice.
  • RAID 2 - v podstatě se nepoužívá : 7bit Hammingův paritní kód => 4 dat. & 3 záložní, data vedle sebe bajt po bajtu na různé disky; velká redundance, malá rychlost
  • RAID 3 - 1 paritní disk; 4 disky po bitech, 1 -záložní: obs. paritní bity; dá se dopočítat, když 1 disk exne; pomalé!
  • RAID 4 - to samé co RAID 3, ale po stripech; nevýhoda: paritní disk - pomalý; vydrží výpadek 1 disku.
  • RAID 5 - odstraňuje větš. nevýhod, dnes používané; parita distribuovaná na různé disky, striping; vydrží výpadek 1 disku; rychlost - i tak poznat zpomalení.
  • RAID 6 - dvojí parita => 2 redundantní disky, vydrží výpadek 2 disků.

    • Ochrana a bezpečnost

  • ochrana - s prostředky mohou pracovat jen autorizované procesy, bezpečnost - zabraňuje neoprávněný přístup do systému
  • právo - povolení/zákaz nějaké operace; doména - množina párů [objekt|právo] (práv něčeho k různým objektům), matice ochrany - řádky tvoří jednotl. domény., sloupce - objekty. Access Control List - seznam práv uživatelů k objektu; C-List (Capability list) - seznam práv uživatele k objektům.
  • cíle útoků - důvěrnost - zjištění obsahu dat , celistvost - změna dat (podstrčení falešných), dostupnost služby - DoS.
  • útočníci - náhodný přístup prostého uživatele, odborný vnitřní pracovník ("test"), snaha krást (zevnitř), špionáž (komerční, vojenská).
  • ztráta dat - Boží zásah (povodeň atp.), HW/SW chyby (programu, disku..), lidské chyby (krádež, špatné používání HW/SW).
  • autentikace - identifikace něčím co uživatel zná, má, nebo je: hesla (slovníkové útoky, brute-force => vynucování složitosti hesla), otázka/odpověď, fyzický objekt (smart card, USB key), biometrika.
  • vnitřní útoky - trojský kůň, login spoofing, logická bomba (zaměstnanec vpraví kód, který začne zlobit, když autora vyhodí z práce), back-door/trap-door (při nějaké podmínce kód přeskočí kontroly), buffer overflow (typicky se přepíše kus zásobníku, lze tam umístit adresu kódu i kód samotný)
  • vnější útoky - virus (přenos médii, sítí - v souborech), červ (šíří se díky chybám systému sám), mobilní kód (schopný přenášet se po síti a pokračovat v běhu) - applety, agenti, skripty; prevence: sandboxing (spouštění v omezeném virtuálním PC), interpretované jazyky (Java), podpisy appletů.

    • Kryptografie

  • cíle : důvěrnost, celistvost, autentikace (vím od koho to je), nemožnost popření (potvrzenou akci nelze vzít zpět)
  • vrstvy : kryptografické algoritmy (MD5...) (směs algebry, teorie čísel, teorie pravděp.), krypt. protokoly (dohoda o způsobu komunikace, sestavovaná použitím kryptogr. primitiv = algoritmů (neklíčovaná/1/2klíčová)) (SSL...)
  • kryptografický systém : prostor zpráv M, prostor šifrovaných zpráv C, prostory šifr.&dešifr. klíčů M, M'. nad nimi efektivní algoritmy generování klíčů (G: N --> K x K'), šifrování (E: M x K --> C), dešifrování (D: C x K' --> M ). ke ∈ K, m ∈ M: c = Eke(m). kd ∈ K', c ∈ C, m = Dkd(c). ∀ m ∈ M, ∀ ke ∈ K ∃ kd ∈ K', t.ž. Dkd( Eke (m)) = m.
  • Kerchoffovy principy dobrého krypt. systému: E, D neobs. tajnou část; E distribuuje rozumné zprávy rovnoměrně po C; se správným klíčem jsou E & D efektivní; bez správného klíče je dešifrování minimáně NP-úplné.
  • symetrické krypt. systémy : k = k'; asymetrické : k ≠ k' ( veřejný a tajný klíč ).
  • model útočníka : Dolev, Yao : může získat ∀ zprávu jdoucí po síti, může zahájit komunikaci s jiným uživatelem, může se stát příjemcem zpráv od kohokoliv, může zasílat zprávy komukoliv & vydávat se za jiného uživatele, nemůže uhádnout náh. číslo z dost velké množiny, bez klíče nemůže dešifrovat zprávu & nemůže vytvořit platnou šifrovanou zprávu (vzhledem k šifr. alg.).
  • neklíčovaná primitiva : náh. posloupnosti (HW/SW/pseudonáhodné - Mersenne Twister 19937), hashovací fce. (požadavky: míchající transformace (rovnoměrný&náh. výstup), odolnost na umělé nalezení kolize, odolnost na nalezení zdroje, efektivita ).
  • módy operací - šifrování zpráv delších než klíč: Electronic CodeBook : rozdělení na bloky, každý šifrovaný zvlášť; Cipher Block Chaining : xoruju ∀ blok plaintextu s výsledkem šifrování předch. bloku (&inicializační vektor); Output FeedBack : vytv. proudové šifry, šifruju výsledek předch. šifry, xoruju na blok plaintextu (&inicializační vektor), E & D stejná operace; Cipher FeedBack - to samé, šifruju už výsledek předch. xorování; CounTeR - vytv. proudové šifry, jako OFB, ale šifruju vždy nějaké počítadlo (lib. fce, jejíž sekvence hodnot se moc neopakují).
  • symetrické systémy - blokové šifry (DES, AES), proudové šifry (SEAL); výhody: dat. propustnost, krátké klíče, slučování -> silnější šifra; nevýhody: klíč musí být tajný!, potřeba měnit klíče, trusted party (ověřená 3. strana)
  • asymetrické systémy - RSA, DSA (ElGamal); výhody: jen privátní klíč je tajný, není potřeba trusted party, nevýhody : pomalé, delší klíče; není matem. dokázáno, že jsou bezpečné.
  • útoky : "nepřítel naslouchá" = packet sniffing na nezabezp. kanále; "s výměnou klíčů" = navíc ex. zabezp. kanál, po kterém se vyměňují klíče. "s veřejnými klíči" = příjemce pošle odesílateli veřejný klíč (nezabezp. kanály); "man-in-the-middle" = nepřítel pro oba předstírá, že je druhá strana, zprávy otevírá & přešifrovává.;
  • Diffie-Hellman algoritmus pro výměnu klíčů: A & B zvolí (veřejné) prvočíslo p, základ g; A zvolí tajné a (∈ [1,..p-1)), pošle B ga mod p; B zvolí tajné b, pošle gb mod p. (ga mod p)b mod p ≡ (gb mod p)a mod p ( =gab mod p) - tajný sdílený klíč.
  • útoky na protokoly - "přehrání zpráv" (nahrání & pokus použít znova) - řeší timestamp; "man-in-the-middle" - řeší přísnější autentikace (SSH: dotazy na fingerprinty); "paralelní spojení" - několik běhů protokolu současně pod řízením útočníka; "odražení (reflection)" - vracím zprávy zpět zdroji (po úpravě aby nepoznal že je to od něj); "prokládání" - paralelní spojení, zprávy z 1 běhu se použijí v dalším; "chyba typu" - podstrčení neplatných zpráv; "chybné použití šifrovací služby" - špatný algoritmus na nevhodném místě.