操作系统2重点范围习题解答答案

1、一、简答题(每题5 分，共 30 分)1. 什么是虚拟设备2. What s the differrence between a process and a program3. s Hyper-Treading technology4. 死锁的必要条件是什么5. 为什么将文件控制块分成主部和次部两部分6. 若系统有同类资源m个，被n个进程共享，问：当 m>n和m<=n时每个进程最多可以请求多少个这类资源，使系统一定不会发生死锁为什么二、填空题(每空1 分，共 10 分)1. 操作系统的两个重要特性是：(1) 和 (2)。2. 只能在管态下执行的指令称为(3) 。处理机状态由目态转换

2、为管态的唯一途径是 (4) ，管态到目态的转换可以通过修改(5) 来实现。3. 进程在其生存期内可以处于如下三种基本状态之一：运行态、就绪态和等待态。当一个就绪进程(6)时，其状态由就绪变为运行，当一个运行进程被抢占处理机时，其状态由运行变为(7)， 当一个运行进程因某事件受阻时，其状态由运行变为(8)， 当进程所等待的事件已经发生时，该进程状态由(9) 变为就绪。4. 线程是进程内的一个相对独立的(10) 。三、计算题(每题10 分，共 40 分)1.设某计算机系统采用虚拟页式存储管理方法，进程的虚拟地址空间为64KB页面尺寸为4KB。 假设当前进程的页表如右图所示(页表以二进制形式表示)，

3、 请将虚拟地址8196 和 2050转换为物理地址。2. 设某计算机系统采用虚拟页式存储管理方法，内存中为该进程分配4 个物理页架, 开始时 内 存 页 架 为 空 ,假 设 进 程 在 一 段 时 间 内 的 页 面 访 问 序 列 如下 :6,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1， 请画图表示采用以下页面淘汰算法时的缺页中断次数：（ 1）最佳页面淘汰算法（OPT） ； （ 2）先进先出页面淘汰算法（FIFO） ； （ 3）使用过最久的先淘汰（LRU）。3 .在UNIX系统中，设磁盘物理块大小为1KB,每个索引块可以保存 256个索引项，请画出UNIX文

4、件的物理结构。假设某文件大小为1028KB,请计算访问以下逻辑块时需要多少次I/O传输： （ 1 ） 8； （ 2） 300； （ 3） 16。4 .设有周期性实时任务集如下表所示，用最早截止期优先算法（EDF算法）和速率单调算法（RM砥法）是否可以调度画出相应的Gantt图。四、算法设计（每题10 分，共 20 分）1.设有一个可以装 A B两种物品的仓库， 其容量无限大，但要求仓库中 A、B两种物品的数量满足下述不等式:-MW A物品数量B物品数量w N其中M和N为正整数。试用信号灯和 PV操作描述A、B两种物品的入库过程。2.用信号量和PV操作实现读者/写者问题，要求读者优先，即：当有读

5、者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。0250-52试题A答案 一、1 虚拟设备是利用共享型设备实现的数量较多、速度较快的独占型设备。2进程是具有独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的独立单位。程序是指令的有序序列。进程与程序的区别在于：。1进程是动态的，程序是静态的；。2进程是短暂的，程序可以永久保存；。3进程与程序之间不具有一一对应关系： 一个程序可以对应一个进程，也可以对应多个进程；一个进程可以对应一个程序，或者对应一段程序。5树型目录结构解决了命名冲突；有利于提高文件的检索速度；有利于实现文件共享；有利于用户对文件进行分门别类

6、地组织。67并发执行的进程为了协调一致地完成指定任务，进程之间具有一定的联系，这种联系通常采用进程间交换数据的方式进行。进程间交换数据叫进程通信。进程之间所交换的信息量，少则是一个状态或数值，多则是成千上万个字节。因而进程通信的类型分为：低级通信（进程间交换少量数据，如信号量机制）；高级通信（进程间交换大量数据）。8 UC/OS-II 是一个嵌入式操作系统，其功能包括任务管理、时间管理、任务间通信、内存管理等。二、（ 1 ） 0 ， 350 ：由段号0 查段表得其段长200，将虚拟地址中的段内偏移350 与该段段长相比较：350>200，所以产生越界中断；（ 2） 1,25 ：由段号1

7、查段表得其段长100，将虚拟地址中的段内偏移25 与该段段长相比较：25<100，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：25+3000=3025；（ 3） 2,120：由段号2 查段表得其段长105，将虚拟地址中的段内偏移120 与该段段长相比较：120>105，所以产生越界中断；（ 4） 3,415：由段号3 查段表得其段长600，将虚拟地址中的段内偏移415 与该段段长相比较：415<600，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：415+1200=1615；（ 5） 4,20 ：由段号4 查段表得其段长150，将

8、虚拟地址中的段内偏移20 与该段段长相比较：20<150，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：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 中的进程可能处于以下九个状态之一：创建、内存就绪、外存就绪、内存睡眠、外存睡眠、核心态执行、用户态执行、剥夺、僵

9、死。UNIX进程的状态转换图如下：七、设cache的命中率为hl,访问时间为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)

10、/n+1 。当 m<n时，x=1;当 m>n时，x=INT (m-1)/n )+1，其中INT 表示向下取整数。0219 0224， 0279 操作系统试卷A1、 名词解释(10 分，每题2 分)1 操作系统2进程3线程4作业5中断2、 简要回答下述问题(20 分，每题4 分)1 常用的文件物理结构有哪几种，请简述它们，至少给出三种。2 请你简述段页式虚拟存储系统使用的数据结构。3 请简述SPOOLING 系统的组成及各部分的功能。4 请叙述在进程通信中有哪几种通信方式5 什么是地址重定位动态重定位和静态重地位有何区别3、 在一个支持虚拟分页并采用请求页式调度的存储管理系统中，有一

11、用户程序，它访问其地址空间的字地址序列是：70， 74， 135， 276， 400， 300， 700， 266， 148， 560， 284， 172 问：若分配给该作业的内存大小为384字，初始为空，页大小为128字，试按FIFO、LRU页面淘汰算法，分别计算页面访问的缺页率。（ 10 分）4、 在下面的段表中对于以下逻辑地址（ 段号， 单元号 ） ， 求对应的物理地址。（ 10 分） （ 1）0,400;（2）3,300;（3）1,20;5、 有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，作业序列如表所示（表中所列作业优先

12、数即为进程优先数，数值越小优先级越高）。 （ 15 分） 列出所有作业进入内存时间及结束时间。 计算平均周转时间。作业的执行时间六、设由n 个缓冲区组成缓冲池，每个缓冲区可以存放一个消息，有两类进程：x 个生产者和 y 个消费者，且只要缓冲池未满，生产者便可以将消息送入缓冲池，而只要缓冲池未空，消费者就可以取走一个消息。各个进程对缓冲池进行互斥访问，用信号量实现协调过程。要求写出使用的信号量、初值及其作用，并写出生产者进程和消费者进程的处理流程（10 分）七、假定UNIX系统V中磁盘块地大小为 1K,每个磁盘块当用于做间接块时最多可登记256个块号， 现在要对一个大小为2000K， 已经打开的

13、文件检索一遍，请画出该文件的索引结构，并回答将要发生多少次磁盘传输完成中断（10 分）八、在银行家算法中，若出现如下资源分配情况：NeedAllocationAvailable0 0 1 21 7 5 02 3 5 60 6 5 20 6 5 6P000321 6 2 3P11000P21354P30332P40014试回答下列问题：（ 15 分）1 、找出一个安全序列。2、在上述状态下，对于下列由进程P2 发出申请命令request（1,2,2,2） ，会被接受吗原因何在0219-0224、0279操作系统 A答案一、名词解释（10 分，每题2 分 ）1、操作系统：是位于硬件层之上，所有其它

14、软件之下的一个系统软件，是管理系统中的软硬资源，使其得以充分利用并方便用户使用的程序集合。2、进程：具有一定独立功能的程序关于一个数据集合的一次运行活动。3、线程：也称轻进程，是进程内的一个相对独立的执行流。4、作业：用户要求计算机系统为其完成的计算任务的集合。5、中断：在程序运行过程中，出现的某种紧急事件，必须中止当前正在运行的程序，转去处理此事件，然后再恢复原来运行的程序，这个过程称为中断。二、简要回答下述问题（20 分，每题4 分 ）1、常用文件的物理结构有顺序文件、链接文件、索引结构、Hash 结构、倒排结构。顺序结构：一个文件占有若干个连续的物理块，首块号块数记录在FCB中。链接结构

15、：一个文件占有若干个不连续的存储块，各块之间以指针相连，其首块号及块数记录于FCB中。索引结构：一个文件占有若干个不连续的存储块，这些块的号记录于一个索引块中。2、段页虚拟存储采用的数据结构：每个作业一张段表系统一张快表每个段一张页表 页表控制寄存器主存一张位示图段表控制寄存器3、 Spooling 系统的组成：磁盘开辟输入井，输出井，其中输入井用于存放预先读入的作业，输出井保存输出结果。提供预输入程序，负责控制外围设备预先装入用户的作业到输入井中。缓输出程序：负责控制将输出井中的信息送往外围设备。井管理程序：负责控制将输入井中的数据读入内存，将程序结果存放到输出井中。4、进程通信中包括共享内

16、存方式和消息缓冲方式，消息缓冲方式又分为直接通信和间接通信，直接通信分为有缓冲方式和无缓冲方式。5、地址重定位：指逻辑地址转换为物理地址的过程。静态重定位：指装入时完成地址转化。动态重定位：指运行指令时将逻辑地址转化为物理地址。3、 （10 分 ）由题知内存为3 块：地址序列转成页面序列：0 0 1 2 3.2 5.2 1 4 2 1FIFO:淘汰最先装入主存的页面，使用队列 缺页率 = 8/12=2/3LRU：使用栈顶为最新访问项，底为淘汰项缺页率 =7/124、 (10 分 )(0,400) 的物理地址：200+400=600(3,300) 的物理地址：1300+300=1600(1,(2

17、0) 的物理地址：因为1 段长为14，所以地址越界，出错。5、 (10 分 )10:00J1进入，运行20 分10:00 10:2010:20J2进入，运行30 分10:20 10:50完成J4 10:50 进入主存完10:50 12:2010:50 J4 进入，级别低于J1 ， J1 运行 20 分。 10:50 11:10成11:10 J3 进入，运行50 分 完成 12:0011:00 12:2012:20 J4 运行 20 分钟，结束10:50 12:20J1： 10:00 11:10 J2： 10:20 10:50 J3： 11:10 12:00J4：TJ1=70 分 TJ2=30

18、分 TJ3=90 分 TJ4=90 分平均周转时间= 70+30+920+90/4 = 280/4 = 70 分钟6、 ( 10 分)7、 （10 分 ）2000 块，由索引结构知前10 项直接访问10 块，一级访问256 块， 2000 256 10= 1734 块1734 + 256= 8个索引项（二级索引）发生中断次数为：1+ 1 + 7 + 2000= 2009次磁盘传输中断。8、 （ 15 分）1) work Allocation Need finishP0 1 6 2 3 0 0 3 2 0 0 1P3165403320652TP4198600140656TP1 19 9 10 1 0 0