1、第二章一、思考題1. 什么是PSW，它有何作用？psw:操作系統將程序運行時的一組動態信息會聚在一起，稱為程序的狀態字 作用：實現程序狀態的保護和恢復3.為什么要把機器指令分成特權指令和非特權指令？應用程序在執行有關資源管理的機制指令時易于導致系統混亂，造成系統或用戶信息被破壞，因此在多道程序設計環境中，從資源管理和控制程序執行的角度出發，必須把指令系統中的指令分成這兩類。4.試分別從中斷事件的性質、來源和實現角度對其進行分類從中斷事件的性質和激活的手段來說，可以分成兩類： （1）強迫性中斷事件強迫性中斷事件不是正在運行的程序所期待的，而是由于某種事故或外部請求信息所引起的，分為：機器故障中斷

2、事件。程序性中斷事件。外部中斷事件。輸入輸出中斷事件。（2）自愿性中斷事件自愿性中斷事件是正在運行的程序所期待的事件。按事件來源和實現手段分類：（1） 硬中斷；硬中斷分為外中斷（中斷、異步中斷）和內中斷（異常、同步中斷）；（2） 軟中斷；軟中斷分為信號和軟件中斷。9.什么是系統調用？試述API、庫函數及系統調用間的關系。敘述系統調用執行流程。由操作系統實現的所有系統調用所構成的集合即程序接口或應用編程接口(Application Programming Interface，API)。系統調用是一種API，是應用程序同系統之間的接口。庫函數是語言本身的一部分，可以調用多個系統調用；系統調用（函數

3、）是內核提供給應用程序的接口，屬于系統的一部分，可以認為是某種內核的庫函數；操作系統API是有系統調用（函數）的集合（也就是將許多的系統調用封裝在了一起）。一是編寫系統調用服務例程；二是設計系統調用入口地址表，每個入口地址都指向一個系統調用的服務例程，有的還包括系統調用自帶的參數個數；三是陷阱處理機制，需要開辟現場保護區，以保存發生系統調用時應用程序的處理器現場。應用程序執行系統調用，產生中斷指向內核態，進入陷阱處理程序，它將按功能查詢入口地址表，并轉至對應服務例程執行，完成后退出中斷，返回應用程序斷點繼續運行。14.簡述Linux的快中斷和慢中斷快中斷：快中斷處理僅要保存被常規C函數修改的寄

4、存器；中斷處理時會屏蔽所有其他中斷；中斷處理完畢后，通常恢復現場返回被中斷的進程繼續執行(是非搶先式調度)。慢中斷：處理慢中斷前需保存所有寄存器的內容，中斷處理時，不屏蔽其他中斷信號，慢中斷處理完畢后，通常不立即返回被中斷的進程，而是進入調度程序重新調度，調度結果未必是被中斷的進程運行(是搶先式調度)。17.討論Linux系統的tasklet、work queue和softirq任務延遲處理進制。（1）tasklet：能更好支持SMP，它基于軟中斷來實現，但比軟中斷接口簡單，鎖保護要求低；softirq保留給執行頻率及時間要求特高的下半部分使用(如網絡和SCSI)，多數場合下可使用taskle

5、t。使用tasklet的步驟：聲明 、編程、調度 。 BH全局串行處理，不適應SMP環境，而不同tasklet可同時運行于不同CPU上，當然，系統保證相同tasklet不會同時在不同CPU上運行，在這種情形下，tasklet就不需要是可重入的。在新版Linux中，tasklet是建議的異步任務延遲執行機制。（2）work queue：Linux 2.5內核引入-工作隊列，它把一個任務延遲，并交給內核線程去完成，且該任務總是在進程上下文中執行，通過工作隊列執行的代碼能占盡進程上下文的優勢，最重要的是工作隊列允許重新調度及阻塞。默認的工作者線程:event/n如果延遲執行的任務需要阻塞，需要獲取信

6、號量或需要獲得大量主存時，那么，可選擇工作隊列，否則可使用tasklet或softirq。(3) Sorfirq：（軟中斷）是一種軟中斷機制，亦即是一種信號機制，中斷處理程序在其返回前標記下半部分，讓其稍后執行；它又是一個框架，納入了tasklet及為網絡操作專門設計的軟中斷。18.什么是進程？計算機系統中為什么要引入進程？（1）進程定義：進程是可并發執行的程序在某個數據集合上的一次計算活動，也是操作系統進行資源分配和保護的基本單位（2）刻畫系統的動態性，發揮系統的并發性，提高資源利用率。程序是并發執行的，即不是連續而是走走停停的。程序的并發執行引起資源共享和競爭問題，執行的程序不再處在封閉環

7、境中。“程序”自身只是計算任務的指令和數據的描述，是靜態概念無法刻畫程序的并發特性，系統需要尋找一個能描述程序動態執行過程的概念，這就是進程。它能解決系統的“共享性”，正確描述程序的執行狀態。程序與程序的執行不再一一對應19.進程有哪些主要屬性？試解釋之共享性：同一程序同時運行于不同數據集合上時構成不同進程，即多個不同進程可執行相同的程序，所以進程和程序不是一一對應的。動態性：進程是程序在數據集合上的一次執行過程，是動態概念，同時它有生命周期，由創建而產生、由調度而執行、由事件而等待、由撤銷而消亡；而程序是一組有序指令序列，是靜態概念，所以程序作為系統中的一種資源是永遠存在的獨立性：每個進程是

8、操作系統中的一個獨立實體，有自己的虛存空間，程序計數器和內部狀態；制約性：進程因共享進程資源或協同工作產生相互制約關系，造成進程執行速度的不可預測，必須對進程的執行次序或相對執行速度加以協調；并發性：多個進程的執行在時間上可以重疊，在單處理器系統中可并發執行；在多處理器環境中可并發執行。因此，并發的執行是可被打斷的，或者說，進程執行完一條指令后在執行下一條指令前可能被迫讓出處理器，由其它若干個進程執行若干條指令后才能再次獲得處理器執行。20.進程最基本的狀態有哪些？哪些事件可能引起不同狀態間的轉換？運行態、就緒態、等待態（1）運行態-等待態：運行進程等待使用某種資源或者某事件發生（2）等待態-

9、就緒態：所需資源得到滿足或某事件已經完成（3）運行態-就緒態：運行時間片到時或出現更高優先級的進程，當前進程被迫讓出處理器。（4）就緒態-運行態：當CPU空閑時，調度程序選中一個就緒進行執行21.五態模型的進程中，新建態和終止態的主要作用是什么？新建態：對應于進程被創建時的狀態，進程尚未進入就緒隊列，對于進程管理非常有用。終止態：進程完成任務到達正常結束點或者因錯誤而終止，或被操作系統及有終止權的進程時所處的狀態。進入終止態程序不再執行，等待操作系統進行善后處理。24.什么是進程的掛起狀態？列出掛起進程的主要特征。（1）為了讓某些進程暫時不參與低級調度，釋放它占有的資源，將其置于磁盤對換區中，

10、以平滑系統負荷的目的而需引入掛起態；（2）特征：該進程不能立即被執行。掛起進程可能會等待事件，但所等待事件是獨立于掛起條件的，事件結束并不能導致進程具備執行條件。進程進入掛起狀態是由于操作系統、父進程或進程本身阻止它的運行。結束進程掛起狀態的命令只能通過操作系統或父進程發出25.試述組成進程的基本要素，并說明其作用。控制塊：存儲進程的標志信息，現場信息和控制信息；程序塊：規定進程的一次運行所應完成的功能；核心塊：用來保護中斷/異常現場，保存函數調用的參數和返回地址；數據塊：存放各種私有數據26.何謂進程控制塊（PCB）？它包含哪些基本信息？（1）進程控制塊P C B ，是操作系統用于記錄和刻劃

11、進程狀態及有關信息的數據結構。也是操作系統掌握進程的唯一資料結構，它包括進程執行時的情況，以及進程讓出處理器后所處的狀態、斷點等信息。 （2）進程控制塊包含三類信息 標識信息 現場信息 控制信息28.請列舉組織進程隊列的各種方法通用隊列組織方式： 線性方式 鏈接方式 索引方式30.什么是進程上下文？簡述其主要內容操作系統中把進程物理實體和支持進程運行的環境合稱為進程上下文。當系統調度新進程占有處理器時，新老進程隨之發生上下文切換。進程的運行被認為是上下文中執行。 進程上下文組成用戶級上下文系統級上下文寄存器上下文31.什么是進程切換？試述進程切換的主要步驟（1）進程切換是讓處于運行態的進程中斷

12、運行，讓出處理器，這時要做一次進程上下文切換、即保存老進程狀態而裝入被保護了的新進程的狀態，以便新進程運行（2）保存被中斷進程的處理器現場信息修改被中斷進程的進程控制塊有關信息，如進程狀態等把被中斷進程的PCB加入有關隊列選擇下一個占有處理器運行的進程修改被選中進程的PCB的有關信息根據被選中進程設置操作系統用到的地址轉換和存儲保護信息根據被選中進程恢復處理器現場32.什么是模式切換？它與進程切換之間有何區別？模式切換即CPU模式切換，是從用戶態到核心態或者核心態到用戶態的轉換是CPU模式切換，此時仍然在同一個進程中運行。模式切換不同于進程切換，它不一定會引起進程狀態的轉換，也不一定會引起進程

13、切換，在完成系統調度服務或中斷處理之后，可通過逆向模式來恢復被中斷進程的運行。35.在操作系統引入進程概念后，為什么還有引入線程的概念？操作系統中再引入線程，則是為了減少程序并發執行時所付出的時空開銷，使得并發粒度更細、并發性更好。38.試從調度、并發性、擁有資源和系統開銷等四個方面對傳統進程和多線程進程進行比較。40.試對下列系統任務進行比較：（1）創建一個線程和創建一個進程（2）兩個進程間通信與同一進程中的兩個線程間通信 （3）同一進程中的兩個線程的上下文切換和不同進程中兩個線程的上下文切換。43.列舉線程的組織方式和應用場合。答：線程組織方式：（1）調度員/工作者方式（2）組模式（3）流

14、水線模式應用場合：（1）前臺和后臺工作（2）C/S應用模式（3）異步處理（4）加快執行速度（5）設計用戶接口45.試分析Linux系統的進程和線程。進程描述符task_struct中包含：進程標識、鏈接信息、調度信息、文件信息、虛存空間信息、信號處理信息等。Linux中認為線程就是共享地址空間及其他資源的進程，故并沒有單獨為線程定義數據結構，有一套在用戶模式下運行的線程庫-pthread，但每個線程都擁有惟一隸屬于自己的task_struct48.處理器調度分為哪幾種類型？簡述各種調度的主要任務。答：（1）高級調度：在多道處理操作系統中，從輸入系統的一批作業中按照預定的調度策略挑選若干個作業進

15、入主存，為其分配所需資源，并創建作業的相應用戶進程后便完成啟動階段的高級調度任務；（2）中級調度：根據主存資源決定主存中所能容納的進程數目，并根據進程的當前狀態來決定輔助存儲器和主存中的進程的對換；（3）低級調度：根據某種原則決定就緒隊列中的哪個進程或內核級線程獲得處理器，并將處理器讓出給它使用。49.試述衡量一個處理器調度算法優劣的主要任務。根據調度機制 的三個邏輯功能程序模塊組成來評判：（1）隊列管理程序（2）上下文切換程序（3）分派程序52.解釋：（1）作業周轉時間；（2）作業帶權周轉時間；（3）相應時間；（4）吞吐率。答：（1）作業周轉時間：批處理用戶從系統提交作業開始，到作業完成為止

16、的時間間隔；（2）作業帶權周轉時間：在操作系統中，帶權周轉時間反映作業（或進程）長短問題，帶權周轉時間越大，作業（或進程）越短；帶權周轉時間越小，作業（或進程）越長。（3）響應時間：從交互式進程提交一個請求至得到響應之間的時間間隔稱為響應時間。（4）吞吐率：單位時間CPU處理作業的個數。53.試述作業、進程、線程和程序之間的關系。進程是操作系統結構的基礎；是一個正在執行的程序；計算機中正在運行的程序實例；可以分配給處理器并由處理器執行的一個實體；由單一順序的執行顯示，一個當前狀態和一組相關的系統資源所描述的活動單元。 線程（thread, 臺灣稱 執行緒）是"進程"中某個單

17、一順序的控制流。也被稱為輕量進程（lightweight processes）。計算機科學術語，指運行中的程序的調度單位。作業：用戶在一次運算過程中，或一次事務處理中要求計算機所做的全部工作的總和。進程是在自身的虛擬地址空間正在運行的一個程序 程序運行產生進程 程序是一組靜態的指令集，不占用系統運行資源 進程是隨時都可能發生變化的，動態的。占用系統運行資源的程序 一個程序可以產生多個進程 作業嘛，是一個或多個正在執行的相關進程。一般來講當進程與作業控制相關聯時才被稱為作業55.在時間片輪轉低度調級算法中，根據哪些因素確定時間片的長短？答：進程數目、切換開銷、系統效率及響應時間等多方面因素。57

18、.為什么多級反饋隊列算法能較好地滿足各種用戶的需求？答：高級調度的主要任務是根據某種算法，把外存上處于后備隊列中的那些作業調入內存。低級調度是保存處理機的現場信息，按某種算法先取進程，再把處理器分配給進程。引入中級調度的主要目的是為了提高內存利用率和系統吞吐量。使那些暫時不能運行的進程不再占用內存資源，將它們調至外存等待，把進程狀態改為就緒駐外存狀態或掛起狀態。58.分析靜態優先數和動態優先數低級調度算法各自的優缺點。答：靜態優先級在進程或線程創建時確定，且生命周期中不再改變，可按照外部指定和內部指定方法計算靜態優先級。靜態優先級算法的實現簡單，但會產生饑餓現象，使某些低優先級進程或線程無限期

19、對的被推遲進行。動態優先級使各進程或線程優先級隨時間而改變，克服了靜態優先級的饑餓問題，等待時間足夠長的進程或線程會因其優先級不斷提高而被調度運行。62.在多級反饋隊列中，對不同的隊列分配大小不同的時間片值，其意義何在?應用題1.下列指令中，哪些只能在內核態運行？（1）讀時鐘日期 （2）訪管指令 （3）設時鐘日期 （4）加載PSW（5）置特殊寄存器 （6）改變存儲器映像圖 （7）啟動I/O指令4.在按照動態優先數調度進程的系統中，每個進程的優先數需定時重新計算。在處理器不斷在進程之間交替的情況下，重新計算進程優先數的時間從何而來？許多操作系統重新計算進程的優先數在時鐘中斷處理例程中進行，由于中

20、斷是隨機碰到哪個進程，就插入哪個進程中運行處理程序，并把處理時間記在這個進程的賬上。7. 8.10. 按照最短作業優先的算法可以使平均響應時間最短。X取值不定，按照以下情況討論： 1） x3 次序為：x，3，5，6，9 2） 3<x5 次序為：3，x，5，6，9 3） 5<x6 次序為：3，5，x，6，9 4） 6<x9 次序為：3，5，6，x，9 5） 9<x 次序為：3，5，6，9，x11.( l ) FCFS 調度算法( 2 ）優先級調度算法 ( 3 ）時間片輪轉法按次序ABCDEBCDECDEDEE 輪轉執行。12 16.20.21. A 10:00 12:40

21、 160B 10:20 10:50 30C 10:30 11:50 80D 10:50 13:00 130E 12:00 12:20 80F 11:50 1200 50平均作業周轉時間 =(160+30+80+130+80+50)/6=88.3326.(1) Job4最后一個完成(2) 各個作業的平均周轉時間為：(90+40+120+120+30)/5 = 80 各個作業的平均帶權周轉時間為：(1.8+1+2.4+6+3)/5 = 2.8432. 循環周期為4*100+400=800ms A類進程需要2*1000/100=20個時間片的執行時間，B類進程需要2*1000/400=5個時間片的執

22、行時間， A類進程的平均周轉時間為20*0.8=16s B類進程的平均周轉時間為5*0.8=4s第三章思考題：一：試述順序程序設計的特點，以及采用順序程序設計的優缺點。答：順序程序設計的特性：（1）：執行的順序性。一個程序在處理器上嚴格按序執行的，每一個操作必須在下一個操作開始之前結束。（2）：環境的封閉性。運行程序獨占全機資源，資源狀態只能由此程序本身決定和改變，也不受外界因素的影響。（3）：結果的確定性。程序在執行過程中允許出現中斷，但這種中斷不會對程序的最終結果產生影響。（4）：過程的可在現行。程序針對同一個數據結構的執行過程在下一次執行時會重現，即重復執行的程序會獲得相同的執行過程和計

23、算結果。 程序順序執行與其速度無關，即程序的最終輸出僅與初始輸入數據有關，而與時間無關。優點：為程序的編制和調試帶來很大方便。缺點：計算機系統的效率不高。二：試述并發程序設計的特點，以及采用并發程序設計的優缺點。答：特性：從宏觀上看：并發性反映一個時間段內有幾個程序都處于運行但運行尚未結束的狀態；從微觀上看：任一時刻僅有一個程序的一個操作在處理器上執行。程序的并發執行產生資源共享的需求，從而使程序失去封閉性、順序性、確定性、可在現行。優點：（1）：若為單處理系統，可以有效地利用資源，讓處理器和設備、設備和設備同時工作，充分發揮硬部件的并行工作能力；（2）：若為多處理系統，可讓進程在不同處理器上

24、物理的并行工作，加快計算速度；（3）：簡化程序設計任務，一般來說，編制并發執行的小程序進度快，容易保持正確性。可見，計算機硬部件能并行工作僅具備提高效率的可能性而并行工作的實現還需要通過并發程序設計和操作系統引入并發技術來發揮。五：解釋并發進程的無關性和交互性。答：無關性：無關的并發進程是指他們分別在不同的變量集合上操作，一個進程的執行與其他并發進程的進展無關，即一個進程不會改變另一個與其并發執行的晉城的變量。 交互性：交互的并發進程共享某些變量，一個進程的執行可能會影響其他進程的執行結果，交互的并發進程之間具有制約關系。六：并發進程的執行可能產生于時間有關的錯誤，試各舉一例來說明于時間有關錯

25、誤的兩種表現形式。 答：時間有關的錯誤有兩種形式，一是結果不唯一，二是永遠等待。 結果不唯一：飛機售票問題。 永遠等待：內存資源的管理問題。八：試述進程的互斥和同步兩個概念之間的異同。答：進程互斥是指若干進程因相互爭奪獨占性資源而產生的競爭制約關系。 進程同步是指為完成共同任務的并發進程基于某個條件來協調其活動，因為需要在某些位置上排定執行的先后順序而等待、傳遞順序或消息所產生的協調制約關系。進程互斥關系是一種特殊的進程同步關系，即逐次使用進程同步資源，也是對進程使用資源的次序的一種協調。九：什么是臨界區和臨界資源？臨界區管理的基本規則是什么？答：并發進程中與共享變量有關的程序稱為臨界區。共享

26、變量所代表的資源稱為臨界資源。臨界區管理的基本規則：（1）：一次至多只有一個進程進入臨界區內執行。（2）：如果已有近程在臨界區中，試圖進入此臨界區的其他程序應等待。（3）：進入臨界區內的進程應在有限時間內退出，以便讓等待隊列中的一個進程進入。可把臨界區的調度原則總結為三句話：互斥使用，有空讓進；忙碌要等，有限等待；擇一而入，算法可行。十二：那些硬件設施可以實現臨界區的管理，簡述其的用法。答：1：關中斷。用法：在進程進入臨界區時關中斷，進程進入臨界區時開中斷。終端被關閉后，時鐘中斷也被屏蔽，進程上下文切換都是由中斷事件引起的，這樣進程的執行再也不會被打斷，因此采用關中斷、開中斷的辦法就能確保并發

27、進程互斥的進入臨界區。 2：測試并設置指令。用法：使用硬件所提供的“測試并設置“機器指令TS（Test and Set），可把這條指令看做函數，他有布爾型參數x和返回條件碼，當TS（&x）測到x值為true時則置x為false，且根據所測試到的x值形成條件碼。 3：兌換指令。用法：為每個臨界區設置布爾型鎖變量。十三：什么是信號量？如何對其進行分類？ 答：信號量：將交通管制中的多種顏色的信號燈管理方法引入操作系統，讓多個進程通過特殊變量展開交互。一個進程在某一關鍵點上被迫停止執行直至接受到對應的特殊變量值，通過這一措施，任何復雜的進程交互要求均可達到滿足，這種特殊變量就是信號量。對其進行

28、分類：按用途分有兩種:公用信號量；私有信號量。按取值分為兩種：二值信號量；一般信號量，又稱計數信號量。十五：何謂管程？他有什么屬性？答：管程是指吧分散在各個進程之間的臨界區集中起來管理，并把共享資源用數據用數據結構抽象的表示，由于臨界區是訪問資源的代碼段，建立一個“秘書“程序管理到來的訪問。管程與進程具有同等的表達能力。管程的屬性：進程調用管程的過程是有一定的限制。 （1）：共享性。管程中的移出過程可悲所有要調用管程的進程共享。 （2）：安全性。管程的局部變量只能由此管理的過程訪問，不允許進程訪問或其他管程來直接訪問，一個管程的過程也不應該訪問非局部于他的變量。（3）：互斥性。在任意時刻共享資

29、源的進程可以訪問管程中的管理此資源的過程，但最多只有一個調用者能夠真正地進入管程，其他調用者必須等待直至管程可用。十六：試述管程中條件變量的含義和作用。答：含義：條件變量是出現在關城內的一種數據結構，且只有在管程中才能被訪問，其功能是進程可以在該條件變量上等待或被喚醒他對管程內的所有過程是全局的，只能通過兩個原語操作來控制它。十七：試比較管程與進程的不同點。答：（1）：管程定義的是公用數據結構，而進程所定義的是私有數據結構；（2）：管程把共享變量上的同步操作集中起來統一管理，而臨界區卻分散在每個進程中；（3）：管程是為解決進程共享資源的互斥而建立的，而進程是為戰友系統資源和實現系統并發性而引入

30、的；（4）：管程被欲使用共享資源的所有進程所調用，管程和調用它的進程不能明確并行工作；而進程之間能夠并行工作，并發性是其固有特性。（5）：管程可作為語言或操作系統成分，不必創建或撤銷；而進程有生命周期，由創建產生至撤銷便消失。十八：已經有信號量和pv操作可用作同步工具，為什么還要有消息傳遞機制？答：進程同步本質上是一種僅傳送信號的進程通信，通過修改信號量，進程之間可以建立聯系，相互協同運行和協同工作，但他缺乏傳遞數據的能力。在多任務系統中，可由多個進程分工協作完成同一任務，于是他們需要共享一些數據，和相互交換信息，在很多場合需要交換大批量數據可以通過通信機制來完成。二十二：試述信號通信機制及其

31、實現。答：（1）：每個進程task_struct結構中signal域專門保存接收到的信號，內核根據所發生的時間產生相應的信號并發送給接收數據。（2）：進程task_struct結構中的blocked是信號屏蔽標記，相當于中斷屏蔽寄存器。（3）：信號處理函數的入口存放在進程task_struct的sigaction數組中，利用sigction函數為進程設置信號處理函數。（4）：函數sigaction(signo,act,oldacd)為指定信號設置處理函數。（5）：函數kill(pid,sig)用來向指定的進程或進程組發送指定信號。（6）：信號檢測和相應總發生在系統空間。23：試述進程的低級通信

32、機制以及其高級通信機制。24：什么是死鎖？什么是饑餓？試舉生活中的例子加以說明。答：如果一個進程集合中的每個進程都在等待只能由此集合中的其他進程才能引發的事件，而無限期的陷入僵持的局面稱為死鎖。25：試述產生死鎖的必要條件。答：（1）：互斥條件：臨界資源是獨占資源，進程應互斥且排他的使用這些資源。（2）：占有和等待資源：進程在等待資源得不到滿足而等待時，不釋放以占有資源。（3）：不剝奪條件：又稱為不可搶占，已獲資源只能有進程自愿釋放，不允許被其他進程剝奪。（4）：循環等待條件：又稱環路條件，存在循環等待鏈，其中每個進程都在循環等代練中等待下一個進程所處有的資源，造成這組進程處于永遠等待狀態。2

33、6：列舉死鎖的各種防止策略。答：破壞條件1（互斥條件）：使資源可同時訪問而不是互斥使用，就沒有錦城湖阻塞在資源上，從而不發生死鎖。破壞條件2（戰友和等待條件）：靜態分配是指進程必須在執行之前就申請需要的全部資源，且直至所需要的資源全部得到滿足后才開始執行。破壞條件3（不剝奪條件）：剝奪調度能夠防止死鎖但只是用于內存和處理器資源。破壞條件4（循環等待條件）：采用層次分配策略，將系統中所有資源排列到不同層次中。27：何謂銀行家算法？試述其基本思想。答：銀行家算法：一種能夠避免死鎖的調度方法。基本思想：系統中所有進程放入進程集合，在安全狀態下系統受到進程的資源請求后，先把資源試探性的分配給他，然后系

34、統將剩下的可用資源和進程集合中的其他進程還需要的資源數作比較，找出剩余資源能滿足最大需求量的進程，從而保證進程運行完畢并歸還全部資源；這時吧這個進程從進程集合中刪除，歸還其所占用的所有資源，系統的剩余資源則更多；反復執行上述步驟，最后檢查進程集合，若為空則表明本次申請可行，系統處于安全狀態，可以真正實施本次分配，否則只要進程集合非空，系統便處于不安全狀態，本次資源分配暫不實施，讓申請資源的進程等待。28：解釋進程-資源分配圖，死鎖的判定法則，死鎖定理。答：設某個計算機系統中有多種資源和多個進程，每個資源類用一個方框表示，方框中的黑圓點表示此資源類中的各個資源，每個進程用一個類來表示，用有向邊表

35、示進程申請資源和資源被分配的情況。死鎖判定：（1）：如果進程-資源分配圖中無環路，此時系統沒有發生死鎖。（2）：如果進程-資源分配圖中有環路，且每個資源類中僅有一個資源，則系統中發生死鎖。此時環路是系統發生死鎖的充要條件，環路中的進程就是死鎖中的進程。（3）：如果進程-資源分配圖中有環路，且所涉及的資源類中有多個資源，則環路的存在只是系統發生死鎖的必要條件而不是充分條件，系統不一定會發生死鎖。死鎖定理即系統產生死鎖的充要條件為：當且僅當此狀態的進程-資源分配圖是不可完全簡化的。29：系統有輸入及和打印機各一臺，現有兩個進程都要使用他們，采用PV操作實現請求使用和歸還資源后還會產生死鎖嗎？說明理

36、由，若是，則給出防止死鎖的方法。答：不會產生死鎖，因為系統的輸入機和行式打印機作為臨界資源分別用兩個信號量表示，初值為1，在需要使用它們時用P操作申請，在需要歸還他們時用V操作釋放，這樣就保證了兩個進程對輸入機和行式打印機的互斥作用，可防止死鎖的產生。34：什么是競爭條件？答：多個進程并發訪問和操作同一數據且執行結果與訪問的特定順序有關，稱為競爭條件35：什么是忙式等待？答：不進入等待狀態的等待稱為忙式等待。38：試舉出系統資源分配圖有環鎖和環而不鎖的示例。答：應用題：1：有三個并發進程：R負責從輸入設備讀入信息塊，M負責對信息塊加工處理；P負責打印輸出信息塊。今提供；1） 一個緩沖區，可放置

37、K個信息塊；2） 二個緩沖區，每個可放置K個信息塊；試用信號量和P、V操作寫出三個進程正確工作的流程。答： 2：設有n個進程共享一個互斥段，如果：(1)每次只允許一個進程進入互斥段；(2)每次最多允許m個進程（mn）同時進入互斥段。試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？答：所采用的互斥信號量初值不同。 1）互斥信號量初值為1，變化范圍為-n+1，1。當沒有進程進入互斥段時，信號量值為1；當有1個進程進入互斥段但沒有進程等待進入互斥段時，信號量值為0；當有1個進程進入互斥段且有一個進程等待進入互斥段時，信號量值為-1；最多可能有n-1個進程等待進入互斥段，故此時信號

38、量的值應為-(n-1)也就是-n+1。2）互斥信號量初值為m，變化范圍為-n+m，m。當沒有進程進入互斥段時，信號量值為m；當有1個進程進入互斥段但沒有進程等待進入互斥段時，信號量值為m-1；當有m個進程進入互斥段且沒有一個進程等待進入互斥段時，信號量值為0；當有m個進程進入互斥段且有一個進程等待進入互斥段時，信號量值為-1；最多可能有n-m個進程等待進入互斥段，故此時信號量的值應為-(n-m)也就是-n+m。3：有兩個優先級相同的進程P1和P2，各自執行的操作如下，信號量S1和S2初值均為0。試問P1、P2并發執行后，x、y、z的值各為多少？P1： P2：begin beginy:=1; x

39、:=1;y:=y+3; x:=x+5;V(S1); P(S1);z:=y+1; x:=x+y;P(S2); V(S2);y:=z+y z:=z+x;end. End.5：有一閱覽室，讀者進入時必須先在一張登記表上登記，該表為每一座位列出一個表目，包括座號、姓名，讀者離開時要注銷登記信息；假如閱覽室共有100個座位。試用：1）信號量和P、V操作；2）管程，來實現用戶進程的同步算法。答：1) 使用信號量和P、V操作： 6：在一個盒子里，混裝了數量相等的黑白圍棋子。現在用自動分揀系統把黑子、白子分開，設分揀系統有二個進程P1和P2，其中P1揀白子；P2揀黑子。規定每個進程每次揀一子；當一個

40、進程在揀時，不允許另一個進程去揀；當一個進程揀了一子時，必須讓另一個進程去揀。試寫出兩進程P1和P2能并發正確執行的程序。答：實質上是兩個進程的同步問題，設信號量S1和S2分別表示可揀白子和黑子，不失一般性，若令先揀白子。coend8：設公共汽車上，司機和售票員的活動分別如下：司機的活動：啟動車輛：正常行車；到站停車。售票員的活動：關車門；售票；開車門。在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關系？用信號量和P、V操作實現它們的同步。答：在汽車行駛過程中，司機活動與售票員活動之間的同步關系為：售票員關車門后，向司機發開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票

41、員售票，到站時司機停車，售票員在車停后開門讓乘客上下車。因此，司機啟動車輛的動作必須與售票員關車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步。 應設置兩個信號量：s1、s2；s1表示是否允許司機啟動汽車(其初值為0)；s2表示是否允許售票員開門(其初值為0)。用P、V原語描述如下：9：一個快餐廳有4類職員：（1）領班：接受顧客點菜；（2）廚師：準備顧客的飯菜；（3）打包工：將做好的飯菜打包；（4）出納員：收款并提交食品。每個職員可被看作一個進程，試用一種同步機制寫出能讓四類職員正確并發運行的程序。答：S的值表示它代表的物理資源的使用狀態：S>0表示還有共享資源可

42、供使用。S=0表示共享資源正被進程使用但沒有進程等待使用資源。S<0表示資源已被分配完，還有進程等待使用資源。10：二個并發進程并發執行，其中，A、B、C、D、E是原語，試給出可能的并發執行路徑。Process P Process Qbegin beginA； C；B； D；C； end；end；16：另一個經典同步問題：吸煙者問題(patil，1971)。三個吸煙者在一個房間內，還有一個香煙供應者。為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴，供應者有豐富貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。供應者隨機地將兩樣東西放在桌子上，允

43、許一個吸煙者進行對健康不利的吸煙。當吸煙者完成吸煙后喚醒供應者，供應者再把兩樣東西放在桌子上，喚醒另一個吸煙者。試采用：(1)信號量和P、V操作；(2)管程編寫他們同步工作的程序。18：系統有同類資源m個，被n個進程共享，問：當mn和mn時，每個進程最多可以請求多少個這類資源時，使系統一定不會發生死鎖?答：當mn時，每個進程最多請求1個這類資源時，系統一定不會發生死鎖。當m>n時，如果m/n不整除，每個進程最多可以請求”商+1”個這類資源，否則為”商”個資源，使系統一定不會發生死鎖。19：N個進程共享M個資源，每個進程一次只能申請/釋放一個資源，每個進程最多需要M個資源，所有進程總共的資

44、源需求少于M+N個，證明該系統此時不會產生死鎖。答：設max（i）表示第i個進程的最大資源需求量，need(i)表示第i個進程還需要的資源量，alloc(i)表示第i個進程已分配的資源量。由題中所給條件可知： max(1)+max(n)=(need(1)+need(n)+(alloc(1)+alloc(n)<m+n如果在這個系統中發生了死鎖，那么一方面m個資源應該全部分配出去，alloc(1)+alloc(n)=m,另一方面所有進程將陷入無限等待狀態。可以推出need(1)+ +need(n)<n上式表示死鎖發生后，n個進程還需要的資源量之和小于n，這意味著此刻

45、至少存在一個進程i,need(i)=0,即它已獲得了所需要的全部資源。既然該進程已獲得了它所需要的全部資源，那么它就能執行完成并釋放它占有的資源，這與前面的假設矛盾，從而證明在這個系統中不可能發生死鎖。21：Jurassic公園有一個恐龍博物館和一個花園，有m個旅客和n輛車，每輛車僅能乘一個旅客。旅客在博物館逛了一會，然后，排隊乘坐旅行車，當一輛車可用時，它載入一個旅客，再繞花園行駛任意長的時間。若n輛車都已被旅客乘坐游玩，則想坐車的旅客需要等待。如果一輛車已經空閑，但沒有游玩的旅客了，那么，車輛要等待。試用信號量和P、V操作同步m個旅客和n輛車子。答：23：設當前的系統狀態如下，系統此時Av

46、ailable=(1，1，2)：Claim Allocation進程, R1 R2 R3 R1 R2 R3P1 3 2 2 1 0 0P2 6 1 3 5 1 1P3 3 1 4 2 1 1P4 4 2 2 0 0 2(1) 計算各個進程還需要的資源數Cki-Aki?(2) 系統是否處于安全狀態，為什么?(3) P1發出請求向量request2(1，0，1)，系統能把資源分給它嗎？(4) 若在P2申請資源后，若P1發出請求向量request1(1，0，1)，系統能把資源分給它嗎？(5) 若在P1申請資源后，若P3發出請求向量request3(0，0，1)，系統能把資源分給它嗎？答：(1)

47、60;P1，P2，P3，P4的Cki-Aki分別為：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0) (2) 系統處于安全狀態，存在安全序：P2，P1，P3，P4 (3) 可以分配，存在安全序列：P2，P1，P3，P4。 (4) 不可以分配。 (5) 不可以分配。24：系統有A、B、C、D共4種資源，在某時刻進程P0、P1、P2、P3和P4對資源的占有和需求情況如表，試解答下列問題：Allocation Claim Available進程 A B C D A B C D A B C DP0 0 0 3

48、 2 0 0 4 4 1 6 2 2P1 1 0 0 0 2 7 5 0P2 1 3 5 4 3 6 10 10P3 0 3 3 2 0 9 8 4P4 0 0 1 4 0 6 6 10(1)系統此時處于安全狀態嗎？(2) 若此時P1發出request1(1、2、2、2)，系統能分配資源給它嗎？為什么？答：(1)系統處于安全狀態，存在安全序列：P0，P3，P4，P1，P2。   (2)不能分配，否則系統會處于不安全狀態。25：把死鎖檢測算法用于下面的數據，并請問：Available=(1，0，2，0)1 1 0 03 0 1 10 1 1 2 Allocation

49、= 0 1 0 0Need=3 1 1 1 1 0 0 01 1 0 10 0 1 0=2 1 1 0 0 0 0 0(1)此時系統此時處于安全狀態嗎？(2)若第二個進程提出資源請求request2(0，0，1，0)，系統能分配資源給它嗎？(3)若第五個進程提出資源請求request5(0，0，1，0)，系統能分配資源給它嗎？答：(1)此時可以找出進程安全序列：P4，P1，P5，P2，P3。故系統處于安全狀態。 (2)可以分配，存在安全序列：P4，P1，P5，P2，P3。(3)不可分配，系統進入不安全狀態。26:考慮一個共有150個存儲單元的系統，如下分配給三個進程，P1最大需求70

50、,己占有25；P2最大需求60,己占有40；P3最大需求60,己占有45。使用銀行家算法，以確定下面的任何一個請求是否安全。(1)P4進程到達，P4最大需求60,最初請求25個。(2)P4進程到達，P4最大需求60,最初請求35。如果安全，找出安全序列；如果不安全，給出結果分配情況。答：29：進程A1、A2、An1通過m個緩沖區向進程B1、B2、Bn2不斷地發送消息。發送和接收工作符合以下規則：(1) 每個發送進程每次發送一個消息，寫進一個緩沖區，緩沖區大小與消息長度相等；(2) 對每個消息，B1、B2、Bn2都需接收一次，并讀入各自的數據區內；(3) 當M個緩沖區都滿時，則發送進程等待，當沒

51、有消息可讀時，接收進程等待。試用信號量和PV操作編制正確控制消息的發送和接收的程序。答：30：某系統有R1設備3臺，R2設備4臺，它們被P1、P2、P3和P4進程共享，且已知這4個進程均按以下順序使用設備：申請R1申請R2申請R1釋放R1釋放R2釋放R1(1) 系統運行中可能產生死鎖嗎？為什么？(2) 若可能的話，請舉出一種情況，并畫出表示該死鎖狀態的進程資源圖。答：39：一組生產者進程和一組消費者進程共享九個緩沖區，每個緩沖區可以存放一個整數。生產者進程每次一次性向3個緩沖區寫入整數，消費者進程每次從緩沖區取出一個整數。請用：(1)信號量和P、V操作；(2)管程，寫出能夠正確執行的程序。答：41：下述流程是解決兩進程互斥訪問臨界區問題的一種方法。試從“互斥”(mutual exclusion)、“空閑讓進”(progres