Operációs Rendszerek II. 4. előadás

Operációs Rendszerek II. 4. előadás

Sunday, March 7, 2010

Valós idejű ütemezés (általános célú OS-ek esetén) • Egyre inkább a figyelem középpontjába kerülő problémakör • Ebben az esetben a végrehajtás sikere nem csak a végeredményen, hanem annak időbeliségén is múlik • Megkülönböztetünk: – Hard és Soft RT feladatokat – Periodikus és nem periodikus feladatokat


Valós idejű… • 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


Valós idejű… • 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 • Látni kell, hogy a valós idejű rendszerek szempontjából a tervezhetőség kardinális!


Valós Idejű OS-ek jellemzői • • • • •

Megjósolhatóság Válaszkészség Felhasználói kontroll Megbízhatóság Fail-soft működés


Valós Idejű OS-ek jellemzői • 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 • Felhasználói kontroll • Megbízhatóság • Fail-soft működés


Valós Idejű OS-ek jellemzői • Megjósolhatóság • Válaszkészség – Meghatározza, hogy az OS mennyi idő alatt hajtja végre a megszakítás kód közös részét. – A megjósolhatósággal együttvéve vizsgálandó • Felhasználói kontroll • Megbízhatóság • Fail-soft működés


Valós Idejű OS-ek jellemzői • Megjósolhatóság • Válaszkészség • 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 • Fail-soft működés


Valós Idejű OS-ek jellemzői • • • •

Megjósolhatóság Válaszkészség Felhasználói kontroll 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)

• Fail-soft működés


Valós Idejű OS-ek jellemzői • • • • •

Megjósolhatóság Válaszkészség Felhasználói kontroll Megbízhatóság 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ű OS tulajdonságok • • • • • • • • •

Gyors folyamat és/vagy szálváltás Kis méret, korlátozott funkciók Gyors reagálás a megszakításokra Multiprocessing, „komoly” IPC támogatás Speciális fájlok gyors adatrögzítéshez (pl. szekvenciális fájlok) Prioritás alapú, preemptiv ütemezés Megszakítások letiltásának ideje minimális Szolgáltatások folyamatok pontos késleltetésére Speciális időzítési funkciók


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

Statikus, táblázat alapú megoldások Statikus, prioritás alapú algoritmusok Dinamikus, terv alapú megközelítés Dinamikus, „best effort” működés


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 • Dinamikus, terv alapú megközelítés • Dinamikus, „best effort” működés


Valós idejű ütemezési megoldások • Statikus, táblázat alapú megoldások • 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 • Dinamikus, „best effort” működés


Valós idejű ütemezési megoldások • Statikus, táblázat alapú megoldások • Statikus, prioritás alapú algoritmusok • 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


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

Statikus, táblázat alapú megoldások Statikus, prioritás alapú algoritmusok Dinamikus, terv alapú megközelítés 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.


Ütemezési példa – klasszikus Unix • Jellemzői – 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 – 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).


Unix – prioritás számítása •

•

Változók – p_pri: aktuális ütemezési prioritás – p_usrpri: user módú prioritás (ez ált. azonos p_pri értékkel) – p_cpu: CPU használat mérésére szolgál – p_nice: felhasználó által megadható prioritás érték Algoritmus lépések – TMR IRQ (10 msec), aktív folyamat: p_cpu = max(p_cpu+1, 127) – schedcpu() rutint (1/sec), minden folyamat p_cpu értékét megszorozza • A szorzó értéke SVR3 esetén fix (½) • BSD esetén a rendszer aktuális terhelésétől függ – a terhelés növekedésével egyhez tart (kisebb, mint 1), így a folyamatok prioritásának növekedése nem gyorsul (nem úgy, mint konstans esetén).

•

– Az ütemező (1/sec) újraszámolja a folyamatok prioritását p_uspri = PUSER + (p_cpu / 4) + (2 * p_nice), PUSER=50 Kevesebb ideig futó és az I/O igényes folyamatoknak kedvez (utóbbiak sokszor várakoznak, így prioritásuk növekszik).


Ütemezési példa – Unix SVR4 • Teljesen újradolgozták az ütemezőt – Ez sem igazi RT, de már bizonyos időkorlátos műveleteket támogat.

• Statikus prioritású ütemezési osztály, 160 prioritási szint (egyes szinteken belül RR ütemezés) – 159 … 100: RT osztály (statikus prioritás) – 99 … 60 : Kernel – 59 … 0 : Időosztásos, változó prioritású

• Időosztásos tartományban az időszelet prioritás függő – (P0: 100 ms … P59: 10 ms)

• Megszakítási pontok kialakítása a kernelben – A kernel ettől nem lett tetszőlegesen megszakítható, de vannak benne olyan pontok, ahol biztonságban meg lehet szakítani az aktuális kernel funkciót.


Ütemezési példa – Unix SVR4

TS (timeshare): the default class. Priorities (0-59) are dynamically adjusted in an attempt to allocate processor resources evenly. IA (interactive): enhanced version of the TS class that applies to the window in the GUI.az Its ütemezőt intent is to give extra resources to •in-focus Teljesen újradolgozták processes associated window (rangeműveleteket is 0-59). – Ez sem igazi RT,with de that márspecific bizonyos időkorlátos támogat. scheduler): This class is share-based rather than FSS (fair-share •priorityStatikus based. prioritású Threadsütemezési managed by osztály, FSS are 160 scheduled prioritási based szinton (egyes szinteken belül their associated shares andRR the ütemezés) processor's utilization (range is – 159 … 100: RT osztály (statikus prioritás) 0-59). 99 … 60 : Kernel FX –(fixed-priority): The priorities for threads associated with this – 59 : Időosztásos, változó prioritású class do … not0 vary dynamically over the lifetime of the thread (range •0-59). Időosztásos tartományban az időszelet prioritás függő (P0: 100 ms P59:class 10 ms) SYS– (system): The…SYS is used to schedule kernel threads. •Threads Megszakítási in this class pontok are "bound" kialakítása threads, a kernelben which means that they A kernel ettől nem lett tetszőlegesen de vannak run –until they block or complete. Prioritiesmegszakítható, are in the 60-99 range. benne olyan pontok,inahol biztonságban meg lehet szakítani az RT (real-time): Threads the RT class are fixed-priority, with a aktuális kernel funkciót. fixed time quantum. Their priorities range 100-159. Sunday, March 7, 2010

Ütemezési példa – Unix SVR4 • Teljesen újradolgozták az ütemezőt – Ez sem igazi RT, de már bizonyos időkorlátos műveleteket támogat.

• Statikus prioritású ütemezési osztály, 160 prioritási szint (egyes szinteken belül RR ütemezés) – 159 … 100: RT osztály (statikus prioritás) – 99 … 60 : Kernel – 59 … 0 : Időosztásos, változó prioritású

• Időosztásos tartományban az időszelet prioritás függő – (P0: 100 ms … P59: 10 ms)

• Megszakítási pontok kialakítása a kernelben – A kernel ettől nem lett tetszőlegesen megszakítható, de vannak benne olyan pontok, ahol biztonságban meg lehet szakítani az aktuális kernel funkciót.


Mikor nem csak egy folyamat... • Korai megoldások (Unix) – signal-ok – pipe és FIFO

• Újabb eszközök (Unix, SysV IPC) – üzenetsorok (message queue) – osztott memória – szemaforok

• Az elv más rendszerekben is hasonló...


signal-ok

• • •

aszinkron események, callback függvény jellegű megvalósítás legtöbbjét a kernel küldi (timer, hibák), típuson túl adatot nem közvetít egy részük elkapható, egyesek tilthatók (de van, ami nem)


signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



signal-ok

• • •



pipe

• •

•

Bájt alapú kommunikáció Nincs fájlrendszer kapcsolat, csak „közeli rokon” folyamatok között működik • int fd[2]; • ... • pipe(fd); • if(fork() == 0) { read(fd[0], msg, 128); ... } • else { write(fd[1], message, 32); ... } Nem perzisztens


FIFO (named pipe)

• • •

Bájt alapú kommunikáció Fájlrendszer kapcsolat (speciális fájl), független folyamatok között is Perzisztens


üzenetsorok

• • •

Blokk alapú kommunikáció, több-több kapcsolat Header információ (int) alapján kiválasztási szabály adható Perzisztens


osztott memória

• •

Osztott lapok elérhetővé tétele az összes érintett folyamat címterében Hozzáférés vezérléssel


osztott memória

• •

Osztott lapok elérhetővé tétele az összes érintett folyamat címterében Hozzáférés vezérléssel


szemaforok • „Klasszikus” szemafor implementáció – bináris szemaforok (0,1 érték) – számláló típusú szemaforok

• Bináris szemafor kizárólagos hozzáféréshez • Számláló típusú véges mennyiségű erőforrás menedzsmentjéhez


Memóriakezelés • Az operációs rendszerek egyik legfontosabb funkciója • Az idők során különböző megoldások születtek, a fő elvárások konkrét megoldástól függetlenek: – – – – –

Á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 • Folyamatotkat 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


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.


Memóriakezelés – 1 „VM előtti idők” • Korai rendszerekben egyetlen program, memória kezelés nem volt • Az első operációs rendszerek (monitor) megjelenése: igény a memória védelemre (OS megvédése a programoktól) • Multiprogramozott rendszerek: OS általi, „valós” memória menedzsment megjelenése


Lapozás előtti megoldások • A programok számára a kért helyet egyben, összefüggő területként foglaljuk le • Algoritmusok – Particionálások (fix és dinamikus) – „Buddy” algoritmus – Szegmentálás


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)


Fix particionálás alesetei


Fix particionálá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:


Fix particionálá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


Partíció kiválasztási algoritmusok


Partíció kiválasztási algoritmusok • Közös várakozósor, a legkisebb szabad partíció használata • Minden programot a méretben legjobban illeszkedő várakozósorba helyezünk Összevetés:


Partíció kiválasztási algoritmusok • Közös várakozósor, a legkisebb szabad partíció használata • Minden programot a méretben legjobban illeszkedő várakozósorba helyezünk Összevetés: • Egyes partíciók kihasználtsága : 2. alg.


Partíció kiválasztási algoritmusok • Közös várakozósor, a legkisebb szabad partíció használata • Minden programot a méretben legjobban illeszkedő várakozósorba helyezünk Összevetés: • Egyes partíciók kihasználtsága : 2. alg. • Teljes rendszer hatékonysága: 1. alg.


Partíció kiválasztási algoritmusok • Közös várakozósor, a legkisebb szabad partíció használata • Minden programot a méretben legjobban illeszkedő várakozósorba helyezünk Összevetés: • Egyes partíciók kihasználtsága : 2. alg. • Teljes rendszer hatékonysága: 1. alg. Használat: IBM korai OS/MFT, ma már nem


Dinamikus particionálás • Fix particionálás gyengeségeinek áthidalására született • IBM OS/MVT által használt (Multiprogramming with variable number of tasks) • 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és • Ü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

• De: 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 • 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


OS, 8M

Free 56M

56/56M


Start (OS: 8M)

OS, 8M

Free 56M

56/56M


Start (OS: 8M)

OS, 8M

-P1: 20M Free 56M

56/56M


Start (OS: 8M)

OS, 8M

OS, 8M P1, 20M

-P1: 20M Free 56M

36M

56/56M


36/36M

Start (OS: 8M)

OS, 8M

P1, 20M

-P1: 20M -P2: 14M

OS, 8M

Free 56M 36M

56/56M


36/36M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

Free 56M

P2, 14M 36M 22M

56/56M


36/36M

22/22M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

Free 56M

P2, 14M 36M 22M

56/56M


36/36M

22/22M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

4M

56/56M


36/36M

22/22M

4/4M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

-P2: exit

4M

56/56M


36/36M

22/22M

4/4M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

-P2: exit

4M

56/56M OS, 8M P1, 20M 14M

P3, 18M 4M

18/14M Sunday, March 7, 2010

36/36M

22/22M

4/4M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

-P2: exit -P4: 8M

4M

56/56M OS, 8M P1, 20M 14M

P3, 18M 4M

18/14M Sunday, March 7, 2010

36/36M

22/22M

4/4M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

-P2: exit -P4: 8M


4M

56/56M

36/36M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

14M

P4, 8M

P3, 18M

P3, 18M

4M

4M

18/14M

10/6M

6M

22/22M

4/4M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

-P2: exit -P4: 8M -P1: exit


4M

56/56M

36/36M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

14M

P4, 8M

P3, 18M

P3, 18M

4M

4M

18/14M

10/6M

6M

22/22M

4/4M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

-P2: exit -P4: 8M -P1: exit


4M

56/56M

36/36M

22/22M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

20M

14M

P4, 8M

P4, 8M

6M

6M

P3, 18M

P3, 18M

P3, 18M

4M

4M

4M

18/14M

10/6M

30/20M

4/4M

Start (OS: 8M)

OS, 8M

-P1: 20M -P2: 14M -P3: 18M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

P1, 20M

P2, 14M

P2, 14M

22M

P3, 18M

Free 56M 36M

-P2: exit -P4: 8M -P1: exit -P5: 24M


4M

56/56M

36/36M

22/22M

OS, 8M

OS, 8M

OS, 8M

P1, 20M

P1, 20M

20M

14M

P4, 8M

P4, 8M

6M

6M

P3, 18M

P3, 18M

P3, 18M

4M

4M

4M

18/14M

10/6M

30/20M

4/4M

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


Buddy algoritmus • 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


Buddy algoritmus • 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

Start

1M

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

R100k

A

128k

256k

512k

R64k

A

B

64

256k

512k

R240k

A

B

64

C

512k

R256k

A

B

64

C

D

256k

Rel B

A

128k

256k

D

256k

D

256k

-A: out

Rel A


512k

Buddy értékelés • Általános célú algoritmusként már nem… • A mai (lapozásos) megoldásoknál sokkal egyszerűbb algoritmus –Módosított változata a mai Unix rendszerekben is megtalálható, kernel memória kezeléshez


Áthelyezés kérdésköre • Az eddigi algoritmusok esetén is felmerül – Swap folyamat következtében – Tömörítés során

• Lehetséges megoldás, CPU támogatással


Áthelyezési megoldá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

• 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.


Relatív cím

Base reg

program Összeadó

Ellenőr

adat Bounds reg

stack


Lapozás (egyszerű) • 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 • Folyamatos foglalás: a lapokat összefüggő módon foglaljuk a memóriában – Igazából „semmi extra”

• De: a memória hozzáférés (a most vizsgált esetekben címtől független  NUMA) – Ott foglaljunk lapot (egyesével), ahol éppen van üres – ez már komoly előnyökkel kecsegtet


Page no

Start

Load A

Load B

Load C

Term B

Load D

4 pgs

3 pgs

4 pgs

-

5 pgs

0

Free

A.0

A.0

A.0

A.0

A.0

1

Free

A.1

A.1

A.1

A.1

A.1

2

Free

A.2

A.2

A.2

A.2

A.2

3

Free

A.3

A.3

A.3

A.3

A.3

4

Free

Free

B.0

B.0

Free

D.0

5

Free

Free

B.1

B.1

Free

D.1

6

Free

Free

B.2

B.2

Free

D.2

7

Free

Free

Free

C.0

C.0

C.0

8

Free

Free

Free

C.1

C.1

C.1

9

Free

Free

Free

C.2

C.2

C.2

10

Free

Free

Free

C.3

C.3

C.3

11

Free

Free

Free

Free

Free

D.3

12

Free

Free

Free

Free

Free

D.4

13

Free

Free

Free

Free

Free

Free


Megoldás jellemzői • 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 Sunday, March 7, 2010

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

Fizikai cím

Megoldás jellemzői • 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 - 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


Fizikai cím

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).


Következmények • 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


Virtuális memóriakezelés • Megjelenésekor komoly viták zajlottak a megoldás hatékonyságáról • A (nem túl jelentős) teljesítmény csökkenésért cserébe jelentős előnyök: – 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)


VM működés • 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!


Visszatekintés - Lapozás • Laptábla meglehetősen nagy lehet, azt a központi memóriában tároljuk (nem CPU-ban). A laptábla kezdőpontjára egy CPU regiszter (Page table ptr) mutat. • 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. Sunday, March 7, 2010

Visszatekintés - Lapozás •

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)


Operációs Rendszerek II. 4. előadás

Recommend Documents