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