Paging Memory Management (PDF)

Paging “Non–Contiguous Allocation” (cont.) Paged memory management (Paging): Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non – contiguous...

Paging “Non–Contiguous Allocation” (cont.) Paged memory management (Paging): Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non – contiguous The Physical Address Space is divided into a number of fixed-size blocks called frames The Logical Address Space is divided into fixed-size blocks called pages (Each process is divided into equal parts called pages) Page is a chunk of memory Main memory is also divided into equal parts and each part is called a frame Each page gets stored in one of the frames of the main memory whenever required => the size of a frame = the size of a page Each process has its own Page Table (PT) Page table can be stored in Storage, RAM, TLB (Translation Look-aside Buffer) or dedicated register (# of entries & # of pages) Operating System Concepts – 10th Edition 9.35 Silberschatz, Galvin and Gagne ©2018  Paging - Mapping of Virtual addresses to Physical addresses  The basic idea behind paging is to divide physical memory into a number of equal sized blocks called frames, and to divide a programs logical memory space into blocks of the same size called pages.  CPU can only see the logical address “virtual address ”  CPU issues a read to a logical address “virtual address ”. CPU first checks the address in Translation Lookaside Buffer (TLB). If it's a TLB miss, you have to go for a (page table walk). The page table entry gives the memory's physical address, which is fetched from the main memory. Now, if the page table says the page is marked invalid, then it generates a page fault “page fault handler exception” Operating System Concepts – 10th Edition 9.37 Silberschatz, Galvin and Gagne ©2018  Why TLB(Translation Look Aside Buffer)  Page table is stored in physical memory, and sometimes can be very large, so to speed up the translation of logical address to physical address , we sometimes use TLB, which is made of expensive and faster associative memory, So instead of going into page table first, we go into the TLB and use page number to index into the TLB, and get the corresponding page frame number and if it is found, we completely avoid page table( because we have both the page frame number and the page offset) and form the physical address  TLB Miss If we don't find the page frame number inside the TLB, it is called a TLB miss only then we go to the page table to look for the corresponding page frame number  TLB Hit If we find the page frame number in TLB, its called TLB hit, and we don't need to go to page table  Page Fault Occurs when the page accessed by a running program is not present in physical memory. It means the page is present in the secondary memory but not yet loaded into a frame of physical memory Operating System Concepts – 10th Edition 9.38 Silberschatz, Galvin and Gagne ©2018  Remember  Virtual memory is a memory management technique that provides an "abstraction" of the secondary storage to act as a very large main memory (RAM)  Physical memory, can be second storage, main memory or cache  Virtual address, (Logical Address), is the process Address Space  Physical Address, is the whole main memory Address Space  Cache Line, Cache lines or cache blocks are the unit of data transfer between main memory and cache. They have a fixed size which is typically 64 bytes on x86/x64 CPUs—this means accessing a single, uncached 4-byte integer entails loading another 60 adjacent bytes  Offset, contains bits that can represent each memory address in a page table  Demand Paging, is a method of virtual memory management. Operating System Concepts – 10th Edition 9.39 Silberschatz, Galvin and Gagne ©2018  Page Replacement  In modern computer systems, the operating system (OS) uses a technique called paging for virtual memory management (VMM) to store and retrieve data from a computer's secondary or virtual storage (hard drive, SSD, etc.) to the primary memory/main memory (RAM).  The OS divides any process into what is called pages.  Each process’s pages can be either stored as pages in secondary storage or as frames with non-contagious locations in the main memory => frames do not have to comprise a single physically contiguous region in the main memory. Operating System Concepts – 10th Edition 9.40 Silberschatz, Galvin and Gagne ©2018  Page Replacement (Cont.) Whenever a process refers to a page that is not present in the main memory, then page fault occurs, which causes the computer hardware to raise an interrupt or an exception. A page fault occurs due to various reasons:  Page being paged out or swapped out to disk “Secondary Storage” (to free the main memory/ make room for other pages in main memory). This is called swapping out  Page not being allocated yet (in the main memory). Retrieving data back to main memory is called swapping in Operating System Concepts – 10th Edition 9.41 Silberschatz, Galvin and Gagne ©2018  Page Replacement (Cont.)  Page replacement algorithm is an important part of virtual memory management. It helps the OS to decide which page can be moved out to leave a space for the currently needed page  With the help of page replacement algorithms, large virtual memory can be provided in smaller physical memory.  The ultimate objective of all types of page replacement algorithms is to minimize the number of page faults  The most common page replacement algorithms:  FIFO Page Replacement Algorithm  Optimal Page Replacement Algorithm  LRU Page Replacement Algorithm Operating System Concepts – 10th Edition 9.42 Silberschatz, Galvin and Gagne ©2018  Page Replacement (Cont.)  Prevent over-allocation of memory by modifying page-fault service routine to include page replacement  Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk  Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory Operating System Concepts – 10th Edition 9.43 Silberschatz, Galvin and Gagne ©2018  Basic Page Replacement 1. Find the location of the desired page on disk 2. Find a free frame: - If there is a free frame, use it - If there is no free frame, use a page replacement algorithm to select a victim frame - Write victim frame to disk if dirty 3. Bring the desired page into the (newly) free frame; update the page and frame tables 4. Continue the process by restarting the instruction that caused the trap Note now potentially 2 page transfers for page fault – increasing EAT Operating System Concepts – 10th Edition 9.45 Silberschatz, Galvin and Gagne ©2018