Principy operačních systémů
Lekce 4: Správa procesů
Principy operačních systémů – Ing. Nulíček Vladimír
Základní pojmy • Program = zápis algoritmu v programovacím jazyce – Je statický (neměnný)
• Proces = instance programu běžícího v počítači – Je tvořen nejen kódem programu, ale i konstantami a proměnnými daty (stav procesoru, data na zásobníku, globální proměnné aj). – Jeden program může být spuštěn jako několik procesů (např. webový prohlížeč s různými stránkami, aplikace s různými soubory apod.)
Lekce 4: Správa procesů
2
Principy operačních systémů – Ing. Nulíček Vladimír
Životní cyklus procesu
Lekce 4: Správa procesů
3
Principy operačních systémů – Ing. Nulíček Vladimír
Stavy procesu • • • •
INIT = program byl spuštěn, proces je vytvářen READY = proces je připraven ke spuštění RUNNING = běžící, má přidělen procesor SLEEP/WAITING = spící (nějakou dobu nemá přidělen procesor) nebo čekající (na dokončení I/O operace) • SWAPPING = odložení procesu na vnější paměť (odložený může být proces ze stavu Sleep/Waiting nebo Ready) • ZOMBIE = ukončený proces čekající např. na uvolnění paměti Lekce 4: Správa procesů
4
Principy operačních systémů – Ing. Nulíček Vladimír
Stavy procesu – sedmistavový model
Lekce 4: Správa procesů
5
Principy operačních systémů – Ing. Nulíček Vladimír
Plánování procesů • pokud některý proces přejde ze stavu běžící do stavu blokovaný (čekání na I/O operaci nebo na uplynutí zadaného časového intervalu nebo na ukončení procesu-potomka) • pokud některý proces skončí • pokud je některý proces převeden ze stavu běžící do stavu připravený • pokud některý proces přejde ze stavu čekající (odložený připravený) do stavu připravený
Lekce 3: Správa procesů
6
Principy operačních systémů – Ing. Nulíček Vladimír
Plánování procesů - preemptivnost • Nepreemptivní (první 2 případy) – Proces se musí sám vzdát přidělení CPU a čekat, až mu proces nabídne přeplánování procesoru speciálním voláním služby operačního systému
• Preemptivní – Procesor odebere procesu OS, např. po uplynutí určitého časového okamžiku
Lekce 4: Správa procesů
7
Principy operačních systémů – Ing. Nulíček Vladimír
Plánování procesů z hlediska času • Dlouhodobé plánování (Long-Term Scheduling) – Označuje se též jako plánování úloh (Job Scheduling) – Výběr, která úloha bude spuštěna (má význam u dávkového zpracování) – Jeho účelem je naplánovat spouštění úloh tak, aby byl počítač maximálně využit, například vhodného mixu úloh, které jsou náročné na I/O nebo CPU
• Střednědobé plánování (Mid-Term Scheduling) – Používají systémy s virtuální pamětí – Jde o výběr, který blokovaný nebo připravený proces bude odsunut z vnitřní paměti na pevný disk, je-li vnitřní paměti nedostatek (swapping out resp. swapping in)
• Krátkodobé plánování (Short-Term Scheduling) – Plánování procesoru (CPU Scheduling) – Vybírá se, kterému z připravených procesů bude přidělen procesor – Používá se ve všech víceúlohových systémech Lekce 4: Správa procesů
8
Principy operačních systémů – Ing. Nulíček Vladimír
Typy procesů • vstupně-výstupně orientovaný proces – většinu času čeká na dokončení operací V/V – typická je krátká výpočetní doba – časté používání blokujících systémových volání • výpočetně orientovaný proces – používá intenzivně procesor – blokovaná volání téměř nepoužívá
Lekce 4: Správa procesů
9
Principy operačních systémů – Ing. Nulíček Vladimír
Strategie plánování procesů Strategie použitá pro výběr, kterému z připravených procesů bude přidělen procesor, je vybírána podle těchto kritérií: • spravedlnost: každý proces dostane spravedlivý díl času procesoru • efektivita: snaha udržovat maximální vytížení procesu nebo jiné části systému • čas odezvy: minimalizovat dobu odezvy pro interaktivní uživatele • doba obrátky: minimalizovat dobu zpracování každé dávkové úlohy • průchodnost: maximalizovat množství úloh zpracovaných za jednotku času Různá váha jednotlivých kritérií různé strategie plánování procesu
Lekce 4: Správa procesů
10
Principy operačních systémů – Ing. Nulíček Vladimír
FCFS = First-Come First-Served • Procesy přicházející do stavu připraven jsou umísťovány na konec fronty typu FIFO (First In First Out). • Při plánování procesoru se procesor přidělí procesu, který je první na řadě (který čekal ve frontě nejdéle) • Nepreemptivní plánování (obdoba u preemptivního plánování je Round Robin Scheduling) • Nevýhoda: krátké procesy musí zbytečně dlouho čekat • Zvýhodňuje výpočetně orientované proces procesy bez I/O čekají pouze jednou procesy s I/O čekají při každém dokončení operace
Lekce 4: Správa procesů
11
Principy operačních systémů – Ing. Nulíček Vladimír
SJF = Shortest Job First • Přednost mají úlohy, u nichž se předpokládá že poběží krátkou dobu nebo že využijí pouze část přiděleného časového kvanta • Předpověď se provádí podle chování úlohy při minulých spuštěních • nepreemptivní • Závislé na dobrém odhadu délky běhu procesu • Hhrozí vyhladovění dlouhodobých procesů
Lekce 4: Správa procesů
12
Principy operačních systémů – Ing. Nulíček Vladimír
Shortest Remaining Time First • preemptivní varianta SJF • spustí se proces s nejkratší očekávanou dobou do dokončení • dále minimalizuje obrat (Turnaround Time)
Lekce 4: Správa procesů
13
Principy operačních systémů – Ing. Nulíček Vladimír
Round Robin Scheduling • • • •
Preemptivní varianta FCFS Preempce založená na časovači Každý proces dostane časové kvantum na CPU Přepnutí je prováděno při vypršení kvanta nebo při volání blokujícího systémového volání • Je třeba optimalizovat délku kvanta – Příklad: – kvantum 4 ms, context switch 1 ms – CPU pracuje produktivně jen 80 % času
• Typické nastavení časovače je 100Hz (jednou za 10ms) Lekce 4: Správa procesů
14
Principy operačních systémů – Ing. Nulíček Vladimír
Round Robin Scheduling
Lekce 4: Správa procesů
15
Principy operačních systémů – Ing. Nulíček Vladimír
Round Robin Scheduling
Lekce 4: Správa procesů
16
Principy operačních systémů – Ing. Nulíček Vladimír
Priority Based Scheduling (prioritní strategie) • Každému procesu je přidělena priorita, procesy jsou vybírány podle priority. • Procesy se stejnou prioritou jsou obvykle vybírány v pořadí, v jakém přišly do stavu připravený. • Problémem je tzv. stárnutí (starvation) – procesy s nízkou prioritou mohou čekat velmi dlouho (až nekonečně dlouho) • Řeší se tzv. agingem – postupné zvyšování priority procesů, které jsou dlouho ve stavu čekající.
Lekce 4: Správa procesů
17
Principy operačních systémů – Ing. Nulíček Vladimír
Guaranteed Scheduling – FairShare (Plánování se zárukou) • Zaručuje každému uživateli stejné podmínky • n uživatelů na systému, každý dostane časové kvantum 1/n • Příklad: • • • •
uživatel A spustí 9 procesů uživatel B spustí 1 proces při Round Robin má uživatel A 90 % času CPU, B pouze 10 % při Fair Share se využití CPU rozdělí mezi A a B na 50 % • B: jeden proces 50 % času CPU • A: devět procesů si rozdělí 50 % času, jeden má cca 5,56 %
Lekce 4: Správa procesů
18
Principy operačních systémů – Ing. Nulíček Vladimír
Lottery Scheduling (loteriové plánování) • Každý proces dostane tikety a periodicky se losuje • „Výherní“ proces získá čas CPU
• Důležité procesy mohou mít více tiketů • Procesy jsou si rovny, ale některé jsou si „rovnější“
• Kooperativní procesy si mohou předávat tikety • Lze použít jako aproximace jiných algoritmů • Snadná implementace
Lekce 4: Správa procesů
19
Principy operačních systémů – Ing. Nulíček Vladimír
RTOS – Operační systém reálného času • Poskytuje možnost reagovat na události v okolí počítače průběžně (tj. v reálném čase). • Poskytuje uživateli (nebo programátorovi) záruky, že je určitou činnost v určitém časovém úseku možné dokončit • Hard RT – deadline musí být splněna • Soft RT – akceptovatelný občasný výpadek • události se dělí na • periodické • aperiodické – nelze je předpovědět • systém je plánovatelný, pokud suma časů potřebných na obsloužení událostí dělená jejich periodami je menší nebo rovna jedné Lekce 4: Správa procesů
20
Principy operačních systémů – Ing. Nulíček Vladimír
Kontext procesu • Každý proces probíhá ve vlastním virtuální prostředí, které mu jádro operačního systému vytvoří. • Aktuální stav toho virtuálního prostředí se nazývá kontext procesu. • Kontext procesu tvoří: – – – – – –
stav procesu čítač programu registry CPU informace o plánování CPU (priorita procesu) informace o managementu operační paměti účtovací informace (spotřebovaný čas CPU, celkový reálný čas trvání procesu, číslo procesu, ...) – informace o stavu vstupních a výstupních zařízení.
Lekce 4: Správa procesů
21
Principy operačních systémů – Ing. Nulíček Vladimír
Změna kontextu • Při přepínání mezi procesy se provádí uložení kontextu (context save) původně běžícího procesu a obnovení kontextu (context restore) procesu, kterému se přiděluje procesor. • Kontext se ukládá buď na zásobník procesu, nebo do předem připravené oblasti dat v adresním prostoru procesu.
Lekce 4: Správa procesů
22
Principy operačních systémů – Ing. Nulíček Vladimír
Změna kontextu Ke změně kontextu dochází: • Při preemptivním plánování procesů (přerušení procesu plánovačem = scheduler) • Obsluha přerušení – pokud procesor vyžaduje z disku nějaká data, nemusí se zatěžovat čekáním, než čtení skončí, stačí podat žádost a pokračovat s jinou operací; když čtení skončí, řadič disku vygeneruje přerušení, které v procesoru spustí část operačního systému zvanou obsluha přerušení.
Lekce 4: Správa procesů
23
Principy operačních systémů – Ing. Nulíček Vladimír
Běh procesů Procesy mohou běžet několika způsoby: • Sekvenčně – další proces může být spuštěn až po ukončení činnosti předchozího • Sekvenčně paralelně – je spuštěno více procesů, které se dělí o čas procesoru – např. se střídají po určitých časových intervalech o CPU – multitaskový systém (pseudoparelelismus) • Paralelně – procesy pracují souběžně, každý může běžet na jiném procesoru – multiprocesorový systém s multitaskingem
Lekce 4: Správa procesů
24
Principy operačních systémů – Ing. Nulíček Vladimír
Multiprogramování – předchůdce multitaskingu • Vzájemné volání: – Implementován procesem (nikoliv OS) – Procesu je přidělen procesor, pokud je volán jiným běžícím procesem
• Omezené přepínání: – Systém přepíná mezi jedním běžným procesem a tzv. pomůckami (accessories) – malé programy specielně pro tento účel programované (např. jednoduchý textový, grafický editor, kalkulačka)
• Neomezené přepínání: – Možnost přepínání mezi jakýmikoli běžícími procesy (Apple MacOS – modul MultiFinder) Lekce 3: Správa procesů
25
Principy operačních systémů – Ing. Nulíček Vladimír
Kooperativní (nepreemptivní) multitasking
•
•
– Jeden proces na popředí ostatní na pozadí. – Proces na popředí má přidělen procesor, když jej nepotřebuje (např. čeká na událost, např. vstup z klávesnice), může být na krátkou dobu přidělen procesor některému procesu na pozadí. – Procesy kooperují s OS (předávají mu řízení, když nepotřebují procesor) – voláním služby systému Výhody: – Možnost spuštění více procesů, kooperace mezi nimi – Lepší využití prostředků v systému (paměť, čas procesoru) – Možnost implementovat víceuživatelský systém) Nevýhody: – Větší nároky na HW – Nutnost řešit problémy s bezpečností a stabilitou systému – Při chybě volání služby přerušení může dojít k zamrznutí systému
Lekce 3: Správa procesů
26
Principy operačních systémů – Ing. Nulíček Vladimír
Preemptivní multitasking – Neustálé přepínání mezi procesy – Procesy na multitaskingu nespolupracují – Přerušení odebrání procesoru je vygenerováno při každé události v systému – Kontext musí obsahovat více údajů než např. u přepínání úloh stav registrů procesoru a koprocesoru (proces po znovupřidělení procesoru nemusí být informován o tom, že jeho činnost nebyla souvislá) – Je nutno řešit problém přidělování prostředků (architektura klient-server pro přístup k ovladačům zařízení)
Lekce 3: Správa procesů
27
Principy operačních systémů – Ing. Nulíček Vladimír
Time slicing (sdílení času) – Vylepšení preemptivního multitaskingu – Přepnutí kontextu nejen při vygenerování nějaké události, ale i v určitých časových intervalech (v řádu jednotek až desítek ms) – Rychlé střídání procesů ve využití času procesoru = pseudoparalelismus (uživatel má dojem paralelního zpracování úloh) – Přerušení procesu – vždy po uplynutí stanoveného časového intervalu nebo dříve, bylo-li přerušení vyvoláno nějakou událostí resp. pokud byl dokončen před uplynutím intervalu
Lekce 3: Správa procesů
28
Principy operačních systémů – Ing. Nulíček Vladimír
Preemptivní multitasking • Výhody: – – – – – – –
Možnost spuštění více procesů, možnost spolupráce a komunikace procesů Lepší využití prostředků systému (paměť, čas procesoru apod.) Možnost implementace víceuživatelského systému Možnost implementace GUI Možnost implementace bezpečnostních mechanismů Snadnější implementace než u kooperativního multitaskingu Nezávislost na běhu procesů (a dobré vůli programátorů)
• Nevýhody: – Vetší nároky na HW – Rozsáhlejší kontext než u kooperativního multitaskingu
Lekce 3: Správa procesů
29
Principy operačních systémů – Ing. Nulíček Vladimír
Vlákno (Thread) • Vlákno (též vlákno řízení, anglicky thread) označuje v informatice odlehčený proces, pomocí něhož se snižuje režie operačního systému při změně kontextu, které je nutné pro zajištění multitaskingu (zdánlivého běhu více úloh zároveň, který je zajištěn jejich rychlým střídáním na procesoru) nebo při masivně paralelních výpočtech. • Zatímco běžné procesy jsou navzájem striktně odděleny, sdílí vlákna nejen společný paměťový prostor, ale i další struktury. • Procesy – Jednovláknové – Vícevláknové (Multithreading)
Lekce 3: Správa procesů
30
Principy operačních systémů – Ing. Nulíček Vladimír
Vztah procesu a vlákna Vlákno:
Lekce 3: Správa procesů
31
Principy operačních systémů – Ing. Nulíček Vladimír
Proces a vlákna
Lekce 3: Správa procesů
32
Principy operačních systémů – Ing. Nulíček Vladimír
Proces a vlákna
Lekce 3: Správa procesů
33
Principy operačních systémů – Ing. Nulíček Vladimír
Rozdíly mezi multithreadovým a multiprocesorovým multitaskingem • Sdílená paměť • Jednodušší režie při přepínání: Přepnutí mezi vlákny bývá výrazně rychlejší neboť vlákna sdílejí paměť a uživatelská práva svého mateřského procesu a není je třeba při přepínání měnit. V některých případech není třeba při přepínání vláken volat jádro OS. Rychlejší může být i vytváření a rušení vlákna. Vlákno také spotřebuje méně paměti, což je důležité pro aplikace, které používají stovky nebo více vláken.
Lekce 3: Správa procesů
34
Principy operačních systémů – Ing. Nulíček Vladimír
Podpora vláken v OS: Z hlediska spravování vláken OS můžeme vlákna rozdělit na • vlákna na uživatelské úrovni (ULT) • vlákna na úrovni jádra (KLT) • kombinace KLT a ULT
Lekce 3: Správa procesů
35
Principy operačních systémů – Ing. Nulíček Vladimír
Vlákna na uživatelské úrovni (ULT = UserLevel Threads) • Vlastnosti Správu vláken provádí tzv. vláknová knihovna (Thread Library) na úrovni aplikačního procesu, JOS o jejich existenci neví Přepojování mezi vlákny nepožaduje provádění funkcí jádra Nepřepíná se ani kontext procesu ani režim procesoru Aplikace má možnost zvolit si nejvhodnější strategii a algoritmus pro plánování vláken • Příklady POSIX – některé implementace knihovny Pthreads Solaris1 – knihovna Threads
Lekce 3: Správa procesů
36
Principy operačních systémů – Ing. Nulíček Vladimír
Vlákna na uživatelské úrovni (ULT)
Lekce 3: Správa procesů
37
Principy operačních systémů – Ing. Nulíček Vladimír
Vlákna na uživatelské úrovni (ULT) • Výhody nezávislost na podpoře vláken v OS přepínání mezi vlákny je nezávislé na OS (může být rychlejší) výrazně rychlejší tvorba a přepínání vláken plná kontrola procesu nad správou běhu vláken • Nevýhody volání služby jedním vláknem zablokuje všechna vlákna procesu nutnost dodatečného programování (řízení vláken programátorem) pokud jádro přiděluje procesor pouze procesům, nemohou dvě vlákna téhož procesu běžet současně, i když systém obsahuje více procesorů Lekce 3: Správa procesů
38
Principy operačních systémů – Ing. Nulíček Vladimír
Vlákna na úrovni jádra (KLT = Kernel-Level Threads) • Vlastnosti Veškerá správa vláken je realizována OS Každé vlákno v uživatelském prostoru je zobrazeno na vlákno v jádře (model 1:1) JOS vytváří, plánuje a ruší vlákna Jádro může plánovat vlákna na různé CPU Skutečný multiprocessing • Příklady Windows NT/2000/XP Linux 4.4BSD UNIX Tru64 UNIX
Lekce 3: Správa procesů
39
Principy operačních systémů – Ing. Nulíček Vladimír
Vlákna na úrovni jádra
Lekce 3: Správa procesů
40
Principy operačních systémů – Ing. Nulíček Vladimír
Vlákna na úrovni jádra • Výhody: Volání systému neblokuje ostatní vlákna téhož procesu Jeden proces může využít více procesorů (skutečný paralelismus uvnitř jednoho procesu – každé vlákno běží na jiném procesoru) Tvorba, rušení a přepínání mezi vlákny je levnější než mezi procesy I moduly jádra mohou mít vícevláknový charakter • Nevýhody: Systémová správa je režijně nákladnější než u čistě uživatelských vláken Klasické plánování není spravedlivé: Dostává-li vlákno své kvantum, pak procesy s více vlákny dostávají více času Lekce 3: Správa procesů
41
Principy operačních systémů – Ing. Nulíček Vladimír
Kombinace ULT a KLT • Některé OS podporují oba způsoby běhu vláken. • Přiřazování uživatelských vláken k systémovým se děje automaticky (bez programátora) anebo programátor může nastavit počet vláken na úrovni jádra.
Příklady • Windows 2000/XP s nadstavbou ThreadFiber • FreeBSD 5.x
Lekce 3: Správa procesů
42
Principy operačních systémů – Ing. Nulíček Vladimír
Kdy se vlákna používají • Obsluha periferií
U některých zařízení je třeba periodicky testovat stav hardware Vláknu pak nemusí zbývat mnoho času na obsluhu uživatelského rozhraní Jedno vlákno pro komunikaci s uživatelem a druhé obsluhuje hardware
• Síťová komunikace
Jedno vlákno akceptuje příchozí komunikace Jedno vlákno odesílá data Jedno vlákno zpracovává data
• Vyvolání dojmu rychlé odezvy programu
Práce s velkým objemem data uložených v databázi Hlavní vlákno pouze obsluhuje uživatelské rozhraní, další pracuje s databází
Lekce 3: Správa procesů
43
Principy operačních systémů – Ing. Nulíček Vladimír
Kdy se vlákna používají • Urychlení výpočtu
Lze-li spustit na víceprocesorovém stroji kooperující vlákna na několika procesorech Vhodné pro architekturu aplikace Simulace – jedno vlákno počítá vlastní simulaci Další vlákno periodicky vzorkuje stav simulace a zobrazuje ho Primární vlákno obsluhuje uživatelské rozhraní
• Efektivita
Některé aplikace jsou ze své podstaty nevhodná pro jednovláknovou architekturu Použití vláken může vést k výraznému zpřehlednění programového kódu V moderním OS už beztak běží několik vláken, pár navíc nehraje roli. Každý OS má maximální strop na počet threadů, kdy je plánování procesu stále ještě efektivní
Lekce 3: Správa procesů
44
Principy operačních systémů – Ing. Nulíček Vladimír
Kritéria pro použití vláken Vlákna je výhodné použít, pokud aplikace splňuje některé z následujících kritérií:
• • • • •
Je složena z několika nezávislých úloh. Může být blokována po dlouhou dobu. Obsahuje výpočetně náročnou část. Reaguje na asynchronní události. Obsahuje úlohy s nižší nebo vyšší prioritou než zbytek aplikace.
Lekce 3: Správa procesů
45
Principy operačních systémů – Ing. Nulíček Vladimír
Nevýhody vláken Vlákna byste měli používat jen tam, kde je to opravdu nutné, protože tvorba vlákna na určitých platformách je poněkud zdlouhavá operace. K vyřešení tohoto problému se u vícevláknových aplikací používá mechanismus sdružování vláken. Každé vlákno vytváří v paměti vlastní zásobník, do kterých jsou ukládány mezivýsledky, stavy proměnných, adresy apod. I když je teoreticky možné vytvářet obrovský počet vláken, maximální počet vláken je omezen platformou. Z toho vyplývá, že při tvorbě vláken je třeba se řídit zdravým rozumem. Tento problém nelze vyloučit, lze jej však ovlivnit pomocí sdružování vláken. Je však nutno nechat na správci sdružovaní, kdy vlákno vytvořit a kolik jich vůbec vytvářet. Jednou z největších nevýhod vláken je však zvýšená složitost kódu Je daleko složitější sledovat tok programu. Další z nevýhod vláken je sdílení prostředků, za kterou je většinou odpovědný programátor. K řízení sdílení prostředků se používá synchronizace. Ta zaručuje, že stav dat nebude změněn z více vláken zároveň. Lekce 3: Správa procesů
46
Principy operačních systémů – Ing. Nulíček Vladimír
Typické vícevláknové aplikace
Lekce 3: Správa procesů
47
Principy operačních systémů – Ing. Nulíček Vladimír
Modely vícevláknových aplikací
Lekce 3: Správa procesů
48
Principy operačních systémů – Ing. Nulíček Vladimír
Model Boss/Worker
Lekce 3: Správa procesů
49
Principy operačních systémů – Ing. Nulíček Vladimír
Model Boss/Worker
Lekce 3: Správa procesů
50
Principy operačních systémů – Ing. Nulíček Vladimír
Model Peer
Lekce 3: Správa procesů
51
Principy operačních systémů – Ing. Nulíček Vladimír
Model Peer
Lekce 3: Správa procesů
52
Principy operačních systémů – Ing. Nulíček Vladimír
Model Pipeline
Lekce 3: Správa procesů
53
Principy operačních systémů – Ing. Nulíček Vladimír
Model Pipeline
Lekce 3: Správa procesů
54
Principy operačních systémů – Ing. Nulíček Vladimír
Vícevláknové aplikace a ladění Hlavní problémy vícevláknových aplikací souvisí se synchronizací •
•
•
Uváznutí (Deadlock) – úspěšné dokončení první akce je podmíněno předchozím dokončením druhé akce Souběh (Race Conditions) - přístup více vláken ke sdíleným proměnným a alespoň jedno vlákno nevyužívá synchronizačních mechanismů. Vlákno čte hodnotu zatímco jiné vlákno zapisuje. Zápis a čtení nejsou atomické a data mohou být neplatná. Vyhladovění - stav, kdy jsou vláknu neustále odepírány prostředky. Bez těchto prostředků program nikdy nedokončí svůj úkol.
Lekce 3: Správa procesů
55