Számítógép Architektúrák

Számítógép Architektúrák A virtuális memória

Horváth Gábor

2016. március 30. Budapest

docens BME Hálózati Rendszerek és Szolgáltatások Tanszék [email protected]

Virtuális tárkezelés  Motiváció: • Multitaszking környezet • Taszkok jönnek-mennek • A programunknak jutó memóriaméret változó • Olcsó 64 bites processzorok • Ebből pl. az AMD64 48 bitet használ: 256 TB • Ennyi memóriát nem tudunk hozzáilleszteni

 A CPU minden programnak a teljes címtartományt felajánlja • 0-tól → a címtartomány tetejéig • Ne legyen gond a memóriaméret

 Ezt a „virtuális” memóriát kell leképezni a fizikaiba → Virtuális tárkezelés

Számítógép Architektúrák

© Horváth Gábor, BME Hálózati Rendszerek és Szolgáltatások Tsz.

2

Virtuális tárkezelés  Programok: Virtuális címeket használnak  CPU lábain/buszon: Fizikai címek jelennek meg  Virtuális → fizikai cím leképzés: Címfordítás • Aki csinálja: MMU • Amikor csinálja: minden memóriahivatkozáskor • Egysége: Lap (fix) vagy szegmens (változó méretű)

 Ha nem fér mindenki a fizikai memóriába → háttértárra kerül (swap-elés)



3

Virtuális tárkezelés



4

Címfordítás  A virtuális címtartományt fix méretű lapokra particionáljuk  A fizikai címtartományt ugyanekkora keretekre osztjuk  Méretek: • Lapok mérete = 2 L • Alsó L bit: lapon belüli eltolás • Felső bitek: virt. címeknél lapsorszám, fiz. címeknél keretsorszám  Lap ↔ keret összerendeléseket tárolja: laptábla  Összerendeléshez kell: • • • •

Lap sorszáma Keret sorszáma Védelmi információ (írható/olvasható) Vezérlő bitek: • Valid • Dirty



5

Címfordítás



6

TLB  Memória-hozzáférés menete: • Címfordítás: Fizikai cím előállítása a virtuálisból • Tényleges adat olvasás/írás a fizikai címről/címre

 A laptábla is a fizikai memóriában van!

 1 memóriaművelet a programban    

→ 2 memóriaművelet a valóságban !! Nem elég lassú a memória e nélkül is? De. Reménység: lokalitás TLB: translation lookaside buffer • A gyakran használt virtuális ↔ fizikai összerendelések cache-e • Címfordításkor először a TLB-ben keres



7

Címfordítás TLB-vel



8

TLB jellemzői  TLB lefedettség: a TLB bejegyzések által lefedett címtartomány • Minél nagyobb, annál ritkábban kell a lassú laptáblához nyúlni

 TLB megvalósítása: tartalom szerint címezhető memória → Nagy a felülete és sokat fogyaszt → Szűkös a tárolási kapacitása :( TLB méret:

16 – 512 bejegyzés

Találat ideje:

0.5 – 1 órajel

TLB hiba esetén címfordítási idő:

10 – 100 órajel

TLB hibaarány:

0.01% – 1%



9

Laptábla implementációk  Cél: • Címfordítás legyen minél gyorsabb → virtuális cím szerinti keresés legyen gyors

→ minél kevesebbszer kelljen a memóriához nyúlni • Laptábla legyen a lehető legkisebb

 Eszköz: • Speciális adatszerkezetek • Egyszintű laptábla • Többszintű (hierarchikus) laptábla • Inverz laptábla • (Virtualizált laptábla)



10

Egyszintű laptábla  Laptáblabejegyzések tömbje  i. bejegyzés: i. laphoz tartozó keret



11

Egyszintű laptábla  Keresés: gyors!  Bejegyzés megtalálása: pontosan 1 memóriaművelet!



12

Egyszintű laptábla  Bejegyzés mérete: kicsi • Nem kell tárolni a virtuális címet → az pont az index • Nem kell külön tárolni a háttértáron való elhelyezkedést



13

Egyszintű laptábla  Gyors, kevés memória-hozzáférés kell, kicsi a bejegyzés... ...miért nem használ mindenki ilyet? A teljes laptáblának bent kell lennie a memóriában!  Gyors kalkuláció: • 32 bites esetben, 4 kB lapokkal: • Lapméret: 12 bit, lapok száma: 32-12 = 20 bit, 1 mega-lap • 1 bejegyzés: 4 bájt elég, laptábla mérete: 4 MB • 64 bites esetben, 4 kB lapokkal: • Lapméret: 12 bit, lapok száma: 64-12 = 52 bit, 2 52 db lap • 1 bejegyzés: 8 bájt, laptábla mérete: 8 * 2 52 = 32 PB Számítógép Architektúrák


14

Hierarchikus laptábla  Ötlet: magát a laptáblát is lapokra bontjuk  A laptábla lapok elhelyezkedését egy másik laptáblában tároljuk, azokét egy harmadikban, stb.



15

Hierarchikus laptábla  Csak azt tartjuk a memóriában, ami tényleg kell  Több memóriaművelet kell a címfordításhoz → lassú!



16

Kétszintű laptábla, példa



17

Hierarchikus laptábla  Gyors kalkuláció: • 32 bites esetben, 4 kB lapokkal: • Lapméret: 12 bit, 1 bejegyzés: 4 bájt elég • Egy lapra 1024 bejegyzés fér → 10 bittel indexelhető • Kell 1024 laptábla lap, és még egy lap, ami ezekre mutat • 32 bites cím = 10 + 10 + 12 bites részek → 2 szintű laptábla kell • 64 bites esetben, 4 kB lapokkal: • Lapméret: 12 bit, 1 bejegyzés: 8 bájt • Egy lapra 512 bejegyzés fér → 9 bittel indexelhető • 64 bites cím = 7 + 9 + 9 + 9 + 9 + 9 + 12 bites részek → 6 szintű laptábla kell! 6 memóriaművelet / címfordítás !!!  X86, ARM Számítógép Architektúrák


18

Inverz laptábla  Miért is voltak nagyok az eddigi laptáblák? • Összerendelés: i. bejegyzés = i. laphoz tartozó keret • Elemszám = lapok száma

 Fordított gondolkodás: • Összerendelés: i. bejegyzés = i. keretben lévő lap száma • Elemszám = keretek száma • → Inverz laptábla

 Mit nyerünk? • Kicsi lesz a laptábla (fizikai memória méretével arányos)

 Mit vesztünk? • Adott lapsorszámhoz tartozó keretet keressük • A tömbünk indexei keretsorszámok, a bejegyzés tartalma a lap száma → Tartalom szerint kell keresnünk!

 Tartalom szerinti kereséshez: hash függvény Számítógép Architektúrák


21

Inverz laptábla

 Pl. jó hash függvény: Lapsorszám alsó bitjei Számítógép Architektúrák


22

Inverz laptábla  Hash mutató táblában: • Pointer: „Hol lehetnek az ilyen lapok a laptáblában?”

 Laptáblában: • „Ebbe a bejegyzésbe én vagyok írva?” • „Nem? Pech. Hol vannak még hozzám hasonló lapok?” „Követem a pointert” • „Ebbe a bejegyzésbe már én vagyok írva?” • „Nem. Nem baj, megyek tovább. Talán itt?” • „Igen? Szuper. Hányadik bejegyzésen állok? 329?” • „Akkor a fizikai memória 329-es keretében vagyok elhelyezve!” Számítógép Architektúrák


23

Inverz laptábla  Mitől függ a memóriaműveletek száma? • Először a hash mutató táblát kell kiolvasni • + ahány lépést kell tenni a laptábla láncolt listájában

 És az mitől függ? → Attól, hogy mennyire van tele a memória

 Normál terhelés (nincs tele a memória) → 1 memóriaművelet / címfordítás (+1: hash mutató tábla)

 Nagy terhelés (megtelt a memória) → >1 memóriaművelet / címfordítás (+1: hash mutató tábla) De akkor már úgyis mindegy (swap-eléstől lassú a rendszer)

 PA-RISC, PowerPC



24

Szoftver menedzselt TLB  Eddig: laptábla bejárás → hardver  Csinálhatja a szoftver is! → Szoftver menedzselt TLB  Címfordítás: • CPU a TLB-ből próbálkozik, • TLB hiba: op. rendszerre bízza a címfordítást! • A lap ↔ keret összerendelést az op. rendszer írja a TLB-be

 Op. rendszer kezeli: • A TLB tartalmát • A laptábla bejárást (tetszőleges adatszerkezet lehet) • pl. SPARC Solaris Unix: Inverz laptáblát használ • pl. SPARC Linux: Hierarchikus laptáblát használ

 Előnye: • Nincs hardver megkötés, op. rendszer frissítéssel jöhet hatékonyabb laptábla • Bonyolultabb adatszerkezetek is használhatók

 Hátránya: • Sokkal lassabb címfordítás

 Példa: SPARC, Alpha, MIPS, félig a PA-RISC Számítógép Architektúrák


25

Méretezési kérdések  Mekkora lapokat használjunk? • Nagyot, mert • Nagyobb a TLB lefedettség, kevesebb a laphiba • Diszk háttértár nagyot és kicsit kb. egyforma ideig tölt be – Akkor már vigyünk be minél nagyobb darabot • Kicsit, mert • A lapon csak az van, ami kell. • És ami nem kell, ne foglalja már a drága, kicsi memóriát • Gyakorlatban: 4 – 8 kB



26

Címtér elkülönítés 

Cél: minden taszk kapja meg a teljes címtartományt (pl. 0 → 4 GB)



Előnyök: • Állandó futási környezet → könnyebb szoftverfejlesztés – Fordításkor ismert » a belépési pont » a globális változók címe » a függvények címe » stb. •



Védelmet ad • Nem tudja elérni más taszkok címterét!

Megoldások: • Kizárólag laptáblával trükközve is lehet •

Vagy hardver támogatással



27

Címtér elkülönítés a laptáblára alapozva 

Megoldás: • Taszkonként külön laptábla •

Taszkváltáskor: • Laptábla kezdőpointer lecserélése • TLB invalidálás!



Lehetnek osztott címtartományok, ugyanazokkal a keretekkel • Szükséges az op. rendszer meghívásához!



28

Címtér elkülönítés a laptáblára alapozva  Gond: TLB ürítés taszkváltáskor • Míg fel nem telik újra, lassúak a memóriaműveletek

 Megoldás: • Címtér azonosító (ASID) → taszk azonosító • TLB bejegyzés mezői: lap, keret, ASID • Működés: • Op. rendszer taszk váltáskor egy spec. regiszterbe írja az aktuális ASID-ot • A CPU csak az erre vonatkozó TLB bejegyzéseket használja • A TLB több taszk laptábla bejegyzéseit is tudja tárolni! → nem kell TLB invalidálás taszkváltáskor!



29

Címtér elkülönítés szegmentálással  Logikailag egybetartozó objektumok külön szegmensbe • A virtuális memóriában • Bárhol kezdődhetnek • Folytonosak • Tetszőleges (sőt, változó) hosszúak • Saját címterük van (0-tól címezhető)!

 Kétlépcsős címfordítás • Szegmens → virtuális memória (szegmensleíró tábla) • Virtuális memória → fizikai memória (laptábla)



30

Címtér elkülönítés szegmentálással

 Szegmensen belül: közeli címzés / ugrás  Szegmenseken át: távoli címzés / ugrás  X86 / 32 bites mód: taszkonként 3 szegmens: • Kód / adat / stack • Windows/linux nem használja  X86 / 64 biten: gyakorlatilag megszünt Számítógép Architektúrák


31

Fizikai címkiterjesztés  Általában: virtuális memória > fizikai memória  De mi van, ha nem? • 32 bites CPU tud-e > 4GB memóriát? • Alapesetben nem tud • pointerek 32 bitesek!

 1. megoldás: váltás 64 bitre → inkompatibilitás • Milliárdnyi lefordított 32 bites program van • Nem mindig oldható meg az újrafordítás

 2. megoldás: fizikai címkiterjesztés (PAE) • • • •

Hack: szélesítsük ki a laptáblában a keret azonosítót! Minden program továbbra is 0 → 4 GB De több program együttvéve > 4GB is lehet! Viszont • Szélesebb laptábla bejegyzés → nő a laptábla szintek száma • Más laptábla formátum → op. rendszer támogatás szükséges

 Gyakorlatban: • x86: 36 bites fizikai cím (64 GB) • ARM: 40 bites fizikai cím (1 TB)



32

Virtuális tárkezelés a gyakorlatban



33

Virtuális tárkezelés a gyakorlatban x86  Szegmentálás + lapozás, gyakorlatban inkább csak lapozás  Hierarchikus laptábla. Alap: 4 kB-os lapok  Módok: • 32 bit, PAE nélkül: 12 bit eltolás, 10 bit másodszintű, 10 bit első szintű laptábla index • 32 bit, PAE: • 36 bites fizikai címek támogatása (64 GB, de csak 4 GB / program!) • 8 bájtos laptábla bejegyzések: 512/lap, 3 szint kell! 12 bit eltolás, 9 bit harmad, 9 bit másod, 2 bit első szintű laptábla index • 64 bit: • 48 bites virtuális, 40 bites fizikai címek (bővíthetők 64-ig) • 8 bájtos laptábla bejegyzések: 512/lap, 4 szint kell! 12 bit eltolás, 9 bit negyed, 9 bit harmad, 9 bit másod, 9 bit első szintű laptábla index 

Nagy lapok: 1 szint megspórolható



34

Virtuális tárkezelés a gyakorlatban ARM  Hierarchikus laptábla  Vegyesen használható lapméretek: • • • •

4 kB (small page) 64 kB (large page) 1 MB (section) 16 MB (super section)

 Section / supersection: 1 szintű címfordítás  Small page / large page: 2 szintű címfordítás  Az ARM is tud PAE-t (Cortex A15, 40 bites fizikai címek, 1 TB RAM) • Ára: egy szinttel mélyebb laptáblák

 ARMv8: 48 bites virtuális és fizikai címek, 4 szintű laptáblák



35

Virtuális tárkezelés a gyakorlatban PowerPC  Inverz laptábla, de láncolt lista nélkül  2 tömböt használ: • (Inverz) laptábla: lap ↔ keret összerendelések • Hash tábla: • Hash függvény: minden laphoz → 2 hash tábla bejegyzés • 1 hash tábla bejegyzés: 8 lapszám ↔ laptábla index összerendelés • A lapszám a 16 laptábla bejegyzés egyikében kell legyen • Ha nincs → laphiba (op. rendszer kezeli)



37

Számítógép Architektúrák

Recommend Documents