PAMĚŤOVÝ SUBSYSTÉM. Principy počítačů I. Literatura. Parametry paměti. Parametry paměti. Dělení pamětí podle funkce. Kritéria dělení pamětí

2003/2004 ZS

RNDr. David Obdržálek

Principy počítačů I

PAMĚŤOVÝ SUBSYSTÉM

2003/2004 ZS


Literatura • http://www.tomshardware.com

• http://www.play-hookey.com/digital/

„640 kB ought to be enough for anybody.“

Bill Gates, 1981

2003/2004 ZS


2003/2004 ZS

Parametry paměti

Parametry paměti

• kapacita

• přenosová rychlost

– objem informace, který je možno uchovat v jedné paměťové jednotce (obvykle ve slovech nebo bytech)

– čas, za který je paměť schopna vyřídit požadavek

– velikost přirozené jednotky paměti

(obvykle počet bitů, pomocí kterého je slovo reprezentováno)

• přenosová jednotka – počet datových elementů, které je možno přenést v 1 kroku (obvykle počet bitů (hl. paměť) nebo bloků (sek. paměť))


Kritéria dělení pamětí • • • • • • •

funkce způsob přístupu technologie umístění v systému vnitřní organizace detekce / opravy chyb ...

– rychlost, kterou mohou být data přenášena do/z paměti (špičková vs. zaručená)

• vybavovací doba

• velikost slova

2003/2004 ZS


• cyklus paměti – doba mezi dvěma bezprostředně za sebou jdoucími požadavky

• přístupová metoda

2003/2004 ZS


Dělení pamětí podle funkce • ROM – read only memory • RWM – read-write memory • Speciální – IRAM (Intelligent RAM) CRAM (Crypting RAM) ... • (WORM – write once, read many)

1

2003/2004 ZS


2003/2004 ZS

Varianty • ROM – – – – –

Dělení podle způsobu přístupu • RAM – Random Access Memory

• RWM

Mask ROM PROM EPROM EEPROM FLASH

– všechna paměťová místa mají svou adresu – k paměťovým místům může být přistupováno v libovolném pořadí – doba přístupu nezáleží na předchozí adrese, je konstantní

– DRAM – SRAM

• Speciální

• SAM – Sequential Access Memory

– IRAM – CRAM –……

2003/2004 ZS


– paměťová místa nemusejí mít svou adresu – přístup sekvenční – doba přístupu je závislá na vzdálenosti od počátku


2003/2004 ZS


Dělení podle způsobu přístupu • DAM – Direct Access Memory – paměťová místa mají jednoznačné adresy – přístup ke konkrétnímu místu je proveden kombinací výběru paměťové oblasti a sekvenčního přístupu v rámci této oblasti

• AAM – Associative Access Memory CAM – Contents-Addressable Memory

Technologie pamětí • • • • •

Pre-elektronické – relé, zpožďovací linky, ferritová pole Elektronické – RAM, FLASH,… Magnetické – bubny, pásky, disky Optické – CD, DVD, MD (chemické, biologické... )

– přístup k datům ne podle adresy, ale podle (části) obsahu – obvykle paralelní prohledávání

2003/2004 ZS


Elektronické paměti • Dynamické

2003/2004 ZS


Odbočka – číslicová logika • Booleova algebra

– pro udržení obsahu paměti je třeba obnovování

• Statické – pro udržení dat není třeba periodicky obnovovat

– NOT – AND – OR – XOR

& 1 =1

• pravdivostní tabulky!

2

2003/2004 ZS


2003/2004 ZS

NOR / NAND

Full-adder

• Pomocí hradla NOR (nebo NAND) je možno realizovat všechny ostatní logické funkce

• V některých technologických postupech je výroba NOR / NAND jednoduchá a laciná.

2003/2004 ZS



x

y

c-in

s

c-out

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

2003/2004 ZS


Klopný obvod R-S = jednoduchá statická paměť

8bitová sčítačka

1

0

1 -

1

0 0

0

0

1

R

S

0

0

Qn

Qn

Qn-1 Qn-1

0

1

1

0

1

0

0

1

1

1

?

?

Realizace hradly NOR

Realizace hradly NAND

... konec odbočky

2003/2004 ZS


http://www.play-hookey.com/digital/

2003/2004 ZS


Dynamická paměť - destruktivní čtení - limitovaná doba uložení + malý počet součástek (SRAM...6 tranz/b.)

Příklad realizace dynamické paměti pomocí kondenzátoru a tranzistoru

3

2003/2004 ZS


organizace paměti

X

2003/2004 ZS


typická organizace DRAM paměti řídící logika

paměť

addr

X

paměť

Y

sense amps Y-gating

addr RAS CAS WE

Y-gating Y data

2003/2004 ZS

data


2003/2004 ZS


Zvyšování výkonu DRAM • (Nibble Mode Access – využita lokalita přístupu – po vystavení dat možno pulsy ~CAS získat 4 po sobě jdoucí data)

• Page Mode Access – signál ~RAS podržen => data držena sense amps – signál ~CAS a sloupcová adresa měněny podle potřeby

• Fast Page Mode Access – podobné PM – ~RAS není držen po celou dobu => snížená spotřeba

2003/2004 ZS


Zvyšování výkonu DRAM • HyperPage Mode – Extended DataOut = EDO – datový výstup může být zachován i při změně adresy

• Burst EDO = BEDO – čtení / zápis formováno po čtyřech => interní změna dvou bitů adresy místo celé

2003/2004 ZS


Synchronní / asynchronní přístup • asynchronní – pro dokončení operace je třeba časové kvantum • synchronní – operace zcela řízena jednotným tikáním hodin

• Video DRAM = VRAM – přidán posuvný registr jako druhý interface, kam je zkopírován vystavený řádek – 1280x1024x70 = 90 MB/s ~ 1 B / 11 ns

4

2003/2004 ZS


Synchronní přístup k paměti • eliminace dodatečných signálů, jednotné časování, zjednodušení interface • JEDEC SDRAM (PC66 SDRAM) – – – –

dual-bank architektura možnost burst mode (1,2,4,8,page) 83 / 100 MHz (12 / 10 ns) chipy přidání SPD chipu pro identifikaci

2003/2004 ZS


• Double Data Rate = DDR SDRAM – Standard JEDEC omezen 125MHz – výstup aktivován jak na náběžné, tak na sestupné hraně hodinového signálu

• Rambus DRAM – – – –

Rambus a Intel celková změna interface 1,6GB/s Base, Standard, Direct

• PC100 SDRAM – specifikace Intel pro systémy > 83MHz

2003/2004 ZS


2003/2004 ZS

Protocol-based DRAM


Hierarchie pamětí mikropočítače

• Rambus DRAM • SyncLink DRAM (SLDRAM)

2003/2004 ZS

vyrovnávací paměť hlavní paměť

vnitřní

– open-industry standard – nevyžaduje změnu návrhu – nižší hodinová frekvence

odkládací (sekundární) paměť archivní paměť

vnější RNDr. David Obdržálek

Typické parametry v hierarchii technologie registry polovodiče, na procesoru cache polovodiče na/vně proc. hlavní p. polovodiče sekundární p. magnetický záznam archivní p. optický

procesor

registry

– proprietary

velikost

přístupová doba

B

~ 1 ns

kB

~ 10 ns

MB

~ 10-100 ns

GB

~ 1-10 ms

TB

~ 100 a více ms

2003/2004 ZS

L1,L2 cache „RAM“ pevný disk CD, DVD, pásek


Vyrovnávací paměti – cache • obvyklé použití: – procesor-hlavní paměť – počítač-pomalá periferie

• využití lokality přístupu: – Pokud byla data použita, je naděje, že budou použita znovu. Budou-li k dispozici v rychlé vyrovnávací paměti, nebude třeba na ně čekat

5

2003/2004 ZS


2003/2004 ZS

organizace cache

Fully Associative Mapping

• data v cache uložena spolu se svou adresou • Vyhledávání dat v cache: – – – –


• při vyhledávání adresy je adresa vyhledána v asociativním adresáři cache přímo • vysoká cena

plně asociativní mapování přímé mapování skupinově asociativní mapování (sektorové mapování)

tag

word data

tag

inf

= = =

2003/2004 ZS


2003/2004 ZS

Direct Mapping

Set Associative Mapping • kompromis mezi přímým a plně asociativním přístupem • cache rozdělena na množiny • množina obsahuje N řádek

• na jednom místě v cache může být více bloků • každý blok má v cache své místo tag

line tag

word

tag data

tag dekodér

word

data

inf

tag

=


uvolňovací mechanismy • Problém: jsou potřeba data, v cache není volné místo • Řešení: „něco“ se „vyhodí“ direct mapping: určeno jednoznačně LRU FIFO LFU random (vše bude vysvětleno později)

data

inf

dekodér

=

– – – – –

set

inf

dekodér

2003/2004 ZS


=

2003/2004 ZS


konzistence dat • Je třeba zajistit, aby data v cache odpovídala datům hlavní paměti • Strategie: – Write-Through – současný zápis do cache i hlavní paměti • časté zápisy do hlavní paměti

– Write-Back – zápis až při uvolnění z cache • možné problémy s koherencí při sdílení (více pamětí cache)

6

2003/2004 ZS


2003/2004 ZS

•

Přidělování paměti

OS

OS

OS

Uživatelský proces

Část uživatelského kódu je stále v paměti

Uživatelský proces

Uživatelský proces OS

OS

nutno řešit relokace a ochranu pevné oddíly – volné oddíly • •

•

•

bitová mapa (bloky stejné délky, „paragrafy“) spojový seznam bloků

Je třeba řešit: • •


pevné – paměť rozdělena na oddíly, procesy ve frontách podle požadované velikosti volné – procesy dostávají paměť podle potřeby

Řízení paměti • •

Overlays

Oblast překrývání

2003/2004 ZS

Přidělování v prostředí více procesů: • •

• (spojité - nespojité) • Přidělování v jednouživatelských OS:


který blok spojování volných bloků

2003/2004 ZS

Strategie přidělování • • • •

Virtuální paměť • Schopnost adresovat větší adresový prostor, než je fyzická paměť • Klíč – převod virtuálních adres na fyzické (parciální zobrazení) • 2 základní metody:

First Fit Next Fit Best Fit Worst Fit 6


5

3

10

20

– stránkování – segmentace

4

2003/2004 ZS


2003/2004 ZS

Stránkování

Stránkování fyzická paměť

• Virtuální adresový prostor rozdělen na bloky stejné velikosti – stránky (pages) • Fyzický adresový prostor rozdělen na bloky stejné velikosti jako stránky – rámce (frames)


rámec 0 rámec 1 ... rámec N-1

správce

představa procesu

stránka 0 ... stránka i ... stránka M-1

7

2003/2004 ZS


• Adresa ve virtuálním prostoru vyjádřena jako dvojice [p,d] • Mechanismus stránkování převede číslo stránky p na odpovídající číslo rámce p’ (lze-li to) – mapování. • Adresa ve fyzickém prostoru je pak vyjádřena dvojicí [p’,d] • Neexistuje-li mapování, dojde k výpadku stránky (page fault)

2003/2004 ZS

Překlad adresy u stránkování page number


page offset

virtuální adresa

stránkovací tabulka

fyzická adresa

příznaky

2003/2004 ZS


rámec

2003/2004 ZS

Problémy stránkování


Úpravy • Víceúrovňové stránkování

• velikost stránkovacích tabulek 32b adresy → 4GB, stránky 4kB ⇒ stránkovací tabulka má 1MB položek

• rychlost přístupu do stránkovacích tabulek instrukce s paměťovými operandy...

řeší problém velikosti tabulek

• Asociativní paměť řeší problém rychlosti přístupu - lokalita

• Nulaúrovňové stránkování nejsou stránkovací tabulky, pouze asociativní paměť

• Inverzní stránkovací tabulky organizace nad rámci, nikoli stránkami

2003/2004 ZS


Reálný příklad (4MB stránky)

2003/2004 ZS


Reálný příklad (4kB stránky)

8

2003/2004 ZS


2003/2004 ZS

Záznam stránkovací tabulky

2003/2004 ZS

Algoritmy výměny stránek


•

Skripta – FIFO, LIFO, LRU, LFU

• • • • •

Optimální stránka NRU – Not Recently Used CLOCK – Hodinový algoritmus LRU – Least Recently Used NFU – Not Frequently Used

2003/2004 ZS

FIFO


Optimální stránka

• klasická fronta: nahrazení stránky, která byla v paměti nejdéle – Beladiova anomálie – zvýšení počtu rámců může vést ke zvýšení počtu výpadků

2003/2004 ZS


1

2

3

4

5

4

3

2

1

6

7

1

1

1

1

5

5

5

5

5

5

5

2

2

2

2

2

2

2

1

1

1

3

3

3

3

3

3

3

6

6

4

4

4

4

4

4

4

7


• Vybrána bude stránka, na kterou přistoupíme za nejdelší dobu – nelze implementovat

2003/2004 ZS

NRU – Not Recently Used • Příznaky Accessed, Dirty (nastavuje HW, nuluje OS) • Algoritmus: periodické nulování A při výpadku volím náhodně ze tříd v pořadí A-D 0-0, 0-1, 1-0, 1-1


CLOCK – Hodinový algoritmus • • • •

Stránky jsou zařazeny v kruhovém seznamu Nastavování A Při výpadku: Je-li A=0, vyměním, je-li A=1, nastavím A=0 a posunu se

9

2003/2004 ZS


2003/2004 ZS


LRU – Least Recently Used

NFU – Not Frequently Used

• dlouho nepoužívané stránky asi nebudu potřebovat • seznam, který je při každém přístupu upravován • HW realizace:

• SW řešení LRU • Čítač u stránek, periodicky přičítáme A, vybere se nejnižší • Problém – nezapomíná. • Úprava – posunu doprava, přičítám doleva – stárnutí (aging)

– 64b čítač, který CPU při přístupu uloží do PTE, vybírá se nejnižší – matice n×n, při přístupu do rámce k nastavíme k-tý řádek na 1 a k-tý sloupec na 0. Vybírá se řádek s nejméně 1.

2003/2004 ZS


2003/2004 ZS


Segmentace

Segmentace fyzická paměť

• • • • • •

Segment – nezávislý adresový prostor 0..limit Organizace podle potřeb a struktury programu Segmenty různé a měnitelné velikosti Umístění v paměti neviditelné pro proces Výpadky segmentů obdobně jako u stránkování Segmenty je možno přesouvat

segment M


představa procesu

segment 0

segment i segment i ... segment 0

2003/2004 ZS

správce

2003/2004 ZS

segment M-1


Překlad adresy u segmentace segment number

segment offset

virtuální adresa

tabulka segmentů

+

fyzická adresa příznaky

adr. začátku segmentu

10

2003/2004 ZS


Kombinace segmentace a stránkování

2003/2004 ZS


Překlad adresy segment number

page number

virtuální adresa page offset

Logická adresa (Logical address) Jednotka řízení paměti (MMU - memory management unit)

46

Segmentace Lineární adresa (Linear address)

tabulka segmentů

stránkovací tabulka

32

Stránkování Fyzická adresa (Physical address)

+

32 (32-36)

fyzická adresa

11

PAMĚŤOVÝ SUBSYSTÉM. Principy počítačů I. Literatura. Parametry paměti. Parametry paměti. Dělení pamětí podle funkce. Kritéria dělení pamětí

Recommend Documents