Procesy, synchronizace, Coffman

BI-SPOL.21-17
  • Procesy
    • Implementace
  • Vlákna
    • Implementace
  • Nástroje pro 03.1 Synchronizace vláken
  • Klasické synchronizační úlohy
  • Deadlock
    • Alokace prostředků
    • Coffmanovy podmínky
    • Strategie pro řešení uváznutí
  • Program -> v systému reprezentovaný spustitelným binárním souborem, uloženým na disku
  • Proces -> instance spuštěného programu. Entita v rámci které jsou alokovány prostředky (paměť, periferie, vlákna, soubory)
  • Vlákno -> výpočetní entita, která vykonává instrukce a je plánovaná na CPU. Vlákna v jednom procesu sdílí většinu alokovaných prostředků.

Vytvoření procesu

Nový proces lze vytvořit jako klon původního procesu, nebo jako úplně nový proces. ve Windows CreateProcessA() v Linuxu

  • Fork() vytvoří nový klon aktuálního procesu. vrací -1 při chybě, v rodiči PID potomka a v potomkovi 0.
  • exec() přepíše aktuální proces novým a začne ho vykonávat od začátku.
  • wait() zablokuje rodiče, dokud se potomek neukončí

Implementace procesů

  • Jádro OS si udržuje spojový seznam struktur -> Tabulku procesů
  • Jedna položka tabulky ukládá všechny nutné informace o procesu (PCB)
    • identifikace (PID, parent ID, jméno procesu,...)
    • identita (vlastní, oprávnění, skupina)
    • informace o alokovaných prostředcích (paměť soubory, mezi procesorová komunikace)

Ukončení procesu

  • Jádro se pokusí předat návratový kód rodiči
  • Ukončí všechna vlákna pod procesem
  • Uvolní paměť a OS struktury
  • Proces se buď ukončí sám (return, error) nebo ho zabije jádro (segfault)

Vlákna

  • Proces se vytváří s jedním main vláknem
  • Další vlákna lze vytvořit voláním OS

Implementace vláken

  • Thread Control Block - identifikace vlákna,
    • Informace o přepínání kontextu(změna registrů a security ringů 0-3),
    • Adresa zásobníku
    • Informace pro plánovač (priorita, čas na CPU)
  • Implementace v Userspace (zastaralé)
    • OS přistupuje k procesům jako by měli jedno vlákno
    • Každý proces si vlákna spravuje sám
    • Plánovaní uvnitř procesu
  • Implementace v jádře OS
    • OS plánuje samotná vlákna
    • OS udržuje jeden PCB @ proces a jeden TCB @ vlákno
    • Preemptivní plánovaní pro vlákna v procesu
  • Stavy vláken
    • Idle -> nové vlákno
    • Ready -> čeká na CPU
    • Running -> běží na CPU
    • Blocked -> čeká na událost (není plánováno)
    • Zombie -> ukončování vlákna
    • Free -> zrušení vlákna
      Pasted image 20260608125914.png

Plánování vláken

Plánování vláken

V okamžiku, kdy se uvolní jádro CPU, musí OS vybrat „vhodné“ vlákno ve stavu „ready“, a umožní mu používat toto jádro po určitou dobu

Přepínání kontextu

Mechanismus, při kterém se vlákna vystřídají v používání jádra CPU

  • Kontext = všechny nezbytné inf. nutné pro pozdější spuštění přeruš. vlákna od okamžiku přerušení
    1. Uloží se kontext původního vlákna
    2. Jádro OS naplánuje další vlákno
    3. Nastaví se kontext tohoto vlákna

Plánovací algoritmy

  • Plánování s odnímáním (preemptive scheduling)
    • Jádro OS přidělí vláknu jádro CPU pouze na určitou dobu, po uplynutí mu ho odebere
    • Vhodná pro vlákna v interaktivních systémech
    • Umožňuje rozumně sdílet CPU výkon systému
    • Dochází k častějšímu přepínání kontextu – horší využití CPU, lepší doba odezvy
  • Round-robin plánování (RR) – vlákna ve stavu „Ready“ čekají ve frontě FIFO, až jim bude přiděleno jádro CPU
    • Všem vláknům je jádro CPU propůjčováno na stejně velkou dobu. Poté se znovu řadí do fronty
    • Prioritní RR se statickou prioritou – každému vláknu přiřazena statická priorita (číslo 1,...,N), která se během existence vlákna nemění (vyšší číslo = vyšší priorita)
      • Volné jádro CPU je vždy přiřazeno vláknu s nejvyšší prioritou, které je na začátku příslušné fronty (Ready queue)
      • Různé priority mohou mít různý čas na CPU
    • Prioritní RR s dynamickou prioritou – výchozí plánovací strategie běžných OS
      • Priorita i čas CPU se může během existence vlákna měnit
      • Cíl minimalizovat problém hladovění vláken, zlepšit odezvu a snížit počet přepnutí kontextu
      • Strategie:
        • Priorita se zvýší a časové kvantum sníží – pokud vlákno v posledním běhu nevyužilo celé své časové kvantum nebo dlouho čeká na CPU
        • Priorita se sníží a časové kvantum se zvýší – pokud vlákno v posledním běhu využilo celé své časové kvantum
  • Kooperativní plánování (cooperative scheduling) – není vhodná pro běžná uživatelská vlákna
    • Jádro OS přidělí vláknu jádro CPU a vlákno ho používá, dokud ho samo neuvolní
    • First-come-first-served (FCFS)¨- vlákna ve stavu „ready“ čekají ve FIFO frontách na přidělení jádra CPU, když běžící vlákno uvolní jádro CPU, první vlákno z Ready fronty s nejvyšším číslem bude pokračovat
    • Vlákna ve stavu blocked čekají ve frontě Blocked
    • Jednoduché na implementaci, minimalizuje počet přepnutí kontextu

Synchronizační nástroje

  • Časově závislé chyby -> situace, kdy více vláken používá společné sdílené prostředky a výsledek deterministického algoritmu je závislý na rychlosti jednotlivých vláken, které používají tyto prostředky. Špatně se detekují — lze předcházet správným návrhem paralelního algoritmu.
  • Kritická sekce –> část programu, kde vlákna používají sdílené prostředky.
  • Sdružené kritické sekce – kritické sekce více vláken, které se týkají stejného sdíleného prostředku.
  • Vzájemné vyloučení –> vláknům není dovoleno sdílet stejný prostředek ve stejném čase, tedy se nenachází ve stejné sdružené sekci současně.
  • Korektní paralelní program – nesmí klást předpoklady na rychlost vláken a počet jader. Musí zajistit výlučný přístup ke sdíleným prostředkům. Mimo kritické sekce by vlákno nemělo být zpomalováno ostatními vlákny.
    Při použití synchronizace (bez ní časové chyby (race conditions))
  • Deadlock -> Několik vláken čeká na událost, kterou může vyvolat jen jedno z čekajících vláken
  • Livelock -> Několik vláken vykonává neužitečný výpočet ale nemohou ho dokončit
  • Starvation -> Ready vlákno se dlouho nedostane na CPU

Pouze jedno vlákno v kritické sekci, je nutné ostatní blokovat.

Aktivní čekání

  • Sdílená proměnná indikuje obsazenost.
  • running vlákno permanentně čeká na uvolnění
  • při uvolnění zamkne a vstoupí do kritické sekce
  • Problém čeká se na vlákno co má zamčeno, nijak neni ovlivněné plánování

Blokující volání

  • Dostupnost kritické sekce se zjišťuje systémovým/api voláním
  • Při nedostupnosti je vlákno zablokováno a neplánuje se
  • Odemčení sekce naplánuje jedno čekající vlákno.

MUTEX

  • Blokující volání
  • První zamkne a je majitel
  • Další se blokují do odemčení
  • Odemčení probudí jedno vlákno (když nikdo nečeká, odemkne)

Condition variables

  • Blokující
  • Čeká se na splnění podmínky
  • Může probudit jednoho nebo všechny čekající

Semafor

  • Blokující
  • Obsahuje čítač a frontu blokovaných vláken
  • Čítač říká kolik může do kritické sekce
  • Při vstupu se čítač dekrementuje, pokud je 0, tak se vlákno blokuje

Bariéra

  • Blokující
  • Obsahuje čítač (sílu bariéry) a seznam blokovaných
  • Čítač říká kolik vláken bariéru prolomí.
  • Při příchodu se čítač dekrementuje a vlákno zablokuje
  • Když 1 všechny vlákna se probudí

Synchronizační úlohy

Večeřící filozofové

  • Reprezentuje situaci, kdy několik vláken soutěží o omezený počet prostředků
  • V systému N filozofů sedících kolem kulatého stolu, před každým talíř s jídlem a mezi sousedy vždy jedna vidlička (celkem N). Pokud dostane filozof hlad, musí získat obě vidličky, které leží napravo a nalevo od něj. F může být ve 3 stavech – přemýšlí, má hlad a snaží se získat prostředky, jí
  • Optimální řešení – v jeden okamžik může jíst až floor(N/2) filozofů
  • Správné optimální řešení – mutexy a N semaforů/podmíněných proměnných (pro vidlyčky)

Čtenáři - písaři

  • 2 typy vláken soutěží o přístup ke společnému prostředku
  • Máme 1 sdílený prostředek a 2 typy vláken – čtenáři (pouze read) a písaři (mohou write), pouze jeden písař může modifikovat prostředek v jednom okamžiku.
  • Optimální řešení – více čtenářů může číst současně, pokud žádný písař nepřistupuje k prostředku
  • Spravedlivé řešení – pokud p/č čeká, pak by ho nikdo neměl předběhnout
  • Problém hladovění – řešení pomocí dvou mutexů - Optimální spravedlivé řešení – musíme si pamatovat v jakém pořadí čtenáři a písaři začínají čekat

Spící holiči

  • V holičství je N holičů, N křesel k holení a M křesel k čekání pro zákazníka. Pokud není žádný zákazník v holičství, holič sedne do křesla k holení a usne. Pokud přijde zákazník: holič je volný (spí) – zákazník se nechá ostříhat / holič není volný, ale je volné místo v čekárně – zákazník počká / jinak opustí holičství
  • Správné optimální řešení – jeden mutex (zákazníci) a dva semafory

Producent konzument

  • Několik vláken si vyměňuje data prostřednictvím např. sdílené paměti s omezenou velikostí
  • Producent – produkuje data a vkládá je do sdílené paměti (fronty) s omezenou velikostí
  • Konzument – vybírá data ze sdílené paměti (fronty)
  • Problémy:
    • Musíme zajistit výlučný přístup při vkládání/vybírání dat z fronty
    • Pokud je fronta prázdná, musíme zablokovat konzumenta
    • Pokud je fronta plná, musíme zablokovat producenta

Uváznutí (deadlock)

  • K uváznutí dochází když jsou splněny všechny Coffmanovy podmínky
  • Dochází k tomu při práci s více sdílenými prostředky
  • Je nutné tomu předcházet

Coffmanovy podmínky

  1. Vzájemné vyloučení – každý prostředek je buď přidělen právě jednomu vláknu, nebo je volný.
  2. Podmínka neodnímatelnosti – prostředek, který byl již přidělen vláknu mu nemůže být násilím odebrán
  3. Podmínka „drž a čekej“ – vlákno, které má přiděleno prostředky, může zažádat o další
  4. Podmínka kruhového čekání – musí existovat smyčka dvou nebo více vláken, ve které každé vlákno čeká na prostředek přidělený dalšímu vláknu ve smyčce
  • 1 – 3 jsou nutné, ale ne dostačující – k uváznutí může dojít, 4. představuje samotné uváznutí

Strategie pro řešení uváznutí

  • Pštrosí strategie
    • problém se neřeší, je třeba zásah admina
  • Prevence uváznutí - Narušení alespoň jedné Coffmanovy podmínky
    • Vzájemné vyloučení:: může způsobit časově závislé chyby
    • Neodnímatelnost:: např. přepínání kontextu
    • Drž a čekej:: vede k horšímu využití prostředků
    • Kruhové čekání:: vlákno může žádat o prostředky jen v rostoucím očíslovaném pořadí, ale takové číslování nemusí existovat
  • Předcházení vzniku uváznutí
    • Předem známe všechny požadavky a vytvoříme manuálně bezpečný stav
  • Detekce uváznutí a zotavení
    • Pravidelné kontroly pro odhalení uváznutí
      • Watchdog timer
    • Pro zotavení se část prostředků uvolní

Vytvořeno: 27. 5. 2026, 11:59
Poslední aktualizace: 9. 6. 2026, 12:18