CSC 414 Notes, Spring 2007

CSC 414 Final Chapter 10 Memory Management - The memory management portion of the Operating System is responsible for the efficient usage of main memory, especially in a multiprogramming environment where processes contend for memory. - It must also offer protection of one process address space from another (including protection of system address space from user processes). - The memory subsystem should also provide programmers with a convenient logical or virtual address space, in which the low-level details of memory management are hidden. Sharing of Memory Issues  Allocation schemes  Protection from each other  Protecting OS code  Translating logical addresses to physical  Swapping programs  What if physical memory is small: Virtual memory Memory Management Strategies 1 Fetch Strategy: Determine when to load and how much to load at a time. E.g., demand fetching, anticipated fetching (pre-fetching). 2 Placement (or allocation) Strategy: Determine where information is to be placed. E.g., Best-Fit, First-Fit, Buddy-System. 3 Replacement Strategy: Determine which memory area is to be removed under contention conditions. E.g., LRU, FIFO. Memory Management Evolution - Variations 1 Fixed Partitions 1 Variable Partitions 1 Segmentation Page 1 of 12 Prog ram 2 O S Program 3 Free space Program 1 CSC 414 Final 1 Paging - Criteria 1 How efficiently can it be implemented? 1 How effectively can the physical memory be utilized? Fixed Partitions 1 Divide all physical memory into a fixed set of contiguous partitions. E.g., early IBM 360 models. 1 +---------+ | 12K | Queue for waiting processes +---------+ | 2K | .... +---------+ | 6K | .... +---------+ | OS: 2K | +---------+ 2 Place only one process at a time in any partition. 3 Bind physical to virtual address during loading, not during execution. 4 Partition boundaries limit the available memory for each process. 5 A process is either entirely in main memory or entirely on backing store (i.e., swapped in or swapped out). 6 A process may only be swapped into the same partition from which it was swapped out (why?) 7 It can only simulate smaller, not larger, virtual space than physical space. 8 No sharing between processes. 9 Should there be a single queue per partition or one global queue? 10 Memory space wasted:  Internal fragmentation: memory which is internal to a partition, but not used.  External fragmentation: a partition is unused and available, but too small for any waiting job. Page 2 of 12 CSC 414 Final Managing Free Space: Linked Lists - Each record has  Process ID/ Free (H: hole)  Start location  Size  Pointer to Next record  - Current state (H,2,3),(B,5,5),(H,10,2),(D,12,2),(H,14,6) - How should we update the list when B leaves? Managing Free Space: Linked Lists - Current state (H,2,3),(B,5,5),(H,10,2),(D,12,2),(H,14,6) - PCB for a process can have a pointer into the corresponding record - When a process terminates, neighboring blocks need to be examined  Doubly-linked lists Allocation Strategy - Suppose a new process requests 15K, which hole should it use? - First-fit: 30K hole - Best-fit: 20K hole - Worst-fit: 60K hole - Let {Hi | i = 1,…,n} be unused blocks and k be the size of a requested block. - First-Fit  Select the first Hi such that size (Hi) ³ k.  That is, select the first block that is big enough - Best-Fit  Select Hi such that size (Hi) ³ k and, if size (Hj) ³ k then size (Hj) ³ size (Hi) for i ¹ j.  That is, select the smallest block that is big enough. - Worst-Fit  Select Hi such that size (Hi) ³ k, and if size(Hj) ³ k then size(Hj) ³ size(Hi) for i ¹ j. (idea: to produce the largest left-over block.) - Buddy System Best-fit vs. First-fit - Both could leave many small and useless holes. Page 3 of 12 Free: 30K O S: 20K Free: 20K B: 50K Free: 60K D: 20K CSC 414 Final - To shorten search time for First-Fit, start the next search at the next hole following the previously selected hole. - Best-Fit performs better: Assume holes of 20K and 15K, requests for 12K followed by 16K can be satisfied only by best-fit - First-Fit performs better: Assume holes of 20K and 15K, requests for 12K, followed by 14K, and 7K, can be satisfied only by first-fit - In practice, F-F is usually better than B-F, and F-F and B-F are better than W-F. -Allocation algorithm that forms basis of Linux memory management - Suppose we have 128 units (128 pages or 128K) - Each request is rounded up to powers of 2 - Initially a single hole of size 128 - Suppose, A needs 6 units, request rounded up to 8 - Smallest hole available: 128. Successively halved till hole of size 8 is created - At this point, holes of sizes 8, 16, 32, 64 - Next request by B for 5 units: hole of size 8 allocated -Next request by C for 24 units: hole of size 32 allocated Chapter 11 Lecture Note: Virtual Memory - Recall: memory allocation with variable partitions requires mapping logical addresses to physical addresses - Virtual memory achieves a complete separation of logical and physical address-spaces Page 4 of 12 64H 32C 16H 8A 8B 64H 32C 8A 8B 8H 4 H4 D D requests 3 64H 32C 16H 8H 4 H4 D B exits 64H 32C 8H 8B 8H 4 H4 D A exits CSC 414 Final Today, typically a virtual address is 32 bits, this allows a process to have 4GB of virtual memory  Physical memory is much smaller than this, and varies from machine to machine  Virtual address spaces of different processes are distinct - Structuring of virtual memory  Paging: Divide the address space into fixed-size pages  Segmentation: Divide the address space into variable-size segments (corresponding to logical units) Paging (1) The position and function of the MMU Virtual Memory (Paging) - Physical memory is divided into chunks called page-frames (on Pentium, each page- frame is 4KB) - Virtual memory is divided into chunks called pages; size of a page is equal to size of a page frame  So typically, 220 pages (a little over a million) in virtual memory - OS keeps track of mapping of pages to page-frames - Some calculations:  10-bit address : 1KB of memory; 1024 addresses  20-bit address : 1MB of memory; about a million addresses Page 5 of 12 CSC 414 Final  30-bit address : 1 GB of memory; about a billion addresses Virtual Memory in Unix Page 6 of 12 The relation between virtual Addresses and physical memory addresses given by page table. CSC 414 Final Paging - A virtual address is considered as a pair (p,o)  Low-order bits give an offset o within the page  High-order bits specify the page p - E.g. If each page is 1KB and virtual address is 16 bits, then low-order 10 bits give the offset and high-order 6 bits give the page number - The job of the Memory Management Unit (MMU) is to translate the page number p to a frame number f  The physical address is then (f,o), and this is what goes on the memory bus - For every process, there is a page-table (basically, an array), and page-number p is used as an index into this array for the translation Page Table Entry - Validity bit: Set to 0 if the corresponding page is not in memory - Frame number  Number of bits required depends on size of physical memory - Protection bits:  Read, write, execute accesses - Referenced bit is set to 1 by hardware when the page is accessed: used by page replacement policy - Modified bit (dirty bit) set to 1 by hardware on write-access: used to avoid writing when swapped out Page Tables (1) Page 7 of 12 CSC 414 Final Internal operation of MMU with 16 4 KB pages Design Issues - What is the “optimal” size of a page frame ?  Typically 1KB – 4KB, but more on this later - How to save space required to store the page table  With 20-bit page address, there are over a million pages, so the page-table is an array with over million entries  Solns: Two-level page tables, TLBs (Translation Lookaside Beffers), Inverted page tables - What if the desired page is not currently in memory?  This is called a page fault, and it traps to kernel  Page daemon runs periodically to ensure that there is enough free memory so that a page can be loaded from disk upon a page fault - Page replacement policy: how to free memory? Multi-Level Paging Page 8 of 12 CSC 414 Final - Keeping a page-table with 220 entries in memory is not viable - Solution: Make the page table hierarchical  Pentium supports two-level paging - Suppose first 10-bits index into a top-level page-entry table T1 (1024 or 1K entries) - Each entry in T1 points to another, second-level, page table with 1K entries (4 MB of memory since each page is 4KB) - Next 10-bits of physical address index into the second-level page-table selected by the first 10-bits - Total of 1K potential second-level tables, but many are likely to be unused - If a process uses 16 MB virtual memory then it will have only 4 entries in top-level table (rest will be marked unused) and only 4 second-level tables Paging in Linux Linux uses three-level page tables Translation Lookaside Buffer (TLB) - Page-tables are in main memory - Access to main memory is slow compared to clock cycle on CPU (10ns vs 1 ns) - An instruction such as MOVE REG, ADDR has to decode ADDR and thus go through page tables - This is way too slow !! Page 9 of 12 CSC 414 Final - Standard practice: Use TLB stored on CPU to map pages to page-frames - TLB stores small number (say, 64) of page-table entries to avoid the usual page-table lookup - TLB is associative memory and contains, basically, pairs of the form (page-no, page- frame) - Special hardware compares incoming page-no in parallel with all entries in TLB to retrieve page-frame - If no match found in TLB, standard look-up invoked More on TLB - Key design issue: how to improve hit rate for TLB?  Which pages should be in TLB: most recently accessed - Who should update TLB?  Modern architectures provide sophisticated hardware support to do this  Alternative: TLB miss generates a fault and invokes OS, which then decides how to use the TLB entries effectively. Inverted Page Tables - When virtual memory is much larger than physical memory, overhead of storing page- table is high - For example, in 64-bit machine with 4KB per page and 256 MB memory, there are 64K page-frames but 252 pages ! - Solution: Inverted page tables that store entries of the form (page-frame, process-id, page-no) - At most 64K entries required! Page 10 of 12 Page number Frame number Modified bit Protection bits CSC 414 Final - Given a page p of process x, how to find the corresponding page frame? - Linear search is too slow, so use hashing - Note: issues like hash-collisions must be handled - Used in some IBM and HP workstations; will be used more with 64-bit machines Hashed Page Tables Steps in Paging - Today’s typical systems use TLBs and multi-level paging - Paging requires special hardware support - Overview of steps  Input to MMU: virtual address = (page p, offset o)  Check if there is a frame f with (p,f) in TLB  If so, physical address is (f,o)  If not, lookup page-table in main memory ( a couple of accesses due to multi-level paging)  If page is present, compute physical address  If not, trap to kernel to process page-fault Page 11 of 12 Page number Offset Hash Page # Frame # Hash table Number of entries: Number of page frames PID PID CSC 414 Final  Update TLB/page-table entries (e.g. Modified bit) Page 12 of 12