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;;
