Carnegie Mellon 1 Virtual(Memory:(Concepts(15#213:'Introduc0on'to'Computer'Systems ''15th'Lecture,'Oct.'14,'2010'Instructors:''Randy'Bryant'and'Dave'O’Hallaron'Carnegie Mellon 2 Today ( (( Address(spaces( VM(as(a(tool(for(caching( VM(as(a(tool(for(memory(management( VM(as(a(tool(for(memory(protec;on( Address(transla;on(Carnegie Mellon 3 A(System(Using(Physical(Addressing( Used(in(“simple”(systems(like(embedded(microcontrollers(in(devices(like(cars,(elevators,(and(digital(picture(frames(0:(1:(MG1:(Main(memory(CPU(2:(3:(4:(5:(6:(7:(Physical(address((PA)(Data(word(8:(...(4Carnegie Mellon 4 A(System(Using(Virtual(Addressing( Used(in(all(modern(servers,(desktops,(and(laptops( One(of(the(great(ideas(in(computer(science(0:(1:(MG1:(Main(memory(MMU(2:(3:(4:(5:(6:(7:(Physical(address((PA)(Data(word(8:(...(CPU(Virtual(address((VA)(CPU$Chip$4 4100Carnegie Mellon 5 Address(Spaces( Linear(address(space:(Ordered'set'of'con0guous'non#nega0ve'integer'addresses:'' '{0,'1,'2,'3'…'}' Virtual(address(space:(Set'of'N'='2n'virtual'addresses'' '{0,'1,'2,'3,'…,'N#1}' Physical(address(space:(Set'of'M'='2m'physical'addresses'' '{0,'1,'2,'3,'…,'M#1}' Clean(dis;nc;on(between(data((bytes)(and(their(aVributes((addresses)( Each(object(can(now(have(mul;ple(addresses( Every(byte(in(main(memory:((one(physical(address,(one((or(mor e)(virtual(addresses(Carnegie Mellon 6 Why(Virtual(Memory((VM)?( Uses(main(memory(efficiently( Use'DRAM'as'a'cache'for'the'parts'of'a'virtual'address'space' Simplifies(memory(manageme nt( Each'process'gets'the'same'uniform'linear'address'space' Isolates(address(spaces( One'process'can’t'interfere'with'another’s'memory '' User'program'cannot'access'privileged'kernel'informa0on'Carnegie Mellon 7 Today ( (( Address(spaces( VM(as(a(tool(for(caching( VM(as(a(tool(for(memory(management( VM(as(a(tool(for(memory(protec;on( Address(transla;on(Carnegie Mellon 8 VM(as(a(Tool(for(Caching( Virtual$memory(is(an(array(of(N(con;guous(bytes(stor e d(on(disk.(( The(contents(of(the(array(on(disk(are(cached(in(physical$memory((DRAM$cache)( These'cache'blocks'are'called'pages&(size'is'P'='2p'bytes)'PP(2mGpG1(Physical(memory(Empty(Empty(Uncached(VP(0(VP(1(VP(2nGpG1(Virtual(memory(Unallocated(Cached(Uncached(Unallocated(Cached(Uncached(PP(0(PP(1(Empty(Cached(0(NG1(MG1(0(Virtual(pages((VPs)((stored(on(disk(Physical(pages((PPs)((cached(in(DRAM(Carnegie Mellon 9 DRAM(Cache(Organiza;on( DRAM(cache(organiza;on(driven(by(the(enormous(miss(penalty( DRAM'is'about'10x'slower'than'SRAM' Disk'is'about'10,000x'slower'than'DRAM' Consequences( Large'page'(block)'size:'typically'4#8'KB,'some0mes'4'MB' Fully'associa0ve'' Any'VP'can'be'placed'in' any'PP' Requires'a'“large”'mappin g'fun c0on'–'d iff erent'from'CPU'caches' Highly'sophis0cated,'expensive'replacement'algorithms' Too'compli cated'and 'open# ended'to'b e'impl emented'in'h ardware' Write#back'rather'than'write#through'Carnegie Mellon 10 Page(Tables( A(page$table$is(an(array(of(page(table(entries((PTEs)(that(maps(virtual(pages(to(physical(pages.(( Per#process'kernel'data'structure'in'DRAM'null(null(Memory(resident(page(table((DRAM)(Physical(memory((DRAM)(VP(7(VP(4(Virtual(memory((disk)(Valid$0(1(0(1(0(1(0(1(Physical$page$number$or$$disk$address$PTE(0(PTE(7(PP(0(VP(2(VP(1(PP(3(VP(1(VP(2(VP(4(VP(6(VP(7(VP(3(Carnegie Mellon 11 Page(Hit( Page$hit:$reference(to(VM(word(that(is(in(physical(memory((DRAM(cache(hit)(null(null(Memory(resident(page(table((DRAM)(Physical(memory((DRAM)(VP(7(VP(4(Virtual(memory((disk)(Valid$0(1(0(1(0(1(0(1(Physical$page$number$or$$disk$address$PTE(0(PTE(7(PP(0(VP(2(VP(1(PP(3(VP(1(VP(2(VP(4(VP(6(VP(7(VP(3(Virtual(address(Carnegie Mellon 12 Page(Fault( Page$fault:$reference(to(VM(word(that(is(not(in(physical(memory((DRAM(cache(miss)(null(null(Memory(resident(page(table((DRAM)(Physical(memory((DRAM)(VP(7(VP(4(Virtual(memory((disk)(Valid$0(1(0(1(0(1(0(1(Physical$page$number$or$$disk$address$PTE(0(PTE(7(PP(0(VP(2(VP(1(PP(3(VP(1(VP(2(VP(4(VP(6(VP(7(VP(3(Virtual(address(Carnegie Mellon 13 Handling(Page(Fault( Page'miss'causes'page'fault'(an'excep0on)'null(null(Memory(resident(page(table((DRAM)(Physical(memory((DRAM)(VP(7(VP(4(Virtual(memory((disk)(Valid$0(1(0(1(0(1(0(1(Physical$page$number$or$$disk$address$PTE(0(PTE(7(PP(0(VP(2(VP(1(PP(3(VP(1(VP(2(VP(4(VP(6(VP(7(VP(3(Virtual(address(Carnegie Mellon 14 Handling(Page(Fault( Page'miss'causes'page'fault'(an'excep0on)' Page'fault'handler'selects'a'vic0m'to'be'evicted'(here'VP'4)'null(null(Memory(resident(page(table((DRAM)(Physical(memory((DRAM)(VP(7(VP(4(Virtual(memory((disk)(Valid$0(1(0(1(0(1(0(1(Physical$page$number$or$$disk$address$PTE(0(PTE(7(PP(0(VP(2(VP(1(PP(3(VP(1(VP(2(VP(4(VP(6(VP(7(VP(3(Virtual(address(Carnegie Mellon 15 Handling(Page(Fault( Page'miss'causes'page'fault'(an'excep0on)' Page'fault'handler'selects'a'vic0m'to'be'evicted'(here'VP'4)'null(null(Memory(resident(page(table((DRAM)(Physical(memory((DRAM)(VP(7(VP(3(Virtual(memory((disk)(Valid$0(1(1(0(0(1(0(1(Physical$page$number$or$$disk$address$PTE(0(PTE(7(PP(0(VP(2(VP(1(PP(3(VP(1(VP(2(VP(4(VP(6(VP(7(VP(3(Virtual(address(Carnegie Mellon 16 Handling(Page(Fault( Page'miss'causes'page'fault'(an'excep0on)' Page'fault'handler'selects'a'vic0m'to'be'evicted'(here'VP'4)' Offending'instruc0on'is'restarted:'page'hit!'null(null(Memory(resident(page(table((DRAM)(Physical(memory((DRAM)(VP(7(VP(3(Virtual(memory((disk)(Valid$0(1(1(0(0(1(0(1(Physical$page$number$or$$disk$address$PTE(0(PTE(7(PP(0(VP(2(VP(1(PP(3(VP(1(VP(2(VP(4(VP(6(VP(7(VP(3(Virtual(address(Carnegie Mellon 17 Locality(to(the(Rescue(Again!( Virtual(memory(works(because(of(locality( At(any(point(in(;me,(programs(tend(to(access(a(set(of(ac;ve(virtual(pages(called(the(working$set( Programs'with'beger'temporal'locality'will'have'smaller'working'sets' If((working(set(size(<(main(memory(size)(( Good'performance'for'one'process'aier'compulsory'misses' If(((SUM(working(set(sizes)(>(main(memory(size()(( Thrashing:&Performance'meltdown&where'pages'are'swapped'(copied)'in'and'out'con0nuously'Carnegie Mellon 18 Today ( (( Address(spaces( VM(as(a(tool(for(caching( VM(as(a(tool(for(memory(management(
View Full Document