操作系統(tǒng)自考復習重點

PAGEPAGE48一、操作系統(tǒng)概述習題及解答:硬件將處理機劃分為兩種狀態(tài)，即管態(tài)和目態(tài)，這樣做給操作系統(tǒng)設計帶來什么好處?答：便于設計安全可靠的操作系統(tǒng)。管態(tài)和目態(tài)是計算機硬件為保護操作系統(tǒng)免受用戶程序的干擾和破壞而引入的兩種狀態(tài)。通常操作系統(tǒng)在管態(tài)下運行，可以執(zhí)行所有機器指令；而用戶程序在目態(tài)下運行，只能執(zhí)行非特權指令。如果用戶程序企圖在目態(tài)下執(zhí)行特權指令，將會引起保護性中斷，由操作系統(tǒng)終止該程序的執(zhí)行，從而保護了操作系統(tǒng)。2．

何謂特權指令?舉例說明之。如果允許用戶進程執(zhí)行特權指令會帶來什么后果?答：在現(xiàn)代計算機中，一般都提供一些專門供操作系統(tǒng)使用的特殊指令，這些指令只能在管態(tài)執(zhí)行，稱為特權指令。這些指令包括：停機指令、置PSW指令、中斷操作指令（開中斷、關中斷、屏蔽中斷）、輸入輸出指令等。用戶程序不能執(zhí)行這些特權指令。如果允許用戶程序執(zhí)行特權指令，有可能干擾操作系統(tǒng)的正常運行，甚至有可能使整個系統(tǒng)崩潰。

3．中斷向量在機器中的存儲位置是由硬件確定的，還是由軟件確定的?答：中斷向量在機器中的存放位置是由硬件確定的。例如，在INTEL80x86CPU中，內存空間0x00000—0x003ff為中斷向量空間。

4．中斷向量的內容是由操作系統(tǒng)程序確定的，還是由用戶程序確定的?答：由操作系統(tǒng)程序確定的。向量的內容包括中斷處理程序的入口地址和程序狀態(tài)字（中斷處理程序運行環(huán)境），中斷處理程序是由操作系統(tǒng)裝入內存的，操作系統(tǒng)將根據裝入的實際地址和該中斷處理程序的運行環(huán)境來填寫中斷向量。

5．中斷向量內的處理機狀態(tài)位應當標明是管態(tài)還是目態(tài)?為什么?答：應當標明是管態(tài)。這樣才能保證中斷發(fā)生后進入操作系統(tǒng)規(guī)定的中斷處理程序。

6．中斷與程序并發(fā)之間的關系是什么？答：中斷是程序并發(fā)的前提條件。如果沒有中斷，操作系統(tǒng)不能獲得系統(tǒng)控制權，無法按調度算法對處機進行重新分配，一個程序將一直運行到結束而不會被打斷。

7．說明“棧”和“堆”的差別．答：棧是一塊按后進先出規(guī)則訪問的存儲區(qū)域，用來實現(xiàn)中斷嵌套和子程序調用的參數和返回斷點。堆雖然是一塊存儲區(qū)域，但是對堆的訪問是任意的，沒有后進先出的要求，堆主要用來為動態(tài)變量分配存儲空間。

8．何謂系統(tǒng)棧?何謂用戶棧?系統(tǒng)棧有何用途?用戶棧有何用途?答：系統(tǒng)棧是內存中屬于操作系統(tǒng)空間的一塊固定區(qū)域，其主要用途為：(1)保存中斷現(xiàn)場，對于嵌套中斷，被中斷程序的現(xiàn)場信息依次壓入系統(tǒng)棧，中斷返回時逆序彈出；(2)保存操作系統(tǒng)子程序間相互調用的參數、返回值、返回點、以及子程序的局部變量。用戶棧是用戶進程空間中的一塊區(qū)域，用于保存用戶進程的子程序間相互調用的參數、返回值、返回點、以及子程序的局部變量。

9．用戶堆棧段的長度為何無法確定?答：用戶堆棧段的長度主要取決于兩個因素：（1）用戶進程（線程）中子程序（函數）之間的嵌套調用深度；（2）子程序參數和局部變量的數量及類型。這些在進程（線程）運行前無法確定，由此導致用戶堆棧段的長度無法確定。

10．堆棧段的動態(tài)擴充為何可能導致進程空間的搬遷?答：堆棧段的擴充需要在原來進程空間大小的基礎上增添新的存儲區(qū)域，而且通常要求與原來存儲區(qū)域連續(xù)。由于原存放位置處可擴展的區(qū)域可能已經被其它進程占用，故可能需要將整個進程空間搬遷到另外一個區(qū)域，以實現(xiàn)地址空間擴展要求。

11．何謂并行?何謂并發(fā)?在單處理機系統(tǒng)中，下述并行和并發(fā)現(xiàn)象哪些可能發(fā)生，哪些不會發(fā)生?(1)進程與進程之間的并行；(2)進程與進程之間的并發(fā)；(3)處理機與設備之間的并行；(4)處理機與通道之間的并行；(5)通道與通道之間的并行；(6)設備與設備之間的并行。答：所謂并行是指同一時刻同時進行，進程并行需要多處理器的支持；所謂并發(fā)，是指在一段時間內，多個進程都在向前推進，而在同一時刻，可能只有一個進程在執(zhí)行，多個進程輪流使用處理器。在單處理器系統(tǒng)中，可能發(fā)生的并行和并發(fā)現(xiàn)象如下：(2)進程與進程之間的并發(fā)。例如，在Windows操作系統(tǒng)中，mp3播放進程和Word字處理進程可以并發(fā)執(zhí)行，這樣用戶就可以邊聽音樂邊寫文章了。(3)處理機與設備之間的并行。例如，當處理機進行科學運算時，打印機可以打印文檔。(4)處理機與通道之間的并行。通道程序的執(zhí)行可與處理機的操作并行。(5)通道與通道之間的并行。通常一個系統(tǒng)中有多個通道，這些通道可以并行地執(zhí)行相應的通道程序。(6)設備與設備之間的并行。例如打印機打印文檔時，磁帶機在輸入數據。

12．何謂作業(yè)?它包括哪幾個部分?各部分用途是什么?答：所謂作業(yè)是指用戶要求計算機系統(tǒng)為其完成的計算任務的集合，一個作業(yè)通常包括程序、程序所處理的數據以及作業(yè)說明書。程序用來完成特定的功能，數據是程序處理的對象，作業(yè)說明書用來說明作業(yè)處理的步驟。

13．從透明性和資源共享兩方面，說明網絡操作系統(tǒng)與分布式操作系統(tǒng)之間的差別。答：從透明性上看，分布式操作系統(tǒng)優(yōu)于網絡操作系統(tǒng)。網絡用戶能夠感覺到所訪問的資源是在本地還是在遠地；而在分布式系統(tǒng)中，用戶感覺不到所訪問的資源是否在本地。分布式操作系統(tǒng)掩蓋了資源在地理位置上的差異。從資源共享上看，分布式操作系統(tǒng)比網絡操作系統(tǒng)能共享更多的資源。在網絡操作系統(tǒng)中，一個計算任務不能由一臺主機任意遷移到另外一臺主機上運行；而在分布式操作系統(tǒng)中，所有作業(yè)可以由一臺主機任意遷移到另外一臺主機上處理，即可實現(xiàn)處理機和存儲資源的共享，從而達到整個系統(tǒng)的負載平衡。

14．為什么構成分布式系統(tǒng)的主機一般都是相同的或兼容的?答：這樣更有利于進程的動態(tài)遷移。如果主機不兼容，則在一臺主機上能運行的進程，因所用指令系統(tǒng)不同，在另一臺主機上可能無法運行，導致進程難于在不同主機間遷移，使得分布式系統(tǒng)難于實現(xiàn)負載平衡。

15．為什么嵌入式操作系統(tǒng)通常采用微內核結構？答：嵌入式操作系統(tǒng)與一般操作系統(tǒng)相比具有比較明顯的差別:(1)嵌入式操作系統(tǒng)規(guī)模一般較小，因為一般硬件配置較低，而且對操作系統(tǒng)提供的功能要求也不高。(2)應用領域差別大，對于不同的應用領域其硬件環(huán)境和設備配置情況有明顯差別。所以，嵌入式操作系統(tǒng)一般采用微內核(microkernel)結構。微內核包括如下基本成分:(1)處理機調度；(2)基本內存管理；(3)通訊機制；(4)電源管理。二、進程管理習題及解答:

1.為何引入多道程序設計?在多道程序系統(tǒng)中，內存中作業(yè)的道數是否越多越好?請說明原因。答：引入多道程序設計技術是為了提高計算機系統(tǒng)資源的利用率。在多道程序系統(tǒng)中，內存中作業(yè)的道數并非越多越好。一個計算機系統(tǒng)中的內存、外設等資源是有限的，只能容納適當數量的作業(yè)，當作業(yè)道數增加時，將導致對資源的競爭激烈，系統(tǒng)開銷增大，從而導致作業(yè)的執(zhí)行緩慢，系統(tǒng)效率下降。

2.什么是進程?進程具有哪些主要特性?比較進程與程序之間相同點與不同點．答：進程是具有一定獨立功能的程序關于一個數據集合的一次運行活動。進程具有以下主要特性：（1）并發(fā)性：可以與其它進程一道在宏觀上同時向前推進。（2）動態(tài)性：進程是執(zhí)行中的程序。此外進程的動態(tài)性還體現(xiàn)在如下兩個方面：首先，進程是動態(tài)產生、動態(tài)消亡的；其次，在進程的生存期內，其狀態(tài)處于經常性的動態(tài)變化之中。（3）獨立性：進程是調度的基本單位，它可以獲得處理機并參與并發(fā)執(zhí)行。（4）交往性：進程在運行過程中可能會與其它進程發(fā)生直接或間接的相互作用。（5）異步性：每個進程都以其相對獨立、不可預知的速度向前推進。（6）結構性：每個進程有一個控制塊PCB。進程和程序的相同點：程序是構成進程的組成部分之一，一個進程存在的目的就是執(zhí)行其所對應的程序，如果沒有程序，進程就失去了其存在的意義。進程與程序的差別：（1）程序是靜態(tài)的，而進程是動態(tài)的；（2）程序可以寫在紙上或在某一存儲介質上長期保存，而進程具有生存期，創(chuàng)建后存在，撤銷后消亡；(3)一個程序可以對應多個進程，但一個進程只能對應一個程序；例如，一組學生在一個分時系統(tǒng)中做C語言實習，他們都需要使用C語言的編譯程序對其源程序進行編譯，為此每個學生都需要有一個進程，這些進程都運行C語言的編譯程序。另外，一個程序的多次執(zhí)行也分別對應不同的進程。

3.有人說，用戶進程所執(zhí)行的程序一定是用戶自己編寫的。這種說法對嗎？如不對舉例說明之。答：這種說法不對。例如，C編譯程序以用戶進程身份運行，但C編譯程序一般并不是用戶自己編寫的。此外還有調試程序、字處理程序等工具軟件。

4.什么是進程上下文？進程上下文包括哪些成分？哪些成分對目態(tài)程序是可見的？答：進程是在操作系統(tǒng)支持下運行的，進程運行時操作系統(tǒng)需要為其設置相應的運行環(huán)境，如系統(tǒng)堆棧、地址映射寄存器、打開文件表、PSW與PC、通用寄存器等。在UNIXSystemV中，將進程的物理實體與支持進程運行的物理環(huán)境合稱為進程上下文(processcontext)，進程上下文包括三個組成部分：·用戶級上下文。是由用戶進程的程序塊、用戶數據塊（含共享數據塊）和用戶堆棧組成的進程地址空間?！は到y(tǒng)級上下文。包括進程控制塊、內存管理信息、進程環(huán)境塊，以及系統(tǒng)堆棧等組成的進程地址空間·寄存器上下文。由程序狀態(tài)字寄存器、各類控制寄存器、地址寄存器、通用寄存器、用戶堆棧指針等組成。其中用戶級上下文和部分寄存器上下文對目態(tài)程序是可見的。

5.

進程一般具有哪三個主要狀態(tài)？舉例說明狀態(tài)轉換的原因。答：進程在其生存期內可能處于如下三種基本狀態(tài)之一:(1)運行態(tài)(Run):進程占有處理機資源，正在運行。顯然，在單處理機系統(tǒng)中任一時刻只能有一個進程處于此種狀態(tài);(2)就緒態(tài)(Ready):進程本身具備運行條件，但由于處理機的個數少于可運行進程的個數，暫未投入運行。即相當于等待處理機資源(3)等待態(tài)(Wait):也稱掛起態(tài)(Suspended)、封鎖態(tài)(Blocked)、睡眠態(tài)(Sleep)。進程本身不具備運行條件，即使分給它處理機也不能運行。進程正等待某一個事件的發(fā)生，如等待某一資源被釋放，等待與該進程相關的I/O傳輸的完成信號等。進程的三個基本狀態(tài)之間是可以相互轉換的。具體地說，當一個就緒進程獲得處理機時，其狀態(tài)由就緒變?yōu)檫\行；當一個運行進程被剝奪處理機時，如用完系統(tǒng)分給它的時間片、出現(xiàn)更高優(yōu)先級別的其它進程，其狀態(tài)由運行變?yōu)榫途w；當一個運行進程因某事件受阻時，如所申請資源被占用、啟動I/O傳輸未完成，其狀態(tài)由運行變?yōu)榈却?；當所等待事件發(fā)生時，如得到申請資源、I/O傳輸完成，其狀態(tài)由等待變?yōu)榫途w。

6.

有幾種類型進程隊列？每類各應設置幾個隊列？答：通常，系統(tǒng)中的進程隊列分為如下三類：(1)就緒隊列：整個系統(tǒng)一個。所有處于就緒狀態(tài)的進程按照某種組織方式排在這一隊列中，進程入隊列和出隊列的次序與處理機調度算法有關。在某些系統(tǒng)中，就緒隊列可能有多個，用以對就緒進程分類，以方便某種調度策略的實施。(2)等待隊列：每個等待事件一個，當進程等待某一事件時，進入與該事件相關的等待隊列中；當某事件發(fā)生時，與該事件相關的一個或多個進程離開相應的等待隊列，進入就緒隊列。(3)運行隊列：在單CPU系統(tǒng)中只有一個，在多CPU系統(tǒng)中每個CPU各有一個，每個隊列中只有一個進程，指向運行隊列頭部的指針被稱作運行指示字。

7.線程控制塊TCB中一般應包含那些內容？答：一般TCB中的內容較少，因為有關資源分配等多數信息已經記錄于所屬進程的PCB中．TCB中的主要信息包括線程標識、線程狀態(tài)、調度參數、現(xiàn)場、鏈接指針，其中現(xiàn)場信息主要包括通用寄存器、指令計數器PC以及用戶棧指針．對于操作系統(tǒng)支持的線程，TCB中還應包含系統(tǒng)棧指針。

8.同一進程中的多個線程有哪些成分是共用的，哪些成分是私用的？答：同一進程中的多個線程共享進程獲得的主存空間和資源，包括代碼區(qū)、數據區(qū)、動態(tài)堆空間。線程的私有成分包括：線程控制塊；一個執(zhí)行棧；運行時動態(tài)分給線程的寄存器。

9.比較用戶級線程與系統(tǒng)級線程間在以下方面的差別和各自的優(yōu)缺點。(1)創(chuàng)建速度；(2)切換速度；(3)并行性；(4)TCB的存儲位置答：用戶級線程由系統(tǒng)庫支持。線程的創(chuàng)建和撤銷，以及線程狀態(tài)的變化都由庫函數控制并在目態(tài)完成，與線程相關的控制結構TCB保存在目態(tài)空間并由運行系統(tǒng)維護。由于線程對操作系統(tǒng)不可見，系統(tǒng)調度仍以進程為單位，核心棧的個數與進程個數相對應。用戶級別線程的優(yōu)點在于：(1)線程不依賴于操作系統(tǒng)，可以采用與問題相關的調度策略，靈活性好；(2)同一進程中的線程切換不需進入操作系統(tǒng)，因而實現(xiàn)效率較高。缺點在于：(1)同一進程中的多個線程不能真正并行，即使在多處理機環(huán)境中；(2)由于線程對操作系統(tǒng)不可見，調度在進程級別，某進程中的一個線程通過系統(tǒng)調用進入操作系統(tǒng)受阻，該進程的其它線程也不能運行。核心級別線程通過系統(tǒng)調用由操作系統(tǒng)創(chuàng)建，線程的控制結構TCB保存于操作系統(tǒng)空間，線程狀態(tài)轉換由操作系統(tǒng)完成，線程是CPU調度的基本單位。另外由于系統(tǒng)調度以線程為單位，操作系統(tǒng)還需要為每個線程保持一個核心棧。核心級線程的優(yōu)點是并發(fā)性好，在多CPU環(huán)境中同一進程中的多個線程可以真正并行執(zhí)行。核心級別線程的缺點是線程控制和狀態(tài)轉換需要進入操作系統(tǒng)完成，系統(tǒng)開銷比較大。

10.何謂作業(yè)?何謂作業(yè)步？作業(yè)何時轉為進程?答：作業(yè)是早期批處理系統(tǒng)引入的一個概念。用戶要求計算機系統(tǒng)為其完成的計算任務的集合稱為作業(yè)，分時用戶在一次登錄后所進行的交互過程也常被看作一個作業(yè)。一般來說，作業(yè)是比進程大的一個概念，一個作業(yè)通常包含多個計算步驟，作業(yè)中一個相對獨立的處理步驟稱為一個作業(yè)步。當作業(yè)被作業(yè)調度程序選中并調入內存時，將按作業(yè)步創(chuàng)建相應進程。作業(yè)步驟之間具有順序或并發(fā)關系。一個作業(yè)步通?？梢杂梢粋€進程來完成，這樣一個作業(yè)在內存處理時通常與多個進程相對應，即作業(yè)與進程具有一對多的關系。

11.分析作業(yè)、進程、線程三者之間的關系。答：一個作業(yè)被調入內存執(zhí)行時可能要為其創(chuàng)建多個進程，進程是資源分配的基本單位，一個進程可能對應若干個線程，線程是處理器調度的基本單位。

12.

何謂系統(tǒng)開銷?試舉三個例子說明之。答：運行操作系統(tǒng)程序，實現(xiàn)系統(tǒng)管理所花費的時間和空間稱為系統(tǒng)開銷。例如，操作系統(tǒng)的內核要占用內存空間，頁面調度時需占用設備資源并消耗處理機時間，進程切換時也要占用處理器時間。三、處理機調度習題及解答:1.試說明下述概念之間的聯(lián)系與差別:(1)系統(tǒng)調用命令(2)訪管指令(3)廣義指令答：訪管指令由指令碼和訪管中斷號兩部分組成。即:SVCn───①其中SVC(SuperVisorCall)為指令碼，表明為訪管指令;n為訪管中斷號，其值是一整數，具體表示何種訪問要求。中斷發(fā)生時，硬件中斷裝置將訪管中斷號n送入舊的程序狀態(tài)字內的中斷碼字段，訪管中斷總控程序由系統(tǒng)堆棧中將其取出，并據此轉入對應的服務程序。在實際使用時，用戶程序與操作系統(tǒng)之間還需要相互傳遞參數和返回值。如此，用戶使用訪管指令的一般形式為:準備參數SVCn取返回值───②根據具體訪管要求約定，參數及返回值可以通過寄存器傳遞，也可以通過內存?zhèn)鬟f。對于后者，操作系統(tǒng)必須能夠訪問進程空間。通常將②稱為系統(tǒng)調用命令，它除訪管指令外，還有準備參數和取返回值。為了使用方便，在高級語言中一般將其寫為與過程調用相類似的形式，即:返回值＝系統(tǒng)調用名稱(參數1,參數2,…,參數m);───③當然，編譯程序會將③翻譯成形如②的形式。其中系統(tǒng)調用名稱對應①，不同的系統(tǒng)調用名稱對應不同的整數n。在有的書中，也將③稱為代表②的宏指令或廣義指令。

2.為什么說中斷是進程切換的必要條件，但不是充分條件?答：假如在時刻T1與時刻T2之間發(fā)生了進程切換，則在時刻T1與時刻T2之間一定執(zhí)行了處理機調度程序，而處理機調度程序是操作系統(tǒng)低層中的一個模塊，運行于管態(tài)，說明在T1與T2時刻之間處理機狀態(tài)曾由目態(tài)轉換到管態(tài)。由于中斷是系統(tǒng)由目態(tài)轉換為管態(tài)的必要條件，所以在時刻T1與時刻T2之間一定發(fā)生過中斷，也就是說，中斷是進程切換的必要條件，然而中斷不是進程切換的充分條件。例如:一個進程執(zhí)行一個系統(tǒng)調用命令將一個消息發(fā)給另外一個進程，該命令的執(zhí)行將通過中斷進入操作系統(tǒng)，操作系統(tǒng)處理完消息的發(fā)送工作后可能返回原調用進程，此時中斷未導致進程切換；也可能選擇一個新的進程，此時中斷導致了進程切換。

3.試分析中斷與進程狀態(tài)轉換之間的關系。答：進程狀態(tài)轉換是由內核控制的，如果一個進程的狀態(tài)發(fā)生了改變，則在新舊狀態(tài)之間一定發(fā)生了處理機狀態(tài)由目態(tài)到管態(tài)的轉換，而中斷是處理機狀態(tài)由目態(tài)轉換到管態(tài)的必要條件，所以中斷也是進程狀態(tài)轉換的必要條件。

4.中斷發(fā)生時，舊的PSW和PC為何需要壓入系統(tǒng)棧?答：因為通常中斷處理程序的最后一條指令是中斷返回指令，該指令從系統(tǒng)棧頂彈出斷點信息，如果未將PSW和PC壓入系統(tǒng)棧，則中斷返回指令彈出的不是中斷前的斷點信息，而是不確定的信息，這將導致系統(tǒng)處于不確定的狀態(tài)，嚴重的情況會使系統(tǒng)崩潰。采用棧結構的原因是中斷可能發(fā)生嵌套，此時能保證以與中斷相反的次序返回上層中斷處理程序或返回目態(tài)。在某些硬件系統(tǒng)中，沒有采用棧結構，中斷發(fā)生時現(xiàn)場信息被送到系統(tǒng)空間指定單元，對每種中斷硬件規(guī)定一個現(xiàn)場保存單元，這樣處理的缺點是中斷類型不能增加，相同類型中斷不能嵌套發(fā)生。

5.何謂中斷向量?用戶能否修改中斷向量的值?答：當中斷事件發(fā)生時，中斷裝置根據中斷類別自動地將中斷處理程序所對應的PSW和PC送入程序狀態(tài)字和指令計數器中，如此便轉移到對應的中斷處理程序。這個轉移類似于向量轉移，因而PSW和PC被稱為中斷向量。用戶不能修改中斷向量的值，因為修改中斷向量是特權指令，普通用戶程序不能執(zhí)行特權指令。另外，如果允許用戶修改中斷向量的值，那么用戶就可以破壞中斷向量與處理程序之間的聯(lián)系，并可能攻擊系統(tǒng)。例如將中斷向量與一段病毒程序聯(lián)系起來，使中斷發(fā)生時便執(zhí)行病毒程序，從而破壞計算機系統(tǒng)。

6.中斷向量的存儲位置是否可由程序改變?為什么?中斷向量的值是如何確定的?答：中斷向量的存儲位置是由硬件確定的，不能由程序改變。中斷發(fā)生后，中斷裝置按照中斷類型到內存指定位置取出中斷向量。例如，在IBMPC系統(tǒng)中，地址000~03FF是中斷向量空間。操作系統(tǒng)的設計者根據各中斷事件處理程序的存儲位置及運行環(huán)境確定對應中斷向量的值，系統(tǒng)啟動時由初始化程序將該值填入指定位置。

7.有人說，中斷發(fā)生后硬件中斷裝置保證處理機進入管態(tài)，這種說法準確嗎?說明理由。答：這種說法不準確。中斷發(fā)生后，硬件中斷裝置負責引出中斷處理程序，中斷處理程序是否運行于管態(tài)取決于PSW中的處理機狀態(tài)位，該位的值是操作系統(tǒng)初始化時設置的，只有在初試化程序正確設置該狀態(tài)位的前提下，才能保證中斷后系統(tǒng)進入管態(tài)。

8.為什么在中斷處理過程中通常允許高優(yōu)先級別的中斷事件中途插入，而不響應低優(yōu)先級別的中斷事件?答：根據引起中斷事件的重要性和其緊迫程度，硬件將中斷源分為若干個級別，稱作中斷優(yōu)先級。如果有多個中斷同時發(fā)生，硬件將首先響應優(yōu)先級別最高的中斷請求。對于相同優(yōu)先級別的中斷，硬件將按照事先規(guī)定好的次序依次響應。在中斷事件的處理過程中可能會發(fā)生新的中斷，這就是中斷嵌套。中斷嵌套是必要的。但是，如果不加以控制，低優(yōu)先級別的中斷源可能打擾高優(yōu)先級別中斷事件的處理過程，甚至可能會使中斷嵌套層數無限增長，直至系統(tǒng)棧溢出。為此，硬件提供了中斷屏蔽指令，利用中斷屏蔽指令可以暫時禁止任意一個或多個中斷源向處理機發(fā)中斷請求。當然，在需要的時候還可以利用硬件指令解除對中斷源的屏蔽。通常，在一個中斷事件的處理過程中，程序屏蔽包括該級在內的所有低優(yōu)先級別的中斷，但允許更高優(yōu)先級別的中斷中途插入。這樣，發(fā)生中斷嵌套時，嵌套中斷事件的優(yōu)先級別是按照響應的順序依次遞增的。這樣做處理主要有兩個原因：(1)從邏輯上來說，高優(yōu)先級別中斷源所對應的事件比低優(yōu)先級別中斷源所對應的中斷事件急迫；(2)由于硬件中斷類型是有限的，這樣做實際上也就限制了中斷嵌套的深度。

9.為什么說“關中斷”會影響系統(tǒng)的并發(fā)性?答：考慮單處理機系統(tǒng)。在單處理機系統(tǒng)中，并發(fā)是通過將處理機輪流分配給多個進程而實現(xiàn)的，這個分配是由操作系統(tǒng)中處理機調度程序完成的。中斷是進程切換的必要條件，如果關了中斷，則操作系統(tǒng)無法獲得處理機的控制權，也就無法使多個進程分時共享處理機。在關中斷期間，一個進程獨占處理機。所以說“關中斷”會影響系統(tǒng)的并發(fā)性

10.假如關中斷后操作系統(tǒng)進入了死循環(huán)，會產生什么后果?答：系統(tǒng)不響應任何外部干預事件，系統(tǒng)表現(xiàn)為“死機”。

11.為什么不允許目態(tài)程序執(zhí)行關中斷指令及中斷屏蔽指令?答：開關中斷指令和中斷屏蔽指令屬于特權指令，一般用戶無權訪問。如果允許用戶使用，用戶關中斷后可能影響系統(tǒng)對內部或外部事件的響應，也會使操作系統(tǒng)無法獲得系統(tǒng)控制權。

12.如果沒有中斷，是否能夠實現(xiàn)多道程序設計?為什么?答：不能。因為一個程序一旦被調度執(zhí)行，將一直執(zhí)行下去，中間不可能被打斷，不可能達到多個進程交替執(zhí)行的并發(fā)目的。

13.下列中斷源哪些通常是可以屏蔽的，哪些通常是不可屏蔽的?(1)I/O中斷；(2)訪管中斷；(3)時鐘中斷；(4)掉電中斷。答：(1)I/O中斷可以屏蔽；(2)訪管中斷不可以屏蔽；(3)時鐘中斷可以屏蔽；(4)掉電中斷不可以屏蔽。對于訪管中斷來說，若在管態(tài)屏蔽沒有意義（不會發(fā)生訪管中斷）；若在目態(tài)屏蔽，則應用程序無法訪問操作系統(tǒng)，不能正常運行。

14.下列中斷事件哪些可由用戶自行處理?哪些只能由操作系統(tǒng)中斷服務程序統(tǒng)一處理?為什么?(1)溢出；(2)地址越界；(3)除零；(4)非法指令；(5)掉電答：一般來說，只影響應用程序自身的中斷，可以由用戶自行處理，包括：(1)溢出；(3)除零?？赡苡绊懫渌脩艋虿僮飨到y(tǒng)的中斷只能由操作系統(tǒng)中斷服務程序統(tǒng)一處理，包括：(2)地址越界；(4)非法指令；(5)掉電。

15.如果中斷由用戶程序自行處理，為何需要將被中斷程序的斷點由系統(tǒng)堆棧彈出并壓入用戶堆棧?答：中斷發(fā)生時，被中斷程序的現(xiàn)場信息已被壓入系統(tǒng)棧中。而中斷續(xù)元運行于目態(tài)，它執(zhí)行完畢后將由用戶棧區(qū)中恢復現(xiàn)場。為此，操作系統(tǒng)在轉到中斷續(xù)元之前應當將系統(tǒng)棧中的現(xiàn)場信息彈出并壓入用戶棧中，否則用戶中斷續(xù)元執(zhí)行完畢后將無法恢復現(xiàn)場返回斷點。

16.對于下面中斷與進程狀態(tài)轉換之間的關系各舉兩個例子說明之:(1)定會引起進程狀態(tài)轉換的中斷事件;(2)可能引起進程狀態(tài)轉換的中斷事件。答：定會引起進程狀態(tài)轉換的中斷事件：當前運行進程終止、應用程序啟動I/O傳輸并等待I/O數據、運行程序申請當前被占用的某一資源?？赡芤疬M程狀態(tài)轉換的中斷事件：時鐘中斷事件可能引起進程狀態(tài)轉換，例如對于時間片輪轉進程調度算法，若時鐘中斷發(fā)生后，當前進程的時間片已用完，則將發(fā)生進程切換；否則不發(fā)生進程切換。

17.若在T1時刻進程P1運行，T2時刻進程P2運行，且P1≠P2,則在時刻T1和時刻T2期間之內一定發(fā)生過中斷。這種說法對嗎?為什么?答：這種說法對。如果在時刻T1進程P1在運行，在時刻T2進程P2在運行，且P1≠P2，則說在時刻T1和時刻T2之間發(fā)生了進程切換。這說明在時刻T1和時刻T2之間執(zhí)行了處理機調度程序，而處理機調度程序是操作系統(tǒng)低層中的一個模塊，在系統(tǒng)運行的過程中，除非顯式地調用到該模塊，否則系統(tǒng)不會由運行一個進程轉去運行另外一個進程，就是說不會發(fā)生進程切換。只有進入操作系統(tǒng)，即處于系統(tǒng)態(tài),才有可能調用到處理機調度，因為處于用戶態(tài)運行的用戶程序不可能直接調用操作系統(tǒng)中的任何模塊。中斷是系統(tǒng)由用戶態(tài)轉換為系統(tǒng)態(tài)的必要條件。據此，假如在時刻T1與時刻T2之間發(fā)生了進程切換，則在時刻T1與時刻T2之間一定發(fā)生過中斷。

18.進程切換時，上升進程的PSW和PC為何必須由一條指令同時恢復?答：中斷向量中程序狀態(tài)字PSW與指令計數器PC的內容必須由一條指令同時恢復，這樣才能保證系統(tǒng)狀態(tài)由管態(tài)轉到目態(tài)的同時，控制轉到上升進程的斷點處繼續(xù)執(zhí)行。如果不同時恢復，則只能（1）先恢復PSW再恢復PC，在恢復PSW后已經轉到目態(tài)，操作系統(tǒng)恢復PC的使命無法完成；（2）先恢復PC再恢復PSW，PC改變后轉到操作系統(tǒng)另外區(qū)域（因為PSW仍為系統(tǒng)狀態(tài)），PSW無法恢復。

19.某系統(tǒng)采用可搶占處理機的靜態(tài)優(yōu)先數調度算法，請問何時會發(fā)生搶占處理機的現(xiàn)象?答：當一個新創(chuàng)建的進程或一個被喚醒進程的優(yōu)先數比正在運行進程的優(yōu)先數高時，可能發(fā)生搶占處理機現(xiàn)象。

20.在實時系統(tǒng)中，采用不可搶占處理機的優(yōu)先數調度算法是否適宜?為什么?答：不適宜。一旦一個低優(yōu)先數、需要大量CPU時間的進程占用處理機，就會一直運行，直到運行結束，或者直到因某事件而阻塞。在此之前，即使高優(yōu)先數的緊急任務到達，也得不到處理，因而可能延誤對重要事件的響應和處理。

21.在分時系統(tǒng)中，進程調度是否只能采用時間片輪轉算法?為什么?答：分時系統(tǒng)的特點是要求響應速度及時，除RR算法之外，還可以采用可剝奪CPU的動態(tài)優(yōu)先數調度算法。如經典UNIX的處理機調度算法，由于負反饋性質，算法也可以保證響應速度。

22.有人說，在采用等長時間片輪轉處理機調度算法的分時操作系統(tǒng)中，各終端用戶所占有處理機的時間總量是相同的。這種說法對嗎?為什么?答：這種說法不對。因為處理機是分配給進程（線程）的，而不同終端用戶可能有不同數量的進程，一個擁有較多數量進程的終端顯然比擁有較少數量進程的終端獲得CPU的時間要多。

23.對于下述處理機調度算法分別畫出進程狀態(tài)轉換圖。(1)時間片輪轉算法;(2)可搶占處理機的優(yōu)先數調度算法;(3)不可搶占處理機的優(yōu)先數調度算法。答：(1)時間片輪轉算法(2)可搶占處理機的優(yōu)先數調度算法;(3)不可搶占處理機的優(yōu)先數調度算法

24.舉出兩個例子說明操作系統(tǒng)訪問進程空間的必要性。答：例（1）：進程執(zhí)行輸出操作時，通過系統(tǒng)調用進入系統(tǒng)，由操作系統(tǒng)將待輸出的數據由進程空間取出送給指定的外部設備，為此操作系統(tǒng)必須訪問用戶進程空間。例（2）：當發(fā)生可由用戶自己處理的中斷事件時，操作系統(tǒng)在轉到中斷續(xù)元之前應當將系統(tǒng)堆棧中的現(xiàn)場信息彈出并壓入用戶堆棧中，為此操作系統(tǒng)也必須訪問進程空間。

25．根據進程和線程的組成說明進程調度和線程調度各需要完成哪些工作。答：進程調度：(1)地址映射寄存器；(2)用戶棧指針；(3)通用寄存器；(4)PSW與PC。線程調度：(1)用戶棧指針；(2)通用寄存器；(3)PC。

26.系統(tǒng)資源利用率與系統(tǒng)效率是否一定成正比?如不是，舉例說明之。答：系統(tǒng)效率高則資源利用率高，而反之卻不盡然。例如，在虛擬頁式存儲管理系統(tǒng)中，當頁面置換算法不合理或分給進程的頁架數過少時，可能發(fā)生抖動(thrashing)，此時I/O設備很忙碌，但系統(tǒng)效率可能很低。

27.設有周期性實時任務集如下表所示，用EDF算法和RMS算法是否可以調度？畫出相應的Gantt圖。任務發(fā)生周期Ti處理時間CiA3010B4015C505答：由于，因而采用EDF算法一定可以調度，其Gantt圖為：

C1A1B1A2B2C251015101550

5

15

30

40

55

60A1B1C1A2B2C2A3

B3A4C3

101551015510

15105

010

253040

5560708095105110120

由于，因而采用RMS算法不可調度。28.分析Linux進程調度算法的調度效果。答：Linux在調度級別上考慮三種特征進程：Real-timeFIFO,Real-timeRoundRobin,Timesharing.調度基于Goodness度量指標，涉及如下一些參量：Priority:1~40(缺省值20)，可通過nice系統(tǒng)調用調整，nice(value)中value的取值范圍為(-20,20)之間，以與經典UNIX保持兼容，但在內部對value值進行反向，取priority=20-value。Quantum:進程尚可運行的剩余時間．對于運行進程來說，每個時鐘間隔(10ms，稱為一個jiffy)，將quantum減1，當所有就緒進程的quantum配額下降到0時，重新計算所有進程(包括等待進程)的quantum值。Goodness值的計算方法如下：If(Real-time)Goodness=1000+priority;If(Timesharing&&quantum=0))Goodness=0;If(Timesharing&&quantum>0)Goodness=quantum+priority.調度發(fā)生在如下時刻：(1)運行進程的quantum減至0；(2)運行進程執(zhí)行系統(tǒng)調用exit；(3)運行進程因等待I/O、信號燈而被封鎖；(4)原來具有高goodness的進程被解除封鎖。容易看出調度效果：實時優(yōu)先于分時，交互和I/O進程優(yōu)先于CPU進程。四、同步與互斥習題及解答:

何謂與時間有關的錯誤?舉例說明之。答：并發(fā)進程的執(zhí)行實際上是進程活動的某種交叉，某些交叉次序可能得到錯誤結果。由于具體交叉的形成與進程的推進速度有關，而速度是時間的函數，因而將這種錯誤稱為與時間有關的錯誤。例如，兩個并發(fā)進程的程序如下：intn=0;main(){創(chuàng)建進程A；創(chuàng)建進程B；}；

A(){while(1){n++;}};B(){while(1){睡眠一段時間；printf(“%d”,n);n=0;}};假設進程A被部署在公園入口的終端上，用來記錄一段時間內進入公園的人數，進程B被部署在公園的控制中心，用來輸出一段時間內進入公園的總人數。進程A和進程B共享全局變量n，n表示記錄下的人數。如果在進程B執(zhí)行完打印語句后被進程A打斷，進程A執(zhí)行了若干次變量自增語句，之后進程B接著執(zhí)行清0語句，那么進程A對n的累加丟失了，相當于進程B被打斷的這段時間內進入公園的人沒有被記錄下來。發(fā)生與時間有關的錯誤。

2．有人說，假設兩個進程之間沒有共享內存，則二者之間沒有公共變量，這種說法準確嗎?說明原因。答：如果只從用戶空間考慮，這種說法是正確的。但從操作系統(tǒng)的角度來說并不準確。兩個沒有公共內存的用戶進程可能同時（宏觀）進入操作系統(tǒng)，并訪問操作系統(tǒng)空間中的公共變量。

3．何謂忙式等待?是否還有其它方式的等待?比較它們之間的聯(lián)系和差別。答：不進入等待狀態(tài)的等待稱為忙式等待。另一種等待方式是阻塞式等待，進程得不到共享資源時將進入阻塞狀態(tài)，讓出CPU給其他進程使用。忙等待和阻塞式等待的相同之處在于進程都不具備繼續(xù)向前推進的條件，不同之處在于處于忙等待的進程不主動放棄CPU，盡管CPU可能被剝奪，因而是低效的；而處于阻塞狀態(tài)的進程主動放棄CPU，因而是高效的。

4．下列進程互斥方法哪些存在忙式等待問題?

（1）軟件:面包店算法(2)硬件:TS指令(3)關中斷指令答：（1）、（2）存在忙等待問題。

5．為何開關中斷進程互斥方法僅在單CPU系統(tǒng)中是有效的？答：關中斷方法不適用于多CPU系統(tǒng)，因為關中斷只能保證CPU不由一個進程切換到另外一個進程，從而防止多個進程并發(fā)地進入公共臨界區(qū)域。但即使關中斷后，不同進程仍可以在不同CPU上并行執(zhí)行關于同一組共享變量的臨界區(qū)代碼.

6．在多處理機系統(tǒng)中，軟件互斥方法是否有效？為什么？答：依然有效。多處理機并行與單處理并發(fā)之間的差別在于程序交叉的粒度，單處理機機環(huán)境中進程交叉發(fā)生在指令之間，多處理機環(huán)境中進程交叉發(fā)生在指令周期之間。由于純軟件互斥算法并不依賴特殊的硬件指令(如test_and_set)，指令之間的交叉與指令周期之間的交叉結果相同。

7．試分析臨界區(qū)域的大小與系統(tǒng)并發(fā)性之間的關系。答：關于同一組變量的臨界區(qū)域是不能并發(fā)執(zhí)行的代碼，臨界區(qū)越大，并發(fā)性越差，因而編寫并發(fā)程序應盡量縮小臨界區(qū)域范圍。

8．設CR1是關于一組共享變量SV1的臨界區(qū)域，CR2是關于另外一組共享變量SV2的臨界區(qū)域，當進程P1進入CR1時，進程P2是否可以進入CR2?為什么?答：可以。因為互斥是在變量級別上的，多個進程同時進入關于不同變量的臨界區(qū)不會引起與時間有關的錯誤。

9．Lamport面包店互斥算法是否會出現(xiàn)餓死情況?不會，該算法是公平的。假定系統(tǒng)中共有n個進程，每個想要進入臨界區(qū)域的進程(線程)在最壞的情況下需要等待其它n-1個進程進入并離開臨界區(qū)域之后即可獲得進入臨界區(qū)域的機會，因而存在(忙式)等待的上界。

10．試用信號燈和PV操作實現(xiàn)臨界區(qū)語句:region<共享變量>do<語句>變量類型<共享變量>答：semaphores=1;P(s);<語句>V(s);

11.由V操作喚醒的進程是否一定能夠直接進入運行狀態(tài)?舉例說明之。答：否。一般來說，喚醒是將進程狀態(tài)由等待狀態(tài)變成就緒狀態(tài)，而就緒進程何時獲得處理機則是由系統(tǒng)的處理機調度策略確定的。如果采用搶占式優(yōu)先級調度算法，并且被喚醒的進程是當前系統(tǒng)中優(yōu)先級最高的進程，那么該進程將被調度執(zhí)行，其狀態(tài)變成運行態(tài)。如果該進程不是系統(tǒng)中優(yōu)先級最高的進程或系統(tǒng)采用其它調度算法，那么該進程不會被調度執(zhí)行，其狀態(tài)將維持在就緒態(tài)。

12.設S1和S2為兩個信號燈變量，下列八組P、V操作哪些可以同時進行?哪些不能同時進行?為什么?(1)P(S1)，P(S2)(2)P(S1)，V(S2)(3)V(S1)，P(S2)(4)V(S1)，V(S2)(5)P(S1)，P(S1)(6)P(S2)，V(S2)(7)V(S1)，P(S1)(8)V(S2)，V(S2)答：能同時進行的包括：(1)、(2)、(3)、(4)。這些操作涉及不同信號燈變量，屬于關于不同組共享變量的臨界區(qū)。不能同時進行的包括：(5)、(6)、(7)、(8)。這些操作涉及相同的信號燈變量，屬于關于同一組共享變量的臨界區(qū)。

13.對于生產者—消費者問題，假設緩沖區(qū)是無界的，試用信號燈與PV操作給出解法。答：由于是無界緩沖區(qū)，所以生產者不會因得不到緩沖區(qū)而被阻塞，不需要對空緩沖區(qū)進行管理，可以去掉在有界緩沖區(qū)中用來管理空緩沖區(qū)的信號量及其PV操作。semaphoremutex_in=1;semaphoremutex_out=1;semaphoreempty=0;intin=0，out=0;

生產者活動：while(1){producenextproduct;P(mutex_in);addtheproducttobuffer[in];in++;v(mutex_in);V(empty);}消費者活動：while(1){P(empty);P(mutex_out);taketheproductfrombuffer[out];out++;V(mutex_out);}

14.設有一個可以裝A、B兩種物品的倉庫，其容量無限大，但要求倉庫中A、B兩種物品的數量滿足下述不等式:-M≤A物品數量－B物品數量≤N其中M和N為正整數。試用信號燈和PV操作描述A、B兩種物品的入庫過程。答：已知條件-M≤A物品數量－B物品數量≤N可以拆成兩個不等式，即A物品數量－B物品數量≤N，B物品數量－A物品數量≤M。這兩個不等式的含義是：倉庫中A物品可以比B物品多，但不能超過N個；Ｂ物品可以比A物品多，但不能超過M個。

semaphorea=n;semaphoreb=m;voidmain(){createprocess(A,…);createprocess(B,…);}A物品入庫：voidA(){while(1){P(a);A物品入庫;V(b);}}B物品入庫：voidB(){while(1){P(b);B物品入庫;V(a);}}

15.試用信號燈與PV操作實現(xiàn)司機與售票員之間的同步問題。設公共汽車上有一個司機和一個售票員，其活動如下圖所示。

為了安全起見，顯然要求:(1)關車門后方能啟動車輛；(2)到站停車后方能開車門。亦即“啟動車輛”這一活動應當在“關車門”這一活動之后，“開車門”這一活動應當在“到站停車”這一活動之后。解：如果進程P2尚未推進到②處時，進程P1已經推進到①處，則P1應等待直到P2推進到②處為止；同樣，如果進程P1尚未推進到③處時，進程P2已經推進到④處，則P2應等待直到P1推進到③處為止。如果進程P1在①處發(fā)生了等待，則當進程P2執(zhí)行到②處時應將P1喚醒；同樣，如果進程P2在④處發(fā)生了等待，則當進程P2執(zhí)行到③處時應將P1喚醒。用信號量和P、V操作解決這一問題，需要定義兩個信號量，一個信號量start表示是否允許司機啟動車輛，另一個信號量open表示是否允許售票員開車門。初始狀態(tài)是車停在始發(fā)站，車門開著，等待乘客上車。因此，兩個信號量的初值都是0。

semaphorestart=0;semaphoreopen=0;

司機的活動:P1:do{P(start);啟動車輛;正常行車;到站停車;V(open);}while(1);售票員的活動:P2:do{關車門;V(start);售票;P(open);開車門;}while(1);

16.設有A、B、C三組進程，它們互斥地使用某一獨占型資源R，使用前申請，使用后釋放。資源分配原則如下:(1)當只有一組申請進程時，該組申請進程依次獲得R；(2)當有兩組申請進程時，各組申請進程交替獲得R，組內申請進程依次獲得R；(3)當有三組申請進程時，各組申請進程輪流獲得R，組內申請進程依次獲得R。試用信號燈和PV操作分別給出各組進程的申請活動程序段和釋放活動程序段。解：intfree=1;//設備狀態(tài)標志semaphoremutex=1;semaphoreqa=qb=qc=0;//各組等待隊列intcounta=countb=countc=0;//等待隊列長度

A組申請：P(mutex);if(free==1){free=0;V(mutex);}else{counta++;V(mutex);P(qa);}A組釋放：P(mutex);if(countb>0){countb--;V(qb);}else{if(countc>0){countc--;V(qc);}else{if(counta>0){counta--V(qa);}else{free=1;}}}}A組進程活動可以給出B組和C組進程活動。

17.設自行車生產線上有一只箱子，其中有N個位置(N≥3)，每個位置可存放一個車架或一個車輪;又設有三個工人，其活動分別為:工人1活動：do{加工一個車架;車架放入箱中;}while(1)工人2活動：do{加工一個車輪;車輪放入箱中;}while(1)工人3活動：do{箱中取一車架;箱中取二車輪;組裝為一臺車;}while(1)試分別用信號燈與PV操作、管程、會合實現(xiàn)三個工人的合作，要求解中不含死鎖。解：用信號燈與PV操作實現(xiàn)三個工人的合作，管程與會合解法可仿照給出。首先不考慮死鎖問題，工人1與工人3、工人2與工人3構成生產者與消費者關系，這兩對生產/消費關系通過共同的緩沖區(qū)相聯(lián)系。從資源的角度來看，箱子中的空位置相當于工人1和工人2的資源，而車架和車輪相當于工人3的資源。定義三個信號燈如下：semaphoreempty=N;//空位置semaphorewheel=0;//車輪semaphoreframe=0;//車架三位工人的活動分別為：工人1活動：do{加工一個車架;P(empty);車架放入箱中;V(frame);}while(1)工人2活動：do{加工一個車輪;P(empty);車輪放入箱中;V(wheel);}while(1)工人3活動：do{P(frame);箱中取一車架;V(empty);P(wheel);P(wheel);箱中取二車輪;V(empty);V(empty);組裝為一臺車;}while(1)分析上述解法易見，當工人1推進速度較快時，箱中空位置可能完全被車架占滿或只留有一個存放車輪的位置，而當此時工人3同時取2個車輪時將無法得到，而工人2又無法將新加工的車輪放入箱中；當工人2推進速度較快時，箱中空位置可能完全被車輪占滿，而當此時工人3取車架時將無法得到，而工人1又無法將新加工的車架放入箱中。上述兩種情況都意味著死鎖。為防止死鎖的發(fā)生，箱中車架的數量不可超過N-2，車輪的數量不可超過N-1，這些限制可以用兩個信號燈來表達。semaphores1=N-2;semaphores2=N-1;如此，可以給出不含死鎖的完整解法如下：工人1活動：do{加工一個車架;P(s1);P(empty);車架放入箱中;V(frame);}while(1)工人2活動：do{加工一個車輪;P(s2);P(empty);車輪放入箱中;V(wheel);}while(1)工人3活動：do{P(frame);箱中取一車架;V(empty);V(s1);P(wheel);P(wheel);箱中取二車輪;V(empty);V(empty);V(s2);V(s2);組裝為一臺車;}while(1)詳細描述還應考慮對箱子單元的描述以及訪問互斥問題。建議車架放在箱子的一端，車輪放在箱子的另一端，車架與車輪都采用后進先出的管理方式。

18.一座小橋(最多只能承重兩個人)橫跨南北兩岸，任意時刻同一方向只允許一人過橋，南側橋段和北側橋段較窄只能通過一人，橋中央一處寬敞，允許兩個人通過或歇息。試用信號燈和PV操作寫出南、北兩岸過橋的同步算法。解：橋上可能沒有人，也可能有一人，也可能有兩人。(a)兩人同時過橋(b)兩人都到中間(c)南(北)來者到北(南)段共需要三個信號量，load用來控制橋上人數，初值為2，表示橋上最多有2人；north用來控制北段橋的使用，初值為1，用于對北段橋互斥；south用來控制南段橋的使用，初值為1，用于對南段橋互斥。semaphoreload=2;semaphorenorth=1;semaphoresouth=1;

tosouth(){P(load);P(north);過北段橋;到橋中間;V(north);P(south);過南段橋;到達南岸V(south);V(load);}tonorth(){P(load);P(south);過南段橋;到橋中間V(south);P(north);過北段橋;到達北岸V(north);V(load);}

19.某寺廟，有小和尚、老和尚若干．廟內有一水缸，由小和尚提水入缸，供老和尚飲用。水缸可容納30桶水，每次入水、取水僅為1桶，不可同時進行。水取自同一井中，水井徑窄，每次只能容納一個水桶取水。設水桶個數為5個，試用信號燈和PV操作給出老和尚和小和尚的活動。semaphoreempty=30;//表示缸中目前還能裝多少桶水，初始時能裝30桶水semaphorefull=0;//表示缸中有多少桶水，初始時缸中沒有水semaphorebuckets=5;//表示有多少只空桶可用，初始時有5只桶可用semaphoremutex_well=1;//用于實現(xiàn)對井的互斥操作semaphoremutex_bigjar=1;//用于實現(xiàn)對缸的互斥操作

young_monk(){while(1){P(empty);P(buckets);gotothewell;P(mutex_well);getwater;V(mutex_well);gotothetemple;P(mutex_bigjar);purethewaterintothebigjar;V(mutex_bigjar);V(buckets);V(full);}}old_monk(){while(){P(full);P(buckets);P(mutex_bigjar);getwater;V(mutex_bigjar);drinkwater;V(buckets);V(empty);}}

20.設系統(tǒng)中有5臺類型相同的打印機，依次編號為1～5。又設系統(tǒng)中有n個使用打印機的進程，使用前申請，使用后釋放。每個進程有一個進程標識，用于區(qū)別不同的進程。每個進程還有一個優(yōu)先數，不同進程的優(yōu)先數各異。當有多個進程同時申請時，按照進程優(yōu)先數由高到低的次序實施分配。試用信號燈和PV操作實現(xiàn)對于打印機資源的管理，即要求編寫如下函數和過程:(1)函數require(pid，pri):申請一臺打印機。參數pid為進程標識，其值為1到n的整數;pri為進程優(yōu)先數，其值為正整數;函數返回值為所申請到打印機的編號，其值為1到5的整數;(2)過程return(prnt):釋放一臺打印機。參數prnt為所釋放打印機的編號，其值為1到5的整數。解：#defineN5boolflag[N+1];//flag[0]表示可用打印機數,//flag[i]表示第i號打印機的狀態(tài)（1<=i<=N），0表示占用，1表示空閑PCB*queue=NULL;//進程阻塞隊列semaphoremutex_flag=1;//用于對flag數組的互斥操作semaphoremutex_queue=1;//用于對阻塞隊列的互斥操作

process(inti,intpriority){intprint;print=require(i,priority);useprint;return(print);}

intrequire(intpid,intpriority){P(mutex_flag);if(flag[0]>0){flag[0]--;for(inti=1;i<N+1;i++)if(flag[i]==1){flag[i]=0;break;}V(mutex_flag);returni;}else{V(mutex_flag);p(mutex_queue);將進程pid按其優(yōu)先數插入到等待隊列queue中；V(mutex_queue);}}

return(intprint){P(mutex_flag);if(queue==NULL){flag[0]++;flag[print]=1;V(mutex_flag);}else{V(mutex_flag);p(mutex_queue);將print分配給queue隊首進程；queue下移；V(mutex_queue);}}

21.試用管程實現(xiàn)單一資源的管理。解：TYPEsingle_resource=MONITOR;Varstate:(free,used);//資源狀態(tài)q:condition;//等待隊列definerequire,release;PROCEDURErequire;BEGINIFstate=usedTHENwait(q);state:=used;END;PROCEDURErelease;BEGINstate:=free;signal(q);END;BEGINstate:=freeEND;

22.雖然管程是互斥進入的，但管程中定義的外部子程序必須是可再入的，試說明原因。答：管程互斥是在變量級別的，同一管程類型可以有多個實例，而管程內部子程序只在管程類型定義時生成一套代碼，為保障對不同管程變量的操作具有相同語義，管程外部子程序必須是可再入的。

23.編寫一個管程，使得調用進程能夠等待若干指定時間單位(ticks)．可以假定有一個硬件實時鐘，每隔一個tick時間單位調用該管程一次。解：兩個外部過程：sleep用于進程等待指定時間，tick用于時鐘中斷記數和喚醒等待進程。TYPEsleep_interval=MONITOR;Varcount:integer;//tick計數q:condition;//等待隊列definesleep,tick;PROCEDUREsleep(interval:integer);BEGINcount:=intervalwait(q);END;PROCEDUREtick;BEGINcount:=count-1;IFcount=0THENsignal(q);END;BEGINEND;

24.管程與會合這兩種同步機制之間的主要差別何在?答：管程與會合都屬于集中式結構化同步機制，但二者的實現(xiàn)機理完全不同。管程是被動性語言成分，管程本身不能占有處理機，管程外部子程序是由調用進程占有處理機執(zhí)行的。會合是主動性語言成分，一個任務調用另一任務中的入口時，入口代碼是由被調用任務自己占有處理機執(zhí)行的。

25.試用會合給出讀寫問題的解法，要求寫者優(yōu)先．解：定義一個任務，包含如下四個入口：start_read,finish_read,start_write,finish_write。該問題的關鍵是：strat_write的入口條件不應考慮當前讀者情況，當會合發(fā)生后再判斷當前是否有讀者，并與其finish_read會合。這里顯然需要accept語句的嵌套。taskreaders_and_writersisstart_read;finish_read;start_write;finish_write;endreaders_and_writers;taskbodyreaders_and_writersisread_count,write_count:integer;read_count:=0;write_count:=0;loopselectwhenwrite_count=0=>acceptstart_readdoread_count:=read_count+1;endstart_readorwhenread_count>0=>acceptfinish_readdoread_count:=read_count-1;endfinish_read;orwhenwrite_count=0=>//也許當前有讀者acceptstart_writedowhileread_count>0do//等待讀者讀完acceptfinish_readdoread_count:=read_count-1endfinish_readendwhilewrite_count:=write_count+1;endstart_writeorwhenwrite_count>0=>acceptfinish_writedowrite_count:=write_count-1;endfinish_writeendselect;endloop;endreaders_and_writers;

26.關于讀者/寫者問題,有人給出如下改進解法:semaphorer_w_w,mutex,s;(初值均為1)intcount;(初值為0)讀者活動：P(s);P(mutex);count++;if(count==1)P(r_w_w);V(mutex);V(s);{讀操作}P(mutex);count--;If(count==0)V(r_w_w);V(mutex);

寫者活動：P(s);P(r_w_w);{寫操作}V(r_w_w);V(s);

分析上述改進算法的調度效果。答：由于s以及讀者和寫者對s的操作，讀者和寫者都不會無限等待，因而算法不會出現(xiàn)餓死現(xiàn)象，是一個公平的解法五、死鎖習題及解答:1．下面關于死鎖問題的敘述哪些是正確的，哪些是錯誤的，說明原因。(1)參與死鎖的所有進程都占有資源；(2)參與死鎖的所有進程中至少有兩個進程占有資源；(3)死鎖只發(fā)生在無關進程之間；(4)死鎖可發(fā)生在任意進程之間。答：說法（1）是錯誤的，應該是參與死鎖的所有進程都等待資源。如下圖所示，參與進程p1、p2、p3、p4，盡管p3、p4不占有資源，但也卷入死鎖。說法(2)正確。參與死鎖的進程至少有兩個，設為p1,p2，p1占有資源r1而等待資源r2，p2占有資源r2而等待資源r1。說法(3)錯誤。死鎖也可能發(fā)生在相關進程之間，如p1和p2也可能是相關進程。說法(4)正確，死鎖既可能發(fā)生在相關進程之間，也可能發(fā)生在無關進程之間。即死鎖可發(fā)生在任意進程之間。

2．試證明當每個資源類中僅有一個資源實例時，資源分配圖中的環(huán)路是死鎖的充要條件。證明：已知必要條件成立，即發(fā)生死鎖必存在環(huán)路，下面只需證明充分條件，即在每類資源僅有一個實例的前提下，環(huán)路意味著死鎖。假定環(huán)路上共有k個進程(k32)，設這k個進程為p1,p2,…,pk。p1等待p2占有的資源r1，p2等待p３占有的資源r２，…，pk等待p１占有的資源rk。顯然，這k個資源類中的所有資源實例均被環(huán)路上的進程所占有，環(huán)路外的進程有關資源的任何釋放動作必不涉及這k類資源，因而無法使環(huán)路上的等待進程解除等待狀態(tài)，因而這k個進程將無限期地等待下去，即發(fā)生死鎖。證畢。

3．什么叫饑餓？什么叫餓死？什么叫活鎖？舉例說明之．答：在一個動態(tài)系統(tǒng)中，資源請求與釋放是經常性發(fā)生的進程行為。對于每類系統(tǒng)資源，操作系統(tǒng)需要確定一個分配策略，當多個進程同時申請某類資源時，由分配策略確定資源分配給進程的次序。資源分配策略可能是公平的(fair)，能保證請求者在有限的時間內獲得所需資源；資源分配策略也可能是不公平的(unfair)，即不能保證等待時間上界的存在。在后一種情況下，即使系統(tǒng)沒有發(fā)生死鎖，某些進程也可能會長時間等待。當等待時間給進程推進和響應帶來明顯影響時，稱發(fā)生了進程饑餓(starvation)，當饑餓到一定程度的進程所賦予的任務即使完成也不再具有實際意義時稱該進程被餓死(starvetodeath)。

考慮一臺打印機分配的例子，當有多個進程需要打印文件時，系統(tǒng)按照短文件優(yōu)先的策略排序，該策略具有平均等待時間短的優(yōu)點，似乎非常合理，但當短文件打印任務源源不斷時，長文件的打印任務將被無限期地推遲，導致饑餓以至餓死。

與饑餓相關的另外一個概念稱為活鎖(livelock)，在忙式等待條件下發(fā)生的饑餓，稱為活鎖。例如不公平的互斥算法。

4．死鎖與餓死之間有何相同點和不同點?答：餓死與死鎖有一定聯(lián)系：二者都是由于競爭資源而引起的，但又有明顯差別，主要表現(xiàn)在如下幾個方面：(1)從進程狀態(tài)考慮，死鎖進程都處于等待狀態(tài)，忙式等待(處于運行或就緒狀態(tài))的進程并非處于等待狀態(tài)，但卻可能被餓死；(2)死鎖進程等待永遠不會被釋放的資源，餓死進程等待會被釋放但卻不會分配給自己的資源，表現(xiàn)為等待時限沒有上界(排隊等待或忙式等待)；(3)死鎖一定發(fā)生了循環(huán)等待，而餓死則不然。這也表明通過資源分配圖可以檢測死鎖存在與否，但卻不能檢測是否有進程餓死；(4)死鎖一定涉及多個進程，而饑餓或被餓死的進程可能只有一個。饑餓和餓死與資源分配策略(policy)有關，因而防止饑餓與餓死可從公平性考慮，確保所有進程不被忽視，如FCFS分配算法。

5．何謂銀行家算法的保守性?舉例說明之。答：銀行家算法的保守性是指銀行家算法只給出了進程需要資源的最大量，而所需資源的具體申請和釋放順序仍是未知的，因而銀行家只能往最壞處設想．考慮資源集合R={A(1),B(1)}，進程集合P={p1,p2}，已知進程p1和進程p2的活動序列分別為：p1：a,b,,;p2：b,,b,a,,。顯然p1和p2的資源最大需求量均為A(1)，B(1)。假定某時刻系統(tǒng)狀態(tài)如下：ClaimAllocationNeedAvailableABABABABp1:11100101p2:110011即此時p1的a被系統(tǒng)接受。其后系統(tǒng)接收到的命令有兩種可能，一是p1的請求b，二是p2的請求b。假定為p2的請求b，因Request[2]=(0,1)￡Need[2]=(1,1)，故該請求是合法的。又Request[2]=(0,1)￡Available=(0,1)，故該請求系統(tǒng)當前能夠滿足。假定分配，系統(tǒng)狀態(tài)變化如下：ClaimAllocationNeedAvailableABABABABp1:11100100p2:110110運行安全性檢測算法發(fā)現(xiàn)此時系統(tǒng)處于不安全狀態(tài)，因而取消分配，p2等待。實際上如果真正實施分配系統(tǒng)并不會進入死鎖狀態(tài)，因為分配后按照p2(),p1(b),p1(),p1(),p2(b),p2(a),p2(),p2()的次序兩個進程可以執(zhí)行完，這是一個p1和p2交叉執(zhí)行的次序，而不是一個順序執(zhí)行的次序，銀行家算法不能判斷。

6．能否給出避免死鎖的充要性算法?為什么?答：目前關于避免死鎖的算法，如銀行家算法是充分性算法，即確保系統(tǒng)時刻處于安全狀態(tài)，這是在系統(tǒng)已知每個進程所需資源最大量的條件下可以給出的最好結果。如果系統(tǒng)不僅知道每個進程所需資源的最大量，而且知道進程有關資源的活動序列，在這個更強的條件下，則可以給出避免死鎖的充要性算法（讀者可以證明），但其復雜度是很高(NP完全)的。而且由于程序中分支和循環(huán)的存在，事先給出進程有關資源的命令序列一般是不可能的。

7．設有一個Ｔ型路口，其中A、B、C、D處各可容納一輛車，車行方向如下圖所示，試找出死鎖并用有序分配法消除之。要求資源編號合理。

AB<-E：左轉W：直行->DC

/\|S:左轉

解：(1)Ｅ方向兩臺車分別位于A和B；S方向一臺車位于C；W方向一臺車位于D。(2)S方向兩臺車分別位于B和C；E方向一臺車位于A；W方向一臺車位于D。設位置資源C、B、A、D的編號從低到高依次為1、2、3、4，管理四個位置的信號量分別為s1,s2,s3,s4，信號量的初值均為1。車輛活動如下：semaphores1=1,s2=1,s3=1,s4=1;W：直行P(s1);//按序申請P(s4);駛入D;駛入C;V(s4);駛出C;V(s1);E：左轉P(s2);駛入B;P(s3)；駛入A;V(S2)P(s4)；駛入D;V(s3)；駛出D;V(s4);S：左轉P(s1);駛入C;P(s2)；駛入B;V(S1)P(s3)；駛入A;V(s2)；駛出A;V(s3);

8．設系統(tǒng)中僅有一個資源類，其中共有M個資源實例，使用此類資源的進程個數共有N個，它們所需資源最大量總和為S，試證明發(fā)生死鎖的必要條件是S3M+N。證明：假定發(fā)生死鎖，且參與死鎖的進程個數為n(2￡n￡N)，參與死鎖的n個進程已經占有系統(tǒng)中全部M個資源實例，而還沒夠(因它們處于無限期等待狀態(tài))，每個進程至少還需要一個資源實例，因而參與死鎖進程所需要資源總量3M＋n。每個未參與死鎖進程至少需要一個資源實例(若不需要則不屬于N集合中，它們沒有參與死鎖是因為它們在得到并使用完資源后已經將其釋放)，由于共有N-n個未參與死鎖的進程，它們所需資源總量3N-n。由此可知，全部進程所需要的資源總量S3(M+n)+(N-n)=M+N。

9．在銀行家算法中，若出現(xiàn)如下資源分配情況：AllocationNeedAvailableABCDABCDABCDP0:003200121623P1:10001750P2:13542356P3:03320652P4:00140656試問：(1)當前狀態(tài)是否安全？(2)如果進程P2提出安全請求Request[2]=(1,2,2,2),系統(tǒng)能否將資源分配給它？說明原因．解：（1）當前狀態(tài)是安全狀態(tài)。運行安全性檢查算法如下：1）Work=Available；Finish=false；2）尋找滿足如下條件的i:Finish[i]==false并且Need[i]≤Work[i]；如果不存在，則轉步驟4）；3）Work=Work+Allocation[i]；Finish[i]=true；轉步驟2）4）如果對于所有i，F(xiàn)inish[i]=true，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)。令Work=Available=（1,6,2,3）運行安全性檢測算法，F(xiàn)inish[0]=false并且Need[0]=(0012)<Work,則Work=Work+Allocation[0]=（1,6,2,3）+（0,0,3,2）=（1,6,5,5）；Finish[0]=true；Finish[3]=false并且Need[3]=（0,6,5,2）<Work,則Work=Work+Allocation[3]=（1,6,5,5）+（0,3,3,2）=（1,9,8,7）；Finish[3]=true；Finish[4]=false并且Need[4=（0,6,5,6）<Work,則Work=Work+Allocation[4]=（1,9,8,7）+（0,0,1,4）=（1,9,9,11）；Finish[4]=true；Finish[1]=false并且Need[1]=（1,7,5,0）<Work,則Work=Work+Allocation[4]=（1,9,9,1）+(1,0,0,0)=(2,9,9,11)；Finish[1]=true；Finish[2]=false并且Need[2]=（2,3,5,6）<Work,則Work=Work+Allocation[4]=（2,9,9,11）+（1,3,5,4）=（3,12,14,15）；Finish[2]=true；可以找到一個安全進程序列<p0,p3，p4，p1,p2>，它使Finish[i]=true，對于所有0≤i≤4，因而可以斷言系統(tǒng)當前處于安全狀態(tài)．（2）運行銀行家算法，由于Request[2]=（1,2,2,2）￡Need[2]=（2,3,5,6），因而請求合法。進一步，Request[2]=（1,2,2,2）￡Available=（1,6,2,3），故該請求是可以滿足的。假設將資源分配給p2，則系統(tǒng)狀態(tài)變?yōu)?AllocationNeedAvailableABCDABCDABCDP0:003200120401P1:10001750P2:25761134P3:03320652P4:00140656運行安全性檢測算法，Work=Available=（0,4,0,1），F(xiàn)inish[i]=false，此時所有Need[i]￡Work[i]均不成立，結果Finish[i]均為false，不存在安全進程序列，系統(tǒng)處于不安全狀態(tài)。系統(tǒng)將取消資源分配并恢復原來狀態(tài)，進程p2等待。某系統(tǒng)采用死鎖檢測手段發(fā)現(xiàn)死鎖，設系統(tǒng)中資源類集合為{A，B，C}，資源類A中共有8個實例，資源類B中共有6個實例，資源類C中共有5個實例．又設系統(tǒng)中進程集合為{p1,p2,p3,p4,p5,p6}，某時刻系統(tǒng)狀態(tài)如下：AllocationRequestAvailableABCABCABCp1:100000221p2:321000p3:012202p4:000000p5:210031p6:001000在上述狀態(tài)下系統(tǒng)依次接受如下請求：Request[1]=(1,0,0)；Request[2]=(2,1,0)；Request[4]=(0,0,2)。給出系統(tǒng)狀態(tài)變化情況，并說明沒有死鎖。在由(1)所確定的狀態(tài)下系統(tǒng)接收如下請求：Request[1]=(0,3,1)，說明此時已發(fā)生死鎖，并找出參與死鎖的進程。解：（1）①如果系統(tǒng)只是接受請求，但是沒有分配資源給進程，那么系統(tǒng)狀態(tài)變?yōu)椋篈llocationRequestAvailableABCABCABCp1:100100221p2:321210p3:012202p4:000002p5:210031p6:001000在該狀態(tài)下運行死鎖檢測算法，可以找到一個進程序列<p4,p1,p2,p3,p5,p6>，它使Finish[i]=true，對于所有1≤i≤6，因而可以斷言系統(tǒng)當前沒有進入死鎖狀態(tài)。②如果系統(tǒng)接受請求后，將一個A分配給進程p1，則系統(tǒng)狀態(tài)變?yōu)椋篈llocationRequestAvailableABCABCABCp1:200000121p2:321210p3:012202p4:000002p5:210031p6:001000在該狀態(tài)下運行死鎖檢測算法，可以找到一個進程序列<p4,p1,p2,p3,p5,p6>，它使Finish[i]=true，對于所有1≤i≤6，因而可以斷言系統(tǒng)當前沒有進入死鎖狀態(tài)。（2）設在（1）的①狀態(tài)下系統(tǒng)接收如下請求：Request[1]=(0,3,1)，則系統(tǒng)狀態(tài)變?yōu)椋篈llocationRequestAvailableABCABCA