l14虛擬機提綱內(nèi)容主要取材cs61c24講cs1528虛擬存儲器

MemoryHierarchy

UpperLevelInstrOperands Faster

Earlier:

Caches

Blocks

Blocks

NextUp:VirtualMemory

Pages

Files

7/30/2012

Summer2012--Lecture#24

LargerLowerLevel

3

Tape

Disk

Memory

L2Cache

L1Cache

Regs

MemoryHierarchyRequirements

PrincipleofLocality

Allowscachestooffer(closeto)speedofcachememorywithsizeofDRAMmemory

CanweusethisatthenextleveltogivespeedofDRAMmemorywithsizeofDiskmemory?

Whatotherthingsdoweneedfromour

memorysystem?

7/30/2012

Summer2012--Lecture#24

4

MemoryHierarchyRequirements

Allowmultipleprocessestosimultaneouslyoccupymemoryandprovideprotection

Don’tletprogramsreadfromorwritetoeach

other’smemories

Giveeachprogramtheillusionthatithasitsownprivateaddressspace(viatranslation)

Supposecodestartsataddress0x00400000,thendifferentprocesseseachthinktheircoderesidesatthesameaddress

Eachprogrammusthaveadifferentviewofmemory

7/30/2012 Summer2012--Lecture#24 5

VirtualMemory

Nextlevelinthememoryhierarchy

Providesillusionofverylargemainmemory

Workingsetof“pages”residinginmainmemory(subsetofallpagesresidingondisk)

Maingoal:Avoidreachingallthewaybacktodiskasmuchaspossible

Additionalgoals:

LetOSsharememoryamongmanyprogramsandprotectthemfromeachother

Eachprocessthinksithasallthememorytoitself

7/30/2012

Summer2012--Lecture#24

6

VirtualtoPhysicalAddressTranslation

Virtual

Address(VA)

(inst.fetchload,store)

load,store)

Eachprogramoperatesinitsownvirtualaddress

spaceandthinksit’stheonlyprogramrunning

Eachisprotectedfromtheother

OScandecidewhereeachgoesinmemory

Hardwaregivesvirtual→physicalmapping

7/30/2012 Summer2012--Lecture#24

7

Programoperatesinitsvirtualaddressspace

Physicalmemory(includingcaches)

HW

mapping

Physical

Address(PA)

(inst.fetch

VMAnalogy(1/2)

TryingtofindabookintheUCBsystem

Booktitleislikevirtualaddress(VA)

Whatyouwant/arerequesting

Bookcallnumberislikephysicaladdress(PA)

Whereitisactuallylocated

Cardcatalogueislikeapagetable(PT)

Mapsfrombooktitletocallnumber

Doesnotcontaintheactualthatdatayouwant

Thecatalogueitselftakesupspaceinthelibrary

7/30/2012 Summer2012--Lecture#24 8

VMAnalogy(2/2)

Indicationofcurrentlocationwithinthe

librarysystemislikevalidbit

Validifincurrentlibrary(mainmemory)vs.invalidifinanotherbranch(disk)

Foundonthecardinthecardcatalogue

Availability/termsofuselikeaccessrights

Whatyouareallowedtodowiththebook(abilitytocheckout,duration,etc.)

Alsofoundonthecardinthecardcatalogue

7/30/2012

Summer2012--Lecture#24

9

北京航空航天大學(xué)計算機學(xué)院

提綱

內(nèi)容主要取材：CS61C的24講

虛擬存儲器

頁表(PageTables)

TLB(TranslationLookasideBuffer)

VM性能

VM總結(jié)

UserC

UserB

UserA

OS

Heap

Static

MappingVMtoPM

Divideintoequalsizedchunks(about4KiB-8KiB)

AnychunkofVirtualMemorycanbeassignedtoanychunkofPhysical

Memory(“page”)

PhysicalMemory

VirtualMemory

64MB

7/30/20120 Summer2012--Lecture#24 0 12

page0

page1

page2

VirtualMemoryMappingFunction

Howlargeismainmemory?Disk?

Don’tknow!Designedtobeinterchangeablecomponents

Needasystemthatworksregardlessofsizes

Uselookuptable(pagetable)todealwitharbitrarymapping

Indexlookuptableby#ofpagesinVM(notallentrieswillbeused/valid)

SizeofPMwillaffectsizeofstoredtranslation

7/30/2012

Summer2012--Lecture#24

14

AddressMapping

Pagesarealignedinmemory

Borderaddressofeachpagehassamelowestbits

PagesizeissameinVMandPM,sodenotelowestO=log2(pagesize/B)bitsaspageoffset

Useremainingupperaddressbitsinmapping

Tellsyouwhichpageyouwant(similartoTag)

PhysicalPage#PageOffset

VirtualPage# PageOffset

Notnecessarily

thesamesize

7/30/2012

SameSize

Summer2012--Lecture#24

15

AddressMapping:PageTable

PageTablefunctionality:

IncomingrequestisVirtualAddress(VA),wantPhysicalAddress(PA)

PhysicalOffset=VirtualOffset(aligned)

SojustswapVirtualPageNumber(VPN)forPhysicalPageNumber(PPN)

VirtualPage# PageOffset

Implementation?

UseVPNasindexintoPT

StorePPNandmanagementbits(Valid,AccessRights)

DoesNOTstoreactualdata(thedatasitsinPM)

7/30/2012 Summer2012--Lecture#24 16

PhysicalPage#

V

AR

PPN

X

XX

2)CheckValidandAccessRightsbits

...

PageTableEntryFormat

ContainseitherPPNorindicationnotinmainmemory

Valid=Validpagetableentry

1→virtualpageisinphysicalmemory

0→OSneedstofetchpagefromdisk

AccessRightscheckedoneveryaccesstoseeifallowed(providesprotection)

ReadOnly:Canread,butnotwritepage

Read/Write:Readorwritedataonpage

Executable:Canfetchinstructionsfrompage

7/30/2012

Summer2012--Lecture#24

18

PageTables(1/2)

Apagetable(PT)containsthemappingofvirtualaddressestophysicaladdresses

Pagetableslocatedinmainmemory–Why?

Toolargetofitinregisters(220entriesfor4KiBpages)

Fastertoaccessthandiskandcanbesharedbymultipleprocessors

TheOSmaintainsthePTs

Eachprocesshasitsownpagetable

“State”ofaprocessisPC,allregisters,andPT

OSstoresaddressofthePTofthecurrentprocessinthePageTableBaseRegister

7/30/2012 Summer2012--Lecture#24 19

PageTables(2/2)

Solvesfragmentationproblem:allpagesare

thesamesize,socanutilizeallavailableslotsOSmustreserve“swapspace”ondisk

foreachprocess

Runningprogramsrequiresharddrivespace!

Togrowaprocess,askOperatingSystem

IfunusedpagesinPM,OSusesthemfirst

Ifnot,OSswapssomeoldpages(LRU)todisk

7/30/2012

Summer2012--Lecture#24

20

Paging/VirtualMemoryMultipleProcesses

UserA: UserB:

VirtualMemory

VirtualMemory

Physical

Memory

64MB

Code

7/30/2012

Page

TableA

Page

TableB

Summer2012--Lecture#24

21

Static

Stack

Static

Code

Review:PagingTerminology

Programsusevirtualaddresses(VAs)

Spaceofallvirtualaddressescalledvirtualmemory(VM)

Dividedintopagesindexedbyvirtualpagenumber(VPN)

Mainmemoryindexedbyphysicaladdresses(PAs)

Spaceofallphysicaladdressescalledphysicalmemory(PM)

Dividedintopagesindexedbyphysicalpagenumber(PPN)

7/30/2012 Summer2012--Lecture#24 22

Question:Howmanybitswidearethefollowing

fields?

16KiBpages

40-bitvirtualaddresses

64GiBphysicalmemory

?

?

?

?

VPN PPN

26 26

24

22

20

22

23

北京航空航天大學(xué)計算機學(xué)院

提綱

內(nèi)容主要取材：CS61C的24講

虛擬存儲器

頁表(PageTables)

TLB(TranslationLookasideBuffer)

VM性能

VM總結(jié)

RetrievingDatafromMemory

PTUser1 Physical

Memory

VA1

1)Accesspage

tableforaddresstranslation

PTUser2

User1Virtual

AddressSpace

VA2

2)Accesscorrect

physicaladdress

User2Virtual

AddressSpace

7/30/2012

Requirestwoaccesses

ofphysicalmemory!

Summer2012--Lecture#24

25

VirtualMemoryProblem

2physicalmemoryaccessesperdataaccess

=SLOW!

Sincelocalityinpagesofdata,theremustbelocalityinthetranslationsofthosepages

BuildaseparatecacheforthePageTable

Forhistoricalreasons,cacheiscalledaTranslationLookasideBuffer(TLB)

NoticethatwhatisstoredintheTLBisNOTdata,

buttheVPN→PPNmappingtranslations

7/30/2012

Summer2012--Lecture#24

26

TLBsvs.Caches

Memory

Address

D$/I$

Dataatmemoryaddress

VPN

TLB

PPN

Onmiss:Accessnext

cachelevel/mainmemory

Onmiss:AccessPage

Tableinmainmemory

TLBsusuallysmall,typically16–512entries

TLBaccesstimecomparabletocache(?mainmemory)

TLBscanhaveassociativity

–Usuallyfully/highlyassociative

7/30/2012 Summer2012--Lecture#24 27

WhereAreTLBsLocated?

Whichshouldwecheckfirst:CacheorTLB?

Cancacheholdrequesteddataifcorrespondingpageisnotinphysicalmemory?No

WithTLBfirst,doescachereceiveVAorPA?

CPU

VA

TLB

hit

PA

miss

Cache

Main

dataMemory

miss hit

Page Noticethatitisnowthe

Table TLBthatdoestranslation,notthePageTable!

7/30/2012

Summer2012--Lecture#24

28

BasedVirtual-MemoryMachine

(HardwareTableWalk)

PageFault? PageFault?

Protectionviolation? Protectionviolation?

Virtual Virtual

Address

PhysicalAddress

Address

Inst.

PC TLB

Inst.Cache

D

Decode

E +M

DataTLB

PhysicalAddress

DataCache

W

Miss?

Miss?

BaseRegister

PhysicalAddress

PhysicalAddress

PhysicalAddress

Assumespagetablesheldinuntranslatedphysicalmemory

February16,2012

CS152,Spring2012

29

MainMemory(DRAM)

MemoryController

HardwarePageTableWalker

TLBTag

PPN

(usedjust

likeinacache)

...

Tag

BlockData

...

Valid

Dirty

Ref

AccessRights

TLBTag

PPN

X

X

X

XX

Valid

Dirty

Ref

AccessRights

TLBTag

PPN

X

X

X

XX

FetchingDataonaMemoryRead

CheckTLB(input:VPN,output:PPN)

TLBHit:Fetchtranslation,returnPPN

TLBMiss:Checkpagetable(inmemory)

PageTableHit:LoadpagetableentryintoTLB

PageTableMiss(PageFault):Fetchpagefromdisktomemory,updatecorrespondingpagetableentry,thenloadentryintoTLB

Checkcache(input:PPN,output:data)

CacheHit:Returndatavaluetoprocessor

CacheMiss:Fetchdatavaluefrommemory,storeitincache,returnittoprocessor

7/30/2012 Summer2012--Lecture#24 33

PageFaults

Loadthepageoffthediskintoafreepageofmemory

Switchtosomeotherprocesswhilewewait

Interruptthrownwhenpageloadedandtheprocess'pagetableisupdated

Whenweswitchbacktothetask,thedesireddatawillbeinmemory

Ifmemoryfull,replacepage(LRU),writingbackifnecessary,andupdatebothpagetables

Continuousswappingbetweendiskandmemorycalled“thrashing”

7/30/2012 Summer2012--Lecture#24 34

PerformanceMetrics

VMperformancealsousesHit/MissRatesandMissPenalties

TLBMissRate:FractionofTLBaccessesthatresultinaTLBMiss

PageTableMissRate:FractionofPTaccessesthatresultinapagefault

Cachingperformancedefinitionsremainthesame

Somewhatindependent,asTLBwillalwayspassPAtocacheregardlessofTLBhitormiss

7/30/2012

Summer2012--Lecture#24

35

DataFetchScenarios

Arethefollowingscenariosforasingledata

accesspossible?

TLBMiss,PageFault Yes

TLBHit,PageTableHit No

TLBMiss,CacheHit Yes

PageTableHit,CacheMiss Yes

PageFault,CacheHit No

7/30/2012

Summer2012--Lecture#24

36

Question:AprogramtriestoloadawordatXthatcausesaTLBmissbutnotapagefault.ArethefollowingstatementsTRUEorFALSE?

ThepagetabledoesnotcontainavalidmappingforthevirtualpagecorrespondingtotheaddressX

Thewordthattheprogramistryingtoloadispresentinphysicalmemory

37

1 2

F F

T F

F T

UpdatingScenarios

UsingV=valid,D=dirty,R=reftomeanthatfieldissettotheshownvalueforanyentryineitherPTorTLB

Whichofthefollowingscenariosforasingledataaccessarepossible?

Read,D=1 No

Write,R=1 Yes

Read,V=0 Yes

Write,D=0 No

7/30/2012 Summer2012--Lecture#24 38

Question:AssumethepagetableentryinquestionispresentintheTLBandweareusingauniprocessorsystem.ArethefollowingstatementsTRUEorFALSE?

ThevalidbitforthatpagemustbethesameinthePTandTLB

ThedirtybitforthatpagemustbethesameinthePTandTLB

39

1 2

F F

F T

T F

北京航空航天大學(xué)計算機學(xué)院

提綱

內(nèi)容主要取材：CS61C的24講

虛擬存儲器

頁表(PageTables)

TLB(TranslationLookasideBuffer)

VM性能

VM總結(jié)

VMPerformance

VirtualMemoryisthelevelofthememory

hierarchythatsitsbelowmainmemory

TLBcomesbeforecache,butaffectstransferofdatafromdisktomainmemory

Previouslyweassumedmainmemorywaslowestlevel,nowwejusthavetoaccountfordiskaccesses

SameCPI,AMATequationsapply,butnowtreatmainmemorylikeamid-levelcache

7/30/2012

Summer2012--Lecture#24

41

TypicalPerformanceStats

secondarymemory

primarymemory

Caching Demandpaging

cacheentry pageframe

cacheblock(≈32bytes) page(≈4Kibytes)

cachemissrate(1%to20%) pagemissrate(<0.001%)

cachehit(≈1cycle) pagehit(≈100cycles)cachemiss(≈100cycles) pagemiss(≈5Mcycles)

7/30/2012

Summer2012--Lecture#24

42

cache

CPU

CPU

primarymemory

ImpactofPagingonAMAT(1/2)

MemoryParameters:

L1cachehit=1clockcycles,hit95%ofaccesses

L2cachehit=10clockcycles,hit60%ofL1misses

DRAM=200clockcycles(≈100nanoseconds)

Disk=20,000,000clockcycles(≈10milliseconds)

AverageMemoryAccessTime(nopaging):

1+5%×10+5%×40%×200=5.5clockcycles

AverageMemoryAccessTime(withpaging):

5.5(AMATwithnopaging)+?

7/30/2012 Summer2012--Lecture#24 43

ImpactofPagingonAMAT(2/2)

AverageMemoryAccessTime(withpaging)=

5.5+5%×40%×(1-HRMem)×20,000,000

AMATifHRMem=99%?

5.5+0.02×0.01×20,000,000=4005.5(≈728xslower)

1in20,000memoryaccessesgoestodisk:10secprogramtakes2hours!

AMATifHRMem=99.9%?

5.5+0.02×0.001×20,000,000=405.5

AMATifHRMem=99.9999%

5.5+0.02×0.000001×20,000,000=5.9

7/30/2012

Summer2012--Lecture#24

44

ImpactofTLBsonPerformance

EachTLBmisstoPageTable~L1Cachemiss

TLBReach:AmountofvirtualaddressspacethatcanbesimultaneouslymappedbyTLB:

TLBtypicallyhas128entriesofpagesize4-8KiB

128×4KiB=512KiB=just0.5MiB

Whatcanyoudotohavebetterperformance?

Multi-levelTLBs Conceptuallysameasmulti-levelcaches

Variablepagesize(segments)

Specialsituationally-used“superpages”

Notcovered

here

7/30/2012 Summer2012--Lecture#24 45

北京航空航天大學(xué)計算機學(xué)院

提綱

內(nèi)容主要取材：CS61C的24講

虛擬存儲器

頁表(PageTables)

TLB(TranslationLookasideBuffer)

VM性能

VM總結(jié)

VirtualMemoryMotivation

Memoryascachefordisk(reducediskaccesses)

Diskissoslowitsignificantlyaffectsperformance

Pagingmaximizesmemoryusagewithlarge,evenly-sizedpagesthatcangoanywhere

Allowsprocessortorunmultipleprocessessimultaneously

Giveseachprocessillusionofitsown(large)VM

EachprocessusesstandardsetofVAs

Accessrightsprovideprotection

7/30/2012

Summer2012--Lecture#24

47

PagingSummary

Pagingrequiresaddresstranslation

Canrunprogramslargerthanmainmemory

Hidesvariablemachineconfigurations(RAM/HD)

Solvesfragmentationproblem

Addressmappingsstoredinpagetablesinmemory

AdditionalmemoryaccessmitigatedwithTLB

CheckTLB,thenPageTable(ifnecessary),then

Cache

7/30/2012

Summer2012--Lecture#24

48

Hardware/SoftwareSupportfor

MemoryProtection

Differenttaskscansharepartsoftheirvirtualaddressspaces

Butneedtoprotectagainsterrantaccess

RequiresOSassistance

HardwaresupportforOSprotection

Privilegedsupervisormode(a.k.a.kernelmode)

Privilegedinstructions

Pagetablesandotherstateinformationonlyaccessibleinsupervisormode

Systemcallexception(e.g.syscallinMIPS)

7/30/2012

Summer2012--Lecture#24

49

ContextSwitching

Howdoesasingleprocessorrunmany

programsatonce?

Con