深圳大学2015年操作系统复习提纲-吴少滨整理 - 图文 下载本文

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.引入缓冲的原因