Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
mgr-szz:in-pos:1-pos [2019/06/05 18:58] lachmanfrantisek synchronizace, uváznutí |
mgr-szz:in-pos:1-pos [2019/06/16 20:21] lachmanfrantisek |
||
---|---|---|---|
Řádek 53: | Řádek 53: | ||
* příklad: MACH | * příklad: MACH | ||
* ➕ snadná přenositelnost OS, jádro je malé | * ➕ 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) | * ➕ vyšší bezpečnost (méně kódu OS běží v režimu jádra) | ||
* ➕ flexibilita (jednodušší modifikace, přidání, odebrání modulů) | * ➕ 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 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 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 | * Toto je úkol dlouhodobého (strategického) plánovače | ||
* Vybírá který proces lze zařadit mezi připravené procesy. | * 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. | * 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í. | * 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ý. | * Nemusí být super rychlý. | ||
* Určuje stupeň multiprogramování. | * Určuje stupeň multiprogramování. | ||
+ | * Nemusí být ve všech systémech přítomen. | ||
=== Krátkodobý plánovač === | === Krátkodobý plánovač === | ||
Řádek 370: | Řádek 371: | ||
</box> | </box> | ||
- | ===== Synchronizace procesů ===== | + | ===== Komunikace a synchronizace procesů ===== |
Synchronizace běhu procesů = "Jeden proces čeká na událost z druhého procesu." | 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. | 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> | </note> | ||
+ | |||
Řádek 382: | Řádek 384: | ||
* **Komunikaci mezi procesy** | * **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ů** | * **Sdílení prostředků** | ||
Řádek 392: | Řádek 395: | ||
* operace čtení mohou být realizovány souběžně | * operace čtení mohou být realizovány souběžně | ||
* pro zabezpečení integrity dat se používají kritické sekce | * 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 | * zamezujeme současné platnosti všech nutných podmínek | ||
* prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí) | * prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí) | ||
- | |||
<box 95% round blue|Bankéřův algoritmus > | <box 95% round blue|Bankéřův algoritmus > | ||
Řádek 561: | Řádek 570: | ||
* postupně předbíhat uváznuté procesy | * postupně předbíhat uváznuté procesy | ||
* zamezit současné platnosti nutných podmínek | * 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=== | ===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ěť. | * 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ů. | * 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=== | ===Požadavky na správu paměti=== | ||
+ | |||
==Možnost relokace programů== | ==Možnost relokace programů== | ||
* programátor nemůže vědět, ze které části paměti bude jeho program interpretován | * programátor nemůže vědět, ze které části paměti bude jeho program interpretován | ||
Řádek 602: | Řádek 643: | ||
=== LAP a FAP === | === 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. | **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 | **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> | </box> | ||
+ | |||
+ | {{:mgr-szz:in-pos:vazani-adres.png?300|}} | ||
==Vázání adres LAP na adresy FAP== | ==Vázání adres LAP na adresy FAP== | ||
Řádek 624: | Řádek 666: | ||
* nutná HW podpora | * nutná HW podpora | ||
* proces může měnit svoji polohu ve FAP během provádění | * 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í=== | ===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 rezidentní část OS, obvykle bývá umístěna od počátku | ||
* sekce pro uživatelské procesy | * 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: | 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)== | ==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. | 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í== | ==Stránkování== | ||
+ | |||
* LAP procesu není zobrazován do jediné souvislé sekce FAP, zobrazuje se po částech do volných sekcí FAP | * 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) | * 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) | *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/home:prog:ap5 | ||
* http://statnice.dqd.cz/mgr-szz:ap-ap:7 | * http://statnice.dqd.cz/mgr-szz:ap-ap:7 | ||
- | * slidy PB153 | + | * slidy PB153 (text i schémata) |
* 04 Principy výstavby OS | * 04 Principy výstavby OS | ||
* 05 Procesy | * 05 Procesy | ||
* 06 Vlákna | * 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 | ||