- první pořítače běželi pouze s jedním programem
- programy byly rozplánovány dopředu (ahead of time)
- používání děrovaných štítků, počítače zabírali celé místonsti
- v ‘mini’ počítačích mohl programy interaktivně
- teletype terminály, obrazovky, klávesnice
- více uživatelů zároveň
- proto i více programů zároveň spustěných
- proces je vykonávaný program
- může být vícero procesů
- procesům patří mnohé zdroje
- každý proces patří dnaému uživateli
- paměť (address space)
- processor time
- otevřené soubory (file descriptors), také pracující adresář a síťové připojení
- program test - obsahuje instrukce
- data - statická a dynamická data s oddělenou read-only sekcí
- stack memory - vykonávaný zásobník - return adresy, automatické proměnné
- každý proces má vlastní address space
- procesy jsou navzájem izolované
- požaduje aby CPU mělo MMU
- implementováno pomocí paging (page tables)
- změna procesů znamená změna page tables
- fyzické adrase se nemění,
- ale mapping virtuálních adres se mění
- velká část fyzické paměti není mapována
- může být nealokované (nepoužité)
- nebo patří jiným procesům
- překlad adres je pomalý
- nedávno použité stránky jsou uloženy v TLB
- zkratka pro Translation Look-aside Buffer
- velmi rychlá hw cache
- TLB musí být flushed na process switch
- toto je poměrně drahé (microseconds)
- moderní jednotka CPU scheduling
- jednotlivé vlákna běží sekvenčně
- jeden proces může mít více vláken, taková vlákna sdílí jeden address space
- vlákna je sekvence instrukcí - instrukce závisí na výsledku předchozích instrukcí
- různá vlákna spouští různé instrukce
- as opposed to SIMD or many-core units (GPUs)
- každé vlákno má vlastní zásobník
- čas CPU je rozdelěn do time shares
- time shares (slices) jsou jako paměťové rámce (memory frames)
- process computation je jako paměťové stránky (memory pages)
- procesy jsou alokované do time shares
- vykonání vláken je sekvenční
- jeden CPU = jedna instrukční sekvence za čas
- fyzický limit na rychlost CPU → more cores
- více CPU jader = větší throughput (propustnost)
- v moderním pohledu jsou procesy address space
- vlánka jsou správná scheduling abstraction
- processje jednotka správy paměti (memory management)
- vlákno je jednotka výpočtu (computation)
- starý pohled: jeden proces = jedno vlákno
- jeden (sdílený) text segment
- sdílený read-write data segment
- read-only data segment
- jeden zásobník pro každé vlákno
- Jak se tvoří nové procesy?
- pomocí
fork-ování existujících procesů
- fork vytvoří identickou kopii existujícího procesu
- vykonávání pokračuje v obou procesech
- každý dostane rozdílnou return hodnotu
- stránkování může
fork udělat velmi efektivním
- začneme zkopírováním page table
- ze začátku jsou všechny stránky označené jako read-only
- procesy začínají pameť sdílet
- sdílená paměť se stane copy on write
- fault když nějaký proces se pokusí zapsat (pameť byla označena read-only)
- OS ověří, jestli paměť má být zapisovatelná, jestli ano, vytvoří kopii a povolí zápis
- na UNIXu,
fork je jediný způsob, jak vytvořit proces, ale fork rozdělí existující proces do 2
- první proces je speciální, je přímo vyvolán kernelem při bootu
- procesům jsou přiřazeny číselné identifikátory - známe jako PID (Process ID)
- tyto čísla jsou používány v process management
- použití calls jako
kill nebo setpriority
- proces je dynamická entita
- spustitelný soubor je statický soubor
- executable obsahuje začínající memory image
- tota nsataví memory layout
- a content text a data segmentů
- na UNIXu procesu jsou tvořeny pomocí
fork
- Jak se tedy spouští programy?
exec: načte novou executable do procesu
- toto kompletně přepíše paměť procesu
- execution začíná z entry point
- spouštení programů:
fork + exec
- scheduler má dvě přidělené práce
- plánování kdy které vlánko má běžet
- switch vláken a procesů
- normálně část kernelu (i u micro-kernelů OS)
- vlákna stejného procesu sdílí address space
- částečný context switch je potřeba
- jen stav registru musí být ulože na uchován
- no TLB flushing - zmenšení overhead
- fixní schedule = všechny procesy jsou známé napřed (in advance)
- užitečné pouze ve speciálních / embedded systémech
- může conserve resources
- plánoavání není součástí OS
- většina systémů používá dynamic scheduling, co běží dál je rozdhodnuto periodicky
- úkoly (vlákna) běží jako když jsou vlastněny CPU
- OS jim násilně CPU odebere
- toto se nazávý preemption
- pro: šatný progam nemůže zablokovat systém
- tak nějak méně efektivní než cooperative
- vlákna cooperate ke sdílení CPU
- každé vlánka musí explicitně yield CPU (vzdát se CPU dobrovolně)
- toto může být velmi efektivníkdyž nadesignováno dobře
- ale špatný program může zablokovat systém
- cooperative na Windows 3.X pro všechno
- cooperative pro vlákna na klasickém macOS
- ale preemptive pro procesy
- preemptive na snad každém moderním OS (včetně real-time i embedded systémech)
- vlákna často musí čekat na zdroje nebo události (mohou také používat sw timers)
- čekájící vlákno by nemělo konzumovat CPU time
- taková vlánko se CPU vzdá (yield the CPU)
- a je zapsáno na list a později probuzeno kernelem
- runnable (non-waiting) vlákno jsou řazeny do fronty
- mohou být prioritní, round-robin nebo jiné typy front
- scheduler vybere vlákno z run queue
- preepmted threads are put back
- jaký díl CPU by mělo vlákno dostat?
- priority jsou statické i dynamické
- dynamické priority jsou přizpůsobeny za běhu vláken (toto dělá systém/scheduler)
- statická priorita je přidána uživatelem
- equal (nebo priority-based) díl per thread
- Co když má proces více vláken?
- Co když má uživatel více procesů?
- Co když jedna skupina uživatelů má více aktivních uživatelů?
- můžeme použít více-úrovňové scheduling scheme
- CPU je rozděleno podobně přes uživatelské skuupiny
- poté přes uživatele
- následně přes procesy
- a nakonec přes vlákna
- first in, first served (batch systems)
- earliest deadline first (realtime)
- round robin
- fixed priority preepmtive
- fair share scheduling (multi-user)
- throughput vs latency
- latency je více důležité pro interaktivní práci (například teledon, desktop nebo také web servery)
- throughput je více důležité pro batch systémy
- render farms, compute grids, simulation, …
- kratší time slices
- větší odhodlanost task switching (více preemption)
- dynamické priority
- prioritní zvýšení pro procesy v popředí
- delší time slices
- reduce context switches na minimum
- cooperative multitasking
- tradičně jedno CPU, více vláken
- dneska: mnoho vláken, mnoho CPUs (jader)
- více komplikované algoritmy
- více komplikované a concurrent-safe data structures
- vlákna se mohou přemisťovať (move) mezi CPU jádry
- důležité když jsou různá jádra idle a runnable thread čeká na CPU
- ale to něco stojí
- vlákna/data procesů jsou hodně cachována
- caches typicky nejsou sdílené všemi jádry
- moderní schedulers se snaží vyhnout přesouváním vláken
- vlákna jsou affinity to a core
- extrémní případ je pinning
- toto zabraňuje vlánka být migrated
- prakticky toto zlepšuje throughput, přestože nomal core utilisation může být nižší
- non-uniform memory architecture
- jiná paměť je přiřazená jiném CPUs
- každá SMP block je v NUMA se nazývá node
- migrating procesu do jiného node je drahé
- thread vs node ping-pong může zabít výkon
- vlákna jednoho procesu by měli žít na jednom node
- způsob jak si hw žádá o poroznost
- CPU mechanismus jak ?
- částečný (CPU state only) context switch
- změna na privilegovaný (kernel) CPU mód
- asynchronní, narozdíl od sw interruptům
- spuštěň přes signál na sběrnici do CPU (bus signal)
IRQ = interrupt request (jiný název pro hw int)PIC = programovatelný interrupt controler
PIC: jednoduchý obvod
- typicky 8 vstupních linek
- periferní připojení k PIC pomocí drátů
- PIC přináší prioritizované singály do CPU
APIC: advanced programmable int controller
- rozděleno do sdílených IO APIC a per-core local APIC
- typicky 24 vstupních IRQ linek
- OpenPic, MPIC: podobný APIC, používán Freescale
PIT: **programmable interval timer
- crystalový oscilátor + dělitel
- IRQ linka do CPU
- local APIX timer: vestavěný, per-core clock
HPET: high-precision event timerRTC: real-time clock
- generován PIT nebo lokálním APIC
- OS může nastavit frekvenci
- hw int se uskuteční každý tick
- toto vytváří možnosti pro bookkeeping a preemptive scheduling
- měření jak dlouho to aktuálnímu vláknu trvalo
- jestli došel ze svých slice, preepmt it
- vyber nové vlákno na vykonávání
- uskutečni context switch
- kontrole ja provedena každým tickem
- rescheduling je méně časté
- typicky je 100 Hz
- to znamená, že 10ms je scheduling tick (quantum) - nejmenší time slice
- 1kHz je také možný
- ale škodí throughput, ale lepšují latency
- timer interrupt wakes up the CPU
- toto může být neefektivní jestli je systém idle
- alternativa: použití us-off timers
- umožňuje CPU spát delší dobou
- toto zlepšuje pwer efficiency při slabém využití
- quantum length se stane část plánování
- jádro je udle, probudí se při dalším sw timer - synchronizace sw časovačů
- ostatní int jsou deliverd as normal
- síť nebo atkivita disku
- klávesnice, myš, ..
- seriový port - data jsou dostupná na portu
- síťový hw - data jsou připravené v paket frontě
- klávesnice, myš
- USB zařízení obecně
- né všechna CPU jádra vidí všechny int
- APIC může dostat jak bude IRQs doručeno - OS může přesměrovat do CPU jader
- multi-core ystems: IRQ load balancing
- užitečné pro rozložení IRQ zátěže
- speciálně užitečné pro vysoko rychlostní sítě