Pamět ová hierarchie, virtuální pamět. doc. Ing. Róbert Lórencz, CSc

Architektura poˇcítaˇcových systému˚ ˇ ˇ Pamet’ová hierarchie, virtuální pamet’

doc. Ing. Róbert Lórencz, CSc.

ˇ Ceské vysoké uˇcení technické v Praze Fakulta informaˇcních technologií Katedra poˇcítaˇcových systému˚

ˇ Pˇríprava studijních programu˚ Informatika pro novou fakultu CVUT je spolufinancována Evropským sociálním fondem ˇ a rozpoˇctem Hlavního mesta Prahy v rámci Operaˇcního programu Praha — adaptabilita (OPPA) projektem ˇ CZ.2.17/3.1.00/31952 – „Pˇríprava a zavedení nových studijních programu˚ Informatika na CVUT v Praze“. Praha & EU: Investujeme do vaší budoucnosti

ˇ R. Lórencz (CVUT FIT)

ˇ ˇ Pamet’ová hierarchie, virtuální pamet’

BI-APS, 2011, Pˇredn. 8.-10.

1 / 28

Obsah pˇrednášky

CPU výkonnostní rovnice ˇ virtuální pamet’ stránkování TLB segmentace



BI-APS, 2011, Pˇredn. 8.-10.

2 / 28

CPU výkonnostní rovnice s cache 1 ˇ Prum ˚ erný cˇ as CPU TCPU pro vykonání programu s použitím cache TCPU

= (CycCPU + CycMEM ) × TCLK = IC × (CPI + MAPI × MR × MP) × TCLK

ˇ CycMEM – # pamet’ových cˇ ekacích (stall) taktu˚ programu. CycMEM = IC × MAPI × MR × MP ˇ MAPI – # pamet’ových pˇrístupu˚ na instrukci programu.

ˇ prum ˚ erný # cˇ ekajících taktu˚ na jeden pˇrístup ˇ do pameti

?

MAPI =

ˇ # pˇrístupu˚ do pameti # instrukcí


AMAT = HT + MR × MP [takty]


BI-APS, 2011, Pˇredn. 8.-10.

3 / 28

CPU výkonnostní rovnice s cache 2 Instrukˇcní, datová a unifikovaná (spoleˇcná, sjednocená) cache ˇ ˇ rozdelená ˇ Prum ˚ erná doba pˇrístupu do pameti na cˇ tení instrukcí a dat AMAT = FI × (HTI + MRI × MPI ) + FD × (HTD + HTLS + MRD × MPD ) HTLS – extra hit pro load a store pro unifikovanou cache ⇐ jenom pro jednoportovou cache FI =

# instr. pˇrístupu˚ do MEM celkový # pˇrístupu˚ do MEM

FD =

# datových pˇrístupu˚ do MEM celkový # pˇrístupu˚ do MEM

HTI , MRI , MPI jsou hit time, miss rate a miss penalty pro instrukce HTD , MRD , MPD jsou hit time, miss rate a miss penalty pro data

ˇ Celkový miss rate MRS pro rozdelenou cache MRS = FI × MRI + FD × MRD



BI-APS, 2011, Pˇredn. 8.-10.

4 / 28

CPU výkonnostní rovnice s cache 3 Pˇríklad: FI = 75%, FD = 25%, HTI = HTD = HTU = HTLS = 1 16 KB instrukˇcní cache s 16 KB datovou cache MRI = 0.64 %, MPI = 50 taktu˚ ˇ Rešení: MRD = 6.47 %, MPD = 50 taktu˚ MRS = FI × MRI + FD × MRD 32 KB unifikovaná cache = (0.75 × 0.0064) + (0.25 × 0.0647) MRU = 1.99 %, MPU = 50 taktu˚ = 2.10 % Která cache má menší miss rate? MRS > MRU AMATS = FI × (HTI + MRI × MPI ) + FD × (HTD + MRD × MPD ) = 0.75 × (1 + 0.0064 × 50) + 0.25 × (1 + 0.0647 × 50) = 2.049 AMATU = FI × (HTU + MRI × MPI ) + FD × (HTU + HTLS + MRD × MPD ) = 0.75 × (1 + 0.0199 × 50) + 0.25 × (1 + 1 + 0.0199 × 50) = 2.245 AMATS < AMATU



BI-APS, 2011, Pˇredn. 8.-10.

5 / 28

CPU výkonnostní rovnice s cache 4 Pˇríklad 2: 8 KB unifikovaná cache s 32 B blok, 33 % L/S CPI = 2 takty, MAPI = 1.33, MP = 50 taktu, ˚ MR = 2% ˇ než bez ní? O kolik je výkonnost systému s cache vetší ˇ Rešení: S cache TCPU+CACHE

= = =

IC × (CPI + MAPI × MR × MP) × TCLK IC × (2 + 1.33 × 0.02 × 50) × TCLK IC × 3.33 × TCLK

Bez cache TCPU = IC × (CPI + MAPI × MP) × TCLK = IC × (2 + 1.33 × 50) × TCLK = IC × 68.5 × TCLK SCACHE =

TCPU TCPU+CACHE


=

IC × 68.5 × TCLK = 20.6 IC × 3.33 × TCLK


BI-APS, 2011, Pˇredn. 8.-10.

6 / 28

ˇ – principy 1 Virtuální pamet’

Virtuální pamìt’ Registry

L1 Cache

L2 Cache

Memory

Disk

Tape

Instrukce Operandy

Bloky

Bloky

Stránky

Soubory

Velikost

1 – 16 B

8 – 128 B

8 – 128 B

512 – 8 KB

» MB

Øídí

prog./poè.

OS

XåLY26

cache kon. cache kon.

ˇ Principu˚ lokalit lze podobneˇ jako u pamet’ových systému˚ s cache ˇ využít dále pro pamet’ové systémy rozšíˇrené o diskové jednotky.



BI-APS, 2011, Pˇredn. 8.-10.

7 / 28

ˇ – principy 2 Virtuální pamet’ ˇ – Virtual memory Virtuální pamet’ ˇ ˇ (OS) umožnuje sdílení pameti vzájemná ochrana programu˚ ˇ ochrana dat, než využití principu˚ lokalit v souˇcasnosti je duležit ˚ ejší Program pracuje se svým virtuálním adresním prostorem

VA – virtuální adresa HW mapování

PA – fyzická adresa

Fyzická pamìt’ (+caches)

ˇ každý bežící program pracuje se svým virtuálním adresním prostorem ˇ v pameti ˇ daných bežících ˇ OS rozhoduje o umístení programu˚ HW provádí VA → PA mapování ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

8 / 28

ˇ – principy 3 Virtuální pamet’ V = {0, 1, ..., n − 1} VA prostor (n m) M = {0, 1, ..., m − 1} PA prostor MAP: V → M ∪ {Z } zobrazovací – mapovací funkce adres MAP(a) = a0 , když data na adrese a VA jsou reprezentována daty ˇ PA na adrese a0 ∈ M fyzické pameti = Z když data na místeˇ VA a nejsou obsažena ve fyzické ˇ pameti ¡ Chybìjící polozka Zpracování chybìjících stránek

Procesor

a Virtuální adresa

Pøevod adres

Z a'

Hlavní pamìt’

Fyzická adresa

Vedlejší pamìt’ OS vykonává pøesun

Spolupráce hardwaru a softwaru



BI-APS, 2011, Pˇredn. 8.-10.

9 / 28

ˇ – stránkování 1 Virtuální pamet’

Virtuální adresní prostor 1. procesu

Rámce stránek

Virtuální adresní prostor 2. procesu

Disk

Velikost stránky = velikost rámce Fyzická pamìt’

ˇ Virtuální prostor je rozdelen na stejneˇ velké stránky (pages), které ˇ se pˇriˇrazují jednotlivým bežícím procesum. ˚ ˇ je rozdelená ˇ ˇ eˇ velkých rámcu˚ (frames) Fyzická pamet’ do stejn ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

10 / 28

ˇ – stránkování 2 Virtuální pamet’ Tabulka stránek Page table Stránky jsou mapované do rámcu˚ Stránky tvorí souvislý VA prostor, ale I I

ˇ ˇ korespondující rámce jsou libovolneˇ umístené ve fyzické pameti ne všechny stránky jsou mapované do rámcu˚

Stránky jsou jednotkou mapování a souˇcasneˇ jedna stránka je jednotˇ – fyzickou pametí ˇ kou pˇrenosu mezi diskem a hlavní pametí Protože je nemožné mít jednoduchou funkci pro libovolný pˇrevod VA na PA je pro tento úˇcel používána Lookup table – Page table (vyhledávací tabulka – tabulka stránek). Použití tabulky stránek pro mapování prostoru VA do prostoru PA: offset VA = offset PA = velikost stránky cˇ íslo rámce = Tabulka stránek (ˇcíslo virtuální strány) ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

11 / 28

ˇ – stránkování 3 Virtuální pamet’ VA – virtuální adresa

Page # Offset

Page Table Base Reg.PTBR

Page table ... V Access rights - AR Frame #

+

Index do page table

PA – Fyzická adresa Kdyz¡ bit platnosti V = 0, stránka není v pamìti (page fault)

. ... Page table je umístìná ve fyzické pamìti



BI-APS, 2011, Pˇredn. 8.-10.

12 / 28

ˇ – stránkování 4 Virtuální pamet’ Formát položky tabulky stránek tabulka stránek je dána struk. OS – obsahuje mapování VA → PA ˇ každý proces bežící v OS má vlastní tabulku stránek stav procesu: PC, všechny registry a tabulka stránek ˇ tabulky stránek se zmenou ˇ OS mení PTBR – obsahuje zaˇcátek tabulky stránek Formát položky tabulky stránek – Page table entry format (PTE) ˇ bud’ cˇ íslo rámce, nebo indikaci, že stránka není v hlavní pameti ˇ když V = 0, potom OS pˇrenese stránku z disku do hlavní pameti ˇ potom se když je stránka platná a je pˇrítomná v hlavní pameti, ˇ rí ješteˇ práva použití této stránky daným procesem: oveˇ I I

Access rights AR – pˇrístupová práva: Read Only, Read/Write, Executable



V

AR

Frame #

BI-APS, 2011, Pˇredn. 8.-10.

13 / 28

ˇ – stránkování 5 Virtuální pamet’ ˇ Porovnání 2 úrovní pamet’ové hierarchie ˇ Cache Virtuální pamet’ Blok/ˇrádek Stránka Miss Page fault Velikost bloku: 8 – 128B Velikost stránky: 512B – 8KB Typ: DM, N-way, asociativní asociativní ˇ obeti: ˇ LRU/Random ˇ obeti: ˇ LRU Výber Výber Write Thru/Write back Write back Poznámky k stránkování fragmentace: stránky mají stejnou velikost ⇒ každý rámec je využit OS rezervuje Swap space na disku pro každý proces když proces narustá ˚ potom: I I I

ˇ ˇ ené ˇ pokud nejaké stránky nejsou používané, jsou vymen jako první když ne, potom OS swapuje starší stránky na disk LRU vybírá stránky k swapování

každý proces má vlastní tabulku stránek ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

14 / 28

ˇ – stránkování 6 Virtuální pamet’ Výpadek stránky – page fault Když data jsou na disku ⇒ ˇ naˇcte se žádaná stránka z disku do prázdného rámce pameti pˇrenos prostˇrednictvím DMA a pˇrepnutí na proces, který cˇ eká když DMA je ukonˇcen ⇒ pˇrerušení a update tabulky stránek procesu ˇ na puvodní pˇri pˇrepnutí zpet ˚ úlohu jsou požadovaná data v hl. ˇ – naˇctené stránce pameti ˇ ⇒ Když je nedostatek pameti uvolníme rámec tak, že stránku s dirty bitem náležící programu zapíšeme na disk uvolníme rámec obsazen stránkou pomocí LRU aktualizuje se tabulka stránek programu (procesu) ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

15 / 28

ˇ – stránkování 7 Virtuální pamet’ Problem 1 ˇ Je málo fyzické pameti ˇ ˇ mejme 64 MB fyzické pameti ˇ N procesu˚ a každý z nich má 4 GB virtuální pameti mužeme ˚ mít až 1000 virtuálních stránek na 1 fyzickou stránku ˇ Rešení: Princip prostorové lokality velikost stránky ≈ 4 KB ⇒ množství blízkých referencí i veliký program požaduje v urˇcitém cˇ ase jen málo stránek ˇ pracovmí set: "práve"používané stránky ˇ navíc mapování každé adresy ⇒ další pˇrístup do pameti pozorování: platí princíp lokality uvnitˇr stránky ⇒ musí platit ve ˇ virtuálních adresách techto stránek proˇc nepoužít "cache – TLB"pro pˇrevod VA → PA pro urychlení pˇrevodu? ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

16 / 28

ˇ – stránkování 8 Virtuální pamet’ ˇ Cache a virtuální pamet’: VA Procesor

miss

PA Translation hit

Cache

Hlavní pamìt’

data

cache typicky pracuje s fyzickými adresami ˇ pro každý tabulka stránek pˇredstavuje další pˇrístup do pameti ˇ programový pˇrístup do pameti jak ˇrešit tento problém?



BI-APS, 2011, Pˇredn. 8.-10.

17 / 28

Translation Lookaside Buffer – TLB 1 Valid 1

VA 0xFA00

PA 0x0003

AR R/W

Dirty 1

Ref 0

ASID 34

TLB je cache pro položky tabulky stránek TLB pˇrístupový cˇ as je srovnatelný s cache Ref: používá se pro výpoˇcet LRU ˇ et ˇ jestli se Dirty: protože TLB pracuje Write back, musíme ved ˇ zapsat na disk má/nemá stránka pˇri odstranení AR: pˇrístup ASID: který uživatel Co když je miss TLB? 1

HW se podívá do tabulky stránek a naˇcte nové PTE do TLB

2

HW s OS rozhodne co dál ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

18 / 28

TLB 2

VA Procesor

Hit TLB Miss Translation

Miss

PA Hit Cache

Hlavní pamìt’

Data

TLB obvykle malá, typicky 128 - 256 položek ˇ asociativity TLB jako cache, muže ˚ být DM, s omezeným stupnem a plneˇ asociativní ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

19 / 28

Stránkování Problem 2 Tabulka stránek je pˇríliš velká! ˇ 4 KB stránka 4 GB virtuální pameti, ∼ 1 milión PTE 4 MB jen pro tabulku stránek jednoho procesu 25 procesu˚ ⇒ 100 MB pro tabuky stránek ˇ tak jeho tabulka stránek musí být celá ve fyzické Pokud proces beží, ˇ pameti. ˇ Rešení: ˇ víceúrovnové stránkování inverzní tabulka stránek segmentace ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

20 / 28

ˇ Víceúrovnové stránkování 1 ˇ Jednoúrovnová tabulka stránek: ˇ Císlo stránky p = 20 b

Offset d = 12 b

ˇ Víceúrovnová tabulka stránek: ˇ Super Císlo stránky p1 = 10 b

Offset p2 = 10 b

Offset d = 12 b

Tabulky stránek 2. úrovneˇ máme jenom pro platné položky super tabulky stránek Pokud máme jenom 10 % platných vstupu˚ super tabulky stránek, potom pro všechny tabulky stránek potˇrebujeme pˇribližneˇ 1/10 prostoru stránek jednoduchého stránkovaní !



BI-APS, 2011, Pˇredn. 8.-10.

21 / 28

ˇ Víceúrovnové stránkování 2 ˇ Pˇri víceúrovnovém stránkování jsou jednotlivé tabulky menší než ˇ ˇ v pameti ˇ pˇri jednoúrovnovém a mohou být ruzn ˚ eˇ umísteny ˇ ˇ dvouúrovnové stránkování vyžaduje 3 pˇrístupy do pameti p1

VA p2

d

Super Page Table

2nd Level Page Tables

p1{ p2 {

Fyzická pamìt’ PA



d{

BI-APS, 2011, Pˇredn. 8.-10.

22 / 28

Inverzní tabulka stránek – hashing 1 VA p

d

i

d

PA

Page Table Hash Table Page # PTE Chain (Hash) Fyzická pamìt’

Linked list

Frame #

jeden vstup pro každý rámec hledání pomocí hašovací tabulky/funkce vzhledem k tomu, že více VA mohou být mapovány do stejného vstupu, je pro nalezení správné položky použito "chaining"techniky, typický poˇcet kroku˚ je 1 až 2 ˇ R. Lórencz (CVUT FIT)


BI-APS, 2011, Pˇredn. 8.-10.

23 / 28

ˇ 2 Inverzní tabulka stránek – asociatívní pamet’

VA pid

p

d

Page table

i

d

PA

}i pid

p Fyzická pamìt’

Hledání

AsociatLvní pamìt’



BI-APS, 2011, Pˇredn. 8.-10.

24 / 28

Segmentace Puvodn ˚ eˇ není vztažené k stránkování, ale v mnoha systémech je segmentace spojená se stránkováním.



BI-APS, 2011, Pˇredn. 8.-10.

25 / 28

Segmentace se stránkováním 1 Jednotlivé segmenty jsou implementované jako stránkovaný virtuální adresní prostor.



BI-APS, 2011, Pˇredn. 8.-10.

26 / 28

Segmentace se stránkováním 2 Ochrana muže ˚ být specifikována lépe pˇres segment než pˇres stránku (sdílení).



BI-APS, 2011, Pˇredn. 8.-10.

27 / 28

Segmentace vs. stránkování

ˇ Externí fragmentace typická pro segmentci, absolutní pamet’ový ˇ požadavku, prostor je k dispozici pro splnení ˚ ale není souvisle obsazován. Interní fragmentace typická pro stránkování, alokovaná cˇ ást ˇ muže ˇ než je požadováno. pameti ˚ být vetší



BI-APS, 2011, Pˇredn. 8.-10.

28 / 28

Pamět ová hierarchie, virtuální pamět. doc. Ing. Róbert Lórencz, CSc

Recommend Documents