Virtual vs Real Address Spaces Memory Hierarchy and Cache Design 4 Virtual Address Space Mapping Real Address Space Virtual Memory vs Cache Virtual Memory the logical concept Page 1 1 Virtual Memory vs Cache Types of Virtual Memory Replacement Paged Cache controlled by hardware Virtual memory controlled by operating system HUGE miss penalty Fixed size blocks pages Size usually 4K 64Kbytes Segmented Size Variable size blocks Sizes vary Virtual memory size is determined by processor address size Cache size is independent of processor address size Combined usage of secondary memory Backing store of main memory File system Segmentation and Paging Mapping Base Value Segmentation Virtual Address Space Block Organize Virtual Address Space in variable size blocks Need information about the length of blocks also Addresses from one segment to the next may not be considered contiguous Virtual address Segment ID Offset in Segment Real Address Space Paging Organize Virtual Address Space in fixed size blocks Virtual Address Single Address R V Base Register Mapping requires one Base Value for each block Blocks may be of same size or varying size Page 2 2 Segmentation vs Paging Segmentation vs Paging External Fragmentation Internal Fragmentation process 1 segment 1 page 1 page 2 segment 2 page 3 process 2 page 4 segment 3 doesn t fit segment 5 page 5 page 6 segment 4 Page 3 3 Translating Virtual Addresses Block Segmentation Offset seg no Translation Table offset within segment P length start addr User s address Offset physical address Paging Address Translation Four Questions for Virtual Memory Block Placement Fully Associative Block Identification Fully Associative Block Replacement LRU or its variants Write Strategy Write back Write allocate Page 4 4 Block Placement Block Identification Fully Associative the obvious choice Huge miss penalty low miss rate is extremely important VM managed by software in OS much more flexible than cache managed by hardware Paging Logical to Physical Addresses VAX Memory Management 32 Bit addresses 4 GB Virtual Address Space 512 Bytes per page 2 23 pages Real Address Space is limited to 1GB 2 21 Page Frames Page 5 5 Address Translation Block Replacement Pure LRU is difficult if not impossible to implement The Clock Algorithm Maintain a circular list of pages in physical memory Use a use bit to track how recently a page is referenced Use bit set whenever a page is referenced On a page fault look for a page with use bit 0 in the clock order Replaces a page that hasn t been referenced for one complete revolution of the clock Write Strategy Fast Address Translation Write back the obvious choice Page tables are large and often paged Need fast mechanism for address translation USE TRANSLATION LOOK ASIDE BUFFERS TLB Associative memory Page 6 6 More Details on TLB TLB Page Table Cache Alpha AXP 21064 TLB TLB Page Size Segmentation and Paging Size of page table is inversely proportional to the page size Transferring larger pages to and from the secondary storage is more efficient than smaller pages As TLB sizes are restricted larger page sizes imply more address space can be translated Larger page sizes lead to higher internal fragmentation Larger pages lead to higher startup time for a process seg no segment table offset within the segment page table real address Page 7 7 Segmentation and Paging Segmentation 1 Block size Variable 2 Placement First fit et al 3 How found Size location 4 Replacement by programmer 5 Write action Write back Paging Fixed Fully associative Page table registers LRU Write back Fragmentation Programming Protection Internal Transparent Difficult External Visible RO RW EX Protection Have bounds register and check it for each access Have at least two modes Kernel and User Have CPU states that can be used by a user but not modified Base and Bound Registers Controlled change of mode System Call Example AXP 21064 Mapping of an Alpha Virtual Address 64 bit addresses kseg bits 63 and 62 10 Reserved for Operating system kernel Uses no memory management Uniform protection Seg0 Bit 63 0 seg 1 bits 63 and 62 11 User processes use Seg 0 and Seg1 Mapped to pages with individual protection Seg0 grows upwards and Seq 1 downwards Three level hierarchical page table Page 8 8 8KB pages Entries are 64 bit 8 bytes long 32 bit contain physical page frame number 5 protection Fields Valid User read enable Kernel read enable User write enable Kernel write enable Fields reserved for system software use One page contains 1024 PTEs Each Level is 10 bits long Leaves 21 bits to be defined For Seg0 all are 0 and for Seg1 all are 1 Address Spaces Alpha Page Table Influenced by page size E g Page Size 64 KB Virtual address 3 x 13 16 55 bits Physical address 32 16 or 48 bits Virtual addresses are 43 bits long and not 64 Physical address are 34 bits not 32 13 Requirement physical address virtual address Memory Hierarchy TLB Parameters Use two TLBs One for instructions and one for data OS can tell TLB to treat contiguous sequences of pages as one Block Size Hit Time Miss Penalty Avg TLB Size Block Selection Write Strategy Block Placement 1 PTE 8Bytes 1 clock cycle 20 cycles Instruction 8PTE for 8KB pages 4 PTE for 4 MB pages 96 bytes total Data 32 PTE for 8 KB 64 KB 512KB 4 MB 256 Bytes total Random but not last used Not Applicable Fully Associative Overall Picture AXP 21064 From Hennessey J L and D A Patterson Computer Architecture A Quantitative Approach Second Edition Copyright 1996 Morgan Kaufman Publishers San Francisco CA All rights reserved Page 9 9 Access Control VAX Memory Management Access Level No Access Read Only Access Read Write Access 32 Bit addresses 4 GB Virtual Address Space 512 Bytes per page 2 23 pages Real Address Space is limited to 1GB 2 21 Page Frames Access Mode Kernel Kernel functions of the OS Executive System Calls Supervisor Operating system services e g responses to user commands User Each page in memory is defined to have a particular access level for each access mode Address Translation VAX Address Space 0 User 31 2 System 32 2 Page 10 10 VAX Address Translation VAX TLB 2 Way Set Associative 64 entries per set Divided into 32 entries for system and 32 for process VAX TLB VAX Virtual Memory Scheme Page 11 11 Address Formats System 370 Memory Management Two level Segments Pages Page size 2KB or 4KB Segment Size 64KB or 1MB For 370 XA 4KB pages and 1M segments Structure INTEL 80386 Memory Management One segment table for each virtual address space One