%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% Přepis přednášek z předmětu Základy operačních systémů %
% %
% Ve školním roce 2006/2007 %
% Sepsal a vypracoval Petr Hošek (petr.hosek@hotmail.com) %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper]{article}
\frenchspacing
\usepackage[utf8]{inputenc}
\usepackage{czech}
\usepackage{a4wide}
\usepackage[unicode]{hyperref}
\hypersetup{unicode=true,
pdftitle={Základy operačních systémů},
pdfauthor={Petr Hošek},
pdfsubject={Základy operačních systémů},
pdfkeywords={operační systémy}}
\title{Základy operačních systémů\thanks{sepsal a vypracoval Petr Hošek}}
\author{RNDr. Jakub Yaghob}
\date{\ }
\begin{document}
\maketitle
\tableofcontents
\newpage
\section{Historie, architektury}\label{sec:historie_architektury} % (fold)
\paragraph{Co je to operační systém?}\label{ssub:co_je_to_operacni_system} % (fold)
\begin{itemize}
\item operační systém jako abstrakce pro zjednodušení přístupu a ovládání zařízení
\item operační systém jako nástroj pro přidělování a správu prostředků
\end{itemize}
% paragraph paragraph_name (end)
\subsection{Historie}\label{sub:historie} % (fold)
\subsubsection{První generace}\label{ssub:prvni_generace} % (fold)
Operační systém jako takový neexistoval. Počítače se programovaly přímo, neexistovaly žádné standardy.
% subsubsection subsubsection_name (end)
\subsubsection{Druhá generace}\label{ssub:druha_generace} % (fold)
Nástup prvního programovacího jazyka \emph{Fortran}. Operační systém stále neexistoval ale objevovaly se první myšlenky.
% subsubsection subsubsection_name (end)
\subsubsection{Třetí generace}\label{ssub:treti_generace} % (fold)
První počítač pro všeobecné použítí \emph{IBM 360}. Tento počítač bylo možné jako první přizpůsobit různému způsobu použití.
Obsahoval také první operační systém \emph{OS 360}. Tento operační systém měl otevřené zdrojové kódy a tyto se upravovaly způsobu použití daného počítače.
Obsahoval také několik v té době převratných vlastností.
\begin{description}
\item[multitasking] prostředky počítače může využívat ``paralelně'' více procesů
\item[spooling] umožňuje každému procesu používat zařízení bez ohledu na ostatní a zajišťuje správné rozvržení přístupu k zařízení
\item[interaktivní uživatelé] umožňuje více uživatelům paralelně používat operační systém
\item[virtuální paměť] zvětšení velikosti operační paměti
\item[sítě] podpora prvních sítí
\item[real-time] umožňuje vykonání procesu v zadaný čas, samotné plánování úloh je \emph{NP-uplná} úloha
\end{description}
% subsubsection subsubsection_name (end)
\subsubsection{Čtvrtá generace}\label{ssub:ctvrta_generace} % (fold)
Zmenšuje se objem počítačů. Síťové operační systémy umožňují využívat síťové zdroje. Distribuované operační systémy využívají transparentně síťové zdroje.
% subsubsection subsubsection_name (end)
\subsubsection{Čtyřapůltá generace}\label{ssub:ctyrapulta_generace} % (fold)
Operační systémy pro jednoduchá zařízení, většinou jednodušší než klasické systémy uzpůsobené konkrétnímu použití.
% subsubsection subsubsection_name (end)
% subsection subsection_name (end)
\subsection{Architektury}\label{sub:architektury} % (fold)
\paragraph{Základní pojmy}\label{ssub:zakladni_pojmy} % (fold)
\begin{description}
\item[systémová volání] volání operačního systému
\item[proces] vykonávaný program
\item[soubor] persistentní data
\end{description}
% paragraph paragraph_name (end)
\subsubsection{Monolitická struktura}\label{ssub:monoliticka_struktura} % (fold)
Veškeré služby operačního systému běží v chráněném režimu, tedy v privilegované části procesoru. Procesy samotné běží na uživatelské úrovni a s operačním systémem komunikuje pomocí systémových volání.
Všechny servisní a pomocné funkce jsou společné a běží v chráněném režimu.
% subsubsection subsubsection_name (end)
\subsubsection{Virtuální stroje}\label{ssub:virtualni_stroje} % (fold)
Poprvé se objevily v \emph{OS 360}. Systém byl rozdělen na několik částí. Obsahoval \emph{virtuální stroje} jejichž jediným úkolem byl \emph{multitasking}.
Každý \emph{virtuální stroj} obsluhoval jednu \emph{aplikaci} a vlastní \emph{operační systém}.\\
V dnešní podobě existují abstraktní stroje, které vykonávají instrukce skutečného stroje. Nezáleží na skutečném hardware.\\
V současnosti se začíná využívat \emph{paravirtualizace}. Operační systémy v tomto případě vědí o tom že jsou \emph{virtualizovány} a koopoerují s \emph{paravirtualizérem}.
% subsubsection subsubsection_name (end)
\subsubsection{Mikrojádro}\label{ssub:mikrojadro} % (fold)
\emph{Mikrojádro} obsluhuje pouze základní prostředky, jako jediné běží v chráněném režimu. Zbývající zařízení obsluhují \emph{servery}. Pro komunikaci mezi procesy a servery se používá architektura \emph{klient/server}.
Úkolem mikrojádra je zajistit tuto komunikaci.
% subsubsection subsubsection_name (end)
% subsection architektury (end)
\subsection{Používané architektury}\label{sub:pouzivane_architektury} % (fold)
\subsubsection{Architektura Windows NT}\label{ssub:architektura_windows_nt} % (fold)
Velmi malé jádro nad kterým běží nezávislé subsystémy, tyto mohou podporovat různé jiné systémy.
% subsubsection subsubsection_name (end)
\subsubsection{Architektura Windows 2000}\label{ssub:architektura_windows_2000} % (fold)
Velmi dobře organizované jádro, jedinou vyjímku tvoří grafický subsystém který je kvůli optimalizaci implementován přímo do jádra.
Teoreticky nezávislé na hardwaru díky abstrakční vrstvě \emph{HAL}, vyjímku opět tvoří grafický subsytém který přistupuje k hardwaru přímo.
% subsubsection subsubsection_name (end)
\subsubsection{Architektura Linuxu}\label{ssub:architektura_linuxu} % (fold)
Klasické monolitické jádro.
% subsubsection subsubsection_name (end)
% subsection pouzivane_architektury (end)
% section section_name (end)
\section{Procesy, plánování}\label{sec:procesy_planovani} % (fold)
\paragraph{Základní pojmy}\label{ssub:zakladni_pojmy} % (fold)
\begin{description}
\item[proces] vlastní běžící program, obálka sdružující prostředky pro jednotlivé vlákna; těžká entita
\item[vlákno] oddělení místa vykonávání instrukcí od adresního prostoru; lehká entita
\item[přerušení] přerušení způsobí že procesor přeruší proud vykonávaných instrukcí a začne vykonávat instrukce na jiné adrese obsluhující toto přerušení,
po vykonání těchto instrukcí se vrací zpět k vykonávání původního proudu instrukcí
\end{description}
% paragraph paragraph_name (end)
\subsection{Procesy, vlákna}\label{ssub:procesy_vlakna} % (fold)
\subsubsection{Proces}\label{ssub:proces} % (fold)
V různých operačních systémech má pojem \emph{proces} mírně odlišný význam. Mají svou hierarchii.\\
Typicky proces spravuje adresový prostor (paměť), prostředky, práva a některé signály.
% subsubsection subsubsection_name (end)
\subsubsection{Vlákno}\label{ssub:vlakno} % (fold)
Vlákno spravuje jediný prostředek, a to procesor. Dříve běželi vlákna pouze na uživatelské úrovni, jádro operačního systému o vláknech nevědělo.
Postupně se koncept vláken dostal i do jader operačních systémů a dnes tyto jádra vlákna přímo podporují.\\
Dříve docházelo k problémům s omezeným počtem vláken na jaderné úrovni.
Dnes existují hybridní vlákna, tedy jaderné vlákna které jsou na uživatelské úrovni rozděleny na další vlákna.\\
Každé vlákno musí mít vlastní zásobník. Typicky má také programový čítač a registry procesoru. Tyto prostředky se nazývají kontext.
% subsubsection subsubsection_name (end)
\subsubsection{Stavy procesu}\label{par:stavy_procesu} % (fold)
Obecně stavy nejmenších entit které daný operační systém rozeznává.
Pomocí plánovače a dostupných prostředků se snažíme vytvořit iluzi že na jednom procesoru běží více procesů zároveň.\\
Standardně procesy díky režii plánovače přechází ze stavu \emph{připraven} do stavu \emph{běžící} a zpět jakmile běží moc dlouho, případně dokud neskončí.
Pokud přijde systémové volání, je nutné proces \emph{blokovat}, jakmile tato situace vyřešena, přechází proces opět do stavu \emph{připraveno}.
% subsubsection subsubsection_name (end)
% subsection procesy_vlakna (end)
\subsection{Přerušení}\label{sub:preruseni} % (fold)
\paragraph{Druhy přerušení}\label{ssub:druhy_preruseni} % (fold)
\begin{description}
\item[synchronní] speciální instrukce umožňující vstoupit do operačního systému díky speciálnímu druhu přerušení, takto fungují systémová volání;
druhým případem jsou vyjímky které generuje procesor a které informují operační systém o nesprávném chování procesoru
\item[asynchroní] vzníkají díky vnějším událostem
\item[polling] umožňuje operačnímu systému pravidelně kontrolovat stav zařízení pomocí přerušení,
náhrada pro zařízení které generování přerušení při změně stavu nepodporují
\end{description}
% paragraph paragraph_name (end)
\subsubsection{Obsluha přerušení}\label{ssub:obsluha_preruseni} % (fold)
Procesor obsahuje vektor přerušení který obsahuje informace o jednotlivých druzích přerušení a místa které obsahují instrukce k jejich obsluze.
Operační systém typicky obsadí tyto místa vlastními instrukcemi.
\paragraph{Průběh obsluhy přerušení}\label{ssub:prubeh_obsluhy_preruseni} % (fold)
\begin{enumerate}
\item operační systém převezme řízení
\item uloží se stav procesoru, kontexty procesů se uloží do tabulky procesů
\item analyzuje se druh přerušení; více zařízení typicky využívají jedno přerušení, operační systém musí zjistit které zařízení přerušení vyvolalo
\item vyvolá se příslušná obsluha
\item obslouží se přerušení
\item obnoví se stav procesoru; této situace se typicky využívá k přeplánování
\item aplikace pokračuje
\end{enumerate}
% paragraph paragraph_name (end)
% subsubsection subsubsection_name (end)
% subsection subsection_name (end)
\subsection{Plánování}\label{sub:planovani} % (fold)
Plánování řídí plánovač. V operačním systému existují plánovací entity.
\subsubsection{Druhy plánování}\label{ssub:druhy_planovani} % (fold)
\begin{description}
\item[preemtivní plánování] plánování při kterém je operační systém schopen vynutit si převzetí plánování od plánovací entity a přeplánovat procesy;
operační systém má plnou kontrolu nad běžícími procesy
\item[nepreemtivní plánování (kooperativní plánování)] procesy předávají řízení dobrovolně, kooperují při řízení práce procesoru mezi sebou a operačním systémem
\end{description}
% subsubsection subsubsection_name (end)
\subsubsection{Cíle plánování}\label{ssub:cile_planovani} % (fold)
\begin{description}
\item[spravedlnost] každý proces dostane jednou za čas příležitost využívat procesor
\item[efektivnost] snaha o maximální využití procesoru
\item[doba odpovědi] dostatečná doba odezvy procesu
\item[průchodnost] ukončit v čase maximální počet procesů
\item[minimální režie systému] algoritmus pro plánování by měl využívat co nejmíň prostředků
\end{description}
% subsubsection subsubsection_name (end)
\subsubsection{Kritéria plánování}\label{ssub:kriteria_planovani} % (fold)
\begin{itemize}
\item proces který se váže na procesor tento často využívá
\item proces který se váže vstupně výstupní zařízení tyto často využívá
\item dávkový a interaktivní proces se liší dobou odezvy
\item priorita symbolizuje jak důležitý uvnitř systému proces je
\item výpadky stránek
\item skutečný čas procesoru
\end{itemize}
% subsubsection subsubsection_name (end)
\subsubsection{Priority}\label{ssub:priority} % (fold)
Statická priorita se nemění v průběhu času a je dána důležitosti, dynamická priorita se mění s časem a její účel je splnění cíle spravedlnosti.
Celková priorita je dána součtem statické a dynamické priority. Čím větší má proces prioritu, tím větší je četnost jeho naplánování v čase.
% subsubsection subsubsection_name (end)
\subsubsection{Plánovací algoritmy}\label{ssub:planovaci_algoritmy} % (fold)
\begin{description}
\item[FIFO] proces běží tak dlouho dokud má procesor, přicházející procesy se řadí do fronty
\item[Round Robin] jakmile proces spotřebuje své časové kvantum, je mu pomocí preemce odebrán procesor což je zařízeno pomocí vnějšího přerušení časovače
\item[více FIFO se zpětnou vazbou] více front, každá má určené časové kvantum, nejnižší fronta je typu \emph{Round Robin}; při plánování hledám první neprázdnou frontu,
pokud proces spotřebuje své časové kvantum, je mu preemtivně odebrán procesor a je posunut do nižší fronty,
pokud je proces zablokován, posunu ho po odblokování do vyšší fronty, tím upřednostňuji I/O procesy které jsou často blokovány
\end{description}
% subsubsection planovaci_algoritmy (end)
\subsubsection{Plánování v SMP}\label{ssub:planovani_v_smp} % (fold)
Samostatná fronta procesů a procesorů. Pokud je proces i procesor připraven, spustí se tento proces na daném procesoru.\\
Při \emph{aktivním} čekání plánovač aktivně využívá jeden procesor, toto čekání spotřebovává výkon a energii.
Při \emph{pasivním} čekání je využito speciálních instrukcí.\\
Problém při přeplánování nastává při přesunutí procesu na jiný procesor kdy je nutné provést synchronizaci cache,
toto řeší \emph{afinita} procesů k procesoru kdy se plánovač snaží aby daný proces běžel stále na stejném procesoru.
% subsubsection planovani_v_smp (end)
\subsubsection{Real-time plánování}\label{ssub:real_time_planovani} % (fold)
Každý úkol má určený realný čas na dokončení. \emph{NP-úplný} problém, řešení pomocí heuristik. Obvykle předimenzování hardwarových prostředků.
% subsection planovani (end)
\subsection{Používané plánování}\label{sub:pouzivane_planovani} % (fold)
% subsubsection real_time_planovani (end)
\subsubsection{Plánování ve Windows}\label{ssub:planovani_ve_windows} % (fold)
Plánování na úrovni vláken. Neexistuje samostatný plánovač, kód pro plánování rozprostřen po celém jádře. Samostatné fronty vláken pro jednotlivé priority.
\paragraph{Priority}\label{ssub:priority} % (fold)
32 úrovní rozdělených podle důležitosti. Priority se dynamicky mění v rozsahu $<-2;2>$ od základní přidělené.
% paragraph priority (end)
\paragraph{Časová kvanta}\label{ssub:casova_kvanta} % (fold)
Abstraktní časové jednotky. Velikost kvanta se liší podle typu systému. Časové jednotky určuje \emph{HAL} vrstva podle hardware.
% paragraph casova_kvanta (end)
\paragraph{Zvýšení priority}\label{ssub:zvyseni_priority} % (fold)
Úprava priority pouze pro jedno časové kvantum. Zajištění interaktivity systému. Ochrana před nenaplánováním.
% paragraph zvyseni_priority (end)
\paragraph{Plánovací scénáře}\label{ssub:planovaci_scenare} % (fold)
Standardní situace které jsou rozeznávány a standardním způsobem řešeny.
% paragraph planovaci_scenare (end)
\paragraph{Plánování na SMP}\label{ssub:planovani_na_smp} % (fold)
Každé vlákno má dvě čísla určující ideální procesor a poslední procesor. Tyto čísla využívám k plánování.
Systém Windows neobsahuje vyvažování zátěže, toto je řešeno pomocí generování čísel.
% paragraph planovani_na_smp (end)
% subsubsection planovani_ve_windows (end)
\subsubsection{Plánování v Linuxu}\label{ssub:planovani_v_linuxu} % (fold)
Obsahuje vyvažování zátěže na procesorech.
\paragraph{Plánování}\label{ssub:planovani} % (fold)
Datová struktura \emph{Runqueue} určující aktivní a neaktivní procesy pro jednotlivé procesory.
% paragraph planovani (end)
\paragraph{Priorita}\label{ssub:priorita} % (fold)
Statická a dynamická priorita podobně jako na systému Windows s větším škálováním.
% paragraph priorita (end)
\paragraph{Vyvažování front na SMP}\label{ssub:vyvazovani_front_na_SMP} % (fold)
Vyvažuje se, pokud se vyprázdní \emph{Runqueue}, jinak v pravidelných intervalech podle zátěže systému.
Hledá se nejvíce zatížený procesor a algoritmus pro vyvažování se mu snaží ulehčit přesouváním procesů na méně zatížené procesory.
% paragraph vyvazovani_front_na_SMP (end)
% subsubsection planovani_v_linuxu (end)
% subsection pouzivane_planovani (end)
% section procesy_planovani (end)
\section{Meziprocesová komunikace a synchronizace}\label{sec:meziprocesova_komunikace_a_synchronizace} % (fold)
\paragraph{Základní pojmy}\label{ssub:zakladni_pojmy} % (fold)
\begin{description}
\item[race conditions] výsledek operace závisí na plánování
\item[vzájemná vyloučení (mutual exclusion)] kritickou sekci provádí nejvýše jeden proces
\item[kritická sekce] část programu, kde se provádí kritická operace
\end{description}
Potřebuji zajistit atomicitu procesů, to znamená že kritickou operaci provádí v jednom okamžiku pouze jeden proces.
% paragraph zakladni_pojmy (end)
\paragraph{Podmínky}\label{ssub:podminky} % (fold)
\begin{enumerate}
\item žádné 2 procesy nemohou být najednou v jejich kritické sekci
\item nemohou být učiněny žádné předpoklady o rychlosti nebo počtu procesorů
\item žádný proces mimo kritickou sekci nesmí blokovat jiný proces
\item žádný proces nesmí čekat nekonečně dlouho v jeho kritické sekci
\end{enumerate}
\subsection{Klasické synchronizační problémy}\label{sub:klasicke_synchronizacni_problemy} % (fold)
\paragraph{Problém producent-konzument}\label{ssub:problem_producent_konzument} % (fold)
Producent produkuje prostředky, konzument je spotřebovává. Mezi nimi je sklad pevné velikosti.
Konzument nemá co prodávat když je sklad prázdný, producent přestane vyrábět, když je sklad plný.
% paragraph problem_producent_konzument (end)
\paragraph{Problém obědvajících filosofů}\label{ssub:problem_obedvajicich_filosofu} % (fold)
Pět filosofů sedí okolo kulatého stolu. Každý má před sebou talíř špaget a jednu vidličku.
Špagety jsou bohužel slizké a je třeba je jíst dvěma vidličkami.
Život filosofa sestává z období jídla a období přemýšlení.
Když dostane hlad, pokusí se vzít dvě vidličky, když se mu to podaří, nají se a vidličky odloží.
% paragraph problem_obedvajicich_filosofu (end)
\paragraph{Problém ospalého holiče}\label{ssub:problem_ospaleho_holice} % (fold)
Holič má ve své oficíně křeslo na zákazníka a pevný počet sedaček pro čekájící zákazníky.
Pokud v oficíne nikdo není, holič se posadí a spí. Pokud přijde první zákazník a holič spí, probudí se a posadí si zákazníka do křesla.
Pokud přijde zákazník a holič už stříhá a je volné místo v čekárně, posadí se, jinak odejde.
% paragraph problem_ospaleho_holice (end)
% subsection klasicke_synchronizacni_problemy (end)
% paragraph podminky (end)
\subsection{Metody dosažení vzájemného vyloučení}\label{sub:metody_dosazeni_vzajemneho_vylouceni} % (fold)
\subsubsection{Aktivní čekání}\label{ssub:aktivni_cekani} % (fold)
\begin{itemize}
\item spotřebovává čas procesor
\item vhodnější pro předpokládané krátké doby čekání
\item nespotřebovává prostředky operačního systému
\item rychlejší
\end{itemize}
\paragraph{Zakázání přerušení}\label{ssub:zakazani_preruseni} % (fold)
Zakázání přerušení nelze použít v preemtivních operačních systémech, kde je instrukce pro zakázání přerušení procesům nedostupná.
Taktéž nelze použít na více procesorech kde procesy na různých procesorech mohou přistupovat ke stejným prostředkům.
Používá se v jádrech operačních systémů.
% paragraph zakazani_preruseni (end)
\paragraph{Zámky}\label{ssub:zamky} % (fold)
Nefungují protože samotný zámek je sdíleným prostředkem a problém s přístupem může nastat i na něm.
% paragraph zamky (end)
\paragraph{Důsledné střídání}\label{ssub:dusledne_stridani} % (fold)
Fungují pokud výpočty v nekritických sekcích jsou vyvážené. V opačném případě porušuje podmínku 3.
% paragraph dusledne_stridani (end)
\paragraph{Petersonovo řešení}\label{ssub:petersonovo_reseni} % (fold)
Inteligentně kombinuje \emph{zámky} a \emph{důsledné střídání}, tak aby fungovalo ve všech případech.
Pro více než 2 procesy se jedná o poměrně komplikované řešení.
% paragraph petersonovo_reseni (end)
\paragraph{Instrukce TSL}\label{ssub:instrukce_tsl} % (fold)
Vyžaduje podporu hardwaru. Instrukce pro \emph{spin-lock} je atomická ale poměrně složitá, proto se kombinuje s vnější smyčkou aby se zajistilo,
že se bude provádět co nejméně. Jedná se o funkční a používané řešení.
% paragraph instrukce_tsl (end)
% subsubsection aktivni_cekani (end)
\subsubsection{Pasivní čekání/blokování}\label{ssub:pasivni_cekani} % (fold)
\begin{itemize}
\item proces je ve stavu blokován
\item vhodné pro delší doby čekání
\item spotřebovává prostředky operačního systému
\item pomalejší
\item používá se také u bariér které slouží pro synchronizaci vláken
\end{itemize}
Jednotlivé synchronizační primitiva jsou navzájem ekvivalentní a každé z nich lze implementovat pomocí jiného.
\paragraph{Sleep/Wakeup}\label{ssub:sleep_wakeup} % (fold)
Implementuje operační systém. Atomické operace \emph{Sleep} a \emph{Wakeup}. Nejedná se o funkční řešení!
V případě problému \emph{producent-konzument} řešení nebude fungovat, protože čítač je v tomto případě sdílený prostředek v kritické sekci.
% paragraph sleep_wakeup (end)
\paragraph{Semafory}\label{ssub:semafory} % (fold)
Vylepšení metody \emph{Sleep/Wakeup} zajišťující atomicitu operací. Struktura obsahující čítač a frontu uspaných procesů,
atomické operace \emph{Up} a \emph{Down} pracující s touto strukturou. Pokud je čítač nezáporný dojde při operaci \emph{Down} ke snížení čítače,
v opačném případě dojde k zablokování a proces je přidán do frony čekajících.
Pokud je fronta neprázdná, probudí operace \emph{Up} libovolný proces z fronty, jinak zvětší čítač.
\emph{Binární semafor} se používá na vynucení vzájemného vyloučení. Díky atomicitě operací bude toto řešení fungovat.
% paragraph semafory (end)
\paragraph{Monitory}\label{ssub:monitory} % (fold)
Synchronizační primitivum implementované překladačem. Vzájemné vyloučení v jedné instanci zajištěné synchronizací na vstupu a výstupu veřejných funkcí.
Překladač zajistí synchronizaci pomocí některého z blokovacích primitiv poskytovaných operačním systémem.
Uvnitř monitoru existují proměnné sloužící k zablokování uvnitř monitoru. Pro práci s těmito proměnnými slouží operace \emph{Wait} a \emph{Signal}.
Může nastat problém při probouzení procesu. Jedná se o funkční teoretické řešení, ale v praxi neexistuje.
% paragraph monitory (end)
\paragraph{Zprávy}\label{ssub:zpravy} % (fold)
\emph{Zpráva} je množina dat a informací přenášených mezi odesilatelem a příjemcem. Atomické operace \emph{Send} a \emph{Receive}.
Při odeslání zprávy operací \emph{Send} nedochází k zablokovaní, pokud na zprávu čeká příjemce operací \emph{Receive}, odblokuje se.
Pokud není žádná zpráva dostupná, operace \emph{Receive} zablokuje proces.
Princip klient/server. Adresace pomocí identifikace procesu nebo schránky. \emph{Randezvous} je speciální situace kdy mám schránku nulové velikosti
a synchronizuji dva procesy v čase.
% paragraph zpravy (end)
% subsubsection pasivni_cekani (end)
% subsection metody_dosazeni_vzajemneho_vylouceni (end)
\subsection{Reálně používaná primitiva}\label{sub:realne_pouzivana_primitiva} % (fold)
\begin{itemize}
\item \emph{spin-lock}, \emph{kritické sekce}, \emph{semafor}
\item závislé na operačním systému
\end{itemize}
\subsubsection{Synchronizační primitiva vyšší úrovně}\label{ssub:synchronizacni_primitiva_vyssi_urovne} % (fold)
\begin{description}
\item[Read-Write Lock] vícenásobně/paralelně operace \emph{Read}, exkluzivně \emph{Write} operace
\item[Bariéry] hlavní vlákno vypustí pomocná vlákna a čeká na bariéře na dokončení úkolu všech vláken
\item[Reentrantní zámky] několik funkcí které používají stejnou kritickou sekci, některé z těchto funkcí volají jiné z těchto funkcí,
zdánlivě zjednodušuje použití, reálně přináší spíše potíže, to lze odstranit vyrobením blokovacích a neblokovacích variant funkcí
\item[Uzamčené operace] atomicky prováděné jednoduché operace
\end{description}
% subsubsection synchronizacni_primitiva_vyssi_urovne (end)
\subsubsection{Synchronizační primitiva ve Windows}\label{ssub:synchronizacni_primitiva_ve_windows} % (fold)
\begin{itemize}
\item jednotné funkce pro pasivní čekání
\item \emph{semafor}, \emph{event}, \emph{kritické sekce}, \emph{jednosměrný spojový seznam}, \emph{uzamčené operace}
\end{itemize}
% subsubsection Synchronizační primitiva ve Windows (end)
\subsubsection{Synchronizační primitiva v Unixových systémech}\label{ssub:synchronizacni_primitiva_v_unixovych_systemech} % (fold)
\begin{itemize}
\item operační systém implementuje \emph{semafor}
\item dnes obvykle knihovna \emph{pthread}, ta implementuje \emph{podmíněné proměnné}, \emph{mutexy}, \emph{Read-Write Lock}, \emph{spin-lock},
nemusí být vždy dostupná
\end{itemize}
% subsubsection synchronizacni_primitiva_v_unixovych_systemech (end)
% subsection realne_pouzivana_primitiva (end)
% section meziprocesova_komunikace_a_synchronizace (end)
\section{Prostředky, zablokování}\label{sec:prostredky_zablokovani} % (fold)
\subsection{Prostředky}\label{sub:prostredky} % (fold)
Prostředek je cokoliv, k čemu je třeba hlídat přístup.
\begin{itemize}
\item operační systém jako správce prostředků
\item hardwarové zařízení (procesor, tiskárna, \ldots)
\item informace (záznam v databázi, \ldots)
\end{itemize}
\paragraph{Druhy prostředků}\label{ssub:druhy_prostredku} % (fold)
\begin{description}
\item[odnímatelné] lze odejmout bez následků
\item[neodnímatelné] nelze odejmout bez nebezpečí selhání výpočtu
\end{description}
% paragraph druhy_prostredku (end)
\subsubsection{Práce s prostředky}\label{ssub:prace_s_prostredky} % (fold)
\begin{enumerate}
\item žádost o prostředek
\begin{itemize}
\item blokující
\item právě zde dochází k zablokování
\end{itemize}
\item používání prostředku
\item odevzdání prostředku
\begin{itemize}
\item dobrovolné
\item při skončení procesu
\end{itemize}
\end{enumerate}
% subsubsection prace_s_prostredky (end)
% subsection Prostředky (end)
\subsection{Zablokování}\label{sub:zablokovani} % (fold)
Množina procesů je zablokována, jestliže každý proces z této množiny čeká na událost, kterou může způsobit pouze jiný proces z této množiny.
\subsubsection{Coffmanovy podmínky}\label{ssub:coffmanovy_podminky} % (fold)
\begin{description}
\item[vzájemné vyloučení] každý prostředek je buď vlastněn právě jedním procesem nebo je volný
\item[drž a čekej] procesy aktuálně vlastnící nějaké prostředky mohou žádat o další
\item[neodnímatelnost] přidělené prostředky nemohou být procesům odebrány
\item[čekání do kruhu] existuje kruhový řetěz procesů, kde každý z nich čeká na prostředek vlastněný dalším článkem řetězu
\end{description}
% subsubsection Coffmanovy podmínky (end)
\subsubsection{Modelování zablokování}\label{ssub:modelovani_zablokovani} % (fold)
Lze modelovat jako orientovaný graf se dvěma typy uzlů - prostředky a procesy.
% subsubsection Modelování zablokování (end)
% subsection Zablokování (end)
\subsection{Řešení zablokování}\label{sub:reseni_zablokovani} % (fold)
\begin{itemize}
\item pštrosí algoritmus
\item detekce a zotavení
\item vyhýbání se
\item předcházení (prevence)
\end{itemize}
\subsubsection{Pštrosí algoritmus}\label{ssub:pstrosi_algoritmus} % (fold)
Zablokování se ani nedetekuje, ani se mu nezabraňuje, ani se neodstraňuje. Uživatel sám rozhodne o řešení.
Nespotřebovává prostředky operačního systému, používané na systémech Windows, Unix.
% subsubsection Pštrosí algoritmus (end)
\subsubsection{Detekce a zotavení}\label{ssub:detekce_a_zotaveni} % (fold)
Operační systém modeluje zablokování orientovaným grafem, hledá v něm kružnici, pokud ji nalezne, došlo k zablokování a je třeba ho řešit.
\begin{description}
\item[odebrání prostředku] pod dohledem operátora, pouze na přechodnou dobu
\item[zabíjení procesů] z cyklu, mimo cyklus vlastnící identický prostředek
\item[rollback] operační systém ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu,
dojde ke ztracení práce
\end{description}
% subsubsection Detekce a zotavení (end)
\subsubsection{Vyhýbání se}\label{ssub:vyhybani_se} % (fold)
Spotřebovává prostředky operačního systému. Procesy musí dopředu hlásit jaké prostředky budou požadovat.
\begin{description}
\item[bezpečný stav] stav procesů a prostředků, nejsou zablokovány a existuje cesta jak uspokojit všechny požadavky na prostředky
\item[nebezpečný stav] nesplňuje podmínky bezpečného stavu
\end{description}
\paragraph{Bankéřův algoritmus}\label{ssub:bankeruv_algoritmus} % (fold)
Bankéř má klienty a těm slíbil jistou výšku úvěru. Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou.
Klienti občas navštíví banku a žádají postupně o prostředky do maximální výše úvěru. Až klient skončí s obchodem, vrátí bance
vypůjčené peníze. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu.
% paragraph Bankéřův algoritmus (end)
% subsubsection Vyhýbání se -- stavy (end)
\subsubsection{Prevence}\label{ssub:prevence} % (fold)
\begin{description}
\item[vzájemné vyloučení] spooling
\item[drž a čekej] žádost o všechny prostředky před startem procesu; nejprve je potřeba vše uvolnit a poté žádat o vše najednou
\item[neodnímatelnost] vede k chaosu
\item[čekání do kruhu] nejvýše jeden prostředek; všechny prostředky jednoznačně očíslovány, procesy mohou žádat o prostředky ve vzestupném pořadí,
musím vrátit prostředky, pokud chci prostředek s nižším číslem
\end{description}
\paragraph{Dvoufázové zamykání}\label{ssub:dvoufazove_zamykani} % (fold)
Nejdříve se vše zamyká, pokud je něco zamčeno, je třeba vše uvolnit a začít znovu.
Poté lze může pracovat se zamčenými prostředky. Na závěr pouze odemyká, nesmí se nic zamykat.
% paragraph dvoufazove_zamykani (end)
% subsubsection Prevence (end)
% subsection reseni_zablokovani (end)
% section Prostředky, zablokování (end)
\section{Správa paměti}\label{sec:sprava_pameti} % (fold)
\subsection{Hierarchie paměti}\label{sub:hierarchie_pameti} % (fold)
\subsubsection{Registry}\label{ssub:registry} % (fold)
Extremní rychlost ale malá kapacita v řádu desítek až stovek bajtů. Klíčové pro překladače.
% subsubsection registry (end)
\subsubsection{Cache}\label{ssub:cache} % (fold)
Slouží jako nárazník pro vyrovnání rozdílů rychlostí mezi registry a hlavní pamětí.
Dělí se do více úrovní podle rychlosti a velikosti v řádu desítek kilobajtů až jednotek megabajtů podle úrovně.\\
V současných procesorech velmi efektivně využívány, \emph{cache-hit} se pohybuje okolo 95-97\%, \emph{cache-miss} se pohybuje okolo 3-5\%.
Obrazy paměti se v cache drží po řádcích označované jako \emph{cache-line}, její velikost je v řádu bajtů.\\
Na vícejaderných procesorech se využívá \emph{koherence} cache paměti, cache paměť by měla být co nejvíce transparentní,
pokud je nutné neustále synchronizovat cache paměť mezi jednotlivými jádry dochází k jevu nazývanému \emph{cache-trashing}.
% subsubsection cache (end)
\subsubsection{Hlavní paměť}\label{ssub:hlavni_pamet} % (fold)
Poslední úroveň paměti kterou je procesor přímo schopen adresovat. Velikost v řádu gigabajtů. Několik úrovní rychlosti podle typu přístupu.
% subsubsection hlavni_pamet (end)
\subsubsection{Pomocná paměť}\label{ssub:pomocna_pamet} % (fold)
Pomocná paměť hraje významnou úlohu ve spojitosti s \emph{virtuální pamětí}. Slouží k uchování \emph{persistentních dat}, tedy dat které
zůstávají v paměti i po vypnutí počítače. Důležitým údajem u tohoto typu paměti je \emph{seek}, tedy doba nutná k adresování bloku paměti.
% subsubsection pomocna_pamet (end)
\subsubsection{Zálohovací paměť}\label{ssub:zalohovaci_pamet} % (fold)
Zařízení jejichž úlohou bylo archivovat data. Dnes je ale kapacita disků tak vysoká, že neexistuje vhodná zálohovací technologie.
Přitom jejich cena neustále klesá. Používaným řešením je tedy v současnosti vytvoření diskových polí s vysokou mírou \emph{redundance dat}.\\
Tyto zařízení používají typicky sekvenční přístup.
% subsubsection zalohovaci_pamet (end)
% subsection hierarchie_pameti (end)
\subsection{Správa paměti}\label{sub:sprava_pameti} % (fold)
Důležitá součást operačního systému jejíž součástí je správa paměťové hierarchie.
\paragraph{Úkoly memory managementu}\label{ssub:ukoly_memory_managementu} % (fold)
\begin{itemize}
\item informace o volné/plné části paměti, její rozdělení
\item přidělování paměti
\item výměna paměti s diskem
\end{itemize}
% paragraph ukoly_memory_managementu (end)
\subsubsection{Přiřazení adresy}\label{ssub:prirazeni_adresy} % (fold)
\begin{description}
\item[při překladu] je již známo umístění procesu, generuje se absolutní kód; používá se pro systémové knihovny
\item[při zavádění] operační systém rozhodne o umístění, generuje se kód s relokacemi; používá se pro knihovny
\item[za běhu] proces se může stěhovat i za běhu, používá se \emph{relokační registr}
\end{description}
% subsubsection prirazeni_adresy (end)
\paragraph{Overlay}\label{ssub:overlay} % (fold)
Proces potřebuje více paměti než je skutečně k dispozici. Vyžaduje spolupráci programátora,
ten rozdělí program na nezávislé části a část nezbytnou pro všechny části, ta je neustále v paměti,
ostatní části jsou v oblasti překrývání a jejich paměťový prostor se navzájem překrývá.
% paragraph overlay (end)
\paragraph{Výměna (swapping)}\label{ssub:vymena_swapping} % (fold)
Proces musí být v hlavní paměti aby jeho instrukce mohly být vykonávány procesorem.
% paragraph vymena_swapping (end)
\subsubsection{Překlad adresy}\label{ssub:preklad_adresy} % (fold)
Proces pracuje v logickém (virtuálním) adresovém prostoru. Hardware pracuje s fyzickým adresovým prostorem.
Mezi těmito adresovými prostory je potřeba provádět \emph{překlad adresy}, ten zajišťuje hardware.
% subsubsection preklad_adresy (end)
\subsubsection{Přidělování paměti}\label{ssub:pridelovani_pameti} % (fold)
\paragraph{Spojité přidělování}\label{ssub:spojite_pridelovani} % (fold)
Část přidělené paměti je fyzicky spojitá.
\begin{description}
\item[spojité přidělování s jedním pamětovým oddílem] jednoduchý překlad adres, tato technika byla často používána při \emph{swappingu}
\item[spojité přidělování s více paměťovými oddíly] pamětový prostor je rozdělen do několika pevných oddílů podle velikosti,
procesy jsou přiřazovány do jednotlivých front podle paměťových požadavků
\item[spojité přidělování s více volnými pamětovými oddíly] dnes používaný způsob přidělování paměti, často při správě \emph{haldy};
bloky jsou alokovány a přidělovány podle potřeby, při přidělování a uvolňování paměti dochází k jevu nazývanému \emph{interní fragmentace}
\end{description}
% paragraph subsubsection_name (end)
\paragraph{Uložení informací o volném místě}\label{ssub:ulozeni_informaci_o_volnem_miste} % (fold)
\begin{description}
\item[bitmapa] bloky pevné velikosti
\begin{itemize}
\item s velikostí bloku roste \emph{interní fragmentace} ale klesá režie nutná ke správě paměti
\item některé procesory obsahují specialní instrukce pro práci s bitmapou
\end{itemize}
\item[spojový seznam] seznam volných bloků
\begin{itemize}
\item se snižující se velikostí bloků roste délka seznamu a zvyšuje se režie nutná ke správě seznamu
\item při uvolňování je nutné spojit uvolněné bloky
\end{itemize}
\end{description}
% paragraph ulozeni_informaci_o_volnem_miste (end)
\paragraph{Algoritmy pro přidělování paměti}\label{ssub:algoritmy_pro_pridelovani_pameti} % (fold)
\begin{description}
\item[first-fit] použiji první volný blok dostatečné velikosti
\begin{itemize}
\item rychlý
\item občas rozdělí velký blok
\end{itemize}
\item[next-fit] použiji první volný blok dostatečené velikosti, hledání začíná na poslední prohledávané pozici
\begin{itemize}
\item ještě rychlejší než \emph{first-fit}
\item rovnoměrnější rozdělení paměti
\item větší tendence k rozdělování velkých bloků
\end{itemize}
\item[best-fit] použiji nejmenší volný blok dostatečné velikosti
\begin{itemize}
\item pomalý vzhledem k nutnosti procházení celého seznamu
\item nechává velké bloky vcelku
\item zanechává velmi malé bloky do kterých se nic nevejde, tento jev se nazývá \emph{externí fragmentace}
\end{itemize}
\item[worst-fit] použiji největší volný blok
\begin{itemize}
\item pomalý vzhledem k nutnosti procházení celého seznamu
\item rozděluje velké bloky
\item teoretický algoritmus vytvořený k zabránění \emph{externí fragmentace}, v praxi nepoužívaný
\end{itemize}
\item[buddy systém] bloky o velikosti $2^n$, bloky stejné velikosti v seznamu, zarovnání adres
\begin{itemize}
\item při přidělování se velikost bloku zaokrouhluje na nejbližší $2^n$
\item pokud neexistuje volný blok, rozštěpí se větší bloky na příslušné menší velikosti
\item při uvolnění paměti se slučují sousední bloky stejné velikosti
\item přidělování paměti lze provádět s konstatní časovou složitostí
\end{itemize}
\end{description}
% paragraph algoritmy_pro_pridelovani_pameti (end)
% subsubsection pridelovani_pameti (end)
\subsubsection{Fragmentace paměti}\label{ssub:fragmentace_pameti} % (fold)
\begin{description}
\item[externí fragmentace] volný paměťový prostor je rozdělen na malé části, v některých případech může dosáhnout až 50\%
\item[Interní fragmentace] nevyužití celého přiděleného prostoru
\end{description}
\paragraph{Sesypání}\label{ssub:sesypani} % (fold)
Snaha o odstranění externí fragmentace. Lze použít pouze při přiřazení adresy za běhu nebo segmentaci. Velká časová náročnost,
z toho důvodu se v praxi nepoužívá.
% paragraph sesypani (end)
% subsubsection fragmentace_pameti (end)
% subsection sprava_pameti (end)
\subsection{Virtuální paměť}\label{sub:virtualni_pamet} % (fold)
Procesy nepracují s fyzickou adresou ale virtuální adresou paměti, tato je hardwarově převáděna na fyzickou adresu.
Zobrazení virtuální adresy do fyzické nemusí existovat, v tom případě dochází k vyjímce a je nutné změnit obsah paměti tak aby toto zobrazení existovalo.
Obraz virtuální paměti je částečně v hlavní a částečně v pomocné paměti.
Použitím virtuální paměti dochází ke zvětšení adresního prostoru.
Jednotlivé procesy mají vlastní adresní prostor čímž je zajištěna ochrana paměťového prostoru jednotlivých procesů.
Na 32-bitových procesorech je fyzický adresový prostor větší než virtuální adresový prostor. Každý proces má vlastní adresový prostor.
Na 64-bitových procesorech virtuální adresový prostor větší než fyzický adresový prostor.
Používá se technika nazývaná \emph{Single Address Space} umožňující vytvořit spojitý adresový prostor velikosti $2^{64}$ bitů ve kterém běží všechny procesy,
ochrana je v tomto případě zajištěna pomocí klíčů.
\subsubsection{Stránkování}\label{ssub:strankovani} % (fold)
Virtuální adresový prostor je rozdělen na úseky stené délky nazývané \emph{stránky}.
Fyzický adresový prostor je rozdělen na úseky stejné délky jako \emph{stránky} nazývané \emph{rámce}.\\
Převod adres je zajištěn pomocí stránkovací tabulky. Každý virtuální adresový prostor má vlastní stránkovací tabulku.
První část adresy stránky použiji jako index stránkovací tabulky, obsahuje příznak existence mapování; druhá část funguje jako offset.
Pokud chci dosáhnout sdílení paměti mezi procesy, sdílím rámce mezi více stránkovacími tabulkami.\\
Virtuální i fyzický adresní prostor je jednorozměrný. Podporován většinou procesorů a operačních systémů.
\paragraph{Stránkovací tabulky}\label{ssub:strankovaci_tabulky} % (fold)
Jsou umístěny v hlavní paměti. Problémem je jejich velikost a pomalost.
\begin{description}
\item[víceúrovňové stránkování] stránkovací tabulky jsou rozděleny do více úrovní
\item[TLB] asociativní paměť, lokalita chování programů
\item[nulaúrovňové stránkování] využívá poze \emph{TLB}, ta je řízena i operačním systémem
\item[inverzní stránkování] fyzický adresový prostor je menší než virtuální adresní prostor,
použití hašovací tabulky o velikosti fyzického adresového prostoru
\end{description}
% paragraph strankovaci_tabulky (end)
\paragraph{Algoritmy pro výměnu stránek}\label{ssub:algoritmy_pro_vymenu_stranek} % (fold)
\begin{description}
\item[Optimal Page] teoreticky perfektní algoritmus který se nedá implementovat
\item[Not Recently Used] dělí stránky do kategorií podle frekvence přístupu
\item[First In First Out] může vykazovat anomálie
\item[Second Chance] úprava algoritmu \emph{First In First Out} která nevykazuje anomálie
\item[Clock] modifikace algoritmu \emph{Second Chance}
\item[Least Recently Used] stránky často používané v předchozím krátkém časovém úseku budou v nejbližších okamžicích znovu použity, lze implementovat v hardwaru
\item[Not Frequently Used] softwarová simulace agoritmu \emph{Least Recently Used} která používá softwarový čítač ke každé stránce, modifikací je stárnutí čítače
\item[Random]
\end{description}
% paragraph algoritmy_pro_vymenu_stranek (end)
\paragraph{Alokační strategie}\label{ssub:alokacni_strategie} % (fold)
Alokace paměti pro jednotlivé procesy.
\begin{description}
\item[lokální] každý proces má svoji množinu rámců a v ní provádí algoritmy pro výměnu, pracovní množina
\item[globální] procesy sdílí všechny rámce
\end{description}
% paragraph alokacni_strategie (end)
\paragraph{Implementace}\label{ssub:implementace} % (fold)
Je nutné zajistit znovuspuštění instrukce po výpadku stránky. Často se využívá sdílení stránek, při použití \emph{Single Address Space} není nutné přepočítávat adresy.
Po zrušení mapování je nutné zrušit položku \emph{TLB}, při použití více procesorů je nutné toto zařídit na všech procesorech.
% paragraph implementace (end)
% subsubsection strankovani (end)
\subsubsection{Segmentace}\label{ssub:segmentace} % (fold)
Program je rozdělen na logické celky se stejnými vlastnostmi nazývané \emph{segmenty}. Ty mohou mít různou velikost a ta se může za běhu měnit.
Dvojrozměrný virtuální adresní prostor, jednorozměrný fyzický adresní prostor.\\
\emph{Segment} vytváří souvislou oblast ve fyzické paměti, fyzický adresní prostor tedy vypadá stejně jako při spojitém přidělování.
Lze implementovat sesypání ve fyzickém adresním prostoru. Umožňuje rozdělit paměť procesu na různé části podle použití.\\
Při výpadku \emph{segmentu} je nutné vyměnit celý \emph{segment} a ten může být velký. Nelze mít \emph{segment} větší než fyzický adresní prostor.\\
Lze kombinovat se stránkováním, toto řešení odstraňuje nevýhody segmentace protože se neprovádí výpadky \emph{segmentů}.
Dnes implementován pouze na architektuře \emph{Intel IA-32}.
% subsubsection segmentace (end)
% subsection virtualni_pamet (end)
% section sprava_pameti (end)
\section{Souborové systémy}\label{sec:souborove_systemy} % (fold)
\subsection{Soubory}\label{sub:soubory} % (fold)
\emph{Soubor} je pojmenovaná množina souvisejících informací která leží v pomocné paměti. Jde o abstrakci umožňující uložit informaci na disk a později ji přečíst.
Soubory mají jméno, atributy, strukturu, typ. Na souborech jsou definovány druhy přístupu a operace.
\subsubsection{Pojmenování souborů}\label{ssub:pojmenovani_souboru} % (fold)
Umožňuje i prostému uživateli přístup k jeho datům. Existují pravidla pro pojmenování souborů které určuje operační systém.
% subsubsection pojmenovani_souboru (end)
\subsubsection{Atributy souborů}\label{ssub:atributy_souboru} % (fold)
Definují vlastnosti a uchovávají informace o souboru. Atributy opět určuje operační systém.
% subsubsection atributy_souboru (end)
\subsubsection{Struktura souborů}\label{ssub:struktura_souboru} % (fold)
Sekvence bajtů, záznamů; strom. Struktura se běžně používá, navenek ale není vidět.
% subsubsection struktura_souboru (end)
\subsubsection{Typy souborů}\label{ssub:typy_souboru} % (fold)
\begin{description}
\item[běžné soubory] obsahují informace
\item[adresáře] systémové soubory vytvářející strukturu souborového systému
\item[speciální soubory] znakové/blokové, soft linky
\end{description}
% subsubsection typy_souboru (end)
\subsubsection{Druhy přístupu k souborům}\label{ssub:druhy_pristupu_k_souborum} % (fold)
\begin{description}
\item[sekvenční] umožňují pohyb pouze jedním směrem, možné převynutí, umožňují operačnímu souboru přednačítání
\item[přímý] umožňuje měnit aktuální pozici
\item[paměťově mapované] využití stránkování
\end{description}
% subsubsection druhy_pristupu_k_souborum (end)
\subsubsection{Paměťově mapované soubory}\label{ssub:pametove_mapovane_soubory} % (fold)
Pojmenovaná virtuální paměť. Výhodou je že program přistupuje k souboru instrukcemi pro práci s pamětí, tím se ušetří kopírování paměti.\\
Problémem je přesná velikost souboru, stránkování má \emph{granularitu} která znemožňuje přesně namapovat soubor do paměti.\\
Dalším problémem je zvětšování souboru při jejich mapování do virtuálního adresového prostoru.\\
Maximální velikost souboru může být větší než velikost virtuálního adresového prostoru,
k řešení tohoto problému se používá \emph{okno} které určí mapovanou část souboru.
Při použití \emph{Single Address Space} tento problém odpadá.
% subsubsection pametove_mapovane_soubory (end)
\subsubsection{Operace se soubory}\label{ssub:operace_se_soubory} % (fold)
\begin{itemize}
\item vytvoření souboru
\item smazání souboru
\item otevření souboru
\item zavření souboru
\item čtení souboru
\item zápis souboru
\item posun aktuální pozice v souboru
\end{itemize}
% subsubsection operace_se_soubory (end)
% subsection soubory (end)
\subsubsection{Adresáře}\label{ssub:adresare} % (fold)
Jde o zvláštní typ souboru který slouží pro udržení organizační struktury souborů, uchovávání atributů souboru.
Dnes typicky hierarchický systém který má definovaný kořen.
\subsubsection{Operace s adresáři}\label{ssub:operace_s_adresari} % (fold)
\begin{itemize}
\item hledání souboru
\item vypsání adresáře
\item přejmenování adresáře
\item vytvoření adresáře
\item smazání adresáře
\end{itemize}
% subsubsection operace_s_adresari (end)
\subsubsection{Cesty}\label{ssub:cesty} % (fold)
Pojmenování souboru v hierarchickém uspořádání. Aktuální adresář je vlastnost procesu, jména souborů která nezačínají kořenem se hledají vzhledem k aktuálnímu adresáři.
\begin{itemize}
\item absolutní cesta
\item relativní cesta
\end{itemize}
% subsubsection cesty (end)
\subsubsection{Linky}\label{ssub:linky} % (fold)
\begin{description}
\item[hard link] na jedna data souboru zse odkazuje z ruzných položek v adresářích
\item[soft link] speciální soubor, který obsahuje jméno souboru
\end{description}
% subsubsection linky (end)
\subsubsection{Hierarchická struktura}\label{ssub:hierarchicka_struktura} % (fold)
\begin{description}
\item[strom] jednoznačné pojmenování
\item[\emph{Direct Acyclic Graph}] víceznačné pojmenování, neexistují zde cykly
\item[obecný graf] víceznačné pojmenování, existují zde cykly, ty mohou být problematické při vyhledávání
\end{description}
% subsubsection hierarchicka_struktura (end)
% subsubsection adresare (end)
\subsection{Implementace souborových systémů}\label{sub:implementace_souborovych_systemu} % (fold)
\paragraph{Základní pojmy}\label{ssub:zakladni_pojmy} % (fold)
\begin{description}
\item[správa souborů] kde jsou umístěna data uložená v souboru
\item[správa adresářů] mapování jména na jeho binární identifikaci, uložení atributů
\item[správa volného místa] informace o volných blocích
\end{description}
% paragraph zakladni_pojmy (end)
\paragraph{Velikost bloku}\label{ssub:velikost_bloku} % (fold)
Disky jsou organizovány po sektorech.
Pro zjednodušení správy sektorů se sousedící sektory spojují do bloků, jejich velikost je daná souborovým systémem.
Operační systém pracuje s těmito bloky. Soubory se ukládájí na disk po blocích.
\begin{description}
\item[velké bloky] rychlejší práce s diskem, nebezpečí velké vnitřní fragmentace (průměrná velikost souboru je v řádu jednotek kB)
\item[malé bloky] pomalejší práce s diskem, větší režie na udržení informace o volných blocích
\end{description}
% paragraph velikost_bloku (end)
\subsubsection{Uložení souborů}\label{ssub:ulozeni_souboru} % (fold)
\paragraph{Souvislá alokace}\label{ssub:souvisla_alokace} % (fold)
Souvislý sled bloků. Informace o uložení souboru sestává pouze z čísla prvního bloku. Výhodou je lepší práce s diskem.
Problém nastává při hledání volného místa, při zvětšování souborů. Z tohoto důvodu se nepoužívá.
% paragraph souvisla_alokace (end)
\paragraph{Spojovaná alokace}\label{ssub:spojovana_alokace} % (fold)
Pospojování bloků použitých pro soubor. Pro udržení informace o uložení souboru je potřeba pouze číslo prvního bloku.
Nevýhodou je nutnost většího místa pro blok pro uložení informace o následníkovi.
Operace posunu je díky nutnosti procházet spojový seznam velmi pomalá.
V případě jednosměrného seznamu je problémem posun směrem dozadu.
V praxi se používá modifikace která spočívá v přemístění spojového seznamu do speciální oblasti disku.
Tato struktura také udržuje informace o volném místě na disku.
Tento typ alokace používají všechny souborové systému typu \emph{FAT}.
% paragraph spojovana_alokace (end)
\paragraph{Indexová alokace}\label{ssub:indexova_alokace} % (fold)
Bloky jsou rozděleny na dva navzájem různé typy.
\emph{i-node} bloky obsahují informace o bloku a také indexy datových bloků souboru.
Předposlední dva indexy se používají pro jednoúrovňovou indexaci, poslední index se používá pro dvouúrovňovou indexaci.
% paragraph indexova_alokace (end)
% subsubsection ulozeni_souboru (end)
\subsubsection{Implementace adresářů}\label{ssub:implementace_adresaru} % (fold)
\begin{itemize}
\item záznamy pevné velikosti
\item spojový seznam
\item B-stromy
\end{itemize}
% subsubsection implementace_adresaru (end)
\subsubsection{Volné místo na disku}\label{ssub:volne_misto_na_disku} % (fold)
Obdoba udržování informací o volném místě v paměti.
\begin{itemize}
\item bitmapa
\item spojový seznam volných bloků
\end{itemize}
% subsubsection volne_misto_na_disku (end)
% subsection implementace_souborovych_systemu (end)
\subsection{Implementace}\label{sub:implementace} % (fold)
\subsubsection{NTFS}\label{ssub:ntfs} % (fold)
V podstatě neomezená velikost i počet souborů. Jména v \emph{UCS2} délky maximálně 255 znaků.
Umožňuje libovolné atributy včetně přístupových práv. Dovolují vícenásobné streamy a
\emph{Sparse file} tedy díry ve streamech.
Podpora šifrování a komprese.
Automatická \emph{fault tolerance} pomocí žurnálování (transakce).
Dovolují \emph{hard linky} i \emph{soft linky}.
Adresáře jsou soubory s \emph{B-stromy} a odkazy na soubory.
Řídicí struktury obsaženy ve speciálním souboru \emph{Master File Table}.
\paragraph{Master File Table}\label{ssub:master_file_table} % (fold)
Rozdělena na soubory velikosti 1kB.
Prvních 16 souborů je speciálních (metasoubory), ty obsahují informace o souborovém systému, o žurnálu, o velikosti, o atributech.
Základní záznam obsahuje počet odkazů, příznaky a seznam atributů (včetně streamů).
Malé soubory jsou uloženy přímo v tomto záznamu.
Pokud pro popis dat nebo seznamu atributů nestačí základní záznam, připojí se další záznamy.
% paragraph master_file_table (end)
\paragraph{Run list}\label{ssub:run_list} % (fold)
Funkční implementace souvislé alokace pomocí spojového seznamu souvislých částí, prvek je \emph{run} který obsahuje
velikost, \emph{virtual cluster number}, \emph{logical cluster number} a odkaz na další \emph{run}.
% paragraph run_list (end)
% subsubsection ntfs (end)
\subsubsection{EXT2/EXT3}\label{ssub:ext2_ext3} % (fold)
Velikost systému 4TB. Jména délky maximálně 255 znaků. Rezervace volného místa pro \emph{roota}.
Dovoluje \emph{hard linky} i \emph{soft linky}.
Prealokace po 8 souvislých blocích při zápisu, zbytek vrácen při zavření.
EXT3 implementuje \emph{žurnálování} jako rozšíření EXT2, souborový systém rozumí transakci ale nedělá žurnálování,
několik transakcí je cachováno, a pak uloženo najednou do žurnálu jako složená transakce.
\paragraph{Struktura}\label{ssub:struktura} % (fold)
Disk je rozdělen na části. Na počátku je uložen \emph{boot block}, zbylá část je rozdělena do skupin.
Každý blok je rozdělen na část která obsahuje superblok, popis bloku, bitmapy pro uložení informací o volném místě,
\emph{i-node} bloky a datové bloky.
% paragraph struktura (end)
\paragraph{i-node}\label{ssub:i_node} % (fold)
Předdefinované soubory odkazující na metasoubory. Několik pevných atributů UID, GID, velikost, různé časy, počet odkazů, 12 přímých odkazů na bloky,
jeden nepřímý, jeden dvojitě a jeden trojitě nepřímý soubor. Žurnál je uložen jako rezerovaný \emph{i-node}.
% paragraph i_node (end)
% subsubsection ext2_ext3 (end)
% subsection implementace (end)
% section souborove_systemy (end)
\section{Vstupně/výstupní subsystémy}\label{sec:vstupne_vystupni_subsystemy} % (fold)
Operační systém je abstraktní stroj. Pro přístup k zařízení slouží řadič zařízení, adaptér jako část I/O jednotky.
% paragraph druhy_pristupu (end)
\subsection{Charakteristiky zařízení}\label{sub:charakteristiky_zarizeni} % (fold)
\subsubsection{Druhy přístupu}\label{ssub:druhy_pristupu} % (fold)
\begin{description}
\item[port] speciální adresový prostor procesoru
\item[paměťove mapované] mapované do fyzické paměti
\end{description}
% subsubsection druhy_pristupu (end)
\subsubsection{Druhy zařízení}\label{ssub:druhy_zarizeni} % (fold)
\begin{itemize}
\item blokové
\item znakové
\end{itemize}
% subsubsection druhy_zarizeni (end)
\subsubsection{Přístup}\label{ssub:pristup} % (fold)
\begin{itemize}
\item sekvenční
\item náhodný
\end{itemize}
% subsubsection pristup (end)
\subsubsection{Synchronnost komunikace}\label{ssub:synchronnost_komunikace} % (fold)
\begin{description}
\item[synchronní] zařízení pracuje s daty na žádost
\item[asynchronní] zařízení poskytuje i ``nevyžádaná'' data, v operačním systému musí být dále zpracována
\end{description}
% subsubsection synchronnost_komunikace (end)
\subsubsection{Sdílení}\label{ssub:sdileni} % (fold)
\begin{itemize}
\item sdílené, preemtivní
\item vyhrazené, nepreemtivní, dedikovaná
\end{itemize}
% subsubsection sdileni (end)
\subsubsection{Rychlost}\label{ssub:rychlost} % (fold)
Rozsah od několika B/s do GB/s.
% subsubsection rychlost (end)
\subsubsection{Směr dat}\label{ssub:smer_dat} % (fold)
\begin{itemize}
\item read/write
\item read/only
\item write/only
\end{itemize}
% subsubsection smer_dat (end)
% subsection charakteristiky_zarizeni (end)
\subsection{Cíle vstupně/výstupních subsystémů}\label{sub:cile_vstupne_vystupnich_subsystemu} % (fold)
\begin{description}
\item[nezávislost zařízení] programy nemusí dopředu vědět, s jakým přesně zařízením budou pracovat
\item[jednotné pojmenování]
\item[připojení] časté u vyměnitelných zařízení, možné i u pevných zařízení, nutné pro správnou funkci cache operačního systému
\item[obsluha chyb] v mnoha případech oprava bez vědomí uživatele, velmi často způsobeno právě uživatelem
\end{description}
% subsection cile_vstupne_vystupnich_subsystemu (end)
\subsection{Přenos dat}\label{sub:prenos_dat} % (fold)
\begin{description}
\item[polling] ovladač aktivně čeká na změnu stavu zařízení, přenos dat je úkolem procesoru
\item[přerušení] zařízení hlásí připravenost nebo dokončení činnosti, přenos dat je úkolem procesoru
\item[DMA (direct memory access)] zařízení si samo řídí přístup na sběrnici a přenáší data z/do paměti, po skončení přenosu dojde k vyvolání přerušení;
\emph{scatter-gather DMA} kdy popíši celou sérii bloků které chci přenést
\end{description}
% subsection prenos_dat (end)
\subsection{Vstupně/výstupní software}\label{sub:vstupne_vystupni_software} % (fold)
Typicky ve 4 vrstvách.
\begin{enumerate}
\item uživatelský I/O software
\item I/O nezávislý subsystém
\item ovladače zařízení
\item obsluha přerušení
\end{enumerate}
\subsubsection{Obsluha přerušení}\label{ssub:obsluha_preruseni} % (fold)
\begin{enumerate}
\item uložení stavu procesoru (kontext vlákna)
\item potvrzení přerušení řadiči přerušení
\item obsluha přerušení ovladačem
\item přeplánování
\item načtení stavu procesoru
\end{enumerate}
% subsubsection obsluha_preruseni (end)
\subsubsection{Jednotné rozhraní pro zařízení}\label{ssub:jednotne_rozhrani_pro_zarizeni} % (fold)
Poskytuje uživatelským programům jednotné rozhraní. Skrývá rozdíly mezi jednotlivými zařízeními. Provádí pomocné úkoly pro ovladače.
% subsubsection jednotne_rozhrani_pro_zarizeni (end)
\subsubsection{Vyrovnávací paměti}\label{ssub:vyrovnavaci_pameti} % (fold)
Vyrovnání rychlosti aplikace a zařízení, cachování. Některá zařízení pracují po blocích.
% subsubsection vyrovnavaci_pameti (end)
% subsection vstupne_vystupni_software (end)
\subsection{Zařízení}\label{sub:zarizeni} % (fold)
\subsubsection{Disky}\label{ssub:disky} % (fold)
Čas na provedení operace se skládá je rozdělen na tři části.
\begin{description}
\item[seek] čas nutný k přesunu hlaviček
\item[latency] zpoždění způsobené rotací
\item[transfer] doba přenosu dat z disku do paměti
\end{description}
Prostor disku je dnes lineární.
\paragraph{Plánování pohybu hlav disků}\label{ssub:planovani_pohybu_hlav_disku} % (fold)
\begin{description}
\item[FCFS (First-Come, First-Served)] ``kdo dřív přijde, ten dřív mele'', vhodné pro malé zátěže
\item[SSTF (Shortest Seek Time First)] hledám nejmenší vzdálenost od aktuální pozice, v případě velké zátěže se může stát že na krajní pozice se nedostane,
vhodný pro malé zátěže
\item[LOOK] algoritmus výtahu, hlavy se vždy pohybují od kraje ke kraji jedním směrem, příznak směru pohybu,
v průběhu zpracováváme příchozí požadavky ve směru pohybu, vhodný pro velké zátěže
\item[C-LOOK (Circular LOOK)] směr provádění je pouze jeden, jakmile hlavy dorazí na konec, vrací se zpět a začínají znovu
\end{description}
% paragraph planovani_pohybu_hlav_disku (end)
% subsubsection disky (end)
\subsection{RAID (Redundant Array of Inexpensive Disks)}\label{ssub:raid_redundant_array_of_inexpensive_disks} % (fold)
Pole paralelně zapojených disků. Cílem je vytvořit iluzi jednoho disku použítím více disků.
\paragraph{Důvody}\label{ssub:duvody} % (fold)
\begin{itemize}
\item zvětšení spolehlivosti
\begin{description}
\item[MTBF (Mean Time Between Failure)] průměrný čas mezi poruchami
\item[MTTR (Mean Time To Repair)] průměrný nutný k rekonstrukci
\end{description}
\item zrychlení
\end{itemize}
% paragraph duvody (end)
\begin{description}
\item[JBOD (Just Bunch Of Disks)] spojení disků za účelem zvýšení kapacity
\item[RAID 0 (Striping)] spojení disků za účelem zvýšení rychlosti, operace se provádějí paralelně na všechny disky najednou
\item[RAID 1 (Mirroring)] spojení disků za účelem zvýšení spolehlivosti, zápisy se provádějí paralelně, ke čtení se používá pouze jeden disk
\item[RAID 0+1] spojení \emph{RAID 0} a \emph{RAID 1}
\item[RAID 2] použití 7-bitového \emph{Hammingova paritního kódu}, data se ukládají po bitech na jednotlivé disky
\item[RAID 3] použití jednoho paritního disku, data se ukládají po bitech na disky
\item[RAID 4] použití jednoho paritního disku a \emph{stripingu}, paritní disk se v tomto případě stává úzkým hrdlem
\item[RAID 5] distribuovaná parita a \emph{striping}, paritní \emph{stripy} jsou na všech discích
\item[RAID 50] spojení více \emph{RAID 5} jako \emph{RAID 0} pomocí \emph{stripingu}
\item[RAID 6] distribuovaná parita P+Q a \emph{striping}
\item[RAID 60] spojení více \emph{RAID 6} jako \emph{RAID 0} pomocí \emph{stripingu}
\end{description}
% subsection raid_redundant_array_of_inexpensive_disks (end)
% subsection zarizeni (end)
% section vstupne_vystupni_subsystemy (end)
\section{Ochrana a bezpečnost}\label{sec:ochrana_a_bezpecnost} % (fold)
\subsection{Ochrana a bezpečnost}\label{sub:ochrana_a_bezpecnost} % (fold)
\begin{description}
\item[ochrana] s prostředky operačního systému mohou pracovat pouze autorizované procesy
\item[bezpečnost] zabraňuje neautorizovaným přístup do systému
\end{description}
\subsubsection{Domény ochrany}\label{ssub:domeny_ochrany} % (fold)
\emph{Právo} je povolení/zakázání vykonávat nějakou operaci. \emph{Doména} je množina párů objekt a právo. Spojením dostáváme \emph{matici ochrany}.
\begin{description}
\item[ACL (Access Control List)] ke každému objektu seznam práv pro uživatele/skupiny
\item[C-list (Capability List)] ke každému uživateli/skupině seznam práv pro objekty
\end{description}
% subsubsection domeny_ochrany (end)
\subsubsection{Cíle útoků}\label{ssub:cile_utoku} % (fold)
\begin{description}
\item[důvěrnost dat] uživatel může určit kdo má data vidět, a systém skutečně dovolí pracovat s daty pouze povoleným uživatelům
\item[celistvost dat] možnost podstrčení falešných dat
\item[dostupnost systému] \emph{DoS (Denial of Service)}
\end{description}
% subsubsection cile_utoku (end)
\subsubsection{Autentikace}\label{ssub:autentikace} % (fold)
Identifikace něčím, co uživatel ví, má nebo je.
\begin{description}
\item[heslo] dá se napadnout slovníkovým útokem, hrubou sílou, řešením může být vynucování délky, složitosti hesla
\item[model otázka/odpověď] často v kombinaci s heslem
\item[fyzický objekt] použití fyzického zařízení
\item[biometrika] rozeznání papilárních čar, rohovek, hlasu
\end{description}
% subsubsection autentikace (end)
\subsubsection{Vnitřní útoky}\label{ssub:vnitrni_utoky} % (fold)
\begin{description}
\item[trójský kůň] zdánlivě neškodný program obsahuje ``zlý'' kód
\item[trap door, back door] kód při nějaké podmínce přeskočí normální kontroly
\item[buffer overflow] ve velkém množství kódu nejsou dělány kontroly na přetečení polí pevné velikosti,
při přetečení se typuicky přepíše část zásobníku a lze tam umístit adresu kódu i samostatný kód, který se vykoná při návratu z funkce
\end{description}
% subsubsection vnitrni_utoky (end)
\subsubsection{Vnější útoky}\label{ssub:vnejsi_utoky} % (fold)
\begin{description}
\item[virus] vytvoření nakaženého souboru, po spuštění infikuje další soubory, přenos pomocí médií, sítí
\item[worm] samoreplikující se program využívající chyby systému
\end{description}
% subsubsection vnejsi_utoky (end)
% subsection ochrana_a_bezpecnost (end)
\subsection{Kryptografie}\label{sub:kryptografie} % (fold)
\paragraph{Cíle kryptografie}\label{ssub:cile_kryptografie} % (fold)
\begin{itemize}
\item důvěrnost
\item celistvost
\item autentikace
\item nemožnost popření
\end{itemize}
% paragraph cile_kryptografie (end)
\paragraph{Vrstvy}\label{ssub:vrstvy} % (fold)
\begin{itemize}
\item kryptografické algoritmy
\item kryptografické protokoly
\end{itemize}
% paragraph vrstvy (end)
\subsubsection{Kryptografický systém}\label{ssub:kryptograficky_system} % (fold)
Prostor otevřených zpráv $M$, šifrovaných zpráv $C$, šifrovacích a dešifrovacích klíčů $K$ a $K'$. Efektivní generování klíčů
$G:N\to K\times K'$, šifrování $E:M\times K\to C$, dešifrování $D:C\times K'\to M$.
Dobrý kryptografický systém dodržuje \emph{Kerchoffovy principy} dobrého kryptografického systému.
\paragraph{Kerchoffovy principy dobrého kryptografického systému}\label{ssub:kerchoffovy_principy_dobreho_kryptografickeho_systemu} % (fold)
\begin{itemize}
\item algoritmy neobsahují žádnou tajnou část
\item šifrovací algoritmus distribuuje rozumné zprávy rovnoměrně po celém prostoru šifrovaných zpráv
\item se správným klíčem jsou šifrovací a dešifrovací algoritmy ekvivalentní
\item bez správného klíče je nalezení otevřené zprávy ze šifrované zprávy NP-úplný problém
\end{itemize}
% paragraph kerchoffovy_principy_dobreho_kryptografickeho_systemu (end)
\paragraph{Model útočníka podle Doleva a Yao}\label{ssub:model_utocnika_podle_doleva_a_yao} % (fold)
\begin{itemize}
\item může získat libovolnou zprávu putující po síti
\item je právoplatným uživatelem sítě a tudíž může zahájit komunikaci s jiným uživatelem
\item může se stát příjemcem zpráv kohokoliv
\item může zasílat zprávy komukoliv zosobněním se za jiného uživatele
\item nemůže odhadnout náhodné číslo z dostatečně velkého prostoru
\item bez správného klíče nemůže nalézt zprávu k šifrované zprávě a nemůže vytvořit platnou šifrovanou zprávu z dané zprávy,
vše vzhledem k nějakému šifrovacímu algoritmu
\end{itemize}
% paragraph model_utocnika_podle_doleva_a_yao (end)
% subsubsection kryptograficky_system (end)
\subsubsection{Symetrické kryptografické systémy}\label{ssub:symetricke_kryptograficke_systemy} % (fold)
Šifrovací klíč je shodný s dešifrovacím. Mají vysokou datovou propustnost. Klíče mají malou délku. Slučováním více šifer získáváme silnější šifru.\\
Klíče na obou koncích musí zůstat utajeny, ty je také třeba často měnit. Potřeba ověřené \emph{Trusted Third Party}.
% subsubsection symetricke_kryptograficke_systemy (end)
\subsubsection{Asymetrické kryptografické systémy}\label{ssub:asymetricke_kryptograficke_systemy} % (fold)
Šifrovací klíč se liší od dešifrovacího, rozlišuje se veřejný a soukromý klíč. Pouze soukromý klíč je tajný.
Klíče není nutné často měnit, není zapotřebý \emph{Trusted Third Party}.\\
Jsou mnohem pomalejší než symetrické šifry. Používají dlouhé klíče. O žádném schématu veřejného klíče nebylo dokázáno, že je bezpečné.
% subsubsection asymetricke_kryptograficke_systemy (end)
\subsubsection{Útoky na protokoly}\label{ssub:utoky_na_protokoly} % (fold)
\begin{itemize}
\item přehrání zpráv
\item \emph{man-in-the-middle}
\item paralelní spojení
\item odražení
\item prokládání
\item chyba typu
\item vypuštění jména
\item chybné použití šifrovací služby
\end{itemize}
% subsubsection utoky_na_protokoly (end)
% subsection kryptografie (end)
% section ochrana_a_bezpecnost (end)
\end{document}