Operační systém si potřebuje pamatovat mnoho informací, například seznam běžících procesů, údaje o všech načtených ovladačích či seznam volných a alokovaných bloků fyzické paměti. S každým druhem informací je potřeba zacházet trochu odlišným způsobem. Například pokud nějaká součást jádra požádá o alokaci fyzické paměti, je žádoucí velmi rychle najít potřebné bloky (u fyzické paměti se též nazývají rámce, u virtuální paměti stránky) a přidělit je volajícímu. Přidělování virtuální paměti by mělo splňovat podobná kriteria. Na druhou stranu není v drtivé většině případů nutné rychle vědět, jaké procesy používají určitou knihovnu DLL.
Z předchozího odstavce plyne, že různé informace je třeba reprezentovat různým způsobem, aby s nimi mohl operační systém a aplikace pracovat co nejefektivněji. Následující odstavce popisují několik možností, jak reprezentovat soubor údajů. Tyto reprezentace se nazývají datové struktury a jednotlivé údaje v nich obsažené se často označují jako prvky.
| Pro čtení dalších kapitol není nutné do detailů pochopit, jak dále popisované datové struktury fungují. Ale měli byste získat rámcový přehled o jejich výhodách, nevýhodách a při jakých příležitostech a na jaká data jsou vhodné. |
Pole (array)
Pole je datová struktura, která slouží k uchovávání prvků stejného druhu. Všechny prvky jsou uloženy za sebou v souvislém bloku paměti.
Výhodou pole je velmi rychlý přístup k N-tému prvku (tato vlastnost se též označuje jako náhodný přístup). Pokud známe adresu začátku pole, adresa N-tého prvku je určena vzorcem:
\(adresa\_i\_teho\_prvku = adresa\_pole + i * velikost\_prvku\)
Číslu i se také říká index. Obsah prvku na určitém indexu tedy získáme v jediném kroku nezávisle na velikosti pole. Pokud je pole navíc setříděné, je možné rychle provést test na existenci prvku s určitou hodnotou. Tato operace již závisí na velikosti pole. Je nutné provést nejvýše tolik operací, kolik je dvojkový logaritmus z počtu prvků ve struktuře.
Na obrázku 2 vidíte, jak se obvykle při testování existence prvku v setříděném poli postupuje. Tato metoda se nazývá půlení intervalů. Nejprve se otestuje hodnota prvku uprostřed pole. Pokud je hledaná hodnota menší, musí se nacházet před ním. Pokud je větší, musí, díky faktu, že pole je v tomto příkladu setříděné vzestupně, ležet za ním. A stejný postup se aplikuje na příslušnou polovinu pole – tedy provede se test, zda se její prostřední prvek nerovná hledané hodnotě. Po každém testování se interval, ve kterém se hledaný prvek může nacházet, zmenší na polovinu. Pokud zdegeneruje na interval tvořený jedním prvkem, který není shodný s hledanou hodnotou, hledaný prvek v poli není obsažen. Obrázek 2 konkrétně ukazuje, jak v setříděném poli, jehož prvky tvoří čísla, probíhá test na existenci hodnoty 25.
Tím jsou však výhody pole téměř vyčerpány. Velkým problémem může být fakt, že se nachází v jednom souvislém bloku paměti. Postupným přidáváním nových prvků může dojít k naplnění celého bloku. Potom je nutné alokovat větší souvislý blok a obsah celého pole do něho překopírovat. A kopírování velkých bloků paměti již není časově zanedbatelné, probíhá-li relativně často. Tento případ demonstruje obrázek 3.
Navíc se může stát, že volná paměť je rozdrolena do malých kousků, které sice v součtu dávají dostatek místa pro větší blok, ale souvislý blok dostatečné velikosti neexistuje.
Přidávání doprostře seřazeného pole představuje několik operací.
Přidávání nového prvku může být ještě pomalejší, není-li přidáván na konec, ale někam doprostřed. Tento případ může nastat například u setříděných polí (viz obrázek 4). Pro nový prvek je třeba uvolnit místo a to je možné provést jen překopírováním prvků ležících za ním o jednu pozici dozadu. Na obrázku 4 vidíte tuto operaci schématicky znázorněnou.
Odebírání prvku je možné provést nezávisle na velikosti pole, pokud není nutné datovou strukturu udržovat celistvou a může obsahovat díry – prvky se speciální hodnotou, která reprezentuje volné místo. Pokud si není možné díry dovolit, je při odebrání prvku nutné posunout jiné prvky tak, aby byla vzniklá díra zacelena. Příklad takového mazání vidíte na obrázcích 5 a 6.
Pole se využívají především při implementaci složitějších datových struktur jako zásobník, fronta či hašovací tabulka. Hodí se na uchovávání dat, která se příliš často nemění – nedochází k častému přidávání nových a mazání starých prvků. Jak je totiž vidět z předchozích odstavců, přidávání či mazání prvků může způsobit i kopírování celého pole, což je operace pomalá, ačkoliv probíhá celá v operační paměti počítače.
Spojové seznamy (lists)
Spojový seznam ukládá každý svůj prvek v odděleném bloku paměti. Tím je eliminována potřeba velkých volných souvislých úseků paměťových stránek, pokud datová struktura obsahuje velké množství prvků. Každý paměťový blok, který obsahuje jeden prvek seznamu, v sobě zároveň uchovává další informace o poloze ostatních prvků. Podle množství těchto informací se spojové seznamy rozdělují na několik druhů. Čím více informací navíc se uchovává, tím lépe lze s daným seznamem pracovat. Spojové seznamy můžeme rozdělit do následujících kategorií:
-
Lineární (jednosměrné) – každý prvek obsahuje adresu následujícího prvku v seznamu (viz obrázek 8). Do lineárního spojového seznamu se snadno přidává na začátek a snadno ze začátku odebírá. Poslední prvek má adresu následujícího prvku seznamu vyplněnou hodnotou pro neplatný ukazatel (NULL, Nil). Pokud je známa adresa nějakého prvku, snadno lze za něho přidat další prvek.
-
Obousměrné – každý prvek obsahuje odkaz (adresu) na svého následníka a předchůdce. I do obousměrného spojového seznamu se snadno přidává na začátek a snadno ze začát- ku odebírá. Dále je možné snadno přidat další prvek za nebo před jiný prvek se známou adresou. Přidávání a mazání, ačkoliv nezávisí na délce (počtu prvků) seznamu, je však pomalejší než u lineárního seznamu – kromě adresy následníka je nutné měnit i adresu předchůdce. Ukázku obousměrného seznamu vidíte na obrázku 9.
Zásobník (stack)
Zásobník je datová struktura pro uchovávání souboru prvků, která podporuje pouze následující operace:
-
Vložení nového prvku (push).
-
Odebrání naposledy vloženého prvku (pop).
-
Test prázdnosti (empty).
Je vidět, že nad takovouto strukturou lze provádět méně operací než s polem či se spojovým seznamem. Protože tyto operace tvoří podmnožinu operací nad oběma výše popsanými strukturami, je možné je pomocí pole či spojového seznamu implementovat.
Implementace prostřednictvím pole může vypadat například takto:
-
K poli si zavedeme proměnnou PosledniPlatny , ve které si budeme pamatovat index posledního platného prvku. Na začátku, kdy je zásobník prázdný, má tato proměnná hodnotu –1.
-
Z předchozího bodu vyplývá implementace operace empty. Zásobník je prázdný právě tehdy, když je hodnota proměnné PosledniPlatny rovna –1.
-
Operace push znamená zvýšení hodnoty proměnné PosledniPlatny o jedničku a uložení nového prvku do slotu s příslušným indexem.
-
Operace pop se implementuje jako snížení hodnoty proměnné PosledniPlatny o jedničku a vrácení prvku s indexem rovným její předchozí hodnotě.
