２００９年全国研究生统一入学考试“操作系统”试卷浅析

季江民　李善平　钱　徽

摘要:本文是作者在评阅“操作系统”试卷后,进行的初步的分析和总结。论文重点对计算机学科专业基础综合科目的第45题各种答案进行了评析。最后针对某省考生的计算机学科专业基础综合科目得分情况进行了分析。

关键词:计算机学科专业基础综合;操作系统;考试

中图分类号:G642 文献标识码:B

1引言

教育部决定,从2009年起对全国硕士研究生统一入学考试计算机科学与技术学科的初试科目进行调整及命题形式进行改革。计算机科学与技术学科的初试科目调整后为4门,即政治理论、外国语、数学一和计算机学科专业基础综合。计算机学科专业基础综合的考试内容包括:数据结构、计算机组成原理、操作系统和计算机网络,重点考查考生掌握相关基础知识、基本理论和分析问题解决问题的能力。

根据2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲的规定,试卷的内容结构为:数据结构45分,占30%;计算机组成原理45分,占30%;操作系统35分,约占23%;计算机网络25分,约占17%。试卷题型结构为:单项选择题80分(40小题,每小题2分),综合应用题70分。计算机学科专业基础综合总分为150分。

从2009年的试题看,试卷题目分布如下:

(1) 数据结构范围内的选择题10题(第1～10题),每题2分,共20分;综合应用题2题(第41、42题),共25分;总计是45分。

(2) 计算机组成原理范围内的选择题12题(第11～22题),每题2分,共24分;综合应用题2题(第43、44题),共21分;总计是45分。

(3) 操作系统范围内的选择题10题(第23～32题),每题2分,共20分;综合应用题2题(第45、46题),第45题7分、第46题8分,共15分;总计是35分。

(4) 计算机网络范围内的选择题8题(第33～40题),每题2分,共16分;综合应用题1题(第47题),共9分;总计是25分。

22009年“操作系统”考题分析

2009年计算机学科专业基础综合科目考试操作系统第23-32题是选择题,第45、46题是综合应用题。

第23题考查并发和并行概念;第24题考查进程调度算法;第25题考查因进程竞争资源产生的死锁问题;第26题考查内存保护方法;第27题考查分段存储管理的地址结构概念;第28题考查文件系统的各种存储空间分配方法;第29题考查磁盘调度算法;第30题考查文件属性的存储问题;第31题考查Unix/Linux文件硬链接和符号链接概念;第32题考查逻辑设备概念。

第46题考查是请求分页存储管理,计算从虚拟地址到物理地址变换所需要的时间和给定虚拟地址计算物理地址。看上去很简单,但这个题比较综合,它综合了从虚拟地址到物理地址变化的所有过程和机制,包括缺页中断处理、页面置换算法、TLB等。

第45题是进程同步算法,这个题目是生产者和消费者问题的延伸。本文作者参加了2009年全国硕士研究生统一入学考试操作系统试题的阅卷工作,我们收集了第45题各种答案,给出了标准答案,并列举了3种典型的错误解法(为节省版面我们在代码编程风格上进行了调整)。

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

第45题标准答案:

(1) 缓冲区是一互斥资源,因此设互斥信号量mutex。

(2) 同步问题:P1、P2因为奇数的放置与取用而同步,设同步信号量odd;P1、P3因为偶数的放置于取用而同步,设同步信号量even;P1、P2、P3因为共享缓冲区,设同步信号量empty。

semaphore mutex = 1,odd = 0,even = 0,empty = N;

main()

cobegin{

Process P1

while(true)

{number = produce();

P(empty);P(mutex);

put();

V(mutex);

If number % 2 == 0

V(even);

else

V(odd);}

Process P2

while(true)

{ P(odd); P(mutex);

getodd();

V(mutex);V(empty);

countodd();}

Process P3

while(true)

{ P(even); P(mutex);

geteven();

V(mutex);V(empty);

counteven(); }

}coend

典型错误1:使用三个信号量答题

(1) 缓冲区是一互斥资源,因此设互斥信号量mutex。

(2) 同步问题:设互斥信号量full通知缓冲区有可用资源;P1、P2、P3因为共享缓冲区,设同步信号量empty。

semaphore mutex = 1,full = 0, empty = N;

main()

cobegin{

Process P1

while(true)

{number = produce();

P(empty);P(mutex);

put();

V(mutex);V(full);}

Process P2

while(true)

{ P(full); P(mutex);

Boolean ok = getodd();

V(mutex);

If (ok)

{V(empty); countodd();} }

Process P3

while(true)

{ P(full); P(mutex);

Boolean ok = geteven();

V(mutex);

If (ok)

{ V(empty);counteven();} }

}coend

这种解法有两个主要错误。其一,题目并未定义getodd()和geteven()的返回值,与题意不甚符合;其二,即使上述两函数可以返回取数成功与否,也不满足有限等待的原则。因为,P2和P3进入存取缓冲区,都要通过P(full)和P(mutex),因此,有可能总是P2得到进入的机会,从而使P3无法进入,没有实现同步,导致不满足有限等待的原则。

典型错误2:使用五个信号量答题

(1) 缓冲区是一互斥资源,因此设互斥信号量mutex。

(2) 同步问题:P1、P2因为奇数的放置与取用而同步,设同步信号量odd;P1、P3因为偶数的放置于取用而同步,设同步信号量even;设互斥信号量full通知缓冲区有可用资源;P1、P2、P3因为共享缓冲区,设同步信号量empty。