ZOS 21 Flashcards
Dva základní pohledy na OS:
- Rozšířený stroj (shora dolů)
- Holý počítač –> rozšířený stroj
- Místo jednoduchých strojových instrukcí komplexní akce
- Ulož číslo do registru x zobraz řetězec „ahoj“
- Správce zdrojů (zdola nahoru)
- OS jako manager , přiřazuje a spravuje zdroje
- Zdroje: čas CPU, alokace v RAM, přístup k disku
Struktura OS
- modul pro správu procesů
• program, proces, vlákno, plánování procesů a vláken
• kritická sekce, souběh, synchronizace (semafory, …)
• deadlock, vyhladovění - modul pro správu paměti
• virtuální paměť: stránkování, segmentace - modul pro správu I/O
- modul pro spr ávu souborů
- síťování
- ochrana a bezpečnost
- uživatelské rozhraní
Operační systém definice
OS je softwarová vrstva (základní programové vybavení), jejíž úlohou je spravovat hardware a poskytovat k němu programům jednotné rozhraní
• OS zprostředkovává aplikacím přístup k hardwaru
• OS koordinuje zdroje a poskytuje služby aplikacím
• Zdroje čas na procesoru, přidělená paměť, disk, síťová karta
• OS je program, který slouží jako prostředník mezi
aplikacemi a hardwarem počítače.
Program
- Spustitelný kód, v binární podobě je sekvence instrukcí
- Nejčastěji soubor uložený na disku
- Např. C windows system32 calc.exe
Proces
instance běžícího programu
• PID (process id) číslo přidělené procesu systémem
• Přidělen čas CPU
• Potřebuje paměťový prostor
• vstupy a výstupy
• Dle jednoho programu můžeme spustit více procesů
Režimy
- Privilegovaný
2. Uživatelský
Privilegovaný režim
• Všechny instrukce CPU jsou zde povoleny
• Běží v něm jádro OS, které mj. vykonává služby
(systémová volání), o které je aplikace požádá
Uživatelský režim
Aplikace v uživatelském režimu CPU
- Některé instrukce zakázány (tzv. privilegované instrukce) např. není přímý přístup k disku, narušitel –> formátování
- Při pokusu o vykonání privilegované instrukce = => chyba, výjimka
- Aplikace musí požádat OS o přístup k souboru, ten rozhodne zda jej povolí
• Nemůžou vykonávat všechny instrukce, např. přímý
přístup k zařízení (tj. zapiš datový blok x na disk y
• Proč? Jinak by škodlivá aplikace mohla např. smazat disk
• Jak se tomu zabrání? Aplikace musí požádat jádro o službu, jádro ověří, zda aplikace má na podobnou činnost oprávnění
Jak CPU ví, v jakém je režimu?
CPU ví, v jakém je režimu podle bitu ve stavovém registru CPU (0 = priv., 1 = uživ.) - CS (code segment) registr;;
reálně může být bitů více když se v uživatelském -> protection ring
Jak se dostat z uživatelského režimu
do režimu jádra?
Jde o přepnutí „mezi dvěma světy“, v každém z
nich platí jiná pravidla
• Softwarové přerušení instrukce INT -> začne se vykonávat kód přerušení
• Speciální instrukce mikroprocesoru sysenter sysexit , syscall sysret
Systémové volání - definice
Mechanismus používaný aplikacemi k volání služeb
operačního systému.
Systémové volání - důvod
- V uživatelském režimu CPU není možné celou řadu věcí vykonat není přímý přístup k HW , nelze tedy přímo přečíst blok z disku, tedy otevřít soubor, číst z něj a zapisovat do něj.
- Pokud aplikace takovou činnost požaduje, nezbývá jí, než požádat o danou službu operační systém
- Operační systém zkontroluje , zda má aplikace pro danou činnost oprávnění a pokud ano, požadovanou činnost vykoná. (Kontrola může být např. podle ACL, zda má proces daného uživatele právo zapisovat do souboru).
Možnosti aplikace, která chce volat službu
• přímo systémové volání open, creat
• prostřednictvím knihovní funkce (v C např. fopen ),
která následně požádá o systémové volání sama.
• Výhodou knihovní funkce je, že je na různých platformách stejná, ať už se vyvolání systémové služby děje různým způsobem na různých platformách.
Možnosti programátora, když chce službu od jádra
- inline assembler a INT 0x80
viz předchozí ukázka (reálný příklad Linux) - použití instrukce syscall potřebujeme znát číslo funkce interně použije INT 0x80
id 1 = syscall SYS_getpid - přímo je funkce, např. getpid (), fopen () existuje „ wrapper “ v libc knihovně nejpohodlnější a také nejpoužívanější
id 2 = getpid
Vyvolání služby systému
- Parametry uložíme na určené místo
- registry, zásobník…
- Provedeme speciální instrukci, např. INT
- vyvolá obsluhu v jádře
- přepne do privilegovaného režimu
- OS převezme parametry, zjistí, která služba je vyvolána a zavolá příslušnou obsluhu
- Návrat zpět
- Přepnutí do uživatelského režimu (obecně do původního režimu)
Co znamená INT x?
• instrukce v assembleru pro x86 procesory,
která generuje SW přerušení
• x je v rozsahu 0 až 255
• Index do tabulky vektorů přerušení
INT 0x80
• v 16kové soustavě 80, dekadicky 128
• pro vykonání systémového volání v Linuxu
• do registru EAX se dá číslo systémového volání,
které chceme vyvolat
Přerušení x Obsluha přerušení
- Přerušení = Událost
- Obsluha přerušení = obsluha události
• asynchronní (přijde kdykoliv HW stisk klávesy)
• synchronní (instrukce SW přerušení v programu INT),
pak přijde očekávaně
- Analogie z reálného života
- S někým si povídáte
- Zazvoní telefon, vyřídíte telefon
- Vrátíte se k předchozímu povídání
Přerušení - definice
Metoda pro asynchronní obsluhu událostí, kdy procesor přeruší vykonávání sledu instrukcí, vykoná obsluhu přerušení a pak pokračuje v předchozí činnosti.
Přerušení - rozdělení
• HW přerušení (vnější) obsluha HW zařízení
(klávesnice)
• SW přerušení synchronní, instrukcí INT číslo v kódu
procesu
• Vnitřní přerušení (výjimky) procesor oznamuje chyby
při vykonávání instrukcí (dělení nulou, neplatná instrukce)
Jak probíhá asynchronní obsluha události
obsluha události, procesor přeruší vykonávání
sledu instrukcí (části kódu, které se právě věnuje), vykoná obsluhu přerušení (tj. instrukce v obslužné rutině přerušení) a pokračuje předchozí činností
Hardwarové přerušení (vnější)
- Přichází z I /O zařízení, např. stisknutí klávesy na klávesnici
- Asynchronní událost uživatel stiskne klávesu, kdy se mu zachce
- Vyžádá si pozornost procesoru bez ohledu na právě zpracovávanou úlohu
- Doručovány prostřednictvím řadiče přerušení (umí stanovit prioritu přerušením,aj.)
Vnitřní přerušení
- Vyvolá je sám processor
* Např. pokus o dělení nulou, ne platná instrukce, výpadek stránky paměti
Softwarové přerušení
• Speciální strojová instrukce (např. zmiňovaný příklad INT 0x80
• Je synchronní, vyvolané záměrně programem (chce službu volání služeb operačního systému z běžícího procesu, uživatelská úloha nemůže sama skočit do prostoru jádra OS, ale má právě k tomu
softwarové přerušení
Kdy v OS použiji přerušení? - Systémové volání
• Využiji softwarového přerušení a instrukce INT
Kdy v OS použiji přerušení? - Výpadek stránky paměti
• V logickém adresním prostoru procesu se odkazuji na stránku, která není namapovaná do paměti RAM (rámec), ale je odložená na disku
• Dojde k přerušení výpadek stránky
• Běžící proces se pozastaví
• Ošetří se přerušení z disku se stránka natáhne do paměti (když je operační pamět
plná, tak nějaký rámec vyhodíme dle nám známých algoritmů)
• Pokračuje původní proces přístupem nyní už do paměti RAM
Kdy v OS použiji přerušení? - Obsluha HW zařízení
- Zařízení si žádá pozornost
- Klávesnice: stisknuta klávesa
- Disk : mám k dispozici data
- Síťová karta: došel paket
Vektor přerušení
index do pole, obsahující adresu obslužné rutiny, vykonané při daném typu přerušení
Maskování přerušení
v době obsluhy přerušení lze zamaskovat méně důležitá přerušení, ale SW přerušení jsou nemaskovatelná (NMI)
Příchod přerušení
dokončí se rozpracovaná strojová instrukce, na zásobník se uloží adresa následující instrukce (CS:IP) tj. kde jsme skončili a kde budeme chtít pokračovat, z vektoru přerušení se zjistí adresa podprogramu pro obsluhu přerušení, přepnutí do priv. režimu, na zásobník se uloží hodnoty registrů, obsluha, instrukce návratu RET (IRET) a přepnutí do uživ. režimu
Tabulka vektorů přerušení
• Můžeme si ji představit jako pole,
index do pole představuje číslo přerušení,
obsah daného prvku pole adresa obsluhy
- Od adresy 0 do adresy 1KB v RAM
- 256 x 4bytový ukazatel
- Ukazatel adresa obslužného programu pro dané přerušení
- Toto platí v tzv. reálném režimu CPU (MS DOS)
- V tzv. protected modu CPU (neplést s privilegovaným) 8byte ukazatele (tedy celkem 2KB) a začíná od zvolené adresy v paměti udává registr IDTR
- Tabulka IDT
Definice:
Tabulka vektorů přerušení je datová struktura, ve které se uschovávají vektory přerušení.
Vektor přerušení je adresa první instrukce podprogramu pro obsluhu daného přerušení.
Obsluha přerušení může mít 2 části
• první část ve vlastním režimu obsluhy přerušení
velmi rychlé (stabilita)
• odložená část může naplánovat další část, která se vykoná „až bude čas”
Generace počítačů
- Elektronky
- Tranzistory
- Integrované obvody
- LSI, VLSI (mikroprocesory,..)
1.Generace (1945 - 55)
• Elektronky, propojovací desky
• Programování:
- V absolutním jazyce
- Propojování zdířek na desce
- Později děrné štítky, assemblery, knihovny, FORTRAN
- Numerické kalkulace
• Způsob práce
- Stejní lidé stroj navrhli, postavili, programovali
- Zatrhnout blok času na rozvrhu, doufat, že to vyjde
• OS ještě neexistují
- Generace (1955 - 65)
- Tranzistory, dávkové OS
- Vyšší spolehlivost; klimatizované sály
- Oddělení návrhářů, výroby, operátorů, programátorů, údržby
- Miliony velké firmy, vlády, univerzity
- Způsob práce
• Vyděrovat štítky s programem
• Krabici dát operátorovi
• Výsledek vytisknut na tiskárně - Optimalizace
• Na levném stroji štítky přenést na magnetickou pásku
- Generace (1965 - 80)
- Integrované obvody, multiprogramování
- Do té doby 2 řady počítačů
- Vědecké výpočty
- Komerční stroje banky, pojišťovny
• IBM 360 sjednocení
- Malé i velké stroje
- Komplexnost spousta chyb
• Spooling
- Na vstupu ze štítků na disk, úloha se zavede z disku
- Na výstupu výsledky na disk před výtiskem na tiskárně
- Generace (1980+)
• Mikroprocesory, PC • GUI x CLI • Síťové a distribuované systémy • MS DOS, Unix, Windows NT • UNIX dominantní na nonIntel • Linux, BSD rozšíření i na PC - Výzkum Xerox PARC vznik GUI - Apple Macintosh
Dělení OS - Dle úrovně sdílení CPU:
- Jednoprocesový • MS DOS, v daném čase v paměti aktivní 1 program - Multiprocesový • Efektivnost využití zdrojů • Práce více uživatelů
Dělení OS - Dle typu interakce:
• Dávkový systém - Sekvenční dávky, není interakce - Dodáme program a data, čekáme na výsledek - i dnes má smysl, viz. meta. cesnet.cz • Interaktivní - Interakce uživatel úloha - Víceprocesové interakce max. do několika sekund Winows, Linux, ..
OS reálného času
• Výsledek má smysl, pouze pokud je získán v nějakém
omezeném čase
• Přísné požadavky aplikací na čas odpovědi
- Řídící počítače, multimedia
• Časově ohraničené požadavky na odpověď
- Řízení válcovny plechu, výtahu mrakodrapu
• Nejlepší snaha systému
- Multimedia, virtuální realita
Hard realtime OS
- Zaručena odezva v ohraničeném čase
- Všechna zpoždění a režie systému ohraničeny
Omezení na OS:
• Často není systém souborů
• Není virtuální paměť
• Nelze zároveň sdílení času
• Řízení výroby, robotika, telekomunikace
Soft realtime OS
- Priorita RT úloh před ostatními
- Nezaručuje odezvu v daném čase
- Lze v systémech sdílení času
- RT Linux
- Multimédia, virtuální realita
Další dělení OS - Dle velikosti HW
Superpočítač, telefon, čipová karta
Další dělení OS - Míra distribuovanosti
• Klasické centralizované 1 a více CPU
• Paralelní
• Síťové
- Na více uzlech sítě
• Distribuované
- Virtuální uniprocesor (tváří se jako jeden
- Uživatel neví kde běží programy, kde jsou soubory
Další dělení OS - Podle počtu uživatelů
Jedno a víceuživatelské
Další dělení OS - Podle funkcí
- Univerzální
* Specializované (např. Cisco IOS)
Uživatelské rozhraní dělení
- CLI ( command line interface)
* GUI ( graphical user interface)
Dělení dle jádra OS
- Monolitické jádro jádro je jeden funkční celek
- Mikrojádro malé jádro, oddělitelné části pracují jako samostatné procesy v user space
- Hybridní jádro kombinace
Monolitické jádro
- Jeden spustitelný soubor
- Uvnitř moduly pro jednotlivé funkce
- Jeden program, řízení se předává voláním podprogramů
- Příklady: UNIX, Linux, MS DOS
Typickou součástí monolitického jádra je
např. souborový systém
Mikrojádro
- Model klient server
- Většinu činností OS vykonávají samostatné procesy mimo jádro (servery, např. systém souborů)
Mikrojádro
• Poskytuje pouze nejdůležitější nízkoúrovňové funkce
- Nízkoúrovňová správa procesů (vytvoř proces, vlákno, …)
- Adresový prostor, komunikace mezi adresovými prostory
- Někdy obsluha přerušení, vstupy výstupy
• Pouze mikrojádro běží v privilegovaném režimu
- Méně pádů systému
Hybridní jádro
• Kombinuje vlastnosti monolitického a mikrojádra
• Část kódu součástí jádra (monolitické)
• Jiná část jako samostatné procesy ( mikrojádro
• Příklady
- Windows 7 (NT, Win 2000, Win XP, Windows Server 2003, Windows Vista,..)
- Windows CE (Windows Mobile)
- BeOS
Obsluha přerušení - podrobně (znát vše)
I. Mechanismus vyvolání přerušení (vyvolání instrukcí: INT číslo)
◦ Na zásobník se uloží registr příznaků FLAGS
◦ Zakáže se přerušení (vynuluje příznak IF Interrupt Flag v registru FLAGS)
◦ Na zásobník se uloží návratová adresa (obsah registrů CS:IP ) ukazující na instrukci, kde
budeme po návratu z přerušení pokračovat
II. Kód obsluhy přerušení ––„píše programátor”
◦ Na zásobník uložíme hodnoty registrů (abychom je procesu nezměnili)
◦ Vlastní kód obsluhy (musí být rychlý, případně naplánujeme další věci)
◦ Ze zásobníku vybereme hodnoty registrů (aby přerušený proces nic nepoznal)
III. Návrat z přerušení (instrukce:
IRET)
◦ Ze zásobníku je vybrána návratová adresa (obsah registrů CS:IP ) kde budeme pokračovat
◦ Ze zásobníku se obnoví registr FLAGS obnoví původní stav povolení přerušení
Přístup k souboru
pomocí ACL nebo základní unixová práva (UGO - rwx)
IRQ
signál, kterým zařízení žádá procesor o přerušení zpracovávaného procesu
IRQL - priorita přerušovacího požadavku (level)
NMI - nemaskovatelné přerušení, např. nezotavitelná hw chyba (non maskable interrupt)
Sdílení IRQ více zařízeními
na jedno IRQ lze registrovat několik obslužných rutin
(registrovány při inicializaci
do tabulky vektorů přerušení je zavěšena superobsluha
superobsluha pouští postupně jednotlivé zaregistrované obsluhy, až jedna z nich zafunguje
pokud dané přerušení naráz více zařízeními - zavolá opakovaně
DMA
přímý přístup do paměti
Mechanismus umožňující perifernímu zařízení číst či zapisovat z/do operační paměti počítače bez účasti procesoru.
Procesor dá pouze pokyn co se má provést (pomocí IN, OUT instrukcí naprogramuje řadič) a je informován o výsledku (pomocí IRQ signálu).
Např. načtení stránky paměti ze swapu na disku do RAM a naopak
Adresní prostor procesu
- Proces používá typicky virtuální paměť (od 0 do nějaké adresy), která se mapuje do fyzické paměti (RAM paměťové čipy)
- MMU (Memory Management Unit) zajištuje mapování a tedy i soukromí procesu je součástí procesoru
- kód spustitelného programu, data, zásobník
Stavové informace procesu
• S procesem sdruženy registry a další info potřebné k běhu procesu = stavové informace
• registry čítač instrukcí PC , ukazatel zásobníku SP
univerzální registry
Paměť RAM
Fyzická operační paměť RAM
- Při vypnutí napájení ztratí svůj obsah
- Tvořena paměťovými chipy
obecné registry - SP
offset adresy vrcholu zásobníku (Stack Pointer)
obecné registry - BP
určen pro ukládání offsetu při práci se zásobníkem (Base Pointer)
obecné registry - SI
určen pro uložení offsetu zdroje (Source Index)
obecné registry - DI
určen pro uložení offsetu cíle (Destination Index)
Segmentové registry – CS, DS, ES, FS, GS, SS.
CS – Code Segment. Segment kódu programu. Nelze přímo číst ani do něj zapisovat.
DS – Data Segment – Segment dat programu.
ES – Extra segment
FS – Volné použití
GS – Volné použití
SS – Segment zásobníku.
Speciální registry – IP a FLAG
IP – Instruction Pointer. Ukazuje offset právě vykonávané instrukce. Přímo nelze měnit.
FLAGS – registr příznaků. Tento registr není interpretován jako jedno číslo, ale jeho jednotlivé bity mají smysl příznaků
◦ IF .. interrupt flag (přerušení zakázáno povoleno)
◦ ZF .. zero flag (je li výsledek operace 0)
Vytvoření nového procesu (funkce)
fork() v UNIXu, CreateProcess() ve Windows
Ukončení procesu (funkce)
◦ exit() v UNIXu, ExitProcess() ve Windows
Čekání na dokončení potomka (funkce)
◦ wait(), waitpid() v UNIXu
◦ WaitForSingleObject() ve Windows
Další služby - procesy
Alokace a uvolnění paměti procesu
Komunikace mezi procesy (IPC)
Identifikace ve víceuživatelských systémech
- identifikátor uživatele (UID)
- skupina uživatele (GID)
- proces běží s UID toho, kdo ho spustil (jsou i výjimky)
- v UNIXu UID , GID celá čísla
–> Problém uvíznutí procesu
fork
systémové volání pro vytvoření procesu
Vytvoří identickou kopii (klon) původního procesu
Nový proces vykonává stejný kód
Nový proces má jiný PID
Návratová hodnota fork:
- rodič hodnota větší než nula (PID potomka)
- potomek: nula (signalizuje, že je potomek)
- záporná hodnota, pokud nemůže proces vytvořit
Jak za řídit, aby proces vykonával jiný program?
- Systémové volání execve
- Specifikujeme, jaký program má náš proces začít vykonávat
- Vykonává jiný kód
- PID a vazba na rodiče zůstane
Sekvenční x náhodný přístup
Sekvenční přístup ◦ soubor musíme číst od začátku do konce ◦ nemůžeme přeskakovat, vracet se ◦ příkladem např. magnetická páska ◦ (lze rewind a znovu číst od začátku)
Náhodný přístup
◦ nejběžnější
◦ můžeme přeskakovat, vracet se libovolně
◦ potřebujeme operaci lseek
Pseudoparalelní běh
Pseudoparalelní běh v jednu chvíli aktivní pouze jeden proces (při 1 CPU)
Po určité době pozastaven a spuštěn další
Po určité době všechny procesy vykonají část své činnosti
Stavy procesu
- běžící - využívá CPU
- připravený - pozastaven, aby mohl jiný proces pokračovat, čeká na CPU
- blokovaný - neschopný běhu, dokud nenastane externí událost (čeká na zdroj nebo zprávu)
- nový - právě vytvořený proces
- ukončený
- zombie - proces dokončí svůj kód, pořád má záznam v tabulce procesů, čekání, dokud rodič nepřečte exit status voláním wait
- sirotek - jeho kód stále běží, ale skončil rodičovský proces, adoptován procesem init
Přechody stavů procesu
- plánovač vybere nějaký proces
- proces je pozastaven, plánovač vybere jiný proces (např. vypršelo časové kvantum)
- proces se zablokuje, protože čeká na událost
- nastala očekávaná událost
Tabulka procesů
- OS si musí vést evidenci, jaké procesy v systému v danou chvíli existují.
- Tato informace je vedena v tabulce procesů
- Každý proces v ní má záznam, a tento záznam se nazývá process control block (PCB)
- Na základě informací zde obsažených se plánovač umí rozhodnout, který proces dále poběží a bude schopen tento proces spustit ze stavu, v kterém byl naposledy přerušen.
PCB
info o procesu v tabulce procesů
PCB obsahuje všechny informace potřebné pro opětovné spuštění přerušeného procesu
Pole správy procesů , správy paměti , správy souborů
Ukončení procesu
- proces úspěšně vykoná kód programu
- skončí rodičovský proces
- proces překročí limit nějakého zdroje
Přepnutí kontextu - průběh
◦ Uloží obsah registrů do zásobníku
◦ Plánovač nastaví proces, který opouští CPU jako ready
◦ Vybere nový proces pro spuštění
◦ Nastaví mapu paměti nového procesu
◦ Nastaví zásobník, načte z něj obsah registrů
◦ Provede návrat z přerušení IRET (do PC adresa ze zásobníku, hodnota registru FLAGS, přepne do uživatelského režimu)
Rychlost CPU vs. paměť
CPU
◦ Rychlost počet instrukcí za sekundu
◦ Obvykle nejrychlejší komponenta v systému
◦ Skutečný počet instrukcí závisí na rychlosti, jak lze instrukce a data přenášet z a do hlavní paměti
Hlavní paměť
◦ Rychlost v pamětových cyklech (čtení, zápis)
◦ O řád pomalejší než CPU
◦ Proto důvod používat cache paměť
MMU
více procesů v paměti a každý má paměť pro sebe, program pracuje s virtuálními adresami a MMU je převede na fyzické adresy
Procesy a vlákna
každý proces svůj vlastní PID, PGID, UID, GID, adresový prostor a místo, kde leží (bod běhu), instrukce programu, registry, zásobník, haldu, popisovače souborů, signal actions, shared libraries, IPC, aktuální prioritu, výši priority (nice), celkovou velikost, velikost použité fyzické paměti, stav, %CPU; PID atd. uložený v PCB (včetně kontextu procesu) v tabulce procesů, ta je v RAM a je to datová struktura jádra OS
Vlákna
v procesu sdílejí adresní prostor, otevřené soubory; každé vlákno má svůj zásobník, čítač instrukcí, obsah registrů, zásobník, lokální proměnné, množinu blokovaných signálů, plánovací vlastnosti
Mechanismus pro obecný popis paralelních aktivit - Fork, join, quit
fork X; - Spuštění nového vlákna od příkazu označeného návěštím X; nové vlákno poběží paralelně s původním
quit; - Ukončí vlákno
join t, Y; - Atomicky (nedělitelně) provede:
t = t - 1;
if (t == 0) then goto Y;
Základní funkce libpthread
t = pthread_create(..f..) - Podprogram f se spustí jako vlákno, vrací id vlákna
pthread_exit() - Odpovídá quit, může předat návratovou hodnotu
x = pthread_join(t) - Čeká na dokončení vlákna t, vrací hodnotu předanou voláním exit
pthread_detach(t) - Na dokončení vlákna se nebude čekat joinem
pthread_cancel(t) - Zruší jiné vlákno uvnitř stejného procesu
Plánování procesů - dle stupně multiprogramování
stupeň multiprogramování = počet procesů v paměti
- nepreemptivní - proces skončí, nebo běžící -> blokovaný;
- preemptivní - navíc přechod běžící -> připravený (uplynulo časové kvantum), k odstavení procesu může dojít v nevhodný čas
Plánování procesů - dle frekvence spouštění plánovače
Krátkodobé: CPU scheduling - kterému z připravených procesů bude přidělen procesor - je vždy ve více úlohovém Střednědobé: swap out - odsun procesu z vnitřní paměti na disk Dlouhodobé: job scheduling - výběr, která úloha bude spuštěna - dávkové zpracování (dostatek zdrojů spusť proces)
Modely vláken
1:1 - vlákna v jádře
M:1 - vlákna jen v user space
M:N - komerční unixy (Solaris)
Vlákna základní funkce
pthread_create - Vytvoří nové vlákno
pthread_join - Čeká na dokončení jiného vlákna
pthread_detach - Vlákno bude v detached stavu, nepůjde na něj čekat pomocí pthread_join
pthread_exit - Naše vlákno končí když doběhne funkce, kterou vykonává, nebo když zavolá pthread_exit
Vlákno má vlastní
Zásobník ( stack pointer)
Registry
Plánovací vlastnosti ( policy, priority)
Množina pending a blokovaných signálů
Data specifická pro vlákno (vlastní proměnné)
Vlákna stejného procesu sdílejí
Adresní prostor
Otevřené soubory
Možnosti ukočení vlákna (5x)
- Vlákno dokončí „proceduru vlákna“ nejčastější
- Vlákno kdykoliv zavolá pthread_exit
- Vlákno je zrušené jiným vláknem pthread_cancel
- Volání execve() nebo exit() týká se celého procesu
- Pokud main() skončí první bez explicitního volání pthread_exit
Časový souběh
dva nebo více procesů či vláken se pokusí
současně přistoupit ke stejným zdrojům a výsledkem může býtchyba (např. špatná hodnota sdílené proměnné)
Zdrojem rozumíme např. sdílené proměnné.
Klasický příklad: dva procesy zvětšují asynchronně sdílenou proměnnou X
Kritická sekce
Kritická sekce je místo v programu, kde je prováděn přístup ke společným datům.
Procesy, vlákna komunikují přes společnou datovou oblast (sdílená paměť procesy, globální proměnné vlákna)
Cílem je zařídit, aby byl v kritické sekci v daný okamžik pouze JEDEN proces (vlákno)
Pravidla pro řešení časového souběhu
- vzájemné vyloučení - uvnitř KS vždy jen 1 proces
- proces mimo KS nesmí blokovat jiné procesy (bránit ve vstupu do KS)
- žádný proces nesmí na vstup do KS čekat nekonečně dlouho
Možnosti řešení časového souběhu
- Zákaz přerušení
- Aktivní čekání
- Zablokování procesu
Aktivní čekání
průběžné testování proměnné ve smyčce, dokud nenabyde očekávanou hodnotu, ale plýtvá časem CPU, tak se používá, jen pokud předpokládáme krátké čekání (spin lock)
Spin lock s instrukcí TSL
instrukce, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (Test and Set Lock)
boolean atomic function TSL (boolean zamceno) {
int pom;
pom = zamceno;
zamceno = true;
return pom;
}
boolean lock;
void spin_lock (var m: lock) {
while TSL(m) do ;
{
čeká dokud je m true
}
}
void spin_unlock (var m: lock) {
m = false;
}
Algoritmus - Peterson
Algoritmus pro řešení kritické sekce s aktivním čekáním
Problém inverze priorit
- L je v kritické sekci
- H se stane připravený (např. dostal vstup)
- H začne aktivní čekání
- L ale nebude už nikdy naplánován , nemá šanci dokončit KS
- H bude aktivně čekat do nekonečna
Semafor
tvořen celočíselnou proměnnou „s“ (obsahující nezáporné celé číslo, hodnotu lze přiřadit pouze při deklaraci, 0 = sem. je zablokovaný, nenula = kolik procesů může zavolat P(), aniž by se blokly) a frontou procesů, které na něj čekají; nad semafory pouze operace P(s) a V(s) - nedělitelné operace
P - blokuje, snižuje;; V - odblokuje, zvyšuje;;
Producent konzument implementace
Zkusit si
Vzájemné vyloučení vs. Serializace
Vzájemné vyloučení: události A a B se nesmí stát ve stejný čas
- ošetření kritické sekce, semaphore inicializován na 1
Serializace událost A se musí stát před událostí B
- B na začátku blokujeme operací P() semaforu s počáteční hodnotou 0
Mutex
(binární semafor (ale jiná implementace), vzájemné vyloučení), spin_lock bez aktivního čekání; implementace pomocí yield - dobrovolně se vzdává CPU, šetří čas
Mutex s koncepcí vlastnictví:
Odemknout mutex může jen stejné vlákno proces, který jej zamkl
Mutex x binární semafor
• binární semafory
- Vzájemné vyloučení i synchronizace (A před B)
• mutexy
- paměťové zámky zamykací mechanismus
- pouze pro vzájemné vyloučení
- při vhodné implementaci efektivnější
Reentrantní mutex
Stejné vlákno může získat několikrát zámek
Stejně tolikrát jej musí zas odemknout, aby mohlo mutex získat jiné vlákno
Futex
Userspace mutex v Linuxu
V kernel space : wait queue (fronta
V user space : integer (celé číslo, zámek)
Monitor
v jednu chvíli aktivní pouze jeden proces
výhody - automaticky řeší vzájemné vyloučení, větší odolnost proti chybám programátora;
tvořen podmínkami (definovány a použity pouze uvnitř bloku, nejsou proměnné v klasickém smyslu, neobsahují hodnotu, představují frontu procesů, které na danou podmínku čekají)
c.wait monitor
volající bude pozastaven nad podmínkou c, pokud je některý proces připraven vstoupit do monitoru, bude mu to dovoleno;
c.signal monitor
pokud existují procesy pozastavené nad podmínkou c, reaktivuje jeden z pozastavených procesů a bude mu dovoleno pokračovat v běhu uvnitř monitoru,, pokud nad podmínkou nespí žádný proces, nedělá nic;;
Problém s operací signal
Pokud by signál pouze vzbudil proces, běžely by v monitoru dva
◦ Vzbuzený proces
◦ A proces co zavolal signal
ROZPOR s definicí monitoru
◦ V monitoru může být v jednu chvíli aktivní pouze jeden proces
Řešení reakce na signal - Hoare
◦ proces volající c.signal se pozastaví
◦ Vzbudí se až poté co předchozí rektivovaný proces opustí monitor nebo se pozastaví
Řešení reakce na signal - Hansen
◦ Signal smí být uveden pouze jako poslední příkaz v monitoru
◦ Po volání signal musí proces opustit monitor
Řešení reakce na signal - Java
Čekající může běžet až poté, co proces (vlákno) volající signál opustí monitor.
Řešení producent/konzument pomocí monitoru
Zkus si to
Implementace monitorů pomocí semaforů
Zkus si to
Meziprocesová komunikace
přes sdílenou paměť, zasíláním zpráv, signály (jen v Linuxu, speciální zpráva zaslaná jádrem OS procesu, asynchronní);;
Události generující signály
◦ Stisk kláves ( CTLR+C generuje SIGINT)
◦ Příkaz kill (1), systémové volání kill (2)
◦ Mohou je generovat uživatelské programy přes systémové volání
Reakce na signály
◦ Standardní zpracování
- ukončí proces (Term), zastaví (Stop), pustí zastavený (Cont), ukončí a provede dump (Core)
◦ Vlastní zpracování naší funkcí
◦ Ignorování signálu (ale některé nelze , např. SIGKILL, SIGSTOP)
Datové roury
- jednosměrná komunikace mezi 2 procesy
- data zapisována do roury jedním procesem lze dalším hned číst
- data čtena přesně v tom pořadí, v jakém byla zapsána
Problém sdílené paměti
vyžaduje umístění objektu ve sdílené paměti
- někdy nevhodné (bezpečnost - globální data přístupná kterémukoliv procesu bez ohledu na semafor)
- někdy nemožné (procesy běží na různých strojích, komunikují spolu po síti)
Řešení = předávaní zpráv
Předávání zpráv
send(adresát, zpráva) - neblokující,
receive(odesílatel, zpráva) - blokující;
blokující send - čeká na převzetí zprávy příjemcem, neblokující send - vrací se ihned po odeslání zprávy
blokující receive - není-li ve frontě žádná zpráva, zablokuje se
neblokující receive - není-li zpráva, vrací chybu;
Adresování
skupinové (multicast) - zprávu pošleme skupině procesů, obdrží ji každý proces;
všesměrové (broadcast) - zprávu posíláme všem procesům, více nespecifikovaným příjemcům
Producent - konzument pomocí zpráv
Zkus si to
Délka fronty zpráv
nulová - žádná zpráva nemůže čekat, odesílatel se zablokuje (rendezvous);
omezená - blokování při dosažení kapacity
neomezená - odesílatel se nikdy nezablokuje
Doručování zpráv
v pořadí FIFO, neztrácejí se
Určení adresáta
procesy nejsou trvalé entity, proto neadresujeme proces, ale frontu zpráv (nepřímá komunikace)
Fronta zpráv
mailbox - více odesílatelů a příjemců
port - omezená forma mailboxu, zprávy může vybírat pouze 1 příjemce
Ztráta zprávy
řeší potvrzení o přijetí; pokud vysílač nedostane potvrzení do nějakého časového okamžiku, zprávu pošle znovu
ztráta potvrzení - zpráva dojde ok, ztratí se potvrzení - řeší číslování zpráv, duplicitní zprávy se ignorují
Problém autentizace
zprávy možno šifrovat, klíč známý pouze autorizovaným uživatelům (procesům), zašifrovaná zpráva obsahuje redundanci (umožní detekovat změnu zašifrované zprávy)
Lokální komunikace
- na stejném stroji, snížení režie;
dvojí kopírování (z procesu odesílatele do fronty v jádře, z jádra do procesu příjemce);
rendezvous - eliminuje frontu zpráv, zpráva se zkopíruje z odesílatele přímo do příjemce
virtuální paměť - paměť obsahující zprávu je přemapována (z procesu odesílatele do procesu příjemce), zpráva se nekopíruje
RPC
dovolit procesům (klientům) volat procedury umístěné v jiném procesu (serveru)
variantou RPC je i volání vzdálených metod Remote Method Invocation , RMI) v OOP, např. Javě
snaha aby co nejvíce připomínalo lokální volání
Spojka klienta, serveru
klientský program sestaven s knihovní funkcí,
tzv. spojka klienta ( client stub)
reprezentuje vzdálenou proceduru v adresním prostoru klienta
stejné jméno, počet a typ argumentů jako vzdálená procedura
program serveru sestaven se spojkou serveru (server stub
spojky zakrývají, že volání není lokální
Kroky komunikace klient - server
- klient zavolá spojku klienta (reprezentující vzdálenou proceduru)
- spojková procedura argumenty zabalí do zprávy a pošle ji serveru
- spojka serveru zprávu přijme, vezme argumenty a zavolá proceduru
- procedura se vrátí, návratovou hodnotu pošle spojka serveru zpět klientovi
- spojka klienta přijme zprávu obsahující návratovou hodnotu a předá ji volajícímu;;
RPC více procedur
spojka klienta ve zprávě předá kromě parametrů i číslo požadované procedury
Problémy RPC
- Parametry předávané odkazem
◦ Klient a server různé adresní prostory
◦ Odeslání ukazatele nemá smysl
◦ Pro jednoduchý datový typ, záznam, pole lze řešit- Spojka klienta pošle odkazovaná data spojce serveru
- Spojka serveru vytvoří nový odkaz na data atd.
- Modifikovaná data pošle zpátky na klienta
- Spojka klienta přepíše původní data
- Globální proměnné
◦ Použití není možné x lokálních procedur
Bariéry
synchronizační mechanismus pro skupiny procesů, skládá se z fází (žádný proces nesmí do následující fáze, dokud všechny procesy nedokončily fázi předchozí), na konci každé fáze synchronizace na bariéře (volajícího pozastaví, dokud všechny procesy také nezavolají barrier), všechny procesy opustí bariéru současně
Problém večeřících filozofů
5 filozofů sedí kolem kulatého stolu
Každý filozof má před sebou talíř se špagetami
Mezi každými dvěma talíři je vidlička
Filozof potřebuje dvě vidličky, aby mohl jíst
Čtenáři-písaři
• modeluje přístup do databáze • rezervační systém (místenky, letenky) • množina procesů, které chtějí přistupovat - souběžné čtení lze - výhradní zápis (žádný další čtenář ani
Řešení čtenáři-písaři
Zkus si to
Zámky v OS a DB
přístup procesu k souboru nebo záznamu databázi;
výhradní zámek (pro zápis) - nikdo další nesmí přistupovat
sdílený zámek (pro čtení) - mohou o něj žádat další procesy;
granularita zamykání - celý soubor vs. část souboru, tabulka vs. řádka v tabulce;;
Plánovač
určí, který proces (vlákno) by měl běžet nyní
Kde leží tabulka procesů?
v paměti RAM, je to datová struktura jádra OS
kde leží informace o PIDu procesu?
v tabulce procesů –> v PCB (řádce tohoto procesu)
jak procesor v í, kterou instrukci procesu (vlákna) má
vykonávat?
podle program counteru (PC, typicky CS:EIP), ukazuje na oblast v paměti, kde leží vykonávaná instrukce
obsah CS:EIP, stejně jako dalších registrů je součástí PCB
Dispatcher
provede vlastní přepnutí z aktuálního běžícího procesu na nově vybraný proces
CPU, IO burst
CPU burst - vykonávání kódu,
I/O burst - čekání,
CPU-vázaný proces - hodně času tráví výpočtem,
I/O-vázaný proces - hodně času tráví čekáním na I/O
Plánování
nepreemptivní - každý proces dokončí svůj CPU burst;
preemptivní - (u interaktivních systémů) proces lze přerušit kdykoliv během CPU burstu a naplánovat jiný, vyžaduje speciální hardware (timer - generuje přerušení),, nejen u uživatelských procesů, ale i u jádra
Cíle plánování - společné
Spravedlivost (Fairness)
• Srovnatelné procesy srovnatelně obsloužené
Vynucení politiky (Policy enforncement)
• Bude vyžadováno dodržení stanovených pravidel
Balance (Balabce)
• Snaha, aby všechny části systému (CPU, RAM, periferie) byly vytížené
Nízká režie plánování
Cíle plánování - dávkové systémy
Propustnost Throughput
•maximalizovat počet jobů za jednotku času (hodinu)
Doba obrátky Turnaround time
•minimalizovat čas mezi přijetím úlohy do systému a jejím dokončením
CPU využití
• snaha mít CPU pořád vytížené
Tři zásadní údaje, které charakterizují plánovač
- rozhodovací mód
- prioritní funkce
- rozhodovací pravidla
Plánovač - Rozhodovací mód
Okamžik, kdy dojde k vyhodnocení priorit a výběru procesu pro běh
1. Nepreemtivní systém • Proces využívá CPU, dokud se jej sám nevzdá (např. I/O) • jednoduchá implementace • vhodné pro dávkové systémy • nevhodné pro interaktivní a RT systémy
- Preemptivní systém
Kdy dojde k vybrání nového procesu pro běh ?
• přijde nový proces (algoritmus SRT u dávkových
• periodicky kvantum (interaktivní systémy)
• jindy priorita připraveného běžícího (RT systémy)
Náklady (režie)
• přepínání procesů, logika plánovače
Plánovač - Prioritní funkce
Určuje prioritu procesu v systému
bere v úvahu čas, jak dlouho proces využíval CPU, aktuální zatížení systému, paměťové požadavky procesu, čas strávený v systému, celkovou dobu provádění úlohy, urgenci;
statická priorita - přiřazena při startu procesu;
dynamická priorita - za běhu, dle chování procesu (dlouho čekal); plánovač snižuje dynamickou prioritu běžící procesu při každém tiku časovače
Proč má prioritní funkce 2 složky?
priorita = statická + dynamická
Pokud by chyběla statická: nemohl by uživatel např. při startu označit proces jako důležitější než jiný
Pokud by chyběla dynamická: proces by mohl vyhladovět, mohl by být neustále předbíhán v plánování jinými procesy s lepší prioritou
Co všechno může vzít v úvahu prioritní funkce?
- čas, jak dlouho proces využíval CPU
- aktuální zatížení systému
- paměťové požadavky procesu
- čas, který strávil v systému
- celková doba provádění úlohy (limit)
- urgence (RT systémy)
Plánovač - Rozhodovací pravidlo
- Jak rozhodnout při stejné prioritě
• pokud malá pravděpodobnost stejné priority
-> náhodný výběr
velká pravděpodobnost stejné priority
- > cyklické přidělování kvanta
- > chronologický výběr (FIFO)
Cíle plánovacích algoritmů
Každý algoritmus nutně upřednostňuje nějakou
třídu úloh na úkor ostatních.
• dávkové systémy
- dlouhý čas na CPU, omezí se přepínání úloh
• interaktivní systémy
- interakci s uživatelem, tj. I /O úlohy
•systémy reálného času
-> dodržení deadlines
Algoritmy plánování úloh v dávkových systémech (4x)
FCFS ( First Come First Served) SJF ( Shortest Job First) SRT ( Shortest Remaining Time) -> jediný z nich je preemptivní Multilevel Feedback
FCFS
(nepreemptivní FIFO) - nově příchozí úloha na konec fronty připravených a běží, dokud neskončí (když neprovádí I/O, jinak do stavu blokovaný,, až provede I/O, jde na konec fronty připravených);
SJF
nepreemptivní, nejkratší úloha jako první, ale musíme dopředu přibližně znát dobu trvání úloh
SRT
preemptivní, plánovač vždy vybere úlohu, jejíž zbývající doba běhu je nejkratší;
MLF
nepreemptivní, N prioritních úrovní, každá úroveň má svou frontu úloh, úloha vstoupí do systému do fronty s nejvyšší prioritou, na každé prioritní úrovni stanoveno max času CPU, který může úloha obdržet,, proces obsluhuje nejvyšší neprázdnou frontu; upřednostňuje I/O vázané
Plánování procesů v interaktivních systémech
potřeba docílit, aby proces neběžel „příliš dlouho”
- možnost obsloužit další procesy - na každého se dostalo
nevíme jak dlouhý bude CPU burst procesu
vestavěný systémový časovač v po čítači
- provádí pravidelně přerušení (tiky časovače, clock ticks
- vyvolá se obslužný p odprogram v jádře
- rozhodnutí , zda proces bude pokračovat, nebo se spust í jiný preemptivní plánování po několika tikách časovače
Round Robin - popis
Algoritmus cyklické obsluhy
každému procesu přiřazeno časové kvantum, po které může běžet,, pokud proces nevyužije celé časové kvantum, nebo se zablokuje před uplynutím kvanta (dobrovolně se vzdá CPU), nebo vyprší časové kvantum (odebrán CPU nedobrovolně, přejde do stavu připravený), naplánuje se další proces
Časové kvantum
nemusí být konstantní;
krátké - snižuje efektivitu (velká režie s přeplánováním),
dlouhé - zhoršuje dobu odpovědi na interaktivní požadavky
Problém s algoritmem cyklické obsluhy
v systému výpočetně vázané i I O v ázané úlohy
výpočetně vázané většinou kvantum spotřebují
I /O vázané pouze malá část kvanta se využije a zablokují se
==> výpočetně vázané získají nespravedlivě vysokou část času CPU
Jedno z možných řešení:
modifikace VRR (Virtual RR)
- procesy po dokončení I/O mají přednost před ostatními
Dynamická priorita v kvantově orientovaných plánovacích algoritmech:
1/f (f = velikost části kvanta, kterou proces naposledy použil), zvýhodní I/O vázané
Spojení cyklického a prioritního plánování
prioritní třídy
- v každé třídě procesy se stejnou prioritou
prioritní plánování mezi třídami
- Bude obsluhována třída s nejvyšší prioritou
cyklická obsluha uvnitř třídy
- V rámci dané třídy se procesy cyklicky střídají
obsluhovány jsou pouze připravené procesy v nejvyšší neprázdné prioritní třídě
Plánovač spravedlivého sdílení
problém:
◦ čas přidělován každému procesu nezávisle
◦ Pokud uživatel má více procesů než jiný uživatel
dostane více času celkově
spravedlivé sdílení
◦ přidělovat čas každému uživateli (či jinak definované skupině procesů) proporcionálně , bez ohledu na to, kolik má procesů
◦ máme li N uživatelů, každý dostane 1/N času
Plánování pomocí loterie
procesy obdrží tickety (losy), plánovač vybere náhodně 1 tiket, vítězný proces obdrží cenu - 1 kvantum času CPU, důležitější procesy - více tiketů, aby se zvýšila šance na výhru; výhody - spolupracující procesy si mohou předávat losy, rozdělení času mezi procesy v určitém poměru
Interaktivní systémy obecně
Základem je round robin
◦ Pojem časové kvantum
Prioritní plánování
◦ Statická a dynamická složka priority
Spojení RR + priority => prioritní třídy
Spravedlivé sdílení
◦ Modifikace plánovače pro spravedlnost vůči uživatelům
Loterie
◦ Experimentální, zajímavé vlastnosti
◦ Nelze použít pro řídící systémy nedeterminismus
Souborové systémy - hlavní požadavky
možnost uložit velké množství dat
potřeba uchovávat strukturovaně = => adresářový strom a soubory
informace zachována i po ukončení procesu
data přístupná více procesům
společné problémy při přístupu k zařízení
alokace prostoru na disku
pojmenování dat
ochrana dat před neoprávněným přístupem
zotavení po havárii (výpadek napájení)
Soubor - definice
soubor je pojmenovaná množina souvisejících informací, uložená
na datovém médiu , se kterou lze pracovat nástroji operačního systému jako s jedním celkem
Souborový systém - definice
Způsob organizace dat ve formě souborů (a adresářů), tak aby k nim bylo možné snadno přistupovat.
Způsob přístupu k souboru
Sekvenční nebo přímý
Sekvenční přístup
procesy mohou číst data pouze v pořadí, v jakém jsou uloženy v souboru
tj. od prvního záznamu (bytu), nemohou přeskakovat
možnost „přetočit pásku“ a číst opět od začátku, rewind
hlavně v prvních OS, kde data na magnetických páskách
přímý přístup
přístup ( random access file)
čtení v libovolném pořadí nebo podle klíče
přímý přístup je nutný např. pro databáze
uživatel např. přeskakování děje filmu
určení začátku čtení
každá operace určuje pozici
OS udržuje pozici čtení / zápisu, novou pozici lze nastavit speciální operací seek
Atributy souboru
ochrana souboru
- kdo je vlastníkem, množina přístupových práv, heslo, …
příznaky
- určují vlastnosti souboru
- hidden neobjeví se při výpisu
- archive soubor nebyl zálohován
- temporary soubor bude automaticky zrušen
- read only ,
- text/ binary , random access ,
velikost, datum vytvoření, poslední modifikace, poslední přístup
Služby OS pro práci se soubory - základní model dle UNIXu
veškerý I/O prováděn pouze pomocí souborů
- obyčejné soubory, data, spustitelné programy
- zařízení disky, tiskárny
- se všemi typy zacházení pomocí stejných služeb systému
obyčejný soubor = posloupnost bytů
- význam znají pouze programy, které s ním pracují
- interní struktura souboru OS nezajímá
seznam souborů = adresář
- adresář je také soubor
- soubory a adresáře koncepčně umístěny v adresáři
speciální soubory pro přístup k zařízením
- Linux –/ sda , / tty aj.
file descriptor
úspěšné otevření souboru => služba pro otevření souboru vrátí popisovač souboru = malé celé číslo = index to tabulky souborů uvnitř OS
Základní služby pro práci se soubory
fd = open(jmeno, způsob) fd = creat(jméno, práva) - nikoliv create read(fd, buffer, počet_bytů) write(fd, buffer, počet_bytů) lseek(fd, offset, odkud) close(fd)
Paměťově mapované soubory
- možnost mapování souboru do adresního prostoru procesu
- služby systému mmap (), munmap
- mapovat je možné i jen část souboru
- k souboru pak přistupujeme např. přes pointery v C
Adresářová struktura
Jeden oddíl disku obsahuje jeden filesystém
filesystém 2 součásti:
- množina souborů, obsahujících data
- adresářová struktura udržuje informace o všech souborech v daném fs
adresář překládá jméno souboru na informace o souboru (umístění, velikost, typ)
Základní požadavky na adresář (příkazy)
cd, ls, rm, rmdir, mv
Základní služby pro práci s adresáři
chdir (adresář)
=> nastavení pracovního adresáře
getcwd (buffer, počet_znaků)
=> zjištění pracovního adresáře
Práce s adresářovou strukturou
vytváření a rušení adresářů
◦ mkdir (adresář, přístupová_práva)
◦ rmdir (adresář) - musí být prázdný
zrušení souboru
◦ remove ( jméno_souboru)
◦ volá unlink() pro soubory, rmdir () pro adresáře
přejmenování souboru
◦ rename jméno_souboru , nové_jméno
◦ provádí také přesun mezi adresáři
Pevný disk: cluster, sektor
Cluster
◦ nejmenší alokovatelná jednotka pro uložení souboru
◦ Soubor velikosti 1B zabere celý cluster
◦ Např. FAT32 32bitová adresa
(z nich používá jen 28bitů pro čísla clusterů, 4 bity for future use)
◦ Skládá se z 1 nebo více sektorů
Sektor
◦ Základní adresovatelná fyzická jednotka disku
◦ 512B, 1KB, 4KB, …
Příklady
◦ Disk s 512B cluster 512B sektor
◦ Disk se 4KB clusterem 8 sektorů po 512B (nebo 1 sektor 4KB)
Pevný disk (rotační) - rozdělení
- Pevný disk je složen z jedné nebo více ploten , na kterých je magnetická vrstva.
- Záznam je prováděný do jednotlivých stop soustředné kružnice.
- Každá plotna má nad sebou a pod sebou čtecí/záznamovou hlavu
- U více ploten všechny hlavy jsou nastaveny na stejnou stopu (tzv. cylindr plocha procházející všemi plotnami)
- Stopy se dělí na sektory
- Dříve stejný počet sektorů na vnitřní i vnější stopě, později proměnlivý, aby byla stejná hustota záznamu.
CHS a LBA adresování
CHS ( Cylinder Head Sector , Stopa Hlava Sektor)
• Starší způsob adresování sektorů
• Uvedeme stopu, hlavu disku, číslo sektoru na stopě
• Omezení velikosti disku, BIOS uměl jen 1024 cylindrů, 256 hlav, 64 sektorů
• Triky - elektronika disku přemapovala počet válců na vyšší počet hlav, abychom mohli adresovat větší disky
LBA ( Logical Block Addressing ) adresování
• Nahradilo původní CHS
• Čísluje sektory na disku lineárně a není třeba znát geometrii disku
Implementace fs - vrstvy
- Logický (virtuální) souborový systém
- Volán aplikacemi - Modul organizace souborů
- Konkrétní souborový systém (např. ext3) - Ovladače zařízení
- Pracuje s daným zařízením
- Přečte /zapíše logický blok
virtuální fs
Volán aplikacemi
Rozhraní s moduly organizace souborů
Obsahuje kód společný pro všechny typy fs
Převádí jméno souboru na informaci o souboru
Udržuje informaci o otevřeném souboru
Pro čtení / zápis (režim)
Pozice v souboru
Ochrana a bezpečnost (ověřování přístupových práv)
modul organizace souborů
Implementuje konkrétní souborový systém
ext3, xfs , ntfs , fat,
Čte/zapisuje datové bloky souboru
Bloky souboru číslovány 0 až N-1 (nebo a1, a2 , …, aN)
Převod čísla bloku souboru na diskovou adresu
Volání ovladače pro čtení či zápis bloku
Správa volného prostoru + alokace volných bloků souborům
Údržba datových struktur filesystému
ovladače zařízení
Zařízení: SATA disk, SCSI disk, DVD mechanika
Interpretují požadavky: přečti logický blok 6456 ze zařízení 3
Jak VFS pracuje s konkrétním filesystémem
Nový filesystém , který chceme používat se nejprve v systému zaregistruje
Díky registrací VFS ví, jak zavolat jeho metody open, read , write pro konkrétní soubor
Při požadavku na soubor VFS napřed zjistí, na kterém filesystému leží
Kontinuální alokace
Soubor jako kontinuální posloupnost diskových bloků
Implementace:
Potřebujeme znát číslo prvního bloku
Znát celkový počet bloků souboru (např. v adresáři)
Problém = dynamičnost OS
soubory vznikají, zanikají, mění velikost
Seznam diskových bloků (typ alokace)
Svázat diskové bloky do seznamu nebude vnější fragmentace
Na začátku diskového bloku je uložen odkaz na další blok souboru, zbytek bloku obsahuje data souboru
Pro přístup k souboru stačí znát pouze číslo prvního bloku souboru (může být součástí záznamu v adresáři) a velikost (kolik využito z posledního bloku)
Sekvenční čtení bez potíží
Přímý přístup simulován sekvenčním, pomalé
(musí dojít ke správnému bloku)
Velikost dat v bloku není mocnina dvou
- Část bloku je zabraná odkazem na další blok
- Někdy může být nevýhodou ( kešování , optimalizace)
FAT
Přesunutí odkazů do samostatné tabulky FAT
FAT ( File Allocation Table)
- Každému diskovému bloku odpovídá jedna položka ve FAT tabulce
- Položka FAT obsahuje číslo dalšího bloku souboru (je zároveň odkazem na další položku FAT
- Řetězec odkazů je ukončen speciální značkou, která není platným číslem bloku (poslední blok souboru)
- Volný blok značí, že je odpovídající datový blok volný
- Bad block značí, že je odpovídající datový blok poškozený
FAT typy defragmentace
Úplná = obsazené bloky souborů půjdou na disku za sebou, poté následuje volné místo
Částečná = upraví se jen tak, že napřed je obsazený prostor soubory a za ním volné bloky
Příklady filesystémů
FAT NTFS Ext2 Ext3 Ext4
Další používané filesystémy:
XFS, JFS, btrfs , ZFS
NTFS vlastnosti
nativní souborový systém Windows od NT výše
žurnálování
= zápisy na disk se zapisují do žurnálu, pokud uprostřed zápisu systém havaruje, je možné dle stavu žurnálu zápis dokončit nebo anulovat => konzistentní stav
access control list
= přidělování práv k souborům (na rozdíl od FAT)
komprese
= na úrovni fs lze soubor nastavit jako komprimovaný
šifrování
= EFS ( encrypting file system ), transparentní otevřu ahoj.txt, nestarám se, zda je šifrovaný
diskové kvóty
= max. velikost pro uživatele na daném oddíle dle reálné velikosti (ne komprimované)
pevné a symbolické linky
NTFS struktura
64bitové adresy c lusterů .. cca 16EB
clustery číslovány od začátku partition logická čísla clusterů
systém jako obří databáze = záznam v ní odpovídá souboru
základ 11 systémových souborů metadata vzniknou hned při formátování svazku
Logfile = žurnálování
$MFT (Master File Table) !nejdůležitější! =
záznamy o všech souborech, adresářích, metadatech
hned za boot sektorem, za ním se udržuje zóna volného místa
NTFS způsob uložení dat
kódování délkou běhu
od pozice 100 máme např. uloženo:
A1, A2, A3, B1, B2, A4, A5, C1, …
soubor A bude popsaný fragmenty
fragment
- index
- počet bloků daného fragmentu
v našem příkladě pro soubor A dva fragmenty:
- I. 100, 3 (od indexu 100 patří tři bloky souboru)
- II. 105, 2 (od indexu 105 patří dva bloky souboru
V ideálním případě 1 soubor = 1 fragment
(výhody kontinuální alokace)
Defragmentovat můžeme jak celou partition , tak jen vybrané soubory (přes utility v sysinternals)
Systémy využívající i-uzlů
Každý soubor a tedy i adresář je reprezentovaný i uzlem
i-uzel = datová struktura - Metadata popisující vlastníka souboru, přístupová práva, velikost souboru (pozor, není zde název souboru) Umístění bloků souboru na disku Přímé odkazy a nepřímé 1. 2. 3. úrovně Abychom věděli, jaké bloky přistupovat
Adresář systému s i-uzly
Soubor obsahující dvojice
název_souboru , číslo_odpovídajícího_i uzlu
2 základní uspořádání adresáře
- Adresář obsahuje jméno souboru, atributy, diskovou adresu souboru (např. adresa 1. bloku
(používá např. FAT) - Adresář obsahuje pouze jméno + odkaz na jinou datovou strukturu obsahující další informace, jako je i uzel
(používá systém s i uzly)
Hard link
Soubor ve více podadresářích nebo pod více jmény
Hard links (pevné odkazy)
◦ Každý soubor má datovou strukturu, která ho popisuje (i uzel), můžeme vytvořit v adresářích více odkazů na stejný soubor
◦ Všechny odkazy (jména) jsou rovnocenné
◦ V popisu souboru (i uzlu) musí být počet odkazů
◦ Soubor zanikne při zrušení posledního odkazu
Symbolický link
Symbolický link
◦ Nový typ souboru, obsahuje jméno odkazovaného souboru
◦ OS místo symbolického odkazu otevře odkazovaný soubor
◦ Obecnější může obsahovat cokoliv
◦ Větší režie
Kvóty
Maximální počet bloků obsazených soubory uživatele
Ve víceuživatelských OS, na serverech
Hard kvóta
◦ Pevná mez, uživatel ji nepřekročí
Soft kvóta
◦ Po překročení uživatel dostane varování
◦ Grace period po zadanou dobu může překročit soft kvótu, po uplynutí času už více neuloží
Jak funguje žurnál
- Zapíši do žurnálu
- Když je žurnál kompletní, zapíšeme značku ZURNAL_KOMPLETNI
- Začneme zapisovat datové bloky
- Je-li hotovo, smažeme žurnál
Žurnál = ošetření výpadku
Dojde-li k výpadku elektřiny- > nebyl korektně odmontovaný oddíl se souborovým systémem
Podívá se do žurnálu:
a) Je prázdný
- > není třeba nic dělat
b) Je tam n ějaký zápis, ale není značka ZURNAL_KOMPLETNI
- -> jen smažeme žurnál
c) V žurnálu je zápis včetně značky ZURNAL_KOMPLETNI
- -> přepíšeme obsah žurnálu do datových bloků
ACL x capability list
ACL - s objektem je sdružen seznam subjektů a jejich
přístupových práv
Capability list - se subjektem je sdružen seznam objektů a přístupových práv k nim
ACL
Sdružování subjektů do tříd nebo do skupin
Skupiny mohou být uvedeny na místě subjektu v ACL
viz příklad
Mechanismus capability lists (C seznamy)
S každým subjektem (procesem) sdružen seznam objektů, kterým může přistupovat a jakým způsobem (tj. přístupová práva)
Seznam se nazývá capability list (C list)
Jednotlivé položky capabilities
Typy záloh
normální
- zálohuje, označí soubory jako “ zazálohované „ (atribut archive shodí)
copy
- zálohuje, ale neoznačí jako “ zazálohované „ (nemanipuluje s atributem s archive)
- nenaruší používané schéma zálohování
incremental (přírůstková)
- zálohuje pouze vybrané soubory, tj. pokud nebyly “ zazálohované “ nebo byli změněny a označí je jako “ zazálohované”
diferential (rozdílová)
- viz předchozí, ale neoznačuje jako “ zazálohované „ (nemanipuluje s atrib . a rchive)
- změny, které proběhly od plné zálohy
- diferenciální zálohy nejsou na sobě závislé
daily
- zálohuje soubory změněné dnes, ale neoznačuje je jako “ zazálohované”
Co se děje při spuštění PC?
- Pustíme proud do počítače
- Power on self test
- test operační paměti, grafické karty, procesoru
- test pevných disků, dalších ATA/SATA/USB zařízení - spustí z ROM paměti BIOSu bootstrap loader
- pustí se zavaděč (např. GRUB2 , Windows zavaděč …)
- zavaděč nahraje jádro do paměti a spustí
ho - první proces init
- spustí program getty na virtuálních terminálech
- spustí se login
BIOS vs. UEFI
Limitace BIOSu
• Je už léta, sice se vyvíjel (např. ACPI a podpora sleep ), ale má řadu omezení
• 16bit kód, 1MB paměti
• Pomalá inicializace více HW zařízení souběžně
UEFI • Nová zařízení podporují UEFI • Používá GPT rozdělení disku místo MBR • Běží v 32/64bit režimu • Podporuje Secure Boot kontrola, zda škodlivý kód nenarušil proces bootování OS
Instrukce CAS - Filozofie
- Compare and Swap
- Jiná filozofie místo zamykání spoléháme, že nám pod rukama hodnotu proměnné nikdo nezmění
- S předpokládanou hodnotou provedeme výpočet
- Pokud nám risk vyšel a předpokládaná hodnota se nezměnila, můžeme dosadit vypočtenou hodnotu
- Pokud nevyšel, musíme výpočet opakovat pro novou předpokládanou hodnotu
- Není deterministické
Linux - vývoj plánovače
jádro 2.4
- O (n) pl ánovač
- Globální runque (fronta úloha může být na libovolném CPU (dobré pro vybalancování využití CPU, ale ne pro cache
jádro 2.6 nižší verze
- O (1) pl ánovač
- pole 5 integerů bitmapa ve které frontě je úloha k běhu
- Čas najít úlohu nezávisí na počtu úloh ale na počtu priorit (140)
- Runque pro každé CPU
jádro 2.6.23 a výše
- CFS plánovač jiný přístup, nejsou pole úloh atd.
CFS
red black tree místo front - klíč spent processor time vruntime kolik času na CPU již spotřeboval proces - účtovací čas v nanosekundách rovnoměrné rozdělení času procesům žádný idle procesor, pokud je co dělat - Na každém CPU migration thread - Přesunout task z jednoho CPU na jiné - Periodicky nebo když je potřeba
Vruntime v CFS
Vruntime říká, jak moc si úloha zaslouží běžet, oproti
ostatním úlohám na stejném procesoru.
Bere v úvahu celou řadu věcí prioritu procesu, kolik času už proces na CPU strávil atd.
Nižší číslo vruntime zasloužil by si více běžet
Organizováno ve stromu, vybere se vždy nejlevější prvek, tedy s nejnižší hodnotou vruntime
CFS - plánovací politiky
SCHED_NORMAL - tradiční SCHED_OTHER - pro běžné úlohy (tasky) SCHED_BATCH - preempce po delším čase, tj. dávkové úlohy - lepší využití cache x interaktivita SCHED_IDLE - ještě slabší než nice 19, ale není idle time scheduler vyhne se problémům s inverzí priority
Afinita
určení jader CPU, na kterých může proces běžet
hard afinity - seznam jader
soft afinity - vlákno přednostně plánováno na procesor, kde běželo naposledy
Přiřazení procesů procesorům - možnosti (2x)
◦ Permanentní přiřazení
- Menší režie , některá CPU mohou zahálet
- Afinita procesu k procesoru, kde běžel naposledy
- Někdy procesoru přiřazen jediný proces RT procesy
◦ Společná fronta připravených procesů
- Plánovány na libovolný procesor
- Častější
Charakteristika RT systémů
◦ RT procesy řídí nebo reagují na události ve vnějším světě
◦ Správnost závisí nejen na výsledku, ale i na čase, ve kterém je výsledek vyprodukován
◦ S každou podúlohou sdružit deadline čas kdy musí být spuštěna nebo dokončena
◦ Hard RT = času musí být dosaženo
◦ Soft RT = dosažení deadline je žádoucí
Vlákna plánována OS
◦ Stejné mechanismy a algoritmy jako pro plánování procesů
◦ Často plánována bez ohledu, kterému procesu patří
(proces 10 vláken, každé obdrží časové kvantum)
◦ Používá Linux, Windows
Vlákna plánována uvnitř procesu
◦ Běží v rámci času, který je přidělen procesu
◦ Přepínání mezi vlákny systémová knihovna
◦ Pokud OS neposkytuje procesu pravidelné “p řerušení“, tak pouze nepreemtivní plánování
◦ Obvykle algoritmus RR nebo prioritní plánování
◦ Menší režie oproti kernel level threads, menší možnosti
Trace tape
monitorujeme běh reálného systému, zaznamenáváme posloupnost událostí Tento záznam použijeme pro řízení simulace Lze využít pro porovnávání algoritmů Nutno uložit velké množství dat
Zdroje (preempce)
přeplánovatelné (preemtable)
◦ lze je odebrat procesu bez škodlivých efektů
nepřeplánovatelné (nonpremeptable)
◦ proces zhavaruje, pokud jsou mu odebrány
Zdroje (využitelnost)
Sériově využitelné zdroje
◦ Proces zdroj alokuje, používá, uvolní
Konzumovatelné zdroje
◦ Např. zprávy, které produkuje jiný proces
◦ Viz producent konzument
Práce se zdrojem
Žádost (request)
◦ Uspokojena bezprostředně nebo proces čeká
◦ Systémové volání
Použití (use)
◦ Např. tisk na tiskárně
Uvolnění (release)
◦ Proces uvolní zdroj
◦ Systémové volání
Uvíznutí - definice
V množině procesů nastalo uvíznutí, jestliže každý proces množiny čeká na událost, kterou může způsobit jiný proces množiny.
Podmínky vzniku uvíznutí
musí být splněny všechny 4 podmínky:
- vzájemné vyloučení - každý zdroj je buď dostupný, nebo přiřazen právě 1 procesu (spooling - soutěžení o tiskárnu);
- hold and wait - proces držící přiřazené zdroje může požadovat další;
- nemožnost odejmutí - přiřazené zdroje nemohou být procesu násilně odejmuty (musí je sám uvolnit);
- cyklické čekání - cyklický řetězec procesů, kde každý čeká na zdroj držený dalším členem;
Uvíznutí - graf
cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí; pokud by procesy žádaly o zdroje ve stejném pořadí, uvíznutí nenastane
Vypořádání se s uvíznutím
- ignorace - předstíráme, že problém neexistuje (pštrosí algoritmus), vysoká cena za eliminaci uvíznutí; u uživatelských procesů uvíznutí neřešíme, ale snažíme se, aby k uvíznutí nedošlo v jádře OS;
- detekce a zotavení - systém se nesnaží zabránit vzniku uvíznutí, jen ho detekuje a pokud nastane, provede akci pro zotavení; zotavení pomocí preempce - vlastníkovi dočasně odebrat zdroj; zotavení pomocí zrušení změn (checkpointing) - zápis stavu procesů do souboru, aby proces mohl být v případě potřeby vrácen do uloženého stavu; zrušení procesu - nejhorší způsob;
- dynamické zabránění - většinou procesy žádají o zdroje po jednom; je třeba rozhodnout, zda je přiřazení zdroje bezpečné, pokud ne, pozastaví se žádající proces; stav je bezpečný, pokud existuje min. 1 posloupnost, ve které mohou procesy doběhnout bez uvíznutí (ale i když není bezpečný, uvíznutí nastat nemusí) - bankéřův algoritmus (v praxi nepoužitelný);
- prevence uvíznutí - 4 Coffmanovy podmínky;;
◦ Vzájemné vyloučení = spooling všeho
◦ Hold and wait = procesy požadují zdroje na začátku
◦ Nemožnost odejmutí = odejmi (nefunguje)
◦ Cyklické čekání zdroje očíslujeme a žádáme v číselném pořadí
Bankéřův algoritmus
Podívej se
Vyhladovění
procesy požadují zdroje, ale proces zdroj nikdy nemusí obdržet (filosofové zvedají a pokládají vidličku, SJF) - řešení: FIFO
Bernsteinovy podmínky
R(p) ∩ W(q) = Ø
W(p) ∩ R(q) = Ø
W(p) ∩ W(q) = Ø
Procesy p, q
Množina dat, kterou daný proces čte nebo zapisuje
Dodatek ke kritickým sekcím
Souběžné čtení je OK
Více procesorů - typy (2x)
Symetrický multiprocesor (SMP)
- Dva nebo více identických procesorů (nebo jader CPU) jsou připojeny k jedné hlavní paměti
- Libovolné vlákno lze přidělit libovolnému procesoru.
- Lze ovlivnit: thread affinity, thread ideal processor
Non uniform memory access (NUMA)
- Každý procesor má blíž k jedné části paměti než ostatní procesory.
- Systém se pokusí plánovat vlákno na procesoru, který je blízko používané paměti.
Instrukce IN, OUT
Privilegované
Používají adresy I/O portu jiný adresní prostor, než do RAM
Adresa 70 v IN instrukci je jiná než adresa 70 do RAM
Signál M/ IO určuje, zda je adresa na adresních vodičích do paměti nebo I/O portu
Vývoj rozhraní mezi CPU a zařízeními
- CPU řídí přímo periferii
- CPU řadič periferie (řadič a aktivní čekání CPU na dokončení operace)
- řadič umí vyvolat přerušení
- řadič umí DMA
- I/O modul
- I/O modul s vlastní pamětí
CPU řídí přímo periferii (Vývoj rozhraní mezi CPU a zařízeními)
CPU přímo vydává potřebné signály
CPU dekóduje signály poskytované zařízením
Nejjednodušší HW
Nejméně efektivní využití CPU
Jen v jednoduchých mikroprocesorem řízených zařízeních (dálkové ovládání)
CPU - řadič - periférie (Vývoj rozhraní mezi CPU a zařízeními) + 3 pojmy k tomu vztažené
Řadič (device controller)
◦ Převádí příkazy CPU na elektrické impulzy pro zařízení
◦ Poskytuje CPU info o stavu zařízení
◦ Komunikace s CPU pomocí registrů řadiče na známých I/O adresách
◦ HW buffer pro alespoň 1 záznam (blok, znak, řádka)
◦ Rozhraní řadič periférie může být standardizováno
(SCSI, IDE..)
3 pojmy:
Povel = příkaz, který dává CPU řadiči
Stav = informace o stavu, např. přenos OK
Data = buffer na předávaná data
Řadič umí vyvolat přerušení (Vývoj rozhraní mezi CPU a zařízeními)
CPU nemusí testovat příznak dokončení
Při dokončení I/O vyvolá řadič přerušení
CPU začne obsluhovat přerušení
- Obslužná procedur a přerušení
(Provádí instrukce na předdefinovaném místě)
- Určí co dále
Postačuje pro pomalá zařízení, např. sériové I/O
Řadič může přistupovat k
paměti pomocí DMA (Vývoj rozhraní mezi CPU a zařízeními) (!)
DMA přenosy mezi pamětí a I/O zařízením
CPU inicializuje přenos, ale sám ho nevykonává
Řadič DMA speciální obvod, zajištuje blokové přenosy mezi I/O zařízením a pamětí
- CPU zadá požadavek řadiči DMA (adresu I/O zařízení, adresu v RAM, počet bytů)
- DMA obvod provede přesun dat bez zásahu CPU
- CPU se zatím může věnovat dalším věcem (ale je omezen ve využití sběrnice)
- Po ukončení přenosu DMA obvod vyvolá přerušení
Bus mastering zařízení převezme kontrolu nad sběrnicí a přenos provede samo (PCI sběrnice)
Vhodné pro rychlá zařízení řadič disků, síťová karta,
zvuková karta, grafická karta atd.
I/O modul umí interpretovat speciální I/O programy (Vývoj rozhraní mezi CPU a zařízeními)
I/O procesor
Interpretuje programy v hlavní paměti (RAM)
CPU spustí I /O procesor
(I/O procesor provádí své instrukce samostatně)
I/O modul s vlastní pamětí (Vývoj rozhraní mezi CPU a zařízeními)
I/O modul provádí programy Má vlastní paměť - Je vlastně samostatným počítačem Složité a časově náročné operace grafika, šifrování, …
Komunikace CPU s řadičem (3x)
1- Odlišné adresní prostory (I/O prostor)
- CPU zapisuje do registrů řadiče pomocí speciálních I/O instrukcí
- Vstup: IN R, port
- Výstup: OUT R, port
2. 1 adresní prostor (RAM)
3. Hybridní schéma (I/O, RAM)
Mezi privilegované instrukce patří:
řízení CPU zákaz přerušení práce se speciálními registry práce se vstupními a výstupními zařízeními nastavení a mapování paměti
Principy I/O software - struktura do 4 úrovní
- obsluha přerušení nejnižší úroveň v OS)
- ovladač zařízení
- SW vrstva OS nezávislá na zařízení
- uživatelský I/O SW
Obsluha přerušení (Principy I/O software)
řadič vyvolá přerušení ve chvíli dokončení I /O požadavku
snaha, aby se přerušením nemusely zabývat vyšší vrstvy
ovladač zadá I /O požadavek, an. usne P(sem)
po příchodu přerušení ho obsluha přerušení vzbudí an. V(sem)
časově kritická obsluha přerušení co nejkratší
Ovladače zařízení (Principy I/O software)
obsahují veškerý kód závislý na konkrétním I /O zařízení (např. ovladač zvukovky od daného výrobce)
ovladač zná jediný hw podrobnosti
-> způsob komunikace s řadičem zařízení
-> zná detaily např. ví o sektorech a stopách na disku, pohybech diskového raménka, start stop motoru
může ovládat všechna zařízení daného druhu nebo třídu příbuzných zařízení
-> např. ovladač SCSI disků všechny SCSI disky
Funkce ovladače zařízení
- ovladači předán příkaz od vyšší vrstvy
◦ např. zapiš data do bloku n - nový požadavek zařazen do fronty
◦ může ještě obsluhovat předchozí - ovladač zadá příkazy řadiči (požadavek přijde na řadu)
◦ např. nastavení hlavy, přečtení sektoru - zablokuje se do vykonání požadavku
◦ neblokuje při rychlých operacích např. zápis do registru - vzbuzení obsluhou přerušení (dokončení operace)
zkontroluje, zda nenastala chyba - pokud OK, předá výsledek ( status data ) vyšší vrstvě
◦ status datová struktura pro hlášení chyb - Zpracuje další požadavky ve frontě
◦ jeden vybere a spustí
Problémy s ovladači
Chyba ovladače = pád systému - Běh v privilegovaném režimu (jádře) - Chyba v ovladači může způsobit pád systému Ovladač pro určitý HW i určitý OS - Můžete mít starší kameru s ovladačem pro Windows XP, ale třeba nebude použitelná ve Windows 8.1
SW vrstva OS nezávislá na zařízení (Principy I/O software)
I/O funkce společné pro všechna zařízení daného druhu
- např. společné fce pro všechna bloková zařízení
definuje rozhraní s ovladači
poskytuje jednotné rozhraní uživatelskému SW
Poskytované funkce SW vrstvy (Principy I/O software) (6x + pozn.)
- pojmenování zařízení
- LPT1, COM1 (paralelní a sériový port), /dev/lp0 - ochrana zařízení ( přístupová
- alokace a uvolnění vyhrazených zařízení
- v 1 chvíli použitelná pouze jedním procesem
- např. tiskárna, plotter, magnetická páska - vyrovnávací paměti
- bloková zařízení bloky pevné délky
- pomalá zařízení čtení zápis s využitím bufferu - hlášení chyb
- jednotná velikost bloku pro bloková zařízení
Pozn.:
v moderních OS se zařízení jeví jako objekty v souborovém systému (v mnoha OS je tato vrstva součástí logického souborového systému)
I/O sw v uživatelském režimu (Principy I/O software)
programátor používá v programech I/O funkce nebo příkazy jazyka
např. printf v C, writeln v Pascalu
knihovny sestavené s programem
formátování printf (“%.2d:%.2d n”, hodin , minut
často vlastní vyrovnávací paměť na jeden blok
spooling
implementován pomocí procesů běžících v uživ. režimu
způsob obsluhy vyhrazených I /O zařízení multiprogram
např. proces by alokoval zařízení a pak hodinu nic nedělal
Příklad spoolingu:
přístup k fyzické tiskárně pouze 1 speciální proces
- daemon lpd
proces vygeneruje celý soubor, lpd ho vytiskne
- proces chce tisknout, spustí lpr a naváže s ním komunikaci
- proces předává tisknutá data programu lpr
- lpr zapíše data do souboru v určeném adresáři
-> spooling directory přístup jen lpr a lpd
dokončení zápisu lpr oznámí lpd , že soubor je připraven k vytisknutí, lpd soubor vytiskne a zruší
lpd – démon (služba) čte ze spoolovacího adresáře a přistupuje k tiskárně
lpr – data, která chce aplikace vytisknout se zapisují do spoolovacího adresáře
Disk (varianty 3x)
Rotační disky
- doba vystavení + rotační zpoždění
- Stopa, sektor
SSD disky
- dražší, menší kapacita
- rychlejší
Mix
- SSD disk v kombinaci s rotačním diskem
Důvody pro RAID
pevný disk - elektronická část + mechanická - náchylnost k poruchám - cena dat >> cena hw odstávka při výměně zařízení - náhrada hw, přenos dat ze zálohy prostoje - SLA 24/7 ( Service Level Agreement ) větší disková kapacita než 1 disk
RAID (popis)
data jsou distribuována na více disků
datová operace je realizována paralelně (např. na disk 1 a 2)
kromě distribuování dat na více disků zvýšení spolehlivosti (mimo RAID 0) redundance informace (zdvojení disků nebo parita)
sada fyzických disků, OS je následně vidí jako jeden disk
= Redundant Array of Independent Disks
= Redundant Array of Inexpensive Disks
RAID 0
není redundantní, neposkytuje ochranu dat
ztráta 1 disku ztráta celého pole nebo části (dle režimu)
důvod použití může být výkon při režimu prokládání ( např. střih videa)
Dva režimy zřetězení nebo prokládání (stripping)
Zřetězení
Data postupně ukládána na několik disků
Zaplní se první disk, pak druhý, atd.
Snadné zvětšení kapacity, při poruše disku ztratíme jen část dat
Prokládání
Data ukládána na disky cyklicky po blocích ( stripy
Při poruše jednoho z disků přijdeme o data
Větší rychlost čtení zápisu
Jeden blok z jednoho disku, druhý blok z druhého disku
RAID 1
mirroring .. zrcadlení
na 2 disky stejných kapacit totožné informace
výpadek 1 disku nevadí
jednoduchá implementace často čistě sw
nevýhoda využijeme jen polovinu kapacity
zápis pomalejší (stejná data na 2 disky) ovlivněn diskem, na němž bude trvat déle
čtení rychlejší (řadič lze střídat požadavky mezi disky)
RAID 5
redundantní pole s distribuovanou paritou
minimálně 3 disky
režie: odpovídá kapacitě 1 disku z pole n disků
- 5 disků 100GB : 400GB pro data
výpadek 1 disku nevadí
čtení výkon ok
zápis pomalejší 1 zápis čtení starých dat, čtení staré parity, výpočet nové parity, zápis nových dat, zápis nové parity
Degradovaný režim (RAID)
Máme disky v RAID 5
Jeden z disků nám vypadne
- Uživatel to nepozná
- Pole běží v degradovaném režimu, maskuje poruchu
- Je třeba, aby se dozvěděl administrátor jinak vypadne další disk a přijdeme o data
RAID 6
RAID 5 + navíc další paritní disk
odolné proti výpadku dvou disků
rychlost čtení srovnatelná s RAID 5
zápis pomalejší
RAID 10
kombinace RAID 0 ( stripe ) a RAID 1 (
min. počet disků 4
režie 100 % diskov é kapacity navíc
vyšší výkon v bezpečných typech polích
podstatně rychlejší než RAID 5, při zápisu
odolnost proti ztrátě až 50 disků x RAID 5
RAID 2 - 4
RAID 2
Data po bitech stripována mezi jednotlivé disky
Rotačně synchronizované disky
(na všech discích jsou hlavy ve stejné pozici z hlediska otáčení disků a jejich vystavení)
Zabezpečení Hammingovým kódem
RAID 3 N+1 disků, bitové prokládání Rotačně synchronizované disky Na N data, poslední disk XOR parita Jen 1 disk navíc Paritní disk vytížen při zápisu na libovolný disk vyšší opotřebení
RAID 4
Disky stripovány po blocích, ne po bitech
Každý disk je nezávislý
Parita je opět po blocích
HOT SPARE DISK
záložní disk okamžitě připravený k nahrazení vadného disku
při výpadku disku v poli automaticky aktivován hot spare disk a dopočítána data
minimalizace rizika (časové okno)
Pole je degradované a je třeba vyměnit disk
Administrátor nemusí být poblíž
hot spare disk lze sdílet mezi více RAIDy (někdy)
HOT PLUG
Snadná výměna disku za běhu systému
Není třeba vypnout server pro výměnu disku
šuplík z přední strany
Ukládání dat (3x)
- DAS
- Directly attached storage
- ukládací zařízení přímo u serveru - SAN
- Storage Area Network
- oddělení storage a serverů
- Fibre Channel propojení, optický kabel - iSCSI
- SCSI + TCP /IP
SCSI
- protokol, bez fyzické vrstvy (kabely, konektory)
- zapouzdření do protokolů TCP /IP
Hierarchie pamětí
◦ Registry CPU
◦ Cache paměť - malé množství, rychlá
◦ RAM paměť 4GB, 8GB dnešní PC
◦ Pevné disky 1-2TB, pomalé, persistentní, SSD vs. rotační
Správce paměti (5 funkcí)
Část OS, která spravuje paměť
- informace o přidělení paměti
- volná = která část paměti je volná
- přidělená (a kterému procesu) - přidělování paměti na žádost
- uvolnění paměti
- zařazení k volné paměti - odebírá paměť procesům
- ochrana paměti
- přístup k paměti jiného procesu
- přístup k paměti OS
Jak probíhá alokování paměti?
• proces po žádá o alokaci n bajtů paměti funkcí
ukazatel = malloc (n)
• malloc je knihovní fce alokátoru paměti (součást glibc)
• paměť je alokována z haldy
• alokátor se podívá, zda má volnou paměť k dispozici, když ne, požádá OS o přidělení dalších stránek paměti (systémové volání sbrk)
• proces uvolní paměť, když už ji nepotřebuje voláním
free(ukazatel)
Vrací malloc ukazatel fyzické adresy?
ukazatel = malloc (size)
- takto získaný ukazatel obsahuje virtuální adresu , tj. není to přímo adresa do fyzické paměti (RAM)
virtuální adresa se uvnitř procesoru převede na fyzickou adresu (s využitím tabulky stránek atd.)
Mechanismy správy pamětí (dvě kategorie)
Základní mechanismy
◦ Program je v paměti po celou dobu svého běhu
Mechanismy s odkládáním
◦ Programy přesouvány mezi hlavní pamětí a diskem
Základní mechanismy pro správu paměti bez odkládání a stránkování (3x)
- Jednoprogramové systémy
- Multiprogramování s pevným přidělením paměti
- Multiprogramování s proměnnou velikostí oblasti
Jednoprogramové systémy (správa paměti) + tři příklady rozdělení
- Spouštíme pouze jeden program v jednom čase
- Uživatel zadá příkaz , OS zavede program do paměti
- Dovoluje použít veškerou paměť, kterou nepotřebuje OS
- Po skončení procesu lze spustit další proces
Tři příklady rozdělení paměti:
a) OS ve spodní části adresního prostoru v RAM (minipočítače)
b) OS v horní části adresního prostoru v ROM (zapouzdřené systémy)
c) OS v RAM, výchozí obslužné rutiny v ROM
(na PC MS DOS v RAM, BIOS v ROM)
Multiprogramování s pevným přidělením paměti (správa paměti)
Paralelní nebo pseudoparelelní běh více programů = multiprogramování
Práce více uživatelů, maximalizace využití CPU apod.
Nejjednodušší schéma rozdělit paměť na n oblastí (i různé velikosti)
- V historických systémech rozdělení ručně při startu stroje
- Po načtení úlohy do oblasti je obvykle část oblasti nevyužitá
- Snaha umístit úlohu do nejmenší oblasti, do které se vejde
2 strategie pevného rozdělení sekcí (Multiprogramování s pevným přidělením paměti (správa paměti) )
- Více front, každá úloha do nejmenší oblasti, kam se vejde
◦ Může se stát, že existuje neprázdná oblast, která se nevyužije, protože úlohy čekají na jiné oblasti - Jedna fronta po uvolnění oblasti z fronty vybrat největší úlohu, která se vejde (tj. není FIFO)
◦ Diskriminuje malé úlohy (vybíráme největší co se vejde ) x malým bychom měli obvykle poskytnout nejlepší službu
◦ Řešení mít vždy malou oblast, kde poběží malé úlohy
◦ Řešení s každou úlohou ve frontě sdružit „čítač přeskočení“, bude zvětšen při každém přeskočení úlohy po dosažení mezní hodnoty už nesmí být úloha přeskočena
Pravděpodobnost využití dle multiprogramování
p = pravděpodobnost čekání na I/O
p^n = pravděpodobnost, že všechny úlohy čekají na I/O
1 - p^n = pravděpodobnost využití CPU
==> stupeň multiprogramování zvyšuje využití CPU
Multiprogramování s proměnnou velikostí oblasti (správa paměti)
Úloze je přidělena paměť dle požadavku V čase se mění => Počet oblastí => Velikost oblastí => Umístění oblastí Zlepšuje využiti paměti Komplikovanější alokace dealokace
Problém mnoha volných oblastí
Může vzniknout mnoho volných oblastí (děr)
=> Paměť se „rozdrobí“
Kompaktace paměti (compaction)
Přesunout procesy směrem dolů
Drahá operace (pokud 1B .. 10ns, pak 256MB .. 2.7s)
Neprovádí se bez speciálního HW
Pro zajištění správy paměti se používají (volná x alokovaná paměť)
- bitové mapy
- seznamy (first fit, best fit, next fit, …)
- buddy systems
Správa pomocí bitových map (správa paměti)
-> Paměť rozdělíme na alokační jednotky stejné délky (B až KB)
výhoda: konstantní velikost bitové mapy
nevýhoda: najít požadovaný úsek N volných jednotek
Náročné, příliš často se nepoužívá pro RAM
Ale používá se např. pro určení volných bloků a volných i uzlů na disku
Práce se seznamem (správa paměti)
Seznam alokovaných a volných oblastí (procesů, děr) Položka seznamu: ◦ Info o typu proces nebo díra (P vs. H) ◦ Počáteční adresa oblasti ◦ Délka oblasti
Proces skončí P se nahradí H (dírou)
Dvě díry vedle sebe sloučí se
5x alokace práce se seznamem (správa paměti)
- First Fit (první vhodná)
Prohledávání od začátku, dokud se nenajde dostatečně velká díra
Díra se rozdělí na část pro proces a nepoužitou oblast (většinou „nesedne“ přesně)
Rychlý, prohledává co nejméně - Next fit (další vhodná)
Prohledávání začne tam, kde skončilo předchozí
O málo horší než first fit - Best fit (nejmenší/nejlepší vhodná)
Prohlédne celý seznam, vezme nejmenší díru, do které se proces vejde
Pomalejší prochází celý seznam
Více ztracené paměti než FF,NF zaplňuje paměť malými nepoužitelnými dírami - Worst fit (největší díra) - není vhodné
- Quick fit
Samostatné seznamy děr nejčastěji požadovaných délek
Díry velikosti 4KB, 8KB,…
Ostatní velikosti v samostatném seznamu
Alokace rychlá
Dealokace obtížné sdružování sousedů
Urychlení práce se seznamem (správa paměti)
- Oddělené seznamy pro proces a díry
◦ Složitější a pomalejší dealokace
◦ Vyplatí se při rychlé alokaci paměti pro data z I /O za řízení
◦ Alokace = jen seznam děr
◦ Dealokace = složitější přesun mezi seznamy, z děr do procesů - Oddělené seznamy, seznam děr dle velikosti
◦ Optimalizace best fitu
◦ První vhodná je i nejmenší vhodná, rychlost First fitu
◦ Režie na dealokaci sousední fyzické díry nemusí být sousední v seznamu
Asymetrie mezi procesy a dírami (správa paměti)
Dvě sousední díry H se sloučí
Dva procesy P se nesloučí
Při normálním běhu je počet děr
poloviční oproti počtu procesů
Buddy systems (správa paměti)
Seznamy volných bloků 1, 2, 4, 8, 16 … alokačních jednotek až po velikost celé paměti
Nejprve seznamy prázdné vyjma 1 položky v seznamu o velikosti paměti
Př.: Alokační jednotka 1KB, paměť velikosti 64KB
Seznamy 1, 2, 4, 8, 16, 32, 64 (7 seznamů)
Požadavek se zaokrouhlí na mocninu dvou nahoru
např. požadavek 7KB na 8KB
Blok 64KB se rozdělí na 2 bloky 32KB (buddies)
a dělíme dále…
Neefektivní (plýtvání místem) x rychlý
◦ Chci 9KB, dostanu 16KB
◦ Alokace paměti vyhledání v seznamu dostatečně velkých děr
◦ Slučování vyhledání buddy
Statická relokace
modifikace instrukce programu při zavedení do paměti
překládám call 123 na call 1123, pokud program začíná na 1000
Mechanismy ochrany paměti
mechanismus přístupového klíče
- pamět rozdělena na bloky
- každý blok 4 bity ochrany
- psw (registr) obsahuje 4 bitový klíč
- při pokusu o přístup k paměti porovnání klíče a kódu ochrany
- kód ochrany a klíč může měnit jen OS (privilegované isntrukce)
mechanismus báze a limitu
- jednotka správy paměti je MMU (uvnitř CPU)
- dva registry - báze a limit
- Báze = počáteční adresa oblasti
- Limit = velikost oblasti
- převádí adresu používanou procesem na adresu do fyzické paměti
- předtím kontrola, zda adresa není větší než limit
- Zajistí nejen ochranu, ale i dynamickou relokaci
Dynamická relokace
- Provádí se za běhu
- Lze použít mechanismus báze a limitu
- Změna privilegovaná (může měnit OS)
- Předchůdce virtuální paměti
- viz MMU
Co dělat pokud se všechny spuštěné procesy nevejdou do paměti? (2 strategie)
- Odkládání celých procesů (swapping)
- Nadbytečný proces se odloží na disk
- Daný proces se ale stále celý vejde do fyzické paměti - Virtuální paměť
- překrývání, stránkování, segmentace
- V paměti nemusí být procesy celé
Odkládání celých procesů (správa paměti) - Co dělat, když je více paměti než alokováno (4 kroky) + jak vyhradit prostor na disku
Co dělat, když je více paměti než alokováno?
- Přesunout proces do větší oblasti (díry)
- Překážející proces odložit na disk
- Odložit na disk žadatele
- Proces zrušit
Pozn.:
Typicky proces dvě rostoucí částí:
zásobník, halda
Jak vyhradit prostor na disku?
- Pořád do stejného místa
- Alokace při každém odložení
Pozn.:
- Stejné algoritmy jako při přidělení paměti
Virtuální paměť - překrývání
Program = rozdělen na moduly
Moduly postupně zaváděny do paměti
Závadění modulů:
- více překryvných modulů - data v paměti současně
- moduly zaváděny dle potřeby
- mechanismus odkládání (jako odkládání procesů)
- Zavádění modulů zařizuje OS
- Rozdělení programů a dat na části - navrhuje programátor
Virtuální paměť - rozdělení adresového prostoru
- Rozsáhlý adresový prostor
- Ve skutečnosti je pouze část adresového prostoru v paměti
- Zbytek odložen na disku
- Ve fyzické paměti ta část, co zrovna potřebujeme
Vztah RAM a virtuálního adresního prostoru
fyzická paměť RAM slouží jako cache virtuálního adresního prostoru procesů
Stránkování
- program používá virtuální adresy
= číslo stránky a offset - rychle zjistíme, zda je požadovaná adresa v paměti
- ANO - převod VA => FA
- NE - zavedení z disku
- Co nejrychlejší
Pojmy: stránky/rámce
VAP stránky (pages) pevné velikosti
- nejčastěji 4KB , další běžné: 2MB , 4MB a 1GB
fyzická paměť rámce (page frames) stejné velikosti
- rámec může obsahovat PRÁVĚ JEDNU stránku
- na známém místě v paměti tabulka stránek
- tabulka stránek poskytuje mapování virtuálních stránek na rámce
Tabulka stránek + obsah položky
Stránky mapovány na rámce případně na swap na disku, součástí tabulky procesů
Obsahuje:
1. číslo rámce (nejdůležitější)
= udává ve kterém rámci RAM je stránka uložena
2. platné/neplatné mapování
- jestli je v RAM/swapu
3. příznak ochrany (čtení, zápis, execute)
4. bit modifikace
- zda je rámec potřeba uložit do swapu při odstranění z RAM
- pokud byla modifikována, znamená to, že pokud je i ve swapu, je nyní neakuální
5. bit referenced
- zda byla stránka přistupována v poslední době
6. adresa ve swapu
7. bit caching
- povolení/zákaz cashování
Výpadek stránky
Stránka není mapována
Výpadek stránky způsobí výjimku , zachycena OS (pomocí přerušení)
OS iniciuje zavádění stránky a přepne na jiný proces
Po zavedení stránky OS upraví mapování
(tabulku stránek)
Proces může pokračovat
Problémy s tabulkou stránek
- Velký rozsah
- Pomůže váceúrovňová struktura
- např 10 bitů 1 úroveň
- 10 bitů 2. úroveň
- 12 bitů offset - Rychlost přístupu
- TLB (Translation Look-aside Buffer)
Vnější / vnitřní fragmentace
Vnější:
- zůstávají nepřidělené úseky paměti
- moc malé díry
- u stránkování nenastává
Vnitřní:
- část přidělené paměti nevyužita
- při stránkování: v průměru polovina poslední stránky prázdná
Velikost VA
32 bitů
12 offset
20 číslo stránky
TLB
Každý přístup do paměti sáhne do tabulky stránek
2x více paměťových přístupů
musíme sáhnout do tabulky stránek a pak do paměti kam chceme
TLB ( Translation Look aside Buffer ) HW cache Vstup: číslo stránky Výstup: číslo_rámce nebo odpoví, že neví Dosáhneme zpomalení jen 5 až 10 % Přepnutí kontextu na jiný proces - problém (vymazání cache) - než se TLB opět zaplní a tedy naučí mapování pomalý přístup
Stránkování na žádost
= stránkování s využitím swapu
Pracovní množina stránek
Má-li proces svou pracovní množinu stránek v paměti , může pracovat bez mnoha výpadků, dokud se pracovní množina stránek nezmění, např. do další fáze výpočtu
Ošetření výpadku stránky
- Výpadek mechanismem přerušení vyvolán OS
- OS zjistí, pro kterou stránku nastal výpadek
- OS určí umístění stránky na disku
◦ Často je tato informace přímo v tabulce stránek - Najde rámec, do kterého bude stránka zavedena
◦ Co když jsou všechny rámce obsazené? - Načte požadovanou stránku do rámce ( DMA přenos…)
- Změní odpovídající mapovací položku v tabulce stránek
- Návrat..
- CPU provede instrukci , která způsobila výpadek
Algoritmy nahrazování stránek popis + 7 příkladů
Použijí se, pokud potřebujeme uvolnit místo v operační paměti pro další stránku:
nastal výpadek stránky, je třeba někam do RAM zavést stránku a RAM je plná..
nějakou stránku musíme z RAM odstranit, ale jakou?
- Algoritmus FIFO
- MIN/OPT
- LRU
- NRU
- Second Chance
- Clock
- Aging
Algoritmus FIFO pro nahrazování stránek v paměti
Udržovat seznam stránek v pořadí, ve kterém byly zavedeny
Vyhazujeme nejstarší stránku (nejdéle zavedenou do paměti první na seznamu)
Není nejvhodnější
Často používané stránky mohou být v paměti dlouho
analogie s obchodem, nejdéle zavedený výrobek chleba)
Trpí Beladyho anomálií
= zvětšíme pamět, ale bude více výpadů pro FIFO
Algoritmus MIN/OPT pro nahrazování stránek v paměti
Optimální - nejlepší možný výpadek stránky
= ten, který nejdelší dobu nikdo nebude potřebovat
- pouze teoretický, nejde udělat, pohled do budoucna
- pouze pro srovnání
Algoritmus LRU pro nahrazování stránek v paměti
Least Recently Used
-nejdéle nepoužitá stránka
princip lokality
-> stránky používané v posledních instrukcích se budou pravděpodobně používat i v následujících
-sw řešení (není použitelné)
Zpomalení cca 10x
HW řešení čítač
MMU obsahuje čítač (64bit), při každém přístupu do paměti zvětšen
každá položka v tabulce stránek pole pro uložení čítače
odkaz do paměti
- obsah čítače se zapíše do položky pro odkazovanou stránku
výpadek stránky
- vyhodí se stránka s nejnižším číslem
výhody
z časově založených (realizovatelných) nejlepší
Beladyho anomálie nemůže nastat
nevýhody
každý odkaz na stránku aktualizace záznamu (zpomalení)
- položka v tab. stránek
- řádek a sloupec v matici
LRU se pro stránkovanou virtuální paměť
příliš nepoužívá
LRU ale např. pro blokovou cache souborů
HW matice LRU
MMU udržuje matici n * n bitů
n = počet rámců
všechny prvky 0
odkaz na stránku odpovídající k tému rámci
- všechny bity k tého řádku matice na 1
-všechny bity k tého sloupce matice na 0
řádek s nejnižší binární hodnotou
= nejdéle nepoužitá stránka
Algoritmus NRU pro nahrazování stránek v paměti
snaha vyhazovat nepoužívané stránky
HW podpora:
- stavové bity Referenced ( a Dirty (M = modified)
- v tabulce stránek
bity nastavované HW dle způsobu přístupu ke stránce
bit R nastaven na 1 při čtení nebo zápisu do stránky
- pravidelně nulován (aby označoval referenci v poslední době)
bit M na 1 při zápisu do stránky
- stránku je třeba při vyhození zapsat na disk
- bit zůstane na 1, dokud ho SW nenastaví zpět na 0
Rozhodneme na základě R a M
4 kategorie dle R a M
NRU náhodně vyhodí stránku z nejnižší neprázdné třídy
výhody
jednoduchost, srozumitelnost
efektivně implementovaný
nevýhody
výkonnost (jsou i lepší algoritmy)
Algoritmy Second Chance a Clock pro nahrazování stránek v paměti
vycházejí z FIFO
- FIFO obchod vyhazuje zboží zavedené před nejdelší dobou, ať už ho někdo chce nebo ne
- Second Chance evidovat, jestli zboží v poslední době někdo koupil (ano prohlásíme za čerstvé zboží)
modifikace FIFO zabránit vyhození často používané
Second Chance:
- dle bitu R nejstarší stránky
Clock:
- Stránky udržovány v kruhovém seznamu
- Ukazatel na nejstarší stránku = ručička hodi
Od SC se líší pouze implementací
Algoritmus Aging pro nahrazování stránek v paměti
Algoritmus Aging
Každá položka tabulky stránek pole stáří ( age), N bitů (8)
Na počátku age = 0
Při každém přerušení časovače pro každou stránku:
Posun pole stáří o 1 bit vpravo
Zleva se přidá hodnota bitu R
Nastavení R na 0
Při výpadku se vyhodí stránka, jejíž pole age má nejnižší hodnotu
Aging x LRU
Několik stránek může mít stejnou hodnotu age a nevíme, která byla odkazovaná dříve (u LRU jasné vždy) hrubé rozlišení
Age se může snížit na 0 nevíme, zda odkazovaná před 9ti nebo 1000ci tiky časovače
Uchovává pouze omezenou historii
V praxi není problém tik 20ms, N=8, nebyla odkazována 160ms nejspíše není tak důležitá, můžeme jí vyhodit
stránky se stejnou hodnotou age vybereme náhodně
Alokace fyzických rámců
Globální a lokální alokace
Globální pro vyhození se uvažují všechny rámce
- Lepší průchodnost systému častější
- Na běh procesu má vliv chování ostatních procesů
Lokální uvažují se pouze rámce alokované procesem (tj. obsahující stránky procesu, jehož výpadek stránky se obsluhuje)
- Počet stránek alokovaných pro proces se nemění
- Program se vzhledem k stránkování chová přibližně stejně při každém běhu
Lokální alokace (strategie 3x)
- Nejjednodušší = všem procesům dát stejně
- Ale potřeby procesů jsou různé - Proprocionální = každému proporcionální díl podle velikosti procesu
- Nejlepší = podle frekvence výpadků stránek za jednotku času (Page Fault Frequency, PFF ) (!znát)
- Pro většinu rozumných algoritmů se PFF snižuje s množstvím přidělených rámců
Zloděj stránek (page daemon)
v systému se běžně udržuje určitý počet volných rámců
když klesne pod určitou mez, pustí page daemon - kswapd (zloděj stránek), ten uvolní určité množství stránek (rámců)
když se čerstvě uvolněné stránky hned nepřidělí, lze je v případě potřeby snadno vrátit příslušnému procesu
Zamykání stránek
zabrání odložení stránky části jádra stránka, kde probíhá I/O tabulky stránek nastavení uživatelem mlock () , viz man 2 mlock
Zahlcení a pracovní množina stránek
Proces pro svůj rozumný běh potřebuje pracovní množinu stránek
Pokus se pracovní množiny stránek aktivních procesů nevejdou do paměti, nastane zahlcení (trashing)
Zahlcení
V procesu nastane výpadek stránky
Paměť je plná (není volný rámec) je třeba nějakou stránku vyhodit , stránka pro vyhození bude ale brzo zapotřebí , bude se muset vyhodit jiná používaná stránka
Uživatel pozoruje systém intenzivně pracuje s diskem a běh procesů se řádově zpomalí (víc času stránkování než běh)
Řešení při zahlcení snížit úroveň multiprogramování
(zahlcení lze detekovat pomocí PFF)
Sdílení paměti mezi procesy
Sdílené regiony paměti
Volání shmget , shmat , shmdt (viz
chci sdílenou pamět 2000B s klíčem 5678
Paměťově mapované soubory
Volání mmap
Soubor na disku se tváří jako blok paměti
Zápis do stránky –> nastaví bit modified
Při odstranění z paměti zapíše na disk
Mechanismus VP výhody a nevýhody
+ Rozsah virtuální paměti
+ Efektivnější využití fyzické paměti
- Režie při převodu VA na FA
- Režie procesoru (údržba tabulek, výběr stránky pro vyhození)
- Režie I/O při čtení/zápisu stránky
- Paměť pro tabulky
- Vnitřní fragmentace
Rozdělení paměti pro proces
Od začátku:
- Operační systém
- Zásobník
- Prostor pro zásobník
- Sdílené knihovny
- Prostor pro haldu
- Halda
- Inicializovaná data
- Kód programu
Segmentace obecně
= více samostatných virtuálních adresových prostorů
- dosud jednorozměrná, tj. od 0 do max
Paměť nejlépe více nezávislých adresových prostorů segmenty
Segment logické seskupení informací
Každý segment lineární posloupnost adres od 0
Programátor o segmentech ví , používá je explicitně (adresuje konkrétní segment)
Např. Kód přeloženého program (CS) Globální proměnné Hromada (DS) Zásobník návratových adres (SS)
Čistá segmentace
Každý odkaz do paměti dvojice (selektor, offset)
- Selektor obsahuje mj. odkaz do tabulky segmentů, určuje segment
- Offset relativní adresa v rámci segmentu
Technické prostředky musí umět přemapovat dvojici selektor, offset) na lineární adresu (je fyzická když není dále stránkování)
Tabulka segmentů - každá položka má
Počáteční adresa segmentu ( báze)
Rozsah segmentu ( limit)
Příznaky ochrany segmentu ( čtení,zápis , provádění - rwx)
Selektor, offset, deskriptor
Selektor = z větší části index do tabulky segmentů (1 bit říká jestli je tabulka globální nebo lokální GDT x LDT -> LDT v PCB)
Offset = relativní adresa v rámci segmentu
Deskriptor (segmentu) = kombinace báze a limitu + další položky (adresa, rozsah…)
Kontroly porušení ochrany paměti v čisté segmentaci
- Ukazuje selektor na vyplněnou řádku v tabulce segmentů?
Pokud ne (např. samé 0) ukončení procesu - Platí, že ofset limit?
Pokud ne ukončení procesu - Podle příznaků, nechci sahat na segment, kam může např. jen jádro?
Opět může vést k ukončení procesu
Segmentace na žádost
Segment zavedený v paměti nebo odložený na disku
Adresování segmentu co není v paměti výpadek segmentu zavede do paměti není-li místo jiný segment odložen na disk
HW podpora bity v tabulce segmentů
- Bit segment je zaveden v paměti ( Present / absent)
- Bit referenced
(Segment oproti stránce velký)
Adresy - Segmentace (+ segmentace se stránkováním)
virtuální adresa –> lineární adresa –> fyzická adresa
virtuální = používá proces ( selektor:offset)
lineární po segmentaci (už jedno číslo od 0 výše) pokud není dále stránkování, tak už představuje i fyzickou adresu
fyzická adresa = do fyzické paměti RAM (CPU jí vystaví na sběrnici)
Selektor segmentu (bity)
16 bitů
13 bitů - index do GDT nebo LDT
1 bit - 0=GDT, 1=LDT
2 bity - úroveň privilegovanosti (ring = 0 jádro, 3 už. proces)
Rychlý přístup k deskriptoru segmentu
logická adresa: segment selektor (16bitů) + offset (32bitů)
zrychlení převodu:
přídavné neprogramovatelné registry (pro každý segm. reg.)
když se nahraje segment selektor do segmentového registru, odpovídající deskriptor se nahraje do odpovídajícího neprogramovatelného registru
Deskriptor segmentu (bity)
64bitů 32 bitů báze 20 bitů limit - v bytech, do 1MB (2^20) - v 4K stránkách (do 2^32)(2^12 4096) příznaky - typ (kód nebo data/zásobník) a ochrana segmentu - segment přítomen v paměti..
Komplexní schéma převodu VA na FA
viz přednáška 12 stránka 50 (zkus si nakreslit)
Reálný x chráněný mód
Běžný procesor v PC může běžet v reálném nebo chráněném módu
Po zapnutí napájení byl puštěn reálný mód , ten využíval např. MS DOS není zde však žádný mechanismus ochrany
Dnešní systémy přepínají procesor ihned do chráněného režimu (ochrana segmentů uplatněním limitu, ochrana privilegovanosti kontrolou z jakého ringu je možné přistupovat)
Jak funguje malloc?
v C o paměť žádáme malloc() a máme ji uvolnit free()
paměť nám přidělí knihovna alokátor paměti , která spravuje volnou paměť
pokud alokátor nemá volnou paměť k dispozici, požádá operační systém systémovým voláním o přidělení další části paměti (další stránky)
Amdahlův zákon
Určuje urychlení výpočtu při užití více procesorů
Urychlení je limitováno sekvenčními částmi výpočtu
tj. u 2 CPU není urychlení 2x, ale pouze část kódu lze provést paralelně
