操作系统期末试题(长春)

一、名词解释（10分） 1、操作系统 2、进程3、设备无关性4、数组多路通道 5、死锁 二、简答题（15分） 1、一台计算机有8台磁带机，他们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危险。请说明其原因。 2、叙述设备分配时需要的数据结构，及其分配方法。 3、请你简述段页式虚拟存储系统使用的数据结构及地址变换过程。 4、请简述SPOOLING 系统的组成及各部分的功能 5、假定一个处理器正在执行两道作业，一道以计算为主，一道以输入输出为主，你将怎样赋予它们占有处理器的优先级？为什么？ 三、现要求从输入机（速度为6400字符/秒）输入1000个字符，经处理（费时37毫秒）后，将结果（仍假设为1000字符）存到磁带上（磁带机速度为10万字符/秒），然后，再读1000个字符处理，直到所有的输入数据全部处理完毕。假定处理器具有与外围设备并行工作的能力，请计算处理器的利用率。 （5分） 四、在一个支持虚拟分页并采用请求页式调度的存储管理系统中，有一用户程序，它访问其地址空间的字地址序列是：70，74，135，276，400，300，700，266，148，560，284，172 问：若分配给该作业的内存大小为384字，初始为空，页大小为128字，试按FIFO、LRU页面淘汰算法，分别计算页面访问的缺页率。 （10分） 五、假定UNIX系统V中磁盘块大小为1K,每个磁盘块当用于做间接块时最多可登记256个块号，现要对一个大小为200000字节的文件检索一边，问将要发生多少次磁盘传输中断？为什么？（10分） 六、某系统中采用银行家算法避免死锁。设其资源集合为A，B，C，其中资源类A含有5个资源实例，资源类B含有10个资源实例，资源类C含有9个资源实例。又设系统中进程集合为P1，P2，P3，P4。在时刻T0系统状态如下： Max Allocation Need Available A B C A B C A B C A B C P1 4 9 3 2 3 2 2 6 1 1 4 1 P2 3 0 3 2 0 2 1 0 1 P3 1 7 5 0 2 3 1 5 2 P4 3 2 1 0 1 1 3 1 0试回答当前状态是否是安全的，为什么？（10分） 七、设某移动磁盘上共有200个磁道，由内向外依次编号为0199。又设该磁盘仅配有一个读写磁头，且磁头在完成对于第127号磁道的I/O请求后，正在为第140号磁道的I/O请求服务。假定此时I/O队列中有九个读写请求，所访问磁道列表如下： 到达次序：1 2 3 4 5 6 7 8 9 访问磁盘：83 148 91 178 94 150 102 175 130对于短距离优先、电梯调度磁盘调度算法分别求出为这九个请求服务所需的磁头移动量（以跨越磁道为单位）。 （10分） 八、请用PV操作解决读者和写者问题。有两组并发进程：读者和写者，共享一个文件，要求：（1）允许多个读者同时执行读操作 （2）在任意写者在完成写操作之前，不允许其他任意的读者和写者工作 （3）写者预工作，但在它之前已有读者在执行读操作，那么，待现有读者完成读操作后在执行写操作，新的读者和写者均被拒绝。（10分） 九、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，作业序列如表所示（表中所列作业优先数即为进程优先数，数值越小优先级越高）。 （10分） 列出所有作业进入内存时间及结束时间。 计算平均周转时间。 作业的执行时间 作业名 到达时间 估计运行时间 优先数 A 10：00 40分 5 B 10：20 30分 3 C 10：30 50分 4 D 10：50 20分 6 答案：一、（10分） 1.OS:是一组程序的集合,用于管理计算机系统的资源,方便用户的使用. 2.进程:是一个程序段在其数据集合上的运行过程. 3.设备无关性:用户在使用设备时,选用逻辑设备,而不必面对一种设备一种接口.设备管理实现逻辑设备到物理设备的映射,这就是设备无关性. 4.数组多路通道:是指连接多台设备.同时为多台设备服务,每次输入/输出一个数据块.这样的通道叫数组多路通道. 5.死锁:一组并发进程,因争夺彼此占用的资源而无法执行下去,这种僵局叫死锁. 二、（15分） 1.N循环测试方式2中断方式3DMA方式4通讯方式3.死锁产生的必要条件:1互斥条件2请求保持条件3部分分配条件4循环等待条件4.在段页式管理中,由于每段分成若干页,所以需要在段表中给出页表长度,以便检查逻辑地址中的页号是否越界.5.在进程通信中有共享存储器方式,消息缓冲方式及共享文件方式,其中共享存储器方式又分为直接通信与间接通信.(信箱通信)三（10分） 序列 主存页面 2 3 中断 次缺页率1275%四、（15分） 分解前：目录文件块数=254*64/512=32块 平均访盘次数为（1+32）/2=16.5 分解后：符号目录块数=254*10/512=5块 基本目录文件块数为254*56/512 平均访问次4次。五、（10分） Work Allocation Need FlagP0 622 032 011 TP3 654 332 652 TP1 986 000 750 TP2 986 354 356 TP4 12 13 10 014 656 T存在一安全通路p0p3p1p2p4.故当前时刻是安全的。六（15分）Semapher s=1/*用于缓冲区共享*/ S1=k/*空位置*/ S2=0/*产品*/ Producer Consumer Repeat Repeat Produce a product p(S2); P(S1); p(S); P(S0); get a product; Put a product; V(S); V(S2); V(S1); V(S); forever; Forever;七、（10分）作业 到达时间 开始处理时间 处理完成时间 周转时间J1 15 18 22 7J2 18 21 23 5J3 17 19 21 4平均周转时间为（7+51-4）/3=16/3时八、（10分）FCFS: 访问顺序为：83 148 91 178 94 150 102 175 130 移动距离=（140-83）+（148-83）+（148-91）+（178-91）+（178-94）+（150-102） +（175-102）+（175-130）=571乘电梯调度算法：方向为：由内向外。 访问顺序为：140 148 150 175 178 130 102 94 91 83 移动距离为：（148-140）+（150-148）+（175-150）+（178-175）+（178-130）+（130-102）+（102-94）+（94-91）+（91-83）=133三、 简答题（20分，每题4分）1、什么是操作系统？2、什么是系统调用？3、什么是用户接口？通常在操作系统和用户之间提供哪些类型的接口？4、解释预输入和缓输出？5、设备驱动程序的功能是什么？四、（10分）在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法” 。假设目录文件存放在磁盘上，每个盘块512字节。文件控制块占64字节，其中文件名占8字节。通常将文件控制块分解成两部分，第1部分占10字节（包括文件名和文件内部号），第2部分占56字节（包括文件内部号和文件其他描述信息）。 假设某一目录文件共有254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数。 一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减少的条件。五、（10分）近代计算机系统常采用请求页式存储管理方案来管理自己的主存。假定某作业J所涉及的页面依次为：0，1，0，2，0，1，0，1，2，0，并已知主存中有3个可供作业J使用的空白存储块(块的大小与页面相同)。试说明采用FIFO和LRU两种不同淘汰算法时，缺页中断率各是多少?六、（10分）有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，有如表的作业序列（表中所列作业优先数即为进程优先数，数值越小优先级越高）。 列出所有作业进入内存时间及结束时间。 计算平均周转时间。表 作业的执行时间七、（10分）某系统有R1，R2和R3共3种资源，在T0时刻P1、P2、P3和P4这个进程对资源的占用和需求情况见表，此刻系统的可用资源向量为（2，1，2），问题： 将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来； 如果此时P2发出资源请求向量Request（1，0，1），能否分配？八、（10分）某寺庙共有老和尚和小和尚若干人，庙外有一口井，只能容一人打水，庙内有6只水桶和一口缸，缸内最多能装30桶水，每只桶每次只能由一人使用，缸每次只能由一人使用。小和尚负责从庙外的井里打水，老和尚使用缸里的水，老和尚取水的单位是桶。请利用信号量和P、V操作描述老和尚和小和尚的活动。九、（10分）设某移动磁盘上共有200个磁道，由内向外依次编号为0199。又设该磁盘仅配有一个读写磁头，且磁头在完成对于第127号磁道的I/O请求后，正在为第140号磁道的I/O请求服务。假定此时I/O队列中有九个读写请求，所访问磁道列表如下：到达次序： 1 2 3 4 5 6 7 8 9访问磁盘：83 148 91 178 94 150 102 175 130对于先来先服务、电梯磁盘调度算法分别给出访问顺序。答案三、简答题（20分，每题4分）1、 什么是操作系统？操作系统是控制和管理计算机软件、硬件资源，合理地组织计算机工作流程以及方便用户使用计算机的系统软件。2、 什么是系统调用？系统调用使用户或系统程序在程序以及上请求系统为之服务的一种手段。它的功能由操作系统的一些程序段完成。3、 什么是用户接口？通常在操作系统和用户之间提供哪些类型的接口？用户接口是指用户和操作系统打交道，请求使用操作系统的途径和方式。通常在操作系统和用户之间提供两类接口：一类是命令接口，另一类是程序接口。命令接口又分为联机控制命令和脱机控制命令。4、 解释预输入和缓输出？作业执行前，SPOOLing系统将大批作业从输入设备预先输入到磁盘输入井存放，称为预输入。作业的执行结果被存入磁盘的输出井，在作业执行完毕后，由操作系统组织信息成批输出，称为缓输出。5、设备驱动程序的功能是什么？设备驱动程序的主要功能有：根据传输要求设置I/O接口中的有关的控制寄存器的值，启动设备、通道或DMA控制器工作，检测处理设备错误，对设备的输入输出请求队列、睡眠、唤醒等操作进行处理。四、（10分）答： 采用分解法前，查找该目录文件的某一个文件控制块的平均访问磁盘次数为：64*（254/2）/512=16采用分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数为：10*（254/2）/512+1=4 访问磁盘次数减少的条件为： mn和m200，所以产生越界中断；（2）1,25：由段号1查段表得其段长100，将虚拟地址中的段内偏移25与该段段长相比较：25105，所以产生越界中断；（4）3,415：由段号3查段表得其段长600，将虚拟地址中的段内偏移415与该段段长相比较：415600，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：415+1200=1615；（5）4,20：由段号4查段表得其段长150，将虚拟地址中的段内偏移20与该段段长相比较：20150，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：20+4000=4020；三、FIFO页面替换算法：LRU页面替换算法：四、semaphore a=n,b=m;void main()createprocess(A,);createprocess(B,);void A()while(1)P(a);输入化合物A;V(b);void B()while(1)P(b);输入化合物B;V(a);五、六、UNIX中的进程可能处于以下九个状态之一：创建、内存就绪、外存就绪、内存睡眠、外存睡眠、核心态执行、用户态执行、剥夺、僵死。UNIX进程的状态转换图如下：七、设cache的命中率为h1，访问时间为t1；主存的命中率为h2，访问时间为t2；则被访问的字在cache中的概率为h1，则不在cache中但在主存中的概率为（1-h1）h2，不在cache中也不在主存中的概率为(1-h1)(1-h2) ；设磁盘的访问时间为t3，那么一个字的平均访问时间为：t1h1+(t1+t2)(1-h1)h2+(t1+t2+t3)(1-h1)(1-h2)。八、设每个进程最多可以请求x个这类资源，为了使系统一定不会发生死锁m,x,n需要满足关系式：n(x-1)+1=m，即x=(m-1)/n+1。当mn时，x=INT（(m-1)/n）+1，其中INT表示向下取整数。一、简答题（每题5分，共40分）1. 什么是SPOOLING系统？2. 什么是重定位？重定位有哪两种方式？3. 操作系统有哪些功能？4. 进程与程序有何区别？5. 在文件系统中，为什么将文件控制块FCB分割为两部分？6. 对UNIX系统来说，如果一个文件需占用268个物理块，画出该文件的索引结构。7. 什么是进程通信？8. 请给出一个实时操作系统，并说明该操作系统的功能。二、（10分）假设某系统采用段式存储管理，该系统为装入主存的一个作业建立了如下表所示的段表。请计算该作业分别访问0，305,1,55,2,125,3,410,4,50 时的绝对地址。三、（10分）在动态分页式存储管理系统中，设作业的页面引用序列为3 ,1, 0,2,3,2,7,1,0,3，内存可用帧数为4，试分别采用FIFO和LRU页面替换算法，计算缺页次数。（设初始时所有页面都不在内存）。四、（10分）设有两组进程：A组和B组，它们共享一个文件F，A组进程可以同时读文件，B 组进程也可以同时读文件，但是，若A组进程中的任何一个进程在读文件F，则B组进程中的任何一个进程必须等待直到A组进程中的所有进程都读完；同理，B组进程中的任何一个进程在读文件F时，A组进程中的任何一个进程必须等待直到B组进程中的所有进程都读完。请用信号量解决该问题。五、（10分）假如有四个进程，它们进入系统的时间及要求运行的时间如下表： 设采用单道程序设计技术，在0时刻进行进程调度，请分别计算采用先来先服务、短作业优先、响应比高者优先调度算法时这些进程的执行顺序、各个进程周转时间及所有进程的平均周转时间。六、（10分）在UNIX操作系统中，进程有哪几种状态，请画出进程之间的状态转换图。七、（5分）假设一个任务被划分成8个大小相等的段，并且系统为每一个段建立了一个有16项的页描述符表。因此该系统是分段与分页的结合。假设页大小为4