Víceúrovňová fronta zpětné vazby - Multilevel feedback queue

Ve vědě o počítačích , je víceúrovňový fronta zpětná vazba je plánovací algoritmus. Plánovač Solaris 2.6 Time-Sharing (TS) implementuje tento algoritmus. Plánovače MacOS a Microsoft Windows lze považovat za příklady širší třídy plánovačů front víceúrovňové zpětné vazby. Tento plánovací algoritmus je určen ke splnění následujících požadavků na design pro multimode systémy :

  1. Upřednostňujte krátké práce.
  2. Upřednostněte procesy vázané na I / O.
  3. Rozdělte procesy do kategorií na základě jejich potřeby procesoru.

Víceúrovňový plánovač front zpětné vazby byl poprvé vyvinut Fernandem J. Corbató a kol. v roce 1962 a tato práce spolu s dalšími pracemi na Multics vedla ACM k udělení Corbató Turing Award .

Plánování procesu

Na rozdíl od algoritmu plánování víceúrovňových front , kde jsou procesy trvale přiřazeny do fronty, umožňuje plánování víceúrovňových front zpětné vazby proces přesouvat se mezi frontami. Tento pohyb je usnadněn charakteristikou shluku CPU procesu. Pokud proces používá příliš mnoho času CPU, bude přesunut do fronty s nižší prioritou. Toto schéma ponechává I / O vázané a interaktivní procesy ve frontách s vyšší prioritou. Kromě toho může být proces, který čeká příliš dlouho ve frontě s nižší prioritou, přesunut do fronty s vyšší prioritou. Tato forma stárnutí také pomáhá předcházet hladovění určitých procesů s nižší prioritou.

Algoritmus

Používá se více front FIFO a operace je následující:

  1. Na konec (ocas) fronty FIFO nejvyšší úrovně se vloží nový proces .
  2. V určité fázi se proces dostane do čela fronty a je mu přiřazeno CPU .
  3. Pokud je proces dokončen v časovém kvantu dané fronty, opouští systém.
  4. Pokud se proces dobrovolně vzdá kontroly nad CPU, opouští síť front a když se proces znovu připraví, je vložen na konec stejné fronty, které se vzdal dříve.
  5. Pokud proces využívá veškerý kvantový čas, je předjímán a vložen na konec další fronty nižší úrovně. Tato další fronta nižší úrovně bude mít časové kvantum, které je větší než čas předchozí fronty vyšší úrovně.
  6. Toto schéma bude pokračovat, dokud se proces nedokončí nebo dokud nedosáhne fronty na základní úrovni.
  • Na frontě na základní úrovni procesy cirkulují způsobem každý s každým, dokud nedokončí a neopustí systém. Procesy ve frontě na základní úrovni lze také naplánovat podle zásady „kdo dřív přijde, je dřív na řadě“ .
  • Volitelně, pokud proces blokuje I / O, je „povýšen“ o jednu úroveň a umístěn na konec další vyšší fronty. To umožňuje, aby plánovač upřednostňoval I / O vázané procesy, a umožňuje procesům „uniknout“ z fronty na základní úrovni.

Pro plánování začíná plánovač vždy vyzvedávat procesy z hlavy fronty nejvyšší úrovně. Pouze pokud se fronta nejvyšší úrovně vyprázdní, plánovač zahájí proces z další fronty nižší úrovně. Stejná zásada je implementována pro vyzvednutí v následujících frontách nižší úrovně. Mezitím, pokud proces přijde do některé z front na vyšší úrovni, bude předcházet procesu ve frontě na nižší úrovni.

Nový proces je také vždy vložen na konec fronty nejvyšší úrovně s předpokladem, že bude dokončen v krátkém čase. Dlouhé procesy budou automaticky klesat do front na nižší úrovni na základě jejich spotřeby času a úrovně interaktivity. Ve víceúrovňové frontě zpětné vazby má proces pouze jednu šanci dokončit na dané úrovni fronty, než je vynucen dolů do fronty nižší úrovně.

Parametry plánování

Obecně je víceúrovňový plánovač front zpětné vazby definován následujícími parametry:

  • Počet front.
  • Algoritmus plánování pro každou frontu, který se může lišit od FIFO.
  • Metoda použitá k určení, kdy se má povýšit proces do fronty s vyšší prioritou.
  • Metoda použitá k určení, kdy snížit úroveň procesu do fronty s nižší prioritou.
  • Metoda použitá k určení, do které fronty vstoupí proces, když tento proces potřebuje servis.

Viz také

Reference