部分高校操作系统硕士研究生入学试题参考答案
北京航空航天大学2002年硕士入学操作系统试题参考答案
一、简答题（20分）
- 操作系统的基本特征是什么？
答：
并发性（concurrence）是指两个或两个以上的事件或活动在同一时间间隔内发生。操作系统是一个并发系统，并发性是它的重要特征，操作系统的并发性指计算机系统中同时存在若干个运行着的程序，因此，它应该具有处理和调度多个程序同时执行的能力。
共享性是指计算机系统中的资源（包括硬件资源和信息资源）可被多个并发执行的用户程序和系统程序共同使用，而不是被其中某一个程序所独占。又可分互斥访问和共享访问。
异步性是指在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况下，进程的执行不是一贯到底，而是“走走停停”。异步性给系统带来了潜在的危险，有可能导致进程产生与时间有关的错误，操作系统必须保证多次运行进程，都会获得完全相同的结果。
虚拟性是指操作系统中的一种管理技术，它是把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。例如，在多道程序系统中，物理CPU可以只有一个，每次也仅能执行一道程序，但通过多道程序和分时使用CPU技术，宏观上有多个程序在执行，就好像有多个CPU在为各道程序工作一样，物理上的一个CPU变成了逻辑上的多个CPU。虚拟存储器则是把物理上的多个存储器(主存和辅存)变成逻辑上的一个(虚存)的例子。
- 什么是死锁？死锁的原因是什么？
答：
如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。
- 信号量的物理意义是什么？
答：
信号量S的值表示它代表的物理资源的使用状态：S>0表示还有共享资源可供使用。S=0表示共享资源正被进程使用但没有进程等待使用资源。S<0表示资源已被分配完，还有进程等待使用资源。
- 什么是进程？进程的基本特征？
答：
进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。它具有结构性、共享性、动态性、独立性、制约性、并发性等特征。
二、判断题（5分）
1．当一个进程从等待态变成就绪态，就一定有一个进程从就绪态变成运行态。(错)
2．在请求页式存储管理中，页面淘汰所花费的时间不属于系统开销。(错)
3．在中断处理过程中，必须屏蔽中断。(对)
- 在有虚拟存储器的系统中，可以运行比主存容量还大的程序。(对)
6．打印机是一类典型的字符设备。(错)
三、考虑一仅460B的程序的下述内存的访问序列（该序列的下标均从0开始）10，11，104，170，73，309，185，245，246，434，458，364，且页面大小为100B，则（1）写出页面的访问序列。（2）假设内存中仅有200 B可供程序使用且采用FIFO算法，那么共发生多少次缺页中断？ （3）如果采用最近最久未使用算法（LRU），则又会发生多少次缺页中断? （10分）
答：设逻辑地址为L，页面大小为M(=100B)，故虚页号P=[L/M]
- 页面的访问序列为：0、0、1、1、0、3、1、2、2、4、4、3。
- 6次
- 7次
四、在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车：售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用P，V操作实现司机与售票员之间的同步。（10分）
答：
var s1，s2：semaphore；
s1=0； s2=0;
cobegin
{
driver ( );
busman ( );
}
coend
driver ( )
begin
while(1)
{
P(s1)
启动车辆；
正常行车；
到站停车；
V(s2);
}
end
busman ( )
begin
while(1)
{
关车门；，
V(s1)
售票；
P(s2)
开车门；
上下乘客；
}
end
五、下面是两个并发执行的进程。它们能正确运行吗？若不能请举例说明，并改正之。（5分）
parbegin
var x：integer;
process P1 process P2
var y，z：integer： var t,u：integer；
begin begin
x:=1； x:=0：
y:=0： t=0；
if x≥l then y:=y十1； if x≤l then t:=t+2；
z:=y； u:=t；
end； end；
parend.
答：显然，由于有共享变量x，并发执行时会产生与时间有关的错误。例P1先运行，程序执行完后z=1，而u=2。但若P1执行x:=1后暂仃，进程P2执行，此时x的值又重新赋0。待进程P2执行结束后，P1再运行，结果z=0，u=2。从而，结果不唯一。改正后程序为：
parbegin
var x：integer;mutex:semaphore;mutex:=1;
process P1 process P2
var y，z：integer： var t,u：integer；
begin begin
P(mutex); P(mutex);
x:=1； x:=0：
y:=0： t=0；
if x≥l then y:=y十1； if x≤l then t:=t+2；
V(mutex); V(mutex);
z:=y； u:=t；
end； end；
parend.
北京理工大学2001年硕士入学操作系统试题参考答案
一、选择填空题（10分）
1.在单处理机系统中实现并发技术后，（ (2) ）。
（1）各进程在某一时刻并行运行，CPU与外设间并行工作
（2）各进程在一个时间段内并行运行，CPU与外设间并行工作
（3）各进程在一个时间段内并行运行，CPU与外设间串行工作
（4）各进程在某一时刻并行运行，CPU与外设间串行工作
2.在进程的生命期内，进程与其执行的程序个数之间是（ (2) ）关系。
（1）一对一 （2）一对多 （3）多对一 （4）多对多
3.文件系统中的路径名是由（ (3) ）组成。
（1）磁盘符和目录名
（2）文件名和目录名
（3）磁盘符、目录结构的各个目录名、文件名
（4）磁盘符、根目录名、 文件名
4.在内存管理模式中，内存利用率最高的是（ (2) ）模式：动态扩充实现得最好的是（ (3) ）模式；内存利用率最高且保护和共享容易的是（ (4) ）模式。（1）分区管理 （2）分页管理 （3） 分段管理 （4）段页式管理
5.在SPOOLing系统中，用户进程实际分配到的是（ (3) ）。
（1）用户所要求的外设 （2）一块内存区，即虚拟设备
（3）共享设备的一部分存储区 （4）虚拟设备的一部分空间
6.按照地址映射的时机不同，可以分为（ (2) ）和（ (4) ）。
（1）静态分配 （2）静态重定位（3）动态分配 （4）动态重定位
7.用户及其应用程序和应用系统是通过（ (3) ）提供的支持和服务来使用系统资源完成其操作的。
（1）点击鼠标 （2）键盘命令 （3）系统调用 （4）图形用户界面
二、正误判断题（5分）
1.原语可以被多个进程同时执行。(错)
2.对文件进行检索时，检索的起点必须是根目录而不是其他目录。(错)
3．并发性是指若干个事件在不同的时刻发生。(错)
4．死锁是系统中的全部进程都处于阻塞状态。(错)
5．在用P，V操作解决进程之间的同步与互斥时，一定要正确地安排P，V操作的顺序，否则会引起死锁。(对)
三、简答题（15分）
- 在设备管理中，何谓设备的独立性？如何实现设备的独立性？
答：用户编程时，指定逻辑设备，使用户程序独立于物理设备，再通过适当途径建立逻辑设备与物理设备的对应关系，称设备的独立性。实现设备的独立性的主要方法是程序员利用逻辑设备I/O，而逻辑设备与物理设备的对应转换可由操作系统命令或语言实现。
2.在UNIX系统中，每个i节点中分别含有10个直接地址的索引和一、二、三级间接索引。若每个盘块放128个盘块地址，则一个1MB的文件分别占用多少间接盘块？20MB的文件呢？设每个盘块有512B。
答：
直接块容量=10×512B/1024=5KB
一次间接容量=128×512B/1024=64KB
二次间接容量=128×128×512B/1024=64KB×128=8192KB
三次间接容量=128×128×128×512B/1024=64KB×128=8192KB×128=1048576KB
1MB为1024KB，1024KB-69KB=955KB，955×1024B/512B=1910块，1MB的文件分别占用1910个二次间接盘块。
20×1024KB-69-8192=12219KB，12219×1024B/512=24438块，20MB的文件分别占用24438个三次间接盘块和8192个二次间接盘块。
3.假定一个处理机正在执行两道作业，一道作业以计算为主，另一道以I/O为主，你将怎样为它们分配优先级？为什么？
答：
优先级调度的基本原则是：照顾时间紧迫的作业使其得到及时处理、照顾会话型作业使其快速响应、照顾I/O繁忙型作业，使外设充分保持忙碌。故I/O为主的作业对应的进程优先级高，而以计算为主的作业对应的进程优先级低。
4.列举出操作系统向用户提供的接口方式。
答：操作系统通过程序接口和操作接口两种方式把它的服务和功能提供给用户。
程序接口又称应用编程接口，由一组系统调用（system call）组成，用户在编写的程序中使用“系统调用”就可获得操作系统的底层服务，使用或访问系统管理的各种软硬件资源。
操作接口又称作业(或功能)接口，是操作系统为用户操作控制计算机工作和提供服务的手段的集合，通常可借助操作控制命令、图形操作界面(命令)、以及作业控制语言(命令)等等来实现。
四、一条南北方向的公路桥，任何时候同时只能有一个方向的汽车通过它。试用P，V操作写出南向或北向的一辆车到达桥时，通过它，然后离开它到达对岸的同步算法。（桥上可以有多辆车）（10分）
答：
var mutex1,mutex2:semaphore;
mutex1:=mutex2:=1;wait:=0;
count1,count2:integer;
cobegin
{
process P南汽车 process P北汽车
begin begin
P(mutex1); P(mutex2);
count1++; count2++;
if count1=1 then P(mutex2); if count2=1 then P(mutex1);
V(mutex1); V(mutex2);
过桥; 过桥;
P(mutex1); P(mutex2);
Count1-- count2--;
if count1=0 then V(mutex2); if count2=0 then P(mutex1);
V(mutex1); V(mutex2);
end end
}
coend
五、设某分页系统中，页帧的大小为100字。一个程序大小为1200个字，可能的访问序列为：10，205，110，735，603，50，815，314，432，320，225，80，130，270。系统采用LRU算法。当为其分配4个内存块时，给出该作业驻留的各个页的变化情况及页故障率。（10分）
解：
因页面大小为100字，故程序大小为12个页面，访问序列为：0、2、1、7、6、0、8、3、4、3、2、0、1、2。
共11次缺页，缺页率为11/14。淘汰页面为：0、2、1、7、6、0、8。
六、假定系统有进程集合（Po，Pl，P2，P3，P4），资源集合为（A，B，C），资源数量分别为（10，8，7）。假定某时刻系统的状态如表所示。
|
|
Allocation |
MAX |
Available |
||||||
|
|
A |
B |
C |
A |
B |
C |
A |
B |
C |
|
PO |
0 |
2 |
0 |
7 |
7 |
3 |
3 |
3 |
1 |
|
P1 |
2 |
1 |
0 |
3 |
3 |
2 |
|
|
|
|
P 相关话题/操作系统
| |||||||||
