2011. Vysoké učení technické v Brně Fakulta informačních technologií Božetěchova 2, Brno. Úvod p

Toto jsou slajdy z předmětu IOS doplněné o mé vlastní poznámky z přednášek. Za správnost neručím, případné chyby mi oznamte, viz můj web. Milan Seitler, www.seitler.cz

ˇ systémy Operacní IOS 2010/2011

Tomáš Vojnar vojnarfit.vutbr. z

ˇ Vysoké ucení technické v Brneˇ ˇ Fakulta informacních technologií ˇ Božetechova 2, 612 66 Brno

Úvod – p.1/30

ˇ IOS na FIT VUT. Obsahují základní ❖ Tyto slajdy jsou urˇceny pro studenty pˇredmetu ˇ rením na systém UNIX. popis vývoje, struktury a vlastností operaˇcních systému˚ se zameˇ ❖ Pˇredpokládají se základní znalosti programování a pˇrehled základních pojmu˚ z oblasti poˇcítaˇcu. ˚ ˇ ˇ informace jsou ❖ Obsah slajdu˚ muže ˚ být v nekterých pˇrípadech struˇcný, podrobnejší souˇcástí výkladu: Velmi silneˇ se pˇredpokládá úˇcast na pˇrednáškách a doporuˇcuje se vytváˇret si poznámky. ❖ Pˇredpokládá se také aktivní pˇrístup ke studiu, vyhledávání informací na Internetu cˇ i v literatuˇre (jimiž doporuˇcuji si pˇrípadneˇ doplnit obsah slajdu) ˚ a také praktické experimentování s GNU/Linuxem (ˇci FreeBSD nebo podobnými UNIXovými systémy)...

Úvod – p.2/30

Motivace ❖ Operaˇcní systém je významnou cˇ ástí prakticky všech výpoˇcetních systému, ˚ jež typicky zahrnují:

• • • •

hardware, operaˇcní systém (OS), uživatelské aplikaˇcní programy a uživatele.

❖ I pro ty, kteˇrí se nebudou nikdy podílet na vývoji žádného OS, má studium OS velký význam:

• OS mají významný vliv na fungování celého výpoˇcetního systému a znalost principu˚ jejich fungování je tedy zapotˇrebí pˇri vývoji: – hardware, na kterém má bežet ˇ ˇ nejaký OS a – software, který má prostˇrednictvím nejakého ˇ OS efektivneˇ využívat zdroje ˇ platit vždy. ˇ – což by melo hardware, na kterém beží

Úvod – p.3/30

• OS jsou obvykle znaˇcneˇ komplikované systémy, jež prošly a procházejí dlouhým vývojem, pˇri kterém: – byla uˇcinena ˇ ˇrada rozhodnutí ovlivnujících ˇ filozofii vývoje poˇcítaˇcových ˇ systému˚ (otevˇrený x uzavˇrený software, ovlivnování poˇcítaˇcového trhu na ˚ ...), základeˇ vlastností OS, vývoj SW v komunitách vývojáˇru, – byla použita ˇrada zajímavých algoritmu, ˚ zpusob ˚ u˚ návrhu architektury SW, metodologií a technik softwarového inženýrství apod., jež jsou inspirující i mimo oblast OS.

ˇ ˇ ❖ Zapojení se do vývoje nekterého OS cˇ i jeho cˇ ásti není navíc zcela nepravdepodobné:

• Není napˇr. možné dodávat noveˇ vyvinutý hardware (rozšiˇrující karty apod.) bez podpory v podobeˇ ovladaˇcu˚ (driveru). ˚

• Pro potˇreby ruzných ˇ ˚ aplikací (napˇr. u vestavených poˇcítaˇcových systému) ˚ muže ˚ být zapotˇrebí vyvinout/pˇrizpusobit ˚ vhodný OS.

• Zapojení se do vývoje nekterého ˇ otevˇreného OS (Linux, FreeBSD, mikrojádra typu Hurd cˇ i L4, ...) je znaˇcnou intelektuální výzvou a muže ˚ pˇrinést pˇríslušné intelektuální uspokojení.

Úvod – p.4/30

Organizace studia ❖ Pˇrednáška:

• 3h/týden • principy a vlastnosti operaˇcních systému˚ (UNIX obvykle jako pˇrípadová studie) • UNIX z uživatelského a cˇ ásteˇcneˇ programátorského pohledu ❖ Samostatná práce:

• min. 2h/týden • samostudium, experimenty, ..., úkoly ❖ Hodnocení: projekty pulsem. ˚ zkouška semestrální zkouška celkem

30b 0b (!) 70b 100b

(zápoˇcet: min 15b – tj. ne 14b, ne 13b, ...) (minimum: 32b – tj. ne 31b, ne 30b, ...)

ˇ ˇ Pro ilustraci: v lonském roce úspešnost cca 52%. Úvod – p.5/30

Zdroje informací ❖ WWW stránky kursu: http://www.fit.vutbr. z/study/ ourses/IOS/publi / ❖ Diskusní fóra kursu: jsou dostupná v IS FIT – diskutujte! ❖ Literatura: koupit cˇ i vypujˇ ˚ cit (napˇr. v knihovneˇ FIT, ale i v jiných knihovnách).

• Je-li nekterá ˇ ˇ ˇ kniha dlouhodbeˇ vypujˇ ˚ cena nekterému zamestnanci, neváhejte a kontaktujte ho. ❖ Internet:

• vyhledávaˇce (google, ...); cˇ asto jsou užiteˇcné dokumenty typu HOWTO, FAQ, ... • encyklopedie: http://www.wikipedia.org/ – velmi vhodné pˇri prvotním oveˇ ˇ rování ˇ nekterých bodu˚ z pˇrednášek pˇri studiu, lze pokraˇcovat uvedenými odkazy – nutné ˇ rování. kˇrížové oveˇ

• NetNews: omp.os.* • dokumentaˇcní projekty: http://www.tldp.org/, ... ❖ UNIX, Linux: program man („RTFM!“), GNU info a další dokumentace (/usr/share/do , /usr/lo al/share/do ), ... Úvod – p.6/30

Literatura [1] Silberschatz, A., Galvin, P.B., Gagne, G.: Operating Systems Concepts, 8th ed., John Wiley & Sons, 2008. (Významná cˇ ást pˇrednášek je založena na tomto textu.) [2] Tanenbaum, A.S.: Modern Operating Systems, 2nd ed., Prentice Hall, 2001. [3] Tanenbaum, A.S., Woodhull, A.S.: Operating Systems Design and Implementation, 3rd ed., Prentice Hall, 2006. [4] Raymond, E.S.: The Art Of Unix Programming, Addison-Wesley, 2003. http://www. atb.org/esr/writings/taoup/html/ [5] Russinovich, M., Solomon, D.: Windows Internals, 5th ed., Microsoft Press, 2009. [6] Skoˇcovský, L.: Principy a problémy operaˇcního systému UNIX, 2. vydání, 2008. http://sko ovsky. z/paposu2008/ ˇ Uvedeny jsou pouze nekteré základní, zejména pˇrehledové knihy. Existuje samozˇrejmeˇ ˇrada dalších knih, a to vˇcetneˇ knih specializovaných na detaily ruzných ˚ subsystému˚ ˇ souborové systémy, ovladaˇce, ...). Tyto operaˇcních systému˚ (plánovaˇc, správa pameti, ˇ ˚ které uvádejí knihy cˇ asto vycházejí pˇrímo ze zdrojových kódu˚ pˇríslušných subsystému, s pˇríslušným komentáˇrem.

Úvod – p.7/30

Základní pojmy

Úvod – p.8/30

Význam pojmu operaˇcní systém ❖ Operaˇcní systém je program, resp. kolekce programu, ˚ která vytváˇrí spojující mezivrstvu ˇ mezi hardware výpoˇcetního systému (jenž muže ˚ být nekdy virtualizován) a uživateli a jejich uživatelskými aplikaˇcními programy.

ˇ ❖ Cíle OS – kombinace dvou základních, do jisté míry protichudných ˚ cílu, ˚ jejichž pomer se volí dle situace:

• Maximální využití zdroju˚ poˇcítaˇce (drahé poˇcítaˇce, levnejší ˇ pracovní síla; zejména dˇríve).

• Jednoduchost použití poˇcítaˇcu˚ (levné poˇcítaˇce a drahá pracovní síla; dnes pˇrevažuje). dnes důraz kladen spíše na jednoduchost použití

Úvod – p.9/30

❖ Dveˇ základní role OS:

sdílení přístupu ke zdrojů, snaha řídit co nejefektivněji, ale také bezpečně. např. zajisití, aby se nepřepisovala data různých uživatelů

• Správce prostˇredku˚ (pamet’, ˇ procesor, periferie). – Dovoluje sdílet prostˇredky efektivneˇ a bezpeˇcne. ˇ – Více procesu˚ sdílí procesor, více programu˚ sdílí pamet’, ˇ více uživatelu˚ a souboru˚ obsazuje diskový prostor, ...

• Tvurce ˚ prostˇredí pro uživatele a jejich aplikaˇcní programy (tzv. virtuálního poˇcítaˇce). – Poskytuje standardní rozhraní, které zjednodušuje pˇrenositelnost aplikací a zauˇcení uživatelu. ˚ – Poskytuje abstrakce: ◦ Technické vybavení je složité a znaˇcneˇ ruznorodé ˚ – práci s ním je nutné zjednodušit. ◦ Problémy abstrakcí: menší efektivita, nepˇrístupné nekteré ˇ ˇ nízkoúrovnové operace. ◦ Pˇríklady abstrakcí: procesa , souborb , virtuální pamet’, ˇ ... např. soubory jako přístup k disku, či "vlastní" paměť pro každý proces. abstrakce spotřebovává výkon

a

ˇ Program: pˇredpis, návod na nejakou cˇ innost zakódovaný vhodným zpusobem ˚ (zdrojový text, binární program). Proces: cˇ innost ˇrízená programem. proces = běžící program b ˇ jako základní jednotka pro ukládání Soubor: kolekce záznamu˚ sloužící (primárne) ˇ ˇ dat na vnejších pamet’ových médiích. Adresáˇr: kolekce souboru. ˚ Úvod – p.10/30

ˇ cˇ as procesoru). ❖ Výše uvedené není zadarmo! OS spotˇrebovává zdroje (pamet’,

❖ OS se obvykle chápe tak, že zahrnuje:

• jádro (kernel), • systémové knihovny a utility (systémové aplikaˇcní programy), • textové a/nebo grafické uživatelské rozhraní.

běží nad jádrem

❖ Pˇresná definice, co vše OS zahrnuje, však neexistuje:

• Nekdy ˇ ˇ bývá OS ztotožnován takˇrka pouze s jádrem. • GNU – GNU is Not UNIX : Projekt vývoje „svobodného“ (free) OS, který zahrnuje jádro (Linux, Hurd), utility, knihovny a grafické i textové rozhraní (gcc, gdb, bash, Gnome, KDE, ...) i ˇradu dalších programu˚ (vˇcetneˇ kanceláˇrských programu˚ a her)...

• Microsoft Windows: Je cˇ i není prohlížeˇc Internetu cˇ i pˇrehrávaˇc videa nedílnou souˇcástí OS?

Úvod – p.11/30

Jádro OS ˇ cˇ ást OS. ❖ Jádro OS je nejnižší a nejzákladnejší

• Zavádí se první a beží ˇ po celou dobu behu ˇ poˇcítaˇcového systému (tzv. reaktivní spíše než transformaˇcní program).

transformační program = zpracuje vstup, předloží výstup, např překladač reaktivní program = běží dokud není ukončen

• Navazuje pˇrímo na hardware, pˇríp. virtualizovaný HW, a typicky ho pro uživatele a uživatelské aplikace zcela zapouzdˇruje.

uživatel a aplikace nemohou komunikovat přímo s HW, jsou potřeba knihovny, ovladače

• Beží ˇ obvykle v privilegovaném režimu. – V tomto režimu lze obvykle provádet ˇ libovolné operace nad HW poˇcítaˇce. – Za úˇcelem oddelení ˇ a ochrany uživatelu˚ a jejich aplikaˇcních programu˚ nesmí tyto mít možnost do tohoto režimu libovolneˇ vstupovat. aplikace běží v neprivilegovaném režimu – Nutná HW podpora v CPU.

• Zajišt’uje nejzákladnejší ˇ správu prostˇredku˚ a tvorbu prostˇredí pro vyšší vrstvy OS a uživatelské aplikace.

Úvod – p.12/30

❖ Systémové i uživatelské aplikaˇcní programy mohou explicitneˇ žádat jádro o služby ˇ se tak pˇrímo nebo nepˇrímo prostˇrednictvím systémových volání (system call). Deje s využitím specializovaných instrukcí (napˇr. u x86 softwarové pˇrerušení nebo SYSCALL/SYSENTER), které zpusobí ˚ kontrolovaný pˇrechod do režimu jádra. jádro ověří žádost, pokud vyhoví, začne službu vykonávat

❖ Rozlišujeme dva typy rozhraní:

• Kernel Interface: pˇrímé volání jádra specializovanou instrukcí • Library Interface: volání funkcí ze systémových knihoven, které mohou (ale nemusí) vést na volání služeb jádra např printf, volá nejdřív knihovnu, ta až jádro

Applications Library Interface Libraries Kernel Interface Kernel HW Interface Hardware

Úvod – p.13/30

Typy jader OS ❖ Monolitická jádra:

• Vytváˇrí vysokoúrovnové ˇ komplexní rozhraní s ˇradou služeb a abstrakcí nabízených vyšším vrstvám.

• Všechny moduly implementující tyto služby (správa pameti, ˇ plánování, meziprocesová komunikace, souborové systémy, podpora sít’ové komunikace ˇ v privilegovaném režimu a jsou tesn ˇ eˇ provázané za úˇcelem vysoké apod.) beží efektivity. méně bezpečné, selhání jedné části, může ohrozit zbytek systému

❖ Vylepšením koncepce monolitických jader jsou monolitická jádra s modulární strukturou:

• Umožnuje ˇ ˇ ˇ ˇ zavádet/odstra novat subsystémy jádra za behu. • Napˇr. FreeBSD cˇ i Linux (lsmod, modprobe, rmmod, ...) např ovladače zařízení, lze je odpojit, když zařízení není potřeba

Úvod – p.14/30

❖ Mikrojádra:

• Minimalizují rozsah jádra a nabízí jednoduché rozhraní, s jednoduchými ˇ a abstrakcemi a malým poˇctem služeb pro správu procesoru, pameti meziprocesové komunikace.

• Vetšina ˇ služeb nabízených monolitickými jádry (vˇcetneˇ napˇr. ovladaˇcu, ˚ ˇ cˇ i plánování) je implementována mimo mikrojádro významných cˇ ástí správy pameti ˇ v privilegovaném režimu. komunikují prostřednictvím zpráv řízeních v tzv. serverech, jež nebeží mikrojádrem

• Pˇríklady mikrojáder: Mach, QNX, L4 (pouhých 7 služeb oproti více než 200 u jádra 2.6 Linuxu; verze L4: Fiasco, Pistachio, seL4, ...), ...

• Výhody mikrojáder: – Flexibilita – možnost více souˇcasneˇ bežících ˇ implementací ruzných ˚ služeb, serverů zaráz, aktualizace za běhu, ˇ jejich dynamické spouštení, zastavování apod. spouštění stejné servery pro různé úlohy – Zabezpeˇcení – servery nebeží ˇ v privilegovaném režimu, chyba v nich/útok na neˇ neznamená ihned selhání/ovládnutí celého OS.

• Nevýhoda mikrojáder: vyšší režie – výrazneˇ vyšší u mikrojader 1. generace (Mach), lepší je situace u (stále experimentálních) mikrojader 2. generace (napˇr. L4: minimalismus, optimalizace pro konkrétní architekturu), nicméneˇ tato nevýhoda pˇretrvává. Úvod – p.15/30

❖ Hybridní jádra:

• Mikrojádra rozšíˇrená o kód, který by mohl být implementován ve formeˇ serveru, ale ˇ eji ˇ provázán s mikrojádrem a beží ˇ v jeho režimu. je za úˇcelem menší režie tesn

• Pˇríklady: Mac OS X (Mach kombinovaný s BSD), Windows NT (a vyšší), ...

❖ Exojádra:

• Experimentální jádra poskytující velmi nízké rozhraní zameˇ ˇ rené hlavneˇ na bezpeˇcné sdílení prostˇredku˚ (a ne na tvorbu abstrakcí cˇ i standardního rozhraní). ˇ ˇ eˇ jádrem. Doplneno o knihovny implementující služby jinak nabízené bežn

• Pˇríklady: Aegis, Nemesis, ... tento typ se zatím příliš neuplatnil

Úvod – p.16/30

Historie vývoje OS ❖ Je nutné znát historii, protože se opakuje... :-)

❖ První poˇcítaˇce: často se opakující úlohy, např

• Knihovna podprogramu˚ (napˇríklad pro vstup a výstup) – zárodek OS. alokace, dealokace • Dávkové zpracování: duležité ˚ je vytížení stroje, jednoduchá podpora OS pro ˇ jednotlivých úloh seˇrazených operátory do dávek. postupné provádení

snaha optimalizovat výkon

• Multiprogramování – více úloh zpracovávaných souˇcasne: ˇ – Pˇrekrývání cˇ innosti procesoru a vstup/výstupního podsystému (vyrovnávací ˇ pˇrerušení). pameti, – Zatímco jedna úloha beží, ˇ jiná muže ˚ cˇ ekat na dokonˇcení I/O (problém: ˇ ˇrešeno technickými prostˇredky). ochrana pameti, – OS zaˇcíná být významnou cˇ ástí programového vybavení (nevýhoda: OS ˇ zatežuje poˇcítaˇc).

Úvod – p.17/30

ˇ ❖ Pˇríchod levnejších poˇcítaˇcu: ˚

cca 70. léta

• Interaktivnost, produktivita práce – lidé neˇcekají na dokonˇcení zpracování dávky. • Stále se ješteˇ nevyplatí každému uživateli dát poˇcítaˇc – terminály a sdílení cˇ asu: ˇ více aplikací na jednom procesoru. timesharing/multitasking, tj. „souˇcasný“ beh

• • • •

Problém odezvy na vstup: preemptivní plánování úloha . ˇ Oddelené ukládání dat uživatelu: ˚ systémy souboru. ˚ Problémy s pˇretížením poˇcítaˇce mnoha uživateli. OS ˇrídí sdílení zdroju: ˚ omezené použití prostˇredku˚ uživatelem (priority, quota).

a Nepreemptivní plánování: Procesor muže ˚ být procesu odebrán, pokud požádá jádro

ˇ o nejakou službu (I/O operaci, ukonˇcení, vzdání se procesoru). Preemptivní plánování: ˇ OS muže ˚ procesu odebrat procesor i „ proti jeho vuli“ ˚ (tedy i když sám nežádá o nejakou službu jádra), a to na základeˇ pˇríchodu pˇrerušení pˇri urˇcité události (typicky pˇri vypršení ˇ cˇ asového kvanta, ale také dokonˇcení I/O operace jiného procesu apod.). pˇrideleného

Úvod – p.18/30

ˇ poˇcítaˇce: ❖ Ješteˇ levnejší

• Každý uživatel má svuj ˚ poˇcítaˇc, který musí být levný a jednoduchý (omezená ˇ chybející ˇ ˇ jednoduchý OS – na poli OS jde o návrat zpet: ˇ pamet’, ochrana pameti, CP/M, MS-DOS).

• Další pokrok v technologiích – síte, ˇ GUI. • Nové OS opet ˇ získávají vlastnosti starších systému˚ (propojení pˇres sít’ si opet ˇ vynucuje patˇriˇcné ochrany, ...). do jednoduchých OS se postupně doplňují funkce ze složitějších OS - ochrana, multitasking...

❖ Malé (a prozatím nepˇríliš výkonné) kapesní poˇcítaˇce s omezenými vlastnostmi OS...

Úvod – p.19/30

Pˇrehled technického vybavení

CPU

Procesor: ˇradiˇc, ALU, registry (IP, SP), instrukce paměť CPU - registry

MEMORY

BUS

I/O

ˇ adresa, hierarchie Pamet’: ˇ (cache, ...) pametí

1. registry 2. cache 3. RAM 4. disková paměť

Periferie: disk, klávesnice, monitor, (pˇrerušení, DMA) ˇ Sbernice: FSB, HyperTransport, QPI, PCI, USB, IEEE1394, ATA/SATA, SCSI, SAS, ...

Úvod – p.20/30

Klasifikace poˇcítaˇcu˚ ❖ Klasifikace poˇcítaˇcu˚ podle úˇcelu:

• univerzální, • specializované: – vestavené ˇ (ˇrízení technologických zaˇrízení, palubní poˇcítaˇce, spotˇrební elektronika, ...), – aplikaˇcneˇ orientované (databázové, Lisp, ...), – vývojové, ... ❖ Klasifikace poˇcítaˇcu˚ podle výkonnosti:

• • • • • •

ˇ vestavené poˇcítaˇce, handheldy, mobily, ..., osobní poˇcítaˇce (personal computer), pracovní stanice (workstation), servery, stˇrediskové poˇcítaˇce (mainframe), superpoˇcítaˇce. Úvod – p.21/30

Klasifikace OS ❖ Klasifikace OS podle úˇcelu:

• univerzální (UNIX, Windows, Linux, ...), • specializované: – real-time (QNX, RXS, RT-Linux, ...), – databáze, web, ... (napˇr. z/VSE), – mobilní zaˇrízení (Symbian, ...), ... ❖ Klasifikace OS podle poˇctu uživatelu: ˚

• jednouživatelské (CP/M, MS-DOS, ...) a • víceuživatelské (UNIX, Windows, ...). ˇ ❖ Klasifikace OS podle poˇctu souˇcasneˇ bežících úloh:

• jednoúlohové a • víceúlohove (multitasking: ne/preemptivní).

Úvod – p.22/30

Pˇríklady dnes používaných OS typ poˇcítaˇce mainframe superpoˇcítaˇce server PC real-time handheldy, mobily

pˇríklady OS MVS, z/OS, VM/CMS, VM/Linux, z/VSE cˇ asto varianty UNIXu/Linuxu, Windows HPC UNIX, FreeBSD, WinNT/2000/XP, Linux MacOS X, Windows 98/2000/XP, Linux QNX, RT-Linux PalmOS, Symbian, Windows CE, Linux

Úvod – p.23/30

Implementace OS ❖ OS se obtížneˇ programují a ladí, protože to jsou

• velké programové systémy, • paralelní a asynchronní systémy, • systémy závislé na technickém vybavení. ❖ Z výše uvedeného plyne:

• Jistá setrvaˇcnost pˇri implementaci: snaha nemenit ˇ kód, který již spolehliveˇ pracuje. • Používání ˇrady technik pro minimalizaci chyb, napˇr.: – inspekce zdrojového kódu (duraz ˚ na srozumitelnost!), – rozsáhlé testování, – podpora vývoje technik automatizované (formální) verifikace.

Úvod – p.24/30

ˇ ve vývoji OS Hlavní smery • Pokroˇcilé architektury (mikrojádra, hybridní jádra, ...): zdurazn ˇ výhod, ˚ ení ˇ minimalizace nevýhod, možnost kombinace ruzných, ˚ souˇcasneˇ bežících OS, ...

• • • • • • • •

Bezpeˇcnost a spolehlivost. Podpora hard real-time (prumyslové ˚ procesy), soft real-time (multimédia). Multiprocessing (SMP, ...). Virtualizace. Distribuované zpracování, clustery, gridy. ˇ OS kapesních poˇcítaˇcu˚ (handheld), vestavených systému, ˚ mobilu, ˚ ... Vývoj nových technik návrhu a implementace OS (podpora formální verifikace, ...). ...

Úvod – p.25/30

Základy práce s UNIXem

Úvod – p.26/30

Studentské poˇcítaˇce s UNIXem na FIT • studentské UNIXové servery: eva (FreeBSD), merlin (Linux/CentOS) • PC s Linuxem (CentOS): bežn ˇ eˇ na uˇcebnách (dual boot) ❖ Pˇrihlášení: Login: xnovak00 Password: # neopisuje se - zmˇ ena: pˇ rı ´kaz passwd ... $ # prompt - vyz´ yvac´ ı znak shellu ❖ Vzdálené pˇrihlášení:

• programy/protokoly pro vzdálení pˇrihlášení: ssh, telnet (telnet neužívat!) • putty – ssh klient pro Windows

Úvod – p.27/30

Základní pˇríkazy ❖ Práce s adresáˇri a jejich obsahem:

• cd – change directory • pwd – print working directory • ls [-al] – výpis obsahu adresáˇre/informace o souborech • mkdir – make a directory • rmdir – remove a directory • mv – pˇresun/pˇrejmenování souboru/adresáˇre (move) • cp [-r] – kopie souboru/adresáˇre (copy) • rm [-ir] – smazání souboru/adresáˇre (remove)

Úvod – p.28/30

❖ Výpis obsahu souboru:

• • • •

ˇ cat – spojí nekolik souboru˚ na std. výstup more/less – výpis po stránkách head -13 FILE – prvních 13 ˇrádku˚ tail -13 FILE – posledních 13 ˇrádku˚

• file FILE – informace o typu obsahu souboru

Úvod – p.29/30

Speciální znaky • • • •

^C – ukonˇcení procesu na popˇredí ^Z – pozastavení procesu na popˇredí (dále bg/fg) ^S/^Q – pozastavení/obnovení výpisu na obrazovku ^\ – ^C a výpis „core dump“

• ^D – konec vstupu ($^D ukonˇcí shell) • ^H – smazání posledního znaku (backspace) • ^W – smazání posledního slova • Û – smazání souˇcasného ˇrádku

Úvod – p.30/30




Úvod do UNIXu – p.1/15

Unix – úvod


Historie UNIXu ❖ 1961: CTSS (Compatible Time-Sharing System)

první systém který podporoval multitasking email, podpora pro zpracování textu, zárodek shellu

❖ 1965: MULTICS – Multiplexed Information and Computation Service (Bell Labs, MIT, General Electric) založen na multitaskingu, nebyl realizován, byl příliš velkolepý koncepty - hierachická struktura souborů, ACL, dynamická rekonfigurace...

❖ 1969: Zaˇcátek vývoje nového OS – PDP 7 (K. Thompson, D. Ritchie) ❖ 1970: Zavedeno jméno UNIX

PDP7 - nevýkonný počítač

implementováno v asembleru

❖ 1971: PDP-11 (24KB RAM, 512KB disk) – text processing ❖ 1972: asi 10 instalací ❖ 1973: UNIX pˇrepsán do C ˇ ❖ 1974: Clánek: „Unix Timesharing System“, asi 600 instalací ❖ 1977: Berkeley Software Distribution – BSD

pvní klon Unixu

❖ 1978: SCO (Santa-Cruz Operation) – první Unixová spoleˇcnost ❖ 1980:

1979 - vzniká Version 7 Unix - moderní podoba Unixu, která přetrvala dodnes

v 70. letech začal vznikat ARPANET, zárodek internetu

• DARPA si vybrala UNIX jako platformu pro implementaci TCP/IP. • Microsoft a jeho XENIX Úvod do UNIXu – p.3/15

❖ 1981: Microsoft, smlouva s IBM, QDOS, MS-DOS ❖ 1982: Sun Microsystems

vývojáři Unixu nejevili zájem o PC, toho využívá Microsoft

❖ 1983:

• AT&T UNIX System V • BSD 4.2 – sít’ TCP/IP • GNU, R. Stallman ❖ 1984: X/OPEN XPG ❖ 1985: POSIX (IEEE)

komerční verze Unixu, zdrojový kód uzavřen => Unixové války, přichází vývoj mnoha různých verzí Unixu

snaha zavést standardy, v začátcích nepříliš úspěšné

❖ 1987: AT&T, SUN: System V Release 4 a OSF/1 ❖ 1990: ❖ 1991: ❖ 1992: ❖ 1994:

Windows 3.0 první MS rozhraní s okny Solaris, Linux Linux - autorem Linus Torvalds, nový Unixový systém pro PC 386BSD verze pro PC Single Unix Specification (The Open Group)

❖ 1998:

• zaˇcátek prací na slouˇcení základu SUS a POSIX • open source software ❖ 2002: SUS v3 – zahrnuje POSIX, poslední revize 2008 (SUS v4)

posix = přenositelné rozhraní


ˇ Pˇríˇciny úspechu ˇ ❖ Mezi pˇríˇciny úspechu UNIXu lze zaˇradit:

• • • • • • • • •

víceprocesový, víceuživatelský, napsán v C – pˇrenositelný,

usnadňovalo pochopitelnost

ˇ šíˇren ve zdrojovém tvaru, zpoˇcátku (a pozdeji) na kladen na dekomponování základních algoritmů, udržování stabilních „mechanism, not policy“, důraz základních funkcí, nad kterými je možné tvořit nové či "módní" součásti

„fun to hack“,

čitelný a přehledný kód

jednoduché uživatelské rozhraní,

základem je textový příkazový řádek

ˇ skládání složitejších programu˚ z jednodušších, např. používání rour, přesměrování vstupu a výstupu hierarchický systém souboru, ˚ konzistentní rozhraní periferních zaˇrízení, ...

ˇ ˇ z techto myšlenek je inspirující i mimo oblast OS. ❖ Rada


Varianty UNIXu ˇ ❖ Hlavní vetve OS UNIXového typu:

• • • •

UNIX System V

tvořen skupinou AT&T

BSD UNIX ruzné ˚ firemní varianty (AIX, Solaris, ...) Linux

❖ Související normy:

• • • • • •

XPG – X/OPEN

"mrtvé" normy

SVR4 – AT&T a SUN OSF/1 Single UNIX Specification POSIX – IEEE standard Single UNIX Specification v3/v4 – shell a utility (CLI) a API


Základní koncepty

procesy - abstrakce aktivit, výpočtů,... soubory - abstrakce dat

❖ Dva základní koncepty/abstrakce v UNIXu: procesy a soubory.

I/O

Process

File

File IPC

Process

Process

File Process

File

ˇ IPC = Inter-Process Communication – roury (pipes), signály, semafory, sdílená pamet’, sockets, RPC, zprávy, streams... (způsoby komunikace) I/O = Input/Output Úvod do UNIXu – p.7/15

Struktura jádra UNIXu APPLICATIONS

❖ Základní podsystémy UNIXu: libraries

• Správa souboru˚

user−level

(File Management) system call interface

• Správa procesu˚ (Process Management) rozhraní s HW - komunikace s CPU (nastavování režimu procesoru...) , řadičemi přerušení, periferiemi, pamětí,...

kernel File system management

Process Management − Interprocess communication

HAL - zapouzdřuje nejnižší detaily HW, umožňuje přenositelnost

− Memory management správa souborů - ke komunikaci s HAL využívá ovladače, nepřistupuje přímo rozhraní systémových volání - aplikace většinou komunikují s jádrem prostřednictvím knihoven, kontroluje volání aplikací (např. zda mají právo k jádru přistupovat)

− Scheduler

buffers

block

character drivers

hardware abstraction layer processor

i/o

interrupts

HARDWARE


Komunikace s jádrem ❖ Služby jádra – operace, jejichž realizace je pro procesy zajišt’ována jádrem. Explicitneˇ je možno o provedení urˇcité služby žádat prostˇrednictvím systémového volání („system call“). ˇ ❖ Pˇríklady nekterých služeb jádra dostupných systémovým voláním v UNIXu: např. volání printf -> ..magie.. -> write

služba

jaká operace se provede

open close read write kill fork exec exit

otevˇre soubor zavˇre soubor cˇ te ze souboru zapisuje pošle signál duplikuje proces pˇrepíše kód ukonˇcí proces

nahradí funkci současného procesu jiným kódem


❖ HW pˇrerušení (hardware interrupts) – mechanismus, kterým HW zaˇrízení oznamují jádru asynchronneˇ vznik událostí, které je zapotˇrebí obsloužit. asynchronní = nezávislé na činnosti jádra

• Žádosti o HW pˇrerušení pˇrichází jako elektrické signály do ˇradiˇce pˇrerušení.

HW prvek

Na PC dˇríve PIC, nyní APIC (distribuovaný systém: každý procesor má lokální APIC, externí zaˇrízení mohou být pˇripojena pˇrímo nebo pˇres I/O APIC – souˇcást chip setu). • Pˇrerušení mají pˇriˇrazeny priority, dle kterých se oznamují procesoru. • Pˇrijme-li procesor pˇrerušení s urˇcitým cˇ íslem (tzv. interrupt vector) vyvolá odpovídající obslužnou rutinu (interrupt handler) na základeˇ tabulky pˇrerušení, pˇriˇcemž automaticky pˇrejde do privilegovaného režimu. ˇ • Radiˇ ˇ c muže ˚ být naprogramován tak, že nekterá pˇrerušení jsou maskována, ˇ pˇrípadneˇ jsou maskována všechna pˇrerušení až po urˇcitou prioritní úroven. Interrupt controller IRQ signals

masked?

HW errors

masked? high

Processor Interrupt vector table

interrupt number

Priority

tabulka přerušení = pole ukazatelů na funkce, indexováno číslem přerušení

Clock Disk i/o

Pointers to interrupt handlers

Keyboard ......

low NMI, exceptions

processor enables interrupts? interrupts not SW disabled? Úvod do UNIXu – p.10/15

❖ Pˇríjem nebo obsluhu HW pˇrerušení lze také zakázat:

blokování přerušení - maskování na řadiči - zakázaní na procesoru - procesor přerušení přijme, ale nevykoná žádnou akci

• na procesoru (instrukce CLI/STI na Intel/AMD), • cˇ isteˇ programoveˇ v jádˇre (pˇrerušení se pˇrijme, ale jen se poznamená jeho pˇríchod a dále se neobsluhuje). ❖ NMI (non-maskable interrupt): HW pˇrerušení, které nelze zamaskovat na ˇradiˇci ani zakázat jeho pˇríjem na procesoru (typicky pˇri chybách HW bez možnosti zotavení: chyby ˇ sbernice ˇ ˇ ˇ cˇ i ˇrešení uváznutí v jádˇre: “NMI watchdog”). pameti, apod., nekdy také pro ladení ❖ Pˇrerušení také vznikají pˇrímo v procesoru – synchronní pˇrerušení, výjimky (exceptions):

• trap: po obsluze se pokraˇcuje další instrukcí (breakpoint, pˇreteˇcení apod.), • fault: po obsluze se (pˇrípadne) ˇ opakuje instrukce, která výjimku vyvolala (napˇr. ˇ výpadek stránky, delení nulou, chybný operaˇcní kód apod.),

• abort: nelze urˇcit, jak pokraˇcovat, provádení ˇ se ukonˇcí (napˇr. nekteré ˇ zanoˇrené výjimky typu fault, chyby HW detekované procesorem – tzv. „machine check např odložení paměti procesu na disk, proces mechanism“). nemůže pracovat, data se vrátí do paměti, znovu se provede instrukce procesu


❖ Pˇri obsluze pˇrerušení je zapotˇrebí dávat pozor na souˇcasný pˇríchod více pˇrerušení a možnost pˇrerušení obsluhy pˇrerušení:

• Nutnost synchronizace obsluhy pˇrerušení tak, aby nedošlo k nekonzistencím ve stavu jádra díky interferenci cˇ ásteˇcneˇ provedených obslužných rutin.

různé obsluhy přerušení by si mohly přepisovat data

• Využívají se ruzné ˚ mechanismy vylouˇcení obsluhy pˇrerušení (viz pˇredchozí slajd). • Pˇri vylouˇcení obsluhy je zapotˇrebí venovat ˇ ˇ po kterou je obsluha pozornost dobe, vylouˇcena: – muže ˚ dojít ke ztráteˇ pˇrerušení (nezaznamenají se opakované výskyty), např. 5 přerušení disku po sobě – zvyšuje se latence (odezva systému), – výpoˇcetní systém se muže ˇ cˇ asu, ˚ dostat do nekonzistentního stavu (zpoždení ˇ ztráta pˇrehledu o situaci vneˇ jádra, neprovedení nekterých akcí v hardware, ˇ apod.). pˇreteˇcení vyrovnávacích pametí

• Vhodné využití priorit, rozdelení ˇ obsluhy do více cˇ ástí (viz další slajd).


ˇ ˇ ❖ Obsluha pˇrerušení je cˇ asto rozdelena na dveˇ úrovne:

• 1. úroven: ˇ měla by být co nejkratší – Zajišt’uje minimální obsluhu HW (pˇresun dat z/do bufferu apod.) a plánuje beh ˇ ˇ obsluhy 2. úrovne. – Behem ˇ obsluhy na této úrovni muže ˚ být zamaskován pˇríjem dalších pˇrerušení stejného typu, stejné cˇ i nižší priority, pˇrípadneˇ i všech pˇrerušení.

• 2. úroven: ˇ – Postupneˇ ˇreší zaznamenaná pˇrerušení, nemusí zakazovat pˇrerušení. – Vzájemné vylouˇcení se dá ˇrešit bežnými ˇ synchronizaˇcními prostˇredky ˇ kde by se blokoval proces, v rámci (semafory apod. – nelze u 1. úrovne, kterého pˇrerušení vzniklo). – Mohou zde být samostatné úrovneˇ priorit. – Obsluha muže ˇ ˚ bežet ve speciálních procesech (interrupt threads ve FreeBSD, tasklety/softIRQ v Linuxu).


❖ Mohou existovat i další speciální typy pˇrerušení, která obsluhuje procesor zcela specifickým zpusobem, ˚ cˇ asto mimo vliv jádra. Napˇr. na architekturách Intel/AMD:

• Interprocessor interrupt (IPI): umožnuje ˇ ˇ SW bežícímu na jednom procesoru poslat ˇ urˇcité pˇrerušení jinému (nebo i stejnému) procesoru – využití napˇr. pro zajištení ˇ ˇ ve víceprocesorovém systému (TLB), koherence nekterých vyrovnávacích pametí pˇredávání obsluhy pˇrerušení cˇ i v rámci plánování. vyvažování výkonu, rozkládá zátěž mezi procesory

• System management interrupt (SMI): generováno HW i SW, zpusobí ˚ pˇrechod do tzv. system management mode (SMM) procesoru. režim správy systému (HW, ne SW) – V rámci SMM beží ˇ firmware, který muže ˚ být využit k optimalizaci spotˇreby energie, obsluhu ruzných ˚ chybových stavu˚ (pˇrehˇrátí) apod. – Po dobu behu ˇ SMM jsou prakticky vylouˇcena ostatní pˇrerušení, což muže ˚ zpusobit ˚ zpožd’ování cˇ asu v jádˇre a pˇrípadné další nekonzistence stavu jádra oproti okolí, které mohou vést k pádu jádra.

• HW signály jako RESET, INIT, STOPCLK, FLUSH apod.


A a B běží v režimu multitaskingu

❖ Pˇríklad komunikace s jádrem:

Jádro neběží, čeká na volání služeb -> proces potřebuje číst, jádro začne pracovat, zkontroluje službu read, zadá úkoly HW, nechá HW pracovat, proces pozaství, jádro opět čeká -> práce HW, proces B dále běží -> proces B potřebuje číst, jádro opět nastaví činnost HW, proces B čeká, jádro čeká -> disk oznámí dokončení operace (přerušení), jádro zkontroluje, která operace je hotová, dokončí obsluhu čtení, aktivuje zpět proces B, jádro čeká -> disk dokončí další operaci, jádro opět obslouží data a proces A pokračuje

• synchronní: proces-jádro • asynchronní: hardware-jádro time

Process A

read()

return from read() sleep

Process B

Kernel

read()

return from read() user mode kernel mode interrupts Disk





Shell a utlity UNIXu – p.1/66

Programování v UNIXu: pˇrehled


Nástroje programátora ❖ Prostˇredí pro programování zahrnuje:

• • • • • • • •

API OS a ruzných ˚ aplikaˇcních knihoven,

API = aplikační rozhraní

CLI a GUI, editory, pˇrekladaˇce a sestavovaˇce/interprety, ladící nástroje, nástroje pro automatizaci pˇrekladu, ... dokumentace.

❖ CLI a GUI v UNIXu:

• CLI: shell (sh, ksh, csh, bash, dash, ...) • GUI: X-Window

textová příkazová řádka


X-Window Systém ❖ Základní charakteristiky:

není součástí jádra

• grafické rozhraní typu client-server, nezávislé na OS, umožnující ˇ vzdálený pˇrístup, (organizace) • otevˇrená implementace: XFree86/X.Org, • mechanismy, ne politika — výhoda cˇ i nevýhoda? různé tvary oken, tlačítek,.. postaveny nad základními mechanismy

❖ X-server: zobrazuje grafiku, ovládá grafický HW, myš, klávesnici...; s aplikacemi a správcem oken komunikuje pˇres X-protokol. komponenty X-Window System mohou běžet na různých uzlech v síti ˇ ˇ ❖ Window Manager: správce oken (dekorace, zmena pozice/rozmeru, ...); s aplikacemi komunikuje pˇres ICCM protokol (Inter-Client Communication Protocol). ❖ Knihovna xlib: standardní rozhraní pro aplikace, implementuje X-protokol, ICCM, ...

X−application

X−server

xlib libc kernel HW

libc kernel HW

X−protocol Network

X-server musí běžet na uzlu, ke kterému je připojen vstup/výstup

Display Keyboard Shell a utlity UNIXu – p.4/66

Vzdálený pˇrístup pˇres X-Window ˇ aplikace s GUI ze vzdáleného poˇcítaˇce: ❖ Spuštení

• lokální systém: xhost + ... • vzdálený systém: export DISPLAY=... a spuštení ˇ aplikace • tunelování pˇres ssh: ssh -X ❖ Vnoˇrené GUI ze vzdáleného poˇcítaˇce: Xnest. ❖ Konkurence X-Window pro vzdálený pˇrístup – mj. VNC (Virtual Network Computing): ˇ vzdálený grafický pˇrístup, client-server systém, možnost odpojení a zpetného pˇripojení klienta k serveru, pˇrenos bitmap, nezávislé na OS, implementováno i pod X-Window.


Editory, vim

u - undo

ˇ ❖ Textové editory bežné v UNIXu:

• v terminálu: vi, vim, ema s, ... • grafické: gvim, xema s, nedit, ... ❖ Tˇri režimy vi, vim:

přechod na insert mode a - append (a - za aktuální znak, A - na konec řádku) i - insert (i - před aktuální znak, I - na začátek řádku) o - nový řádek (o - za aktuální řádek, O - před aktuální řádek) r - replace (r - nahraď aktuální znak, R - od následující pozice dál) přechod na režim příkazové řádky q - ukonči q! - ukonči i když proběhly změny wq - ulož a ukonči

p,P,yy,... Shift+ZZ Command mode a,i,o,r, A,I,O,R,...

: Esc

Esc, Enter q,q!,wq,...

Insert mode

Command line

editing


Užiteˇcné pˇríkazy ve vim ❖ Mazání – smaže a vloží do registru:

• • • • • •

znak: x/X ˇrádek: dd konec/zaˇcátek ˇrádku: dEnd / dHome konec/zaˇcátek slova: dw / db konec/zaˇcátek odstavce: d} / d{ do znaku: dt znak

ˇ ❖ Zmena: r, R a

, w, b, +End/Home, }, t+ukonˇcující znak, ... ❖ Vložení textu do registru: yy, yw, y}, yt+ukonˇcující znak, ... ❖ Vložení registru do textu: p/P ❖ Bloky: (Shift-V+šipky)/(Ctrl-V+šipky)+y /d, ...


❖ Vícenásobná aplikace: cˇ íslo+pˇríkaz (napˇr. 5dd) ❖ undo/redo: u /Ctrl-R ❖ Opakování posledního pˇríkazu: . (teˇcka) ❖ Vyhledání: / regulární výraz ❖ Aplikace akce po vzorek: d/ regulární výraz


Regulární výrazy ❖ Regulární výrazy jsou nástrojem pro koneˇcný popis pˇrípadneˇ nekoneˇcné množiny ˇretezc ˇ u. ˇ je velmi široké – nejde jen o vyhledávání ve vim! ˚ Jejich uplatnení ❖ Základní regulární výrazy (existují také rozšíˇrené RV – viz dále): znak

význam

obyˇcejný znak . * [množina] [^množina] \ ^ $ [[:k :]]

daný znak libovolný znak 0 − n výskytu˚ pˇredchozího znaku znak z množiny, napˇr: [0-9A-Fa-f] ˇ množiny znak z doplnku ruší ˇrídicí význam následujícího znaku zaˇcátek ˇrádku konec ˇrádku znak z dané kategorie k podle locale

:alpha:, :lower:, :digit: ...

❖ Pˇríklad: "^ *\* [0-9][0-9]* *$" hledej řádky, které libovolným počtem mezer, následuje hvězdička, právě jedna mezera, pak číslo tvořeno alespoň jednou číslicí, na závěr libovolný počet mezer Shell a utlity UNIXu – p.9/66

Pˇríkazová rˇádka ve vim ❖ Uložení do souboru: w, pˇrípadneˇ w! ˇ ˇrádky s/ regulární výraz / regulární výraz (/g) ❖ Vyhledání a zmena: ❖ Adresace ˇrádku: ˚ cˇ íslo ˇrádku, interval (x,y), aktuální ˇrádek (.), poslední ˇrádek ($), ˇ ˇ (/ˇretezec /), nejbližší pˇredchozí všechny ˇrádky (%), nejbližší další ˇrádek obsahující ˇretezec ˇrádek obsahující ˇretezec ˇ ˇ (?ˇretezec ?) ˇ ❖ Pˇríklad – vydelení cˇ ísel 10: :%s/$[0-9]*$$[0-9]$/\1.\2/ pro všechny řádky aplikuj: najdi libovolný počet číslic 0-9, po kterém následuje právě jedna číslice 0-9, nahraď tak, že za první číslici dáš tečku (desetinnou čárku), po které následuje desetinná část


Základní dokumentace v UNIXu ❖ man, info, /usr/share/do , /usr/lo al/share/do , HOWTO, FAQ, ..., README, INSTALL, ... ˇ ❖ man je rozdelen do sekcí (man n name): 1. Executable programs or shell commands 2. System calls (functions provided by the kernel) 3. Library calls (functions within program libraries) 4. Special files (usually found in /dev) 5. File formats and conventions, e.g., /et /passwd 6. Games 7. Miscellaneous (including macro packages and conventions) 8. System administration commands (usually only for root) 9. Kernel routines (Non standard) ❖ apropos name – kde všude se v man mluví o name. Shell a utlity UNIXu – p.11/66

Bourne shell 1. shell - interpretovaný programovací jazyk 2. shell - interpret jazyka shell


❖ Skriptování:

• • • •

Interpret: program, který provádí cˇ innost popsanou v souboru–programu. Skript: textový soubor s programem pro interpret. Nevýhody: pomalejší, je tˇreba interpret. Výhody: nemusí se pˇrekládat (okamžiteˇ spustitelné), cˇ itelný obsah programu.

interaktivní shell - vstup / výstup spojený s terminálem, načítá vstup z klávesnice, vypisuje výstup na displej neinteraktivní shell - načítá příkazy z programu, výstupy vypisuje do souboru

ˇ skriptu v UNIXu: ❖ Spuštení sh skript.sh

# explicitn´ ı vol´ an´ ı interpretu

sh může odkazovat na různý shell na různých systémech

chmod +x skript.sh ./skript.sh

# nastav´ ı pˇ rı ´znak spustitelnosti # spuˇ stˇ en´ ı shell spustí nový shell, po skončení programu jej zase ukončí,

. ./skript.sh

# spuˇ stˇ en´ ı v aktu´ aln´ ım shellu

nelze například nastavovat prostředí - zahodí se


❖ “Magic number” = cˇ íslo uvedené na zaˇcátku souboru a charakterizující jeho obsah:

• U spustitelných souboru˚ jádro zjistí na základeˇ magic number, jak soubor spustit: ˇ ˚ zevedení do pameti, tj. u binárních programu˚ jejich formát urˇcující zpusob u intepretovaných programu˚ pak, který interpret použít (první ˇrádek: #!/ esta/interpret).

• Výhoda: možnost psát programy v libovolném skriptovacím jazyku. ❖ Pˇríklady: #!/bin/sh

- skript pro Bourne shell

#!/bin/ksh #!/bin/csh

- skript pro Korn shell - skript pro C shell

#!/usr/bin/perl #!/usr/bin/python

- skript v Perlu - skript v Pythonu

\177ELF

- bin´ arn´ ı program - form´ at ELF


Speciální znaky (metaznaky) ˇ ❖ Jsou interpretovány shellem, znamenají provedení nejaké speciální operace. ˇ eˇ pˇred speciálním znakem. ❖ Jejich speciální význam lze zrušit napˇríklad znakem \ tesn

❖ Poznámky: znak

význam a pˇríklad použití

#

poznámka do konce ˇrádku echo "text" # pozn´ amka


ˇ ❖ Pˇresmerování vstupu a výstupu: znak >

význam a pˇríklad použití ˇ pˇresmerování výstupu, pˇrepíše soubor standardně propojeno s terminálem

echo "text" >soubor # pˇ resmˇ erov´ an´ ı stdout pˇ rı ´kaz 2>soubor # pˇ resmˇ erov´ an´ ı stderr pˇ rı ´kaz [n]>soubor

# n je ˇ cı ´slo, implicitnˇ e 1

ˇ Císla zde slouží jako popisovaˇce otevˇrených souboru˚ (file handle). Standardneˇ používané a otevírané popisovaˇce:

• stdin=0 • stdout=1 • stderr=2

standardní vstup (klávesnice) std. výstup (obrazovka) std. chybový výstup (obrazovka)


znak >&

>>

význam a pˇríklad použití duplikace popisovaˇce pro výstup echo "text" >&2 pˇ rı ´kaz >soubor 2>&1 pˇ rı ´kaz 2>&1 >soubor

# # # #

stdout pˇ resm. stdout stderr

do stderr stderr i stdout do souboru, nejprve přesměruje stderr na stdout, až pak na obrazovku stdout do souboru

m>&n

# m a n jsou ˇ cı ´sla

ˇ pˇresmerování výstupu, pˇridává do souboru echo "text" >> soubor pˇ rı ´kaz 2>>log-soubor


znak <

význam a pˇríklad použití ˇ pˇresmerování vstupu pˇ rı ´kaz < soubor

<
ˇ pˇresmerování vstupu, cˇ te ze skriptu až po token, který musí být samostatneˇ na ˇrádku – tzv. “here document” cat >soubor <<__END__ jak´ ykoli text, i $PROMENNA kromˇ e ukonˇ covac´ ıho ˇ ra ´dku __END__ musí být na začátku řádku

výstup přesměruje do souboru, vstup načítá ze sebe samého (následující část skriptu) až po značku __END__ dosazuje hodnoty proměnných, provádí zanořené příkazy

Varianty: <<\token

quoting jako ’, dále žádná expanze

<<-token

možno odsadit tabelátory


❖ Zástupné znaky ve jménech souboru: ˚ znak *

význam a pˇríklad použití zastupuje libovolnou sekvenci libovolných znaku, ˚ shell vyhledá všechna odpovídající jména souboru: ˚ ls *.c ls *archiv*gz ls .*/*.conf

# skryt´ e soubory .*

Poznámka: Není nutné v každém programu zpracovávat tyto expanzní znaky. Poznámka: Pozor na limit délky pˇríkazového ˇrádku! ?

zastupuje libovolný (jeden) znak jména souboru ls x???.txt ls soubor-?.txt

[mnoˇ zina]

zastupuje jeden znak ze zadané množiny ls [A-Z]* ls soubor-[1-9].txt


❖ Skládání pˇríkazu: ˚ znak ‘pˇ rı ´kaz‘

význam a pˇríklad použití

|

ˇ pˇresmerování stdout procesu na stdin dalšího procesu, slouží pro vytváˇrení kolon procesu-filtr ˚ u: ˚ paralelní provádění ls | more cat /etc/passwd | obsah /etc/passwd se rozdělí podle ":", pro každý řádek první část souboru, tedy přihlašovací jména, ty awk -F: ’{print $1}’ | sort vytiskne seřadí podle abecedy pˇ rı ´kaz | tee soubor | pˇ rı ´kaz

ˇ eno ˇ je zamen za standardní výstup pˇríkazu (command substitution) příkaz se provede, výstup se dosadí do '' -> sh vypíše cestu k sh, ls pak ls -l ‘which sh‘ zobrazí údaje např. o /bin/sj DATUM=‘date +%Y-%m-%d‘ # ISO form´ at zjistí aktuální datum a uloží do proměnné echo Pˇ rihl´ as ˇeno ‘who|wc -l‘ uˇ zivatel˚ u


znak ;

význam a pˇríklad použití sekvence pˇríkazu˚ na jednom ˇrádku ls ; echo ; ls /

||

ˇ provede následující pˇríkaz, pokud pˇredchozí neuspel (exitcode<>0) cc program.c || echo Chyba pˇ rekladu

&&

ˇ provede následující pˇríkaz, pokud pˇredchozí uspel (exitcode=0) cc program.c && ./a.out


ˇ pˇríkazu: ❖ Spouštení ˚ znak (pˇ rı ´kazy)

význam a pˇríklad použití spustí subshell, který provede pˇríkazy ( echo "Text: " cat soubor echo "konec" ) > soubor2

&

nelze načítat standardní vstup, není napojen na subshell

spustí pˇríkaz na pozadí (pozor na výstupy programu) program &

ˇ ❖ Práce s promennými: $

ˇ hodnoty promenné ˇ zpˇrístupnení echo $TERM


❖ Rušení významu speciálních znaku˚ (quoting):

• Znak \ ruší význam jednoho následujícího speciálního znaku (i znaku "nový ˇrádek"). echo \* text \* \\ echo "fhgksagdsahfgsjdagfjkdsaagjdsagjhfdsa\ jhdsajfhdsafljkshdafkjhadsk" echo 5 \> 2 text \$TERM

• Uvozovky "" ruší význam speciálních znaku˚ krome: ˇ $prom¥nná, `p°íkaz` a \. echo echo echo echo echo

3 * 4 = 12 # chyba, pokud # jsou v adres´ ar ˇi soubory "3 * 4 = 12" "Dneˇ sn´ ı datum: ‘date‘" "PATH=$PATH" "\ <\"test\"> *** ‘date‘ *** $PATH *** "

• Apostrofy ruší speciální význam všech znaku˚ v ˇretezci. ˇ echo ’$<>*‘ jak´ ykoli text kromˇ e apostrofu ’ echo ’toto ->’\’’<- je apostrof’ echo ’*\** \" $PATH ‘ls‘ <> \’ Shell a utlity UNIXu – p.23/66

Postup pˇri hledání pˇríkazu˚ ˇ ❖ Po zadání pˇríkazu postupuje shell následovne: 1. Test, zda se jedná o funkci nebo zabudovaný pˇríkaz shellu (napˇr. d), a pˇrípadné provedení této funkce/pˇríkazu. 2. Pokud se jedná o pˇríkaz zadaný i s cestou (napˇr. /bin/sh), pokus provést program s pˇríslušným jménem v pˇríslušném adresáˇri. 3. Postupné prohlížení adresáˇru˚ v PATH. 4. Pokud program nenalezne nebo není spustitelný, hlásí chybu.

❖ Poznámka: Vlastní pˇríkazy do $HOME/bin a pˇridat do PATH.


ˇ pˇríkazy Vestavené ˇ ❖ Které pˇríkazy jsou vestavené závisí na použitém interpretu. ❖ Pˇríklad: d, wait, ... ❖ Výhoda: rychlost provedení. ˇ ❖ Ostatní pˇríkazy jsou bežné spustitelné soubory.


Pˇríkaz eval ❖ eval p°íkaz:

• Jednotlivé argumenty jsou naˇcteny (a je proveden jejich rozvoj), výsledek je konkatenován, znovu naˇcten (a rozvinut) a proveden jako nový pˇríkaz.

• Možnost za behu ˇ sestavovat pˇríkazy (tj. program) na základeˇ aktuálneˇ cˇ teného obsahu souboru, vstupu od uživatele apod.

❖ Pˇríklady: echo "text > soubor" eval echo "text > soubor" eval ‘echo x=1‘ ; echo "x=$x" read X; eval echo "$"$X - vypíše obsah proměnné s názvem X


Ukonˇcení skriptu ❖ Ukonˇcení skriptu: exit [£íslo℄

• vrací exit-code £íslo nebo exit-code pˇredchozího pˇríkazu, • vrácenou hodnotu lze zpˇrístupnit pomocí $?, • možné hodnoty: – 0 – O.K. – <>0 – chyba

ˇ nového kódu: exe p°íkaz: ❖ Spuštení

• nahradí kód shellu provádejícího ˇ exe kódem daného pˇríkazu, • spuštení ˇ zadaného programu je rychlé – nevytváˇrí se nový proces, • bez parametru umožnuje ˇ ˇ pˇresmerování vstupu/výstupu uvnitˇr skriptu. např. během programu: exec < blabla - přesměruje vstup programu z souboru blabla


Správa procesu˚ ps nohup kill wait

výpis stavu procesu˚ proces nekonˇcí pˇri odhlášení posílání signálu˚ procesum ˚ cˇ eká na dokonˇcení potomka/potomku˚

❖ Pˇríklady: ps ax nohup program kill -9 1234

# vˇ sechny procesy # pozor na vstup/v´ ystup # nelze odm´ ıtnout


Subshell ❖ Subshell se spouští v pˇrípadeˇ použití: ./skript.sh (pˇ rı ´kazy)

ˇ skriptu (i na pozadí) spuštení skupina pˇríkazu˚

ˇ promenné ˇ ˇ lokální promenné ˇ ❖ Subshell dedí prostˇredí, nededí (tj. ty, u kterých nebyl proveden export). ˇ promenných ˇ ❖ Zmeny a dalších nastavení v subshellu se neprojeví v puvodním ˚ shellu! ❖ Provedení skriptu aktuálním interpretem:

• pˇríkaz . • napˇr. . skript ❖ Posloupnost pˇríkazu˚ { p°íkazy } – stejné jako ( ), ale nespouští nový subshell.


❖ Pˇríklad – možné použití { } (a souˇcasneˇ demonstrace jedné z programovacích technik používaných v shellu): # Changing to a log directory. cd $LOG_DIR if [ "‘pwd‘" != "$LOG_DIR" ]

# or if [ "$PWD" != "$LOG_DIR" ] # Not in /var/log?

then echo "Cannot change to $LOG_DIR." exit $ERROR_CD fi # Doublecheck if in right directory, before messing with log file. # However, a far more efficient solution is: cd /var/log || { echo "Cannot change to $LOG_DIR." >&2 exit $ERROR_CD; }

pokud příkaz cd neuspěje, vykonají se příkazy v { }


ˇ Promenné ˇ ❖ Rozlišujeme promenné:

• lokální (nededí ˇ se do subshellu) PROM=hodnota PROM2="hodnota s mezerami"

• promenné ˇ ˇ se do subshellu) prostˇredí (dedí PROM3=hodnota export PROM3

# mus´ ıme exportovat do prostˇ red´ ı

❖ Pˇríkaz export:

• export seznam_prom¥nný h • exportuje promenné ˇ ˇ subshell, do prostˇredí, které dedí • bez parametru vypisuje obsah prostˇredí.


ˇ ❖ Pˇrehled standardních promenných: $HOME

jméno domovského adresáˇre uživatele

$PATH

seznam adresáˇru˚ pro hledání pˇríkazu˚

$MAIL

úplné jméno poštovní schránky pro e-mail

$USER

login jméno uživatele

$SHELL

úplné jméno interpretu pˇríkazu˚

$TERM

typ terminálu (viz termcap/terminfo)

$IFS

ˇ obsahuje oddelovaˇ ce položek na pˇríkazové ˇrádce – implicitneˇ mezera, tabelátor a nový ˇrádek

$PS1

výzva interpretu na pˇríkazové ˇrádce – implicitneˇ znak $

$PS2

výzva na pokraˇcovacích ˇrádcích – implicitneˇ znak >


ˇ ❖ Další standardní promenné: $$

cˇ íslo = PID interpretu

$0

jméno skriptu (pokud lze zjistit)

$1..$9

argumenty pˇríkazového ˇrádku (dále pak ${n} pro n ≥ 10)

$*/$@

všechny argumenty pˇríkazového ˇrádku

"$*"

všechny argumenty pˇríkazového ˇrádku jako 1 argument v ""

"$@"

všechny argumenty pˇríkazového ˇrádku, individuálneˇ v ""

$#

poˇcet argumentu˚

$?

exit-code posledního pˇríkazu

$!

PID posledního pˇríkazu na pozadí

$-

aktuální nastavení shellu


❖ Pˇríklady: echo echo echo echo

"skript: $0" prvn´ ı argument: $1 vˇ sechny argumenty: $* PID=$$

ˇ ❖ Použití promenných: $PROM text ${PROM}text ${PROM-word} ${PROM+word} ${PROM=word} ${PROM?word}

ˇ mezi jménem a dalším textem musí být oddelovací znak ˇ není nutný další oddelovaˇ c word pokud nenastaveno pokud proměnná nemá hodnotu, použije se word word pokud nastaveno, jinak nic pokud má proměnná hodnotu, použije se word pokud nenastaveno, pˇriˇradí a použije word pokud nenastaveno, tisk chybového hlášení word a konec (exit)


❖ Pˇríkaz env:

• env nastavení_prom¥nný h program [argumenty℄ • spustí program s nastaveným prostˇredím, • bez parametru˚ vypíše prostˇredí.

ˇ ❖ Promenné pouze pro cˇ tení:

• readonly seznam_prom¥nný h • oznaˇcí promenné ˇ pouze pro cˇ tení, • subshell toto nastavení nededí. ˇ

❖ Posun argumentu˚ skriptu:

• pˇríkaz shift, • posune $1 <- $2 <- $3 ...


ˇ Ctení ze standardního vstupu ˇ ❖ Pˇríkaz read seznam_prom¥nný h cˇ te ˇrádek ze stdin a pˇriˇrazuje slova do promenných, do poslední dá celý zbytek vstupního ˇrádku. ❖ Pˇríklady: echo "x y z" | (read A B; echo "A=’$A’

B=’$B’")

IFS=","; echo "x,y z" | (read A B; echo "A=’$A’

A=x B=yz

B=’$B’") změní oddělovač slov, A = x

IFS=":"; head -1 /etc/passwd | (read A B; echo "$A")

B=yz

A = login prvního uživatele = root


ˇ Pˇríkazy vetvení ❖ Pˇríkaz if:

vyhodnocuje se podle návratového kódu posledního příkazu

if seznam pˇ rı ´kaz˚ u then seznam pˇ rı ´kaz˚ u elif seznam pˇ rı ´kaz˚ u then seznam pˇ rı ´kaz˚ u else seznam pˇ rı ´kaz˚ u fi

Pˇríklad použití: if [ -r soubor ]; then cat soubor else echo soubor nelze ˇ cı ´st fi


Testování podmínek ❖ Testování podmínek:

• konstrukce test výraz nebo [ výraz ℄, • výsledek je v $?. výraz -d file -f file -l string -n string string -z string -r file -w file -x file -t fd např. stdin, stdout..

0 = true <> 0 = false

význam je adresáˇr není adresáˇr ˇ délka ˇretezce ˇ neprázdný ˇretezec ˇ neprázdný ˇretezec ˇ prázdný ˇretezec je cˇ itelný soubor je zapisovatelný soubor je proveditelný soubor deskriptor fd je spojen s terminálem

výraz str1 = str2 str1 != str2 int1 -eq int2 int1 -ne int2 int1 -gt int2 int1 -ge int2 int1 -lt int2 int1 -le int2 ! expr expr1 -a expr2 expr1 -o expr2 

význam ˇ u˚ rovnost ˇretezc ˇ u˚ nerovnost ˇretezc rovnost cˇ ísel nerovnost cˇ ísel > >= < <= negace výrazu and or závorky


❖ Pˇríkaz ase: case v´ yraz in vzor { | vzor }* ) seznam pˇ rı ´kaz˚ u ;; esac

Pˇríklad použití: echo -n "zadejte ˇ cı ´slo: " read reply case $reply in "1") echo "1" ;; "2"|"4") echo "2 nebo 4" ;; *) echo "nˇ eco jin´ eho" ;; esac * je expanze, ne regulární výraz


Cykly ❖ Cyklus for: for identifik´ ator [ in seznam slov ] do seznam pˇ rı ´kaz˚ u done

Pˇríklad použití: for i in *.txt ; do echo Soubor: $i done

# bez []: $1 ...

*.txt - všechny .txt soubory v adresáři, postupně prochází všechna jména


❖ Cyklus while: while seznam pˇ rı ´kaz˚ u # posledn´ ı exit-code se pouˇ zije do seznam pˇ rı ´kaz˚ u done

rozhoduje se podle posledního návratového kódu

Pˇríklad použití: while true ; do date; sleep 1 done

❖ Cyklus until: until seznam pˇ rı ´kaz˚ u # posledn´ ı exit-code se pouˇ zije do seznam pˇ rı ´kaz˚ u done


❖ Ukonˇcení/pokraˇcování cyklu: break, continue

break - ukončí provádění cyklu continue - přejde na další iteraci cyklu

❖ Pˇríklady: stop=-1 while [ $stop -ne 0 ]; do echo -n "zadejte ˇ cı ´slo: " read stop echo $stop if [ $stop -ge 10 ] ; then echo "pˇ rı ´liˇ s velk´ e" break fi done


Zpracování signálu˚ ❖ Pˇríkaz trap:

• trap [p°íkaz℄ {signál}+ man 7 signal - seznam signálů • pˇri výskytu signálu provede pˇríkaz, • pro ladení ˇ lze užít trap p°íkaz DEBUG. DEBUG - vyvolá se po každém příkazu

❖ Pˇríklad zpracování signálu: #!/bin/sh trap ’echo Ctrl-C; exit 1’ 2

# ctrl-C = sign´ al ˇ c.2

while true; do echo "cykl´ ıme..." sleep 1 done


Vyhodnocování výrazu˚ true = 1

❖ Pˇríkaz expr výraz: false = 0

• Vyhodnotí výraz, komponenty musí být oddeleny ˇ mezerami (pozor na quoting!). • Operace podle priority: \* + = \& \|

/ \>

% \>=

\<

\<=

!=

• Lze použít závorky:  ❖ Pˇríklady: V=‘expr 2 + expr 1 = 1

3 \&

\* 4‘ ; echo $V 0 != 1 ; echo $?

V = 14, vypíše 14 expr vypíše 1, protože hodnota expr je true, nastavuje návratový kód na true, což už je pro shell zase 0, $? tedy vypíše 0 (návratová hodnota posledního příkazu)

expr "$P1" = "$P2" # test obsahu promˇ enn´ ych V=‘expr $V + 1‘

je vhodné uzavírat do " "

# V++ Shell a utlity UNIXu – p.44/66

ˇ ezcové ˇ ❖ Ret operace v expr: String : Regexp match String Regexp ˇ který vyhovuje Regexp, nebo 0 – vrací délku podˇretezce, substr String Start Length ˇ od zadané pozice – získá podˇretezec index String Charlist – vrací pozici prvního znaku ze seznamu, který se najde length String ˇ – vrací délku ˇretezce


Korn shell – ksh ❖ Rozšíˇrení Bourne shellu, POSIX shell (starší verze ksh88 základem pro definici ˇ v bash-i. POSIX), jeho duležité ˚ vlastnosti jsou zabudovány rovnež ❖ Pˇríkaz alias: alias rm=’rm -i’ ❖ Historie pˇríkazu: ˚

• možnost vracet se k již napsaným pˇríkazum ˚ a editovat je (bash: viz šipka nahoru a dolu˚ a R.) ctrl + r = "vyhledávání" napsaných příkazů ❖ Vylepšená aritmetika:

• pˇríkaz let, napˇr. let "x=2*2", • operace: + - * / % ! < > <= >= == != = ++ • zkrácený zápis a vyhodnocení bez spouštení ˇ dalšího procesu: (( x=2 )) (( x=2*x )) (( x++ )) echo $x vytiskne 5 Shell a utlity UNIXu – p.46/66

❖ Speciální znak “vlnovka”: ~ ~user ~+ ~-

$HOME $PWD $OLDPWD

domovský adresáˇr domovský adresáˇr daného uživatele pracovní adresáˇr pˇredchozí prac. adresáˇr

❖ Primitivní menu: select identifik´ ator [in seznam slov] do select x in "prvni moznost " "druha moznost" "treti moznost (konec)" do seznam pˇ rı ´kaz˚ u echo $x done if [ "$x" = "treti moznost (konec)" ] ; then break; fi done

– funguje jako cyklus; nutno ukonˇcit!


❖ Vylepšené testování: [[ ]] (v´ yraz) v´ yraz && v´ yraz v´ yraz || v´ yraz

nemusíme používat \ uvnitř [[ ]]

Zbytek stejneˇ jako test. ❖ Substituce pˇríkazu: ˚ ‘command‘

$(command)

❖ Pole: declare -a p p[1]=a echo ${p[1]}

# pole (deklarace je nepovinn´ a) declare -A = asociativní pole


❖ Pˇríkaz printf: formátovaný výpis na standardní výstup.

❖ Zásobník pro práci s adresáˇri:

• pushd – uložení adresáˇre do zásobníku, • popd – pˇrechod do adresáˇre z vrcholu zásobníku, • dirs – výpis obsahu zásobníku.


❖ Pˇríkaz set

• bez parametru˚ vypíše promenné, ˇ • jinak nastavuje vlastnosti shellu: parametr

-n -u -v -x --

akce neprovádí pˇríkazy ˇ chyba pokud promenná není definována opisuje cˇ tené pˇríkazy ˇ opisuje provádené pˇríkazy další znaky jsou argumenty skriptu

• vhodné pro ladení ˇ skriptu. ˚ ❖ Pˇríklady: set -x -- a b c * for i ; do echo $i; done

za * nahradí všechny soubory v adresáři


Omezení zdroju˚ ˇ shellu (a jeho uživateli) provádet ˇ jisté pˇríkazy (použití d, ❖ Restricted shell: zabránení ˇ programu˚ zadaných s cestou, použití exe ...). ˇ ˇ pˇresmerování, PATH, spouštení zmena např. omezení přístupu pouze na domovský adresář

ˇ ˇ ❖ ulimit: omezení prostˇredku˚ dostupných shellu a procesum ˚ z neho spušteným (poˇcet ˇ procesu, poˇcet otevˇrených souboru, ˚ ...). procesu, ˚ pamet’ ❖ quota: omezení diskového prostoru pro uživatele.


Funkce ❖ Definice funkce: function ident () { seznam pˇ rı ´kaz˚ u } ❖ Parametry jako u skriptu: $1 ... ❖ Ukonˇcení funkce s exit- ode: return [exit- ode℄. ˇ ❖ Definice lokální promenné: typeset prom. ❖ Možnost rekurze.


Správa prací – job control ˇ ❖ Job (úloha) v shellu odpovídá provádené koloneˇ procesu˚ (pipeline). ˇ kolony se vypíše [jid℄ pid, kde jid je identifikace úlohy a pid ❖ Pˇri spuštení ˇ identifikace posledního procesu v kolone. ˇ ❖ Pˇríkaz jobs vypíše aktuálneˇ provádené úlohy. ˇ ❖ Úloha muže ˚ být spuštena na popˇredí, nebo pomocí & na pozadí. ˇ ❖ Úloha bežící na popˇredí muže ˚ být pozastavena pomocí Z a pˇresunuta na pozadí ˇ pomocí fg). pomocí bg (a zpet ❖ Explicitní identifikace úlohy v rámci fg, bg, kill,...: %jid


Interaktivní a log-in shell ˇ v ruzných ❖ Shell muže ˚ být spušten ˚ režimech – pro bash máme dva významné módy, které se mohou kombinovat:

• interaktivní bash (vstup/výstup z terminálu) a • log-in shell (parametr login). ˇ a ukonˇcení interpretu pˇríkazu˚ závisí na režimu v nemž ˇ ˇ Napˇr. pro ❖ Start, beh shell beží. interaktivní log-in bash platí: 1. úvodní sekvence: /etc/profile (existuje-li) a dále ~/.bash_profile, ~/.bash_login, nebo ~/.profile ~/ = domovský adresář 2. tisk $PROMPT, zadávání pˇríkazu˚ 3. exit,^D,logout – ukonˇcení interpretu s provedením ~/.bash_logout. ˇ implicitního interpretu pˇríkazu: ❖ Výber ˚

• /et /passwd • hsh – change shell


Utility UNIXu


❖ Utiliy UNIXu:

• užiteˇcné programy (asi 150), • souˇcást normy SUSv3, • ruzné ˚ nástroje na zpracování textu atd.

❖ Pˇrehled základních programu: ˚ awk cmp cut dd bc

jazyk pro zpracování textu, výpoˇcty atd. porovnání obsahu souboru˚ po bajtech ˇ sloupcu˚ textu výber kopie (a konverze) cˇ ásti souboru kalkulátor s neomezenou pˇresností Pokraˇcování na dalším slajdu...


❖ Pˇrehled základních programu˚ – pokraˇcování... df diff du file find getopt(s) grep iconv nl od patch sed sort split tr uniq xargs

volné místo na disku rozdíl textových souboru˚ (viz i tkdiff) zabrané místo na disku informace o typu souboru hledání souboru˚ pˇredzpracování argumentu˚ skriptu˚ ˇ ˇrádku˚ textového souboru výber pˇrekódování znakových sad oˇcíslování ˇrádku˚ výpis obsahu binárního souboru oprava textu podle výstupu diff neinteraktivní editor textu ˇrazení ˇrádku˚ ˇ rozdelení souboru na menší ˇ zámena znaku˚ v souboru vynechání opakujících se ˇrádku˚ zpracování argumentu˚ (napˇr. po find) Shell a utlity UNIXu – p.57/66

Program grep ˇ ˇ ˇrádku˚ podle regulárního výrazu. ❖ Umožnuje výber ❖ Existují tˇri varianty:

• fgrep – rychlejší, ale neumí regulární výrazy

• grep – základní regulární výrazy • egrep – rozšíˇrené regulární výrazy

❖ Pˇríklady použití: fgrep -f seznam soubor grep ’^ *[A-Z]’ soubor egrep ’(Jan|Honza) +Nov´ ak’

soubor

❖ Rozšíˇrené (extended) regulární výrazy: znak

význam

+ ? {m} {m,n} (r ) |

1 − n výskytu˚ pˇredchozího podvýrazu 0 − 1 výskyt pˇredchozího podvýrazu m výskytu˚ pˇredchozího podvýrazu m − n výskytu˚ pˇredchozího podvýrazu specifikuje podvýraz, napˇr: (ab*c)* ˇ oddeluje dveˇ varianty, napˇr: (ano|ne)? Shell a utlity UNIXu – p.58/66

Manipulace textu ˇ ˇ sloupcu˚ textu. ❖ Program ut – umožnuje výber cut -d: -f1,5 /etc/passwd rozdělí podle : a vybere sloupce 1 a 5 cut -c1,5-10 soubor # znaky na pozici 1 a 5-10 ❖ Program sed:

• Neinteraktivní editor textu (streaming editor). • Kromeˇ základních editaˇcních operací umožnuje ˇ ˇ ˇ i podmínené a nepodmínené skoky (a tedy i cykly). sed ’s/nov´ ak/Nov´ ak/g’ soubor nahradí novák za Novák (/g - všechny výskyty) sed ’s/^[^:]*/-/’ /etc/passwd nahradí všechny loginy pomlčkou = tisk (tiskne řádky, na kterých najde obsah proměnné sed -e "/$xname/p" -e "/|/d" soubor_seznam -p xname ... -d = delete (smaže řádkek, pokud na něm je |) sed ’/tel:/y/0123456789/xxxxxxxxxx/’ soubor y = nahrazení znaků... nahradí všechna telefonní čísla sed -n ’3,7p’ soubor -n = netiskne implicitně řádky, tiskne pouze řádky 3 až 7 sed ’1a\ a = append tento text bude pˇ rid´ an na 2. ˇ ra ´dek’ soubor sed -n ’/start/,/stop/p’ soubor vytiskne řádky od řádku, na kterém se vyskytuje start až po řádek, na kterém je stop


❖ Program awk:

• AWK je programovací jazyk vhodný pro zpracování textu, výpoˇcty atd. záznamy = řádky sloupce = sloupce :))

awk ’{s+=$1}END{print s}’ soubor_cisel pro každý řádek s+=$1, po posledním řádku vytiskne součet awk ’{if(NF>0){s+=$1;n++}} pokud je počet sloupců > 0, přičte $1, navýší počet sečtených řádků END{print n " " s/n}’ soubor_cisel vytiskne počet zpracovaných řádků a průměrnou hodnotu s awk -f awk-program soubor

❖ Program paste:

• Spojení odpovídajících ˇrádku˚ vstupních souboru. ˚ paste -d\| sloupec1.txt sloupec2.txt

vypíše se první řádek 1. souboru | první řádek 2. souboru


Porovnání souboru˚ a patchování ❖ Program mp:

• Porovná dva soubory nebo jejich cˇ ásti byte po bytu. cmp soubor1 soubor2

❖ Program diff:

• Výpis rozdílu˚ textových souboru˚ (porovnává ˇrádek po ˇrádku). diff old.txt new.txt diff -C 2 old.c new.c diff -urN dir1 dir2

-C počet vypsaných předchozích řádků -r rekurzivní prohledávání -N chybějící soubory bere jako prázdné -u unifikovaný formát výstupu

❖ Program pat h:

• Zmena ˇ textu na základeˇ výstupu z programu diff. • Používá se pro správu verzí programu˚ (cvs, svn, ...). Shell a utlity UNIXu – p.61/66

Hledání soboru ❖ Program find:

• Vyhledání souboru podle zadané podmínky. find find find find find find find find

. / / / / / . .

-name ’*.c’ -type d -size +1000000c -exec ls -l {} \; -size +1000000c -execdir command {} \; -type f -size -2 -print0 | xargs -0 ls -l -type f -size -2 -exec ls -l {} + -mtime -1 -mtime +365 -exec ls -l {} \;

- hledá všechny *.c soubory - hledá všechny adresáře (zanořeně z /) - hledá všechny soubory větší než 1MB, pro každý soubor udělá ls -l {} znamená dosazení jména nalezeného adresáře \; - tady končí exec - execdir se volá tam, kde byl nalezen soubor (adresář) || - exec volá z místa spuštění find - hledá všechny soubory menší než 2, print0 odděluje slova 0(ascii), xargs zpracovává vstup a předává ho do ls -l (nespustí se 1000krát, ale 1krát s tisícem souborů), xargs rozděluje vstup do bezpečně spustitelných částí - hledá podle času modifikace (formát ve dnech) Shell a utlity UNIXu – p.62/66

ˇ Razení ❖ Program sort:

• seˇrazení ˇrádku. ˚ sort sort sort

soubor -u -n soubor_ˇ cı ´sel -t: -k3,3n /etc/passwd

-n porovnání číselně -u vyhodí duplicity -t oddělovač -k od kterého záznamu kam hledat

❖ Program uniq:

• odstranení ˇ duplicitních ˇrádku ze seˇrazeného souboru. ❖ Program omm:

• výpis unikátních/duplicitních ˇrádku˚ seˇrazených souboru. ˚ comm soubor1 soubor2 # 3 sloupce comm -1 -2 s1 s2 # jen duplicity comm -2 -3 s1 s2 # pouze v s1

předpokládá seřazené soubory

-x vyhodí sloupec


Další nástroje programátora • skriptovací jazyky a interprety (perl, python, tcl, ...) • pˇrekladaˇce (cc/gcc, c++/g++, ...) • assemblery (nasm, ...) • linker ld (statické knihovny .a, dynamické knihovny .so) – dynamické knihovny používané programem: ldd, – knihovny standardneˇ v /lib a /usr/lib, – cesta k pˇrípadným dalším knihovnám: LD_LIBRARY_PATH, – run-time sledování funkcí volaných z dynamických knihoven: ltrace.


• Program make: – automatizace (nejen) pˇrekladu a linkování, – pˇríklad souboru makefile (pozor na odsazení tabelátory): test: test.o tisk.o gcc $(CFLAGS) -o test test.o tisk.o test.o: test.c gcc $(CFLAGS) -c test.c tisk.o: tisk.c gcc $(CFLAGS) -c tisk.c clean: rm -f *.o test

– použití: make, make CFLAGS=-g, make lean.


• automatizovaná konfigurace – GNU auto onf: – Generuje na základeˇ šablony založené na volání pˇredpripravených maker ˇ rení dostupnosti skripty pro konfiguraci pˇrekladu (urˇcení platformy, oveˇ knihoven a nástroju, ˚ nastavení cest, ...), pˇreklad a instalaci programu˚ šíˇrených ˇ ve zdrojové podobe.

– Používá se mj. spolu s automake (usnadnení ˇ tvorby makefile) a autos an ˇ tvorby šablon pro auto onf). (usnadnení – Použití vygenerovaných skriptu: ˚ ./ onfigure, make, make install • ladení: ˇ debugger napˇr. ddd postavený na gdb (pˇreklad s ladícími informacemi gcc -g ...)

• sledování volání jádra: strace • profiling: profiler napˇr. gprof (pˇreklad pomocí gcc -pg ...)





Správa souboru˚ – p.1/76

Správa souboru˚


Pevný disk

vnější paměťové médium, obsahuje kruhové plotny, na kterých jsou uloženy data do jenotlivých kruhových stop. nad těmito stopami obíhá sada čtecích hlav (jsou na jednom rameni). data jsou na disku dělena do sektorů, typicky o velikost 512b. cylindr = stopa, která se nachází v jednom sloupci ("nad sebou")

Head Sector

Platter Track

Cylinder

❖ Adresace sektoru: ˚

• CHS = Cylinder, Head (typicky 1-6 hlav), Sector (typicky 512B) • LBA = Linear Block Address (ˇcíslo 0..N) číslo sektoru


❖ Rozložení sektoru˚ na pevném disku:

❖ Zejména dˇríve se používalo tzv. prokládání (interleaving) sektoru˚ – z hlediska cˇ ísla za sebou následující sektory nebyly fyzicky uloženy za sebou. To proto, aby pˇres pomalý ˇradiˇc disku a pomalou komunikaci se systémem nehrozilo, že se za sebou následující sektory nestaˇcí naˇcíst v rámci jedné otáˇcky disku a bude se muset cˇ ekat na další otoˇcku ˇ zpet. ˇ záležitost starších disků disku, kdy se pˇríslušný sektor vrátí opet


❖ Pro pˇripojení disku˚ se používá ˇrada ruzných ˇ periferních) rozhraní: ˚ diskových (ˇci obecneji primárneˇ ATA (IDE)/SATA cˇ i SCSI/SAS, ale také USB, FireWire, FibreChannel, aj. ˇ ˇ ❖ Diskové sbernice se liší mj. rychlostí (napˇr. do 6 Gbit/s u nejnovejších SATA cˇ i SAS), poˇctem pˇripojitelných zaˇrízení (desítky SATA/65535 SAS), max. délkou kabelu˚ (1-2m SATA, 10m SAS), architekturou pˇripojení (napˇr. více cest k zaˇrízení u SAS), podporovanými pˇríkazy (flexibilita pˇri chybách). ˇ i jiné typy pametí: ˇ flash disky, ❖ Stejným zpusobem ˚ jako disky mohou být zpˇrístupneny SSD, pásky, CD/DVD, ... ˇ ve které stoupá kapacita a klesá rychlost a cena/B: ❖ Vzniká hierarchie pametí,

• primární pamet’: ˇ RAM (nad ní ješteˇ registry, cache L1-L3) nejrychlejší • sekundární pamet’: ˇ pevné disky, SSD (mají také své cache) • terciární pamet’: ˇ pásky, CD, DVD, ...


Parametry pevných disku˚ ˇ ❖ Pˇrístupová doba = doba vystavení hlav + rotaˇcní zpoždení. ˇ ❖ Typické parametry souˇcasných disku˚ (orientaˇcneˇ – neustále se mení): kapacita ˇ prum ˚ erná doba pˇrístupu otáˇcky pˇrenosová rychlost

do nízkých jednotek TB od nízkých jednotek ms 4200-15000/min desítky až nízké stovky MB/s

❖ U kapacity disku udávané výrobcem/prodejcem je tˇreba dávat pozor, jakým zpusobem ˚ ˇ GiB = 10243 = 230 B. ji poˇcítá: GB = 109 B nebo 1000 ∗ 220 B nebo ... Správne: ❖ U pˇrenosových rychlostí pozor na sustained transfer rate (opravdové cˇ tení z ploten) a maximum transfer rate (z bufferu disku). ˇ rení pˇrenosových rychlostí: hdparm -t. ❖ Možnost meˇ

• hdparm umožnuje ˇ ˇ celou ˇradu dalších parametru˚ disku. cˇ íst/menit ˚ • Pozor! hdparm -T meˇ ˇ rí rychlost pˇrenosu z vyrovnávací pameti ˇ OS (tedy z RAM). Správa souboru˚ – p.6/76

Solid State Disks – SSD ˇ založeno na nevolatilních pametech ˇ ❖ SSD je nejˇcasteji NAND flash, ale vyskytují se i ˇrešení založená na DRAM (se zálohovaným napájením) cˇ i na kombinacích. rychlejší

❖ Výhody SSD:

• rychlý (v zásadeˇ okamžitý) nábeh, ˇ • náhodný pˇrístup – pˇrístupová doba od jednotek µs (DRAM) do desítek cˇ i nízkých stovek µs,

• vetší ˇ pˇrenosové rychlosti – stovky MB/s (500 MB/s), zápis bývá mírneˇ pomalejší (viz dále).

• tichý provoz, mechanická a magnetická odolnost, ..., • obvykle nižší spotˇreba (neplatí pro DRAM). ❖ Nevýhody SSD:

• vyšší cena za jednotku prostoru (dˇríve i nižší kapacita, dnes již až do nízkých jednotek TB),

• omezený poˇcet pˇrepisu, ˚ • možné komplikace se zabezpeˇcením (napˇr. bezpeˇcné mazání/šifrování pˇrepisem dat vyžaduje speciální podporu – data mohla být diskem pˇri pˇrepisech zapsána na ˇ nekolik míst). zápis se rozkládá rovnoměrně po disku Správa souboru˚ – p.7/76

Problematika zápisu u SSD ❖ NAND flash SSD jsou organizovány do stránek (typicky 4KiB) a ty do bloku˚ (typicky 128 stránek, tj. 512KiB). ˇ Pro pˇrepis nutno naˇcíst celý blok do ❖ Prázdné stránky lze zapisovat jednotlive. ˇ v ní zmenit, ˇ ˇ eˇ zapsat. vyrovnávací pameti, na disku vymazat a pak zpetn

• Problém je menší pˇri sekvenˇcním než pˇri náhodném zápisu do souboru. ˇ problému˚ s pˇrepisem v SSD: ❖ Rešení

• Aby se problém minimalizoval, SSD muže ˚ mít více stránek, než je oficiální kapacita. • Pˇríkaz TRIM umožnuje ˇ ˇ SSD, které bloky nejsou souborovému systému sdelit ˇ považovat za prázdné. používány a lze je opet

nelze použít např. při virtualizaci

• Novejší ˇ ˇradiˇce SSD provádí samy uvolnování ˇ stránek na základeˇ dostupných dat (napˇr. na základeˇ informací o pˇresunutých stránkách).

• Pˇresto jistý rozdíl v rychlosti cˇ tení/zápisu zustává. ˚ • TRIM navíc nelze užít vždy (souborové systémy uložené jako obrazy, kde nelze ˇ uvolnovat bloky, které nejsou na samém konci obrazu; podobneˇ u RAID cˇ i databází ukládajících si data do velkého pˇredalokovaného souboru). ❖ Aby ˇradiˇc SSD minimalizoval poˇcet pˇrepisu˚ stránek, muže ˚ pˇrepisovanou stránku zapsat ˇ ené ˇ na jinou pozici; pˇrípadneˇ i pˇresouvá dlouho nemen stránky. Správa souboru˚ – p.8/76

Zabezpeˇcení disku˚ ❖ Disková elektronika používá ECC = Error Correction Code: k užiteˇcným datum ˚ sektoru ˇ opravu (a z hlediska OS transparentní si ukládá redundantní data, která umožnují realokaci), nebo alesponˇ detekci chyb. ❖ S.M.A.R.T. – Self Monitoring Analysis and Reporting Technology: moderní disky si automaticky shromažd’ují ˇradu statistik, které lze použít k pˇredpovídání/diagnostice chyb. Viz smart tl, smartd, ... teplota, počty roztočení disku, záznam chyb... ❖ Rozpoznávání a oznaˇcování vadných bloku˚ (bad blocks) muže ˚ probíhat také na úrovni OS (napˇr. e2fs k a badblo ks), pokud si již s chybami disk sám neporadí (což je ale ˇ vymenit). ˇ možná také vhodná doba disk radeji


Disková pole ❖ RAID (Redundant Array of Inexpensive Disks):

použití více levných disků pro dosažení vlastností drahého disku

• RAID 0 – disk stripping, následné bloky dat rozmísteny ˇ na ruzných ˚ discích, vyšší výkonnost, žádná redundance.

• RAID 1 – disk mirroring, všechna data ukládána na dva disky, velká redundance (existuje také RAID 0+1 a RAID 1+0/10). to co se uloží na jeden disk se uloží i na druhý disk, rychlejší čtení

• RAID 2 – data rozdelena ˇ mezi disky po bitech, použito zabezpeˇcení Hammingovým kódem uloženým na zvláštních discích (napˇr. 3 bity zabezpeˇcení pro 4 datové: chybu na 1 disku lze automaticky opravit, na 2 discích detekovat).

• RAID 3 – sekvence bajtu˚ dat jsou rozdeleny ˇ na cˇ ásti uložené na ruzných ˚ discích, navíc je užit disk s paritami.

jeden paritní disk - po selhání jednoho disku lze chybějící data dopočítat podle parity

stejné jako RAID 3, zápis • RAID 4 – bloky dat na ruzných ˚ discích a paritní bloky na zvláštním disku.probihá po blocích

• RAID 5 – jako RAID 4, ale paritní a datové bloky jsou rozloženy na všech discích, odpadá pˇretížení paritního disku.

• RAID 6 – jako RAID 5, ale parita uložena 2x, vyrovná se i se ztrátou 2 disku. ˚ Správa souboru˚ – p.10/76

Uložení souboru na disku ❖ Alokaˇcní blok (2n sektoru) ˚ – nejmenší jednotka diskového prostoru, se kterou OS ˇ umožnuje pracovat uživatelum. ˚ external fragmentation

Logical file

8 16

4KB

1 9

4096 4KB

4KB

7 15

10 2

6 14

11

8192 9000

internal fragmentation externí fragmentace = související sektory nenásledují za sebou, mohou být promíchány s "cizími" či prázdnými sektory interní fragmentace = OS alokuje místo na disku, které zůstává nevyužité (je zaplněno pouze z části)

13 5

3

12 4

ˇ ❖ Poznámka: Nekdy se též užívá oznaˇcení cluster. Správa souboru˚ – p.11/76

Fragmentace ˇ ˇ ❖ Pˇri pˇridelování a uvolnování prostoru pro soubory dochází k tzv. externí fragmentaci – na disku vzniká posloupnost volných a (ruznými ˚ soubory) využitých oblastí, což má dva možné dusledky: ˚

• Vzniknou nekteré ˇ nevyužité oblasti pˇríliš malé na to, aby se ješteˇ daly využít (napˇr. ˇ prostoru souborum, ˚ které je aktuálneˇ zapotˇrebí uložit). pro spojité pˇridelování

• Pˇri nespojitém pˇridelování ˇ prostoru po alokaˇcních blocích (nebo pˇri nespojitém ˇ pˇridelování bez dolního omezení využitelného prostoru) výše uvedený problém ˇ a pomalejší nevzniká, ale data souboru jsou na disku uložena nespojiteˇ – složitejší pˇrístup (neprojevuje se tolik u SSD).

• Moderní souborové systémy užívají ruzné ˚ techniky k minimalizaci externí fragmentace: rozložení souboru˚ po disku, pˇredalokace (alokuje se více místa, než je momentálneˇ zapotˇrebí), odložená alokace (odkládá zápis, než se nasbírá více ˇ požadavku˚ a je lepší povedomí, kolik je tˇreba alokovat).

• Pˇresto bývají k dispozici nástroje pro defragmentaci. ˇ ❖ Interní fragmentace – nevyužité místo v posledním pˇrideleném alokaˇcním bloku – plýtvání místem.

• Nekteré ˇ ˇ sdílení posledních alokaˇcních bloku˚ více souborové systémy umožnují soubory. Správa souboru˚ – p.12/76

Pˇrístup na disk ˇ ❖ Prostˇrednictvím I/O portu˚ a/nebo pamet’ov eˇ mapovaných I/O operací (HW zajišt’uje, že ˇ ˇ I/O zaˇrízení) se ˇradiˇci nekteré adresy RAM ve skuteˇcnosti odkazují do interní pameti disku pˇredávají pˇríkazy definované diskovým rozhraním (ATA, SCSI, ...). ❖ Pˇrenos z/na disk je typicky ˇrízen ˇradiˇcem disku s využitím technologie pˇrímého ˇ (DMA). O ukonˇcení operací cˇ i chybách informuje ˇradiˇc procesor (a na pˇrístupu do pameti ˇ bežící ˇ nem jádro OS) pomocí pˇrerušení. DMA - přístup do paměti bez využití procesoru Process

read(fd, buf, 9000)

Kernel

4KB

4KB

4KB read 9000B

jádro načítá data z disku po blocích, tyto bloky ukladá do své dočasné paměti. uživatel žádal 9KB, celkově je načteno 12KB, protože jeden blok má 4KB

Device driver i/o

řadič disku je HW ovladač zařízení je SW

Interrupts

Disk controller

Disk Správa souboru˚ – p.13/76

Plánování pˇrístupu na disk ˇ ❖ Poˇradí bloku˚ cˇ tených/zapisovaných na disk ovlinuje plánovaˇc diskových operací.

• Pˇricházející požadavky na cˇ tení/zápis jsou ukládány do vyrovnávací pameti ˇ a jejich ˇ eno ˇ poˇradí je pˇrípadneˇ men tak, aby se minimalizovala režie diskových operací.

• Napˇr. tzv. výtahový algoritmus (elevator algorithm, SCAN algorithm) pohybuje ˇ a vyˇrizuje požadavky v poˇradí hlaviˇckami od stˇredu k okraji ploten a zpet ˇ pohybu hlaviˇcek. odpovídajících pozici a smeru směrem • Další plánovací algoritmy: Circular SCAN (vyˇrizuje požadavky vždy pˇri pohybu např. ke středu

ˇ ˇ ejší ˇ doba obsluhy), LOOK (pohybuje se jen v mezích jedním smerem – rovnomern ˇ daných aktuálními požadavky – nižší prum ˚ erná doba pˇrístupu), C-LOOK, ...

• Plánovaˇc muže ˚ sdružovat operace, vyvažovat požadavky ruzných ˚ uživatelu, ˚ ˇ že je bude možno implementovat priority operací, odkládat operace v nadeji, ˇ propojit, implementovat cˇ asová omezení možného cˇ ekání operací na pozdeji provedení apod. ˇ nastavení prostˇrednictvím ❖ V Linuxu možno zjistit/zmenit /sys/blo k/<devicename>/queue/s heduler.


Logický disk

MBR - záznam umístěný v prvním sektoru disku, obsahuje kromě tabulky diskových oblastí také zavaděč operačního systému (předá řízení aktivní diskové oblasti)

ˇ ❖ Delení fyzického disku na logické disky – diskové oblasti (partitions):

• Na systémech PC tzv. MBR (Master Boot Record) obsahuje tabulku diskových ˚ být nahrazena oblastí s 1-4 primárními diskovými oblastmi, jedna z nich muže rozšíˇrenou diskovou oblastí,

• Rozšíˇrená disková oblast se delí ˇ na logické diskové oblasti popsané EBR (Extended Boot Record) nacházejícími se v jejich prvním sektoru a vytváˇrejícími ˇ zˇretezený seznam.

• Pro správu diskových oblastí lze užít programy fdisk, fdisk, gparted, ... • LVM = Logical Volume Manager: umožnuje ˇ tvorbu logických disku˚ pˇresahujících ˇ velikosti, pˇridávání a ubírání disku, hranice fyzického disku, snadnou zmenu ˚ tvorbu snímku, ˚ ... ˇ ❖ Formátování – program mkfs; existuje (existovalo) také nízkoúrovnové formátování. vytvoření struktury stop a sektorů na fyzickém disku

❖ Kontrola konzistence souborového systému: program fs k.


❖ Ruzné ˚ typy souborových systému: ˚ ufs, ufs2, ext2, ext3, ext4, btrfs, ReiserFS, HFS+ (Mac OS X), FFS, XFS (od Silicon Graphics, puvodn ˚ eˇ pro IRIX), JFS (od IBM), ZFS (od Sunu), FAT, VFAT, FAT32, HPFS, NTFS, ISO9660 (Rock Ridge, Joliet), UDF, Lustre (Linuxové clustry a superpoˇcítaˇce), GPFS (clustry a superpoˇcítaˇce), ... ❖ Virtuální souborový systém (VFS) – vrstva, která zastˇrešuje všechny použité ˇ souborové systémy a umožnuje pracovat s nimi jednotným, abstraktním zpusobem. ˚ ❖ Sít’ové souborové systémy: NFS, ...

přístup ke vzdáleným diskům v síti

ˇ ❖ Speciální souborové systémy: procfs, sysfs (souborové systémy informující o dení ˇ v systému a umožnující nastavení jeho parametru), ˚ tmpfs (souborový systém alokující prostor v RAM a sloužící pro ukládání doˇcasných dat), ...


Žurnálování

žurnál = soubor či oblast na disku metadata = data o datech (kde se vyskytují, jejich velikost,...)

❖ Žurnál slouží pro záznam modifikovaných metadat (pˇríp. i dat) pˇred jejich zápisem na disk.

• Obvykle implementován jako cyklicky pˇrepisovaný buffer ve speciální oblasti disku. ❖ Kompromis mezi žurnálováním a nežurnálováním dat pˇredstavuje pˇredˇrazení zápisu ˇ dat na disk pˇred zápis metadat do žurnálu: zajistí konzistenci pˇri chybeˇ behem zápisu dat na konec souboru (ˇcásteˇcneˇ zapsaná nová data nebudou uvažována).

např. smazání souboru - je potřeba odstranit soubor z adresáře, uvolnit místo na disku...nemusí se povést všechny potřebné operace operace se nejprve uloží do žurnálu a až pak se provedou. pokud se některá nezdaří, žurnál po startu systému zajišťuje, aby byly všechny operace dokončeny

ˇ nebo neprobehnou. ˇ ❖ Operace pokryté žurnálováním jsou atomické: bud’ uspejí

ˇ ˇ a rychlejší návrat do konzistentního stavu po chybách ❖ Umožnuje spolehlivejší provedením operací pouze zaznamených v žurnálu, ale dosud nerealizovaných ve vlastním obsahu disku. ❖ Implementace žurnálování není snadná: musí zajišt’ovat správné poˇradí zápisu ˇ operací, které ovlinuje plánování diskových operací v OS a také pˇrípadneˇ jejich pˇreuspoˇrádání v samotném disku. ❖ Journaling File Systems: (ext3, ext4, ufs, ReiserFS, XFS, JFS, NTFS, ...): Správa souboru˚ – p.17/76

Alternativy k žurnálování ❖ Technologie copy-on-write (napˇr. ZFS, btrfs):

• Nejprve zapisuje nová data cˇ i metadata na disk, pak je zpˇrístupní. • Zmeny ˇ provádí hierarchicky v souladu s hierarchickým popisem obsahu disku. • Na nejvyšší úrovni se udržuje nekolik ˇ verzí koˇrenového záznamu se zabezpeˇcovacím kódem a cˇ asovými razítky.

• Po chybeˇ se bere koˇren s nejˇcerstvejším ˇ cˇ asovým razítkem a správným kontrolním souˇctem.


Alternativy k žurnálování ❖ Další možnosti:

• Soft updates (napˇr. UFS): sleduje závislosti mezi zmen ˇ enými ˇ metadaty a daty a zaruˇcuje zápis na disk v takovém poˇradí, aby v kterékoli dobeˇ byl obsah disku konzistentní (až na možnost vzniku volného místa považovaného za obsazené).

• Log-structured file systems (LFS, UDF): celý souborový systém má charakter logu ˇ s obsahem disku vždy pˇrístupným pˇres poslední záznam (a odkazy z nej). ˇ bázi pro implementaci ❖ Poznámka: CoW nabízí rovnež

• snímku˚ souborového systému (uložení stavu v urˇcitém okamžiku s možností ˇ pozdejšího návratu – staˇcí zálohovat si pˇrístup ke starším uzlum ˚ stromové struktury souborového systému) a

• klonu˚ souborového systému (vytvoˇrení kopií, které jsou v budoucnu samostatneˇ ˇ manipulovány – vzniká nekolik cˇ ásteˇcneˇ sdílených stromových struktur popisujících ruznéí ˚ verze obsahu souborového systému).


Klasický UNIXový systém souboru˚ (FS) boot blok super blok tabulka i-uzlu˚ datové bloky

pro zavedení systému pˇri startu informace o souborovém systému (typ, velikost, poˇcet iuzlu, ˚ volné místo, volné i-bloky, koˇrenový adresáˇr,...) tabulka s popisy souboru˚ data souboru˚ a bloky pro nepˇrímé odkazy

zaváděcí blok, zavaděč operačního systému údaje o souborovém systému - typ, velikost, volné místo, odkaz na kořenový adresář, údaje o i-uzlech

i-uzly

ˇ ❖ Nekteré modifikace základního konceptu ˇ klasického Unixového FS v nekterých navazujících souborových systémech:

• 12 pˇrímých odkazu˚ z i-uzlu. • Tabula i-uzlu˚ rozdelena ˇ ˇ do nekolika cˇ ástí, mezi nimi uloženy datové bloky (lepší lokalita).


i-uzel ❖ Základní datová struktura popisující soubor v UNIXu. ❖ i-uzel obsahuje metadata:

neobsahuje jméno souboru, to se nachází v adresáři, soubor může mít více jmen

typ souboru (obyˇcejný, adresáˇr, zaˇrízení, ...) délka souboru v bajtech mtime = cˇ as poslední modifikace dat atime = cˇ as posledního pˇrístupu ctime = cˇ as poslední modifikace i-uzlu UID = identifikace vlastníka (ˇcíslo) GID = identifikace skupiny (ˇcíslo) pˇrístupová práva (ˇcíslo, napˇríklad 0644 znamená rw-r–r–) odkazuje na pomocný poˇcet pevných odkazu˚ (jmen) adresovací blok, který obsahuje 10 pˇrímých odkazu˚ další odkazy 1 nepˇrímý odkaz první úrovneˇ • tabulka odkazu˚ na datové bloky: 1 nepˇrímý odkaz druhé úrovneˇ odkazují na bloky odkazů odkazující na bloky 1 nepˇrímý odkaz tˇretí úrovneˇ odkazů... • (odkaz na) další informace (ACL, extended attributes, dtime, ...)

• • • • • • • • •


Inode data blocks

Block map 0 1 2 3 4 5 6 7 8 9 indirect 1 indirect 2 indirect 3

...


❖ Teoretický limit velikosti souboru: 10 ∗ D + N ∗ D + N 2 ∗ D + N 3 ∗ D kde:

• N = D/4 je poˇcet odkazu˚ (4B) v bloku a • D je velikost bloku v bajtech. nap. 4096

v tomto příkladu tedy může jeden blok obsahovat 1024 odkazů

❖ Velikost souboru˚ je omezena také dalšími strukturami FS, VFS, rozhraním jádra a architekturou systému (32b/64b) – viz Large File System support: podpora souboru˚ > 2GiB. ❖ Co vypisují programy o velikosti souboru? ˚

• du soubor – zabrané místo v blocích, vˇcetneˇ režie, • ls -l soubor – velikost souboru v bajtech, • df – volné místo na namontovaných discích. ˇ i-uzlu: ❖ Zpˇrístupnení

• ls -i soubor – cˇ íslo i-uzlu souboru soubor, • ils -e /dev/... n – výpis i-uzlu n na /dev/...

každé zařízení má své vlastní uzly


ˇ ❖ Architektura souborových systému˚ je ovlivnována snahou o minimalizaci jejich režie pˇri ˇ pruchodu, ˚ pˇresuvu v souboru (seek), zvetšování/zmenšování souboru:

• • • •

snadnost vyhledání adresy prvního/urˇcitého bloku souboru, snadnost vyhledání lineárneˇ následujících bloku, ˚ snadnost pˇridání/ubrání dalších bloku, ˚ snadnost alokace/dealokace volného prostoru (informace o volných oblastech, minimalizace externí fragmentace).

❖ FS (a ˇrada jeho následníku˚ UFS, ext2, ext3) pˇredstavuje kompromis s ohledem na pˇrevážneˇ malé soubory.

• U vetších ˇ ˇ objem metadat. souboru˚ nutno procházet/modifikovat vetší ❖ Další optimalizace pro malé soubory: data pˇrímo v i-uzlu (napˇr. u symbolických odkazu˚ definovaných dostateˇcneˇ krátkou cestou, tzv. fast symlinks).


Jiné zpusoby ˚ organizace souboru˚ soubor = posloupnost dat na disku

❖ Kontinuální uložení: jedna spojitá posloupnost na disku.

• Problémy se zvetšováním ˇ souboru˚ díky externí fragmentaci nebo obsazení prostoru hned za koncem souboru.

nepoužívá se

ˇ ❖ Zˇretezené seznamy bloku: ˚ každý datový blok obsahuje kromeˇ dat odkaz na další blok (nebo pˇríznak konce souboru).

• Pˇri pˇrístupu k náhodným blokum ˇ ˚ cˇ i ke konci souboru (zmena velikosti) nutno projít celý soubor.

• Chyba kdekoliv na disku muže ˚ zpusobit ˚ ztrátu velkého objemu dat (rozpojení seznamu). pole integerů

❖ FAT (File Allocation Table): seznamy uložené ve speciální oblasti disku. Na zaˇcátku disku je (pro vyšší spolehlivost zdvojená) tabulka FAT, která má položku pro každý blok. ˇ Do této tabulky vedou odkazy z adresáˇru. ˚ Položky tabulky mohou být zˇretezeny do seznamu, ˚ pˇríp. oznaˇceny jako volné cˇ i chybné.

• Opet ˇ vznikají problémy s náhodným pˇrístupem. Správa souboru˚ – p.25/76

Jiné zpusoby ˚ organizace souboru˚ ❖ B+ stromy:

strom = datová struktura, skládá se z uzlů a hran, každý uzel může obsahovat N odkazů na další uzly, logaritmická složitost B+ strom = speciální typ stromu, všechny uzly se skládají ze seřazených sekvencí

• Vnitˇrní uzly obsahují sekvenci link0 , key0 , link1 , key1 , ..., linkn , keyn , linkn+1 , kde keyi < keyi+1 pro 0 ≤ i < n. Hledáme-li záznam s klíˇcem k, pokraˇcujeme link0 , je-li k < key0 ; jinak linki , 1 ≤ i ≤ n, je-li keyi−1 ≤ k < keyi ; jinak užijeme keyn+1 .

• Listy mají podobnou strukturu. Je-li keyi = k pro nejaké ˇ 0 ≤ i ≤ n, linki odkazuje na hledaný záznam. Jinak hledaný záznam neexistuje.

• Poslední odkaz linkn+1 v listech je užit k odkazu na následující listový uzel pro urychlení lineárního pruchodu ˚ indexovanými daty. K0

K00

K000

D0

Kn

K0n0

K00n00

D1


Jiné zpusoby ˚ organizace souboru˚ ❖ B+ stromy:

• Vkládá se na listové úrovni. Dojde-li k pˇreplnení, ˇ ˇ a pˇridá se nový list se rozštepí ˇ se pokraˇcuje smerem ˇ ke odkaz do nadˇrezeného vnitˇrního uzlu. Pˇri pˇreplnení ˚ být nový koˇren pˇridán. koˇreni. Nakonec muže

• Ruší se od listové úrovne. ˇ Klesne-li zaplnenost ˇ sousedních uzlu˚ na polovinu, uzly se spojí a ruší se jeden odkaz na nadˇrazené úrovni. Rušení muže ˚ pokraˇcovat ˇ smerem ke koˇreni. Nakonec muže ˚ jedna úrovenˇ ubýt. ❖ B+ stromy a jejich ruzné ˚ varianty jsou použity pro popis diskového prostoru ˇ pˇrideleného souborum ˚ v ruzných ˚ moderních souborových systémech:

• XFS, JFS, ReiserFS, btrfs, ..., • v omezené podobeˇ tzv. stromu˚ extentu˚ v ext4 (pouze dveˇ úrovne, ˇ bez vyvažování, ˇ bez zˇretezení listu), ˚ podobná struktura je i v NTFS. ❖ Je možné užít i jiné vyvážené stromové struktury: napˇr. AVL stromy (ZFS).


Jiné zpusoby ˚ organizace souboru˚ extent udává, kde na disku začíná a kolik bloků obsahuje

❖ V moderních systémech se cˇ asto indexuje alokovaný prostor po tzv. extentech, tj. ˇ posloupnostech promenného poˇctu bloku˚ uložených na disku fyzicky za sebou:

• zrychluje se práce s velkými soubory: menší, lépe vyvážené indexové struktury; menší objem metadat, které je tˇreba procházet a udržovat; lepší lokalita dat i metadat. ❖ Extenty jsou použity ve všech výše zmínených ˇ systémech s B+ stromy a jejich variantami.

• B+ stromy se snadno kombinují s extenty. To neplatí pro klasický Unixový strom, ˇ který není kompatibilní s adresováním jednotek promenné velikosti. ❖ Lineárnímu pruchodu ˚ muže ˚ pomoci prolinkování listu˚ vyhledávacích stromu, ˚ je-li použito. ❖ Pro malé soubory muže ˚ B+ strom pˇredstavovat zbyteˇcnou režii: používá se pˇrímé uložení v i-uzlu nebo pˇrímé odkazy na extenty z i-uzlu (do urˇcitého poˇctu). nevýhoda B+ - vyšší režie


Ext4 ❖ Strom extentu: ˚

❖ Malé soubory: až 4 extenty odkazované pˇrímo z i-uzlu, pˇríp. pˇrímo v i-uzlu (symbolické odkazy). Správa souboru˚ – p.29/76

NTFS ❖ MFT – Master File Table: alesponˇ jeden ˇrádek pro každý soubor.

❖ Obsah souboru pˇrímo v záznamu MFT odpovídajícím pˇríslušnému souboru, nebo ˇ rozdelen na extenty odkazované z tohoto záznamu, nebo z pomocných MFT záznamu˚ odkazovaných z primárního MFT záznamu ve stylu B+ stromu.


Organizace volného prostoru ❖ Organizace volného prostoru v klasickém Unixovém FS a ˇradeˇ jeho následovníku˚ (UFS, ext2, ext3) a také v NTFS: bitová mapa s jedním bitem pro každý blok.

• Umožnuje ˇ zrychlit vyhledávání volné souvislé oblasti pomocí bitového maskování ˇ ˇ (test volnosti nekolika bloku˚ souˇcasne). ❖ Další zpusoby ˚ organizace volného prostoru:

• • • •

seznam, oznaˇcení volných položek v tabulce bloku˚ (FAT), B+ strom (adresace velikostí a/nebo offsetem),

lze hledat podle velikosti, kterou potřebujeme

ˇ nekdy se také – jako u btrfs – eviduje jen obsazený prostor podle pozice na disku ˇ se vytváˇrí pomocné struktury pro efektivnejší ˇ (a pˇrípadneˇ pouze v pameti vyhledávání – napˇr. red-black stromy bitových map). red-black strom - nejrychlejší v nejhorších případech

❖ Volný prostor muže ˚ být také organizován po extentech.


Adresáˇr ❖ Soubor obsahující seznam dvojic – “hard-links” – (jméno souboru, £íslo i-uzlu): hard link = odkazuje pouze na soubory, nemůže odkazovat do jiných oddílů

• jméno souboru – melo ˇ v tradiˇcním UNIXu délku max 14 znaku, ˚ – dnes je typicky až 255 znaku, ˚ – muže ˚ obsahovat jakékoli znaky kromeˇ '/' a ’\0’, • £íslo i-uzlu je u klasického Unixového FS a souborových systému˚ z neho ˇ

vycházejících index do tabulky i-uzlu˚ logického disku (v jiných pˇrípadech muže ˚ sloužit jako index pro vyhledávání v B+ stromu apod.).

❖ Adresáˇr vždy obsahuje jména:

. ..

odkaz na sebe odkaz na rodiˇcovský adresáˇr

❖ Poznámka: rychlost vyhledávání/vkládání: seznam, B+ stromy a jejich varianty: NTFS, ˇ neužívá vyvažování, vyhledává XFS,JFS, btrfs, HFS+, ext3/4 (H-stromy: 1 nebo 2 úrovne, na základeˇ zahashovaného jména), ... Správa souboru˚ – p.32/76

❖ Soubor muže ˚ mít více jmen:

• ln jmeno-existuji iho-souboru nove-jmeno ❖ Omezení: Obeˇ jména musí být v rámci jednoho logického disku! ❖ Rušení souboru (rm soubor) ruší pevný odkaz (jméno, £íslo i-uzlu) a snižuje poˇcitadlo odkazu˚ v i-uzlu. Dokud je poˇcitadlo nenulové, soubor se nemaže. smaže pouze jeden odkaz, ne celý soubor

❖ Princip montování disku: ˚

• Všechny soubory jsou v jednom “stromu” adresáˇru. ˚ • Další logické disky lze pˇripojit programem mount.


❖ Pˇríklad: mount /dev/floppy /mnt

/dev/floppy

/

/

bin

usr

tmp1

mnt

tmp2

/

bin

usr

mnt

tmp1

tmp2 Správa souboru˚ – p.34/76

❖ Poznámky:

• Parametry pˇríkazu mount – viz man mount. • Soubor /et /fstab – popis disku˚ typicky pˇripojovaných na urˇcité pozice adresáˇrového stromu.

• Soubor /et /mtab – tabulka aktuálneˇ pˇripojených disku. ˚ • Nekteré ˇ ˇ technologie umožnují automatické montování noveˇ pˇripojených novejší zaˇrízení. Napˇr. udev dynamicky vytváˇrí rozhraní souborového systému na zaˇrízení ˇ v adresáˇrí /dev a informuje zbytek systému prostˇrednictvím sbernice D-Bus, ˚ provést automatické montování a další akce aplikace nautilus pak muže ˇ (parametry muže ˚ zjištovat automaticky, cˇ erpat z ruzných ˚ nastavení zúˇcastnených technologií, ale pˇrednost má stále /et /fstab).

• Automounter – automaticky pˇripojuje potˇrebné disky pˇri pokusu o pˇrístup na pozici ˇ být pˇripojeny, a také po urˇcité dobeˇ neaktivity adresáˇrového stromu, kam by mely disky odpojuje (výhodné zejména u sítových souborových systému). ˚

• Union mount: – Montuje více disku˚ (adresáˇru) ˚ do jednoho místa – obsah je pak sjednocením ˇreší kolize obsahu namontovaných adresáˇru˚ s tím, že se vhodným zpusobem ˚ (napˇr. prioritou zdrojových disku/adresáˇ ˚ ru). ˚ – Plan9, Linux – UnionFS, ... – UnionFS: má copy-on write sémantiku: soubor puvodn ˇ ˚ eˇ v read-only vetvi, pˇri ˇ eˇ se uloží do read-write vetve ˇ zmen s vyšší prioritou. Správa souboru˚ – p.35/76

Typy souboru˚ ❖ Pˇríkaz ls -l vypisuje typ jako první znak na ˇrádku: d b c l p s

obyˇcejný soubor adresáˇr blokový speciální soubor znakový speciální soubor symbolický odkaz (symlink) pojmenovaná roura socket

soubor, který reprezentuje nějaké zařízení, např. /dev/loop

slouží jako zprostředkovatel komunikace mezi procesy


Symbolické odkazy ln -s existují í-soubor symboli ký-odkaz symlink = soubor, odkazuje na soubor, neobsahuje údaje o souboru, pouze cestu k němu

❖ V datech souboru typu “symlink” je jméno jiného cílového suboru. ❖ Jádro pˇri otevˇrení souboru automaticky provede otevˇrení cílového souboru. ˇ en ˇ – pˇrístup k souboru pˇres nej ˇ ❖ Po zrušení cílového souboru zustává ˚ symlink nezmen ˇ vede k chybe. ❖ Symlink muže ˚ odkazovat na i jiný logický disk. ˇ ❖ Rešení cyklu: ˚ omezený poˇcet úrovní odkazu. ˚

zabraňuje zacyklení - jeden symlink odkazuje na druhý symlink, ten odkazuje zpátky na první

❖ Rychlé symlinky: uloženy v i-uzlu, pomalé symlinky: uloženy ve zvláštním souboru (užívá se tehdy, je-li cesta, která definuje symlink, pˇríliš dlouhá pro uložení do i-uzlu).


Speciální soubory soubor

tvoˇrí souborové rozhraní na zaˇrízení

/dev/hda /dev/hda1 /dev/sda /dev/mem /dev/zero /dev/null

první fyzický disk (master) na prvním ATA/PATA rozhraní (dˇríve) první logický disk (partition) na hda první fyzický disk SCSI cˇ i emulované SCSI (SATA/PATA/usb flash) ˇ fyzická pamet’ nekoneˇcný zdroj nulových bajtu˚ soubor typu "ˇcerná díra"– co se zapíše, to se zahodí; pˇri cˇ tení se chová jako prázdný soubor generátor náhodných cˇ ísel terminál první tiskárna myš zvuková karta souborové systémy nad soubory (losetup/mount -o loop=...) .......

/dev/random /dev/tty /dev/lp0 /dev/mouse /dev/dsp /dev/loop ......

❖ Poznámka: Názvy závisí na použitém systému (Linux). Správa souboru˚ – p.38/76

ˇ ❖ Výhoda zavedení speciálních souboru: ˚ Programy mohou použít bežné souborové rozhraní pro práci se soubory i na cˇ tení/zápis z ruzných ˚ zaˇrízení.

❖ Pˇríklady práce se speciálními soubory: dd if=/dev/hda of=mbrbackup bs=512 count=1 cat /dev/hda1 | gzip >zaloha-disku.gz cp /dev/zero /dev/hda1 # vynulov´ an´ ı disku


Pˇrístupová práva ❖ V UNIXu jsou typicky rozlišena práva pro vlastníka, skupinu a ostatní. (Rozšíˇrení: ACL (access control lists), viz man a l, man setfa l...) ❖ Uživatelé:

• Uživatele definuje administrátor systému (root): /et /passwd, • UID: cˇ íslo identifikující uživatele (root UID = 0). • Pˇríkaz hown – zmena ˇ vlastníka souboru (pouze root). ❖ Skupiny:

• Skupiny definuje administrátor systému (root): /et /group, • GID: cˇ íslo identifikující skupinu uživatelu, ˚ • Uživatel muže ˚ být cˇ lenem více skupin, jedna z nich je aktuální (používá se pˇri vytváˇrení souboru). ˚

• Pˇríkaz – groups – výpis skupin uživatele, – hgrp – zmena ˇ skupiny souboru, – newgrp – nový shell s jiným aktuálním GID. Správa souboru˚ – p.40/76

Typy pˇrístupových práv obyˇcejné soubory r právo cˇ íst obsah souboru w právo zapisovat do souboru x právo spustit soubor jako program adresáˇre r právo cˇ íst obsah (ls adres´ ar ˇ) w právo zapisovat = vytváˇrení a rušení souboru˚ x právo pˇristupovat k souborum ˚ v adresáˇri (cd adres´ ar ˇ, ls -l adres´ ar ˇ/soubor) ❖ Pˇríklad: -rwx---r-- (ˇcíselné vyjádˇrení: 0704):

• obyˇcejný soubor, •

vlastník: skupina: ostatní:

cˇ tení, zápis, provedení nemá žádná práva pouze cˇ tení


ˇ ❖ Zmena pˇrístupových práv – pˇríkaz hmod: chmod chmod chmod chmod

a+rw soubory 0644 soubor -R u-w . g+s soubor

# # # #

vˇ sichni mohou ˇ cı ´st i zapisovat rw-r--r-zak´ az ˇe z´ apis vlastn´ ıkovi nastav´ ı SGID -- viz d´ ale

❖ Výpis informací o souboru: ls -l soubor -rw-r--r-- 1 joe joe 331 Sep 24 13:10 .profile typ pr´ ava poˇ cet pevn´ ych odkaz˚ u vlastn´ ık skupina velikost cas posledn´ ˇ ı modifikace jm´ eno souboru Správa souboru˚ – p.42/76

Sticky bit ❖ Sticky bit je pˇríznak, který nedovoluje rušit cizí soubory v adresáˇri, i když mají všichni právo zápisu. chmod +t adresar chmod 1777 /tmp

# nastav´ ı Sticky bit

❖ Pˇríklad: /tmp má práva rwxrwxrwt


SUID, SGID ❖ Urˇcení práv pro procesy: UID EUID GID EGID

reálná identifikace uživatele = kdo spustil proces efektivní UID se používá pro kontrolu pˇrístupových práv ˇ (pro bežné programy je rovno UID) reálná identifikace skupiny = skupina toho, kdo spustil proces efektivní GID se používá pro kontrolu pˇrístupových práv ˇ (pro bežné programy je rovno GID)

❖ Vlastník programu muže ˚ propujˇ ˚ cit svoje práva komukoli, kdo spustí program s nastaveným SUID. uživatel, který pak spouští daný program, má práva vlastníka ❖ Pˇríklad: Program passwd musí editovat soubor /et /shadow, do kterého má právo zápisu pouze superuživatel root. nastavením chmod u+S tak umožníme uživatelům přistupovat k souboru jako root ❖ Pˇríklad propujˇ ˚ cených pˇrístupových práv: -rwsr-Sr-x fileUID fileGID

• s = je nastaveno x, S = není nastaveno x, • v našem pˇríkladu s: SUID=set user identification, EUID:=fileUID • v našem pˇríkladu S: SGID=set group identification: EGID:=fileGID Správa souboru˚ – p.44/76

Typická struktura adresáˇru˚ v UNIXu ❖ FHS = Filesystem Hierarchy Standard /bin /dev /etc /home /lib /proc /root /sbin /tmp

programy pro všechny (nutné pˇri bootování) obsahuje speciální soubory – rozhraní na zaˇrízení konfiguraˇcní soubory pro systém i aplikace domovské adresáˇre uživatelu˚ sdílené knihovny, moduly jádra (nutné pˇri bootování) obsahuje informace o procesech domovský adresáˇr superuživatele programy pro superuživatele (nutné pˇri bootování) doˇcasné pracovní soubory ˇ Pokraˇcování na další strane...


Typická struktura adresáˇru˚ v UNIXu – pokraˇcování: /usr

/usr/bin,sbin /usr/lib /usr/include /usr/share /usr/local /usr/src /var /var/log /var/spool /var/mail

ˇ systému – muže obsahuje soubory, které nejsou nutné pˇri zavádení ˚ se ˇ a muže ˚ být pouze pro cˇ tení pˇrimontovat až po bootu (napˇríklad ze síte) (napˇríklad na CD) programy, které nejsou tˇreba pro bootování knihovny (statické i dynamické) hlaviˇckové soubory pro jazyk C atd. soubory, které lze sdílet (napˇríklad pˇres sít’) nezávisle na architektuˇre poˇcítaˇce další hierarchie bin, sbin, lib,... urˇcená pro lokální (nestandardní) instalace programu˚ zdrojové texty jádra systému a programu˚ ˇ pˇri behu ˇ obsahuje soubory, které se mení systému záznamy o cˇ innosti systému pomocné soubory pro tisk atd. poštovní pˇrihrádky uživatelu˚


Datové struktury pro vstup/výstup


Typy souboru˚ a základní systémová volání ❖ Unix definuje tˇri základní kategorie souboru: ˚

• obyˇcejné soubory, • adresáˇre, • speciální soubory: – symbolické odkazy, – roury (pojmenované, nepojmenované), – sockety, – periferie (blokové, znakové). ❖ Základní systémová volání pro vstup/výstup: dup ioctl link, symlink lseek mknod

mount, umount open, close read, write sync, fsync unlink

open - otevře soubor close - zavře soubor unlink - smaže soubor lseek - posouvá se na danou pozici v otevřeném souboru mknod - vytvřáří blokové nebo znakové zařízení dup - duplikuje file descriptory


ˇ Použití vyrovnávacích pametí ❖ I/O buffering:

• buffer = vyrovnávací pamet’ ˇ (VP) • Cílem je minimalizace poˇctu pomalých operací s periferiemi (typicky s disky). • Vyrovnávací pameti ˇ jsou sdruženy v tzv. buffer pool: pevná/promenná ˇ velikost. operace se udržují ve vyrovnávací paměti, provádějí se rychleji, např. opakované čtení disku po malých částech buffer pool - sdružení vyrovnávacích pamětí

❖ Možná implementace: kernel Hash table

buffers

Disk

Process

free ...

prochází se seznam vyrovnávacích pamětí, alokovaných na danou položku hashovací tabulky, pokud je nalezen hledaný alokační blok, použije se, jinak se alokuje nová vyrovnávací paměť

při nedostatku paměti se vybere určitá část vyrovnávací paměti, přepíše se na disk a uvolní se pro další použití


ˇ Ctení Disk Buffer (2)

(1)

Process

data block

❖ Postup pˇri prvním cˇ tení (read): ˇ 1. pˇridelení VP a naˇctení bloku, 2. kopie požadovaných dat do adresového prostoru procesu (RAM→RAM). ❖ Pˇri dalším cˇ tení už pouze (2). ˇ ˇ (1) a (2). ❖ Ctení, které pˇrekroˇcí hranice bloku provede opet


Zápis

Disk Buffer (1) Process

data block

0

Buffer (2) Process

data block

1

1. z disku se do bufferu načte část, která se má upravit 2. proces upraví data v bufferu 3. data jsou zapsána zpět na disk

fsync, sync Buffer (3) Process 1

data block

❖ Postup pˇri zápisu (write): ˇ 1. pˇridelení VP a cˇ tení bloku do VP, 2. zápis dat do VP (RAM→RAM), nastaví se pˇríznak modifikace (dirty bit), ˇ zápis na disk, nuluje pˇríznak. 3. zpoždený

lze vynutit okamžitý zápis na disk Správa souboru˚ – p.51/76

Otevˇrení souboru pro cˇ tení fd = open("/path/file", O_RDONLY); ˇ že soubor ješteˇ nebyl otevˇren: ❖ V pˇrípade, 1. Vyhodnotí cestu a nalezne cˇ íslo i-uzlu. 2. V systémové tabulce aktivních i-uzlu˚ vyhradí novou položku a naˇcte do ní i-uzel. ˇ Vzniká rozšíˇrená pamet’ová kopie i-uzlu: v-uzel. 3. V systémové tabulce otevˇrených souboru˚ vyhradí novou položku a naplní ji: • odkazem na položku tabulky v-uzlu, ˚ • režimem otevˇrení, • pozicí v souboru (0), • cˇ ítaˇcem poˇctu referencí na tuto položku (1). 4. V poli deskriptoru˚ souboru˚ v uživatelské oblasti procesu vyhradí novou položku (první volná) a naplní ji odkazem na položku v tabulce otevˇrených souboru. ˚ 5. Vrátí index položky v poli deskriptoru. ˚


❖ Ilustrace prvního otevˇrení souboru (ˇcísla v obrázku udávají cˇ ítaˇce poˇctu referencí na danou položku):

file descriptor table

open file table

fd

v−node table

1

Disk

1

user area v-uzel = rozšířená paměťová kopie i-uzlu, pamatuje si např. kolikrát je soubor otevřen, číslo i-uzlu napříč všemi disky,... 1.otevření souboru - alokuje položku v tabulce v-uzlů, do ní zapíše údaje o i-uzlu (poznačí 1 otevření), alokuje se položka v tabulce otevřených souborů a naplní se odkazem na záznam v tabulce v-uzlů (pamatuje si režim otevření, čítač otevření souboru např 1x pro čtení, 2x pro zápis), na závěr se alokuje položka v tabulce popisovačů souborů, naplní se odkazem na záznam v tabulce otevřených souborů, číslo popisovače souboru se vrátí procesu otevření již otevřeného souboru - otevře se i-uzel, v tabulce v-uzlů se u odpovídajícího záznamu navýší počet otevření, alokuje se nová položka v tabulce otevření souborů, naplní se odkazem na v-uzel, alokuje se nová položka v tabulce popisovačů Správa souboru˚ – p.53/76

❖ Otevˇrení již jednou otevˇreného souboru: 1. Vyhodnotí cestu a získá cˇ íslo i-uzlu. 2. V systémové tabulce v-uzlu˚ nalezne již naˇctený i-uzel. Zvýší poˇcitadlo odkazu˚ na v-uzel o 1. ˇ 3. A další beze zmeny.


fd1 fd

open file table

v−node table

2 1

user area

1


❖ Pˇri otevírání se provádí kontrola pˇrístupových práv.

❖ Soubor je možno otevˇrít v režimu:

• cˇ tení, • zápis, • cˇ tení i zápis modifikovaných volbou dalších parametru˚ otevˇrení:

• • • •

pˇridávání, zkrácení na nulu, synchronní zápis, ...

ˇ ❖ Pˇri chybeˇ vrací -1 a nastaví chybový kód do knihovní promenné errno (pro standardní chybové kódy viz man errno; lze užít napˇr. spolu s knihovní funkcí perror). Podobneˇ je tomu i u ostatních systémových volání v UNIXu.


ˇ Ctení a zápis z/do souboru ˇ ❖ Ctení ze souboru – n = read(fd, buf, 3000); 1. Kontrola platnosti fd.

(popisovač souboru, ukazatel na místo kam uložit data, velikost načtených dat)

ˇ že jde o první pˇrístup k souboru, dojde k alokaci VP a naˇctení bloku˚ 2. V pˇrípade, souboru z disku do VP. Jinak dochází k alokaci VP a diskové operaci jen tehdy, je-li je to nutné. 3. Kopie požadovaných dat z VP (RAM, jádro) do pole buf (RAM, adresový prostor procesu). ˇ 4. Funkce vrací poˇcet opravdu pˇreˇctených bajtu˚ nebo -1 pˇri chybe.

❖ Zápis do souboru – n = write(fd, buf, 3000);

• Funguje podobneˇ jako read – viz i dˇríve.


Pˇrímý pˇrístup k souboru n = lseek(fd, offset, whence);

přístup na libovolnou pozici v souboru

❖ Postup pˇri žádosti o pˇrímý pˇrístup k souboru: 1. Kontrola platnosti fd. 2. Nastaví pozici offset bajtu˚ od • zaˇcátku souboru pro when e=SEEK_SET, • aktuální pozice pro when e=SEEK_CUR, • konce souboru pro when e=SEEK_END. ˇ 3. Funkce vrací výslednou pozici od zaˇcátku souboru nebo -1 pˇri chybe. ❖ Poznámka: Hodnota parametru offset muže ˚ být záporná, nelze však nastavit pozici pˇred zaˇcátek souboru.


❖ Sparse files – “ˇrídké soubory”:

• Vznikají nastavením pozice za konec souboru a zápisem. • Bloky, do kterých se nezapisovalo nejsou alokovány a nezabírají diskový prostor. Pˇri cˇ tení se považují za vynulované.

DATA

000000000000

DATA

0000000000000000 DATA


Zavˇrení souboru x = close(fd); ❖ Postup pˇri uzavírání souboru: 1. Kontrola platnosti fd. 2. Uvolní se odpovídající položka v tabulce deskriptoru, ˚ sníží se poˇcitadlo odkazu˚ v odpovídající položce tabulky otevˇrených souboru. ˚ 3. Pokud je poˇcitadlo odkazu˚ nulové, uvolní se odpovídající položka v tabulce otevˇrených souboru˚ a sníží se poˇcitadlo odkazu˚ ve v-uzlu. 4. Pokud je poˇcitadlo odkazu˚ nulové, i-uzel se z v-uzlu okopíruje do VP a uvolní. ˇ 5. Funkce vrací nulu nebo -1 pˇri chybe. ❖ Pokud se ukonˇcuje proces, automaticky se uzavírají všechny jeho deskriptory. ❖ Uzavˇrení souboru nezpusobí ˚ uložení obsahu jeho VP na disk!


Duplikace deskriptoru souboru fd2 = dup(fd); fd2 = dup2(fd,newfd); ❖ Postup pˇri duplikaci deskriptoru: 1. Kontrola platnosti fd. 2. Kopíruje danou položku v tabulce deskriptoru˚ do první volné položky (dup) nebo do zadané položky (dup2). Je-li deskriptor newfd otevˇren, dup2 ho automaticky uzavˇre. 3. Zvýší poˇcitadlo odkazu˚ v odpovídající položce tabulky otevˇrených souboru. ˚ ˇ 4. Funkce vrací index nové položky nebo -1 pˇri chybe.


fd fd2

open file table

v−node table

1 2

user area

ˇ ❖ Poznámka: Použití pro pˇresmerování stdin/stdout. Správa souboru˚ – p.60/76

Rušení souboru x = unlink("/path/filename"); ❖ Postup pˇri rušení souboru: 1. Kontrola platnosti jména souboru. 2. Odstraní pevný odkaz (hard link) mezi jménem souboru a i-uzlem. Vyžaduje právo zápisu do adresáˇre. 3. Zmenší poˇcitadlo jmen v i-uzlu. ˇ vˇcetneˇ 4. Pokud poˇcet jmen klesne na nulu a i-uzel nikdo nepoužívá, je i-uzel uvolnen ˇ odloženo všech používaných bloku˚ souboru. Je-li i-uzel používán, bude uvolnení až do okamžiku zavˇrení souboru (poˇcitadlo otevˇrení souboru klesne na 0). ˇ 5. Funkce vrací nulu nebo -1 pˇri chybe. ❖ Poznámky:

• Proces muže ˚ provést unlink na otevˇrený soubor a dále s ním pracovat až do jeho uzavˇrení.

• Je možné zrušit spustitelný soubor, i když beží ˇ jím ˇrízené procesy (výhoda pˇri instalaci nových verzí programu). ˚ Správa souboru˚ – p.61/76

Další operace se soubory • • • • • • •

Vytvoˇrení souboru: creat, open Pˇrejmenování: rename Zkrácení: truncate, ftruncate Zamykání záznamu: ˚ fcntl nebo lockf ˇ atributu: Zmena ˚ chmod, chown, utime Získání atributu: ˚ stat Zápis VP na disk: sync, fsync


Adresáˇrové soubory ˇ ❖ Adresáˇre se liší od bežných souboru: ˚

• • • • •

vytváˇrí se voláním mkdir (vytvoˇrí položky . a ..), mohou být otevˇreny voláním opendir, mohou být cˇ teny voláním readdir, mohou být uzavˇreny voláním losedir, modifikaci je možné provést pouze vytváˇrením a rušením souboru˚ v adresáˇri ( reat, link, unlink, ...).

❖ Poznámka: Adresáˇre nelze cˇ íst/zapisovat po bajtech! ❖ Pˇríklad obsahu adresáˇre:

číslo i-uzlu

32577 2 2361782 1058839 1661377

jméno

. .. Archiv Mail tmp Správa souboru˚ – p.63/76

Pˇripojení systému souboru˚ • • • •

jako první se připojí kořenový systém

V poˇcítaˇci muže ˚ být více fyzických disku. ˚ ˇ na cˇ ásti (partition, volume). Disk mužeme ˚ rozdelit Každá cˇ ást je identifikována speciálním souborem (/dev/hda1, /dev/hda2, ...). Logický disk muže ˚ obsahovat souborový systém. – mount pˇripojí systém souboru˚ do hlavního adresáˇrového stromu, – umount odpojí systém souboru. ˚

❖ Pˇríklad: x = mount("/dev/hda2","/mnt",parameters);

v−node table

mount table

(zařízení které chceme připojit, místo v současném adresářovém stromu, parametry připojení)

root filesystem

boot−block MP

copy

i−node

/mnt

hda2#

/dev/hda2

copy buffer

copy

boot−block super−block / i−node Správa souboru˚ – p.64/76

Blokové a znakové speciální soubory ˇ ❖ Jádro mapuje bežné souborové operace (open, read, ...) nad blokovými a znakovými speciálními soubory na odpovídající podprogramy tyto operace implementující prostˇrednictvím dvou tabulek:

• tabulky znakových zaˇrízení a • tabulky blokových zaˇrízení.

zápis a čtení po znacích zápis a čtení po blocích

ˇ ❖ Zmínené tabulky obsahují ukazatele na funkce implementující pˇríslušné operace v ovladaˇcích pˇríslušných zaˇrízení. ❖ Ovladaˇc (device driver ) je sada podprogramu˚ pro ˇrízení urˇcitého typu zaˇrízení.


obsahem speciálního souboru je: typ speciálního souboru, vlastník, práva,...hlavní a vedlejší číslo, zabírá pouze i-uzel

❖ Rozhraní zaˇrízení – speciální soubory (napˇr. /dev/tty): mají v i-uzlu typ souboru a dveˇ cˇ ísla: cˇ íslo význam hlavní cˇ íslo (major number) vedlejší cˇ íslo (minor number)

typ zaˇrízení instance zaˇrízení

• Typ souboru (blokový nebo znakový) urˇcuje tabulku. • Hlavní cˇ íslo se použije jako index do tabulky zaˇrízení. • Vedlejší cˇ íslo se pˇredá jako parametr funkce ovladaˇce (identifikace instance zaˇrízení).


character device switch table

kernel code

open close read write ioctl

device drivers

major 0 number 1 2

block device switch table

term_open term_close term_read term_write term_ioctl

open close read write ioctl strategy

disk_open disk_close disk_read disk_write disk_ioctl disk_st

0 1 2 3

... open("/dev/hdb1",O_RDWR);

i−node type = block major = 2 minor = 65 Správa souboru˚ – p.67/76

Terminály ˇ textový vstup/výstup ❖ Terminály – fyzická nebo logická zaˇrízení ˇrídící (primárne) systému: vstup/výstup po ˇrádcích, editace na vstupním ˇrádku, speciální znaky (Ctrl-C, Ctrl-D, ...), ... ❖ Rozhraní:

• /dev/tty – ˇrídící terminál aktuálního procesu, odkaz na pˇríslušné terminálové zaˇrízení,

• /dev/ttyS1, ... – terminál na sériové lince, • /dev/tty1, ... – virtuální terminály (konzole), • pseudoterminály (napˇr. /dev/ptmx a /dev/pts/1, ...) – tvoˇreny párem master/slave emulujícím komunikaci pˇres sériovou linku (napˇr. použito u X-terminálu cˇ i ssh).


❖ Ruzné ˚ režimy zpracování znaku˚ (line discipline): režim raw cbreak cooked

význam bez zpracování ˇ zpracovává jen nekteré znaky (Ctrl-C, ...) zpracovává vše

❖ Nastavení režimu zpracování znaku˚ (nastavení ovladaˇce terminálu): program stty. ❖ Nastavení režimu terminálu (tedy fyzického zaˇrízení nebo emulujícího programu):

• promenná ˇ TERM – typ aktuálního terminálu, • databáze popisu terminálu˚ (možnosti nastavení terminálu): terminfo cˇ i term ap. • nastavení pˇríkazy: tset, tput, reset, ... ❖ Knihovna urses – standardní knihovna pro ˇrízení terminálu a tvorbu aplikací s terminálovým uživatelským rozhraním (vˇcetneˇ menu, textových oken apod.).


Roury ❖ Roury (pipes) – jeden z typu˚ speciálních souboru. ˚ Rozlišujeme:

• roury nepojmenované – nemají adresáˇrovou položku, – pipe vrací dva deskriptory (ˇctecí a zápisový), jsou pˇrístupné pouze pˇríbuzným proces, který rouru zavolal, případně jeho potomci procesum, ˚ – vytváˇrí se v kolonách (napˇr. p1 | p2 | p3),

• Roury pojmenované – vytvoˇrení mknod cˇ i mkfifo. ❖ Roury representují jeden z mechanismu˚ meziprocesové komunikace. ❖ Implementace: kruhový buffer s omezenou kapacitou (využívá jen pˇrímé odkazy na bloky v i-uzlu). ❖ Procesy komunikující pˇres rouru (producent a konzument) jsou synchronizovány.


Sockets ˇ sít’ovou i lokální komunikaci. ❖ Umožnují ˇ ❖ Lokální komunikace muže ˚ probíhat pˇres sockety pojmenované a zpˇrístupnené v souborovém systému). ❖ API pro práci se sockets:

• • • • •

vytvoˇrení (so ket), cˇ ekání na pˇripojení (bind, listen, a

ept), pˇripojení ke vzdálenému poˇcítaˇci ( onne t), pˇríjem a vysílání (re v, send, read, write), uzavˇrení ( lose).

❖ Sockets podporují blokující/neblokující I/O. U neblokujícího režimu je možno použít sele t pro souˇcasnou obsluhu více sockets jedním procesem (vláknem).


VFS ❖ VFS (Virtual File System) vytváˇrí jednotné rozhraní pro práci s ruznými ˚ souborovými ˇ systémy, oddeluje vyšší vrstvy OS od konkrétní implementace jednotlivých souborových operací na jednotlivých souborových systémech. ˇ ❖ Pro popis souboru˚ používá zobecnené a rozšíˇrené i-uzly (tzv. v-uzly), které obsahují unikátní numerickou identifikaci pˇríslušného souboru v rámci systému (nejen v rámci logického disku jako u i-uzlu).


❖ VFS v Linuxu:

• Používá objektove-orientovaný ˇ pˇrístup se 3 základními typy objektu: ˚ – souborové systémy, – v-uzly pro soubory s nimiž se pracuje, – otevˇrené soubory, • Každý z techto ˇ objektu˚ obsahuje odkazy na funkce implementující pˇríslušné operace.

• Navíc má VFS tabulku s odkazy na funkce, které umožnují ˇ provést pro jednotlivé známé souborové systémy operaci mount.

• Pracuje s tzv. položkami adresáˇru˚ d-entries – mapují jméno uložené v adresáˇri na v-uzel, ukládá se v d-cache pro urychlení pˇrekladu jmen na v-uzly.


NFS ˇ ❖ NFS (Network File System) – transparentneˇ zpˇrístupnuje soubory uložené na vzdálených systémech.


ˇ ❖ Umožnuje kaskádování: lokální pˇripojení vzdáleného adresáˇrového systému do jiného vzdáleného adresáˇrového systému. ❖ Autentizace cˇ asto prostˇrednictvím uid a gid – pozor na bezpeˇcnost! ❖ NFS verze 3:

• bezestavové – nepoužívá operace otevírání a uzavírání souboru, ˚ každá operace musí nést veškeré potˇrebné argumenty,

• na straneˇ klienta se neužívá cache, • nemá podporu zamykání. ❖ NFS verze 4:

• stavové, • cache na straneˇ klienta, • podpora zamykání.


Spooling ❖ Spooling = simultaneous peripheral operations on-line. ˇ (typicky soubor) pro zaˇrízení (nejˇcasteji ˇ tiskárny), které ❖ spool = vyrovnávací pamet’ ˇ prokládané zpracování dat ruzných neumožnují ˚ procesu. ˚ ❖ Výstup je proveden do souboru, požadavek na jeho fyzické zpracování se zaˇradí do fronty, uživatelský proces muže ˚ pokraˇcovat a zpracování dat se provede, až neˇ pˇrijde ˇrada. ❖ V Unixu/Linuxu: /var/spool Spooling je v informatice technika sdílení vstupně-výstupních zařízení v multitaskingovém (víceúlohovém) operačním systému. V daném okamžiku může vstupně-výstupní zařízení provádět jen jednu úlohu, proto při současném přístupu více aplikací k zařízení jsou jejich požadavky řazeny do fronty. Pro realizaci fronty požadavků (úloh) je většinou využit souborový systém s přímým přístupem (disk, ramdisk). (z Wikipedie)






Správa procesu˚


❖ Správa procesu˚ (process management) zahrnuje:

• plánovaˇc (scheduler) – pˇrideluje ˇ CPU procesum, ˚ • správu pameti ˇ (memory management) – pˇrideluje ˇ ˇ pamet’, • podporu meziprocesové komunikace (IPC) – signály, RPC, ...


Proces ˇ ❖ Proces = bežící program. program - statická entita, která představuje předpis (návod) pro provedení určité činnosti ❖ Proces je v OS definován:

• identifikátorem (PID), • stavem jeho plánování, • programem, kterým je ˇrízen, • obsahem registru˚ (vˇcetneˇ EIP a ESP apod.), • daty a zásobníkem, • využitím dalších zdroju˚ OS a vazbou na další objekty OS (otevˇrené soubory, signály, PPID, UID, GID, ...).


ˇ Stavy plánování a jejich zmeny ˇ eˇ se rozlišují následující stavy procesu: ❖ Bežn ˚

přidělování zdrojů

např. přerušení časovače

přidělení procesoru


❖ Stavy plánování procesu v Unixu: stav Vytvoˇrený Pˇripravený ˇ Bežící Mátoha ˇ Cekající Odložený

význam ješteˇ neinicializovaný ˇ mohl by bežet, ale nemá CPU používá CPU po exit, rodiˇc ješteˇ nepˇrevzal exit-code cˇ eká na událost (napˇr. dokonˇcení read) "zmrazený"signálem SIGSTOP

❖ Pˇrechodový diagram stavu˚ plánování procesu v Unixu:

Suspended SIGCONT

SIGSTOP preempt yield

init

init

Runnable

CPU

event

exit

Running

Zombified

wait for event

Sleeping Správa souboru˚ – p.6/38

❖ V OS bývá proces reprezentován strukturou oznaˇcovanou jako PCB (Process Control Block) nebo též task control block cˇ i task struct apod. ❖ PCB zahrnuje:

• • • • • • •

identifikátor procesu, stav plánování procesu, obsah registru˚ (vˇcetneˇ EIP a ESP apod.), plánovací informace (priorita, ukazatele na plánovací fronty, ...), ˇ (tabulky stránek, ...), informace spojené se správou pameti informace spojené s úˇctováním (spotˇreba procesoru, ...), využití I/O zdroju˚ (otevˇrené soubory, používaná zaˇrízení., ...).

ˇ ˇ ˇ ❖ PCB muže ˚ být nekdy rozdelen do nekolika dílˇcích struktur.


ˇ ˇ v Unixu Cásti procesu v pameti ❖ Uživatelský adresový prostor (user address space) pˇrístupný procesu:

• • • •

kód (code area/text segment),

oblast kódu, kterým je proces řízen

data (inicializovaná/neinicializovaná data, heap), zásobník, ˇ soukromá data sdílených knihoven, sdílené knihovny, sdílená pamet’.

❖ Uživatelská oblast (user area) – ne vždy použita:

• Uložena zvlášt’ pro každý proces spolu s daty, kódem a zásobníkem v user address space pˇríslušného procesu (s nímž muže ˚ být odložena na disk).

• Je ale pˇrístupná pouze jádru. informace jádra o procesu • Obsahuje cˇ ást PCB, která je používána zejména za behu ˇ procesu: – PID, PPID, UID, EID, GID, EGID, – obsah registru, ˚ – deskriptory souboru, ˚ – obslužné funkce signálu, ˚ – úˇctování (spotˇrebovaný cˇ as CPU, ...), – pracovní a koˇrenový adresáˇr, – ...


❖ Záznam v tabulce procesu˚ (process table):

součást adresové oblasti jádra

• Uložen trvale v jádru. • Obsahuje zejména informace o procesu, které jsou duležité, ˇ ˚ i když proces nebeží: – PID, PPID, UID, EID, GID, EGID, – stav plánování, – událost, na kterou se cˇ eká, – plánovací informace (priorita, spotˇreba cˇ asu, ...), – cˇ ekající signály, – odkaz na tabulku pamet’ových ˇ regionu˚ procesu, – ... ˇ ˇ ❖ Tabulka pamet’ových regionu˚ procesu (per-process region table) – popis pamet’ových ˇ použitá pro data, kód, zásobník, sdílenou regionu˚ procesu (spojitá oblast virtuální pameti ˇ + pˇríslušné položky tabulky regionu, pamet’) ˚ tabulka stránek. tabulka stránek obsahuje informace o tom, které logické stránky paměti se mapují do kterých fyzických stránek paměti

ˇ ❖ Zásobník jádra využívaný za behu služeb jádra pro daný proces. používá se k ukládání aktivačních záznamů funkcí, které se volá jádro, ve chvíli, kdy proces zažádá o nějakou službu


Kontext procesu v Unixu ˇ ❖ Nekdy se též používá pojem kontext procesu = stav procesu. ❖ Rozlišujeme:

• uživatelský kontext (user-level context): kód, data, zásobník, sdílená data, • registrový kontext, obsah registrů • systémový kontext (system-level context): uživatelská oblast, položka tabulky ˇ procesu, ˚ tabulka pamet’ových regionu˚ procesu, ...


Systémová volání nad procesy v Unixu ❖ Systémová volání spojená s procesy v Unixu:

• • • •

fork, exe , exit, wait,

wait = čekání na dokončení potomka

kill, signal, getpid, getppid, ...

❖ Identifikátory spojené s procesy v UNIXu:

• • • • •

identifikace procesu PID, identifikace pˇredka PPID, reálný (skuteˇcný) uživatel, skupina uživatelu˚ UID, GID, kdo proces spustil efektivní uživatel, skupina uživatelu˚ EUID, EGID,

viz. předchozí přednáška, práva, která proces skutečně má (většinou shodné s UID a GID)

ˇ uložená EUID, uložená EGID – umožnuje doˇcasneˇ snížit efektivní práva a pak se ˇ k nim vrátit (pˇri zpetném nastavení se kontroluje, zda se proces vrací k reálnému ID nebo k uloženému EUID),

• v Linuxu navíc FSUID a FSGID (pro pˇrístup k souborum ˚ se zvýšenými privilegii), • skupina procesu˚ a sezení, do kterých proces patˇrí (PGID, SID). Správa souboru˚ – p.11/38

Vytváˇrení procesu˚ ❖ Vytváˇrení procesu˚ v UNIXu – služba fork: duplikuje proces, vytvoˇrí potomka. pid=fork(); if (pid==0) { // k´ od pro proces potomka // exec(....), exit(exitcode) } else if (pid==-1) { // k´ od pro rodiˇ ce, nastala chyba pˇ ri fork() // errno obsahuje bliˇ zs ˇı ´ informace } else { // k´ od pro rodiˇ ce, pid = PID potomka // pid2 = wait(&stav); } ❖ Vzniká vztah rodiˇc–potomek (parent–child) a hierarchie procesu. ˚


Hierarchie procesu˚ v Unixu ❖ Pˇredkem všech uživatelských procesu˚ je init s PID=1. ❖ Existují procesy jádra, jejichž pˇredkem init není:

• Naprosto prvním procesem (PID=0) bývá swapper (na Linuxu pouze idle, nevypisuje se).

swapper - vytvořen jádrem, provádí inicializační akce (např. spuštění init), po jejich skončení se zabývá swapováním (odstraňování pozastavených procesů z paměti, případně jejich vracení zpět)

❖ Procesy jádra (kernel processes/threads): jejich kód je souˇcástí jádra. ❖ Vztahy mezi init a procesy jádra nejsou pˇríliš významné a mohou se lišit. ˇ ❖ Pokud procesu skonˇcí pˇredek, jeho pˇredkem se automaticky stane init, který pozdeji pˇrevezme jeho návratový kód (proces nemuže ˚ definitivneˇ skonˇcit a jako zombie cˇ eká, dokud neodevzdá návratový kód). ❖ Výpis stromu procesu: ˚ napˇr. pstree.

začíná u init


ˇ Zmena programu – exe ❖ Skupina funkcí:

• exe ve – základní volání, • exe l, exe lp, exe le, exe v, exe vp. • exe l("/bin/ls", "ls", "-l", NULL); – argumenty odpovídají $0, $1, ...

(program který má být spuštěn, argumenty programu)

ˇ ❖ Nevrací se, pokud nedojde k chybe!

❖ Windows: CreatePro ess(...) – zahrnuje funkˇcnost fork i exe .


Start systému ❖ Posloupnost akcí pˇri startu systému: 1. BIOS.

základní testování a inicializace HW

ˇ ce, obvykle v nekolika ˇ ˇ zavadeˇ fázích (využívá mbr a pˇrípadneˇ 2. Naˇctení a spuštení další cˇ ásti disku). ˇ inicializaˇcní funkcí. 3. Naˇctení inicializaˇcních funkcí jádra a samotného jádra, spuštení 4. Inicializaˇcní funkce jádra vytvoˇrí proces swapper , ten vytvoˇrí pˇrípadné další procesy jádra a proces init. 5. init naˇcítá inicializaˇcní konfigurace a spouští další démony a procesy. • V urˇcitém okamžiku spustí gdm/kdm pro pˇrihlášení v grafickém režimu (z nej ˇ se pak spouští další procesy pro práci pod X Window). • Na konzolích spustí getty, který umožní zadat pˇrihlašovací jméno a zmení ˇ se ˇ se na shell, ze kterého se spouští další na login. Ten naˇcte heslo a zmení ˇ getty. procesy. Po ukonˇcení se na terminálu spustí opet • Proces init i nadále beží, ˇ pˇrebírá návratové kódy procesu, ˚ jejichž rodiˇc již skonˇcil a ˇreší pˇrípadnou reinicializaci systému cˇ i jeho cˇ ástí pˇri výskytu ruzných ˚ nakonfigurovaných událostí nebo na pˇrání uživatele.


ˇ Úrovneˇ behu ˇ – SYSV init run-levels: 0-6, s/S ❖ V UNIXu System V byl zaveden systém úrovní behu (0=halt, 1=single user, s/S=alternativní pˇrechod do single user, 6=reboot). zastavení systému

ˇ ˇ ❖ Zmena úrovneˇ behu: telinit N. ❖ Konfigurace:

2 - 5: záleží na konkr=tní distribuci, jedná se o víceuživatelským režim, někdy jsou všechny úrovně stejné, jindy např. víceuživatelský režim v grafickém rozhraní, víceuživatelský režim se sítí bez grafického rozhraní...

• Adresáˇre /etc/rcX.d obsahují odkazy na skripty spouštené ˇ pˇri vstupu do urˇcité ˇ Spouští se v poˇradí daném jejich jmény, skripty se jménem zaˇcínajícím K úrovne. na skripty s argumentem kill, skripty se jménem zaˇcínajícím S s parametrem start. odkazují v /etc/init.d

• Vlastní implementace v adresáˇri /etc/init.d, lze spouštet ˇ i ruˇcneˇ (napˇr. také ˇ s argumentem reload cˇ i restart – reinicializace ruzných ˚ služeb, napˇr. síte).

• Soubor /etc/inittab obsahuje hlavní konfiguraˇcní úroven: ˇ napˇr. implicitní úrovenˇ ˇ behu, odkaz na skript implementující výše uvedené chování, popis akcí pˇri mimoˇrádných situacích, inicializace konzolí apod. ❖ Existují ruzné ˚ nové implementace procesu init:

kompatibilní s SYSV

• Upstart: duraz ˚ na ˇrízení událostmi generovanými jím samým (napˇr. pˇri ukonˇcení ˇ ˇ nejaké jím spuštené úlohy) pˇríp. generovanými jádrem nebo dalšími procesy.

• Initng, systemd: spouští inicializaˇcní akce paralelneˇ na základeˇ jejich závislostí. Správa souboru˚ – p.16/38

Plánování procesu˚ ˇ a pˇrípadne, ˇ jak dlouho. ❖ Plánovaˇc rozhoduje, který proces pobeží ˇ eˇ bežícího ˇ ❖ Preemptivní plánování: ke zmen procesu muže ˚ dojít, aniž by tento jakkoliv pˇrepnutí kontextu napomohl, a to na základeˇ pˇrerušení (typicky od cˇ asovaˇce, ale muže ˚ se jednat i o jiné pˇrerušení). např. dokončení I/O operace ˇ eˇ bežícího ˇ ❖ Nepreemptivní plánování: ke zmen procesu muže ˚ dojít pouze tehdy, pokud ˇ to bežící proces umožní pˇredáním ˇrízení jádru (žádá o službu – typicky I/O operaci nebo se sám vzdává procesoru – volání yield). plánovač nemusí běžet nemusí běžet v režimu jádra (narozdíl od dispečera)

❖ Vlastní pˇrepnutí kontextu ˇreší na základeˇ rozhodnutí plánovaˇce tzv. dispeˇcer. ˇ ❖ Plánování muže ˚ být též ovlivneno systémem swapování rozhodujícím o tom, kterým ˇ ˇ aby mohly bežet, ˇ ˇ nových procesum ˚ je pˇridelena pamet’, pˇrípadneˇ systémem spouštení ˇ procesu˚ odkládat na vhodný okamžik. procesu, ˚ která muže ˚ spuštení

• V techto ˇ ˇ ˇ pˇrípadech nekdy hovoˇríme o stˇrednedobém a dlouhodobém plánování. střednědobé plánování - rozhodování o procesech, které budou odstraněny z paměti, případně vráceny zpět (swapování) dlouhodobé plánování - rozhodování o tom zda, procesy, které mají být spuštěny, budou spouštěny ihned nebo se zpožděním


Pˇrepnutí procesu (kontextu) ˇ ho procesu B – (1) úschova stavu ❖ Dispeˇcer odebere procesor procesu A a pˇridelí oprava - pouze části stavu, procesu A do PCB, (2) obnova stavu procesu B z PCB:

neuchovává se celý stav viz

❖ Pˇrepnutí trvá stovky až tisíce instrukcí. ❖ Poznámka: Ne vše se musí ukládat/obnovovat: napˇr. se uloží jen ukazatel na tabulku ˇ procesu muže stránek, tabulka stránek a vlastní obsah pameti ˚ zustat. ˚ Správa souboru˚ – p.18/38

Klasické plánovací algoritmy ❖ Klasické plánovací algoritmy uvedené níže se používají pˇrímo, pˇrípadneˇ v ruzných ˚ modifikacích a/nebo kombinacích ❖ FCFS (First Come, First Served):

• Procesy cˇ ekají na pˇridelení ˇ ˇ procesoru ve FIFO fronte. • Pˇri vzniku procesu, jeho uvolnení ˇ z cˇ ekání nebo vzdá-li se proces procesoru, je tento proces zaˇrazen na konec fronty.

• Procesor se pˇrideluje ˇ procesu na zaˇcátku fronty. • Algoritmus je nepreemptivní a k pˇrepnutí kontextu dojde pouze tehdy, pokud se ˇ bežící proces vzdá procesoru (I/O, konec, dobrovolné vzdání se procesoru – volání yield). jednoduchá implementace ❖ Round-robin – preemptivní obdoba FCFS:

• Pracuje podobneˇ jako FCFS, navíc má ale každý proces pˇrideleno ˇ cˇ asové kvantum, po jehož vypršení je mu odebrán procesor a proces je zaˇrazen na konec fronty pˇripravených procesu. ˚ Správa souboru˚ – p.19/38

Klasické plánovací algoritmy ❖ SJF (Shortest Job First):

• Pˇrideluje ˇ ˇ procesor procesu, který požaduje nejkratší dobu pro své další provádení na procesoru bez vstup/výstupních operací (tzv. CPU burst).

• Nepreemptivní algoritmus, který nepˇrerušuje proces pˇred dokonˇcením jeho aktuální výpoˇcetní fáze.

• Minimalizuje prum ˇ ˚ ernou dobu cˇ ekání, zvyšuje propustnost systému. • Nutno znát dopˇredu dobu behu ˇ procesu˚ na procesoru nebo mít možnost tuto rozumneˇ odhadnout na základeˇ pˇredchozího chování.

• Používá se ve specializovaných (napˇr. dávkových) systémech. dá se předpokládat délka trvání • Hrozí stárnutí (nekdy ˇ ˇ – starvation): též hladovení – Stárnutím pˇri pˇridelování ˇ zdroju˚ (procesor, zámek, ...) rozumíme obecneˇ ˇ ˇ cˇ eká bez záruky, že jej situaci, kdy nekterý proces, který o zdroj žádá, na nej ˇ nekdy získá. – V pˇrípadeˇ SJF hrozí hladovení ˇ procesu˚ cˇ ekajících na procesor a majících dlouhé výpoˇcetní fáze, které mohou být neustále pˇredbíhány kratšími výpoˇcty. ❖ SRT (Shortest Remaining Time): obdoba SJF s preempcí pˇri vzniku cˇ i uvolnení ˇ procesu.

• Procesor pˇriˇrazen procesu, kterému chybí nejkratší cˇ as k dokonˇcení jeho aktuální výpoˇcetní fáze.


Klasické plánovací algoritmy ˇ ❖ Víceúrovnové plánování:

• Procesy jsou rozdeleny ˇ do ruzných ˚ skupin (typicky podle priority). • V rámci každé skupiny muže ˚ být použit jiný dílˇcí plánovací algoritmus (napˇr. FCFS cˇ i round-robin).

• Je použit také algoritmus, který urˇcuje, ze které skupiny bude vybrán proces, který ˇ má aktuálneˇ bežet (ˇcasto jednoduše na základeˇ priority skupin).

• Muže ˇ nekterých ˇ ˚ hrozit hladovení (obvykle nízko prioritních) procesu˚ cˇ ekajících na procesor. ˇ ˇ ❖ Víceúrovnové plánování se zpetnou vazbou:

multilevel feedback scheduling

• Víceúrovnové ˇ ˇ plánování se skupinami procesu˚ rozdelenými dle priorit. • Noveˇ vznikající proces je zaˇrazen do fronty s nejvyšší prioritou, postupneˇ klesá do nižších prioritních front, nakonec plánován round-robin na nejnižší úrovni.

• Používají se varianty, kdy je proces zaˇrazen do poˇcáteˇcní fronty na základeˇ své statické priority. Následneˇ se muže ˚ jeho dynamická priorita snižovat, spotˇrebovává-li mnoho procesorového cˇ asu, nebo naopak zvyšovat, pokud hodneˇ cˇ eká na vstup/výstupních operacích. – Cílem je zajistit rychlou reakci interaktivních procesu. ˚ Správa souboru˚ – p.21/38

Plánovaˇc v Linuxu verze 2.6

v tomto případě se používá preemptivní varianta, pokud se proces s vyšší prioritou probudí z čekání, dostává se na řadu

ˇ ˇ ❖ Víceúrovnové prioritní plánovaní se 100 statickými prioritními úrovnemi:

• Priority 1–99 pro procesy reálného cˇ asu plánované FCFS nebo round-robin. • Priorita 0 pro bežné ˇ procesy plánované tzv. O(1) nebo CFS plánovaˇcem. • V rámci úrovneˇ 0 se dále používají dynamické priority v rozmezí -20 (nejvyšší) až 19 (nejnižší): – Vychází z uživatelem nastavené statické základny dynamické priority (tzv. nice) – viz pˇríkazy ni e a reni e. – Snižuje se pˇri vysoké spotˇrebeˇ CPU a zvyšuje pˇri cˇ ekání na I/O.

• Statickou prioritní úrovenˇ a typ plánování mohou ovlivnit procesy s patˇriˇcnými právy: viz funkce s hed_sets heduler.


O(1) plánovaˇc

plánuje v rámci zanořených úrovní na úrovní priority 0

❖ O(1) plánovaˇc – starší jádra verze 2.6:

• Víceúrovnové ˇ ˇ plánovaní se zpetnou vazbou s prioritami vycházejícími ze statické základny modifikované na základeˇ spotˇreby CPU/ˇcekání na I/O. ˇ • Casová ˇ ovlivnena ˇ kvanta pro beh dynamickou prioritou. • Používá dveˇ sady plánovacích front, aby se vyhnul stárnutí: aktivní a expirovanou. ˇ • Casové ˇ ˇ kvantum procesu rozdeleno na nekolik cˇ ástí, v rámci kterých se realizuje round-robin na dané úrovni. Pak se proces pˇreˇradí do expirované sady front.

• Pokud se aktivní fronty vyˇcerpají, dochází k zámen ˇ eˇ aktivních a expirovaných front. • Interaktivní procesy mohou opakovaneˇ zustat ˚ v aktivní sadeˇ front, používá se ale explicitní kontrola na stárnutí procesu˚ v expirované sadeˇ front. každý proces na dané úrovni má přiřazen určitý čas běhu, ten je rozdělen do několika částí, vždy když část skončí, proces se přesune na konec aktivní fronty. po vypršení celého časového limitu pro jeden proces se přesune do expirované fronty. ve chvíli, kdy jsou na dané úrovni všechny procesy v expirované frontě, plánovač se přesune na další úroveň s nižší prioritou. když projde všechny úrovně, prohodí obě plánovací fronty


Completely Fair Scheduler ˇ jádra verze 2.6: ❖ CFS (Completely Fair Scheduler) – novejší

• Odstranuje ˇ složitost implementace O(1) plánovaˇce a jeho heuristik pro detekci ˇ interaktivity, které navíc v nekterých pˇrípadech selhávají.

• Snaží se explicitneˇ každému procesu poskytnout odpovídající procento strojového cˇ asu.

• Vede si u každého procesu údaj o tom, kolik (virtuálního) procesorového cˇ asu strávil.

• Navíc si vede údaj o minimálním stráveném procesorovém cˇ ase, který dává noveˇ pˇripraveným procesum. ˚

• Procesy udržuje ve vyhledávací stromové struktuˇre (red-black strom) podle využitého procesorového cˇ asu.

• Vybírá jednoduše proces s nejmenším stráveným cˇ asem. • Procesy nechává bežet ˇ po dobu cˇ asového kvanta spoˇcteného na základeˇ priorit. • Obsahuje podporu pro skupinové plánování: Muže ˇ ˚ rozdelovat cˇ as spravedliveˇ pro ˇ procesy spuštené z ruzných ˚ terminálu˚ (a tedy napˇr. patˇrící ruzným ˚ uživatelum ˚ nebo u jednoho uživatele sloužící ruzným ˚ úˇcelum). ˚ Správa souboru˚ – p.24/38

ˇ Plánování ve Windows NT a novejších ˇ ˇ ❖ Víceúrovnové prioritní plánovaní se zpetnou vazbou na základeˇ interaktivity:

• 32 prioritních úrovní: 0 – nulování volných stránek, 1 – 15 bežné ˇ procesy, 16 – 31 procesy reálného cˇ asu.

• Základní priorita je dána nastavenou kombinací plánovací tˇrídy a plánovací úrovneˇ v rámci tˇrídy.

• Systém muže ˇ ˚ základní prioritu bežných procesu˚ dynamicky zvyšovat cˇ i snižovat: – Zvyšuje prioritu procesu˚ spojených s oknem, které se dostane na popˇredí. – Zvyšuje prioritu procesu˚ spojených s oknem, do kterého pˇrichází vstupní zprávy (myš, cˇ asovaˇc, klávesnice, ...). – Zvyšuje prioritu procesu, ˇ z cˇ ekání (napˇr. na I/O operaci). ˚ které jsou uvolneny – Zvýšená priorita se snižuje po každém vyˇcerpání kvanta o jednu úrovenˇ až do dosažení základní priority.


Inverze priorit ❖ Problém inverze priorit:

• Nízko prioritní proces si naalokuje nejaký ˇ zdroj, více prioritní procesy ho pˇredbíhají a nemuže ˚ dokonˇcit práci s tímto zdrojem. ˇ • Casem tento zdroj mohou potˇrebovat více prioritní procesy, jsou nutneˇ zablokovány a musí cˇ ekat na nízko prioritní proces.

• Pokud v systému jsou v tomto okamžiku stˇredneˇ prioritní procesy, které nepotˇrebují ˇ a budou dále pˇredbíhat nízko prioritní proces. daný zdroj, pak pobeží

• Tímto zpusobem ˚ uvedené stˇredneˇ a nízko prioritní procesy získávají efektivneˇ vyšší prioritu. ˇ ❖ Inverze priorit nemusí, ale muže, ˚ vadit, zejména pokud jsou blokovány nejaké kritické procesy reálného cˇ asu (ovládání hardware apod.). ❖ Inverze priorit muže ˚ zvyšovat odezvu systému.


Inverze priorit a další komplikace plánování ❖ Možnosti ˇrešení inverze priorit:

• Priority ceiling: procesy v kritické sekci získávají nejvyšší prioritu. • Priority inheritance: proces v kritické sekci, který blokuje výše prioritní proces, dedí ˇ ˇ jeho priority (po dobu behu v kritické sekci).

• Zákaz pˇrerušení po dobu behu ˇ v kritické sekci: v podstateˇ proces získává vyšší prioritu než všichni ostatní. ❖ Další výraznou komplikaci plánování pˇredstavují:

• víceprocesorové systémy – nutnost vyvažovat výkon, respektovat obsah cache procesoru, ˚

• hard real-time systémy – nutnost zajistit garantovanou odezvu nekterých ˇ akcí. soft real-time - doporučení, že by se nějaká akce měla odehrát do určitého času hard real-time - daná akce se MUSÍ odehrát do určitého času Linux i Windows jsou soft real-time systémy


Vlákna, úlohy, skupiny procesu˚ ❖ Vlákno (thread):

• • • • •

“odlehˇcený proces” (LWP – lightweight process), ˇ v rámci jednoho klasického procesu muže ˚ bežet více vláken, vlastní obsah registru˚ (vˇcetneˇ EIP a ESP) a zásobník, sdílí kód, data a další zdroje (otevˇrené soubory, signály), ˇ výhody: rychlejší spouštení, pˇrepínání.


Úlohy, skupiny procesu, ˚ sezení ˇ ❖ Úloha (job) v bashi (a podobných shellech): skupina paralelneˇ bežících procesu˚ ˇ spuštených jedním pˇríkazem a propojených do kolony (pipeline). ❖ Skupina procesu˚ (process group) v UNIXu:

• Množina procesu, ˚ které je možno poslat signál jako jedné jednotce. Pˇredek také muže ˚ cˇ ekat na dokonˇcení potomka z urˇcité skupiny (waitpid).

• Každý proces je v jedné skupineˇ procesu, ˚ po vytvoˇrení je to skupina jeho pˇredka. • Skupina muže ˚ mít tzv. vedoucího – její první proces, pokud tento neskonˇcí (skupina je identifikována cˇ íslem procesu svého vedoucího).

• Zjišt’ování a zmena ˇ skupiny: getpgid, setpgid. ❖ Sezení (session) v UNIXu:

• • • • •

Každá skupina procesu˚ je v jednom sezení. Sezení muže ˚ mít vedoucího. Vytvoˇrení nového sezení: setsid. Sezení muže ˚ mít ˇrídící terminál (/dev/tty). Jedna skupina sezení je tzv. na popˇredí (ˇcte z terminálu), ostatní jsou na pozadí. O ukonˇcení terminálu je signálem SIGHUP informován vedoucí sezení (typicky shell), který ho dále ˇreší (všem, na které nebyl užit nohup/disown, SIGHUP, pozastaveným navíc SIGCONT). Správa souboru˚ – p.29/38

Komunikace procesu˚ ❖ IPC = Inter-Process Communication:

• • • • • • •

signály (kill, signal, ...) roury (pipe, mknod p, ...) zprávy (msgget, msgsnd, msgre v, msg tl, ...) ˇ (shmget, shmat, ...) sdílená pamet’ sockety (so ket, ...) RPC = Remote Procedure Call ...


Signály ❖ Signál (v základní verzi) je cˇ íslo (int) zaslané procesu prostˇrednictvím pro to zvlášteˇ definovaného rozhraní. Signály jsou generovány

• pˇri chybách (napˇr. aritmetická chyba, chyba práce s pametí, ˇ ...), • externích událostech (vypršení cˇ asovaˇce, dostupnost I/O, ...), • na žádost procesu – IPC (kill, ...). ❖ Signály cˇ asto vznikají asynchronneˇ k cˇ innosti programu – není tedy možné ˇ et, ˇ kdy daný signál bude doruˇcen. jednoznaˇcneˇ pˇredpoved ❖ Nutno peˇcliveˇ zvažovat obsluhu, jinak mohou vzniknout “záhadné”, zˇrídka se objevující a velice špatneˇ laditelné chyby (mj. také motivace pro formální verifikaci).


ˇ eˇ používané signály patˇrí: ❖ Mezi bežn

• • • • • • • • • • •

SIGHUP – odpojení, ukonˇcení terminálu SIGINT – pˇrerušení z klávesnice (Ctrl-C) SIGKILL – tvrdé ukonˇcení ˇ SIGSEGV, SIGBUS – chybný odkaz do pameti

SIGPIPE – zápis do roury bez cˇ tenáˇre SIGALRM – signál od cˇ asovaˇce (alarm) ˇ SIGTERM – mekké ukonˇcení

SIGUSR1, SIGUSR2 – uživatelské signály SIGCHLD – pozastaven nebo ukonˇcen potomek SIGCONT – pokraˇcuj, jsi-li pozastaven ˇ SIGSTOP, SIGTSTP – tvrdé/mekké pozastavení

❖ Další signály – viz man 7 signal.


Pˇredefinování obsluhy signálu˚ ❖ Mezi implicitní (pˇrednastavené) reakce na signál patˇrí: ukonˇcení procesu (pˇríp. s generováním core dump), ignorování a pozastavení. ❖ Lze pˇredefinovat obsluhu všech signálu˚ mimo SIGKILL a SIGSTOP. SIGCONT lze pˇredefinovat, ale vždy dojde k odblokování procesu. ❖ K pˇredefinování obsluhy signálu˚ slouží funkce:

• sighandler_t signal(int signum, sighandler_t handler); kde

typedef void (*sighandler_t)(int); – handler je ukazatel na obslužnou funkci, pˇríp. SIG_DFL cˇ i SIG_IGN.

• int siga tion(int signum, onst stru t siga tion *a t, stru t

siga tion *olda t); – komplexnejší ˇ a pˇrenosné nastavení obsluhy, – nastavení blokování behem ˇ obsluhy (jinak stávající nastavení + obsluhovaný signál), – nastavení režimu obsluhy (automatické obnovení implicitní obsluhy, ...), – nastavení obsluhy s pˇríjmem dodateˇcných informací spolu se signálem. Správa souboru˚ – p.33/38

Blokování signálu˚ ❖ K nastavení masky blokovaných signálu˚ lze užít:

• int sigpro mask(int how, onst sigset_t *set, sigset_t *oldset); • how je SIG_BLOCK, SIG_UNBLOCK cˇ i SIG_SETMASK. (jakým způsobem modifikovat stávající blokování, které signály chceme nastavit, staré nastavení blokování)

❖ K sestavení masky signálu˚ slouží sigemptyset, sigfillset, sigaddset, sigdelset, sigismember. ❖ Nelze blokovat: SIGKILL, SIGSTOP, SIGCONT. ˇ do potomku. ˇ se také obslužné funkce signálu, ❖ Nastavení blokování se dedí ˚ Dedí ˚ pˇri použití exe se ovšem nastaví implicitní obslužné funkce. ˇ cˇ ekajících signálu: ❖ Zjištení ˚ int sigpending(sigset_t *set); ˇ ˇ ❖ Upozornení: Pokud je nejaký zablokovaný signál pˇrijat vícekrát, zapamatuje se jen jedna instance! (Neplatí pro tzv. real-time signály.)


Zasílání signálu˚ ˇ ❖ int kill(pid_t pid, int sig); umožnuje zasílat signály

• urˇcitému procesu, kladné číslo • skupineˇ procesu, ˚ záporné číslo • všem procesum ˚ (mimo init, pokud nemá pro pˇríslušný signál definovánu obsluhu). ❖ Aby proces mohl zaslat signál jinému procesu musí odpovídat jeho UID nebo EUID ˚ v UID nebo saved set-user-ID cílového procesu (SIGCONT lze zasílat všem procesum sezení – session), pˇrípadneˇ se musí jednat o privilegovaného odesílatele (napˇr. EUID=0, nebo kapabilita CAP_KILL). ❖ Poznámka: sigqueue – zasílání signálu spolu s dalšími daty.


ˇ Cekání na signál ❖ Jednoduché cˇ ekání: int pause(void);

• Nelze spolehliveˇ pˇrepínat mezi signály, které mají být blokovány po dobu, kdy se cˇ eká, a mimo dobu, kdy se cˇ eká. ❖ Zabezpeˇcené cˇ ekání: int sigsuspend( onst sigset_t *mask);

• Lze spolehliveˇ pˇrepínat mezi signály blokovanými mimo a po dobu cˇ ekání. • mask jsou blokovány po dobu cˇ ekání, po ukonˇcení se nastaví puvodní ˚ blokování.


ˇ ❖ Pˇríklad – proces spustí potomka a poˇcká na signál od nej: #include #include #include #include

<signal.h> <stdio.h> <sys/types.h>

/* When a SIGUSR1 signal arrives, set this variable. */ volatile sig_atomic_t usr_interrupt = 0; sig_atomic_t - nelze přijmout další signál během nastavování hodnoty proměnné

void synch_signal (int sig) { usr_interrupt = 1; } /* The child process executes this function. */ void child_function (void) { ... /* Let the parent know you’re here. */ kill (getppid (), SIGUSR1); pošle rodiči signál SIGUSR1 ... }


❖ Pokraˇcování pˇríkladu – pozor na zamezení ztráty signálu mezi testem a cˇ ekáním: int main (void) { struct sigaction usr_action; sigset_t block_mask, old_mask; pid_t pid; /* Establish the signal handler. */ sigfillset (&block_mask); jsou zablokovány všechny signály usr_action.sa_handler = synch_signal; usr_action.sa_mask = block_mask; usr_action.sa_flags = 0; sigaction (SIGUSR1, &usr_action, NULL); "instalace" obsluhy, signál je obsloužen strukturou usr_action

/* Create the child process. */ if ((pid = fork()) == 0) child_function (); /* Does not return. */ else if (pid==-1) { /* A problem with fork - exit. */ } /* Wait for the child to send a signal */ sigemptyset (&block_mask); sigaddset (&block_mask, SIGUSR1); maska signálů, které budou blokovány před vlastním čekáním sigprocmask (SIG_BLOCK, &block_mask, &old_mask); nyní je SIGUSR1 blokován while (!usr_interrupt) dokud nepřišel signál, čekáme na něj (pozastavíme proces) sigsuspend (&old_mask); sigprocmask (SIG_UNBLOCK, &block_mask, NULL); ... Správa souboru˚ – p.38/38

Synchronizace procesu˚ ´ s Vojnar Tomaˇ

[email protected]

Vysoke´ uˇcen´ı technicke´ v Brneˇ Fakulta informaˇcn´ıch technologi´ı ˇ Boˇzetechova 2, 612 66 BRNO 11. dubna 2011

´ Operaˇcn´ı systemy

Synchronizace procesu˚

ˇ ˇ – Soucasn y´ pˇr´ıstup nekolika paraleln´ıch procesu˚ ke sd´ılenym ´ zdrojum ˚ (sd´ılena´ data, sd´ılena´ I/O ´ k nekonzistenc´ım zpracovavan´ ´ zaˇr´ızen´ı) muˇ ych dat. ˚ ze vest

ˇ ´ – Casov eˇ zavisl a´ chyba (neboli race condition): chyba vznikaj´ıc´ı pˇri pˇr´ıstupu ke sd´ıleným zdrojum ˚ ´ ´ en´ ˇ ı jednotlivých paraleln´ıch výpoˇctu˚ v systemu, ´ kvuli poˇrad´ı provad tj. kvuli ˚ ruzn ˚ emu ˚ jejich ruzn ˚ e´ relativn´ı rychlosti.

ˇ ı konzistence dat vyˇzaduje mechanismy synchronizace procesu˚ zajiˇst’uj´ıc´ı spravn ´ e´ poˇrad´ı – Zajiˇsten´ ´ en´ ˇ ı spolupracuj´ıc´ıch procesu. provad ˚


Synchronizace 1

ˇ ˇ ´ bufferu (napˇr. – Pˇr´ıklad: Mejme promennou N, ktera´ obsahuje poˇcet poloˇzek ve sd´ılenem ´ uvaˇzujme proveden´ı nasleduj´ ıc´ıch operac´ı:

konzument: N--

||

producent: N++

´ ı kontextu muˇ ´ – Na strojove´ urovni a pˇri pˇrep´ınan´ ıc´ımu: ´ ˚ ze doj´ıt k nasleduj´

producent: producent: konzument: konzument: producent: konzument:

N==5) a

race condition - chyba záleží na pořadí prováděn příkazů

register1 = N (register1 == 5) register1 = register1 + 1 (register1 == 6) register2 = N (register2 == 5) register2 = register2 - 1 (register2 == 4) N = register1 (N == 6) N = register2 (N == 4 !!!!!)

´ e´ hodnoty 5! – Výsledkem muˇ ˚ ze být 4, 5, nebo 6 nam´ısto jedine´ spravn


Synchronizace 2

Kriticke´ sekce ´ ˇ z´ıc´ıch o pˇr´ıstup ke sd´ıleným zdrojum. – Mame n procesu˚ souteˇ Kaˇzdý proces je ˇr´ızen urˇcitým programem. ˚

na p. dv a pr oc es y m an ip ul ují sx zá ro ve

– Sd´ılenymi ´ kritickymi ´ sekcemi daných procesu˚ rozum´ıme ty useky jejich ˇr´ıd´ıc´ıch programu˚ ´ ´ en´ ˇ ı jedn´ım procesem vyluˇcuje souˇcasne´ provad ´ en´ ˇ ı pˇristupuj´ıc´ı ke sd´ıleným zdrojum, jejichˇz provad ˚ ´ ˇ libovolneho z techto usek u˚ ostatn´ımi procesy. ´ ´ ´ – Je moˇzný výskyt v´ıce sad sd´ılených kritických sekc´ı, ktere´ navzajem sd´ılene´ nejsou (napˇr. pˇri praci ˇ ymi). s ruzn´ ˚ ymi sd´ılenými promenn´ ˇ s´ım pˇr´ıpadem pak je situace, kdy sd´ılene´ kriticke´ sekce nejsou vzajemn ´ – Obecnejˇ eˇ zcela vylouˇceny, ´ et ˇ nejvýsˇ e urˇcitý poˇcet. ale muˇ ˚ ze se jich souˇcasneˇ provad ´ kriticke´ sekce – pro sd´ılene´ kriticke´ sekce je zapotˇreb´ı zajistit: – Problem ´ ´ e´ vylouˇcen´ı (mutual exclusion): nanejvýsˇ jeden (obecneˇ k) proces(u) • Vzajemn ˚ je v danem okamˇziku v KS.

• Dostupnost KS: ´ proces nemuˇ – Je-li KS volna, ˚ ze neomezeneˇ cˇ ekat na pˇr´ıstup do n´ı. – Je zapotˇreb´ı se vyhnout: ´ ∗ uvaznut´ ı, ´ ıa ∗ blokovan´ ´ ∗ starnut´ ı. ´ Operaˇcn´ı systemy

Synchronizace 3

´ ´ ı, starnut´ ´ Uvaznut´ ı, blokovan´ ı

proces 1 vlastní zdroj A, eká na zdroj B, proces 2 vlastní zdroj B, eká na zdroj A, zacyklení , nedokají se

´ – Uvaznut´ ım (deadlockem) pˇri pˇr´ıstupu ke sd´ıleným zdrojum ˚ rozum´ıme situaci, kdy kaˇzdý ze skupiny ˇ ı zdroje s výluˇcným (omezeným) pˇr´ıstupem vlastnen´ ˇ ym procesu˚ je pozastaven a cˇ eka´ na uvolnen´ ˇ ym procesem z dane´ skupiny. [[ Obecnejˇ ˇ s´ı pojet´ı uvaznut´ ´ ´ ]] nejak´ ı – viz dale. ´ a´ ´ ım (blocking) pˇri pˇr´ıstupu do kriticke´ sekce rozum´ıme situaci, kdy proces, jenˇz zˇ ad – Blokovan´ ´ y proces se nenachaz´ ´ ı o vstup do kriticke´ sekce, mus´ı cˇ ekat, pˇrestoˇze je kriticka´ sekce volna´ (tj. zˇ adn´ ´ e´ sd´ılene´ kriticke´ sekci) a ani o zˇ adnou ´ v n´ı ani v zˇ adn z dane´ mnoˇziny sd´ılených kritických sekc´ı ´ y dalˇs´ı proces neˇzad ´ a. ´ zˇ adn´ ´ z hladoven´ ˇ ım, starvation) – rozum´ıme situaci, kdy proces cˇ eka´ na podm´ınku, ktera´ ´ – Starnut´ ım (teˇ ˇ ı vstupu do kriticke´ sekce. nemus´ı nastat. V pˇr´ıpadeˇ kriticke´ sekce je touto podm´ınkou umoˇznen´ ´ ´ ı zvlaˇ ´ stn´ımi pˇr´ıpady starnut´ ´ – Pˇri striktn´ı interprepatci jsou uvaznut´ ı i blokovan´ ı.

´ ˇ z´ı, ale ´ stn´ım pˇr´ıpadem starnut´ ı je take´ tzv. livelock, kdy vˇsechny procesy z urˇcite´ mnoˇziny beˇ – Zvlaˇ ´ ej´ ˇ ı jen omezený usek ´ ´ opakovaneˇ zˇ adaj´ ´ ı o urˇcitý sd´ılený zdroj, který vlastn´ı provad kodu, ve kterem ´ ˇ ´ eˇ zˇ ad ´ a. ´ nekter´ y z procesu˚ dane´ skupiny, pˇriˇcemˇz ten ho nemuˇ ˚ ze uvolnit, aniˇz by z´ıskal zdroj, o který aktualn ˇ – data race: dva pˇr´ıstupy k teˇ ´ ze promenn ˇ e´ ze dvou procesu˚ bez synchronizace, alesponˇ [[ Doplnek ´ ´ stn´ı pˇr´ıpad chybej´ ˇ ıc´ıho vzajemn ´ ´ jeden pˇr´ıstup je pˇritom pro zapis (zvlaˇ eho vylouˇcen´ı). ]]


Synchronizace 4

Petersonuv ˚ algoritmus

´ – Moˇzne´ ˇreˇsen´ı problemu KS pro dva procesy:

bool flag[2] = { false, false }; int turn = 0;

// shared array // shared variable

// process i (i==0 or i==1): do { //... flag[i] = true; turn = 1-i;

přihlásím svůj zájem o KS a nastavím druhému procesu prioritu pro vstup do KS

while (flag[1-i] && turn != i) ; // critical section flag[i] = false; // remainder section } while (1);

// busy waiting

ˇ ı Petersonova algoritmu pro n procesu˚ a dalˇs´ı algoritmy. – Existuje zobecnen´ ´ Operaˇcn´ı systemy

Synchronizace 5

Bakery algoritmus L. Lamporta ´ – Vzajemn e´ vylouˇcen´ı pro n procesu: ˚ ˇ s´ı neˇz cˇ ´ısla pˇridelen ˇ a´ jiˇz • Pˇred vstupem do KS proces z´ıska´ “l´ıstek”, jehoˇz cˇ ´ıselna´ hodnota je vetˇ cˇ ekaj´ıc´ım procesum. ˚

• Drˇzitel nejmenˇs´ıho cˇ ´ısla a s nejmenˇs´ım PID muˇ ˚ ze vstoupit do KS (v´ıce procesu˚ muˇ ˚ ze l´ıstek z´ıskat ˇ souˇcasne!). ˇ ısla pˇridelovan ˇ • C´ a´ procesum ˚ mohou teoreticky neomezeneˇ rust. ˚ pí zn ak to ho , že pr oc es zí sk áv á lís te k

bool flag[N] = {false}; // shared array int ticket[N] = { 0 }; // shared array int j, max=0; // local (non-shared) variables

ho dn ot a pí st up ov éh o lís tk u, 0 = ne m á zá je m


projde všechny lístky a spoítá maximální hodnotu, kterou použije pro svj lístek

// process i while (1) { // ... before the critical section flag[i] = true; // finding the max ticket for (j = 0; j < N; j++) { if (ticket[j] > max) max = ticket[j]; } ticket[i] = max + 1; // take a new ticket

Synchronizace 6

ˇ an´ ´ ı Bakery algoritmus – pokracov

ko ne c ge ne rov ání sv éh o pís tup ov éh o líst ku

flag[i] = false; // give priority to processes with smaller tickets // (or equal tickets and smaller PID) for (j = 0; j < N; j++) { while (flag[j]); if (ticket[j] > 0 && (ticket[j] < ticket[i] || (ticket[j] == ticket[i] && j 0); } } // the critical section ticket[i] = 0; // the remainder section

proces i iteruje pes procesy, pokud si proces poítá lístek, eká, pokud má proces zájem o KS, zjistí hodnotu jeho lístku, pokud má stejnou hodnotu, oví jeho PID, až proces projde pes všechny ostatní, má jistotu, že je na ad

} – Pozor na moˇznost pˇreteˇcen´ı u cˇ ´ısel l´ıstku! ˚


Synchronizace 7

Vyuˇzit´ı hardware pro synchronizaci ˇ neˇz specializovane´ algoritmy bez HW podpory. – Pouˇz´ıva´ se cˇ asteji

– Atomicka´ instrukce typu TestAndSet (napˇr.

LOCK BTS):

bool TestAndSet(bool &target) { bool rv = target; zamkne KS a vrátí původní stav KS target = true; return rv; } – Vyuˇzit´ı TestAndSet pro synchronizaci na KS:

bool lock = false; // ... while (TestAndSet(lock)) ; // critical section lock = false; // ...


Synchronizace 8

– Atomicka´ instrukce typu Swap (napˇr.

LOCK XCHG):

void Swap(bool &a, bool &b) { bool temp = a; zamění obsah dvou míst v paměti a = b; b = temp; } – Vyuˇzit´ı Swap pro synchronizaci na KS:

// ... bool key = true; while (key == true) Swap(lock,key); // critical section lock = false; // ...


sdí len á pro mn ná

bool lock = false;

dokud bude KS zamčená, key bude true (záměna true za true), proces tedy bude čekat na odemčení

Synchronizace 9

´ ´ – Uvedena´ ˇreˇsen´ı vzajemn eho vylouˇcen´ı zaloˇzena´ na specializovaných instrukc´ıch zahrnuj´ı moˇznost ˇ an´ ´ ı, proto se take´ tato ˇreˇsen´ı cˇ asto oznaˇcuj´ı jako tzv. spinlock. aktivn´ıho cek while(...)

aby nemohlo dojít k přepnutí kontextu

´ ych, – Lze uˇz´ıt na kratk ´ neblokuj´ıc´ıch kritickych ´ sekc´ıch bez preempce (alesponˇ bez preempce na ´ procesoru: proto býva´ vlastn´ı pouˇzit´ı atomicke´ instrukce uzavˇreno mezi zakaz/povolen´ ´ pouˇzitem ı pˇreruˇsen´ı). ´ ˇ ’oveho ´ ˇ ı konzistence cache – Opakovaný zapis pamet m´ısta je problematický z hlediska zajiˇsten´ ´ ˇ zuje sd´ılenou pamet ˇ ’ovou sbernici) ˇ v multiprocesorových systemech (zateˇ – ˇreˇsen´ım je pˇri aktivn´ım ˇ an´ ´ ı pouze c´ ˇ ıst: cek

// ... while (TestAndSet(lock)) while (lock) ; // ... ´ ˇ ı moˇznost starnut´ ´ – Uvedena´ ˇreˇsen´ı nevylucuj´ ı: býva´ tolerovano, ale existuj´ı ˇreˇsen´ı s frontou ´ odstranuj´ ˇ ı. cˇ ekaj´ıc´ıch procesu, ˚ ktere´ tento problem


Synchronizace 10

Semafory ´ ´ ı. – Synchronizaˇcn´ı nastroj nevyˇzaduj´ıc´ı aktivn´ı cˇ ekan´ ˇ ˇ zakladn´ ´ – Jedna´ se typicky o celoˇc´ıselnou promennou pˇr´ıstupnou dvemi ımi atomickými operacemi:

• lock (take´ P cˇ i down), • unlock (take´ V cˇ i up) ´ muˇ ˇ ych operac´ı, napˇr. (dale ˚ ze být k dispozici napˇr. inicializace apod., pˇr´ıpadneˇ ruzn ˚ e´ varianty zm´ınen´ ´ ı atp.). neblokuj´ıc´ı zamknut´ı, pokus o zamknut´ı s horn´ı mez´ı na dobu cˇ ekan´

´ ˇ e´ S odpov´ıdaj´ıc´ı semaforu: celoˇc´ıselne´ promenn – Semantika ˇ ych semaforu, • S > 0 – odemknuto (hodnota S > 1 se uˇz´ıva´ u zobecnen´ ˚ jeˇz mohou propustit do kriticke´ sekce v´ıce neˇz jeden proces), ´ a´ poˇcet procesu˚ cˇ ekaj´ıc´ıch na semaforu). • S ≤ 0 – uzamknuto (je-li S < 0, hodnota |S| udav ˇ ´ – Nekdy se zaporn e´ hodnoty neuˇz´ıvaj´ı a semafor se zastav´ı na nule.


Synchronizace 11

– Vyuˇzit´ı semaforu˚ pro synchronizaci na KS:

semaphore mutex; // shared semaphore init(mutex,1); // initially mutex = 1 // ... lock(mutex); // critical section unlock(mutex); // ...

´ ı implementace semaforu: – Konceptualn´

typedef struct { int value; process_queue *queue; } semaphore;


Synchronizace 12

lock(S) { S.value--; if (S.value < 0) { zjistí výslednou hodnotu semaforu, pokud je kladná, může proces vstoupit do KS // remove the process calling lock(S) from the ready queue C = get(ready_queue); // add the process calling lock(S) to S.queue append(S.queue, C); // switch context, the current process has to wait to get // back to the ready queue je hodnota záporná, proces přidá sám sebe do čekací fronty a přepne kontext (proces je switch(); pokud pozastaven, spustí se jiný proces } } unlock(S) { S.value++; if (S.value <= 0) { pokud je hodnota záporná, někdo čeká // get and remove the first waiting process from S.queue P = get(S.queue); vybere první proces z čekací fronty a zařadí ho do fronty procesů připravených běžet // enable further execution of P by adding it into // the ready queue append(ready_queue, P); } } ´ Operaˇcn´ı systemy

Synchronizace 13

´ en´ ˇ ı lock a unlock mus´ı být atomicke. ´ Jejich telo ˇ pˇredstavuje rovneˇ ˇ z kritickou sekci!!! – Provad ˇ sen´ı atomicity lock a unlock: – Reˇ ´ • zakaz pˇreruˇsen´ı, ´ ´ ım (spinlock) • vzajemn e´ vylouˇcen´ı s vyuˇzit´ım atomických instrukc´ı a aktivn´ım cˇ ekan´ ´ u; – pouˇz´ıva´ se u multiprocesorových system ˚ ´ ı pouze na vstup do lock/unlock, ne na dokonˇcen´ı dlouhe´ uˇzivatelske´ KS. – cˇ ekan´

´ – Pouˇz´ıvaj´ı se take: ´ ´ ˇ • read-write zamky – pro cˇ ten´ı lze zamknout v´ıcenasobn e, ´ ´ ˇ • reentrantn´ı zamky – proces muˇ zamknout opakovane, ˚ ze stejný zamek ´ ı semafory, ktere´ mohou být odemknuty pouze temi ˇ procesy, ktere´ ja zamkly • mutexy – binarn´ ˇ (umoˇznuje optimalizovanou implementaci).


Synchronizace 14

´ ı: – POSIX: Semafory dostupne´ prostˇrednictv´ım volan´

semget - získání semaforu (vytvoření množiny semaforů, zpřístupnění) semop - operace nad semafory semctl - inicializace, zrušení

semget, semop, semctl, ˇ s´ı (viz man sem_overview): sem_open, sem_init, sem_post, novejˇ sem_wait, sem_getvalue, sem_close, sem_unlink, sem_destroy, ´ pthread_mutex_lock, pthread_mutex_unlock, ... POSIXova´ vlakna:

• starˇs´ı rozhran´ı (System V): • •

– Linux: futexes – fast user-space locks: ˇ zna´ celoˇc´ıselna´ promenn ˇ a´ ve sd´ılene´ pameti ˇ s atomickou • pouˇz´ıva´ se beˇ ´ reˇzimu na urovni inkrementac´ı/dekrementac´ı v uˇzivatelskem assembleru, ´ ´ • pˇri detekci konfliktu se vola´ pro ˇreˇsen´ı konfliktu jadro – sluˇzba

futex (hlavn´ı operace

FUTEX WAIT a FUTEX WAKE), ´ poˇctu konfliktu˚ se zcela obejde reˇzie spojena´ s volan´ ´ ım • rychlost vyplýva´ z toho, zˇ e pˇri malem ´ sluˇzeb jadra.


Synchronizace 15

Monitory ˇ ych synchronizaˇcn´ıch prostˇredku. – Jeden z vysokourov ´ nov´ ˚ Zapouzdˇruje data, ma´ definovane´ ´ et ˇ nejakou ˇ ´ en´ ˇ ymi daty: operace, jen jeden proces muˇ operaci nad chran ˚ ze provad

monitor monitor-name { shared variable declarations

s daty se neoperuje přímo, ale prostřednictvím monitoru, který automaticky zajišťuje, že na ním v dané chvíli pracuje pouze jeden proces

procedure body P1 (...) { ... } procedure body P2 (...) { ... } { initialization code } }


Synchronizace 16

´ ı uvnitˇr monitoru jsou k dispozici tzv. podm´ınky (conditions), nad kterými je – Pro moˇznost cˇ ekan´ předá monitor jinému procesu ´ et ˇ operace: moˇzne´ provad

• wait() a ´ neˇceka-li ´ nikdo, jedna´ se • signal(), resp. notify() – pokraˇcuje pˇr´ıjemce/odes´ılatel signalu; ´ o prazdnou operaci.

– Implementace moˇzna´ pomoc´ı semaforu. ˚ – Monitory jsou v urˇcite´ podobeˇ pouˇzity v Javeˇ (viz kl´ıcˇ ove´ slovo synchronized). Pro POSIXova´ ´ vlakna jsou k dispozici podm´ınky pthread cond t a souvisej´ıc´ı funkce pthread cond wait/ signal/ broadcast. ´ Operaˇcn´ı systemy

Synchronizace 17

ˇ ˇ ı problemy ´ Nekter e´ klasicke´ synchronizacn´

´ ˇ ’ s kapacitou omezenou na N – Komunikace producenta a konzumenta pˇres vyrovnavac´ ı pamet poloˇzek: – Synchronizaˇcn´ı prostˇredky:

semaphore full, empty, mutex; // Initialization: init(full,0); init(empty,N); init(mutex,1);


full - počet položek v bufferu empty - počet volných míst v bufferu mutex - přístup do KS

Synchronizace 18

– Producent:

do { ... // produce an item I ... lock(empty); je k dispozici volné místo? lock(mutex); ... // add I to buffer zápis do KS ... unlock(mutex); unlock(full); oznámí konzumentovi, že zapsal do bufferu } while (1);


– Konzument:

do { lock(full) nachází se něco v bufferu? lock(mutex); ... // remove I from buffer ... čtení z KS unlock(mutex); unlock(empty); v bufferu je volné místo, producent může zapsat ... // consume I ... } while (1);

Synchronizace 19

´ cten ´ ru˚ muˇ ˇ ˇ ´ ru˚ a p´ısaˇru: – Problem aˇ ˚ libovolný poˇcet cˇ tenaˇ p´ısˇ e, nikdo dalˇs´ı ˚ ze cˇ ´ıst; pokud ale nekdo ´ ani cˇ ´ıst. nesm´ı psat

– Synchronizaˇcn´ı prostˇredky:

int readcount; semaphore mutex, wrt;

readcount - počet čtenářů mutex - přístup k readcount wrt - vyloučení písařů navzájem, vyloučení čtenářů a písařů

// Initialization: readcount=0; init(mutex,1); init(wrt,1);


Synchronizace 20

ˇ ´ r: aˇ – Cten

– P´ısaˇr:

do { ... lock(wrt); vyloučení ostatních ... // writing is performed ... unlock(wrt); pustí ostatní ... } while (1);

ˇ ı” p´ısaˇru: – Hroz´ı “vyhladoven´ ˚ pˇridat dalˇs´ı semafor.


do { lock(mutex); readcount++; if (readcount == 1) lock(wrt); první čtenář zamyká před písaři unlock(mutex); ... // reading is performed ... lock(mutex); readcount--; if (readcount == 0) unlock(wrt); poslední čtenář odemkne unlock(mutex); písařům ... } while (1); pokud bude v KS vždy aspoň jeden čtenář, písař se nedostane na řadu přidáme semafor, který signalizuje, že písař čeká, čtenář se úplně na začátku pokusí zamknout zájem písaře, pokud se mu to nepovede, znamená to, že před ním již čeká písař a musí proto čekat. v případě, že se zámek povede, zase jej odemkne. písař Synchronizace 21 zámek odemyká po vstupu do KS

´ veceˇ ˇ r´ıc´ıch filozofu: – Problem ˚


Synchronizace 22

ˇ sen´ı (s moˇznost´ı uvaznut´ ´ – Reˇ ı):

semaphore chopstick[5]; // Initialization: for (int i=0; i<5; i++) init(chopstick[i],1); // Philospher i: do { lock(chopstick[i]) zamkne obě své hůlky lock(chopstick[(i+1) % 5]) ... // eat ... unlock(chopstick[i]); obě hůlky uvolní unlock(chopstick[(i+1) % 5]); ... uváznutí - každý filozof zaráz uchopí levou hůlku a bude se dožadovat pravé hůlky // think řešení: - např. semafory SYSV (umožňuje zamknout dva semafory zaráz) ... - jeden proces bude asymetrický, například první proces bude zamykat nejdříve } while (1); pravou hůlku ´ ˇ z´ıskavat ´ – Lepˇs´ı ˇreˇsen´ı: z´ıskavat obeˇ hulky souˇcasne, hulky asymetricky, ... ˚ ˚ ´ Operaˇcn´ı systemy

Synchronizace 23

´ ı synchronizacn´ ˇ ıch problem ´ u˚ Modelovan´ ´ u˚ je moˇzne´ pouˇz´ıt napˇr. Petriho s´ıteˇ (a ˇradu dalˇs´ıch – K popisu a analýze synchronizaˇcn´ıch problem formalismu). ˚ – P/T Petriho s´ıt’ ma´ charakter bipartitn´ıho grafu: dva typy uzlu˚ (m´ısta a pˇrechody), hrany propojuj´ı ruzn ˚ e´ typy uzlu˚ (nelze propojit m´ısto s m´ıstem): ˇ ych. M´ısta – reprezentuj´ı moˇzne´ stavy procesu˚ a promenn´ Pˇrechody – reprezentuj´ı moˇzne´ akce. ˇ ych. Znaˇcen´ı s´ıteˇ (teˇcky v m´ıstech) – stavy procesu˚ a promenn´ Proveden´ı pˇrechodu (pˇresuv znaˇcek ze vˇsech vstupn´ıch do vˇsech výstupn´ıch m´ıst) – reprezentuje ˇ e´ akce. je proveditelný, pokud má v každém vsutpním místě alespoň jednu značku proveden´ı nejak


Synchronizace 24

´ ´ – Pˇr´ıklad: model vzajemn eho vylouˇcen´ı na kriticke´ sekci

P(mutex)

mutex

critical section V(mutex)


Synchronizace 25

´ Uvaznut´ ı (deadlock) ´ – Uvaznut´ ım (deadlockem) pˇri pˇr´ıstupu ke sd´ılenym ´ zdrojum ˚ rozum´ıme situaci, kdy kaˇzdý ze ˇ ı zdroje s výluˇcným (omezeným) pˇr´ıstupem skupiny procesu˚ je pozastaven a cˇ eka´ na uvolnen´ ˇ ym nejak´ ˇ ym procesem z dane´ skupiny. vlastnen´ P1

P2

dva sdílené zdroje (např. paměť a I/O), první proces zamyká nejprve paměť, poté I/O, druhý proces zamyká I/O a pak paměť. může nastat situace, že první proces zamkne paměť, druhý zároveň zamkne I/O a oba čekají na odemknutí druhého zdroje - uváznutí

a

b

c

d

ˇ s´ı definice, ktera´ poˇc´ıta´ i s moˇznost´ı uvaznut´ ´ ´ ı – Obecnejˇ ı bez sd´ılených postˇredku˚ (napˇr. pˇri zas´ılan´ ´ ´ ´ zprav): Uvaznut´ ım rozum´ıme situaci, kdy kaˇzdý ze skupiny procesu˚ je pozastaven a cˇ eka´ na udalost, ˇ ktera´ by ovˇsem mohla nastat pouze, pokud by mohl pokraˇcovat nekter´ y z procesu˚ z dane´ mnoˇziny. ´ Operaˇcn´ı systemy

Synchronizace 26

ˇ ıc´ı podm´ınky uvaznut´ ´ – Nutne´ a postacuj´ ı pˇri pˇr´ıstupu ke sd´ılenym ´ zdrojum ˚ (Coffmanovy podm´ınky): (co se musí stát, aby vzniklo uváznutí) ´ ´ ı prostˇredku, 1. vzajemn e´ vylouˇcen´ı pˇri pouˇz´ıvan´ ˚ ´ ı na dalˇs´ı, 2. vlastnictv´ı alesponˇ jednoho zdroje, pozastaven´ı a cˇ ekan´ 3. prostˇredky vrac´ı proces, který je vlastn´ı, a to po dokonˇcen´ı jejich vyuˇzit´ı,

prostředky nemohou být odebrány

´ 4. cyklicka´ zavislost na sebe cˇ ekaj´ıc´ıch procesu. ˚ ´ ı cyklen´ım v cˇ ekac´ı smyˇcce.) (Pozor: Nesouvis´ı nijak s pojmem aktivn´ıho cˇ ekan´

ˇ sen´ ˇ ı: – Re ´ • prevence uvaznut´ ı, ´ ı se uvaznut´ ´ • vyhýban´ ı,

• detekce a zotaven´ı, ˇ ren´ı, zˇ e uvaznut´ ´ • (oveˇ ı nemuˇ ˚ ze nastat).


Synchronizace 27

´ Prevence uvaznut´ ı

ˇ ´ – Zruˇs´ıme platnost nekter e´ z nutných podm´ınek uvaznut´ ı: při práci s proměnnými v paměti použijeme atomické instrukce a nebude potřeba zamykání

ˇ ı (skuteˇcneˇ 1. Nepouˇz´ıvat sd´ılene´ prostˇredky nebo uˇz´ıvat sd´ılene´ prostˇredky, ktere´ umoˇznuj´ ´ souˇcasný) sd´ılený pˇr´ıstup a u kterých tedy nen´ı nutne´ vzajemn e´ vylouˇcen´ı procesu. ˚ ´ ´ e´ nevlastn´ı. 2. Proces muˇ o prostˇredky pouze pokud zˇ adn ˚ ze zˇ adat ´ a´ o prostˇredky, ktere´ nemuˇ ´ eˇ z´ıskat, je pozastaven, vˇsechny 3. Pokud proces poˇzad ˚ ze momentaln ´ a cˇ eka´ se, aˇz mu mohou být vˇsechny potˇrebne´ prostˇredky pˇrideleny. ˇ prostˇredky jsou mu odebrany ´ a je moˇzne´ je z´ıskavat ´ 4. Prostˇredky jsou oˇc´ıslovany pouze od nejniˇzsˇ ´ıch cˇ ´ısel k vyˇssˇ ´ım.


Synchronizace 28

´ ı se uvaznut´ ´ Vyhyb ´ an´ ı

– Procesy pˇredem deklaruj´ı urˇcite´ informace o zpusobu, jakým budou vyuˇz´ıvat zdroje: ˚ ´ ı pocet ˇ souˇcasneˇ poˇzadovaných zdroju˚ jednotlivých v nejjednoduˇssˇ ´ım pˇr´ıpadeˇ se jedna´ o maximaln´ typu. ˚

´ e´ informace o moˇzných poˇzadavc´ıch jednotlivých procesu˚ a o aktualn´ ´ ım stavu – Pˇredem znam ˇ an´ ´ ı se vyuˇzij´ı k rozhodovan´ ´ ı o tom, ktere´ poˇzadavky mohou být uspokojeny (a ktere´ mus´ı pˇridelov ´ poˇckat) tak, aby nevznikla cyklicka´ zavislost na sebe cˇ ekaj´ıc´ıch procesu. ˚ pokud hrozí, že po přidělení zdroje určitému procesu nastane uváznutí, systém požadavek na zdroje odmítne


Synchronizace 29

´ ı se uvaznut´ ´ – Existuje ˇrada algoritmu˚ pro vyhýban´ ı: ´ ´ • napˇr. algoritmus zaloˇzený na grafu alokace zdroju˚ pro systemy s jednou instanc´ı kaˇzdeho zdroje – ´ r´ıme graf vztahu, ˇ (Ri ⇒ Pj ), kdo o který zdroj zˇ ad ´ a´ cˇ i muˇ vytvaˇ ˚ který zdroj je kým vlastnen ˚ ze ˇ ´ ´ pouze tehdy, pokud nehroz´ı vznik cyklicke´ zavislosti poˇzadat (Pi ⇒ / → R j ); zdroj je pˇridelen cˇ ekaj´ıc´ıch procesu, ˚ coˇz by se projevilo cyklem v grafu), zdroj

R1

R1

P2 může žádat o R1

P1 vlastní R1

proces

P1

P2

P1

P2

P2 žádá o R2

R2

R2

"splníme" požadavky, tedy modelujeme situaci, kdy je procesu přidělen požadovaný zdroj, pokud vzniká cyklus, nastává uváznutí - přidělení zdroje není povoleno

´ ruv ´ s v´ıce instancemi zdroju. • tzv. bankeˇ ˚ algoritmus pro praci ˚


Synchronizace 30

´ Detekce uvaznut´ ı a zotaven´ı

´ – Uvaznut´ ı muˇ ˚ ze vzniknout; periodicky se pˇritom detekuje, zda k tomu nedoˇslo, a pokud ano, provede se zotaven´ı. ´ ı pro systemy ´ ´ ´ – Detekce uvaznut´ ı: graf cˇ ekan´ s jednou instanc´ı kaˇzdeho zdroje (který proces cˇ eka´ na ˇ ı zdroje kterým procesem: cyklus implikuje deadlock), ... uvolnen´ ´ – Zotaven´ı z uvaznut´ ı: ˇ • ukonˇcen´ı vˇsech nebo nekter´ ych zablokovaných procesu, ˚ ´ ı zdroju˚ nekter´ ˇ ˇ umoˇznen´ ˇ ı pokraˇcovat (pˇr´ıpadneˇ • odebran´ ym procesum, jejich pozastaven´ı a pozdeji ˚ jejich restart).

možnost nekonzistence zdrojů

V obou pˇr´ıpadech anulace nedokonˇcených operac´ı (rollback ), nebo nutnost akceptace moˇzných nekonzistenc´ı.


Synchronizace 31

´ ˇ ı procesu˚ (starvation) Starnut´ ı/hladoven´ ˇ ı zdroju), – Procesy cˇ ekaj´ı na podm´ınku (napˇr. pˇridelen´ ˚ u n´ızˇ nen´ı zaruˇceno, zˇ e nastane (napˇr. proto, ´ pˇredb´ıhany ´ jinými procesy). zˇ e pˇr´ısluˇsne´ procesy mohou být neustale

2

a

b

2


Synchronizace 32

´ ı verifikace Formaln´ ´ ´ – Pokud nen´ı pouˇzit mechanismus prevence, obchazen´ ı cˇ i detekce a zotaven´ı se z uvaznut´ ı (ˇci jiných ´ ˇ rit, zˇ e system ´ je navrˇzen tak, zˇ e zˇ adn ´ e´ neˇzadouc´ ´ ´ ı neˇzadouc´ ıch vlastnost´ı), je vhodne´ oveˇ ı chovan´ nehroz´ı. ´ ı neˇzadouc´ ´ ´ ı system ´ u˚ (mj. uvaznut´ ´ ´ – Moˇznosti odhalovan´ ıho chovan´ ı cˇ i starnut´ ı) zahrnuj´ı: ´ ´ ´ • inspekce systemu (nejlepe nezavislou osobou), ˇ ´ ı, dynamicka´ analýza, (pˇr´ıp. i samo-oprava za behu: self-healing), • simulace, testovan´ ´ ı verifikace, • formaln´

• nebo kombinace vˇsech uvedených pˇr´ıstupu. ˚ ´ ı) umoˇznuje ˇ ´ ´ ı verifikace (na rozd´ıl od simulace a testovan´ – Formaln´ nejen vyhledavat chyby, ale take´ ´ ´ ´ ´ ´ zˇ e zˇ adn ´ e´ chyby nezustaly dokazat spravnost systemu s ohledem na zadana´ kriteria (coˇz znamena, ˚ bez povˇsimnut´ı).


Synchronizace 33

´ ı verifikace: – Proces formaln´ model systému ´ pˇr´ımo se systemem), ´ • vytvoˇren´ı modelu (lze pˇreskoˇcit pˇri praci

ˇ rit (nekter ˇ • specifikace vlastnosti, kterou chceme oveˇ e´ vlastnosti mohou být genericke´ – napˇr. absence deadlocku, null pointer exceptions apod.), ´ kontrola, zda model splnuje ˇ • (automaticka) specifikaci.

´ ´ ı verifikaci zahrnuj´ı: – Zakladn´ ı pˇr´ıstupy k formaln´

• model checking • theorem proving • static analysis


Synchronizace 34

– Theorem proving: splňuje systém danou podmínku?

• Vyuˇz´ıva´ (typicky) poloautomatický dokazovac´ı prostˇredek (PVS, Isabel,Coq,ACL/2,...). ´ • Vyˇzaduje experta, který urˇcuje, jak se ma´ dukaz vest. ˚ – Model checking: generuje a prohledává všechny možné stavy procesu

• Vyuˇz´ıva´ obvykle automatický prostˇredek (Spin, SMV, Slam/SDV, Blast, JPF, ...). ´ ´ ı a prohledav ´ an´ ´ ı stavoveho prostoru. • Vyuˇz´ıva´ typicky generovan´ ´ stavove´ exploze, kdy velikost stavoveho ´ • Hlavn´ı nevýhodou je problem prostoru roste ´ eˇ s velikost´ı modelu, pˇr´ıpadneˇ prace ´ s neomezeným poˇctem stavu. exponencialn ˚ – Static analysis: ˇ ren´ı pˇr´ısluˇsných vlastnost´ı na zaklad ´ ´ • Snaha o oveˇ eˇ popisu modelu cˇ i systemu, aniˇz by se tento ´ el ˇ a prochazel ´ ´ ı jen na urˇcite´ abstraktn´ı urovni). provad se stavový prostor (pˇr´ıpadneˇ se provad´ ´

• Ruzn ˚ e´ podoby: dataflow analysis, constraint analysis, type analysis, abstract interpretation.


Synchronizace 35

Verifikace na FIT – VeriFIT ˇ ´ ´ – Rada temat sahaj´ıc´ıch od teoretickeho vyzkumu ´ (teorie jazyku˚ a automatu˚ a jej´ı vyuˇzit´ı, Petriho ˇ ...), pˇres pokrocil ˇ e´ algoritmy a datove´ struktury potˇrebne´ pro efektivn´ı implementaci s´ıte, ´ e´ pˇr´ıpadove´ studie: verifikaˇcn´ıch metod po realn ´ ı verifikace parametrických a nekoneˇcneˇ stavových system ´ u˚ (napˇr. programy s • formaln´ dynamickými datovými strukturami: seznamy, stromy, ...) pomoc´ı automatu, ˚ logik, ... – partneˇri LIAFA (Paˇr´ızˇ ), Verimag (Grenoble), Uppsala University, ... ´ ı verifikace Java programu˚ (ve spolupraci ´ s Universitou v Milan ´ e), ˇ • formaln´ ´ ı verifikace v OS, ... • formaln´ ´ ı, dynamicka´ analýza a sebe-opravovan´ ´ ı paraleln´ıch programu˚ (Java, C) – EU projekt • testovan´ Shadows (partneˇri: IBM Haifa Research Laboratories, ...)

– Jedna z hlavn´ıch aplikac´ı v oboru Matematicke´ metody v IT na FIT. ´ ˇ ıkovou praci, ´ ´ ´ – Zajemci o moˇznou rocn´ diplomovou praci, ... jsou v´ıtani!


Synchronizace 36

´ pameti ˇ Sprava

´ s Vojnar Tomaˇ

[email protected]

Vysoke´ uˇcen´ı technicke´ v Brneˇ Fakulta informaˇcn´ıch technologi´ı ˇ Boˇzetechova 2, 612 66 BRNO 26. dubna 2011


´ pameti ˇ Sprava

ˇ – Aby program mohl být proveden, mus´ı nad n´ım být vytvoˇren proces, mus´ı mu být pˇridelen procesor ˇ ˇ ’ (a pˇr´ıpadneˇ dalˇs´ı zdroje). např. I/O zdroje a mus´ı mu být pˇridelena pamet – Rozliˇsujeme: ´ ı adresový prostor, se kterým pracuje procesor pˇri • logicky´ adresovy´ prostor (LAP): virtualn´ ´ en´ ˇ ı kodu ´ ´ provad (kaˇzdý proces i jadro maj´ı svuj), ˚ ˇ (spoleˇcný pro vˇsechny • fyzicky´ adresovy´ prostor (FAP): adresový prostor fyzických adres pameti ´ procesy i jadro).


´ pameti ˇ Sprava

1

– MMU (Memory Management Unit) = HW jednotka pro pˇreklad logických adres na fyzicke´ (dnes ´ cˇ ipu procesoru): souˇcast

CPU

Logical Address

MMU

Physical Address

Memory

TLB

interrupt Data

datová sběrnice

´ ıch registru˚ a pˇr´ıpadeˇ i hlavn´ı pameti ˇ systemu; ´ – MMU vyuˇz´ıva´ specialn´ pro urychlen´ı pˇrekladu muˇ ˚ ze ´ ˇ (napˇr. TLB). obsahuje informace potřebné pro překlad adres obsahovat ruzn ı pameti ˚ e´ vyrovnavac´


´ pameti ˇ Sprava

2

ˇ ´ ı pameti ˇ Pˇridelov an´

´ re setkat s pˇridelov ˇ an´ ´ ım FAP pro – Na nejniˇzsˇ ´ı urovni z hlediska bl´ızkosti HW se muˇ ´ ˚ zeme v jadˇ ´ ı do LAP, ktere´ je konzistentn´ı se zpusobem ´ HW zamapovan´ pˇrekladu LAP na FAP, jenˇz je podporovan ˚ ´ ´ daneho výpoˇcetn´ıho systemu:

• spojite´ bloky (contiguous memory allocation), • segmenty, ´ • stranky, ´ • kombinace výsˇ e uvedeneho. ˇ an´ ´ ı LAP pro konkretn´ ´ ı potˇreby uˇzivatelských procesu˚ – Na vyˇssˇ ´ı urovni se pak pouˇz´ıva´ pˇridelov ´ ´ ´ ˇ znou potˇrebu v jadˇ ´ re ( kmalloc, ( malloc, ... – implementovano mimo reˇzim jadra) i pro beˇ ˇ ych usek ´ u˚ FAP. vmalloc, ...), a to v ramci bloku˚ LAP jiˇz zamapovaných do pˇridelen´ ´


´ pameti ˇ Sprava

3

Contiguous Memory Allocation

ˇ any ´ spojite´ bloky pameti ˇ urˇcite´ velikosti. – Procesum ˚ jsou pˇridelov – Snadna´ implementace (jak v HW, tak obsluha v OS):

kde se blok přidělené paměti nachází ve fyzické paměti

velikost bloku přidělené paměti

proces se snaží přistoupit mimo jemu přidělenou paměť


´ pameti ˇ Sprava

4

ˇ (FAP): – Významneˇ se projevuje extern´ı fragmentace pameti ˇ an´ ´ ım a uvolnov ˇ an´ ´ ım pameti ˇ vznika´ posloupnost obsazených a neobsazených usek • pˇridelov u˚ ´ ˇ ruzn ´ protoˇze je nespojite, ´ pameti ıc´ı, zˇ e volne´ m´ısto muˇ ˚ e´ velikosti zpusobuj´ ˚ ˚ ze být nevyuˇzitelne, ˇ (pˇriˇcemˇz je tˇreba brat ´ do uvahy • minimalizace pomoc´ı ruzn´ take´ reˇzii ˚ ych strategi´ı alokace pameti ´ ˇ an´ ´ ım) – mimo first fit lze uˇz´ıt napˇr. best fit, worst fit, binary buddy, ..., spojenou s daným pˇridelov ´ se zvetˇ ˇ sovan´ ´ ım pˇridelen ˇ eho ´ • problem prostoru, ˇ (nakladn ´ ´ • dynamicka´ reorganizace pameti e!).

worst fit - přidělí nejméně odpovídající volný blok best fit - přidělí nejvhodnější blok binary buddy - přiděluje paměť po mocninách 2

ˇ nutno odkladat ´ ˇ ’ procesu: muˇ ´ pomale. ´ na disk veˇskerou pamet – Pˇri nedostatku pameti ˚ ze být zbyteˇcne, ´ ´ pameti. ˇ nen´ı moˇzne´ sd´ılet cˇ asti – Nen´ı moˇzne´ jemneˇ ˇr´ıdit pˇr´ıstupova´ prava, ´ popisuj´ıc´ıch obsazen´ı pameti ˇ je pak ale nutne´ – Nemus´ı zpusobit intern´ı fragmentaci, ve strukturach ˚ ˇ ı evidence pˇridelen ˇ e/voln ´ ˇ a odstranen´ ˇ ı moˇznosti pracovat s upln´ e´ pameti ´ ymi adresami. Pro usnadnen´ ˇ ´ vzniku velmi malých neobsazených usek u˚ se muˇ v nasobc´ ıch urˇcitých bloku, ı ´ ˚ ze pˇridelovat ˚ coˇz zpusob´ ˚ ˇ an´ ´ ı pameti). ˇ intern´ı fragmentaci (toleruje se, vznika´ i u ostatn´ıch mechanismu˚ pˇridelov


´ pameti ˇ Sprava

5

ˇ Segmentace pameti ˇ ˇ pˇrekladaˇcem – LAP rozdelen na kolekci segmentu. ˚ Ruzn ˚ e´ segmenty mohou být pˇrideleny ´ ´ ´ ´ ´ cˇ astem dat, zasobn´ ıku, ...). (programatorem) jednotlivým cˇ astem procesu (napˇr. proceduram, ´ ´ a´ ze jmena ´ – Kaˇzdý segment ma´ jmeno (ˇc´ıslo) a velikost; logicka´ adresa sestav segmentu a posunu ˇ v nem:

logická adresa se zkládá z čísla segmentu a posuvu v rámci segmentu (velikost požadované paměti)

+ další řídící přáznaky

podle indexu segementu se vyhledá odpovídající záznam v tabulce segmentů, pokud proces přistupuje mimo přidělenou oblast, dojde k chybě


´ pameti ˇ Sprava

6

ˇ (segmenty jen pro cˇ ten´ı, – Segmenty mohou být vyuˇzity jako jednotka ochrany a/nebo sd´ılen´ı pameti sd´ılene´ segmenty, ...).

´ pomern ˇ eˇ jednoducha. ´ – Implementace je stale

ˇ ’ pˇridelov ˇ ana ´ ˇ ı dopadu˚ extern´ı fragmentace a jemnejˇ ˇ s´ı odklad ´ an´ ´ ı neˇz – Pamet po segmentech; zm´ırnen´ ˇ an´ ´ ı jedine´ oblasti – ale problem ´ pˇretrvav ´ a. ´ u pˇridelov

– Segmentace je viditelna´ procesu: komplikace pˇri pˇrekladu (tvorbeˇ programu), ˚ moˇznost chyb.


´ pameti ˇ Sprava

7

´ ´ ı Strankov an´ ˇ ´ – LAP rozdelen na jednotky pevne´ velikosti: stranky (pages). ˇ ´ – FAP rozdelen na jednotky stejne´ velikosti: ramce (frames).

– Vlastnosti: ˇ ’ pˇridelov ˇ ana ´ ´ ıch, • pamet po ramc´

• neviditelne´ pro uˇzivatelske´ procesy, ´ problemy ´ • minimalizovany s extern´ı fragmentac´ı,

paměť je rozdělena na stránky, každá je buď volná nebo obsazená, pokud

– nevznika´ nevyuˇzitelný volný prostor, není místo na souvislé uložení, stránky se rozprostřou ˇ (vetˇ ˇ s´ı poˇcet koliz´ı v ruzn´ ´ – moˇzne´ sn´ızˇ en´ı rychlosti pˇr´ıstupu do pameti ıch ˚ ych vyrovnavac´ ˇ ´ se strukturami popisuj´ıc´ımi aktualn´ ´ ı obsah pameti), ˇ pametech) a alokace/dealokace (delˇs´ı prace ´ u: ˇ ˇ ’ pokud moˇzno po spojitých posloupnostech ramc – proto v praxi je snaha pˇridelovat pamet ˚ napˇr. pomoc´ı algoritmu binary buddy“, ” ´ en´ ˇ ı – tzv. NX bit) a/nebo sd´ılen´ı, lze nastavit • jemna´ jednotka ochrany (r/rw, user/system, moˇznost provad ´ an´ ´ ı po strank ´ ach, ´ • jemna´ kontrola odklad

zabezpečení pro každou stránku

ˇ s´ı implementace, vetˇ ˇ s´ı reˇzie, • sloˇzitejˇ

• intern´ı fragmentace.


´ pameti ˇ Sprava

8

ˇ ych) tabulek stranek, ´ – V nejjednoduˇssˇ ´ım pˇr´ıpadeˇ tzv. jednoduchých (ˇci jednourov OS udrˇzuje ´ nov´ ´ ´ ´ informaci o volnych ´ ramc´ ıch a pro kaˇzdý proces (a jadro) tabulku stranek (page table): logická adresa se skládá z čísla stránky a posuvu v rámci stránky každý proces má svou tabulku stránek (uložena v RAM) v MMU je uložen začátek tabulky stránek pro daný proces (registr CR3) pro číslo logické stránky se nalezene odpovídající číslo fyzické stránky a v ní se použije stejný posun jako v logické adrese


´ pameti ˇ Sprava

9

´ ´ ı logických stranek ´ – Tabulka stranek obsahuje popis mapovan´ do FAP a pˇr´ıznaky modifikace, ´ (r/rw, user/system, moˇznost provad ´ en´ ˇ ı), pˇr´ıznak globality (neodstranov ˇ ano ´ pˇr´ıstupu, pˇr´ıstupova´ prava pokud je položka sdílená, ponechá ji v cache automaticky z TLB pˇri pˇrepnut´ı kontextu), ...

ˇ specialn´ ´ ı registr MMU (CR3 u x86) obsahuje ´ ´ v hlavn´ı pameti; – Tabulky stranek jsou udrˇzovany ´ ´ ´ ı proces. adresu zaˇcatku tabulky stranek pro aktualn´ ˇ vyˇzaduje (u jednoduche´ tabulky stranek) ´ – Kaˇzdý odkaz na data/instrukce v pameti dva pˇr´ıstupy do ˇ do tabulky stranek ´ pameti: a na vlastn´ı data/instrukci.

´ ˇ TLB (Translation Look-aside – Urychlen´ı pomoc´ı rychle´ hardwarove´ asociativn´ı vyrovnavac´ ı pameti Buffer ).


´ pameti ˇ Sprava 10

´ ´ ˇ – TLB obsahuje dvojice (ˇc´ıslo stranky,ˇ c´ıslo ramce) + nekter e´ z pˇr´ıznaku˚ spojených s daným ´ en´ ˇ ı, pˇr´ıznak modifikace, pˇr´ıp. dalˇs´ı). ´ ım v tabulkach ´ stranek ´ mapovan´ (pˇr´ıstupova´ opravn ´ ´ – POZOR! V TLB nejsou cele´ stranky cˇ i ramce! ´ a´ paralelneˇ na zaklad ´ ´ ´ – TLB se prohledav eˇ cˇ ´ısla stranky, a to bud’ plneˇ (viz obrazek n´ızˇ e), nebo ´ cneˇ (dojde k indexaci skupiny bunek ˇ TLB dle cˇ asti ´ cˇ ´ısla stranky ´ ´ ı– cˇ asteˇ a pak k paraleln´ımu dohledan´ ´ ´ ´ napˇr. by mohly být uˇzity 2 bity z cˇ ´ısla stranky k rozliˇsen´ı 4 mnoˇzin dvojic stranek prohledavan´ ych jiˇz ´ ˇ tak, jak je znazorn eno n´ızˇ e).

TLB miss - pokud TLB neobsahuje záznam pro danou stránku, pokračuje se podle běžného postupu



– POZOR! K TLB miss muˇ ˚ ze doj´ıt jak pˇri cˇ ten´ı instrukce, tak pˇri cˇ ten´ı jejich operandu, ˚ a to u instrukce i ´ ´ operandu˚ i v´ıcenasobn eˇ (nezarovnana´ instrukce, nezarovnana´ data, data delˇs´ı neˇz jedna stranka). – Po TLB miss: ´ • U HW ˇr´ızených TLB HW automaticky hleda´ v tabulce stranek. ´ ´ • U SW ˇr´ızených TLB (napˇr. MIPS, SPARC) mus´ı v tabulce stranek hledat jadro a patˇriˇcneˇ upravit obsah TLB. ´ st’ pro stranky ´ ´ a data a/nebo hierarchie v´ıce ˇ obsahuj´ıc´ı kod – Nekdy muˇ ˚ ze být pouˇzito v´ıce TLB: zvlaˇ urovn´ ı TLB (ruzn ´ ˚ a´ rychlost, kapacita, cena, spotˇreba). – Pˇri pˇrepnut´ı kontextu nutno obsah TLB invalidovat. Optimalizace: ´ ıch stranek ´ ´ stn´ım pˇr´ıznakem v tabulce stranek ´ oznaˇcených zvlaˇ a TLB cˇ i • pouˇzit´ı globaln´

neodstraňují se z TLB

´ • spojen´ı zaznamu v TLB s identifikac´ı procesu (ASID, PCID, ...). ˇ eˇ obsahu tabulek stranek. ´ ˇ e´ zaznamy ´ – Invalidace TLB nutna´ samoˇrejmeˇ i po zmen Muˇ ˚ ze-li ovlivnen pouˇz´ıvat v´ıce procesoru, ˚ nutno invalidovat TLB na vˇsech procesorech. je třeba vymazat TLB ˇ ´ ´ provad ´ en ˇ e´ – Nekter e´ procesory mohou dopˇredu nahravat do TLB pˇreklad pro odhadovane´ dale instrukce. ´ Operaˇcn´ı systemy


´ ı na usp ˇ snosti TLB: ´ ´ ı velmi silneˇ zavis´ – Efektivnost strankov an´ ´ eˇ

• Efektivn´ı pˇr´ıstupova´ doba: (τ + ε)α + (2τ + ε)(1 − α), kde – τ: vybavovac´ı doba RAM – ε: vybavovac´ı doba TLB ˇ ˇ sných vyhledan´ ´ ı v TLB (TLB hit ratio) – α: pravdepodobnost usp ´ eˇ

při čtení programu by se za sebou měly nacházet odkazy do stejné stránky, pokud se bude neustále přeskakovat ze stránky na stránku, bude se přepisovat TLB -> častý TLB miss -> TLB nevyužita

ˇ e´ zpomalen´ı o 22%. • Napˇr. pro τ = 100ns, ε = 20ns a α = 0.98 dostaneme prum ˚ ern ´ ı na lokaliteˇ odkazu˚ programu. • TLB hit ratio významneˇ zavis´

vlastnost programu, která udává míru toho, kolik různých shluků adres v paměti odpovídajích různým stránkám v dané chvíli program používá...pokud program používá příliš mnoho stránek, dochází k výpadkům z paměti TLB

´ – Výsˇ e uvedený vztah je sestaven za pˇredpokladu, zˇ e po TLB miss a pˇrekladu pˇres tabulky stranek se z´ıskana´ adresa ihned pouˇzije. V praxi se cˇ asto z´ıskaný pˇreklad nejprve vloˇz´ı do TLB a pak se opakuje ´ vztahu nutno pˇri TLB miss pˇripoˇc´ıst dalˇs´ı pˇr´ıstup do TLB pˇreklad pˇres TLB – pak je ve výsˇ e uvedenem a take´ cˇ as pro upravu TLB. ´ – Lokalita odkazu˚ = vlastnost programu – m´ıra toho, kolik ruzn´ ˚ ych shluku˚ adres (odpov´ıdaj´ıc´ıch ´ em ´ cˇ asovem ´ useku. ´ v ruzn´ ´ ach) ´ typicky adresam bude proces potˇrebovat v kratk ´ ˚ ych strank



Pˇr´ıklad: ´ an´ ´ ı matic po ˇradc´ ´ ıch je – Pˇri uklad

for (j = 0; j < MAX; j++) for (i = 0; i < MAX; i++) A[i,j] = 0; ´ eˇ výhodne´ neˇz mnohem men

for (i = 0; i < MAX; i++) for (j = 0; j < MAX; j++) A[i,j] = 0; ˇ pˇri virtualizaci pameti ˇ a odklad ´ an´ ´ ı stranek ´ – Rozd´ıl se projev´ı jeˇsteˇ výrazneji na disk.



´ Implementace tabulek stranek

´ ´ e. ´ – Tabulky stranek mohou být znaˇcneˇ rozsahl

´ se strankami ´ ´ poloˇzek (pˇresneˇ – Pro 32b system o velikosti 4KiB (212 ) muˇ ˚ ze m´ıt tabulka v´ıce neˇz milion ´ poloˇzka tabulky stranek ´ 232/212 = 220 = 1048576 poloˇzek). Ma-li 4B, dostaneme 4MiB na tabulku ´ stranek pro kaˇzdý proces, coˇz je pˇr´ıliˇs na spojitou alokaci (pro 100 procesu˚ 400MiB jen pro tabulky ´ stranek!). ´ ´ exponencialn ´ eˇ roste. – Pro 64b systemy problem



´ ´ ´ ´ – Hierarchicke´ tabulky stranek: tabulka stranek je sama strankov ana, vznikaj´ı tabulky tabulek ´ ´ zpomaluje pˇr´ıstup). stranek, ... (coˇz ovˇsem dale ˇ a´ tabulka stranek ´ – Pˇr´ıklad: dvouurov procesoru˚ i386+ ´ nov Logical address 22 21

31

10 bits horních 10 bitů je index do tabulky tabulek stránek, tam se nalezne odkaz na dílčí tabulku stránek, v níž se podle indexu (prostředních 10 bitů) nalezne odkaz na číslo stránky

12 11

10 bits

odkaz do tabulek tabulek stránek

0

12 bits

odkaz do tabulek stránek

page tables

posuv ve stránce

page directory

index lze přepínat mezi 4KiB a 4MiB velikostmi stránek přepnutím 1 bitu v adresáři tabulek stránek. pak se použije pouza jedna úroveň stránek -> prostřední část adresy pak také tvoří posuv

index

Physical address page number

12 11

0

12 bits offset

´ adresaˇ ´ re stranek ´ ´ ´ ı. T´ımto – Pˇr´ıznak v poloˇzkach urˇcuje, zda je pouˇzita i niˇzsˇ ´ı urove nˇ strankov an´ ´ ´ zpusobem je moˇzno pracovat se strankami o velikosti 4 KiB (212 B) a 4 MiB (222 B). ˚ ´ Operaˇcn´ı systemy


ˇ a´ tabulka stranek ´ – 4-urov na x86-64: ´ nov

´ tabulek PDPE a PDE urˇcuje, zda je pouˇzita i niˇzsˇ ´ı urove ´ ´ ı. T´ımto – Pˇr´ıznak v poloˇzkach nˇ strankov an´ ´ ´ ˇ zpusobem je moˇzno pracovat se strankami o velikosti 4 KiB (212 B), 2 MiB (221 B) a u nekter´ ych ˚ procesoru˚ i 1 GiB (230 B). ´ Operaˇcn´ı systemy


´ – Hashovane´ tabulky stranek:

každý proces má svou hashovací tabulku

číslo logické stránky se zahashuje, podle něj se v tabulce stránek nalezne odpovídající zřetězený seznam, který obsahuje číslo stránky a číslo rámce (v ideálním případě je tento seznam pouze s jedním prvkem), najdu v zřetězeném seznamu číslo dané stránky a jeho odpovídající rámec



´ ıc´ı pro kaˇzdý ramec, ´ ˇ ´ – Invertovana´ tabulka stranek: jedina´ tabulka udavaj´ který proces ma´ do nej ´ kterou stranku. ´ do jednoho rámce může přistupovat více procesů, je proto nutné každý proces identifikovat namapovanu pomocí PID a pamatovat si, kterou jeho stránku mapuje do daného rámce

´ ım napˇr. PowerPC a 64b UltraSparc firmy Sun. – Pouˇz´ıva´ v kombinaci s hashovan´ ´ pameti ˇ (odklad ´ an´ ´ ı na disk apod.) vede dale ´ i klasicke´ tabulky stranek. ´ – OS si pro potˇreby spravy ´ Problematicka´ je implementace sd´ılen´ı stranek.

je nutné postupně procházet invertovanou tabulku stránek, na každém řádku hledáme, zda obsahuje číslo logické stránky a číslo aktuálního procesu, pokud ano, zjistíme index řádku -> číslo rámce

položky indexovány číslem rámce



ˇ Virtualizace pameti virtualizace = technologie, která umožňuje oddělit vazbu mezi obsazenou částí logického adresového prostoru procesu a obsazenou částí paměti. umožňuje ukládat obsazené části logické paměti na disk

ˇ – Vyuˇzitý adresový prostor procesu nemus´ı být celý ve fyzicke´ pameti. – Vyuˇz´ıva´ se prostor na disku.

– Virtualizace pomoc´ı: ´ ´ ı na zˇ adost ´ • strankov an´ (demand paging) ´ ı na zˇ adost ´ • segmentovan´ (demand segmenting)



´ ´ ı na zˇ adost ´ Strankov an´

´ ´ eny ˇ do pameti ˇ jen tehdy, jsou-li zapotˇreb´ı. – Stranky jsou zavad ˇ rychlejˇs´ı odklad ´ an´ ´ ı na disk a zavad ´ en´ ˇ ı do pameti ˇ (nen´ı zapotˇreb´ı odloˇzit – Menˇs´ı spotˇreba pameti, ´ celý vyuˇzitý adresový prostor procesu). nebo zavest

´ ´ je zapotˇreb´ı tehdy, dojde-li k odkazu na ni. V tabulce stranek je pˇr´ıznak, zda pˇr´ısluˇsne´ – Stranka ´ ˇ ´ ´ strance je pˇridelen ramec. Pokud ne, dojde k výpadku stranky (page fault).



´ Obsluha vypadku ´ stranky ´ ´ ıc´ı, zˇ e nelze pˇrevest ´ adresu (nen´ı definovano ´ – Výpadek stranky je pˇreruˇsen´ı od MMU udavaj´ ´ ı v tabulce stranek). ´ mapovan´ ˇ y adresový prostor, dojde – Pokud pˇr´ıcˇ inou výpadku nen´ı to, zˇ e se odkazujeme mimo pˇridelen´ ´ ´ ´ k obsluze výpadku stranky takto (pouze zakladn´ ı ilustrace, bl´ızˇ e viz nasleduj´ ıc´ı slajd):

ke slovu se dostane jádro, zjistí důvod výpadku, pokud je to dáno tím, že se proces pokoušel přistoupit do paměti, která mu nebyla alokována, typicky dojde ke zrušení procesu pokud proces přistupuje do alokované paměti, která však ještě nebyla vytvořena nebo byla odložena, je nutné vytvořit nový rámec, načíst data z dsku, upraví se tabulka stránek, znova se provede instrukce, která selhala



ˇ vypada´ typicka´ obsluha výpadku stranky ´ – Podrobneji takto: ˇ y adresový prostor. 1. Kontrola, zda se proces neodkazuje mimo pˇridelen´ ´ 2. Alokace ramce: ´ ˇ y volný je, • pouˇzijeme volný ramec, pokud nejak´ • pokud nen´ı, ´ ˇ ym ramcem ´ – vybereme vhodnou stranku s pˇridelen´ (victim page), ´ ´ pˇr´ıznak modifikace v tabulce stranek), ´ – stranku odloˇz´ıme na swap (je-li to nutne: ˇ y ramec. ´ – pouˇzijeme uvolnen´ ´ ´ ´ 3. Inicializace stranky po alokaci zavisl a´ na pˇredchoz´ım stavu stranky: ´ • prvn´ı odkaz na stranku: ´ naˇcten´ı z programu, kod: inicializovana´ data: naˇcten´ı z programu, ´ ı (nelze ponechat puvodn´ vˇse ostatn´ı: vynulovan´ ı obsah – bezpeˇcnost), ˚ ´ ˇ • stranka byla v minulosti uvolnena z FAP: ´ znovu naˇcte z programu (jen pokud nelze pˇrepisovat kodov ´ ´ kod: e´ stranky), ´ z co kod, ´ konstantn´ı data: toteˇ ´ ´ ˇ do FAP. ostatn´ı: pokud byla modifikovana, je stranka ve swapu a mus´ı se naˇc´ıst zpet ´ ´ ´ ı zpˇr´ıstupnovan ˇ ´ ˇ y ramec. ´ tabulky stranek: namapovan´ e´ stranky na pˇridelen´ 4. Uprava ´ ı instrukce, ktera´ výpadek zpusobila 5. Proces je pˇripraven k opakovan´ (je ve stavu pˇripravený“). ˚ ”



´ ´ ı na zˇ adost ´ Vykonnost ´ strankov an´ ˇ (1 − p)T + pD, kde – Efektivn´ı doba pˇr´ıstupu do pameti: ˇ ´ • p: page fault rate = pravdepodobnost výpadku stranky,

• T : doba pˇr´ıstupu bez výpadku, • D: doba pˇr´ıstupu s výpadkem.

– Vzhledem k tomu, zˇ e T << D, mus´ı být p co nejmenˇs´ı: ˇ a jemu pˇrimeˇ ˇ rený poˇcet procesu˚ (s ohledem na jejich pamet ˇ ’ove´ naroky), ´ • dostatek pameti ˇ zavad ´ en´ ˇ ych a odkladan´ ´ ´ • vhodný výber ych stranek,

• lokalita odkazu˚ v procesech.



ˇ vypadk Pocet ´ u˚

´ s kaˇzdým z jejich operandu, – K výpadkum ˚ muˇ ˚ ze doj´ıt jak pˇri cˇ ten´ı instrukce, tak pˇri praci ˚ a to ´ ˇ ´ e. u instrukce i u kaˇzdeho z operandu˚ i v´ıcenasobn ´ – V´ıcenasobn e´ výpadky mohou být zpusobeny: ˚ ´ ım instrukce, • nezarovnan´ ´ ım dat, • nezarovnan´

delší než 1 stránka

´ • daty delˇs´ımi neˇz jedna stranka, ´ ´ na stejne´ urovni • výpadky tabulek stranek ruzn´ ı – a to i v´ıcekrat hierarchických tabulek ˚ ych urovn´ ´ ´ ´ ´ ´ ıc´ı se na stejne´ urovni. stranek pˇri dotazech na ruzn nachazej´ ˚ e´ d´ılˇc´ı tabulky stranek ´ ´ tabulek stranek ´ ´ ena ˇ ´ ´ – Obvykle alesponˇ cˇ ast je chran pˇred výpadkem stranek (zejmena se to týka´ ´ ˇ mj. proto, aby bylo moˇzno u hierarchických tabulek stranek d´ılˇc´ı tabulky nejvyˇssˇ ´ı urovn e) ´ ´ obsluˇzit výpadky stranek. ´ ı poˇcet výpadku˚ stranek ´ ´ ´ – Pˇr´ıklad: Jaký je maximaln´ v systemu se strankami o velikosti 4 KiB, ˇ ´ ´ en ˇ a´ proti výpadku, 4-urov tabulkou stranek, u ktere´ pouze d´ılˇc´ı tabulka nejvyˇssˇ ´ı urovn eˇ je chran ´ novou ´ ˇ ´ ´ en´ ˇ ı pˇredem nenaˇctene´ instrukce o delce 4 B, ktera´ pˇresouva´ 8 KiB z jedne´ adresy pameti pˇri provad na jinou?



´ an´ ´ ı stranek ´ Odklad ´ ´ – K odloˇzen´ı stranky muˇ Muˇ ˚ ze doj´ıt pˇri výpadku stranky. ˚ ze být provedeno odloˇzen´ı: ´ ´ ´ ı – tj. v ramci • lokaln´ procesu, u ktereho doˇslo k výpadku ´ u˚ pro pouˇzit´ı procesy, – je zapotˇreb´ı vhodný algoritmus alokace ramc ´ ´ ´ ı – tj. bez ohledu na to, kteremu • globaln´ procesu patˇr´ı ktera´ stranka.

´ udrˇzovan ´ urˇcitý poˇcet volných ramc ´ u: – Typicky je ale neustale ˚ ´ u˚ klesne pod urˇcitou mez, aktivuje se • Pokud poˇcet volných ramc ˇ stranek“), ´ ˇ z´ı tak dlouho, dokud neuvoln´ı dostateˇcný poˇcet stranek ´ page daemon ( zlodej který beˇ ” ˇ ’ uvolnuje ˇ ´ ´ a´ prostor k behu ˇ (pˇr´ıp. pamet po cˇ astech a dav ostatn´ım procesum). ˚ ´ ´ ´ u. • Pˇri výpadku stranky se pak pouˇzije ramec z mnoˇziny volných ramc ˚ ˇ e´ stranky ´ ˇ ı a zjist´ı-li se, zˇ e byla • Lze doplnit heuristikou, kdy cˇ erstveˇ uvolnen se okamˇziteˇ nepˇridel´ ´ ´ a´ obet ˇ ’, lze je snadno vratit ´ pˇr´ısluˇsnemu procesu k pouˇzit´ı. zvolena nespravn



ˇ odkladan ´ ´ Algoritmy vyb ´ eru ych ´ stranek – FIFO:

udržuje seznam stránek ve frontě, odstraňuje stránky ze začátku fronty, nové stránky k uvolnění jsou na konec fronty

• Jednoducha´ implementace. ´ cˇ asto pouˇz´ıvanou stranku. ´ • Muˇ ˚ ze odstranit starou“, ale stale ” ´ ı. • Trp´ı tzv. Beladyho anomali´

správně by při větším množství volných rámců mělo docházet k méně výpadkům, u tohoto algoritmu však může nastat i opačná situace

ˇ ım uvolnen ˇ eho ´ ´ ´ u, ˇ ım • Lze uˇz´ıt v kombinac´ı s pˇrem´ısten´ ramce do mnoˇziny volných ramc ˚ pˇridelen´ ´ ´ ´ ˇ prav ´ eˇ uvolnen´ ˇ y ramec ´ ´ ´ výpadku jineho volneho ramce a moˇznost´ı ihned z´ıskat zpet pˇri nasledn em ´ a´ obet ˇ ’“. signalizuj´ıc´ım, zˇ e byla zvolena nespravn ” ´ Operaˇcn´ı systemy


– LRU (Least Recently Used): ´ a´ nejdele ´ nepouˇzitou stranku. ´ • Odklad ´ ´ ıho algoritmu (tj. algoritmu, který by znal budoucnost • Velmi dobra´ aproximace hypotetickeho idealn´ ´ eˇ odloˇzit tak, aby poˇcet výpadku˚ byl a podle budouc´ıch poˇzadavku˚ rozhodoval, co aktualn ´ ı). v budoucnu minimaln´ ˇ ´ ı problemy ´ ´ ymi poli, spolu se snahou takove´ – Nekdy se uvad´ s cyklickými pruchody rozsahl´ ˚ ´ st’ napˇr. strategi´ı odstranen´ ˇ ı naposledy pouˇzite´ stranky ´ pˇr´ıstupy detekovat a ˇreˇsit zvlaˇ (most recently used – MRU). ´ ı stranek ´ • Problematicka´ implementace vyˇzaduj´ıc´ı výraznou HW podporu (oznaˇcovan´ cˇ asovým ´ ı zasobn´ ´ ´ raz´ıtkem posledn´ıho pˇr´ıstupu, udrˇzovan´ ıku stranek, jehoˇz vrcholem je naposledy pouˇzita´ ´ stranka).

• Pouˇz´ıvaj´ı se aproximace LRU.



ˇ ıho bitu stranek ´ – Aproximace LRU pomoc´ı omezene´ historie referencn´ (page aging): ´ ´ pˇr´ıstupu, • Referenˇc´ı bit stranky je HW nastaven pˇri kaˇzdem ´ ´ • jadro si vede omezenou historii tohoto bitu pro jednotlive´ stranky,

• periodicky posouva´ obsah historie doprava, ˇ s´ı pozici uloˇz´ı aktualn´ ´ ı hodnotu referenˇcn´ıho bitu a vynuluje ho, • na nejlevejˇ ˇ ’ je vybrana ´ ´ • obet jako stranka s nejniˇzsˇ ´ı cˇ ´ıselnou hodnotou historie. ´ ame-li ´ ´ ´ – Uklad 4 bity historie a mame stranky s histori´ı 0110 a 1100, odstran´ıme prvn´ı z nich ˇ s´ı bit je posledn´ı reference). (nejlevejˇ



ˇ – Aproximace LRU algoritmem druhe´ sance: ´ ´ seznamu, postupujeme a nulujeme referenˇcn´ı bit, odstran´ıme prvn´ı stranku, ´ • Stranky v kruhovem ´ ktera´ jiˇz nulový referenˇcn´ı bit ma. ˇ ´ z oznaˇcovaný jako tzv. clock algorithm). • Casto pouˇz´ıvaný algoritmus (teˇ



ˇ – Modifikace algoritmu druhe´ sance: ˇ ı nemodifikovaných stranek ´ ˇ ı (modifikovane´ se zap´ısˇ ´ı na disk a dostanou • upˇrednostnen´ jako obet´ dalˇs´ı sˇ anci), ´ ıc´ı frontou s urˇcitým rozestupem – jeden nuluje referenˇcn´ı bit, druhý • dva ukazatele prochazej´ ˇ ˇ (tzv. double-handed clock algorithm), odstranuje obeti

• Linux: ˇ a´ dvakrat ´ behem ˇ ´ ´ jedne´ periody – fronty aktivn´ıch“ a neaktivn´ıch“ stranek: stranka zpˇr´ıstupnen ” ” ´ ı referenˇcn´ıch bitu˚ a odklad ´ an´ ´ ı neaktivn´ıch stranek ´ nulovan´ se pˇresouva´ do fronty aktivn´ıch ´ ˇ ˇ stranek, z aktivn´ı fronty se odstranuje do neaktivn´ı, z neaktivn´ı se pak vyb´ıraj´ı obeti, ´ se snaˇz´ı nejprve odkladat ´ ´ ´ ˇ pˇri urˇcitem ´ – system stranky pouˇzite´ pro ruzn ı pameti; ˚ e´ vyrovnavac´ ´ ˇ an´ ´ ı jejich stranek: ´ ´ ı procesy poˇctu stranek namapovaných procesy pˇrejde na odstranov prochaz´ ´ ´ stn´ıch seznamu), snaˇz´ı se odstranit vˇzdy alesponˇ urˇcitý poˇcet a jejich stranky (propojene´ ve zvlaˇ ´ ˇ ´ ´ stranek z procesu, neodstranuje stranky z aktivn´ıho seznamu (nebo alesponˇ referencovane), ´ ı odklad ´ an´ ´ ı po urˇcitých poˇctech projdených a odloˇzených stranek, ´ – provad´ agresivita se zvyˇsuje ˇ s rostouc´ım nedostatkem pameti, ´ ´ ˇ ˇ – tzv. swap token“: stranky procesu, kteremu je tato znaˇcka udelena, jsou pˇreskoˇceny pˇri výberu ” ˇ ı, obet´ ´ nedostatku pameti ˇ ukonˇcuje nekter ˇ – pˇri kritickem e´ procesy.



´ ´ Alokace ramc u˚ procesum ˚ (resp. jadru) ˇ an´ ´ ı ramc ´ u˚ procesum ´ ´ ´ ım výberu ˇ obet´ ˇ ı, kde ˇr´ıd´ı – Pˇridelov je významne´ zejmena pˇri lokaln´ ˚ (resp. jadru) při malém počtu dostupných rámců nemá ˇ ı mnoˇziny ramc ´ u, ´ ´ ı lokaln´ ´ ı výmeny. ˇ pˇridelen´ kterých se pak provad´ ˚ v ramci obětování příliš velký efekt

´ ıho výberu ˇ lze pouˇz´ıt pro ˇr´ızen´ı výberu ˇ obet´ ˇ ı. – U globaln´ ˇ ´ ı poˇcet ramc ´ u˚ pro proveden´ı jedne´ instrukce: jinak dojde – Je tˇreba m´ıt vˇzdy pˇridelen minimaln´ ´ ˇ an´ ´ ı stranek ´ k nekoneˇcnemu vymeˇ nov potˇrebných k proveden´ı instrukce. ´ se uˇz´ıvaj´ı ruzn ´ u˚ pro procesy (resp. jadro): ´ – Dale ˚ e´ heuristiky pro urˇcen´ı poˇctu ramc ´ ern ˇ eˇ k velikosti programu, priorite, ˇ objemu fyzicke´ pameti, ˇ ... • Um ´ ´ ´ ´ • Na zaklad eˇ pracovn´ı mnoˇziny stranek, tj. mnoˇziny stranek pouˇzitých procesem (resp. jadrem) za urˇcitou dobu (aproximace s pomoc´ı referenˇcn´ıho bitu). ´ ´ ı frekvence vypadk • Pˇr´ımo na zaklad eˇ sledovan´ ´ u˚ v jednotlivých procesech.



ˇ an´ ´ ı ramc ´ u˚ s vyuˇzit´ım pracovn´ı mnoˇziny a kombinace lokaln´ ´ ı a globaln´ ´ ı výmeny ˇ pouˇz´ıvaj´ı – Pˇridelov ˇ s´ı systemy ´ novejˇ Windows: ´ ´ ı a maximaln´ ´ ı poˇcet ramc ´ u˚ (meze velikosti pracovn´ı mnoˇziny), • Procesy a jadro maj´ı jistý minimaln´ ˇ se jim ramce ´ ´ ı aˇz po dasaˇzen´ı maxima (pˇr´ıp. se povol´ı i – pˇri dostatku pameti pˇri potˇrebeˇ pˇridavaj´ ˇ sen´ı maxima), zvetˇ ˇ se uplatn´ı lokaln´ ´ ı výmena, ˇ – pˇri dosaˇzen´ı maxima, nen´ı-li nadbytek pameti, ´ nedostatku volných ramc ´ u˚ se do vytvoˇren´ı patˇriˇcne´ zasoby ´ ´ u˚ system ´ – pˇri výraznem volných ramc ˇ odeb´ırat procesum snaˇz´ı (s agresivitou rostouc´ı s rostouc´ım nedostatkem pameti) ˚ urˇcitý poˇcet ´ ´ ´ a´ jim dalˇs´ı v posledn´ı dobeˇ nepouˇzitých stranek (u pouˇzitých stranek nuluje referenˇcn´ı bit a dav sˇ anci). ˇ obet´ ˇ ı dav ´ a´ pˇrednost vetˇ ˇ s´ım procesum ˇ z´ıc´ım men ´ eˇ cˇ asto; vyhýba´ se procesum, • Pˇri výberu ktere´ ˚ beˇ ˚ ˇ z´ı na popˇred´ı. zpusobily v posledn´ı dobeˇ mnoho výpadku˚ a procesu, který beˇ ˚ ˇ v ramci ´ ´ ´ • Obeti v posledn´ı dobeˇ nepouˇzitých stranek vyb´ıra´ na zaklad eˇ omezene´ historie pˇr´ıstupu. ˚ ´ cn´ı meze pracovn´ıch mnoˇzin odvozuje pˇri startu systemu ´ ˇ • Poˇcateˇ z velikosti fyzicke´ pameti. ˇ k jinemu ´ ˇ aby bylo moˇzno korigovat chyby pˇri ˇ se snaˇz´ı nepˇridelit pouˇzit´ı okamˇzite, • Vybrane´ obeti ˇ ı. volbeˇ obet´ ˇ odklad ´ an´ ´ ım (swapovan´ ´ ım) celých procesu˚ (vyb´ıra´ dlouho • Uvedený mechanismus je doplnen neaktivn´ı procesy).



Thrashing ˇ odstranovan´ ˇ ´ – I pˇri rozumne´ volbeˇ výberu ych stranek muˇ ˚ ze nastat tzv. thrashing: Proces (v horˇs´ım ´ ´ ı v´ıce cˇ asu nahradou ´ ´ pˇr´ıpadeˇ system) strav´ stranek neˇz uˇziteˇcným výpoˇctem.

´ znem ´ nedostatku pameti ˇ swapper pozastav´ı nekter ˇ ˇ ’. – Pˇri vaˇ e´ procesy a odloˇz´ı veˇskerou jejich pamet ˇ – Jinou moˇznost´ı je ukonˇcen´ı nekter´ ych procesu. ˚



´ Poznamky ´ et ˇ do systemu ´ ´ ´ – Prepaging: snaha zavad v´ıce stranek souˇcasneˇ (zejmena pˇri startu procesu cˇ i po ´ ı, ale i za beˇ ˇ zne´ cˇ innosti s ohledem na pˇredpokladanou ´ odswapovan´ lokalitu odkazu). ˚ načte z disku větší blok dat "do zásoby", může se však stát, že se načtou nepotřebná data

´ ı stranek: ´ – Zamykan´ ˇ • zabranuje odloˇzen´ı,

• uˇz´ıva´ se napˇr. – – – –

´ u stranek, do nichˇz prob´ıha´ I/O, ´ ı) tabulek stranek, ´ u (ˇcast´ ˇ ´ ´ u (nekter´ ych) stranek jadra, ´ ´ ı uˇzivatele (k jeho vyjadˇ ´ ren´ı slouˇz´ı v POSIXu – v ramci pˇrednastavených limitu˚ a na pˇran´ ´ en´ ˇ ı – volan´ ´ ı mlock()): citliva´ data, (soft) real-time procesy. opravn



´ Sd´ılen´ı stranek stránky, které se nacházejí v LAP různých procesů, jsou namapovány na stejný rámec fyzické paměti

´ ´ ı umoˇznuje ˇ ˇ – Strankov an´ jemnou kontrolu sd´ılen´ı pameti.

´ – Sd´ılen´ı stranek: ´ programu˚ (procesy ˇr´ızene´ stejným programem, sd´ılene´ knihovny), • kod

• konstantn´ı data nebo doposud nemodifikovana´ data u kopi´ı procesu˚ (technologie copy-on-write), • mechanismus IPC, ˇ ’oveˇ mapovaných souboru. • sd´ılen´ı pamet ˚



Sd´ılene´ knihovny

´ který je v dane´ verzi v FAP (a na disku) maximaln ´ eˇ jednou a – Sd´ılene´ knihovny ( .dll, .so): kod, muˇ ˚ ze být sd´ılen v´ıce procesy (procesy nemus´ı být ˇr´ızeny stejným programem). ´ • Výhody: menˇs´ı programy – lepˇs´ı vyuˇzit´ı FAP i diskoveho prostoru, moˇznost aktualizovat knihovny. ´ programu˚ na dalˇs´ıch souborech a verz´ıch knihoven, moˇzný pomalejˇs´ı start • Nevýhody: zavislost programu (je nutne´ dynamicky sestavit; na druhou stanu se ale zase muˇ ˚ ze uˇsetˇrit d´ıky nutnosti ´ et ˇ jiˇz zavedene´ stranky). ´ nezavad



Copy-on-Write

ˇ ı procesu pomoc´ı – Pˇri spuˇsten´

ˇ procesu. fork se nevytvoˇr´ı kopie veˇskere´ pameti

´ ´ – Vytvoˇr´ı se pouze tabulky stranek a stranky se poznaˇc´ı jako copy-on-write. ´ ´ – K vytvoˇren´ı fyzicke´ kopie stranky dojde aˇz pˇri pokusu o zapis jedn´ım z procesu. ˚

´ – Poznamka:


ˇ ’ je skuteˇcneˇ sd´ılena. vfork jako alternativa k fork s copy-on-write: pamet


ˇ ’ (shared memory) Sd´ılena´ pamet

´ stejne´ fyzicke´ stranky ´ – Forma IPC: V´ıce procesu˚ ma´ mapovany do LAP. –

shmget, shmat, shmctl, shmdt

Pˇr´ıklad: GIMP plugin



ˇ ’oveˇ mapovane´ soubory Pamet ´ do stranek ´ ˇ – Bloky souboru˚ jsou mapovany v pameti. ´ ´ ım na zˇ adost ´ ´ ach ´ do pameti ˇ a dale ´ muˇ ´ se – Soubory jsou strankov an´ naˇcteny po strank ˚ ze být prace ´ ˇ nam´ısto pouˇzit´ı read()/ write(). soubory realizovana standardn´ım pˇr´ıstupem do pameti ˇ r´ı se reˇzie se systemov´ ´ ´ ım, kop´ırovan´ ´ ı do bufferu a pak do pameti. ˇ Umoˇznuje ˇ – Setˇ ym volan´ sd´ılený pˇr´ıstup k souborum. ˚

´ ı – Dostupne´ prostˇrednictv´ım volan´ ´ Operaˇcn´ı systemy

mmap(). ´ pameti ˇ Sprava 40

ˇ ’ove´ regiony Pamet ˇ ’ove´ regiony jsou jednotkou vyˇssˇ ´ıho strukturovan´ ´ ı pameti ˇ v Unixu (pouˇz´ıvaj´ı se i dalˇs´ı: napˇr. – Pamet uzly - úsek paměti, ke kterému různé procesory přistupují různě ´ v Linuxu tzv. uzly a zony).

zóny - používají se pro odlišení části paměťového prostoru, se kterým pracuje HW nebo jádro

´ ı pameti ˇ pouˇzite´ za urˇcitým uˇ – Jedna´ se o spojite´ oblasti virtualn´ ´ celem (data – staticka´ inicializovana´ ´ zasobn´ ´ ´ eˇ mapovane´ pamet ˇ ’i – data, staticka´ neinicializovana´ data, hromada; kod; ık; useky individualn ´ ˇ ’, pamet ˇ ’oveˇ mapovane´ soubory, anonymn´ı mapovan´ ´ ı). sd´ılena´ pamet

´ ıc´ı pozici regionu v LAP procesu, pˇr´ıstupova´ – Kaˇzdý proces muˇ ˚ ze m´ıt tabulku regionu˚ procesu udavaj´ ´ ´ k regionu a odkazuj´ıc´ı na systemovou tabulku regionu˚ s dalˇs´ımi informacemi o reginu, sd´ılenými prava mezi procesy – pˇr´ıpadneˇ ma´ kaˇzdý proces vˇsechny potˇrebne´ udaje pˇr´ımo ve sve´ tabulce regionu. ´ ˚ ´ ´ – V systemov e´ tabulce regionu˚ je uvedena velikost regionu, typ, i-uzel souboru pˇr´ıpadneˇ mapovaneho do regionu apod.

´ muˇ ´ et ˇ nad regionem jako celkem nekter ˇ ˇ sovan´ ´ ı/zmenˇsovan´ ´ ı (u – System e´ operace: zvetˇ ˚ ze provad ´ ´ ı, mapovan´ ´ ı do pameti ˇ aj. datoveho regionu) brk, swapovan´



´ Rozloˇzen´ı adresoveho prostoru procesu v Linuxu (i386) pro 32b instalace

(Anatomy of a Program in Memory, G. Duarte)

adresový prostor jádra

zásobník pro aktivační záznamy vyvolávaných funkcí

část adresového prostoru používaná pro anonymně mapované úseky paměti či paměťově mapované soubory část LAP, se kterou proces může pracovat

region pro dynamickou alokaci

neinicializovaná statická data

statická data (globální inicializované proměnné) kód, který řídí proces



ˇ Bezpecnost v OS ´ s Vojnar Tomaˇ

[email protected]

Vysoke´ uˇcen´ı technicke´ v Brneˇ Fakulta informaˇcn´ıch technologi´ı ˇ Boˇzetechova 2, 612 66 BRNO ˇ 2. kvetna 2011


ˇ Bezpecnost (Security) ´ zahrnuje: – Informaˇcn´ı/výpoˇcetn´ı system

• hardware (poˇc´ıtaˇce, aktivn´ı a pasivn´ı s´ıt’ove´ prvky, ...), • software (OS a aplikace), • data, ´ spravci, ´ • lidi (uˇzivatele, ...).

– Jiný pohled na IS:

• objekty (pasivn´ı entity: data, sluˇzby, ...) a ´ ...). • subjekty (aktivn´ı entity: procesy, uˇzivatele,


Bezpeˇcnost 1

´ pˇred: – IS je zapotˇreb´ı chranit ´ ...), ´ • zasahy ”vyˇssˇ ´ı moci”(pˇr´ırodn´ı katastrofa, poˇzar,

• chybami lid´ı, SW cˇ i HW a • c´ılenymi ´ utoky ´ ze strany lid´ı.

ˇ s´ı. – Zabezpeˇcen´ı pˇred c´ılenými utoky je obt´ızˇ nejˇ ´

ˇ ı bezpeˇcnosti nen´ı stav, ale nikdy nekonˇc´ıc´ı proces! – Zajiˇsten´


Bezpeˇcnost 2

ˇ ı bezpeˇcnosti (ochrana) zahrnuje: – Zajiˇsten´ ˇ ı dat nepovolaným osobam, ´ ˇ en´ ˇ ı duv ˇ • zajist ˚ ernosti, tj. ochranu proti zpˇr´ıstupnen´ ˇ ´ ˇ en´ ˇ ı integrity, tj. ochranu pˇred nepovolenou zmenou • zajist dat/kodu, ´ nemuˇ ´ ˇ en´ ˇ ı dostupnosti, tj. system • zajist ˚ ze odepˇr´ıt pˇr´ıstup povolaným osobam, ´ ı apod. ´ • zamezen´ı neautorizovaneho vyuˇzit´ı zdroju, ˚ tj. obejit´ı uˇ ´ ctovan´ ´ ı, uˇ ´ ı (logovan´ ´ ı), audit, ... – Funkce prosazuj´ıc´ı bezpeˇcnost: autentizace, autorizace, utajovan´ ´ ctovan´


Bezpeˇcnost 3

Autentizace

ˇ rovan´ ´ ı pravosti identity entity – procesu, uˇzivatele, poˇc´ıtaˇce, ... (Kdo je kdo?) – Autentizace: oveˇ – Autentizace muˇ ˚ ze být zaloˇzena na:

• vlastnictv´ı kl´ıcˇ e, karty, ..., ´ • znalosti pˇrihlaˇsovac´ıho jmena, hesla, ..., cˇ i

• vlastnosti uˇzivatele (otisk prstu, duhovka, s´ıtnice, ...).

´ – Utoky na autentizaci: ´ an´ ´ ı paketu, ´ ... • obejit´ı autentizace – vklad ˚ zadn´ı vratka,

vyhýbá se autentizaci, snaží se vniknout tajně

´ ı autentizace – monitorovan´ ´ ı, pokus/omyl, odpadky, ... • pˇrekonan´


např. útok hrubou silou

Bezpeˇcnost 4

Hesla

– Uloˇzen´ı hesel: ´ ı se zakodovan ´ ˇ ´ • Ukladaj´ a´ vhodnou jednosmernou hashovac´ı funkc´ı f (x) – ochrana i v ramci ´ systemu. – Unix: funkce

crypt zaloˇzena´ na modifikaci DES, pˇr´ıp. MD5, SHA, ...

• Výpoˇcet f −1(x) mus´ı být velmi obt´ızˇ ný. ˇ ren´ı hesla nesm´ı být pˇr´ıliˇs rychle´ (moˇzno vloˇzit zpoˇzden´ ˇ ı). • Samotne´ oveˇ ´ en´ ˇ ı pokusum ´ • Ani zaˇsifrovana´ hesla nemaj´ı být volneˇ pˇr´ıstupna´ – zabran ı hesla: ˚ o uhadnut´ /etc/passwd ⇒ /etc/shadow.


Bezpeˇcnost 5

´ ˇ ruj´ıc´ı na pˇrekonan´ ´ ı hesla: – Utoky smeˇ

• pokus/omyl hrubou silou, ´ ´ • uhadnut´ ı hesla (jmeno uˇzivatele, slova ze slovn´ıku... ⇒ generovana´ hesla), – utilita

crack,

´ • nalezen´ı poznamenaneho hesla,

• zachycen´ı hesla na s´ıti (⇒ uˇz´ıvat ssh apod.), ´ ı pˇri vklad ´ an´ ´ ı, ... • odpozorovan´


Bezpeˇcnost 6

´ ´ – Je rozumne´ omezit cˇ asovou platnost hesel: ale nepˇrehnat (podobneˇ jako u delky generovaneho ´ k poznamenav ´ an´ ´ ı si hesel... hesla), muˇ ˚ ze vest

´ ´ ´ ıho cˇ asu – spoleh ´ a´ na ´ – Jednorazov a´ hesla: vypoˇctena´ na zaklad eˇ výzvy systemu (nebo z aktualn´ ´ dostateˇcneˇ pˇresnou synchronizaci cˇ asu komunikuj´ıc´ıch stran) pomoc´ı bezpeˇcneˇ uloˇzeneho kl´ıcˇ e ´ ´ (v sˇ ifrovac´ım kalkulatoru) cˇ i pˇrevzata´ z kodov e´ knihy.

´ ı se opakovanemu ´ ena ˇ ´ ´ an´ ´ ı hesla (pokud je ˇrada jednotlivých zdroju˚ chran – Vyhýban´ zadav ´ ´ a´ na zˇ adost ´ nezavisle): autentizaˇcn´ı sluˇzby typu Kerberos (specializovaný server vydav doˇcasne´ ´ chran ´ en ˇ e´ jejich kl´ıcˇ i). pˇr´ıstupove´ kl´ıcˇ e, ktere´ pˇreda´ komunikuj´ıc´ım stranam


Bezpeˇcnost 7

Autorizace

– Autorizace: povolen´ı pouˇzit´ı urˇcitých objektu˚ pouze urˇcitým subjektum, a to pouze k urˇcitým ˚ ˇ operac´ım. (Kdo muˇ ˚ ze co delat?) ´ – Plný zapis moˇzný pomoc´ı pˇr´ıstupove´ matice (access matrix):

´ pro skupiny uˇzivatelu. – Moˇzno kombinovat s pˇr´ıstupovými pravy ˚


Bezpeˇcnost 8

– Implementace pˇr´ıstupove´ matice: ´ ´ subjektu. • pˇr´ıstupove´ seznamy (access control lists): ke kaˇzdemu objektu seznam prav ˚ ´ ´ Napˇr. ochrana pˇr´ıstupu k souborum ı Unixova´ prava, ˚ ve Windows NT, v omezene´ podobeˇ zakladn´ v Linuxu a dalˇs´ıch Unixech existuj´ıc´ı rozˇs´ıˇren´ı tohoto mechanismu na obecne´ pˇr´ıstupove´ seznamy – viz setfacl, ...

• seznamy povolenych ´ operac´ı (capability lists): se subjekty jsou spojeny seznamy operac´ı povolených nad objekty. ˇ ı rozliˇsen´ı procesu˚ v Linuxu a dalˇsich Unixech z privilegovaný/neprivilegovaný Napˇr. zjemnen´ ˇ an´ ´ ım povolených operac´ı (muˇ ´ et ˇ zmeny ˇ UID/GID, zamykat stranky ´ pˇridelov ˚ ze/nemuˇ ˚ ze provad ´ ı soubory, zas´ılat broadcast, ... – viz man capabilities) ˇ vytvaˇ ´ ret specialn´ v pameti,


Bezpeˇcnost 9

ˇ Nekter e´ typy utok ´ u˚ ´ zneuˇzitelna´ funkce programu (zvlaˇ ´ st’ nebezpeˇcne´ v pˇrekladaˇci). ´ – Zadn´ı vratka: nedokumentovana, ´ ı nav´ıc nejakou ˇ ˇ program, který provad´ – Trojsky´ ku˚ n: sˇ kodlivou funkci. ´ programu pro dosaˇzen´ı ˇ ı vyrovnavac´ ´ ˇ ı: vyuˇzit´ı chyby v privilegovanem – Pˇretecen´ ıch pamet´ ´ ´ ı ˇr´ızen´ı podstrˇcenemu ´ ´ sˇ kodliveho efektu (pˇr´ımý sˇ kodlivý efekt, pˇredan´ kodu, ...). ´ který infikuje jine´ programy a pomoci nich se sˇ ´ıˇr´ı. – Virus: kod, ˇ ´ poˇc´ıtaˇcovou s´ıt´ı. – Cerv: program podobný viru, nepotˇrebuje vˇsak hostitelský program, sˇ ´ıˇr´ı se sam ´ ´ ´ – Denial of Service: pˇret´ızˇ en´ı napadeneho poˇc´ıtaˇce napˇr. zaplavou zprav. ´ ´ an´ ´ ı paketu: – Vklad ˚ podvrˇzen´ı paketu˚ do otevˇreneho spojen´ı na s´ıti. ´ e´ vyuˇzit´ı der ˇ ve sluˇzbach ´ typu ftp/21, ssh/22, ... ´ ı a vyuˇzit´ı der: ˇ vzdalen – Scanovan´ ´ od ”spravce”se ´ ´ ˇ e´ akce. – Dopisn´ı bomby: zprava zˇ adost´ ı o proveden´ı nejak – ...


Bezpeˇcnost 10

´ Obecne´ zasady pro ochranu ´ ı verze OS (security updates pro Windows, Linux, ...). – Pouˇz´ıvat aktualn´

www.cert.org, www.securityfocus.com, www.microsoft.com/security, www.mcafee.com, www.symantec.com, ...

´ ´ – Sledovat oznamen´ ı o chybach:

ˇ nic nezbytneho. ´ ´ ı sadu systemov ´ – Instalovat minimaln´ ych ´ sluˇzeb, neinstalovat a nespouˇstet ´ eˇ ˇ z s´ıte, ˇ skenovan´ ´ ı – Monitorovat provoz za uˇ ´ celem odhalen´ı bezpeˇcnostn´ıch slabin cˇ i utok ´ u˚ (zat ´ ´ ı uˇzivatelu, ´ portu, e´ logy, pˇrihlaˇsovan´ ych programu˚ – kontroln´ı souˇcty, ˚ systemov ˚ modifikace systemov´ ´ ´ dlouho beˇ ˇ z´ıc´ı procesy, pouˇzit´ı nevhodných hesel, nepovolene´ SUID programy, neoˇcekavan e, ´ ´ r´ıch, nespravn ´ a´ pˇr´ıstupova´ prava ´ adresaˇ ´ ru˚ a souboru,...). nepovolene´ programy v systemov´ ych adresaˇ ˚ ´ Zaznamy analyzovat ruˇcneˇ cˇ i automatizovaneˇ ( tripwire, aide, snort, ...). ˇ spojen´ı dovnitˇr s´ıte. ˇ ˇ s´ ˇ ı pˇr´ıstup, nepouˇstet – Omezit vnej ´ et ˇ filtrovan´ ´ ı posty, ˇ – Provad u Windows pouˇz´ıvat pravidelneˇ aktualizovane´ antivirove´ programy. ´ s podivneˇ vyhl´ızˇ ej´ıc´ımi“ Internetovými strankami, ´ ´ – Konzervativnost pˇri praci emaily, telefonaty ” ´ ı citlivých udaj vyˇzaduj´ıc´ımi zadan´ ´ u, ˚ proveden´ı citlivých operac´ı.


Bezpeˇcnost 11

Firewall – Firewall monitoruje, loguje a omezuje s´ıt’ove´ spojen´ı podle nastavených pravidel.

– Firewall nezastav´ı vˇsechny typy utok tuneluj´ıc´ı v povolených protokolech, denial of service, ´ u: ˚ utoky ´ ´ ı jiných adres (address spoofing), ... pˇredst´ıran´


Bezpeˇcnost 12

Kryptografie Kryptografie je nauka o metodách utajování smyslu zpráv převodem do podoby, která je čitelná jen se speciální znalostí. (wiki)

ˇ ı: – Vyuˇzit´ı pˇri zajiˇsten´ ´ ˇ ı), ´ ı informace (ochrana proti neautorizovanemu • utajovan´ zpˇr´ıstupnen´ ˇ e), ˇ • integrity informace (ochrana proti neautorizovane´ zmen

• autentizace, • nepopiratelnosti informace.

– Kryptografický mechanismus je tvoˇren: ˇ ´ ı a desifrov ˇ ´ ı, • algoritmy pro sifrov an´ an´ ˇ ˇ • kl´ıcem nebo kl´ıci.


Bezpeˇcnost 13

– Symetricka´ kryptografie – kryptografie se sd´ıleným tajným kl´ıcˇ em (mj. DES sˇ ifruj´ıc´ı bloky 64b ˇ s´ı AES 128b x 128-256b, ...). kl´ıcˇ em 56b, novejˇ Vyuˇzit´ı pro utajen´ı, integritu, autentizaci.

– Asymetricka´ kryptografie – odliˇsne´ kl´ıcˇ e komunikuj´ıc´ıch stran, napˇr. kryptografie s veˇrejným a soukromým kl´ıcˇ em (napˇr. RSA s kl´ıcˇ em alesponˇ 1024b). Vyuˇzit´ı pro utajen´ı, integritu, autentizaci a nepopiratelnost.

´ ı soukromeho ´ ´ – Asymetricka´ kryptografie je zaloˇzena na tom, zˇ e z´ıskan´ kl´ıcˇ e z veˇrejneho (a/nebo ´ ˇ ´ cn ˇ e, ´ zˇ e je to prakticky nemoˇzne´ (rozklad na souˇcin zaˇsifrovane´ zpravy) je vypo ´ cetn eˇ natolik naro prvoˇc´ısel).


Bezpeˇcnost 14

symetrická kryptografie - využívá jednu funkci k zašifrování o rozluštšní klíče asmyterická kryptografie - využívá soukromých a veřejných klíčů - Alice zašifruje zprávu pomocí Bobova veřejného klíče, takovou zprávu lze rozšifrovat pouze Bobovým soukromým klíčem 3. případ - Alice zašifruje zprávu svým soukromým klíčem (obsahuje nezpochybnitelný podpis), lze ji rozšifrovat jejím veřjeným klíčem, což dokazuje, ža autorem zprávy je právě Alice


Bezpeˇcnost 15

ˇ Tˇr´ıdy bezpecnosti

´ – TCSEC (Trusted Computer System Evaluation Criteria, ”Orange Book”): starˇs´ı kriteria americke´ ´ vlady: úrovně zabezpečení:

• D: nezabezpeˇceno, • C: volitelne´ ˇr´ızen´ı pˇr´ıstupu (discretionary access control – DAC): vlastn´ık objektu rozhoduje o ˇ pˇr´ıstupu ostatn´ıch uˇzivatelu˚ k tomuto objektu. Rozdeleno na C1 a C2.

• B: povinne´ ˇr´ızen´ı pˇr´ıstupu (mandatory access control – MAC): o ochraneˇ nerozhoduje vlastn´ık, ´ eˇ a system ´ si ji dokaˇ ´ ze vynutit. Rozdeleno ˇ ta je stanovena globaln na B1, B2 a B3.

• A: matematický model a dukaz korektnosti. ˚ ˇ s´ı evropska´ kriteria. ´ – ITSEC dˇr´ıvejˇ – Dnes tzv. Common Criteria ( http://www.commoncriteriaportal.org).


Bezpeˇcnost 16

SELinux – Security Enhanced Linux

´ u˚ jadra ´ – Podpora pro SELinux je jiˇz zahrnuta do zdrojových kod 2.6. – SELinux implementuje MAC s vyuˇzit´ım:

• Identity-Based Access Control (IBAC) – kaˇzdý proces je spojen s identitou uˇzivatele odvozenou ´ sen´ı (nezavisle ´ ˇ jsou striktneˇ kontrolovany ´ a omezeny. od pˇrihlaˇ na UID, EID), zmeny

• Role-Based Access Control (RBAC) – uˇzivatele´ a jejich procesy maji pˇriˇrazenu mnoˇzinu rol´ı, ˇ jsou striktneˇ kontrolovany ´ a omezeny. zmeny ˇ ı procesum ´ • Type Enforcement (TE) – role umoˇznuj´ vstoupit do urˇcitých domen; ˚ (subjektum) ˚ ´ ´ je moˇzno manipulovat objekty urˇcite´ tˇr´ıdy (soubor, socket, ...) a urˇciteho ´ v ramci urˇcitých domen ´ ıho typu pouze urˇcitým zpusobem. konkretn´ ˚ ´ ı systemu ´ ´ nakonfigurovanou bezpecnostn´ ˇ – Detailn´ı chovan´ je definovano ı politikou s pravidly typu:

# Let sshd bind a TCP socket to the SSH port. allow sshd_t ssh_port_t:tcp_socket name_bind; # Let sshd read the host private key file. allow sshd_t sshd_key_t:file read; ´ Operaˇcn´ı systemy

Bezpeˇcnost 17

# Let sshd create its PID file. allow sshd_t var_run_t:dir { search add_name }; allow sshd_t sshd_var_run_t:file { create write }; type_transition sshd_t var_run_t:file sshd_var_run_t;


Bezpeˇcnost 18

2011. Vysoké učení technické v Brně Fakulta informačních technologií Božetěchova 2, Brno. Úvod p

Recommend Documents