Understanding Paging in Operating Systems
Learn about paging in operating systems, virtual address spaces, base+limit registers, out-of-memory processing, and modern solutions like paging. Explore concepts such as virtual memory, process isolation, and handling large data footprints efficiently.
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
Paging David Ferry CSCI 3500 Operating Systems Saint Louis University St. Louis, MO 63103 1
Virtual Memory: Virtual Address Spaces Virtual Address Space Physical Memory (RAM) 0xFFFF .stack Programs see and use virtual memory addresses at the CPU Addresses must be translated between virtual and physical by hardware called the Memory Management Unit (MMU) Translation must be fast- doing everything in software would be too slow- need HW acceleration 0xFFFF Operating System .heap .data Kernel Space User Space .text 0x0 Program Virtual Address Space Program .stack 0xFFFF Library .heap .data Program 0x0 0x0 .text
Recall Base + Limit Registers In real mode the addresses generated by a program go directly to memory- the program sees physical addresses 0xFFFF Operating System Limit Program Base Limit With Base+Limit the addresses generated by a program are translated by adding the program base- the program sees virtual addresses Program Base Limit Program Base CSCI 3500 - Operating Systems 3
Recall Base + Limit Registers Pro: Load programs anywhere into memory Pro: Creates an address space abstraction Pro: Provides process isolation Con: Programs must be contiguous in memory Con: Creates allocation problem and fragmentation Con: Program must fit entirely in memory, or programmer must manage data transfer manually 0xFFFF Operating System Limit Program Base Limit Program Base Limit Program Base CSCI 3500 - Operating Systems 4
Out-of-Memory Processing Many programs have a total data footprint greater than the size of memory. Consider most consumer machines right now have 4-8GB of storage, but: A two-hour HD movie is 10-20GB Red-Dead Redemption 2 is 150GB Simulating a 54-qubit quantum computer is 144,000TB The programmer doesn t want to have to track this data manually unless they absolutely have to. Recall that the address space size is 2^32B = 4GB for 32-bit machines and 2^48B = 280TB for 64-bit machines CSCI 3500 - Operating Systems 5
Modern Solution: Paging Two improvements still to make: We only need to hold parts of our program in memory if they are needed Programs don t have to be contiguous in memory Paging Divide a program s virtual memory into pages Divide physical memory into page frames Memory Program 1 Program 2 D A A A B B B A C C C B D D CSCI 3500 - Operating Systems 6
Computing Address Translations Under Base+Limit the translation was simple- just add a program address to the base register. Paging is quite a bit more complex. Key parameters: Page size / page frame size Physical memory size Number of page frames Bits in a physical address Virtual memory size Number of pages per process Bits in a virtual address And of course we need to know the mapping CSCI 3500 - Operating Systems 7
Paging Example 1 Suppose we have 128KB of RAM and we have a 4KB page size. Q: How many page frames? A: 128KB/4KB = 32 page frames CSCI 3500 - Operating Systems 8
Paging Example 2 Suppose we have 128KB of RAM and we have a 4KB page size. Q: How many pages per process? A: Not enough information CSCI 3500 - Operating Systems 9
Paging Example 3 Suppose we have a 20-bit virtual address and we have a 4KB page size. Q: How many pages per process? A:20-bit address can index 220 bytes Note that 4KB = 212 Thus 220/212 = 28 = 256 pages CSCI 3500 - Operating Systems 10
Understanding Check Suppose we have 128KB of physical memory and 20-bit virtual addresses. Then we have a machine with 32 page frames and up to 256 pages per process. Can we have more pages in a process than there are page frames in the machine? Yes! The virtual memory size and physical memory size are in principle totally unrelated. CSCI 3500 - Operating Systems 11
Understanding Check Continued For example, in the late 2000 s it was very possible to have a 32-bit machine with 32-bit addresses and have 8GB of RAM 32-bit addresses => 4GB of virtual memory per process Implies something like 32-bit virtual addresses and 34-bit physical addresses If you re interested, see Physical Address Extension on Wikipedia for more details CSCI 3500 - Operating Systems 12
Understanding Check Continued 2 Modern 64-bit machines use 48-bit virtual addresses, which index 248 bytes or 256 terabytes of information However, most consumer machines with 64-bit hardware only have between 4GB and 16GB of RAM CSCI 3500 - Operating Systems 13
Paging Example 4 Given a page size of 4KB, what addresses belong to which pages? Each page contains 4096 bytes Page 0 contains bytes 0 Page 1 contains bytes 4096 - 8191 Page 2 contains bytes 8192 - 12,287 - 4095 Page N contains bytes 4096*N through (4096*(N+1)) - 1 CSCI 3500 - Operating Systems 14
Paging Translation Computation Suppose 4KB pages and page 1 is mapped into memory at page frame 5 Physical Address: 23,384 Virtual Address: Page Offset: 2904 7000 ADD SUB Page Start: 4096 Page Frame Start: 20,480 1. Compute page that contains address 2. Compute page start 3. Subtract page start from virtual address to get the page offset 4. Look up page frame from mapping 5. Compute the page frame start 6. Add page frame start to page offset to get the physical address
Paging Example 5 Suppose a machine has 4KB pages Q: If program generates a reference to virtual address 6000, which physical address is accessed? A: Not enough information- need to know the page mapping CSCI 3500 - Operating Systems 16
Paging Example 6 Suppose a machine has 4KB pages and a program has the following page mapping: Memory Program Q: What physical address does virtual address 6000 translate to? Frame 0 Page 0 Frame 1 Page 1 Frame 2 Page 2 Frame 3 Page 3 A: Address 6000 is in page 1, page offset is 1904, page frame is 3, page frame start is 12,288, so the physical address is (12,288 + 1904) = 14,192
Next Time: Page Tables and the TLB Today we calculated address translations explicitly using math but this would be very slow in a real system! Our translation needed two arithmetic operations and a lookup for every memory operation Binary representation of page mappings in page tables makes this translation easier A special hardware cache called the translation lookaside buffer (TLB) will accelerate page mapping lookups CSCI 3500 - Operating Systems 18
