操作系统复习题

一、 单项选择题现代操作系统的基本特征是(C)、资源共享和操作的异步性。A.多道程序设计

B.中断处理

C.程序并发执行

D.实现分时和实时处理在页式虚拟存储管理中，为实现地址变换，应建立（C）P157A．空闲区表 B．分区分配表 C．页表 D．移动表SPOOL技术用于（C）A.处理器管理 B.存储管理C.设备管理 D.文件管理在可变分区分配方案中，在空闲区表中以空闲区长度按递减顺序排列适合于（A）A．最坏适应算法B．最先适应算法C．最优适应算法 D．首次循环适应算法用户程序发出磁盘I/O请求后，系统的正确处理流程是（B）A．用户程序→系统调用处理程序→中断处理程序→设备驱动程序B．用户程序→系统调用处理程序→设备驱动程序→中断处理程序C．用户程序→设备驱动程序→系统调用处理程序→中断处理程序D．用户程序→设备驱动程序→中断处理程序→系统调用处理程序从磁盘读取数据的下列时间中，对系统效率影响最大的是(D)A．处理时间 B．传输时间 C．延迟时间 D．寻道时间以下关于进程的并发执行描述正确的是（A）A.多个进程在某个时间段内轮流占用处理器执行B.多个进程在某个时刻同时占用处理器执行C.单处理器的系统也允许进程并发执行 D.只有多处理器的系统才能允许进程并发执行造成某进程状态从就绪态转变成运行态的原因是（D）A．上次分配给该进程的处理器时间太短 B．有更高优先级的进程要运行C．该进程需要更多的处理器时间运行 D．该进程被进程调度程序选中以下存储管理技术中，可以实现虚拟存储器的技术是（D）A．单用户连续存储管理 B．固定分区存储管理C．可变分区存储管理 D．页式存储管理PCB全称（B）A.进程队列 B.进程控制块C.进程状态 D.进程对象计算机系统能及时处理由过程控制反馈的数据，并做出响应的操作系统是（ B）A.批处理操作系统 B.实时操作系统C.分时操作系统 D.多处理机操作系统某进程所要求的一次打印输出结束，该进程被唤醒，其进程状态将从（B）A.就绪状态到运行状态 B.等待状态到就绪状态C.运行状态到等待状态 D.运行状态到就绪状态内存分配的最差适应算法的空闲区表是（A）A.按大小递减顺序排列 B.按大小递增顺序排列C.按地址由小到大排列 D.按地址由大到小排列以下说法错误的是（D）A.并发进程中与共享变量有关的程序段称为临界区B.并发进程中涉及到相同变量的程序段称为相关临界区C.临界区的引入主要是为了解决并发进程执行时出现与时间有关的错误D.所有并发进程都会产生与时间有关的错误一种既有利于短小作业又兼顾到长作业的作业调度算法是（B）先来先服务 B.最高响应比优先 C.轮转 D.均衡调度某系统采用LRU页置换算法和局部置换策略，若系统为进程P预分配了4个页框，进程P访问页号的序列为0,1,2,7,0,5,3,5,0,2,7,6，则进程访问上述页的过程中，产生页置换的总次数是（C）。A.3 B.4 C.5 D.6计算机操作系统的功能是（D）A.把源程序代码转换为目标代码B.实现计算机用户之间的相互交流C.完成计算机硬件与软件之间的转换D.控制、管理计算机系统的资源和程序的执行多道程序设计是指（C）A.在多台处理机上同时执行多道程序 B.在多台处理机上同一时刻执行多道程序C.在一台处理机上同时执行多道程序 D.在一台处理机上同一时刻执行多道程序有关进程的下列叙述中正确的是（D）A.进程是静态的文本 B.进程与程序是一一对应的C.进程与作业是一一对应的 D.多个进程可以在单个CPU上同时执行在下列操作系统中，对响应时间要求最高的是(C)。A.批处理系统 B.分时系统 C.实时系统 D.网络操作系统关于单向扫描调度算法描述正确的是（A）A.不管等待访问者的顺序，总是从0号柱面开始向里扫描B.按照等待访问者的顺序，总是从0号柱面开始向里扫描C.不管等待访问者的顺序，总是从最大号柱面开始向外扫描D.按照等待访问者的顺序，总是从最大号柱面开始向外扫描“死锁”问题的讨论是针对（D）A.某个进程申请系统中不存在的资源B.某个进程申请资源数超过了系统拥有的最大资源数C.硬件故障D.多个并发进程竞争独占型资源本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是（B）。A.命令解释程序B.中断处理程序C.系统调用服务程序D.用户登录程序在下列作业调度算法中，可能引起作业长时间不能被装入执行的算法是（B）A.FCFS算法 B.计算时间短的作业优先算法C.最高响应比优先算法 D.动态优先数调度算法在解决死锁问题的方法中，属于“死锁避免”策略的是（A）A.银行家算法 B.死锁检测算法C.资源有序分配法 D.资源分配图化简法多道程序设计是指（C）A.在多台处理机上同时执行多道程序 B.在多台处理机上同一时刻执行多道程序C.在一台处理机上同时执行多道程序 D.在一台处理机上同一时刻执行多道程序以下关于可变分区常用主存分配算法描述错误的（B）A.最先适应分配算法总是顺序查找空闲区，找到第一个能满足的停止查找B.最优适应分配算法总是寻找一个最大的空闲区分配给请求的作业C.最先适应分配算法容易产生过多的碎片D.最坏适应分配算法每次都挑选一个最大的空闲区分配给请求的作业在动态分区存储管理中，当回收主存空间时，应检查是否有与归还区相邻的空闲分区进行合并。假定作业归还的分区起始地址为S，长度为L。如果S-Lj正好等于空闲分区链中第j个空闲分区的起始地址，则表示归还区是(A)。A.有上邻空闲分区 B.有下邻空闲分区C.既有上邻空闲分区，又有下邻空闲分区 D.既无上邻空闲分区，又无下邻空闲分区LFU页面调度算法是（A）A.最近最久没使用调度算法 B.先进先出调度算法C.最近最不常使用调度算法 D.最近最常用调度算法以下关于响应比最高者优先算法描述错误的是（C）A.响应比等于等待时间除以计算时间B.计算时间短的作业容易先调用C.计算时间长的作业容易先调用D.等待时间长的作业容易先调用某进程所要求的一次打印输出结束，该进程被唤醒，其进程状态将从(B)。 A.阻塞状态到运行状态 B.阻塞状态到就绪状态C.运行状态到阻塞状态 D.运行状态到就绪状态以下关于安全状态相关的描述正确的是（C）A.只要保证所有进程都能得到所需要的全部资源，系统一定处于安全状态B.安全状态就一定不会发生死锁C.不安全状态就一定会发生死锁D.安全状态也有可能会发生死锁虚拟设备技术是指（C）A.用共享设备代替独占设备的技术 B.用独占设备代替共享设备的技术C.用共享设备模拟独占设备的技术 D.用独占设备模拟共享设备的技术下列算法中可用于磁盘移臂调度的是（B）A.最短计算时间优先 B.电梯算法 C.时间片轮转 D.响应比高者优先在下列操作系统中，对响应时间要求最高的是（C）A.批处理系统 B.分时系统 C.实时系统 D.网络操作系统进程和程序的本质区别是（D）A.存储在内存和外存 B.顺序和非顺序执行机器指令C.分时使用和独占使用计算机资源 D.动态和静态特征引入缓冲技术的主要目的是(B)。A.改善用户编程环境 B.提高CPU的处理速度C.提高CPU与设备之间的并行程度D.降低计算机的硬件成本下面关于高速缓冲存储器的叙述中不正确的是(B)。A.引入高速缓冲存储器，加快了程序的执行速度B.引入高速缓冲存储器，增加了主存储器的容量C.高速缓冲存储器的存取速度比主存储器快D.高速缓冲存储器的存取容量比主存储器小以下关于进程的并发执行描述正确的是（A）A.多个进程在某个时间段内轮流占用处理器执行B.多个进程在某个时刻同时占用处理器执行C.单处理器的系统也允许进程并发执行 D.只有多处理器的系统才能允许进程并发执行对于具备设备独立性的系统，下列叙述中，错误的是（D）。A.可以使用文件名访问物理设备B.用户程序使用逻辑设备名访问物理设备C.需要建立逻辑设备与物理设备之间的映射关系D.更换物理设备后必须修改访问该设备的应用程序PCB全称是（C） A.进程队列 B.进程状态C.进程控制块 D.进程对象任何一个进程进入临界区调用（A）A.P操作 B.V操作C.S操作 D.C操作分页存储管理系统中引入“快表”，是为了(B)。A.保存最近访问的数据 B.保存最近用过的页表项C.保存最近用过的物理地址 D.保存最近用过的虚拟地址目录对文件实行统一管理，最基本的是为用户提供（A）功能A.按名存取 B.文件共享C.文件保护D.提高文件的存取速度可变分区常用的主存分配算法中不包括（B）A.最先适应分配算法 B.顺序分配算法C.最优适应分配算法 D.最坏适应分配算法若当前进程因时间片用完而让出处理机时，该进程应转变为(A状态。

A.就绪B.等待C.运行D.完成产生死锁的四个必要条件是：互斥、(B)、循环等待和不剥夺。A.请求与阻塞 B.请求与保持C.请求与释放 D.释放与阻塞在支持多线程的系统中，进程P创建的若干个线程不能共享的是（D）。A.进程P的代码段C.进程P的全局变量B.进程P中打开的文件D.进程P中某线程的栈指针可变分区常用的主存分配算法中不包括（A）A.顺序分配算法 B.最先适应分配算法C.最坏适应分配算法 D.最优适应分配算法SPOOL技术的主要目的是（B）A.提高CPU和设备交换信息的速度 B.提高独占设备的利用率C.减轻用户的编程负担 D.提供主、辅存接口（C）总是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱面的访问者，若沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。A.先来先服务调度算法 B.最短寻找时间优先调度算法C.电梯调度算法 D.单向扫描调度算法在进行作业调度时，要想兼顾作业等待时间和计算时间，应选取(D)A.均衡调度算法 B.优先数调度算法C.计算机时间短的作业优先算法 D.响应比最高者优先算法对磁盘进行移臂调度的目的是为了缩短（A）时间 Ａ.寻找 Ｂ.启动 Ｃ.传送Ｄ.延迟一种既有利于短小作业又兼顾到长作业的作业调度算法是（B） Ａ.先来先服务Ｂ.最高响应比优先 Ｃ.轮转Ｄ.均衡调度若有4个进程共享同一程序段，每次允许2个进程进入该程序段，用PV操作作为同步机制。则信号量S的取值范围是(B)。A.4，3，2，1，0 B.3，2，1，0，-1C.2，1，0，-1，-2 D.1，0，-1，-2，-3若处理器有32位地址，则采用分页存储管理方式下，页面大小为8KB，则分页地址中页号的最大值是(C)。A.23 B.232 C.219 D.24判断题1．当系统中的进程均处于阻塞状态时，此时系统一定发生了死锁。 错2.并行性是指若干事件在一段时间内发生。 错3.待IO完成时，进程就从执行状态变为就绪状态。 错4.不安全状态一定是死锁状态。 错5.线程是最小的拥有资源的单位。 错6.在页式存储管理系统中，当发生缺页中断时一定会淘汰掉内存中的一页。·错7在二级目录结构中，不同用户能建立与其他用户同名的文件。错早期的批处理系统中，用户可以用交互式方式方便地使用计算机。错8多道程序系统在单处理机的环境下，程序的执行是并发不是并行的，程 序的执行与I/O操作也只能并发不能并行。错9.式虚拟存储系统中，页面长度固定并且是硬件的设计特性.对10.位分区管理可以对作业分配不连续的内存单元. 错11.态重定位技术的系统，目标程序可以不经任何改动，而装入物理内存. 对12.定位技术使得作业在内存中可以移动。 对13、请求分页存储管理技术的逻辑地址由页号p和页内地址d组成，因此是一个二维地址空间。 错14.不同的外存分配方式将形成不同的文件物理结构。 对15设备的数据特性，可以将设备分为存储设备和输入/输出设备。 错16POOLing系统实现设备管理的虚拟技术，即：将独占设备改造为共享设备。它由专门负责I/O的常驻内存进程以及输入、输出井组成。 对17.容量的扩大是以牺牲CPU工作时间以及内、外存交换时间为代价的。 错18.统通过PCB来控制和管理进程，用户进程可以从PCB中读出与本身运行状态相关的信息。对填空题1. 进程是_分配资源___的基本单位，而线程是__系统调度____的基本单位。2. 若信号量s的初始值为3，当前值为-2，则表示有____2__个阻塞进程。块号6014105896173. 有一个作业8:10到达系统，估计运行时间为0.5小时，若10:00开始执行，其响应比为_____5__。响应比定义为：响应比=作业响应时间/运行时间的估计值。其中响应时间为作业进入系统后的等待时间加上估计的运行时间4. 给定如下页表，页面大小为4KB，那么，逻辑地址(2,88)对应的物理地址是_41048____，逻辑地址(5,100)对应的物理地址是__69732___。5. 进程是由___程序段_______.__数据段________和_____进程控制块_____三部分组成的。6. 固定分区和动态分区存储管理的重定位方式是不同的，固定分区管理采用__静态重定位__方式装入用户作业，而动态分区管理采用____动态重定位____方式装入用户作业。7．在DMA控制方式下，_外部设备____与_____CPU_____之间直接进行成批的数据交换。8. 文件的物理结构分为连续存储.___链接存储________和___索引存储_____。9.按照用户界面的使用环境和功能特征的不同,一般可以把操作系统分为三种基本类型,即:____批处理系统____,____分时系统____和实时系统.10.除了新建状态与撤销状态，进程的基本状态有____运行____、____就绪____、____阻塞____11.一般说来,用户程序中所使用的地址是逻辑地址,而内存中各存储单元的地址是____物理地址或绝对地址____;将前者转变为后者的过程称作____重定位____12.通道是独立于____CPU____的、专门负责____数据输入输出传输工作____的处理单元13.分区存贮管理方法的主要优点是易于____实现____，缺点是容易产生____碎片____简答题:什么是操作系统？它的特点答：操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。其主要作用是管理好这些设备，提高他们的利用率和系统的吞吐量，并为用户和应用系统提供一个简单的接口，便于用户使用。它有4个基本特征：并发性共享性虚拟性异步性死锁，产生死锁的原因和必要条件答：如果一组进程中的每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么该组进程的是死锁。产生的必要条件是互斥条件请求和保持条件不可抢占挑战循环等待条件动态分区存储管理中常采用的分配策略。答：基于顺序搜索的动态分区分配方法：首次适应算法FF循环首次适应算法NF最佳适应算法BF最坏适应算法WF基于索引搜索的动态分区分配方法：快速适应算法伙伴系统哈希算法在分页、分段和段页式存储管理中分别需要访问内存几次？答：分页第一次是访问内存中的页表第二次访问内存时，才是第一次所得地址中获得所需数据分段同分页段页式第一次访问时访问内存中的段表第二次访问是访问内存中的页表第三次是从所得的地址中取出指令或数据段式管理和页式管理的异同。答：页式和段式系统有许多相似之处。比如，两者都采用离散分配方式，且都通过地址映射机构来实现地址变换。但概念上两者也有很多区别，主要表现在：页是信息的物理单位，分页是为了实现离散分配方式，以减少内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了更好地满足用户的需要。页的大小固定且由系统决定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的。段的长度不固定，且决定于用户所编写的程序，通常由编译系统在对源程序进行编译时根据信息的性质来划分。页式系统地址空间是一维的，即单一的线性地址空间，程序员只需利用一个标识符，即可表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。6.DMA和中断控制方式异同答：中断方式是在数据缓冲寄存区满后，发中断请求，CPU进行中断处理

DMA方式则是以数据块为单位传输的,即在CPU与I/O设备之间每次传送至少一个数据块处理的次数中断方式的数据传送是由设备到CPU再到内存，或者相反。

DMA方式的数据传送则是将所传输的数据由设备直接送入内存，或是由内存直接送到设备中断控制方式每当完成一个字节的I/O时，控制器便向CPU请求一次中断DMA仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制下完成的7.SPOOLing技术实现虚拟设备。答：Spooling的核心思想是利用一台可共享的，高速大容量的块设备（磁盘）来模拟独占设备的操作，使一台独占设备变成多台可并行使用的虚拟设备。用户向独占设备提交的请求实际上都被提交到可共享的高速大容量块设备。而从该块设备到实际物理独占设备的数据传输有spooling进程统一控制和调度。Spooling能够提高I/O操作的速度，将独占设备改造为虚拟设备，从而实现共享设备功能8、什么是设备独立性，它是如何实现的？答：设备独立性即应用程序独立于使用的物理设备，在应用程序中使用逻辑设备名称来请求使用某类设备。系统在执行时，是使用物理设备名称。要实现设备独立性必须由设备独立性软件完成，包括执行所有设备的公有操作软件提供统一的接口，其中逻辑设备到物理设备的映射是由逻辑设备表LUT完成的。9、操作系统为用户提供哪些接口？答：操作系统为用户提供两种类型的使用接口：一是操作员级的，它为用户提供控制作业执行的途径；二是程序员级的，它为用户程序提供服务功能。计算题：1、对如下表所示的5个进程：进程到达时间（ms）优先级CPU阵发时间（ms）P1233P2012P3443P4024P5552采用可剥夺的静态最高优先数算法进行调度（不考虑系统开销）。问题：⑴画出对上述5个进程调度结果的Gantt图；⑵计算5个进程的平均周转时间、平均带权周转时间。解：⑴调度结果的Gantt图如下：P4P1P3P5P3P1P4P2024579101214(2)时间计算：J2J4J3J110:2011:2011:4012:3014:30J2J4J3J110:2011:2011:4012:3014:30J2J4J3J110:2011:2011:4012:3014:30J2J4J3J110:2011:2011:4012:3014:30进程到达时间（ms）优先级运行时间（ms）开始时间（ms）完成时间（ms）周转时间（ms）带权周转时间（ms）P123321088/3P20121214147P34434955/3P4024012123P55525721平均周转时间=(8+14+5+12+2)/5=41/5=8.2(ms)平均带权周转时间=(8/3+7+5/3+3+1)/5=46/15≈3.07(ms)2、某系统采用虚拟页式存储管理方式，页面大小为2KB，每个进程分配的页框数固定为4页。采用局部置换策略，置换算法采用改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下一个在内存的表项。设当前进程P的页表如下（“时钟”指针指向逻辑页面3的表项）：逻辑页号页框号访问位r修改位m内外标识0101H0011—02110H1013138H0014—05100H111问题：⑴当进程P依次对逻辑地址执行下述操作：①引用4C7H；②修改19B4H；③修改0C9AH；写出进程P的页表内容；⑵在⑴的基础上，当P对逻辑地址27A8H进行访问，该逻辑地址对应的物理地址是多少？解：页面大小为2KB，2KB=2×210=211，即逻辑地址和物理地址的地址编码的低11位为页内偏移；⑴①逻辑地址4C7H=010011000111B，高于11位为0，所以该地址访问逻辑页面0；引用4C7H，页表表项0：r=1；②逻辑地址19B4H=0001100110110100B，高于11位为3，所以该地址访问逻辑页面3；修改19B4H，页表表项3：r=1,m=1;③逻辑地址0C9AH=0000110010011010B，高于11位为1，所以该地址访问逻辑页面1；逻辑页1不在内存，发生缺页中断；①、②两操作后，P的页表如下：逻辑页号页框号访问位r修改位m内外标识0101H1011—02110H1013138H1114—05100H111按改进的时钟算法，且时钟指针指向表项3，应淘汰0页面，即把P的逻辑页面1读到内存页框101H，页表时钟指针指向表项2。并执行操作：修改0C9AH。经上述3个操作后，P的页表如下：逻辑页号页框号访问位r修改位m内外标识0—0001101H1112110H0013138H0114—05100H011⑵逻辑地址27A8H=0010011110101000B，高于11位为4，所以该地址访问逻辑页面4；页面4不在内存，发生缺页中断；按改进的时钟算法，淘汰页面2，页面4读到110H页框，所以，逻辑地址27A8H对应的物理地址为：00010001000011110101000B=887A8H。3、设系统磁盘只有一个移动磁头，磁道由外向内编号为：0、1、2、……、199；磁头移动一个磁道所需时间为1毫秒；每个磁道有32个扇区；磁盘转速R=7500r/min.系统对磁盘设备的I/O请求采用N-StepLook（即N-StepScan，但不必移动到磁道尽头），N=5。设当前磁头在60号磁道，向内移动；每个I/O请求访问磁道上的1个扇区。现系统依次接收到对磁道的I/O请求序列如下：50,20,60,30,75,30,10,65,20,80,15,70问题：写出对上述I/O请求序列的调度序列，并计算磁头引臂的移动量；计算：总寻道时间（启动时间忽略）、总旋转延迟时间、总传输时间和总访问处理时间。解：⑴考虑序列中有重复磁道的I/O请求，调度序列为：60→75→50→30→20→15→10→65→70→80磁头移动量=(75-60)+(75-50)+(50-30)+(30-20)+(20-15)+(15-10)+(65-10)+(70-65)+(80-70)=15+25+20+10+5+5+55+5+10=155（磁道）⑵总寻道时间=1×155=155（ms）一次访盘的旋转时间=1/(2R)=1/(2×7500/min)=(60×1000)/(2×7500)ms=4(ms)请求序列共12次访盘，总旋转延迟时间=4×12=48(ms)1次访盘的传输时间=1/(R×32)=(60×1000)/(7500×32)=1/4ms12次访盘总传输时间=1/4×12=3(ms)总访盘处理时间=155+48+3=206(ms)4、某系统采用死锁检测发现死锁。设系统有资源类集合为R＝｛A，B，C｝，6个进程P0、P1、P2、P3、P4、P5并发运行。当前系统状态如下：allocationrequestavailableABCABCABCP0100000221P1321000P2012202P3000000P4210031P5001000问题：⑴在上述状态下，系统依次接收请求：request[0]=(1,0,0)、request[1]=(2,1,0)、request[3]=(0,0,2)，给出系统状态变化情况，并说明没有死锁。⑵在⑴所确定的状态下，系统接收请求：request[0]=(0,3,1)，说明此时已经发生死锁，并找出参与死锁的进程。解：⑴在上述情况下，系统依次接收请求：request[0]=(1,0,0)、request[1]=(2,1,0)、request[3]=(0,0,2)，系统状态变化如下：allocationrequestavailableABCABCABCP0200000121P1321210P2012202P3000002P4210031P5001000上一状态没有死锁。因为，用死锁检测算法，进程P5、P0、P1、P2、P3、P4能依次运行完。⑵在⑴所确定的状态下，系统接收请求：request[0]=(0,3,1)，系统状态变化如下：allocationrequestavailableABCABCABCP0200031121P1321210P2012202P3000002P4210031P5001000对上一状态用死锁检测算法，P5、P3能完成，P0、P1、P2、P4不能完成，发生死锁，参与死锁的进程为P0、P1、P2、P4。5、一南北流向的小河上有一座独木桥，如下图所示：西西东该独木桥宽度只能容纳一人，且该桥最多只能承重4人；东、西两方向过桥人只能前进、不能后退。问题：写出用信号量和PV操作实现东、西两方向行人过桥没有死锁、没有饿死的并发运行算法。要求：给出定义的各信号量和变量的含义及其初值；算法用类C伪代码描述。解：共享变量定义：intwest_crossing=0,east_crossing=0,west_wait=0,east_wait=0;semaphorewq,eq;/*初值均为0*/semaphoremutex;/*初值均为1，用于共享变量的互斥*/semaphorenum;/*初值为4，用于限制过河人数*/semaphorew_wait,e_wait;/*初值均为1，防止对方饿死*/东面过河者算法：P(east_wait);/*后续过桥者将在此等待*/东面过河者算法：P(east_wait);/*后续过桥者将在此等待*/P(mutex);if(west_crossing>0){east_wait++;if(east_wait==1)P(w_wait);//东边有等待，西边后续过桥者将等待V(mutex);P(eq);/*东边第一位过桥者在此等待*/}else{P(num);/*过河人数超过4人则等待*/east_crossing++;V(mutex);}V(east_wait);<上独木桥过河>;P(mutex);east_crossing--;V(num);/*过桥人数减少1人*/if(east_crossing==0){if(west_wait>0)do{west_wait––;west_crossing++;V(wq);/*唤醒西边第一位等待者*/}V(w_wait);/*唤醒西边后续的等待者*/}V(mutex);西面过河者算法：P(w_wait);/*后续过桥者将在此等待*/P(mutex);if(east_crossing>0){west_wait++;if(west_wait==1)P(e_wait);//西边有等待，东边后续过桥者将等待V(mutex);P(wq);/*西边第一位过桥者在此等待*/}else{P(num);/*过河人数超过4人则等待*/west_crossing++;V(mutex);}V(w_wait);<上独木桥过河>;P(mutex);west_crossing--;V(num);/*过桥人数减少1人*/if(west_crossing==0){if(east_wait>0)do{east_wait––;east_crossing++;V(eq);/*唤醒东边第一位等待者*/}V(e_wait);/*唤醒东边后续的等待者*/}V(mutex);6、某系统按最短剩余时间（ShortestRemainingTimeFirst）优先算法调度CPU。已知四个进程P1、P2、P3、P4的到达时间和CPU阵发时间如下（时间单位：毫秒）：ProcessArrivaltimeBursttimeP1010P236P343P474问题：⑴画出按最短剩余时间优先的CPU调度算法得到的进程调度结果的Gantt图；⑵计算四个进程的平均等待时间、平均周转时间、平均带权周转时间。解：⑴按最短剩余时间优先调度算法的进程调度结果Gantt图：P1P2P3P4P2P10347111623⑵四个进程的平均等待时间、平均周转时间、平均带权周转时间见下表：进程到达时间运行时间开始时间完成时间等待时间周转时间带权周转时间P1010023132323/10P23631671313/6P34347031P474711041平均等待时间=（13+7+0+0）/4=20/4=5ms平均周转时间=（23+13+3+4）/4=43/4=10.75ms平均带权周转时间=（23/10+13/6+1+1）/4=194/(30*4)≈1.62ms7、并发进程P0和P1关于共享变量的临界区分别为region0和region1。用软件方法解决P0和P1互斥进入其临界区的不完整的C伪代码如下：intflag[2]={0,0};/*公共变量*/进程P1：do{flag[1]=1;turn=进程P1：do{flag[1]=1;turn=②;while(④)docontinue;<region1>；flag[1]=0;<其余代码>；}while(1);进程P0：do{进程P0：do{flag[0]=1;turn=①;while(③)docontinue;<region0>；flag[0]=0;<其余代码>；}while(1);问题：1.在①、②处分别填上正确的数；在③、④处分别填上正确的C表达式，使P0、P1满足临界区管理的互斥性、进展性、有限等待性原则；2.当P0和P1两进程都要进入临界区，并分别执行完各自有关turn的赋值语句后，哪个进程先进入临界区？说明理由。解：1.完善进程：①=1、②=0；③=flag[1]&&turn==1、④=flag[0]&&turn==0;2.当P0和P1两进程都要进入临界区，并分别执行完①、②处的有关turn的赋值语句后，哪个进程先执行完turn的赋值语句，哪个进程就先进入临界区。理由如下：假设P0先执行turn=1，P1后执行turn=0，执行各自的while语句之前，turn==0，使P0的while循环条件为假、P1的while循环条件为真，所以P0不用while循环等待，直接跳出循环先进入临界区。8、设某计算机主存按字节编址，容量为512KB；系统采用虚拟页式存储管理方式，虚拟地址空间为4MB，页面大小为4KB，每个进程分配的页框数固定为4页。采用局部置换策略，置换算法采用改进的时钟算法（“时钟”指针初始指向第一个调入页面）。主存空闲区管理采用空闲页面表的结构，存储分配采用下次适应算法（即从上次分配下标的下一个表项开始分配）。系统对上次内存请求，分配了下标为1的空闲区中的页框后，空闲页面表如下（表中数字均为10进制）：空闲页面表下标首页框号页框个数020413562803395204…….0问题：该计算机内存的物理地址编码是多少位？当进程P初始运行，对逻辑页面的操作依次为修改0页；引用1页；修改2页；修改3页写出进程P的页表内容，页表表项为：（逻辑页号、页框号、访问位r、修改位m）；在⑵的基础上，当P依次对逻辑地址97B0H和逻辑地址0B7B0H均进行修改访问时，这两个逻辑地址访问的逻辑页号和物理地址各是多少？解：⑴该计算机主存容量为512KB=29×210bytes＝219，所以该机内存物理地址编码为19位；⑵当进程P初始运行，访问的逻辑页面依次为：修改0、引用1、修改2、修改3时，按下次适应算法应该从下标为2的空闲区开始依次分配，进程P的页表如下：逻辑页号页框号（十进制）访问位r修改位m08011195102201133511⑶逻辑地址97B0H=00,0000,1001,0111,1011,0000B；（4MB＝222bytes，故逻辑地址为22位）因为页面大小为4KB=212bytes，所以地址的低12位为页内偏移，高于12位的部分为逻辑页号。所以逻辑地址97B0H访问的逻辑页号为9，该逻辑页未调入内存，发生缺页；由于固定分配4个页框，且已分配了4个页框，按局部置换的修改的时钟算法置换，时钟指针应从逻辑页号0的表项开始，9号逻辑页置换的逻辑页为1，其页框为95号页框；95=5FH，所以逻辑地址97B0H访问的19位物理地址为101,1111,0111,1011,0000B=5F7B0H此时页表的第二项为：（9,95,1,1）逻辑地址0B7B0H=00,0000,1011,0111,1011,0000B；所以逻辑地址0B7B0H访问的逻辑页号为11，该页未调入内存，发生缺页；采用局部置换改进的时钟算法，并考虑上次置换时清过的访问位，应置换逻辑页面2，由于逻辑页面2分配的是20号页框，20=14H，所以逻辑地址0B7B0H访问的20位物理地址为001,0100,0111,1011,0000B=147B0H9、设系统磁盘只有一个移动磁头，磁道由外向内编号为：0、1、2、……、199；磁头移动一个磁道所需时间为1毫秒；每个磁道有32个扇区；磁盘转速R=6000r/min.系统对磁盘设备的I/O请求采用N-StepLook（即N-StepScan，但不必移动到磁道尽头），N=4。设当前磁头在50号磁道，向内移动。现有对磁道的I/O请求序列：12,24,7,60,30,77,5,26,61,80,53,66；每个I/O请求访问磁道上的1个扇区。问题：写出给定磁道的I/O请求序列的调度序列，并计算磁头的移动量；对给定I/O请求序列，计算：总寻道时间（启动时间忽略）、总旋转延迟时间、总传输时间和总访问处理时间。解：⑴调度序列为（不包括括号内的磁道）：(50)→60→24→12→7→5→26→30→77→80→66→61→53磁头移动量=(60-50)+(60-24)+(24-12)+(12-7)+(7-5)+(26-5)+(30-26)+(77-30)+(80-77)+(80-66)+(66-61)+(61-53)=10+36+12+5+2+21+4+47+3+14+5+8=167（磁道）⑵总寻道时间=1×167=167（ms）一次访盘的旋转时间=1/(2R)=1/(2×6000/min)=(60×1000)/(2×6000)ms=5(ms)请求序列共12次访盘，总旋转延迟时间=5×12=60(ms)1次访盘的传输时间=1/(R×32)=(60×1000)/(6000×32)=5/16(ms)12次访盘总传输时间=5/16×12=3.75(ms)总访盘处理时间=167+60+3.75=230.75(ms)10、设系统有资源集合为R＝｛A，B，C｝，5个进程P0、P1、P2、P3、P4并发运行。按银行家算法，当前系统状态如下：ClaimAllocationAvailableABCABCABCP0554010211P1432221P2652101P3322211P4443002问题：系统中各类资源总量是多少？矩阵Need的值是多少？判断当前系统状态是否安全？在当前状态下，如果进程P0提出资源请求request[0]=(1,0,0)，系统能否实施分配？说明原因。解：⑴系统各类资源总量（A，B，C）=（7，5，6）；⑵矩阵need的值如下：NeedABC544211551111441⑶在当前系统状态下，可找到进程安全状态序列：<P1,P3,P4,P0,P2>，所以当前系统状态是安全状态；⑷在当前系统状态下，进程P0提出资源请求request[0]=(1,0,0)，系统预分配后的状态如下：ClaimAllocationNeedAvaiableABCABCABCABCP0554110444111P1432221211P2652101551P3322211111P4443002441该系统状态可找到进程安全序列：<P3,P1,P4,P0,P2>，所以系统能满足该请求。11、侏罗纪公园内有一个恐龙博物馆和一个花园，游客先步行参观恐龙博物馆，然后乘游览车游览花园。设共有n辆游览车（有司机），每辆游览车一次只能搭载一位游客。试用信号量和PV操作实现游客和游览车之间的同步。要求：（1）给出信号灯及其它变量的定义；（2）分别给出游客和游览车的活动。解：设游客与游览车的进程分别为tourist和car；信号量定义及算法如下：Intcar_status[n];/*初值为均为0，car_status[i]表示i号车的状态，0空闲，1占用。*/semphorecar_wait[n];/*初值均为0，用于游客与i号车的上车、启动的同步。*/semphorecar_stop[n];/*初值均为0，用于游客与i号车的下车、停车的同步。*/semphoredown[n];/*初值均为0，用于游客下车与i号车空闲的同步。*/semaphoreS;/*初值为n，用于n辆游览车的管理；*/semaphoremutex;//初值为1，用于修改车状态的互斥；voidcar(intivoidcar(inti){do{P(car_wait[i]);/*游客上车？*/启动、行驶（顾客游览）；停车；V(car_stop[i]);/*通知游客已停车*/P(down[i]);/*游客下车？