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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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!
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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.
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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.
Sunday, March 7, 2010
Ü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
Sunday, March 7, 2010
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).
Sunday, March 7, 2010
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).
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.
Sunday, March 7, 2010
Ü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.
Sunday, March 7, 2010
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ó...
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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
Sunday, March 7, 2010
FIFO (named pipe)
• • •
Bájt alapú kommunikáció Fájlrendszer kapcsolat (speciális fájl), független folyamatok között is Perzisztens
Sunday, March 7, 2010
üzenetsorok
• • •
Blokk alapú kommunikáció, több-több kapcsolat Header információ (int) alapján kiválasztási szabály adható Perzisztens
Sunday, March 7, 2010
osztott memória
• •
Osztott lapok elérhetővé tétele az összes érintett folyamat címterében Hozzáférés vezérléssel
Sunday, March 7, 2010
osztott memória
• •
Osztott lapok elérhetővé tétele az összes érintett folyamat címterében Hozzáférés vezérléssel
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
Á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
Sunday, March 7, 2010
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.
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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).
Sunday, March 7, 2010
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.
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
Fix particionálás alesetei
Sunday, March 7, 2010
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:
Sunday, March 7, 2010
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
Sunday, March 7, 2010
Partíció kiválasztási algoritmusok
Sunday, March 7, 2010
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:
Sunday, March 7, 2010
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.
Sunday, March 7, 2010
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.
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
OS, 8M
Free 56M
56/56M
Sunday, March 7, 2010
Start (OS: 8M)
OS, 8M
Free 56M
56/56M
Sunday, March 7, 2010
Start (OS: 8M)
OS, 8M
-P1: 20M Free 56M
56/56M
Sunday, March 7, 2010
Start (OS: 8M)
OS, 8M
OS, 8M P1, 20M
-P1: 20M Free 56M
36M
56/56M
Sunday, March 7, 2010
36/36M
Start (OS: 8M)
OS, 8M
P1, 20M
-P1: 20M -P2: 14M
OS, 8M
Free 56M 36M
56/56M
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
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
4M
56/56M
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
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
-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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
Á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
Sunday, March 7, 2010
Á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.
Sunday, March 7, 2010
Relatív cím
Base reg
program Összeadó
Ellenőr
adat Bounds reg
stack
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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).
Sunday, March 7, 2010
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
Sunday, March 7, 2010
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)
Sunday, March 7, 2010
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!
Sunday, March 7, 2010
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)
Sunday, March 7, 2010