COMP2211 Operating Systems: Memory Management Lectures (PDF)

COMP2211 Operating Systems: Memory Management Mantas Mikaitis School of Computer Science, University of Leeds, Leeds, UK Semester 1, November 2024 Week 9, Lectures 15 a...

COMP2211 Operating Systems: Memory Management Mantas Mikaitis School of Computer Science, University of Leeds, Leeds, UK Semester 1, November 2024 Week 9, Lectures 15 and 16 M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 1 / 71 Progress Week Topic 1 Introduction to OS 2 OS services 3 Processes 4 Xv6: Live coding and Q&A from the xv6 book 5 Reading week. No scheduled labs or lectures 6 Threads and concurrency. 7 Scheduling 8 Process synchronisation 9 (current) Memory management 10 Catch up 11 Module review M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 2 / 71 Objectives Discuss why memory management is required in Operating Systems. Introduce paging. Introduce virtual memory. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 3 / 71 Reading List We will be mainly using the Operating System Concepts (OSC) 10th ed., 2018, and the 4th edition of the xv6 book (XV6), 2024. These slides are based on OSC (see the reference list). Week Reading materials 1 Chapter 1 OSC. Chapter 1 XV6. 2 Chapter 2 OSC. Chapter 2 XV6. 3 Chapter 3 OSC. 4 Reread Chapters 1–2 XV6. 5 Reread Chapters 1–3 OSC. 6 Chapter 4 OSC. 7 Chapter 5 OSC. 8 Chapters 6–8 OSC. 9 (current) Chapters 9–10 OSC. Chapter 3 XV6. 10 Reread Chapters 4–6 OSC. 11 Reread Chapters 9–10 OSC. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 4 / 71  Part I: Description of the Problem M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 5 / 71 Introduction Memory operations CPU can only access registers and main memory directly, with cache in between. Programs loaded from disk to memory, within process’ memory structure. CPU sends to the memory unit either address and read requests, or address, data, and write requests. Register access 1 clock cycle. Main memory: multiple cycles (LD/ST instructions). Causing a stall in CPU. Cache helps reduce stall times. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 6 / 71 Introduction M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 7 / 71 Memory protection Why we need memory protection Processes should only be able to access their addresses space. We do not want them to be able to impact each other (or the OS) directly. Each process memory is limited by the limit. Addresses have to lie between a limited range, starting at base address. Error if address > base+limit. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 8 / 71 Memory protection Base and limit registers These registers can be accessed only by privileged instructions in kernel mode. Only the OS can modify them, protecting users from modifying the size of the address space. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 9 / 71 Address binding Programs on disk have to be moved into memory eventually, for execution. We will place them in some location, not necessarily at address 0000. How to represent addresses before the decision of placement is made? Source programs contain symbolic addresses that the compiler bind to relocatable addresses, relative to some reference address that is set later. Linker or loader will bind these to absolute addresses. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 10 / 71 Address binding Address binding can happen at various stages of program lifetime: Compilation: if placement memory location is known, compiler can produce absolute addresses within the binary. Recompilation needed if location changes. Loading: take relocatable code from the compiler and transfer relative addresses to absolute addresses. Execution: if processes can move in memory during execution, then address binding has to be delayed until this time. This is a most common set-up in operating systems today. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 11 / 71 Address binding M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 12 / 71 Logical and physical address spaces Logical address (virtual address) Generated by the CPU. Physical address Address that the memory unit works with. Sets of addresses available: logical address space and physical address space. Compile-time and load-time binding results in equivalent logical and physical addresses. Execution-time binding makes processes think their address starts at 0000 and separate mapping is done to the physical address space. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 13 / 71 Memory-management unit Base register now called relocation register. Value of relocation register is added to every (virtual) address generated by user program. User program never sees actual physical addresses. Execution-time address binding done on memory accesses, by the MMU. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 14 / 71 Memory-management unit M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 15 / 71 Dynamic loading Load routines when needed Entire program does not need to be copied in memory. Load some parts of it only when they are called. Memory utilization is improved because routines that are not used are never loaded. All code kept in relocatable load format on disk. Rarely called large routines do not need to be in memory for the lifetime of the process. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 16 / 71 Dynamic linking Static linking System libraries and program code are combined into a binary executable. Dynamic linking postpones this until execution. Commonly used with system libraries: do not put them into the executable at all until called. Allows to share system libraries among process (Dynamically Linked Libraries - DLL, or shared libraries). Helps versioning: a new version of DLL can be updated in memory and all programs that reference it will dynamically link to the new version - no need to relink. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 17 / 71 Loading and linking M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 18 / 71  Part II: Contiguous Memory Allocation M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 19 / 71 Contiguous memory allocation Contiguous memory allocation OS and processes have to live in memory in order to all run concurrently, requiring efficient allocation of their memory areas. Contiguous allocation of the memory space is one way to implement this. Partition memory into two parts: 1 area for the operating system, and 2 area for processes, stored in single contiguous blocks. Need for memory protection Need to protect OS and processes, that are stored in the same memory space, from each other. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 20 / 71 Memory allocation Keep track of free and occupied partitions. At start, memory is one big free block. Allocate variable size partitions as required. Memory holes of variable size form. When a process exits, it leaves a memory hole that is merged with adjacent holes. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 21 / 71 Memory allocation Given an allocation request of N bytes, how to determine which memory hole to return? First-fit: allocate the first free memory area of size N or larger. Best-fit: Search the list of free memory areas and allocate the smallest that fits N bytes (best case scenario is we find a memory hole of N bytes). Worst-fit: Allocate the largest free memory area available of size at least N. Internal fragmentation Allocated memory is larger than N, the requested size. The extra bytes in the allocated block are unused. Arises when memory is split into fixed-sized partitions. External fragmentation N bytes exist to satisfy the request for memory, but the space is not contiguous. Memory is broken into many small pieces. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 22 / 71 Reducing external fragmentation Compaction Shuffle memory contents to merge all free memory holes into one contiguous space. Dynamic relocation is required for this to work, during execution. Require moving the program and data and updating the relocation register to reflect the change in the starting address. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 23 / 71 Vevox quiz M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 24 / 71  Part III: Paging M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 25 / 71 Motivation Why use paging memory management technique Previous techniques require memory to be contiguous, which introduces memory gaps and external fragmentation (requiring compaction). Paging allows processes to see contiguous memory space despite actual data stored in separate places in the physical memory. Paging A method that allows processes memory space to be fractured, but still look contiguous from process’ perspective. Paging is implemented in collaboration between OS and the hardware. It is in widespread use today. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 26 / 71 Basic method Divide physical memory space into fixed-size blocks, frames Divide virtual memory space into fixed-size blocks, pages Keep track of free frames When program requires N pages, N free frames have to be found Page tables map pages to frames (virtual addresses to physical addresses). Virtual addresses CPU generates addresses comprised of page number p and the page offset d. Entry p in the page table contains a base address of the corresponding frame in the physical memory. Then the offset d allows to find a specific memory address within the frame. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 27 / 71 Hardware support M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 28 / 71 Paging example M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 29 / 71 Example (4-bit logical address: 2-bit page number, 2-bit address offset) M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 30 / 71 Paging Key remarks about paging: No external fragmentation: any free frame can be allocated to a process. Internal fragmentation present: for example, page size is 4 bytes and process requests 10 bytes of memory; we will allocate 3 pages (12 bytes). Page sizes Today pages are typically 4 or 8 KB in size. Some systems support two page sizes which includes an option for huge pages. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 31 / 71 Frame allocation to pages The main steps: 1 Process requiring execution arrives in the system. 2 Size in terms of pages is determined: ⌈ size pagesize ⌉ (number of pages required). 3 Each page requires a frame in physical memory. 4 If a process requires N pages, N frames need to be available. 5 First page is loaded into an allocated frame. 6 Frame number is written to the page table. 7 Repeat two previous steps until all pages are copied into frames and the page table of the process is fully set up. Process can then start and use logical addresses. Programmer’s view of memory Paging allows programmer’s view of memory to be separated from the physical memory. Programmer sees a contiguous area of memory available for a particular program. The program in reality is scattered across physical memory, with frames sitting amongst frames of other programs. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 32 / 71 Frame allocation to pages (a: before allocation, b: after allocation) M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 33 / 71 Paging: implementation Each process has a page table stored in the main memory. Process Control Block of each process stores the address of the page table. When scheduler selects a process, it must set up the hardware page table by getting the copy from the memory. Simple hardware page table Set of high-speed registers. Translation of logical addresses fast. Context switch time increases because these registers have to be exchanged. PTRB register Most CPUs support large tables (for example, 220 entries)—register approach not feasible. Page table kept in memory and page table base register (PTBR) points to it. Context switch requires only one register swap. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 34 / 71 Translation look-aside buffers Page tables in memory When page tables are stored in memory, process data/instruction access requires two memory operations, one for the page tables and another for the actual data. Translation look-aside buffer (TLB) This technique is also called associative memory. Fast memory for storing commonly accessed frame addresses, typically 32 to 1024 entries. When CPU accesses memory, MMU first checks if page number is in the TLB and uses it if so. Otherwise (TLB miss) it gets the frame number from memory and updates the TLB. TLBs in practice Modern CPUs provide multi levels of TLBs. For example Intel Core i7 has 128-entry L1 instruction TLB and 64-entry data TLB. When TLB miss occurs, it checks in the 512-entry L2 TLB. In case of another TLB miss, page table in the main memory is looked at. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 35 / 71 Translation look-aside buffers M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 36 / 71 Memory protection with pages Page table can store read-only or write-only bits to mark restrictions in certain pages. valid bit indicates that the page is in the logical address space of the process. invalid indicates that it is out of bounds of the logical address space. Access to pages marked invalid will result in error. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 37 / 71 Protection with pages Page-table length register (PTLR) Instead of storing unused pages we may have a PTLR register that stores the size of the page table. This can be used for memory protection together with the PTBR. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 38 / 71 Shared pages Paging allows for efficient sharing of code between processes. Reentrant code means that the code of the library is not self-modifying. All processes can read it at the same time. For example, with shared pages, no need to have the copy of libc C standard library in each processes’ memory. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 39 / 71 Hierarchical paging Page tables in practice would be too large; they are split up in multiple layers to reduce size. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 40 / 71 Hierarchical paging address translation 64-bit architectures For 64-bit architectures even the two-level hierarchical page table requires too many entries. Other solutions are hashed page tables and inverted page tables—check OSC Chapter 9 for details. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 41 / 71  Part IV: Memory Swapping M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 42 / 71 Standard swapping Process instructions and data have to reside in memory for execution. When not executing, a process can be swapped out into disc and brought back into memory later. Why? When main memory is at its limit, to make space for something with higher priority. Swapping allows for the total memory to look larger than the available physical memory. If N processes are executing, but only N/2 can fit into memory, the users still see that all N are working even though half of them are swapped out into disc. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 43 / 71 Standard swapping M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 44 / 71 Swapping with paging M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 45 / 71 Swapping in mobile systems Most OS on PCs and high-performance computers support swapping with pages. On mobile systems typically this is not available. On mobile systems flash memory available instead of large hard drives. Space limitation and flash memory degradation due to writing operations make swapping not practical. Instead, iOS for example asks applications to release some memory. May forcibly terminate some processes when out of main memory. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 46 / 71 Vevox quiz M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 47 / 71  Part V: Virtual Memory M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 48 / 71 Virtual memory: introduction Memory management we discussed so far is stemming from a basic requirement: instructions should be in memory for execution. Downside: the size of the program limited to the size of physical memory. The entire program may not be needed; examples: code for error conditions; errors rarely occur, large arrays when not all elements are used, and generally, features of large programs that are rarely used. Store the program in memory only partially? Benefits: Program sizes not constrained by physical memory size, more programs can be ran concurrently, and less I/O needed when loading/swapping programs. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 49 / 71 Virtual memory: introduction Virtual memory Provide an extremely large memory space for the programmer’s view: logical space. This space is implemented by a combination of smaller physical memory space and large (but slow) disk space, by moving pages between the disk and the physical space as required. Programmer’s view Virtual memory allows the programmer not to worry about the physical space limitations and concentrate on solving the problem in the virtual space. The virtual space starts at a certain address and is contiguous. MMU maps this space to the noncontiguous physical space. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 50 / 71 Virtual memory: introduction M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 51 / 71 Virtual memory: introduction Commonly stack placed at the top addresses of logical space; grows down. Heap grows upwards. Hole in the middle - no physical memory used until pages are requested by, for example, malloc or dynamic linking. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 52 / 71 Virtual memory: introduction Each process thinks that the shared memory is in their virtual address space, but the logical addresses are mapped to the same shared pages in the physical memory. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 53 / 71 Demand paging: motivation When loading a process, should we bring all of its memory into the physical memory? A user may not need an entire large program. Instead, bring a page only when needed Similar to paging with swapping (diagram on the right). M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 54 / 71 Demand paging: basic concepts With demand pages, a process in execution will have pages both in memory and in the backing storage (disk). We need some way of distinguishing them. Valid-invalid bit marker can be used here. When a page is set to valid, OK. When invalid, it may be out of address space or it may not be in memory. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 55 / 71 Demand paging: basic concepts If a process makes access to a page that is in the backing store, page fault occurs. We need to bring in that page into memory and set its valid bit to 1. Restart the memory instruction that caused the error. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 56 / 71 Demand paging M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 57 / 71 Demand paging Extreme case: start process without any pages in memory. Let page faults occur and bring in only the required pages. Pure demand paging - never bring in a page until it is addressed. Demand paging main requirement The ability to restart the instruction after the page fault. If a page fault occurs on instruction fetch, we must refetch once the page has been loaded. If a page fault occurs when fetching an operand, we must fetch and decode the instruction again and then fetch the operand. Example Consider instruction ADD A B C which contains three memory locations. The steps are: 1) Fetch instruction, 2) Fetch A, 3) Fetch B, 4) Add A and B, 5) Store result in C. If page fault occurs when writing C, we will need to get the page in and restart the five steps. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 58 / 71 Demand paging On page faults, desired page has to be brought into memory. It needs a frame in memory to fit the page in. A list of free frames is usually maintained: free-frame list. Zero-fill-on-demand is used to zero-out the previous data. Free-frame list also is modified when the stack or heap segments of the process expand. On system start up, available memory is placed on free-frame list. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 59 / 71 Demand paging: steps to take on page fault 1 Trap to the operating system 2 Save the user registers and process state 3 Determine that the interrupt was a page fault 4 Check that the page reference was legal and find the page on the disk 5 Issue a read from the disk to a free frame: 1 Wait in a queue for this device until the read request is serviced 2 Wait for the device seek and/or latency time 3 Begin the transfer of the page to a free frame 6 While waiting, allocate the CPU to some other user 7 Receive an interrupt from the disk I/O subsystem (I/O completed) 8 Save the registers and process state for the other user 9 Determine that the interrupt was from the disk 10 Correct the page table and other tables to show page is now in memory 11 Wait for the CPU to be allocated to this process again 12 Restore the user registers, process state, and new page table, and then resume the interrupted instruction M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 60 / 71 Copy-on-write Remember that fork() creates a copy of the calling process. Traditionally all pages have to be copied and assigned to a new process. But usually forked processes run exec() immediately, loading a new executable. A technique called copy-on-write avoids copying all pages on fork(). Instead, pages will be shared until the child process tries to write to one of them. On write, a copy of the page will be made that is then written to by the child process. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 61 / 71 Copy-on-write M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 62 / 71 Copy-on-write M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 63 / 71  Part VI: Page Replacement M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 64 / 71 No free frames? What should OS do if there are no free frames to copy a certain page to? Terminate the process? Use standard swapping to copy some other process out into memory and free up pages: not used in modern OS because the whole process needs to be moved. Most OS now combine swapping pages (instead of whole processes) with page replacement. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 65 / 71 No free frames? M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 66 / 71 General page-replacement algorithm 1 Find required page on backing storage. 2 Get a free frame: 1 If there is one available, use it. 2 Apply page replacement algorithm to select victim frame. 3 Copy the victim frame to the backing storage. 4 Change page and frame tables to reflect the new state. 3 Move the original required page into the newly freed frame. Change page and frame tables. 4 Continue running the process. Costs Notice that there is performance penalty because two disk operations are required to move out one page and move in another page. Dirty bit is attached to each page to mark when it differs from its copy in the backing store—if dirty bit is not set, we don’t need to copy it. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 67 / 71 General page-replacement algorithm M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 68 / 71 Page-replacement algorithms Some common algorithms for picking the victim page: First-In-First-Out (FIFO): pick the oldest page in memory (arrived earliest). OPT: pick a page that will not be used for the longest period of time. Requires future knowledge. Not used in practice, but useful when comparing algorithms. Least recently used (LRU): look back in the past and pick a page that has not been used the longest. Page replacement FIFO is the cheapest algorithm, but has an anomaly—increasing number of frames increases page faults. In general, any improvements to demand paging will yield large benefits because copying data from backing store take relatively long. Usually lowest page fault frame is a good measure to judge the algorithm on. M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 69 / 71 Vevox quiz M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 70 / 71 COMP2211: Progress Week Topic 1 Introduction to OS 2 OS services 3 Processes 4 Xv6: Live coding and Q&A from the xv6 book 5 Reading week. No scheduled labs or lectures 6 Threads and concurrency. 7 Scheduling 8 Process synchronisation 9 Memory management 10 Catch up 11 Module review M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 71 / 71 References I A. Silberschatz, P. B. Galvin, and G. Gagne Operating System Concepts. 10th edition Wiley. 2018 A. Silberschatz, P. B. Galvin, and G. Gagne Operating System Concepts. 10th edition. Accompanying slides https://www.os-book.com/OS10/slide-dir/index.html 2020 R. Cox, F. Kaashoek, and R. Morris xv6: a simple, Unix-like teaching operating system https://pdos.csail.mit.edu/6.828/2024/xv6/book-riscv-rev4.pdf Version of August 31, 2024 M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 1/2 References II R. H. Arpaci-Dusseau and A. C. Arpaci-Dusseau Operating Systems: Three Easy Pieces. Version 1.0 https://pages.cs.wisc.edu/~remzi/OSTEP/ Arpaci-Dusseau Books. Aug., 2018 M. Mikaitis (Leeds) COMP2211 Operating Systems November 2024 2/2