Virtual Memory 2!Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)P)&)H)Chapter)5.4;5)2)Announcements!PA3)available.))Due)Tuesday,)April)19th)• Work)with)pairs)• Be)responsible)with)new)knowledge)• Scheduling)a)games)night,)possibly)Friday,)April)22nd))))Next)five)weeks)• One)homeworks)and)two)projects)• Prelim2)will)be)Thursday,)April)28th))• PA4)will)be)final)project)(no)final)exam)))3)Goals for Today!Virtual)Memory)• Address)TranslaVon)• Pages,)page)tables,)and)memory)mgmt)unit)• Paging)• Role)of)OperaVng)System)• Context)switches,)working)set,)shared)memory)• Performance ))• How)slow)is)it)• Making)virtual)memory)fast)• TranslaVon)lookaside)buffer)(TLB))• Virtual)Memory)Meets)Caching))))4)Address)TranslaVon)Pages,)Page)Tables,)and))the)Memory)Management)Unit)(MMU))5)Address Translation!A[empt)#1:)How)does)MMU)translate)addresses?)))paddr)=)PageTable[vaddr];)Granularity?)• Per)word…)• Per)block…)• Variable..…)Typical:)• 4KB)–)16KB)pages)• 4MB)–)256MB)jumbo)pages))6)Address Translation!A[empt)#1:)For)any)access)to)virtual)address:)• Calculate)virtual)page)number)and)page)offset)• Lookup)physical)page)number)at)PageTable[vpn])• Calculate)physical)address)as)ppn:offset)vaddr)Page)Offset)Virtual)page)number)Page)offset)Physical)page)number)Lookup)in)PageTable)paddr)7)Simple PageTable!Q:)Where)to)store)page)tables?)A:)In)memory,)of)course…)Special)page%table%base%register)(CR3:PTBR)on)x86))(Cop0:ContextRegister)on)MIPS)%CPU) MMU)Data)Read)Mem[0x00201538])0x00000000)0x90000000)0x10045000)0x4123B000)0xC20A3000)8)Summary!vpn) pgoff)Physical)Page)Number)0x10045))0xC20A3)0x4123B)0x00000)0x20340)vaddr)PTBR)9)Page Size Example!Overhead)for)VM)A[empt)#1)(example))Virtual)address)space)(for)each)process):)• total)memory:)232)bytes)=)4GB)• page)size:)212)bytes)=)4KB)• entries)in)PageTable?)• size)of)PageTable?)Physical)address)space:)• total)memory:)229)bytes)=)512MB)• overhead)for)10)processes?))10)Invalid Pages!Cool)Trick)#1:)Don’t)map)all)pages))Need)valid)bit)for)each))page)table)entry)Q:)Why?)V)Physical)Page)Number)0)1) 0x10045)0)0)1) )0xC20A3)1) 0x4123B)1) 0x00000)0)0x00000000)0x90000000)0x10045000)0x4123B000)0xC20A3000)11)Beyond Flat Page Tables!Assume)most)of)PageTable)is)empty)How)to)translate)addresses?))10)bits)PTBR)10)bits) 10)bits)vaddr)PDEntry)Page)Directory)Page)Table)PTEntry)Page)Word)2)MulV;level)PageTable)*)x86)does)exactly)this)12)Page Permissions!Cool)Trick)#2:)Page)permissions!)Keep)R,)W,)X)permission)bits)for))each)page)table)entry)Q:)Why?)V) R)W)X)Physical)Page)Number)0)1) 0x10045)0)0)1) )0xC20A3)1) 0x4123B)1) 0x00000)0)0x00000000)0x90000000)0x10045000)0x4123B000)0xC20A3000)13)Aliasing!Cool)Trick)#3:)Aliasing)Map)the)same)physical)page)at)several)virtual)addresses)Q:)Why?)V) R)W)X)Physical)Page)Number)0)1) 0xC20A3)0)0)1) )0xC20A3)1) 0x4123B)1) 0x00000)0)0x00000000)0x90000000)0x10045000)0x4123B000)0xC20A3000)14)Paging)15)Paging!Can)we)run)process)larger)than)physical)memory?)• The)“virtual”)in)“virtual)memory”%View)memory)as)a)“cache”)for)secondary)storage)• Swap)memory)pages)out)to)disk)when)not)in)use)• Page)them)back)in)when)needed))Assumes)Temporal/SpaVal)Locality)• Pages)used)recently)most)likely)to)be)used)again)soon))16)Paging!Cool)Trick)#4:)Paging/Swapping)Need)more)bits:)Dirty,)RecentlyUsed,)…)V) R)W)X) D)Physical)Page)Number)0) invalid)1) 0) 0x10045)0) invalid)0) invalid)0) 0) )disk)sector)200)0) 0) disk)sector)25)1) 1) 0x00000)0) invalid)0x00000000)0x90000000)0x10045000)0x4123B000)0xC20A3000)25)200)17)Role)of)the)OperaVng)System)Context)switches,)working)set,))shared)memory)18)sbrk!Suppose)Firefox)needs)a)new)page)of)memory)(1))Invoke)the)OperaVng)System)!void!*sbrk(int!nbytes);!(2))OS)finds)a)free)page)of)physical)memory)• clear)the)page)(fill)with)zeros))• add)a)new)entry)to)Firefox’s)PageTable)19)Context Switch!Suppose)Firefox)is)idle,)but)Skype)wants)to)run)(1))Firefox)invokes)the)OperaVng)System)!int!sleep(int!nseconds);!(2))OS)saves)Firefox’s)registers,)load)skype’s)• (more)on)this)later))(3))OS)changes)the)CPU’s)Page)Table)Base)Register)• Cop0:ContextRegister)/)CR3:PDBR)(4))OS)returns)to)Skype))20)Shared Memory!Suppose)Firefox)and)Skype)want)to)share)data)(1))OS)finds)a)free)page)of)physical)memory)• clear)the)page)(fill)with)zeros))• add)a)new)entry)to)Firefox’s)PageTable)• add)a)new)entry)to)Skype’s)PageTable)– can)be)same)or)different)vaddr)– can)be)same)or)different)page)permissions))21)Multiplexing!Suppose)Skype)needs)a)new)page)of)memory,)but)Firefox)is)hogging)it)all)(1))Invoke)the)OperaVng)System)!void!*sbrk(int!nbytes);!(2))OS)can’t)find)a)free)page)of)physical)memory)• Pick)a)page)from)Firefox)instead)(or)other)process))(3))If)page)table)entry)has)dirty)bit)set…)• Copy)the)page)contents)to)disk)(4))Mark)Firefox’s)page)table)entry)as)“on)disk”)• Firefox)will)fault)if)it)tries)to)access)the)page)(5)))Give)the)newly)freed)physical)page)to)Skype)• clear)the)page)(fill)with)zeros))• add)a)new)entry)to)Skyps’s)PageTable)22)Paging Assumption 1!OS)mulVplexes)physical)memory)among)processes)• assumpVon)#)1:))processes)use)only)a)few)pages)at)a)Vme)• working)set)=)set)of)process’s)recently)acVvely)pages)#)recent)accesses)0x00000000) 0x90000000)23)Reasons for Thrashing!Q:)What)if)working)set)is)too)large?)Case)1:)Single)process)using)too)many)pages)))Case)2:)Too)many)processes)working)set)mem) disk)swapped)P1)working)set)mem) disk)swapped)ws)mem) disk)ws) ws) ws) ws) ws)24)Thrashing!Thrashing)b/c)working)set)of)process)(or)processes))greater)than)physical)memory)available)– Firefox)steals)page)from)Skype)– Skype)steals)page)from)Firefox)• I/O)(disk)acVvity))at)100%)uVlizaVon)– But)no)useful)work)is)gevng)done)Ideal:)Size)of)disk,)speed)of)memory)(or)cache))Non;ideal:)Speed)of)disk)25)Paging Assumption 2!OS)mulVplexes)physical)memory)among)processes)• assumpVon)#)2:))recent)accesses)predict)future)accesses)• working)set)usually)changes)slowly)over)Vme)working)set)Vme)→)26)More Thrashing!Q:)What)if)working)set)changes)rapidly)or)unpredictably?))))))A:)Thrashing)b/c)recent)accesses)don’t)predict)future)accesses)working)set)Vme)→)27)Preventing
View Full Document