{"id":32730,"date":"2019-10-31T21:48:36","date_gmt":"2019-10-31T18:48:36","guid":{"rendered":"https:\/\/prohoster.info\/blog\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod\/"},"modified":"2021-02-08T11:40:35","modified_gmt":"2021-02-08T09:40:35","slug":"operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","status":"publish","type":"post","link":"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","title":{"rendered":"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<h1>\u00davod do opera\u010dn\u00edch syst\u00e9m\u016f<\/h1>\n<p>Ahoj, Habr! R\u00e1d bych v\u00e1m p\u0159edstavil s\u00e9rii \u010dl\u00e1nk\u016f-p\u0159eklad\u016f jedn\u00e9 zaj\u00edmav\u00e9 literatury, kterou pova\u017euji za hodnotnou \u2014 OSTEP. Tento materi\u00e1l se hloub\u011bji zab\u00fdv\u00e1 prac\u00ed unixov\u00fdch opera\u010dn\u00edch syst\u00e9m\u016f, konkr\u00e9tn\u011b prac\u00ed s procesy, r\u016fzn\u00fdmi pl\u00e1nova\u010di, pam\u011bt\u00ed a dal\u0161\u00edmi komponentami, kter\u00e9 tvo\u0159\u00ed modern\u00ed OS. Origin\u00e1l v\u0161ech materi\u00e1l\u016f m\u016f\u017eete vid\u011bt tady <noindex><a rel=\"nofollow\" href=\"http:\/\/pages.cs.wisc.edu\/~remzi\/OSTEP\/\">tady<\/a><\/noindex>. Upozor\u0148uji, \u017ee p\u0159eklad byl proveden neprofesion\u00e1ln\u011b (pom\u011brn\u011b voln\u011b), ale douf\u00e1m, \u017ee jsem zachoval celkov\u00fd smysl.<\/p>\n<p>Laboratorn\u00ed pr\u00e1ce k tomuto p\u0159edm\u011btu najdete zde:<\/p>\n<ul>\n<li><noindex><a rel=\"nofollow\" href=\"http:\/\/pages.cs.wisc.edu\/~remzi\/OSTEP\/Homework\/homework.html\">origin\u00e1l<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/remzi-arpacidusseau\/ostep-code\">origin\u00e1l<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/bykvaadm\/OS\/tree\/master\/ostep\">m\u00e1 osobn\u00ed adaptace<\/a><\/noindex><\/li>\n<\/ul>\n<p>Dal\u0161\u00ed \u010d\u00e1sti:<\/p>\n<ul>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/446340\/\">\u010c\u00e1st 1: \u00davod<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/446866\/\">\u010c\u00e1st 2: Abstrakce: proces<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/447182\/\">\u010c\u00e1st 3: \u00davod do API proces\u016f<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/449026\/\">\u010c\u00e1st 4: \u00davod do pl\u00e1nova\u010de<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/450116\/\">\u010c\u00e1st 5: Pl\u00e1nova\u010d MLFQ<\/a><\/noindex><\/li>\n<\/ul>\n<p>A m\u016f\u017eete tak\u00e9 nahl\u00e9dnout na m\u016fj kan\u00e1l na <noindex><a rel=\"nofollow\" href=\"https:\/\/t.me\/bykvaadm\">Telegramu<\/a><\/noindex> =)<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h2>Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba<\/h2>\n<p>V t\u00e9to p\u0159edn\u00e1\u0161ce se budeme zab\u00fdvat probl\u00e9my v\u00fdvoje jednoho z nejzn\u00e1m\u011bj\u0161\u00edch p\u0159\u00edstup\u016f k<br \/>\npl\u00e1nov\u00e1n\u00ed, kter\u00fd se naz\u00fdv\u00e1 <b>V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba<\/b> (MLFQ). Poprv\u00e9 byl pl\u00e1nova\u010d MLFQ pops\u00e1n v roce 1962 Fernando J. Corbat\u00f3 v syst\u00e9mu nazvan\u00e9m<br \/>\nKompatibiln\u00ed \u010dasov\u011b sd\u00edlen\u00fd syst\u00e9m (CTSS). Tyto pr\u00e1ce (v\u010detn\u011b pozd\u011bj\u0161\u00edch prac\u00ed na<br \/>\nMultics) byly pot\u00e9 nominov\u00e1ny na Turingovu cenu. Pl\u00e1nova\u010d byl<br \/>\nn\u00e1sledn\u011b vylep\u0161en a z\u00edskal podobu, kterou lze nal\u00e9zt ji\u017e v<br \/>\nn\u011bkter\u00fdch modern\u00edch syst\u00e9mech.<\/p>\n<p>Algoritmus MLFQ se sna\u017e\u00ed vy\u0159e\u0161it 2 z\u00e1kladn\u00ed p\u0159ekr\u00fdvaj\u00edc\u00ed se probl\u00e9my.<br \/>\n<b>Za prv\u00e9<\/b>, sna\u017e\u00ed se optimalizovat dobu obratu, kter\u00e1 jak jsme probrali v p\u0159edchoz\u00ed p\u0159edn\u00e1\u0161ce, se optimalizuje metodou spu\u0161t\u011bn\u00ed na za\u010d\u00e1tku fronty nejv\u00edce<br \/>\nkr\u00e1tk\u00fdch \u00faloh. Nicm\u00e9n\u011b, OS nev\u00ed, jak dlouho bude trvat dan\u00fd proces, a to je<br \/>\nnezbytn\u00e9 znalosti pro fungov\u00e1n\u00ed algoritm\u016f SJF, STCF. <b>Za druh\u00e9<\/b>, MLFQ se sna\u017e\u00ed<br \/>\nud\u011blat syst\u00e9m reaguj\u00edc\u00ed na u\u017eivatele (nap\u0159\u00edklad takov\u00e9, kte\u0159\u00ed sed\u00ed a<br \/>\nz\u00edr\u00e1n\u00ed na obrazovku v o\u010dek\u00e1v\u00e1n\u00ed dokon\u010den\u00ed \u00falohy) a t\u00edm minimalizovat dobu<br \/>\nreakce. Bohu\u017eel, algoritmy jako RR sni\u017euj\u00ed dobu reakce, ale extr\u00e9mn\u011b<br \/>\nnegativn\u011b ovliv\u0148uj\u00ed metriku doby obratu. Odtud na\u0161e ot\u00e1zka: Jak navrhnout<br \/>\npl\u00e1nova\u010d, kter\u00fd bude spl\u0148ovat na\u0161e po\u017eadavky a z\u00e1rove\u0148 nic nev\u011bd\u011bt o<br \/>\ncharakter procesu obecn\u011b? Jak bude pl\u00e1nova\u010d schopen studovat charakteristiky \u00faloh,<br \/>\nkter\u00e9 spou\u0161t\u00ed, a t\u00edm p\u00e1dem l\u00e9pe rozhodovat o pl\u00e1nov\u00e1n\u00ed?<\/p>\n<p><u>Podstata probl\u00e9mu: Jak pl\u00e1novat \u00fakoly bez ide\u00e1ln\u00edho znalosti?<br \/>\nJak navrhnout pl\u00e1nova\u010d, kter\u00fd sou\u010dasn\u011b minimalizuje dobu odezvy<br \/>\npro interaktivn\u00ed \u00falohy a z\u00e1rove\u0148 minimalizuje dobu obratu bez p\u0159edchoz\u00edho<br \/>\nznalosti doby prov\u00e1d\u011bn\u00ed \u00falohy?<\/u><\/p>\n<p>Pozn\u00e1mka: u\u010d\u00edme se z p\u0159ede\u0161l\u00fdch ud\u00e1lost\u00ed<\/p>\n<p>Fronta MLFQ je vynikaj\u00edc\u00edm p\u0159\u00edkladem syst\u00e9mu, kter\u00fd se u\u010d\u00ed na<br \/>\nuplynul\u00fdch ud\u00e1lostech, aby predikoval budoucnost. Podobn\u00e9 p\u0159\u00edstupy se \u010dasto<br \/>\nvyskytuj\u00ed v OS (a mnoha dal\u0161\u00edch oblastech informatiky, v\u010detn\u011b v\u011btv\u00ed<br \/>\np\u0159edpov\u011bd\u00ed v hardwaru a algoritm\u016f mezipam\u011bti). Takov\u00e9 p\u0159\u00edstupy<br \/>\nfunguj\u00ed, kdy\u017e maj\u00ed \u00fakoly chov\u00e1n\u00ed a t\u00edm jsou p\u0159edv\u00eddateln\u00e9.<br \/>\nNicm\u00e9n\u011b s touto technikou je t\u0159eba b\u00fdt opatrn\u00fd, proto\u017ee p\u0159edpov\u011bdi se velmi snadno<br \/>\nmohou uk\u00e1zat jako \u0161patn\u00e9 a v\u00e9st syst\u00e9m k hor\u0161\u00edm rozhodnut\u00edm, ne\u017e<br \/>\nby bylo bez jak\u00fdchkoliv znalost\u00ed.<\/p>\n<h3>MLFQ: Z\u00e1kladn\u00ed pravidla<\/h3>\n<p>Poj\u010fme se pod\u00edvat na z\u00e1kladn\u00ed pravidla algoritmu MLFQ. A\u010dkoliv existuje n\u011bkolik<br \/>\nimplementac\u00ed tohoto algoritmu, z\u00e1kladn\u00ed p\u0159\u00edstupy jsou podobn\u00e9.<br \/>\nV t\u00e9 implementaci, kterou budeme zkoumat, bude m\u00edt MLFQ n\u011bkolik<br \/>\nodd\u011blen\u00fdch front, z nich\u017e ka\u017ed\u00e1 bude m\u00edt jinou prioritu. V ka\u017ed\u00e9m okam\u017eiku,<br \/>\n\u00fakol, kter\u00fd je p\u0159ipraven k proveden\u00ed, se nach\u00e1z\u00ed v jedn\u00e9 front\u011b. MLFQ pou\u017e\u00edv\u00e1 priority,<br \/>\naby rozhodoval, kterou \u00falohu spustit k proveden\u00ed, tj. \u00fakol s vy\u0161\u0161\u00edmi<br \/>\nprioritami (\u00fakol z fronty s nejvy\u0161\u0161\u00ed prioritou) bude spu\u0161t\u011bn jako prvn\u00ed.<br \/>\nJist\u011b, v konkr\u00e9tn\u00ed front\u011b m\u016f\u017ee b\u00fdt v\u00edce ne\u017e jedna \u00faloha, tak\u017ee<br \/>\nbudou m\u00edt stejnou prioritu. V tomto p\u0159\u00edpad\u011b bude pou\u017eit mechanismus<br \/>\nRR pro pl\u00e1nov\u00e1n\u00ed spu\u0161t\u011bn\u00ed mezi t\u011bmito \u00falohami.<br \/>\nTakto doch\u00e1z\u00edme k dv\u011bma z\u00e1kladn\u00edm pravidl\u016fm pro MLFQ:<br \/>\nPravidlo 1: Pokud priorita(A) &gt; priorita(B), bude spu\u0161t\u011bn \u00fakol A (B nebude)<\/p>\n<ul>\n<li> Pravidlo 2: Pokud priorita(A) = priorita(B), A i B se spou\u0161t\u00ed pomoc\u00ed RR<\/li>\n<li> Na z\u00e1klad\u011b v\u00fd\u0161e uveden\u00e9ho jsou kl\u00ed\u010dov\u00fdmi prvky pl\u00e1nov\u00e1n\u00ed MLFQ<\/li>\n<\/ul>\n<p>priority. M\u00edsto toho, abychom nastavili fixn\u00ed prioritu ka\u017ed\u00e9mu<br \/>\njsou priority. Nam\u00edsto nastaven\u00ed pevn\u00e9 priority ka\u017ed\u00e9mu<br \/>\nPokud jde o \u00falohu, MLFQ m\u011bn\u00ed jej\u00ed prioritu na z\u00e1klad\u011b pozorovan\u00e9ho chov\u00e1n\u00ed.<br \/>\nNap\u0159\u00edklad pokud \u00faloha neust\u00e1le zdr\u017euje CPU \u010dek\u00e1n\u00edm na vstup z kl\u00e1vesnice,<br \/>\nMLFQ udr\u017euje prioritu procesu na vysok\u00e9 \u00farovni, proto\u017ee tak by m\u011bl fungovat interaktivn\u00ed proces. Pokud \u00faloha naopak neust\u00e1le a intenzivn\u011b vyu\u017e\u00edv\u00e1 CPU po del\u0161\u00ed dobu, MLFQ sn\u00ed\u017e\u00ed jej\u00ed prioritu.<br \/>\nTak\u017ee MLFQ studuje chov\u00e1n\u00ed proces\u016f v pr\u016fb\u011bhu jejich pr\u00e1ce a pou\u017e\u00edv\u00e1 tato chov\u00e1n\u00ed.<br \/>\nNakresl\u00edme si p\u0159\u00edklad toho, jak by mohly vypadat fronty v ur\u010dit\u00e9m okam\u017eiku<br \/>\n\u010dasu a dostaneme n\u011bco takov\u00e9ho:<br \/>\nV tomto sch\u00e9matu jsou 2 procesy A a B v front\u011b s nejvy\u0161\u0161\u00ed prioritou. Proces<br \/>\nC je n\u011bkde uprost\u0159ed, a proces D je na konci fronty. Podle v\u00fd\u0161e uveden\u00fdch<br \/>\npopis\u016f algoritmu MLFQ pl\u00e1nova\u010d vykon\u00e1v\u00e1 \u00fakoly pouze s nejvy\u0161\u0161\u00edmi<br \/>\n<img decoding=\"async\" alt=\"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)\" src=\"\/wp-content\/uploads\/2019\/04\/3598e9ca43a56049625bdcf3074de472.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>prioritami podle RR, zat\u00edmco \u00fakoly C a D z\u016fstanou bez pov\u0161imnut\u00ed.<br \/>\nSamoz\u0159ejm\u011b, statick\u00fd sn\u00edmek neposkytuje \u00fapln\u00fd obr\u00e1zek o tom, jak MLFQ funguje.<br \/>\nJe d\u016fle\u017eit\u00e9 pochopit, jak se obraz m\u011bn\u00ed v pr\u016fb\u011bhu \u010dasu.<br \/>\nPokAttempt 1: Jak m\u011bnit prioritu<br \/>\nV tuto chv\u00edli je t\u0159eba rozhodnout, jak MLFQ zm\u011bn\u00ed \u00farove\u0148 priority<br \/>\n\u00fakolu (a tedy um\u00edst\u011bn\u00ed \u00fakolu ve front\u011b) b\u011bhem jej\u00edho \u017eivotn\u00edho cyklu. Pro<\/p>\n<h4>to je t\u0159eba m\u00edt na pam\u011bti pracovn\u00ed n\u00e1pl\u0148: ur\u010dit\u00e9 mno\u017estv\u00ed<\/h4>\n<p>interaktivn\u00edch \u00faloh s kr\u00e1tkou dobou trv\u00e1n\u00ed (a tedy \u010dast\u00fdm uvol\u0148ov\u00e1n\u00edm<br \/>\nCPU) a n\u011bkolik dlouh\u00fdch \u00faloh, kter\u00e9 pou\u017e\u00edvaj\u00ed CPU po celou dobu sv\u00e9 pracovn\u00ed doby, p\u0159i\u010dem\u017e<br \/>\ndoba reakce pro takov\u00e9 \u00falohy nen\u00ed d\u016fle\u017eit\u00e1. A tud\u00ed\u017e m\u016f\u017eeme ud\u011blat prvn\u00ed pokus<br \/>\nimplementovat algoritmus MLFQ s n\u00e1sleduj\u00edc\u00edmi pravidly:<br \/>\nPravidlo 3: Kdy\u017e \u00faloha vstoup\u00ed do syst\u00e9mu, je za\u0159azena do fronty s nejvy\u0161\u0161\u00edm<br \/>\nprioritou.<br \/>\nPravidlo 4a: Pokud \u00faloha vyu\u017eije cel\u00e9 p\u0159id\u011blen\u00e9 \u010dasov\u00e9 okno, jej\u00ed<\/p>\n<ul>\n<li> priorita se sn\u00ed\u017e\u00ed.<\/li>\n<li>Pravidlo 4b: Pokud \u00faloha uvoln\u00ed CPU p\u0159ed vypr\u0161en\u00edm sv\u00e9ho \u010dasov\u00e9ho okna, jej\u00ed<\/li>\n<li>priorita z\u016fst\u00e1v\u00e1 stejn\u00e1.<\/li>\n<li>P\u0159\u00edklad 1: Jedin\u00e1 dlouh\u00e1 \u00faloha<\/li>\n<li>Jak je vid\u011bt v tomto p\u0159\u00edkladu, \u00faloha p\u0159i vstupu dost\u00e1v\u00e1 nejvy\u0161\u0161\u00ed<\/li>\n<li>prioritu. Po \u010dasov\u00e9m okn\u011b 10 ms je proces sn\u00ed\u017een v priorit\u011b<\/li>\n<\/ul>\n<p><b>pl\u00e1nova\u010dem. Po dal\u0161\u00edm \u010dasov\u00e9m okn\u011b je \u00faloha kone\u010dn\u011b sn\u00ed\u017eena na<\/b><\/p>\n<p>Jak je vid\u011bt v tomto p\u0159\u00edkladu, \u00faloha p\u0159i p\u0159ijet\u00ed dost\u00e1v\u00e1 nejvy\u0161\u0161\u00ed<br \/>\nprioritu. Po \u010dasov\u00e9m okn\u011b 10 ms je proces po sn\u00ed\u017een\u00e9 priorit\u011b<br \/>\npl\u00e1nova\u010dem. Po n\u00e1sleduj\u00edc\u00edm \u010dasov\u00e9m oknu je \u00faloha kone\u010dn\u011b sn\u00ed\u017eena na<br \/>\nn\u00edzk\u00e9 priority v syst\u00e9mu, kde z\u016fst\u00e1v\u00e1.<br \/>\n<img decoding=\"async\" alt=\"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)\" src=\"\/wp-content\/uploads\/2019\/04\/9b4ee6de03aa92d7957d50b4ffa73949.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p><b>P\u0159\u00edklad 2: P\u0159ivezen \u00fakol s kr\u00e1tk\u00fdm trv\u00e1n\u00edm<\/b><\/p>\n<p>Te\u010f se pod\u00edv\u00e1me na p\u0159\u00edklad toho, jak se MLFQ pokus\u00ed p\u0159ibl\u00ed\u017eit SJF. V tomto<br \/>\np\u0159\u00edkladu jsou dva \u00fakoly: A, co\u017e je \u00fakol s dlouh\u00fdm trv\u00e1n\u00edm, kter\u00fd neust\u00e1le<br \/>\nprocesor vyu\u017e\u00edv\u00e1, a B, co\u017e je kr\u00e1tk\u00fd interaktivn\u00ed \u00fakol. P\u0159edpokl\u00e1dejme,<br \/>\n\u017ee A u\u017e n\u011bjakou dobu pracovalo v okam\u017eiku, kdy doraz\u00ed \u00fakol B.<br \/>\n<img decoding=\"async\" alt=\"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)\" src=\"\/wp-content\/uploads\/2019\/04\/19c299b0519585fd1076a341a71f048b.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>Na tomto grafu jsou zobrazeny v\u00fdsledky sc\u00e9n\u00e1\u0159e. \u00dakol A, jako ka\u017ed\u00fd \u00fakol,<br \/>\nkter\u00fd vyu\u017e\u00edv\u00e1 CPU, se ocitl na \u00fapln\u00e9m dn\u011b. \u00dakol B p\u0159ijde v \u010dase T=100 a<br \/>\nbude um\u00edst\u011bn do fronty s nejvy\u0161\u0161\u00ed prioritou. Vzhledem k tomu, \u017ee doba jeho b\u011bhu je kr\u00e1tk\u00e1,<br \/>\ndok\u00e1\u017ee se dokon\u010dit d\u0159\u00edve, ne\u017e se dostane na posledn\u00ed pozici.<\/p>\n<p>Z tohoto p\u0159\u00edkladu bychom m\u011bli pochopit hlavn\u00ed c\u00edl algoritmu: proto\u017ee algoritmus ne<br \/>\nv\u00ed, zda je \u00fakol dlouh\u00fd nebo kr\u00e1tk\u00fd, p\u0159edpokl\u00e1d\u00e1 p\u0159edev\u0161\u00edm, \u017ee \u00fakol<br \/>\nje kr\u00e1tk\u00fd, a ud\u011bluje mu nejvy\u0161\u0161\u00ed prioritu. Pokud je to opravdu kr\u00e1tk\u00fd \u00fakol,<br \/>\nproveden\u00ed bude rychl\u00e9, jinak, pokud je to dlouh\u00fd \u00fakol, bude se pomalu dost\u00e1vat<br \/>\ndol\u016f v priorit\u011b a brzy prok\u00e1\u017ee, \u017ee je to opravdu dlouh\u00fd \u00fakol, kter\u00fd ne<br \/>\nvy\u017eaduje odezvu.<\/p>\n<p><b>P\u0159\u00edklad 3: A co vstup-v\u00fdstup?<\/b><\/p>\n<p>Nyn\u00ed se pod\u00edv\u00e1me na p\u0159\u00edklad se vstupem-v\u00fdstupem. Jak bylo uvedeno v pravidle 4b,<br \/>\npokud proces uvoln\u00ed procesor, ani\u017e by zcela vyu\u017eil sv\u016fj \u010das procesoru,<br \/>\nz\u016fst\u00e1v\u00e1 na stejn\u00e9 \u00farovni priority. Z\u00e1m\u011bry tohoto pravidla jsou docela jasn\u00e9<br \/>\n\u2014 pokud interaktivn\u00ed \u00fakol prov\u00e1d\u00ed mnoho operac\u00ed vstupu-v\u00fdstupu, nap\u0159\u00edklad \u010dekaj\u00edc\u00ed<br \/>\nna stisknut\u00ed kl\u00e1vesy nebo my\u0161i u\u017eivateli, takov\u00fd \u00fakol uvoln\u00ed procesor<br \/>\nd\u0159\u00edve, ne\u017e je stanoven\u00e9 okno. Necht\u011bli bychom, aby takov\u00fd \u00fakol klesl v priorit\u011b,<br \/>\na t\u00edm p\u00e1dem z\u016fstane na stejn\u00e9 \u00farovni.<br \/>\n<img decoding=\"async\" alt=\"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)\" src=\"\/wp-content\/uploads\/2019\/04\/480d33a670fb62a639e5938dd59e30a1.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>Tento p\u0159\u00edklad ukazuje, jak bude algoritmus pracovat s takov\u00fdmi procesy \u2014 interaktivn\u00ed \u00fakol B, kter\u00fd pot\u0159ebuje CPU pouze na 1 ms p\u0159ed proveden\u00edm<br \/>\nprocesu vstupu-v\u00fdstupu, a dlouh\u00fd \u00fakol A, kter\u00fd neust\u00e1le vyu\u017e\u00edv\u00e1 CPU.<br \/>\nMLFQ udr\u017euje \u00fakol B s nejvy\u0161\u0161\u00ed prioritou, proto\u017ee neust\u00e1le osvobozuje<br \/>\nCPU. Pokud je B interaktivn\u00ed \u00fakol, algoritmus v takov\u00e9m p\u0159\u00edpad\u011b dos\u00e1hl<br \/>\nsv\u00e9ho c\u00edle rychle spou\u0161t\u011bt interaktivn\u00ed \u00fakoly.<\/p>\n<p><b>Probl\u00e9my se sou\u010dasn\u00fdm algoritmem MLFQ<\/b><\/p>\n<p>V p\u0159edchoz\u00edch p\u0159\u00edkladech jsme vytvo\u0159ili z\u00e1kladn\u00ed variantu MLFQ. A zd\u00e1 se, \u017ee funguje<br \/>\ndob\u0159e a spravedliv\u011b, rozd\u011bluje procesorov\u00fd \u010das mezi<br \/>\ndlouh\u00e9 \u00fakoly a umo\u017e\u0148uje kr\u00e1tk\u00fdm \u00fakol\u016fm nebo \u00fakol\u016fm s intenzivn\u00edm<br \/>\nI\/O zpracov\u00e1n\u00edm vykon\u00e1vat se rychle. Bohu\u017eel, tento p\u0159\u00edstup obsahuje n\u011bkolik<br \/>\nz\u00e1va\u017en\u00fdch probl\u00e9m\u016f.<br \/>\n<b>Za prv\u00e9<\/b>, probl\u00e9m hladu: pokud bude v syst\u00e9mu mnoho interaktivn\u00edch<br \/>\n\u00fakol\u016f, budou spot\u0159ebov\u00e1vat ve\u0161ker\u00fd procesorov\u00fd \u010das a t\u00edm p\u00e1dem \u017e\u00e1dn\u00fd dlouh\u00fd<br \/>\n\u00fakol nebude m\u00edt mo\u017enost vykon\u00e1vat se (hladov\u00ed).<\/p>\n<p><b>Za druh\u00e9<\/b>, chyt\u0159\u00ed u\u017eivatel\u00e9 by mohli ps\u00e1t sv\u00e9 programy tak, aby<br \/>\nobe\u0161li pl\u00e1nova\u010d. Obejit\u00ed spo\u010d\u00edv\u00e1 v tom, \u017ee ud\u011bl\u00e1te n\u011bco, co donut\u00ed<br \/>\npl\u00e1nova\u010d p\u0159id\u011blovat procesoru v\u00edce procesorov\u00e9ho \u010dasu. Algoritmus, kter\u00fd<br \/>\nbyl pops\u00e1n v\u00fd\u0161e, je zcela zraniteln\u00fd v\u016f\u010di podobn\u00fdm \u00fatok\u016fm: p\u0159ed t\u00edm, ne\u017e \u010dasov\u00fd \u00fasek t\u00e9m\u011b\u0159<br \/>\nskon\u010d\u00ed, je t\u0159eba prov\u00e9st operaci I\/O (na n\u011bjak\u00e9m, nez\u00e1le\u017e\u00ed na jak\u00e9m souboru)<br \/>\na t\u00edm uvolnit CPU. Takov\u00e9 chov\u00e1n\u00ed umo\u017en\u00ed z\u016fstat ve stejn\u00e9<br \/>\nfront\u011b a znovu z\u00edskat v\u011bt\u0161\u00ed procento procesorov\u00e9ho \u010dasu. Pokud se to provedete<br \/>\nspr\u00e1vn\u011b (nap\u0159\u00edklad vykon\u00e1vat se 99 % \u010dasu okna p\u0159ed uvoln\u011bn\u00edm CPU),<br \/>\ntakov\u00fd \u00fakol m\u016f\u017ee jednodu\u0161e monopolizovat procesor.<\/p>\n<p>Nakonec m\u016f\u017ee program m\u011bnit sv\u00e9 chov\u00e1n\u00ed v pr\u016fb\u011bhu \u010dasu. Ty \u00fakoly,<br \/>\nkter\u00e9 vyu\u017e\u00edvaly CPU, se mohou st\u00e1t interaktivn\u00edmi. V na\u0161em p\u0159\u00edkladu podobn\u00e9<br \/>\n\u00fakoly nedostanou adekv\u00e1tn\u00ed zach\u00e1zen\u00ed od pl\u00e1nova\u010de, proto\u017ee dostaly jin\u00e9<br \/>\n(p\u016fvodn\u00ed) interaktivn\u00ed \u00fakoly.<\/p>\n<p><u>Ot\u00e1zka do publika: jak\u00e9 \u00fatoky na pl\u00e1nova\u010d bylo mo\u017en\u00e9 prov\u00e1d\u011bt v modern\u00edm sv\u011bt\u011b?<br \/>\n<\/u><\/p>\n<h4>Pok attempt 2: Zvy\u0161ov\u00e1n\u00ed priority<\/h4>\n<p>Pokud se pokus\u00edme zm\u011bnit pravidla, uvid\u00edme, zda se n\u00e1m poda\u0159\u00ed vyhnout se probl\u00e9m\u016fm s<br \/>\nhladov\u011bn\u00edm. Co bychom mohli ud\u011blat, abychom zajistili, \u017ee \u00fakoly souvisej\u00edc\u00ed s<br \/>\nCPU dostanou sv\u016fj \u010das (i kdy\u017e ne na dlouho).<br \/>\nJako jednoduch\u00e9 \u0159e\u0161en\u00ed probl\u00e9mu lze navrhnout pravideln\u011b<br \/>\nzvy\u0161ovat prioritu v\u0161ech takov\u00fdch \u00fakol\u016f v syst\u00e9mu. Existuje mnoho zp\u016fsob\u016f<br \/>\njak toho dos\u00e1hnout, zkuste implementovat jako p\u0159\u00edklad n\u011bco jednoduch\u00e9ho: p\u0159ev\u00e9st<br \/>\nnajednou v\u0161echny \u00fakoly na nejvy\u0161\u0161\u00ed prioritu, odsud nov\u00e9 pravidlo:<\/p>\n<ul>\n<li><b>Rule5<\/b>: Po uplynut\u00ed ur\u010dit\u00e9 doby S p\u0159ev\u00e9st v\u0161echny \u00fakoly v syst\u00e9mu do nejvy\u0161\u0161\u00ed fronty.<\/li>\n<\/ul>\n<p>Na\u0161e nov\u00e9 pravidlo \u0159e\u0161\u00ed dv\u011b probl\u00e9my najednou. Za prv\u00e9, procesy<br \/>\nzaru\u010den\u011b netrp\u00ed hladov\u011bn\u00edm: \u00fakoly, kter\u00e9 se nach\u00e1zej\u00ed v nejvy\u0161\u0161\u00ed front\u011b, budou d\u011blit<br \/>\nprocesorov\u00fd \u010das podle algoritmu RR a t\u00edm p\u00e1dem v\u0161echny procesy z\u00edskaj\u00ed<br \/>\nprocesorov\u00fd \u010das. Za druh\u00e9, pokud se n\u011bjak\u00fd proces, kter\u00fd d\u0159\u00edve vyu\u017e\u00edval<br \/>\npouze procesor, stane interaktivn\u00edm, z\u016fstane ve front\u011b s vy\u0161\u0161\u00edmi<br \/>\nprioritami pot\u00e9, co jednou z\u00edsk\u00e1 pov\u00fd\u0161en\u00ed priority na nejvy\u0161\u0161\u00ed.<br \/>\nZv\u00e1\u017e\u00edme p\u0159\u00edklad. V tomto sc\u00e9n\u00e1\u0159i zva\u017eme jeden proces vyu\u017e\u00edvaj\u00edc\u00ed<br \/>\n<img decoding=\"async\" alt=\"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)\" src=\"\/wp-content\/uploads\/2019\/04\/3b8d879ab4479622684b126ec5af6af3.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>CPU a dva interaktivn\u00ed, kr\u00e1tk\u00e9 procesy. Vlevo na obr\u00e1zku je zn\u00e1zorn\u011bno chov\u00e1n\u00ed bez povy\u0161ov\u00e1n\u00ed priority, tak\u017ee dlouh\u00e1 \u00faloha za\u010dne hladov\u011bt po p\u0159\u00edchodu dvou interaktivn\u00edch \u00faloh do syst\u00e9mu. Na obr\u00e1zku vpravo se povy\u0161ov\u00e1n\u00ed priority prov\u00e1d\u00ed ka\u017ed\u00fdch 50ms a t\u00edm p\u00e1dem v\u0161echny procesy zaru\u010den\u011b z\u00edskaj\u00ed procesorov\u00fd \u010das a budou se periodicky spou\u0161t\u011bt. 50ms bylo v tomto p\u0159\u00edpad\u011b zvoleno jako p\u0159\u00edklad, ve skute\u010dnosti je toto \u010d\u00edslo trochu vy\u0161\u0161\u00ed.<br \/>\nJe z\u0159ejm\u00e9, \u017ee p\u0159id\u00e1n\u00ed doby periodick\u00e9ho povy\u0161ov\u00e1n\u00ed S vyvol\u00e1v\u00e1<br \/>\nlogickou ot\u00e1zku: jak\u00e1 hodnota by m\u011bla b\u00fdt nastavena? Jeden z v\u00e1\u017een\u00fdch<br \/>\nsyst\u00e9mov\u00fdch in\u017een\u00fdr\u016f John Ousterhout naz\u00fdval podobn\u00e9 hodnoty v syst\u00e9mech jako voo-doo<br \/>\nkonstanty, proto\u017ee do ur\u010dit\u00e9 m\u00edry vy\u017eadovaly \u010dernou magii pro spr\u00e1vn\u00e9<br \/>\nnastaven\u00ed. A, bohu\u017eel, S m\u00e1 takovou p\u0159\u00edchu\u0165. Pokud nastav\u00edte hodnotu p\u0159\u00edli\u0161<br \/>\nvysokou \u2013 dlouh\u00e9 \u00falohy za\u010dnou hladov\u011bt. A pokud nastav\u00edte p\u0159\u00edli\u0161 n\u00edzkou hodnotu,<br \/>\ninteraktivn\u00ed \u00falohy nedostanou dostate\u010dn\u00fd procesorov\u00fd \u010das.<\/p>\n<h4>Pokus 3: Nejlep\u0161\u00ed sledov\u00e1n\u00ed<\/h4>\n<p>Nyn\u00ed m\u00e1me dal\u0161\u00ed probl\u00e9m, kter\u00fd je t\u0159eba vy\u0159e\u0161it: jak nezap\u0159\u00edt<br \/>\nn\u00e1\u0161 pl\u00e1nova\u010d? Na vin\u011b jsou pravidla 4a, 4b, kter\u00e1 umo\u017e\u0148uj\u00ed \u00fakolu udr\u017eovat prioritu t\u00edm, \u017ee uvoln\u00ed procesor<br \/>\np\u0159ed uplynut\u00edm vyhrazen\u00e9ho \u010dasu. Jak se s t\u00edm vypo\u0159\u00e1dat?<br \/>\n\u0158e\u0161en\u00edm v tomto p\u0159\u00edpad\u011b m\u016f\u017ee b\u00fdt nejlep\u0161\u00ed sledov\u00e1n\u00ed \u010dasu CPU na ka\u017ed\u00e9<br \/>\n\u00farovni MLFQ. M\u00edsto toho, abychom zapomn\u011bli \u010das, kter\u00fd program pou\u017eil.<br \/>\n\u00farove\u0148 MLFQ. M\u00edsto toho, aby se zapomn\u011blo na \u010das, kter\u00fd program pou\u017eil<br \/>\nP\u0159i ur\u010den\u00ed p\u0159id\u011blen\u00e9ho \u010dasu procesoru je t\u0159eba to vz\u00edt v \u00favahu a zachovat. Jakmile<br \/>\nproces spot\u0159eboval p\u0159id\u011blen\u00fd \u010das, je t\u0159eba jeho prioritu sn\u00ed\u017eit na dal\u0161\u00ed<br \/>\n\u00farove\u0148. Nyn\u00ed nez\u00e1le\u017e\u00ed na tom, jak proces sv\u016fj \u010das vyu\u017eije \u2014 zda<br \/>\nst\u00e1le vypo\u010d\u00edt\u00e1v\u00e1 na procesoru, nebo prov\u00e1d\u00ed mnoho vol\u00e1n\u00ed. Takto<br \/>\nbylo t\u0159eba p\u0159epsat pravidlo 4 n\u00e1sleduj\u00edc\u00edm zp\u016fsobem:<\/p>\n<ul>\n<li><b>Rule4<\/b>: Jakmile \u00fakol spot\u0159eboval p\u0159id\u011blen\u00fd \u010das v aktu\u00e1ln\u00edm queue (bez ohledu na to, kolikr\u00e1t uvolnil CPU), jeho priorita se sn\u00ed\u017e\u00ed (pohne se dol\u016f v queue).<\/li>\n<\/ul>\n<p>Pod\u00edvejme se na p\u0159\u00edklad:<br \/>\n<img decoding=\"async\" alt=\"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)\" src=\"\/wp-content\/uploads\/2019\/04\/18c53e62b9b342d14a23995bd422ef5e.png\" style=\"display:block;margin: 0 auto;\">\u201e<\/p>\n<p>Na obr\u00e1zku je zn\u00e1zorn\u011bno, co se stane, kdy\u017e se pokus\u00edte podv\u00e9st pl\u00e1nova\u010d, jako<br \/>\nby to bylo s p\u0159edchoz\u00edmi pravidly 4a, 4b, vznikne v\u00fdsledek vlevo. S nov\u00fdm<br \/>\npravidlem \u2014 v\u00fdsledek vpravo. P\u0159ed zapojen\u00edm jak\u00e9koli ochrany mohl jak\u00fdkoli proces volat I\/O do dokon\u010den\u00ed a<br \/>\nt\u00edmto zp\u016fsobem dominovat nad CPU; po zapnut\u00ed ochrany, bez ohledu na chov\u00e1n\u00ed<br \/>\nI\/O, bude p\u0159esto st\u00e1le klesat v queue a t\u00edm nem\u016f\u017ee nepoctiv\u011b<br \/>\novl\u00e1dnout CPU prost\u0159edky.<\/p>\n<h4>Zlep\u0161en\u00ed MLFQ a dal\u0161\u00ed probl\u00e9my<\/h4>\n<p>S uveden\u00fdmi vylep\u0161en\u00edmi vznikaj\u00ed nov\u00e9 probl\u00e9my: jedn\u00edm z hlavn\u00edch<br \/>\not\u00e1zky je, jak parametrizovat takov\u00fd pl\u00e1nova\u010d? Tedy, kolik by m\u011blo b\u00fdt<br \/>\nqueue? Jak\u00e1 by m\u011bla b\u00fdt velikost pracovn\u00edho okna programu v r\u00e1mci queue? Jak<br \/>\n\u010dasto by se m\u011bla priorita programu zvy\u0161ovat, aby se zabr\u00e1nilo hladu a<br \/>\nzohlednilo zm\u011bny chov\u00e1n\u00ed programu? Na tyto ot\u00e1zky nelze jednodu\u0161e odpov\u011bd\u011bt a pouze experimenty s zat\u011b\u017eov\u00e1n\u00edm a n\u00e1sledn\u00e1 konfigurace<br \/>\npl\u00e1nova\u010de mohou p\u0159in\u00e9st jist\u00e9 uspokojiv\u00e9 vyv\u00e1\u017een\u00ed.<br \/>\nNap\u0159\u00edklad v\u011bt\u0161ina implementac\u00ed MLFQ umo\u017e\u0148uje p\u0159i\u0159azovat r\u016fzn\u00e9<\/p>\n<p>\u010dasov\u00e9 intervaly r\u016fzn\u00fdm queue. Vysokopr\u016fm\u011brn\u00e9 queue obvykle<br \/>\ndost\u00e1vaj\u00ed kr\u00e1tk\u00e9 intervaly. Tyto queue se skl\u00e1daj\u00ed z interaktivn\u00edch \u00faloh,<br \/>\nu kter\u00fdch je p\u0159ep\u00edn\u00e1n\u00ed pom\u011brn\u011b citliv\u00e9 a m\u011blo by trvat 10 nebo m\u00e9n\u011b<br \/>\nms. Naopak n\u00edzkopr\u016fm\u011brn\u00e9 queue se skl\u00e1daj\u00ed z dlouh\u00fdch \u00faloh, kter\u00e9 vyu\u017e\u00edvaj\u00ed<br \/>\nCPU. A v tomto p\u0159\u00edpad\u011b se dlouh\u00e9 \u010dasov\u00e9 intervaly hod\u00ed velmi dob\u0159e (100 ms).<br \/>\nV tomto p\u0159\u00edkladu jsou 2 \u00falohy, kter\u00e9 pracovaly ve vysokopr\u016fm\u011brn\u00e9 queue 20<br \/>\n<img decoding=\"async\" alt=\"Opera\u010dn\u00ed syst\u00e9my: T\u0159i snadn\u00e9 kusy. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: V\u00edce\u00farov\u0148ov\u00e1 zp\u011btn\u00e1 vazba (p\u0159eklad)\" src=\"\/wp-content\/uploads\/2019\/04\/4eb6c6669034adeb1615c29454fbb1dc.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>V tomto p\u0159\u00edkladu existuj\u00ed 2 \u00falohy, kter\u00e9 pracovaly ve vysoce prioritn\u00ed front\u011b 20<br \/>\nms, rozd\u011blen\u00e9 do oken po 10 ms. 40 ms ve st\u0159edn\u00ed front\u011b (okno 20 ms) a v n\u00edzk\u00e9 priorit\u011b<br \/>\ntempor\u00e1rn\u00ed okno se stalo 40 ms, kde \u00fakoly dokon\u010dily svou pr\u00e1ci.<\/p>\n<p>Realizace MLFQ v OS Solaris \u2013 t\u0159\u00edda pl\u00e1nova\u010d\u016f, kter\u00e9 d\u011bl\u00ed podle \u010dasu.<br \/>\nPl\u00e1nova\u010d poskytuje sadu tabulek, kter\u00e9 p\u0159esn\u011b definuj\u00ed, jak by m\u011bl<br \/>\nm\u011bnit prioritu procesu v pr\u016fb\u011bhu jeho \u017eivotnosti, jak\u00e1 by m\u011bla b\u00fdt velikost<br \/>\nalokovan\u00e9ho okna a jak \u010dasto je t\u0159eba zvy\u0161ovat priority \u00fakolu. Administr\u00e1tor<br \/>\nsyst\u00e9mu m\u016f\u017ee interagovat s touto tabulkou a p\u0159inutit pl\u00e1nova\u010d jednat<br \/>\njinak. Ve v\u00fdchoz\u00edm nastaven\u00ed obsahuje tato tabulka 60 front s postupn\u00fdm zvy\u0161ov\u00e1n\u00edm<br \/>\nvelikosti okna od 20 ms (vysok\u00e1 priorita) a\u017e po n\u011bkolik set ms (nejni\u017e\u0161\u00ed priorita), a<br \/>\ntak\u00e9 s boostem v\u0161ech \u00fakol\u016f jednou za sekundu.<\/p>\n<p>Jin\u00e9 MLFQ pl\u00e1nova\u010de nepou\u017e\u00edvaj\u00ed tabulku nebo n\u011bjak\u00e1 konkr\u00e9tn\u00ed<br \/>\npravidla, kter\u00e1 jsou pops\u00e1na v t\u00e9to p\u0159edn\u00e1\u0161ce, naopak po\u010d\u00edtaj\u00ed priority pomoc\u00ed<br \/>\nmatematick\u00fdch vzorc\u016f. Tak nap\u0159\u00edklad pl\u00e1nova\u010d ve FreeBSD pou\u017e\u00edv\u00e1 vzorec pro<br \/>\nv\u00fdpo\u010det aktu\u00e1ln\u00ed priority \u00fakolu, zalo\u017een\u00fd na tom, kolik proces<br \/>\npou\u017eil CPU. Krom\u011b toho, vyu\u017eit\u00ed CPU v pr\u016fb\u011bhu \u010dasu kles\u00e1, a t\u00edm<br \/>\nzv\u00fd\u0161en\u00ed priority prob\u00edh\u00e1 pon\u011bkud jinak, ne\u017e je pops\u00e1no v\u00fd\u0161e. To jsou tak<br \/>\nzvan\u00e9 decay algoritmy. Od verze 7.1 ve FreeBSD je pou\u017e\u00edv\u00e1n pl\u00e1nova\u010d ULE.<\/p>\n<p>Nakonec maj\u00ed mnoh\u00e9 pl\u00e1nova\u010de dal\u0161\u00ed vlastnosti. Nap\u0159\u00edklad, n\u011bkter\u00e9<br \/>\npl\u00e1nova\u010de vyhrad\u00ed nejvy\u0161\u0161\u00ed \u00farovn\u011b pro fungov\u00e1n\u00ed opera\u010dn\u00edho syst\u00e9mu, a t\u00edm<br \/>\n\u017e\u00e1dn\u00fd u\u017eivatelsk\u00fd proces nem\u016f\u017ee z\u00edskat nejvy\u0161\u0161\u00ed prioritu v<br \/>\nsyst\u00e9mu. N\u011bkter\u00e9 syst\u00e9my umo\u017e\u0148uj\u00ed d\u00e1vat rady, aby pomohly<br \/>\npl\u00e1nova\u010di spr\u00e1vn\u011b nastavovat priority. Nap\u0159\u00edklad, pomoc\u00ed p\u0159\u00edkazu <b>nice<\/b><br \/>\nje mo\u017en\u00e9 zvy\u0161ovat nebo sni\u017eovat prioritu \u00fakolu, a t\u00edm zv\u00fd\u0161it nebo<br \/>\nsn\u00ed\u017eit \u0161ance programu na procesorov\u00fd \u010das.<\/p>\n<h3>MLFQ: Z\u00e1v\u011bry<\/h3>\n<p>Popisovali jsme p\u0159\u00edstup k pl\u00e1nov\u00e1n\u00ed, kter\u00fd se naz\u00fdv\u00e1 MLFQ. Jeho n\u00e1zev<br \/>\nje zalo\u017een na principu fungov\u00e1n\u00ed \u2013 m\u00e1 n\u011bkolik front a pou\u017e\u00edv\u00e1 zp\u011btnou vazbu<br \/>\nk ur\u010den\u00ed priority \u00fakolu.<br \/>\nKone\u010dn\u00e1 podoba pravidel bude n\u00e1sleduj\u00edc\u00ed:<\/p>\n<ul>\n<li><b>Pravidlo 1<\/b>: Pokud priorita(A) &gt; priorita(B), \u00fakol A bude spu\u0161t\u011bn (B nebude)<\/li>\n<li><b>Pravidlo 2<\/b>: Pokud je priorita(A) = priorita(B), A a B se spou\u0161t\u00ed pomoc\u00ed RR<\/li>\n<li><b>Pravidlo3<\/b>: Kdy\u017e \u00faloha p\u0159ijde do syst\u00e9mu, je um\u00edst\u011bna do fronty s nejvy\u0161\u0161\u00ed prioritou.<\/li>\n<li><b>Rule4<\/b>: Jakmile \u00fakol spot\u0159eboval p\u0159id\u011blen\u00fd \u010das v aktu\u00e1ln\u00edm queue (bez ohledu na to, kolikr\u00e1t uvolnil CPU), jeho priorita se sn\u00ed\u017e\u00ed (pohne se dol\u016f v queue).<\/li>\n<li><b>Rule5<\/b>: Po uplynut\u00ed ur\u010dit\u00e9 doby S p\u0159ev\u00e9st v\u0161echny \u00fakoly v syst\u00e9mu do nejvy\u0161\u0161\u00ed fronty.<\/li>\n<\/ul>\n<p>MLFQ je zaj\u00edmav\u00fd z n\u00e1sleduj\u00edc\u00edho d\u016fvodu \u2014 m\u00edsto aby vy\u017eadoval znalosti o<br \/>\npovaze \u00falohy p\u0159edem, algoritmus se u\u010d\u00ed z minul\u00e9ho chov\u00e1n\u00ed \u00falohy a p\u0159i\u0159azuje<br \/>\npriority odpov\u00eddaj\u00edc\u00edm zp\u016fsobem. Sna\u017e\u00ed se t\u00edm p\u00e1dem sed\u011bt na dvou \u017eidl\u00edch \u2014 dos\u00e1hnout v\u00fdkonu pro mal\u00e9 \u00falohy (SJF, STCF) a spravedliv\u011b spou\u0161t\u011bt dlouh\u00e9,<br \/>\nCPU-n\u00e1ro\u010dn\u00e9 \u00falohy. Proto mnoho syst\u00e9m\u016f, v\u010detn\u011b BSD a jejich odvozenin,<br \/>\nSolaris, Windows, Mac pou\u017e\u00edvaj\u00ed jako pl\u00e1nova\u010d n\u011bjakou formu algoritmu<br \/>\nMLFQ jako z\u00e1kladn\u00ed z\u00e1klad.<\/p>\n<h4>Dal\u0161\u00ed materi\u00e1ly:<\/h4>\n<ol>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/manpages.debian.org\/stretch\/manpages\/sched.7.en.html\">manpages.debian.org\/stretch\/manpages\/sched.7.en.html<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Scheduling_\">en.wikipedia.org\/wiki\/Scheduling_<\/a><\/noindex>(computing)<\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/pages.lip6.fr\/Julia.Lawall\/atc18-bouron.pdf\">pages.lip6.fr\/Julia.Lawall\/atc18-bouron.pdf<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/www.usenix.org\/legacy\/event\/bsdcon03\/tech\/full_papers\/roberson\/roberson.pdf\">www.usenix.org\/legacy\/event\/bsdcon03\/tech\/full_papers\/roberson\/roberson.pdf<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/chebykin.org\/freebsd-process-scheduling\">chebykin.org\/freebsd-process-scheduling<\/a><\/noindex><\/li>\n<\/ol>\n<p>Zdroj: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/450116\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":24514,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32730","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.3 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.3\" \/>\n\t\t<meta property=\"og:locale\" content=\"cs_CZ\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47Operating Systems: Three Easy Pieces. Part 5: \u041f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435: Multi-Level Feedback Queue (\u043f\u0435\u0440\u0435\u0432\u043e\u0434) | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T18:48:36+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2021-02-08T09:40:35+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Operating Systems: Three Easy Pieces. \u010c\u00e1st 5: Pl\u00e1nov\u00e1n\u00ed: Multi-Level Feedback Queue (p\u0159eklad) | ProHoster","description":"\u00davod do opera\u010dn\u00edch syst\u00e9m\u016f Ahoj, Habr! Chci v\u00e1m p\u0159edstavit svou s\u00e9rii p\u0159eklad\u016f jedn\u00e9 zaj\u00edmav\u00e9 literatury \u2014 OSTEP.","canonical_url":"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"cs_CZ","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47Operating Systems: Three Easy Pieces. Part 5: \u041f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435: Multi-Level Feedback Queue (\u043f\u0435\u0440\u0435\u0432\u043e\u0434) | ProHoster","og:description":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP.","og:url":"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:48:36+00:00","article:modified_time":"2021-02-08T09:40:35+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"32730","title":null,"description":"","keywords":"","keyphrases":null,"primary_term":null,"canonical_url":"","og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 12:18:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:53:25","updated":"2026-01-21 12:18:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts\/32730","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/comments?post=32730"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts\/32730\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media\/24514"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media?parent=32730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/categories?post=32730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/tags?post=32730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}