windows
5.20
Steps in Handling a Page Fault
windows
5.21
Page Replacement 页面置换
在进程运行过程中，如果发生缺页，此时内存中又无空闲
块时，为了保证进程能正常运行，就必须从内存中调出一 页程序或数据送磁盘的对换区。但将哪个页面调出，则须 根据一定的页面置换算法来确定。 .
存储管理
本章内容
内存管理概述
Windows 2000/XP内存管理 Windows 2000/XP外存管理 Windows 2000/XP高速缓存管理
windows
5.2
内存管理概述技术
Swapping 交换技术
Contiguous Allocation 连续分配
windows
5.16
Two-Level Page-Table Scheme
windows
5.17
Address-Translation Scheme
Address-translation scheme for a two-level 32-bit paging
architecture （一个两级32位分页结构的地址转换机制）
Paging 分页
Segmentation 分段
Segmentation with Paging 段页式
Demand Paging 请求页式
windows 5.4
Background
存储器是计算机系统的
重要组成部分，虽然内 存容量在不断扩大，但 内存仍是宝贵资源，如 何提高主存储器利用率 ，并扩充大主存，对主 存信息实现有效保护是 存储器管理主要任务， 也是各种不同存储管理 方法的目标
虚拟存储的基本原理


windows
5.19
Demand Paging
在请求分页系统中的每个页表项如图所示：




状态位P（存在位）：用于指示该页是否已调入内存，供程序访问时 参考。 访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有 多长时间未被访问，提供给置换算法选择换出页面时参考。 修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一 页都在外存上保留一份副本，因此，若未被修改，在置换该页时就 不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数； 若已被修改，则必须将该页重写到外存上，以保证外存中所保留的 始终是最新副本。 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调 入该页时使用。
a page number consisting of 20 bits. a page offset consisting of 12 bits. Since the page table is paged, the page number is further divided into : a 10-bit page number. （一个10位的页号） a 10-bit page offset. （一个10位的偏移） Thus, a logical address is as follows :
功能：需要调入页面时，选择内存中哪个物理页面被置换
。称为replacement policy。
出发点：把未来不再使用的或短期内较少使用的页面调出
，通常只能在局部性原理指导下依据过去的统计数据进行 预测。
从理论上讲，应将那些以后不再被访问的页面换出，或把
那些在较长时间内不会再被访问的页面换出。
Internal fragmentation program， no external
fragmentation. associative memory or translation look-aside buffers (TLBs) 联想寄存器（快表）
windows 5.9
Address Translation Scheme（地址变换机制）
Hierarchical Paging
分级页表
Hashed Page Tables 哈希页表 Inverted Page Tables 反向(反置)页
表
windows
5.13
Hierarchical Page Tables
x86的逻辑地址空间有232Byte，如页面大小为4KB（
212Byte），则页表项达1M（220）个，每个页表项占 用4Byte，故每个进程的页表占用4MB内存空间，还 要求是连续的，显然这是不现实的。
行时可以在内存中移动，则地址绑定要延迟到运行时。需要硬件对地 址映射的支持MMU (例如基址和限长寄存器)
windows 5.7
Multistep Processing of a User Program
windows
5.8
Paging（分页）
Divide physical memory into fixed-sized blocks called
。）
31 Page number 12 11 page offset 0

p 地址结构
d
windows
5.10
Address Translation Architecture（地址变换机构）
windows
5.11
Paging Example
windows
5.12
Page Table Structure


page number p1 10
page offset
p2
10
d 12
where p1 is an index into the outer page table, and p2 is the displacement
within the page of the outer page table.
Address generated by CPU is divided into （ CPU产生的地址被分为） :

Page number (p) （页码） – used as an index into a page table which contains base address of each page in physical memory.（它包含每个页在物理内存中的基址，用来作为页表的索引） Page offset (d) （偏移）– combined with base address to define the physical memory address that is sent to the memory unit. （同基址相结合，用来确定送入内存单元的物理内存地址
分解逻辑地址空间到多个页表 一个简单的技术是两级页表
在x86中，为了减少页表所占用的连续的内存空间， 采用了两级页表机制。 Windows , Linux 。
windows
5.14
Two-Level Paging Example
A logical address (on 32-bit machine with 4K page size) is divided into :
frames (size is power of 2, between 512 bytes and 8192 bytes). （把物理内存分成大小固定的块，称为帧或 页框。） Divide logical memory into blocks of same size called pages. （把逻辑内存也分位固定大小的块，称为页。） Set up a page table to translate logical to physical addresses. （设置一个页表以便把逻辑地址转换为物理地 址。） 页表page table列出了进程的逻辑页与其在主存中的物理 帧间的对应关系
生成绝对代码；如果开始位置改变，需要重新编译代码
Load time （装入时期） : Must generate relocatable code if
memory location is not known at compile time.如果内存位置
在编译时不知道，则必须生成可重定位代码
Execution time （执行时期） : Binding delayed until run
windows
5.5
Background
Logical address逻辑地址（相对地址，虚地址）：用户的
程序经过汇编或编译后形成目标代码，目标代码通常采用 相对地址的形式。

其首地址为0，其余指令中的地址都相对于首地址来编址。 不能用逻辑地址在内存中读取信息。
Physical address物理地址（绝对地址，实地址）：内存
windows
5.22
Page Replacement Algorithms
First-In-First-Out Page Replacement (FIFO，先进先出页面置换算法
)
Optimal Page Replacement (OPT，最佳页面置换算法)：选择“未来
不再使用的”或“在离当前最远位置上出现的”页面被置换。 Least Recently Used Page Replacement (LRU，最近最久违用算法)： 选择内存中最久未使用的页面被置换。由于需要记录页面使用时间的 先后关系，硬件开销太大。 LRU Approximation Algorithms 近似LRU算法(NRU) Additional-Reference-Bits Algorithm附加引用位算法 Second-Chance Algorithm二次机会算法（clock算法） Enhanced Second-Chance Algorithm增强二次机会算法（改进 型的clock算法）