【正文】 態(tài)。 （3）執(zhí)行→阻塞：正在執(zhí)行的進(jìn)程因發(fā)生某事件而無(wú)法執(zhí)行，如等待I/O操作的完成或未能申請(qǐng)到所需的系統(tǒng)資源等，則進(jìn)程轉(zhuǎn)為阻塞狀態(tài)。5． 進(jìn)程控制塊的作用是什么？在進(jìn)程控制塊中主要包括哪些信息？參考答案：進(jìn)程控制塊，簡(jiǎn)稱PCB（Process Control Block），是進(jìn)程實(shí)體的重要組成部分，其中記錄了用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需要的全部信息。在進(jìn)程的控制和管理中，隨進(jìn)程的創(chuàng)建而建立PCB；因進(jìn)程的狀態(tài)變化而修改PCB的相關(guān)內(nèi)容；當(dāng)進(jìn)程被撤銷時(shí)，系統(tǒng)收回其PCB。不同的操作系統(tǒng)其PCB所包含的信息會(huì)有些不同，但PCB通常都應(yīng)包含如下基本信息：（1）進(jìn)程標(biāo)識(shí)符：系統(tǒng)中的每個(gè)進(jìn)程都有唯一的標(biāo)識(shí)符，以標(biāo)識(shí)一個(gè)進(jìn)程，可以用字符串或編號(hào)表示。（3）現(xiàn)場(chǎng)信息：主要是由處理器的各個(gè)寄存器中的內(nèi)容組成，包括通用寄存器內(nèi)容、指令計(jì)數(shù)器的值、程序狀態(tài)字內(nèi)容以及用戶棧指針。（4）管理信息：是進(jìn)程管理和控制所需要的相關(guān)信息，包括程序和數(shù)據(jù)在內(nèi)存或外存的地址、進(jìn)程同步和通信機(jī)制、資源清單（記錄進(jìn)程所需的除CPU外的全部資源和已經(jīng)分配到的資源）、進(jìn)程隊(duì)列的鏈接指針等。然后將其PCB插入就緒隊(duì)列等待進(jìn)程調(diào)度。原語(yǔ)首先檢查被撤消進(jìn)程在系統(tǒng)中是否存在，如果存在，則回收該進(jìn)程占用的所有系統(tǒng)資源，將其PCB從所在隊(duì)列中移出。最后撤消其PCB。（4）進(jìn)程喚醒原語(yǔ)首先將被阻塞進(jìn)程的PCB從所在阻塞隊(duì)列中移出，并將其PCB中的狀態(tài)由“阻塞”改為“就緒”，然后插入就緒隊(duì)列中等待調(diào)度。（2） 忙則等待：當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表示相應(yīng)的臨界資源正被訪問(wèn)，因而所 有其它試圖進(jìn)入相關(guān)臨界區(qū)的進(jìn)程必須等待，以保證諸進(jìn)程互斥訪問(wèn)臨界資源。（4） 讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放處理器，以免陷入“忙等”狀態(tài)。參考答案：多個(gè)進(jìn)程之間彼此無(wú)關(guān)，它們并不知道其它進(jìn)程的存在，但由于同處于一個(gè)系統(tǒng)中，必然存在著資源共享關(guān)系。多個(gè)進(jìn)程在共享臨界資源時(shí)，必須以互斥方式共享。具體說(shuō)，這些進(jìn)程之間需要交換一定的信息，當(dāng)某進(jìn)程未獲得其合作進(jìn)程發(fā)來(lái)的信息之前，該進(jìn)程等待，直到接收到相關(guān)信息時(shí)才繼續(xù)執(zhí)行，從而保證諸進(jìn)程的協(xié)調(diào)運(yùn)行。參考答案：P（S）：將信號(hào)量S減1，若結(jié)果大于或等于0，則該進(jìn)程繼續(xù)執(zhí)行；若結(jié)果小于0，則該進(jìn)程被阻塞，并將其插入到該信號(hào)量的等待隊(duì)列中，然后轉(zhuǎn)去調(diào)度另一進(jìn)程。PV操作的物理含義：信號(hào)量S值的大小表示某類資源的數(shù)量。每執(zhí)行一次P操作，S值減1，表示請(qǐng)求分配一個(gè)資源，若S≥0，表示可以為進(jìn)程分配資源，即允許進(jìn)程進(jìn)入其臨界區(qū)；若S0，表示已沒(méi)有資源可供分配，申請(qǐng)資源的進(jìn)程被阻塞，并插入S的等待隊(duì)列中，S的絕對(duì)值表示等待隊(duì)列中進(jìn)程的數(shù)目，此時(shí)CPU將重新進(jìn)行調(diào)度。無(wú)論以上哪種情況，執(zhí)行V操作的進(jìn)程都可繼續(xù)運(yùn)行。每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)。將P（full）與P（mutex）互換位置，系統(tǒng)也可能進(jìn)入死鎖狀態(tài)。12． 假設(shè)有三個(gè)并發(fā)進(jìn)程P，Q，R，其中P負(fù)責(zé)從輸入設(shè)備上讀入信息并傳送給Q，Q將信息加工后傳送給R，R則負(fù)責(zé)將信息打印輸出。（2）進(jìn)程P、Q共享一個(gè)由m個(gè)緩沖區(qū)組成的緩沖池，進(jìn)程Q、R共享另一個(gè)由n個(gè)緩沖區(qū)組成的緩沖池。empty1 :=1。 full1 :=0。cobeginP ( )。 R ( )。end。 P（empty1）。 goto L1 end。從緩沖區(qū)1取出信息。 P（empty2）。 goto L2 end。從緩沖區(qū)2取出信息。將信息打印輸出 。 end。empty1 :=m。 full1 :=0。cobeginP ( )。 R ( )。end。 P（empty1）。 goto L1 end。從緩沖池1中的一個(gè)非空緩沖區(qū)中取出信息。 P（empty2）。 goto L2 end。從緩沖池2中的一個(gè)非空緩沖區(qū)中取出信息。將信息打印輸出 。 end。進(jìn)程R1每次從磁盤(pán)讀入一個(gè)數(shù)存放到緩沖區(qū)中，供進(jìn)程W1打印輸出；進(jìn)程R2每次從鍵盤(pán)讀一個(gè)數(shù)存放到緩沖區(qū)中，供進(jìn)程W2打印輸出。試用PV操作實(shí)現(xiàn)四個(gè)進(jìn)程的協(xié)調(diào)運(yùn)行。empty :=1。 full2 :=0。R2 ( )。 W2 ( )。end。 將數(shù)存放到緩沖區(qū)中； V（full1）。 process R2 ( )begin L2: 從鍵盤(pán)上讀入一個(gè)數(shù)； P（empty）。 goto L2 end。將緩沖區(qū)中的數(shù)取出；V（empty）。 goto L3 end。將緩沖區(qū)中的數(shù)取出；V（empty）。 goto L4 end?，F(xiàn)假設(shè)初始狀態(tài)為：司機(jī)和售票員都已經(jīng)在車上，汽車處于停止?fàn)顟B(tài)，車門(mén)處于開(kāi)的狀態(tài)。參考答案：第一步：確定進(jìn)程2個(gè)進(jìn)程 Driver（司機(jī)）、Busman（售票員）Driver進(jìn)程： l 啟動(dòng)車輛l 正常行車l 到站停車Busman進(jìn)程：l 關(guān)車門(mén)l 售票l 開(kāi)車門(mén)第二步：確定進(jìn)程的同步、互斥關(guān)系l 同步：當(dāng)售票員將車門(mén)關(guān)上后，司機(jī)才可以啟動(dòng)車輛l 同步：當(dāng)司機(jī)到站停車后，售票員打開(kāi)車門(mén)第三步：設(shè)置信號(hào)量l 車門(mén)關(guān)上，close，初值0l 到站停車，stop，初值0第四步：用偽代碼描述begin close, stop：semaphore。 stop := 0。Busman ( )。end。 process Busman ( )begin L2: 關(guān)車門(mén)； V（close）。 開(kāi)車門(mén)；goto L2 end。請(qǐng)用信號(hào)量的PV操作描述哲學(xué)家之間的關(guān)系。chopstick[0~4] := 1。 P（chopstick[i+1%5] ）。 V（chopstick[i] ）。end。解決方案： 至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐,以保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐,最終總會(huì)釋放出他所使用過(guò)的兩支筷子,從而可使更多的哲學(xué)家進(jìn)餐。,將是1,2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子,3,獲得后,再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子,最后總會(huì)有一個(gè)哲學(xué)家能獲得兩支筷子而進(jìn)餐。 將拿筷子的操作做成原子操作，即當(dāng)一個(gè)哲學(xué)家正在拿筷子的時(shí)候，其它的哲學(xué)家不能動(dòng)筷子，當(dāng)他那好筷子開(kāi)始吃飯的時(shí)候，其它哲學(xué)家才可以拿筷子。num : semaphore。num := 4。 P（chopstick[i]）。 吃面條； V（chopstick[i+1%5] ）。 V (num)。end。參考答案：由于打印機(jī)是臨界資源，三個(gè)進(jìn)程共享臨界資源，是互斥關(guān)系。s := 1。 打??； V (s)。end。爸爸放蘋(píng)果，媽媽放桔子，兒子只吃桔子，女兒只吃蘋(píng)果。爸爸放蘋(píng)果，媽媽放桔子，兒子吃桔子、蘋(píng)果。 Sp :=1。 Sa :=0。Mother ( )。Daughter ( )。end。 將蘋(píng)果放入盤(pán)中； V（Sa）。 end。 將桔子放入盤(pán)中； V（So）。 end。 從盤(pán)中取出桔子； V（Sp） 吃桔子； goto L3； end。 從盤(pán)中取出蘋(píng)果； V（Sp） 吃蘋(píng)果； goto L4； end。 empty:=1。cobeginFather ( )。Son ( )。end。 將蘋(píng)果放入盤(pán)中； V（full）。 end。 將桔子放入盤(pán)中； V（full）。 end。 從盤(pán)中取出水果。 吃水果。18． 有一個(gè)閱覽室，共有100個(gè)座位。試用PV操作描述讀者進(jìn)入/離開(kāi)閱覽室的同步與互斥關(guān)系。 seat :=100。 Sout := 1。 begin P(seat)。 登記。 進(jìn)入閱覽室。 離開(kāi)閱覽室。 注銷。 V（seat）。end。生產(chǎn)的每一臺(tái)設(shè)備都必須入庫(kù)，銷售部門(mén)可從倉(cāng)庫(kù)提出設(shè)備供應(yīng)客戶?，F(xiàn)只有一臺(tái)運(yùn)輸工具，每次只能運(yùn)輸一臺(tái)設(shè)備。參考答案：第一步：確定進(jìn)程可以為入庫(kù)（Pin）和出庫(kù)（Pout）各設(shè)置一個(gè)進(jìn)程Pin進(jìn)程： l 生產(chǎn)了一臺(tái)設(shè)備l 使用運(yùn)輸工具入庫(kù)Pout進(jìn)程： l 使用運(yùn)輸工具出庫(kù)l 提出設(shè)備供應(yīng)客戶第二步：確定進(jìn)程的同步、互斥關(guān)系l 同步：當(dāng)倉(cāng)庫(kù)中有空余位置存放設(shè)備時(shí)，設(shè)備才可以入庫(kù)l 同步：當(dāng)倉(cāng)庫(kù)中有存放的設(shè)備時(shí)，設(shè)備才可以出庫(kù)l 互斥：運(yùn)輸工具是臨界資源，要互斥訪問(wèn)第三步：設(shè)置信號(hào)量l 倉(cāng)庫(kù)中有空余位置數(shù)量，empty，初值10l 倉(cāng)庫(kù)中有存放的設(shè)備數(shù)量，full，初值 0l 為運(yùn)輸工具設(shè)置互斥信號(hào)量S，初值 1，表示當(dāng)前可用第四步：用偽代碼描述begin empty, full, S：semaphore。full := 0。cobegin Pin ()。coend。process Pin ( ) begin L1: 生產(chǎn)了一臺(tái)設(shè)備 。 P (S)。V （S）。 goto L1。 process Pout ( ) beginL2: P（full）。使用運(yùn)輸工具出庫(kù)。V（empty）。 goto L2。 20． 進(jìn)程通信主要有哪幾種類型？參考答案：進(jìn)程通信的類型主要有：共享存儲(chǔ)器系統(tǒng)、消息傳遞系統(tǒng)以及管道通信系統(tǒng)。低級(jí)調(diào)度通常又稱為進(jìn)程調(diào)度，其任務(wù)是決定就緒隊(duì)列中的哪個(gè)進(jìn)程獲得處理器，然后由分派程序把處理器分配給該進(jìn)程，為它恢復(fù)運(yùn)行現(xiàn)場(chǎng)，讓其運(yùn)行。22． 引起進(jìn)程調(diào)度的原因有哪些？參考答案：引起進(jìn)程調(diào)度的原因有：（1）正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；（2）執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；（3）在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作；（4）當(dāng)采用基于優(yōu)先權(quán)的強(qiáng)占式調(diào)度算法時(shí)，就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)比當(dāng)前正在執(zhí)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程時(shí)；（5）當(dāng)采用時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)，當(dāng)前進(jìn)程的時(shí)間片用完了。從作業(yè)提交開(kāi)始到作業(yè)完成為止的時(shí)間間隔稱為周轉(zhuǎn)時(shí)間，它包括作業(yè)等待進(jìn)入內(nèi)存、進(jìn)程在就緒隊(duì)列中等待、進(jìn)程在CPU上執(zhí)行和完成I/O操作所花費(fèi)的時(shí)間總和。為了能更準(zhǔn)確地評(píng)價(jià)系統(tǒng)的性能，引入了另一個(gè)指標(biāo)：帶權(quán)周轉(zhuǎn)時(shí)間，即作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)實(shí)際為其提供的服務(wù)時(shí)間之比。從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間間隔稱為響應(yīng)時(shí)間，主要用于評(píng)價(jià)分時(shí)系統(tǒng)。所謂截止時(shí)間，是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間，主要用于評(píng)價(jià)實(shí)時(shí)系統(tǒng)。 當(dāng)CPU的價(jià)格非常昂貴時(shí)，希望盡可能使它得到充分利用。（5） 系統(tǒng)吞吐量高。24． 批處理操作系統(tǒng)、分時(shí)操作系統(tǒng)和實(shí)時(shí)操作系統(tǒng)常用哪些進(jìn)程調(diào)度算法？參考答案：批處理操作系統(tǒng)常用的進(jìn)程調(diào)度算法有：先來(lái)先服務(wù)調(diào)度算法、短進(jìn)程優(yōu)先調(diào)度算法、高優(yōu)先權(quán)優(yōu)先調(diào)度算法、高響應(yīng)比優(yōu)先調(diào)度算法；分時(shí)操作系統(tǒng)常用的進(jìn)程調(diào)度算法有：時(shí)間片輪轉(zhuǎn)調(diào)度算法、多級(jí)反饋隊(duì)列調(diào)度算法；實(shí)時(shí)操作系統(tǒng)常用的進(jìn)程調(diào)度算法主要有：高優(yōu)先權(quán)優(yōu)先調(diào)度算法。對(duì)于動(dòng)態(tài)優(yōu)先級(jí)，也是在創(chuàng)建進(jìn)程時(shí)為進(jìn)程賦予一個(gè)初始優(yōu)先級(jí)，以后在進(jìn)程的運(yùn)行過(guò)程中隨著進(jìn)程特性的變化，不斷修改優(yōu)先級(jí)，如隨著進(jìn)程在就緒隊(duì)列中等待時(shí)間的增長(zhǎng)，可提高進(jìn)程的優(yōu)先級(jí)；隨著進(jìn)程連續(xù)占用CPU時(shí)間的增長(zhǎng)，可降低其優(yōu)先級(jí)，防止一個(gè)進(jìn)程長(zhǎng)期壟斷CPU等。若分別采用先來(lái)先服務(wù)算法和短進(jìn)程優(yōu)先算法，試給出各進(jìn)程的調(diào)度順序以及平均周轉(zhuǎn)時(shí)間。若分別采用非搶占式優(yōu)先級(jí)調(diào)度算法和可搶占式優(yōu)先級(jí)調(diào)度算法，試給出各進(jìn)程的調(diào)度順序以及平均周轉(zhuǎn)時(shí)間。產(chǎn)生死鎖的原因主要有兩個(gè)：一是多個(gè)進(jìn)程競(jìng)爭(zhēng)資源，二是進(jìn)程請(qǐng)求和釋放資源的時(shí)機(jī)不對(duì)。處理死鎖的基本方法有：預(yù)防死鎖、避免死鎖、檢測(cè)和解除死鎖。參考答案：線程是進(jìn)程中的一個(gè)實(shí)體，是CPU調(diào)度和分派的基本單位。傳統(tǒng)的進(jìn)程稱為重型進(jìn)程，相當(dāng)于只有一個(gè)線程的任務(wù)。下面從調(diào)度、并發(fā)性、擁有資源和系統(tǒng)開(kāi)銷幾個(gè)方面對(duì)線程和進(jìn)程進(jìn)行比較。在傳統(tǒng)的操作系統(tǒng)中，進(jìn)程既是資源分配和擁有的基本單位，又是獨(dú)立調(diào)度和執(zhí)行的基本單位。同一進(jìn)程中兩個(gè)線程的切換不會(huì)引起進(jìn)程切換，但由一個(gè)進(jìn)程中的線程切換到另一個(gè)進(jìn)程中的線程時(shí)，將會(huì)引起進(jìn)程切換。在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個(gè)進(jìn)程中的多個(gè)線程之間也可以并發(fā)執(zhí)行，因而使系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。不論是傳統(tǒng)的操作系統(tǒng)，還是引入線程的操作系統(tǒng)，進(jìn)程都是擁有資源的獨(dú)立單位。亦即一個(gè)進(jìn)程的代碼段、數(shù)據(jù)段以及系統(tǒng)資源（如已打開(kāi)的文件、I/O設(shè)備等），可供該進(jìn)程的所有線程共享。系統(tǒng)在創(chuàng)建或撤消進(jìn)程時(shí)，都要為之分配或回收資源，如內(nèi)存空間、I/O設(shè)備等，因此系統(tǒng)所付出的開(kāi)銷將顯著地大于創(chuàng)建或撤消線程的開(kāi)銷。第三章習(xí)題1． 什么叫重定位？它有哪兩種方式？這兩種方式有什么區(qū)別？參考答