重慶郵電大學(xué)《操作系統(tǒng)》考試試卷

1、試題編號： 重慶郵電大學(xué)2014-2015學(xué)年一學(xué)期 操作系統(tǒng)試卷（期末） （a 卷） （閉卷） 題 號 一 二 三 四 五 六 七 八 總 分 得 分 評卷人 一、簡答題（本大題共小題，共 40 分） 、現(xiàn)代 os 的主要目標(biāo)是什么? （本題分） 、試從交互性，及時性和可靠性方面，比較分時系統(tǒng)與實時系統(tǒng)的區(qū)別 （本題分） 、進程和程序有什么區(qū)別，請從動態(tài)性，并發(fā)性和獨立性上進行比較? （本題分） 操作系統(tǒng)期末試卷 第 1 頁（共頁）、在選擇調(diào)度方式和算法時應(yīng)遵循怎樣準(zhǔn)則，請從用戶和系統(tǒng)兩方面的角度分析? （本題分） 、將編輯好的程序裝入內(nèi)存共有幾種不同的方式?它們分別適用于何種場合? （本題

2、分） 、有哪幾種 i/o 控制方式？（本題分） 、什么是文件的邏輯結(jié)構(gòu)？什么是文件的物理結(jié)構(gòu)？根據(jù)用戶和系統(tǒng)管理上的需要可將文件分為哪幾類？（分） 操作系統(tǒng)期末試卷 第 2 頁（共頁）二、程序改錯題（本大題 10 分） 請就以下利用、操作解決同步問題的偽代碼程序的錯誤進行修改，并給出程序中所用到的各種信號量的初始值。 問題定義：桌上有一個空盤子，允許存放一只水果，父親可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果，規(guī)定在盤空時一次只能放一只水果供吃者取用，請用、原語實現(xiàn)父親， 、兒子和女兒三個并發(fā)進程的同步。 解決方法：假設(shè)本程序中用到三個信號量，分別為、o、a

3、：表示盤子是否為空，其初值應(yīng)為多少？即 o：表示盤中是否有桔子，其初值為多少？ 即 o a：表示盤中是否有蘋果，其初值為多少？ 即 a 待修改的程序如下： (請用下劃線標(biāo)識出有錯誤的語句， 并將修正后的正確語句寫在出錯語句所在行的右邊空白處請用下劃線標(biāo)識出有錯誤的語句， 并將修正后的正確語句寫在出錯語句所在行的右邊空白處) main() cobegin father(); /*父親進程*/ son(); /*兒子進程*/ daughter(); /*女兒進程*/ coend father() while(true) v(s); 將水果放入盤中； if(放入的是桔子) p(a) else p(o

4、) son() while(true) v(); 從盤中取出桔子; 操作系統(tǒng)期末試卷 第 3 頁（共頁） p(a) 吃桔子 daughter() while(true) p(); 從盤中取出蘋果; v(o) 吃蘋果 三、填表題（本大題共 2 小題，共分） 1、請?zhí)顚懲晗旅骊P(guān)于處理機調(diào)度算法的表格，不要求寫出運算過程，但要填寫完表格中未畫線的所有空格。計算只要求按四舍五入法精確到小數(shù)點后面三位。（本題 11 分） 進程 a b c d e 進程 a b c d e 到達時間 到達時間 0 3 5 9 11 服務(wù)時間 服務(wù)時間 5 8 6 4 3 平均值平均值 完成時間 完成時間 周轉(zhuǎn)時間 周轉(zhuǎn)時

5、間 sjf 帶權(quán)周轉(zhuǎn)時間 sjf 帶權(quán)周轉(zhuǎn)時間 完成時間 完成時間 周轉(zhuǎn)時間 周轉(zhuǎn)時間 rr q=5 帶權(quán)周轉(zhuǎn)時間 rr q=5 帶權(quán)周轉(zhuǎn)時間 、在一個請求分頁系統(tǒng)中，假定系統(tǒng)分配給一個進程的物理塊數(shù)為 3，并且此進程的頁面號引用串為：2，3，2，1，5，2，4，5，3，2，5，2, 4, 1。利用 lru 算法，將每次加入內(nèi)存的頁號及缺頁標(biāo)識填入表格，并計算 lru 算法的缺頁率是多少（精確到小數(shù)點后兩位）？ （本題 15 分）（提示：前三個不同頁號加入內(nèi)存時不算缺頁提示：前三個不同頁號加入內(nèi)存時不算缺頁） 操作系統(tǒng)期末試卷 第 4 頁（共頁）lru 算法 引用串 引用串 2 2 5 2 2

6、 5 缺頁標(biāo)識 因此 lru 算法的缺頁率為： 因此 lru 算法的缺頁率為： 四、計算題（本題分） 某虛擬存儲器的用戶編程空間共 32 個頁面，每頁為 1kb，內(nèi)存為 16kb。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號和物理塊號的對照表如下： 頁號 物理塊號 0 7 1 13 2 5 3 9 則邏輯地址 0d35(h)所對應(yīng)的物理地址是什么？(要求寫出計算步驟)(要求寫出計算步驟) 操作系統(tǒng)期末試卷 第 5 頁（共頁）五、綜合題（本題分） 在銀行家算法中，若出現(xiàn)下述資源分配情況： process allocation need available 0p 0,0,3,2 0,0,1,2 1

7、,6,2,3 1p 1,0,0,0 1,7,5,0 2p 1,3,5,4 2,3,5,6 3p 0,3,3,2 0,6,5,2 4p 0,0,1,4 0,6,5,6 、請簡要描述銀行家算法中的安全性算法執(zhí)行過程。 、 請問該狀態(tài)是否安全？ 、 若進程提出請求 request(1,2,2,2)后，系統(tǒng)能否將資源分配給它？請說明原因。 2p 操作系統(tǒng)期末試卷 第 6 頁（共頁）操作系統(tǒng)試卷（期末） （a 卷）答案 操作系統(tǒng)試卷（期末） （a 卷）答案 一、簡答題（本大題共小題，共 40 分） 、現(xiàn)代 os 的主要目標(biāo)是什么? （本題分） 答：方便性（分） ，有效性（分） ，可擴充性（分）和開放性（

8、分） 、試從交互性，及時性和可靠性方面，比較分時系統(tǒng)與實時系統(tǒng)的區(qū)別 （本題分） 答：）分時系統(tǒng)是一種通用系統(tǒng)，主要用于運行終端用戶程序，因而它具有較強的交互能力；而實時系統(tǒng)雖然也有交互能力，但其交互能力不及前者。 （分） ）實時信息系統(tǒng)對實用性的要求與分時系統(tǒng)類似，都是以人所能接收的等待時間來確定；而實時控制系統(tǒng)的及時性則是以控制對象所要求的開始截止時間和完成截止時間來確定的。 （分） ） 實時系統(tǒng)對系統(tǒng)的可靠性要求要比分時系統(tǒng)對系統(tǒng)的可靠性要求高。 （分） 、進程和程序有什么區(qū)別，請從動態(tài)性，并發(fā)性和獨立性上進行比較? （本題分） 答：動態(tài)性是進程最基本的特性，可表現(xiàn)為由創(chuàng)建而產(chǎn)生，由調(diào)度

9、而執(zhí)行，因得不到資源而暫停執(zhí)行，以及由撤銷而消亡，因而進程由一定的生命期；而程序只是一組有序指令的集合，是靜態(tài)實體。 （分） 并發(fā)性是進程的重要特征，同時也是 os 的重要特征.引入進程的目的正是為了使其程序能和其它進程的程序并發(fā)執(zhí)行，而程序是不能并發(fā)執(zhí)行的。 （分） 獨立性是指進程實體是一個能獨立運行的基本單位，同時也是系統(tǒng)中獨立獲得資源和獨立調(diào)度的基本 （分） 、在選擇調(diào)度方式和算法時應(yīng)遵循怎樣準(zhǔn)則，請從用戶和系統(tǒng)兩方面的角度分析? （本題分） 答：面向用戶的準(zhǔn)則有周轉(zhuǎn)時間短（分），響應(yīng)時間快（分），截止時間的保證（分），以及優(yōu)先權(quán)準(zhǔn)則（分）。 b. 面向系統(tǒng)的準(zhǔn)則有系統(tǒng)吞吐量高（分），處

10、理機利用率好（分），各類資源的平衡利用（分）。 、將編輯好的程序裝入內(nèi)存共有幾種不同的方式?它們分別適用于何種場合? （本題分） 答：首先由編譯程序?qū)⒂脩粼创a編譯成若干目標(biāo)模塊，再由鏈接程序?qū)⒕幾g后形成的目標(biāo)模塊和所需的庫函數(shù)鏈接在一起， 組成一個裝入模塊， 再由裝入程序?qū)⒀b入模塊裝入內(nèi)存 （分） ； b. 裝入模塊的方式有: 絕對裝入方式，可重定位方式和動態(tài)運行時裝入方式；（分） c. 絕對裝入方式適用于單道程序環(huán)境下；（分） d. 可重定位方式適用于多道程序環(huán)境下；（分） e. 動態(tài)運行時裝入方式也適用于多道程序環(huán)境下。（分） 、有哪幾種 i/o 控制方式？（本題分） 答：程序 i/o

11、控制方式（分）；中斷驅(qū)動 i/o 控制方式（分）；直接存儲器訪問 dma 控制方式（分）及 i/o 通道控制方式（分）。 操作系統(tǒng)期末試卷 第 7 頁（共頁） 、什么是文件的邏輯結(jié)構(gòu)？什么是文件的物理結(jié)構(gòu)？根據(jù)用戶和系統(tǒng)管理上的需要可將文件分為哪幾類？（分） 答：文件的邏輯結(jié)構(gòu)是指從用戶的觀點出發(fā)所觀察到的文件組織形式，也就是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨立于物理特性（分）；而文件的物理結(jié)構(gòu)則是指文件在外存上的存儲組織形式，與存儲介質(zhì)的存儲性能有關(guān)（分）。根據(jù)用戶和系統(tǒng)管理上的需要可將文件分為順序文件（分），索引文件（分），索引順序文件（分） 二、程序改錯題（本大題 10 分） 請就以下

12、利用、操作解決同步問題的偽代碼程序的錯誤進行修改，并給出程序中所用到的各種信號量的初始值。 ：表示盤子是否為空，其初值應(yīng)為多少？即 1 （1 分） o：表示盤中是否有桔子，其初值為多少？ 即 o 0 （1 分） a：表示盤中是否有蘋果，其初值為多少？ 即 a 0 （1 分） 存在錯誤的程序及修改之處 father() while(true) v(s); 修改為：p(s); （1 分） 將水果放入盤中； if(放入的是桔子) p(a) 修改為：v(o) （1 分） else p(o) 修改為：v(a) （1 分） son() while(true) v(); 修改為：p(o) （1 分） 從盤中

13、取出桔子; p(a) 修改為：v(s) （1 分） 吃桔子 daughter() 操作系統(tǒng)期末試卷 第 8 頁（共頁） while(true) p(); 修改為：p(a) （1 分） 從盤中取出蘋果; v(o) 修改為：v(s) （1 分） 吃蘋果 三、填表題（本大題共 2 小題，共分） 1、請?zhí)顚懲晗旅骊P(guān)于處理機調(diào)度算法的表格，不要求寫出運算過程，但要填寫完表格中未畫線的所有空格。計算只要求按四舍五入法精確到小數(shù)點后面三位。（每填對空分，共分） 進程 a b c d e 進程 a b c d e 到達時間 到達時間 0 3 5 9 11 服務(wù)時間 服務(wù)時間 5 8 6 4 3 平均值平均值

14、完成時間 完成時間 5 26 11 18 14 周轉(zhuǎn)時間 周轉(zhuǎn)時間 5 23 6 9 3 9.2 sjf 帶權(quán)周轉(zhuǎn)時間 sjf 帶權(quán)周轉(zhuǎn)時間 1 2.875 1 2.25 1 1.625 完成時間 完成時間 5 22 26 19 25 周轉(zhuǎn)時間 周轉(zhuǎn)時間 5 19 21 10 14 13.8 rr q=5 帶權(quán)周轉(zhuǎn)時間 rr q=5 帶權(quán)周轉(zhuǎn)時間 1 2.375 3.5 2.5 4.667 2.808 、在一個請求分頁系統(tǒng)中，假定系統(tǒng)分配給一個進程的物理塊數(shù)為 3，并且此進程的頁面號引用串為：2，3，2，1，5，2，4，5，3，2，5，2, 4, 1。利用 lru 算法，將每次加入內(nèi)存的頁號及

15、缺頁標(biāo)識填入表格，并計算 lru 算法的缺頁率是多少？（每寫對個有效填空給分，共 1分） lru 算法 lru 算法 引用串 引用串 2 2 5 4 1 2 2 5 4 1 2 2 2 2 2 2 2 3 3 3 3 4 4 3 3 3 5 5 5 5 5 5 5 5 5 1 1 1 1 4 4 4 2 2 2 2 2 缺頁標(biāo)識 因此 lru 算法的缺頁率為： / = 0.43 （分） 因此 lru 算法的缺頁率為： / = 0.43 （分） 四、計算題（本題分） 某虛擬存儲器的用戶編程空間共 32 個頁面，每頁為 1kb，內(nèi)存為 16kb。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號和物理塊

16、號的對照表如下： 操作系統(tǒng)期末試卷 第 9 頁（共頁）頁號 物理塊號 0 7 1 13 2 5 3 9 則邏輯地址 0d35(h)所對應(yīng)的物理地址是什么？(要求寫出計算步驟(要求寫出計算步驟) 解：2535（h） （要求寫出計算步驟）（分）（分） 分析頁式存儲管理的邏輯地址分為兩部分：頁號和頁內(nèi)地址。 由已知條件 “用戶編程空間共 32 個頁面” ， 可知頁號部分占 5 位 (1 分)(1 分)； 由 “每頁為 1kb” ，1k=210，可知內(nèi)頁地址占 10 位 (1 分)(1 分)。由“內(nèi)存為 16kb”，可知有 16 塊，塊號為 4 位 (1分)(1分)。 邏輯地址 0d35（h）所對應(yīng)的

17、二進制表示形式是：000 1101 0011 0101 ，根據(jù)上面的分析，下劃線部分為頁內(nèi)地址，編碼 “000 11” 為頁號，表示該邏輯地址對應(yīng)的頁號為 3 (1 分) (1 分)。查頁表， 得到物理塊號是 9 （十進制） ， 即物理塊地址為： 10 01 (1 分)(1 分) ， 拼接塊內(nèi)地址01 0011 0101，得 10 0101 0011 0101，即 2535（h）(1 分)(1 分)。 五、綜合題（本題分） 在銀行家算法中，若出現(xiàn)下述資源分配情況： process allocation need available 0p 0,0,3,2 0,0,1,2 1,6,2,3 1p 1

18、,0,0,0 1,7,5,0 2p 1,3,5,4 2,3,5,6 3p 0,3,3,2 0,6,5,2 4p 0,0,1,4 0,6,5,6 、請簡要描述銀行家算法中的安全性算法執(zhí)行過程。 、 請問該狀態(tài)是否安全？ 、 若進程提出請求 request(1,2,2,2)后，系統(tǒng)能否將資源分配給它？請說明原因。 2p答：、銀行家算法中的安全性算法執(zhí)行過程參考答案，可酌情給分： （分） （分） 設(shè)置兩個向量 工作向量ork，它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，在執(zhí)行安全算法開始時，work := available finish，它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開

19、始時先做finishi:=false; 當(dāng)有足夠資源分配給進程時，再令 finishi:=true 從進程集合中找到一個能滿足下述條件的進程： finishi=false; needi,jworkj；若能找到，執(zhí)行步驟，否則，執(zhí)行步驟 當(dāng)進程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： ip workj := workj +allocationi,j; finishi:=true; go to step 2; 操作系統(tǒng)期末試卷 第 10 頁（共頁） 如果所有進程的 finishi=true 都滿足，則表示系統(tǒng)處于安全狀態(tài); 否則，系統(tǒng)處于不安全狀態(tài) 、當(dāng)前狀態(tài)是安全狀態(tài)

20、，安全性檢測算法步驟如下： 先選擇，finish0=false；且 need0 = (0,0,1,2) work; 則 work = work + allocation0 (1,6,2,3) + (0,0,3,2) = (1,6,5,5); finish0=true （分）（分） 0p 再選擇，finish3=false；且 need3 = (0,6,5,2) work; 則 work = work + allocation3 (1,6,5,5) + (0,3,3,2) = (1,9,8,7); finish3=true （分）（分） 3p 接著選擇, finish4=false； 且need

21、4 = (0,6,5,6) work; 則work = work + allocation3 (1,9,8,7) + (0,0,1,4) = (1,9,9,11); finish4=true （分）（分） 4p 然后選擇，finish1=false；且 need1 = (1,7,5,0) work; 則 work = work + allocation3 (1,9,9,11) + (1,0,0,0) = (2,9,9,11); finish1=true （分）（分） 1p 最后選擇， finish2=false； 且 need2 = (2,3,5,6) work; 則 work = work

22、+ allocation3 (2,9,9,11) + (1,3,5,4) = (3,12,14,15); finish2=true （分）（分） 2p綜上所述，可以找到一個安全序列， ，使所有進程的 finishi=true都滿足（1i4） ，因此可斷言系統(tǒng)當(dāng)前處于安全狀態(tài)。 （分）（分） 0p3p4p1p2p 、運行銀行家算法，由于 request2=(1,2,2,2),need2=( 2,3,5,6), request2 need2，因此請求合法（分）（分） ； 、 進一步 request2=(1,2,2,2)， 而 available=(1,6,2,3), 故該請求可以滿足 （分）（分）

23、 ； 、 假設(shè)將資源分配給，則系統(tǒng)狀態(tài)變?yōu)椋ǚ郑ǚ郑?2pprocess allocation need available 0p 0,0,3,2 0,0,1,2 0,4,0,1 1p 1,0,0,0 1,7,5,0 2p 2,3,7,6 1,1,3,4 3p 0,3,3,2 0,6,5,2 4p 0,0,1,4 0,6,5,6 運行安全性檢測算法，work := available:=( 0,4,0,1), finishi:=false，此時所有的 needi和orki均不成立，結(jié)果 finishi均為 false，不存在安全進程序列，系統(tǒng)處于不安全狀態(tài)，系統(tǒng)將取消資源分配并恢復(fù)原來狀態(tài)，

24、進程等待。 （分）（分） 2p 操作系統(tǒng)期末試卷 第 11 頁（共頁）試題編號： 重慶郵電大學(xué)2013-2014學(xué)年一學(xué)期 操作系統(tǒng)試卷（期末） （a 卷） （閉卷） 題 號 一 二 三 四 五 六 七 八 總 分 得 分 評卷人 一、簡答題（本大題共小題，共 40 分） 、操作系統(tǒng)具有哪幾大特征?它的最基本特征是什么? （本題分） 、為實現(xiàn)多道程序應(yīng)解決哪些問題? （本題分） 、請說明進程有哪三種基本狀態(tài)，它們之間是如何轉(zhuǎn)換的。 （本題分） 、高級調(diào)度與低級調(diào)度的主要任務(wù)各是什么?為什么要引入中級調(diào)度? （本題分） 操作系統(tǒng)期末試卷 第 12 頁（共頁） 、程序的鏈接有幾種方式？為了實現(xiàn)程序

25、鏈接應(yīng)完成哪些工作？ （本題分） 、有哪幾種 i/o 控制方式？（本題分） 、按文件的物理結(jié)構(gòu)，可將文件分為哪幾類？每類文件有什么特點？（分） 二、編程問答題（本大題 10 分） 問題定義：設(shè)公共汽車上，司機和售票員的活動分別為：司機的活動是啟動車輛、正常開駛、到站停車；售票員的活動是關(guān)門、售票、開門。 1）試指出在汽車出站、行駛、到站過程中，述兩種活動有什么同步關(guān)系？ 2）試編寫一個偽代碼程序，利用 p-v 操作實現(xiàn)它們之間的同步關(guān)系，并給出程序中所用到的信號量的初值。 操作系統(tǒng)期末試卷 第 13 頁（共頁）三、填表題（本大題共 2 小題，共 26 分） 1、請?zhí)顚懲晗旅骊P(guān)于處理機調(diào)度算法的

26、表格，不要求寫出運算過程，但要填寫完表格中未畫線的所有空格。計算只要求按四舍五入法精確到小數(shù)點后面兩位。（本題 11 分） 進程 a b c d e 進程 a b c d e 到達時間 到達時間 0 3 4 6 9 服務(wù)時間 服務(wù)時間 4 7 3 5 2 平均值平均值 完成時間 完成時間 周轉(zhuǎn)時間 周轉(zhuǎn)時間 fcfs 帶權(quán)周轉(zhuǎn)時間 fcfs 帶權(quán)周轉(zhuǎn)時間 完成時間 完成時間 周轉(zhuǎn)時間 周轉(zhuǎn)時間 hrrn q=5 帶權(quán)周轉(zhuǎn)時間 hrrn q=5 帶權(quán)周轉(zhuǎn)時間 2、2、在一個請求分頁系統(tǒng)中，假定系統(tǒng)分配給一個進程的物理塊數(shù)為 3，并且此進程的頁面號引用串為：2，3，2，1，5，2，4，5，3，2，

27、5，4, 5，2。利用 opt 算法，將每次加入內(nèi)存的頁號及缺頁標(biāo)識填入表格，并計算 opt 算法的缺頁率是多少（精確到小數(shù)點后兩位）？（本題 15分） （提示：前三個不同頁號加入內(nèi)存時不算缺頁提示：前三個不同頁號加入內(nèi)存時不算缺頁） opt 算法 引用串 引用串 2 2 5 4 5 2 2 2 5 4 5 2 缺頁標(biāo)識 因此 opt 算法的缺頁率為：因此 opt 算法的缺頁率為： 操作系統(tǒng)期末試卷 第 14 頁（共頁）四、計算題（本題分） 某虛擬存儲器的用戶編程空間共 32 個頁面，每頁為 1kb，內(nèi)存為 16kb。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號和物理塊號的對照表如下： 頁號

28、物理塊號 0 5 1 10 2 4 3 7 則邏輯地址 065c(h)所對應(yīng)的物理地址是什么？(要求寫出計算步驟(要求寫出計算步驟) 五、綜合題（本題分） 在銀行家算法中，若出現(xiàn)下述資源分配情況： process allocation need available 0p 0,0,3,2 0,0,1,2 1,6,2,3 1p 1,0,0,0 1,7,5,0 2p 1,3,5,4 2,3,5,6 3p 0,3,3,2 0,6,5,2 4p 0,0,1,4 0,6,5,6 、請簡要描述銀行家算法中的安全性算法執(zhí)行過程。 、 請問該狀態(tài)是否安全？ 、 若進程提出請求 request(1,2,2,2)后

29、，系統(tǒng)能否將資源分配給它？請說明原因。 2p 操作系統(tǒng)期末試卷 第 15 頁（共頁）操作系統(tǒng)試卷（期末） （a 卷）答案 一、簡答題（本大題共小題，共分） 、操作系統(tǒng)具有哪幾大特征?它的最基本特征是什么? （本題分） 答：并發(fā)(concurrence)分 ； 共享(sharing)分 ； 虛擬(virtual)分 ； 異步性(asynchronism)分 ； 其中最基本特征是并發(fā)和共享分 、為實現(xiàn)多道程序應(yīng)解決哪些問題? （本題分） 答： ） 處理機管理問題； （分） ） 內(nèi)存管理問題； （分） ） i/o 設(shè)備管理問題； （分） ）文件管理問題； （分） ）作業(yè)管理問題. （分） 、請說明進

30、程有哪三種基本狀態(tài)，它們之間是如何轉(zhuǎn)換的。 （本題分） 答：處于就緒狀態(tài)的進程，當(dāng)進程調(diào)度程序為之分配了處理機后，該進程便由就緒狀態(tài)變?yōu)閳?zhí)行狀態(tài)。 （分） 當(dāng)前進程因發(fā)生某事件而無法執(zhí)行，如訪問已被占用的臨界資源，就會使進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。 （分） 當(dāng)前進程因時間片用完而被暫停執(zhí)行，該進程便由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。 （分） 、高級調(diào)度與低級調(diào)度的主要任務(wù)各是什么?為什么要引入中級調(diào)度? （本題分） 答：）作業(yè)調(diào)度又稱宏觀調(diào)度或高級調(diào)度，其主要任務(wù)是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進行選擇，給選中的作業(yè)分配內(nèi)存，輸入輸出設(shè)備等必要的資源，并建立相應(yīng)的進程，以使該作業(yè)的進程獲得競

31、爭處理機的權(quán)利。（分） ）進程調(diào)度又稱微觀調(diào)度或低級調(diào)度，其主要任務(wù)是按照某種策略和方法選取一個處于就緒狀態(tài)的進程，將處理機分配給它。（分） )為了提高內(nèi)存利用率和系統(tǒng)吞吐量，引入了中級調(diào)度. （分） 、程序的鏈接有幾種方式？為了實現(xiàn)程序鏈接應(yīng)完成哪些工作？ （本題分） 答：程序的鏈接有三種方式，它們分別是）靜態(tài)鏈接：是指事先進行鏈接形成一個完整的裝入模塊，以后不再拆開的鏈接方式；（分）； ）裝入時動態(tài)鏈接是指目標(biāo)模塊在裝入內(nèi)存時，邊裝入邊鏈接的鏈接方式；（分）； ）運行時的動態(tài)鏈接是將某些目標(biāo)模塊的鏈接推遲到執(zhí)行時才進行（分）； 在進行程序鏈接時，應(yīng)完成兩個工作，一是對相對地址進行修改（分）

32、；二是變換外部調(diào)用符號。（分） 、有哪幾種 i/o 控制方式？（本題分） 答：程序 i/o 控制方式（分） ；中斷驅(qū)動 i/o 控制方式（分） ；直接存儲器訪問 dma 控制方式（分）及 i/o 通道控制方式（分） 。 、按文件的物理結(jié)構(gòu)，可將文件分為哪幾類？每類文件有什么特點？（分） 答：按文件的物理結(jié)構(gòu)，可將文件分為三類：（1）順序文件，指把邏輯文件中的記錄順序地存儲到連續(xù)的物理盤塊中 （分）；（2）鏈接文件，指文件中的各個記錄可以存放在不相鄰的各個物理塊中，但通過物理塊中的鏈接指針，將它們鏈接成一個鏈表 （分）；（3）索引文 操作系統(tǒng)期末試卷 第 16 頁（共頁）件，指文件中的各個記錄可

33、以存放在不相鄰的各個物理塊中，但通過為每個文件建立一張索引表來實現(xiàn)記錄和物理塊之間的映射關(guān)系 （分）。 二、編程問答題（本大題 10 分） 問題定義：設(shè)公共汽車上，司機和售票員的活動分別為：司機的活動是啟動車輛、正常開駛、到站停車；售票員的活動是關(guān)門、售票、開門。 1）試指出在汽車出站、行駛、到站過程中，述兩種活動有什么同步關(guān)系？ 2）試編寫一個偽代碼程序，利用 p-v 操作實現(xiàn)它們之間的同步關(guān)系，并給出程序中所用到的信號量的初值。 答：司機啟動車輛與售票員關(guān)車門為同步關(guān)系； （1 分） 司機到站停車與售票員開車門為同步關(guān)系。 （1 分） 定義兩個信號量：s1：表示門是否關(guān)了,初始值為 0；

34、（1 分） s2：表示汽車是否到站，初始值為 0 （1 分） 參考程序，只要表達出正確的 p、v 操作意思，都可酌情給分。程序部分共 6 分 main( ) cobegin process driver( )； process conductor( )； coend process driver( ) p(s1); 啟動； 行駛； 到站停車； v(s2); process conductor( ) 關(guān)車門； v（s1）; 售票； p（s2） ； 開車門； 三、填表題（本大題共 2 小題，共 26 分） 1、請?zhí)顚懲晗旅骊P(guān)于處理機調(diào)度算法的表格，不要求寫出運算過程，但要填寫完表格中未畫線的所有空

35、格。計算只要求按四舍五入法精確到小數(shù)點后面兩位。（每填對空分，共分） 進程 a b c d e 進程 a b c d e 到達時間 到達時間 0 3 4 6 9 服務(wù)時間 服務(wù)時間 4 7 3 5 2 平均值平均值 操作系統(tǒng)期末試卷 第 17 頁（共頁）完成時間 完成時間 4 11 14 19 21 周轉(zhuǎn)時間 周轉(zhuǎn)時間 4 8 10 13 12 9.4 fcfs 帶權(quán)周轉(zhuǎn)時間 fcfs 帶權(quán)周轉(zhuǎn)時間 1 1.14 3.33 2.6 6 2.81 完成時間 完成時間 4 11 14 21 16 周轉(zhuǎn)時間 周轉(zhuǎn)時間 4 8 10 15 7 8.8 hrrn q=5 帶權(quán)周轉(zhuǎn)時間 hrrn q=5

36、帶權(quán)周轉(zhuǎn)時間 1 1.14 3.33 3 3.5 2.39 、在一個請求分頁系統(tǒng)中，假定系統(tǒng)分配給一個進程的物理塊數(shù)為 3，并且此進程的頁面號引用串為：2，3，2，1，5，2，4，5，3，2，5，4,。利用 opt 算法，將每次加入內(nèi)存的頁號及缺頁標(biāo)識填入表格，并計算 opt 算法的缺頁率是多少？（每寫對個有效填空給分，共 1分） opt 算法 opt 算法 引用串 引用串 2 2 5 4 5 2 2 2 5 4 5 2 2 2 2 2 2 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 2 1 5 5 5 5 5 5 5 5 5 5 缺頁標(biāo)識 因此 opt 算

37、法的缺頁率為： 3/ = 0.21 （2 分） 因此 opt 算法的缺頁率為： 3/ = 0.21 （2 分） 四、計算題（本題 6 分） 某虛擬存儲器的用戶編程空間共 32 個頁面，每頁為 1kb，內(nèi)存為 16kb。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號和物理塊號的對照表如下： 頁號 物理塊號 0 5 1 10 2 4 3 7 則邏輯地址 065c(h)所對應(yīng)的物理地址是什么？(要求寫出計算步驟(要求寫出計算步驟) 解：2a5c（h） （要求寫出計算步驟）(6 分) 分析頁式存儲管理的邏輯地址分為兩部分：頁號和頁內(nèi)地址。 由已知條件 “用戶編程空間共 32 個頁面” ，可知頁號部分占

38、5 位(1 分)(1 分)； 由 “每頁為 1kb”，1k=210，可知內(nèi)頁地址占 10 位(1 分)(1 分)。由“內(nèi)存為 16kb”，可知有 16塊，塊號為 4 位(1 分)(1 分)。 邏輯地址 065c（h）所對應(yīng)的二進制表示形式是：000 0110 0101 1100 ，根據(jù)上面的分析，下劃線部分為頁內(nèi)地址，編碼 “000 01” 為頁號，表示該邏輯地址對應(yīng)的頁號為 1 (1 分)(1 分)。查頁表，得到物理塊號是 10（十進制） ，即物理塊地址為：10 10 (1 分) (1 分) ，拼接塊內(nèi)地址10 0101 1100，得 10 1010 0101 1100，即 2a5c（h）(

39、1 分)(1 分)。 操作系統(tǒng)期末試卷 第 18 頁（共頁）五、綜合題（本題分） 在銀行家算法中，若出現(xiàn)下述資源分配情況： process allocation need available 0p 0,0,3,2 0,0,1,2 1,6,2,3 1p 1,0,0,0 1,7,5,0 2p 1,3,5,4 2,3,5,6 3p 0,3,3,2 0,6,5,2 4p 0,0,1,4 0,6,5,6 、請簡要描述銀行家算法中的安全性算法執(zhí)行過程。 、 請問該狀態(tài)是否安全？ 、 若進程提出請求 request(1,2,2,2)后，系統(tǒng)能否將資源分配給它？請說明原因。 2p答：、銀行家算法中的安全性算法

40、執(zhí)行過程參考答案，可酌情給分： （分） （分） 設(shè)置兩個向量 工作向量ork，它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，在執(zhí)行安全算法開始時，work := available finish，它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做finishi:=false; 當(dāng)有足夠資源分配給進程時，再令 finishi:=true 從進程集合中找到一個能滿足下述條件的進程： finishi=false; needi,jworkj；若能找到，執(zhí)行步驟，否則，執(zhí)行步驟 當(dāng)進程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： ip workj := workj +allocationi,j; finishi:=t