2-OS Memory Addressing

1 .OS Memory Addressing

2 .Architecture CPU Processing units Caches Interrupt controllers MMU Memory Interconnect North bridge South bridge PCI, etc

3 .PC Architecture

4 .Address Spaces Translation from logical to physical addresses Process 1 Process 3 Process 2 OS 0 2 N Address space 1 0 2 N Address space 3 Address space 2 0 2 N 0 2 N Virtual/Logical Address spaces Physical Address space

5 .Hardware Support Two operating modes Privileged (protected, kernel) mode: OS context Result of OS invocation (system call, interrupt, exception) Allows execution of privileged instructions Allows access to all of memory (sort of) User Mode: Process context Only access resources (memory) in its context (address space) Segmentation (Logical addressing) Base register: Start location for address space Limit register: Size of segment making up address space

6 .Implementation Translation on every memory access in user process Compare logical address to limit register If logical address is greater, ERROR Physical Address = base register + logical address

7 .Managing Processes w/ Base and Limits Context Switch Add base and limit registers to process context Context Switch steps Change to privileged mode Save base and limit registers of old process Load base and limit registers of new process Change to user mode and jump to new process Protection Requirement User process can not change base and limit User process can not run in privileged mode What if base and limit registers don’t change during context switch?

8 .Pros and Cons of Segmentation Advantages Supports dynamic relocation of address spaces Supports protection across multiple address spaces Cheap: Few registers and little logic Fast: Add and Compare is easy Disadvantages Each process must be allocated contiguously in real memory Fragmentation: Cannot allocate a new process Must allocate memory that may not be used No Sharing: Cannot share limited memory regions

9 .Using Segments Divide address space into logical segments Each logical segment can be in separate part of physical memory Separate base and limit for each segment (+ protection bits) Read and write bits for each segment How to designate segment? Use part of logical address Top bits of logical address select segment Low bits of logical address select offset within segment Implicitly by type of memory reference Code vs. Data segments Special registers

10 .Segment Table Segment Table: Base and limit for every segment in process Translation: Indirection -> Table lookup before Add and Compare Segment Base Limit R/W 0 0x4000 0x06FF 1 0 1 0x0000 0x04FF 1 1 2 0x3000 0x0FFF 1 1 Logical Physical Seg 0 Seg 1 Seg 2 Where is: 0x0240 0x1108 0x265c 0x3002 0x0000 0x1000 0x2000 0x3000 0x2a00 0x3800 Caveat: Assume segments are selected via the logical address. NOT A REAL SYSTEM

11 .Pros and Cons of Segmentation Advantages Different protection for different segments E.g Code segment is read only Enables sharing of selected segments Easier to relocate segments than entire address space Enables sparse allocation of address space Disadvantages Still expensive/difficult to allocate contiguous memory to segments F ragmentation: Wasted memory Next approach: Paging Allocation is easier Reduces fragmentation

12 .Example Rep movs See Architecture Manual

13 .x 86 Segments CS = Code Segment DS = Data Segment SS = Stack Segment ES, FS, GS = Auxiliary segments Explicit or implicitly specified by instructions Accessed via special registers 16 bit “Selectors” Identify the segment to the hardware MMU Functionality depends on CPU operating mode

14 .Memory Map Early PC’s depended on BIOS for hardware interactions Standard library Implemented as Real Mode code (16 bit instructions) Hardwired directly into memory All x86 CPUs start execution at 0xffff0 Where is that? 1MB of available memory On a 16 bit architecture?

15 .Real Mode (16 bits) Segment registers act as base address 16 bits Segment size = 64K (2 16 ) Translation: Physical Addr = ( seg a ddr << 4) + logical addr x 86 i nit values: CS: 0xf000 IP: 0xfff0 Goal when in Real Mode: Get Out of Real Mode First thing OS does is transition to Protected (32 bit) mode

16 .32 bit Memory Map 32 bit addresses Up to 4GB (2 32 ) Top of memory used by hardware again “Who would ever need more than 3GB of memory?” BIOS is still there Why? Is it still useful?

17 .Protected Mode (32 bits) Segment information now stored as a table GDT (Global D escriptor Table) Where is the GDT? Array of segment descriptions (base, limit, flags) Segment registers now indicate array index Segment registers select segment descriptor CS points to Code Segment descriptor in GDT Still 16 bits How does Linux use segments? Check architecture manuals

18 .Linear address calculation

19 .Segment descriptors

20 .Segmentation Registers

21 .Paging Memory divided into fixed-sized pages Typical page size: 512-16k bytes Free Page Free Page Free Page Address space 1 Address space 2 Address space 3 Virtual Memory Physical Memory

22 .Page Translation How are virtual addresses translated to physical addresses Upper bits of address designate page number Page Number Page Offset Page Base Address Page Offset Page Table Virtual Address Physical Address 20 Bits 12 Bits 4K Pages No comparison or addition: Table lookup and bit substitution 1 page table per process: One entry per page in address space Base address of each page in physical memory Read/Write protection bits How many entries in page table?

23 .Page Table Example Mapping of virtual addresses to physical memory Free Page Free Page Free Page Address space 1 Physical Memory Page Table for process 1 Base Address Protection 1 1 0 4 1 1 6 1 1 10 1 1 0x0000 0x1000 0x2000 0x3000 4KB Pages

24 .Advantages of Paging Fast to allocate and free Alloc : Keep free list of pages and grab first page in list No searching by first-fit, best-fit Free: Add page to free list No inserting by address or size Easy to swap-out memory to disk Page size matches disk block size Can swap-out only necessary pages Easy to swap-in pages back from disk

25 .Disadvantages of Paging Additional memory reference -> Inefficient Page table too large to store as registers in MMU Page tables kept in main memory MMU stores only base address of page table Storage for page tables may be substantial Simple page table -> Require entry for all pages in address space Even if actual pages are not allocated Solution: Hierarchical page tables Increase granularity of page table entries Internal fragmentation: Page size does not match allocation size How much memory is wasted (on average) per process? Wasted memory grows with larger pages

26 .Paging with Large Address Spaces Mapping of logical addresses to physical memory Page table for process Free Page Free Page Physical Memory Base Address Protection 0 1 0 1 1 0 4 1 1 … skipped entries.. 0 0 6 1 1 10 1 1 How are entries skipped?

27 .Combine paging and segmentation Structure Segments correspond to logical units: code, data, stack Segments very in size and are often large Each segment contains one or more (fixed-size) pages But no longer needs to be contiguous Multiple ways to combine them: System 370: Each segment got own page tables Seg # (4 bits) Page # (8 bits) Page offset (12 bits) x 86: First calculate segment offset then do page table lookup logical address -> linear address -> physical address Why 12 Bits?

28 .Segments + Pages Advantages Advantages of Segments Supports large memory regions Single entry can cover all memory Translation is fast and cheap Advantages of Paging Memory does not have to exist (on demand) Can remap memory without copying Advantages of both Can use protection of segments without preallocating memory Other advantages?

29 .Protected Mode + Paging Segmentation -> Paging -> Physical address Every address in a page table points to a physical address Virtual addresses are only an INDEX into page tables Page size: 4KB Data and page table pages Page table page? 1024 entries per page table page 2 Level Page Tables Page tables set via CR3 ( What is this? ) Top Level: Entire 4GB of virtual address space 2 nd level: 4MB of virtual address space Large Pages Contiguous mappings of virtual addresses to physical addresses