附录B　硕士研究生入学考试计算机专业基础综合试题（操作系统部分）

2009年硕士研究生入学考试计算机专业基础综合试题（操作系统部分）

一、单项选择题（1～40题，每题2分共80分。在每个小题给出的4个选项中选择正确答案）

（22）下列选项中，能引起外部中断的事件是__。

A.键盘输入

B.除数为0

C.浮点运算下溢D.访存缺页

【分析】考查中断的分类。

【答案】A

（23）单处理机系统中，可并行的是__。

Ⅰ.进程与进程

Ⅱ.处理机与设备

Ⅲ.处理机与通道

Ⅳ.设备与设备

A.Ⅰ、Ⅱ和Ⅲ

B.Ⅰ、Ⅱ和Ⅳ

C.Ⅰ、Ⅲ和Ⅳ

D.Ⅱ、Ⅲ和Ⅳ

【分析】考查并行性的概念。

单处理机系统中只有一条指令流水线，一个多功能的操作部件，每个时钟周期只能完成一条指令，故进程与进程显然不可以并行。

【答案】D

（24）下列进程调度算法中，综合考虑进程等待时间和执行时间的是__。

A.时间片轮转调度算法

B.短进程优先调度算法

C.先来先服务调度算法

D.高响应比优先调度算法

【分析】考查进程调度算法。

高响应比优先调度算法，同时考虑每个进程的等待时间和需要的执行时间，从中选出响应比最高的进程投入执行。响应比R定义如下：

响应比R=（等待时间+执行时间）/执行时间

【答案】D

（25）某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是__。

A.2

B.3

C.4

D.5

【分析】考查死锁的条件。

考虑极端情况，每个进程最多需要3台打印机，如果每个进程已经占用了两台打印机，只要还有剩余的打印机，总能满足需要3台的要求。因此，将8台打印机分给K个进程，每个进程拥有2台打印机，K为4时就是极端情况。

【答案】C

（26）分区分配内存管理方式的主要保护措施是__。

A.界地址保护

B.程序代码保护

C.数据保护

D.栈保护

【分析】考查分区存储管理方式的保护。分区存储管理方式的保护方法之一是设置界地址寄存器。

【答案】A

（27）一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是__。

A.2^8字节

B.2^16字节

C.2^24字节

D.2^32字节

【分析】考查分段存储管理。

段地址为32位二进制数，其中8位表示段号，则段内偏移为32-8=24位二进制数，故最大段长为2^24字节。

【答案】C

（28）下列文件物理结构中，适合随机访问且易于文件扩展的是__。

A.连续结构

B.索引结构

C.链式结构且磁盘块定长

D.链式结构且磁盘块变长

【分析】考查文件的物理结构。

【答案】B

（29）假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35、45、12、68、110、180、170、195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是__。

A.110、170、180、195、68、45、35、12

B.110、68、45、35、12、170、180、195

C.110、170、180、195、12、35、45、68

D.12、35、45、68、110、170、180、195

【分析】考查磁盘调度算法。

电梯调度的思想。首先，磁头选择与当前磁头所在磁道距离最近的请求作为首次服务的对象（110），当磁头沿途相应访问请求序列直到达到一端末（110，170，180，195），再反向移动响应另一端的访问请求（68，45，35，12）。

【答案】A

（30）文件系统中，文件访问控制信息存储的合理位置是__。

A.文件控制块

B.文件分配表

C.用户口令表

D.系统注册表

【分析】考查文件控制块的内容。

在文件控制块中，通常含有以下3类信息，即基本信息、访问控制信息及使用信息。

【答案】A

（31）设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是__。

A.0、1

B.1、1

C.1、2

D.2、1

【分析】考查软/硬链接建立的属性。

建立符号链接（软链接）时，引用计数值直接复制；建立硬链接时，引用计数值加1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接；但是对于硬链接则不可以直接删除，引用计数值减1，若值不为0，则不能删除此文件，因为还有其他硬链接指向此文件。

【答案】B

（32）程序员利用系统调用打开I/O设备时，通常使用的设备标志是__。

A.逻辑设备名

B.物理设备名

C.主设备号

D.从设备号

【分析】考查系统调用的设备标志。

用户程序采用逻辑设备名对I/O设备进行访问。物理设备名在程序实际执行时使用。

【答案】A

二、综合应用题（41～47小题，共70分）

（45）（7分）3个进程P1、P2、P3互斥使用一个包含N（N＞0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这3个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

【分析】定义信号量s1控制P1与P2之间的同步；s2控制P1与P3之间的同步；empty控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。程序如下：

Var s1=0,s2=0,empty=N,mutex=1;

Parbegin

P1:begin

X=produce();//生成一个数

P(empty);//判断缓冲区是否有空单元

P(mutex);//判断缓冲区是否被占用

Put();

If x%2==0

V(s2);//如果是偶数，向P3发出信号

else

V(s1);//如果是奇数，向P2发出信号

V(mutex);//使用完缓冲区，释放

end

P2:begin

P(s1);//收到P1发来的信号，已产生一个奇数

P(mutex);//缓冲区是否被占用

Getodd();

Countodd():=countodd()+1;

V(mutex);//释放缓冲区

V(empty);//向P1发信号，多出一个空单元

end

P3:begin

P(s2)//收到P1发来的信号，已产生一个偶数

P(mutex);//缓冲区是否被占用

Geteven();

Counteven():=counteven()+1;

V(mutex);//释放缓冲区

V(empty);//向P1发信号，多出一个空单元

end

Parend

（46）（8分）请求分页管理系统中，假设某进程的页表内容如表B-1所示。

页面大小为4KB，一次内存的访问时间是100纳秒（ns），一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为10^8ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法和局部淘汰策略。假设1）TLB初始为空；2）地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；3）有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设虚地址访问序列2362H、1565H、25A5H，请问：

1）依次访问上述3个虚地址，各需多少时间？给出计算过程。

【分析】根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即2^12，得到页内偏移占虚地址的低12位，页号占剩余高位。可得3个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低3位正好为页内位移，最高位为页号）：

2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。

1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理10^8ns，合成物理地址后访问主存100ns，共计10ns+100ns+10^8ns+100ns≈10^8ns。

25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。

2）基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。

【分析】当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。