34 - Principy a struktury správy souborů a správy paměti

Správa souborů

Fyzický disk

části disku: cylindr, hlava, talíř (platter, disk), stopa, sektor

Zdroj: 4. přednáška IOS z ak. roku 2009/1010 - autor: doc. Vojnar

adresování sektorů
- CHS = cylindr, hlava (nejběžnějši 1-6), sektor (typicky 512B)
- LBA = lineární bloková adresa (pouze číslo 0 .. N)
rozmístění sektorů na disku:
- dříve se používalo prokládání: sektory neležely fyzicky za sebou, protože pomalé řadiče disků, by na ně nestíhali zapisovat/číst a nemuselo se čekat na další otočení disku
typy diskových rozhraní:
- ATA (IDE)/SATA
- SCSI/SAS, USB, FireWire
hierarchie pamětí:
- (stoupá kapacita, ale klesá rychlost (i cena/B))
1. primární paměti: RAM, registry, cache
2. sekundární paměti: disky
3. terciární paměti: CD, DVD, pásky
parametry disků:
- přístupová doba = doba nastavení hlav + rotační zpoždění
- rozdílné značení velikosti u prodejců (1000B = 1KiB, ale 1024B=1KB)
- nástup SSD disků (Solid State Disk)
  - založené na flash pamětech ⇒ mechanická odolnost, tichý provoz
  - rychlejší náběh, náhodný přístup, pomalejší zápis
  - NAND flash SSD jsou organizovány do stránek (typicky 4KiB) a ty do bloků (typicky 128 stránek, tj. 512KiB)
cluster
- Alokační blok (2ⁿ sektorů) - nejmenší jednotka diskového prostoru, se kterou OS umožňuje pracovat uživatelům
přístup na disk:
- přenos z/na disk je typicky řízen řadičem disku s využitím technologie přímého přístupu do paměti (DMA)
- o ukončení operací či chybách informuje řadič procesor (a na něm bežící jádro OS) pomocí přerušení
- pořadí bloku čtených/zapisovaných na disk ovlivňuje plánovač diskových operací
- přicházející požadavky na čtení/zápis jsou ukládány do vyrovnávací paměti a jejich pořadí je případně měněno tak, aby se minimalizovala režie diskových operací
Virtuální souborový systém (VFS) - vrstva, která zastřešuje všechny použité souborové systémy (ufs, ext, NTFS, FAT,…) a umožňuje s nimi pracovat jednotným, abstraktním způsobem
Síťové souborové systémy: NFS, …
zabezpečení disků:
- ECC = Error Correction Code: k užitečným datům sektoru si ukládá redundantní data, která umožňují opravu
- S.M.A.R.T. – Self Monitoring Analysis and Reporting Technology - statistiky
- disková pole (RAIDy)
1. RAID 0:
  - následné bloky jsou rozmístěny na různých discích cyklicky za sebou
  - vysoká výkonnost, žádná redundace, žádná ochrana při pádu jednoho z disků
2. RAID 1: (zrcadlení)
  - všechna data se ukládají na dva disky
  - velká redundance
3. RAID 2:
  - každý bajt je rozdělen po bitech na více disků, používají se navíc disky s EEC (zabezpečení disků)
  - chybu na 1 disku lze opravit
4. RAID 3:
  - sekvence bajtů jsou rozděleny na části uložené na různých discích
  - používá se disk s paritami
5. RAID 4:
  - bloky dat uložené na různých discích a paritní bloky na zvláštním disku
6. RAID 5:
  - obdoba RAID 4, ale paritní bloky jsou rozdělené na více discích → odpadá přetížení paritního disku
7. RAID 6:
  - vylepšení RAID 5
  - parita je uložena 2x na různých discích, proto se dokáže vyrovnat se ztrátou více než jednoho disku

Zdroj obrázků: http://cs.wikipedia.org/wiki/RAID

Logický disk

v pc se fyzické disky dělí na logické (partitions) pomocí:
- MBR (Master Boot Record)
  - nultý sektor na disku obsahující tabulku diskových oblastí (4 oblasti, kde poslední může být rozšířená disková oblast)
  1. EBR (Extended Boot Record)
    - odkazuje na ni případná 4. rozšířená disková oblast
    - je v ní popsáno další rozdělení fyzických disků na logické
- LVM (Logical Volume Manager)
  - umožňuje tvorbu logických disků přesahující hranici fyz. disku a případnou následující změnu velikosti

Žurnálování

žurnál
- slouží pro záznam modifikovaných metadat (příp. i dat) před jejich zápisem na disk
- obvykle implementován jako cyklicky přepisovaný buffer ve speciální oblasti disku
- využívají známé souborové systémy (ext3, ext4, ufs, ReiserFS, XFS, JFS, NTFS, …)
alternativy: např. copy-on-write

Klasický UNIXový systém souboru (FS)

boot block - pro zavedení systému při startu
super block - informace o souborovém systému (typ, velikost, počet i-uzů, volné místo, volné i-bloky, kořenový adresář,…)
tabulka i-uzlů - tabulka s popisy souborů
datové bloky - data souborů a bloky pro nepřímé odkazy

i-uzel - základní datová struktura popisující soubor v UNIXu
- jiné způsoby: B+ stromy, kontinuální uložení

FHS = Filesystem Hierarchy Standard - typická struktura souborů v UNIXu (/bin, /dev, /etc, …)
tři typy souborů
1. obyčejné soubory
2. adresáře
3. speciální soubory:
  1. symbolické odkazy
  2. roury (pojmenované, nepojmenované)
  3. sockety
  4. periferie (blokové, znakové)
adresář - soubor obsahující seznam dvojic - “hard-links” (jméno souboru a číslo uzlu)
mazání souboru - ruší pevný odkaz a snižuje počítadlo odkazu v i-uzlu, dokud je počítadlo nenulové, soubor se nemaže
ACL - Access control list
- v UNIXu jsou typicky rozlišena práva pro vlastníka, skupinu a ostatní
- UID: číslo identifikující uživatele (root UID = 0)
- GID: číslo identifikující skupinu uživatelů
- Sticky bit - příznak, který nedovoluje rušit cizí soubory v adresáři, i když mají všichni právo zápisu
propůjčení práv - Vlastník programu muže propujčit svoje práva komukoli, kdo spustí program s nastaveným SUID

Správa paměti

je soubor metod, které operační systém používá při přidělování operační paměti jednotlivým procesům, které jsou spuštěny
může zajišťovat i následné uvolňování paměti, nastavovat ochranu paměti a eventuálně i správu adresace paměti
všechny tyto činnosti v operačním systému zajišťuje modul správy paměti
pro některé z výše uvedených úkolů je nutná hardwarová podpora uvnitř procesoru
rozlišujeme 2 typy adresových prostorů:
1. logický adresový prostor (LAP) - virtuální adresový prostor
2. fyzický adresový prostor (FAP) - adresový prostor fyzických adres paměti
pro komunikaci LAP a FAP je nutné překládat logické adresy na fyzické a naopak ⇒ slouží k tomu hardwarová jednotka MMU (Memory Managment Unit), která dnes bývá součástí procesoru

Zdroj: přednáška IOS č. 7, autor: doc. Vojnar

MMU využívá speciálních registrů případně i hlavní paměti systému
pro urychlení používá vyrovnávací pamět TLB (hardwarová asociativní vyrovnávací paměť)

Přidělování paměti

na místě nejbližší HW se pro přidělování paměti používájí:
- spojité bloky
- segmenty
- stránky
- kombinace výše uvedeného
z uživatelského hlediska se přiděluje funkcí malloc a její obdoby v jádře kmalloc, vmalloc, které pracují na principu přidělování bloků na ještě nižší úrovni než klasický malloc.
výrazně se projevuje externí fragmentace paměti (FAP):
- přidělováním a uvolňování paměti vznikají různě velké díry (obsazené a neobsazené úseky v paměti, které nemohou být využité, protože se jedná o nespojité volné místo)
- problém se zvětšováním přiděleného prostoru
- minimalizace pomocí různých strategií alokace paměti
- dynamická reorganizace paměti (!velmi nákladné!)
- při nedostatku paměti se začnou data ukládat na disk, ale to je velmi pomalé a nákladné
druhý typem je interní fragmentace paměti (ta se sice neprojevuje tak zásadně):
- jedná se o chyby v evidenci přidělené/volné paměti (mohou vznikat malé neobsazené úseky)
- ve většině mechanismů přidělování paměti se toleruje

Segmentace paměti

LAP je rozdělen na segmenty ⇒ Ty přiděluje překladač (programátor) jednotlivým úsekům kódu
každý segment má jméno (číslo) a velikost ⇒ logická adresa se proto skládá z čísla (jména) segmentu a posunem v segmentu
segmenty mohou být použity jako jednotka ochrany nebo sdílení paměti
poměrně jednoduchá implementace

Stránkování

LAP je rozdělen na stránky, zatímco FAP na rámce.
vlastnosti:
- pamět přidělovaná po rámcích
- minimalizované problémy pro externí fragmentaci
- jemná jednotka ochrany
- složitější implementace, interní fragmentace

v nejjednošším případě postačuje jednoúrovňová tabulka stránek
pro urychlení se však používá vyronávací pamět TLB, která v sobě uchovává poslední přeložené adresy
- (je třeba mít na paměti, že v TLB nejsou celá čísla rámců, ani stránek (posun se řeší zvlášť))
Tabulky stránek, však mohou být hodně rozsáhlé celky ⇒ rozlišuje se několik druhů:
1. Hierarchická dvouúrovňová tabulka stránek
2. Hashovaná tabulka stránek
3. Invertovaná tabulka stránek

Virtualizace paměti

pro přidělování adresového prostoru procesům se využívá fyzický disk
děje se tak pomocí
- stránkování na žádost
  - stránky (LAP) jsou zaváděny do paměti jen, když jsou zapotřebí (tzn. jen když se na ni někdo začne odkazovat → v tabulce stránek je pro každou stránku nastaven příznak, pokud již má přidělený rámec; pokud není nastaven dojde k výpadku stránky)
  - menší spotřeba paměti, rychlejší ukládání na disk
- segmentování na žádost
Obsluha výpadku stránky
- výpadek stránky je vlastně přerušení od MMU udavající, že se nepodařilo převést zadanou adresu LAP na FAP
- průběh obsluhy výpadku
  1. kontrola zda-li se neodkazujeme mimo přidělený adresový prostor
  2. alokace rámce
    - použije se volný rámec
    - případně se vybere oběť (oběť se odloží na swap a použije se uvolněný rámec)
  3. inicializace stránky
  4. úprava tabulky stránek
  5. proces, který výpadek způsobil je znovu připraven
Algoritmy pro výběr odkladu stránek
1. FIFO
  - odkládá nejstraší stránků, která ale může být pořád používaná
  - jednoduchá implementace
2. LRU
  - odkláda nejdéle nepoužitou stránku
  - velmi dobrá implementace teoretického algoritmu, je ke všemu ale potřeba silná HW podpora
3. aproximace LRU
  - využívá referenční bity, které se nastavují pokud je stánka použitá
  - aproximace LRU pomocí druhé šance
  - referenční bit je nastaven na 1, pokud se však stane málo používaným (u předchozího algoritmu by byl vyřazen) je mu nastavena 0, až v další průchodu (pokud nebyl stále použit) je stránka vyřazena

Sdílená paměť

jedna z forem meziprocesové komunikace (IPC): více procesů má namapováno stejné fyzické stránky v LAP
příkladem je výměna dat mezi procesy (programy) běžící současně
velmi rychlí způsob komunikace, ale málo výkonný