操作系統(tǒng)-串講講義北工大版課件

操作系統(tǒng)原理操作系統(tǒng)原理1

第一章操作系統(tǒng)概論第二章進(jìn)程管理第三章內(nèi)存管理第四章設(shè)備管理第五章文件管理和作業(yè)管理操作系統(tǒng)原理

2第一節(jié)操作系統(tǒng)的概念一、什么是操作系統(tǒng)計(jì)算機(jī)硬件操作系統(tǒng)實(shí)用程序應(yīng)用程序操作系統(tǒng)設(shè)計(jì)著程序員終端用戶定義：

操作系統(tǒng)是一個(gè)系統(tǒng)軟件，它管理計(jì)算機(jī)系統(tǒng)中的軟件和硬件資源，在計(jì)算機(jī)硬件和用戶之間起到一個(gè)接口作用。.程序圖標(biāo)顯示、雙擊鼠標(biāo)動作，命令行.文件復(fù)制、磁盤內(nèi)容察看、建立文件.INT中斷語句進(jìn)行系統(tǒng)調(diào)用.通過IE下載文件的同時(shí)可編輯另一個(gè)文本文件？第一節(jié)操作系統(tǒng)的概念一、什么是操作系統(tǒng)計(jì)算機(jī)硬件操作系統(tǒng)3第二節(jié)操作系統(tǒng)的功能一、進(jìn)程管理

進(jìn)程管理主要是對處理機(jī)進(jìn)行管理。CPU是計(jì)算機(jī)中最寶貴的硬件資源。為了提高CPU的利用率，操作系統(tǒng)采用了多道程序技術(shù)。當(dāng)一個(gè)程序因等待某一條件而不能運(yùn)行下去時(shí)，就把處理機(jī)占用權(quán)轉(zhuǎn)交給另外一個(gè)可運(yùn)行程序。或者，當(dāng)出現(xiàn)了一個(gè)比當(dāng)前運(yùn)行的程序更重要的可運(yùn)行程序時(shí)，后者應(yīng)能搶占CPU。為了描述多道程序的并發(fā)執(zhí)行，就引入了進(jìn)程的概念。通過進(jìn)程管理協(xié)調(diào)多道程序之間的關(guān)系，解決處理機(jī)實(shí)施分配策略，使CPU資源得到最充分的利用。正是由于操作系統(tǒng)對處理機(jī)分配策略的不同，從而呈現(xiàn)在用戶面前的就是具有不同性質(zhì)的操作系統(tǒng)，例如批處理方式、分時(shí)處理方式和實(shí)時(shí)處理方式等。二、內(nèi)存管理

存儲器管理主要管理內(nèi)存資源。它包括以下幾點(diǎn)：

1）內(nèi)存分配：在內(nèi)存中除了OS、其他系統(tǒng)軟件外，還有一個(gè)或多個(gè)用戶程序，OS要解決分配問題，使其互不沖突。第二節(jié)操作系統(tǒng)的功能一、進(jìn)程管理進(jìn)程管理主要是4

2）存儲保護(hù)：由于系統(tǒng)中有多個(gè)程序，要保證他們之間互部干擾，保證用

戶程序不破壞系統(tǒng)程序。

設(shè)備管理是指對計(jì)算機(jī)系統(tǒng)中的所有輸入輸出設(shè)備的管理。它不僅涵蓋進(jìn)行實(shí)際I/O操作的設(shè)備，還涵蓋了控制器、通道等I/O支持設(shè)備。

存容量時(shí)，就要把內(nèi)存和外存結(jié)合起來，為用戶提供一個(gè)比

實(shí)際內(nèi)存大的多的虛擬存儲器。

三、設(shè)備管理

3）內(nèi)存擴(kuò)充：當(dāng)用戶作業(yè)所需要的內(nèi)存量超過計(jì)算機(jī)系統(tǒng)所提供的實(shí)際內(nèi)四、文件管理

系統(tǒng)中的信息資源（程序和數(shù)據(jù)）是以文件的形式存放在外存儲器上

的，需要時(shí)再將其裝入。文件管理的任務(wù)就是有效支持文件存儲、檢索修改，解決文件共享、保密和保護(hù)，以方便用戶安全、方便地訪問文件。五、用戶接口

1）程序級：提供一組廣義指令供用戶程序調(diào)用。

2）作業(yè)級：提供一組控制操作命令供用戶去組織、控制自己的作業(yè)執(zhí)行。第一節(jié)作業(yè)的基本概念2）存儲保護(hù)：由于系統(tǒng)中有多個(gè)程序，要保證他們之間5如同任何其他事物一樣，操作系統(tǒng)也有它的誕生、成長和發(fā)展過程。為了更清楚地把握操作系統(tǒng)的實(shí)質(zhì)，了解操作系統(tǒng)的發(fā)展是很有必要的，因?yàn)椴僮飨到y(tǒng)的許多概念都是在操作系統(tǒng)的發(fā)展過程中出現(xiàn)并逐步得到發(fā)展和成熟的。一、手工操作在第一代計(jì)算機(jī)時(shí)期，構(gòu)成計(jì)算機(jī)的主要器件是電子管，計(jì)算機(jī)運(yùn)行速度慢，沒有操作系統(tǒng)。用戶直接用機(jī)器語言編制程序，并在上機(jī)時(shí)獨(dú)占全部計(jì)算機(jī)資源，用戶既是程序員，又是操作員。穿孔->紙帶（卡片）裝上輸入機(jī)->程序和數(shù)據(jù)送入計(jì)算機(jī)->控制臺開關(guān)啟動程序運(yùn)行->計(jì)算->輸出結(jié)果->取走指帶。操作過程第三節(jié)操作系統(tǒng)的發(fā)展歷史如同任何其他事物一樣，操作系統(tǒng)也有它的誕生、成長和6二、批處理

20世紀(jì)50年代晶體管計(jì)算機(jī)出現(xiàn)，開始出現(xiàn)各種高級語言，操作人員、程序人員和維護(hù)人員開始有了明確分工。程序員穿孔操作員計(jì)算機(jī)室卡片盒

許多機(jī)時(shí)被操作員在機(jī)房里走來走去的過程浪費(fèi)了。二、批處理程序員穿孔操作員計(jì)算機(jī)室卡片盒許多機(jī)7

由于處理器速度的提高，造成手工操作的輸入輸出與計(jì)算機(jī)處理速度的不匹配現(xiàn)象。因此，人們設(shè)計(jì)了監(jiān)督程序（或稱為管理程序）來實(shí)現(xiàn)作業(yè)的自動轉(zhuǎn)換處理。程序員將數(shù)據(jù)、程序以及用作業(yè)語言書寫的作業(yè)說明書作為作業(yè)信息提交給操作員，操作員將這些作業(yè)信息“成批”地輸入到計(jì)算機(jī)中，有監(jiān)督程序識別每一個(gè)作業(yè)進(jìn)行處理。這種自動定序的處理方式稱為“批處理”監(jiān)督程序標(biāo)準(zhǔn)輸入程序編譯程序裝配程序標(biāo)準(zhǔn)輸出和處理程序輸入用戶作業(yè)程序編譯后的用戶作業(yè)程序裝配好的用戶作業(yè)程序執(zhí)行、輸出結(jié)果調(diào)用子程序轉(zhuǎn)到下一個(gè)作業(yè)由于處理器速度的提高，造成手工操作的輸入輸出與計(jì)8三、多道程序系統(tǒng)第二代計(jì)算機(jī)后期，特別是計(jì)算機(jī)進(jìn)入第三代以后，系統(tǒng)軟件和硬件都有了很大發(fā)展，特別是主存容量的增大以及大容量輔助存儲器的出現(xiàn)，這一切都使得計(jì)算機(jī)體系結(jié)構(gòu)發(fā)生了很大變化。由以中央處理器為中心的結(jié)構(gòu)改變?yōu)橐灾鞔鏋橹行?，而通道使得輸入輸出操作與CPU操作的并行處理成為可能。所謂多道是指允許多個(gè)程序同時(shí)存在于主存中，由中央處理器以切換方式為之服務(wù)，使得多個(gè)程序可以同時(shí)執(zhí)行，計(jì)算機(jī)資源不再被某一個(gè)用戶所獨(dú)占。待處理程序存入外存形成程序隊(duì)列作業(yè)調(diào)度幾個(gè)程序進(jìn)入內(nèi)存有作業(yè)完成再調(diào)度三、多道程序系統(tǒng)第二代計(jì)算機(jī)后期，特別是計(jì)算機(jī)進(jìn)9

多道程序的引入，使得不同用戶的多道程序可以同時(shí)在系統(tǒng)內(nèi)存并行運(yùn)行，同時(shí)它們共享計(jì)算機(jī)的資源，并行和共享思想的引入大大增加了系統(tǒng)的復(fù)雜性。如，如何分配和管理內(nèi)存、處理機(jī)如何調(diào)度以及外部設(shè)備如何分配等等。這些問題都需要一個(gè)復(fù)雜的管理機(jī)構(gòu)合理有效地進(jìn)行管理。它就是操作系統(tǒng)。

隨著計(jì)算機(jī)的發(fā)展，硬件價(jià)格越來越低,人們開始關(guān)注計(jì)算機(jī)使用的方便性，也就是說如何提高和增加計(jì)算機(jī)的人-機(jī)對話功能，因此很快就出現(xiàn)了分時(shí)系統(tǒng)。這種系統(tǒng)是在一臺計(jì)算機(jī)上掛若干臺聯(lián)機(jī)終端，用戶通過自己的終端與計(jì)算機(jī)對話來控制、調(diào)試、干預(yù)他的程序。而系統(tǒng)則是將處理機(jī)的時(shí)間劃分為小的時(shí)間間隔（又稱時(shí)間片），輪流地為每個(gè)終端上的作業(yè)服務(wù)，使每個(gè)用戶都感覺好象自己在使用計(jì)算機(jī)。

多道和分時(shí)系統(tǒng)的出現(xiàn)，標(biāo)志著操作系統(tǒng)的正式形成。四、操作系統(tǒng)的形成多道程序的引入，使得不同用戶的多道程序可以同時(shí)在10五、操作系統(tǒng)的分類根據(jù)操作系統(tǒng)在用戶界面的使用環(huán)境和功能特征的不同，操作系統(tǒng)一般可分為三種基本類型，即批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)。隨著計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展，又出現(xiàn)了個(gè)人操作系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)。1、批處理操作系統(tǒng)（BatchProcessing)

批處理操作系統(tǒng)的工作方式是：用戶將作業(yè)交給系統(tǒng)操作員，系統(tǒng)操作員將許多用戶作業(yè)組成一批作業(yè)，輸入到計(jì)算機(jī)中，在系統(tǒng)中形成一個(gè)自動轉(zhuǎn)接的連續(xù)的作業(yè)流，然后啟動操作系統(tǒng)，系統(tǒng)自動、依次執(zhí)行每個(gè)作業(yè)。最后由操作員將作業(yè)結(jié)果交給用戶。優(yōu)點(diǎn)：作業(yè)流自動化；效率高；吞吐率高。缺點(diǎn)：無交互手段；調(diào)試程序困難。五、操作系統(tǒng)的分類根據(jù)操作系統(tǒng)在用戶界面的使用環(huán)境112、分時(shí)操作系統(tǒng)（TimeSharing)

分時(shí)操作系統(tǒng)的工作方式是：一臺主機(jī)連接了若干終端，每個(gè)終端有一個(gè)用戶在使用。用戶交互地向系統(tǒng)提出命令請求，系統(tǒng)采用時(shí)間片輪轉(zhuǎn)法方式處理服務(wù)請求，并通過交互方式在終端上向用戶顯示結(jié)果。

分時(shí)系統(tǒng)具有多路性、交互性、“獨(dú)占”性和及時(shí)性的特征：

多路性：宏觀上看多人同時(shí)使用一個(gè)CPU;

交互性：用戶根據(jù)系統(tǒng)響應(yīng)結(jié)果進(jìn)一步提出新請求；

“獨(dú)占”性：用戶感覺不到計(jì)算機(jī)為其他用戶服務(wù);

及時(shí)性：系統(tǒng)對用戶提出的請求及時(shí)響應(yīng)。3、實(shí)時(shí)操作系統(tǒng)（RealTimeOperationSystem)

實(shí)時(shí)操作系統(tǒng)是指計(jì)算機(jī)能及時(shí)響應(yīng)外部事件的請求，在規(guī)定的嚴(yán)格時(shí)間內(nèi)完成對該事件的處理，并控制所有實(shí)時(shí)設(shè)備和實(shí)時(shí)任務(wù)協(xié)調(diào)一致地工作的操作系統(tǒng)。2、分時(shí)操作系統(tǒng)（TimeSharing)124、個(gè)人計(jì)算機(jī)操作系統(tǒng)（PersonOperationSystem)

個(gè)人計(jì)算機(jī)系統(tǒng)是一種單用戶多任務(wù)的操作系統(tǒng)。它主要供個(gè)人使用，功能強(qiáng)、價(jià)格便宜。其特點(diǎn)是采用圖形界面人機(jī)交互的工作方式；使用方便。Dos是單用戶單任務(wù)操作系統(tǒng)，早期Windows是單用戶多任務(wù)操作系統(tǒng)。5、網(wǎng)絡(luò)操作系統(tǒng)（NetworkOperationSystem)

網(wǎng)絡(luò)操作系統(tǒng)是基于計(jì)算機(jī)網(wǎng)絡(luò)的一種操作系統(tǒng)，是在各種計(jì)算機(jī)操作系統(tǒng)之上按網(wǎng)絡(luò)體系結(jié)構(gòu)協(xié)議標(biāo)準(zhǔn)開發(fā)的軟件，包括網(wǎng)絡(luò)管理、通訊、安全、資源共享和各種網(wǎng)絡(luò)應(yīng)用。其主要目標(biāo)是計(jì)算機(jī)之間的相互通訊和資源共享。因?yàn)楝F(xiàn)代操作系統(tǒng)的主要特征之一就是網(wǎng)絡(luò)功能，因此，除了20世紀(jì)90年代初期時(shí)，Novell公司的Netware系統(tǒng)被稱為網(wǎng)絡(luò)操作系統(tǒng)之外，人們一般不再特指某個(gè)操作系統(tǒng)為網(wǎng)絡(luò)操作系統(tǒng)4、個(gè)人計(jì)算機(jī)操作系統(tǒng)（PersonOperation136、分布式操作系統(tǒng)（DistributedOperationSystem)大量的計(jì)算機(jī)通過網(wǎng)絡(luò)被連接在一起，可以獲得極高的運(yùn)算能力和廣泛的數(shù)據(jù)共享。這種系統(tǒng)被稱為分布式操作系統(tǒng)。

分布式操作系統(tǒng)具有：統(tǒng)一性、共享性、“透明性和自治性的特征：

統(tǒng)一性：它是一個(gè)統(tǒng)一的操作系統(tǒng);

共享性：所有的分布式系統(tǒng)中的資源是共享的；

透明性：用戶并不知道某一操作具體運(yùn)行在哪一臺計(jì)算機(jī)。

自治性：分布式系統(tǒng)中的多個(gè)主機(jī)都處于平等地位。

網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)在概念上的區(qū)別是：網(wǎng)絡(luò)操作系統(tǒng)可以構(gòu)架于不同的操作系統(tǒng)之上，通過網(wǎng)絡(luò)協(xié)議實(shí)現(xiàn)網(wǎng)絡(luò)資源的統(tǒng)一配置，需要顯式地指明資源位置與類型，對本地資源和異地資源的訪問要區(qū)別對待。分布式強(qiáng)調(diào)單一性，它是一種操作系統(tǒng)構(gòu)架的。所有資源用同一方式管理和訪問，不必關(guān)心資源在哪，怎樣存儲。6、分布式操作系統(tǒng)（DistributedOperatio14第二章進(jìn)程管理?進(jìn)程是什么?進(jìn)程的狀態(tài)如何?進(jìn)程的互斥與同步?進(jìn)程的通訊方式?操作系統(tǒng)如何解決進(jìn)程死鎖問題第二章進(jìn)程管理?進(jìn)程是什么15第一節(jié)進(jìn)程的基本概念通常，操作系統(tǒng)的重要任務(wù)之一是使用戶充分、有效地利用系統(tǒng)中的資源，那么采用一個(gè)什么樣的概念來描述用戶程序的執(zhí)行過程和作為資源分配的基本單位才能充分反映操作系統(tǒng)的并發(fā)執(zhí)行、資源共享呢？這個(gè)概念就是進(jìn)程。第一節(jié)進(jìn)程的基本概念通常，操作系統(tǒng)的重要任務(wù)16一、進(jìn)程的定義

進(jìn)程：是一個(gè)具有獨(dú)立功能的程序段對某個(gè)數(shù)據(jù)集在處理機(jī)上的執(zhí)行過程和分配資源的基本單位。進(jìn)程的概念是60年代初期首先在IBM的TTS/360系統(tǒng)中引用，人們對進(jìn)程下過許多各式各樣的定義：（1）進(jìn)程是可以并行執(zhí)行的計(jì)算部分；（2）進(jìn)程是一個(gè)獨(dú)立的可以調(diào)度的活動；（3）進(jìn)程是一實(shí)體，當(dāng)它執(zhí)行某個(gè)任務(wù)時(shí)，將要分配和釋放各種資源。以上定義盡管各有側(cè)重，但在本質(zhì)上是相同的，即主要注重進(jìn)程是一個(gè)動態(tài)的執(zhí)行過程，因此我們給出進(jìn)程的一般性定義。一、進(jìn)程的定義進(jìn)程：是一個(gè)具有獨(dú)立功能的程序段對某個(gè)數(shù)據(jù)17進(jìn)程、程序的區(qū)別和關(guān)系：

b.進(jìn)程具有并行特征，而程序則沒有。因?yàn)槌绦虿环从硤?zhí)行過程c.進(jìn)程是競爭計(jì)算機(jī)系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)的制約。d.不同的進(jìn)程可以屬于同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。a.進(jìn)程反映的是一個(gè)動態(tài)概念，而程序是一個(gè)靜態(tài)概念；程序是指令的有序集合，沒有任何執(zhí)行的含義，而進(jìn)程則強(qiáng)調(diào)的是執(zhí)行過程，它動態(tài)被創(chuàng)建、執(zhí)行和消亡。如程序是菜譜，則進(jìn)程就是按照菜譜炒菜的過程。進(jìn)程、程序的區(qū)別和關(guān)系：c.進(jìn)程是競爭計(jì)算機(jī)18第二節(jié)進(jìn)程的描述一個(gè)進(jìn)程是一個(gè)程序?qū)δ骋粋€(gè)數(shù)據(jù)集的執(zhí)行過程，是分配資源的基本單位。那么，從處理機(jī)的活動角度來看，又如何識別和描述程序執(zhí)行活動的進(jìn)程呢？很顯然，系統(tǒng)中需要有描述進(jìn)程存在和能夠反映其變化的物理實(shí)體，即進(jìn)程的靜態(tài)描述。進(jìn)程控制塊PCB包含了有關(guān)進(jìn)程的描述信息、控制信息以及資源信息，是進(jìn)程動態(tài)特征的集中反映。系統(tǒng)根據(jù)PCB感知進(jìn)程的存在和通過PCB中所包含的各項(xiàng)變量的變化，掌握進(jìn)程所處的狀態(tài)以達(dá)到控制進(jìn)程活動的目的。由于進(jìn)程的PCB是系統(tǒng)感知進(jìn)程的唯一實(shí)體，所以進(jìn)程的PCB結(jié)構(gòu)幾乎是常駐內(nèi)存的。

進(jìn)程的靜態(tài)描述由三部分組成：進(jìn)程控制塊PCB(ProcessControlBlock)，有關(guān)程序段和該程序段對其進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)集。第二節(jié)進(jìn)程的描述一個(gè)進(jìn)程是一個(gè)程序?qū)δ骋粋€(gè)數(shù)19進(jìn)程的程序部分是描述進(jìn)程所要完成的功能；數(shù)據(jù)結(jié)構(gòu)集是程序在執(zhí)行時(shí)必不可少的工作區(qū)和操作對象。這兩部分是進(jìn)程完成所需功能的物質(zhì)基礎(chǔ)，通常它們放在外存，直到進(jìn)程執(zhí)行時(shí)再調(diào)入內(nèi)存。進(jìn)程描述進(jìn)程控制塊PCB有關(guān)程序段數(shù)據(jù)結(jié)構(gòu)集進(jìn)程的程序部分是描述進(jìn)程所要完成的功能；進(jìn)程描述20一、進(jìn)程控制塊PCB一般來說，不同的操作系統(tǒng)，PCB表所包含的內(nèi)容多少有所不同，但總的來說還是大致相同的。1、描述信息

進(jìn)程的描述信息包括：進(jìn)程名、用戶名、家族關(guān)系。進(jìn)程名就是進(jìn)程標(biāo)識號，每個(gè)進(jìn)程都有一個(gè)唯一的名稱。用戶名就是指出該進(jìn)程是隸屬于哪個(gè)用戶的。家族關(guān)系是指該進(jìn)程的父進(jìn)程是誰，即誰創(chuàng)建了該進(jìn)程。

PCB塊集中反映一個(gè)進(jìn)程的動態(tài)特征。在進(jìn)程并發(fā)執(zhí)行時(shí)，由于資源共享，帶來各進(jìn)程之間的相互制約。很顯然，為了反映這些制約關(guān)系和資源共享關(guān)系，在創(chuàng)建一個(gè)進(jìn)程時(shí)，應(yīng)首先創(chuàng)建它的PCB，然后才能根據(jù)PCB中的信息對進(jìn)程實(shí)施有效的管理和控制。也就是說，PCB隨著進(jìn)程的創(chuàng)建而創(chuàng)建，隨著進(jìn)程的撤消而消亡。一、進(jìn)程控制塊PCB一般來說，不同的操作系統(tǒng)，P212、控制信息

控制信息包括：進(jìn)程當(dāng)前狀態(tài)、進(jìn)程優(yōu)先級、程序開始地址、各種計(jì)時(shí)信息、通訊信息。進(jìn)程當(dāng)前狀態(tài)說明進(jìn)程當(dāng)前處于何種狀態(tài)。進(jìn)程在活動期間可分為就緒態(tài)、執(zhí)行態(tài)和等待狀態(tài)。就緒態(tài)該進(jìn)程準(zhǔn)備占有處理機(jī)；執(zhí)行態(tài)表示該進(jìn)程正在占有處理機(jī)；而等待狀態(tài)則表示進(jìn)程因某種原因不能占有處理機(jī)。進(jìn)程優(yōu)先級是選取進(jìn)程占有處理機(jī)的重要依據(jù)。程序開始地址規(guī)定該進(jìn)程對應(yīng)的程序段以此地址開始運(yùn)行。各種計(jì)時(shí)信息給出進(jìn)程占有和利用資源的有關(guān)情況。通訊信息用來說明該進(jìn)程在執(zhí)行過程中與別的進(jìn)程所發(fā)生的信息交換情況。2、控制信息控制信息包括：進(jìn)程當(dāng)前狀態(tài)、進(jìn)程優(yōu)先級、程223、資源管理信息資源管理信息包括：

（1）占用內(nèi)存大小、指針；（頁表指針）；（2）對換或覆蓋用有關(guān)信息（對換程序段長度、外存地址），這些信息在申請、釋放內(nèi)存中使用；（3）共享程序段的大小及起始地址；（4）輸入輸出設(shè)備的設(shè)備號，所要傳送的數(shù)據(jù)長度、緩沖區(qū)地址、及所用設(shè)備的有關(guān)數(shù)據(jù)結(jié)構(gòu)指針等，這些信息在進(jìn)程申請、釋放設(shè)備以及數(shù)據(jù)傳送中使用；（5）指向文件系統(tǒng)的指針及有關(guān)標(biāo)識等，以便對文件系統(tǒng)操作。3、資源管理信息資源管理信息包括：（2）對換或覆蓋用有關(guān)信息23第三節(jié)進(jìn)程的狀態(tài)轉(zhuǎn)換及控制一、進(jìn)程的狀態(tài)及轉(zhuǎn)換任何一個(gè)事物都有他的生命期，進(jìn)程也不例外。一個(gè)進(jìn)程的生命期可以劃分為一組狀態(tài)，這些狀態(tài)刻畫了進(jìn)程的整個(gè)生存過程。操作系統(tǒng)根據(jù)PCB中的狀態(tài)值控制進(jìn)程。

進(jìn)程在其生命期內(nèi)被劃分為三種基本狀態(tài)：就緒狀態(tài)、執(zhí)行狀態(tài)、等待狀態(tài)。就緒狀態(tài)(Ready)：剛被創(chuàng)建；或者等待事件發(fā)生被喚醒；執(zhí)行狀態(tài)(Running)：獲得處理機(jī)的使用權(quán)；阻塞狀態(tài)(Blocked)：等待某個(gè)事件的發(fā)生（I/O完成）這只是進(jìn)程的三種基本狀態(tài)，有的系統(tǒng)可能劃分得更細(xì)，但都是圍繞著三個(gè)基本狀態(tài)劃分的。第三節(jié)進(jìn)程的狀態(tài)轉(zhuǎn)換及控制一、進(jìn)程的狀態(tài)及轉(zhuǎn)換24提交調(diào)度時(shí)間片到等待某個(gè)事件（內(nèi)存、設(shè)備等）等待事件發(fā)生就緒執(zhí)行阻塞提交調(diào)度時(shí)間片到等待某個(gè)事件等待事件發(fā)生就緒執(zhí)行阻塞25

除此之外，在有的系統(tǒng)中，將進(jìn)程的狀態(tài)進(jìn)一步細(xì)分為五個(gè)狀態(tài)，除了上述三個(gè)狀態(tài)之外，增加了創(chuàng)建和退出兩個(gè)狀態(tài)。創(chuàng)建狀態(tài)（New)：進(jìn)程還在創(chuàng)建過程中，還不能運(yùn)行。這時(shí)，操作系統(tǒng)要建立PCB、建立資源表、分配資源、建立地址空間表。退出狀態(tài)（Exit)：進(jìn)程運(yùn)行結(jié)束，系統(tǒng)回收所占用資源。創(chuàng)建創(chuàng)建提交就緒調(diào)度執(zhí)行釋放退出等待事件阻塞事件出現(xiàn)超時(shí)除此之外，在有的系統(tǒng)中，將進(jìn)程的狀態(tài)進(jìn)一步細(xì)分26二、進(jìn)程的控制所謂進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)之間的轉(zhuǎn)換，從而達(dá)到高效率并發(fā)執(zhí)行和實(shí)現(xiàn)資源共享的目的。用于進(jìn)程控制的程序段有什么要求呢？我們引入原語的概念。

原語：在系統(tǒng)狀態(tài)下執(zhí)行的具有特定功能的程序段稱為原語，且它們在執(zhí)行期間不允許被中斷、不允許并發(fā)執(zhí)行。1）創(chuàng)建原語：就是系統(tǒng)為進(jìn)程創(chuàng)建一個(gè)進(jìn)程控制塊PCB,并填寫PCB中相應(yīng)信息項(xiàng)的過程。二、進(jìn)程的控制所謂進(jìn)程控制，就是系統(tǒng)使用一些具272）撤消原語：就是系統(tǒng)釋放進(jìn)程所占有的各種資源和PCB結(jié)構(gòu)本身。導(dǎo)致進(jìn)程撤消的原因有多種：

a.該進(jìn)程已完成所要求的功能而正常終止；

b.該進(jìn)程由于某種錯(cuò)誤導(dǎo)致非正常終止；

c.祖先進(jìn)程要求撤消某個(gè)子進(jìn)程；2）撤消原語：就是系統(tǒng)釋放進(jìn)程所占有的各種資源和PCB結(jié)構(gòu)本283）阻塞原語：在一個(gè)進(jìn)程期待某一事件發(fā)生，但發(fā)生條件尚不具備時(shí)，進(jìn)程調(diào)用該原語阻塞自己。

入口保存當(dāng)前進(jìn)程CPU現(xiàn)場置進(jìn)程狀態(tài)為“阻塞”被阻塞進(jìn)程入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度

進(jìn)程阻塞時(shí)，正處于執(zhí)行狀態(tài)，故先要保存CPU現(xiàn)場(PCB中）；另外最后轉(zhuǎn)進(jìn)程調(diào)度程序是很重要的，否則，處理機(jī)將會出現(xiàn)空轉(zhuǎn)現(xiàn)象。3）阻塞原語：在一個(gè)進(jìn)程期待某一事件發(fā)生，但發(fā)生條件入口保存294）喚醒原語：當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，等待該事件的所有進(jìn)程都將被喚醒。但進(jìn)程本身不能自己喚醒自己，有兩種方法：

a.系統(tǒng)喚醒：系統(tǒng)統(tǒng)一管理和控制事件的發(fā)生，并將“發(fā)生”這一消息通知所有等待進(jìn)程，而使他們進(jìn)入就緒隊(duì)列。b.事件發(fā)生進(jìn)程喚醒喚醒：等待進(jìn)程有事件發(fā)生進(jìn)程喚醒，這時(shí)，事件發(fā)生進(jìn)程和被喚醒進(jìn)程之間是合作關(guān)系。入口從等待隊(duì)列中摘下被喚醒進(jìn)程將被喚醒進(jìn)程置為就緒狀態(tài)將被喚醒進(jìn)程送入就緒隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度4）喚醒原語：當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，a.系30第四節(jié)進(jìn)程互斥前面我們已講過，進(jìn)程在執(zhí)行時(shí)，各進(jìn)程具有獨(dú)立性和異步性等并行特征。但是，在計(jì)算機(jī)系統(tǒng)中，由于資源的有限必然導(dǎo)致進(jìn)程之間對資源既有共享、又有競爭。因此并發(fā)進(jìn)程的執(zhí)行不僅僅是用戶程序開始時(shí)間的隨機(jī)性和資源利用率的問題，同時(shí)也造成了進(jìn)程之間的相互制約。一、資源共享引起的進(jìn)程制約從例題中可以看出，系統(tǒng)中進(jìn)程相互影響的原因有二：

a.系統(tǒng)內(nèi)的進(jìn)程共享資源（Diskreq隊(duì)列，Insert程序段）；

b.為完成同一任務(wù)的進(jìn)程之間要進(jìn)行協(xié)作（PHF和IOS)；

因此，我們給出兩個(gè)定義：臨界資源和臨界區(qū)。第四節(jié)進(jìn)程互斥前面我們已講過，進(jìn)程在執(zhí)行時(shí)，311、臨界資源和臨界區(qū)臨界資源：是指一次僅允許一個(gè)進(jìn)程使用的資源。（CriticalResource)（Diskreq隊(duì)列)臨界區(qū)：最多只允許一個(gè)進(jìn)程訪問的程序段。（CriticalSection)（Insert程序段)2、進(jìn)程互斥

定義：一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不允許交叉執(zhí)行的單位執(zhí)行。即，不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)稱為互斥。1、臨界資源和臨界區(qū)臨界資源：是指一次僅允許一個(gè)進(jìn)程使用的資323、并發(fā)進(jìn)程互斥執(zhí)行準(zhǔn)則：1）有空即進(jìn)。并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止其它進(jìn)程進(jìn)入臨界區(qū)。2）擇一而入。并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入。3）限時(shí)進(jìn)入。并發(fā)進(jìn)程中的某個(gè)進(jìn)程申請進(jìn)入臨界區(qū)開始，應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。3、并發(fā)進(jìn)程互斥執(zhí)行準(zhǔn)則：1）有空即進(jìn)。并發(fā)進(jìn)程中的某個(gè)進(jìn)程33二、互斥方法進(jìn)程互斥的解決方法有兩種：一是由競爭各方平等協(xié)商；二是引入進(jìn)程管理者，由管理者協(xié)調(diào)競爭各方對臨界資源的使用。

為了保證臨界資源的正確使用，我們可把臨界資源的訪問過程分成四部分：進(jìn)入?yún)^(qū)退出區(qū)a.進(jìn)入?yún)^(qū)：檢查可否進(jìn)入臨界區(qū)；可進(jìn)入，設(shè)置響應(yīng)的標(biāo)志，阻止其他進(jìn)程。b.臨界區(qū)：進(jìn)程中訪問臨界資源的一段代碼。c.退出區(qū)：將訪問標(biāo)志清除。d.退出區(qū)：代碼中的其余部分。

臨界區(qū)

剩余區(qū)二、互斥方法進(jìn)程互斥的解決方法有兩種：一是由競爭34信號量和P、V原語前面的互斥算法都是平等進(jìn)程間的協(xié)商機(jī)制，它們存在的問題是平等協(xié)商無法解決時(shí)，需要引入一個(gè)管理者來解決公有資源的使用問題。信號量（Semaphore)就是由操作系統(tǒng)提供的管理公有資源的有效手段。1）信號量信號量是一個(gè)整數(shù)，代表系統(tǒng)中可用資源實(shí)體的數(shù)量。信號量Sem>=0表示可用臨界資源的實(shí)體數(shù)；<0表示等待使用該臨界資源的進(jìn)程數(shù)信號量和P、V原語前面的互斥算法都是平等進(jìn)程間的協(xié)352）P、V原語

P、V是對信號量操作的兩個(gè)原語操作，其中P原語操作使信號量減1，V原語操作使信號量加1。

假設(shè)系統(tǒng)中有一共有資源為S,并在系統(tǒng)中設(shè)有表示其實(shí)體數(shù)量的計(jì)數(shù)器Count和進(jìn)程等待隊(duì)列Queue,P、V原語操作描述如下：P(S){--S.Count;if(S.Count<0){阻塞調(diào)用進(jìn)程；進(jìn)程進(jìn)入等待隊(duì)列S.Queue;}}

入口--S.CountS.Count>=0置進(jìn)程為“阻塞”進(jìn)入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度返回YN2）P、V原語P、V是對信號量操作的兩個(gè)原語操作36入口++S.CountS.Count<0喚醒等待隊(duì)列中的一個(gè)進(jìn)程轉(zhuǎn)進(jìn)程調(diào)度返回NYV(S){++S.Count;if(S.Count<0){從等待隊(duì)列S.Queue

中取出一個(gè)進(jìn)程；將該進(jìn)程入就緒隊(duì)列；}}入口++S.CountS.Count<0喚醒等待隊(duì)列中的一個(gè)373）用P、V原語實(shí)現(xiàn)進(jìn)程互斥通過我們對臨界區(qū)訪問過程的分析，信號量機(jī)制中P原語相當(dāng)于進(jìn)入?yún)^(qū)操作，V原語相當(dāng)于退出區(qū)操作。用P、V原語實(shí)現(xiàn)進(jìn)程互斥就是將臨界區(qū)置于P和V兩個(gè)原語操作之間，進(jìn)入時(shí)執(zhí)行P操作，使信號量Sem減1，如果Sem>=0,則進(jìn)入臨界區(qū)，否則不可進(jìn)入。進(jìn)程退出臨界區(qū)時(shí)，執(zhí)行V操作，使信號量Sem+1，表示釋放臨界資源。設(shè)置互斥信號量Sem，并賦初值為1

Sem=1,資源未被占用；

Sem=0,資源被占用；

Sem<0,資源被占用，且有等待進(jìn)程。b.描述：P(Sem);臨界區(qū)V(Sem)剩余區(qū)3）用P、V原語實(shí)現(xiàn)進(jìn)程互斥通過我們對臨界區(qū)訪問384）進(jìn)程互斥舉例例1：設(shè)有三個(gè)進(jìn)程A、B、C需共享一個(gè)臨界資源，用P、V操作寫出其算法。SemaphoreSem=1;VoidP(){while(true){P(Sem);

使用臨界區(qū)；

V(Sem);}}VoidMain{ParbeginPa,Pb,Pc}SemPaPbPc1P(Sem)0P(Sem)-1P(Sem)-2V(Sem)-1V(Sem)0V(Sem)14）進(jìn)程互斥舉例例1：設(shè)有三個(gè)進(jìn)程A、B、C需共享一個(gè)臨界資39例3、讀者-寫者問題（Reader-WriterProblem)在計(jì)算機(jī)系統(tǒng)中當(dāng)若干個(gè)并發(fā)進(jìn)程都要訪問某個(gè)共享文件時(shí)應(yīng)區(qū)分是讀還是寫。顯然可允許多個(gè)進(jìn)程同時(shí)讀文件，不允許在進(jìn)程讀文件時(shí)讓另外一進(jìn)程去寫文件，或者有進(jìn)程在寫文件時(shí)讓另外一個(gè)進(jìn)程去讀該文件，更不允許多個(gè)外進(jìn)程同時(shí)寫同一文件。因此讀-寫進(jìn)程之間關(guān)系為：“讀-寫”互斥、“寫-寫”互斥和“讀-讀”允許。另外，因?yàn)樵试S多個(gè)進(jìn)程同時(shí)讀，系統(tǒng)應(yīng)記錄讀進(jìn)程的個(gè)數(shù)，而每個(gè)讀進(jìn)程去讀文件或讀文件結(jié)束后都要修改讀者個(gè)數(shù)，因此，讀者個(gè)數(shù)又是若干讀進(jìn)程的共享變量，即軟件臨界資源，它們也必須互斥地修改這個(gè)變量。

綜上所述，我們定義兩個(gè)互斥信號量和一個(gè)公共變量：Wmutex用于“讀-寫”和“寫-寫”互斥；Rmutex用于若干讀進(jìn)程對讀者個(gè)數(shù)修改的互斥；公共變量RCount用于記錄當(dāng)前正在讀文件的讀者數(shù)目。例3、讀者-寫者問題（Reader-WriterProbl40過程描述：BeginWmutex,Rmutex:semaphore;Rcount:integer;Wmutex=Rmutex=1;Rcount=0;

ProcessReader(I)Begin++Rcount;

ifRcount=0

thenV(Rmutex);ReadFile;P(Rmutex);--Rcount;IfRcount=0ThenV(Rmutex);End;ProcessWriter(I)BeginP(Wmutex);WriteFile;V(Wmutex);End;End;P(Rmutex);P(Wmutex);V(Wmutex);過程描述：BeginWmutex,Rmutex:sema41第五節(jié)進(jìn)程同步一、同步的概念上一節(jié)我們介紹了并發(fā)進(jìn)程對系統(tǒng)公有資源的競爭，從而引出了進(jìn)程互斥的概念以及解決的辦法，并發(fā)進(jìn)程之間是否還存在其他制約關(guān)系呢？這就是同步問題。

例：設(shè)有計(jì)算和打印兩個(gè)進(jìn)程Pc和Pp,共同使用同一緩沖區(qū)Buffer，Pc向Buffer中存放計(jì)算結(jié)果，Pp從Buffer取計(jì)算結(jié)果送打印機(jī)輸出。PcPpBuffer

這兩個(gè)進(jìn)程的執(zhí)行是相互制約的。即Pc的執(zhí)行結(jié)果是Pp的執(zhí)行條件；而Pp的執(zhí)行結(jié)果也是Pc的執(zhí)行條件，它們是相互制約的。

我們把一組在異步環(huán)境中由于以各自的執(zhí)行結(jié)果而限制其它進(jìn)程的執(zhí)行速度的現(xiàn)象稱為并發(fā)進(jìn)程的直接制約，解決這種直接制約的方法稱為同步。（假設(shè)互斥已解決）第五節(jié)進(jìn)程同步一、同步的概念上一節(jié)我們介紹了并42二、私有信號量前面講到進(jìn)程互斥引入了信號量的概念，它是與所有并發(fā)進(jìn)程都相關(guān)的，因此我們稱其為公有信號量。那么在進(jìn)程同步中，我們同樣也引入信號量的概念，但它只是與制約進(jìn)程和被制約進(jìn)程有關(guān)，并不涉及所有的并發(fā)進(jìn)程，因此我們稱其為私有信號量。上面計(jì)算進(jìn)程和打印進(jìn)程是相互制約的，讓雙方互相發(fā)送條件已經(jīng)具備的信號，以協(xié)調(diào)兩進(jìn)程的運(yùn)行，描述如下：PcA:Wait(Bufferempty)計(jì)算；計(jì)算結(jié)果送緩沖區(qū)；Bufferfull=true;Signal(Bufferfull);GotoA;PpB:Wait(Bufferfull);

打印緩沖區(qū)中的數(shù)據(jù)；Bufferempty=true;

Signal(Bufferempty);

GotoB;二、私有信號量前面講到進(jìn)程互斥引入了信號量的概念，43三、用P、V原語實(shí)現(xiàn)進(jìn)程同步

a.為并發(fā)進(jìn)程設(shè)置私有信號量；

b.為私有信號量賦初值；

c.用P、V原語和私有信號量實(shí)現(xiàn)同步。上面例子中，我們假設(shè)緩沖區(qū)大小為n,同步過程如下：a.設(shè)Bufferempty為Pc進(jìn)程的私有信號量，

Bufferfull為Pp進(jìn)程的私有信號量，b.賦初值；Bufferempty=n,Bufferfull=0;c.實(shí)現(xiàn)：Pc:Deposit(data)

beginP(Bufferempty)DataBuffer[I];V(Bufferfull);end;Pp:Remove(data)

beginP(Bufferfull);Buffer[I]Data;V(Bufferempty);end;三、用P、V原語實(shí)現(xiàn)進(jìn)程同步a.為并發(fā)進(jìn)程設(shè)置私有信號量44四、進(jìn)程互斥、同步的應(yīng)用1.生產(chǎn)-消費(fèi)者問題（Producer-ConsumerProblem)如果把并發(fā)進(jìn)程的互斥和同步問題一般化，我們可以得出一個(gè)抽象化的一般模型，即生產(chǎn)-消費(fèi)者問題。在計(jì)算機(jī)系統(tǒng)中，每個(gè)進(jìn)程都可以申請和釋放各種不同類型的資源。通常把系統(tǒng)中申請資源的進(jìn)程稱為消費(fèi)者，而釋放資源的進(jìn)程稱為生產(chǎn)者。眾多并發(fā)進(jìn)程共同存在于系統(tǒng)之中，必然要解決它們之間的互斥和同步問題。如果我們把前面講述的計(jì)算進(jìn)程Pc和打印進(jìn)程Pp互斥和同步同時(shí)考慮，就是我們要討論的生產(chǎn)-消費(fèi)者問題。

a.設(shè)置公有信號量mutex，以實(shí)現(xiàn)互斥；

b.設(shè)置私有信號量empty和full，以實(shí)現(xiàn)同步；

c.賦初值：empty=n,full=0,mutex=1;

d.實(shí)現(xiàn)deposit和remove.四、進(jìn)程互斥、同步的應(yīng)用1.生產(chǎn)-消費(fèi)者問題（Produce45Deposit(data)BeginP(empty);P(mutex);dataBufferunit[I];V(mutex);V(full);End;Remove(data)BeginP(full);P(mutex);V(mutex);V(empty);End;（生產(chǎn)）Bufferunit[I]data;（消費(fèi)）注意：P、V順序。

Deposit(data)BeginP(empty);P(m46第六節(jié)進(jìn)程通訊一、進(jìn)程通信方式

進(jìn)程之間的通訊也就是進(jìn)程之間進(jìn)行信息、數(shù)據(jù)的交換。這種信息、數(shù)據(jù)的交換一般有兩種：控制信息和大批量信息或數(shù)據(jù)。我們把進(jìn)程之間控制信息的交換稱為低級通訊；而把大批量信息、數(shù)據(jù)的交換稱為高級通訊。前面我們所接觸到的為了實(shí)現(xiàn)進(jìn)程之間的同步，進(jìn)程之間需要傳遞私有信號量，它是屬于為了控制進(jìn)程的執(zhí)行速度而進(jìn)行的低級通訊。下面我們介紹進(jìn)程高級通訊的兩種方式：消息緩沖機(jī)制和信箱機(jī)制。a.消息緩沖方式；

b.信箱方式。

第六節(jié)進(jìn)程通訊一、進(jìn)程通信方式進(jìn)程之間的通訊47一、消息緩沖機(jī)制

它的基本思想是由系統(tǒng)統(tǒng)一管理一組緩沖存儲區(qū)，其中每一個(gè)緩沖區(qū)存放一個(gè)消息。當(dāng)發(fā)送進(jìn)程要發(fā)送消息時(shí)，先想系統(tǒng)申請一緩沖區(qū)，然后把消息寫進(jìn)去，接著再把該緩沖區(qū)送到接收進(jìn)程的一個(gè)消息隊(duì)列中。接收進(jìn)程則在適當(dāng)時(shí)機(jī)從消息隊(duì)列中去走所需消息，然后釋放緩沖區(qū)。由于消息緩沖機(jī)制所使用的緩沖區(qū)為公用緩沖區(qū)，兩個(gè)通訊進(jìn)程必須滿足如下條件：

a.發(fā)送進(jìn)程只有申請到空緩沖區(qū)，才能發(fā)送消息。

b.消息隊(duì)列無消息時(shí)，接收進(jìn)程不能接收到任何信息。

c.各進(jìn)程對消息隊(duì)列操作時(shí)，必須互斥。發(fā)送與發(fā)送，發(fā)送與接收，接收與接收。一、消息緩沖機(jī)制它的基本思想是由系統(tǒng)統(tǒng)一管理一組緩沖481、消息緩沖區(qū)的結(jié)構(gòu)發(fā)送進(jìn)程名消息長度消息正文指針消息緩沖區(qū)發(fā)送消息的進(jìn)程名或標(biāo)示符消息的長度消息的正文指向下一個(gè)消息緩沖區(qū)的指針2、進(jìn)程PCB增加內(nèi)容PCB增加內(nèi)容Pm:指向進(jìn)程接收到的消息隊(duì)列隊(duì)首的指針Mutex:用于消息隊(duì)列操作的互斥信號量。消息隊(duì)列屬于臨界資源，進(jìn)程需互斥進(jìn)行操作。Sem:用于接收進(jìn)程和發(fā)送進(jìn)程之間實(shí)現(xiàn)同步。其值表示接收進(jìn)程消息隊(duì)列中的消息個(gè)數(shù)。接收消息的進(jìn)程名或標(biāo)示符接收進(jìn)程名1、消息緩沖區(qū)的結(jié)構(gòu)發(fā)送進(jìn)程名消息長度消息正文指針消息緩沖區(qū)493、Send和Receive原語發(fā)送進(jìn)程A接收進(jìn)程B的PCB接收進(jìn)程B………..Send(B,消息)………..接收進(jìn)程名B消息長度Size消息正文Text緩沖區(qū)指針………..………..……………隊(duì)首指針PmMutex,Sem…………………………Next接收進(jìn)程名B消息長度Size消息正文TextNil………..Receive(A,消息)………..接收進(jìn)程名B消息長度Size消息正文Text緩沖區(qū)指針………..………..………..發(fā)送進(jìn)程名A發(fā)送進(jìn)程名A發(fā)送進(jìn)程名A3、Send和Receive原語發(fā)送進(jìn)程A接收進(jìn)程B的PCB50Send(Receiver,信件）向系統(tǒng)申請消息緩沖區(qū)；將所要發(fā)送消息復(fù)制到消息緩沖區(qū)；查找Receiver進(jìn)程的PCB表；

P(Mutex);將消息緩沖區(qū)鏈接到Receiver的PCB鏈上；

V(Mutex);

V(Sem);返回;Receiver(Sender,信件）P(Sem)；

P(Mutex)；取消息鏈上Receiver進(jìn)程發(fā)出的消息；將此消息復(fù)制到接收進(jìn)程的接收區(qū)內(nèi);釋放緩沖區(qū)；

V(Mutex);返回;Send(Receiver,信件）向系統(tǒng)申請消息緩沖區(qū)；將51二、信箱方式消息緩沖方式是系統(tǒng)統(tǒng)一管理空緩沖區(qū)，為系統(tǒng)中所有進(jìn)程共享。而信箱方式是指在發(fā)送進(jìn)程和接收進(jìn)程之間建立一個(gè)郵箱實(shí)現(xiàn)信息通信的一種方式，也就是說郵箱是發(fā)送進(jìn)程和接收進(jìn)程的私有數(shù)據(jù)結(jié)構(gòu)。

信箱信箱頭：信箱名稱、大小、傳輸方向、擁有該信箱的進(jìn)程名等信箱體：存放信件。分成若干塊，一塊存放一個(gè)信件。（信箱數(shù)據(jù)結(jié)構(gòu)定義及發(fā)送（SEND）、接收（RECEIVE）原語見書51）。二、信箱方式消息緩沖方式是系統(tǒng)統(tǒng)一管理空緩沖區(qū)，為系52第七節(jié)死鎖一、死鎖的產(chǎn)生前面我們介紹了多道程序環(huán)境下并發(fā)程序的執(zhí)行帶來的眾多問題，這一節(jié)繼續(xù)討論另外一個(gè)問題—死鎖。12341234例1：交通死鎖第七節(jié)死鎖一、死鎖的產(chǎn)生前面我們介紹了多道程序環(huán)53二、死鎖的定義在多道程序系統(tǒng)中，由于程序的并發(fā)執(zhí)行，雖然提高了系統(tǒng)資源的利用率和系統(tǒng)的處理能力，但也帶來了一些新的問題，如我們前面講的互斥、同步等問題，除此之外，也可能會出現(xiàn)一種更危險(xiǎn)的情況：當(dāng)某一進(jìn)程提出資源的使用請求后，使得系統(tǒng)中的一些進(jìn)程處于無休止的阻塞狀態(tài)，在無外力的作用下，這些進(jìn)程永遠(yuǎn)都不能前進(jìn)。因此我們給出死鎖的定義。

死鎖：是指并發(fā)進(jìn)程彼此互相等待對方占有的資源，而這些進(jìn)程在得到對方占有的資源之前又不會釋放自己占有資源，從而造成進(jìn)程永遠(yuǎn)無法執(zhí)行的狀態(tài)，死鎖不僅會給系統(tǒng)造成資源的浪費(fèi)，甚至導(dǎo)致整個(gè)系統(tǒng)崩潰，因此我們分析一下造成死鎖的因素。二、死鎖的定義在多道程序系統(tǒng)中，由于程序的并發(fā)執(zhí)54二、造成死鎖的因素1)具有多個(gè)進(jìn)程。多道程序環(huán)境的特點(diǎn)。2)多個(gè)資源。同類型資源多個(gè)單位；不同類型資源多個(gè)種類，如果只有一個(gè)資源，只要互斥使用即可。3)部分分配。對各進(jìn)程所需資源只分配一部分，否則無死鎖。4)申請與釋放資源的動態(tài)性、分散性和獨(dú)立性。動態(tài)性是指進(jìn)程申請、釋放資源的隨機(jī)性；分散性是指進(jìn)程獲取資源后自己釋放，系統(tǒng)無權(quán)干涉；獨(dú)立性是指資源分配與使用的分離，進(jìn)程得到資源后并不一定一直使用，也可能閑置，但其他進(jìn)程卻無法使用。

以上因素反映了多道程序環(huán)境下并發(fā)進(jìn)程與有限資源多種矛盾，因此必須解決這些矛盾，使系統(tǒng)有條不紊地運(yùn)行。二、造成死鎖的因素1)具有多個(gè)進(jìn)程。多道程序環(huán)境的特點(diǎn)。255三、死鎖產(chǎn)生的條件

死鎖的起因是并發(fā)進(jìn)程的資源競爭。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個(gè)數(shù)少于并發(fā)進(jìn)程所要求的該類資源數(shù)。顯然，由于資源的有限性，不可能為所有要求資源的進(jìn)程無限制地提供資源。但是可以采用適當(dāng)?shù)乃惴?，達(dá)到消除死鎖的目的。1)互斥。任何資源在任何時(shí)刻只能被一個(gè)進(jìn)程使用。3)占有且等待。進(jìn)程在等待申請資源的過程中，原占有資源保持不變。4)循環(huán)等待。發(fā)生死鎖時(shí)，系統(tǒng)中必存在一進(jìn)程循環(huán)等待鏈即前一進(jìn)程占有著后一進(jìn)程所要求的資源。2)非剝奪。進(jìn)程占有的資源，該進(jìn)程以外的進(jìn)程不得搶占，只能由占有者釋放。三、死鎖產(chǎn)生的條件死鎖的起因是并發(fā)進(jìn)程的資源競爭56四、死鎖的解決方法

上面四條是死鎖產(chǎn)生的必要條件，若同時(shí)滿足了這四個(gè)條件死鎖便產(chǎn)生了。解決死鎖的方法一般可分為預(yù)防、避免、檢測和恢復(fù)等三種。1、死鎖的預(yù)防

死鎖的預(yù)防就是預(yù)先防止死鎖的發(fā)生，那么只要破壞死鎖產(chǎn)生的四個(gè)必要條件中任何一條就可以預(yù)防死鎖的產(chǎn)生。

a.破壞互斥。就是說允許一個(gè)資源可由多個(gè)進(jìn)程同時(shí)使用，

但系統(tǒng)中多數(shù)資源必須互斥使用，此法不宜使用。

b.破壞非剝奪。當(dāng)某進(jìn)程申請某一互斥資源時(shí)，如被拒絕，則在進(jìn)程進(jìn)入阻塞狀態(tài)前由操作系統(tǒng)剝奪或自行釋放已占有的所有資源，待以后系統(tǒng)再行分配。但為了保護(hù)進(jìn)程資源現(xiàn)場和以后的再次恢復(fù)，系統(tǒng)需付出高昂代價(jià)。四、死鎖的解決方法上面四條是死鎖產(chǎn)生的必要條件57

c.破壞占有且等待或循環(huán)等待。為達(dá)到此目的，可以采用資源靜態(tài)分配和層次（順序）分配兩種方式：*靜態(tài)分配方式

靜態(tài)分配是指一個(gè)進(jìn)程在被創(chuàng)建時(shí)就賦予它全部所需的資源，只有在該進(jìn)程所需的資源都得到滿足的條件下，進(jìn)程才開始執(zhí)行。

此策略可以破壞占有且等待條件，可以預(yù)防死鎖。但這種策略嚴(yán)重地降低了資源的利用率。因?yàn)檫@些被占有資源有的到進(jìn)程執(zhí)行的后半期才被使用，甚至只有例外的情況下才被用到，而其它進(jìn)程又申請不到這些被占有資源。因此這種方式是低效的，原因有三：

?進(jìn)程因等待所需要的資源阻塞時(shí)間過長，一部分即可；

?部分資源可能在相當(dāng)長的時(shí)間內(nèi)變得不可用；

?進(jìn)程一次性知道所需全部資源不太可能。c.破壞占有且等待或循環(huán)等待。為達(dá)到此目的，可以采用資58*層次（順序）分配方式

層次分配方式的基本思想是將系統(tǒng)中的資源分成若干個(gè)層次，每個(gè)層次中包含有若干個(gè)資源。

?某進(jìn)程得到某一層的一個(gè)資源后，它只能再申請本層次或比本層次更高一層的資源；

?釋放資源時(shí)，先釋放較高層次的資源，后釋放較低層次的資源；

?一個(gè)進(jìn)程得到某一層的資源后，若想再申請?jiān)搶又械牧硪毁Y源時(shí)，必須先釋放該層中已占有的所有其它資源。

此種策略可防止循環(huán)等待情況的發(fā)生。此策略的一種特例就是將系統(tǒng)資源排成一個(gè)序列：RS1,RS2,…..RSn,某進(jìn)程申請了RSi(1<=I<=n)后不得再申請RSj(j<i)。如系統(tǒng)中：#1:卡片讀入機(jī)，#2:打印機(jī)，#3:繪圖儀，#4:磁帶輸入機(jī)。申請：卡片讀入機(jī)，繪圖儀，磁帶輸入機(jī)予以分配。申請：打印機(jī)，卡片讀入機(jī)，繪圖儀不予分配。*層次（順序）分配方式層次分配方式的基592、死鎖的檢測和解除上面講述的各種方法雖然能很好地對死鎖進(jìn)行預(yù)防和避免，但它存在的問題就是資源的利用率不高，況且各種算法會增加系統(tǒng)的開銷。因此解決死鎖的另一種途徑就是對死鎖進(jìn)行檢測。基本思想是系統(tǒng)對資源的分配不加任何限制，系統(tǒng)定時(shí)判斷死鎖是否已經(jīng)出現(xiàn)，若檢查出現(xiàn)了死鎖，則采取一定措施解除死鎖。a.死鎖的檢測方法

操作系統(tǒng)設(shè)置兩張表格，一張表記錄被阻塞進(jìn)程等待資源的情況，另一張表記錄已占有資源的情況，即哪些進(jìn)程占有什么資源，我們不妨稱其為Table1和Table2。

如果進(jìn)程申請某一資源時(shí)，若該資源空閑，則進(jìn)行分配，同時(shí)將該資源填資源占有情況表，即Table2;否則，阻塞該進(jìn)程填寫進(jìn)程等待資源表，即Table1。

操作系統(tǒng)定期檢查Table1和Table2，如果進(jìn)程Pi等待Rk資源，而Rk又被Pj進(jìn)程占用，則認(rèn)為Pi和Pj因該資源具有等2、死鎖的檢測和解除上面講述的各種方法雖然能很好地60待關(guān)系，并記為W(Pi,Pj)。系統(tǒng)記下所有等待關(guān)系，如果出現(xiàn)如下序列：W(Pi,Pj),W(Pj,Pk),………W(Ps,Pm),W(Pm,Pi)，則操作系統(tǒng)就認(rèn)為系統(tǒng)中存在一組循環(huán)等待資源的進(jìn)程：Pi,Pj,……Ps,Pm,因而認(rèn)為出現(xiàn)了死鎖。b.死鎖的解除方法如果檢測到死鎖，系統(tǒng)就必須采用某種恢復(fù)技術(shù)解除死鎖：

?結(jié)束所有進(jìn)程，并重新啟動操作系統(tǒng)；

?結(jié)束所有卷入死鎖的進(jìn)程；

?一次結(jié)束卷入死鎖的一個(gè)進(jìn)程，然后再次檢測直到死鎖消失為止；

?從一個(gè)或多個(gè)卷入死鎖的進(jìn)程中搶占資源，把這些資源分配給卷入死鎖的其它進(jìn)程之一，然后恢復(fù)執(zhí)行；待關(guān)系，并記為W(Pi,Pj)。系統(tǒng)記下所有等待關(guān)系，如果出61在實(shí)際操作系統(tǒng)中，一般都是采用多種方法的組合，而并非采用單一的方法來解決死鎖問題，如對資源進(jìn)行分類，對外設(shè)類使用死鎖避免的方法，而對存儲系統(tǒng)使用預(yù)防的方法。總之，解決死鎖問題要綜合考慮。在實(shí)際操作系統(tǒng)中，一般都是采用多種方法的組合，62第八節(jié)處理器調(diào)度

處理器是計(jì)算機(jī)系統(tǒng)中的重要資源，處理器調(diào)度算法不僅對處理器的利用效率和用戶進(jìn)程的執(zhí)行有影響，同時(shí)還與內(nèi)存等其他資源的使用密切相關(guān)，對整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)也有重要影響。一、處理器調(diào)度類型

從處理器調(diào)度的對象、時(shí)間、功能等角度出發(fā)，將處理器調(diào)度分為宏觀調(diào)度、中級調(diào)度和微觀調(diào)度三個(gè)層次。（1）宏觀調(diào)度。從用戶工作流程的角度，一個(gè)作業(yè)提交幾個(gè)流程，其中每個(gè)程序按照流程進(jìn)行調(diào)度執(zhí)行；（2）中級調(diào)度。涉及進(jìn)程在內(nèi)外存之間的交換。（3）微觀調(diào)度。也稱低級調(diào)度，從處理器資源分配的角度來看，處理器需要經(jīng)常選擇就緒進(jìn)程進(jìn)入運(yùn)行狀態(tài)，因此微觀調(diào)度的尺度是毫秒級的，宏觀調(diào)度的尺度是分鐘、小時(shí)或天，中級調(diào)度則是秒級的。第八節(jié)處理器調(diào)度處理器是計(jì)63就緒掛起掛起就緒調(diào)度執(zhí)行釋放退出等待事件阻塞事件出現(xiàn)超時(shí)阻塞掛起激活事件出現(xiàn)激活掛起提交提交創(chuàng)建宏觀調(diào)度中級調(diào)度微觀調(diào)度就緒掛起掛起就緒調(diào)度執(zhí)行釋放退出等待事件阻塞事件出現(xiàn)超時(shí)阻塞64

三、進(jìn)程調(diào)度(處理機(jī)調(diào)度)算法的功能（1）記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況。

a.各進(jìn)程的執(zhí)行情況和狀態(tài)特征記錄在各進(jìn)程的PCB表中；

b.根據(jù)各進(jìn)程的狀態(tài)特征和資源需求，將各進(jìn)程的PCB排成相應(yīng)隊(duì)列并進(jìn)行動態(tài)隊(duì)列轉(zhuǎn)換；

c.根據(jù)PCB掌握各進(jìn)程的執(zhí)行情況和狀態(tài)特征。三、進(jìn)程調(diào)度(處理機(jī)調(diào)度)算法的功能（1）記錄65（2）選擇占有處理機(jī)的進(jìn)程。

按照一定的策略選擇一個(gè)處于就緒狀態(tài)的進(jìn)程，使其獲得處理機(jī)執(zhí)行。（3）進(jìn)行進(jìn)程的上下文轉(zhuǎn)換。

進(jìn)程的執(zhí)行是在進(jìn)程的上下文中執(zhí)行，當(dāng)正在執(zhí)行的進(jìn)程由于某種原因讓出處理機(jī)時(shí)，系統(tǒng)要在該進(jìn)程的PCB中保留足夠的信息，以便該進(jìn)程的恢復(fù)執(zhí)行，然后調(diào)度程序重新選擇一個(gè)新的處于就緒狀態(tài)的進(jìn)程，并裝配該進(jìn)程的上下外文，使CPU控制權(quán)轉(zhuǎn)換到被選中進(jìn)程。四、進(jìn)程調(diào)度的時(shí)機(jī)(1)正在執(zhí)行的進(jìn)程執(zhí)行完畢；(2)執(zhí)行中的進(jìn)程自己調(diào)用阻塞原語而進(jìn)入等待狀態(tài)；(3)執(zhí)行中進(jìn)程調(diào)用P原語因資源不足而被阻塞；或調(diào)用V原語激活等待資源的等待進(jìn)程；（2）選擇占有處理機(jī)的進(jìn)程。（3）進(jìn)行進(jìn)程的上下文轉(zhuǎn)換。四、66(4)在分時(shí)系統(tǒng)中時(shí)間片用完；(5)在可剝奪方式下，如果就緒隊(duì)列中的某進(jìn)程的優(yōu)先級高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級時(shí)，也引發(fā)進(jìn)程調(diào)度。五、調(diào)度算法

下面討論幾種調(diào)度算法，由于算法設(shè)計(jì)的出發(fā)點(diǎn)不同，他們各自適應(yīng)的場合也不同。有的適合于宏觀調(diào)度，有的算法則適合于微觀調(diào)度，而有的則適合于多種場合。1、先來先服務(wù)（FirstComeFirstService)顧名思義，其基本思想是按進(jìn)程的到達(dá)先后順序進(jìn)行調(diào)度。(1)、按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序分派CPU;(2)、當(dāng)前作業(yè)或進(jìn)程占用CPU，直到執(zhí)行完或阻塞才讓出CPU;(3)、當(dāng)作業(yè)或進(jìn)程被喚醒，并不立即恢復(fù)執(zhí)行，入就緒隊(duì)列等待;(4)在分時(shí)系統(tǒng)中時(shí)間片用完；(5)在可剝奪方式672、優(yōu)先數(shù)法為每個(gè)進(jìn)程設(shè)置一個(gè)優(yōu)先數(shù)，進(jìn)程調(diào)度程序每次選擇就緒隊(duì)列中優(yōu)先數(shù)最大者占有處理機(jī)。確定進(jìn)程優(yōu)先數(shù)的考慮因素：

a.使用外設(shè)頻繁著優(yōu)先數(shù)大，提高外設(shè)CPU的并行性。b.重要程序優(yōu)先數(shù)大，有利于用戶。。

c.進(jìn)入計(jì)算機(jī)時(shí)間長的優(yōu)先數(shù)大，有利于縮短作業(yè)完成時(shí)間。

d.交互用戶的進(jìn)程優(yōu)先數(shù)大，有利于終端用戶的響應(yīng)時(shí)間。（1）靜態(tài)優(yōu)先數(shù)法：在創(chuàng)建進(jìn)程時(shí)，操作系統(tǒng)根據(jù)優(yōu)先數(shù)的確定原則確定該進(jìn)程的優(yōu)先數(shù)，而且在進(jìn)程的生命期內(nèi)該優(yōu)先數(shù)不再改變，稱為靜態(tài)優(yōu)先數(shù)。確定原則：

a.根據(jù)進(jìn)程的類型確定。系統(tǒng)進(jìn)程>用戶進(jìn)程；用戶進(jìn)程I/O相關(guān)的>其他類型的用戶進(jìn)程；分時(shí)系統(tǒng)前臺進(jìn)程>后臺進(jìn)程2、優(yōu)先數(shù)法為每個(gè)進(jìn)程設(shè)置一個(gè)優(yōu)先數(shù)，進(jìn)程調(diào)度程序68

b.根據(jù)進(jìn)程使用資源的狀態(tài)確定。根據(jù)進(jìn)程對系統(tǒng)資源的要求，如CPU占用時(shí)間、內(nèi)存大小、I/O設(shè)備的使用情況等來確定進(jìn)程的優(yōu)先數(shù)大小。這種情況有利于短作業(yè)或進(jìn)程。

c.用戶自己確定進(jìn)程的優(yōu)先數(shù)。這種情況適用于同一用戶的不同進(jìn)程，而不同用戶的進(jìn)程還是有操作系統(tǒng)來確定。（2）動態(tài)優(yōu)先數(shù)法：

動態(tài)優(yōu)先數(shù)方式是指在進(jìn)程創(chuàng)建時(shí)賦予給進(jìn)程一個(gè)優(yōu)先數(shù)，而在進(jìn)程的運(yùn)行過程中可以自動改變，以便獲得更好的調(diào)度性能。影響動態(tài)優(yōu)先數(shù)的因素包括進(jìn)程等待時(shí)間和占用處理機(jī)時(shí)間等。當(dāng)一個(gè)進(jìn)程在就緒隊(duì)列中等待時(shí)間越長，它的優(yōu)先數(shù)越高；其目的就是使優(yōu)先數(shù)較低的進(jìn)程在等待一定時(shí)間后，逐步提高其優(yōu)先數(shù)，進(jìn)而被調(diào)度執(zhí)行。（論年頭）

當(dāng)一個(gè)進(jìn)程占用處理機(jī)的執(zhí)行時(shí)間越長，其優(yōu)先數(shù)逐步降低，目的是讓持續(xù)執(zhí)行的進(jìn)程在降低優(yōu)先數(shù)后讓出處理機(jī)。b.根據(jù)進(jìn)程使用資源的狀態(tài)確定。根據(jù)進(jìn)程對系統(tǒng)資源的要693輪轉(zhuǎn)法：

在分時(shí)系統(tǒng)中，如果仍采用上述算法就不合適了。因?yàn)閮?yōu)先數(shù)低的進(jìn)程可能會在長時(shí)間內(nèi)的不到CPU的服務(wù)，這在分時(shí)系統(tǒng)中是絕對不允許的。因?yàn)榉謺r(shí)系統(tǒng)要求對用戶的響應(yīng)要及時(shí)、快速。其基本思想是：系統(tǒng)確定一個(gè)適當(dāng)大小的時(shí)間片，所有進(jìn)程排成一個(gè)就緒隊(duì)列按時(shí)間片輪流使用CPU。確定時(shí)間片應(yīng)考慮的因素：

a.系統(tǒng)的響應(yīng)時(shí)間；進(jìn)程數(shù)一定，時(shí)間片與響應(yīng)時(shí)間成正比；

b.就緒隊(duì)列中進(jìn)程數(shù)；系統(tǒng)響應(yīng)時(shí)間一定時(shí)，時(shí)間片與進(jìn)程就緒隊(duì)列中的數(shù)目成反比，用戶越多，時(shí)間片應(yīng)越小，反之越大；

c.進(jìn)程的切換時(shí)間；設(shè)計(jì)時(shí)確定一個(gè)標(biāo)準(zhǔn)，如1/10；

d.CPU的執(zhí)行速度；如果CPU速度快，時(shí)間片長，反之則短；3輪轉(zhuǎn)法：在分時(shí)系統(tǒng)中，如果仍采用上述算法就不70時(shí)間片計(jì)算公式：Q=T/N;其中Q為時(shí)間片大小，T為響應(yīng)時(shí)間，N為就緒隊(duì)列中進(jìn)程的個(gè)數(shù)。

這種固定時(shí)間片法簡單有效，但有時(shí)為提高CPU效率、減少進(jìn)程切換次數(shù)降低系統(tǒng)開銷，又可采用可變時(shí)間片輪轉(zhuǎn)法。它的基本思想是：每當(dāng)一輪調(diào)度開始時(shí)，系統(tǒng)便根據(jù)就緒隊(duì)列中現(xiàn)有進(jìn)程的數(shù)目計(jì)算一次時(shí)間片，作為新一輪調(diào)度的時(shí)間片。這樣對減少系統(tǒng)開銷和提高響應(yīng)時(shí)間都是有利的。4多級隊(duì)列法：

多級隊(duì)列法就是引入多個(gè)就緒隊(duì)列，通過各隊(duì)列的區(qū)別對待，達(dá)到一個(gè)綜合的調(diào)度目標(biāo)。如將系統(tǒng)進(jìn)程、用戶進(jìn)程、批處理進(jìn)程分別入不同的就緒隊(duì)列，不同隊(duì)列的優(yōu)先級、時(shí)間片、調(diào)度策略不同。時(shí)間片計(jì)算公式：Q=T/N;這種固71（5）多級反饋隊(duì)列法：多級反饋隊(duì)列算法是時(shí)間片算法和優(yōu)先數(shù)算法的一種綜合使用。與多隊(duì)列法的不同之處是它是按進(jìn)程使用CPU時(shí)間的長短這一特征來劃分隊(duì)列的。..隊(duì)列1（Q=8)隊(duì)列2(Q=16)隊(duì)列n2n(先來先服務(wù)）時(shí)間片增加優(yōu)先級變小（5）多級反饋隊(duì)列法：多級反饋隊(duì)列算法是時(shí)間片算72

多級反饋隊(duì)列算法可兼顧多方面的系統(tǒng)目標(biāo)。如提高系統(tǒng)的吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程；為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧I/O型進(jìn)程。因此這種調(diào)度算法是最通用的CPU調(diào)度算法，但它也是最復(fù)雜的策略。一個(gè)作業(yè)或進(jìn)程剛進(jìn)入就緒隊(duì)列時(shí)，先放到隊(duì)列1，如果在該隊(duì)列所屬時(shí)間片內(nèi)沒有完成，則自動沉入隊(duì)列2，依次類推。各隊(duì)列的運(yùn)行順序是：調(diào)度程序先運(yùn)行隊(duì)列1中的叫做業(yè)或進(jìn)程，只有隊(duì)列1空時(shí)，才調(diào)度執(zhí)行隊(duì)列2中的作業(yè)或進(jìn)程；而且當(dāng)?shù)图夑?duì)列中的進(jìn)程正在執(zhí)行時(shí)，如果高級隊(duì)列中有進(jìn)程到來，則有可能搶占正在運(yùn)行進(jìn)程的CPU.多級反饋隊(duì)列算法可兼顧多方面的系統(tǒng)目標(biāo)。如提高系統(tǒng)73第三章存儲器管理?計(jì)算機(jī)存儲層次?分區(qū)式管理?頁式管理?段式與段頁式管理

第三章存儲器管理?計(jì)算機(jī)存儲層次74第一節(jié)內(nèi)存管理概述一、計(jì)算機(jī)存儲層次寄存器內(nèi)存外存容量速度成本存取速度小大高高低低高低當(dāng)前CPU正在執(zhí)行的指令及被處理的數(shù)據(jù)當(dāng)前CPU正在運(yùn)行的程序代碼及數(shù)據(jù)所有信息第一節(jié)內(nèi)存管理概述一、計(jì)算機(jī)存儲層次寄存器內(nèi)存外存容量75二、內(nèi)存硬件使用特性:微觀角度(指令級)和宏觀角度(程序級)

1、微觀角度（1）程序?qū)?nèi)存的使用體現(xiàn)為程序向內(nèi)存發(fā)出的一次次讀寫請求。

MOVEAX,[1000H](2)、內(nèi)存接受的讀寫請求可能來自CPU或DMA2、宏觀角度從宏觀角度看程序?qū)?nèi)存的使用,主要是意識到內(nèi)存空間和程序空間的存在.二、內(nèi)存硬件使用特性:微觀角度(指令級)和宏觀角度(程序級)76三、用戶對內(nèi)存的使用要求

1、在使用內(nèi)存時(shí)不希望涉及內(nèi)存物理細(xì)節(jié).

2、用戶程序執(zhí)行前的裝入工作,是與應(yīng)用無關(guān)的,不應(yīng)由用戶程序來承擔(dān).3、對內(nèi)存容量和利用率.要滿足用戶大程序和多任務(wù)的要求;避免內(nèi)存有足夠的空閑空間,而用戶程序卻無法裝入運(yùn)行;對超過內(nèi)存容量的大程序裝入束手無策.4、對內(nèi)存存取速度的要求.5、存儲保護(hù)與安全.6、用戶程序運(yùn)行期間的動態(tài)伸縮要求.7、用戶程序的信息共享(程序、數(shù)據(jù)).三、用戶對內(nèi)存的使用要求77四、內(nèi)存管理的任務(wù)和功能1、如何才能使用戶不涉及內(nèi)存物理細(xì)節(jié).

這是由操作系統(tǒng)和編譯程序、硬件共同完成的.首先是高級語言或匯編語言使源程序與可執(zhí)行目標(biāo)程序分化,是源程序得以使用獨(dú)立于物理細(xì)節(jié)的地址和高級語言;其次是可執(zhí)行目標(biāo)程序?qū)?nèi)存物理細(xì)節(jié)的獨(dú)立性.源程序編譯、鏈接庫函數(shù)目標(biāo)文件（邏輯地址空間）運(yùn)行時(shí)（物理地址空間）地址變換四、內(nèi)存管理的任務(wù)和功能源程序編譯、鏈接庫函數(shù)目標(biāo)文件（邏輯78由于用戶的邏輯地址空間都是從0開始的，而當(dāng)該程序裝如內(nèi)存運(yùn)行時(shí)又不是從0開始，因此就需要將邏輯地址轉(zhuǎn)換成實(shí)際的內(nèi)存地址。0：.1:.10:loadA,[500]..500:12345邏輯地址100：.101:.110:loadA,[500].500：（其他數(shù)據(jù)）600:12345內(nèi)存地址由于用戶的邏輯地址空間都是從0開始的，而當(dāng)該程序裝791)、靜態(tài)重定位

在目標(biāo)程序裝入內(nèi)存時(shí)（程序開始執(zhí)行之前），由操作系統(tǒng)裝配程序一次性完成的重定位過程。它由專門設(shè)計(jì)的程序來完成，無需硬件支持。為了使程序能夠正確執(zhí)行，需要將程序中出現(xiàn)的邏輯地址全部映射成內(nèi)存物理地址，這一映射過程稱為重定位。重定位：由邏輯地址空間到內(nèi)存物理地址空間的映射過程。缺點(diǎn)：a.程序經(jīng)地址重定位后就不能再移動了，因而不能重新分配內(nèi)存，不利于內(nèi)存的有效利用；b.程序在存儲空間中只能連續(xù)分配，不能分布在內(nèi)存的不同區(qū)域；1)、靜態(tài)重定位為了使程序能夠正確執(zhí)行，需要將程序802)、動態(tài)重定位

在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前，完成重定位過程。它需要硬件支持。

a.基址寄存器BR：存放用戶程序分配到的內(nèi)存塊的首地址；

b.程序虛地址寄存器VR：存放程序中涉及到的內(nèi)存的虛地址。

MA=(BR)+(VR)LOADA,500010012345500LOADA,50010012345BR100VR5006002)、動態(tài)重定位a.基址寄存器BR：存放用戶程序分配到的812、如何提高內(nèi)存利用率和彌補(bǔ)用戶對內(nèi)存容量要求與實(shí)際內(nèi)存容量之間的差距.

內(nèi)存管理的大部分內(nèi)容都是以提高內(nèi)存的利用率為目的的,詳見具體管理方法.當(dāng)用戶對內(nèi)存要求超過實(shí)際內(nèi)存容量時(shí):

a.程序多、空間小,裝不下:采用交換、虛擬等技術(shù);

b.程序大、空間小,裝不下:采用虛擬、覆蓋動態(tài)裝入等技術(shù).

所有技術(shù)的理論根據(jù)是局部性原理.3、如何解決內(nèi)存速度與CPU速度不匹配問題.

a.高速緩存Cache.若存在Cache命中率98%.

b.盡量減少各種提高內(nèi)存利用率技術(shù)所帶來的副作用.2、如何提高內(nèi)存利用率和彌補(bǔ)用戶對內(nèi)存容量要求與實(shí)際內(nèi)存容量824、如何滿足系統(tǒng)和用戶的安全要求.

出于安全方面的考慮,內(nèi)存保護(hù)通常由操作系統(tǒng)和硬件共同完成.

在多道程序設(shè)計(jì)環(huán)境下，有許多程序段和數(shù)據(jù)是可供多個(gè)用戶共享的，而且，每一個(gè)用戶的進(jìn)程又只能在自己的內(nèi)存區(qū)運(yùn)行，不能破壞和干擾其它用戶進(jìn)程的運(yùn)行，更不能破壞系統(tǒng)程序100上界寄存器200下界寄存器100200被保護(hù)程序100<=訪問地址<=2004、如何滿足系統(tǒng)和用戶的安全要求.在多道程序設(shè)計(jì)835、如何滿足用戶程序的動態(tài)伸縮要求.

具體實(shí)現(xiàn)方法是依不同的內(nèi)存管理模式而異.5、如何滿足用戶程序的動態(tài)伸縮要求.84第二節(jié)分區(qū)存儲管理

分區(qū)管理就是把內(nèi)存劃分成若干個(gè)大小不等的區(qū)域，除操作系統(tǒng)占用一個(gè)區(qū)域之外，其余由多道環(huán)境下的各并發(fā)進(jìn)程共享，它是滿足多道程序設(shè)計(jì)的一種最簡單的存儲管理方法。我們結(jié)合分區(qū)原理來討論分區(qū)存儲管理時(shí)地址變換、內(nèi)存的分配與釋放等問題。一、固定式分區(qū)法

1、分區(qū)方法：

把內(nèi)存固定地劃分為若干個(gè)大小不等的區(qū)域。如可劃分成長作業(yè)區(qū)和短作業(yè)區(qū)。分區(qū)一旦劃分結(jié)束，每個(gè)分區(qū)的長度和總分區(qū)數(shù)將保持不便。

系統(tǒng)對內(nèi)存的管理和控制通過數(shù)據(jù)結(jié)構(gòu)分區(qū)說明表進(jìn)行，它包括分區(qū)號、分區(qū)大小、起始地址、分區(qū)狀態(tài)等信息。分區(qū)的分配、釋放、存儲保護(hù)以及地址變換都通過該表進(jìn)行。第二節(jié)分區(qū)存儲管理分區(qū)管理就是把內(nèi)存劃分成85區(qū)號長度起始地址狀態(tài)1238K32K64K20K28K60K1114132K124K0020K28K60K124K操作系統(tǒng)進(jìn)程A(6K)進(jìn)程B(25K)進(jìn)程C(36K)256K分區(qū)1分區(qū)2分區(qū)3分區(qū)4(a)分區(qū)說明表(B)內(nèi)存相應(yīng)狀態(tài)2、分配回收算法

操作系統(tǒng)為作業(yè)或進(jìn)程分配內(nèi)存時(shí)有兩種方法，一種是絕對地址轉(zhuǎn)換的分配法，即將作業(yè)或進(jìn)程分成多個(gè)隊(duì)列，但內(nèi)存浪費(fèi)大（見書）；另一種是可重定位的分配法，將所有作業(yè)和進(jìn)程排成一個(gè)隊(duì)列，它們可在任何滿足要求的區(qū)中運(yùn)行。區(qū)號長度起始地址狀態(tài)1238K32K64K20K28K60K86要求x大小分區(qū)取分區(qū)表第一項(xiàng)表結(jié)束？空閑？長度>=x？修改狀態(tài)位返回分區(qū)號取下一項(xiàng)無法分配YNYNYN

分配：

當(dāng)用戶程序要裝入內(nèi)存執(zhí)行時(shí)，存儲管理程序根據(jù)用戶程序要求查詢內(nèi)存分區(qū)表，從中找出一個(gè)滿足要求的空閑分區(qū)，將其分配給申請者。算法如右圖。

釋放：用戶進(jìn)程執(zhí)行完畢，存儲管理程序?qū)⒎謪^(qū)表中相應(yīng)的分區(qū)標(biāo)志置為“空閑”即可。要求x大小分區(qū)取分區(qū)表第一項(xiàng)表結(jié)束？空閑？長度>=x？修改狀87二、動態(tài)分區(qū)法

1、分區(qū)方法：

動態(tài)分區(qū)法在作業(yè)或進(jìn)程執(zhí)行前并不建立分區(qū)，分區(qū)的建立是在作業(yè)或進(jìn)程的執(zhí)行過程中進(jìn)行的。在系統(tǒng)初期時(shí)，除了操作系統(tǒng)常住內(nèi)存部分之外，只有一個(gè)空閑分區(qū)，隨后，分配程序?qū)⒃搮^(qū)劃分給調(diào)度選中的作業(yè)和進(jìn)程。如下圖所示：OSOSOSOS進(jìn)程A進(jìn)程A進(jìn)程A進(jìn)程A12進(jìn)程B3進(jìn)程B進(jìn)程C4進(jìn)程B進(jìn)程C進(jìn)程D進(jìn)程A8K進(jìn)程B16K進(jìn)程C64K進(jìn)程D124K二、動態(tài)分區(qū)法1、分區(qū)方法：OSOSOSOS進(jìn)程A進(jìn)88

隨著進(jìn)程的執(zhí)行，會出現(xiàn)一系列的分配和釋放，假設(shè)如下：C進(jìn)程結(jié)束-E進(jìn)程申請50K-F進(jìn)程申請16K-B進(jìn)程釋放-D進(jìn)程釋放。內(nèi)存變化過程如下：操作系統(tǒng)A(8K)B(16K)C(64K)D(124K)24K空閑操作系統(tǒng)A(8K)B(16K)64K空閑D(124K)24K空閑操作系統(tǒng)A(8K)B(16K)E(50K)14K空閑D(124K)24K空閑操作系統(tǒng)A(8K)B(16K)E(50K)14K空閑D(124K)F(16K)8K空閑操作系統(tǒng)A(8K)B(16K)E(50K)合并138K空閑F(16K)8K空閑操作系統(tǒng)A(8K)16K空閑E(50K)14K空閑D(124K)F(16K)8K空閑進(jìn)程C完成進(jìn)程E申請50K進(jìn)程F申請16K進(jìn)程B釋放16K進(jìn)程D釋放124K與14K合并隨著進(jìn)程的執(zhí)行，會出現(xiàn)一系列的分配和釋放，假設(shè)如下89

與固定分區(qū)法相同，動態(tài)分區(qū)法也可采用分區(qū)說明表對內(nèi)存空閑分區(qū)進(jìn)行管理，也可采用可用分區(qū)表或自由鏈方式管理內(nèi)存。

自由鏈就是利用每一個(gè)空閑分區(qū)的前幾個(gè)單元存放本空閑分區(qū)的大小和下一個(gè)空閑分區(qū)的起始地址，從而把所有的空閑分區(qū)連接起來。然后，系統(tǒng)設(shè)置一個(gè)自由鏈?zhǔn)字羔樦赶虻谝粋€(gè)空閑分區(qū)。40K16K78K40K78K24K100K空閑空閑AB

可用表的每個(gè)表目記錄一個(gè)空閑區(qū)，主要參數(shù)包括區(qū)號、長度和起始地址。區(qū)號分區(qū)長度起始地址1316K24K40K78K100K59K100K與固定分區(qū)法相同，動態(tài)分區(qū)法也可采用分區(qū)說明表對90

2、動態(tài)分區(qū)的分配：

動態(tài)分區(qū)的分配主要解決三個(gè)問題：a.

對于用戶作業(yè)或進(jìn)程的內(nèi)存要求，從可用表或自由鏈中尋找合適的空閑區(qū)進(jìn)行分配：b.

分配空閑區(qū)之后，更新可用表或自由鏈：