２００９年全國研究生統一入學考試“操作系統”試卷淺析

季江民　李善平　錢　徽

摘要:本文是作者在評閱“操作系統”試卷后,進行的初步的分析和總結。論文重點對計算機學科專業基礎綜合科目的第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。