Virtual Memory and Paging in Operating Systems
Explore the concept of virtual memory, memory pages, and address translation in operating systems, along with the purpose and benefits they provide to processes. Learn how virtual memory gives processes the illusion of dedicated memory access and why memory pages play a crucial role in efficiently utilizing physical memory. Dive into the details of virtual address spaces and the translation process involved in accessing physical memory. Discover how the /proc//maps file showcases valid virtual addresses within a process.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Virtual Memory and Paging Brian Kocoloski, James Orr, Marion Sudvarg CSE 422S - Operating Systems Organization Washington University in St. Louis St. Louis, MO 63130 1
CSE 361 Review If you took CSE 361 (undergraduates must have), most of today s material will be review If you re a grad student some of it may be new, but hopefully most will be review as well As new material, we provide concrete examples of Linux virtual address spaces, copied from /proc/<pid>/maps files CSE 422S Operating Systems Organization 2
Virtual Memory What is the purpose of virtual memory? 1. Give processes illusion of full dedicated access to entire system memory Every process s virtual address space is unique and independent from all other processes Similar to how a process thinks it has dedicated access to processors 2. Preserve physical resources until they are actually needed Many programs don t need all of their code/data in memory at once (untaken branches, unused data, etc.) Allocating virtual memory != allocating physical memory 3. Unify the differences in physical memory devices behind a common abstraction Simplifies application programming Similar to how processes and threads exist on all different architectures despite core-level differences CSE 422S Operating Systems Organization 3
Memory Pages All physical memory is divided into pages Page sizes are determined by the architecture E.g. on both x86 and ARM, pages are 4KB in size Total amount of physical memory: X bytes Total number of pages: X/4KB Physical Address: 0x0 0x1000 0x2000 0x3000 4KB 4KB 4KB 4KB 4KB 4KB 4KB CSE 422S Operating Systems Organization 4
Memory Pages On all modern architectures, memory is accessed virtually via virtual addresses Virtual addresses require translation Virtual Address Translation: Process A Process B Virtual Address Virtual Memory 4KB 4KB 4KB 4KB 4KB 4KB 4KB 4KB Page# Offset Physical Memory Physical Page Phys. Addr 4KB 4KB 4KB 4KB 4KB 4KB 4KB 4KB 4KB 4KB + CSE 422S Operating Systems Organization 5
/proc/<pid>/maps The valid virtual addresses in a process $ cat /proc/self/maps Executable code Read-only static data Read/write static data CSE 422S Operating Systems Organization 6
/proc/<pid>/maps The valid virtual addresses in a process $ cat /proc/self/maps CSE 422S Operating Systems Organization 7
/proc/<pid>/maps The valid virtual addresses in a process heap: 0x00726000 0x00747000 0x21000 in length, or 132KB stack: 0x7e7f6000 0x7e817000 0x21000 in length, also 132KB CSE 422S Operating Systems Organization 8
Memory Allocation/Mapping In Linux, there are two primary system calls that perform memory allocation brk() expand the process heap mmap() similar to heap, but can have holes in the address space, and do other things like memory map files CSE 422S Operating Systems Organization 9
/proc/<pid>/maps The valid virtual addresses in a process $ cat /proc/self/maps Anonymous Memory (mmap) CSE 422S Operating Systems Organization 10
Paging malloc( ) 0x001b User space Virtual address (x = 0x001b ) # of bytes Allocate new virtual memory area (VA) Allocate physical memory pages (PA) Update page tables to map VA -> PA Kernel space Page Tables PA (y) VA (x) Hardware CSE 422S Operating Systems Organization 11
Paging write( Blah , 0x001b ); malloc( ) 0x001b User space Virtual address (x = 0x001b ) # of bytes Address 0x001b Allocate new virtual memory area (VA) Allocate physical memory pages (PA) Update page tables to map VA -> PA Kernel space Page Tables MMU Hardware CSE 422S Operating Systems Organization 12
Paging write( Blah , 0x001b ); malloc( ) 0x001b User space Virtual address # of bytes Address 0x001b Allocate new virtual memory area (VA) Allocate physical memory pages (PA) Update page tables to map VA -> PA Kernel space Page Tables Physical Memory Address 0x001b MMU Hardware CSE 422S Operating Systems Organization 13
Demand Paging malloc( ) 0x001b User space Virtual address # of bytes Allocate new virtual memory area (VA) DO NOT allocate physical memory DO NOT update page tables X Kernel space X Page Tables Hardware CSE 422S Operating Systems Organization 14
Demand Paging write( Blah , 0x001b ); malloc( ) 0x001b User space Virtual address # of bytes Allocate new virtual memory area (VA) DO NOT allocate physical memory DO NOT update page tables X Kernel space X Page Tables Tables Page Address 0x001b MMU Hardware CSE 422S Operating Systems Organization 15
Demand Paging write( Blah , 0x001b ); malloc( ) 0x001b User space Virtual address PAGE FAULT MMU cannot find VA (0x001b ...) in the page tables # of bytes Allocate new virtual memory area (VA) DO NOT allocate physical memory DO NOT update page tables X Kernel space X Page Tables Tables Page Address 0x001b MMU Hardware CSE 422S Operating Systems Organization 16
Demand Paging write( Blah , 0x001b ); User space Query list of vm_area_struct for the process If no VMA exists, invalid If VMA exists, but no write permission, invalid Else, OK Page fault handler Can user access VA 0x001b ? Kernel space Page Tables Tables Page Address 0x001b MMU Hardware CSE 422S Operating Systems Organization 17
Demand Paging write( Blah , 0x001b ); Segmentation fault User space (1) Allocate physical pages and map them in the page tables (2) Reissue instruction Page fault handler Can user access VA 0x001b ? No Kernel space Yes write( Blah , 0x001b ); Page Tables Tables Page Physical Memory Address 0x001b MMU Hardware CSE 422S Operating Systems Organization 18
Address Translation A virtual address is broken up into 2 pieces: p: page number d: page offset Virtual Address Translation: Virtual Address 64 bit virtual address space 4096 (4KB) byte page frame 12 bits to reference bytes within page frame (2^12 = 4096) Page# Offset Physical Page Phys. Addr + That leaves 52 bits for p CSE 422S Operating Systems Organization 19
Address Translation Q: With 52 bits for the page number, how many different page numbers can we address? Virtual Address Translation: Virtual Address In other words, how big must our translation table be? Page number (52 bits) Translation Table Physical Page CSE 422S Operating Systems Organization 20
Address Translation Q: With 52 bits for the page number, how many different page numbers can we address? Virtual Address Translation: Virtual Address A: 2^52 Page number (52 bits) Q: How to design a lookup table that can efficiently perform translations of up to 2^52 different virtual page numbers? Translation Table Physical Page Solution: multi-level page tables CSE 422S Operating Systems Organization 21
Multi-Level Paging Virtual Address Translation: Virtual Address Top level lookup directory Physical Page Second level lookup directory Third level lookup directory CSE 422S Operating Systems Organization 22
Multi-Level Paging Goal: We want each page table to fit into one page (4096 bytes) of memory Proposed scheme: Page Frame: 12 bits (2^12 = 4KB) Top level page number: 9 bits 2nd level page number: 9 bits 3rd level page number: 9 bits 4th level page number: 9 bits Unused: 16 bits Note: These page numbers are really offsets into other page tables! CSE 422S Operating Systems Organization 23
Sparse Hierarchy Saves Space Image from WUSTL CSE 361S SP2020 Lecture Notes CSE 422S Operating Systems Organization 24
Example Example 0x0000 cd00 2240 6c90 1010 1011 0000 0000 0010 0010 0100 0000 0110 1010 1001 0000 ( c d 0 0 2 2 4 0 6 c 9 0 ) Top level page number (9 bits) 1 0101 0110 : 342 2nd level page number (9 bits) 0 0000 0000 : 0 3rd level page number (9 bits) 1 0001 0010 : 274 4th level page number (9 bits) 0 0000 0110 : 6 Page offset (12 bits) 1010 1001 0000 : 2704 CSE 422S Operating Systems Organization 25
Example CPU instruction: WR R1, 0x0000 cd00 2240 6c90 Step 1: Get Top-level page table address Control Register (x86: CR3; ARM: CP15 c2) MMU WR 0x0000 cd00 2240 6c90 Top level page table address (a) CSE 422S Operating Systems Organization 26
Example 0x0000 cd00 2240 6c90 1010 1011 0000 0000 0010 0010 0100 0000 0110 1010 1001 0000 ( 342 0 274 6 2704 ) Index MetaData (r/w/x) (present) Page Address for next level of page table a 0 342 511 Present: 0 0 Hardware sees present bit set to 0: it CANNOT complete the VA -> PA translation So it raises an exception called a PAGE_FAULT CSE 422S Operating Systems Organization 27
Page Fault Handler Hardware tells the kernel that a process tried to access a virtual address that either Has not associated physical address in the page table Or, accessed the memory in an invalid fashion (i.e., tried to write to read-only memory) Kernel asks: (1) Is this a valid virtual address for the process to be accessing? i.e., if it s a read, is the memory readable? If write, writable? If execution, executable? (2) If not, raise SIGSEGV the dreaded Segmentation Fault (3) Else, update the page tables so the hardware knows how to complete the translation CSE 422S Operating Systems Organization 28
Example 0x0000 cd00 2240 6c90 1010 1011 0000 0000 0010 0010 0100 0000 0110 1010 1001 0000 ( 342 0 274 6 2704 ) a Index MetaData (r/w/x) (present) Page Address for next level of page table 0 342 511 Present: 0 0 Hardware sees present bit set to 0: it CANNOT complete the VA -> PA translation So it raises an exception called a PAGE_FAULT CSE 422S Operating Systems Organization 29
Example 0x0000 cd00 2240 6c90 1010 1011 0000 0000 0010 0010 0100 0000 0110 1010 1001 0000 ( 342 0 274 6 2704 ) a idx P Page Address Kernel Page fault handler Check if access is valid Allocate a new page, say p Determine physical address of, say b Store b in page address of page table Set present bit to 1 0 342 511 1 b Hardware sees present bit set to 0: it CANNOT complete the VA -> PA translation So it raises an exception called a PAGE_FAULT CSE 422S Operating Systems Organization 30
Example 0x0000 cd00 2240 6c90 1010 1011 0000 0000 0010 0010 0100 0000 0110 1010 1001 0000 ( 342 0 274 6 2704 ) a idx P Page Address b idx P Page Address 0 0 342 511 0 511 0 1 b Hardware sees present bit set to 0: it CANNOT complete the VA -> PA translation So it raises an exception called a PAGE_FAULT CSE 422S Operating Systems Organization 31
Example 0x0000 cd00 2240 6c90 1010 1011 0000 0000 0010 0010 0100 0000 0110 1010 1001 0000 ( 342 0 274 6 2704 ) a idx P Page Address b idx P Page Address c c 0 342 511 idx P Page Address 0 511 1 0 274 511 1 b 0 0 Hardware sees present bit set to 0: it CANNOT complete the VA -> PA translation So it raises an exception called a PAGE_FAULT CSE 422S Operating Systems Organization 32
Example 0x0000 cd00 2240 6c90 1010 1011 0000 0000 0010 0010 0100 0000 0110 1010 1001 0000 ( 342 0 274 6 2704 ) Index Page Grab the 2704 th byte in this page a 0 Physical Page (4KB) Index Page Index Page 342 b 0 c 0 511 Index Page 274 d 0 511 511 6 e 511 CSE 422S Operating Systems Organization 33
