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

《操作系统复习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统复习题ppt课件.ppt（67页珍藏版）》请在三一办公上搜索。

1、操作系统复习,南京工业大学信息学院计算机系,2022/11/12,操作系统复习,2,一、单项选择题每题2分，共60分。二、应用题每题10分，共40分。应用题类型：,进程互斥、同步；处理机调度；死锁问题；地址重定位；,页面置换算法；磁盘调度；文件物理结构；目录管理；外存空间的管理等。,2022/11/12,操作系统复习,3,一、选择题,1下列选项中，操作系统提供给应用程序的接口是 。 A系统调用B中断 C库函数D原语 2下列选项中，导致创建新进程的操作是 。I用户登录成功II设备分配 III启动程序执行 A仅I和IIB仅II和III C仅I和IIIDI、II和III 3下列选项中，降低进程优先级

2、的合理时机是 。 A进程的时间片用完 B进程刚完成I/O，进入就绪队列 C进程长期处于就绪队列中 D进程从就绪队列转为运行状态,A,C,A,2022/11/12,操作系统复习,4,4设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则M、N分别是 。A0、1B1、0C1、2D2、0 5某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用最佳适配(Best Fit)算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是 。A7MBB9MBC10MBD15MB 6设

3、置当前工作目录的主要目的是 。A节省外存空间B节省内存空间C加快文件的检索速度D加快文件的读/写速度,B,B,C,2022/11/12,操作系统复习,5,7下列选项中，能引起外部中断的事件是_。 A键盘输入B除数为0 C浮点运算下溢D访存缺页 8某计算机系统中有8台打印机，有k个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的k的最小值是_。 A2B3C4D59一个分段存储管理系统中，地址长度32位，其中段号占8位，则最大段长是_。A2的8次方字节B2的16次方字节C2的21次方字节D2的32次方字节,A,C,C,2022/11/12,操作系统复习,6,10下列文件物理结构中，

4、适合随机访问且易于文件扩展的是_。 A连续结构 B索引结构 C链式结构且磁盘块定长 D链式结构且磁盘块变长11设文件F1当前引用计数值为1，先建立F1的符号链接(软链接)文件F2，再建立F1的硬软链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是_。 A0、1B1、1C1、2D2、1 12单处理机系统中，能并行的是_。I. 进程与进程II. 处理机与设备III. 处理机与通道IV. 设备与设备 AI、II和IIIBI、II和IV CI、III和IVDII、III和IV,B,B,D,2022/11/12,操作系统复习,7,13下列进程调度算法中，综合考虑进程等待时间和执行时间的是_。

5、A时间片轮转调度算法 B短进程优先调度算法C先来先服务调度算法 D高响应比优先调度算法 14多道程序系统中，当 时，进程从执行状态转变为就绪状态。 A. 进程被进程调度程序选中 B. 时间片到 C. 等待某一事件 D. 等待的事件发生 15下述各项中， 不是引起进程切换的直接原因。运行进程的时间片用完B. 运行进程出错C. 运行进程要等待某一事件发生D. 有新进程进入就绪状态,D,B,D,2022/11/12,操作系统复习,8,16在支持多线程的系统中，进程P创建的若干线程不能共享的是 。A进程P的代码段B进程P中打开的文件C进程P的全局变量D进程P中某线程的栈指针17在缺页处理过程中，操作系

6、统执行的操作可能是 。修改页表磁盘I/O 分配页框A仅、B仅C仅D、和 18下列选项中，在用户态执行的是 。A命令解释程序B缺页处理程序C进程调度程序D时钟中断处理程序,2022/11/12,操作系统复习,9,19有两个并发进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。,两个操作完成后，x的值 。A可能为-1或3B只能为1C可能为0、1或2D可能为-1、0、1或2,2022/11/12,操作系统复习,10,1某多道程序设计系统供用户使用的主存为100KB，磁带机2台，打印机1台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作

7、业的I/O时间。现有如下作业序列：,二、应用题,作业调度采用FCFS策略，优先分配主存低地址区域且不准移动已在主存中的作业，进程调度采用时间片轮转算法(即在主存中的作业均分CPU时间)。现求：,2022/11/12,操作系统复习,11,(1) 作业被调度的先后次序；(2) 全部作业运行结束的时间；(3) 作业的平均周转时间；(4) 最大作业周转时间。,先在草稿上分析如下：8:00J1到达，分配它所需资源(15KB内存、 1台磁带机、1台打印机后，调入内存运行。余内存85KB、磁带机1台。8:20J2到达，因无打印机，不调入。同时J3到达，分配它内存60KB，磁带机1台，调入内存，与J1均分CP

8、U时间运行。余内存25KB、磁带机和打印机都已分完(余0台)。8:30J1结束，释放内存15KB、磁带机1台、打印机1台。虽有打印机但内存不够，J2仍不能调入；J4到达，因低端内存15KB不够，分配高端内存20KB和磁带机1台，调入内存与J3一起运行。剩下内存空闲块是15KB、5KB，打印机1台8:35J5到达，因无磁带机，不能调入。,2022/11/12,操作系统复习,12,9:00J3结束。释放资源后，系统有内存75KB，5KB、打印机和磁带机个1台。J2调入，内存余45KB，5KB、磁带机剩1台、打印机0台。J5仍不能进入(无打印机)。将J2、J4运行。J4还需运行5分钟。9:10J4结

9、束，释放资源后，内存空余70KB、磁带机空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) 最大作业周转时间为55分钟。,2022/11/12,操作系统复习,13,CPU,磁带1,磁带2,打印机,8:00,8:20,J1,J1,J1,J1, J3,J3,8:30,J1,J1,J1结

10、束,J4,J3,J2,J3到J2不入J3进入,J3, J4,8:35,J3, J4,J5到达J5不入,9:00,J4,J3,J3结束,9:10,J4结束,内存余,85K,25K,15, 5,15, 5,J2, J4,45, 5,J4,J2,9:15,J2,J2,70K,J2结束,9:30,90K,J5,J5,J5,J5结束,J1到达J1进入,J4到达J2不入J4进入,J2进入,J5仍不能进入,J5进入,以下是画图分析法：,2022/11/12,操作系统复习,14,2多道批处理系统中配有一个处理器和2台外设(D1和D2)，用户存储空间为100MB。已知系统采用可抢占式的高优先数调度算法和不允许移

11、动的可变分区分配策略，设备分配按照动态分配原则。今有4个作业同时提交给系统，如下表所示。,作业运行时间和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/11/12,操作系统复习,15,CPU,D1,D2,时间,A的周转时间为12分钟B的周转时间为13分钟C的周转时间为7分钟D的周转时间为12分钟所以平均周转时间为(12+13+7+12)/

12、4=11(分钟),2022/11/12,操作系统复习,16,进程P1使用缓冲区buffer向进程P2，P3，P4发送消息，要求每当P1向buffer中发消息时，只有当P2，P3，P4进程都读取这条消息后才可向buffer中发送新的消息。利用P、V原语描述如下图所示进程的动作序列。,2022/11/12,操作系统复习,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生成一个消息

13、；P（S1）；P（S1）；P（S1）；P1将消息存入缓冲区buffer；V（S2）；V（S3）；V（S4）； ,解:,2022/11/12,操作系统复习,18,rocess Pi(i=2,3,4) while （condition） P（Si）；Pi从buffer中取出消息；V（S1）；Pi消费（使用）该消息； parend,2022/11/12,操作系统复习,19,有n个输入进程、m个计算进程和p个输出进程，通过循环缓冲区A和循环缓冲区B进行数据传送，如下图所示。,2022/11/12,操作系统复习,20,已知缓冲区A有N个缓冲块，缓冲区B有M个缓冲块。输入进程每次输入1个数据块存入缓冲区A

14、的1个缓冲块中；计算进程每次从缓冲区A取出1个数据块，处理后的数据块存入缓冲区B的1个缓冲块中；输出进程每次从缓冲区B中取出1个数据块进行输出操作。试用P、V操作实现进程间的同步与互斥。,2022/11/12,操作系统复习,21,2022/11/12,操作系统复习,22,5. 三个吸烟者在一个房间内，还有一个香烟供应者。为了制造和抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在

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

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

17、供应者是否在桌上放了烟草和纸 从桌上取烟草和纸; 加工香烟; 抽烟; V(S0);/ 唤醒供应者 parend,2022/11/12,操作系统复习,28,6. 某银行提供1个服务窗口和10个顾客等待座位。顾客到达银行时，若有空座位，则到取号机领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：,cobegin process 顾客i 从取号机获得 一个号码; 等待叫号; 获得服务; ,rocess 营业员 while (TRUE) 叫号; 为顾客服务; ,2022/11/12,操作系统复习,29,请添加必要的信号

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

19、取号互斥从取号机获得一个号码;V(mutex);V(S1); /通知营业员，已有顾客P(S2);等待叫号;V(seat); / 空出一个座位获得服务; ,2022/11/12,操作系统复习,31,rocess 营业员while (TRUE)P(S1);/若无顾客则等待V(S2);/唤醒等待叫号的顾客叫号;为顾客服务; ,2022/11/12,操作系统复习,32,在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字

20、，请回答下列问题：(1)按FIFO调度算法，将产生多少次缺页中断？依次淘汰的页号是什么？缺页中断率为多少？(2)按LRU调度算法，将产生多少次缺页中断？依次淘汰的页号是什么？缺页中断率为多少？,2022/11/12,操作系统复习,33,某进程页面访问序列为4,3,2,1,4,3,5,4,3,2,1,5，且开始时内存中没有页面，分配给该进程的物理块数是3。则采用FIFO页面置换算法是缺页率是_，采用LRU页面置换算法时缺页率是_。,FIFO置换算法，其页面访问过程,缺页9次，缺页率为9/12=75%,2022/11/12,操作系统复习,34,LRU置换算法，其页面访问过程,缺页10次，缺页率为1

21、0/12=83.3%,【注意】通常认为LRU算法比FIFO算法性能好，但不能一概而论。,页面置换次数、缺页次数、缺页率的区别。,对上述问题，考虑时钟(Clock)算法。,2022/11/12,操作系统复习,35,Clock置换算法，其页面访问过程,缺页10次，缺页率为9/12=75%,2022/11/12,操作系统复习,36,9请求分页管理系统中，假设某进程的页表内容如下表所示。页表内容,页面大小为4KB，一次内存的访问时间是100ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(

22、LRU)和局部淘汰策略。假设TLB初始为空；地址转换时先访问TLB，若TLB未命中，在访问页表(忽略访问页表之后的TLB更新时间)；有效位为0表示页面不再内存，产生缺页中断，缺页中断后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：,2022/11/12,操作系统复习,37,(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。(2) 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。,分析：考察点地址转换的过程 快表命中：快表访问时间 + 一次内存访问时间 快表未命中但未缺页：快表访问时间+二次内存访问时间（一次页表访问，

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

24、，合成物理地址后访问内存100ns，共计110ns。(2)故访问1565H时，因在此之前刚刚访问2362H所在的2号页，按LRU算法，应淘汰0号页，空出101H号页框存放逻辑地址1565H所在的1号页。由页框号101H和页内偏移565H合成得到虚地址1565H对应的物理地址为101565H。,2022/11/12,操作系统复习,39,10(2010全国试题)设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框(Page Frame)。在时刻260前的该进程访问情况如下

25、表所示(访问位即使用位)。,当进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：（1）该逻辑地址的对应的页号是多少？（2）若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。,2022/11/12,操作系统复习,40,（3）若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程(设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下)。,2022/11/12,操作系统复习,41,(1) 17CAH=0001 0111 1100 1010B，表示页号的位是左边6位，即00101B，所以页号为5。根据

26、FIFO算法，需要替换装入时间最早的页，故需要置换装入时间最早的0号页，即将5页装入7号页框中，所以物理地址为0001 1111 1100 1010B，换算成十六进制，为1FCAH。根据CLOCK算法，如果当前指针所指页框的使用位为0，则替换该页；否则将其使用位清零，并将指针指向下一个页框，继续查找。根据题设和示意图，将从2号页框开始，前4次查找页框顺序为2479，并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位为0，故淘汰2号页框对应的2号页，把5号页装入2号页框中，并将对应的使用位置为1，所以对应的物理地址为0000 1011 1100 1010B，换算成十六

27、进制，为0BCAH。,2022/11/12,操作系统复习,42,11用银行家算法考虑下列系统状态 ：进程 分配矩阵 最大需求矩阵 资源总数矩阵 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/11/12,操作系统复习,43,解：(1) 由已知条件可得Need和Avaiable矩阵如下：进程 All

28、ication 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，故当前系统是安全的。,2022/11/12,操作系统复习,44,解：(2) 由已知条件可得Need和Avaiable矩阵如下：进程 Allication Need Avaiable A 3 0 1 1 1 1 0 0 1 0 1 0 B 0 1 1 0 0

29、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，故系统仍是否安全的，因此可以立即分配。,2022/11/12,操作系统复习,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 0 0 1 0 2

30、 1 0 0此时系统剩余资源（1，0，0，0）已不能满足任何进程的需求，即已找不到一个安全序列，系统状态将变为不安全，故不能分配给E。,2022/11/12,操作系统复习,46,12假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。（1）请说明在上述条件下如何进行磁盘块空闲状态的管理。（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动(如下图所示)，磁道号请求队列为50,90,30,120，对请求队列中的每一个磁道需读取1

31、个随机分布的扇区，则读完这4个扇区总共需要多少时间？给出计算过程。,2022/11/12,操作系统复习,47,磁头当前运动方向,0号磁道,随机分布的某扇区,100号磁道,（3）如果将磁盘替换为随机访问的Flash半导体存储器(如U盘、SSD等)，是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。,2022/11/12,操作系统复习,48,解：(1) 用位图表示磁盘的空闲块状态。每一位表示一个磁盘块的空闲状态，共需16384/32= 512个字=5124个字节=2KB，正好可放在系统提供的内存中。(2) 采用CSCAN调度算法，访问磁道的顺序为120

32、,30,50,90，则移动磁道长度为20+90+20+40= 170，总的移动时间为1701ms=170ms。由于转速为6000r/m，则平均旋转延迟时间为60/(60002)1000ms=5ms，总的旋转时间为5ms4=20ms。由于转速为6000r/m，则读取一个磁道上的一个扇区的平均读取时间为10ms/100=0.1ms，总的读取扇区的时间=0.1ms4=0.4ms。读取上述磁道上的所有4个扇区所花费的总时间=170ms+20ms+0.4ms=190.4ms。(3) 采用FCFS(先来先服务)调度策略更高效。因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按I/O

33、请求的先后顺序服务。,2022/11/12,操作系统复习,49,假设用户甲要用到文件A、B、C、E，用户乙要用到文件A、D、E、F。已知：用户甲的文件A与用户乙的文件A实际上不是同一文件；用户甲与用户乙又分别用文件名C和F共享同一文件；甲、乙两用户的文件E是同一个文件。请回答下列问题：,系统应采用怎样的目录结构才能使两用户在使用文件时不致于造成混乱？ 画出这个目录结构。 两个用户使用了几个共享文件？写出它们的文件名。,2022/11/12,操作系统复习,50,答：(1) 系统应采用二级或多级目录结构才能使两用户在使用文件时不致于造成混乱。 (2) (3) 两个用户使用了2个共享文件，一个是用户

34、甲的C和用户乙的F，另一个是用户甲的E与用户乙的E。,2022/11/12,操作系统复习,51,考虑一个存在于磁盘上的文件系统，其中的文件由大小为512B的逻辑块组成。假定每一个文件有一个文件目录项，该目录项包含该文件的文件名、文件长度以及第一块（或第一索引块）和最后一块的位置，而且该目录项位于内存。对于索引结构文件，该目录项指明第一索引块，该索引块又一次指向511个文件块（每个索引值占4B），且有一指向下一索引块的指针(指针占4B)。针对连续、链接、索引结构的每一种，如果当前位于逻辑块30（即之前最后一次访问的块是逻辑块30）且希望访问逻辑块20(假设逻辑块号从0开始编号)，那么，必须分别从

35、磁盘上读多少个物理块？,2022/11/12,操作系统复习,52,解：(1) 对于磁盘上的连续结构文件，由文件的逻辑块号、文件块大小、磁盘物理块大小以及文件的首块位置，可以计算该逻辑块所在的物理块号（地址）A：A=A0+(N*L)/S=A0+20*512/2048= A0+5其中：A0为文件第0块位置， N为逻辑块号(N=20)， L为逻辑块长度(L=512)， S为磁盘块长度 (由已知条件得S=511*4+1*4=2048)。因此，无论当前读写位置如何，要访问第20个逻辑块，只要直接读出文件的第6个物理块，即只需读1个磁盘块即可(因目录项已在内存)。,2022/11/12,操作系统复习,53

36、,(2) 对于磁盘上的链接结构文件，当前读写了逻辑块30，要访问逻辑块20，需要从文件开头开始。由前面分析知，磁盘块大小2048B，故每个盘块可存放4个逻辑块。逻辑块20在文件的第6个物理块中，因此需依次读出第1、2、3、4、5等盘块，从第5个物理块获得第6个物理块的块号，在读出第6物理块，其开头的512B即是20号逻辑块的内容。所以，需读6个物理块。 (3)对于磁盘上的索引结构文件，若要访问逻辑块20（假定此前在访问逻辑块30时已将索引块保存在内存），可在内存中的索引表中查到逻辑块20所在的第6个物理块号，再将该物理块读出来，其开头512B即是20号逻辑块的内容。因此需要读1个物理块。,20

37、22/11/12,操作系统复习,54,16.某系统有A、B、C、D这4类资源供5个进程共享，进程对资源的需求和分配情况如下表所示。现在系统中A、B、C、D类资源分别还剩1、5、2、0个，请按银行家算法回答下列问题：,(1) 现在系统是否处于安全状态? 为什么？(2) 如果现在进程P2提出需要(0，4，2，0)个资源的请求， 系统能否满足它的请求？为什么？,2022/11/12,操作系统复习,55,若递交给磁盘驱动程序的磁盘柱面请求按到达时间顺序分别是10、22、20、2、40、6和38，设磁头初始处于20柱面，磁头从一柱面移到另一相邻柱面的时间是2ms，则对于FCFS、最近柱面优先、电梯算法（

38、初始磁头向高柱面移动），平均定位时间各为多少？,2022/11/12,操作系统复习,56,解：对于FCFS，服务顺序为10、22、20、2、40、6、38 平均定位时间=(10+12+2+18+38+34+32)*2/7=41.71ms对于最短寻道时间优先，服务顺序为：20、22、10、6、2、38、40平均定位时间=(0+2+12+4+4+36+2)*2/7=17.14ms对于电梯算法，服务顺序为：20、22、38、40、10、6、2平均定位时间=(0+2+16+2+30+4+4)*2/8=16.57ms,2022/11/12,操作系统复习,57,在某一采用固定分配局部置换策略的请求分页系统

39、中，有一进程逻辑地址空间有10个页，分得了4个页框，每页的装入时间、最后访问时间、访问位R如下表所示(时间用时钟点数表示)。,假设页的大小为4KB(4096B)，当进程执行到时刻300时，要访问逻辑地址6AB8H的数据，请回答下列问题：,2022/11/12,操作系统复习,58,（1）若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（2）若采用最近最久未使用(LRU)页面置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（3）若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程(设搜索下一页的指针沿顺时针方向移动，且

40、当前指向2号页，示意图如下)。,0号页,1号页,2号页,3号页,260号页框,120号页框,100号页框,300号页框,2022/11/12,操作系统复习,59,解：（1）因页的大小为4KB，故逻辑地址6AB8H的页内偏移为0AB8H，页号为6。该逻辑地址所在的页不在内存，产生缺页中断，又因已无空闲页框，故需页面置换。采用先进先出(FIFO)置换算法，由已知条件知2号页最先装入内存，将被置换，其所在的页框号是260，即104H，将104H与页内偏移0AB8H合成，即得到物理地址104AB8H。（2）采用最近最久未使用(LRU)页面置换算法，因1号页是最久没有访问的，将被置换，其所在的页框号是1

41、20，即78H，将其与页内偏移0AB8H合成，得到物理地址78AB8H。（3）采用时钟(CLOCK)置换算法，因0号页的访问位是0，将被置换，其所在的页框号是100，即64H，将其与页内偏移0AB8H合成，得到物理地址64AB8H。,2022/11/12,操作系统复习,60,19假定某系统当时的资源分配图如下所示：,题19图,（1）分析当时系统是否存在死锁。（2）若进程P3再申请R3时，系统将发生什么变化，说明原因。,2022/11/12,操作系统复习,61,解：(1) 因为当时系统的资源分配图中不存在环路所以不存在死锁。(2) 当进程P3申请资源R3后，资源分配图中形成环路P2R2P3R3P

42、2，而R2,R3都是单个资源的类，该环路无法消除，所以进程P2，P3永远处于等待状态从而引起死锁。,2022/11/12,操作系统复习,62,20设某计算机系统有1台输入机，1台打印机。现有2道程序同时投入运行，且程序A先开始运行，程序B后运行。程序A的运行轨迹为：计算50ms，打印100ms，再计算50ms，打印信息100ms，结束。程序B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试说明：（1）两道程序运行时，CPU有无空闲等待？若有，在哪段时间等待？为什么？（2）程序A、B运行时有无等待现象？若有，在什么时候发生等待现象？,【注】本题属于其他类型题。,2022/

43、11/12,操作系统复习,63,解：(1)我们可以画出CPU的运行轨迹图如下图粗线所示。,0,50,100,150,200,A打印,300,ms,A,B,A打印,B输入,从上图可以看出，CPU有等待时间，在100ms到150ms之间，共空闲50ms。在这段时间，A等待打印完成，B等待输入数据，CPU无事可做。（2）程序A无等待现象；程序B有等待现象，在050ms之间以及180ms200ms之间等待CPU。,2022/11/12,操作系统复习,64,一个32位地址的计算机系统使用二级页表，虚地址分为10位顶级页表，10位二级页表，其余是页内偏移。,试问：,(1) 页面长度是多少？(2) 虚拟地址

44、空间有多少个页面？,答: (1) 32位地址，顶级页表与二级页表个10位，因此，页内地址为：32-10-10=12位。即页面长度为：212=4096字节=4KB（2）页面数为：10241024=220项,2022/11/12,操作系统复习,65,答: 表项个数: 210/2=29二级页表页数: 216/29 = 27 = 128,21 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节，页表项大小为2字节，逻辑地址结构为：页目录号 页号 页内偏移量，逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是 。A64 B128 C256 D512,B

45、,2022/11/12,操作系统复习,66,22在页式虚存管理系统中，假定驻留集为m个页面（初始所有页帧均为空），在长为p的引用串中具有n个不同的页号(nm)，对于FIFO、LRU两种页面置换算法，试给出页故障数的上限和下限，说明理由，并举例说明。,答：对于FIFO，页故障数的上限是p，下限是n。因为FIFO淘汰掉先进来的页，而不管其页面以后是否还会用到。在极端情况下，可能刚淘汰的页又接着要使用。故页故障数上限为p；而不同的页至少有一次页故障，故下限是n。,2022/11/12,操作系统复习,67,对于LRU，页故障数的上限是p，下限是n。因为同样可能刚淘汰的页又接着要使用。故页故障数上限为p；而不同的页至少有一次页故障，故下限是n。例如，对于页面引用串：0，1，2，3，0，1，2，分配的内存块数为3。n=4，p=7，m=3，由页面置换图易知，采用FIFO和LRU页面置换算法，其页故障数皆为7(即为上限p)。又如，对于页面引用串：0，1，2，3，1，2，3，分配的内存块数为3。n=4，p=7，m=3，由页面置换图易知，采用FIFO和LRU页面置换算法，其页故障数皆为4 (即下限为n) 。,