Operační systém
a plánování procesů
Komplexní průvodce od základní charakteristiky OS přes typy jader až po plánovací algoritmy – vysvětleno krok za krokem s důrazem na pochopení principů.
Charakteristika operačního systému
Operační systém (OS) je ten nejzákladnější software, který na počítači vůbec existuje – je to vrstva, bez které by hardware byl jen bezcenný kus elektroniky. Abychom skutečně pochopili, co operační systém je a proč existuje, musíme nejdřív pochopit problém, který řeší.
Představte si, že byste chtěli napsat program, který jednoduše zobrazí text na obrazovce. Bez operačního systému byste museli přesně vědět, jaký grafický čip je v počítači, jakou má sběrnici, kde leží paměťová mapa jeho registrů, jak inicializovat monitor a podobně. To by byl jiný kód pro každý počítač. Operační systém tuto složitost skrývá za jednotné rozhraní – tzv. abstrakci.
Tři klíčové role operačního systému
Operační systém plní tři vzájemně propojené role, které je důležité rozlišovat:
1. Správce prostředků (Resource Manager): Moderní počítač má jeden procesor (nebo jejich omezený počet), omezenou RAM, jeden disk. Zároveň ale běží desítky nebo stovky programů najednou – nebo alespoň zdánlivě najednou. Operační systém rozhoduje, který program smí právě teď používat CPU, kolik paměti dostane každý proces, a jak se sdílí přístup k disku. Bez této správy by programy bojovaly o prostředky a celý systém by zkolaboval.
2. Abstrakce hardwaru: OS vytváří virtuální „stroj" pro každý program. Program nevidí skutečný hardware – vidí abstrakci. Nevidí fyzické sektory na disku, vidí soubory. Nevidí fyzické adresy v RAM, vidí lineární adresový prostor. Díky tomu je tentýž program spustitelný na různém hardwaru, pokud mají stejné OS.
3. Prostředí pro uživatele: OS poskytuje rozhraní – ať už grafické (GUI) nebo příkazové (CLI) – které umožňuje člověku se strojem komunikovat. Bez tohoto rozhraní by byl počítač pro běžného uživatele nepoužitelný.
Hlavní funkce OS – podrobněji
| Funkce | Co konkrétně OS dělá | Proč je to důležité |
|---|---|---|
| Správa procesů | Vytváří, plánuje, přerušuje a ukončuje procesy. Přiděluje každému procesu čas CPU. | Umožňuje multitasking – zdánlivé souběžné běžení více programů. |
| Správa paměti | Přiděluje a uvolňuje RAM, implementuje virtuální paměť a stránkování. | Každý program dostane vlastní chráněný prostor; programy se nemohou navzájem přepsat. |
| Správa souborů | Organizuje data na discích do souborů a adresářů. Řídí přístupová práva. | Data jsou persistentní a organizovaná; vícero uživatelů může data sdílet nebo chránit. |
| Správa I/O | Komunikuje s ovladači zařízení (drivery). Abstrauje vstupní a výstupní zařízení. | Programy nemusí znát hardware – OS jim dá jednotné API. |
| Bezpečnost | Autentizace uživatelů, ochrana paměti, řízení přístupu. | Zabraňuje neoprávněnému přístupu k datům a prostředkům. |
| Síťová komunikace | Implementuje síťové protokoly, spravuje sockety a síťová spojení. | Programy mohou komunikovat po síti přes jednotné rozhraní. |
Operační systém je jako ředitel velké firmy. Zaměstnanci (programy) přicházejí s požadavky – potřebují kancelář (paměť), čas manažera (CPU), přístup k archivu (disk). Ředitel rozhoduje, kdo dostane co a kdy, tak aby firma fungovala hladce a nikdo nikoho nerušil při práci. Bez ředitele by byl chaos.
Historický vývoj OS
Pochopení vývoje operačních systémů nám pomáhá pochopit, proč jsou dnešní OS takové, jaké jsou. Každá generace řešila konkrétní problémy a nevýhody té předchozí. Pojďme si projít klíčové epochy.
Generace 1 – Bez OS (40. léta)
Prvních počítačů jako ENIAC bylo na světě jen pár a programátor s ním pracoval přímo – fyzicky přepojoval kabely a přepínal přepínače. Neexistoval žádný operační systém, žádný software jako takový. Programy se zadávaly v binárním kódu přímo do hardware. Bylo to extrémně pomalé a náchylné k chybám – přepojení jednoho kabelu trvalo hodiny.
Člověk byl svázán s fyzickým strojem. Pokud programátor pracoval, CPU nic nepočítal – čekal. CPU (tehdy drahý prostředek) byl vytížen jen zlomek doby.
Generace 2 – Dávkové zpracování / Batch processing (50. léta)
Přišly děrné štítky a magnetické pásky. Programy se připravily předem, odevzdaly operátorovi, a ten je spouštěl hromadně (v dávce) bez lidské interakce. Systém sám přecházel od jedné úlohy k druhé – to byl zárodek prvního OS. Typické systémy: IBM OS/360, GM-NAA I/O.
Problém zůstával: pokud jeden program čekal na I/O operaci (čtení z disku), CPU zůstával nečinný. Vytíženost CPU byla stále nízká.
Generace 3 – Multiprogramming a timesharing (60. léta)
Multiprogramming znamená, že v paměti je najednou více programů. Když jeden čeká na I/O, CPU přeskočí na jiný. Tím se dramaticky zvýšilo využití CPU – místo 20 % třeba 70–80 %.
Timesharing (sdílení času) přidal interaktivitu: každý uživatel dostal malý časový kvantum a CPU se rychle přepínal. Uživateli to připadalo jako by měl počítač jen pro sebe. Vznikly systémy jako CTSS a MULTICS. Z MULTICS se pak vyvinul UNIX.
UNIX a jeho rodokmen
UNIX vznikl v roce 1969 v Bellových laboratořích (Ken Thompson, Dennis Ritchie). Byl přepsán do jazyka C (1973), což bylo revoluční – operační systém v přenositelném jazyce, nikoli jen v assembleru. UNIX zavedl koncepty jako hiearchický souborový systém, pipes, procesy a práva, které se používají dodnes.
Vývoj Windows
Microsoft Windows začaly jako grafická nadstavba DOS (1985). Až Windows NT (1993) přinesl skutečný 32bitový OS s ochranou paměti, oddělením procesů a robustní architekturou. Windows XP (2001) sjednotil domácí a firemní větev. Windows Vista (2007), 7, 8/8.1, 10 a Windows 11 (2021) postupně přinášely vylepšení v oblasti bezpečnosti, UI a výkonu.
Vývoj macOS
Apple začal s proprietárním Mac OS (1984), který byl průkopnický svým GUI. V roce 2001 přešel Apple na macOS X – hybridní jádro XNU postavené na základech Machu a BSD. Od té doby OS X / macOS prošel řadou verzí pojmenovaných po kočkovitých šelmách (Tiger, Leopard…) a poté po kalifornských místech (El Capitan, Sierra, Monterey…).
Vývoj Android
Android (2008, Google) je mobilní OS postavený na linuxovém jádře. Vznikl, aby poskytl otevřenou platformu pro chytré telefony. Rychle se rozšířil a dnes pohání drtivou většinu chytrých telefonů. Verze jsou pojmenovávány abecedně – Cupcake, Donut, Eclair... až po Android 14 (Upside Down Cake).
Typy jader OS
Jádro (kernel) je srdce operačního systému – ta část, která běží s nejvyššími privilegii a přímo komunikuje s hardwarem. To, jak je jádro navrženo, zásadně ovlivňuje výkon, stabilitu a flexibilitu celého systému. Existují čtyři hlavní architektury jader, každá s jiným přístupem k tomu, co „patří" do jádra a co ne.
Monolitické jádro (Monolithic Kernel)
V monolitickém jádru běží veškeré systémové služby v jednom velkém bloku kódu ve stejném adresovém prostoru s plnými privilegii. Zahrnuje to správu paměti, plánovač procesů, systém souborů, síťový stack, ovladače zařízení – vše pohromadě.
Výhoda je rychlost: všechny komponenty mohou přímo volat jedna druhou bez nutnosti přechodu mezi různými ochranami (kontextových přepnutí). Komunikace je přímá – funkce zavolá jinou funkci.
Nevýhoda je robustnost: chyba v jednom ovladači (třeba vadný ovladač tiskárny) může srazit celý systém, protože vše běží ve stejném prostoru. Jádro je také složité na údržbu a ladění.
Linux, starší verze UNIXu. Přestože Linux technicky přidává moduly dynamicky (LKM – Loadable Kernel Modules), stále se považuje za monolitické jádro, protože moduly jsou načítány do prostoru jádra.
Mikrojádro (Microkernel)
Mikrojádro se řídí opačnou filozofií: do privilegovaného prostoru jádra patří jen to nejnezbytněší – typicky správa paměti, meziprocesová komunikace (IPC) a základní plánování procesů. Všechno ostatní (souborový systém, ovladače, síť) běží jako oddělené procesy v uživatelském prostoru.
Výhoda je stabilita a bezpečnost: pokud selže ovladač, nespadne celý systém – ovladač běží jako oddělený proces, který lze restartovat. Systém je modulárnější a snáze testovatelný.
Nevýhoda je výkon: komunikace mezi komponentami probíhá přes IPC zprávy, což je pomalejší než přímé volání funkcí v monolitickém jádru. Každý systémový požadavek vyžaduje přechod mezi režimy a zasílání zpráv.
MINIX, QNX (používaný v embedded systémech a automobilech), Mach (základ macOS). L4 je moderní rodina mikrojader používaná ve výzkumu a bezpečnostních systémech.
Hybridní jádro (Hybrid Kernel)
Hybridní jádro se snaží vzít to nejlepší z obou světů. Většina kódu běží v prostoru jádra (jako monolitické) pro výkon, ale architektura je navržena tak, aby byla více modulární (jako mikrojádro). Některé ovladače nebo služby mohou běžet odděleně.
Windows NT (a všechny moderní Windows), macOS XNU (kombinuje Mach mikrojádro a BSD monolitický kód), BeOS.
Exojádro (Exokernel) a Unikernel
Exojádro jde ještě dál než mikrojádro – snaží se přidělit hardware přímo aplikacím a přesunout veškerou abstrakci do uživatelského prostoru. Aplikace si samy implementují systémové abstrakce, které potřebují. Tento přístup je extrémně výkonný, ale také extrémně složitý na programování. Zatím zůstává hlavně v akademické sféře.
Unikernel je specializovaný OS pro cloudové prostředí: jádro a aplikace jsou zkompilované do jediného obrazu bez zbytečných komponent. Výsledek je extrémně malý, rychlý a bezpečný (menší plocha útoku). Využívá se pro specifické cloudové mikroservisy.
| Typ jádra | V privilegovaném prostoru | Výkon | Stabilita | Příklady |
|---|---|---|---|---|
| Monolitické | Vše (ovladače, FS, síť, správa paměti…) | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ | Linux, classic UNIX |
| Mikrojádro | Pouze IPC, správa paměti, základní plánování | ⭐⭐⭐ | ⭐⭐⭐⭐⭐ | MINIX, QNX, Mach |
| Hybridní | Většina, ale modulárně navržena | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | Windows NT, macOS XNU |
| Exojádro | Jen přidělování HW | ⭐⭐⭐⭐⭐ | ⭐⭐ | Výzkumné (MIT) |
Režimy jádra
Moderní procesory (a tedy i OS) pracují ve dvou základních privilegovaných úrovních – tzv. režimech. Toto rozdělení existuje z bezpečnostních důvodů: nelze nechat každý program přistupovat přímo k hardwaru, protože by mohl narušit chod jiných programů nebo celého systému.
Kernel Mode (Privilegovaný/Jádrový režim)
V kernel mode (jádrovém režimu) má kód přímý přístup ke všemu hardwaru. Může zapisovat kamkoli do paměti, přistupovat k I/O portům, nastavovat řadiče přerušení a měnit tabulky stránek paměti. Není tam žádná ochrana – kód může udělat cokoli.
V tomto režimu běží samotné jádro OS a ovladače (drivery). Chyba zde = modrá obrazovka (BSOD na Windows) nebo kernel panic (Linux). Proto je kód jádra tolik testován a revidován.
User Mode (Uživatelský režim)
V user mode (uživatelském režimu) jsou programy omezeny – nemají přímý přístup k hardwaru. Pokud program chce přistoupit na disk, k síti, do paměti jiného procesu nebo k jinému zařízení, musí požádat OS prostřednictvím systémového volání (syscall).
Toto je klíčová ochrana: pokud program selže nebo se pokusí udělat zakázanou operaci, OS to zachytí a ukončí pouze ten jeden proces, aniž by zasáhl zbytek systému.
- Přímý přístup k hardwaru
- Přístup k celé fyzické paměti
- Spouštění privilegovaných instrukcí
- Nastavování přerušení a časovačů
- Běží zde: jádro OS, ovladače
- Omezený přístup – jen přidělené prostředky
- Vlastní virtuální adresový prostor
- Zakázané privilegované instrukce
- Přístup k HW jen přes syscally
- Běží zde: aplikace, knihovny
Systémové volání (System Call / Syscall)
Systémové volání je mechanismus, jak uživatelský program legálně požádá jádro o privilegovanou operaci. Funguje takto: program zavolá wrapper funkci standardní knihovny (např. read() v C), ta přepne CPU do kernel mode speciální instrukcí (na x86 dříve int 0x80, dnes syscall), jádro provede operaci a vrátí výsledek, poté se CPU přepne zpět do user mode.
Tento přechod (user → kernel → user) trvá typicky desítky až stovky nanosekund a je relativně nákladný. Proto se programy snaží minimalizovat počet syscallů – například bufferovaný I/O v knihovnách shromažďuje data a dělá syscall až při zaplnění bufferu.
User mode je jako pracovat v otevřeném kancelářském prostoru – máte přístup ke svému stolu, ale ne do archívu nebo k technické místnosti. Kernel mode je jako být správcem budovy – máte klíče ode všeho. Systémové volání je jako žádat recepčního (OS), aby pro vás z archívu něco vytáhl.
Ochranné kruhy (Protection Rings)
Procesory Intel/AMD ve skutečnosti implementují až 4 úrovně ochrany – tzv. rings (kruhy), označené Ring 0 až Ring 3. Ring 0 má nejvyšší privilegia (jádro OS), Ring 3 nejnižší (uživatelské aplikace). Ringy 1 a 2 existují, ale v praxi je moderní OS většinou nepoužívají. V kontextu virtualizace se někdy mluví o Ring -1 (hypervisor).
Proces vs. vlákno
Toto je jedno z nejdůležitějších a nejčastěji zkoušených témat v oblasti OS. Zaměňovat procesy a vlákna je běžná chyba – proto jim věnujme dostatečnou pozornost.
Co je proces?
Proces je spuštěný program – konkrétní instance programu běžící v systému. Když spustíte prohlížeč dvakrát, vzniknou dva procesy. Každý proces je od ostatních izolován a má svůj vlastní:
- virtuální adresový prostor – vlastní „pohled" na paměť, chráněný před ostatními procesy
- kód a data – zkopírovaná instance spustitelného souboru
- zásobník (stack) – pro lokální proměnné a volání funkcí
- haldu (heap) – dynamicky alokovanou paměť
- otevřené soubory a sokety
- PID (Process ID) – unikátní identifikátor v rámci OS
- přidělené prostředky – přidělená CPU kvanta, priorita, limity
Klíčová vlastnost procesu je izolace: jeden proces nemůže přímo přistupovat do paměti jiného procesu. To je záměrné a žádoucí – zabraňuje to náhodným kolizím i záměrným útokům.
Životní cyklus procesu
Proces během svého „života" prochází různými stavy. Porozumění těmto stavům je klíčem k pochopení toho, jak OS spravuje více procesů najednou.
| Stav | Co znamená | Příčina přechodu |
|---|---|---|
New (Nový) | Proces byl právě vytvořen, inicializují se jeho datové struktury | Volání fork(), CreateProcess() |
Ready (Připravený) | Proces je připraven běžet, čeká na přidělení CPU | Inicializace hotova, I/O dokončeno, čas vypršel jinému procesu |
Running (Běžící) | Proces právě dostává čas CPU a vykonává instrukce | Plánovač vybral tento proces z fronty Ready |
Waiting/Blocked (Čekající) | Proces čeká na externísněvu – I/O, signál, semafor | Proces zavolal I/O operaci, čeká na mutex |
Terminated (Ukončený) | Proces skončil (normálně nebo chybou), uvolňují se zdroje | exit(), zabití signálem, chyba |
Plánovač OS neustále vybírá z fronty Ready procesů ten, který dostane CPU. Přechod Running → Ready nastane buď když vypršel časový kvantum (preemptivní plánování) nebo když proces sám odvolá CPU. Přechod Running → Waiting nastane, když proces potřebuje čekat na něco mimo CPU (typicky I/O).
PCB – Process Control Block
Každý proces má v jádru OS svou datovou strukturu nazvanou PCB (Process Control Block). Je to jako „rodný list" nebo „zdravotní karta" procesu – obsahuje vše, co OS o procesu potřebuje vědět, aby ho mohl správně spravovat a obnovit po přerušení.
| Pole PCB | Obsah a smysl |
|---|---|
| PID | Unikátní identifikátor procesu v systému |
| Stav procesu | New / Ready / Running / Waiting / Terminated |
| Program Counter (PC) | Adresa příští instrukce k vykonání – ukládá se při přerušení, obnovuje při obnovení |
| Obsah registrů CPU | Všechny hodnoty všech registrů CPU v okamžiku přerušení (AX, BX, SP, FLAGS…) |
| Informace o paměti | Záznamy o tabulkách stránek, hranicích segmentů – kde leží paměť procesu |
| Informace o I/O | Seznam otevřených souborů a zařízení, čekající I/O požadavky |
| Informace o plánování | Priorita procesu, statistiky využití CPU, čas ve frontě |
| Účetní informace | Celkový využitý CPU čas, čas startu, limity |
PCB je tak důležitý, protože při přepnutí kontextu (viz dále) OS uloží celý stav CPU do PCB aktuálního procesu a obnoví stav CPU z PCB nového procesu. Bez PCB by nebylo možné „zastavit" jeden proces a „pokračovat" s druhým.
Co je vlákno (Thread)?
Vlákno je lehčí jednotka výpočtu uvnitř procesu. Jeden proces může mít jedno nebo více vláken. Všechna vlákna v rámci jednoho procesu sdílejí adresový prostor, kód, haldu a otevřené soubory svého procesu. Co si každé vlákno drží vlastní, je svůj zásobník (stack) a Program Counter.
Proč vlákna existují? Protože vytváření nového procesu je drahé – OS musí alokovat nový adresový prostor, zkopírovat stránkovací tabulky, nastavit PCB. Vlákno je mnohem levnější na vytvoření, protože sdílí prostředky s rodičovským procesem.
TCB – Thread Control Block
Analogicky k PCB pro procesy, každé vlákno má svůj TCB (Thread Control Block). Ten obsahuje podobné informace jako PCB, ale jen to, co je vlastní vláknu – ID vlákna, Program Counter, obsah registrů, stav vlákna a ukazatel na zásobník. TCB je menší a jednodušší než PCB.
- PID, stav procesu
- Celý adresový prostor (paměťové mapy)
- Otevřené soubory a I/O zdroje
- Program Counter a registry
- Priorita a účetní informace
- TID, stav vlákna
- Vlastní zásobník (stack pointer)
- Program Counter
- Obsah registrů CPU
- Odkaz na nadřazený PCB
Vlákna na uživatelské vs. jádrové úrovni
Vlákna mohou být implementována na dvou různých úrovních:
Vlákna na uživatelské úrovni (User-level threads) jsou spravována výhradně v uživatelském prostoru pomocí knihovny pro vlákna (thread library). OS o nich neví – z pohledu jádra jde stále o jeden proces. Přepínání vláken je velmi rychlé (není potřeba syscall), ale pokud jedno vlákno zavolá blokující operaci, zablokuje se celý proces.
Vlákna na úrovni jádra (Kernel-level threads) jsou spravována přímo jádrem OS. OS ví o každém vláknu a může je plánovat na různých CPU jádrech nezávisle. Blokování jednoho vlákna nezablokuje ostatní. Nevýhoda je vyšší overhead – každé přepnutí vlákna vyžaduje syscall.
| Vlastnost | Uživatelská vlákna | Jádrová vlákna |
|---|---|---|
| Rychlost přepnutí | Velmi rychlé (bez syscall) | Pomalejší (vyžaduje syscall) |
| Blokující I/O | Zablokuje celý proces | Zablokuje jen dané vlákno |
| Paralelismus na více CPU | Ne – OS plánuje jen 1 proces | Ano – vlákna na různých CPU |
| OS awareness | OS vlákna nevidí | OS vlákna spravuje |
| Příklady | Green threads (Python, starší Java) | POSIX pthreads, Windows threads |
Přepínání kontextu
Přepnutí kontextu (context switch) je mechanismus, díky kterému má uživatel pocit, že počítač dělá více věcí najednou. Ve skutečnosti se CPU velmi rychle přepíná mezi procesy (nebo vlákny), takže pro člověka vypadá vše jako paralelní běh. Pochopení tohoto mechanismu je klíčové pro plánování procesů.
Jak přepnutí kontextu probíhá?
Představte si, že CPU zrovna vykonává Proces A. Přijde přerušení (interrupt) od časovače – tzv. timer interrupt. CPU přestane vykonávat Proces A a předá řízení jádru. Jádro uloží celý stav Procesu A do jeho PCB (program counter, všechny registry, SP…). Poté vybere plánovač (scheduler) nový proces – třeba Proces B. Z PCB Procesu B jádro obnoví jeho stav (registry, PC, atd.) do skutečného CPU. Následně CPU začne vykonávat Proces B od místa, kde naposledy skončil.
Přepnutí kontextu stojí čas – typicky 1–100 mikrosekund v závislosti na CPU a velikosti dat k uložení. Navíc dochází ke ztrátě cache locality: když CPU přechází na jiný proces, obsah CPU cache (L1, L2) je pro nový proces irelevantní a musí se naplnit znovu. To způsobuje tzv. cache miss penalty. Proto příliš časté přepínání (příliš krátké kvanty) snižuje celkový výkon systému.
Přepnutí kontextu vláken vs. procesů
Přepnutí kontextu mezi vlákny téhož procesu je levnější než přepnutí mezi procesy. Proč? Protože vlákna sdílejí adresový prostor – není třeba měnit tabulky stránek (page tables). Stačí uložit/obnovit zásobník a registry vlákna. Přepnutí procesů naproti tomu vyžaduje i přepnutí TLB (Translation Lookaside Buffer) a stránkovacích tabulek, což je časově nákladnější.
Plánovače OS
OS neobsahuje jeden plánovač, ale typicky tři – každý pracuje na jiné časové škále a s jiným cílem. Pochopení rozdílu mezi nimi je klíčové.
Dlouhodobý plánovač (Long-term / Job Scheduler)
Dlouhodobý plánovač rozhoduje, které procesy ze vstupní fronty (job queue) budou vůbec připuštěny do systému a načteny do paměti (přejdou do stavu Ready). Pracuje řádově v sekundách až minutách – zasahuje jen občas. Cílem je udržet vyvážený mix CPU-bound a I/O-bound procesů v systému, aby byl CPU i I/O systém vytížen rovnoměrně. V moderních systémech pro interaktivní použití (Windows, Linux desktop) je dlouhodobý plánovač většinou absent nebo minimalizován – procesy se spouštějí ihned.
Krátkodobý plánovač (Short-term / CPU Scheduler)
Krátkodobý plánovač je tím, o čem se hovoří, když se řekne „plánovač". Vybírá z fronty připravených procesů (Ready Queue) ten, který dostane CPU. Pracuje velmi rychle – stovky milisekund až mikrosekundy. Rozhoduje, který algoritmus se použije (FCFS, RR, SJF…). Je volán při každém přepnutí kontextu, tedy velmi často.
Střednědobý plánovač (Medium-term Scheduler)
Střednědobý plánovač implementuje swapping – pokud je paměť plná, dočasně přesune celý proces z RAM na disk (swap prostor) a uvolní paměť pro jiné procesy. Takový proces je suspended (pozastaven). Když se uvolní paměť nebo si to jinak vyžadují podmínky, proces se vrátí zpět do RAM (swap-in). Pracuje v řádu sekund.
Preemptivní vs. nepreemptivní plánování
Toto je zásadní dělení pro pochopení chování plánovačů:
- OS může proces přerušit kdykoli, i uprostřed výpočtu
- Přerušení typicky probíhá po vypršení časového kvantu (timer interrupt)
- Zaručuje spravedlnost – žádný proces nemůže monopolizovat CPU
- Lepší pro interaktivní systémy (rychlá odezva)
- Příklady: RR, SRTF, MFQS
- Nevýhoda: overhead přepínání kontextu
- Proces drží CPU, dokud sám neskončí nebo nečeká na I/O
- OS nemůže procesu vzít CPU násilím
- Jednodušší implementace, méně overhead
- Hrozí starvation – jeden dlouhý proces blokuje ostatní
- Příklady: FCFS, SJF (nepreemptivní varianta)
- Vhodné pro dávkové systémy
Nepreemptivní plánování je jako přednáška kde každý dostane mikrofon a mluví, dokud neskončí. Preemptivní je jako debata s moderátorem, který po 2 minutách bere mikrofon dál – nikdo nemůže mluvit donekonečna, každý dostane spravedlivý prostor.
Kritéria hodnocení plánovačů
Jak poznáme, že jeden plánovač je lepší než jiný? Existuje sada metrik, které se sledují:
| Metrika | Definice | Chceme |
|---|---|---|
| CPU Utilization | Procentuální využití CPU (čas CPU pracuje / celkový čas) | Maximalizovat (ideálně 100 %) |
| Throughput | Počet procesů dokončených za jednotku času | Maximalizovat |
| Turnaround Time | Čas od příchodu procesu do jeho dokončení | Minimalizovat |
| Waiting Time | Celkový čas procesu strávený ve frontě Ready | Minimalizovat |
| Response Time | Čas od příchodu požadavku do první odpovědi systému | Minimalizovat (klíčové pro interaktivní systémy) |
Waiting Time = Turnaround Time − Burst Time (doba aktivního výpočtu)
Plánovací algoritmy
Teď se dostáváme k samotným algoritmům. Každý z nich je odpovědí na otázku: „Kdo dostane CPU jako další?" Každý má jiné priority, silné stránky a slabiny. Pro každý algoritmus si ukážeme principy, Ganttův diagram a výpočet klíčových metrik.
Pro příklady budeme používat tuto sadu procesů (pokud není uvedeno jinak):
| Proces | Příchod (Arrival Time) | CPU burst (délka výpočtu) |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
FCFS – First Come, First Served
FCFS (First Come, First Served) je nejjednodušší plánovací algoritmus vůbec – procesy dostávají CPU v tom pořadí, v jakém přišly. Kdo přijde první, jde první. Je to jak fronta na poště: nikdo nepředbíhá.
Typ: Nepreemptivní – jakmile proces dostane CPU, drží ho, dokud neskončí nebo nečeká na I/O.
Implementace: Fronta (FIFO queue). Nové procesy se přidávají na konec, CPU dostává vždy první v řadě.
| Proces | Příchod | Burst | Start | Dokončení | Turnaround | Waiting |
|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 0 | 8 | 8 | 0 |
| P2 | 1 | 4 | 8 | 12 | 11 | 7 |
| P3 | 2 | 9 | 12 | 21 | 19 | 10 |
| P4 | 3 | 5 | 21 | 26 | 23 | 18 |
| Průměr | 15.25 | 8.75 | ||||
Problém konvoje (Convoy Effect): Nejzásadnější slabina FCFS. Pokud přijde jako první jeden velmi dlouhý proces, všechny krátké procesy za ním musí čekat. Je to jako kdyby se na silnici za pomalým traktorem vytvořilo dlouhé kolony aut, i kdyby každé z nich potřebovalo jet jen chvíli. Průměrná čekací doba je tak zbytečně vysoká.
Představte si P1 s burst=100, P2 s burst=1, P3 s burst=1. Pokud přijdou v tomto pořadí, P2 a P3 čekají 100 časových jednotek, i když by stačily 2. Průměrná čekací doba = (0 + 100 + 101) / 3 = 67. Přitom kdyby šly nejprve krátké procesy: (0 + 1 + 2) / 3 = 1. Rozdíl je dramatický!
SJF – Shortest Job First
SJF (Shortest Job First) řeší Convoy Effect elegantně: vždy vybere z fronty Ready proces s nejkratším CPU burstem. Krátké procesy jdou napřed, dlouhé čekají.
Typ: Nepreemptivní (v základní verzi) – existuje i preemptivní varianta SRTF (viz níže).
SJF je optimální z hlediska průměrné čekací doby pro dávkové systémy – lze dokázat, že žádný jiný algoritmus nemůže dosáhnout nižší průměrné čekací doby. Proč? Protože umísťuje krátké procesy před dlouhé, čímž minimalizuje celkovou čekací dobu – analogické s optimalizací objednávek v bufetu.
Zásadní problém SJF: Jak víme, jak dlouhý burst proces bude mít? V praxi to nevíme předem! Délku burstu lze pouze odhadovat – typicky pomocí exponenciálního průměrování (aging): odhad pro příště = α × skutečný minulý burst + (1-α) × předchozí odhad. Tímto způsobem se starší hodnoty postupně zapomínají.
kde tn = skutečný n-tý burst, τn = předchozí odhad, α ∈ (0,1) = váha nového měření
Procesy s dlouhým burstem mohou čekat donekonečna, pokud stále přicházejí kratší procesy. Toto se nazývá starvation (vyhladovění). Řešením je aging – priorita procesu se s časem zvyšuje, takže i dlouhé procesy se nakonec dostanou na řadu.
SRTF – Shortest Remaining Time First
SRTF (Shortest Remaining Time First) je preemptivní verze SJF. Kdykoli přijde nový proces, algoritmus porovná jeho burst s zbývajícím časem aktuálně běžícího procesu. Pokud má nový proces kratší zbývající čas, probíhá přepnutí – nový proces přeruší stávající.
Typ: Preemptivní
SRTF je optimální v preemptivním světě – minimalizuje průměrnou čekací dobu ze všech preemptivních algoritmů. Platí stejný problém jako u SJF: neznáme délku burstu předem. A navíc přibývá overhead přepínání kontextu při každém příchodu nového procesu.
RR – Round Robin
Round Robin je nejpoužívanějším algoritmem v moderních interaktivních OS. Každý proces dostane pevně stanovenou časovou dávku – tzv. časové kvantum (time quantum, q), typicky 10–100 ms. Po vypršení kvantu je proces preemptivně přerušen a přesunut na konec kruhové fronty. CPU pak dostane další proces v pořadí.
Typ: Preemptivní
Název „Round Robin" pochází z anglického výrazu pro rotaci – jako když se v kruhu střídají hráči. Každý proces dostane svoji „chvilku", pak musí počkat, až dojde znovu na řadu.
Klíčová volba: délka kvantu. Toto je zásadní parametr, který určuje chování systému:
- Velmi rychlé přepínání = dobrá interaktivita
- Obrovský overhead přepínání kontextu
- Většinu času tráví OS přepínáním, ne výpočtem
- V extrému se chová jako sdílení přesně na mikrosekundy
- Procesy doběhnou bez přerušení = žádný overhead
- Špatná interaktivita – uživatel čeká
- Degeneruje na FCFS
- Convoy effect se vrací
Optimální kvantum je takové, aby bylo větší než 80 % CPU burstů – pak většina procesů doběhne v jednom kvantu a zbytečné přepínání je minimální. V praxi se volí 10–20 ms pro interaktivní OS.
PS – Priority Scheduling (Prioritní plánování)
Priority Scheduling přidává ke každému procesu prioritu (číslo). CPU vždy dostane proces s nejvyšší prioritou. Pokud mají dva procesy stejnou prioritu, obvykle se použije FCFS jako tiebreaker.
Typ: Může být Nepreemptivní i Preemptivní. V preemptivní variantě: příchod procesu s vyšší prioritou přeruší aktuálně běžící proces.
Priority mohou být:
- Interní (static) – stanoveny při startu procesu a nemění se (např. real-time priority, nice hodnota v Linuxu)
- Externí (dynamic/aging) – mění se v čase; typicky se priorita zvyšuje, čím déle proces čeká (aging / stárnutí), aby se zabránilo starvation
Konvence priorit se v různých systémech liší: v některých znamená nižší číslo vyšší prioritu (Linux: -20 = nejvyšší, +19 = nejnižší), v jiných je to naopak.
Čistý Priority Scheduling bez agingu trpí starvation – procesy s nízkou prioritou mohou čekat donekonečna, pokud stále přicházejí procesy s vyšší prioritou. Aging (stárnutí) řeší tento problém: každých X sekund čekání se priorita procesu zvýší o 1. Tím se zaručí, že každý proces se dříve nebo později dostane na řadu.
MFQS – Multilevel Feedback Queue Scheduling
MFQS (Multilevel Feedback Queue Scheduling) je nejsložitější a zároveň nejrealističtější plánovací algoritmus. Používají ho moderní OS jako základ jejich plánovačů (Linux CFS, Windows dispatcher). Kombinuje výhody RR, Priority Scheduling a SJF do jednoho adaptivního systému.
Typ: Preemptivní
Princip: Existuje více front, každá s jinou prioritou a jiným kvántem. Nový proces nastoupí do fronty s nejvyšší prioritou a krátkým kvántem. Pokud nevyčerpá kvantum (= skončil dřív = jde pravděpodobně o krátký/interaktivní proces), může být odměněn. Pokud kvantum vyčerpá (= potřebuje hodně CPU = pravděpodobně CPU-bound), sestoupí do fronty s nižší prioritou a delším kvántem.
Chytrost MFQS spočívá v tom, že nepotřebuje znát délku burstu předem (jako SJF). Místo toho se učí za běhu: procesy, které rychle vzdají CPU (interaktivní, I/O-bound), zůstávají nahoře a mají rychlou odezvu. Procesy, které CPU spotřebovávají naplno (výpočetně náročné, CPU-bound), postupně klesají do nižších front s větším kvántem – dostanou méně priority, ale efektivnější přidělení CPU.
Zpětná mobilita (Feedback): Slovo „Feedback" v názvu označuje, že procesy se mohou pohybovat nejen dolů, ale i nahoru. Pokud CPU-bound proces začne vykazovat interaktivní chování (kratší bursts), může být povýšen zpět do vyšší fronty. Přesná pravidla pohybu jsou konfigurovatelná a různé OS je implementují různě.
Konfigurovatelné parametry MFQS: Počet front, algoritmus v každé frontě, délka kvantu pro každou frontu, pravidla pro sestup a vzestup procesů, metoda určení počáteční fronty pro nový proces.
Srovnání všech plánovacích algoritmů
Nejjednodušší – procesy ve frontě pořadí příchodu. Žádné přerušení.
⛔ Convoy Effect, špatná odezva
Nejkratší burst jde první. Optimální průměrná čekací doba pro dávkové systémy.
⛔ Neznáme délku burstu předem. Starvation.
Preemptivní SJF – nový proces přeruší běžící, pokud má kratší zbývající čas.
⛔ Starvation, odhad burstu, overhead
Každý dostane kvantum a pak jde na konec fronty. Spravedlivý a vhodný pro interaktivní systémy.
⚙️ Výkon závisí na délce kvantu
Každý proces má prioritu. Vyšší priorita = přednostní přístup k CPU.
⛔ Starvation bez agingu
Více front s různou prioritou a kvántem. Procesy se učí svou kategorii za běhu.
✅ Nejreálnější. Používají moderní OS.
| Algoritmus | Preemptivní | Starvation | Vhodný pro | Průměrná čekací doba |
|---|---|---|---|---|
| FCFS | Ne | Ne | Dávkové systémy | Vysoká (convoy effect) |
| SJF | Ne | Ano | Dávkové systémy | Optimální (nepreemptivní) |
| SRTF | Ano | Ano | Dávkové systémy | Optimální (preemptivní) |
| RR | Ano | Ne | Interaktivní systémy | Závisí na kvantu |
| PS | Oboje | Ano (bez agingu) | Real-time, smíšené | Závisí na prioritách |
| MFQS | Ano | Možná (řeší aging) | Moderní GP OS | Adaptivní – nejlepší v praxi |