Scheduler
                                  -=-=-=-=-=-

      Once upon a time there was a DOS user who saw Unix, and saw that it
      was good. After typing cp on his DOS machine at home, he downloaded
       GNU's unix tools ported to DOS and installed them. He rm'd, cp'd,
      and mv'd happily for many days, and upon finding elvis, he vi'd and
       was happy. After a long day at work (on a Unix box) he came home,
        started editing a file, and couldn't figure out why he couldn't
                    suspend vi (w/ ctrl-z) to do a compile.
                                 -- Erik Troan

          Scheduler   (plánovač)  se  stará o  přepínání   úloh   (procesů
      a threadů).  Funguje  přibližně tak, že má seznam všech úloch, které
      by chtěly běžet, jednu z nich vybere a spustí.

          Ze začátku byl scheduler  aktivován  procesem.  Pokud měl proces
      pocit, že nechce  nic dělat a rozhodl se na něco  čekat,  spustil se
      scheduler a ten vybral jiný štastný  proces. To mělo ten nedostatek,
      že pokud se nějaký proces  zadřel a nechtěl  nikoho pustit ke slovu,
      ostatní měli smůlu. (nepreemtivní multitásking)

          Opravdové multitáskingové systémy ale mají scheduler  aktivovaný
      automaticky s časovače  (desetkrát  a více  do  sekundy)  ten  potom
      procesy  rychle  přepíná a vytváří  tak iluzi  toho, že proesy  běží
      zároveň.

          Na scheduler se klade několik poněkud protichůdných požadavků
       - měl  by  být  co  nejrychlejší,  aby  se  mohl   aktivovat  často
         a multitasking byl plynulý
       - měl by být co  nejspravedlivější a něpřidělovat  nějaké  aplikaci
         výrazně více času než jiné
       - měl by  upřednostňovat  interaktivní  úlohy  před  těmy,  co něco
         počítají na pozadí.

                               UNIXový scheduler

          V UNIXu má každý  proces dvě priority.  Jedna  priorita  funguje
      tak, že pokaždé co proces dostane nějaký čas, jeho priorita stoupne.
      Pokud proces spí, jeho priorita klesá. Scheduler potom vybíra proces
      s nejnišší  prioritou.  Proto  procesy co  počítají  svoji  prioritu
      postupně snižují a naopak procesy co spí a čekají na uživatele svoji
      prioritu  zvedají a tak v okamžiku, kdy uživatel  něco zadá a proces
      se zbudí dostane se rychle ke slovu.

          Druhá  priorita se  nastavuje  uživatelem  pomocí  volání  nice.
      Určuje  celkovou  prioritu  procesu.  Procesy  se stejnou  prioritou
      se dělí o CPU  půl na půl.  Procesy s nejvyšší  prioritou  běží  jen
      v případě, že žádný jiný  nechce. A tak můžete  snížit  priotitu těm
      procesům, u kterých nechete, aby vás zdržovaly při práci.

                               Stromový scheduler

          UNIXový  scheduler  má  jednu  základní   nevýhodu.  V  případě,
      že jeden proces si vytvoří více threadů, jsou všechny  thready brány
      jako  rovnocené  procesy.  Proto  proces  mající 10 threadů  dostane
      10krát  více času než proces s jedním  threadem.  Podobně  uživatel,
      který  nastartuje 10 procesů  dostane více času, než jiný  uživatel.
      Navíc v případě, že běží  opravdu  hodně  procesů,  je docela  těžké
      je rychle  seshedulovat.  Tyto  problémy  řeší  stromový  scheduler.
      Zde jsou procesy  rozděleny do skupin.  Například na nejvyšší úrovni
      stromu jsou větve podle jendotlivých  uživatelů, pod nimi jsou větve
      podle  procesů a nakonec jsou jednotlivé  thready.  Schedulování pak
      běží po úrovních.  Napřed se rozhodne, který  uživatel  dostane CPU.
      Potom to samé pro procesy a nakonec pro thready. Takže  scheduler je
      spravedlivější a nikdy  nemusí se probírat všemi  procesy, ale jenom
      určitou úrovní stromu.

                          Scheduler přes náhodná čísla

          Scheduler  přes priority  musí být velmi  pečlivě  doladěn  tak,
      aby žádnému  procesu nestoupla  priorita příliš, nebo aby ji nejakým
      fíglem  nemohl  nahamounit  (třeba  tím,  že  bude  proces  neustále
      startovat a ukončovat).  Jinak se  může  stát, že  přepínaní  nebude
      příliš  plynulé.  Toto  lze  řešit  náhodným  přepínáním.  Napřed si
      vytvoříte  koláč, kde každý  proces  zabírá tak velký kus,  jakou má
      prioritu.  Potom tam hodíte  kuličku a kde se kulička  zastaví,  ten
      proces se spustí. A tak se někdy  stane, že i procesy z hodně  nízou
      prioritou se dostanou ke slovu a priority  nemusí být tak  vyrovnané
      jako v předhozím scheduleru.

          Takový scheduler (spolu se stromem) má například Vsta.

                               Evoluční scheduler

          Protože  scheduling patří mezi MP úplné  úlohy a tedy není známý
      rozumně rychlý algoritmus  podávající  optimální  výsledky, je možné
      nasadit i genetické  algoritmy.  Scheduler pak funguje  podobně jako
      ten náhodný.


            výheň