Principy operačních systémů. Lekce 4: Správa procesů

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.)


2


Životní cyklus procesu


3


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


Stavy procesu – sedmistavový model


5


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ý


6


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


7


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


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á


9


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


10


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


11


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ů


12


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)


13


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


Round Robin Scheduling


15


Round Robin Scheduling


16


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í.


17


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 %


18


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


19


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


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í.


21


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.


22


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í.


23


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


24


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


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


26


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í)


27


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


28


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


29


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)


30


Vztah procesu a vlákna Vlákno:


31


Proces a vlákna


32


Proces a vlákna


33


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.


34


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


35


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


36


Vlákna na uživatelské úrovni (ULT)


37


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


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


39


Vlákna na úrovni jádra


40


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


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


42


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í


43


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í


44


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.


45


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


Typické vícevláknové aplikace


47


Modely vícevláknových aplikací


48


Model Boss/Worker


49


Model Boss/Worker


50


Model Peer


51


Model Peer


52


Model Pipeline


53


Model Pipeline


54


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.


55

Principy operačních systémů. Lekce 4: Správa procesů

Recommend Documents