操作系統(tǒng)自考復(fù)習(xí)重點(diǎn)

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

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

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

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

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

6．中斷與程序并發(fā)之間的關(guān)系是什么？答：中斷是程序并發(fā)的前提條件。如果沒有中斷，操作系統(tǒng)不能獲得系統(tǒng)控制權(quán)，無法按調(diào)度算法對(duì)處機(jī)進(jìn)行重新分配，一個(gè)程序?qū)⒁恢边\(yùn)行到結(jié)束而不會(huì)被打斷。

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

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

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

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

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

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

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

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

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

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

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

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

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

5.

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

6.

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

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

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

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

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

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

12.

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

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

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

4.中斷發(fā)生時(shí)，舊的PSW和PC為何需要壓入系統(tǒng)棧?答：因?yàn)橥ǔＶ袛嗵幚沓绦虻淖詈笠粭l指令是中斷返回指令，該指令從系統(tǒng)棧頂彈出斷點(diǎn)信息，如果未將PSW和PC壓入系統(tǒng)棧，則中斷返回指令彈出的不是中斷前的斷點(diǎn)信息，而是不確定的信息，這將導(dǎo)致系統(tǒng)處于不確定的狀態(tài)，嚴(yán)重的情況會(huì)使系統(tǒng)崩潰。采用棧結(jié)構(gòu)的原因是中斷可能發(fā)生嵌套，此時(shí)能保證以與中斷相反的次序返回上層中斷處理程序或返回目態(tài)。在某些硬件系統(tǒng)中，沒有采用棧結(jié)構(gòu)，中斷發(fā)生時(shí)現(xiàn)場(chǎng)信息被送到系統(tǒng)空間指定單元，對(duì)每種中斷硬件規(guī)定一個(gè)現(xiàn)場(chǎng)保存單元，這樣處理的缺點(diǎn)是中斷類型不能增加，相同類型中斷不能嵌套發(fā)生。

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

6.中斷向量的存儲(chǔ)位置是否可由程序改變?為什么?中斷向量的值是如何確定的?答：中斷向量的存儲(chǔ)位置是由硬件確定的，不能由程序改變。中斷發(fā)生后，中斷裝置按照中斷類型到內(nèi)存指定位置取出中斷向量。例如，在IBMPC系統(tǒng)中，地址000~03FF是中斷向量空間。操作系統(tǒng)的設(shè)計(jì)者根據(jù)各中斷事件處理程序的存儲(chǔ)位置及運(yùn)行環(huán)境確定對(duì)應(yīng)中斷向量的值，系統(tǒng)啟動(dòng)時(shí)由初始化程序?qū)⒃撝堤钊胫付ㄎ恢谩?/p>

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

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

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

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

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

12.如果沒有中斷，是否能夠?qū)崿F(xiàn)多道程序設(shè)計(jì)?為什么?答：不能。因?yàn)橐粋€(gè)程序一旦被調(diào)度執(zhí)行，將一直執(zhí)行下去，中間不可能被打斷，不可能達(dá)到多個(gè)進(jìn)程交替執(zhí)行的并發(fā)目的。

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

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

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

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

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

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

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

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

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

22.有人說，在采用等長(zhǎng)時(shí)間片輪轉(zhuǎn)處理機(jī)調(diào)度算法的分時(shí)操作系統(tǒng)中，各終端用戶所占有處理機(jī)的時(shí)間總量是相同的。這種說法對(duì)嗎?為什么?答：這種說法不對(duì)。因?yàn)樘幚頇C(jī)是分配給進(jìn)程（線程）的，而不同終端用戶可能有不同數(shù)量的進(jìn)程，一個(gè)擁有較多數(shù)量進(jìn)程的終端顯然比擁有較少數(shù)量進(jìn)程的終端獲得CPU的時(shí)間要多。

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

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

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

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

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

C1A1B1A2B2C251015101550

5

15

30

40

55

60A1B1C1A2B2C2A3

B3A4C3

101551015510

15105

010

253040

5560708095105110120

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

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

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

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

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

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

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

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

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

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

8．設(shè)CR1是關(guān)于一組共享變量SV1的臨界區(qū)域，CR2是關(guān)于另外一組共享變量SV2的臨界區(qū)域，當(dāng)進(jìn)程P1進(jìn)入CR1時(shí)，進(jìn)程P2是否可以進(jìn)入CR2?為什么?答：可以。因?yàn)榛コ馐窃谧兞考?jí)別上的，多個(gè)進(jìn)程同時(shí)進(jìn)入關(guān)于不同變量的臨界區(qū)不會(huì)引起與時(shí)間有關(guān)的錯(cuò)誤。

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

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

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

12.設(shè)S1和S2為兩個(gè)信號(hào)燈變量，下列八組P、V操作哪些可以同時(shí)進(jìn)行?哪些不能同時(shí)進(jìn)行?為什么?(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)答：能同時(shí)進(jìn)行的包括：(1)、(2)、(3)、(4)。這些操作涉及不同信號(hào)燈變量，屬于關(guān)于不同組共享變量的臨界區(qū)。不能同時(shí)進(jìn)行的包括：(5)、(6)、(7)、(8)。這些操作涉及相同的信號(hào)燈變量，屬于關(guān)于同一組共享變量的臨界區(qū)。

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

生產(chǎn)者活動(dòng)：while(1){producenextproduct;P(mutex_in);addtheproducttobuffer[in];in++;v(mutex_in);V(empty);}消費(fèi)者活動(dòng)：while(1){P(empty);P(mutex_out);taketheproductfrombuffer[out];out++;V(mutex_out);}

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

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

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

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

semaphorestart=0;semaphoreopen=0;

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

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

A組申請(qǐng)：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組進(jìn)程活動(dòng)可以給出B組和C組進(jìn)程活動(dòng)。

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

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

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

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

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

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);將進(jìn)程pid按其優(yōu)先數(shù)插入到等待隊(duì)列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隊(duì)首進(jìn)程；queue下移；V(mutex_queue);}}

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

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

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

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

25.試用會(huì)合給出讀寫問題的解法，要求寫者優(yōu)先．解：定義一個(gè)任務(wù)，包含如下四個(gè)入口：start_read,finish_read,start_write,finish_write。該問題的關(guān)鍵是：strat_write的入口條件不應(yīng)考慮當(dāng)前讀者情況，當(dāng)會(huì)合發(fā)生后再判斷當(dāng)前是否有讀者，并與其finish_read會(huì)合。這里顯然需要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=>//也許當(dāng)前有讀者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.關(guān)于讀者/寫者問題,有人給出如下改進(jìn)解法:semaphorer_w_w,mutex,s;(初值均為1)intcount;(初值為0)讀者活動(dòng)：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);

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

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

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

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

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

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

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

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

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

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

AB<-E：左轉(zhuǎn)W：直行->DC

/\|S:左轉(zhuǎn)

解：(1)Ｅ方向兩臺(tái)車分別位于A和B；S方向一臺(tái)車位于C；W方向一臺(tái)車位于D。(2)S方向兩臺(tái)車分別位于B和C；E方向一臺(tái)車位于A；W方向一臺(tái)車位于D。設(shè)位置資源C、B、A、D的編號(hào)從低到高依次為1、2、3、4，管理四個(gè)位置的信號(hào)量分別為s1,s2,s3,s4，信號(hào)量的初值均為1。車輛活動(dòng)如下：semaphores1=1,s2=1,s3=1,s4=1;W：直行P(s1);//按序申請(qǐng)P(s4);駛?cè)隓;駛?cè)隒;V(s4);駛出C;V(s1);E：左轉(zhuǎn)P(s2);駛?cè)隑;P(s3)；駛?cè)階;V(S2)P(s4)；駛?cè)隓;V(s3)；駛出D;V(s4);S：左轉(zhuǎn)P(s1);駛?cè)隒;P(s2)；駛?cè)隑;V(S1)P(s3)；駛?cè)階;V(s2)；駛出A;V(s3);

8．設(shè)系統(tǒng)中僅有一個(gè)資源類，其中共有M個(gè)資源實(shí)例，使用此類資源的進(jìn)程個(gè)數(shù)共有N個(gè)，它們所需資源最大量總和為S，試證明發(fā)生死鎖的必要條件是S3M+N。證明：假定發(fā)生死鎖，且參與死鎖的進(jìn)程個(gè)數(shù)為n(2￡n￡N)，參與死鎖的n個(gè)進(jìn)程已經(jīng)占有系統(tǒng)中全部M個(gè)資源實(shí)例，而還沒夠(因它們處于無限期等待狀態(tài))，每個(gè)進(jìn)程至少還需要一個(gè)資源實(shí)例，因而參與死鎖進(jìn)程所需要資源總量3M＋n。每個(gè)未參與死鎖進(jìn)程至少需要一個(gè)資源實(shí)例(若不需要?jiǎng)t不屬于N集合中，它們沒有參與死鎖是因?yàn)樗鼈冊(cè)诘玫讲⑹褂猛曩Y源后已經(jīng)將其釋放)，由于共有N-n個(gè)未參與死鎖的進(jìn)程，它們所需資源總量3N-n。由此可知，全部進(jìn)程所需要的資源總量S3(M+n)+(N-n)=M+N。

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