Unit 4.2
Paging
Presenter Notes
Paging
Objectives
- Virtual Memory
- Paging
- Page request
Virtual Memory
- Comes from the basis that all of a process’ address space is not needed at once
- Thus, chop up the address space into smaller parts and only load the parts that are needed
- These parts need not be contiguous in memory!
Presenter Notes
虚拟内存（virtual memory）将用户逻辑内存和物理内存分开，在现有物理内存有限的情况下为程序员提供了巨大的虚拟内存空间，可以连续存放。
Paging
Presenter Notes
将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(page frame) 。程序加载时，分配其所需的所有页，这些页框不必连续，从而实现了离散分配。
Page request
- Relation beteen virtual addresses and physical memory addresses given by page table.
Presenter Notes
可以看出该方法的好处：没有外碎片、程序不必连续存放、便于改变程序占用空间的大小
VM Usage
Virtual memory is used in most modern operating systems:
- Windows uses one or more “page files” to swap pages
- Linux uses a hard disk partition (“swap partition”) to swap to.
Pros/Cons
- Since only the necessary parts of the process are loaded, processes load faster and it allows much better memory utilization
- Needs lots of extra hardware to accomplish the job (efficiently)
- In some cases too much paging (i.e. “thrashing”) can occur, which is very slow
Presenter Notes
虚拟内存的好处：读写内存的安全性、让每个进程有独立的地址空间、给分配和释放内存带来方便、如果同时运行着很多进程，为各进程分配的内存之和可能会大于实际可用的物理内存，虚拟内存管理使得这种情况下各进程仍然能够正常运行
Summary
- Virtual Memory
- Paging
- Page request
Page Table
Objectives
- Address relocation
- Page table entry
Address relocation
- The internal operation of the MMU with 16 4-KB pages.
Presenter Notes
分页方法通过CPU的硬件支持来实现逻辑地址和物理地址之间的映射。
Address translation
Translate Logical Address (LA) to Physical Address (PA)
- Step 1: Page size 2^n Byte => LA offset n bits
- Page size 4KB = 2^12 B => offset 12 bits
- Step 2: LA = page number + offset
- LA 32 bits , offset 12 bits => page number 20 bits
- Step 3: look up the page table , page number is the index, if the Present bit is 1, get the page frame number, else page fault.
- Step 4: PA = page frame number + offset
Structure of Page Table Entry
- A typical page table entry.
Presenter Notes
Summary
- Address relocation
- Page table entry
More about Page Table
Objectives
- Speeding Up Paging
- Multilevel Page Tables
- Inverted Page Tables
Speeding Up Paging
The mapping from virtual address to physical address must be fast.
A TLB (Translation Lookaside Buffers) to speed up paging.
Presenter Notes
内存管理单元通常借助一种叫做转译旁观缓冲器（Translation Lookaside Buffer，缩写为TLB）的相联高速缓存（associative cache）来将虚拟页号转换为物理页号。当后备缓冲器中没有转换记录时，则使用一种较慢的机制，其中包括专用硬件（hardware-specific）的数据结构（Data structure）或软件辅助手段。
Multilevel Page Tables
|
If the virtual address space is large, the page table will be large.
Multilevel Page Tables (a) A 32-bit address with two page table fields. (b) Two-level page tables. |
|
Presenter Notes
为减少页表的大小并容许忽略不需要的区域，计算机体系结构的涉及会将虚拟地址分成多个部分。同时虚拟地址空间的大部分们区域都没有使用，因而页没有关联到页帧，那么就可以使用功能相同但内存用量少的多的模型: 多级页表
Inverted Page Tables
- Comparison of a traditional page table with an inverted page table.
Presenter Notes
在64位操作系统中，因为有64位地址线，所以页表的大小可能非常非常大，虽然分级页表可以不必加载全部页表，IA-32,IA64系统一般使用四级页表来处理，而在PowerPC等体系中则使用倒排页表来解决这个问题。与传统页表的区别: 使用页框号而不是虚拟页号来索引页表项。
Summary
- Speeding Up Paging
- Multilevel Page Tables
- Inverted Page Tables
Reference
- Chapter 3: Memory management, Modern Operating Systems . Forth Edition, Andrew S. Tanenbaum