CACHE
                                    -=-=-=-

      MSDOS didn't get as bad as it is overnight -- it took over ten years
                            of careful development.

          Většina cache používá  jednoduchý  algoritmus: při čtení z disku
      se načte  větší jednotka  (jedna  stopa), která se uloží do bufferu.
      Ten se  přidá  na  začátek  seznamu a zahashuje  do  tabulky.  Pokud
      program  chce  číst data,  která již jsou v bufferu,  systém to přes
      hashovací  tabulku najde a ušetří tak jeden přístup.  Navíc nalezený
      buffer  posune opět na začátek  seznamu. Pokud je cache plná, uvolní
      se stránka z konce seznamu - tak se smaže  blok, který nejdéle nikdo
      nepotřeboval. To se nazývá LRU cache (last recently used).

          Pro  ukládání je  algoritmus  podobný.  Ukládání  ale  není  tak
      důležité - může  probíhat  asynchroně,  zatímco  čtení  je  většinou
      synchroní a tak musí být co nejrychlejší.

          Existuje  mnoho  vylepšení  tohoto  algoritmu,  které  se  snaží
      číst  větší  bloky.  Nejdůležitější je  read-ahead.  Ten  čte  bloky
      za  posledním  přistupovaným.  To má  tu  výhodu,  že v případě,  že
      program bude chtít další data, nebude muset čekat na jejich  načtení
      a tak i čtení  potom  funguje  asynchroně.  Stejně  při  ukládání se
      vyplatí napřed bloky sdužit do větších skupin.

          Jsou  dva  hlavní  přístupy  ke  cachování.  Master  cache  - ta
      přistupuje k disku  jako k velkému  souboru a cachuje ho  před  tím,
      než se dostane k ovladači  filesystemu. Tento přístup je jednoduchý,
      ale má nevýhodu v tom, že někdy může načítat zbytečná data apod.

          Druhý   přístup je  slave   (Inode)   cache.  Ta  cachuje   data
      v jednotlivých  souborech.  To  ale  zase  má  tu  nevýhodu,  že  se
      nechachují filesystémové  informace (Inode tabulky apod.). Na druhou
      stranu ale tohoto jde využít a napsat speciální cache pro jednotlivé
      části, což může přinést další zrychlení a zvýšení bezpečnosti.

          Protože  každý z přístupů má své výhody, oba postupy se většinou
      kombinují.  Linux  například  používá  directory  cache,  která drží
      informace o soborech,  dělá  hashovací  tabulky  pro  adresáře a tak
      pouhý  výpis  adresáře  je téměř  třikrát  tychlejší.  Buffer  cache
      implementuje  klasickou  cache  pro  disky.  Umí  ale  navíc s vyšší
      prioritou  ukládat  důležitá data. O read ahead se stará filesystém.
      A nakonec Linux implementuje page cache. Ta je propojená s mapováním
      paměti. Všechny namapované soubory handlovány přes tuto cache. Proto
      v případě, že někdo jiný čte, nebo  mapuje ten samý soubor,  použije
      se stených stránek. Navíc se tato cache stará o speciální  readahead
      a algoritmus pro vyhledávání  nepoužitých stránek (protože procesory
      většinou  neumožňují  implementovat  LRU cache).  Také to odstraňuje
      potíže se spožděnou aktualizací dat na disku.

          Další   šikovné   rozšíření  je  spojení  s  memorymanagementem.
      Nejjednodušší věc je, že cache bude moci růst přes  veškerou  volnou
      cache a do swapovací  rutiny se přidá  zmenšování  cache.  Není  pak
      nutné předem nastavovat velikost cache.

          Poslední  jednoduché  rozšíření je bdflush  daemon.  Ten  jednou
      za čas  ukládá  cache na disk. To má zase  výhodu v tom, že ukládání
      probíhá  asynchroně a ne až v situsci, kdy nějaký  proces chce číst,
      nebo zapisovat.  Navíc to zaručuje, že se data uloží v rozumném čase
      na disk.

          Cache je největším  problémem  mikrojádrových  OS,  protože  tam
      nejde pořádně implementovat.


            výheň