計算機學科專業(yè)基礎綜合計算機操作系統(tǒng)-4

1、計算機學科專業(yè)基礎綜合計算機操作系統(tǒng) -4一、綜合應用題 ( 總題數： 41，分數： 100.00)1. 試比較單道與多道批處理系統(tǒng)的特點及優(yōu)缺點。正確答案： (1) 單道批處理系統(tǒng)是最早出現的一種操作系統(tǒng)，它具有自動性、順序性和單道性的特點。多 道批處理系統(tǒng)則具有調度性、 無序性和多道性的特點。 (2) 單道批處理系統(tǒng)是在解決人機矛盾及 CPU和 I/O 設備之間速度不匹配的矛盾中形成的，旨在提高系統(tǒng)資源利用率和系統(tǒng)吞吐量，但是仍然不能很好地利用 系統(tǒng)資源。多道批處理系統(tǒng)是對單道批處理系統(tǒng)的改進，其主要優(yōu)點是資源利用率高，系統(tǒng)吞吐量大；缺 點是平均周轉時間長，無交互能力。 )2. 試比較脫機

2、 I/O 和聯(lián)機 I/O 。正確答案： (1) 脫機輸入 /輸出方式是為了解決人機矛盾及 CPU和 I/O 設備之間速度不匹配而提出的。 它減 少了 CPU的空閑等待時間，提高了 I/O 速度，具體內容是將用戶程序和數據在一臺外圍機的控制下，預先 從低速輸入設備輸入到磁帶上，當 CPU需要這些程序和數據時再直接從磁帶機高速輸入到內存，從而大大 加快了程序的輸入過程， 減少了 CPU等待輸入的時間， 這就是脫機輸入技術； 當程序運行完畢或告一段落， CPU需要輸出時，無須直接把計算結果送至低速輸出設備，而是把結果高速地輸出到磁帶上，然后在外圍 機的控制下，把磁帶上的計算結果由相應的輸出設備輸出，

3、這就是脫機輸出技術。 (2) 若這種輸入 / 輸出操 作在主機控制下進行則稱為聯(lián)機輸入 / 輸出方式。 )3. 試在交互性、及時性和可靠性方面，將分時系統(tǒng)與實時系統(tǒng)進行比較。正確答案： (1) 分時系統(tǒng)是一種通用系統(tǒng)，主要用于運行終端用戶程序，因而它具有較強的交互能力；而 實時系統(tǒng)雖然也有交互能力， 但其交互能力不及前者。 (2) 實時信息系統(tǒng)對實時性的要求與分時系統(tǒng)類似， 都是以人所能接受的等待時間來確定；而實時控制系統(tǒng)的及時性則是以控制對象所要求的開始截止時間和 完成截止時間來確定的。 (3) 實時系統(tǒng)對系統(tǒng)的可靠性要求要比分時系統(tǒng)對系統(tǒng)的可靠性要求高。 )4. 說明實時任務的類型和實時系

4、統(tǒng)的類型。正確答案： (1) 實時任務的類型按任務執(zhí)行時是否呈現周期性來劃分，分為周期性實時任務和非周期性實 時任務；根據對截止時間的要求來劃分，分為硬實時任務和軟實時任務。 (2) 通常把要求進行實時控制的 系統(tǒng)統(tǒng)稱為實時控制系統(tǒng)，把要求對信息進行實時處理的系統(tǒng)稱為實時信息處理系統(tǒng)。 )5. 處理機管理具有哪些功能 ?它們的主要任務是什么 ?正確答案： (1) 進程控制、進程同步、進程通信和調度。 (2) 進程控制的主要任務是為作業(yè)創(chuàng)建進程、撤 銷已結束的進程以及控制進程在運行過程中的狀態(tài)轉換。 進程同步的主要任務是對諸進程的運行進行調節(jié) 進程通信的任務是實現在相互合作進程之間的信息交換。

5、調度分為作業(yè)調度和進程調度，作業(yè)調度的基本 任務是從預備隊列中按照一定的算法，選擇若干個作業(yè)，為它們分配必要的資源；而進程調度的任務是從 進程的就緒隊列中按照一定的算法選出一新進程，把處理機分配給它，并為它設置運行現場，使進程投入 運行。 )6. 操作系統(tǒng)有哪兩種服務方式 ?它們是如何實現服務的 ?正確答案： (1) 系統(tǒng)調用：系統(tǒng)調用本身是一個由若干條指令構成的過程。 (2) 系統(tǒng)程序：現代計算機系 統(tǒng)往往都有一個系統(tǒng)程序包，它包含了系統(tǒng)提供的大量程序，用于解決帶有共性的問題，并為程序的開發(fā) 和執(zhí)行提供了一個方便的環(huán)境。 )7. 操作系統(tǒng)必須具備的功能有哪些 ?正確答案： (1) 用戶接口：

6、操作系統(tǒng)與用戶的接口也簡稱為用戶接口。 (2) 處理機管理：處理機管理的主 要任務是對處理機的分配和運行實施有效管理。 (3) 存儲管理：存儲管理的主要任務包括為多道程序的并 發(fā)運行提供良好環(huán)境，為用戶使用存儲器提供方便，提高存儲器的利用率，為盡量多的用戶提供足夠大的 存儲空間。 (4) 設備管理： 設備管理的主要任務有： 為用戶分配 I/O 設備， 完成用戶程序請求的 I/O 操作， 提高 CPU和輸入/輸出設備的利用率，改善人機界面。 (5) 文件管理：現代計算機系統(tǒng)的外部存儲器中，都 以文件形式存放著大量的信息。操作系統(tǒng)必須配置相應的文件管理機構來管理這些信息。 )8. 為什么說操作系統(tǒng)

7、是由中斷驅動的 ?正確答案： (1) 所有并發(fā)程序都是由中斷 (特別是時鐘中斷 ) 驅動的，故操作系統(tǒng)中屬于這一類的程序也是 由中斷驅動的。 (2) 第二類是直接面對用戶態(tài)“被動”地為用戶服務的程序。系統(tǒng)初啟后，這類程序一般 是不運行的，僅當用戶態(tài)程序執(zhí)行了相應的系統(tǒng)調用時它才被調用、執(zhí)行。而正如上面所說，系統(tǒng)調用指 令的執(zhí)行是經中斷 (自陷)機構處理的。 因此，在這種意義上， 操作系統(tǒng)中的這一類程序也是由中斷驅動的。 (3) 第三類是那些既不主動運行， 也不直接面對用戶態(tài)的程序。 它們是隱藏在操作系統(tǒng)內部，由前兩類程序 所調用的程序。既然前兩類程序都是由中斷驅動的，則此類程序當然也應該是由中

8、斷驅動的。 )9. 簡述判斷死鎖的必要條件。正確答案： (1) 互斥條件。 進程競爭的資源必須互斥使用。 (2) 請求與保持條件。 當前已擁有資源的進程， 仍能申請新的資源， 而當該進程因為新的資源被其他進程占據而被阻塞時， 它仍保持自己的資源不釋放。 (3) 不可剝奪條件。進程申請的資源只能在使用完畢時自行釋放。 (4) 循環(huán)等待條件。存在一個至少包含兩個 進程的循環(huán)等待鏈，鏈中的每個進程都在等待下一個進程所占有的資源。 )10. 假定系統(tǒng)有三個并發(fā)進程 read 、move和 print 共享緩沖器 B1 和 B2。進程 read 負責從輸入設備上讀信 息，每讀出一條記錄后把它存放到緩沖器

9、 B1 中。進程 move從緩沖器 B1 中取出一條記錄， 加工后存入緩沖 器 B2。進程 print 將 B2中的記錄取出打印輸出。緩沖器 B1和 B2 每次只能存放一條記錄。要求三個進程 協(xié)調完成任務，使打印出來的與讀入的記錄的條數，次序完全一樣。請用 wait 和 signal 原語寫出它們的 并發(fā)程序。正確答案： (begin SR,SM1,SM2,SP:semaphore; B1,B2:record; SR:=1;SMl:=0;SM2:=1;SP:=0; cobeginprocess read X:record; begin R: ( 接收來自輸入設備上一條記錄 ) X:=接收的一條

10、記錄 ; wait(SR); B1:=X; signal(SMl); goto R; end; Process move Y:record; begin M:wait(SMl); Y:=B1; Signal(SR)加工 Ywait(SM2); B2:=Y; signal(SP); goto M; end; Process print Z:record; begin P:wait(SP); Z:=B2;signal(SM2) 打印 Z goto P; end; coend; end;)11. 舉例說明，P、V操作為什么要求設計成原語 (即對同一信號量上的操作必須互斥 ) 。P(S) 操作：S.v

11、alue-; if(S.value <0) Add this process to S.L; Block(); V(s) 操作： S.value+; if(S.value <=0) Remove a process P from S.L; Wakeup(P); 正確答案： ( 例如，用 P、V操作來實現進程對臨界資源互斥使用。此時，只需定義一個信號量S，其初值1,NuLL ，并在臨界區(qū)前執(zhí)行 P(S) 操作，而在臨界區(qū)后執(zhí)行 V(S) 操作。此時 P、 V操作不設計成原語，那 么在執(zhí)行 P、V 操作時進程可以被中斷。 由于在初始狀態(tài)下臨界資源空閑， 故應允許第一個申請臨界資源的 進

12、程進入臨界區(qū)使用臨界資源， 但如果該進程在執(zhí)行到 P操作的語句 S.value- 后( 此時 S.value 的值為 0) 便被另一個進程中斷，而那個進程也企圖通過執(zhí)行 P(S) 操作進入臨界區(qū)，則第二個進程也必須執(zhí)行語句 S.value- ，從而將 S.value 的值為 -1 ，并由于 S.value <0 而被阻塞，而第一個進程再次獲得CPU后也同樣由于 S.value <0 而被阻塞，這就造成了臨界資源雖然空閑但進程卻申請不到臨界資源的情況， 也就是說， 此時的 P、 V操作已無法滿足同步機制的要求。同樣，一個執(zhí)行P(S) 操作的進程被中斷后另一進程去執(zhí)行V(S)操作，一個

13、執(zhí)行 V(S)操作的進程被中斷后而另一個進程去執(zhí)行 P(S)或 V(S)操作，都將發(fā)生混亂而難 以實現進程同步。因此， P、V 操作必須設計成原語的方式。 )12. 并發(fā)使得處理機的利用率得到提高， 其主要原因是處理機與 I/O 可以同時為多個進程服務， 也即處理機 與 I/O 設備真正地并行。但是處理機的利用率提高并不是簡單地將兩個進程的處理機利用率相加，而是遵 循一定的規(guī)律。現在有一個計算機系統(tǒng)采用多道程序技術實現了并發(fā)，調度算法采用時間片輪轉，時間片 很小可以不計進程并發(fā)時的次序。忽略計算機系統(tǒng)的開銷。假設進程創(chuàng)建時間和完全占有 CPU運行的確切時間如下表所示。已知其 I/O 繁忙率為

14、80%，處理機的利用 率為 20%。進程 創(chuàng)建時間 CPU運行時間 /min系統(tǒng)中進程的數量1234I/O 繁忙率CPU利用率每個進程的 CPU利用率*請計算并填寫下列空格和圖表空格處。010:004110:103210:152310:202正確答案： ( 本題考查的是并發(fā)進程之間的計算。 計算機引入多道程序設計技術主要是為提高處理機的利用 率。在多道程序并發(fā)的情況下，處理機的利用率呈現出如下的規(guī)律：U=1-Pn其中， U為處理機利用率， P為 I/O 繁忙率， n為并發(fā)進程數。據此，對題目給定的數據進行計算，并將結 果填入表格中。當1 個進程運行時，處理機利用率為 20%，這個進程獨享該處理

15、機，所以 20%的利用率均被使用。在時刻 10:00 到 10:10 期間，進程 0 獨享處理機。這期間，進程 0 實際的處理機時間為 10 分鐘× 20%=2分鐘。 當2 個進程運行時， 根據公式計算得到處理機利用率為 36%，2 個進程共享處理機，所以每個進程的處理機 的利用率為 18%。在時刻 10:10 到 10:15 期間，進程 0 和 1 共享處理機。這期間，進程 0 和 1各自實際的 處理機時間為 5× 36%÷ 2=0.9 分鐘。當3 個進程運行時， 根據公式計算得到處理機利用率為 49%，3 個進程共享處理機，所以每個進程的處理機 的利用率為 1

16、6%。在時刻 10:15 到 10:20 期間，進程 0、1 和 2 共享處理機。這期間，進程 0、1 和 2 各自 實際的處理機時間為 5× 49%÷3=0.8 分鐘。當4 個進程運行時， 根據公式計算得到處理機利用率為 59%，4 個進程共享處理機，所以每個進程的處理機 的利用率為 15%。從時刻 10:20 開始， 4 個進程并發(fā)。那么，從圖中可以看到，進程0 已經運行了 3.7 分鐘，進程 1 運行了1.7 分鐘，進程 2 運行了 0.8 分鐘，進程 3 剛運行。根據題目給出的每個進程實際占有處理機的時間，可 以看出，進程 0 還剩余時間 0.3 分鐘，進程 1 還

17、剩余 1.3 分鐘，進程 2 還剩余 1.2 分鐘，進程 3 還剩余 2 分鐘，顯然，在并發(fā)并且平均使用處理機的情況下，進程結束的次序應該為0、 2、1、3。首先我們計算進程 0 還需要運行多長時間結束。經過剛才計算得知，進程0 還剩余 0.3 分鐘，那么，在進程4并發(fā)，處理機利用率為每進程 15%的情況下，尚需要時間為 0.3 ÷15%=2分鐘，由此得知，到 10:22 時， 進程 0 結束。進程 0退出后再計算剩余進程的剩余時間，進程1， 2，3分別為 1.0 、0.9、1.7 分鐘，上面已經分析，下一個結束的進程是進程 2，所以，我們計算 0.9 ÷16%=5.6分鐘

18、。注意，此時是 3 個進程并發(fā)了，處理機的 利用率為每進程 16%，此處切記不可疏忽。到 10:27.6 ，進程 2 結束。同理，進程 2 退出以后再計算剩余進程的剩余時間，進程1、 3分別為 0.1 、0.8 分鐘，上面已經分析，下一個結束的進程是進程 1，所以， 0.1 ÷18%=0.6分鐘。注意，此時是 2 個進程并發(fā)了，處理機的利用率為 每進程 18%。到 10:28.2 ，進程 1 結束。同樣計算，進程 1 退出以后，進程 3 的剩余時間為 0.7 分鐘，計算得出 0.7 ÷ 20%=3.5 分鐘，而此時處理機 的利用率為每進程 20%。到 10:31.7 ，進程

19、 3 結束。據此，填寫下列各個表格和空格。根據題意計算得到 U1=1-0.8=0.2=20%U2=1-0.8 2=0.36=36%U3=1-0.8 3=0.49=49%U4=1-0.8 4=0.59=59%因此，表格填寫如下：系統(tǒng)中進程的數量I/O 繁忙率CPU利用率1 2 3 4 80%6 4%5 1%4 1% 20%3 6%4 9%5 9%每個進程的 CPU利用率 20%1 8%1 6%1 5%甘特圖中空白括號填寫如下圖所示：*)13. 設有一緩沖池 P，P中含有 10 個可用緩沖區(qū)，一個輸入進程將外部數據讀入P，另有一個輸出進程將 P中數據取出并輸出，如下所示。若進程每次操作均以一個緩沖

20、區(qū)為單位，試用記錄型信號量寫出兩個進程 的同步算法，要求寫出信號量的設置。 輸入進程 輸出進程 L ：讀入數據 L ：從一滿緩沖區(qū)中 取出數據 將數據寫入一空緩沖區(qū)將 數據輸出 GOTO L GOTO L正確答案： ( 設置信號量 mutex,empty,full 初值： mutex=1,empty=10,full=0 (2) 設置 wait,signal 操作 如下： 輸入進程 輸出進程 L: 讀入數據 L:wait(full) wait(empty) wait(mutex) wait(mutex) 從一滿緩 沖區(qū)中取出數據 將數據寫入一空緩沖區(qū) signal(mutex) signal(m

21、utex) signal(empty) signal(full) 數 據輸出 )14. 一個 SPOOLing系統(tǒng)由輸入進程 I 、用戶進程 P、輸出進程 O、輸入緩沖區(qū)、輸出緩沖區(qū)組成。進程I 通過輸入緩沖區(qū)為進程 P 輸入數據，進程 P 的處理結果通過輸出緩沖區(qū)交給進程O輸出。進程間數據交換以等長度的數據塊為單位，這些數據塊均存儲在同一個磁盤上，因此，SPOOLing系統(tǒng)的數據塊通信原語保證始終滿足： i+o()max 。其中， max為磁盤容量 (以該數據塊為單位 )，i 為磁盤上輸入數據塊總數， o 為磁盤 上輸出數據總數。 該 SPOOLing系統(tǒng)運行時： (1) 只要有輸入數據，

22、進程 I 終究會將它放入輸入緩沖區(qū)； (2) 只要輸入緩沖區(qū)有數據塊，進程 P 終究會輸入、處理并產生結果數據寫到輸出緩沖區(qū)； (3) 只要輸出緩沖 區(qū)有數據塊，進程 O終究會輸出它。 請說明該 SPOOLing系統(tǒng)在什么情況下死鎖，并說明如何修正約束條 件(1) 避免死鎖，同時仍允許輸入數據塊和輸出數據塊存儲在同一個磁盤上。正確答案： (1)i+o max (2) 當 i=max，p 的輸出數據無處存放， i 的輸入數據占滿磁盤時，死鎖。 (3) 應 該增加約束： i+o max，使得輸出數據塊的長度 o> 0。)15. 什么是 AND信號量 ?請利用 AND信號量寫出生產者一消費者問

23、題的解法。正確答案： ( 此題主要考查進程與死鎖的相關轉換內容。 (1) 為解決并行所帶來的死鎖問題，在 wait 操作 中引入 AND條件，其基本思想是將進程在整個運行過程中所需要的所有臨界資源一次性地全部分配給進程， 用完后一次性釋放。 (2) 解決生產者一消費者問題可描述如下： var mutex,empty,full:semaphore:=1,n,0;buffer:array0.n-1 of item; in,out:integer:=0,0; begin parbegin producer:begin repeatproduce an item in nextp; wait(empt

24、y); wait(s1,s2,s3, ,sn); /s1 ，s2，s3， sn 為執(zhí)行生產者進程除 empty 外其余的條件 wait(mutex); buffer(in):=nextp; in:=(in+1)mod n; signal(mutex); signal(full); signal(s1,s2,s3, ,sn); until false; end consumer:begin repeat wait(full);wait(k1,k2,k3, ,kn); /k1,k2,k3,kn 為執(zhí)行生產者進程除 full 外其余的條件 wait(mutex);nextc:=buffer (out

25、); out:=(out+1) mod n;signal(mutex); signal(empty); signal(k1,k2,k3, ,kn);consume the item in nextc; until false; end parend end)16. 測量控制系統(tǒng)中的數據采集任務把所采集的數據送一個單緩沖區(qū)， 計算任務從該單緩沖區(qū)中取出數據進 行計算。試寫出利用信號量機制實現兩者共享單緩沖區(qū)的同步算法。正確答案： ( 此題主要考查進程間共享緩 ) 中區(qū)來實現同步的相關內容。 int mutex=1 int empty=n; intfull=0; int in=0; int out

26、=0; main() cobegin send(); obtain(); coend send() while(1) collect data in nextp wait (empty); wait (mutex); buffer (in)=nextp; in=(in+1)mod n; signal(mutex); signal (full); /send obtain() while(1) wait(full); wait(mutex); nextc:=buffer(out);out:=(out+1)mod n ； signal (mutex); signal (empty); culcul

27、ate the data innextc; /while /obtain)17. 試利用記錄型信號量寫出一個不會出現死鎖的哲學家進餐問題的解決算法。正確答案： (此題主要考查進程控制過程中的信號量技術的運用。設初始值為 1的信號量 cI 表示I 號筷 子被拿 (I=1 ，2，3，4， 2n) ，其中 n 為自然數。 send(I); begin if I rood 2 = 1 then P(cI);P(cI-1 rood 5); Eat; V(cI-1 mod 5); V(cI); else P(cI-1 rood 5); P(cI); Eat; V(eI); V(cI-1 rood 5);

28、end)18. 為什么進程在進入臨界區(qū)之前應先執(zhí)行“進入區(qū)”代碼，在退出臨界區(qū)后又執(zhí)行“退出區(qū)”代碼 ?正確答案： ( 為了實現多個進程對臨界資源的互斥訪問， 必須在臨界區(qū)前面增加一段用于檢查欲訪問的臨界 資源是否正被訪問的代碼， 如果未被訪問， 該進程便可進入臨界區(qū)對資源進行訪問， 并設置正被訪問標志； 如果正被訪問，則本進程不能進入臨界區(qū)，實現這一功能的代碼稱為“進入區(qū)”代碼：在退出臨界區(qū)后必 須執(zhí)行“退出區(qū)”代碼，用于恢復未被訪問標志。 )19. 我們?yōu)槟撑R界區(qū)設置一把鎖 W，當 W=1時表示關鎖， W=0時表示鎖已打開。 試寫出開鎖原語和關鎖原語， 并利用它們去實現互斥。正確答案： (

29、 開鎖原語： unlock(W): W=0; 關鎖原語： lock(w); if(W=1) do no_op; W=1; (2)利用開關鎖原語實現互斥： var W:semaphore:=0; begin parbegin process: begin repeat lock(W); critical section unlock(W); remainder section until false; end paxend)20. 試修改下面生產者 - 消費者問題解法中的錯誤。 producer: begin repeat producer an item innextp; wait(mutex

30、); wait(full); buffer(in):=nextp; signal(mutex); until false; end consumer:正確答案： (producer: begin 應為 wait(empty), 而且還應該在 移:in:=(in+1) mod n;*/ signal wait (mutex); wait (empty); /* nextc:=buffer(out); out:=out+1; /*begin repeat wait(mutex); wait(empty); nextc:=buffer(out); out:=out+1; signal(mutex);

31、 consumer item in nextc; until false; end/*repeat producer an item in nextp; wait(mutex); wait(full);wait(mutex) 的前面 */ buffer(in) :=nextp; /*緩沖池數組游標應前(mutex); /*signal (full);*/ until false; end consumer; begin repeat 應為 wait (full), 而且還應該在 wait(mutex) 的前面 */ 考慮循環(huán) , 應改為 :out:=(out+1) mod n;*/ signa

32、l (mutex);/*signal (empty);*/ consumer item in nextc; until false; end)21.3 個進程 P1、P2、P3互斥使用一個包含 N個(N>0) 單元的緩沖區(qū)， P1每次用 produce() 生成一個正整 數并用 put() 送入緩沖區(qū)某一空單元中； P2 每次用 getodd() 從該緩沖區(qū)中取出一個奇數并用 countodd() 統(tǒng)計奇數個數； P3 每次用 geteven() 從該緩沖區(qū)中取出一個偶數并用 counteven() 統(tǒng)計偶數個數。請用信 號量機制實現這 3 個進程的同步與互斥活動，并說明所定義的信號量的

33、含義。要求用偽代碼描述。正確答案： (1) 定義信號量 s1控制 P1與P2之間的同步， s2控制 P1與P3之間的同步， empty控制生產者 與消費者之間的同步， mutex 控制進程間互斥使用緩沖區(qū)。 (2) 程序如下： var s1=0,s2=0,empty=N,mutex=1;parbegin P1:begin X=produce(); /* 生成一個數 */ P(empty); /* 判斷緩沖區(qū)是否有空單元 */ P(mutex); /* 緩沖區(qū)是否被占用 */ Put(); If x% 2=0 V(s2); /*如果是偶數，向 P3發(fā)出信號 */ else V(s1); /*如果

34、是奇數，向 P2 發(fā)出信號 */ V (mutex); /*使用完緩沖區(qū)，釋放 */ end P2:begin P(s1); /*收到 P1 發(fā)來的信號，已產生一個奇數 */ P(mutex); /*緩沖區(qū)是否被占用 */ Getodd(); Countodd():=countodd()+1;V(mutex); /* 釋放緩沖區(qū) */ V(empty); /*向 P1發(fā)信號，多出一個空單元 */ end P3:begin P(s2) /*收到P1 發(fā)來的信號，已產生一個偶數 */ P(mutex); /* 緩沖區(qū)是否被占用 */ Geteven();Counteven():=counteven

35、()+1; V(mutex); /* 釋放緩沖區(qū) */ V(empty); /* 向 P1 發(fā)信號，多出一個空單元 */ end parend)22. 假設程序 PA和 PB單獨執(zhí)行時所需的時間分別用 TA和 TB表示，并且假設 TA=1h，TB=1.5h ，其中處理器工 作時間分別為 TA=18min，TB=27min，如果采用多道程序設計方法，讓PA和 PB 并行工作，假定處理器利用率達到 50%，系統(tǒng)開銷為 15min ，請問系統(tǒng)效率能提高多少 ?正確答案： (1) 在串行情況下，兩個程序運行時間共計2.5h ；在并行方式下，處理器利用率為 50%，說明處理器的工作時間占總運行時間的 5

36、0%。根據已知條件，“處理器工作時間分別為TA=18min， TB=27min” 即總運行時間為 (18+27) ÷50%(min) ，考慮到還有 15min系統(tǒng)開銷， 故并行與串行的效率比為并行處理所需 的時間÷串行處理所需要的時間總和 =(18+27) ÷50%+15÷ 2.5 ÷ 60=70%。(2) 即采用多道處理技術之后， 完成程序 PA和程序 PB所需的時間為串行處理方法的 70%。因此可以說效率提 高了 30%。 )23. 某多道程序設計系統(tǒng)配有一臺處理器和兩臺外設101、102，現有 3個優(yōu)先級由高到低的 J1、J2、J3 都已

37、裝入了主存，它們使用資源的先后順序和占用時間分別是：J1 ：102(30ms) ， CPU(10ms)；101(30ms) ，CPU(10ms)； J2 ：101(20ms) ，CPU(20ms)； 102(40ms) ； J3：CPU(30ms)，101(20ms) 。 處理器調度采用可 搶占的優(yōu)先數算法，忽略其他輔助操作時間，回答下列問題。 (1) 分別計算作業(yè) J1、J2和J3 從開始到完 成所用的時間。 (2)3 個作業(yè)全部完成時 CPU的利用率。 (3)3 個作業(yè)全部完成時外設 101 的利用率。正確答案： (為了清楚地描述作業(yè)執(zhí)行情況，我們對題目假設的情況分析如下：(1)J1 占用

38、 IO2 傳輸 30ms時， J1 傳輸完成，搶占 J2 的 CPU，運行 10ms，再傳輸 30ms，運行 10ms，完成。 J1 從開始到完成所用的時 間為： 30+10+30+10=80(ms) 。 J2 與其并行地在 IO1上傳輸 20ms，搶占J3的CPU，J2運行10ms后，被J1 搶占 CPU，等待 10ms 之后， J2 再次得到 CPU，運行 10ms， J2 啟動： IO2 傳輸， 40ms完成。 J2 從開始到完 成所用的時間為： 20+10+10+10+40=90(ms) 。 J3在CPU上執(zhí)行20ms，被J2搶占CPU，等待 30ms，再運行 10ms，等待 10ms

39、，J3啟動 IO1運行20ms的傳輸，完成。J3從開始到完成所用的時間為 20+30+10+10+20=90(ms) (2) 三個作業(yè)全部完成時， CPU的利用率為 (10+20+30+10)/90=7/9=78% 。 (3) 三個作業(yè)全部完成時， 外設 IO1 的利用率為 (20+30+20)/90=7/9=78% 。 )24. 有 A、B兩個程序，程序 A按順序使用 CPU為 10s，使用設備甲為 5s，使用 CPU為 5s，使用設備乙為 5s， 最后使用 CPU為10s。程序 B按順序使用設備甲為 10s、使用 CPU為 10s，使用設備乙為 5s，再使用 CPU為 5s，使用設備乙為

40、10s，試問： (1) 在順序環(huán)境下執(zhí)行程序 A和程序 B，CPU的利用率是多少 ? (2) 在多道 程序環(huán)境下， CPU的利用率是多少 ?正確答案： ( 此題考查學生對并發(fā)程序概念的理解。(1) 程序 A 和程序 B 順序執(zhí)行時，程序 A執(zhí)行完畢程序 B才開始執(zhí)行。兩個程序共耗時 75s ，其中占用 CPU 的時間為 40s ，因此順序執(zhí)行時 CPU的利用率為 40÷ 75=53%。(2) 在多道程序環(huán)境下，兩個程序并發(fā)執(zhí)行，其執(zhí)行情況如下表所示。 由表中數據可以看出， 兩個程序共耗時 40s，其中 CPU運行時間為 40s，故此時 CPU的利用率為 40/40=100%。 在多道

41、程序環(huán)境下程序 A、B 的執(zhí)行情況在多道程序環(huán)境下程序 A、B 的執(zhí)行情況CPU 程序 A(10s) 程序 B(10s) 程序 A(5s) 程序 B(5s) 設備 A(10s) 程序 A CPU 設備甲+等待 CPU 設備乙 CPU 程序 B 設備甲 CPU 設備乙 CPU 設備)25. 何謂死鎖 ?產生死鎖的原因和必要條件是什么 ?在解決死鎖問題的幾個方法中，哪種方法最容易實現?哪種方法使資源的利用率最高 ?正確答案： (1) 死鎖是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能 再向前推進。 (2) 產生死鎖的原因有二，一是競爭資源，二是進程推進順序非法。 (3)

42、 產生死鎖的必要條 件是互斥條件、請求和保持條件、不可剝奪條件和循環(huán)等待條件。 (4) 解決死鎖可歸納為四種方法：預防 死鎖、避免死鎖、檢測死鎖和解除死鎖。 (5) 解決死鎖的四種方法中，預防死鎖是最容易實現的，而避免 死鎖的發(fā)生則可以使資源的利用率最高。 )26. 簡述預防死鎖的辦法。正確答案： (1) 方法一：如果系統(tǒng)當前存在的資源數量能夠滿足進程的資源需求，便一次性地為進程分配 其所需的全部資源；在該進程完成之后再一次性地回收全部資源。這個做法被稱為摒棄“請求和保持”條 件，該方法可以預防死鎖。 (2) 方法二：當系統(tǒng)中某些進程在已經占有一定數量資源的情況下，又提出新 的資源請求，操作系

43、統(tǒng)不能立即滿足該進程的需求時，該進程必須立即釋放已經占有和保持的所有資源， 待以后需要時再重新申請：這種可以剝奪進程資源的做法可以有效地防止死鎖的產生。其被稱為摒棄“不 可剝奪”條件。 (3) 方法三：就是采用一定的方法，將所有可提供的資源按類型排序編號，所有進程對資 源的請求也必須嚴格按序號遞增的次序提出， 避免產生資源占有和資源需求的回路出現， 造成死鎖的產生。 此方法也被稱為摒棄“環(huán)路等待”條件。 )27. 為使用戶進程互斥地進入臨界區(qū)， 可以把整個臨界區(qū)實現成不可中斷的過程， 即用戶有屏蔽所有中斷的 能力。每當用戶程序進入臨界區(qū)的時候，屏蔽所有中斷；當出了臨界區(qū)的時候，再開放所有中斷。

44、你認為 這種方法有什么缺點 ?正確答案： ( 此題主要考查中斷概念在操作系統(tǒng)設計過程中的重要作用與臨界區(qū)的概念。 用戶進程進入臨 界區(qū)時屏蔽所有中斷，包括系統(tǒng)程序的中斷。假如屏蔽的是用戶進程，確實可以保護臨界資源，但如果連 系統(tǒng)所發(fā)出的中斷也被屏蔽的話，就會引起系統(tǒng)錯誤。雖然系統(tǒng)外中斷往往與當前運行的程序無關，但如 果是一些重要的硬件中斷，如電源故障等，就可能會引起錯誤，故不可盲目屏蔽所有中斷。 )28. 有三個進程 PA、PB和 PC合作解決文件打印問題： PA將文件記錄從磁盤讀入主存的緩沖區(qū) 1，每執(zhí)行一 次讀一個記錄； PB將緩沖區(qū) 1的內容復制到緩沖區(qū) 2，每執(zhí)行一次復制一個記錄； P

45、C將緩沖區(qū) 2 的內容打 印出來，每執(zhí)行一次打印一個記錄。緩沖區(qū)的大小等于一個記錄的大小。請用P、V 操作來保證文件的正確打印。正確答案： ( 本題考查用 P、V 操作解決進程的同步互斥問題。 (1) 進程 PA、PB、PC之間的關系為： PA與 PB共用一個單緩沖區(qū)， PB又與 PC共用一個單緩沖區(qū)，其合作方式如下圖所示。當緩沖區(qū)1 為空時，進程PA可將一個記錄讀入其中；若緩沖區(qū) 1 中有數據且緩沖區(qū) 2 為空，則進程 PB可將記錄從緩沖區(qū) 1復制到 緩沖區(qū) 2 中；若緩沖區(qū) 2 中有數據，則進程。 PC可以打印記錄。在其他條件下，相應進程必須等待。事實 上，這是一個生產者 -消費者問題。

46、* 為遵循這一同步規(guī)則。 應設置 4 個信號量 empty1、empty2、full1 、 full2 ，信號量 empty1 和 empty2 分別表示緩沖區(qū) 1 及緩沖區(qū) 2 是否為空，其初值為 1；信號量 full1 和 full2 分別表示緩區(qū) 1 及緩沖區(qū) 2 是否有記錄可供處理，其初值為 0 。 (2) 相應的進程描述如下： semaphore emptyl=1; / 緩沖區(qū) 1是否為空 semaphore full1=0; / 緩沖區(qū) 1是否有記錄可供處理 semaphore empty2=1; / 緩沖區(qū) 2 是否為空 semaphore full2=0; /緩沖區(qū) 2 是否有

47、記錄可供處理 cobegin processPA() while(TRUE) 從磁盤讀入一條記錄； P(emptyl); 將記錄存入緩沖區(qū) 1; V(full1); process PB() while(TRUE) P(full1); 從緩沖區(qū) 1中取出一條記錄； V(empty1); P(empty2); 將取出的記錄存 入緩沖區(qū) 2：V(full2); process PC() while(TRUE) P(full2); 從緩沖區(qū) 2 中取出一條記錄： V(empty2); 將取出的記錄打印出來 ; coend)29. 在一間酒吧里有 3個音樂愛好者隊列， 第 1隊的音樂愛好者只有隨身聽，

48、 第2隊只有音樂磁帶， 第 3隊 只有電池。而要聽音樂就必須隨身聽、音樂磁帶和電池這3 種物品俱全。酒吧老板一次出售這3 種物品中的任意兩種。當一名音樂愛好者得到這 3 種物品并聽完一首樂曲后，酒吧老板才能再一次出售這 3 種物品 中的任意兩種。于是第 2 名音樂愛好者得到這 3 種物品，并開始聽樂曲。全部買賣就這樣進行下去。試用 P、 V操作正確解決這一買賣。正確答案： (本題考查用 P、 V操作解決進程的同步互斥問題。 (1) 第 1隊音樂愛好者要競爭“待出售的音 樂磁帶和電池”，而且在初始狀態(tài)下系統(tǒng)并無“待出售的音樂磁帶和電池”，故可為該種資源設置一初值 為0的信號量 buy1；同樣，需

49、設置初值為 0的buy2、buy3 分別對應“待出售的隨身聽和電池”、“待出 售的隨身聽和音樂磁帶”。另外，為了同步買者的付費動作和賣者的給貨動作，還需設置信號量 payment 和 goods ，以保證買者在付費后才能得到所需商品。信號量music_over 用來同步音樂愛好者聽樂曲和酒吧老板的下一次出售行為。 (2) 具體的算法描述如下： semaphore buy1=buy2=buy3=0; semaphore payment=0; semaphore goods=0; semaphore music_over=0; cobegin process boss() /酒吧老板 while(

50、TRUE) 拿出任意兩種物品出售 ; if( 出售的是音樂磁帶和電池 ) V(buy1); else if( 出售的是隨身聽和電池 ) V(buy2); else if( 出售的是隨身聽和音樂磁帶 ) V(buy3); P(payment); / 等待付費 V(goods); / 給貨 P(music_over); / 等待樂曲結束 process fan1() /第 1 隊音樂愛好者 while(TRUE) P(buy1); /等待有音樂磁帶和電池出售 V(payment); / 付費 P(goods); / 取貨 欣賞一曲樂曲 ; V(music_over); / 通知老板樂曲結束 pro

51、cess fan2() /第 2隊音樂愛好者 while(TRUE) P(buy2); / 等待有隨身聽和電池出售 V(payment); / 付費 P(goods); / 取貨 欣賞一曲樂曲 ; V(music_over); / 通知老板樂曲結束 process fan3() / 第 3 隊音樂愛好者 while(TRUE) P(buy3); /等待有隨身聽和音樂磁帶出售V(payment); / 付費 P(goods); / 取貨 欣賞一曲樂曲 ; V(music_over); /通知老板樂曲結束 coend)30. 兄弟倆共同使用一個賬號，每次限存或取10 元，存錢與取錢的進程分別如下所

52、示：int amount=0;SAVE() TAKE() int m1; int m2; m1=amount; m2=amount; m2=m2-10; amount=m2; m1=m1+10;a mount=m1; 由于兄弟倆可能同時存錢和取錢，因此兩個進程是并發(fā)的。若哥哥先存了兩次錢，但在第三次存錢時弟弟 在取錢。請問： (1) 最后賬號 amount上面可能出現的值是多少 ? (2) 如何用 P、V操作實現兩并發(fā)進程的互 斥執(zhí)行 ?正確答案： ( 本題考查 P、V操作實現進程的互斥。 (1) 哥哥存兩次錢后，共享變量 amount 的值為 20。哥 哥的第三次存錢與弟弟的取錢同時進行，如

53、果兩者順序執(zhí)行，則最后amount 的值為 20；如果在一個進程的執(zhí)行過程中進行 CPU調度，轉去執(zhí)行另一進程， 則最后 amount的值取決于 amount=m1及 amount=m2的執(zhí) 行先后次序，若前者先執(zhí)行，則最后 amount 的值為 10，若后者先執(zhí)行，則最后 amount 的值為 30。因此， 最后賬號 amount 上可能出現的值有 10、 20、 30。 (2) 在上述問題中，共享變量 amount 是一個臨界資源， 為了實現兩并發(fā)進程對它的互斥訪問， 可為它設置一初值為 1 的互斥信號量 mutex，并將上述算法修改為： int amount=0; semaphore m

54、utex=1; / 互斥訪問 amount 變量的信號量 cobegin process SAVE() int m1; P(mutex); m1=amount; m1=m1+10; amount=m1; V(mutex); process TAKE() int m2; P(mutex); m2=amount; m2=m2-10; amount=m2; V(mutex); coend)31. 某系統(tǒng)有 R1、R2和R3三種資源， 在 T0時刻 P1、P2、P3和 P4四個進程對資源的占用和需求情況如下表 所示，此時系統(tǒng)的可用資源向量為 (2 ，1，2)。進程最大資源需求量已分配資源數量R1R2R

55、3R1R2R3P1322100P2613411P3314211P4422002試問：(1) 系統(tǒng)是否處于安全狀態(tài) ?如安全，請給出一個安全序列。(2) 如果此時 P1和 P2均發(fā)出資源請求向量 Request(1 ，0，1) ，為了保證系統(tǒng)的安全性，應該如何分配資 源給這兩個進程 ?說明你所采用的策略的原因。(3) 如果(2) 中兩個請求立即得到滿足，系統(tǒng)此刻是否處于死鎖狀態(tài)?正確答案： ( 本題考查采用銀行家算法避免死鎖。(1) 利用安全性算法對 T0 時刻的資源分配情況進行分析，可得到如下表所示的安全性檢測情況?？梢钥闯?， 此時存在一個安全序列 P2，P3，P4， P1，故該系統(tǒng)是安全的。

56、Work Need Allocation Work+Allocation FinishR1R 2R 3R 1 R2R 3R 1 R2 R3R1R2R3P2212 20 24 11613TrueP3623 10 32 11834TrueP4834 42 00 02836TrueP1836 22 21 00936True(2) 若此時 P1 發(fā)出資源請求Request1(1 ，0，1) ，按銀行家算法進行檢查：Request1(1 ，0，1) Need1(2 ，2，2) Request1(1 ，0，1)Available(2，1，2)試分配并修改相應的數據結構，由此形成的資源分配情況如下表所示Allocation Max Available 進程R1R2R3R1R 2R 3R 1R2R3P1100222P2512101111P3