操作系统复习题ppt课件.ppt

《操作系统复习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统复习题ppt课件.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统复习操作系统复习南京工业大学信息学院计算机系南京工业大学信息学院计算机系2022-8-8操作系统复习操作系统复习2一、单项选择题一、单项选择题每题每题2分，共分，共60分。分。二、应用题二、应用题每题每题10分，共分，共40分。分。应用题类型：应用题类型： 进程互斥、同步；进程互斥、同步； 处理机调度；处理机调度； 死锁问题；死锁问题； 地址重定位；地址重定位； 页面置换算法；页面置换算法； 磁盘调度；磁盘调度； 文件物理结构；文件物理结构； 目录管理；目录管理； 外存空间的管理等。外存空间的管理等。2022-8-8操作系统复习操作系统复习3一、选择题一、选择题1下列选项中，操作系统提

2、供给应用程序的接口是下列选项中，操作系统提供给应用程序的接口是 。 A系统调用系统调用B中断中断 C库函数库函数D原语原语 2下列选项中，导致创建新进程的操作是下列选项中，导致创建新进程的操作是 。I用户登录成功用户登录成功II设备分配设备分配 III启动程序执行启动程序执行 A仅仅I和和IIB仅仅II和和III C仅仅I和和IIIDI、II和和III 3下列选项中，降低进程优先级的合理时机是下列选项中，降低进程优先级的合理时机是 。 A进程的时间片用完进程的时间片用完 B进程刚完成进程刚完成I/O，进入就绪队列，进入就绪队列 C进程长期处于就绪队列中进程长期处于就绪队列中 D进程从就绪队列转

3、为运行状态进程从就绪队列转为运行状态 ACA2022-8-8操作系统复习操作系统复习44设与某资源关联的信号量初值为设与某资源关联的信号量初值为3，当前值为，当前值为1。若。若M表表示该资源的可用个数，示该资源的可用个数，N表示等待该资源的进程数，则表示等待该资源的进程数，则M、N分别是分别是 。A0、1B1、0C1、2D2、0 5某基于动态分区存储管理的计算机，其主存容量为某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲初始为空闲)，采用最佳适配，采用最佳适配(Best Fit)算法，分配和释算法，分配和释放的顺序为：分配放的顺序为：分配15MB、分配、分配30MB、释放、释

4、放15MB、分配、分配8MB、分配、分配6MB，此时主存中最大空闲分区的大小是，此时主存中最大空闲分区的大小是 。A7MBB9MBC10MBD15MB 6设置当前工作目录的主要目的是设置当前工作目录的主要目的是 。A节省外存空间节省外存空间B节省内存空间节省内存空间C加快文件的检索速度加快文件的检索速度D加快文件的读加快文件的读/写速度写速度BBC2022-8-8操作系统复习操作系统复习57下列选项中，能引起外部中断的事件是下列选项中，能引起外部中断的事件是_。 A键盘输入键盘输入B除数为除数为0 C浮点运算下溢浮点运算下溢D访存缺页访存缺页 8某计算机系统中有某计算机系统中有8台打印机，有台

5、打印机，有k个进程竞争使用，每个个进程竞争使用，每个进程最多需要进程最多需要3台打印机。该系统可能会发生死锁的台打印机。该系统可能会发生死锁的k的最小的最小值是值是_。 A2B3C4D59一个分段存储管理系统中，地址长度一个分段存储管理系统中，地址长度32位，其中段号占位，其中段号占8位，则最大段长是位，则最大段长是_。A2的的8次方字节次方字节B2的的16次方字节次方字节C2的的21次方字节次方字节D2的的32次方字节次方字节 ACC2022-8-8操作系统复习操作系统复习610下列文件物理结构中，适合随机访问且易于文件扩展的下列文件物理结构中，适合随机访问且易于文件扩展的是是_。 A连续结

6、构连续结构 B索引结构索引结构 C链式结构且磁盘块定长链式结构且磁盘块定长 D链式结构且磁盘块变长链式结构且磁盘块变长11设文件设文件F1当前引用计数值为当前引用计数值为1，先建立，先建立F1的符号链接的符号链接(软软链接链接)文件文件F2，再建立，再建立F1的硬软链接文件的硬软链接文件F3，然后删除，然后删除F1。此时，。此时，F2和和F3的引用计数值分别是的引用计数值分别是_。 A0、1B1、1C1、2D2、1 12单处理机系统中，能并行的是单处理机系统中，能并行的是_。I. 进程与进程进程与进程II. 处理机与设备处理机与设备III. 处理机与通道处理机与通道IV. 设备与设备设备与设备

7、 AI、II和和IIIBI、II和和IV CI、III和和IVDII、III和和IV BBD2022-8-8操作系统复习操作系统复习713下列进程调度算法中，综合考虑进程等待时间和执行时下列进程调度算法中，综合考虑进程等待时间和执行时间的是间的是_。A时间片轮转调度算法时间片轮转调度算法 B短进程优先调度算法短进程优先调度算法C先来先服务调度算法先来先服务调度算法 D高响应比优先调度算法高响应比优先调度算法 14多道程序系统中，当多道程序系统中，当 时，进程从执行状态转变为时，进程从执行状态转变为就绪状态。就绪状态。 A. 进程被进程调度程序选中进程被进程调度程序选中 B. 时间片到时间片到

8、C. 等待某一事件等待某一事件 D. 等待的事件发生等待的事件发生 15下述各项中，下述各项中， 不是引起进程切换的直接原因。不是引起进程切换的直接原因。A. 运行进程的时间片用完运行进程的时间片用完B. 运行进程出错运行进程出错C. 运行进程要等待某一事件发生运行进程要等待某一事件发生D. 有新进程进入就绪状态有新进程进入就绪状态 DBD2022-8-8操作系统复习操作系统复习816在支持多线程的系统中，进程在支持多线程的系统中，进程P创建的若干线程不能共创建的若干线程不能共享的是享的是 。A进程进程P的代码段的代码段B进程进程P中打开的文件中打开的文件C进程进程P的全局变量的全局变量D进程

9、进程P中某线程的栈指针中某线程的栈指针17在缺页处理过程中，操作系统执行的操作可能是在缺页处理过程中，操作系统执行的操作可能是 。修改页表修改页表磁盘磁盘I/O 分配页框分配页框A仅仅、B仅仅C仅仅D、和和 18下列选项中，在用户态执行的是下列选项中，在用户态执行的是 。A命令解释程序命令解释程序B缺页处理程序缺页处理程序C进程调度程序进程调度程序D时钟中断处理程序时钟中断处理程序 2022-8-8操作系统复习操作系统复习919有两个并发进程有两个并发进程P1和和P2，共享初值为，共享初值为1的变量的变量x。P1对对x加加1，P2对对x减减1。加。加1和减和减1操作的指令序列分别如下所示。操作

10、的指令序列分别如下所示。 /加加1操作操作load R1, x /取取x到寄存器到寄存器R1中中inc R1store x, R1 /将将R1的内容存入的内容存入x/减减1操作操作load R2, xdec R2store x, R2两个操作完成后，两个操作完成后，x的值的值 。A可能为可能为-1或或3B只能为只能为1C可能为可能为0、1或或2D可能为可能为-1、0、1或或2 2022-8-8操作系统复习操作系统复习101某多道程序设计系统供用户使用的主存为某多道程序设计系统供用户使用的主存为100KB，磁带，磁带机机2台，打印机台，打印机1台。采用可变分区内存管理，采用静态方式台。采用可变分

11、区内存管理，采用静态方式分配外围设备，忽略用户作业的分配外围设备，忽略用户作业的I/O时间。现有如下作业序时间。现有如下作业序列：列： 二、应用题二、应用题作业名作业名提交时间提交时间需运行时间需运行时间主存需求量主存需求量磁带机需求磁带机需求打印机需求打印机需求J18:0025分钟分钟15KB11J28:2010分钟分钟30KB01J38:2020分钟分钟60KB10J48:3020分钟分钟20KB10J58:3515分钟分钟10KB11作业调度采用作业调度采用FCFS策略，优先分配主存低地址区域且不准策略，优先分配主存低地址区域且不准移动已在主存中的作业，进程调度采用时间片轮转算法移动已在

12、主存中的作业，进程调度采用时间片轮转算法(即即在主存中的作业均分在主存中的作业均分CPU时间时间)。现求：。现求： 2022-8-8操作系统复习操作系统复习11(1) 作业被调度的先后次序；作业被调度的先后次序；(2) 全部作业运行结束的时间；全部作业运行结束的时间；(3) 作业的平均周转时间；作业的平均周转时间；(4) 最大作业周转时间。最大作业周转时间。先在草稿上分析如下：先在草稿上分析如下：8:00J1到达，分配它所需资源到达，分配它所需资源(15KB内存、内存、 1台磁带机、台磁带机、1台打印机后，调入内存运行。余内存台打印机后，调入内存运行。余内存85KB、磁带机、磁带机1台。台。8

13、:20J2到达，因无打印机，不调入。同时到达，因无打印机，不调入。同时J3到达，分配它到达，分配它内存内存60KB，磁带机，磁带机1台，调入内存，与台，调入内存，与J1均分均分CPU时间运行。时间运行。余内存余内存25KB、磁带机和打印机都已分完、磁带机和打印机都已分完(余余0台台)。8:30J1结束，释放内存结束，释放内存15KB、磁带机、磁带机1台、打印机台、打印机1台。台。虽有打印机但内存不够，虽有打印机但内存不够，J2仍不能调入；仍不能调入；J4到达，因低端内到达，因低端内存存15KB不够，分配高端内存不够，分配高端内存20KB和磁带机和磁带机1台，调入内存台，调入内存与与J3一起运行

14、。剩下内存空闲块是一起运行。剩下内存空闲块是15KB、5KB，打印机，打印机1台台8:35J5到达，因无磁带机，不能调入。到达，因无磁带机，不能调入。2022-8-8操作系统复习操作系统复习129:00J3结束。释放资源后，系统有内存结束。释放资源后，系统有内存75KB，5KB、打印、打印机和磁带机个机和磁带机个1台。台。J2调入，内存余调入，内存余45KB，5KB、磁带机剩、磁带机剩1台、打印机台、打印机0台。台。J5仍不能进入仍不能进入(无打印机无打印机)。将。将J2、J4运行。运行。J4还需运行还需运行5分钟。分钟。9:10J4结束，释放资源后，内存空余结束，释放资源后，内存空余70KB

15、、磁带机空、磁带机空2台、台、打印机打印机0台。台。J5仍不能进入。仍不能进入。J2单独运行单独运行(还需还需5分钟分钟)。9:15J2结束，释放资源后，内存有结束，释放资源后，内存有100KB、磁带机有、磁带机有2台、台、打印机有打印机有1台。台。J5调入运行。调入运行。9:30J5结束。结束。解：解：(1) 作业被调度的先后次序为作业被调度的先后次序为J1, J3, J4, J2, J5(2) 全部作业运行结束的时间为全部作业运行结束的时间为9:30(3) 作业的平均周转时间为作业的平均周转时间为(30+55+40+40+55)5=44 (分钟分钟)(4) 最大作业周转时间为最大作业周转时

16、间为55分钟。分钟。2022-8-8操作系统复习操作系统复习13CPU磁带磁带1磁带磁带2打印机打印机8:008:20J1J1J1J1, J3J38:30J1J1J1结束结束J4J3J2,J3到到J2不入不入J3进入进入J3, J48:35J3, J4J5到达到达J5不入不入9:00J4J3J3结束结束9:10J4结束结束内存余内存余85K25K15, 515, 5J2, J445, 5J4J29:15J2J270KJ2结束结束9:3090KJ5J5J5J5结束结束J1到达到达J1进入进入J4到达到达J2不入不入J4进入进入J2进入进入J5仍不仍不能进入能进入J5进入进入以下是画图分析法：以下

17、是画图分析法：2022-8-8操作系统复习操作系统复习142多道批处理系统中配有一个处理器和多道批处理系统中配有一个处理器和2台外设台外设(D1和和D2)，用，用户存储空间为户存储空间为100MB。已知系统采用可抢占式的高优先数调度。已知系统采用可抢占式的高优先数调度算法和不允许移动的可变分区分配策略，设备分配按照动态分算法和不允许移动的可变分区分配策略，设备分配按照动态分配原则。今有配原则。今有4个作业同时提交给系统，如下表所示。个作业同时提交给系统，如下表所示。作业名作业名优先数优先数运行时间运行时间内存需求内存需求A65分钟分钟50MB34分钟分钟10MC87分钟分钟60MD46分钟分钟

18、20M作业运行时间和作业运行时间和I/O时间按下述顺序进行：时间按下述顺序进行：A. CPU (1分钟分钟)，D1(2分钟分钟)，D2(2分钟分钟)B. CPU (3分钟分钟)，D1(1分钟分钟)C. CPU (2分钟分钟)，D1(3分钟分钟)，CPU(2分钟分钟)D. CPU (4分钟分钟)，D1(2分钟分钟)忽略其他辅助操作，求忽略其他辅助操作，求4个作业的平均周转时间是多少分钟。个作业的平均周转时间是多少分钟。11分钟分钟分析见后页分析见后页2022-8-8操作系统复习操作系统复习15C C D D D C C A D BBBC C CA A D D BA A12345678910 11

19、 12 13CPUD1D2时间时间A的周转时间为的周转时间为12分钟分钟B的周转时间为的周转时间为13分钟分钟C的周转时间为的周转时间为7分钟分钟D的周转时间为的周转时间为12分钟分钟所以平均周转时间为所以平均周转时间为(12+13+7+12)/4=11(分钟分钟)2022-8-8操作系统复习操作系统复习163. 进程进程P1使用缓冲区使用缓冲区buffer向进程向进程P2，P3，P4发送消息，要求每当发送消息，要求每当P1向向buffer中发消中发消息时，只有当息时，只有当P2，P3，P4进程都读取这进程都读取这条消息后才可向条消息后才可向buffer中发送新的消息。中发送新的消息。利用利用

20、P、V原语描述如下图所示进程的动原语描述如下图所示进程的动作序列。作序列。 P1bufferP2P3P42022-8-8操作系统复习操作系统复习17设设P1、P2、P3、P4的资源信号量分别为的资源信号量分别为S1、S2、S3、S4semaphore S1,S2,S3,S4;S1.value=3;S2.vale=S3.vale=S4.value=0; parbeginprocess P1 while (condition) P1生成一个消息；生成一个消息；P（S1）；）；P（S1）；）；P（S1）；）；P1将消息存入缓冲区将消息存入缓冲区buffer；V（S2）；）；V（S3）；）；V（S4）

21、；）； 解解:2022-8-8操作系统复习操作系统复习18process Pi(i=2,3,4) while （condition） P（Si）；）；Pi从从buffer中取出消息；中取出消息；V（S1）；）；Pi消费（使用）该消息；消费（使用）该消息； parend2022-8-8操作系统复习操作系统复习194.有有n个输入进程、个输入进程、m个计算进程和个计算进程和p个输个输出进程，通过循环缓冲区出进程，通过循环缓冲区A和循环缓冲区和循环缓冲区B进行数据传送，如下图所示。进行数据传送，如下图所示。2022-8-8操作系统复习操作系统复习20已知缓冲区已知缓冲区A有有N个缓冲块，缓冲区个缓冲

22、块，缓冲区B有有M个个缓冲块。输入进程每次输入缓冲块。输入进程每次输入1个数据块存入个数据块存入缓冲区缓冲区A的的1个缓冲块中；计算进程每次从个缓冲块中；计算进程每次从缓冲区缓冲区A取出取出1个数据块，处理后的数据块个数据块，处理后的数据块存入缓冲区存入缓冲区B的的1个缓冲块中；输出进程每个缓冲块中；输出进程每次从缓冲区次从缓冲区B中取出中取出1个数据块进行输出操个数据块进行输出操作。试用作。试用P、V操作实现进程间的同步与互操作实现进程间的同步与互斥。斥。2022-8-8操作系统复习操作系统复习21semaphore mutex1, mutex2, empty1, full1, empty2

23、, full2;int in1, out1, in2, out2;mutex1=1;/互斥信号量，用于互斥访问共享变量互斥信号量，用于互斥访问共享变量in1和和out1mutex2=1;/互斥信号量，用于互斥访问共享变量互斥信号量，用于互斥访问共享变量in2和和out2empty1=N;/同步信号量，表示缓冲区同步信号量，表示缓冲区A的空缓冲区个数的空缓冲区个数empty2=M;/同步信号量，表示缓冲区同步信号量，表示缓冲区B的空缓冲区个数的空缓冲区个数full1=0;/同步信号量，表示缓冲区同步信号量，表示缓冲区A的满缓冲区个数的满缓冲区个数full2=0;/同步信号量，表示缓冲区同步信号量

24、，表示缓冲区B的满缓冲区个数的满缓冲区个数in1=out1=in2=out2=0;/共享变量，表示缓冲区的下标变量共享变量，表示缓冲区的下标变量3分分parbeginprocess inputi ( )/n个输入进程，个输入进程，i=1, 2, . , n while (1) 2022-8-8操作系统复习操作系统复习225. 三个吸烟者在一个房间内，还有一个香三个吸烟者在一个房间内，还有一个香烟供应者。为了制造和抽掉香烟，每个吸烟烟供应者。为了制造和抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者者需要三样东西：烟草、纸和火柴，供应者有丰富的货物提供。三个吸烟者中，第一个有丰富的货物提

25、供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者随机地将两样东西放有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒一个供应者再把两样东西放在桌子上，唤醒一个吸烟者。试采用信号量和吸烟者。试采用信号量和P、V操作，编写操作，编写他们同步工作的算法程序。他们同步工作的算法程序。2022-8-8操作系统复习操作系统复习23分析：一个生产者三个消费者的问题。

26、分析：一个生产者三个消费者的问题。可用资源：可用资源：供应者：空闲位置供应者：空闲位置吸烟者吸烟者1：纸和火柴：纸和火柴吸烟者吸烟者2：烟草和火柴：烟草和火柴吸烟者吸烟者3：烟草和纸：烟草和纸因此可以定义因此可以定义4个资源信号量个资源信号量Semaphore S0, S1, S2, S3;S0=1; S1=S2=S3=0;2022-8-8操作系统复习操作系统复习24Process 供应者供应者 While(1) P(S0) ; /测试桌上是否空着测试桌上是否空着 随机地取两样东西随机地取两样东西x, y放在桌子上放在桌子上; if (x, y是纸和火柴是纸和火柴) V(S1);/通知第一个吸

27、烟通知第一个吸烟者者 else if (x, y是烟草和火柴是烟草和火柴) V(S2);/通知第二通知第二个吸烟者个吸烟者 else V(S3);/通知第三个吸烟者通知第三个吸烟者 2022-8-8操作系统复习操作系统复习25Process 吸烟者吸烟者1 while(1) P(S1);/看看供应者是否在桌上放了纸和火看看供应者是否在桌上放了纸和火柴柴 从桌上取纸和火柴从桌上取纸和火柴; 加工香烟加工香烟; 抽烟抽烟; V(S0); / 唤醒供应者唤醒供应者 2022-8-8操作系统复习操作系统复习26process 吸烟者吸烟者2 while(1) P(S2);/看看供应者是否在桌上放了烟草

28、和看看供应者是否在桌上放了烟草和火柴火柴 从桌上取烟草和火柴从桌上取烟草和火柴; 加工香烟加工香烟; 抽烟抽烟; V(S0);/ 唤醒供应者唤醒供应者 2022-8-8操作系统复习操作系统复习27Process 吸烟者吸烟者3 while(1) P(S3);/看看供应者是否在桌上放了烟草和纸看看供应者是否在桌上放了烟草和纸 从桌上取烟草和纸从桌上取烟草和纸; 加工香烟加工香烟; 抽烟抽烟; V(S0); / 唤醒供应者唤醒供应者 parend2022-8-8操作系统复习操作系统复习286. 某银行提供某银行提供1个服务窗口和个服务窗口和10个顾客等待座位。个顾客等待座位。顾客到达银行时，若有空

29、座位，则到取号机领取一顾客到达银行时，若有空座位，则到取号机领取一个号，等待叫号。取号机每次仅允许一位顾客使用个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：其服务。顾客和营业员的活动过程描述如下：cobegin process 顾客顾客i 从取号机获得从取号机获得 一个号码一个号码; 等待叫号等待叫号; 获得服务获得服务; process 营业员营业员 while (TRUE) 叫号叫号; 为顾客服务为顾客服务; 2022-8-8操作系统复习操作系统复习29请添加必要的

30、信号量和请添加必要的信号量和P、V（或（或wait( )、signal( )）操作实现上述过程的互斥和同步。要求写出完整）操作实现上述过程的互斥和同步。要求写出完整的过程，说明信号量的含义并赋初值。的过程，说明信号量的含义并赋初值。分析：分析：semaphore mutex=1;/用于顾客取号的互用于顾客取号的互斥信号量斥信号量semaphore seat=10;/顾客等待座位的资顾客等待座位的资源信号量，当没有空座位时顾客在其上阻塞源信号量，当没有空座位时顾客在其上阻塞semaphore S1=0;/营业员与顾客的同营业员与顾客的同步信号量，当没有顾客时营业员在其上阻塞步信号量，当没有顾客时

31、营业员在其上阻塞semaphore S2=0;/顾客与营业员的同顾客与营业员的同步信号量，等待叫号时顾客在其上阻塞步信号量，等待叫号时顾客在其上阻塞2022-8-8操作系统复习操作系统复习30cobegin process 顾客顾客i P(seat);/若没有空座位，顾客等待若没有空座位，顾客等待P(mutex); /取号互斥取号互斥从取号机获得一个号码从取号机获得一个号码;V(mutex);V(S1); /通知营业员，已有顾客通知营业员，已有顾客P(S2);等待叫号等待叫号;V(seat); / 空出一个座位空出一个座位获得服务获得服务; 2022-8-8操作系统复习操作系统复习31 pro

32、cess 营业员营业员while (TRUE) P(S1);/若无顾客则等待若无顾客则等待V(S2);/唤醒等待叫号的顾客唤醒等待叫号的顾客叫号叫号;为顾客服务为顾客服务; 2022-8-8操作系统复习操作系统复习327. 在一个采用页式虚拟存储管理的系统中，在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序有一用户作业，它依次要访问的字地址序列是：列是：115，228，120，88，446，102，321，432，260，167，若该作业的第，若该作业的第0页已页已经装入主存，现分配给该作业的主存共经装入主存，现分配给该作业的主存共300字，页的大小为字，页的大小为10

33、0字，请回答下列问题：字，请回答下列问题：(1)按按FIFO调度算法，将产生多少次缺页中断？调度算法，将产生多少次缺页中断？依次淘汰的页号是什么？缺页中断率为多依次淘汰的页号是什么？缺页中断率为多少？少？(2)按按LRU调度算法，将产生多少次缺页中断？调度算法，将产生多少次缺页中断？依次淘汰的页号是什么？缺页中断率为多依次淘汰的页号是什么？缺页中断率为多少？少？2022-8-8操作系统复习操作系统复习338. 某进程页面访问序列为某进程页面访问序列为4,3,2,1,4,3,5,4,3,2,1,5，且开始时内存中没有页面，分配给该进程的物且开始时内存中没有页面，分配给该进程的物理块数是理块数是3

34、。则采用。则采用FIFO页面置换算法是缺页页面置换算法是缺页率是率是_，采用，采用LRU页面置换算法时缺页率页面置换算法时缺页率是是_。页面走向页面走向432143543215第第1块块444111555555第第2块块33344444222第第3块块22233333311缺页标记缺页标记FIFOFIFO置换算法，其页面访问过程置换算法，其页面访问过程缺页缺页9次，缺页率为次，缺页率为9/12=75%2022-8-8操作系统复习操作系统复习34页面走向页面走向432143543215第第1块块444111555222第第2块块33344444411第第3块块2223333335缺页标记缺页标记

35、LRULRU置换算法，其页面访问过程置换算法，其页面访问过程缺页缺页10次，缺页率为次，缺页率为10/12=83.3%【注意注意】通常认为通常认为LRU算法比算法比FIFO算法性能好，算法性能好，但不能一概而论。但不能一概而论。页面置换次数、缺页次数、缺页率的区别。页面置换次数、缺页次数、缺页率的区别。对上述问题，考虑时钟对上述问题，考虑时钟(Clock)(Clock)算法。算法。2022-8-8操作系统复习操作系统复习35页面走向页面走向432143543215第第1块块4*4*4*1*1*1*5*5*5*555*第第2块块3*3*34*4*44*4*2*2*2*第第3块块2*223*333

36、*31*1*缺页标记缺页标记ClockClock置换算法，其页面访问过程置换算法，其页面访问过程缺页缺页10次，缺页率为次，缺页率为9/12=75%2022-8-8操作系统复习操作系统复习369请求分页管理系统中，假设某进程的页表内容如下表所请求分页管理系统中，假设某进程的页表内容如下表所示。示。页表内容页表内容 页号页号页框页框(Page frame)号号有效位（存在位）有效位（存在位）0101H1102254H1页面大小为页面大小为4KB，一次内存的访问时间是，一次内存的访问时间是100ns，一次快表，一次快表(TLB)的访问时间是的访问时间是10ns，处理一次缺页的平均时间为，处理一次缺

37、页的平均时间为108ns(已含更新已含更新TLB和页表的时间和页表的时间)，进程的驻留集大小固定，进程的驻留集大小固定为为2，采用最近最少使用置换算法，采用最近最少使用置换算法(LRU)和局部淘汰策略。假和局部淘汰策略。假设设TLB初始为空；地址转换时先访问初始为空；地址转换时先访问TLB，若，若TLB未命未命中，在访问页表中，在访问页表(忽略访问页表之后的忽略访问页表之后的TLB更新时间更新时间)；有效；有效位为位为0表示页面不再内存，产生缺页中断，缺页中断后，返回表示页面不再内存，产生缺页中断，缺页中断后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列到产生缺页中断的指令处重新执行

38、。设有虚地址访问序列2362H、1565H、25A5H，请问：，请问：2022-8-8操作系统复习操作系统复习37(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。依次访问上述三个虚地址，各需多少时间？给出计算过程。(2) 基于上述访问序列，虚地址基于上述访问序列，虚地址1565H的物理地址是多少？请的物理地址是多少？请说明理由。说明理由。分析：考察点地址转换的过程分析：考察点地址转换的过程 快表命中：快表命中：快表访问时间快表访问时间 + 一次内存访问时间一次内存访问时间 快表未命中但未缺页：快表未命中但未缺页：快表访问时间快表访问时间+二次内存访问时间二次内存访问时间（一次页表访

39、问，一次实际地址访问）（一次页表访问，一次实际地址访问） 快表未命中且存在缺页：快表未命中且存在缺页：快表访问时间快表访问时间+二次内存访问时间二次内存访问时间+缺页处理时间缺页处理时间2022-8-8操作系统复习操作系统复习38(1) 因页的大小为因页的大小为4KB，即，即212，故十六进制地址的低，故十六进制地址的低3位是页位是页内偏移，高位是页号。内偏移，高位是页号。2362H：页号：页号P=2，访问快表，访问快表10ns，因初始为空，访问页表，因初始为空，访问页表100ns得到页框号，与页内偏移合成物理地址后访问内存得到页框号，与页内偏移合成物理地址后访问内存100ns，共花时间，共花

40、时间10+100+100=210ns。1565H：P=1，访问快表，访问快表10ns，落空，访问页表，落空，访问页表100ns缺页，缺页，进行缺页中断处理进行缺页中断处理108ns，合成物理地址后访问内存，合成物理地址后访问内存100ns，共计共计10+100+108+100=318ns。25A5H：P=2，访问快表，访问快表10ns命中，合成物理地址后访问内命中，合成物理地址后访问内存存100ns，共计，共计110ns。(2)故访问故访问1565H时，因在此之前刚刚访问时，因在此之前刚刚访问2362H所在的所在的2号页，号页，按按LRU算法，应淘汰算法，应淘汰0号页，空出号页，空出101H号

41、页框存放逻辑地址号页框存放逻辑地址1565H所在的所在的1号页。由页框号号页。由页框号101H和页内偏移和页内偏移565H合成得合成得到虚地址到虚地址1565H对应的物理地址为对应的物理地址为101565H。2022-8-8操作系统复习操作系统复习3910(2010全国试题全国试题)设某计算机的逻辑地址空间和物理地址空设某计算机的逻辑地址空间和物理地址空间均为间均为64KB，按字节编址。若某进程最多需要，按字节编址。若某进程最多需要6页页(Page)数据数据存储空间，页的大小为存储空间，页的大小为1KB，操作系统采用固定分配局部置换，操作系统采用固定分配局部置换策略为此进程分配策略为此进程分配

42、4个页框个页框(Page Frame)。在时刻。在时刻260前的该进前的该进程访问情况如下表所示程访问情况如下表所示(访问位即使用位访问位即使用位)。 页号页号页框号页框号装入时间装入时间访问位访问位071301142301222001391601当进程执行到时刻当进程执行到时刻260时，要访问逻辑地址为时，要访问逻辑地址为17CAH的数据。的数据。请回答下列问题：请回答下列问题：（1）该逻辑地址的对应的页号是多少？）该逻辑地址的对应的页号是多少？（2）若采用先进先出）若采用先进先出(FIFO)置换算法，该逻辑地址对应的物置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。理地址是多少

43、？要求给出计算过程。2022-8-8操作系统复习操作系统复习40（3）若采用时钟）若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程地址是多少？要求给出计算过程(设搜索下一页的指针沿顺时设搜索下一页的指针沿顺时针方向移动，且当前指向针方向移动，且当前指向2号页框，示意图如下号页框，示意图如下)。 0号页号页1号页号页2号页号页3号页号页2号页框号页框4号页框号页框7号页框号页框9号页框号页框2022-8-8操作系统复习操作系统复习41(1) 17CAH=0001 0111 1100 1010B，表示页号的位是左边，表示页号的位是左边

44、6位，位，即即00101B，所以页号为，所以页号为5。(2) 根据根据FIFO算法，需要替换装入时间最早的页，故需要置算法，需要替换装入时间最早的页，故需要置换装入时间最早的换装入时间最早的0号页，即将号页，即将5页装入页装入7号页框中，所以号页框中，所以物理地址为物理地址为0001 1111 1100 1010B，换算成十六进制，为，换算成十六进制，为1FCAH。(3) 根据根据CLOCK算法，如果当前指针所指页框的使用位为算法，如果当前指针所指页框的使用位为0，则替换该页；否则将其使用位清零，并将指针指向下一则替换该页；否则将其使用位清零，并将指针指向下一个页框，继续查找。根据题设和示意图

45、，将从个页框，继续查找。根据题设和示意图，将从2号页框开号页框开始，前始，前4次查找页框顺序为次查找页框顺序为2479，并将对应页框的，并将对应页框的使用位清零。在第使用位清零。在第5次查找中，指针指向次查找中，指针指向2号页框，因号页框，因2号号页框的使用位为页框的使用位为0，故淘汰，故淘汰2号页框对应的号页框对应的2号页，把号页，把5号号页装入页装入2号页框中，并将对应的使用位置为号页框中，并将对应的使用位置为1，所以对应，所以对应的物理地址为的物理地址为0000 1011 1100 1010B，换算成十六进制，换算成十六进制，为为0BCAH。2022-8-8操作系统复习操作系统复习421

46、1用银行家算法考虑下列系统状态用银行家算法考虑下列系统状态 ：进程进程 分配矩阵分配矩阵 最大需求矩阵最大需求矩阵 资源总数矩阵资源总数矩阵 A 3 0 1 1 4 1 1 1 6 3 4 2 B 0 1 0 0 0 2 1 2 C 1 1 1 0 4 2 1 0 D 1 1 0 1 1 1 1 1 E 0 0 0 0 2 1 1 0问：问：(1)此时系统是否安全？为什么？此时系统是否安全？为什么？(2)若进程若进程B请求请求(0,0,1,0)，可否立即分配？，可否立即分配？(3)此后进程此后进程E也请求也请求(0,0,1,0)，可否分配给它？，可否分配给它？2022-8-8操作系统复习操作系

47、统复习43解：解：(1) 由已知条件可得由已知条件可得Need和和Avaiable矩阵如下：矩阵如下：进程进程 Allication Need Avaiable A 3 0 1 1 1 1 0 0 1 0 2 0 B 0 1 0 0 0 1 1 2 C 1 1 1 0 3 1 0 0 D 1 1 0 1 0 0 1 0 E 0 0 0 0 2 1 1 0利用银行家算法对此时刻的资源分配情况进行分析如下表：利用银行家算法对此时刻的资源分配情况进行分析如下表：从上述分析可知，存在一个安全序列从上述分析可知，存在一个安全序列D，A，B，C，E，故，故当前系统是安全的。当前系统是安全的。进程WorkN

48、eedAllocationWork+Alloc.FinishD1 0 2 00 0 1 01 1 0 12 1 2 1trueA2 1 2 11 1 0 03 0 1 15 1 3 2trueB5 1 3 20 1 1 20 1 0 05 2 3 2trueC5 2 3 23 1 0 01 1 1 06 3 4 2trueE6 3 4 22 1 1 00 0 0 06 3 4 2true2022-8-8操作系统复习操作系统复习44解：解：(2) 由已知条件可得由已知条件可得Need和和Avaiable矩阵如下：矩阵如下：进程进程 Allication Need Avaiable A 3 0 1

49、 1 1 1 0 0 1 0 1 0 B 0 1 1 0 0 1 0 2 C 1 1 1 0 3 1 0 0 D 1 1 0 1 0 0 1 0 E 0 0 0 0 2 1 1 0利用银行家算法对此时刻的资源分配情况进行分析如下表：利用银行家算法对此时刻的资源分配情况进行分析如下表：从上述分析可知，存在安全序列从上述分析可知，存在安全序列D，A，B，C，E，故系统，故系统仍是否安全的，因此可以立即分配。仍是否安全的，因此可以立即分配。进程WorkNeedAllocationWork+Alloc.FinishD1 0 2 00 0 1 01 1 0 12 1 2 1trueA2 1 2 11 1

50、 0 03 0 1 15 1 3 2trueB5 1 3 20 1 1 20 1 0 05 2 3 2trueC5 2 3 23 1 0 01 1 1 06 3 4 2trueE6 3 4 22 1 1 00 0 0 06 3 4 2true2022-8-8操作系统复习操作系统复习45解：解：(3) 由已知条件可得由已知条件可得Need和和Avaiable矩阵如下：矩阵如下：进程进程 Allication Need Avaiable A 3 0 1 1 1 1 0 0 1 0 0 0 B 0 1 1 0 0 1 0 2 C 1 1 1 0 3 1 0 0 D 1 1 0 1 0 0 1 0 E