國防科技大學(xué)研究生院1999年碩士生入學(xué)考試
軟件技術(shù)（操作系統(tǒng)部分）
考生注意：1．答案必須寫在我校統(tǒng)一配發(fā)的答題紙上
2．統(tǒng)考生做 一、1,2,3 二、1,2,3,4 三、1,2,3，4，5（1）（3）
3．單獨考生做一、1,2,4 二、1,2,3,5 三、1,2,3，4，5（1）（2）
一．（40分）操作系統(tǒng)部分
1． （共20分，每小題5分）回答如下問題：
（1） 在設(shè)備管理中，何謂設(shè)備獨立性？如何實現(xiàn)設(shè)備獨立性？
（2） 給出一個程序的優(yōu)先圖如下，試用并發(fā)語句parbegin / parend 寫出相應(yīng)的并發(fā)程序
（3） 下面的算法是解決兩個臨界段問題的解法，試判斷其正確性。如果不正確，舉例說明該算法違背了關(guān)于臨界段問題的哪條準(zhǔn)則。
兩個進(jìn)程P0，P1共享如下變量：
Var flag : array [0…1] of Boolean;
turn : 0..1;
其中flag數(shù)組元素初值均為false。turn的初值為0或1
進(jìn)程Pi（i=0或1,j=1－i ）所對應(yīng)的程序表示為：
repeat
flag : = true ;
while turn<> i do
begin
while flag do skip ;
turn : = i ;
end;
…
Critical section
…
non_Critical section
until false ;
（4） 在磁盤上有一個文件系統(tǒng)，磁盤每塊512字。假定每個文件在目錄中占有一個目錄項，該目錄項給出了文件名。第一個索引塊的地址，文件長度（塊數(shù)）。在索引塊中（包括第一個索引項）前面511個字指向文件塊，即第i個索引項（i = 0,1,…,510）指向文件的第i塊，索引塊中最后一個字指向下一個索引塊，最后一個索引塊中最后一個字為nil。假定目錄在存儲器中，每個文件的邏輯塊號均從0開始編號，邏輯塊長與物理塊長相同。對這關(guān)的索引物理結(jié)構(gòu)。該系統(tǒng)應(yīng)如何將邏輯塊號變換成物理塊號？
2．（11分）假定具有5個進(jìn)程的進(jìn)程集合P＝｛P0,P1,P2,P3,P4｝,系統(tǒng)中有三類資源A，B和C。其中A類資源有10個，B類資源有5個，C類資源有7個。假定在某時刻有如下狀態(tài)：
Allocation Max Available
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
試給出Need，并說明當(dāng)前系統(tǒng)是否處于安全狀態(tài)，如果是，給出安全序列。如果不是，說明理由。
3．（9分）設(shè)某程序大小為1000個字，考慮如下訪問序列：202，610，825，110，50，434，358，210，108，95，276，101 。頁幀大小為100個字。
（1） 試給出訪問串。
（2） 取出控制參數(shù)∆＝4時，分別給出用WS（working set ）和VMIN（Variable Minimal replacement）兩種算法控制該訪問串時，駐留集的變化情況及頁故障率。
4．（9分）在某段式系統(tǒng)中，某道作業(yè)被分成5個段，其段表如下：
段長 始地址
600 14 10058096 21923009013271952
現(xiàn)給出如下6個邏輯地址：（0，430），（1，10），（2，500），（3，400），（4，112）和（5，120），請分別求出它們的物理地址（若不能求出，說明理由）。
軟件技術(shù)（含數(shù)據(jù)庫原理、編譯原理和操作系統(tǒng)原理）
操作系統(tǒng)原理命題標(biāo)準(zhǔn)答案、評分標(biāo)準(zhǔn)
一．（40分）操作系統(tǒng)部分
1． （共20分，每小題5分）回答如下問題：
（1） 設(shè)備獨立性是指用戶程序獨立于所使用的具體物理設(shè)備。即用戶只使用邏輯設(shè)備名。為實現(xiàn)設(shè)備獨立性，系統(tǒng)應(yīng)為每個用戶進(jìn)程配置1張用于聯(lián)系邏輯設(shè)備名和物理設(shè)備名的映射表，表中一般應(yīng)包含：邏輯設(shè)備名，物理設(shè)備名和驅(qū)動程序入口地址。
（2）
Var a , b , c , d , e , f , g : Semaphores ;{初始值都為0}
Parbegin
begin S1; V(a) ; V(b) ; end
begin P(a) ; S2 ; S4 ; V(c) ; V(d) ; end
begin P(b) ; S3 ; V(e) ; end
begin P(c) ; S5 ; V(f) ; end
begin P(d) ; P(e) ; S6 ; V(g) end
begin P(f) ; P(g) ;P(g) ; S7; end
Parend
（3） 該解法不正確，違背了臨界段問題的互斥準(zhǔn)則。
例如：令turn = 1,當(dāng)P0執(zhí)行到第二個while do 語句并使之在此時中斷，并P1執(zhí)行，而P1要進(jìn)入CS，并能成功地進(jìn)入CS0，當(dāng)P1正在CS執(zhí)行時發(fā)生中斷，進(jìn)程P0執(zhí)行，P0此時也能進(jìn)入CS，導(dǎo)致P0、P1均進(jìn)入各自的CS。
（4） 首先通過文件名在目錄中找到該目錄項，根據(jù)給出的邏輯塊j，與文件長度（目錄中）比較，如果j>文件長度則報錯返回。否則，判 j>=510
如果是讀入第一個索引塊，用j作索引，由該索引塊中可獲得物理塊地址。
如果 510＜j <=1022
則由第一個索引塊的最后一個字所指出的下一個索引塊地址，讀入該索引塊，并用j作索引。由該索引塊可獲得物理塊地址。依此類推。
2．（11分）
當(dāng)前系統(tǒng)處于安全狀態(tài)，安全序列如下求解：
work = Available = (3 , 3 , 2 )
尋找 Needj <= work = ( 3 , 3 , 2 ) ( j = 0 , 1 , 2 , 3 , 4)
j = 1 Need1 = (1 ,2 ,3 ) < = (3 , 3 , 2 )
work : = (3 , 3 , 2 ) (2 ,0 ,0 ) = (5 , 3 , 2 )
尋找 Needj <= work = ( 5 , 3 , 2 ) ( j = 0 , 2 , 3 , 4)
j = 3 Need3 = (0 ,1 ,1 ) < = (5 , 3 , 2 )
work : = (5 , 3 , 2 ) (2 ,1 ,1 ) = (7 , 4 , 3 )
尋找 Needj <= work = (7 , 4 , 3 ) ( j = 0 , 2 , 4)
j = 4 Need4 = (4 ,3 ,1 ) < = (7 , 4 , 3 )
work : = (7 , 4 , 3 ) (0 ,0 ,2 ) = (7 , 4 , 5)
尋找 Needj <= work = (7 , 4 , 5) (j = 0 , 2 )
j = 2 Need2 = (6 ,0 ,0 ) < = (7 , 4 , 5 )
work : = (7 , 4 , 5 ) (3 ,0 ,2 ) = (10 , 4 , 7)
尋找 Needj <= work = (10 , 4 , 7) ( j = 0 )
j = 0 work : = (10 , 4 , 7 ) (0 ,1 ,0 ) = (10 , 5 , 7)
所以安全序列為＜P1，P3，P4，P2，P0＞。
3．（9分）
（1） 訪問串為2，6，8，1，0，3，5，4，3，2，1，0，2，1
（2） WS
訪問串 2 6 8 1 0 3 5 4 3 2 1 0 2 1
駐留集 2 2 2 2 0 0 0 0 3 3 3 3 1 1
6 6 6 6 3 3 3 5 5 1 1 0 0
8 8 8 8 5 5 4 4 4 0 2 2
1 1 1 4 2 2 2
-------------------------------------------------------------------------------------------------------------
大小 1 2 3 4 4 4 4 4 3 4 4 4 3 3
頁故障 X X X X X X X X X X X 11次
VMIN
訪問串 2 6 8 1 0 3 5 4 3 2 1 0 2 1
駐留集 2 6 8 1 0 3 3 3 3 2 2 2 2 1
5 4 1 1 1
0
-------------------------------------------------------------------------------------------------------------
大小 1 1 1 1 1 1 2 2 1 1 2 3 2 1
頁故障 X X X X X X X X X X X 11次
4．（9分）
（0，430）物理地址 219＋430＝649
(1，10) 物理地址 2300＋10＝2310
(2，500) 500大于段長，越界，不能轉(zhuǎn)換
(3，400) 物理地址 1327＋400＝1727
(4，112) 112＞段長96不能轉(zhuǎn)換，越界。
(5，120) 段號越界，不能轉(zhuǎn)換。
結(jié)束
特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；
②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。
招生服務(wù)平臺始創(chuàng)于1999年
打開微信掃一掃，關(guān)注育路教育官方微信
