計(jì)算機(jī)操作系統(tǒng)復(fù)習(xí)(共20頁)

1、任何一個(gè)計(jì)算機(jī)系統(tǒng)都是由兩部分組成：計(jì)算機(jī)硬件和計(jì)算機(jī)軟件。計(jì)算機(jī)硬件通常是由中央處理機(jī)（運(yùn)算器和控制器）、存儲(chǔ)器、輸入(shr)設(shè)備和輸出設(shè)備等部件組成。計(jì)算機(jī)軟件包括(boku)系統(tǒng)軟件和應(yīng)用軟件。操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中的一個(gè)系統(tǒng)軟件，它是這樣一些(yxi)程序模塊的集合它們管理和控制計(jì)算機(jī)系統(tǒng)中的硬件及軟件資源，合理地組織計(jì)算機(jī)工作流程，以便有效地利用這些資源為用戶提供一個(gè)功能強(qiáng)大、使用方便和可擴(kuò)展的工作環(huán)境，從而在計(jì)算機(jī)與其用戶之間起到接口的作用。分時(shí)技術(shù)，就是把處理機(jī)的運(yùn)行時(shí)間分成很短的時(shí)間片，按時(shí)間片輪流把處理機(jī)分配給各聯(lián)機(jī)作業(yè)使用。若某個(gè)作業(yè)在分配給它的時(shí)間片內(nèi)不能完成其計(jì)算，則

2、該作業(yè)暫時(shí)中斷，把處理機(jī)讓給另一作業(yè)使用，等待下一輪時(shí)再繼續(xù)其運(yùn)行。由于計(jì)算機(jī)速度很快，作業(yè)運(yùn)行輪轉(zhuǎn)得很快，給每個(gè)用戶的印象是好像他獨(dú)占了一臺(tái)計(jì)算機(jī)。而每個(gè)用戶可以通過自己終端向系統(tǒng)發(fā)出各種操作控制命令，完成作業(yè)的運(yùn)行。分時(shí)系統(tǒng)一般采用時(shí)間片輪轉(zhuǎn)的方式，使一臺(tái)計(jì)算機(jī)為多個(gè)終端用戶服務(wù)。對(duì)每個(gè)用戶能保證足夠快的響應(yīng)時(shí)間，并提供交互會(huì)話能力。具有下述特點(diǎn)。(1) 交互性：首先， 用戶可以在程序動(dòng)態(tài)運(yùn)行情況下對(duì)其加以控制。其次，用戶上機(jī)提交作業(yè)方便。第三，分時(shí)系統(tǒng)還為用戶之間進(jìn)行合作提供方便。(2) 多用戶同時(shí)性：多個(gè)用戶同時(shí)在自己的終端上上機(jī)，共享CPU和其他資源，充分發(fā)揮系統(tǒng)的效率。(3) 獨(dú)立

3、性：客觀效果上用戶彼此間感覺不到有別人也在使用該臺(tái)計(jì)算機(jī)，如同自己獨(dú)占計(jì)算機(jī)一樣。處理機(jī)管理: 在多道程序或多用戶的情況下，要組織多個(gè)作業(yè)同時(shí)運(yùn)行，就要解決對(duì)處理機(jī)分配調(diào)度策略、分配實(shí)施和資源回收等問題。存儲(chǔ)管理: 對(duì)內(nèi)部存儲(chǔ)器進(jìn)行分配、保護(hù)和擴(kuò)充。(1) 內(nèi)存分配。如何分配內(nèi)存，以保證系統(tǒng)及各用戶程序的存儲(chǔ)區(qū)互不沖突。(2) 存儲(chǔ)保護(hù)。保證一道程序在執(zhí)行過程中不會(huì)有意或無意地破壞另一道程序，保證用戶程序不會(huì)破壞系統(tǒng)程序。(3) 內(nèi)存擴(kuò)充。當(dāng)用戶作業(yè)所需要的內(nèi)存量超過計(jì)算機(jī)系統(tǒng)所提供的內(nèi)存容量時(shí)，把內(nèi)部存儲(chǔ)器和外部存儲(chǔ)器結(jié)合起來管理，為用戶提供一個(gè)容量比實(shí)際內(nèi)存大得多的虛擬存儲(chǔ)器。設(shè)備管理:

4、(1) 通道、控制器、輸入輸出設(shè)備的分配和管理。設(shè)備管理的任務(wù)就是根據(jù)一定的分配策略，把通道、控制器和輸入輸出設(shè)備分配給請(qǐng)求輸入輸出操作的程序，并啟動(dòng)設(shè)備完成實(shí)際的輸入輸出操作。為了盡可能發(fā)揮設(shè)備和主機(jī)的并行工作能力，常需要采用虛擬技術(shù)和緩沖技術(shù)。(2) 設(shè)備獨(dú)立性。輸入輸出設(shè)備種類很多，使用方法各不相同。設(shè)備管理應(yīng)為用戶提供一個(gè)良好的界面，而不必去涉及具體的設(shè)備特性，以使用戶能方便、靈活地使用這些設(shè)備。計(jì)算機(jī)提供(tgng)的最基本功能是執(zhí)行指令。任何應(yīng)用程序都只有通過(tnggu)指令的執(zhí)行才能得以完成。執(zhí)行指令的基本過程分為兩步，即處理機(jī)從內(nèi)存把指令讀入的過程和執(zhí)行的過程。把指令的讀入和

5、執(zhí)行過程稱為一個(gè)執(zhí)行周期。在指令的執(zhí)行過程中或一條指令執(zhí)行結(jié)束時(shí)，盡管指令地址計(jì)數(shù)器中已指明了下一條被訪問指令的地址，但是，外部設(shè)備或計(jì)算機(jī)內(nèi)部可能會(huì)發(fā)來亟須處理的數(shù)據(jù)或其他緊急事件處理信號(hào)。這就需要處理機(jī)暫停(zn tn)正在執(zhí)行的程序，轉(zhuǎn)去處理相應(yīng)的緊急事件，待處理完畢后再返回原處繼續(xù)執(zhí)行，這一過程稱為中斷操作系統(tǒng)為用戶提供兩個(gè)接口界面。一個(gè)是系統(tǒng)為用戶提供的各種命令接口界面。用戶利用這些操作命令來組織和控制作業(yè)的執(zhí)行或管理計(jì)算機(jī)系統(tǒng)。另一個(gè)接口是系統(tǒng)調(diào)用。編程人員使用系統(tǒng)調(diào)用來請(qǐng)求操作系統(tǒng)提供服務(wù)。一般把處理機(jī)在用戶程序中執(zhí)行稱為用戶態(tài)，而把處理機(jī)在系統(tǒng)程序中執(zhí)行稱為系統(tǒng)態(tài)?，F(xiàn)代操作系統(tǒng)

6、的重要特點(diǎn)是程序的并發(fā)執(zhí)行，及系統(tǒng)所擁有的資源被共享和系統(tǒng)的用戶隨機(jī)地使用。操作系統(tǒng)的重要任務(wù)之一是使用戶充分、有效地利用系統(tǒng)資源。采用一個(gè)什么樣的概念，來描述計(jì)算機(jī)程序的執(zhí)行過程和作為資源分配的基本單位才能充分反映操作系統(tǒng)的執(zhí)行并發(fā)、資源共享及用戶隨機(jī)的特點(diǎn)呢？這個(gè)概念就是進(jìn)程。程序的順序執(zhí)行具有如下特點(diǎn)：(1) 順序性:程序順序執(zhí)行時(shí)，其執(zhí)行過程可看作一系列嚴(yán)格按程序規(guī)定的狀態(tài)轉(zhuǎn)移過程。(2) 封閉性:程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因素的影響。(3) 可再現(xiàn)性:只要輸入的初始條件相同，則無論何時(shí)重復(fù)執(zhí)行該程序都會(huì)得到相同的結(jié)果。多道程序系統(tǒng)中程序執(zhí)行環(huán)境三個(gè)特點(diǎn)：(1

7、) 獨(dú)立性: 每道程序都是邏輯上獨(dú)立的，它們之間不存在邏輯上的制約關(guān)系。(2) 隨機(jī)性: 在多道程序環(huán)境下，特別是在多用戶環(huán)境下，程序和數(shù)據(jù)的輸入與執(zhí)行開始時(shí)間都是隨機(jī)的。(3) 資源共享: 資源共享將導(dǎo)致對(duì)進(jìn)程執(zhí)行速度的制約。程序的并發(fā)執(zhí)行可進(jìn)一步分為兩種：第一種是多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行。由于資源的有限性，多道程序的并發(fā)執(zhí)行總是伴隨著資源的共享與競(jìng)爭(zhēng)。從而制約各道程序的執(zhí)行速度。而無法作到在微觀上，也就是在指令級(jí)上的同時(shí)執(zhí)行。因此，盡管多道程序的并發(fā)執(zhí)行在宏觀上是同時(shí)進(jìn)行的，但在微觀上仍是順序執(zhí)行的；第二種并發(fā)執(zhí)行是在某道程序的幾個(gè)程序段中（例如幾個(gè)程序），

8、包含著一部分可以同時(shí)執(zhí)行或順序顛倒執(zhí)行的代碼。程序的并發(fā)執(zhí)行可總結(jié)為：一組在邏輯上互相獨(dú)立的程序或程序段在執(zhí)行過程中，其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始的這種執(zhí)行方式。進(jìn)程和程序是兩個(gè)既有聯(lián)系又有區(qū)別的概念，它們的區(qū)別和關(guān)系可簡(jiǎn)述如下：(1) 進(jìn)程是一個(gè)動(dòng)態(tài)概念，而程序則是一個(gè)靜態(tài)概念。程序是指令的有序集合，沒有(mi yu)任何執(zhí)行的含義。而進(jìn)程(jnchng)則強(qiáng)調(diào)執(zhí)行過程，它動(dòng)態(tài)地被創(chuàng)建，并被調(diào)度(diod)執(zhí)行后消亡。(2) 進(jìn)程具有并行特征，而程序沒有。由進(jìn)程的定義可知，進(jìn)程具有并行特征的兩個(gè)方面，即獨(dú)立性和異步性。也就是說，在不考慮資

9、源共享的情況下，各進(jìn)程的執(zhí)行是獨(dú)立的，執(zhí)行速度是異步的。顯然，由于程序不反映執(zhí)行過程，所以不具有并行特征。(3) 進(jìn)程是競(jìng)爭(zhēng)計(jì)算機(jī)系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)自己的制約。這里，制約就是對(duì)進(jìn)程獨(dú)立性和異步性的限制。(4) 不同的進(jìn)程可以包含同一程序，只要該程序所對(duì)應(yīng)的數(shù)據(jù)集不同。進(jìn)程的靜態(tài)描述由三部分組成：進(jìn)程控制塊PCB，有關(guān)程序段和該程序段對(duì)其進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)集。進(jìn)程控制塊包含了有關(guān)進(jìn)程的描述信息、控制信息以及資源信息，是進(jìn)程動(dòng)態(tài)特征的集中反映。系統(tǒng)根據(jù)PCB感知進(jìn)程的存在和通過PCB中所包含的各項(xiàng)變量的變化，掌握進(jìn)程所處的狀態(tài)以達(dá)到控制進(jìn)程活動(dòng)的目的。由于進(jìn)程的PCB 是系統(tǒng)

10、感知進(jìn)程的唯一實(shí)體，因此，在幾乎所有的多道操作系統(tǒng)中，一個(gè)進(jìn)程的PCB結(jié)構(gòu)都是全部或部分常駐內(nèi)存的。任一進(jìn)程，都有一個(gè)自己的地址空間，把該空間稱為進(jìn)程空間或虛空間。進(jìn)程空間的大小只與處理機(jī)的位數(shù)有關(guān)。進(jìn)程空間被劃分為兩大部分，用戶程序在用戶空間內(nèi)執(zhí)行，而操作系統(tǒng)內(nèi)核程序則在進(jìn)程的系統(tǒng)空間內(nèi)執(zhí)行。為了防止用戶程序訪問系統(tǒng)空間，造成訪問出錯(cuò)，計(jì)算機(jī)系統(tǒng)還通過程序狀態(tài)寄存器等設(shè)置不同的執(zhí)行模式，即用戶模式和系統(tǒng)模式來進(jìn)行保護(hù)。人們也把用戶執(zhí)行模式和系統(tǒng)執(zhí)行模式分別稱為用戶態(tài)和系統(tǒng)態(tài)。一個(gè)進(jìn)程的生命期可以劃分為一組狀態(tài)，這些狀態(tài)刻劃了整個(gè)進(jìn)程。系統(tǒng)根據(jù)PCB 結(jié)構(gòu)中的狀態(tài)值控制進(jìn)程。在進(jìn)程的生命期內(nèi)，

11、一個(gè)進(jìn)程至少具有三種基本狀態(tài)，它們是：執(zhí)行狀態(tài)、等待狀態(tài)和就緒狀態(tài)。處于就緒狀態(tài)的進(jìn)程已經(jīng)得到除 CPU之外的其他資源，只要由調(diào)度得到處理機(jī)，便可立即投入執(zhí)行。在單CPU系統(tǒng)中，任一時(shí)刻處于執(zhí)行狀態(tài)的進(jìn)程只能有一個(gè)。只有處于就緒狀態(tài)的進(jìn)程經(jīng)調(diào)度選中之后才可進(jìn)入執(zhí)行狀態(tài)。進(jìn)程的執(zhí)行狀態(tài)又可進(jìn)一步劃分為用戶執(zhí)行狀態(tài)和系統(tǒng)執(zhí)行狀態(tài)。劃分用戶態(tài)和系統(tǒng)態(tài)最主要的原因是要把用戶程序和系統(tǒng)程序區(qū)分開來，以利于程序的共享和保護(hù)。進(jìn)程因等待某個(gè)事件發(fā)生而放棄處理機(jī)進(jìn)入等待狀態(tài)。等待狀態(tài)可根據(jù)等待事件的種類而進(jìn)一步劃分為不同的子狀態(tài)，例如內(nèi)存等待、設(shè)備等待、文件等待和數(shù)據(jù)等待等。這樣做的好處是系統(tǒng)控制簡(jiǎn)單，發(fā)現(xiàn)和

12、喚醒相應(yīng)的進(jìn)程較為容易。但系統(tǒng)中設(shè)置過多的狀態(tài)又會(huì)造成系統(tǒng)參數(shù)和狀態(tài)轉(zhuǎn)換過程的增加。進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建(chungjin)、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程(jnchng)高效率并發(fā)執(zhí)行(zhxng)和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。原語可分為兩類：一類是機(jī)器指令級(jí)的，其特點(diǎn)是執(zhí)行期間不允許中斷，在操作系統(tǒng)中，它是一個(gè)不可分割的基本單位。另一類是功能級(jí)的，其特點(diǎn)是作為原語的程序段不允許并發(fā)執(zhí)行。這兩類原語都在系統(tǒng)態(tài)下執(zhí)行用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。進(jìn)程創(chuàng)建:(1)

13、 由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建(2) 由父進(jìn)程創(chuàng)建，例如在層次結(jié)構(gòu)的系統(tǒng)中，父進(jìn)程創(chuàng)建子進(jìn)程以完成并行工作。由系統(tǒng)統(tǒng)一創(chuàng)建的進(jìn)程之間的關(guān)系是平等的，它們之間一般不存在資源繼承關(guān)系。而在父進(jìn)程創(chuàng)建的進(jìn)程之間則存在隸屬關(guān)系，且互相構(gòu)成樹型結(jié)構(gòu)的家族關(guān)系。屬于某個(gè)家族的一個(gè)進(jìn)程可以繼承其父進(jìn)程所擁有的資源。另外，無論是哪一種方式創(chuàng)建進(jìn)程，在系統(tǒng)生成時(shí)，都必須由操作系統(tǒng)創(chuàng)建一部分承擔(dān)系統(tǒng)資源分配和管理工作的系統(tǒng)進(jìn)程。創(chuàng)建原語掃描系統(tǒng)的PCB鏈表，在找到一定PCB表之后，填入調(diào)用者提供的有關(guān)參數(shù)，最后形成代表進(jìn)程的PCB結(jié)構(gòu)。這些參數(shù)包括：進(jìn)程名、進(jìn)程優(yōu)先級(jí)、進(jìn)程正文段起始地址、資源清單等。進(jìn)程(jnchng

14、)撤消: 以下幾種情況導(dǎo)致進(jìn)程(jnchng)被撤消：(1) 該進(jìn)程已完成所要求(yoqi)的功能而正常終止。(2) 由于某種錯(cuò)誤導(dǎo)致非正常終止。(3) 祖先進(jìn)程要求撤消某個(gè)子進(jìn)程。無論哪一種情況導(dǎo)致進(jìn)程被撤消，進(jìn)程都必須釋放它所占用的各種資源和PCB 結(jié)構(gòu)本身，以利于資源的有效利用。撤消原語首先檢查 PCB進(jìn)程鏈或進(jìn)程家族，尋找所要撤消的進(jìn)程是否存在。如果找到了所要撤消的進(jìn)程的 PCB結(jié)構(gòu)，則撤消原語釋放該進(jìn)程所占有的資源之后，把對(duì)應(yīng)的 PCB結(jié)構(gòu)從進(jìn)程鏈或進(jìn)程家族中摘下并返回給 PCB空隊(duì)列。如果被撤消的進(jìn)程有自己的子進(jìn)程，則撤消原語先撤消其子進(jìn)程的 PCB結(jié)構(gòu)并釋放子進(jìn)程所占用的資源之后

15、，再撤消當(dāng)前進(jìn)程的 PCB結(jié)構(gòu)和釋放其資源。阻塞原語在一個(gè)進(jìn)程期待某一事件發(fā)生，但發(fā)生條件尚不具備時(shí)，被該進(jìn)程自己調(diào)用來阻塞自己。阻塞原語在阻塞一個(gè)進(jìn)程時(shí)，由于該進(jìn)程正處于執(zhí)行狀態(tài)，故應(yīng)先中斷處理機(jī)和保存該進(jìn)程的CPU現(xiàn)場(chǎng)。然后將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，等待該事件的所有(suyu)進(jìn)程都將被喚醒。喚醒一個(gè)進(jìn)程有兩種方法：一種是由系統(tǒng)進(jìn)程喚醒。當(dāng)由系統(tǒng)進(jìn)程喚醒等待進(jìn)程時(shí)，系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生(fshng)并將“事件發(fā)生”這一消息通知等待進(jìn)程。從而使得該進(jìn)程因等待事件已發(fā)生而進(jìn)入就緒隊(duì)列。另一種

16、是由事件發(fā)生進(jìn)程喚醒。喚醒原語首先將被喚醒進(jìn)程從相應(yīng)的等待隊(duì)列中摘下，將被喚醒進(jìn)程置為就緒狀態(tài)之后，送入就緒隊(duì)列。在把被喚醒進(jìn)程送入就緒隊(duì)列之后，喚醒原語既可以返回原調(diào)用程序，也可以轉(zhuǎn)向進(jìn)程調(diào)度(diod)，以便讓調(diào)度程序有機(jī)會(huì)選擇一個(gè)合適的進(jìn)程執(zhí)行。把不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界部分（critical section ）或臨界區(qū)（critical region）。一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)稱為互斥。一組并發(fā)進(jìn)程互斥執(zhí)行時(shí)必須滿足如下準(zhǔn)則：(1)

17、不能假設(shè)各并發(fā)進(jìn)程的相對(duì)執(zhí)行速度。即各并發(fā)進(jìn)程享有平等的、獨(dú)立的競(jìng)爭(zhēng)共有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時(shí)，其他并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)。(2) 并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止(zzh)其他進(jìn)程進(jìn)入臨界區(qū)。(3) 并發(fā)(bngf)進(jìn)程中的若干個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入。(4) 并發(fā)進(jìn)程(jnchng)中的某個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。一次原語操作使得信號(hào)量sem減1，而一次原語操作將使得信號(hào)量sem加1。當(dāng)某個(gè)進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時(shí)，其他進(jìn)程如果執(zhí)行了原語操作，則該進(jìn)程并不像調(diào)用lock時(shí)那樣因進(jìn)不了臨界區(qū)

18、而返回到lock的起點(diǎn)，等以后重新執(zhí)行測(cè)試，而是在等待隊(duì)列中等待有其他進(jìn)程做原語操作釋放資源后，進(jìn)入臨界區(qū)，這時(shí)，原語的執(zhí)行才算真正結(jié)束。原語操作的主要?jiǎng)幼魇牵?1) sem減 1；(2) 若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；(3) 若sem減1后小于零，則該進(jìn)程被阻塞后與該信號(hào)相對(duì)應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。原語的操作主要?jiǎng)幼魇牵?1) sem加1；(2) 若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3) 若相加結(jié)果小于或等于零，則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。用信號(hào)量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：1) 設(shè) sem為互斥信號(hào)量，其取值范圍

19、(fnwi)為(1,0,-1)。其中(qzhng)sem=1表示(biosh)進(jìn)程PA和PB都未進(jìn)入類名為的臨界區(qū)，sem=0表示進(jìn)程PA或PB已進(jìn)入類名為的臨界區(qū)，sem=-1表示進(jìn)程PA和PB中，一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一個(gè)進(jìn)程等待進(jìn)入臨界區(qū)。2) 描述：PA：(sem)(sem)：PB：(sem)(sem)：把異步環(huán)境下的一組并發(fā)進(jìn)程，因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過程稱為進(jìn)程間的同步。具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間互相發(fā)送的信號(hào)稱為消息或事件。如果對(duì)一個(gè)消息或事件賦以唯一的消息名，則可用過程wait(消息名）表示進(jìn)程

20、等待合作進(jìn)程發(fā)來的消息，而用過程signal（消息名）表示向合作進(jìn)程發(fā)送消息。設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)（如圖3.14）。PA為發(fā)送進(jìn)程，PB為接收進(jìn)程。PA發(fā)送數(shù)據(jù)時(shí)調(diào)用發(fā)送過程deposit(data)，PB接收數(shù)據(jù)時(shí)調(diào)用過程remove(data)。且數(shù)據(jù)的發(fā)送和接收過程滿足如下條件：(1) 在PA至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長(zhǎng)等于緩沖區(qū)長(zhǎng)度）；（2) PA往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí)，至少有一個(gè)緩沖區(qū)是空的；（3) 由PA發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出（FIFO）方式排列。描述發(fā)送過程deposit(data)和接收過程remove(

21、data)。解：由題意可知，進(jìn)程PA調(diào)用的過程deposit(data)和進(jìn)程PB調(diào)用的過程remove(data)必須同步執(zhí)行，因?yàn)檫^程 deposit(data)的執(zhí)行結(jié)果是過程remove(data)的執(zhí)行條件，而當(dāng)緩沖隊(duì)列全部裝滿數(shù)據(jù)時(shí)，remove(data)的執(zhí)行結(jié)果又是deposit(data)的執(zhí)行條件，滿足同步定義。從而，按以下三步描述過程deposit(data)和remove(data)：（1) 設(shè)Bufempty為進(jìn)程PA的私用信號(hào)量，Buffull 為進(jìn)程PB的私用信號(hào)量；（2) 令Bufempty的初始值為n（n 為緩沖隊(duì)列的緩沖區(qū)個(gè)數(shù)），Buffull 的初始值為

22、0；（3) 描述：PA: deposit(data):begin local xP(Bufempty)；按FIFO方式選擇一個(gè)空緩沖區(qū)Buf(x)；Buf(x) dataBuf(x)置滿標(biāo)記(bioj)（Buffull）endPB: remove(data):Begin local x （Buffull）；按FIFO方式(fngsh)選擇一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)Buf(x)data Buf(x)Buf(x)置空標(biāo)記(bioj) （Bufempty）end把系統(tǒng)中使用某一類資源的進(jìn)程稱為該資源的消費(fèi)者，而把釋放同類資源的進(jìn)程稱為該資源的生產(chǎn)者。生產(chǎn)者-消費(fèi)者問題是一個(gè)同步問題。即生產(chǎn)者和消費(fèi)者之間滿

23、足如下條件：(1) 消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的；(2) 生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的。另外，由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程之間必須互斥執(zhí)行。由以上分析，設(shè)公用信號(hào)量mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥，設(shè)信號(hào)量avail為生產(chǎn)者進(jìn)程的私用信號(hào)量，信號(hào)量full為消費(fèi)者進(jìn)程的私用信號(hào)量。信號(hào)量avail表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號(hào)量full表示有界緩沖區(qū)中非空單元數(shù)，初值為0。信號(hào)量mutex表示可用有界緩沖區(qū)的個(gè)數(shù)，初值為 1。從而有：deposit(data):begin（avail）（mu

24、tex）送數(shù)據(jù)入緩沖區(qū)某單元（full）（mutex）endremove(data):begin （full） （mutex） 取緩沖區(qū)中某單元數(shù)據(jù) （avail） （mutex）end、原語的操作次序要非常小心。一般說來，由于原語是釋放資源的，所以可以以任意次序出現(xiàn)。但原語則不然，如果次序混亂，將會(huì)造成進(jìn)程之間的死鎖。通信(tng xn)（communication）意味著在進(jìn)程間傳送數(shù)據(jù)。操作系統(tǒng)可以被看作(kn zu)是各種進(jìn)程組成的。這些進(jìn)程都具有各自的獨(dú)立功能，且大多數(shù)被外部需要而啟動(dòng)執(zhí)行。一般來說，進(jìn)程間的通信根據(jù)通信內(nèi)容可以劃分為二種：即控制信息的傳送與大批量數(shù)據(jù)傳送。有時(shí)，也把

25、進(jìn)程(jnchng)間控制信息的交換稱為低級(jí)通信，而把進(jìn)程間大批量數(shù)據(jù)的交換稱為高級(jí)通信。在單機(jī)系統(tǒng)中，進(jìn)程間通信可分為4種形式：(1) 主從式；(2) 會(huì)話式；(3) 消息或郵箱機(jī)制；(4) 共享存儲(chǔ)區(qū)方式。死鎖，是指各并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。死鎖的起因是并發(fā)進(jìn)程的資源競(jìng)爭(zhēng)。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個(gè)數(shù)少于并發(fā)進(jìn)程所要求的該類資源數(shù)。產(chǎn)生死鎖的必要條件(1) 互斥條件。并發(fā)進(jìn)程所要求和占有的資源是不能同時(shí)被兩個(gè)以上進(jìn)程使用或操作的，

26、進(jìn)程對(duì)它所需要的資源進(jìn)行排他性控制。(2) 不剝奪條件。進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行剝奪，而只能由獲得該資源的進(jìn)程自己釋放。(3) 部分分配。進(jìn)程每次申請(qǐng)它所需要的一部分資源，在等待新資源的同時(shí)繼續(xù)占用已分配到的資源。(4) 環(huán)路條件。存在一種進(jìn)程循環(huán)鏈，鏈中每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求。顯然，只要使上述4個(gè)必要條件中的某一個(gè)不滿足，則死鎖就可以排除。解決死鎖的方法一般可分為預(yù)防、避免、檢測(cè)與恢復(fù)等三種。引入線程主要是為了提高系統(tǒng)的執(zhí)行效率，減少處理機(jī)的空轉(zhuǎn)時(shí)間和調(diào)度切換（保護(hù)現(xiàn)場(chǎng)信息）的時(shí)間，以及便于系統(tǒng)管理。一個(gè)進(jìn)程內(nèi)的基本調(diào)度單位稱為線程或稱為輕權(quán)

27、進(jìn)程（Light weight process）進(jìn)程是資源分配的基本單位。所有與該進(jìn)程有關(guān)的資源，例如打印機(jī)，輸入緩沖隊(duì)列等，都被記錄在進(jìn)程控制塊PCB中。以表示該進(jìn)程擁有這些資源或正在使用它們。另外，進(jìn)程也是搶占處理機(jī)的調(diào)度單位，它擁有一個(gè)完整的虛擬地址空間（后述）。與進(jìn)程相對(duì)應(yīng)，線程與資源分配無關(guān)，它屬于某一個(gè)進(jìn)程，并與進(jìn)程內(nèi)的其他線程一起共享進(jìn)程的資源。再者，當(dāng)進(jìn)程發(fā)生調(diào)度時(shí)，不同的進(jìn)程擁有不同的虛擬地址空間，而同一進(jìn)程內(nèi)的不同線程共享同一地址空間。線程只由相關(guān)堆棧（系統(tǒng)?；蛴脩魲＃┘拇嫫骱途€程控制表TCB組成。發(fā)生進(jìn)程切換與發(fā)生線程切換時(shí)相比較，進(jìn)程切換時(shí)將涉及到有關(guān)資源指針的保存以及

28、地址空間的變化等問題，線程切換時(shí)，由于同一進(jìn)程內(nèi)的線程共享資源和地址空間，將不涉及資源信息的保存和地址變化問題，從而減少了操作系統(tǒng)的開銷時(shí)間。而且，進(jìn)程的調(diào)度與切換都是由操作系統(tǒng)內(nèi)核完成，而線程則既可由操作系統(tǒng)內(nèi)核完成，也可由用戶程序進(jìn)行。使用線程的最大好處是在有多個(gè)任務(wù)需要處理(chl)機(jī)處理時(shí)，減少處理機(jī)的切換時(shí)間；而且，線程的創(chuàng)建和結(jié)束所需要的系統(tǒng)開銷也比進(jìn)程(jnchng)的創(chuàng)建和結(jié)束要小得多。由此，可以推出最適合使用線程的系統(tǒng)是多處理機(jī)系統(tǒng)。在多處理機(jī)系統(tǒng)中，同一(tngy)用戶程序可以根據(jù)不同的功能劃分為不同的線程，放在不同的處理機(jī)上執(zhí)行。在用戶程序可以按功能劃分為不同的小段時(shí)，單

29、處理機(jī)系統(tǒng)也可因使用線程而簡(jiǎn)化程序的結(jié)構(gòu)和提高執(zhí)行效率。線程的兩個(gè)基本類型是：用戶級(jí)線程和系統(tǒng)級(jí)線程(核心級(jí)線型)。Windows 中創(chuàng)建 進(jìn)程的函數(shù)是CreateProcess.Windows 中創(chuàng)建線程的函數(shù)：(1)使用Windows系統(tǒng)調(diào)用函數(shù)CreateThread; (2)使用c/c+運(yùn)行庫中的創(chuàng)建線程的函數(shù)，它們是： _beginthread 和_beginthreadex; (3)使用MFC庫中的創(chuàng)建線程的函數(shù)AfxBeginThread，它有兩個(gè)重載版本，MF可以創(chuàng)建兩類線程：用戶界面線程和工作者線程。用戶界面線程有消息循環(huán)，工作者線程無消息循環(huán)。衡量調(diào)度策略的最常用的幾個(gè)指標(biāo)

30、是：周轉(zhuǎn)時(shí)間、吞吐率、響應(yīng)時(shí)間以及設(shè)備利用率等。周轉(zhuǎn)時(shí)間是指將一個(gè)作業(yè)提交給計(jì)算機(jī)系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。吞吐率是指在給定的時(shí)間內(nèi)，一個(gè)計(jì)算機(jī)系統(tǒng)所完成的總工作量。響應(yīng)時(shí)間則是指從用戶向計(jì)算機(jī)發(fā)出一個(gè)命令到計(jì)算機(jī)把相應(yīng)的執(zhí)行結(jié)果返回給用戶所需要的時(shí)間。設(shè)備利用率主要指輸入輸出設(shè)備的使用情況。一般來說，處理機(jī)調(diào)度可以分為4級(jí)：(1) 作業(yè)調(diào)度(2) 交換調(diào)度(3) 進(jìn)程調(diào)度(4) 線程調(diào)度。周轉(zhuǎn)時(shí)間：作業(yè)i的周轉(zhuǎn)時(shí)間Ti為Ti=Tei-Tsi其中Tei為作業(yè)i的完成時(shí)間，Tsi為作業(yè)的提交時(shí)間。作業(yè)的周轉(zhuǎn)時(shí)間包含了兩個(gè)部分，即等待時(shí)間和執(zhí)行時(shí)間。為了更進(jìn)一步反映調(diào)度性能，使用

31、帶權(quán)周轉(zhuǎn)時(shí)間的概念。帶權(quán)周轉(zhuǎn)時(shí)間是作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)執(zhí)行時(shí)間的比：Wi=Ti/Tri進(jìn)程調(diào)度的功能：(1) 記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況; (2) 選擇占有處理機(jī)的進(jìn)程; (3) 進(jìn)行進(jìn)程上下文切換引起進(jìn)程調(diào)度的原因有以下幾類：(1) 正在執(zhí)行的進(jìn)程執(zhí)行完畢。這時(shí)，如果不選擇新的就緒進(jìn)程執(zhí)行，將浪費(fèi)處理機(jī)資源。(2) 執(zhí)行中進(jìn)程自己調(diào)用阻塞原語將自己阻塞起來進(jìn)入睡眠等待狀態(tài)。(3) 執(zhí)行中進(jìn)程調(diào)用了P原語操作，從而因資源不足而被阻塞；或調(diào)用了V原語操作激活了等待資源的進(jìn)程隊(duì)列。(4) 執(zhí)行中進(jìn)程提出IO請(qǐng)求后被阻塞。(5) 在分時(shí)系統(tǒng)中時(shí)間(shjin)片已經(jīng)用完。(6) 在執(zhí)行(zhxng)

32、完系統(tǒng)(xtng)調(diào)用，在系統(tǒng)程序返回用戶進(jìn)程時(shí)，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶進(jìn)程執(zhí)行。以上都是在CPU執(zhí)行不可剝奪方式下所引起進(jìn)程調(diào)度的原因。在CPU執(zhí)行方式是可剝奪時(shí)，還有：(7) 就緒隊(duì)列中的某進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級(jí)，從而也將引發(fā)進(jìn)程調(diào)度。所謂可剝奪方式，即就緒隊(duì)列中一旦有優(yōu)先級(jí)高于當(dāng)前執(zhí)行進(jìn)程優(yōu)先級(jí)的進(jìn)程存在時(shí)，便立即發(fā)生進(jìn)程調(diào)度，轉(zhuǎn)讓處理機(jī)。而非剝奪方式或不可剝奪方式即使在就緒隊(duì)列存在有優(yōu)先級(jí)高于當(dāng)前執(zhí)行進(jìn)程時(shí)，當(dāng)前進(jìn)程仍將繼續(xù)占有處理機(jī)，直到該進(jìn)程自己因調(diào)用原語操作或等待IO而進(jìn)入阻塞、睡眠狀態(tài)，或時(shí)間片用完時(shí)才重新發(fā)生調(diào)度讓出處理機(jī)。進(jìn)程調(diào)度

33、性能的衡量方法可分為定性和定量?jī)煞N。在定性衡量方面，首先是調(diào)度的可靠性。另外，簡(jiǎn)潔性也是衡量進(jìn)程調(diào)度的一個(gè)重要指標(biāo)。進(jìn)程調(diào)度的定量評(píng)價(jià)包括CPU的利用率評(píng)價(jià)、進(jìn)程在就緒隊(duì)列中的等待時(shí)間與執(zhí)行時(shí)間之比等。先來先服務(wù)（FCFS）調(diào)度算法: 將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理。優(yōu)點(diǎn)：該算法在一般意義下是公平的。即每個(gè)作業(yè)或進(jìn)程都按照它們?cè)陉?duì)列中等待時(shí)間長(zhǎng)短來決定它們是否優(yōu)先享受服務(wù)。缺點(diǎn)：對(duì)于那些執(zhí)行時(shí)間較短的作業(yè)或進(jìn)程來說，如果它們?cè)谀承﹫?zhí)行時(shí)間很長(zhǎng)的作業(yè)或進(jìn)程之后到達(dá)，則它們將等待很長(zhǎng)時(shí)間。輪轉(zhuǎn)法的基本思路是讓每個(gè)進(jìn)程在就緒隊(duì)列中的等待

34、時(shí)間與享受服務(wù)的時(shí)間成比例。輪轉(zhuǎn)法的基本概念是將CPU的處理時(shí)間分成固定大小的時(shí)間片。如果一個(gè)進(jìn)程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時(shí)間片，但未完成要求的任務(wù)，則它自行釋放自己所占有的CPU而排到就緒隊(duì)列的末尾，等待下一次調(diào)度。同時(shí)，進(jìn)程調(diào)度程序又去調(diào)度當(dāng)前就緒隊(duì)列中的第一個(gè)進(jìn)程或作業(yè)。在輪轉(zhuǎn)法中，加入到就緒隊(duì)列的進(jìn)程有三種情況，一種是分給它的時(shí)間片用完，但進(jìn)程還未完成，回到就緒隊(duì)列的末尾等待下次調(diào)度去繼續(xù)執(zhí)行。另一種情況是分給該進(jìn)程的時(shí)間片并未用完，只是因?yàn)檎?qǐng)求IO或由于進(jìn)程的互斥與同步關(guān)系而被阻塞。當(dāng)阻塞解除之后再回到就緒隊(duì)列。再有一種情況就是新創(chuàng)建進(jìn)程進(jìn)入就緒隊(duì)列。多級(jí)反饋輪轉(zhuǎn)法: 對(duì)上面

35、三種情況的進(jìn)程區(qū)別對(duì)待，給予不同的優(yōu)先級(jí)和時(shí)間片。多級(jí)反饋輪轉(zhuǎn)法與優(yōu)先級(jí)法在原理上的區(qū)別是，一個(gè)進(jìn)程在它執(zhí)行結(jié)束之前，可能需要反復(fù)多次通過反饋循環(huán)執(zhí)行，而不是優(yōu)先級(jí)法中的一次執(zhí)行。確定優(yōu)先級(jí)的方法可分為靜態(tài)法和動(dòng)態(tài)法。靜態(tài)法根據(jù)作業(yè)或進(jìn)程的靜態(tài)特性，在作業(yè)或進(jìn)程開始執(zhí)行之前就確定它們的優(yōu)先級(jí)，一旦開始執(zhí)行之后就不能改變。動(dòng)態(tài)法把作業(yè)或進(jìn)程的靜態(tài)特性和動(dòng)態(tài)特性結(jié)合起來確定作業(yè)或進(jìn)程的優(yōu)先級(jí)，隨著作業(yè)或進(jìn)程的執(zhí)行過程，其優(yōu)先級(jí)不斷變化。進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)一般根據(jù)以下(yxi)原則確定：(1) 根據(jù)進(jìn)程(jnchng)占有CPU時(shí)間的長(zhǎng)短來決定。一個(gè)進(jìn)程占有處理機(jī)的時(shí)間愈長(zhǎng)，則在被阻塞之后(zhhu)

36、再次獲得調(diào)度的優(yōu)先級(jí)就越低，反之，其獲得調(diào)度的可能性就會(huì)越大。(2) 根據(jù)就緒進(jìn)程等待CPU的時(shí)間長(zhǎng)短來決定。一個(gè)就緒進(jìn)程在就緒隊(duì)列中等待的時(shí)間越長(zhǎng)，則它獲得調(diào)度選中的優(yōu)先級(jí)就越高。最短作業(yè)優(yōu)先法（SJF）就是選擇那些估計(jì)需要執(zhí)行時(shí)間最短的作業(yè)投入執(zhí)行，為它們創(chuàng)建進(jìn)程和分配資源。優(yōu)點(diǎn)：使得系統(tǒng)在同一時(shí)間內(nèi)處理的作業(yè)個(gè)數(shù)最多，從而吞吐量也就大于其他調(diào)度方式。缺點(diǎn)：對(duì)于一個(gè)不斷有作業(yè)進(jìn)入的批處理系統(tǒng)來說，最短作業(yè)優(yōu)先法有可能使得那些長(zhǎng)作業(yè)永遠(yuǎn)得不到調(diào)度執(zhí)行的機(jī)會(huì)。最高響應(yīng)比優(yōu)先法（HRN）是對(duì)FCFS方式和SJF 方式的一種綜合平衡。HRN調(diào)度策略同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長(zhǎng)短和估計(jì)需要的執(zhí)行時(shí)間

37、長(zhǎng)短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。響應(yīng)比R定義如下：R=(W+T)/T=1+W/T其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，W為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)間。每當(dāng)要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。馮諾依曼體系結(jié)構(gòu)計(jì)算機(jī)的核心思想：存儲(chǔ)程序控制C語言的編譯鏈接過程要把我們編寫的一個(gè)c程序(源代碼)轉(zhuǎn)換成可以在硬件上運(yùn)行的程序(可執(zhí)行代碼)，需要進(jìn)行編譯和鏈接。編譯就是把文本形式源代碼翻譯為機(jī)器語言形式的目標(biāo)文件的過程。鏈接是把目標(biāo)文件、操作系統(tǒng)的啟動(dòng)代碼和用到的庫文件進(jìn)行組織形成最終生成可執(zhí)行代碼的過程。在虛擬空間中，除了有與PE文件中.text/.data等

38、各段相對(duì)應(yīng)的存儲(chǔ)空間外，還包括兩種特殊的地址空間：1、棧區(qū)（stack） 存放函數(shù)的參數(shù)變量、局部變量、函數(shù)返回地址等。在多線程環(huán)境中，每個(gè)線程有自己的棧。棧由系統(tǒng)自動(dòng)管理，但經(jīng)常成為黑客攻擊目標(biāo)緩沖區(qū)溢出。棧是向低地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)2、堆區(qū)（heap） 進(jìn)程創(chuàng)建時(shí)，系統(tǒng)會(huì)為進(jìn)程創(chuàng)建一個(gè)堆并負(fù)責(zé)管理 和維護(hù)，我們平常進(jìn)行的動(dòng)態(tài)內(nèi)存分配都是在默認(rèn)堆中進(jìn)行的。但程序員可以在虛擬地址空間的空閑地帶創(chuàng)建和管理自己的堆。堆也可能成為黑客攻擊的對(duì)象。堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)鏈接庫(DLL)與靜態(tài)鏈接庫(Lib)靜態(tài)鏈接庫：鏈接時(shí)與我們自己的目標(biāo)程序組裝成一個(gè)模塊動(dòng)態(tài)鏈接庫：(1)啟動(dòng)時(shí)由OS動(dòng)態(tài)加載

39、到進(jìn)程的虛擬地址空間中（通常在高地址區(qū))(2)在程序執(zhí)行過程中執(zhí)行LoadLibrary函數(shù)加載到進(jìn)程的虛擬地址空間中進(jìn)程虛擬存儲(chǔ)空間分為內(nèi)核(ni h)空間與用戶空間用戶空間主要(zhyo)包括各個(gè)模塊映像空間以及?？臻g(kngjin)和堆空間每個(gè)模塊都有自己的代碼段、數(shù)據(jù)段每個(gè)線程有自己的棧空閑空間可用于程序運(yùn)行時(shí)動(dòng)態(tài)分配內(nèi)存和加載動(dòng)態(tài)鏈接庫等用途，但低64K和高64K不能使用。模塊的每個(gè)段的映像地址和大小都是頁面大小的整數(shù)倍虛擬內(nèi)存塊的類型有：映像、映射、私有、空閑虛擬內(nèi)存塊的保護(hù)屬性有：執(zhí)行、讀、寫、寫入時(shí)拷貝把虛擬空間中已鏈接和劃分好的內(nèi)容裝入內(nèi)存，并將虛擬地址映射為內(nèi)存地址的問題，

40、稱之為地址重定位或地址映射。地址映射就是要建立虛擬地址與內(nèi)存地址的關(guān)系。實(shí)現(xiàn)地址重定位或地址映射的方法有兩種：靜態(tài)地址重定位和動(dòng)態(tài)地址重定位。靜態(tài)地址重定位(static address relocation)是在虛擬空間程序執(zhí)行之前由裝配程序完成地址映射工作。動(dòng)態(tài)地址重定位(dynamic address relocation)是在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前，將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址。動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成。動(dòng)態(tài)重定位的主要優(yōu)點(diǎn)有：可以對(duì)內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)；有利于程序段的共享。為了有效合理地利用內(nèi)存，設(shè)計(jì)內(nèi)存的分配和回收方法時(shí)，

41、必須考慮和確定以下幾種策略和數(shù)據(jù)結(jié)構(gòu)：(1) 分配結(jié)構(gòu)：登記內(nèi)存使用情況，供分配程序使用的表格與鏈表。例如內(nèi)存空閑區(qū)表、空閑區(qū)隊(duì)列等。(2) 放置策略：確定調(diào)入內(nèi)存的程序和數(shù)據(jù)在內(nèi)存中的位置。這是一種選擇內(nèi)存空閑區(qū)的策略。(3) 交換策略：在需要將某個(gè)程序段和數(shù)據(jù)調(diào)入內(nèi)存時(shí)，如果內(nèi)存中沒有足夠的空閑區(qū)，由交換策略來確定把內(nèi)存中的哪些程序段和數(shù)據(jù)段調(diào)出內(nèi)存，以便騰出足夠的空間。(4) 調(diào)入策略：外存中的程序段和數(shù)據(jù)段什么時(shí)間按什么樣的控制方式進(jìn)入內(nèi)存。調(diào)入策略與5.1.3節(jié)中所述內(nèi)外存數(shù)據(jù)流動(dòng)控制方式有關(guān)。(5) 回收策略：回收策略包括二點(diǎn)，一是回收的時(shí)機(jī)，二是對(duì)所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存

42、空閑區(qū)的調(diào)整。分區(qū)管理的基本原理是給每一個(gè)內(nèi)存中的進(jìn)程劃分一塊適當(dāng)大小的存儲(chǔ)區(qū)，以連續(xù)存儲(chǔ)各進(jìn)程的程序和數(shù)據(jù)，使各進(jìn)程得以并發(fā)執(zhí)行。按分區(qū)的時(shí)機(jī)，分區(qū)管理可以分為固定分區(qū)和動(dòng)態(tài)分區(qū)兩種方法。固定分區(qū)法就是把內(nèi)存區(qū)固定地劃分為若干個(gè)大小不等的區(qū)域。分區(qū)劃分的原則由一般系統(tǒng)操作員或操作系統(tǒng)決定。分區(qū)一旦劃分結(jié)束，在整個(gè)執(zhí)行過程中每個(gè)分區(qū)的長(zhǎng)度和內(nèi)存的總分區(qū)個(gè)數(shù)將保持不變。系統(tǒng)對(duì)內(nèi)存的管理和控制通過數(shù)據(jù)結(jié)構(gòu)分區(qū)說明表進(jìn)行，分區(qū)說明表說明各分區(qū)號(hào)、分區(qū)大小、起始地址和是否是空閑區(qū)(分區(qū)狀態(tài))。內(nèi)存的分配釋放、存儲(chǔ)保護(hù)以及地址變換等都通過分區(qū)說明表進(jìn)行。動(dòng)態(tài)分區(qū)(fn q)法在作業(yè)執(zhí)行前并不建立分區(qū)，分

43、區(qū)的建立是在作業(yè)的處理過程中進(jìn)行的，且其大小可隨作業(yè)或進(jìn)程對(duì)內(nèi)存的要求而改變。這就改變了固定分區(qū)法中那種即使是小作業(yè)也要占據(jù)大分區(qū)的浪費(fèi)現(xiàn)象，從而提高了內(nèi)存的利用率。采用(ciyng)動(dòng)態(tài)分區(qū)法，在系統(tǒng)初啟時(shí)，除了操作系統(tǒng)中常駐內(nèi)存部分之外，只有一個(gè)空閑分區(qū)(fn q)。隨后，分配程序?qū)⒃搮^(qū)依次劃分給調(diào)度選中的作業(yè)或進(jìn)程。隨著進(jìn)程的執(zhí)行，會(huì)出現(xiàn)一系列的分配和釋放。會(huì)出現(xiàn)一些新的小空閑區(qū)，如果被回收分區(qū)有和它鄰接的空閑分區(qū)存在，則要進(jìn)行合并。動(dòng)態(tài)分區(qū)時(shí)的分配方法從可用表或自由鏈中尋找空閑區(qū)的常用方法有三種：最先適應(yīng)法FF(first fit algorithm)、最佳適應(yīng)法BF(best fit

44、 algorithm)、最壞適應(yīng)法WF(worst fit algorithm)幾種分配算法的比較搜索速度：最先適應(yīng)算法最佳。盡管最佳適應(yīng)算法或最壞適應(yīng)算法看上去能很快找到一個(gè)最適合的或最大的空閑區(qū)，但后兩種算法都要求首先把不同大小的空閑區(qū)按其大小進(jìn)行排隊(duì)，這實(shí)際上是對(duì)所有空閑區(qū)進(jìn)行一次搜索。回收過程：最先適應(yīng)算法最佳。因?yàn)槭褂米钕冗m應(yīng)算法回收某一空閑區(qū)時(shí)，無論被釋放區(qū)是否與空閑區(qū)相鄰，都不用改變?cè)搮^(qū)在可用表或自由鏈中的位置，只需修改其大小或起始地址。而最佳適應(yīng)算法和最壞適應(yīng)算法都必須重新調(diào)整該區(qū)的位置。最先適應(yīng)算法盡可能地利用低地址空間，保證高地址有較大的空閑區(qū)來放置要求內(nèi)存較多的進(jìn)程或作業(yè)

45、。最佳適應(yīng)法找到的空閑區(qū)最佳，用最佳適應(yīng)法找到的空閑區(qū)或者是正好等于用戶請(qǐng)求的大小或者是能滿足用戶要求的最小空閑區(qū)。盡管最佳適應(yīng)法能選出最適合用戶要求的可用空閑區(qū)，但這樣做在某些情況下并不一定能提高內(nèi)存的利用率。最壞適應(yīng)算法選擇最大的空閑區(qū)來滿足用戶要求，以期分配后的剩余部分仍能進(jìn)行再分配，少留碎片空閑區(qū)分區(qū)存儲(chǔ)管理的主要優(yōu)缺點(diǎn)分區(qū)存儲(chǔ)管理的主要優(yōu)點(diǎn)實(shí)現(xiàn)了多個(gè)作業(yè)或進(jìn)程對(duì)內(nèi)存的共享，有助于多道程序設(shè)計(jì)，從而提高了系統(tǒng)的資源利用率。該方法要求的硬件支持少，管理算法簡(jiǎn)單，因而實(shí)現(xiàn)容易。主要(zhyo)缺點(diǎn)有內(nèi)存利用率仍然不高。和單一連續(xù)分配算法一樣，存儲(chǔ)器中可能含有從未用過的信息。而且，還存在著嚴(yán)

46、重的碎小(su xio)空閑區(qū)(碎片(su pin)不能利用的問題，這更進(jìn)一步影響了內(nèi)存的利用率。作業(yè)或進(jìn)程的大小受分區(qū)大小控制，除非配合采用覆蓋和交換技術(shù)。無法實(shí)現(xiàn)各分區(qū)間的信息共享。交換與覆蓋的區(qū)別：(1)交換不要求程序員給出程序段之間的覆蓋結(jié)構(gòu)。(2)交換主要是在進(jìn)程或作業(yè)之間進(jìn)行，而覆蓋則主要在同一個(gè)作業(yè)或進(jìn)程內(nèi)進(jìn)行。(3)覆蓋只能覆蓋那些與覆蓋程序段無關(guān)的程序段。頁式管理的基本原理如下：(1)各進(jìn)程的虛擬空間被劃分成若干個(gè)長(zhǎng)度相等的頁(page)。經(jīng)過頁劃分之后，進(jìn)程的虛地址變?yōu)轫撎?hào)p與頁內(nèi)地址w所組成。(2)頁式管理把內(nèi)存空間按頁的大小劃分為片或頁面(page frame)。(3)

47、頁式虛擬地址變換為內(nèi)存頁面物理地址的方法:頁式管理把頁式虛地址與內(nèi)存頁面物理地址建立一一對(duì)應(yīng)的頁表，并用相應(yīng)的硬件地址變換機(jī)構(gòu)，來解決離散地址變換問題。(4)頁式管理采用請(qǐng)求調(diào)頁或預(yù)調(diào)頁技術(shù)實(shí)現(xiàn)了內(nèi)外存儲(chǔ)器的統(tǒng)一管理。(5)頁式管理時(shí)把內(nèi)存頁面的分配與回收已和頁面淘汰技術(shù)及缺頁處理技術(shù)結(jié)合起來。靜態(tài)頁面管理方法是在進(jìn)程開始執(zhí)行之前，把該作業(yè)或進(jìn)程的程序段和數(shù)據(jù)全部裝入內(nèi)存的各個(gè)頁面中，并通過頁表(page mapping table)和硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)虛擬地址到內(nèi)存物理地址的地址映射。動(dòng)態(tài)頁式管理方法是在作業(yè)或進(jìn)程開始執(zhí)行之前，都不把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性地全部裝入內(nèi)存，而只裝入

48、被認(rèn)為是經(jīng)常反復(fù)執(zhí)行和調(diào)用的工作區(qū)部分。其他部分則在執(zhí)行過程中動(dòng)態(tài)裝入。頁面分配與回收涉及到三個(gè)主要數(shù)據(jù)結(jié)構(gòu)：(1)頁表：最簡(jiǎn)單的頁表由頁號(hào)與頁面號(hào)組成。頁式管理時(shí)每個(gè)進(jìn)程至少擁有一個(gè)頁表。(2)請(qǐng)求表：用來確定作業(yè)或進(jìn)程的虛擬空間的各頁在內(nèi)存中的實(shí)際對(duì)應(yīng)位置。整個(gè)系統(tǒng)只有一張請(qǐng)求表。(3)存儲(chǔ)頁面表：存儲(chǔ)頁面表也是整個(gè)系統(tǒng)一張，存儲(chǔ)頁面表指出內(nèi)存各頁面是否已被分配出去，以及未分配頁面的總數(shù)。存儲(chǔ)頁面表有兩種構(gòu)成方法:位示圖法和空閑頁面鏈的方法。頁面分配算法：請(qǐng)求表給出進(jìn)程或作業(yè)要求的頁面數(shù)。由存儲(chǔ)頁面表檢查是否有足夠的空閑頁面。如果沒有，則本次無法分配。如果有則首先分配設(shè)置頁表，并填寫請(qǐng)求表

49、中的相應(yīng)表項(xiàng)后，按一定的查找算法、搜索出所要求的空閑頁面，并將對(duì)應(yīng)的頁面號(hào)填入頁表中。圖5.18給出了上述頁面分配算法的流程圖。地址變換：規(guī)定怎樣由頁號(hào)和頁內(nèi)相對(duì)地址變換到內(nèi)存物理地址的問題。舉例說明地址變換過程。圖5.19取一個(gè)數(shù)據(jù)或指令至少要訪問內(nèi)存兩次以上。一次訪問頁表以確定所取數(shù)據(jù)或指令的物理地址，另一次是根據(jù)地址取數(shù)據(jù)或指令。這比通常執(zhí)行指令的速度慢了一倍。說明動(dòng)態(tài)頁式管理中頁表結(jié)構(gòu)(jigu)中每一項(xiàng)的用途或含意，圖5.22。包含頁號(hào)、頁面號(hào)、中斷位、起始地址(dzh)、改變位抖動(dòng)(dudng)(thrashing)現(xiàn)象：剛被調(diào)出內(nèi)存的頁又要馬上被調(diào)回內(nèi)存，調(diào)回內(nèi)存不久又馬上被調(diào)出

50、內(nèi)存，如此反復(fù)的這種現(xiàn)象被稱為抖動(dòng)(thrashing)現(xiàn)象。動(dòng)態(tài)頁式管理的流程圖如圖5.23所示。請(qǐng)求頁式管理中的置換算法在內(nèi)存中沒有空閑頁面時(shí)被調(diào)用。它的目的是選出一個(gè)被淘汰的頁面。如果內(nèi)存中有足夠的空閑頁面存放所調(diào)入的頁，則不必使用置換算法。把內(nèi)存和外存統(tǒng)一管理的真正目的是把那些被訪問概率非常高的頁存放在內(nèi)存中。因此，置換算法應(yīng)該置換那些被訪問概率最低的頁，將它們移出內(nèi)存。幾種常用的置換算法：隨機(jī)淘汰算法(random glongram)：在系統(tǒng)設(shè)計(jì)人員認(rèn)為無法確定哪些頁被訪問的概率較低時(shí)，隨機(jī)地選擇某個(gè)用戶的頁面并將其換出將是一種明智的作法。輪轉(zhuǎn)法(round robin)： 輪轉(zhuǎn)法循

51、回?fù)Q出內(nèi)存可用區(qū)內(nèi)一個(gè)可以被換出的頁，無論該頁是剛被換進(jìn)或已換進(jìn)內(nèi)存很長(zhǎng)時(shí)間。先進(jìn)先出算法(FIFO)：FIFO算法總是選擇在內(nèi)存駐留時(shí)間最長(zhǎng)的一頁將其淘汰。FIFO算法認(rèn)為先調(diào)入內(nèi)存的頁不再被訪問的可能性要比其他頁大，因而選擇最先調(diào)入內(nèi)存的頁換出。最近最久未使用頁面置換算法(least recently used)。理想型淘汰算法(OPT)：淘汰在訪問串中再也不出現(xiàn)或離當(dāng)前最遠(yuǎn)的位置上出現(xiàn)的頁頁面置換算法中的FIFO算法的缺點(diǎn)：內(nèi)存利用率不高。陷阱現(xiàn)象（Belady現(xiàn)象）。Belady現(xiàn)象：分配的頁面數(shù)增多，缺頁次數(shù)反而增加的奇怪現(xiàn)象。FIFO算法頁面變化情況舉例圖5.25，缺頁率計(jì)算 頁式

52、管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：它不要求進(jìn)程的程序段和數(shù)據(jù)在內(nèi)存中連續(xù)存放，有效地解決了碎片問題。提供了內(nèi)存和外存統(tǒng)一管理的方式，用戶可利用的存儲(chǔ)空間增加。提高了主存的利用率，有利于組織多道程序執(zhí)行主要缺點(diǎn)：要求有相應(yīng)的硬件支持。例如地址變換機(jī)構(gòu)，缺頁中斷和選擇淘汰頁面等都要求有硬件支持。增加了機(jī)器成本。增加了系統(tǒng)開銷，例如缺頁中斷處理等。請(qǐng)求調(diào)頁的算法如選擇不當(dāng)，有可能產(chǎn)生抖動(dòng)現(xiàn)象。雖然消除了碎片，但每個(gè)進(jìn)程的最后一頁內(nèi)總有一部分空間得不到利用。如果頁面較大，這一部分的損失仍然較大。段式虛存空間段式管理把一個(gè)(y )進(jìn)程的虛地址空間設(shè)計(jì)成二維結(jié)構(gòu)，即段號(hào)s與段內(nèi)相對(duì)(xingdu)地址w。對(duì)段式虛地址(dzh)空間的訪問包括兩個(gè)部分：段名和段內(nèi)地址。段號(hào)與段號(hào)之間無順序關(guān)系。段的長(zhǎng)度是不固定的，段長(zhǎng)可動(dòng)態(tài)增長(zhǎng)。每個(gè)段定義一組邏輯上完整的程序或數(shù)據(jù)。每個(gè)段是一個(gè)首地址為零的、連續(xù)的一維線性空間。段式管理的內(nèi)存分配與釋放：段式管理的內(nèi)存分配與釋放在作業(yè)或進(jìn)程的執(zhí)行過程中動(dòng)態(tài)進(jìn)行。首先，段式管理程序?yàn)橐粋€(gè)進(jìn)入內(nèi)存準(zhǔn)備執(zhí)行的進(jìn)程或作業(yè)分配部分內(nèi)存，以作為該進(jìn)程的工作區(qū)和放置即將執(zhí)行的程序段。隨著進(jìn)程的執(zhí)行，進(jìn)程隨時(shí)根據(jù)需要申請(qǐng)調(diào)入新段和釋放老段。進(jìn)程對(duì)內(nèi)存區(qū)的申請(qǐng)和釋放可分為兩種情況。一種是當(dāng)進(jìn)程要求調(diào)入某一段時(shí)，內(nèi)存中有足夠的空閑區(qū)滿足該段的內(nèi)存要求。可采用和動(dòng)態(tài)分區(qū)式管理相同的空閑