Zásobník, fronta, seznam

2016-06-08T20:26:19Z

147.228.209.161: /* Fronta */

Všechny tyto ADT implementují IsEmpty (prázdná struktura) a Size (pošet prvků ve struktuře)

== Zásobník ==

Interface: operace Push, Pop, Peek
* '''Push''' vkládá data do zásobníku za sebe
* '''Pop''' vybírá nejpozději vložená data
* '''Peek''' vrátí nejpozději vložená data bez výběru prvku ze struktury
= LIFO pamět (Last In First Out)

Všechny operace jsou O(1)

[[Soubor:Zasobnik.jpg]]

Head: vrchol zásobníku

Implementace objektově:
* Prvky (objekty) obsahují data a ukazují na nižžší prvky v zásobníku (na prvky pod sebou)
* '''Konstruktor:''' Vytvoříme ukazatel Head, který nastavíme na null
* '''Modifikátor:''' Push vytvoří pro data nový prvek, který ukazuje na prvek Head (Head bude předchozí), a změní ukazatel Head na vytvořený prvek
* '''Selektor:''' Peek vrátí data prvku Head, pokud Head != null. Pop vrátí stejná data jako Peek, ale před návratem změní ukazatel Head na předchozí prvek (Head = Head.Previous)

Implementace na poli:
* Máme pole typu stejného jako data
* '''Konstruktor:''' Alokace pole a indexu Head, nastavení Head na -1
* '''Modifikátor:''' Push zvýší index Head o 1 a zapíše data do pole na tento index. Pokud je index mimo pole, zvětšení pole (např. 2x), a po té zápis
* '''Selektor:''' Peek vrátí prvek pole pod indexem Head, pokud Head >= 0. Pop jako peek, ale před návratem provede Head--, pokud Head >= 0.

== Fronta ==

Interface: operace Push, Pop, Front
* '''Enqueue''' vkládá data do fronty za sebe
* '''Dequeue''' vybírá nejdříve vložená data
* '''Front''' vrátí nejdříve vložená data bez výběru prvku ze struktury
= FIFO pamět (First In First Out)

[[Soubor:Fronta.jpg]]

First: začátek fronty; Last: konec fronty

Implementace objektově:
* Prvky obsahují data a ukazují na následující prvky fronty
* '''Konstruktor:''' Vytvoříme pouze ukazatele First a Last, ukazující na null.
* '''Modifikátor:''' Push vytvoří pro data nový prvek, upraví prvek Last (pokud != null) tak, aby ukazoval na tento prvek, a změní ukazatel Last na tento prvek. Je-li ukazatel First nastaven na null, nastaví tento také na vytvořený prvek.
* '''Selektor:''' Front vrátí data prvku First, pokud First != null. Pop vrátí stejná data jako Front, ale před návratem změní ukazatel First na následující prvek, pokud First != null (First = First.Next)

Implementace na poli (cyklicky):
Máme pole typu stejného jako data a indexy First a Last. Indexy neukazují přímo do pole, nýbrž je proveden přepočet (Index mod Delka pole)
abychom využili celé pole. Tato fronta má omezenou délku.
* '''Konstruktor:''' Alokace pole a indexů, nastavení Last na -1 a First na -1
* '''Modifikátor:''' Pokud ((Last + 1) mod Delka) != (First mod Delka), Push provede Last++ a zapíše data do pole na tento index, jinak chyba (plná fronta). Pokud First = -1, pak First = 0 (první prvek).
* '''Selektor:''' Front vrátí prvek pole pod indexem First, pokud First <= Last. Pop jako Front, ale před návratem provede First++.

Speciálním případem je například prioritní fronta, která řadí prvky ve frontě podle priority

== Seznam ==

Interface - Iterator nad seznamem: Add, Remove, Get; First, Next, IsLast, případně další (Previous, Last, IndexOf, ...)

[[Soubor:Seznam.jpg]]

* '''Add''' vkládá data na pozici iterátoru. Složitost dle implementace.
* '''Remove''' maže data na pozici iterátoru
* '''Get''' vrátí data na pozici iteratoru
* '''First''' vrátí iterátor na začátek seznamu
* '''Next''' posune iterátor dále
* '''IsLast''' indikuje koncová prvek
* (Previous v obousměrných seznamech posune iterator na předchozí prvek)
* (Last posune iterator na poslední prvek)
* (IndexOf vyhledá prvek ve struktuře)
= struktura, do které je možné libovolně zapisovat a číst (na libovolné pozici)

Iterator: ukazatel do struktury

Implementace objektově - nástřel:

[[Soubor:Zasovnik-fronta-seznam-objektove.jpg]]

Prvky ukazují na následující prvky seznamu. Iterátor je dobré implementovat tak, že ve skutečnosti ukazuje na předchozí prvek (Pokud tedy seznam není obousměrný, pak máme metodu Previous a je to jedno). Metoda add vloží prvek za prvek, na který ukazuje iterátor tak, že pouze upraví ukazatele prvků:

Remove je opačný proces, Get vrátí data (Tedy Iterator.Next.Data), První prvek seznamu si uložíme, abychom se mohli rychle vracet, stejně jako poslední prvek. Next provede Iterator.Next = Iterator.Next.Next. Kontrolujeme, zda nejsme mimo seznam.

* Obousměrný seznam: Prvky mají i ukazatele na předchozí prvky, a je tedy možné se po nich pohybovat na obě strany.
* Kruhový seznam: Poslední prvek neukazuje na null, ale na první prvek. Tyto seznamy jsou použitelné ve speciálních případech (například nastavení segmentů sedmisegmentovky pro digitální hodiny)

Implementace na poli (nástřel):
Pole má nevýhodu, že je nutné přesunout prvky doprava od iterétoru, pokud vkládáme prvky. Při mazání lze prvky posunout doleva, nebo do pole uložit hodnotu, která se zcela jistě nebude v poli nebude vyskytovat, nebo vytvořit stínové pole, ve kterém si smazané prvky označíme, a při posunu iterátoru je poté vynecháme. Tento přístup je dobrý pokud pole často upravujeme.

{{fav-kiv-bzinf}}
[[Kategorie:fav-kiv-bzinf]]

Plánování úloh a procesů v dávkových systémech

2016-06-08T13:13:21Z

147.228.209.161: /* Multilevel Feedback */

* Non-preemtivní plánování: proces si podrží kontrolu nad CPU dokud se jí nevzdá
* Preemtivní - proces lze přerušit během CPU burstu a naplánovat jiný

Bere se ohled na:
* průchodnost (počet úloh dokončených za časovou jednotku)
* průměrnou dobu obrátky (průměrná doba od zadání úlohy do systému do dokončení úlohy)
* využití CPU

== First-Come First-Served (FCFS) ==

* Někdy používán název FIFO
* Zpracování podle času příchodu úlohy, „kdo dřív přijde, ten dřív mele“
* Nepreemptivní FCFS je nejjednodušší plánovací algoritmus (úloha běží dokud neskončí)
* Je spravedlivý
* Během I/O operací se CPU nevyužívá, ale přesto je blokováno stávajícím procesem

== Shortest Job First (SJF) ==

* Předpoklad, že je předem známá doba vykonávání úlohy
* Nepreemptivní, jedna fronta příchozích úloh, plánovač vybere vždy úlohu s nejkratší dobou běhu
* Nevýhodou je, že na dlouho trvající úlohy se nemusí vůbec dostat

== Shortest Remaining Time (SRT) ==

* Preemptivní varianta SJF
* Plánovač vždy vybere úlohu, jejíž zbývající doba běhu je nejkratší
* Např. právě prováděné úloze to bude trvat 10 min., do systému přijde úloha trvající 1 minutu - systém prováděnou úlohu pozastaví a nechá běžet novou úlohu
* Problém: možnost vyhladovění úloh

== Multilevel Feedback ==

* Je preemptivní
* N rozdílných prioritních úrovní, každá úroveň má svou frontu úloh
* Úloha vstoupí do systému s nejvyšší prioritou
* Na každé prioritní úrovni je stanoveno maximu času CPU, které může úloha na této úrovni obdržet
** Pokud úloha překročí limit, její priorita se sníží
** Na nejnižší úrovni může proces běžet neustále nebo může být překročení považováno za chybu
* Procesor obsluhuje nejvyšší neprázdnou frontu
* Výhoda: rozlišuje mezi I/O a CPU úlohami (upřednostňuje I/O)

{{fav-kiv-bzinf}}

[[Kategorie:fav-kiv-bzinf]]

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

Zásobník, fronta, seznam

Plánování úloh a procesů v dávkových systémech