26.页面置换算法

（1）最佳页面置换算法：选择被置换的页面，将是永不使用的页面，或最长时间不使用的页面

优点：可保证最低的缺页率

缺点：不可能真正实现，只可作为其它算法的评价参考

（2）先进先出（FIFO）页面置换算法

选择最先进入内存的页面，即选择在内存中驻留时间最长的页面予以淘汰 优点：算法简单

缺点：性能不佳

（3）最近最久未使用（LRU）页面置换算法：选择最近最久未被使用的页面淘汰

优点：性能较好

缺点：需要较多的硬件支持

（4）Clock置换算法 （5）改进型Clock置换算法

①查找指针前进一步，判断当前页是否为第1类页（A=0，M=0），是则选择该页淘汰 ②否则，继续沿链向下查找

③如果沿链查找一周，没有第1类页面，则查找第2类页（A=0，M=1），找到后淘汰，并将访问过的页面访问位置为0（A=0）

④如果沿链查找一周后，未找到第2类页面（则所有页面的访问位置已被置为0），重新从第⑴步开始

（6） 页面缓冲（PBA）置换算法 练习

（1）在一个请求页式存储管理系统中，访问串为1, 3, 6, 7, 1, 3, 6, 7, 1, 3, 6, 7时，试用最近最久未使用（LRU）置换算法，计算当分配给该进程的内存块数为3时，访问过程中发生的页面置换过程及页面置换次数。（假定开始时，物理块中为空）

（2）在一个请求页式存储管理系统中，进程P共有5页，访问串为3，2，1，0，3，2，4，3，2，1，0，4时，试用CLOCK置换算法，计算当分配给该进程的内存块数为3时，访问过程中发生的页面置换过程及页面置换次数。（假定开始时，物理块中为空）

27.当需要访问的段不在内存时,便产生一缺段中断 与缺页中断的相同点：

⑴.缺段中断同样可能发生在指令执行过程中 ⑵.一条指令执行期间，可能发生多次缺段中断 与缺页中断的不同点：

⑴.一条指令只可能存在于一个段中 ⑵.一个（组）数据只可能存在于一个段中 习题

1. 分页和分段存储管理相同点和不同点是什么？

a.分页和分段都采用离散分配的方式，且都要通过地址映射机构来实现地址变换，这是它们的共同点；

b.对于它们的不同点有三，第一，从功能上看，页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率，即满足系统管理的需要，而不是用户的需要；段是信息的逻辑单位，它含有一组其意义相对完整的信息，目的是为了能更好地满足用户的需要；第二页的大小固定且由系统确定，而段的长度却不固定，决定于用户所编写的程序；第三分页的作业地址空间是一维的，而分段的作业地址空间是二维的。

2. 某系统采用页式存储器管理,页长为 1K(1024)字,有一作业四个页面 0， 1， 2，3 按顺序装入主存的 2，4，5，7 块中去,当前正在运行该作业。求（1）逻辑地址 2500 所对应的物理地址为多少；（2）物理地址 7218 对应的逻辑地址是多少？(上述地址都是十进制表示) 解：

（1）页号=逻辑地址/页大小= 2500/1024=2

页内地址=逻辑地址 mod 页大小=2500 mod 1024=452 查页表页号 2 对应块号 5

物理地址=块号 * 页大小 +页内地址= 5*1024+452 =5572 （十六进制:15C4） （2）物理块号=物理地址/页大小 = 7218/1024 = 7 页内地址 =物理地址 mod 页大小= 7218 mod 1024 =50 查页表块号 7 对应的页号为 3

逻辑地址=页号*页大小+页内地址=3*1024+50 = 3122 （十六进制：C32）

3. 在一个请求页式存储管理系统中，页面大小为 100B，一个程序的访问地址序 列为：115、218、320、402、246、102、521、632、260、167、280、311、 720，若系统采用最近最久未使用（LRU）置换算法，计算当分配给该进程的 内存块数为 3 时，访问过程中发生的页面置换过程及页面置换次数。（假定开 始时，物理块中为空）

第五章

1.设备管理的必要性（为什么管理？）

设备种类繁多，特性（速率、传送单位、容许操作）各异 设备驱动、控制、分配复杂，用户难以胜任 设备速率与CPU速率相差很大，如何提高效率

2.设备管理的目标：方便性、并行性、均衡性、无关性

3.设备管理的功能： 监视所有设备的状态

制定设备分配策略，实现设备合理分配和回收 设备的驱动和处理 数据缓冲

4.I/O设备分类

（1）按传输速率分类：低速设备、中速设备、高速设备 （2）按信息交换的单位分类

块设备：信息的存取以数据块为单位，如磁盘 字符设备：用于无结构的数据I/O，如键盘、打印机 （3）按设备的共享属性分类：独占设备、共享设备、虚拟设备 （4）按设备的外部特征分类：存储设备、输入设备、输出设备

5.设备与控制器之间的接口：数据信号线、控制信号线、状态信号线

6.设备控制器的功能 接收和识别命令 标识和报告设备的状态 数据交换 地址识别 数据缓冲 差错控制

7.I/O通道

（1）单通路I/O通道：设备与计算机之间只有一条通路 （2）多通路I/O通道：设备与计算机之间有多条通路

8.I/O控制方式

（1）程序I/O控制方式

由CPU采用循环查询的方式直接控制I/O （2）中断方式

CPU启动I/O后，继续其它工作，等I/O设备数据准备好后，再将数据读入/写出 （3）DMA方式

CPU启动I/O后，由DMA设备控制器自动完成一块（连续）数据的读写工作，CPU可以继续其它工作，等I/O设备完成数据块读/写工作后，再作后续处理 （4）I/O通道方式

CPU启动I/O后，由I/O通道设备控制器自动完成一组数据块（离散）数据的读写工作，CPU可以继续其它工作，等I/O设备完成一组数据块读/写工作后，再作后续处理

9.引入缓冲的原因