【操作系统】虚拟存储器

比眉伴天荒 2023-01-10 14:41 245阅读 0赞

> 写在前面  
> 资料来源于我的操作系统老师——WYQ老师

### 文章目录 ###

*  5.1 虚拟存储器概述
 *   *  5.1.1 常规存储管理方式的特征 和局部性原理
     *  5.1.2 虚拟存储器的定义和特征
     *  5.1.3 虚拟存储器的实现方法
 *  5.2 请求分页存储管理方式
 *   *  5.2.1 请求分页中的硬件支持
     *   *  练习题
         *  练习题
         *  练习题
     *  5.2.2 内存分配策略和分配算法
     *  5.2.2 内存分配策略和分配算法
     *   *  练习题
     *  5.2.3 调页策略
     *   *  练习题
 *  5.3 页面置换算法
 *   *  5.3.1 最佳置换算法和先进先出置换算法
     *  5.3.2 最近最久未使用(LRU)置换算法
     *   *  练习题
     *  5.3.3 Clock置换算法-LRU的近似算法
     *   *  练习题
     *  5.3.4 其它置换算法
 *  5.4 “抖动”与工作集
 *  5.5 请求分段存储管理方式
 *   *  5.5.1 请求分段中的硬件支持
     *  5.5.2 分段的共享与保护

# 5.1 虚拟存储器概述 #

## 5.1.1 常规存储管理方式的特征 和局部性原理 ##

**1. 常规存储器管理方式的特征**  
(1) 一次性  
(2) 驻留性  
**2.局部性原理**  
**（1）定义**  
指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中。  
**（2）分类**  
时间局部性：

*  被访问过一次的存储器位置很可能在不远的将来再被多次访问。
 *  循环结构

空间局部性：

*  如果一个存储器位置被访问了一次，那么程序很可能在不远的将来访问附近的一个存储器位置
 *  顺序结构/大数组

**3.虚拟存储器的基本工作情况**

*  所谓虚拟存储技术是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作。
 *  虚拟地址空间 即为 分配给进程的虚拟内存。
 *  虚拟地址 是 在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分。

**存储器的层次结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]  
**虚存与存储器体系**

*  把内存与磁盘有机地结合起来使用，从而得到一个容量很大的“内存”，即虚存。
 *  虚存是对内存的抽象，构建在存储体系之上，由操作系统协调各存储器的使用。
 *  虚存提供了一个比物理内存空间大得多的地址空间。

理论最大：CPU的寻址范围  
实际最大：内存+外存

## 5.1.2 虚拟存储器的定义和特征 ##

以CPU时间和磁盘空间换取昂贵内存空间，这是操作系统中的资源转换技术 。  
**1.虚拟存储器的定义**

*  是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。
 *  其容量接近于外存，其运行速度接近于内存速度，而每位的成本却又接近于外存。

**在虚存管理中**

*  虚拟地址空间是指逻辑地址空间，实地址空间是指物理地址空间；
 *  前者的大小受CPU可寻址范围(机器地址长度)的限制，而后者的大小受物理内存大小的限制。

**虚拟存储器的概念图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 1]  
**2.虚拟存储器的特征**

*  离散性：在分配内存时采用离散分配方式
 *  多次性：一个作业被分成多次调入内存运行
 *  对换性：允许在作业的运行过程中进行换进、换出
 *  虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量

虚拟性以多次性和对换性为基础；  
多次性和对换性以离散分配为基础。

## 5.1.3 虚拟存储器的实现方法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 2]  
**实现虚存技术的物质基础**

*  二级存储结构——内存+外存
 *  动态地址转换机构——将逻辑地址转换成物理地址

**实现虚拟存储器须解决的问题**

*  主存辅存统一管理问题
 *  逻辑地址到物理地址的转换问题
 *  部分装入和部分对换问题

**引入虚拟存储技术的好处**

*  大程序：可在较小的可用内存中执行较大的用户程序；
 *  大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)；
 *  并发性：可在内存中容纳更多程序并发执行；
 *  易于开发：与覆盖技术比较，不必影响编程时的程序结构。

# 5.2 请求分页存储管理方式 #

基本思想：请求分页=分页+请求  
逻辑空间分页 物理空间分块  
页与块同样大 页连续块离散  
用页号查页表 硬件做重定位

**请求分页的基本思想**  
（2）作业部分装入内存  
（3）作业所占的内存块不连续  
（4）硬件通过页表生成访问内存的地址  
（5）若发生缺页，则进行缺页中断处理，将该页调入内存  
（6）利用快表可以加速地址转换

**请求分页式虚拟存储**  
**硬件支撑**：硬件（主存管理单元MMU）  
**主要任务**：将逻辑地址转换为物理地址  
**功能**

*  管理硬件页表基址寄存器
 *  分解逻辑地址
 *  管理快表
 *  访问页表
 *  发出缺页中断或越界中断，并将控制权交给内核存储管理处理
 *  设置和检查页表中各个特征位

## 5.2.1 请求分页中的硬件支持 ##

**1.页表机制**  
![在这里插入图片描述][20210125002409927.png]  
**状态位P**：指示该页是否已调入内存  
**访问字段A**：记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考  
**修改位M**：该页在调入内存后是否被修改过，供置换页面时参考  
**外存地址**：指出该页在外存上的地址，供调入该页时参考

### 练习题 ###

**1.** 虚拟页式存储系统中页表的作用十分重要，页表由页表项组成，在页表项中标记出页面尚未读入内存的是（B）  
A.保护位  
B.有效位  
C.访问位  
D.修改位

**2. 缺页中断(异常)**

*  是一种Page Fault；
 *  在地址映射过程中，硬件检查页表时发现所要访问的页面不在内存，则产生该异常——缺页异常；
 *  操作系统执行缺页异常处理程序，获得磁盘地址，启动磁盘，将该页调入内存：  
    如果内存中有空闲页框，则将新页调入，并修改页表项的有效位、访问位及页框号；  
    若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘。

**缺页中断与一般中断的区别**  
（1）缺页中断是在执行一条指令中间时产生的中断，并立即转去处理。而一般中断则是在一条指令执行完毕后，当发现有中断请求时才去响应和处理。  
（2）缺页中断处理完成后，仍返回到原指令去重新执行，因为那条指令并未执行。而一般中断则是返回到下一条指令去执行，因为上一条指令已经执行完毕了。

**缺页中断处理过程**  
①根据当前执行指令中的虚拟地址，形成数对：（页号，页内位移）。用页号去查页表，判断该页是否在内存。  
②若该页的状态位为“0”，表示当前该页不在内存，于是产生缺页中断，让操作系统的中断处理程序进行中断处理。  
③中断处理程序去查存储分块表，寻找一个空闲的内存块；查页表，得到该页在辅助存储器上的位置，并启动磁盘读信息。  
④把从磁盘上读出的信息装入到分配的内存块中。  
⑤根据分配存储块的信息，修改页表中相应的表目内容，另外，还要修改存储分块表里相应表目的状态。  
⑥由于产生缺页中断的那条指令并没有执行，所以在完成所需页面的装入工作后，应该返回原指令重新执行。这时再执行时，由于所需页面已在内存，因此可以顺利执行下去。

### 练习题 ###

**1.\[2016统考试题 22\]** 异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。  
下列关于中断或异常情况的叙述中，错误的是：(A)  
A．“访存时缺页”属于中断  
B．“整数除以0”属于异常  
C．“DMA传送结束”属于中断  
D．“存储保护错”属于异常

**3.地址变换机构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 3]

### 练习题 ###

**\[1.2013统考试题 30\]** 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是 （B）  
I. 处理越界错 II. 置换页 III. 分配内存  
A. 仅 I、II  
B. 仅 II、III  
C. 仅 I、III  
D. I、II和 III

**地址转换过程**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 4]  
**由此过程可知，当系统对数据进行存取时，有三种可能:**  
A． 所存取的数据的页面在内存，其页表项已经存储到快表，此时存取数据的时间是：查询快表的时间+存取内存数据的时间  
B． 所存取的数据的页面在内存，但其页表项没有存储到快表，没有命中快表。此时存取数据的时间是：查询快表+查询页表的时间+存取内存数据的时间  
C． 所存取的数据的页面不在内存，发生缺页中断，此时存取数据的时间是：查询快表+查询页表的时间+缺页中断的时间+查询快表的时间+存取内存数据的时间

**请求分页存储管理优缺点**  
优点

*  按页分散存放在内存中，减少移动开销；
 *  有利于改进主存利用率；
 *  部分装入，有利于多道程序运行。

缺点

*  需要硬件支持，进行缺页中断处理，成本增加，开销加大；
 *  存在页内碎片。

## 5.2.2 内存分配策略和分配算法 ##

**考虑因素**

*  分给进程的空间越小,同一时间处于内存的进程就越多，并发度越高；
 *  如果进程只有小部分在主存里,即使局部性很好,缺页中断率也可能会相当高；
 *  因程序的局部性原理，分给进程的内存超过一定限度后，再增加内存空间,不会明显降低进程的缺页中断率。

**置换问题**  
（1）置换范围

*  **局部置换策略**：仅在产生本次缺页的进程的驻留集中选择。
 *  **全局置换策略**：将内存中所有未锁定的页框都作为置换的候选。

（2）置换策略

*  决定置换当前内存中的哪一个页框；
 *  目标：→ 置换最近最不可能访问的页；
 *  根据局部性原理，最近的访问历史和最近将要访问的模式间存在相关性，因此，大多数策略都基于过去的行为来预测将来的行为；
 *  注意：置换策略设计得越精致、越复杂，实现的软硬件开销就越大；
 *  约束：不能置换被锁定的页框！

（3）页框锁定

*  采用虚存技术后
 *  开销 → 使进程运行时间变得不确定
 *  给每一页框增加一个锁定位
 *  通过设置相应的锁定位，不让操作系统将进程使用的页面换出内存，避免产生由交换过程带来的不确定的延迟

## 5.2.2 内存分配策略和分配算法 ##

**1. 最小物理块数的确定**  
进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、 功能和寻址方式

**2. 物理块的分配策略**  
内存分配策略：固定和可变分配策略  
置换策略：全局置换和局部置换

1.  固定分配局部置换  
    缺点：难以确定固定分配的页数(太少:缺页率高;太多:浪费)
2.  可变分配全局置换  
    置换算法复杂；
3.  可变分配局部置换  
    根据进程的缺页率进行页面数调整，进程之间相互不会影响。

### 练习题 ###

**1.\[2015统考试题 30\]** 在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（C）  
A．可变分配，全局置换  
B．可变分配，局部置换  
C．固定分配，全局置换  
D．固定分配，局部置换

**3. 物理块分配算法**

1.  平均分配算法  
    将系统中所有可供分配的物理块，平均分配给各个进程。  
    缺点：未考虑各进程本身的大小。
2.  按比例分配算法  
    这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为： S = ∑ i = 1 n S i S=∑^n\_\{i=1\} S\_i S=∑i=1nSi  
    又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有： b i = S i / S ∗ m b\_i=S\_i/S\*m bi=Si/S∗m  
    b应该取整，它必须大于最小物理块数。
3.  按优先级分配  
    在实际应用中，为了照顾重要的、急迫的作业尽快完成，应为它分配较多的内存空间。  
    方法：一部分按比例分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。

## 5.2.3 调页策略 ##

**1. 何时调入页面**  
（1）请调(demand paging)  
upon page fault, 发生缺页中断时调入（较费系统开销）  
（2）预调(prepaging)  
before page fault, 将要访问时调入(根据程序顺序行为，不一定准）（根据空间局部性，目前：成功率≤50％）

**2. 从何处调入页面**  
外存：文件区、对换区  
(1)系统拥有足够的对换区空间：对换区  
(2)系统缺少足够的对换区空间：文件区/对换区  
(3)UNIX方式：首次->文件区/再请调->对换区

**3. 页面调入过程**

*  缺页中断
 *  保留CPU环境
 *  缺页中断处理
 *  访问内存数据

**页面调入策略**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 5]  
**影响缺页率的主要因素**  
(1)分配给作业的主存块数: 多则缺页率低，反之则高。  
(2)页面大小：大则缺页率低；反之则高。  
(3)页面调度算法：对缺页中断率影响很大，但不可能找到一种最佳算法。  
(4)程序编制方法：以数组运算为例，如果每一行元素存放在一页中，则按行处理各元素缺页中断率低；反之，按列处理各元素，则缺页中断率高。

### 练习题 ###

**1.** 在请求调页系统中，地址变换过程可能会因为逻辑地址越界、缺页和访问权限错误等原因而产生中断。

\*\*2.\*\*在虚拟页式存储系统中，对缺页异常没有影响的因素是（C）  
A.程序本身的编制方法  
B.分配给进程的页框数目  
C.页表在内存中的位置  
D.页面置换算法

**3.** 下列哪一项不属于页错误(Page Fault)发生的原因（C）  
A.虚拟地址落在地址空间中没有内容的区域  
B.用户进程访问的地址对应的页表项的U/S位是S标志  
C.用户进程对一个页面执行了读操作  
D.所访问的页面在磁盘上

**4.** 在虚拟页式存储系统中，若页面尺寸为4K，页表项大小为4字节，则采用三级页表结构可以表示多大的虚拟地址空间（A）  
A. 242  
B. 248  
C. 220  
D. 239

**5.** 在虚拟页式存储系统中，引入快表后，MMU将虚拟地址划分为虚页号和页内偏移，之后的主要工作包括：  
①根据虚页号查找页表，得到对应的页表项  
②根据虚页号查找快表TLB，得到对应的页框号  
③根据页表项中的页框号与页内偏移形成物理地址  
④MMU产生Page Fault，陷入操作系统，执行缺页异常处理程序  
下列选项中，哪一项不是MMU的正确工作顺序（D）  
A.②①③  
B.②③  
C.②①④③  
D.②④①③

**6.** 下列关于快表的叙述中，哪些是正确的（ACDE）  
A.对快表的查找是按内容并行完成的  
B.快表保存在内存固定位置  
C.操作系统实现进程切换时候会刷新TLB  
D.快表的内容是页表的子集  
E.引入快表可以加快地址转换速度

**7.** 下列哪些因素影响了虚存的容量（BC）  
A.快表的大小  
B.计算机系统的寻址机制  
C.磁盘空间大小  
D.数据存放的实际地址  
E.物理内存大小

# 5.3 页面置换算法 #

用于：页淘汰、段淘汰、快表淘汰。

## 5.3.1 最佳置换算法和先进先出置换算法 ##

**1. 最佳(Optimal)置换算法-理想化**  
最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。

**2.先进先出(FIFO)页面置换算法**  
1）该算法的出发点是最早调入内存的页面，其不再被访问的可能性会大一些。  
2）该算法实现比较简单(队列)，对具有线性顺序访问的程序比较合适，而对其他情况效率不高。因为经常被访问的页面，往往在内存中停留最久，结果这些常用的页面却因变老而被淘汰。  
3）先进先出算法存在一种异常现象，即在某些情况下会出现分配给的进程物理块数增多，缺页次数有时增加，有时减少的奇怪现象，这种现象称为Belady现象。

**Belady异常**  
随着物理块数的增多缺页率可能增大

## 5.3.2 最近最久未使用(LRU)置换算法 ##

**1. LRU(Least Recently Used)置换算法的描述**  
**2. LRU置换算法的硬件支持**  
(1) 寄存器  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 6]  
(2) 栈  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 7]

### 练习题 ###

**1.\[2014考研题 30\]** 在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（A）。  
I．LRU算法  
II．FIFO算法  
III．OPT算法  
A．仅II  
B．仅I、II  
C．仅I、III  
D．仅II、III

\*\*2.\[2015考研题 27\]\*\*系统为某进程分配了4 个页框，该进程已访问的页号序列为  
2,0,2,9,3,4,2,8,2,4,8,4,5，若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（A）  
A．2  
B．3  
C．4  
D．8

**3.\[2009年统考计算机考研真题\]** 请求分页管理系统中，假设某进程的页表内容如下表所示。 页表内容  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 8]  
页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。  
假设  
①TLB初始为空；  
②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；  
③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：  
(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。  
(2) 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。  
**解答**  
（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。  
页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。  
可得三个虚地址的页号P如下：2 1 2  
![在这里插入图片描述][20210125011833252.png]

*  2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
 *  1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，重新执行指令，访问快表命中10ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+10ns+100ns=100000220ns。
 *  25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。

（2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。

## 5.3.3 Clock置换算法-LRU的近似算法 ##

**1. 简单的Clock置换算法**

*  内存中的所有页按FIFO链接成一个循环队列，用一个指针指向最老的页面，每页设置一位访问位：初值为0；被访问时置1。
 *  需要淘汰时，循环检查各页面的访问位：  
    为“0”：选择该页淘汰；  
    为“1”：复位访问位为“0”，查询指针前进一步。
 *  又称为“最近未使用”置换算法（NRU）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 9]  
**2.改进型Clock置换算法- 计算置换代价**  
由访问位A和修改位M可以组合成下面四种类型的页面：  
1类(A=0, M=0): 表示该页最近既未被访问，又未被修改，是最佳淘汰页。  
2类(A=0, M=1)： 表示该页最近未被访问，但已被修改，并不是很好的淘汰页。  
3类(A=1, M=0)： 最近已被访问， 但未被修改，该页有可能再被访问。  
4类(A=1, M=1): 最近已被访问且被修改，该页可能再被访问。

**改进的Clock算法**  
访问位A 修改位M  
A=0 M=0  
A=0 M=1  
A=1 M=0  
A=1 M=1  
扫描寻找A=0 M=0的页 ——>扫描寻找A=0 M=1的页,把经过的A=1改为0

### 练习题 ###

**1.\[2016考研题 26\]** 某系统采用改进型CLOCK置换算法，页表项中A为访问字段位，M为修改位。A=0表示页最近没有被访问，A=1表示页最近被访问过。M=0表示页没有被修改过，M=1表示页被修改过。按（A，M）所有可能的取值，将页分为四类：（0，0）、（1，0）、（0，1）和（1，1），则该算法淘汰页的次序为：（A）  
A．（0，0），（0，1），（1，0），（1，1）  
B．（0，0），（1，0），（0，1），（1，1）  
C．（0，0），（0，1），（1，1），（1，0）  
D．（0，0），（1，1），（0，1），（1，0）

**2.\[2010年考研试题 46（8分）\]** 设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 10]  
当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：  
（1）该逻辑地址对应的页号是多少？  
（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。  
（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程(设搜索下一页的指针沿顺时针方向移动，当前指向2号页框，示意图如下)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 11]  
**解答**  
17CAH=(0001 0111 1100 1010)2  
（1）页大小为1K，所以页内偏移地址为10位，于是前6位是页号，所以第一问的解为：5  
（2）FIFO，则被置换的页面所在页框为7，所以对应的物理地址为：(0001 1111 1100 1010)2—1FCAH  
（3）CLOCK,则被置换的页面所在页框为2，所以对应的物理地址为:(0000 1011 1100 1010)2—OBCAH

## 5.3.4 其它置换算法 ##

1）最少使用(LFU： Least Frequently Used)置换算法

*  选择到当前时间为止被访问次数最少的页面来置换；
 *  每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；
 *  发生缺页中断时，淘汰计数值最小的页面，并将所有计数器清零；

**LRU和LFU的区别**  
LFU(Least Frequently Used-最近最少使用)  
LRU(Least Recently Used最近最久未使用)

2）页面缓冲算法  
它是对FIFO算法的发展，通过对淘汰页面的缓冲，有机会找回刚被淘汰的页面；

*  淘汰页面的选择和处理：用FIFO算法选择淘汰页，把淘汰的页面放入两个链表之一。  
    如果页面未被修改，就将其归入到空闲块链表的末尾  
    否则将其归入到已修改块链表。
 *  需要调入新的页面时，将新页面内容读入到空闲块链表的第一块，然后将该块从空闲链表摘下挂入进程相应队列并修改页表。
 *  对于被淘汰到空闲链和已修改链中的页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，使其重新进入进程相应队列。
 *  当已修改页面达到一定数目后，再将它们一起回写到外存，再将相应内存块归入空闲页面链表，这样能大大减少I/O操作的次数。

**访问内存的有效时间**:是指给定逻辑地址找到内存中对应物理地址单元中的数据所用的总时间。

**基本分页管理方式有效访问时间的计算**  
（1） 没有快表的情况(设访存一次所需的时间为t)：  
查找页表找到对应页表项，需要访存一次;  
通过对应页表项中的物理地址访问对应内存单元，需要访存一次;  
因此，EAT=t+t=2t  
（2）有快表的情况：  
设访问快表的时间为λ，快表的命中率为a，则EAT=a(λ+t)+(1-a)(λ+t+λ+t)

*  访问的页在主存中，且访问页在快表中:  
    EAT=查找快表时间+根据物理地址访存时间= λ+t
 *  访问的页在主存中，但不在快表中:  
    EAT=查找快表时间+查找页表时间+修改快表时间+根据物理地址访存时间= λ+t+λ+t=2(λ+t)
 *  访问的页不在主存中，即发生缺页，设处理缺页中断的时间为ε（包括将该页调入主存，更新页表和快表时间）：  
    EAT=查找快表时间+查找页表时间+处理缺页时间+查找快表时间+根据物理地址访存时间=λ+t+ε+λ+t=ε+2(λ+t)

**加入缺页率和命中率**  
设a为快表命中率，f为缺页率，λ为一次读或更新快表时间，t为访问一次内存时间，ε为一次缺页中断时间；  
EAT=a(λ+t)+(1-a)\[(1-f)(λ+t+λ+t)+f(λ+t+ε+λ+t)\]  
=aλ+at+(1-a)\[(1-f)(λ+t)+(λ+t)-f(λ+t)+f(λ+t)+f(ε+λ+t)  
=λ+at+(1-a)\[t+(1-f)(λ+t)+ f(ε+λ+t)\]  
**说明**

*  如果没说明快表访问和修改时间，就表示没有快表，则命中率a和访问时间λ=0；
 *  缺页中断时间ε的计算：  
    如果题目中没有说明被置换出的页面是否被修改，则缺页中断时间统一为一个值ε。  
    如果题目中说明了被置换的页面分为修改和未修改两种不同的情况;  
    假设被修改的概率为n，处理被修改的页面时间为ε1，处理未被修改的页面时间为ε2;  
    则处理缺页时间ε =nε1+(1-n) ε2

# 5.4 “抖动”与工作集 #

抖动thrashing：刚刚被换出的页面很快又要用到，CPU忙于调出和调入页面。  
根本原因：页面淘汰算法不合理；分配给进程的物理页面数(驻留集)太少。

**防止抖动发生的方法**  
(1)挂起某些进程-调节多道程序度。  
(2)采用局部置换策略。  
(3)L=S准则(产生缺页的平均时间等于系统处理缺页的平均时间。  
(4)利用工作集策略防止抖动。

**工作集**  
工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元函数W(t, Δ)来表示：

*  t是当前的执行时刻；
 *  Δ称为工作集窗口（working-set window ），即一个定长的页面访问窗口；
 *  W(t, Δ)＝在当前时刻 t 之前的Δ窗口当中的所有页面所组成的集合（随着 t 的变化，该集合也在不断地变化）；
 *  | W(t, Δ) | 指工作集的大小，即页面数目。

**驻留集**

*  驻留(常驻)集是指在当前时刻，进程实际驻留在内存当中的页面集合。
 *  工作集是进程在运行过程中固有的性质，而驻留集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法；
 *  如果一个进程的整个工作集都在内存当中，即驻留集工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）；
 *  当驻留集达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降。

**缺页率与驻留集的关系**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70_pic_center]

# 5.5 请求分段存储管理方式 #

## 5.5.1 请求分段中的硬件支持 ##

**1. 段表机制**  
![在这里插入图片描述][20210328000741976.png]  
存取方式：标志本分段的存取属性  
访问字段A：记录该段被访问的频繁程度（与分页相应字段同）  
修改位M：该段在调入内存后是否被修改过，供置换时参考  
存在位P：指示本段是否已调入内存，供程序访问时  
增补位：本段在运行过程中，是否允许动态增长  
外存始址：本段在外存中的起始地址  
**2. 缺段中断机构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 12]  
**3. 地址变换机构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 13]

## 5.5.2 分段的共享与保护 ##

**1. 共享段表**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 14]  
**2. 共享段的分配与回收**  
1）分配：  
第一次访问：分配内存（1）增加共享段表；（2）修改进程段表。  
第二次访问：（1）修改共享段表；（2）修改进程段表。  
2）回收： （1）count=0 （2）count< >0

*  在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区；
 *  同时将该区的始址填入请求进程的段表的相应项中；
 *  在共享段表中增加一表项，填写有关数据，把count置为1；
 *  之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中增加一表项，填写该共享段的物理地址；
 *  在共享段的段表中，填上调用进程的进程名、存取控制等；
 *  再执行count∶=count+1操作，以表明有两个进程共享该段。
 *  当共享此段的某进程不再需要该段时，应将该段释放， 包括撤销在该进程段表中共享段所对应的表项，以及执行count∶=count-1操作；
 *  若count =0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项， 表明此时已没有进程使用该段；
 *  否则(减1结果不为0)， 则只是取消调用者进程在共享段表中的有关记录。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 15]  
**环保护机构**  
操作系统应处于最高特权环，一般应用程序应处于最低特权环，某些重要的实用程序和操作系统服务占居中间环；  
一个程序可以访问驻留在相同环或较低特权环中的数据；  
一个程序可以请求驻留在相同环或较高特权环中的服务。

**虚拟存储管理方案**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 16]  
**页面置换算法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 17]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]: /images/20221119/902fd2b93b34462fabaf7af1406e8f49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210125000914373.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210125001401460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[20210125002409927.png]: https://img-blog.csdnimg.cn/20210125002409927.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210125003247802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2021012500343089.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210125005845587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210125011336111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2021012501140640.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20210125011727424.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[20210125011833252.png]: https://img-blog.csdnimg.cn/20210125011833252.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20210125012054887.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20210125012631533.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20210125012725890.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210328000638212.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70#pic_center
[20210328000741976.png]: https://img-blog.csdnimg.cn/20210328000741976.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/2021032800101537.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20210328001145134.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20210328001219514.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20210328001529859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20210328001701233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20210328001752512.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70