5. přednáška20. 3. 2014

- složení OS- proces (co je to, vytvoření a přerušení, implementace)- vztah mezi OS a procesy- PCB (Process Control Block)- trasování procesů- stavové diagramy procesů- odkládání procesů

Studijní materiály najdete na adrese:

http://www.uai.fme.vutbr.cz/~vdumek/

Operating system Design Hierarchy

L Name Objects Example Operations

13 Shell User programming environment Statements in shell language

12 User processes User processes Quit, kill, suspend, resume

11 Directories Directories Create, destroy, attach, detach, search list

10 DevicesExternal devices, such as printers, displays and keyboards

Open, close, read, write

9 File system Files Create, destroy, open, close, read, write

8 Comunications Pipes Create, destroy, open, close, read, write

7 Virtual memory Segments, pages Read, write, fetch

6 Load secondary store Blocks of data, device channels Read, write, allocate, free

5 Primitive processes Primitive processes, semaphores, ready list Suspend, resume, wait, signal

4 Interrupts Interrupt-handling programs Invoke, mask, unmask, retry

3 Procedures Procedures, call stack, display Mark stack, call, return

2 Instruction setEvaluation stack, microprogram interpreter, scalar and array data

Load, store, add, subtract, branch

1 Electronic circuits Registers, gates, buses, etc. Clear, transfer, activate, complement

Operating system Design Hierarchy

Level 1: obsahuje elektronické obvody, které představují registry, paměťové buňky a logická hradla, operace na těchto objektech jsou např. mazání registrů, čtení z paměti, atd.

Level 2: představuje instrukční soubor procesoru se strojovými instrukcemi (sčítání, odčítání, přesun, ...)

Level 3: volání procedur a funkcí (podprogramů), call and return

Level 4: představuje přerušení, při kterém se ukládá starý kontext a aktivuje se přerušovací rutina

První 4 úrovně nejsou součástí operačního systému, ale zahrnují HW. Přesto některé části operačního systému těchto úrovní využívají (přerušení).

Operating system Design Hierarchy

Level 5: v této úrovni běží procesy, jsou přepínány, je zajištěna synchronizace

Level 6: zabývá se sekundární pamětí počítače (pevný disk), jsou zde implementovány funkce polohování čtecích hlav, přesun bloků dat, využívá sousedních vrstev pro plánování a adresování přesunů bloků dat

Level 7: vytváří logický adresní prostor pro procesy, tato vrstva zajišťuje přesun dat mezi operační pamětí a diskem, běžná jsou 3 schémata: pevná délka stránky, proměnná délka stránky a obojí, pokud není požadovaný blok dat v paměti, zapojí se vrstva 6

Do úrovně Level 7 se operační systém zabývá pouze procesory, od úrovně Level 8 jsou zapojeny periferie a počítačová síť, objekty jsou sdíleny na jednom nebo více počítačích.

Operating system Design Hierarchy

Level 8: zabývá se komunikací mezi procesy, pipes (roury) slouží k předávání informací mezi procesy, synchronizace, zprávy

Level 9: long-term storage pojmenovaných souborů, čtení dat do proměnných, stopy, sektory, konstantní velikost bloku (Level 6)

Level 10: poskytuje přístup k externím zařízením pomocí standardních interfaces

Level 11: zodpovídá za asociace mezi externími a interními identifikátory zdrojů a objektů, externí jsou textové položky pro uživatele, interní jsou indikátory pro OS, přístupová práva

Level 12: poskytuje podporu procesům na vyšší úrovni, než Level 5 (virtuální adresování, seznamy procesů k přepínání, atd.)

Level 13: poskytuje intarface OS s uživatelem, shell, transformuje vlastnosti OS do služeb

- prováděný program- instance běžícího programu- entita, která může být popsána a provedena na počítači- aktivní jednotka charakterizovaná a prováděná jedním sekvenčním vláknem, se svým stavem a sdružená se systémovými zdroji

Proces

Vytváření procesu

- přiřazení jedinečného identifikátoru- alokování paměti pro zásobník, image procesu, program a data, hodnoty mohou být imlicitní nebo explicitní- inicializace PCB- nastavení příslušných vazeb (různé fronty dle plánování, ...)- vytváření všech potřebných datových struktur

Vytvoření a přerušení procesu

Důvody pro vytvoření procesu

- spuštění nového programu (příkaz, dávka, ...)

- přihlášení uživatele

- operační systém potřebuje provést nějakou službu ve prospěch uživatele nebo jiného procesu

- při běhu programu se objeví potřeba paralelismu nebo modularity (spawn)

Důvody pro přerušení (ukončení) procesu

- vše je hotovo

- překročení časového limitu určeného pro běh procesu

- proces požaduje více paměti, než mu OS může poskytnout

- porušení ochrany paměti, souboru, prostředku, ...

- vznik chyby při výpočtu (dělení nulou, velké číslo, ..)

- překročení časového limitu při čekání procesu na událost

- chyba při I/O operaci

- pokus o provedení neexistující instrukce (při větvení programu skok na data, ...)

- snaha o provedení instrukce rezervované pro OS

- špatný typ nebo inicializace dat

- intervence OS nebo rodičovského procesu

Korektní

- při přerušení procesu je aktuální obsah programového čítače a registrů procesoru (datový kontext) přenesen do příslušné datové oblasti korespondující s PCB a stav procesu je označen jinou hodnotou, přepnutí kontextu

Typical Process Implementation

Context

Data

Program

Context

Data

Program

b

h

ProcessA

ProcessB

Processlist

i

Mainmemory

Processorregisters

bh

Process index

PC

BaseLimit

Otherregisters

.

.

.

i

j

P1

OS1

kernel

. . .

Vztah mezi operačním systémem a procesy

process switching functions

process switching functions

. . .

P1 P2 P3 Pn

. . .

P2 P3 Pn

OS2 OS3 OSn

P1 P2 P3 Pn

funkce OS

- tradiční přístup, běžný pro starší OS, kernel běží vně všech procesů, procesy jsou přerušovány pomocí supervissor call, kontext procesu je uložen, kernel má vlastní paměť a zásobník, po provedení požadované funkce se provede návrat k procesu

- způsob běžný pro PC a workstations, funkce OS se provádí v kontextu procesů, OS je kolekcí rutin prováděných v rámci uživatelských procesů, každý image procesu obsahuje i program, data a zásobník kernelu

- OS je implementován jako kolekce systémových procesů, většina kernelových funkcí je organizována v samostatných procesech

OS je prováděn během procesu

PCB

Process identification

Process state information

Process controlinformation

User stack

Private user addressspace (program, data)

Kernel stack

Shared address space

běžné pro OS na PC a workstations, SW OS probíhá v kontextu uživatelského procesu každý image procesu obsahuje i program, data a zásobník kernelusdílení všemi

procesy

Uživatelské procesy v paměti

Processidentification

Process stateinformation

Process controlinformation

User stack

Private useraddress space

(programs, data)

Sharedaddress space

Process 1

Processidentification

Process stateinformation

Process controlinformation

User stack

Private useraddress space

(programs, data)

Sharedaddress space

Process 2

Processidentification

Process stateinformation

Process controlinformation

User stack

Private useraddress space

(programs, data)

Sharedaddress space

Process n

. . .

pro

cess

imag

e

Struktura seznamů procesů

Running

Ready

Blocked

PCB

PCB

PCB

PCB PCB

PCB PCB PCB PCB

Typické komponenty PCB

Process Identification – obsahuje identifikátory (procesu, rodiče,

uživatele)

Process State Information – registry viditelné uživatelem (pouze některé), řídící a stavové registry (program counter, condition codes (výsledky logických a aritmetických operací)), ukazatele zásobníků

Process Control Information – plánovací informace (stav,

priorita, ...), ukazatele na spolupracující datové struktury, meziprocesová komunikace (příznaky, signály, zprávy, ...), informace o MMU, informace o vlastnění zdrojů, informace o využití procesoru

Zjednodušený Process Control Block

PCB (execution context)- datová struktura vytvářená a řízená prostřednictvím OS, jedná se o klíčový moment v otázce podpory běhu více procesůIdentifikátor – jedinečné označení procesu, odlišné od všech jinýchStav – označuje stav procesu z množiny stavového diagramuPriorita – je zde poznamenána úroveň priority procesuČítač instrukcí – ukazuje na další instrukci při provádění procesuPaměťové ukazatele – obsahují údaje o umístění kódu procesu, datech a sdílených oblastech s jinými procesySouvisející data – obsah registrů během provádění procesuStav V/V – obsahuje nevyřízené V/V požadavky procesu, sdružená zařízení s procesem, seznam souborů souvisejících s procesem, ...Účtovací informace – mohou obsahovat údaje o spotřebovaném procesorovém čase, časové limity, ...

Identifier

State

Priority

Program counter

Memory pointers

Context data

I/O status information

Accounting information

. . .

500050015002500350045005500650075008500950105011

8000800180028003

120001200112002120031200412005120061200712008120091201012011

Trace of Process A

Trace of Process B

Trace of Process C

5000 – Starting address of program of Process A8000 – Starting address of program of Process B12000 – Starting address of program of Process C

Trasování procesů

Process C

Process A

Process B

Dispatcher

0

100

5000

8000

12000

8000

Main memory

Program counter

Timeout

Timeout

I/O request

Timeout

1 50002 50013 50024 50035 50046 5005

7 1008 1019 10210 10311 10412 10513 800014 800115 800216 8003

17 10018 10119 10220 10321 10422 10523 1200024 1200125 1200226 12003

27 1200428 12005

29 10030 10131 10232 10333 10434 10535 500636 500737 500838 500939 501040 5011

41 10042 10143 10244 10345 10446 10547 1200648 1200749 1200850 1200951 1201052 12011 Timeout

Enter Notrunning

RunningExit

Dispatch

Pause

Queue

Processor

Enter Exit

Pause

Dispatch

Dvoustavový diagram procesů

Process A

Process B

Process C

100 5 15 20 25 30 35 40 45 50

Dispatcher

Running Ready Blocked

Stavy procesů při trasování

připraven

probíhající

čekajícípředán přijat

dokončen

Procesu je přiřazen procesor

Čekání na dokončení I/O operace

I/O operace je dokončena

- probíhající: je přidělen procesor- čekající: čekání na určitou událost- připraven: čeká na přidělení procesoru- předán: očekává se reakce OS na předání úlohy

- přijat: úloha převedena do vnitřního tvaru, procesům nejsou přiděleny žádné prostředky- dokončen: prostředky jsou volné

Stavy procesu

Pětistavový model procesu

- předpokládejme přítomnost jednoho procesoru

- New – vytvořený proces, který ještě nebyl přijat operačním systémem, už má vytvořený PCB

- Ready – čeká na svoji příležitost (modifikováno politikou přidělování)

- Running – právě zpracovávaný proces, může být pouze jeden

- Exit – proces uvolnil veškeré přidělené prostředky, ukončen, zrušen

- Blocked – odložený proces z důvodu očekávání události (prostředek, zpráva, ...)

New Ready Running

Blocked

Exit

Dispatch

TimeoutPřijmout

Očekávanáudálost

Událostnastala

Uvolnit

Jeden stav suspend

New AdmitDispatch

Release

Timeout

Suspend

Act

ivat

e

Eve

nt

occu

rs

Eve

nt w

ait

Ready Running Exit

Suspend Blocked

Ready – proces je v paměti a je připraven k provedeníBlocked – proces je v paměti a očekává nějakou událostSuspend – proces je na disku a čeká na uvolnění místa v paměti

Dva stavy suspend

Ready /Suspend

DispatchRelease

Timeout

Suspend

Activate

Eve

nt

occu

rs

Event

wai

t

Ready Running Exit

Blocked /Suspend

Blocked

New

Suspend

Activate

Eve

nt

occu

rs

Adm

itAdmit

Suspend

Přechody mezi stavy procesu

Blocked -> Blocked/Suspend: málo místa v paměti, možnost vzniku nových procesůBlocked/Suspend -> Ready/Suspend: pokud nastala událost, na kterou proces musel čekatReady/Suspend -> Ready: pokud není v paměti žádný proces schopný svého provedení, záleží na prioritě procesůReady -> Ready/Suspend: používá se v případě potřeby získat hodně místa v paměti, někdy si pro suspendování může OS vybrat ready proces s nízkou prioritou místo blokovaného procesu s prioritou vysokou

- nově vzniklý proces někdy nemusí mít vytvořeny všechny podmínky pro svůj běh

Odkládání procesů

- stav suspend- každý prováděný proces musí být uložený v paměti, pokud blokované procesy zaplní paměť do určité míry, jsou převedeny do stavu suspend a odkládány na disk (swapování), diskové operace jsou z hlediska výměn rychlostně uspokojivé- systém má možnost vzít do fronty připravených procesů proces nový (zvýšení míry multiprogramování) nebo proces ze stavu suspend (z disku)- při opuštění stavu suspend se předpokládá okamžité zapojení procesu do mechanismu plánování- není účelné zařazovat suspendované procesy, které očekávají nějakou událost

Důvody pro odložení procesu

Swapping OS potřebuje uvolnit místo v operační paměti, potřebuje zde umístit proces ve stavu Ready

Other OS Reason OS může suspendovat nějaký méně důležitý (background) proces, nějakou utilitu nebo proces podezřelý z působení problémů

User Reguest interaktivní požadavek uživatele přerušení programu z důvodů trasování, modifikace HW zdrojů

Timing přerušení periodicky se opakujícího procesu (účtování, monitorování, ...) a čekání na další periodu

Parent Request rodič si může přát suspendování potomka za účelem jeho zkoumání nebo modifikace, pro koordinaci akcí několika potomků