Motivation 1 DRAM a Cache for Disk CS740 The full address space is quite large Virtual Memory October 2 2002 32 bit addresses 4 000 000 000 4 billion bytes 64 bit addresses 16 000 000 000 000 000 000 16 quintillion bytes Disk storage is 30X cheaper than DRAM storage 8 GB of DRAM 12 000 8 GB of disk 200 To access large amounts of data in a cost effective manner the bulk of the data must be stored on disk Topics Motivations for VM Address Translation Accelerating with TLBs Alpha 21X64 memory system 4 MB 400 SRAM 2 Page 1 256 MB 400 DRAM 20 GB 400 Disk CS 740 F 02 S 99 Levels in Memory Hierarchy cache CPU CPU regs regs Register size speed Mbyte block size 200 B 3 ns 8B 8B C a c h e 32 B Cache DRAM vs SRAM as a Cache DRAM vs disk is more extreme than SRAM vs DRAM virtual memory Memory Memory 8 KB Memory 32 KB 4MB128 MB 60 ns 6 ns 1 50 MB 100 MB 8 KB 32 B access latencies DRAM is 10X slower than SRAM disk is 100 000X slower than DRAM importance of exploiting spatial locality first byte is 100 000X slower than successive bytes on disk vs 4X improvement for page mode vs regular accesses to DRAM cache size main memory is 100X larger than an SRAM cache addressing for disk is based on sector address not memory address disk disk Disk Memory 20 GB 8 ms 0 05 MB SRAM larger slower cheaper 3 CS 740 F 02 S 99 4 Page 2 DRAM Disk CS 740 F 02 S 99 Impact of These Properties on Design Locating an Object in a Cache If DRAM was to be organized similar to an SRAM cache how would we set the following design parameters 1 Search for matching tag Line size Object Name X Associativity X D 243 1 X J 17 105 2 Use indirection to look up actual object location Write through or write back virtual memory Lookup Table Cache Location What would the impact of these choices be on miss rate hit time miss latency tag overhead 5 Data 0 N 1 Replacement policy if associative Cache Tag SRAM cache D 0 0 243 X J N 1 1 1 17 105 X CS 740 F 02 S 99 6 Page 3 Data Object Name N 1 CS 740 F 02 S 99 A System with Physical Memory Only A System with Virtual Memory Examples Examples most Cray machines early PCs nearly all embedded systems etc workstations servers modern PCs etc Memory Virtual Addresses 0 1 Store 0x10 Store 0x10 CPU Page Table 0 1 0 1 Physical Addresses CPU Load 0xf0 Load 0xf0 P 1 N 1 N 1 Disk Address Translation the hardware converts virtual addresses into physical addresses via an OS managed lookup table page table CPU s load or store addresses used directly to access memory 7 Memory CS 740 F 02 S 99 8 Page 4 CS 740 F 02 S 99 Servicing a Page Fault Page Faults Similar to Cache Misses What if an object is on disk rather than in memory Page table entry indicates that the virtual address is not in memory An OS trap handler is invoked moving data from disk into memory Memory current process suspends others can resume OS has full control over placement etc 0 1 Page Table Virtual Addresses CPU 0 1 1 Initiate Block Read Processor Signals Controller Read block of length P starting at disk address X and store starting at memory address Y Direct Memory Access Under control of I O controller 3 Read Done Cache Cache Memory I O Memory I Obus bus 2 DMA Transfer I O Controller Signals Completion P 1 Reg Read Occurs Physical Addresses Load 0x05 Store 0xf8 Processor Processor Interrupt processor Can resume suspended process N 1 Memory Memory I O I O controller controller disk Disk disk Dis k Disk 9 CS 740 F 02 S 99 10 Page 5 CS 740 F 02 S 99 Soln Separate Virtual Addr Spaces Motivation 2 Memory Management Virtual and physical address spaces divided into equal sized blocks Pages both virtual and physical Each process has its own virtual address space operating system controls how virtual pages as assigned to physical memory Multiple processes can reside in physical memory How do we resolve address conflicts Virtual Memory Image for Alpha Process 0000 03FF 8000 0000 Reserved Not yet allocated Dynamic Data gp Static Data Text Code 0000 0001 2000 0000 sp Virtual Addresses e g what if two different Alpha processes access their stacks at address 0x11fffff80 at the same time 0 Process 1 0 PP 2 N 1 Stack PP 7 Process 2 Not yet allocated 0000 0000 0001 0000 0 N 1 Reserved 11 VP 1 VP 2 Address Translation Physical Addresses CS 740 F 02 S 99 12 Page 6 VP 1 VP 2 Read only library code PP 10 M 1 CS 740 F 02 S 99 VM Address Translation Motivation 3 Protection V 0 1 N 1 virtual address space P 0 1 M 1 physical address space Page table entry contains access rights information hardware enforces this protection trap into OS if violation occurs Page Tables Memory Read Write Physical Addr Process i VP 0 Yes No VP 1 Yes Yes PP 4 VP 2 No No XXXXXXX PP 9 MAP V P U address mapping function MAP a 0 1 Process j 13 Yes PP 6 VP 1 Yes No PP 9 VP 2 No No XXXXXXX fault handler Processor Read Write Physical Addr Yes a if data at virtual address a is present at physical address a in P if data at virtual address a is not present in P missing item fault VP 0 N M a N 1 Addr Trans Mechanism a physical address CS 740 F 02 S 99 14 Page 7 Main Memory Secondary memory OS performs this transfer only if miss CS 740 F 02 S 99 Page Tables VM Address Translation Virtual Page Number Parameters P 2p page size bytes Typically 1KB 16KB N 2n Virtual address limit M 2m Physical address limit n 1 p p 1 virtual page number 0 1 1 0 1 1 1 0 1 0 1 virtual address page offset address translation m 1 p p 1 physical page number page offset 0 Page Table physical page Valid or disk address Physical Memory Disk Storage physical address Notice that the page offset bits don t change as a result of translation 15 CS 740 F 02 S 99 16 Page 8 CS 740 F 02 S 99 Address Translation via Page Table page table base register VPN acts as table index Page Table Operation Translation virtual address n 1 p p 1 virtual page number valid access Separate set of page table s per process VPN forms index into page table 0 page offset Computing Physical Address Page Table Entry PTE provides information about page if Valid bit 1 then page in memory Use physical page number …
View Full Document
Unlocking...