２００９年全國研究生統(tǒng)一入學(xué)考試“操作系統(tǒng)”試卷淺析

季江民　李善平　錢　徽

摘要:本文是作者在評閱“操作系統(tǒng)”試卷后,進(jìn)行的初步的分析和總結(jié)。論文重點(diǎn)對計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合科目的第45題各種答案進(jìn)行了評析。最后針對某省考生的計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合科目得分情況進(jìn)行了分析。

關(guān)鍵詞:計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合;操作系統(tǒng);考試

中圖分類號:G642 文獻(xiàn)標(biāo)識碼:B

1引言

教育部決定,從2009年起對全國碩士研究生統(tǒng)一入學(xué)考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的初試科目進(jìn)行調(diào)整及命題形式進(jìn)行改革。計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的初試科目調(diào)整后為4門,即政治理論、外國語、數(shù)學(xué)一和計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合。計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合的考試內(nèi)容包括:數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理、操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò),重點(diǎn)考查考生掌握相關(guān)基礎(chǔ)知識、基本理論和分析問題解決問題的能力。

根據(jù)2009年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考試大綱的規(guī)定,試卷的內(nèi)容結(jié)構(gòu)為:數(shù)據(jù)結(jié)構(gòu)45分,占30%;計(jì)算機(jī)組成原理45分,占30%;操作系統(tǒng)35分,約占23%;計(jì)算機(jī)網(wǎng)絡(luò)25分,約占17%。試卷題型結(jié)構(gòu)為:單項(xiàng)選擇題80分(40小題,每小題2分),綜合應(yīng)用題70分。計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合總分為150分。

從2009年的試題看,試卷題目分布如下:

(1) 數(shù)據(jù)結(jié)構(gòu)范圍內(nèi)的選擇題10題(第1～10題),每題2分,共20分;綜合應(yīng)用題2題(第41、42題),共25分;總計(jì)是45分。

(2) 計(jì)算機(jī)組成原理范圍內(nèi)的選擇題12題(第11～22題),每題2分,共24分;綜合應(yīng)用題2題(第43、44題),共21分;總計(jì)是45分。

(3) 操作系統(tǒng)范圍內(nèi)的選擇題10題(第23～32題),每題2分,共20分;綜合應(yīng)用題2題(第45、46題),第45題7分、第46題8分,共15分;總計(jì)是35分。

(4) 計(jì)算機(jī)網(wǎng)絡(luò)范圍內(nèi)的選擇題8題(第33～40題),每題2分,共16分;綜合應(yīng)用題1題(第47題),共9分;總計(jì)是25分。

22009年“操作系統(tǒng)”考題分析

2009年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合科目考試操作系統(tǒng)第23-32題是選擇題,第45、46題是綜合應(yīng)用題。

第23題考查并發(fā)和并行概念;第24題考查進(jìn)程調(diào)度算法;第25題考查因進(jìn)程競爭資源產(chǎn)生的死鎖問題;第26題考查內(nèi)存保護(hù)方法;第27題考查分段存儲管理的地址結(jié)構(gòu)概念;第28題考查文件系統(tǒng)的各種存儲空間分配方法;第29題考查磁盤調(diào)度算法;第30題考查文件屬性的存儲問題;第31題考查Unix/Linux文件硬鏈接和符號鏈接概念;第32題考查邏輯設(shè)備概念。

第46題考查是請求分頁存儲管理,計(jì)算從虛擬地址到物理地址變換所需要的時(shí)間和給定虛擬地址計(jì)算物理地址?？瓷先ズ芎唵?但這個(gè)題比較綜合,它綜合了從虛擬地址到物理地址變化的所有過程和機(jī)制,包括缺頁中斷處理、頁面置換算法、TLB等。

第45題是進(jìn)程同步算法,這個(gè)題目是生產(chǎn)者和消費(fèi)者問題的延伸。本文作者參加了2009年全國碩士研究生統(tǒng)一入學(xué)考試操作系統(tǒng)試題的閱卷工作,我們收集了第45題各種答案,給出了標(biāo)準(zhǔn)答案,并列舉了3種典型的錯(cuò)誤解法(為節(jié)省版面我們在代碼編程風(fēng)格上進(jìn)行了調(diào)整)。

第45題題目:三個(gè)進(jìn)程P1、P2、P3互斥使用一個(gè)包含N(N>0)個(gè)單元的緩沖區(qū)。P1每次用produce()生成一個(gè)正整數(shù)并用put()送入緩沖區(qū)某一個(gè)空單元中;P2每次用getodd()從該緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd()統(tǒng)計(jì)奇數(shù)個(gè)數(shù);P3每次用geteven()從該緩沖區(qū)中取出一個(gè)偶數(shù)并用counteven()統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請用信號量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng),并說明所定義的信號量的含義。要求用偽代碼描述。

第45題標(biāo)準(zhǔn)答案:

(1) 緩沖區(qū)是一互斥資源,因此設(shè)互斥信號量mutex。

(2) 同步問題:P1、P2因?yàn)槠鏀?shù)的放置與取用而同步,設(shè)同步信號量odd;P1、P3因?yàn)榕紨?shù)的放置于取用而同步,設(shè)同步信號量even;P1、P2、P3因?yàn)楣蚕砭彌_區(qū),設(shè)同步信號量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

典型錯(cuò)誤1:使用三個(gè)信號量答題

(1) 緩沖區(qū)是一互斥資源,因此設(shè)互斥信號量mutex。

(2) 同步問題:設(shè)互斥信號量full通知緩沖區(qū)有可用資源;P1、P2、P3因?yàn)楣蚕砭彌_區(qū),設(shè)同步信號量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

這種解法有兩個(gè)主要錯(cuò)誤。其一,題目并未定義getodd()和geteven()的返回值,與題意不甚符合;其二,即使上述兩函數(shù)可以返回取數(shù)成功與否,也不滿足有限等待的原則。因?yàn)?P2和P3進(jìn)入存取緩沖區(qū),都要通過P(full)和P(mutex),因此,有可能總是P2得到進(jìn)入的機(jī)會(huì),從而使P3無法進(jìn)入,沒有實(shí)現(xiàn)同步,導(dǎo)致不滿足有限等待的原則。

典型錯(cuò)誤2:使用五個(gè)信號量答題

(1) 緩沖區(qū)是一互斥資源,因此設(shè)互斥信號量mutex。

(2) 同步問題:P1、P2因?yàn)槠鏀?shù)的放置與取用而同步,設(shè)同步信號量odd;P1、P3因?yàn)榕紨?shù)的放置于取用而同步,設(shè)同步信號量even;設(shè)互斥信號量full通知緩沖區(qū)有可用資源;P1、P2、P3因?yàn)楣蚕砭彌_區(qū),設(shè)同步信號量empty。