計(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ù)。對每個(gè)用戶能保證足夠快的響應(yīng)時(shí)間，并提供交互會(huì)話能力。具有下述特點(diǎn)。(1) 交互性：首先， 用戶可以在程序動(dòng)態(tài)運(yùn)行情況下對其加以控制。其次，用戶上機(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)行，就要解決對處理機(jī)分配調(diào)度策略、分配實(shí)施和資源回收等問題。存儲(chǔ)管理: 對內(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è)備分配給請求輸入輸出操作的程序，并啟動(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ù)或其他緊急事件處理信號。這就需要處理機(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)用來請求操作系統(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)致對進(jìn)程執(zhí)行速度的制約。程序的并發(fā)執(zhí)行可進(jìn)一步分為兩種：第一種是多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行。由于資源的有限性，多道程序的并發(fā)執(zhí)行總是伴隨著資源的共享與競爭。從而制約各道程序的執(zhí)行速度。而無法作到在微觀上，也就是在指令級上的同時(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)系可簡述如下：(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ì)算機(jī)系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)自己的制約。這里，制約就是對進(jìn)程獨(dú)立性和異步性的限制。(4) 不同的進(jìn)程可以包含同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。進(jìn)程的靜態(tài)描述由三部分組成：進(jìn)程控制塊PCB，有關(guān)程序段和該程序段對其進(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)控制簡單，發(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ī)器指令級的，其特點(diǎn)是執(zhí)行期間不允許中斷，在操作系統(tǒng)中，它是一個(gè)不可分割的基本單位。另一類是功能級的，其特點(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ì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)程所占有的資源之后，把對應(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)場。然后將被阻塞進(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)程的相對執(zhí)行速度。即各并發(fā)進(jìn)程享有平等的、獨(dú)立的競爭共有資源的權(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)程申請進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入。(4) 并發(fā)進(jìn)程(jnchng)中的某個(gè)進(jìn)程申請進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。一次原語操作使得信號量sem減1，而一次原語操作將使得信號量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í)行測試，而是在等待隊(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)程被阻塞后與該信號相對應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。原語的操作主要?jiǎng)幼魇牵?1) sem加1；(2) 若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3) 若相加結(jié)果小于或等于零，則從該信號的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。用信號量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：1) 設(shè) sem為互斥信號量，其取值范圍

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ā)送的信號稱為消息或事件。如果對一個(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ù)塊長等于緩沖區(qū)長度）；（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的私用信號量，Buffull 為進(jìn)程PB的私用信號量；（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è)公用信號量mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥，設(shè)信號量avail為生產(chǎn)者進(jìn)程的私用信號量，信號量full為消費(fèi)者進(jìn)程的私用信號量。信號量avail表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號量full表示有界緩沖區(qū)中非空單元數(shù)，初值為0。信號量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ìn)程間大批量數(shù)據(jù)的交換稱為高級通信。在單機(jī)系統(tǒng)中，進(jìn)程間通信可分為4種形式：(1) 主從式；(2) 會(huì)話式；(3) 消息或郵箱機(jī)制；(4) 共享存儲(chǔ)區(qū)方式。死鎖，是指各并發(fā)進(jìn)程彼此互相等待對方所擁有的資源，且這些并發(fā)進(jìn)程在得到對方的資源之前不會(huì)釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。死鎖的起因是并發(fā)進(jìn)程的資源競爭。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個(gè)數(shù)少于并發(fā)進(jìn)程所要求的該類資源數(shù)。產(chǎn)生死鎖的必要條件(1) 互斥條件。并發(fā)進(jìn)程所要求和占有的資源是不能同時(shí)被兩個(gè)以上進(jìn)程使用或操作的，

26、進(jìn)程對它所需要的資源進(jìn)行排他性控制。(2) 不剝奪條件。進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行剝奪，而只能由獲得該資源的進(jìn)程自己釋放。(3) 部分分配。進(jìn)程每次申請它所需要的一部分資源，在等待新資源的同時(shí)繼續(xù)占用已分配到的資源。(4) 環(huán)路條件。存在一種進(jìn)程循環(huán)鏈，鏈中每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請求。顯然，只要使上述4個(gè)必要條件中的某一個(gè)不滿足，則死鎖就可以排除。解決死鎖的方法一般可分為預(yù)防、避免、檢測與恢復(fù)等三種。引入線程主要是為了提高系統(tǒng)的執(zhí)行效率，減少處理機(jī)的空轉(zhuǎn)時(shí)間和調(diào)度切換（保護(hù)現(xiàn)場信息）的時(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)程相對應(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é)構(gòu)和提高執(zhí)行效率。線程的兩個(gè)基本類型是：用戶級線程和系統(tǒng)級線程(核心級線型)。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級：(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請求后被阻塞。(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)先級變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級，從而也將引發(fā)進(jìn)程調(diào)度。所謂可剝奪方式，即就緒隊(duì)列中一旦有優(yōu)先級高于當(dāng)前執(zhí)行進(jìn)程優(yōu)先級的進(jìn)程存在時(shí)，便立即發(fā)生進(jìn)程調(diào)度，轉(zhuǎn)讓處理機(jī)。而非剝奪方式或不可剝奪方式即使在就緒隊(duì)列存在有優(yōu)先級高于當(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、性能的衡量方法可分為定性和定量兩種。在定性衡量方面，首先是調(diào)度的可靠性。另外，簡潔性也是衡量進(jìn)程調(diào)度的一個(gè)重要指標(biāo)。進(jìn)程調(diào)度的定量評價(jià)包括CPU的利用率評價(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)程都按照它們在隊(duì)列中等待時(shí)間長短來決定它們是否優(yōu)先享受服務(wù)。缺點(diǎn)：對于那些執(zhí)行時(shí)間較短的作業(yè)或進(jìn)程來說，如果它們在某些執(zhí)行時(shí)間很長的作業(yè)或進(jìn)程之后到達(dá)，則它們將等待很長時(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)檎埱驣O或由于進(jìn)程的互斥與同步關(guān)系而被阻塞。當(dāng)阻塞解除之后再回到就緒隊(duì)列。再有一種情況就是新創(chuàng)建進(jìn)程進(jìn)入就緒隊(duì)列。多級反饋輪轉(zhuǎn)法: 對上面

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

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

37、長短，從中選出響應(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、各段相對應(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)建和管理自己的堆。堆也可能成為黑客攻擊的對象。堆是向高地址擴(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è)線程有自己的?？臻e空間可用于程序運(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)有：可以對內(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ī)，二是對所回收的內(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ū)的長度和內(nèi)存的總分區(qū)個(gè)數(shù)將保持不變。系統(tǒng)對內(nèi)存的管理和控制通過數(shù)據(jù)結(jié)構(gòu)分區(qū)說明表進(jìn)行，分區(qū)說明表說明各分區(qū)號、分區(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)程對內(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í)際上是對所有空閑區(qū)進(jìn)行一次搜索?；厥者^程：最先適應(yīng)算法最佳。因?yàn)槭褂米钕冗m應(yīng)算法回收某一空閑區(qū)時(shí)，無論被釋放區(qū)是否與空閑區(qū)相鄰，都不用改變該區(qū)在可用表或自由鏈中的位置，只需修改其大小或起始地址。而最佳適應(yīng)算法和最壞適應(yīng)算法都必須重新調(diào)整該區(qū)的位置。最先適應(yīng)算法盡可能地利用低地址空間，保證高地址有較大的空閑區(qū)來放置要求內(nèi)存較多的進(jìn)程或作業(yè)

45、。最佳適應(yīng)法找到的空閑區(qū)最佳，用最佳適應(yīng)法找到的空閑區(qū)或者是正好等于用戶請求的大小或者是能滿足用戶要求的最小空閑區(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)程對內(nèi)存的共享，有助于多道程序設(shè)計(jì)，從而提高了系統(tǒng)的資源利用率。該方法要求的硬件支持少，管理算法簡單，因而實(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è)長度相等的頁(page)。經(jīng)過頁劃分之后，進(jìn)程的虛地址變?yōu)轫撎杙與頁內(nèi)地址w所組成。(2)頁式管理把內(nèi)存空間按頁的大小劃分為片或頁面(page frame)。(3)

47、頁式虛擬地址變換為內(nèi)存頁面物理地址的方法:頁式管理把頁式虛地址與內(nèi)存頁面物理地址建立一一對應(yīng)的頁表，并用相應(yīng)的硬件地址變換機(jī)構(gòu)，來解決離散地址變換問題。(4)頁式管理采用請求調(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)頁表：最簡單的頁表由頁號與頁面號組成。頁式管理時(shí)每個(gè)進(jìn)程至少擁有一個(gè)頁表。(2)請求表：用來確定作業(yè)或進(jìn)程的虛擬空間的各頁在內(nèi)存中的實(shí)際對應(yīng)位置。整個(gè)系統(tǒng)只有一張請求表。(3)存儲(chǔ)頁面表：存儲(chǔ)頁面表也是整個(gè)系統(tǒng)一張，存儲(chǔ)頁面表指出內(nèi)存各頁面是否已被分配出去，以及未分配頁面的總數(shù)。存儲(chǔ)頁面表有兩種構(gòu)成方法:位示圖法和空閑頁面鏈的方法。頁面分配算法：請求表給出進(jìn)程或作業(yè)要求的頁面數(shù)。由存儲(chǔ)頁面表檢查是否有足夠的空閑頁面。如果沒有，則本次無法分配。如果有則首先分配設(shè)置頁表，并填寫請求表

49、中的相應(yīng)表項(xiàng)后，按一定的查找算法、搜索出所要求的空閑頁面，并將對應(yīng)的頁面號填入頁表中。圖5.18給出了上述頁面分配算法的流程圖。地址變換：規(guī)定怎樣由頁號和頁內(nèi)相對地址變換到內(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。包含頁號、頁面號、中斷位、起始地址(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所示。請求頁式管理中的置換算法在內(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)存很長時(shí)間。先進(jìn)先出算法(FIFO)：FIFO算法總是選擇在內(nèi)存駐留時(shí)間最長的一頁將其淘汰。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)開銷，例如缺頁中斷處理等。請求調(diào)頁的算法如選擇不當(dāng)，有可能產(chǎn)生抖動(dòng)現(xiàn)象。雖然消除了碎片，但每個(gè)進(jìn)程的最后一頁內(nèi)總有一部分空間得不到利用。如果頁面較大，這一部分的損失仍然較大。段式虛存空間段式管理把一個(gè)(y )進(jìn)程的虛地址空間設(shè)計(jì)成二維結(jié)構(gòu)，即段號s與段內(nèi)相對(xingdu)地址w。對段式虛地址(dzh)空間的訪問包括兩個(gè)部分：段名和段內(nèi)地址。段號與段號之間無順序關(guān)系。段的長度是不固定的，段長可動(dòng)態(tài)增長。每個(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ù)需要申請調(diào)入新段和釋放老段。進(jìn)程對內(nèi)存區(qū)的申請和釋放可分為兩種情況。一種是當(dāng)進(jìn)程要求調(diào)入某一段時(shí)，內(nèi)存中有足夠的空閑區(qū)滿足該段的內(nèi)存要求?？刹捎煤蛣?dòng)態(tài)分區(qū)式管理相同的空閑