數(shù)據(jù)庫作業(yè)第二章第三章

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

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

3、）是內(nèi)核提供給應(yīng)用程序的接口，屬于系統(tǒng)的一部分，可以認(rèn)為是某種內(nèi)核的庫函數(shù)；操作系統(tǒng)API是有系統(tǒng)調(diào)用（函數(shù)）的集合（也就是將許多的系統(tǒng)調(diào)用封裝在了一起）。一是編寫系統(tǒng)調(diào)用服務(wù)例程；二是設(shè)計系統(tǒng)調(diào)用入口地址表，每個入口地址都指向一個系統(tǒng)調(diào)用的服務(wù)例程，有的還包括系統(tǒng)調(diào)用自帶的參數(shù)個數(shù)；三是陷阱處理機(jī)制，需要開辟現(xiàn)場保護(hù)區(qū)，以保存發(fā)生系統(tǒng)調(diào)用時應(yīng)用程序的處理器現(xiàn)場。應(yīng)用程序執(zhí)行系統(tǒng)調(diào)用，產(chǎn)生中斷指向內(nèi)核態(tài)，進(jìn)入陷阱處理程序，它將按功能查詢?nèi)肟诘刂繁恚⑥D(zhuǎn)至對應(yīng)服務(wù)例程執(zhí)行，完成后退出中斷，返回應(yīng)用程序斷點(diǎn)繼續(xù)運(yùn)行。14.簡述Linux的快中斷和慢中斷快中斷：快中斷處理僅要保存被常規(guī)C函數(shù)修改的寄

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

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

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

7、境中?！俺绦颉弊陨碇皇怯嬎闳蝿?wù)的指令和數(shù)據(jù)的描述，是靜態(tài)概念無法刻畫程序的并發(fā)特性，系統(tǒng)需要尋找一個能描述程序動態(tài)執(zhí)行過程的概念，這就是進(jìn)程。它能解決系統(tǒng)的“共享性”，正確描述程序的執(zhí)行狀態(tài)。程序與程序的執(zhí)行不再一一對應(yīng)19.進(jìn)程有哪些主要屬性？試解釋之共享性：同一程序同時運(yùn)行于不同數(shù)據(jù)集合上時構(gòu)成不同進(jìn)程，即多個不同進(jìn)程可執(zhí)行相同的程序，所以進(jìn)程和程序不是一一對應(yīng)的。動態(tài)性：進(jìn)程是程序在數(shù)據(jù)集合上的一次執(zhí)行過程，是動態(tài)概念，同時它有生命周期，由創(chuàng)建而產(chǎn)生、由調(diào)度而執(zhí)行、由事件而等待、由撤銷而消亡；而程序是一組有序指令序列，是靜態(tài)概念，所以程序作為系統(tǒng)中的一種資源是永遠(yuǎn)存在的獨(dú)立性：每個進(jìn)程是

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

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

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

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

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

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

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

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

16、的時間間隔；（2）作業(yè)帶權(quán)周轉(zhuǎn)時間：在操作系統(tǒng)中，帶權(quán)周轉(zhuǎn)時間反映作業(yè)（或進(jìn)程）長短問題，帶權(quán)周轉(zhuǎn)時間越大，作業(yè)（或進(jìn)程）越短；帶權(quán)周轉(zhuǎn)時間越小，作業(yè)（或進(jìn)程）越長。（3）響應(yīng)時間：從交互式進(jìn)程提交一個請求至得到響應(yīng)之間的時間間隔稱為響應(yīng)時間。（4）吞吐率：單位時間CPU處理作業(yè)的個數(shù)。53.試述作業(yè)、進(jìn)程、線程和程序之間的關(guān)系。進(jìn)程是操作系統(tǒng)結(jié)構(gòu)的基礎(chǔ)；是一個正在執(zhí)行的程序；計算機(jī)中正在運(yùn)行的程序?qū)嵗?；可以分配給處理器并由處理器執(zhí)行的一個實(shí)體；由單一順序的執(zhí)行顯示，一個當(dāng)前狀態(tài)和一組相關(guān)的系統(tǒng)資源所描述的活動單元。 線程（thread, 臺灣稱 執(zhí)行緒）是"進(jìn)程"中某個單

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

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

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

20、斷是隨機(jī)碰到哪個進(jìn)程，就插入哪個進(jìn)程中運(yùn)行處理程序，并把處理時間記在這個進(jìn)程的賬上。7. 8.10. 按照最短作業(yè)優(yōu)先的算法可以使平均響應(yīng)時間最短。X取值不定，按照以下情況討論： 1） x3 次序?yàn)椋簒，3，5，6，9 2） 3<x5 次序?yàn)椋?，x，5，6，9 3） 5<x6 次序?yàn)椋?，5，x，6，9 4） 6<x9 次序?yàn)椋?，5，6，x，9 5） 9<x 次序?yàn)椋?，5，6，9，x11.( l ) FCFS 調(diào)度算法( 2 ）優(yōu)先級調(diào)度算法 ( 3 ）時間片輪轉(zhuǎn)法按次序ABCDEBCDECDEDEE 輪轉(zhuǎn)執(zhí)行。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平均作業(yè)周轉(zhuǎn)時間 =(160+30+80+130+80+50)/6=88.3326.(1) Job4最后一個完成(2) 各個作業(yè)的平均周轉(zhuǎn)時間為：(90+40+120+120+30)/5 = 80 各個作業(yè)的平均帶權(quán)周轉(zhuǎn)時間為：(1.8+1+2.4+6+3)/5 = 2.8432. 循環(huán)周期為4*100+400=800ms A類進(jìn)程需要2*1000/100=20個時間片的執(zhí)行時間，B類進(jìn)程需要2*1000/400=5個時間片的執(zhí)

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

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

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

25、誤的兩種表現(xiàn)形式。 答：時間有關(guān)的錯誤有兩種形式，一是結(jié)果不唯一，二是永遠(yuǎn)等待。 結(jié)果不唯一：飛機(jī)售票問題。 永遠(yuǎn)等待：內(nèi)存資源的管理問題。八：試述進(jìn)程的互斥和同步兩個概念之間的異同。答：進(jìn)程互斥是指若干進(jìn)程因相互爭奪獨(dú)占性資源而產(chǎn)生的競爭制約關(guān)系。 進(jìn)程同步是指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個條件來協(xié)調(diào)其活動，因?yàn)樾枰谀承┪恢蒙吓哦▓?zhí)行的先后順序而等待、傳遞順序或消息所產(chǎn)生的協(xié)調(diào)制約關(guān)系。進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系，即逐次使用進(jìn)程同步資源，也是對進(jìn)程使用資源的次序的一種協(xié)調(diào)。九：什么是臨界區(qū)和臨界資源？臨界區(qū)管理的基本規(guī)則是什么？答：并發(fā)進(jìn)程中與共享變量有關(guān)的程序稱為臨界區(qū)。共享

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

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

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

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

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

31、實(shí)現(xiàn)。答：（1）：每個進(jìn)程task_struct結(jié)構(gòu)中signal域?qū)ｉT保存接收到的信號，內(nèi)核根據(jù)所發(fā)生的時間產(chǎn)生相應(yīng)的信號并發(fā)送給接收數(shù)據(jù)。（2）：進(jìn)程task_struct結(jié)構(gòu)中的blocked是信號屏蔽標(biāo)記，相當(dāng)于中斷屏蔽寄存器。（3）：信號處理函數(shù)的入口存放在進(jìn)程task_struct的sigaction數(shù)組中，利用sigction函數(shù)為進(jìn)程設(shè)置信號處理函數(shù)。（4）：函數(shù)sigaction(signo,act,oldacd)為指定信號設(shè)置處理函數(shù)。（5）：函數(shù)kill(pid,sig)用來向指定的進(jìn)程或進(jìn)程組發(fā)送指定信號。（6）：信號檢測和相應(yīng)總發(fā)生在系統(tǒng)空間。23：試述進(jìn)程的低級通信

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

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

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

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

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

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

38、量的值應(yīng)為-(n-1)也就是-n+1。2）互斥信號量初值為m，變化范圍為-n+m，m。當(dāng)沒有進(jìn)程進(jìn)入互斥段時，信號量值為m；當(dāng)有1個進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時，信號量值為m-1；當(dāng)有m個進(jìn)程進(jìn)入互斥段且沒有一個進(jìn)程等待進(jìn)入互斥段時，信號量值為0；當(dāng)有m個進(jìn)程進(jìn)入互斥段且有一個進(jìn)程等待進(jìn)入互斥段時，信號量值為-1；最多可能有n-m個進(jìn)程等待進(jìn)入互斥段，故此時信號量的值應(yīng)為-(n-m)也就是-n+m。3：有兩個優(yōu)先級相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問P1、P2并發(fā)執(zhí)行后，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：有一閱覽室，讀者進(jìn)入時必須先在一張登記表上登記，該表為每一座位列出一個表目，包括座號、姓名，讀者離開時要注銷登記信息；假如閱覽室共有100個座位。試用：1）信號量和P、V操作；2）管程，來實(shí)現(xiàn)用戶進(jìn)程的同步算法。答：1) 使用信號量和P、V操作： 6：在一個盒子里，混裝了數(shù)量相等的黑白圍棋子?，F(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設(shè)分揀系統(tǒng)有二個進(jìn)程P1和P2，其中P1揀白子；P2揀黑子。規(guī)定每個進(jìn)程每次揀一子；當(dāng)一個

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

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

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

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

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

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

46、ailable=(1，1，2)：Claim Allocation進(jìn)程, 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) 計算各個進(jìn)程還需要的資源數(shù)Cki-Aki?(2) 系統(tǒng)是否處于安全狀態(tài)，為什么?(3) P1發(fā)出請求向量request2(1，0，1)，系統(tǒng)能把資源分給它嗎？(4) 若在P2申請資源后，若P1發(fā)出請求向量request1(1，0，1)，系統(tǒng)能把資源分給它嗎？(5) 若在P1申請資源后，若P3發(fā)出請求向量request3(0，0，1)，系統(tǒng)能把資源分給它嗎？答：(1)

47、60;P1，P2，P3，P4的Cki-Aki分別為：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0) (2) 系統(tǒng)處于安全狀態(tài)，存在安全序：P2，P1，P3，P4 (3) 可以分配，存在安全序列：P2，P1，P3，P4。 (4) 不可以分配。 (5) 不可以分配。24：系統(tǒng)有A、B、C、D共4種資源，在某時刻進(jìn)程P0、P1、P2、P3和P4對資源的占有和需求情況如表，試解答下列問題：Allocation Claim Available進(jìn)程 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)系統(tǒng)此時處于安全狀態(tài)嗎？(2) 若此時P1發(fā)出request1(1、2、2、2)，系統(tǒng)能分配資源給它嗎？為什么？答：(1)系統(tǒng)處于安全狀態(tài)，存在安全序列：P0，P3，P4，P1，P2。   (2)不能分配，否則系統(tǒng)會處于不安全狀態(tài)。25：把死鎖檢測算法用于下面的數(shù)據(jù)，并請問：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)此時系統(tǒng)此時處于安全狀態(tài)嗎？(2)若第二個進(jìn)程提出資源請求request2(0，0，1，0)，系統(tǒng)能分配資源給它嗎？(3)若第五個進(jìn)程提出資源請求request5(0，0，1，0)，系統(tǒng)能分配資源給它嗎？答：(1)此時可以找出進(jìn)程安全序列：P4，P1，P5，P2，P3。故系統(tǒng)處于安全狀態(tài)。 (2)可以分配，存在安全序列：P4，P1，P5，P2，P3。(3)不可分配，系統(tǒng)進(jìn)入不安全狀態(tài)。26:考慮一個共有150個存儲單元的系統(tǒng)，如下分配給三個進(jìn)程，P1最大需求70

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

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