Operációs rendszerek II. jegyzet

Operációs rendszerek II. jegyzet Bringye Zsolt tanár úr fóliái alapján

Operációs rendszer: •

•

A számítógép hardver elemei és az (alkalmazói) programok közötti szoftver réteg, amely biztosítja a hardver komponensek (erőforrások) hatékony használatát Az operációs rendszer elfedi a hardver sajátosságait, egyfajta virtuális gépként jelenik meg a felsőbb rétegek számára

Black-box leírás:

Felhasználói csoportok: •

Végfelhasználók – Napi tevékenységükhöz szükséges alkalmazásokat használnak, operációs rendszerrel minimális a közvetlen kapcsolatuk

•

Fejlesztők (alacsony szintű megoldások) – Operációs rendszer által biztosított virtuális gépen fejlesztenek – Operációs rendszeri eszközöket (is) használnak (utility-k)

•

Rendszer adminisztrátorok – Oprendszer működését felügyelik, hangolják – Folyamatos állapot információkkal kell rendelkezniük – A működésbe is beavatkoz(hat)nak

1

Felhasználói felületek: • • • • •

Grafikus és karakteres felületek egyaránt használatosak A karakteres felület lehet parancssoros és menü alapú Egy rendszernek lehet többféle felülete is A végfelhasználók esetén szinte csak grafikus felület, de a többi csoportban is használják Feladatok összekapcsolása sokszor hasznos lehet, ez jellemzően parancssoros megoldásoknál használatos

Alkalmazási Programozói Felület (API): • •

Az operációs rendszer, mint virtuális gép „utasításkészlete” (a számítógép utasításkészletének kiterjesztése) Tipikusan rendszerhívásokon keresztül érhető el

Hardver Interfész jellemzői: – – – –

Hatékonyság Hardverek sokaságának támogatása Képesség a fejlődésre (új fajta hardverek) Hibakezelés

Interfészek:

2

Operációs rendszerek fejlődése: 1. Operációs rendszer nélkül:

•

A kezdeti idők (40-es évek végétől az 50-es évek közepéig) teljesen manuális megoldása Kézi ütemezés (foglalási tábla) – lehet, hogy programot ki kellett lőni, de az is lehet, hogy a gép „üresen állt” A program indítása jelentős időt vett el a hasznos működéstől

•

Feladat: rendszer kihasználtságának növelése

• •

2. Egyszerű kötegelt feldolgozás: • • • •

50-es évek közepe, GM (IBM platformra) A rendszer vezérlése nem manuálisan, hanem egy program által (rezidens monitor) történik A futtatandó program kártyáit a monitornak szóló leírással (JCL) együtt előre be kellett „tárazni” A megvalósítás feltételei: – Memória védelem (monitor meg tudja védeni magát) – Időzítő (timer), megszakítások (később) – Privilegizált utasítások (monitor megkerülése ellen) – végrehajtási módok (user, kernel) megjelenése

3. Multiprogramozott kötegelt feldolg.: • • • •

60-as évek közepétől A kötegelt feldolgozás nem segített a processzor futás közbeni üresjáratain (I/O-ra várakozás) Egy időben több program található a memóriában, ezek közül választjuk ki azt, amelyik futhat Feltételek – Memória menedzsment (több program a memóriában) – Megszakítások

4. Időosztásos rendszerek:

• • • •

kötegelt rendszerek bizonyos feladatokra (pl. tranzakció feldolgozás) alkalmatlanok, viszont a számítógépek túl drágák, hogy egyetlen ember használja őket Az interaktív felhasználók (programjaik) időszeleteket kapnak Egyik első megvalósítás: CTSS, MIT 60-évek eleje Terminálok elterjedése

3

Hardver ismeretek: a., Processzor: • Utasítások végrehajtása (utasításkészlet) • Az utasítások forrása a központi memória • Regiszterek (általános célú, státusz és vezérlő) • További adatok tárolása: központi memória • Megszakítások (hw. és sw.) b., Memória: • Utasítások és adatok tárolása • Stack terület • RAM és NVRAM (ROM) részek c., I/O: • • • •

Másodlagos tároló Humán interfész Gép-gép kapcsolat Szélsőséges sávszélesség igények

OS szintek: a., nincs OS: • Rendszer indításakor a program feladata az inicializálás – (Legalább részben) NVRAM-ból kell futnia – CPU beállítások (opcionális) – Perifériavezérlő áramkörök inicializálása • Teljes kontroll az összes hardver elem felett (beleértve a processzort is)

• •

•

Processzor, memória, I/O kezelése – Teljes mértékben egyéni megvalósítás Védekezés hibás, rosszindulatú kódoktól – Amit a programozó beépít, nincsenek „társak” (csak önmagától kell megvédenie magát) Környezet változására való érzékenység – Amit a programozó beépít (jellemzően rendkívül nagy lehet)

b., minimál OS: • Rendszer indítás és inicializálás • Minimális parancs interfész (CLI, batch) • Loader funkció, program lehet másodlagos tárolón vagy távoli helyen (tftp) – a betöltés után a vezérlés alapvetően a programnál van • Opcionálisan: sokat használt funkciók megvalósítása (kezdetleges virtuális gép!) – Perifériák kezelése (tip. megszakítás alapon)

4

•

•

•

Processzor, memória, I/O kezelése – Egyéni megvalósítás, esetleg I/O esetén minimális támogatás (kb. instant eljárások) Védekezés hibás, rosszindulatú kódoktól – Amit a programozó beépít, nincsenek „társak” – Az OS védtelen a programtól (⇒MS DOS éra) Környezet változására való érzékenység – Alapvetően nagy, de mértéke az „instant eljárások” segítségével csökkenthető

c., Minimál OS-en túl
védelem: •

Az operációs rendszer védje meg magát – Memória védelme – Kontroll memória műveletek (címek) alapján – Bizonyos utasítások letiltása a programnak (pl. amivel a memória védelmet lehet befolyásolni) – Hardver támogatás nélkül nem lehet hatékonyan megoldani (esetleg emulációval, lassú) • Memória védelmi rendszer • Legalább kétféle CPU üzemmód: privilegizált az OS és „normál” a user kód számára (korlátozott) • Átjárás a két mód között: szoftver megszakítások

d., multiprogramozott rendszerek: •

rendszer egyetlen program általi kisajátítása nem „szerencsés” – Régen: drága a számítógép idő • Kötegelt: egyetlen program ált. nem tudja folyamatosan kihasználni a rendszer erőforrásait (pl. I/O-ra vár) • Időosztásos: a számítógépek túl drágák voltak ahhoz, hogy egy időben egyetlen ember használja őket – Ma: hatékonyság • A PC felhasználók szeretnek egyszerre több dologgal foglalkozni (ugye Önök is) • A szerverek egy időben több kliens kérését is ki kell, hogy szolgálják (ezért szerverek)

•

Elvárás: több program váltott futtatása – Kötegelt rendszerek esetén a rendszer terhelését maximalizáljuk (ha egy program nem tud tovább futni /mert vár/ válasszunk helyette egy másik, futásra készet) – Interaktív rendszerek esetén a válaszidőt kell kordában tartani, a programok között periodikusan kell váltani (a felhasználók egymást nem akadályozhatják) – PC-k: egy felhasználó több programjára igaz

5

Memóriakezelés: • • • •

A processzor csak a központi memóriában található kódhoz/adathoz fér közvetlenül hozzá Programok (adatok) folyamatos mozgatása a másodlagos tárolóról/ra jelentős erőforrás és időigényt jelentene, ezalatt a processzor semmittevésre kényszerül Egy időben több programot kell a memóriában tartani ⇒ egyetlen program sem sajátíthatja ki a memóriát A memóriamenedzsment az operációs rendszer feladata, meglehetősen összetett probléma (foglalási módok, relokáicó)

I/O kezelés: • •

•

A „minden I/O eszköz kisajátítása” koncepció nem működik (és felesleges) Az operációs rendszernek kell felügyelnie az I/O kezelést úgy, hogy a programoknak ne kelljen egymással törődniük – Megosztható és nem megosztható erőforrások – Nem megosztható erőforrás megoszthatóvá tétele Ha az operációs rendszer nem eléggé „szigorú” egész rendszer hatékonysága múlhat egyes programok „jólneveltségén”

Értékelés: •

Processzor, memória, I/O kezelése – Virtualizált környezet

•

Védekezés hibás, rosszindulatú kódoktól – A folyamatok csak a saját címterükben futhatnak (önmagukat igen, másokat nem károsíthatnak) – Az élet nem ennyire egyszerű  • Nem megfelelő (védelmi) rendszerbeállítások • Hibák, hibák, hibák

•

Környezet változására való érzékenység – Alapvetően az operációs rendszer szintjén jelentkezik – Valós és virtuális erőforrások minél teljesebb szétválasztása – Ha az OS nem kezeli a változást, alkalmazás szintről nem (vagy nagyon nehezen) lehet rajta segíteni

6

A kernel:

Klasszikus UNIX:

7

Windows:

A folyamat: DEF: a program végrehajtás alatt álló példánya Jellemzői: • A program futásához – legalább az aktuálisan végrehajtandó – utasításoknak és az általuk kezelt adatoknak a memóriában kell lennie • A program futása során több-kevesebb I/O eszközt szeretne használni (írni, olvasni), ezeket az operációs rendszer szolgáltatja a programoknak • Ahhoz, hogy a program valóban fusson, a fenti feltételeken (memória, I/O) túl a processzorhoz is hozzáférést kell kapjon

A folyamat leírható: 8

– – – – • •

Terület a központi memóriában (kód, adat, stack) Adatok és státuszinformációk a processzor regisztereiben Egyéb státuszinformációk (pl. erőforrásokkal kapcsolatos) Egy végrehajtási szál (most éppen melyik utasítást kell végrehajtani)

Kiindulás: az operációs rendszerek folyamatok szintjén ütemeznek Folyamat váltáskor a teljes folyamat környezetet meg kell őrizni – ez biztosítja a folytathatóságot!

Folyamatmodellek: a., kétállapotú:

b., 3 állapotú modell:

Kritika: Nem tudjuk, a blokkolt folyamat milyen (melyik) erőforrásra vár! 9

Kibővítés, javítás:

10

c., 5 állapotú modell:

d., 7 állapotú modell:

11

Folyamatváltás: •

•

Okai – – –

Időszelet letelte (Aktív ⇒ Futásra kész) Blokkolódás I/O miatt (Aktív ⇒ Blokkolt) Egyéb (pl. prioritások miatt)

Megvalósítás (process switch) – Az éppen futó folyamat összes fontos adatának (környezetének) elmentése – A futásra kiválasztott folyamat környezetének visszaállítása – Vezérlés átadása az újonnan kiválasztott folyamatnak

háttere: • • •

A környezet mentés és visszaállítás minden esetben kernel kódot igényel A váltás során általában a memória táblákat (virtuális memória kezelés) is módosítani kell A folyamat váltás meglehetősen sok utasítás végrehajtását (CPU ciklus) igényli, „drága” tevékenység!

Mód váltás: • • • •

Folyamat váltás során az érintett folyamat állapota megváltozik, másik folyamat lesz aktív (futó) Bizonyos esetekben nem más folyamat, hanem a kernel kell, hogy fusson (pl. IRQ) A folyamat folytatásához szükséges adatok ilyenkor is mentendők, de ez kevesebb, mint a teljes környezet (kevésbé „drága” tevékenység)! Célszerű folyamat váltásról és mód váltásról külön beszélni!

Mód váltás

Folyamat váltás

- kernel módba vált - folyamat minden adatát menteni kell - kernel által használt adatokat menti - címtér változik - címtér nem változik, de kernel - a folyamat státusza változik, más címtér elérhető folyamat fog futni - folyamat tovább futhat, státusza nem változik

12

Folyamatok létrehozása windows alatt.

13

Végrehajtható fájl típus

Végrehajtás módja

Windows .exe

Közvetlenül

Win16 .exe

Ntvdm.exe program

MS-DOS .exe, .com, .pif

Ntvdm.exe program

MS-DOS .bat, .cmd

Cmd.Exe

POSIX kód

Posix.exe

OS/2 1.x kód

Os2.exe

Folyamatok létrehozása UNIX alatt: •

A program indítása két részből áll – Aktuális folyamat duplikálása (szülő-gyerek) – Az indítandó program betöltése a gyerek folyamat helyére

Fork(): • A fork() hatására a teljes folyamat címterét és az erőforrás adatokat is duplikáljuk • A duplikálás után a címterek függetlenek, a változók külön élnek (a kezdőérték ua.) • A fájlokat mindkét folyamatból el lehet érni (ha mindkettőből írunk, akkor a kimenet összekeveredve jelenik meg) Exec(): • A fork() érdekes, de hogyan indítunk új programot? • Az exec() hívás az éppen futó folyamat „helyére” tölt be (és indít el) egy programot • A pid nem változik és az erőforrás leírók is öröklődnek (pl. így működik a pipe a shell-ben)

Folyamat-leírók: •

Memória tábla (fizikai és VM is) – memória – folyamat összerendelés, – védelmi információk, – VM információk

14

•

•

•

I/O tábla – Processz információ – Státusz – Memória info (pl. puffer terület) Fájl tábla – Adattartalma attól függ, hogy a fájlkezelés feladatai milyen módon oszlanak meg az OS és az alkalmazás között Folyamat tábla

Jellemzők: • •

A táblázatok függenek egymástól, hivatkoznak egymásra (pl. fájl és I/O, folyamat és mindegyik). A táblázatokat inicializálni kell, meg kell határozni határértékeket. Ez történhet: – konfiguráció alapján (statikus) – dinamikusan

OPR végrehajtási modellek: •

Nonprocess kernel – Folyamatok fogalma kernel szinten nincs – Kernel teljesen szeparált, saját törvényei szerint fut

•

Folyamat címterében végrehajtott kernel kód – –

•

Mernel nem folyamat alapú, (user) folyamatok címterében fut Minden folyamat címterében elérhető (folyamatok nem látják)

Folyamat alapú kernel – Kernelt is folyamatokként valósítjuk meg • Kliens-szerver modell • többprocesszoros rendszeren is hatékony – Kell egy folyamat váltási funkció, ami a folyamatok „alatt” fut

Mikrokernel: A kernel csak az alapfunkciókat tartalmazza, a kód többi részét felhasználói módban futó szolgáltatások valósítják meg.

Szálak: •

Alapötlet: válasszuk külön az erőforrások birtoklását a program futtatásától! – Folyamat: erőforrás foglalás alapegysége (mint eddig is) – Szál: folyamaton belüli futási végrehajtás egysége

•

Egy folyamaton belül egyszerre több végrehajtási szál is létezhet 15

Multi-Threading

Single Threading

Előnyei: •

Gyorsabb végrehajtás

•

Gyorsabb terminálás

•

Egy folyamaton belül – A szálak közötti váltás gyorsabb, mint a folyamatváltás – A szálak közötti adatcsere, kommunikáció kernel funkciók igénybe vétele nélkül zajlik Nem a folyamatok helyett van!

•

Megvalósítási lehetőségek: a., felhasználói szálak (USER thread):

16

• • • •

•

Kernel nem tud róla, továbbra is folyamatokat lát Szálmenedzsment alkalmazás szintű kóddal (lib) Szálütemezés folyamatonként eltérő lehet Előnyök – szálváltás gyors (user módban fut) – OS-től független, hordozható megoldás Korlátok – I/O blokkolhatja az összes folyamat-szálat (aszinkron I/O) – 1 folyamat összes szála 1 CPU! – Signal-ok kezelése nem triviális (csak folyamatszinten)

b., Kernel szálak:

• • •

A teljes szálmenedzsment kernel módban Felhasználói szinten csak API van A szálak ütemezést a kernel végzi

•

Erősségek – egy szál blokkolódása nem blokkolja a teljes folyamatot – folyamat szálai több CPU-n is futhatnak – Signal kezelés megoldott

•

Korlátok – drága

c., Hibrid szálak: • • •

A felhasználói szálak alkalmazás szinten értelmezettek, de vannak szálak kernel szinten is. A kernel LWP-k (LightWeight Process) szintjén látja a folyamatokat (ezek 1:1-ben kapcsolódnak kernel szálakhoz) Az LWP-k és a felhasználói szálak közötti kapcsolatot felhasználói szintű kód menedzseli 17

•

A felhasználói szálak és LWP-k aránya dinamikus, de kódból is módosítható

További megoldások:

thread

process

Name

1

1

Klasszikus (multiprocessing)

n

1

Multithreading

1

n

Experimental (in distrib. sys)

m

n

Experimental

Ütemezés Folyamatok ütemezése: •

A folyamat ütemezés célja a folyamatok és a processzor(ok) összerendelésének dinamikus szabályozása.

Típusai: – – –

Hosszú távú ütemezés Közép távú ütemezés Rövid távú ütemezés

a., hosszútávú megvalósítása: •

Kötegelt rendszerek esetén a job-ok egy várakozó sorba kerülnek, ebből választ a hosszú távú ütemező. A döntés dimenziói: – Mikor válasszon új folyamatot: multiprogramozás fokának optimalizálása – Melyik folyamatot válassza: FIFO vagy terhelési minta optimalizálás.

•

Interaktív rendszerekben a felhasználó a fő ütemező, OS lehetőségei: ha a rendszer terhelése meghalad egy kritikus szintet (ez általában a folyamatok számában, esetleg a szabad virtuális memória mennyiségében mérhető), akkor nem engedi új folyamat létrehozását.

18

b., középtávú: Feladata komplett folyamatok mozgatása a központi memória és a másodlagos tároló (swap terület) között (swapping).

c., rövidtávú: •

•

•

Ez az ütemező közvetlenül és folyamatosan meghatározza a processzor(ok) és a folyamatok közötti kapcsolatot. – A hosszú- és közép távú ütemezők viszonylag ritkán aktivizálódnak csak durva ütemezési döntéseket hoznak. A rövid távú ütemező aktivizálódásához különböző események vezethetnek (nem mindegyik esemény érvényes minden algoritmus esetén): – Időzítő megszakítása – I/O megszakítások – Operációs rendszer hívások – Signal-ok Lehetséges vizsgálati szempontok: – felhasználó vagy rendszer orientált: • Felhasználó orientált eset – az egyedi felhasználók (folyamatok) igényeit vesszük figyelembe, így például az egyes folyamatok válaszidejét. – Ezek azok a szempontok, melyeket interaktív rendszer esetén egy felhasználó valóban érzékel. • Rendszer szempontjából – a rendszernek a kihasználtsági szint maximalizálására kell törekednie – az egyes felhasználók (folyamatok) kevésbé érdekesek, – ez a felhasználók érdekét sértheti • Egyszerre mindkét szempontot nem lehet teljesen kielégíteni.

–

teljesítmény alapú vagy „egyéb”: •

A közvetlen teljesítmény jellemzők mellett más tényezők is befolyásolják a rendszerről alkotott véleményt, pl: – megjósolhatóság: folyamatosan hasonló válaszidőket produkáló rendszer sokkal inkább elfogadható egy felhasználó számára, mint egy folyamatosan ingadozó rendszer (ugyanarra a tevékenységre vizsgálva)

19

Teljesítmény alapú Felhasználó orientált

- Fordulási idő (B) - Válaszidő (I) - Határidők betartása

Rendszer orientált

- Átbocsátókép. (B) - CPU kihasználtság

Egyéb -

Megjósolhatóság

- Korrektség (kiéhezt.) - Prioritások bizt. - Erőforrások kihaszn.

Algoritmusok jellemzői: Folyamat megszakíthatósága (preemptive): • Meghatározza, hogy az ütemező algoritmus megszakíthatja-e egy folyamat futását, vagy az csak akkor szakad meg, ha a folyamat lemond a CPU-ról vagy erőforrás miatt blokkolódik. • A megszakítható ütemező algoritmusok általában bonyolultabbak, jobban terhelik a rendszert – ugyanakkor sokkal korrektebb ütemezési megoldást biztosítanak

Prioritások alkalmazása • Több olyan algoritmus is van, ahol a folyamatok közötti választást egy, a felhasználó által meghatározott fontossági információ (prioritás) befolyásolja. • A „tiszta” prioritásos megoldás fő problémája az alacsonyabb prioritású folyamatok kiéheztetése.

A döntés alapja több paraméter közül kerülhet kiválasztásra: – A folyamat rendszerben eddig eltöltött összes ideje (várakozás és végrehajtás egyaránt): w – Az eddig futással eltöltött idő: e – A folyamat becsült teljes kiszolgálási ideje (az eddig eltöltött időt is beleértve): s – Fontos látni, hogy a kiszolgálási idő valóban csak becsülhető – amely az esetleges múltbéli tapasztalatok alapján pontosítható. A túlzottan optimista folyamatok futását (amelyek az előre megadottnál sokkal tovább kívánnak futni) a megadott idő letelte után a rendszer megszakíthatja.

20

Vizsgált algoritmusok:

a., FCFS (FIFO): •

•

Működés – A legegyszerűbb algoritmus, amely beérkezésük sorrendjében futtatja a folyamatokat. – Az algoritmus nem megszakítható, ha valamely folyamat blokkolódik, helyette a legrégebben a sorban található folyamat kerül kiválasztásra. Értékelés – Az algoritmus előnybe részesíti a CPU igényes folyamatokat, hiszen azok sokkal ritkábban blokkolódnak, mint az I/O igényes folyamatok. – Az algoritmus következtében az I/O eszközök kihasználtsága meglehetősen rossz.

b., Round Robin: •

•

Az interaktív rendszerek alapalgoritmusa. Az időzítő periodikusan megszakításokat generál, a kernel minden megszakításkor másik folyamatot választ ki futásra a futásra kész folyamatok közül – így alapesetben minden folyamat egy időszeletnyi ideig futhat. Az algoritmus egyik alapvető kérdése az időszelet hosszának meghatározása. – Nagyon rövid időszelet választásával a rövid folyamatok gyorsan végrehajtásra kerülnek, ugyanakkor a sok folyamatváltás komoly többletterhet ró a rendszerre. – Legcélszerűbb olyan időszeletet választani, amely egy tipikus interakció végrehajtását lehetővé teszi – ez a megoldás kifejezetten jó hatással van a válaszidőre.

Értékelés: •

I/O igényes folyamatokkal szemben igazságtalan – az I/O igényes folyamat viszonylag gyorsan blokkolódik, így az időszelete egy részét elveszti – összességében a CPU igényes folyamatok sokkal több időt kapnak, mint az I/O igényes társaik.

•

Módosított algoritmus a fenti probléma megoldására – a várakozósor két sorból áll: az egyik „normál” várakozósoron kívül van egy sor a blokkolásból visszatérő folyamatok számára is. – Amíg a második sor nem üres, a kernel ebből választ folyamatot – azonban ez a folyamat csak a blokkoláskori időszeletéből megmaradt időtartamig futhat (ezután – ha nem blokkolódik ismét – visszakerül a normál várakozósorba)

21

c., Shortest Process Next: • • •

Az ütemező mindig azt a folyamatot választja, amelynek legrövidebb a becsült teljes kiszolgálási ideje Rövid folyamatokat favorizálja a hosszabbakkal szemben Nem megszakítható algoritmus

d., Shortest Remaining Time: •

Az SPN egy megszakítható változatának tekinthető – Mindig az a folyamat lesz futásra kiválasztva, amelynek legkisebb a várható futási időszükséglete (tehát ami még hátra van) – Amennyiben folyamat kerül a várakozósorba (pl. blokkolódásból visszatér), a megtörténik a folyamatok felülvizsgálata, és a legrövidebb folyamat kiválasztása

e., Highest Response Ratio Next: •

•

Célja a fordulási idő és az aktív idő (mikor a folyamat valóban futott) arányának minimalizálása. – (nem megszakítható módon) mindig azt a folyamatot választja ki, amely esetében az R=(w+s)/s hányados értéke a legnagyobb. – w a rendszerben eltöltött összes idő, s pedig a becsült teljes kiszolgálási idő. Előnye: figyelembe veszi a folyamatok korát

f., Feedback: •

• •

Az előző algoritmusok közös problémája az, hogy alkalmazásukhoz legalább becsléssel kell rendelkeznünk az adott folyamat várható futási idejéről – ez pedig sok esetben nem lehetséges. A feedback algoritmus az ütemezési döntést a folyamat eddigi „élete” alapján hozza meg. Az algoritmus megszakítható, időszelet alapú azonban változtatható prioritásokat használ: – minél hosszabb ideje fut a folyamat a rendszerben, annál jobban csökken a prioritása (egy minimum értékig). Értékelés:

•

•

Probléma: az algoritmus a hosszú folyamatokat komolyan bünteti – Megoldás: különböző prioritási szintek esetén eltérő időszeleteket használ: minél alacsonyabb a prioritás, annál hosszabb az időszelet Probléma: sok rövid folyamat könnyen kiéheztet egy hosszabb folyamatot – Megoldás: az algoritmus módosított változatában a várakozó folyamatok prioritása lassan növekszik

22

g., Lottó algoritmus: •

• • •

A klasszikus változó prioritásos ütemezők problémáit próbálja kiküszöbölni: – nem lehet a folyamatoknak CPU birtoklási arányt megadni – egy felhasználó monopolizálhatja a rendszert ha sok folyamatot indít Minden folyamat adott számú (sors)jegyet kap, az ütemezés „véletlen” sorshúzással zajlik. A folyamatok CPU birtoklási aránya a kapott jegyek számán alapul Ha a jegyeket a felhasználóhoz rendeljük, akkor az összes folyamata számára adunk birtoklási arányt – nem lehet monopolizálni a rendszert A megoldás egyik komoly hátránya az, hogy a blokkolás miatt elveszett idő-töredékek valóban elvesznek – erre az algoritmus továbbfejlesztése ad megoldást

Összefoglaló táblázat:

Folyamatok és CPU-k összerendelése: •

•

Az összerendelés lehet – Statikus (a folyamat CPU-hoz kötött) – Dinamikus (mindig az éppen szabad CPU-t használjuk) SMP megoldások esetén a statikus összerendelés jelentős teljesítmény problémákat okozhat (bár sokkal egyszerűbb megvalósítani) – az egyik CPU várakozósorában több folyamat várakozik, míg egy másik CPU kihasználatlanul várakozik.

23

Ütemezés többprocesszoros rendszerekben – szemcsézettség: Szemcsézettség

Leírás

Szinkronizálási időszak (utasítások) Kevesebb, mint 20

Finom

A párhuzamosság utasítás szintű

Közepes

Párhuzamos feldolgozás folyamaton belül

Durva

Konkurrens, folyamatok rendszerben

Nagyon durva

Elosztott feldolgozás hálózaton 2000-1M keresztül összekapcsolt csomópontokon, amelyek közös környezetet alkotnak

Független

Egymástól független folyamatok

egy 20-200

együttműködő 200-2000 multiprogramozott

N.A.

Szálak ütemezése: •

Egyprocesszoros rendszerekben a szálakat a programozás megkönnyítésére használták

•

Többprocesszoros rendszerekben a szálak már a valós párhuzamosság kihasználására is alkalmasak Ebben az esetben azonban fontos lehet, hogy a párhuzamos szálak valóban egy időben fussanak (kommunikáció).

•

Módjai: • Terhelés megosztás: az egyprocesszoros rendszerek esetén megismert megoldást terjesztjük ki MP rendszerekre • Csoportos ütemezés, a szálak és a CPU-k között 1:1 megfelelést alakítunk ki, a folyamat futásához pontosan annyi CPU kell, amennyi szála van • Dedikált CPU-k, a CPU-kat a folyamat élete alatt hozzárendeljük az adott folyamathoz • Dinamikus ütemezés, dinamikusan kezeljük a folyamatokhoz tartozó szálak számának változását Terhelés megosztás: • Jellemzők – Terhelést egyenlően osztjuk szét a CPU-k között – Nincs szükség központi ütemezésre, minden szabad CPU magának választ folyamatot • Ehhez kell egy globális folyamat-sor

24

•

Hátrányok – A folyamat-sor szűk keresztmetszet lehet, bár ez a probléma több tíz, sőt több száz CPU esetén jelentkezik – A szálak nem biztos, hogy az előzőleg kiválasztott CPU-hoz térnek vissza, ami lokális gyorsítótárral rendelkező CPU-k esetében problématikus – Több szálból álló folyamat esetén nem valószínű, hogy az összes szál egyszerre aktivizálódik – ez pedig a szál szinkronizáció során teljesítmény probléma.

Hátrányai ellenére ez a legelterjedtebb ütemezési mód!

Valós idejű ütemezés: • •

• •

Hard real-time feladatok: a határidő nem teljesítése elfogadhatatlan károkat vagy végzetes hibákat okozhat Soft real-time: a határidő inkább elvárt, mint kötelező – megsértése esetén még mindig lehet értelme a feladat végrehajtásának Nem periodikus feladat esetén a feladat végrehajtás kezdési vagy befejezési ideje (vagy mindkettő) kötött Periodikus esetben valamiféle periódusidő adott

Jellemzők: •

Megjósolhatóság: Az OS determinisztikus, ha a feladatokat fix, ismert időintervallumonként hajtja végre. A determinisztikusság meghatározza, hogy az OS mennyi időn belül tud reagálni egy megszakításra.

•

Válaszkészség: – A megjósolhatósággal együttvéve vizsgálandó – Meghatározza, hogy az OS mennyi idő alatt hajtja végre a megszakítás kód közös részét.

•

Felhasználói kontroll… – A rendszer finomhangolhatósága, akár egyedi folyamatok szintjén – Prioritások, VM (nem lapozható részek), diszk-kezelő algoritmusok

•

Megbízhatóság – Egy olyan átmeneti hiba, ami egy sima rendszernél egy reboot után megszűnik, az RT rendszernél katasztrofális lehet (mi lesz a reboot alatt?) – Valamely komponens hibája (pl. CPU), ami sima rendszernél „csak” teljesítmény csökkenést okoz, itt az egész rendszert ellehetetlenítheti (válaszidők)

25

•

Fail-soft működés… – A rendszernek túl kell élnie a hibákat (akár csökkentett funkcionalitással) – Tipikus (pl. Unix) rendszerekben ha a kernel hibát detektál megpróbálja a lehető legkisebb adatvesztéssel kezelni a problémát. Ennek tipikus módja a crash.

Valós idejű ütemezési megoldások: •

Statikus, táblázat alapú megoldások: – Periodikus feladatok esetén használható. Előzetes végrehajthatósági tervet készít, az ütemezés ennek alapján történik

•

Statikus, prioritás alapú algoritmusok: – A szituáció elemzése statikus, de az eredmények alapján az ütemezést „hagyományos” prioritás alapú ütemező végzi

•

Dinamikus, terv alapú megközelítés: – Új taszk indítása esetén az indítást csak akkor engedi, ha az újratervezett ütemezési terv alapján az időzítési elvárások tarthatók

•

Dinamikus, „best effort” működés… – Nem végzünk megvalósíthatósági analízist, a rendszer mindent megtesz, hogy a határidőket tartsa (de nincs rá garancia). Jelenleg elterjedten használt megoldás, nem periodikus megoldások esetén is működik.

UNIX ütemezési példa: –

– – –

A tradicionális Unix ütemezője csak a felhasználói folyamatok esetén szakítja meg a futást időzítés alapján, kernel folyamatok esetén megszakítás nem lehetséges. A Unix ütemezése prioritásos, mindig a legmagasabb prioritású folyamat fut. Amennyiben azonos prioritású folyamatok találhatók a várakozósorban, közöttük az ütemező RR algoritmust használva választ. Egy folyamat prioritása egy kezdeti érték mellett előéletétől függ

UNIX folyamatok prioritása: •

Egy folyamat prioritása egy kezdeti érték mellett előéletétől függ: – minden futási állapotban töltött időszelettel csökken, – minden várakozással töltött időszelettel növekszik

26

–

–

•

Kernel funkcióból való visszatérés után a folyamat prioritása átmenetileg a felhasználói tartomány fölé emelkedik – ezzel is biztosítva, hogy az eredmény gyors elvételével a folyamat a kernel erőforrásait a lehető legrövidebb ideig használja A különböző kernel funkciókhoz más-más érték tartozik, pl. a merevlemez funkcióé magasabb, mint a terminál inputot feldolgozóé

– Unix esetén a folyamatok prioritása az értékükkel fordítottan arányos – pl. a 4.3BSD esetén 50...127 között lehet (0 és 49 közötti rész a kernelnek van fenntartva).

Folyamat-tábla: DEF: A folyamat legfontosabb jellemzői, a folyamat minden állapotában elérhető a központi memóriában

Főbb elemei: – Folyamat állapota – Azonosítók (real/effecive, user/group) – Azonosítók (folyamat ID, rokonok ID-i) – Prioritiás információk – Erőforrás felhasználási mutatók – Várakozó signal-ok

USER AREA: •

Folyamat végrehajtása során szükséges további információk (egyebek között): – Signal kezelési adatok (melyik signal esetén mit tegyünk) – Kapcsolódó terminál azonosítója – Rendszerhívás visszatérési értéke, hibakód – Folyamat által használ fájlok adatai – I/O paraméterek – Limit és jogosultsági adatok (jogosultsági maszk) – Parancssori és környezeti paraméterek

27

Memória-kezelés

Elvárások: – Áthelyezhetőség (relocation) – Védelem (protection) – Megosztás (sharing) – Logikai szervezés (logical organization) – Fizikai szervezés (fizikai szervezés)

Áthelyezhetőség: • Multiprogramozott rendszerekben a szabad memória több folyamat között oszlik meg, kevés kivételtől eltekintve a programozó nem tudhatja, hogy a program pontosan hova fog betöltődni a memóriába • A helyzetet tovább bonyolítja, hogy a program futás közben is swapelhető – ami ismételten a memóriabeli hely megváltozásával járhat • A program futása során többször is találkozik a címzés problémájával: – vezérlés átadások – adatterülethez való hozzáférés • Az áthelyezésre megfelelő választ a processzor hardvernek és az operációs rendszernek együttesen kell biztosítania

Védelem: • Folyamatokat védeni kell a többi folyamat véletlen vagy direkt hozzáférési próbálkozásától (kód és adatterület, írásra és olvasás) • A program kódok sok esetben a következő utasítás címét is dinamikusan állapítják meg, és ez az adathozzáférésekre kiemelten igaz (lásd. Tömbök, mutatók) – védelemnek is dinamikusan, minden egyes hivatkozáskor kell működnie. • Komoly hardveres támogatás szükséges (sw overhead). – Az operációs rendszer feladata a hardver (processzor) megfelelő információkkal való ellátása.

Megosztás: • Szükséges több folyamat számára is ellenőrzött hozzáférés (írás, olvasás, futtatás) biztosítása bizonyos memóriaterületekhez • Okok – ugyanazon program több példányban való futtatása (helypazarlás, indítási idő) – Folyamatok közötti együttműködés biztosítása, osztott memória • megvalósítása hardver támogatást igényel

28

Logikai szervezés: • •

•

A számítógépek memória szervezése tipikusan lineáris, egydimenziós címterű. – Ugyanez igaz a másodlagos memóriára is. A programok felépítése ettől általában eltér, – a programokat általában nem monolitikus tömbként kezeljük, hanem modulokból felépülő rendszernek tekintjük. – A modulok egy része csak olvasható (és végrehajtható), míg más részük írható és olvasható is. Ha a memóriakezelés támogatja ezt a fajta szervezést, annak több előnye is lehet: – A modulok egymástól függetlenül kezelhetők, a modulok közötti hivatkozás futási időben fordul le – A memóriavédelem modul szintű megfogalmazása magától értetődő (csak olvasható, írható-olvasható, stb.) – A memóriamegosztás szintén jól kezelhető modulok szintjén (ez az a szint, amelyen a programozó is gondolkodik).

Fizikai szervezés: • A memória szervezése ma kétszintű: – gyors és viszonylag korlátos mennyiségű elsődleges memória – lassabb, olcsóbb és sokkal nagyobb kapacitású másodlagos memória •

•

Az elsődleges memória mérete meglehetősen korlátos (és multiprogramozott rendszerek esetén folyamatosan változó), csak a központi memória használata meglehetősen lekorlátozza a programok méretét; ezen túllépni csak programozói beavatkozással (overlay technika) lehet – amely többletmunka és igazából csak megkerüli a problémát. A legtöbb megoldás a programok számára kínált memóriát az elsődleges és a másodlagos memória valamiféle kapcsolataként hozza létre. – A processzor közvetlenül továbbra is csak az elsődleges memóriához fér hozzá. – Az adatok mozgatása az elsődleges és a másodlagos memóriák között az operációs rendszerek egyik legfontosabb feladata.

Megoldások: a., fix particionálás: • A memóriát a rendszer „generálása” során fix méretű és számosságú darabra osztjuk • Egy program egy ilyen darabot „kap” • Mekkora legyen a darab? – „Kicsi”: a programok „nem férnek el” (overlay) – „Nagy”: kihasználatlan, más program által nem használható helyek maradnak (belső elaprózódás) Alesetei: • Felosztás azonos méretű partíciókra • Eltérő méretű partíciók alkalmazása • Utóbbi – bár az előző problémákat valamelyest csökkenti – új kérdést hoz: – Partíció kiválasztásának módja

29

b., Dinamikus particinálás: Jellemzői: – Dinamikus particionálás esetén a partíciók mérete és számossága dinamikusan változik – A program betöltésekor pontosan annyi memória allokálódik le a számára, amennyi a futásához szükséges • Ezt a programnak előre tudnia kell

•

•

Működése: Üres memória esetén – A program igénye alapján foglalunk le szabad blokkot a memóriából – Újabb programok, újabb foglalás programok terminálnak, helyek szabadulnak fel – ezekből foglalunk – Előbb-utóbb a memória tele lesz olyan kis üres részekkel, ami már kevés egy programnak – külső elaprózódás

Külső elaprózódás fogalma: • Előfordul, hogy nem tudunk újabb folyamatot indítani, bár a szabad memóriák összeges lehetővé tehetné. • Megoldást a memória tömörítése jelenti, ez azonban meglehetősen erőforrás igényes tevékenység – igényli, hogy a kód futás közben is áthelyezhető legyen

Lefoglalandó terület kiválasztása: • • •

First-fit: első megfelelő hely Best-fit: a lehető legjobban illeszkedő hely Next-fit: utolsó foglalást követő „first-fit”

Tapasztalatok: – legjobb a legegyszerűbb „first-fit” – egy kicsit gyengébb a „next-fit” (ez gyorsan elpazarolja a felsőbb memória részeket) – Legbonyolultabb „best-fit” a legrosszabb, a megmarandó memória darab általában túl kicsi ahhoz, hogy abból újabb kérést ki lehessen szolgálni

A Buddy algoritmus: •

•

Előzményként a fix és dinamikus particionálás korlátai. – a fix particionálás során a folyamatok száma kötött, a memóriahasználat kis hatékonyságú – dinamikus particionálás esetén az algoritmusok lényegesen bonyolultabbak és a tömörítés jelentős többletráfordítást igényel Érdekes kompromisszum a „buddy” algoritmus 30

Működés: • A memóriablokkok mérete 2L és 2U között változhat, ahol – – • •

2L foglalható legkisebb blokkméret 2U pedig a memória teljes mérete

Kezdetben a teljes memória szabad, foglaláskor pedig a rendszer egy fát épít fel – felezve a memóriablokkok méretét Ha két egy szinten lévő blokk felszabadul, azt összevonva magasabb szintre emeljük

-A: 128k -B: 64k -C: 256k -D: 256k -C: out -B: out -A: out

Start

1M

R100k

A

128k

256k

512k

R64k

A

B

6 4

256k

512k

R240k

A

B

6 4

C

512k

R256k

A

B

6 4

C

D

512k

Rel B

A

128k

256k

D

512k

D

512k

Rel A

512k

Az áthelyezés: •

•

Címek (fajták) – logikai cím, fizikai elhelyezkedéstől független címzés (tényleges használat előtt fizikai címre kell fordítani) – relatív cím a logikai cím egy fajtája, ahol a cím egy ismert ponthoz képest relatív kerül megadásra – a programban csak ilyet lehet használni! – fizikai cím a memóriabeli „valós” (abszolút) cím – Regiszterek – „Base” regiszter, a folyamat futó állapotba kerülésekor állítjuk be – „Bounds” regiszterek: memóriavédelem

31

•

A fizikai címet a CPU határozza meg – A megoldás egyben a memóriavédelmet is megvalósíthatja, hiszen a folyamat csak a „bounds” regisztereken belül férhet hozzá a memóriához.

Lapozás: •

Alapötlet: memóriát osszuk fel egyenlő méretű, de egy folyamat méreténél lényegesen kisebb (tipikusan néhány kilobyte méretű) lapokra.

•

Tegyük meg ugyanezt a folyamatokkal is (azonos lapmérettel) – ismét megjelenik a belső elaprózódás, de a lapméret miatt meglehetősen kis mértékben).

•

Ezek után a folyamat lapjaihoz rendeljünk hozzá lapokat a fizikai memóriából

Lapok összerendelése: •

A folyamat címtere és a lapok között egyértelmű összerendelést kell

•

Relokációs mechanizmusba beépíthető – Egy táblázat – laptábla – segítségével minden folyamatbeli laphoz hozzárendelünk egy memória lapot

Page no.

offset

0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1

Logikai cím

0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1

Laptábla

0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1

32

Jellemzők: • • • • • •

Védelem: a folyamatok csak a saját lapjaikat láthatják A hozzáférés-kontroll (olvas, ír) lap szintű A címzés teljes mértékben logikai, a folyamat összefüggő címteret lát. A cím azonban – tudva azt, hogy a lapméret mindig kettő egész számú hatványa – felbontható egy lapcímre és egy lapon belüli relatív címre A lapcím alapján a laptáblából meghatározható a lap fizikai címe – és a cím egyszerűen generálható A címszámításhoz CPU támogatás szükséges, a laptáblák kezelése (kitöltése) az operációs rendszer feladata

Szegmentálás: • •

•

A programok természetes felépítését próbáljuk követni – azaz a folyamat memóriáját nem egyben, hanem modulonként (szegmensenként) foglaljuk A szegmenseken belüli címek szintén logikai címek, itt azonban a címszámítás már összeadással jár – hiszen a szegmensek mérete tetszőleges – CPU támogatás szükséges! A szegmensek megoldják a védelmet is (az egyes szegmensek méretét a CPU ismeri)

Címszámítás és szegmentálás:

Seg.

offset

Logikai cím

0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1

0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0

+

0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0

Szegmens tábla 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1

33

Következmények: •

Egyszerű lapozás és szegmentáció esetén két fontos tényező jelenik meg: – A folyamatok teljes egészében logikai címzést használnak, semmiféle közvetlen kapcsolatuk nincs a fizikai memóriával (és címekkel) – A folyamatokat kisebb darabokra (lapokra vagy szegmensekre) osztottak, ezek egymástól függetlenül helyezkedhetnek el a memóriában (folytonos elhelyezkedés nem szükséges, sőt előnnyel sem jár).

•

A folyamat akkor is tud futni, ha a lapjainak (vagy szegmenseknek) csak egy része található meg a memóriában – az utasítás lefut, ha az éppen végrehajtandó kódot és az (esetlegesen) hivatkozott adatot tartalmazó memória részek elérhetők ⇒ Virtuális memóriakezelés

A virtuális memóriakezelés: Előnyei: – – –

a rendszer több folyamatot tud a központi memóriában tartani, így a CPU kihasználtsága növekedhet a program mérete túlnőhet a fizikai memória méretén, nincs szükség alkalmazás szintű trükközésekre ugyanaz a program különböző memóriamennyiséggel bíró gépen is futtatható újrafordítás, illetve bármilyen alkalmazás szintű törődés nélkül (úgy, hogy a több memória jótékonyan hathat a futásra)

Működése: • A folyamat indulásakor legalább annyi lapot vagy szegmenst be kell tölteni, amivel a futás megkezdődhet • Futás közben a CPU folyamatos címfordítást végez (logikai, fizikai) – Ha úgy találja, hogy valamely címhez nem tartozik terület a memóriában, úgy meghívja a megfelelő operációs rendszeri funkciót, amely gondoskodik a hiányzó lap pótlásáról. • A programok a cache megoldásoknál is megismert tulajdonsága: a kód futása során meglehetősen hosszú ideig limitált területen lévő utasításokat hajt végre (ciklusok, stb.), a feldolgozott adatok köre sem változik túl sűrűn – ez biztosítja a VM létjogosultságát! • Hatékony hardver támogatás nélkülözhetetlen

Lapozás és szegmentálás VM esetén: Lapozás:

•

Laptábla meglehetősen nagy lehet, azt a központi memóriában tároljuk (nem CPUban). A laptábla kezdőpontjára egy CPU regiszter (Page table ptr) mutat.

34

•

•

Nagy laptábla miatt, több rendszer a laptáblát magát is a virtuális memóriában tárolja (lapozható) – pl. a VAX rendszereken a folyamat max. 2GB memóriát használhat, egy lap 512 byte így a laptábla maximum 222 darab bejegyzést tartalmazhat Szintén elterjedt a több szintű laptábla használata, ahol az első szintű tábla mindig a fizikai memóriában van – Pl. 32 bites rendszeren, 4 kbyte méretű lapoknál, 4 GB címtérnél a teljes laptábla 220 bejegyzést tartalmaz, ami 4 Mbyte méretű – ez 210 lapot jelent. Ha az első szintű laptábla a fenti lapok címeit tartalmazza, akkor mérete 4 kbyte (212 – 4 byte x 210). Két szintű laptáblánál a címfordítás is bonyolultabb, a logikai cím három részből áll.

•

A virtuális címtérrel arányosan növekvő laptáblák problémáját többen is próbálták megoldani – pl. UltraSPARC és az IA-64 architektúrák inverz laptábla megoldást alkalmaznak (a tábla méretét a fizikai memória határozza meg).

•

Laptáblák miatt minden memória hivatkozáshoz legalább két hivatkozás szükséges: egy (vagy több) a címfordításhoz és egy a tényleges hozzáféréshez. – A cache memóriához hasonlóan a CPU-ban a címfordítást is gyorsítják egy nagy sebességű laptábla-cache segítségével (TLB).

•

A lapméret fontos hardvertervezési szempont – minél kisebb a lapméret, annál kisebb a belső elaprózódás – ugyanakkor növekszik a lapok száma és így a laptábla mérete – A lapok optimális méretére nincs tökéletes megoldás – Egyes processzorok változó lapméretet is támogatnak (UltraSPARC, Pentium, Itanium), a mai OS-ek széleskörűen nem támogatják a változó lapméretet (pl. Solarisban van ilyen)

Szegmentálás: • A programot különböző méretű modulokra bontjuk (ez lehet programozói vagy fordítóprogram szintű döntés), a modulokat egymástól függetlenül kezeljük a memóriában. • A címfordítás szegmenstáblán keresztül történik (összeadással) • A szegmenstábla a szegmens méretét is tartalmazza, így a hozzáférés ellenőrzése is megoldott. • A szegmensméret dinamikus változtatásával a futási idejű adatfoglalás és felszabadítás is kezelhető.

A két módszer együtt: •

Egyesíti a két megoldás előnyét: a lapozás átlátszó módon biztosítja a memória hatékony használatát, míg a szegmentáció a program logikájának megjelenítését biztosítja a memóriakezelésben.

•

A két módszer összekapcsolása esetén a szegmensek lapokból épülnek fel, így a memóriafoglalás egyszerűsödik (nem beszélve a méret változásáról). 35

•

A logikai cím három részből áll: [Szegmens][Lap cím][Offset]. A szegmenstábla az adott szegmenshez tartozó laptáblára mutat.

•

Szegmentálás használatával a védelem biztosítása nyilvánvalóbb, mint lapozás esetén – kombinált esetben így a szegmentálási megoldás védelmét használhatjuk.

Algoritmusok –tervezési tér

Politikák: • • • • • •

Betöltési (fetch) politika, amely a lap betöltésének idejét határozza meg (első hivatkozáskor vagy előre) Elhelyezési (placement) politika, amely a betöltendő lap fizikai memóriában történő elhelyezését befolyásolja Csere (replacement) politika, amely azt határozza meg, hogy szükség esetén melyik lapot cseréljük Rezidens lapok kezelésének szabályai, melyek meghatározzák, hogy egy adott folyamathoz tartozó lapokat miként kezeljük Laptisztítási politika, amely a lapok felszabadítását, lemezre írását szabályozza Terhelés szabályozás, amely a multiprogramozás fokát adja meg

a., betöltési politika: A betöltési politika kétféle lehet: – Igény szerinti (demand) betöltésről beszülünk, ha a lapot csak akkor töltjük be, amikor arra az első hivatkozás (és ezzel együtt a laphiba) bekövetkezik. – Előzetes (prepaging) betöltés esetén nem csak a hivatkozott lapot, de az azt követő néhány lapot is betöltjük • feltételezzük, hogy a program azt is használja majd • Ez a módszer a laphibák számát próbálja csökkenteni, illetve a lassú diszk miatti várakozás idejét próbálja leszorítani – annak árán, hogy esetleg feleslegesen betöltött lapokkal foglalja le a memóriát.

36

b., Elhelyezési politika: •

A politika azt határozza meg, hogy a memória mely részére töltsük be a lapot. – A legtöbb rendszer esetén a memóriakezelés módja (eltérően pl. a diszkektől) helyfüggetlen, úgyhogy e politika nem releváns. – Fontos kivételt jelentenek a NUMA architektúrák, melyek esetén a memóriához való hozzáférés sebessége függ attól, hogy saját memóriáról vagy távoli memóriáról van szó.

c., csere politika: • Az eldobandó lap kiválasztásának szabályait alapalgoritmusok: – Optimális – Legutoljára használt (Last recenty used) – FIFO – Óra (Clock)

adja

meg.

Legfontosabb

Optimális algoritmusa: Az optimális algoritmus azt a lapot választja ki eldobásra, amelyre a rendszerben a lapok közül legkésőbben fogunk hivatkozni. – Ez az algoritmus jövőbeli információra épít – azaz ilyen nem létezik! – A valós algoritmusoknak a rendszer múltbeli viselkedése alapján kell „megjósolnia” a jövőt. – Ez az algoritmus jó összehasonlítási alap

LRU: Az LRU algoritmus a lapok használati mintájára épít, csere esetén a legrégebben használt lapot dobja el – Arra gondolnak, hogy ezt a lapot fogjuk legkisebb valószínűséggel használni – Az algoritmus megvalósítása nem triviális, a lapokhoz olyan információt kell rendelni, amely alapján meghatározható a lapok utolsó használatának sorrendje.

FIFO: A FIFO algoritmus a lapok betöltési ideje alapján választja ki az eldobandó lapot. – Ezt az információt sokkal könnyebb nyilvántartani, mint az utolsó használat idejét – így ennek az algoritmusnak a megvalósítása sokkal egyszerűbb, mint az LRU-é. 37

CLOCK: • Cél: az LRU algoritmushoz hasonlóan hatékony, de annál sokkal „olcsóbb” algoritmus létrehozása – Az óra algoritmus ilyen-olyan verziójával több operációs rendszerben is találkozhatunk. • Az algoritmus működéséhez minden laphoz hozzá kell rendelni egy használati bitet. – Mikor a lapot betöltjük a memóriába, a lap használati bitjét 1-es értékre állítjuk. – A lapra való hivatkozás esetén a lap használati bitjét szintén 1-re kell állítani. • A lapokat körkörös pufferbe szervezzük, melyhez hozzárendelünk egy mutatót (a körkörös pointer-lista az óra számlapja, a mutató pedig az ami). • Lapcsere igény esetén – A mutató körbejár, hogy nullás használati bittel rendelkező lapot keressen. – A lapokon átlépve (ha a használati bit egyes értékű volt), a használati bitet nullázza. – Ha a mutató körbeér, akkor megáll a kezdőlapnál (ahonnan idul), és azt cseréli le. – Egy lap cseréje után a mutató a kicserélt utáni lapra mutat.

Page Buffing: • FIFO algoritmus, de nem dobja el rögtön a lapot, hanem lista végére írja – Szabad lapok listája (nem változott) – Változott lapok listája • Ha a lapra hivatkoznak, visszaszedhető a listáról

d., rezidens lapok kezelése: •

•

•

Virtuális memóriakezelés esetén nem szükséges a folyamathoz tartozó összes lapnak a memóriában lennie (hiszen erről szól az egész) – egy adott folyamat esetén az egyidejűleg szükséges lapok számának meghatározása politikai döntéseken (is) múlik. A folyamathoz tartozó lapok számának hatásai: – Minél kevesebb lapot rendelünk egy folyamathoz, annál több marad a többi folyamatnak, azaz több folyamatot tudunk egyszerre futtatni. – A folyamatokhoz rendelt lapok számának csökkentésével a laphibák száma egyre több lesz. – A folyamatokhoz rendelt lapok számának növelése egy ideig csökkenti a laphibák számát, azonban egy határon túli növelése már nem vezet észrevehető javuláshoz. – A fenti szempontok egymásnak ellentmondanak, tökéletes (minden helyzetre egyaránt megfelelő) megoldás nincs. A rezidens lapkezelés szempontjai: – Lapkészlet mérete: egy folyamathoz rendelt lapok száma a futás során állandó, vagy változhat – Lapcsere hatásköre: lapcsere során az operációs rendszer csak a laphibát okozó folyamat lapját veheti el, vagy az összes lap közül választhat 38

Fix lapszám, lokális csere: •

•

A folyamathoz rendelt lapok száma állandó, laphiba esetén az operációs rendszer az eldobandó lapot csak a folyamatok saját lapjai közül választhatja ki. – Egy adott folyamathoz rendelt lapkészlet méretét a futás megkezdésekor meg kell határozni, ez történhet automatikusan (az indítandó program fajtája alapján), de kérelmezheti az indítandó program is. Ez a fajta foglalási megoldás kétélű: – ha a rendszer túl sok lapot foglal le a folyamathoz, akkor a lapok egy része kihasználatlan, ami – globálisan szemlélve – a teljes rendszer teljesítményét rontja (kevesebb folyamat futhat). – ha túl kevés lapot rendelünk a folyamathoz, akkor folyamatos laphibákkal kell szembenézni, amely egyrészt rossz a folyamatnak (lassan fut), ugyanakkor a sok laphiba a rendszert is leterheli.

Változó lapszám, lokális csere: •

A lapcsere mindig a folyamat saját lapjaiból történik, azonban a rendszer periodikusan felülvizsgálja, és szükség esetén növeli vagy csökkenti a folyamathoz rendelt lapkészlet méretét. – A folyamatok ebben az esetben – a fix/lokális esethez hasonlóan – meghatározott méretű készlettel indulnak, és ennek a készletnek a mérete a periodikus felülvizsgálat során változhat (a folyamat laphasználási szokásainak függvényében). – Ez a megoldás meglehetősen jó teljesítményt biztosíthat, azonban sok múlik a lapkészlet méretét szabályozó algoritmuson.

Változó lapszám, globális csere: • •

Ennek a politikának az implementálása a legegyszerűbb, több operációs rendszeri megvalósításban is találkozhatunk vele. Az operációs rendszer általában fenntart egy listát néhány szabad lappal, laphiba esetén erről a listáról emel le egy szabad lapot – laphiba esetén a folyamat által birtokolt lapok száma nő – Probléma a lapok elvétele a folyamattól: • amennyiben a szabad lapok száma nullára (vagy egy limit alá) csökken, valamely folyamattól lapot kell elvenni – ebben viszont bármelyik folyamat érintett lehet. • E megoldás esetén jelentős teljesítmény javulást lehet elérni az ún. „page buffering” eljárás segítségével, mely esetében a folyamattól visszavett lapokat nem szabadítjuk fel azonnal.

e., Laptisztítási politika: • A laptisztítási politika a betöltési politika ellentéte – azt határozza meg, hogy lapok felszabadítása – igény esetén (ha laphiba lép fel) történjék (on-demand) 39

•

•

– mindig tartsunk néhány szabad lapot a rendszerben (precleaning). Gyengeségek – Előzetes laptisztás esetén olyan lapot is felszabadítunk, amire rövidesen ismét szükség lesz – azaz ezzel növeljük a laphibák számát. – Igény szerinti laptisztítás esetén viszont a laphibák kezelése lesz hosszadalmas (hiszen ilyenkor esetleg ki is kell írni az eldobandó lap tartalmát a másodlagos tárolóra). A „page buffering” algoritmus ezen a problémán is segít, hiszen ebben az esetben egy, a közelmúltban felszabadított lapra történő hivatkozás esetén a lap könnyen visszanyerhető.

f., Terhelés-szabályozás: •

•

•

Memóriában található folyamatok számának korlátok közé szorítása – túl kevés folyamat esetén a rendszer kihasználtsága lesz alacsony – túl sok folyamat esetén a laphibák száma emelkedik túlzottan magasra Rendszer kihasználtsága a folyamatok számának tükrében – A folyamatok számának növelésével eleinte javul a rendszer kihasználtsága, – egy maximum érték után a görbe csökkenni kezd. A folyamatszám további növelésének következménye a „trashing” jelenség, mikor a CPU idejét folyamatosan a laphibák kezelését szolgáló kód futtatásával tölti. Ha a terhelés meghaladja az optimális értéket, az operációs rendszernek néhány folyamat futását fel kell függesztenie (suspension), a teljes folyamatot (minden lap) a másodlagos tárolóra másolnia.

Felfüggesztendő folyamatok kiválasztása: Megvalósítások fajtái: • • • • •

Legalacsonyabb prioritású folyamatok kiválasztása Laphibát okozó folyamatok, mert valószínű, hogy ezek újabb laphibákat fognak előidézni A legutoljára indított folyamat, mert valószínűleg ez még nem töltötte be a futásához szükséges összes lapot Legkevesebb lapot birtokoló folyamat, mert ennek mentése és visszatöltése a „legolcsóbb” Legtöbb lapot birtokló folyamat, mert ennek felszabadítása eredményezi a legnagyobb javulást a rendszer állapotában

UNIX lapcsere: •

A lapcsere algoritmus a „clock” algoritmus finomított változata, két mutatóval. Az első mutató körbeforogva nullázza a használati biteket, de a lapok kiválasztását a második mutató végzi – így ha közben a lapot használják, úgy annak használati bitje ismét egy lesz.

40

•

Az algoritmust két paraméter jellemzi: – a mutatók forgási sebessége – a fáziseltolás a két mutató között

Swapping: •

Soft swapping: ha a rendszerben a szabad lapok elmúlt 30 másodperces átlaga a desfree érték alatt volt, a kernel inaktív folyamatokat keres és azokat teljesen eltávolítja a memóriából (swap)

•

Hard swapping: több feltételnek is teljesülnie kell, amelyek azt jelzik, hogy a rendszer komoly memóriagondokkal küzd (szabad lapok száma, lapcsere aktivitás foka, stb.). Ebben az esetben a kernel nem használt modulokat és aktív folyamatokat is swapelhet.

A swapping rendkívül erőforrás igényes, megjelenése kerülendő (memória bővítés)!

I/O kezelés I/O eszközök csoportosítása: •

Csoportosítás kapcsolódás fajtája szerint – Felhasználói kapcsolat (bevitel és kivitel is) – Gép általi kapcsolat (pl. HDD, tape) – Kommunikáció (gép-gép közötti)

I/O eszközök jellemzői: 1. Adatátviteli sebesség (Data rate):

Különféle eszközök átviteli sebessége között több nagyságrendi eltérés is lehet! Pl.

- Billentyűzet kevesebb, mint 100 bps - Ethernet: 109 bit/sec

A sávszélesség nem köthető a kapcsolat fajtájához!

2. Felhasználási terület (Application) •

Az eszköz felhasználási területe befolyásolja, hogy az operációs rendszernek milyen módon kell azt kezelnie

41

–

Például a lemezegységek használatához általában fájlkezelő rendszer szükséges, azonban ha a lemezegységet a memória lapok tárolására használjuk (másodlagos memória) a fájlkezelés helyett másfajta lemezkezelésre lesz szükség

További jellemzők: 3. 4. 5. 6.

Vezérlés összetettsége (Complexity of control) Adatátvitel egysége (Unit of transfer) Adatok megjelenése (Data representation) Hibalehetőségek (Error conditions

Összegzésképpen:

A változatosság ellenére azt várjuk, hogy az operációs rendszer az I/O kezelést egységes, eszközfüggetlen interfészen keresztül biztosítsa számunkra.

Az I/O szervezés lehetőségei:

•

I/O kezelési technikák – Programozott I/O – Megszakítás vezérelt I/O – DMA alapú I/O

•

Az I/O funkciók fejlődése – A processzor direkt vezérli az eszközöket – Kontroller (I/O modul) hardver hozzáadása –

Megszakítások kezelése (I/O modul)

– –

DMA megjelenése Az I/O modul egy programozható célprocesszorként jelenik meg. A központi CPU feladata a programkód megadása és a folyamat indítása (I/O csatorna) Az I/O processzor nem a központi memóriát használja, hanem dedikált memóriával rendelkezik

–

42

Operációs rendszer elvárások: •

Hatékonyság: – az I/O eszközök többsége a CPU-hoz képest lassú
az I/O kezelő funkciókat úgy kell elkészíteni, hogy a lassú eszköz miatti várakozás során más folyamat futhasson –

•

ma már léteznek olyan gyors perifériák, amelyek kiszolgálása jelentős teljesítmény-optimalizálást igényel

Általánosság: sokszínűségük ellenére egységes periféria-kezelési megoldás: -folyamatok felé nyújtott interfészen (read, write, open, close, lock, unlock) keresztül – megoldást a hierarchikus struktúrák alkalmazása jelenti

I/O funkciók logikai struktúrája: •

Klasszikus megoldás: hierarchikus megközelítés, az egyes rétegek csak a saját feladatukért „felelnek” – Logikai I/O: általános I/O funkciók szolgáltatása a folyamatok felé –

Eszköz I/O: I/O kérések „lefordítása” eszköz specifikus parancs-szekvenciákra

–

Ütemezés, vezérlés: I/O műveletek sorba állítása, ütemezés (pl. IRQ-k kezelése)

43

I/O Pufferelés:

•

Ha az eszközök közvetlenül „csatoltak” a folyamathoz, akkor: – az érintett memória lapok nem lapozhatók – a művelet befejeztéig a folyamatnak várnia kell (az adott terület nem módosítható) – beviteli műveletek esetén csak az „igény szerinti” (on-demand) működés képzelhető el

Megoldás a pufferelés: egy kernel területén található átmeneti tár közbeiktatásával szétválasztjuk az eszközt és a folyamatot

Módjai: •

Egyszeres puffer: – A műveletek egy kernel puffer- be/ből történnek. – A kernel-user címtér utáni mozgatás után a puffer felszabadul (kezdődhet a következő művelet) – A user címtér lapozható (de a memória menedzsment elbonyolódik)

•

Dupla puffer – Két puffert használunk, az egyiket az OS, a másikat a user folyamat „fogja” – Két művelet történhet egy időben – Gyorsabb, mint az egyszeres
de bonyolultabb is

•

Cirkuláris pufferek – A dupla pufferelés továbbgondolása, a kernel n puffert rendel egy folyamathoz – Bizonyos esetekben tovább gyorsít – A megoldás a „termelők-fogyasztók” modellel írható le

Diszkek teljesítményének elemei: Probléma: diszk és CPU/Mem közötti sebesség különbség folyamatosan növekedett az elmúlt időben. •

Elemek: – Seek time: a fej mozgásának ideje (megfelelő track fölé) –

Forgási késleltetés: amíg a track-on belül a kívánt blokk befordul

–

Átviteli idő: a konkért írás vagy olvasás

44

Összetevők: • •

A seek time és a forgási késleltetés összege adja az elérési időt. A fenti időkön túl még számolni kell: – az eszközre való várakozás ideje – I/O csatornára való várakozás ideje (ha az osztott)

Meghatározások:

•

•

•

Seek time – A fej mozgásához szükséges idő. Ez a mozgás nem teljesen lineáris. A mai kisebb diszkek esetén rövidebb, mint a régi nagyobb (pl. 14 inch) lemezeknél. Mai jellemző érték 4…10 ms. Forgási késleltetés – A lemez forgási sebességétől függ – Mai HDD-k esetén a 3.600 és a 15.000 közötti percenkénti fordulatszám a jellemző (a 3.600 csak a low-end, hordozható eszközökben) – 15k esetén egy teljes fordulat ideje 4ms, így az átlag 2ms! Átviteli idő: – Szintén a fordulatszám függvénye. Egy track-en belül számítható: T = b/(rN) – b: átviendő bájtok, r: forgási sebesség, N: track mérete (byte)

Példa:

•

– átlagos seek idő: 4ms – fordulatszám: 15.000 (full: 4 ms) – szektorméret: 512 byte – szektor/track: 500 (16 us) Feladat: 2500 szektor (1.28 MB beolvasása)

Scenario 1: összefüggő elhelyezkedés – 5 track – 1. track: seek + forgás + 500 rekord olvasása = 10 ms – 2...5. track: 4x(forgás + olvasás) /no seek/ = 24 ms – Összesen: 34 ms Scenario 2: véletlenszerű elhelyezkedés – 2500 x (átlagos seek + átl. Forgás + olvasás) – 2500 x (4m+2m+16u) = 14.6s! – Összesen: 14.6 s

Tanulságok: Fájlrendszereket célszerű úgy szervezni, hogy a fájlok elhelyezkedése ne legyen teljesen véletlenszerű!

45

Diszk ütemezés:

Algoritmusai: •

• •

•

FIFO: kiszolgálás a beérkezés sorrendjében. – Korrekt ütemezés, kevés számú folyamatnál hatékony is lehet – Sok folyamatnál hatékonysága drasztikusan romlik Prioritásos: mindig a legnagyobb prioritású kérést – Kiéheztetés lehetséges LIFO: Mindig a legfrissebb kérést szolgálja ki – Filozófiája lényege, hogy az utolsó kérés az előző közelében lehet – így gyorsan kiszolgálható – Sok folyamatnál ez nem feltétlenül igaz – Kiéheztetés lehetséges SSTF: mindig a legrövidebb kiszolgálási időt igénylő (legkisebb fejmozgás) tartozó kérést szolgálja ki – A megoldás nem garantálja, a fejmozgások globális minimumát – Kiéheztetés lehetséges

Scan változatok: •

Scan: – Cél a hatékonyság növelése a a kiéheztetést elkerülése mellett (ezt eddig csak a FIFO oldotta meg) – A fej fel-le mozog, és minden útjába akadó kérést kiszolgál. • középső részeket favorizálja • tömeges kérésekkel „leragasztható”

•

C-Scan: mindig csak egy irányba megy, – a Scan első problémáját megoldja

•

N-step-Scan: a diszk sort N nagyságú részekre osztja, egyszerre csak egy N-est dolgoz fel

•

FSCAN: két sor van. Amíg az egyikből dolgozik, a kérések a másikba gyűlnek – e két megoldás a leragadást oldja meg

46

Név

Leírás

Megjegyzés

A kiválasztás a művelet igénylőjétől függ FIFO

FIFO elv

A legkorrektebb

Prioritásos

A folyamat prioritása alapján

Független a diszk ütemezőtől

LIFO

LIFO

A lokalitás maximalizálja

A kiválasztás a kért elemek függvénye SSTF

Shortest Service Time First

Magas kihasználtság

SCAN

Felvonóként

Korrekt, de gyengékkel

CSCAN

Egyirányú gyűjtőlift

Megjósolhatóbb szolgáltatás

N-Step-SCAN

Fix számú rekordot dolgoz fel

Garantált szolgáltatás

FSCAN

Változó rekordszám

Érzékeny a terhelésre

RAID(Redundant array of Inexpensive Disks):

Általános diszk problémák: – Teljesítményük növekedési rátája szignifikánsabban alacsonyabb a CPU növekedésnél – a tárolt adatok fontossága miatt a nagy kapacitású diszkek hibája egyre nagyobb üzleti kockázattal járt – A nagy kapacitású diszkek sem „eléggé nagyok”

RAID koncepciója: nagy kapacitású és teljesítményű drága diszkek helyett kisebb (olcsóbb) diszkeket használva érjük el célunkat, azaz: – Kapacitás növelése – Teljesítmény növelése – Megbízhatóság növelése

•

Dióhéjban: úgy kapcsolunk össze több diszket, hogy: – – – –

az operációs rendszer számára egy diszknek látszanak az adatot szétosztjuk a diszkek között, a diszk hibák ellen paritás információ tárolásával védekezzünk (ezt két megoldás nem elégíti ki)

47

•

A szabvány 5+1 szintet definiál : – a „+1” nem redundáns és 3 terjedt el – különböző gyártók további szinteket is definiálnak – szint-kombinációkat is alkalmazunk

A különböző megoldások a szükséges tárolóterület overhead-ben, a megoldás teljesítményigényében és a biztonság szintjében térnek el

Változatok: • • •

•

•

•

RAID-0 (striping) – Redundancia nélküli megoldás RAID-1 (tükrözés) – Adatduplikáláson alapul (nem paritás alapú) RAID-2 – Speciális, Hamming kód alapú – Gyakorlatilag kihalt RAID-3 – Kizáró vagy műveletre épít, egy blokk az összes diszkre szét van osztva – Erős hardver támogatást igényel! RAID-4 – Kizáró vagy műveletre épít, egy blokk csak egy diszken található – Dedikált paritás diszket használ RAID-5 – Hasonló a RAID-4 megoldáshoz, de itt a paritás is szét van osztva a diszkek között

RAID háttér információk:

•

•

•

•

A diszkek átviteli jellemzőjének tényezői – a mechanikai működésből adódó késleltetés – az adatátvitel végrehajtásának teljesítménye (átviteli sebesség) A terhelés jellege – Kevés számú, kis párhuzamosságú, de nagy mennyiségű adatot mozgató terhelése (pl. kötegelt feldolgozás) – Nagy számú, magas párhuzamosságú, de kicsi adatmennyiséget érintő terhelés (tranzakciós rendszerek) Kapcsolat a fentiek között – Nagy mennyiségű adatot mozgató terhelésnél az adatátvitel teljesítménye domináns – Nagy tranzakciószámnál a késleltetések sokkal fontosabbak Olvasás és írás műveletek különbsége redundáns tároláskor – olvasáskor csak annyi adatot kell beolvasni, ami elegendő a kért adatblokk biztosításához – íráskor az adatblokkhoz tartozó összes részt aktualizálni kell 48

•

•

Vizsgáljuk – Tárolás módja – Viselkedés íráskor és olvasáskor – Példák – Diszkek száma: N – Egy diszk átviteli sebessége: T

Változatok bővebb jellemzői: RAID 0: •

•

•

Tárolás módja – Nagyméretű csíkok, egy blokk egyetlen diszken tárolódik. – Redundancia nincs a rendszerben. – Hasznos terület: N. Olvasás – Egy időben ~N független olvasási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: T – Hiba esetén: működésképtelen! Írás – Egy időben ~N független írása tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: T – Hiba esetén: működésképtelen!

RAID1: •

Tárolás módja: – – –

•

Olvasás: – –

•

Nagyméretű csíkok, egy blokk egyetlen diszken tárolódik. A redundanciát a teljes adat duplikálása eredményezi. Tipikusan N=2, hasznos terület: N/2.

Írás: – –

Egy időben ~N független olvasási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: T Hiba esetén: egy időben ~(N-1) független olvasási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: T

Egy időben 1 írási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: =< T Hiba esetén: Egy időben 1 írási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: =< T

49

RAID3: •

Tárolás módja: – Byte szintű csíkok, a blokkok az összes diszkre szét vannak osztva. – Byte szintű paritás képzés XOR művelettel történik, – a megoldás dedikált paritás diszket használ. N>2, hasznos terület: N-1.

•

Olvasás: – Egy időben 1 olvasási tranzakció szolgálható ki • Tranzakciónkénti átviteli sebesség: (N-1)*T – Hiba esetén: egy időben 1 olvasási tranzakció szolgálható ki • Tranzakciónkénti átviteli sebesség: < (N-1)*T (számolni kell)

•

Írás: – –

Egy időben 1 írási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: <= (N-1)*T (számolni is kell) Hiba esetén: egy időben 1 írási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség: <= (N-1)*T (számolni is kell)

RAID4:

RAID5: •

Tárolás módja: – – –

Nagyméretű csíkok, egy blokk egyetlen diszken tárolódik. Blokk szintű paritás képzés XOR művelettel történik, a paritás blokkok is szét vannak osztva a diszkek között. N>2, hasznos terület: N-1.

50

•

Olvasás: – Egy időben (N-1)...(N) független olvasási tranzakció • Tranzakciónkénti átviteli sebesség: T – Hiba esetén: az olvasási tranzakciók száma akár egyre is lecsökkenhet, mert a hibás diszkeken található adatok előállításához az összes többi diszkblokk adata szükséges!

•

Írás: – –

Egy időben 1 írási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség << T Hiba esetén: 1 írási tranzakció szolgálható ki. • Tranzakciónkénti átviteli sebesség << T

51

Diszk Cache

Tervezési kérdések: •

•

Gyorsítás „iránya” – Csak olvasáskor (write through) – Mindkét irányban (write back) – Memória felhasználás módja – Fix (előre meghatározott) – Dinamikus (terheléstől függő)

•

Adat átadás a cache-területről (olvasáskor) – Másolás a felhasználói címtérbe – Osztott memória használata

•

Blokkcsere algoritmusa – LRU (least recently used) – LFU (least frequently used) – Frequency-based

Unix I/O: • •

• •

Hozzáférés fájl-interfészen keresztül Kétféle eszköz – Blokkos – Karakteres Eredeti buffer cache fix Kernel tábla hivatkozások az i-node táblában vannak

52

•

Klasszikus: statikus táblázatok – Új hardver illesztéséhez új kernel kell (a meghajtó programok statikusan betöltve) – – Sok esetben előre „belepakoltak” minden drivert a kernelbe

•

Modern: dinamikus kernelek – A különféle meghajtó programok futási időben is betölthetők (igény szerint) • Függőségek! –

Lényegesen rugalmasabb és erőforrás takarékosabb működés – de a kernel sokkal bonyolultabb lesz

Fájlok, fájlrendszerek

•

Felhasználói szempontból az operációs rendszer (egyik) legfontosabb része: – Ezzel közvetlen „találkozik” – A fájlok tárolása, hozzáférés alapvető – Teljesítmény szempontból kritikus

Elvárások: •

Hosszú távú tárolás – A fájlokat másodlagos tárolón (tipikusan merevlemezen) tároljuk – A fájlok tartalma a felhasználó kilépése, a gép kikapcsolását követően is megmarad

•

Megoszthatóság – Ugyanazt azt az adathalmazt több program is elérhesse – a fájlok egyértelmű azonosítása alapvető – Amennyiben igényelt, a fájlokat több felhasználó is elérhesse

•

Strukturáltság – A fájlok tartalmát (adatokat) jól ismert struktúrába kell szervezni – A fájlok között is célszerű struktúrát definiálni (sok fájl, átláthatóság)

53

Fájlműveletek: •

Általános modell – Létrehozás – Törlés – Megnyitás – Lezárás – Olvasás – Írás

Fájlstruktúrák: •

Struktúra-elemek: – Mező, alapelem – Rekord, összetartozó mezők gyűjteménye – Fájl, összetartozó rekordok – Adatbázis, összetartozó fájlok

Fájl menedzsment elvárások: •

Felhasználók (és alkalmazások) adattárolási, adatkezelési igényeinek kielégítése

•

Tárolt adatok validitásának biztosítása

•

Teljesítmény optimalizálás rendszer (globális) és felhasználói szempontból egyaránt

•

Különféle tároló eszközök támogatása

•

Adatvesztés kockázatának minimalizálása

•

Szabványos (programozói) interfész biztosítása

•

Többfelhasználós működés támogatása

A fájlrendszer architektúrája: Rétegei: • Device driver: kommunikáció a különféle hardver elemekkel (eszközfüggő) •

Basic FS (physical I/O): alacsony (blokk) szintű műveletek

•

Basic I/O supervisor: I/O sorbaállítás, ütemezés

•

Logical I/O: magas szintű file műveletek

54

•

File szervezés: NEM Unix/Win világban – Pile („struktúrálatlan”, ahogy jön) – Szekvenciális (rekord alapú) – Indexelt szekvenciális (rekord alapú) – Indexelt (rekord alapú) – Direct (hash) fájlok (rekord alapú)

Könyvtárak: •

A legtöbb rendszerben a fájlokat valamiféle struktúrába szervezzük – –

A könyvtár tipikusan egy fájl, ami a benne található fájlok adatait tartalmazza A fájlokról tárolt adatok köre eltérő, de tipikusan az alábbiakat kell tárolni: • • • •

• •

Alapinformációk (név, típus, szervezés) Elhelyezkedési információk (kezdőpont, méret, részek) Hozzáférés vezérlési információk (jogosultság) Használati információk (időpontok, esetleg userek)

Alapvető könyvtár műveletek: – – – –

Keresés (fájl keresése) Fájl létrehozása Fájl törlése Könyvtár tartalom listázása

55

–

•

Könyvtárban tárolt fájl-jellemzők aktualizálása

Megoldások: – Egyszerű lista –

Kétszintű (felhasználónkénti)

–

Fastruktúra (szinte egyeduralkodó)

Jogosultságok: Többfelhasználós rendszerben hozzáférés kontroll szükséges!

•

Jogosultsági szintek: – Semmi (nem is tud róla) – Tudhat róla – Végrehajtás – Olvasás – Hozzáfűzés – Módosítás – Jogosultság módosítás – Törlés

•

Hozzáférési szintek (Unix): – Egyedi felhasználók – Csoportok – Mindenki

•

Jogosultsági szintek: – Sokszor egyszerűbb és/vagy más mint a fent felsorolt • a jogosultsági modell függ a fájl/könyvtár kezelési metódusoktól is Megoldás: – Fix jogosultsági struktúra (pl. tulajdonos – csoport – egyebek) – ACL-ek

Párhuzamos elérés: •

Multiprogramozott rendszerekben egy időben egy fájlhoz több folyamat is próbál(hat) hozzáférni: – Ha mind csak olvasni próbálja, nincs gond –

Ha csak egy is írni próbál, lehetnek problémák 56

•

A fájlokhoz való egyidejű hozzáférés korlátozása a zárolás.

•

Zárolási szempontok:

–

Zárolás módja: • Csak olvasás: mindenki csak olvashatja a fájlt (írást nem enged) • Teljes: egy felhasználó (folyamat) módosíthat, a többi nem férhet hozzá

–

Zárolás szintje • Teljes fájl • Fájl egy része

Másodlagos tároló menedzsment tervezési tere

•

Fájl foglalása: – Előzetes foglalás: a létrehozáskor lefoglaljuk • Fix, létrehozáskor megadandó fájlméret • Mivel a fájlok mérete legtöbbször nehezen becsülhető, tipikus a „túlfoglalás” –

•

Dinamikus foglalás • A fájl mérete futási időben változhat

Foglalási egység lehet: – Összefüggő? • nagyon jó teljesítmény • módosítás és felszabadítás problémás

–

blokk alapú: fix méretű (kicsi) blokkokból foglalunk. • Bonyolultabb nyilvántartás, rosszabb teljesítmény • könnyen módosítható és újrahasználható •

•

Foglalási algoritmusok: • First fit (első megfelelő blokk keresése) • Best fit (a legjobban illeszkedő blokk keresése) • Nearest fit (legközelebbi blokk keresése)

Fájl foglalási módszerek (blokkos): – Folyamatos foglalás: • Összefüggő területet foglal, előzetes foglalással •

Nagyon jó szekvenciális I/O teljesítmény

57

• •

•

Kellő méretű helyet lefoglalni sokszor nehéz Külső elaprózódás és tömörítés problémája jelentkezik

–

Láncolt foglalás : • minden blokk külön foglalandó, a blokkokból láncot képzünk • a fájlban való mozgás a láncon keresztül történik • a fájlok széttöredezhetnek, ez jelentős teljesítmény probléma lehet

–

Indexelt foglalás : • minden blokk külön foglalandó, a blokkokból index-táblát építünk • Az index-tábla kezelése kérdéseket vet fel

Szabad hely nyilvántartásának megoldásai: – Bit tábla használata: • Bitvektor, a diszk minden blokkjához egy bitet rendelünk, a bit értéke mutatja az adott blokk foglaltságát • Könnyű benne összefüggő blokkokat keresni • A tábla meglehetősen nagy lehet, ez problémákat vet fel • Diszk: 16 Gbyte, Blokkméret: 512 byte – tábla: 4 Mbyte • Memóriában legyen vagy diszken? • Mennyi CPU ciklus végignézni a teljes táblát?

–

Láncolás: • Láncolt lista a szabad blokkokról

–

Indexelés: • Indextábla a szabad blokkokról

–

Szabad blokkok listája : • külön területen, a diszken tárolva • Az lista elejét a memóriába töltjük és ezt használjuk (ha elfogy, újra beolvasunk egy részt a diszkről)

Esettanulmány: Unix fájl rendszer klasszikus •

Fájlok a felhasználók szempontjából: – egyedi névvel (nevekkel) rendelkező (régen 14, ma 255 hosszú) – bájtfolyamok

•

Belső ábrázolás ettől lényegesen eltér: – Adattárolás tip. blokkorientált eszközön, tárolási mód is ehhez igazodik –

A fájlokat adatblokkokban tároljuk, a fájlokról tárolt információk kezelésének alapja pedig az inode (index-node) - amely az i-node táblázat egy bejegyzése.

58

•

–

Az inode tartalmazza : • A fájlokhoz rendelt lemezterületek azonosítóit (blokk sorszámait), • A fájl tulajdonosát, elérési jogokat, • A létrehozási, címzési dátumot • nevet nem tartalmaz

–

Minden fájlhoz egyetlen inode tartozik, azonban egy inode-hoz tartozhat több fájlnév is - ekkor ugyanarra a fizikai fájlra több helyről (több néven) hivatkozunk. Minden inode-hoz rendelt fájlnevet linknek nevezünk.

Az inode-fájlnév összerendeléseket a - szintén fájlként létező - könyvtár-fájlok tartalmazzák –

Könyvtár fájl tartalma: a könyvtárban található fájlok és a hozzájuk tartozó inode értékek listája

–

Alkönyvtárak: ezek is fájlok (tehát ugyanúgy név és i-node pár, de a típusok ‘könyvtár’)

–

Minden könyvtárfájl tartalmaz egy '.' és egy '..' nevű fájlt (‘könyvtár’ típus). • a '.' fájl az aktuális könyvtárra mutató link • a '..' a szülő könyvtárra mutat • Ez a két fájl (link) teszi lehetővé a relatív mozgást a könyvtárstruktúrában

Fájlok tárolása: •

Fájlok tárolása nem (feltétlenül) egymást követő blokkokban történik, a fájlhoz tartozó összes blokk címét tárolni kell (nem elég csak az első blokk címe).

•

A fájlokhoz tartozó lemezterületek azonosítása a UNIX rendszerben az i-node bejegyzésen belül történik. – –

a - FAT stílusú - láncolt listánál biztonságosabb megoldás mivel az i-node mérete (és ezzel együtt a bejegyzésen belül tárolt lemezhivatkozások száma) kötött, szembe kell néznünk a változó fájlméret okozta problémákkal. • Ha egy i-node bejegyzésen belül „sok” lemezhivatkozási címet helyezünk el, sok (kis méretű) fájl esetén a bejegyzések nagy része kihasználatlan marad • Szinte biztos, hogy felmerül az igény a kezelhető méretnél nagyobb méretű fájl kezelésére is.

59

–

A UNIX a következő módszert használja: minden i-node bejegyzés kötött számú rekord-hivatkozást tartalmaz, azonban ezen bejegyzések egy része nem adatterületre, hanem lemezterület-leíró rekordra mutat - amely ismét tartalmazhat hivatkozást további terület(ek)re.

Fájl blokkok címeinek meghatározása:

Fájlrendszerek mérete: •

•

1024 bájtos blokkméret, az i-node 13 bejegyzést tartalmaz – ebből 10 adatterületre mutat – 3 pedig un. indirekt rekordokra – az i-noden belül max. 10 kbájt méretű fájl adatai tárolhatóak 32 bites blokkcím, egy indirekt rekord 256 rekordcímet tartalmaz – Az első indirekt rekord 256 adatterület címét tartalmazza, – a második 256 lemezterület-leíró rekord címet (dupla indirekció), – a harmadik pedig már tripla indirekció.

•

Méretek: – ezzel a módszerrel 16 Gbájtnál nagyobb fájlok is kezelhetőek – A 32 bites rekordcímek miatt a legnagyobb fájlméret 4 gigabájt

•

Értékelés: – 1984-es vizsgálat szerint az i-noden belül tárolható 10 kbájtos fájllimit sok esetben elegendő (19.978 mintafájl 85%-a 8 Kbájtnál kisebb volt). – A mai rendszerekben a 4 giga kevés, de a blokkméret sem 1k…

60

Fájl hivatkozások (System V): •

A felhasználó a fájlokra a nevével hivatkozik

•

A rendszer (a könyvtárfájlokon keresztül) megkeresi a fájlnévhez tartozó inode-t: – ebből megállapítja a hozzáférés jogosságát – és a fájl elhelyezkedését a háttértárolón

•

Új fájl létrehozásakor a rendszer a fájlhoz egy nem használt inode-t rendel: – –

Az inode-kat a rendszer a fájlrendszer részeként tárolja a megnyitott fájlok inode-it a memóriában tárolja.

•

A kernel az inode-táblán (nyitott fájlok inode-i) túl két további táblát is tartalmaz: – a fájl táblát – felhasználói fájlleíró táblát, ezt minden folyamathoz külön létrehozza a rendszer

•

Ha egy folyamat megnyit vagy létrehoz egy fájlt a kernel mindhárom táblában létrehoz bejegyzést (kivétel, ha a fájlt már más is megnyitotta): – –

A fájl tábla - többek között - a fájlmutató helyét tartalmazza a fájlban A felhasználói fájlleíró tábla a folyamat rendelt megnyitott fájlok listáját tartalmazza. • Fájlmegnyitás (létrehozás) esetén a kernel egy ún. fájlleírót ad vissza ez a leíró a felhasználói fájlleíró táblának egy helyét azonosítja.

Esettanulmány: System V file system

•

A háttértárak kezeléséhez a UNIX minden (fizikai) egységen létrehoz egy vagy több fájlrendszert. – A UNIX számára minden fájlrendszer egy különálló logikai egységet jelent. –

A fájlrendszer logikai blokkok (rekordok) egymásutánjából áll.

–

A blokkok mérete rendszerfüggő, általában 512 byte szorozva kettő (kis) hatványával, a blokkméret egy fájlrendszeren belül állandó.

–

A logikai blokk jelentőssége a következő: minden kernel-háttértároló közötti adatcsere esetén a blokkméret egész számsorosa áramlik - a legkisebb adatátviteli egység a (logikai) blokk • Ez akkor is igaz, ha csak néhány bájtot olvasok vagy írok!

–

A logikai blokk méretétől az adatátvitel gyorsasága, és a háttértároló kihasználtsága függ - ezek azonban egymásnak ellentmondó szempontok (míg a a System V esetén egy blokk egy és csakis egy fájlhoz tartozhat, a 4.2 BSD már megengedi a blokk felosztását)

61

A fájlrendszer felépítése a következő: – a boot block a fájlrendszer legelső blokkja, és a rendszer indításakor végrehajtandó, rendszertöltést indító kódot tartalmazza –

a super block írja le a fájlrendszert • hány blokkból áll, hány fájlt tud tárolni • hol vannak szabad i-nodek (ez a lista nem teljes) • hol találhatóak szabad blokkok (teljes lista, de részben az adatterületen van)

–

inode lista - az inode-kat tartalmazó blokk(ok), • a terület méretét a rendszergazda határozza meg generáláskor (statikus) • Ez határozza meg a létrehozható fájlok számának maximumát

–

adat block-ok • Alapvetően a fájlok adattartalma (blokkok) található itt, de vannak kivételek – Könyvtárfájlok – Szabad blokkok listája • minden egyes blokk egy és csakis egy fájlhoz tartozhat

Folyamatok együttműködése

•

•

A folyamatoknak kommunikáljanak

sokszor

szükségük

van

arra,

hogy

más

folyamatokkal

–

Folyamatok működésükhöz más folyamattól várnak adatot • Adatok átadása (egyik folyamat a másiknak) • Adatok megosztása folyamatok között

–

Közös erőforrásokért versengő folyamatok szinkronizációja

–

Különböző folyamatok által végzett műveletek megfelelő sorrendben történő végrehajtásának biztosítása

Sok operációs rendszer lehetővé teszi, hogy az együtt dolgozó folyamatok megosszanak bizonyos erőforrásokat egymás között – versenyhelyzet alakulhat ki

62

Versenyhelyzetek: •

•

Klasszikus probléma, egy print spooler rendszer: – Ha egy folyamat ki szeretne nyomtatni egy fájlt, akkor a fájl nevét elhelyezi a print spooler következő üres sorában. • Spooler betelésével most nem foglalkozunk (kellően nagy) –

A spooler bejegyzéseit természetes számokkal azonosítjuk (sorszám)

–

A rendszer továbbá két osztott változót használ • out változó a következő nyomtatandó fájl helyét adja meg • in változó a következő szabad bejegyzés helyét mutatja.

Az alábbi szituációban kíván az A és B folyamat többé-kevésbé egyszerre új bejegyzést átadni a rendszernek.

Worst case scenario: •

•

•

‘A’ folyamat – Kiolvassa az in változó értékét (6), majd eltárolja egy belső változójában. – Mielőtt megnövelhetné az in változó értékét, az ütemező átadja a vezérlést a B folyamatnak ‘B’ folyamat – Szintén 6-ot olvas ki az in változóból – Az általa nyomtatni kívánt fájl nevét eltárolja a spooler 6-os sorában – Utána megnöveli in értékét is – Vezérlés visszakerül az A folyamathoz ‘A’ folyamat – A sor számát nem az in változóból veszi, hanem a belső változójából, – A folyamat is a 6-es sorba fogja elhelyezni a fájlnevet

Megállapítások: •

A fenti problémához hasonló problémákat, ahol több folyamat szeretne közös adatokat használni, és a futás eredménye a folyamatok végrehajtásának egymáshoz képesti ütemezésétől is függ versenyhelyzetnek nevezzük.

63

•

Az átmeneti változó az előző példában a processzor akkumulátor regisztere is lehet, tehát még egy gépi kódú program sem lenne elegendő a probléma feloldásához

Versenyhelyzetek kialakulásának megakadályozása: •

•

Megoldás az, ha biztosítani tudjuk, hogy az osztott erőforrásokat egy időben csak egy folyamat olvashassa ill. módosíthassa — tehát kizárólagos hozzáférésre van szükségünk: – A kizárólagos hozzáférés biztosítása azonban nem csak egyetlen gépi utasítás erejéig szükséges, hanem egy kódrészlet végrehajtása alatt. –

A programok azon részét, amelynek megszakított végrehajtása problémákat okozhat kritikus régiónak (critical section) hívjuk.

–

Ha el tudjuk érni, hogy egyszerre csak egy folyamat hajtsa végre a kritikus régiójához tartozó kódrész utasításait, elkerülhetjük a versenyhelyzeteket.

A teljes megoldáshoz négy feltétel egyidejű teljesülése szükséges: – Egy időben csak egy folyamat futtathat a kritikus régiójához tartozó kódot. –

A processzorok sebessége vagy száma nem befolyásolhatja a működés végeredményét.

–

A kritikus szekcióján kívül futó program nem blokkolhatja más folyamatok végrehajtását

–

Egyetlen folyamatnak sem kell örökre várakoznia, hogy végrehajthassa a kritikus szekcióhoz tartozó utasításait.

A kizárólagos hozzáférés alapjai: •

Megszakítások tiltása: – A legegyszerűbb megoldást jelenti, ha a kritikus szekciójába belépő folyamat által végrehajtott első utasítás a megszakítások tiltása. • Ha a megszakításokat letiltjuk, a rendszeróra megszakítása sem jut érvényre, így az ütemező sem jut érvényre. •

Ez a megoldás a gyakorlatban használhatatlan, ugyanis egyetlen hibás felhasználói folyamat a teljes rendszert lebénítaná. Az operációs rendszer kódján belül azonban sokszor használják ezt a fajta megoldást (bár mára jelentőssége erősen lecsökkent).

64

•

Üzenettovábbítás: – Az üzenettovábbítás a folyamatok közötti kommunikáció egy igen elterjedt módja. Két primitív műveletet használ, a SEND művelet segítségével egy üzenetet továbbíthatunk, míg a RECEIVE művelet üzenet vételét célozza.

•

Szemaforok: – A szemaforok elméletét E. W. Dijkstra dolgozta ki 1965-ben –

A megoldás lényege egy számláló változó, amelyet két művelet segítségével változtathatunk: • A Down művelet eggyel csökkenti a számláló értékét. Ha a számláló értéke nulla volt, akkor a művelet mindaddig nem tér vissza, amíg a számláló értékét egy másik művelet nem növeli meg egyel. Ebben az esetben már a csökkentés végrehajtható •

Az Up művelet a számláló értékét egyel növeli, és ha az érték előzőleg nulla volt, akkor egy várakozó Down műveletet „felébreszt”

A megoldás leglényegesebb eleme az, hogy az Up és a Down műveletek atomiak, tehát végrehajtásuk nem szakítható meg. • A mai processzorok többsége már rendelkezik olyan gépi kódú utasítással ami lehetővé teszi a fenti műveletek atomi szintű megvalósítását A szemaforokat a kizárólagos hozzáférés megvalósításán túl szinkronizációs célokra is felhasználhatjuk (pl. jelezzük, hogy egy puffer megtelt)

A folyamatok viszonya •

Folyamatok közötti viszony szintjei: –

Folyamatoknak nincs tudomásuk egymásról: • Egymástól teljesen független folyamatok (pl. multiprogramozott környezetben) •

–

Az erőforrásokért folyó küzdelem miatt felléphet verseny szituáció, ezt OS szinten kezelni kell!

Folyamatoknak indirekt módon tudomásuk van egymásról: •

A folyamatok közös objektumokon (pl. I/O puffer) osztoznak

A közös objektumhoz való hozzáférés együttműködést igényel

65

–

Folyamatok tudatosan együttműködnek: •

A folyamatok feladatuk kapcsán működnek együtt (tudatos tervezési döntés következményeképpen)

További fontos fogalmak: •

Holtpont (deadlock) – Folyamatok permanens blokkolódása – Elkerülésére nincsen általánosan jó megoldás

•

Kiéheztetés (starvation) – Valamely folyamat nem jut hozzá az általa igényelt erőforráshoz – Megfelelő (igazságos) erőforrás ütemezési algoritmusokkal kivédhető

A 90-es évek UNIX fájlrendszerei Többféle fájlrendszer megjelenése, elvárások, jellemzők: • Szolgáltatások (pl. hosszú fájlnevek) • Méret (fájlrendszer, fájlok) • Teljesítmény • Megbízhatóság • Speciális funkciók (pl. tmp terület)

Network File System: Az 1980-as években a kommunikációs hálózatok elterjedésével a fájlmegosztás igénye is előtérbe került, egyebek mellett a transzparens hozzáférést kínáló Sun által fejlesztett NFS: – –

NFS használata esetén a felhasználó ugyanolyan módon láthatja a helyi fájlokat, mint a távoli gépen lévőket Az NFS megoldáshoz a Sun teljesen átalakította a fájl keretrendszert, később a megoldás (vnode/vfs) de facto szabvány lett (az SVR4 részévé is vált)

A vnode/vfs architektúra: •

Tervezési szempontok: – Többféle fájlrendszer egyidejű (Unix és nem Unix – pl. MS-DOS) támogatása

66

–

– –

Különféle fájlrendszereket tartalmazó diszk partíciók csatolása (mount) után létrejövő kép konzisztens, a felhasználónak nem kell törődnie a különféle fájlrendszerek sajátosságaival Fájlok (távoli) megosztásának támogatása Saját fájlrendszerek típusok létrehozásának lehetősége

Koncepciója: •

Objektum szemléletű megközelítés: – Vnode: a fájlok absztrakciója, a – Vfs: pedig fájlrendszeré a Unix kernelben

• •

Absztrakt alaposztályok, minden tényleges fájlrendszer-implementáció ősei Az osztályok adatelemei és metódusai virtualizáltak, a funkciók két szintre oszthatók – alacsony szintű funkciók (pl. open, read) – ezeket egyes fájlrendszerimplementációk implementálnak – magas szintű „utility” funkciók – alacsony szintű funkcióra épülő funkciók, ezeket tipikusan a kernel egyéb részei használják

Fájlrendszer implementációs elvárások: • • • • • • •

Minden művelet végrehajtása a hívó folyamat nevében történik, a végrehajtás alatt a hívó blokkolódik/hat Bizonyos műveletek kizárólagos fájl hozzáférést igényelnek – ezek struktúrák zárolását igényelhetik Az interfésznek állapotmentensnek kell lennie, globális változókra nem támaszkodhat Reentráns interfész szükséges, ez tiltja a globális változók használatát Globális erőforrások (pl. buffer cache) használata megengedett Támogatnia kell a távoli fájlelérést szerver oldalát Fix méretű, statikus táblák használata nem lehetséges

S5FS: • •

•

A fájlrendszer egyetlen diszk partíciót foglal el, használatához más információ kell A partíció logikailag blokkok lineáris tömbjének tekinthető – A blokkok mérete 512 szorzata 2 egész számú hatványával – A diszk műveletek előtt a blokkok címét át kell fordítani a lemez fizikai címadataira A partíció négy részből áll – Boot terület – Szuper blokk – i-node lista – adatterület 67

Fájlok tárolása: •

•

Kb. fa struktúrájú szervezés, a struktúrát a könyvtár fájlok írják le. Felépítés: – Fájl neve 14 karakteren – i-node szám, 2 bájton (0 érték foglalt, törölt fájlt jelöl) – A ‘.’ és ‘..’ minden könyvtárban kötelező, root könyvtár i-node értéke: 2 Index node fájl adatait tárolja (kivétel név) – Fájl elhelyezkedésének magadása: indexelt, 13 bejegyzés, ebből 3 indirekt – Lyukak támogatása fájlokban (ilyenkor a blokkcím 0) • Másoláskor gond lehet…

A SZUPERBLOKK: •

•

•

•

A fájlrendszer metaadatait tartalmazza – Minden fájlrendszer tartalmaz egy ilyen blokkot – Csatoláskor a kernel memóriába tölti, leválasztásig ott is marad Szuperblokkban tárolt adatok – Fájlrendszer mérete (blokkok) – I-node lista mérete (blokkok) – Szabad blokkok és i-node bejegyzések száma – Szabad blokkok listája – Szabad I-node bejegyzések listája

Szabad i-node blokkok nyilvántartása – Csak részleges lista van a szuperblokkban – Ha elfogy, a rendszer szabad blokkokat keres a diszken Szabad diszk blokkok nyilvántartása – Az összes szabad blokkot nyilván kell tartani – Teljes lista szuperblokk-ban tartása nem lehetséges – A szuperblokkban csak a lista „eleje” van, a többi tárolása adatblokkokban történik • Minél jobban telített a diszk, annál kisebb ez a lista!

CACHE: • • •

•

Korai megoldásokban különálló buffer cache SVR4 esetén a fájlkezelés a virtuális memóriakezeléssel integrált Olvasási művelet (példa) – Blokk diszk-beli címének meghatározása – Lap foglalás kernelben, megadva az előbb kiszámolt cím – Lap másolása felhasználói térbe – laphiba, adatterület beolvasása Az írás is virtuális memórián át történik, de: – A fájl mérete változhat – Ha nem teljes blokkot ír, akkor visszaíráskor szükség van a diszken található adatokra is

68

Értékelése: •

• • • • • •

Egyszerűsége kiemelkedő, de problémák több területen is jelentkeznek: – Megbízhatóság – Teljesítmény – Szolgáltatások A szuperblokk sérülése a teljes fájlrendszert tönkreteszi Teljesítmény szempontjából kritikus a teljes i-node tábla partíció elején való elhelyezése Az i-node foglalás véletlenszerű, nem ügyel kapcsolatokra (pl. egy könyvtár fájljai) A fájlrendszer létrehozásakor a szabad blokkok listája optimális (a diszk műveletekre nézve), később azonban ezzel nem foglalkozik A diszk blokkok mérete szintén nem optimális (nagyobb méret, kevesebb művelet – jobb teljesítmény, de sok pazarlás) A 14 karakteres fájlnév komoly funkcionális korlát

FFS: • •

• •

•

• • •

Az FFS célja az s5fs korlátainak túllépése volt Teljesítmény-növelés – Bár a fájlrendszer továbbra is blokkok tömbjének tekinthető, a műveleteknél figyelembe veszi a diszkek forgási késleltetését – A fejmozgások csökkentése érdekében a partíciót tovább osztjuk, ún. cilinder csoportokat hozunk létre • Cél az összetartozó adatok egy cilinder-csoportban tartása • A szuperblokk adatainak egy része is a cilinder-csoportokba vándorol Biztonság növelés érdekében a szuperblokk több példányban „elszórtan” tárolódott A helykihasználás javítása (és a teljesítmény növelése) miatt a (s5fs-nél nagyobb méretű) blokkokat oszthatóvá tették

Fájlfoglalás optimalizálása cilinder-csoportokon keresztül – Egy könyvtár fájljai egy csoportba kerülnek (lokalitás, gyors könyvtárműveletek) – Új alkönyvtárat eltérő csoportba helyezi – A fájl blokkokat egy csoportba helyezi az i-node blokkal – A nagy fájlokat „szétkeni” a blokkok között – Szekvenciális blokkok elhelyezése a diszk forgás függvényében (késleltetések) Az optimális működéshez legalább 10% szabad diszk terület szükséges! Hosszú fájlnevek (255 karakter) – Tárolás változó hosszon a könyvtár fájlokban (a fix 255 hossz túlzás lenne) Szimbolikus linkek

Blokk fogalma: 1 transzfer alatt átvihető adatmennyiség • •

Az FFS egy fájlrendszeren belül csak egyféle blokkméretet támogat (ez általános) A blokkméret 2 hatványa, legalább 4096 byte 69

Értékelése: • • • •

S5fs-hez képes jelentős teljesítmény növekedés – 1983: olvasás ~8x, írás ~3x Fájlrendszer kihasználási hatékonyság hasonló – Több tényező, kiegyenlítik egymást Mai diszkek esetén a sávonkénti blokkok száma eltérő, így az FFS elhelyezési politikája többé-kevésbé elévült Összességében az FFS jelentős előrelépés a s5fs-hez képest, azonban innen van még hova fejlődni

Általánosságban a tradicionális fájlrendszerek korlátai: •

Teljesítmény: – Még az FFS sávszélessége is jelentősen elmarad a diszk potenciális sávszélességétől

•

Összeomlás esetén: – A cache miatt adat és metaadat is elveszhet, helyreállás során hosszadalmas konzisztencia ellenőrzés (fsck) szükséges –

Minél nagyobb a diszk, annál tovább tart

•

Biztonság: – A klasszikus Unix hozzáférés kontroll sokszor nem elég finom, ACL-re lenne szükség

•

Méretek: – A 32 bit korlátjai…

Speciális fájlrendszerek jellemzői: •

Átmeneti adattárolás (tmp terület): – –

•

Sok alkalmazás intenzíven használ átmeneti fájlokat – a teljesítmény fontos, a hosszú távú megőrzés szükségtelen Sokáig az ún. RAM diszkek használata volt a tipikus, ez viszont a központi memóriát statikusan foglalja

Naplózás: Alapkoncepció (jelentősen leegyszerűsítve) – Minden változást feljegyzünk egy szekvenciális fájlba (is) – Hiba esetén csak a fájlt kell ellenőrizni (végrehajtatlan tranzakciókat keresve)

70