电子科大02级操作系统试卷-有答案

0250-0252操作系统试卷A一、简答题（每题5分，共30分）

1.什么是虚拟设备？

2.What’sthedifferrencebetweenaprocessandaprogram？

3.What’sHyper-Treadingtechnology？

4.死锁的必要条件是什么？

5.为什么将文件控制块分成主部和次部两部分？

6.若系统有同类资源m个，被n个进程共享，问：当m>n和m<=n时每个进程最多可以请求多少个这类资源，使系统一定不会发生死锁？为什么？二、填空题（每空1分，共10分）

1.操作系统的两个重要特性是：(1)和(2)。

2.只能在管态下执行的指令称为(3)。处理机状态由目态转换为管态的唯一途径是(4)，管态到目态的转换可以通过修改(5)来实现。

3.进程在其生存期内可以处于如下三种基本状态之一：运行态、就绪态和等待态。当一个就绪进程(6)时，其状态由就绪变为运行，当一个运行进程被抢占处理机时，其状态由运行变为(7)，当一个运行进程因某事件受阻时，其状态由运行变为(8)，当进程所等待的事件已经发生时，该进程状态由(9)变为就绪。

4.线程是进程内的一个相对独立的(10)。三、计算题（每题10分，共40分）

1.设某计算机系统采用虚拟页式存储管理方法，进程的虚拟地址空间为64KB，页面尺寸为4KB。假设当前进程的页表如右图所示（页表以二进制形式表示），请将虚拟地址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文件的物理结构。假设某文件大小为1028KB，请计算访问以下逻辑块时需要多少次I/O传输：（1）8；（2）300；（3）16。4.设有周期性实时任务集如下表所示，用最早截止期优先算法（EDF算法）和速率单调算法（RMS算法）是否可以调度？画出相应的Gantt图。

四、算法设计（每题10分，共20分）

1.设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式:

-M≤A物品数量－B物品数量≤N

其中M和N为正整数。试用信号灯和PV操作描述A、B两种物品的入库过程。

2.用信号量和PV操作实现读者/写者问题，要求读者优先，即：当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。0250-0252试题A答案

一、

1．虚拟设备是利用共享型设备实现的数量较多、速度较快的独占型设备。

2．进程是具有独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的独立单位。程序是指令的有序序列。进程与程序的区别在于：○1进程是动态的，程序是静态的；○2进程是短暂的，程序可以永久保存；○3进程与程序之间不具有一一对应关系：一个程序可以对应一个进程，也可以对应多个进程；一个进程可以对应一个程序，或者对应一段程序。

5．树型目录结构解决了命名冲突；有利于提高文件的检索速度；有利于实现文件共享；有利于用户对文件进行分门别类地组织。

6．

7．并发执行的进程为了协调一致地完成指定任务，进程之间具有一定的联系，这种联系通常采用进程间交换数据的方式进行。进程间交换数据叫进程通信。进程之间所交换的信息量，少则是一个状态或数值，多则是成千上万个字节。因而进程通信的类型分为：低级通信（进程间交换少量数据，如信号量机制）；高级通信（进程间交换大量数据）。

8．UC/OS-II是一个嵌入式操作系统，其功能包括任务管理、时间管理、任务间通信、内存管理等。二、

（1）[0，350]：由段号0查段表得其段长200，将虚拟地址中的段内偏移350与该段段长相比较：350>200，所以产生越界中断；

（2）[1,25]：由段号1查段表得其段长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，将虚拟地址中的段内偏移20与该段段长相比较：20<150，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：20+4000=4020；三、FIFO页面替换算法：

LRU页面替换算法：

四、semaphorea=n,b=m;

voidmain(){

createprocess(A,…);

createprocess(B,…);

}

voidA(){

while(1){

P(a);

输入化合物A;

V(b);

}

}

voidB(){

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。当m<n时，x=1；当m>n时，x=INT（(m-1)/n）+1，其中INT表示向下取整数。0250-0252操作系统试卷B一、简答题（每题5分，共30分）

1.什么是SPOOLING系统？

2.操作系统有哪些功能？

3.进程与程序有何区别？

4.在文件系统中，为什么将文件控制块FCB分割为两部分？

5.什么是进程通信？

6.什么是死锁？二、填空题（每空1分，共10分）

1.操作系统的两个重要特性是：(1)和(2)。

2.只能在管态下执行的指令称为(3)。处理机状态由目态转换为管态的唯一途径是(4)，管态到目态的转换可以通过修改(5)来实现。

3.进程在其生存期内可以处于如下三种基本状态之一：运行态、就绪态和等待态。当一个就绪进程(6)时，其状态由就绪变为运行，当一个运行进程被抢占处理机时，其状态由运行变为(7)，当一个运行进程因某事件受阻时，其状态由运行变为(8)，当进程所等待的事件已经发生时，该进程状态由(9)变为就绪。

4.线程是进程内的一个相对独立的(10)。

三、计算题（每题10分，共40分）

1.设某计算机系统采用虚拟页式存储管理方法，进程的虚拟地址空间为64KB，页面尺寸为4KB。假设当前进程的页表如右图所示（页表以二进制形式表示），请将虚拟地址8194和2049转换为物理地址。2.设某计算机系统采用虚拟页式存储管理方法，内存中为该进程分配3个物理页架,开始时内存页架为空,假设进程在一段时间内的页面访问序列如下: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文件的物理结构。假设某文件大小为1028KB，请计算访问以下逻辑块时需要多少次I/O传输：（1）6；（2）400；（3）26。4.设有周期性实时任务集如下表所示，用最早截止期优先算法（EDF算法）和速率单调算法（RMS算法）是否可以调度？画出相应的Gantt图。

四、算法设计（每题10分，共20分）

1.对于生产者—消费者问题，假设缓冲区是无界的，试用信号灯与PV操作给出解法。

2.用信号量和PV操作实现读者/写者问题，要求写者优先，即：当有读者和写者同时等待时，首先满足写者。当一个写者声明想写文件时，不允许新的读者再访问文件。0250-0252试题B答案

一、

1．它使用直接存取的大容量磁盘作为缓冲，将一个可共享的磁盘空间改造成若干台输入设备和输出设备，并使得I/O设备与CPU并行操作。SPOOLING系统通常包括井管理模块、预输入模块、缓输出模块组成。

2．重定位用于实现逻辑地址到物理地址的转换。静态重定位是当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）；动态重定位是在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）。

3．操作系统主要有五大功能：存储器管理——内存分配、地址映射、内存保护和内存扩充。处理机管理——作业和进程调度、进程控制和进程通信。设备管理——缓冲区管理、设备分配、设备驱动和设备无关性。文件管理——文件存储空间的管理、文件操作的一般管理、目录管理、文件的读写管理和存取控制。用户界面管理——命令界面、程序界面和图形界面。

4．进程是具有独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的独立单位。程序是指令的有序序列。进程与程序的区别在于：

1)进程是动态的，程序是静态的；

2)进程是短暂的，程序可以永久保存；

3)进程与程序之间不具有一一对应关系：一个程序可以对应一个进程，也可以对应多个进程；一个进程可以对应一个程序，或者对应一段程序。

5．文件控制块（FCB）是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件属性），文件控制块是文件存在的标志。为加快目录检索可采用目录项分解法：把FCB分成两部分，符号目录顶（次部）和基本目录项（主部）6.

7．并发执行的进程为了协调一致地完成指定任务，进程之间具有一定的联系，这种联系通常采用进程间交换数据的方式进行。进程间交换数据叫进程通信。进程之间所交换的信息量，少则是一个状态或数值，多则是成千上万个字节。因而进程通信的类型分为：低级通信（进程间交换少量数据，如信号量机制）；高级通信（进程间交换大量数据）。

8．UC/OS-II是一个嵌入式操作系统，其功能包括任务管理、时间管理、任务间通信、内存管理等。二、

（1）[0，305]：由段号0查段表得其段长200，将虚拟地址中的段内偏移305与该段段长相比较：305>200，所以产生越界中断；

（2）[1,55]：由段号1查段表得其段长100，将虚拟地址中的段内偏移55与该段段长相比较：55<100，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：55+3000=3055；

（3）[2,125]：由段号2查段表得其段长105，将虚拟地址中的段内偏移125与该段段长相比较：125>105，所以产生越界中断；

（4）[3,410]：由段号3查段表得其段长600，将虚拟地址中的段内偏移410与该段段长相比较：410<600，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：410+1200=1610；

（5）[4,50]：由段号4查段表得其段长150，将虚拟地址中的段内偏移50与该段段长相比较：50<150，是合法虚拟地址，所以将段内偏移与该段在主存的起始地址相加得绝对地址：50+4000=4050；三、FIFO页面替换算法：

LRU页面替换算法：

四、intrca=0;/*readersingroupAreadingthefileinaperiodoftime*/

intrcb=0;/*readersingroupBreadingthefileinaperiodoftime*/

semaphoremutexa=1;/*toensureexclusiveaccessto‘rca’*/

semaphoremutexb=1;/*toensureexclusiveaccessto‘rcb’*/

semaphoremutex=1;/*toensureexclusiveaccesstothefile*/

voidreaderrA(){

P(mutexa);

rca++;

if(rca==1)P(mutex)

V(mutexa);

readthefile;

P(mutexa);

rca--;

if(rca==0)V(mutex)

V(mutexa);

}

VoidreaderB(){

P(mutexb;

rcb++;

if(rcb==1)P(mutex);

V(mutexb);

readthefile;

P(mutexb);

rcb--;

if(rcb==0)V(mutex);

V(mutexb)；

}

五、

六、UNIX中的进程可能处于以下九个状态之一：创建、内存就绪、外存就绪、内存睡眠、外存睡眠、核心态执行、用户态执行、剥夺、僵死。UNIX进程的状态转换图如下：七、根据题意，每段最多有16页，每页大小为4KB，则每段大小为16*4KB=64KB；该任务最多有8个段，所以最大逻辑地址空间为8*64KB=512KB。八、设每个进程最多可以请求x个这类资源，为了使系统一定不会发生死锁m,x,n需要满足关系式：n(x-1)+1<=m，即x<=(m-1)/n+1。当m<n时，x=1；当m>n时，x=INT（(m-1)/n）+1，其中INT表示向下取整数。0219—0224，0279操作系统试卷A

一、名词解释（10分，每题2分）

1．操作系统2．进程3．线程4．作业5．中断二、简要回答下述问题（20分，每题4分）

1．常用的文件物理结构有哪几种，请简述它们，至少给出三种。

2．请你简述段页式虚拟存储系统使用的数据结构。

3．请简述SPOOLING系统的组成及各部分的功能。

4．请叙述在进程通信中有哪几种通信方式？

5．什么是地址重定位？动态重定位和静态重地位有何区别？三、在一个支持虚拟分页并采用请求页式调度的存储管理系统中，有一用户程序，它访问其地址空间的字地址序列是：70，74，135，276，400，300，700，266，148，560，284，172问：若分配给该作业的内存大小为384字，初始为空，页大小为128字，试按FIFO、LRU页面淘汰算法，分别计算页面访问的缺页率。（10分）四、在下面的段表中对于以下逻辑地址(段号，单元号)，求对应的物理地址。（10分）

（1）0,400;(2)3,300;(3)1,20;

五、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，作业序列如表所示（表中所列作业优先数即为进程优先数，数值越小优先级越高）。（15分）

①列出所有作业进入内存时间及结束时间。

②计算平均周转时间。

作业的执行时间

六、设由n个缓冲区组成缓冲池，每个缓冲区可以存放一个消息，有两类进程：x个生产者和y个消费者，且只要缓冲池未满，生产者便可以将消息送入缓冲池，而只要缓冲池未空，消费者就可以取走一个消息。各个进程对缓冲池进行互斥访问，用信号量实现协调过程。要求写出使用的信号量、初值及其作用，并写出生产者进程和消费者进程的处理流程（10分）七、假定UNIX系统V中磁盘块地大小为1K，每个磁盘块当用于做间接块时最多可登记256个块号，现在要对一个大小为2000K，已经打开的文件检索一遍，请画出该文件的索引结构，并回答将要发生多少次磁盘传输完成中断？（10分）

八、在银行家算法中，若出现如下资源分配情况：

Allocation

Need

Available

ABCD

ABCD

ABCD

P0

0032

0012

1623

P1

1000

1750

P2

1354

2356

P3

0332

0652

P4

0014

0656

试回答下列问题：（15分）

1、找出一个安全序列。

2、在上述状态下，对于下列由进程P2发出申请命令request(1,2,2,2)，会被接受吗？原因何在？0219-0224、0279操作系统A答案

一、名词解释(10分，每题2分)

1、操作系统：是位于硬件层之上，所有其它软件之下的一个系统软件，是管理系统中的软硬资源，使其得以充分利用并方便用户使用的程序集合。

2、进程：具有一定独立功能的程序关于一个数据集合的一次运行活动。

3、线程：也称轻进程，是进程内的一个相对独立的执行流。

4、作业：用户要求计算机系统为其完成的计算任务的集合。

5、中断：在程序运行过程中，出现的某种紧急事件，必须中止当前正在运行的程序，转去处理此事件，然后再恢复原来运行的程序，这个过程称为中断。二、简要回答下述问题(20分，每题4分)

1、常用文件的物理结构有顺序文件、链接文件、索引结构、Hash结构、倒排结构。

顺序结构：一个文件占有若干个连续的物理块，首块号块数记录在FCB中。

链接结构：一个文件占有若干个不连续的存储块，各块之间以指针相连，其首块号及块数记录于FCB中。

索引结构：一个文件占有若干个不连续的存储块，这些块的号记录于一个索引块中。

2、段页虚拟存储采用的数据结构：

每个作业一张段表

系统一张快表

每个段一张页表

页表控制寄存器

主存一张位示图

段表控制寄存器

3、Spooling系统的组成：

磁盘开辟输入井，输出井，其中输入井用于存放预先读入的作业，输出井保存输出结果。提供预输入程序，负责控制外围设备预先装入用户的作业到输入井中。

缓输出程序：负责控制将输出井中的信息送往外围设备。

井管理程序：负责控制将输入井中的数据读入内存，将程序结果存放到输出井中。

4、进程通信中包括共享内存方式和消息缓冲方式，消息缓冲方式又分为直接通信和间接通信，直接通信分为有缓冲方式和无缓冲方式。

5、地址重定位：指逻辑地址转换为物理地址的过程。

静态重定位：指装入时完成地址转化。

动态重定位：指运行指令时将逻辑地址转化为物理地址。三、(10分)

由题知内存为3块：

地址序列转成页面序列：00123.25.21421

FIFO:

淘汰最先装入主存的页面，使用队列

缺页率=8/12=2/3

LRU：使用栈顶为最新访问项，底为淘汰项

缺页率=7/12四、(10分)

(0,400)的物理地址：200+400=600

(3,300)的物理地址：1300+300=1600

(1,20)的物理地址：因为1段长为14，所以地址越界，出错。五、(10分)

10:00J1进入，运行20分10:00—10:20

10:20J2进入，运行30分10:20—10:50完成

10:50J4进入，级别低于J1，J1运行20分。10:50—11:10J410:50进入主存完成

11:10J3进入，运行50分完成12:0011:00—12:20

12:20J4运行20分钟，结束10:50—12:20

J1：10:00—11:10J2：10:20—10:50J3：11:10—12:00J4：10:50—12:20

TJ1=70分TJ2=30分TJ3=90分TJ4=90分

平均周转时间=70+30+920+90/4=280/4=70分钟六、（10分）七、(10分)

由题知：文件共2000块，由索引结构知前10项直接访问10块，一级访问256块，

2000－256－10＝1734块

1734÷256＝8个索引项（二级索引）

发生中断次数为：1＋1＋7＋2000＝2009次磁盘传输中断。八、（15分）

1）workAllocationNeedfinish

P0162300320012T

P3165403320652T

P4198600140656T

P11991010001750T

P22991013542356T

3121414

存在安全序列P0P3P4P1P2所以此刻是安全的

2）P2发出请求命令request(1,2,2,2)

request<Need(2,3,5,6)合理

Request<Available(1,6,2,3)有资源

试分配：

P2:AllocationNeedAvailable

257611340401

安全检查：WORK=0401不能满足任务资源申请，没有安全序列，所以不安全，取消试探分配，申请者P2等待。0219—0224，0279操作系统试卷B

一、名词解释（10分，每题2分）

1．操作系统2．死锁3．文件4．进程互斥5．系统开销二、简答题（20分，每题4分）

1．简述死锁产生的必要条件。

2．什么是文件系统？文件系统的功能如何？

3．简要回答程序和进程的相同点与差别。

4．在操作系统中，I/O传输方式有哪些？简要说明它们。

5．简述页式存储管理中采用的数据结构。三、设有周期性实时任务集如下表所示，用EDF算法和RMS算法是否可以调度?

画出相应的Gantt图。（10分）

四、在请求页式存储管理方案中，假定某作业J所涉及的页面依次为：0，1，0，2，0，1，0，1，2，0，并已知主存中有3个可供作业J使用的空白存储块(块的大小与页面相同)。试说明采用FIFO和LRU两种不同淘汰算法时，缺页中断率各是多少?（10分）五、设某移动磁盘上共有200个磁道，由外向内依次编号为0～199。又设该磁盘仅配有一个读写磁头，且磁头在完成对于第120号磁道的I/O请求后，正在为第130号磁道的I/O请求服务。假定此时I/O队列中有九个读写请求，所访问磁道列表如下：

到达次序：123456789

访问磁盘：801589117294150102175134

对于先来先服务、电梯磁盘调度算法分别给出访问顺序。（10分）六、假定UNIX系统V中磁盘块地大小为1K，每个磁盘块当用于做间接块时最多可登记256个块号，现在要对一个大小为1000K，已经打开的文件检索一遍，请画出该文件的索引结构，并回答将要发生多少次磁盘传输完成中断？（10分）七、设有多个读进程和多个写进程，它们共享一个内存区，读进程从内存区读出信息，写进程把信息写入内存区，读写规则如下：

1）各个读进程可以同时读，但是当某个读进程正在读时，写进程不能写。

2）当某个写进程正在写时其他写进程和读进程均不能进行。

3）对读进程和写进程的优先顺序不作约定。

试设必要的信号量及赋初值，用P、V操作写出它们的同步算法。（15分）八、某系统中采用“银行家算法”避免死锁，设其资源集合为{A,B,C}，其中资源A含有5个资源实例，资源类B含有10个资源实例，资源类C含有9个资源实例。又设系统中进程集合为{P1，P2，P3，P4}，在时刻T0系统状态如下：

Claim

AllocationNeed

Available

ABC

ABC

ABC

ABC

P1

493

232

261

141

P2

303

202

101

P3

175

023

152

P4

321

011

310

试回答下列问题：（15分）

1、找出一个安全序列。

2、在上述状态下，对于下列由进程P2发出的资源申请命令request(1,0,0)，会被接受吗？原因何在？0219—0224，0279操作系统试卷B答案

一、名词解释（10分，每题2分）

1操作系统

位于硬件层之上，其他所有软件层之下的系统软件，是管理系统的软硬件资源，使其得到充分利用并方便用户使用的程序的集合。

2死锁

一组进程中的每个进程均等待此组进程中某一其他进程所占有的、因而永远无法得到的资源，这种现象称作进程死锁。

3文件

具有符号名而且在逻辑上具有完整意义的信息项的有序序列。

4进程互斥

两个或两个以上的进程，不同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象叫互斥。

5系统开销

指运行操作系统程序，对系统进行管理而花费的时间和空间。二、问答题（20分，每题4分）

1死锁产生的必要条件

资源独占，不可剥夺，保持申请，循环等待。

2文件系统

文件与管理信息资源的程序的集合。

功能

1)管理文件信息、实现对文件的按名存取

2)对辅存空间管理、完成对辅存空间的分配与支配

3程序和进程的联系：程序是构成进程的组成部分之一

其差别在于

1)程序是静态的，进程是动态的

2）程序可以写在纸上或在某一存储介质上长期保存，而进程创建生存、撤销后消失

3）一个程序可以对应多个进程，但一个进程只能对应一个程序

4I/O传输方式

程序查询控制方式、中断方式、DMA方