FAV wiki - Příspěvky uživatele [cs]

Stromové struktury (Avl, BVS, B, Red-Black) a jejich implementace

2015-06-10T12:41:59Z

95.47.186.95: /* B-strom */

Strom je ADT uchovávající prvky v hierarchické struktuře předcůdce-následovník. Použití v reprezentaci znalostí a stavového prostoru, popis scény při zpracování obrazu, v databázových systémech, systémech souborů, pro rozhodovací stromy, komprese dat, raytracing.

* '''Obecné stromy''' - uzly mohou mít libovolný počet následovníků. Implementace pomocí ukazatelů, ve vrcholech spojový seznam následovníku.
* '''N-ární stromy''' - uzel má nejvýše n následovníků. Implementace ukazateli, ve vrcholech pole následovníků.
* '''Binární stromy''' - uzel má nejvýše dva následovníky. Implementace ukazateli a výčtem následovníků, případne polem.

Binární strom, kde nalevo od každého prvku jsou k prvky s nižším klíčem a napravo s vyšším (příp. obráceně), je binární vyhledávací strom (BVS). Kořenem obyčejného BVS je první vložený prvek, další prvky se vkládají nalevo nebo napravo od něj. Při postupném vkládání seřazené posloupnosti ale takový strom degraduje na lineární seznam, což zvyšuje složitost vyhledávání. Proto je na místě snaha o vyvážení stromu.

== AVL ==

(Adelson-Velsky, Landis)

BVS zachovávající pravidlo, že podstromy každého vrcholu se mohou výškou lišit nejvýše o 1. Vyvážení kontrolováno po každém vložení a výberu. Vrchol obsahuje navíc položku informující o rozdílu výšek obou jeho podstromu (-2, -1 levá strana, 0 vyvážený, 1, 2 pravá strana). Vložení stejné jako u BVS, po vložení prepocet rozdílu výšek (v každém kořenu na cestě z vloženého prvku do kořenu stromu sledujeme, jak se jeho vyvýžení změní). Při nevyváženosti v některém vrcholu rotace v tomto vrcholu.

Rotace:
* '''Jednoduchá''' - nevyváženost způsobuje levá větev levého podstromu nebo pravá větev pravého podstromu. Kontrolujeme, zda kořen podstromu má stejné znamínko jako kořen nadstromu ???
* '''Dvojitá''' - nevyváženost způsobuje pravá vetev levého podstromu nebo levá větev pravého podstromu. Provedeme nejdříve rotaci spodní větve, a tím se dostaneme na předchozí problém.

Odebrání stejné jako u BVS - nahrazení prvku symetrickým následovníkem, po odstranění prvku prepočty rozdílu výšek kontrola vyváženosti smerem ke kořeni (od původní pozice symetrického následovníka - prvky prohozeny a zde odstraňován).

// přidat obrázek

== Red-Black ==

Další modifikace BVS. Vrcholy obsahují navíc položku s informací o barve (cervená nebo cerná).
Pravidla:
koren je vždy cerný,
cesty od korene do každého listu obsahují stejný pocet cerných vrcholu (cerná výška stromu),
cervený vrchol má pouze cerné následovníky.

Vkládaný vrchol je na zacátku vždy cervený, postupne od jeho pozice ke koreni kontrola pravidel a prípadná náprava

- přebarvením vrcholů: pokud je rodič červený a jeho bratr také, oba přebarvíme na černé a jejich rodiče na černé)
- pokud bratr rodiče červený není, přebarvíme na černo pouze rodiče a provedeme rotace
- pokud je rodič levým synem, a vkládaný také, provedeme rotaci do prava (rodič se stane kořenem)
- pokud je rodič levý, ale vkládaný pravý, provedeme nejprve rotaci do leva (vkládaný se stane rodičem) a tím získáme předchozí problém, tedy přebarvíme a zarotujeme do prava podle vkládaného prvku, který se stane kořenem.

Rotace jsou stejné jako u AVL stromu. Odebrání - nahrazení symetrickým následovníkem, ten ale obarven barvou odebíraného vrcholu, a po té postupujeme stejně jako při vkládání, tedy od místa odebrání kontrola pravidel smerem ke koreni.

== B-strom ==

B-strom řádu '''m''' má v každém vrcholu nejvýše m následovníků.

Pravidla:
* klíčů ve vrcholu je o 1 méně než následovníků
* všechny listy jsou stejně hluboko
* všechny vrcholy mají maximálně '''m''' následovníků
* všechny vrcholy kromě kořene mají minimálně m/2 následovníků
* kořen je buď list nebo má alespoň 2 následovníky

Ve vrcholech klíce serazené, vrcholy razeny jako u BVS (menší klíce vlevo, vetší vpravo). Pri vkládání se pridávají klíce do listu, pokud je v listu prekrocen maximální pocet (pretecení stránky), je list rozdelen uprostred a prostrední klíc vložen do rodice (zde opet kontrola prekrocení poctu). Odebereme-li klíc z listu a ten má potom príliš málo podtecení stránky), muže si vypujcit od sousedu (klíc z rodice do vrcholu, klíc ze souseda do rodice), pokud sousedi mají minimální pocet, dojde ke sloucení vrcholu s jedním sousedem a klícem z rodice. Pri odebírání z vnitrních vrcholu je nutné místo vždy zaplnit - klíc od potomka. Nemají-li potomci dost klícu, sloucí se dva potomci do jednoho. Implementace ukazateli s následovníky seznamem nebo polem, prípadne pomocí dvourozmerných polí (jedno pro klíce, jedno pro indexy následovníku, index korenu).

[[Kategorie:fav-kiv-bzinf]]

Prostředky pro synchronizaci procesů

2015-06-10T11:51:16Z

95.47.186.95:

Zakázání přerušení
* V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení
* Zakážeme-li přerušení, k přepínání nedochází
* Nejjednodušší řešení, možné pouze v jednoprocesorovém systému
* Není dovoleno v uživatelském režimu

Řešení s aktivním čekáním
Základní předpoklady o systému:
# Zápis a čtení ze společné datové oblasti jsou nedělitelné operace
# Kritické sekce nemohou mít přiřazenou prioritu
# Relativní rychlost procesů je neznámá
# Proces se může pozastavit mimo kritickou sekci

Průběžně se testuje, zra už může proces do kritické sekce vstoupit - plýtvání časem CPU

Petersonovo řešení
* Na začátku není v kritické sekci žádný proces
* Proces 0 volá enter_CS(0)
** Nastaví interested[0]:=true, turn:=0;
** Protože interested[1]=false, nebude čekat ve smyčce
* Pokud proces 1 volá enter_CS(1)
** Nastaví interested[1]:=true, turn:=1;
** Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_CS(0))
* Co kdyby oba procesy volaly enter_CS téměř současně?
** Oba nastaví interested na true
** Oba nastaví turn na své číslo; „téměř souběžný zápis“ se ale provede sekvenčně, tj. nejdříve nastaví turn jeden, hodnota bude přepsána druhým
** Oba se dostanou do while, proces 0 projde, proces 1 aktivně čeká

Spin-lock s instrukcí TSL

Většina současných počítačů má instrukci, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (TSL - „Test and Set Lock“) - HW podpora

* Proměnná zámek - na počátku 0
* Proces, který chce vstoupit do KS otestuje
** Pokud 0 nastaví na 1 a vstoupí do KS
** Pokud 1 čeká
* Problém časového souběhu (pokud by TSL nebyla atomická):
** Jeden proces přečte, vidí 0
** Druhý proces je naplánován, přečte, vidí 0, nastaví na 1, vstoupí do KS
** Po naplánování první zapíše 1 a máme 2 procesy v KS
* Řešení vyžaduje HW podporu

Další možnosti
* [[Semafory, jejich použití a implementace|Semafory]]
* Mutexy - někdy nepotřebujeme použít schopnost semaforů čítat, tj. stačila by nám pouze jejich schopnost zajistit vzájemné vyloučení => mutex
* [[Monitory]]

Předávání zpráv - primitiva send a receive
# Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.
# Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.

----

== Synchronizační primitiva ==

jsou v operačních systémech prostředky, umožňující zároveň běžícím
aplikacím ošetřit současný přístup ke sdíleným prostředkům. Ve smyslu algoritmu se jedná o rozhraní
a jeho implementace není důležitá.

Chybné použití synchronizačních primitiv může vést k jejich '''neúčinnosti''' (tedy k prostředku stejně
mohou přistoupit dva procesy najednou) nebo k '''deadlocku''' (vzájemnému zablokování).

'''Deadlock''' (česky také uváznutí) je odborný výraz pro situaci, kdy úspěšné dokončení nějaké akce je
podmíněno předchozím dokončením jiné akce, přičemž tato jiná akce může být dokončena až po
dokončení původní akce. Vzniká paradox, často označovaný jako ''Co bylo dříve? Slepice nebo vejce?''.

V počítači se jedná o zablokování procesů (případně vláken) způsobené čekáním na synchronizačních
primitivech. Obvykle k němu dochází v důsledku chyby při jejich programování. Pokud uváznutí
nastane, řeší se například zrušením transakce (rollback) nebo násilným ukončením procesů.
Některé systémy spoléhají na to, že deadlock nastává zřídka a uživatel si pomůže sám.

=== K uváznutí dojde jen při splnění všech následujících podmínek: ===

* '''Vzájemné vyloučení (Mutual exclusion)'''
Prostředek může v jednom okamžiku používat jenom jeden proces (jinak dojde k chybě).
* '''Drž a čekej (Hold & wait)'''
Proces může žádat o další prostředky, i když už má nějaké přiděleny.
* '''Neodnímatelnost (No preemption)'''
Jakmile proces zmíněný prostředek vlastní, nelze mu ho bezpečně odejmout, musí ho sám vrátit.
* '''Čekání do kruhu (Circular wait)'''
Je možné uzavřít cyklus z procesů čekající každý na svého předchůdce – respektive k deadlocku
dojde, jakmile je tento cyklus uzavřen.

Mezi synchronizační primitiva patří '''zámek''' a jejich zobecnění '''semafory''', '''fronty zpráv''' a '''monitor'''.

'''Zámky a semafory''' bývají implementovány operačním systémem pomocí atomických operací na
sdílené paměti a plánovače.

Pro synchronizaci v paralelním programování stačí atomické operace na sdílené paměti (čekají na
sebe procesy na různých procesorech a tedy mohou čekat aktivně) a je možné je implementovat i bez
pomoci operačního systému.

'''Fronty zpráv''' jsou primitivní operací v případě paralelního programování, ale je možné je
implementovat v operačním systému i na jednom procesoru.

'''Monitor''' je možné realizovat pouze s podporou programovacího jazyka.

Korektní paralelní program - Nutné podmínky
# Dva procesy se nesmí nacházet současně ve stejné sdružené sekci.
# Žádné předpoklady nesmí být kladeny na rychlost a počet procesorů.
# Pokud proces běžící mimo kritickou sekci nesmí být blokován ostatní procesy.
# Žádný proces nesmí do nekonečna čekat na vstup do kritické sekce

{{fav-kiv-bzinf}}

[[Kategorie:fav-kiv-bzinf]]

Problém uvíznutí procesů, graf alokace zdrojů

2015-06-10T11:25:43Z

95.47.186.95:

V množině procesů nastalo uvíznutí, jestliže každý proces množiny čeká na událost, kterou může způsobit pouze jiný proces množiny. Protože všechny čekají, žádný z nich událost nevygeneruje, nevzbudí jiný proces.

== Podmínky vzniku uvíznutí ==
(musejí být splněny všechny 4, 1-3 jsou předpoklad pro 4):
# Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu
# „hold and wait“: proces držící výhradně přiřazené zdroje může požadovat další zdroje
# Nemožnost odejmutí: jednomu přiřazené zdroje nemohou být procesu násilně odejmuty
# Cyklické čekání: musí být cyklický řetězec dvou nebo více procesů, kde každý z nich čeká na zdroj držený dalším členem

Tyto 4 podmínky mohou být modelovány pomocí orientovaných grafů = ''graf alokace zdrojů''.

Graf má 2 typy uzlů:
* proces - zobrazujeme jako kruh
* zdroj - zobrazujeme jako čtverec
Význam hran:
* od zdroje k procesu: zdroj držen procesem
* od procesu ke zdroji: proces je blokován čekáním na zdroj
Cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí

[[Soubor:Alokace-zdroju.jpg]]

== Řešení zablokování ==

# '''Pštrosí algoritmus''' - Zablokování se ani nedetekuje, ani se mu nezabraňuje, ani se neodstraňuje, Uživatel sám rozhodne o řešení (kill). Nespotřebovává prostředky OS - nemá režii ani neomezuje podmínky provozu. (Nejčastější řešení - Unix, Windows)
# '''Detekce a zotavení''' - Hledá kružnici v orientovaném grafu (hrany vedou od procesu, který čeká, k procesu, který prostředek vlastní), pokud tam je kružnice, nastalo zablokování a je třeba ho řešit:
#* Odebrání prostředku - dohled operátora, pouze na přechodnou dobu
#* Zabíjení procesů z cyklu (resp. mimo cyklus vlastnící identický prostředek)
#* Rollback (OS ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu => ztracena práce... obdoba u DB)
# '''Vyhýbání se''' - Bezpečný stav (procesy/prostředky nejsou zablokovány, existuje cesta, jak uspokojit všechny požadavky na prostředky spouštěním procesů v jistém pořadí); Viď. bankéřův algoritmus. Nutné je předem znát všechny prostředky, které budou programy potřebovat; OS pak dává prostředky tomu, který je nejblíž svému maximu potřeby a navíc pro který je prostředků dost na dokončení. Dnes se moc nepoužívá.
# P'''ředcházení (prevence)''' - napadení jedné z Coffmanových podmínek
# '''Vzájemné vyloučení''' - spooling (prostriedky spravuje jeden systemový proces, ktory dohliada na to, aby jeho stav bol konzistentny (tiskarna) - pozor na místo na disku)
# '''Drž a čekej''' - žádat o všechny prostředky před startem procesu. Nejprve všechno uvolnit a pak znovu žádat o všechny najednou
# '''Neodnímatelnost''' - vede k chaosu
# '''Čekání do kruhu''' - nejvýše jeden prostředek - všechny prostředky jednoznačně očíslovány, procesy mohou žádat o prostředky jen ve vzestupném pořadí
# '''Dvojfázové zamykání''' - nejprve postupně všechno zamykám (první fáze). Potom se může pracovat se zamčenými prostředky - a na závěr se už jen odemyká (druhá fáze) - viď transakční spracování u databází ((striktní/konzervativní) dvoufázové zpracování)

''Bankéřův algoritmus'': Bankéř má klienty a těm slíbil jistou výšku úvěru. Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky do maximální výšky úvěru. Až klient skončí s obchodem, vrátí bance vypůjčené peníze. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu.

{{fav-kiv-bzinf}}

[[Kategorie:fav-kiv-bzinf]]

Problém uvíznutí procesů, graf alokace zdrojů

2015-06-10T11:21:54Z

95.47.186.95:

V množině procesů nastalo uvíznutí, jestliže každý proces množiny čeká na událost, kterou může způsobit pouze jiný proces množiny. Protože všechny čekají, žádný z nich událost nevygeneruje, nevzbudí jiný proces.

== Podmínky vzniku uvíznutí ==
(musejí být splněny všechny 4, 1-3 jsou předpoklad pro 4):
# Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu
# „hold and wait“: proces držící výhradně přiřazené zdroje může požadovat další zdroje
# Nemožnost odejmutí: jednomu přiřazené zdroje nemohou být procesu násilně odejmuty
# Cyklické čekání: musí být cyklický řetězec dvou nebo více procesů, kde každý z nich čeká na zdroj držený dalším členem

Tyto 4 podmínky mohou být modelovány pomocí orientovaných grafů = ''graf alokace zdrojů''.

Graf má 2 typy uzlů:
* proces - zobrazujeme jako kruh
* zdroj - zobrazujeme jako čtverec
Význam hran:
* od zdroje k procesu: zdroj držen procesem
* od procesu ke zdroji: proces je blokován čekáním na zdroj
Cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí

[[Soubor:Alokace-zdroju.jpg]]

== Řešení zablokování ==

# Pštrosí algoritmus - Zablokování se ani nedetekuje, ani se mu nezabraňuje, ani se neodstraňuje, Uživatel sám rozhodne o řešení (kill). Nespotřebovává prostředky OS - nemá režii ani neomezuje podmínky provozu. (Nejčastější řešení - Unix, Windows)
# Detekce a zotavení - Hledá kružnici v orientovaném grafu (hrany vedou od procesu, který čeká, k procesu, který prostředek vlastní), pokud tam je kružnice, nastalo zablokování a je třeba ho řešit:
#* Odebrání prostředku - dohled operátora, pouze na přechodnou dobu
#* Zabíjení procesů z cyklu (resp. mimo cyklus vlastnící identický prostředek)
#* Rollback (OS ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu $ \Rightarrow$ ztracena práce... obdoba u DB)
# Vyhýbání se - Bezpečný stav (procesy/prostředky nejsou zablokovány, existuje cesta, jak uspokojit všechny požadavky na prostředky spouštěním procesů v jistém pořadí); Viď. bankéřův algoritmus. Nutné je předem znát všechny prostředky, které budou programy potřebovat; OS pak dává prostředky tomu, který je nejblíž svému maximu potřeby a navíc pro který je prostředků dost na dokončení. Dnes se moc nepoužívá.
# Předcházení (prevence) - napadení jedné z Coffmanových podmínek
# Vzájemné vyloučení - spooling (prostriedky spravuje jeden systemový proces, ktory dohliada na to, aby jeho stav bol konzistentny (tiskarna) - pozor na místo na disku)
# Drž a čekej - žádat o všechny prostředky před startem procesu. Nejprve všechno uvolnit a pak znovu žádat o všechny najednou
# Neodnímatelnost - vede k chaosu
# Čekání do kruhu - nejvýše jeden prostředek - všechny prostředky jednoznačně očíslovány, procesy mohou žádat o prostředky jen ve vzestupném pořadí
# Dvojfázové zamykání - nejprve postupně všechno zamykám (první fáze). Potom se může pracovat se zamčenými prostředky - a na závěr se už jen odemyká (druhá fáze) - viď transakční spracování u databází ((striktní/konzervativní) dvoufázové zpracování)

Bankéřův algoritmus: Bankéř má klienty a těm slíbil jistou výšku úvěru. Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky do maximální výšky úvěru. Až klient skončí s obchodem, vrátí bance vypůjčené peníze. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu.

{{fav-kiv-bzinf}}

[[Kategorie:fav-kiv-bzinf]]