Architektura operačních systémů, vrstvená struktura, vlastnosti a

f k kl ifikfunkce, klasifikace.

Abstraktní pohled na systémové komponenty

Uživatel1

Uživatel 2

Uživatel n

Kompilátor textový editor databázový systém

Operační systém

Hardware počítače

Definice operačního systému

• Správce prostředků – spravuje a přiděluje zdroje systému

• Řídicí program – řídí prováděníŘídicí program řídí provádění uživatelských programů a operací I/O zařízenízařízení

• Jádro – trvale běžící program – všechny ostatní lze chápat jako aplikační programy

Operační systémy-způsoby popisu

Proces 3

h lý

Proces 1

„holý počítač Uživatelské programy

OS Avnitřní

vnějšíProces 2 OS-A

Virtuální počítač

Operační systém je

• Program, který řídí běh ostatních procesů– Ostatním procesům bezpečně a efektivně předává řízení

a získává je zpětCPU děl j kd á š ě í– CPU sděluje, kdy má spouštět ostatní procesy

• Rozhraní mezi uživatelem a hardware• Skrývá ostatním procesům detaily o hardware

– Musí zvládnout správu detailů hardware ve své režiip

Typické poskytované služby

• Vytváření programů• Provádění programů, běh procesů• Zpřístupňování V/V zařízení• Zpřístupňování V/V zařízení• Řízení přístupů k souborům• Řízení přístupu k systému

D t k h b h b é ří í• Detekce chyb a chybové řízení• Protokolování činností

Struktura operačního systému

• Monolitický systém• Vrstvená struktura• Virtuální počítač• Virtuální počítač• Model klient-server

Monolitický systém

• velmi rozšířený• model jádra OS+systémových služeb• bez vnitřní struktury• bez vnitřní struktury• Unix, CP/M, MS-DOS• různé režimy činnosti procesoru různé

fáze činnosti OSfáze činnosti OS

Monolitický systém

uživatelské programy běžící v uživatelském

uživatelský program 2

uživatelský program 1 módu

Operační systém běžící v módu jádramódu jádra

Vrstvená struktura

• hierarchické uspořádání vrstev• vyšší vrstva využívá pouze služeb nejbližší

nižší vrstvynižší vrstvy• příklad návrh OS „THE System“

( h i h h l idh(Technische Hogeschool Eidhoven –Dijkstra 1968): 6 vrstev

Vrstvená struktura

5 operátor

4 uživatelské programy

3

2

správa I/O zařízení

2

1 správa paměti

komunikace s procesy

0

sp v p ě

přidělování procesoru

Virtuální počítač (virtual machine).

• oddělení funkce multiprogramování od funkce šíř éh j ( d d hi )rozšířeného stroje (extended machine)

• příklad CP/CMS (VM/370)• OS SW emuluje existenci více jednouživatelských

systémů s vlastním HW (virtual machine monitor -y (VM), které jsou přesnou kopií HW (VM vrstva emuluje HW)j )

Virtuální počítač

CMS CMS CMSOperační systémy zajišťující funkci

Virtuální 370’ CMS CMS CMS zajišťující funkci

rozšířeného počítače

370

VM /370

HW 370 Vlastní HW

počítačepočítače

Model klient-server

• trend minimalizace rozsahu jádra OS (mikrokernel),

• část funkcí OS implementována do úrovněčást funkcí OS implementována do úrovně uživatelských procesů (zasílání požadavků mezi procesy)mezi procesy),

• mikrokernel zajišťuje zejména komunikaci

Model klient-server

kli t kli t kli t v uživatelském

Jád ód jád

klient klient klient server server server v uživatelském módu

Jádro v módu jádra

Generické komponenty OSp y

Interpret příkazů

Networking Sy

Správa souborů

Správa sekundární paměti

stéSpráva sekundární paměti

Správa I/O systému

ém p y

Správa hlavní paměti

och

Správa procesů

hra

Správa procesorů n

Principy vonNeumannovyPrincipy vonNeumannovy koncepce počítače, jednotlivýchkoncepce počítače, jednotlivých

podsystémů, zobrazování informací v počítači, principy

k ik if í h ří íkomunikace periferních zařízení s procesorem jiné architekturys procesorem, jiné architektury

počítačů.p

Operační paměťOperační paměťPAMĚŤOVÉ BUŇKY

ADRESOVÝ REGISTR PAMĚTI

ŘADIČ PAMĚTI

ÚDAJOVÝ REGISTR PAMĚTI

NAJDI ADRESU

REGISTR PAMĚTI - RAP

- RDP

HOTOVO SESTAVNASTAV ADRESU

ADRESA VYBER

ULOŽ START

HOTOVOÚDAJ SESTAV

ÚDAJSU

Předpoklady paměťové buňky

• Obsahuje jedno slovo – slabiku – byte• Při získání údaje čtením se obsah neporuší• Lze do ní zapsat novou informaci s• Lze do ní zapsat novou informaci s

podmínkou že se zruší existující informace• Má jednoznačně přidělenou adresu

Hierarchie paměťového podsystémuHierarchie paměťového podsystémuŘADIČ ŘÍDÍCÍ PAMĚŤ

OPERAČNÍ ZÁPISNÍKOVÁ JEDNOTKA PAMĚŤ

OPERAČNÍ PAMĚŤOPERAČNÍ PAMĚŤ

ÝVSTUP / VÝSTUP

VNĚJŠÍ VELKOKAPACITNÍ

PAMĚŤ

VNĚJŠÍ VELKOKAPACITNÍ

PAMĚŤPAMĚŤ PAMĚŤ

•••

•••• •

Procesor:

• aritmeticko-logická jednotka • registry • řadič• řadič

Aritmeticko logická jednotkag j

REGISTR A - STŘADAČ

1 d ∑1. operand

2 d

PŘEPÍ

∑PŘEP DOZ PAMĚTI

RESITR B - BÁZE

2. operand

VÝSLEDEK

ÍNAČ

PÍNAČ

DO PAMĚTI

Z PAMĚTI

REGISTR Q - PODÍL

řízenířízení

ŘADIČ OPERAČNÍ JEDNOTKY

řízení přepínačů

řízení posunů

ŘadičŘadič

RDP RAP RAP

OK ADRESAŘÍDÍCÍ REGISTR

ČÍTAČ INSTRUKCÍ

Dekodér ÚstředníDekodér instrukcí

Ústřední řadič

ČASOVÁNÍ A ŘÍZENÍ

PŘEPÍNAČŮ (PŘENOSŮ)(PŘENOSŮ)

Základní instrukční cyklus

Výběrová ProváděcíSTART

Výběrová fáze řadiče

Prováděcí fáze řadiče HALT

Způsoby komunikace procesoru sZpůsoby komunikace procesoru s okolímokolím

• Programovou smyčkou• Přerušením• DMA• DMA

Podmíněný přenos datý p

Při ?Připraven?

neano

ne

přenos

Přenos dat systémem přerušení

Hlavní program Přerušení

Nalezení příčiny přerušení a uchování stavu CPU

program

Odskok do podprogramu pro obsluhu přerušení

Obnovení stavu CPU

Posloupnost obsluhy přerušení

• Uchování stavu procesoru• Vlastní obsluha přerušení • Obnovení stavu procesoru• Obnovení stavu procesoru

Instrukční cyklus s přerušením

Interrupt

Výbě á P ádě í P

Interrupt Disabled

START Výběrová fáze řadiče

Prováděcí fáze řadiče

Proces přerušení

Interrupt Enabled

HALT

DMA přenos

Procesor Paměť Řadič

disků

Kradení cyklů

Harwardská koncepce

paměť paměťpaměť programu

paměť dat

registr instrukcí

/programu

řadič

ALU vstupy/výstupy

Sériový procesor s jedním tokem instrukcí a jedním tokem dat SISD

Procesor

Data Instrukce Data

Paměť

Řetězený procesor s jedním tokem dat a ícenásobným tokem instr kcí MISDvícenásobným tokem instrukcí MISD

ProcesorProcesor

Data Data

Instrukce

Paměť

Maticový procesor s jedním tokem instrukcí a vícenásobným tokem dat SIMDinstrukcí a vícenásobným tokem dat SIMD

Řídící jednotka systému Paměť programů

Instrukce

Instrukce

Data Data

P ěť d tPaměť dat

Multiprocesor s mnohonásobnýmMultiprocesor s mnohonásobným tokem instrukcí a dat MIMDtokem instrukcí a dat MIMD

Procesor

Instrukce Instrukce DataData

Paměť

Obecné uspořádání čísla v pevnéObecné uspořádání čísla v pevné řádové čárce

Znaménko

Číslo

Řádová čárka

Obecné uspořádání čísla v pohyblivéObecné uspořádání čísla v pohyblivé řádové čárce

Znaménko Znaménko

Exponent MantisaExponent Mantisa

Obecná struktura instrukce

Operační kód Adresová část

Tříadresová instrukceTříadresová instrukce OK A1 A2 A3

• Y = A * B + (C – D) * E / F• Instrukce Význam• Instrukce Význam• Násob a b p1 A * B -> P1• Odečti c d - C - D -> R

Ná b R * E > R• Násob - e - R * E -> R• Děl - f - R / F -> R• Sečti - p1 - R + P1 -> Y

Dvouadresová instrukceDvouadresová instrukce OK A1 A2

• Y = A * B + (C – D) * E / F• Instrukce Význam• Násob a b A * B -> R• Zapiš p1 - R -> P1• Odečti c d R D > R• Odečti c d R - D -> R• Násob - e R * E -> R• Děl - f R / F -> R• Sečti P1 y R + P1 -> Yy

Jednoadresová instrukce OK A1

• Y = A * B + (C – D) * E / F• Instrukce VýznamInstrukce Význam• Ulož a A -> R• Násob b R * B -> RNásob b• Zapiš p1 R -> P1• Ulož c C -> R• Odečti d R - D -> R• Násob e R * E -> R• Děl f R / F -> R• Sečti p1 R + P1-> R• Zapiš y R -> Y

S á ů č íhSprávce procesů operačního systému plánování procesůsystému, plánování procesů, komunikace mezi procesy, p y,

kritická sekce, uváznutí, vlákna.

Pojmy

• Program = zápis algoritmu v nějakém í j ( říkl d j éprogramovacím jazyce (například ve strojovém

kódu). Je statický, neměnný (neuvažujeme-li ý j ý h í ů)vývoj nových verzí programů).

• Proces (process, task) = běžící program. Proces je tvořen neměnným kódem programu a konstantami a proměnnými daty jako je stav procesoru, data na zásobníku, globální proměnné, halda, soubory atd

Zdroje systému nutné pro běhZdroje systému nutné pro běh procesuprocesu

• operační paměť • procesor • další prostředky (I/O zařízení soubory• další prostředky (I/O zařízení, soubory

apod.)

2 stavový model

ý

běží í

vytvoření Spuštění ukončení

neběžící běžící

Potlačení

vytvoření spuštění ukončení fronta

procesor

potlačení

3 stavový modelý

vytvoření

Procesu je přiřazen procesor ukončení

připravený běžící P íProces musí čekat na dokončení I/O

b jinebo jinou událost I/O nebo jiná

událost je ukončena

čekající

ukončena

ukončení čekající

5-stavový modelý vytvoření spuštění ukončení

připravený běžící

Čas, priorita

Potlačení – čekání na událost

Aktivace – vznik

obnova

odložení

Odložený připravený

událostudálosti

odložení

ukončení čekající

připravený

odložení Aktivace – vznik události

Odložený čekající

Informace OS o procesuInformace OS o procesu

• Process Control Block – tabulka b h jí í i f ř b é

Ukazatel Stav procesu

Číslo procesu

obsahující informace potřebné pro definici a správu procesu

Programový čítač (čítač instrukcí)

Registry procesoru

– stav procesu (běžící, připravený, …)– čítač instrukcí

i– registry procesoru– informace potřebné pro správu

ěti

Oblast operační paměti

Seznam otevřených souborů paměti

– informace potřebné pro správu I/Oúčtovací informace

..

.. – účtovací informace ..

Přepnutí procesuPřepnutí procesuProces P1 Proces P2Operační systém

Běžící P1

p y

Uložení kontextu P1 Čekající P2

Načtení kontextu P2

Běžící P2 Čekající P1

Uložení kontextu P2

Načtení kontextu P1

Čekající P2

Běžící P1

Nepreemptivní plánováníp p p• V případě nepreemptivního plánování se proces

d k d b d bmusí procesoru sám vzdát. Pokud má být doba, po kterou je proces ve stavu běžící, omezená, je nutné, aby proces kontroloval časovač a po překročení stanovené doby se dobrovolně vzdal procesorustanovené doby se dobrovolně vzdal procesoru vyvoláním služby OS, která je k tomuto účelu určena Výhodou je že proces nemůže být přerušenurčena. Výhodou je, že proces nemůže být přerušen, pokud nechce (například v kritické sekci). N ýh d j ž š ě h jí í ůžNevýhodou je, že špatně chovající se proces může zablokovat celý OS. Takto fungují například MS-Windows.

Preemptivní plánování

• V případě preemptivního plánování OS může odebrat procesu procesor. Zpravidla se tak děje při uplynutí časového kvanta j p p yurčeného pro běh procesu a celá akce je vyvolána přerušením od časovačevyvolána přerušením od časovače. Příkladem OS, který používá preemptivní

lá á í j OS U iplánování je OS Unix.

Strategie plánování procesoruStrategie plánování procesoru -podle těchto kritérií:podle těchto kritérií:

• spravedlnost: každý proces dostane spravedlivý díl času procesoručasu procesoru

• efektivita: udržovat maximální vytížení procesoru, příp jiné části systémupříp. jiné části systému

• čas odezvy: minimalizovat dobu odezvy pro interaktivní uživateleinteraktivní uživatele

• doba obrátky: minimalizovat dobu zpracování každé dávkové úlohykaždé dávkové úlohy

• průchodnost: maximalizovat množství úloh zpracovaných za jednotku časuzpracovaných za jednotku času

Plánovací algoritmyTyp

Využívá charakteristickou veličinu

Princip

FCFS, také FIFO (first come - first served / First in - first out)

toi řádný frontový režim

SXFS (shortest execution -first served)

ti proces s nejkratší dobou provádění, je první obsloužen

LCFS (l l d ř d ě b l h jLCFS (least completed -first served)

tbi přednostně se obsluhuje proces, který zatím běžel nejkratší dobu

EDFS (e lie t d e ti e t řed t ě e b l h jeEDFS (earliest - due-time fisrst served)

tdi přednostně se obsluhuje proces, kterému zbývá nejméně času na dokončení, tj. do okamžiku, kdy musí j , ybýt dokončen

HSFS (highest static priority first served)

Pi přednostně se obsluhuje proces s nejvyšší statickou prioritou

RR (round-robin) Δti cyklická obsluha procesů po časových intervalech

Spolupráce mezi procesyp p p y• sdílená paměť - jednodušší programování,

mocnější - programátor má více prostředků, zpravidla i jednodušší implementace.zpravidla i jednodušší implementace.

• zasílání zpráv - flexibilnější, je možné použít i pro komunikaci mezi procesy běžícími na různých procesorech nebo počítačíchp oceso ec ebo poč tač c

• Některé operační systémy podporují oba mechanismy

Prostředky předávání zprávy p p• SEND zašle zprávu. Nikdy se nezablokuje.

P k d á č ká říj íPokud na zprávu čeká příjemce operací RECEIVE, je mu zpráva doručena a příjemce odblokován.

• RECEIVE zprávu přijímá Pokud žádná zpráva• RECEIVE zprávu přijímá. Pokud žádná zpráva není dostupná, přijímající proces je zablokován.

• Je třeba vyřešit problém adresace, tj. určení odesilatele a příjemce. Lze řešit např. p j pidentifikací procesu na daném počítači. Jiným řešením je zavedení schránek (mailboxů) ařešením je zavedení schránek (mailboxů) a adresace pomocí identifikace schránky.

Sdílená paměť

• Sdílená paměť je paměť, do které má přístup více procesů. Může být použita pro komunikaci mezi procesyp y

Souběh - race condition

• při přístupu dvou nebo více procesů ke sdíleným d ů d jd k h bě ř ž k ždý ůdatům dojde k chybě, přestože každý z procesů samostatně se chová korektně

• K chybě dochází díky tomu, že data jsou modifikována některým procesem v době, kdy s nimi jiný proces provádí několik operací, o kterých se předpokládalo, že budou provedeny jako jeden nedělitelný celek.

Kritická oblast

• Data, která jsou sdílena několika procesy tak, že při přístupu k nim by mohlo dojít k souběhu

• Kritická sekce je nejmenší část programu, ve které se pracuje s daty v nějaké kritickéve které se pracuje s daty v nějaké kritické oblasti, a která musí být provedena jako jeden celek.

Souběh

• Zejména u složitějších datových struktur ( b ě é j é l ži é d i ké(obousměrné spojové seznamy, složité dynamické struktury uložené v souborech apod.) dochází č k ž či é di á í jčasto k tomu, že v určitém stadiu zpracování jsou data dočasně nekonzistentní

• Pokud v tom okamžiku dojde k přepnutí kontextu na proces, který tato data také používá, může nastat souběh

Problém kritické sekce• umožnit přístup ke kritické oblasti procesům, které o to

usilují, při dodržení následujících podmínek:usilují, při dodržení následujících podmínek: – výhradní přístup; v každém okamžiku smí být v kritické sekci

nejvýše jeden proces j ý j p– vývoj; rozhodování o tom, který proces vstoupí do kritické sekce,

ovlivňují pouze procesy, které o vstup do kritické sekce usilují; toto rozhodnutí pro žádný proces nemůže být odkládáno do nekonečna; nedodržení této podmínky může vést například k tomu, ž j ž ě t ikt í lt (d řiže je umožněna pouze striktní alternace (dva procesy se při průchodu kritickou sekcí musí pravidelně střídat) omezené čekání; pokud jeden proces usiluje o vstup do kritické– omezené čekání; pokud jeden proces usiluje o vstup do kritické sekce, nemohou ostatní procesy tomuto vstupu zabránit tím, že se v kritické sekci neustále střídají - mohou do této kritické sekce jvstoupit pouze omezený počet krát (zpravidla pouze jednou)

Znázornění paralelismu pomocí PetrihoZnázornění paralelismu pomocí Petriho sítí (problém kritické sekce)(p )

A C

KSP KSQ

B D

B D

Prostředky pro zajištěníProstředky pro zajištění výlučného přístupuvýlučného přístupu

• Zákaz přerušení• Instrukce Test and set lock• Semafory• Semafory

Princip operace P

P

S(i)=0?ANO

S(i) := S(i) - 1

NE

Princip operace V

V

NEANO

S(i)=C(i)?NE

S(i) := S(i) + 1

Uváznutí - deadlockUváznutí - deadlock• je situace, kdy dva nebo více procesů čekají j y p j

na událost, ke které by mohlo dojít pouze pokud by jeden z těchto procesů pokračovalpokud by jeden z těchto procesů pokračoval (vyřešení dopravní situace couváním).

Podmínky uváznutíy• Výlučný přístup (mutual exclusion). Existence

ř dků k é j řiděl á ýh d íprostředků, které jsou přidělovány pro výhradní použití jednomu procesu, tj. nesdílitelných

dkůprostředků. • Postupné přidělování prostředků (hold and wait). p p p ( )

Procesy nežádají o přidělení všech prostředků najednou, ale postupně. Pokud požadovaný j , p p p ýprostředek není volný, musí proces čekat.

• Přidělování prostředků bez preempce Přidělené• Přidělování prostředků bez preempce. Přidělené prostředky nelze procesu násilím odebrat. C kli ké č ká í• Cyklické čekání

Řešení otázky uváznutíy• ignorovat je - přestože tato strategie vypadá nepřijatelně, používá ji

například OS Unix; v případě uváznutí musí zasáhnout některý z uživatelů a jeden nebo více procesů násilím ukončit; v krajním případě může být nutné znovu nastartovat celý systém

• předcházet mu zabránit splnění aspoň jedné z podmínek nutných• předcházet mu - zabránit splnění aspoň jedné z podmínek nutných pro vznik uváznutí

• vyhýbat se mu - systém se vyhýbá situaci, kdy by došlo k cyklickému y ý y y ý , y y yčekání tím způsobem, že zná maximální nároky procesů na jednotlivé prostředky a před přidělením každého prostředku zjišťuje, zda existuje způsob jak dokončit všechny procesy i když budou vyžadovatzpůsob, jak dokončit všechny procesy i když budou vyžadovat prostředky odpovídající maximálním nárokům; OS přidělí prostředek pouze tehdy, je-li to bezpečné (existuje-li způsob, jak všechny aktivní procesy zdárně dokončit)

• detekovat uváznutí a zotavit se z něj

Předcházení uváznutí

• Strategie předcházení uváznutí se snaží zabránit splnění alespoň jedné z podmínek uváznutí: – Výlučný přístup

Postupné přidělování prostředků– Postupné přidělování prostředků – Přidělování prostředků bez preempce – Cyklické čekání

Výlučný přístupý ý p p• Prostředky, které jsou bez omezení sdílené, nemohou

způsobit uváznutí Příkladem jsou read-only souboryzpůsobit uváznutí. Příkladem jsou read-only soubory. • Virtualizace prostředků - používá se například u tiskáren.

P ží jí ří ti ká l ý t i jí dProcesy nepoužívají přímo tiskárnu, ale výstupy zapisují do diskového souboru, který operační systém vytiskne později. U t í h ří í té čt ž d á d t dU vstupních zařízení systém načte požadovaná data do souborů, ze kterých je pak jednotlivé procesy čtou. Tato

t d ý á li ( i lt i h i l t tmetoda se nazývá spooling (simultaneous peripherial output on-line).

• Bohužel existují prostředky, které jsou z podstaty nesdílitelné, na které není možné tuto metodu použít.

Postupné přidělování prostředkůp p p• Jednorázové přidělování prostředků - každý proces si

vyžádá všechny prostředky, které potřebuje při svém startu y y p y p j pa žádné další mu nebudou později přidělovány. Pokud procesu nemohou být přiděleny všechny požadované

ř dk j řiděl žád é í č kprostředky, nejsou mu přiděleny žádné a proces musí čekat. • Alternativou je strategie, při které je možné přidělovat

ř dk k ý žád é á Díkprostředky pouze procesu, který žádné nemá. Díky tomu může proces několikrát za dobu svého běhu vrátit všechny prostředky a pak žádat o dalšíprostředky a pak žádat o další.

• Nevýhody: žití tř dků j í ké tř dk j l t ě řiděl á– využití prostředků je nízké, prostředky jsou vlastně přidělovány

procesům, které je ve skutečnosti zatím nepotřebují – možnost stárnutí procesů (starvation); nároky procesu kterýmožnost stárnutí procesů (starvation); nároky procesu, který

potřebuje několik často používaných prostředků, nemusí být nikdy uspokojeny a proces tak může čekat neomezenou dobu

Přidělování prostředků bez preempcep p p

• Pokud je možné snadno uschovat a následně• Pokud je možné snadno uschovat a následně obnovit stav prostředků, může operační systém

d b t tř dk kt é tř b jodebrat procesu prostředky, které potřebuje pro jiné procesy.

• Díky nutnosti uschovat o obnovit stav prostředku, je možné tuto strategii používat pouze uje možné tuto strategii používat pouze u prostředků, které to umožňují jako je procesor nebo operační paměťnebo operační paměť.

Cyklické čekání

• Algoritmus, který zamezuje cyklickému č ká íčekání: – Každému typu prostředku je přiděleno číslo. – Pokud má proces přiděleny nějaké prostředky,

může žádat pouze o takové další prostředky, j ji h l j j ljejichž číslo je větší než největší z čísel procesem už držených prostředků. O ř dk k é jí j é čí l í žád– O prostředky, které mají stejné číslo musí žádat najednou.

Shrnutí

• Některé ze strategií, které se používají pro předcházení uváznutí je možné použít pouze propředcházení uváznutí, je možné použít pouze pro určité prostředky (sdílitelné prostředky a prostředky jejichž stav je možné uschovat aprostředky, jejichž stav je možné uschovat a obnovit).

• Ostatní strategie mohou vést k nízkému využitíOstatní strategie mohou vést k nízkému využití prostředků a ke stárnutí procesů, což může být považováno za tak velkou nevýhodu, že v mnoha p ý ,operačních systémech nejsou tyto strategie používány.

Vyhýbání se uváznutí• Strategie předcházení uváznutí jsou buď příliš omezující,

nebo nepokrývají všechny prostředky používané v příslušném systému. Pokud není možné zabránit prvním třem podmínkám vzniku uváznutí a není schůdné ani podstatné omezení, které klade na systém výše popsaný algoritmus předcházení cyklickému čekání, je možné použít strategii vyhýbání se uváznutí.

• Při žádosti o prostředek systém kontroluje, zda existuje p y j jalespoň jeden proces, který je možné po přidělení tohoto prostředku dokončit. Po jeho dokončení opět musí existovat p j palespoň jeden proces, který může být dokončen a tak dále až po ukončení všech procesů. Pokud by tato podmínka nebyla p p y p ysplněna, systém prostředek nepřidělí.

Bankéřům algoritmus• Každý proces deklaruje pro každý typ prostředku

maximální množství které bude potřebovatmaximální množství, které bude potřebovat. • Operační systém si musí při přidělování

prostředků ponechat tolik prostředků, aby byl p p p , y yschopen uspokojit maximální požadavky alespoň jednoho procesu.Tí j č ž k čí l í• Tím je zaručeno, že tento proces skončí a uvolní prostředky, které pak mohou být přiděleny dalším procesům OS nekontroluje pouze zda je možnéprocesům. OS nekontroluje pouze, zda je možné dokončit jeden proces, ale všechny aktuální procesy.

Definice problémup• Bankéř chce rozdělit pevný kapitál abstraktních peněžních

jednotek mezi pevný počet zákazníků• Každý zákazník udává předem svou maximální potřebu

peněžních jednotek• Bankéř vyhoví zákazníku, pokud potřeba zákazníka

nepřevyšuje kapitál bankéře• Během transakcí zákazník může vracet nebo si půjčovat

peněžní jednotky• Bankéř musí zaručit, že čekací doba zákazníka na přidělení

peněžních jednotek bude vždy konečná• Běžná půjčka zákazníka nesmí nikdy převýšit jeho

maximální potřebu• Zákazník zaručuje, že dokončí své transakce a splatí půjčku

v konečném čase

Algoritmus

• Stav jistý – jestliže bankéř umožní všem zákazníkům dokončení všech jejich transakcí v konečném čase

• Stav nejistý – opačná situace

Situace

• zákazníka– požadavek = potřeba – půjčka

• bankéře• bankéře– hotovost = kapitál – součet půjček

Příklad

• bankéř má 10 jednotek• zákazníci P,Q R mají potřebu 20 jednotek • zápis = (půjčka)požadavek• zápis = (půjčka)požadavek• Algoritmus vyšetřuje zákazníky jednoho po

druhém a hledá toho, jehož požadavek nepřevyšuje hotovost Hnepřevyšuje hotovost H

Stav jistýj ýnejdříve uspokojí zákazníka Q

2 4

H H

4(4) 8

H

HP

2(1)

4(4) 8

10 HP

Q 2(1)

2(7) 2(7) 2(7) R R R

Q

R R R

Stav nejistýpřidělil R jednu jednotku a popřidělil R jednu jednotku a po

uspokojení Q se navodí neřešitelnáuspokojení Q se navodí neřešitelná situace

1 3

H H

4(4) 3

2(1)

4(4)

P

P 2(1)

3(6)

PQ

3(6) 3(6)

R R

Procesy a vlákna• Program

– soubor definovaného formátu obsahující instrukce, data a další informace ř b é k d í d éh úk lpotřebné k provedení daného úkolu

• Proces– systémový objekt charakterizovaný svým paměťovým prostorem a

kontextem (paměť i některé další zdroje jsou přidělovány procesům)kontextem (paměť i některé další zdroje jsou přidělovány procesům)• Vlákno, také „sled“

– objekt, který vzniká v rámci procesu, je viditelný pouze uvnitř procesu a je charakterizován svým stavem (CPU se přidělují vláknům)charakterizován svým stavem (CPU se přidělují vláknům)

• Model – jen procesy (ne vlákna)– proces: jednotka plánování činnosti i jednotka vlastnící prostředky

• Model – procesy a vláknaModel procesy a vlákna– proces: jednotka vlastnící zdroje– vlákno: jednotka plánování činnosti

Procesy a vlákna• Každé vlákno si udržuje svůj vlastní

– zásobník– zásobník– PC (program counter)– registry– TCB (Thread CB)

• Vlákno může přistupovat k paměti a ostatním zdrojům svého procesusvého procesu– zdroje procesu sdílí všechny vlákna jednoho procesu– jakmile jedno vlákno změní obsah (nelokální – mimo zásobník)

b ňk š h í lák ( éh ž ) idíbuňky, všechny ostatní vlákna (téhož procesu) to vidí– soubor otevřený jedním vláknem mají k dispozici všechny ostatní

vlákna (téhož procesu)

Stavy vláken

• Tři klíčové stavy vláken:– běží– připravený– čekající

• Vlákna se (samostatně) neodkládajíVlákna se (samostatně) neodkládají– všechny vlákna jednoho procesu sdílejí stejný

adresový prostoradresový prostor• Ukončení procesu ukončuje všechny

vlákna existující v rámci tohoto procesuvlákna existující v rámci tohoto procesu

Vlákna na uživatelské úrovni• User-Level Threads (ULT)

– Správa vláken se provádí prostřednictvím vláknové knihovny– Správa vláken se provádí prostřednictvím vláknové knihovny („thread library“) na úrovni uživatelského / aplikačního programu

– Jádro 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žimprovádění funkcí jádra nepřepíná se ani kontext procesu ani režim procesoru

– Plánování přepínání vláken je specifické pro konkrétní aplikaci aplikace si volí pro sebe nejvhodnější (např plánovací) algoritmusaplikace si volí pro sebe nejvhodnější (např. plánovací) algoritmus

• Příklady– POSIX Pthreads– Mach C-threads– Solaris threads

Vlákna na úrovni jádra• Kernel - Level Threads (KLT)• Správu vláken podporuje jádro nepoužívá se threadSprávu vláken podporuje jádro, nepoužívá se „thread

library“– používá se API pro vláknové služby jádra

informaci o kontextu procesů a vláken udržuje jádro– informaci o kontextu procesů a vláken udržuje jádro– přepojování mezi vlákny aktivuje jádro– plánování na bázi vláken již v jádře OSříkl d• Příklady

– OS/2– Windows 95/98/NT/2000/XP– Solaris– Tru64 UNIX– BeOSBeOS– Linux

Správce operační paměti, metody přidělování paměti, ochrana

ěti i t ál í ěťpaměti, virtuální paměť.

Hlavní úkoly správce paměti

• Přidělovat operační paměť jednotlivým ů kd ž i ji žád jíprocesům, když si ji vyžádají

• Udržovat informace o paměti, o tom, která pčást je volná a která přidělená (a komu)

• Zařazovat paměť, kterou procesy uvolní,Zařazovat paměť, kterou procesy uvolní, opět do volné části

• Odebírat paměť procesům je li to zapotřebí• Odebírat paměť procesům, je-li to zapotřebí• ochrana paměti – umožňuje-li to HW

Strategie přidělování paměti

• Přidělování veškeré volné paměti• Přidělování pevných bloků paměti• Přidělování bloků paměti proměnné velikostip p• Segmentace paměti• Stránkování paměti• Stránkování paměti• Stránkování na žádost (demand paging)• Segmentace se stránkováním na žádost

Přidělování veškeré volné pamětip• Část paměti RAM je obsazena operačním systémem

(kód ě é á í ěti) b t k j k(kód, proměnné, vyrovnávací paměti), zbytek je k dispozici pro uživatelský program. V každém okamžiku je tedy v paměti nejvýše jeden uživatelský programp g

• Přeadresování provádí program zvaný locator. Locator podle tabulky adres v relativním programuLocator podle tabulky adres v relativním programu změní (dle umístění) příslušné adresy na absolutní.

• Ochrana paměti - pouze ochrana OS před přepsáním uživatelským programem (pomocí mezního registru;uživatelským programem (pomocí mezního registru; změna pouze v privilegovaném stavu procesoru)

Spojité přidělování paměti doSpojité přidělování paměti do jednoho úsekujednoho úseku

• Nejjednodušší verze: V paměti v daném okamžiku pouze jeden proces, který může používat celou paměť,p p ,

• Později přechod na systém, kdy jsou v operační paměti umístěny: operační systémoperační paměti umístěny: operační systém a jednouživatelský proces, zbylé místo nevyužité rozdělení na tři souvislé oblasti (úseky)( y)

operační systém

uživatelský proces

volný prostor

Operačnísystémsystém

Základnísegmentg

overlayinicializace

prováděnívýstup

overlayarea

Strategie přidělování pevných bloků pamětig p p ý p• First fit - procházejí se bloky paměti a přidělí se

bl k d lk j b dprvní blok délka je větší nebo rovna požadované paměti.

• Last fit - vybere se poslední vyhovující W t fit b j ětší h jí í• Worst fit - vybere se největší vyhovující u přidělovaných bloků proměnné velikosti (používá se u strategie přidělování bloků paměti proměnné velikosti pro omezení fragmentace) p g )

• Best fit - vybere se nejmenší vyhovující (pro přidělo ání bloků pe né elikosti se pra idlapřidělování bloků pevné velikosti se zpravidla používá tato strategie)

Přidělování bloků paměti proměnné elikostivelikosti

• Výhody:Výhody:– ve vnitřní paměti může být několik procesů současně– lepší využití paměti

• Nevýhody: – součet paměťových nároků, které jsou současně v paměti musí být menší nebo

roven velikosti pamětiroven velikosti paměti – fragmentace paměti - procesy vyžadují souvislé úseky paměti. Může se stát, že

není možné spustit další proces, protože má větší nároky na paměť než je velikost největšího volného bloku i přesto že součet velikostí volných bloků jevelikost největšího volného bloku i přesto, že součet velikostí volných bloků je větší než paměťové nároky procesu

• Pro odstranění fragmentace používají další strategie správy paměti g p j g p y pnásledující metody:– setřásání bloků; problémy s adresními konstantami lze odstranit použitím

segmentacesegmentace – stránkování = programu se jeví adresní prostor jako souvislý, přestože ve

skutečnosti není

Fragmentace paměti volný blok 30 KB

Proces 1 10 KB

volný blok

Proces 2

40 KB

10 KB

Proces 2

volný blok

10 KB

20 KB

Proces 3

volný blok

10 KB

30 KB

30 KB

Setřesená paměť

Proces 1 10 KB

Proces 2

Proces 3

10 KB

10 KB

volný blok120 KB

volný blok

Stránkování paměti

• Stránkování paměti umožňuje přidělit procesu několik nesouvislých úseků paměti, a vytvořit pro proces iluzi, že tato paměť y p p , psouvislá je.

• Při stránkování paměti je fyzická paměť je• Při stránkování paměti je fyzická paměť je rozdělená na rámce - frames (někdy se nerozlišuje rámec a stránka).

St á k á íStránkování

l i ké f i kélogické adresy

fyzické adresy

CPU fyzickápaměť

p d f d

page table

pf

p

Stránkování čísla á ů fyzickáStránkování

0rámců

logický adresový

fyzická paměť

page 01logický adresový prostor

page 0

1 page 20 12

3page 1

page 2

page 2

page 112

43

3

4p g3 7

page 3 5

tabulka stránek

6

page 37

Princip stránkování pamětip p• Logická adresa (= adresa použitá v programu) je

rozdělena na dvě složky číslo stránky a posunutí vrozdělena na dvě složky, číslo stránky a posunutí v rámci stránky (OFFSET). Velikost stránky bývá řádově kilobyty Při velikosti stránky 4 KB je prořádově kilobyty. Při velikosti stránky 4 KB je pro offset potřeba 12 bitů (2^12 = 4K), čili spodních 12 bitů logické adresy je offset zbylé bity jsou číslobitů logické adresy je offset, zbylé bity jsou číslo stránky. Po rozkladu adresy (vše provádí procesor bez asistence programátora) na číslo stránky abez asistence programátora) na číslo stránky a offset se číslo stránky použije jako index do tab lk stránek (každý proces má s oji lastní) Vtabulky stránek (každý proces má svoji vlastní). V tabulce stránek je uvedeno číslo rámce ve fyzické

ěti K čí l á ři jí ff t ý l dkpaměti. K číslu rámce se připojí offset a výsledkem je fyzická adresa v paměti.

Vytváření adresy při stránkové organi aci pamětiorganizaci paměti

Tabulka stránek konkrétního

0 1

programu

1 . V

Skutečná adresa slova

.

. Adr. fyz. stránky Adresa slova.

.

Adr. fyz. stránky Adresa slova

d i á k Adadr. virt. stránkyV

Adresaslova

Segmentace paměti

• Fyzická (skutečná) adresa v paměti se získává řič í b h i l i képřičtením obsahu segment registru a logické

adrese (= adresa použitá v programu). Obsah i j OS ži l kýsegment registru nastavuje OS a pro uživatelský

program je nepřístupný. Díky tomu adresní prostor k ždéh čí á 0 d d jí blékaždého procesu začíná na 0 a odpadají problémy s relokací programu. Většina systémů, které

ží jí i ě i d l j ůpoužívají segmentaci paměti dovoluje procesům použít více segmentů.

SegmentaceSegmentace

operační systémLAP

FAP

Segmentacesegment 0 segment 1 segment 2 segment 3 segment 4

Source Constant

Call

Symbol

text Parsetree

Call stack

ytable

SegmentaceSegmentace

Symbol table

Source text

Constant table

Parse tree

Call stack

SegmentaceSegmentacess

limit base

segmentCPU s d fyzická

paměť

segment table

< +

Segmentaceg

t 4

segment 0

1400

segment 0

segment 4 2400

3200segment 3

segment 3

3200

segment 1

segment 2 segment 2limit base 4300

g g

segment 4

0 1000 1400

1 400 6300

2 400 4300

4700

5700

1

3 1100 3200

4 1000 4700

5700

6300

segment 1

6700

Struktura paměťového prostoru procesprocesu

• kód programu -> neměnný (obsah ani délka)kód programu neměnný (obsah ani délka) • konstanty -> neměnné • inicializované statické proměnné -> délka se nemění obsah• inicializované statické proměnné -> délka se nemění, obsah

je nastaven při startu procesu (načte se z souboru, který obsahuje program), při běhu procesu se jejich obsah může obs uje p og ), p bě u p ocesu se jej c obs ů eměnit, délka se nemění

• neinicializované statické proměnné, délka se nemění, obsah p , ,ano

• zásobník (návratové adresy z procedur a lokální proměnné a ( y p pparametry); proměnná velikost i obsah, neobsahuje díry

• halda; proměnná velikost i obsah, může obsahovat díry ; p , y• paměť pro overlaye (překryvné segmenty), dynamické

knihovny

Segmentace paměti

• Výhody: j ž é d i ké ř í ť á í tů běh– je možné dynamické přemísťování segmentů za běhu procesu pro odstranění fragmentace (lze spojovat volné bloky paměti přesunutím překážejícího bloku) y p p p j )

– možnost dodatečně zvětšovat adresní prostor procesu – není nutné provádět relokaci programu – možnost sdílení segmentů

• Nevýhody: – součet nároků procesů v paměti musí být menší nebo

roven velikost paměti (lze obejít odkládáním segmentů na disk) může časo ě náročnéna disk) - může časově náročné

– nutná hardwarová podpora segmentace

Ochrana paměti

• mezní registr na číslo segmentu • pro každý segment mezní registr obsahující

maximální povolenou adresu segmentumaximální povolenou adresu segmentu (limit velikosti segmentu); segmenty mají různou délku !!!různou délku !!!

Ochrana mezními registryg y

HMA

Horní mezní adresa

( HMA – A ) : 0 Překročení horní mezeRSH

HMA

<0 horní meze

AdresovýA Adresový registr paměti RAP

( A- DMA ) : 0 Překročení dolní mezeRSD <0 dolní meze

DMA

Dolní mezní adresa

Ochrana paměti klíčip

adresový registr

Registr klíče programu

KP

B ARAP

4 1

4 1 RKP

&

& B = BRZ

i t á k

4 1 &B = BRZ

BRZ adresa stránky 4 Z – zámek 1

registr zámku

Z

RZP

ZB

Paměť zámků stránek 0 1

Z0 Z1

B ZB

Stránkování na žádost (demand paging)( p g g)• V tabulce stránek je pro každou stránku údaj, zda se stránka

nachází v paměti nebo na disku. V případě, že je stránka na p p p , jdisku, je uvedeno i její umístění na disku. Pro stránkování se používá zpravidla zvláštní soubor, partition (oblast na disku)

b d k di knebo dokonce disk. • V případě, že se proces odkazuje na stránku, která je přítomna ve

fyzické paměti vše probíhá jako u běžného stránkování Pokudfyzické paměti, vše probíhá jako u běžného stránkování. Pokud však stránka ve fyzické paměti není (je na disku), dojde k vyvolání vnitřního přerušení "výpadek stránky". Obslužný y p ýp y ýprogram přerušení musí do vnitřní paměti zavést stránku z disku, opravit odkaz v tabulce stránek, a zajistit zopakování instrukce, kt á ý d k t á k ů bil P k d j itř í ětikterá výpadek stránky způsobila. Pokud je ve vnitřní paměti volné místo, použije se libolný z volných rámců. Pokud jsou všechny rámce plné, je nutné vybrat některý z nich a přenést jejvšechny rámce plné, je nutné vybrat některý z nich a přenést jej do stránkovacího souboru na disk.

Algoritmy nahrazování stránekg y

• Algoritmus FIFO• Algoritmus LRU• Algoritmus NUR - zjednodušení• Algoritmus NUR - zjednodušení

algoritmu LRU

Algoritmus FIFOg• Vyhodí z paměti stránku, která je v ní nejdéle.

Bohužel to může být stránka která se používáBohužel to může být stránka, která se používá trvale, což efektivitu algoritmu snižuje.

• Algoritmus FIFO také vykazuje tzv. FIFO anomálií. Pokud se provede tentýž výpočet dvakrát s různě p ý ýpvelkou vnitřní pamětí, mělo by při výpočtu s větší pamětí dojít nejvýše ke stejnému počtu výpadkůpamětí dojít nejvýše ke stejnému počtu výpadků stránek jako při výpočtu s menší pamětí. Při použití t t i FIFO t í žd l tit N í ístrategie FIFO to nemusí vždy platit. Navíc není

snadné implementovat nahrazování stránek pomocí strategie FIFO.

Algoritmus LRU (least recentlyAlgoritmus LRU (least recently used))

• vyhazuje z paměti tu stránku, která nebyla nejdelší dobu použita Implementace tohoto algoritmudobu použita. Implementace tohoto algoritmu může používat buď registr udávající čas posledního odkazu na danou stránku nebo frontuposledního odkazu na danou stránku nebo frontu, na jejiž začátek se zařazuje stránka, na kterou byl právě proveden odkaz. Má-li být z paměti některá p p ý pstránka vyhozena, vybere se ta, která nebyla použita nejdéle (v případě použití fronty je to poslední ve frontě). Algoritmus LRU je sice kvalitní, ale jeho hardwarová implementace je

btíž áobtížná.

Algoritmus NUR (not used recently) g ( y)• Zjednodušení algoritmu LRU.• V tomto případě je každému rámci přiřazen jednobitový

příznak, zda byla příslušná stránka použita. Při hledání oběti se vybere ta stránka, která použita nebyla.

• V algoritmech nahrazování stránek je vhodné brát v úvahu, zda byl obsah stránky změněn. V případě, že nebyl, stačí stránku pouze zahodit (její kopie je na disku). Pokud byla stránka změněna, je nutné ji nahrát na disk, což trvá přibližně stejně dlouho jako načtení nové stránky z disku. Pro tento účel bývá pro každý rámec k dispozici jednobitový příznak, který se vynuluje při zavedení stránky do vnitřní paměti a nastaví při zápisu do rámce.

Segmentace se stránkováním na žádost

• Logická adresa se skládá z čísla segmentu, čísla stránky a offsetu na stránce. Každý proces má vlastní tabulku segmentů. Každý p g ýsegment má vlastní tabulku stránek (pro sdílený segment je tabulka jen jedna)sdílený segment je tabulka jen jedna).

Segmentace se stránkováním naSegmentace se stránkováním na žádostžádost

• Výhody: – odstranění fragmentace – je možné používat více paměti (virtuální

paměť) než je velikost fyzické paměti – je možné sdílet segmenty

• Nevýhody: – složitostsložitost – nutná podpora hardware

Vytváření adresy při segmentovéVytváření adresy při segmentové organizaciorganizaci

Virtuální adresar. začátek tab.

segmentů č. segmentu adr. stránky adr. slova

∑ ∑ ∑

Poč. adr.tab. stránek

Sk t č áTabulka T b lk

Adr. fyz. str.

daného segmentu

Skutečná adresa

Tabulka segmentů

Tabulkastránek

S á b ů iSpráva souborů, organizace adresářů vlastnosti souborůadresářů, vlastnosti souborů,

metody přístupu na disk, výpočet y p p , ýpparametrů disku.

Systémy souborů

• Soubory uchovávají data a programy• OS implementuje abstraktní koncepci

souborů správou velkokapacitních záznamových zařízení

• Systém souborů se skládá ze dvou částí:y– sada souborů obsahující vlastní uložené

informace– struktura adresářů obsahující informace o

souborech

Organizace struktury adresářů • Dnes obvykle v nějaké podobě grafu s kořenem.• Aktuální adresář - pozice uživatele v adresářové struktuře• Absolutní cesta - jméno souboru spojené se jmény všech podadresářů

ležících na cestě z kořenového adresáře k danému souboru• Relativní cesta - jméno spojené se jmény všech podadresářů ležících

na cestě z aktuálního adresáře k danému souboru, obvykle přidány speciální jména adresářů pro aktuální adresář a předchůdce adresářespeciální jména adresářů pro aktuální adresář a předchůdce adresáře (., ..)

• Stromová struktura - adresář obsahuje množinu souborů a adresářůStromová struktura adresář obsahuje množinu souborů a adresářů, strom má kořenový adresář

• Struktura acyklického grafu - sdílení adresářů a souborů, linkyy g , y• Struktura obecného grafu - možnost cyklů znesnadňuje procházení

adresářů

Stromová struktura - /A/B/D/ggA

B Ca

D b dD b c d

e f ge f g

Acyklický graf – /A/B/D/g a /C/g ukazují na stejný souborukazují na stejný soubor

A

B Ca

D b c d

e f g

Obecný graf - /A/B/D/g a např. /A/B/D/A/C/ k jí t j ý/A/B/D/A/C/g ukazují na stejný

souborsouborAA

B Ca

D b c dD b c d

e f g

Správa velkokapacitních záznamových zařízení

V lk k it í á á ří í h á jí• Velkokapacitní záznamová zařízení uchovávají permanentně velké množství dat (na rozdíl od operační paměti)

• Disk má S sektorů H hlav a T stop• Disk má S sektorů, H hlav a T stop. • Převod trojrozměrné adresy (s, h, t), kde s je číslo

sektoru, h je číslo hlavy a t je číslo stopy (cylindru) na jednorozměrný prostor sektorů pomocí formule j ý p p

( )tHhSs ×+×+ ( )tHhSs ×+×+

Alokační metody• Dány možností přímého přístupu na disk.• Souvislá alokace

– Každý soubor zabírá souvislou množinu bloků na disku. Adresa souboru je pak udána pouze adresou prvního bloku.

– Výhodou je malá pravděpodobnost pohybu hlavou disku.– Nevýhodou je nacházení volného místa pro soubor a obtížná

implementace dynamických změn velikosti souboru (zvětšování).• Spojovaná alokace

– Odstraňuje nevýhody souvislé alokace pospojováním bloků použitých pro soubor.

ýh d h ří j á "h ké" lik i l i í– Nevýhodou tohoto přístupu je ztráta "hezké" velikosti a relativní pomalost při náhodném přístupu do souboru.Ú j FAT kd j ý j t ř l– Úpravou je FAT, kde spojový seznam je tvořen polem na vyhrazeném místě disku.

Indexová alokace - upravuje špatný přímý přístup spojované metody umístěním indexů bloků jednotlivých souborůspojované metody umístěním indexů bloků jednotlivých souborů

pohromadě

Plánování disku

• Čas přístupu na disk je dělen na tři části:– SEEK přesun hlavy na požadovaný cylindr– LATENCY otočení disku na začátek požadovaného

ksektoru– TRANSFER přesun dat z disku/na disk

• Při velkých zátěžích v OS s více procesy nejvíce zpomaluje přístup na disk čas SEEK.

Obsluha požadavků na přístup k diskup p p

Při ři á í ž d k OS di k j ř b• Při vyřizování požadavku OS na disk je potřeba nejprve vystavit hlavy na příslušnou stopu a pak počkat, až bude požadovaný sektor pod hlavami. U víceúlohových systémů mohou přicházet požadavky v ceú o ovýc sys é ů o ou p c e po d v yna disk rychleji, než je možné je vyřizovat. V ři á í ž d ků ř dí j k ři há jí (t• Vyřizování požadavků v pořadí, jak přicházejí (tzv. FIFO nebo FCFS - First In First Out, First Come First Serve), není optimální.

FCFS (First Come First Served)FCFS (First Come, First Served) • Vhodný pro lehké zátěže• Vhodný pro lehké zátěže.• žádosti v pořadí: 98, 183, 37, 122, 14,

124, 65, 67• hlavy jsou na pozici 53hlavy jsou na pozici 53

14 37 53 65 67 12412298 18314 37 53 65 67 12412298 183

• Používají se jiné algoritmy (oba lze modifikovat vPoužívají se jiné algoritmy (oba lze modifikovat v případě, že existuje rychlý způsob, jak se dostat na stopu 0):stopu 0):– SSF (Shortest Seek First)

• máme-li hlavu na 50 cylindru a přijdou požadavky na 52, 80, 7, 49, 45 -> SSF -> bude vyřízeno v pořadí 50, 49, 52, 45, 80, 7

• dochází k diskriminaci okrajových cylindrů

– Elevátorový algoritmus ý g• totéž co automatické výtahy (nahoru -> dolů)

• pohyb hlavy je změněn na 50 52 80 49 45 7pohyb hlavy je změněn na 50, 52, 80, 49, 45, 7

SSTF (Shortest Seek Time First)SSTF (Shortest Seek Time First)• Naplánován je požadavek s nejmenším

relativním pohybem hlavy. • Existuje zde možnost že nastaneExistuje zde možnost, že nastane

starvation.

14 37 53 65 67 12412298 183

SCAN• Je určen směr pohybu hlav. Z fronty jsou

zpracovávány pouze požadavky postupně vzpracovávány pouze požadavky postupně v určeném směru. Po zpracování

jk j ějšíh ž d k ě h bnejkrajnějšího požadavku se směr pohybu hlav obrátí.

14 37 53 65 67 12412298 183

C-SCAN (Circular SCAN)C SCAN (Circular SCAN)

• posouvá hlavy pouze v jednom směru a po• posouvá hlavy pouze v jednom směru a po zpracování nejkrajnějšího požadavku přesune hl ě čá khlavy opět na začátek.

14 37 53 65 67 12412298 183

Příklad - zadání Di k t• Disk s parametry– 20 povrchů, 25 sektorů/stopu, 800 stop/povrch

512 slabik/blok 3600 ot/min– 512 slabik/blok, 3600 ot/min,– Rotační zpoždění = 16,7 ms

Průměrná doba vystavení = 28 ms (mezi válci 7 ms)– Průměrná doba vystavení = 28 ms (mezi válci 7 ms)• Slabik/stopu

Slabik/blok x bloků/stopu– Slabik/blok x bloků/stopu– 512 x 25 = 12 800 B = 12,8 kB

• Slabik/povrch• Slabik/povrch– Slabik/stopu x stop/povrch– 12 800 x 800 = 10 240 000 B = 10 24 MB12 800 x 800 10 240 000 B 10,24 MB

• Slabik/svazek– Slabik/povrch x povrchů/svazek– Slabik/povrch x povrchů/svazek– 10,24 x 20 = 204,8 MB

Doba přečtení celého disku sekvenčně ( álel po álci sek enčně)(válel po válci, sekvenčně)

• Doba přečtení stopy : 16,7 ms (doba otočky)Doba přečtení stopy : 16,7 ms (doba otočky)• Doba přečtení válce = doba přečtení stopy x

t / ál 16 7 20 334stop/válec = 16,7 x 20 = 334 ms• Doba přečtení svazku = čtení 800 válců + 799 p

vystavení = 800 x 334 + 799 x 7 = 267200 + 5593= 272793 ms = 272 793 s272793 ms 272,793 s

• Doba odpovídající čtení slabik = 273s/204,8MB = 1,33 ms/KB

Příklad - zadání• Disk s parametry

6000 á ů 200– 6000 záznamů po 200B– 1K sektor– 16 sektorů/stopu– Clustery po 4 sektorechClustery po 4 sektorech– Blokování více záznamů do sektorů

P ů ě á d b í 25– Průměrná doba vystavení = 25 ms– 3600 ot/min, rotační zpoždění = 16,7 ms

• Kolik se obsadí clusterů?• Jak dlo ho se čte cl ster/so bor?• Jak dlouho se čte cluster/soubor?

Řešení• Volí se blokovací faktor 5 (24B fragmentace při

K=1024))• Pak je 20 záznamů/cluster (4 sektory x 5)• A je třeba 300 clusterů (6000 záznamů/20)• A je třeba 300 clusterů (6000 záznamů/20)• Průměrná doba čekání na natočení na cluster =

rotační zpoždění/2= 8ms• Průměrná doba přenesení bloku =1/4stopy= rotační p py

zpoždění/4= 4 ms• Průměrná doba čtení clusteru = průměrná dobaPrůměrná doba čtení clusteru průměrná doba

vystavení 25ms + 8ms + 4 ms = 37 msP ů ě á d b čt í b 300 l t ů 37• Průměrná doba čtení souboru = 300 clusterů x 37 ms = 11,1 s

Windows XP, UNIX (Linux) architektura, vlastnosti, služby,

i t linstalace.

BIOS – Basic Input Output SystemBIOS Basic Input Output System

• Tvoří rozhraní mezi hardwarem a č í téoperačním systémem

• Provádí úvodní test po spuštění počítačep p p• Umožňuje nastavení základních parametrů

počítačepočítače• Zavádí operační systém

P k j č í é ř dk• Poskytuje operačnímu systému prostředky pro realizaci víceúlohového prostředí

Jádro OS DOS• IO.SYS (IBMBIO.COM) – příkazy a rutiny V/V

operací – načte zaváděcí sektor DOSu do operační p ppaměti a předá řízení – zůstává v paměti (mimo zavaděč)zavaděč)

• MSDOS.SYS (IBMDOS.COM) – interní příkazy a rutiny – zůstává v paměti

• COMMAND. COM – interpretCOMMAND. COM interpret – Rezidentní funkce – trvale v paměti (DIR,CLS..)

T i í f k j ě i í bý– Transientní funkce – nejsou v paměti – musí být přístupné na disku

Komponenty Windows 98p y

Windows XPWindows XP

– 32-bitová architektura Intel,– multi-uživatelský univerzální OS pro PC,– plánování – preemptivní multitasking– aplikace modelu klient-server na více různých úrovních– uplatněná architektura mikrojádrauplatněná architektura mikrojádra

• Klíčové cíle:– portabilita, přenositelnost

b č t l hli t– bezpečnost, spolehlivost– splnění norem POSIX– extensibility, rozšiřitelnost– podpora multiprocessingu– velký výkon– podpora národních klonů– slučitelnost s MS-DOS a MS-Windows aplikacemi

Architektura XP

Základní typy přechodů mezi stavyZákladní typy přechodů mezi stavy rámců

Uspořádání virtuální paměti veUspořádání virtuální paměti ve Windows XP

Princip 2 úrovňové hierarchickéPrincip 2-úrovňové hierarchické tabulky stránek v XPy

Executive – Plug-and-Play Manager

• Plug-and-Play (PnP) manager– používá se k rozpoznání a pro přizpůsobení

systému změnám konfigurace hardware– zařízení a driver musí splňovat PnP standard

• Když se přidá nové zařízení (PCI, USB) y p ( , )zavede PnP manager odpovídající driver

• PnP manager také sleduje zdroje používanéPnP manager také sleduje zdroje používané každým zařízením a zavádí potřebné drivery

Executive – Registry• vnitřní databáze• v jednotlivých úlech se pamatují• v jednotlivých úlech se pamatují

– implicitní preference uživatelů– informace o instalacích softwareinformace o instalacích software– bezpečnostní informace– . . .

• systémový úl se používá při zavádění – proto součást Executive

á j i di k hi i d bá• ex. nástroje pro periodickou archivaci databáze a pro návrat k předchozí verzi po instalaci chybné aplikace třetí stranyaplikace třetí strany

Booting – zavedení systému• zapnutí (energie) → spustí se provádění BIOS z ROM• BIOS identifikuje zařízení ze kterého se bude zavádětBIOS identifikuje zařízení, ze kterého se bude zavádět

zavlékací program – bootstrap loader• BIOS zvede zavlékací program ze zavlékacího sektoru

tohoto zařízenítohoto zařízení• Bootstrap loader zná formát systému souborů a zavede z

kořenového adresáře program NTLDRp g• NTLDR

– ze zavlékacího zařízení (boot device) zavede knihovnu HAL, jádro a systémový úl (registry)a systémový úl (registry)

– určí ze systémového úlu driver zařízení pro zavedení operačního systému (boot driver) a zavede jej a spustí jádro

. . .

Systém souborů

• alokační blok se nazývá clusterl t j t ř ji tý čt kt ů délk– cluster je tvořen jistým počtem sektorů, délka =

mocnina 2(sektor pro HD < 1 GB 1 KB pro 1 GB HD 2K pro 2(sektor pro HD < 1 GB, 1 KB pro 1 GB HD, 2K pro 2 GB HD,4 KB pro 4 GB, 32 KB pro 32 GB, 128 KB pro větší disky )

– má délku menší, než by si vynucovalo použití 16-bitové FAT vzhledem ke kapacitám používaných diskůFAT vzhledem ke kapacitám používaných disků (desítky GB),

– je tudíž minimalizovaná vnitřní fragmentaceje ud ov v g e ce

NTFS — vnitřní uspořádání• diskové adresy NTFS: pořadová čísla – logical cluster numbers

(LCNs)• soubor v NTFS

– není prostým proudem bytů jako vMS-DOS nebo v UNIXu,– je spíše strukturovaným objektem tvořeným atributy

(pojmenované atributy – jméno, přístupová práva, doba vytvoření, . . .nepojmenované atributy – data)

– je popsaný jedním nebo několika záznamy v poli (,,řádku”) uchovávaném ve speciálním souboru ( tabulce”) Master File Table (MFT)ve speciálním souboru (,,tabulce ) – Master File Table (MFT)

– zobrazení souboru –• rezidentní atributy (definice a méně rozsáhlá data) v záznamech MFT• nerezidentní atributy (nerezidentní vůči MFT) – rozsáhlé datové atributy v y ( ) y

externích alokačních blocích referencovaných z rezidentních atributů

NTFS — vnitřní uspořádáníKaždý soubor na NTFS svazku má

• vnější jméno (až 255 znaků) a• jedinečné vnitřní jméno, ID, file reference:

– 64-bitové hodnota tvořená• 48-bitovým číslem souboru

(pořadové číslo definičního záznamu souboru v MFT) a• 16-bitovým pořadovým číslem inkrementovaným každým použitím záznamu

MFT(lze použít k provádění vnitřních kontrol konzistence)( p p )

• prostor jmen NTFS je organizován do hierarchie adresářů– index jmen v každém adresáři má strukturu B+-stromu– v listech B+-stromu jsou vedle ukazatelů na data zopakovány atributy typu j p y y yp

jméno, rozměr, doba vytvoření (pro výpisy)– rychlé prohlížení – jména souborů jsou tříděná, doba prohlížení neroste

lineárně s růstem počtem souboru

Vnitřní struktura OS

UNIX

StavyStavy procesuprocesu