Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- mgr-szz:in-pos:1-pos [2019/06/05 18:58]
lachmanfrantisek synchronizace, uváznutí
+++ mgr-szz:in-pos:1-pos [2020/04/12 16:56] (aktuální)
@@ Řádek 53: / Řádek 53: @@
   * příklad: MACH
   * ➕ snadná přenositelnost OS, jádro je malé
-  * ➕ vyšší spolehlivost (moduly mají jasné API a jsou snadněji
+  * ➕ vyšší spolehlivost (moduly mají jasné API a jsou snadněji testovatelné)
-testovatelné)
   * ➕ vyšší bezpečnost (méně kódu OS běží v režimu jádra)
   * ➕ flexibilita (jednodušší modifikace, přidání, odebrání modulů)
@@ Řádek 95: / Řádek 94: @@
   * OS spravuje zdroje přidělováním procesům podle zvolené politiky (priorita, vzájemná výlučnost, zabraňuje uváznutí).
   * OS podporuje tvorbu procesu a jejich komunikaci.
-  * OS s multiprogramováním <color red> multiprogramování = multitasking</color>
+  * OS s multiprogramováním (<color red>multiprogramování = multitasking</color>)
@@ Řádek 245: / Řádek 244: @@
   * Toto je úkol dlouhodobého (strategického) plánovače
     * Vybírá který proces lze zařadit mezi připravené procesy.
+    * Řeší přechod ze stavu ''nový'' do stavu ''připravený''.
   * Plánovač je spouštěn je relativně málo často.
     * Typicky při ukončení jednoho procesu rozhodne, kterou úlohu dále vybrat k zavedení do paměti a spuštění.
     * Nemusí být super rychlý.
   * Určuje stupeň multiprogramování.
+  * Nemusí být ve všech systémech přítomen.
 === Krátkodobý plánovač ===
@@ Řádek 370: / Řádek 371: @@
 </box>
-===== Synchronizace procesů =====
+===== Komunikace a synchronizace procesů =====
 Synchronizace běhu procesů = "Jeden proces čeká na událost z druhého procesu."
@@ Řádek 377: / Řádek 378: @@
 Se souběžně běžícími procesy se můžeme setkat buď v přímo paralelním prostředí, kde je jedna paměť sdílena více procesy, nebo v prostředí distribuovaném, kde má každý proces vlastní lokální paměť. Hlavním problémem výskytu souběžných procesů je sdílení prostředků (paměť, zařízení, soubory, atd.) Tento problém se vyskytuje dokonce i v mnohouživatelských OS, kdy se např. řeší sdílení paměti mezi hlavní linií výpočtu v jádře a obslužnou rutinou přerušení při I/O operaci. Především při sdíleném přístupu do paměti nebo do souboru mohou vznikat neočekávané problémy – časové závislé chyby.
 </note>
@@ Řádek 382: / Řádek 384: @@
   * **Komunikaci mezi procesy**
-    * komunikace – způsob synchronizace, koordinace různých aktivit
+    * zasílání zpráv
-    * může dojít k uváznutí (každý proces čeká na zprávu od nějakého jiného procesu)
+    * synchronizace
-    * může dojít ke stárnutí (dva procesy si opakovaně posílají zprávy zatímco třetí proces čeká na zprávu nekonečně dlouho)
+    * sdílená paměť
+    * vzdálené volání procedur (RPC)
   * **Sdílení prostředků**
@@ Řádek 392: / Řádek 395: @@
       * operace čtení mohou být realizovány souběžně
     * pro zabezpečení integrity dat se používají kritické sekce
+Komunikace – způsob synchronizace, koordinace různých aktivit
+  * může dojít k uváznutí (každý proces čeká na zprávu od nějakého jiného procesu)
+  * může dojít ke stárnutí (dva procesy si opakovaně posílají zprávy zatímco třetí proces čeká na zprávu nekonečně dlouho)
@@ Řádek 504: / Řádek 514: @@
   * zamezujeme současné platnosti všech nutných podmínek
   * prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí)
 <box 95% round blue|Bankéřův algoritmus >
@@ Řádek 561: / Řádek 570: @@
   * postupně předbíhat uváznuté procesy
   * zamezit současné platnosti nutných podmínek
+<box 90% blue|Resource-Allocation Graph, RAG>
+  * množina uzlů (procesy ⚫, zdroje ⬛)
+  * hrany
+    * požadavků (proces -> zdroj)
+    * přidělení (zdroj -> proces)
+  * zdroje mohou mít více instancí
+Jestliže se v RAG nevyskytuje cyklus:
+  * => k uváznutí nedošlo
+Jestliže se v RAG vyskytuje cyklus:
+  * existuje pouze jedna instance daného typu => k uváznutí došlo
+  * existuje více instancí daného typu => k uváznutí může dojít
+</box>
+<box 90% blue|Wait-for-Graph, WFG>
+  * vztahy pouze mezi procesy
+  * hrana = proces čeká na uvolnění zdroje druhým procesem
+  * Systém uvázl, pokud je v grafu cyklus.
+</box>
@@ Řádek 571: / Řádek 603: @@
-===== Práce s pamětí, logický a fyzický adresový prostor, správa paměti a způsoby jejího provádění =====
+===== Správa paměti a virtualizace paměti =====
 ===Obecné poznatky správy paměti===
-  *
- Pro běh procesu je nutné, aby program, který ho řídí, byl umístěn v operační paměti.
+Pro běh procesu je nutné, aby program, který ho řídí, byl umístěn v operační paměti.
-  * Program se převádí do formy schopné interpretace procesorem ve více krocích, jednou musí někdo rozhodnout kde bude v operační paměti (FAP) umístěn.
+  * Z programu se stává proces (aktivní entita schopná spuštění na CPU) provedením celé řady kroků:
+    * naplnění tabulek, umístění do operační paměti
+    * vázání adres instrukcí a dat na adresy operační paměti
+  * Více procesů může sdílet společnou část paměti, aniž by se tím porušovala ochrana paměti
+    * neboť sdílení jedné datové struktury je lepší řešení než udržování konzistence násobných kopií vlastněných jednotlivými proces
   * Roli dlouhodobé paměti programu plní vnější paměť.
   * Vnitřní operační paměť uschovává data a programy právě běžících, resp. plánovatelných procesů.
@@ Řádek 583: / Řádek 623: @@
 ===Požadavky na správu paměti===
 ==Možnost relokace programů==
   * programátor nemůže vědět, ze které části paměti bude jeho program interpretován
@@ Řádek 602: / Řádek 643: @@
 === LAP a FAP ===
-<box 95% round blue|Správa paměti, základní pojmy>
+<box 95% round blue|Fyzický a logický adresový prostor>
-**Vstupní fronta (input queue)**: Fronta procesů čekajících na zavedení do paměti.
 **Logický adresový prostor (LAP)**: virtuální adresový prostor, se kterým pracuje procesor při provádění kódu (každý proces i jádro mají svůj). Dán šířkou a formou adresy. Kapacita je dána šířkou adresy v instrukci.
@@ Řádek 609: / Řádek 649: @@
 **Fyzický adresový prostor (FAP)**: adresový prostor fyzických adres paměti (společný pro všechny procesy i jádro). Adresa akceptovaná operační pamětí. Kapacita je dána šířkou adresové sběrnice operační paměti
 </box>
+{{:mgr-szz:in-pos:vazani-adres.png?300|}}
 ==Vázání adres LAP na adresy FAP==
@@ Řádek 624: / Řádek 666: @@
     * nutná HW podpora
     * proces může měnit svoji polohu ve FAP během provádění
+{{:mgr-szz:in-pos:relokacni-registr.png?300|}}
 ===Přidělování souvislých oblastí===
@@ Řádek 629: / Řádek 674: @@
   * sekce pro rezidentní část OS, obvykle bývá umístěna od počátku
   * sekce pro uživatelské procesy
+{{:mgr-szz:in-pos:rezidentni-oblast-pameti.png?300|}}
 Pro ochranu procesů uživatelů mezi sebou a OS při přidělování sekce procesům lze použít schéma s relokačním a mezním registrem:
@@ Řádek 654: / Řádek 701: @@
 ==Překryvy (Overlays)==
 Historická, klasická technika. V operační paměti se uchovávají pouze ty instrukce a data, která je potřeba zde uchovat "v nejbližší budoucnosti". Vyvolávání překryvů je implementované uživatelem, není potřeba speciální podpory ze strany OS.
+{{:mgr-szz:in-pos:overlays.png?300|}}
 ==Stránkování==
   * LAP procesu není zobrazován do jediné souvislé sekce FAP, zobrazuje se po částech do volných sekcí FAP
   * FAP se dělí na //rámce// -- pevná délka (např. 512 B)
@@ Řádek 666: / Řádek 716: @@
   *Problém snížení efektivnosti dvojím přístupem lze řešit speciální rychlou HW cache (asociativní paměť, TLB -- Translation Look-aside Buffer)
+{{:mgr-szz:in-pos:strankovani.png?300|}}
+==Segmentace==
+  * Logická adresa je dvojice (segment s, offset d)
+  * Tabulka segmentů, Segment table, ST:
+    * **base** – počáteční adresa umístění segmentu ve FAP
+    * **limit** – délka segmentu
+{{:mgr-szz:in-pos:segmentace.png?300|}}
+== Virtuální pamět ==
+  * Uložení obrazu LAP (virtuální paměti) v externí paměti
+    * nepoužívá se standardní systém souborů OS, používají se speciální metody, optimalizované pro tento účel
+    * speciální partition/slice disku
+  * Stránkování / segmentaci musí podporovat hardware správy paměti
+    * stránkování na žádost
+    * segmentování na žádost
+    * **žádost** – dynamicky kontextově generovaná indikace nedostatku
+  * OS musí být schopen organizovat tok stránek / segmentů mezi vnitřní a vnější pamětí
+<box 95% round blue|Stránkování na žádost (Demand paging)>
+  * stránka se zobrazuje do FAP při odkazu na ni, pokud ve FAP není již zobrazena
+  * počáteční shluky výpadků stránek
+</box>
+<box 95% round blue|Předstránkování (Prepaging)>
+  * umístění na vnější paměti sousedních stránek v LAP bývá blízké („sousedi“)
+  * princip lokality
+  * zavádí se více stránek než se žádá
+  * vhodné při inicializaci procesu
+</box>
+== Výpadek stránky ==
+Pokud se stránka nenachází ve FAP je aktivován OS pomocí přerušení „page fault“ (výpadek stránky)
+  * OS zjistí:
+    * nelegální reference → procesu je informován (např. signál SIGSEGV)
+    * legální reference, ale stránka chybí v paměti → zavede ji
+  * Zavedení stránky
+    * získání prázdného rámce
+    * zavedení stránky do tohoto rámce
+    * úprava tabulky, nastaven bit valid/invalid na 1
+  * Pak se opakuje instrukce, která způsobila „page fault“
+== Algoritmy určující oběť ==
+  * **Algoritmus LRU (Least Recently Used)**
+    * oběť = nejdéle neodkazovaná stránka
+  * **Algoritmus FIFO (First-In-First-Out)**
+    * oběť = stránka nejdéle zobrazená ve FAP
+  * **Algoritmus poslední šance**
+    * FIFO + vynechávání z výběru těch stránek, na které od posledního výběru bylo odkázáno
+===== Ovládání vstupů a výstupů =====
+  * HW pro I/O je značně rozmanitý
+  * Existují však určité běžně používané prvky:
+    * port
+    * sběrnice (bus)
+    * řadič (host adapter, controller)
+  * I/O zařízení jsou řízeny I/O instrukcemi (IN, OUT)
+  * Adresy I/O zařízení
+    * uváděné přímo v I/O instrukcích (např. IN AL, DX : DX port, AL získaný bajt)
+    * I/O se mapuje na přístup k paměti (např. grafická karta, videopaměť)
+==== Základní způsoby ovládání I/O ====
+=== Polling, programované I/O operace ===
+  * aktivní čekání na konec operace
+  * opakovaně se ptám na stav zařízení
+    * připraven
+    * pracuje
+    * chyba
+=== Přerušení ===
+  * zahájení I/O pomocí I/O příkazu
+  * paralelní běh I/O s během procesoru
+  * I/O modul oznamuje přerušením konec přenosu
+  * Přerušení obsluhuje ovladač přerušení (kód OS)
+  * Maskováním lze některá přerušení ignorovat nebo oddálit jejich obsluhu
+  * Patřičný ovladač přerušení se vybírá přerušovacím vektorem
+    * některá přerušení nelze maskovat
+    * přerušení mohou být uspořádána podle priorit
+  * Přerušení se používá i pro řešení výjimek (nejsou asynchronní)
+=== DMA ===
+  * kopírování bloků mezi pamětí a I/O zařízením na principu kradení cyklů paměti
+  * přerušení po přenosu bloku (indikace konce)
+  * nahrazuje programovaný I/O při velkých přesunech dat
+  * vyžaduje speciální DMA řadič
+  * při přenosu dat se obchází procesor, přístup do paměti
+  * zajišťuje přímo DMA řadič
+  * procesor a DMA soutěží o přístup k paměti
+==== Aplikační rozhraní I/O ====
+  * Jádro OS se snaží skrýt rozdíly mezi I/O zařízeními a programátorům poskytuje jednotné rozhraní.
+  * Dále vrstva ovladačů ukrývá rozdílnost chování I/O řadičů i před některými částmi jádra
+  * Některé vlastnosti I/O zařízení
+    * mód přenosu dat: znakové (terminál) / blokové (disk)
+    * způsob přístupu: sekvenční (modem) / přímý (disk)
+    * sdílené/dedikované: klávesnice / páska
+    * rychlost přenosu: vystavení, přenos, ...
+    * read-write, read only, write only
+==== Síťová zařízení ====
+  * Přístup k nim se značně liší jak od znakových, tak od blokových zařízení
+    * proto mívají samostatné rozhraní OS
+  * Unix i Windows obsahující rozhraní nazývané „sockets“
+    * separují síťové protokoly od síťových operací
+    * přístup jako k souborům (včetně funkce select)
+  * Existuje celá řada přístupů k síťovým službám
+    * Pipes (roury), FIFOs, streams, queues, mailboxes
+==== Blokující a neblokující I/O ====
+  * Blokující
+    * z hlediska procesu synchronní
+    * proces čeká na ukončení I/O
+    * snadné použití (programovaní), snadné porozumění (po provedení operace je hotovo to co jsem požadoval)
+    * někdy však není dostačující (z důvodu efektivity)
+  * Neblokující
+    * řízení se procesu vrací co nejdříve po zadání požadavku
+    * vhodné pro uživatelské rozhraní, bufferovaný I/O
+    * bývá implementováno pomocí vláken
+    * okamžitě vrací počet načtených či zapsaných znaků
+  * Asynchronní
+    * proces běží souběžně s I/O
+    * konec I/O je procesu hlášen signály
+    * obtížné na programovaní, složité používání, ale v případě vhodně promyšleného programu velice efektivní
+==== I/O subsystém v jádře ====
+  * Plánování
+    * některé I/O operace požadují řazení do front na zařízení
+    * některé OS se snaží o „spravedlnost“
+  * Vyrovnání (vyrovnávací paměti), buffering
+    * ukládání dat v paměti v době přenosu k/ze zařízení
+    * řeší rozdílnost rychlosti
+    * řeší rozdílnost velikosti datových jednotek
+  * Caching
+    * rychlá paměť udržuje kopii dat
+    * vždy pouze kopii
+    * caching je klíčem k dosažení vysokého výkonu
+  * Spooling
+    * udržování fronty dat určených k výpis na zařízení
+    * pokud zařízení může vyřizovat požadavky pouze sekvenčně
+    * typicky tiskárna
+  * Rezervace zařízení
+    * exkluzivita přístupu k zařízení pro proces
+    * rezervace / uvolnění – volání systému
+    * pozor na uváznutí (deadlock)
+  * Chybové řízení
+    * Vzpamatování se po poruše při chybě čtení z disku, zjištění nedostupnosti zařízení, po náhodné chybě zápisu, ...
+    * Volání požadující I/O operaci získá číslo chyby
+      * typicky záporná hodnota
+    * Udržuje se záznam o chybách v systému
+      * pro následné analýzy
+      * syslog, events (viewer), ...
@@ Řádek 672: / Řádek 915: @@
   * http://statnice.dqd.cz/home:prog:ap5
   * http://statnice.dqd.cz/mgr-szz:ap-ap:7
-  * slidy PB153
+  * slidy PB153 (text i schémata)
     * 04 Principy výstavby OS
     * 05 Procesy
     * 06 Vlákna
+    * 07 Plánování CPU
+    * 08 Synchronizace procesů
+    * 09 Uváznutí
+    * 10 Správa paměti
+    * 11 Virtuální paměť
+    * 12 I/O systém

mgr-szz/in-pos/1-pos.1559753922.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru