操作系統(tǒng)課件

操作系統(tǒng)引論1.0什么是操作系統(tǒng)1.0.1計算機系統(tǒng)的組成1.0.2操作系統(tǒng)的定義1.0.3操作系統(tǒng)在軟硬件層次中的地位1.0.1計算機系統(tǒng)的組成

輸入設(shè)備：鍵盤、鼠標(biāo)、掃描儀

輸出設(shè)備：顯示器、打印機

外

存：軟、硬盤、光盤、閃存

網(wǎng)絡(luò)設(shè)備：網(wǎng)卡、調(diào)制解調(diào)器等

計算機系統(tǒng)軟件外部設(shè)備系統(tǒng)軟件應(yīng)用軟件硬件運算器控制器主機內(nèi)存CPU隨機存儲器(RAM)只讀存儲器(ROM)高速緩沖存儲器

操作系統(tǒng)：Windows、Unix、Linux語言處理程序：C、Pascal、VB等實用程序：診斷程序、排錯程序等

辦公軟件包、數(shù)據(jù)庫管理系統(tǒng)

1.0.2操作系統(tǒng)的定義

操作系統(tǒng)是計算機系統(tǒng)的一個系統(tǒng)軟件，它直接控制和管理計算機系統(tǒng)中的硬件及軟件資源，合理的組織計算機工作流程，以便有效的利用這些資源為用戶提供一個功能強大、使用方便和可擴展的工作環(huán)境，從而在計算機與其用戶之間起到接口的作用。操作系統(tǒng)（operatingsystem，簡稱OS）1.0.3操作系統(tǒng)在軟硬件層次中的地位

裸機操作系統(tǒng)編譯軟件應(yīng)用軟件1.1操作系統(tǒng)的目標(biāo)和作用1.1.1操作系統(tǒng)的目標(biāo)1.1.2操作系統(tǒng)的作用1.1.3推動操作系統(tǒng)發(fā)展的主要動力1.1.1操作系統(tǒng)的目標(biāo)

目前存在著多種類型的OS，不同類型的OS，其目標(biāo)各有所側(cè)重。通常在計算機硬件上配置的OS，其目標(biāo)有以下幾點：

1.方便性

2.有效性

3.可擴充性

4.開放性1.1.2操作系統(tǒng)的作用1.OS作為用戶與計算機硬件系統(tǒng)之間的接口

OS作為用戶與計算機硬件系統(tǒng)之間接口的含義是：OS處于用戶與計算機硬件系統(tǒng)之間，用戶通過OS來使用計算機系統(tǒng)?；蛘哒f，用戶在OS幫助下，能夠方便、快捷、安全、可靠地操縱計算機硬件和運行自己的程序。應(yīng)注意，OS是一個系統(tǒng)軟件，因而這種接口是軟件接口。圖1-1OS作為接口的示意圖用戶應(yīng)用程序系統(tǒng)調(diào)用命令圖標(biāo)、窗口操作系統(tǒng)計算機硬件

(1)命令方式。這是指由OS提供了一組聯(lián)機命令(語言)，用戶可通過鍵盤輸入有關(guān)命令，來直接操縱計算機系統(tǒng)。

(2)系統(tǒng)調(diào)用方式。OS提供了一組系統(tǒng)調(diào)用，用戶可在自己的應(yīng)用程序中通過相應(yīng)的系統(tǒng)調(diào)用，來操縱計算機。

(3)圖形、窗口方式。用戶通過屏幕上的窗口和圖標(biāo)來操縱計算機系統(tǒng)和運行自己的程序。2.OS作為計算機系統(tǒng)資源的管理者

處理機管理，用于分配和控制處理機；

存儲器管理，主要負責(zé)內(nèi)存的分配與回收；

I/O設(shè)備管理，負責(zé)I/O設(shè)備的分配與操縱；

文件管理，負責(zé)文件的存取、共享和保護。

3.OS用作擴充機器

把覆蓋了軟件的機器稱為擴充機器或虛機器。

OS包含了若干個層次，因此在裸機上覆蓋OS后，便可獲得一臺功能顯著增強，使用極為方便的多層擴充機器或多層虛機器。1.1.3推動操作系統(tǒng)發(fā)展的主要動力不斷提高計算機資源利用率2.方便用戶3.器件的不斷更新?lián)Q代4.計算機體系結(jié)構(gòu)的不斷發(fā)展1.2操作系統(tǒng)的發(fā)展過程1.2.1無操作系統(tǒng)的計算機系統(tǒng)1.2.2單道批處理系統(tǒng)1.2.3多道批處理系統(tǒng)1.2.4分時系統(tǒng)1.2.5實時系統(tǒng)1.2.1無操作系統(tǒng)的計算機系統(tǒng)1.人工操作方式電子管計算機時代（1945年到50年代中期），無操作系統(tǒng)。由手工控制作業(yè)的輸入輸出,通過控制臺開關(guān)啟動程序運行。用戶使用計算機的過程大致如下：先把程序紙帶裝上輸入機，啟動輸入機把程序和數(shù)據(jù)送入計算機，然后通過控制臺開關(guān)啟動程序運行，計算完畢后，用戶拿走打印結(jié)果，并卸下紙帶。缺點：(1)用戶獨占全機(2)CPU等待人工操作。2.脫機輸入/輸出(Off-LineI/O)方式

用戶使用計算機的過程大致如下：先把程序紙帶裝上輸入機，在外圍機的控制下，輸入到磁帶上，當(dāng)CPU需要時，從磁帶高速調(diào)入內(nèi)存。輸出時，CPU直接高速把數(shù)據(jù)從內(nèi)存送到磁帶，然后在另一臺外圍機的控制下，將磁帶上的結(jié)果通過輸出設(shè)備輸出。脫機輸入/輸出（Off－LineI/O）方式脫離主機的情況下輸入輸出程序和數(shù)據(jù)聯(lián)機輸入/輸出（On－LineI/O）方式在主機的直接控制下輸入輸出程序和數(shù)據(jù)脫機I/O方式的主要優(yōu)點如下：減少了CPU的空閑時間。(2)提高I/O速度。輸入設(shè)備外圍機磁盤主機外圍機輸出設(shè)備圖1-2脫機I/O示意圖1.2.2單道批處理系統(tǒng)(SimpleBatchProcessingSystem)1.單道批處理系統(tǒng)的處理過程圖1-3單道批處理系統(tǒng)的處理流程把下一個作業(yè)的源程序轉(zhuǎn)換為目標(biāo)程序源程序有錯嗎？否裝配目標(biāo)程序還有下一個作業(yè)？是否停止運行目標(biāo)程序是開始2.單道批處理系統(tǒng)的特征單道批處理系統(tǒng)是最早出現(xiàn)的一種OS，嚴格地說，它只能算作是OS的前身而并非是現(xiàn)在人們所理解的OS。盡管如此，該系統(tǒng)比起人工操作方式的系統(tǒng)已有很大進步。該系統(tǒng)的主要特征如下：

(1)自動性。

(2)順序性。

(3)單道性。1.2.3多道批處理系統(tǒng)1.多道程序設(shè)計的基本概念

在單道批處理系統(tǒng)中，內(nèi)存中僅有一道作業(yè)，它無法充分利用系統(tǒng)中的所有資源，致使系統(tǒng)性能較差。為了進一步提高資源的利用率和系統(tǒng)吞吐量，在60年代中期又引入了多道程序設(shè)計技術(shù)，由此而形成了多道批處理系統(tǒng)(MultiprogrammedBatchProcessingSystem)。在該系統(tǒng)中，用戶所提交的作業(yè)都先存放在外存上并排成一個隊列，稱為“后備隊列”；然后，由作業(yè)調(diào)度程序按一定的算法從后備隊列中選擇若干個作業(yè)調(diào)入內(nèi)存，使它們共享CPU和系統(tǒng)中的各種資源。在OS中引入多道程序設(shè)計技術(shù)可帶來以下好處：提高CPU的利用率。比較：圖1-4(a)：單道程序的運行情況圖1-4(b)：多道程序的運行情況（以四道為例）(2)可提高內(nèi)存和I/O設(shè)備利用率。(3)增加系統(tǒng)吞吐量（在單位時間內(nèi)完成的總工作量）。圖1-4單道和多道程序運行情況(b)四道程序運行情況t1t2t3t4t5t6t7t8結(jié)束中斷I/O

完成啟動I/OI/O

中斷請求I/O

完成啟動

I/OI/O

中斷請求用戶程序監(jiān)督程序I/O

操作(a)單道程序運行情況程序A程序AI/O請求程序AI/O完成程序B程序BI/O請求程序C程序CI/O請求程序D程序DI/O請求CI/O完成C再被調(diào)度程序BI/O完成程序A再被調(diào)度程序A程序B程序C程序D調(diào)度程序A完成結(jié)束中斷2.多道批處理系統(tǒng)的特征多道性。(2)無序性。(3)調(diào)度性。3.多道批處理系統(tǒng)的優(yōu)缺點資源利用率高。(2)系統(tǒng)吞吐量大。(3)平均周轉(zhuǎn)時間長。(4)無交互能力。優(yōu)點缺點

作業(yè)的周轉(zhuǎn)時間：是指從作業(yè)進入系統(tǒng)開始，直至其完成并退出系統(tǒng)為止所經(jīng)歷的時間。4.多道批處理系統(tǒng)需要解決的問題處理機管理問題。(2)內(nèi)存管理問題。(3)I/O設(shè)備管理問題。(4)文件管理問題。(5)作業(yè)管理問題。1.2.4分時系統(tǒng)1.分時系統(tǒng)(Time-SharingSystem)的產(chǎn)生

推動多道批處理系統(tǒng)形成和發(fā)展的動力是提高資源利用率和系統(tǒng)吞吐量。推動分時系統(tǒng)形成和發(fā)展的主要動力是用戶的需要：（1）人機交互（2）共享主機（3）便于用戶上機

分時系統(tǒng)是指在一臺主機上連接多個帶有顯示器和鍵盤的終端，同時允許多個用戶通過自己的鍵盤，以交互的方式使用計算機，共享主機中的資源。主機終端2.分時系統(tǒng)實現(xiàn)中的關(guān)鍵問題

如何使用戶能與自己的作業(yè)進行交互，即當(dāng)用戶在自己的終端上鍵入命令時，系統(tǒng)應(yīng)能及時接收并及時處理該命令，再將結(jié)果返回給用戶。即使有多個用戶同時通過自己的鍵盤鍵入命令，系統(tǒng)也應(yīng)能全部地及時接收并處理。(1)及時接收（多路卡和緩沖區(qū)）(2)及時處理（作業(yè)直接進入內(nèi)存，劃分時間片）3.分時系統(tǒng)的特征多路性。(2)獨立性。(3)及時性。(4)交互性。

1.2.5實時系統(tǒng)

實時系統(tǒng)(Real-TimeSystem)是指系統(tǒng)能及時(或即時)響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致地運行。1.應(yīng)用需求實時控制：通常是指以計算機為中心的生產(chǎn)過程控制系統(tǒng)和武器控制系統(tǒng)。(2)實時信息處理：通常是指對信息進行實時處理的系統(tǒng)。2.實時任務(wù)1)按任務(wù)執(zhí)行時是否呈現(xiàn)周期性來劃分周期性實時任務(wù)外部設(shè)備發(fā)出周期性的激勵信號。

(2)非周期性實時任務(wù)外部設(shè)備所發(fā)出的激勵信號并無明顯的周期性，但都必須聯(lián)系著一個截止時間(Deadline)。它又可分為：

①開始截止時間——任務(wù)在某時間以前必須開始執(zhí)行

②完成截止時間——任務(wù)在某時間以前必須完成

2)根據(jù)對截止時間的要求來劃分

(1)硬實時任務(wù)(hardreal-timetask)。系統(tǒng)必須滿足任務(wù)對截止時間的要求，否則可能出現(xiàn)難以預(yù)測的結(jié)果。

(2)軟實時任務(wù)(Softreal-timetask)。它也聯(lián)系著一個截止時間，但并不嚴格，若偶爾錯過了任務(wù)的截止時間，對系統(tǒng)產(chǎn)生的影響也不會太大。3.實時系統(tǒng)與分時系統(tǒng)特征的比較多路性。(2)獨立性。(3)及時性。(4)交互性。(5)可靠性。1.3操作系統(tǒng)的基本特性1.3.1并發(fā)（Concurrence）1.3.2共享（Sharing）1.3.3虛擬（Virtual）1.3.4異步性（Asynchronism）1.3.1并發(fā)(Concurrence)

所謂并發(fā)是指在內(nèi)存中放多道作業(yè)，在一個時間段上來看，每一道作業(yè)都能不同程度地向前推進，但在任何一個時間點上只能有一道占用CPU。與并發(fā)相關(guān)的兩個概念：串行：在內(nèi)存中每次只能放一道作業(yè)，只有它完 全執(zhí)行完后別的作業(yè)才能進入內(nèi)存執(zhí)行。并行：存在于有多個CPU的環(huán)境中，在內(nèi)存中放 多道作業(yè)，在任一時間點上都可能有多道 作業(yè)在不同的CPU上同時執(zhí)行。1.3.2共享(Sharing)

共享：系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進程（線程）共同使用。兩種資源共享方式：互斥共享方式（臨界/獨占資源）同時訪問方式并發(fā)與共享互為條件！1.3.3虛擬(Virtual)

虛擬是指通過某種技術(shù)，將一個物理實體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。用來實現(xiàn)虛擬的技術(shù)，被稱為虛擬技術(shù)。在現(xiàn)代OS中利用了多種虛擬技術(shù)，分別用來實現(xiàn)虛擬處理機、虛擬存儲器和虛擬設(shè)備等。1.3.4異步性(Asynchronism)

異步性是指在多道程序的環(huán)境下，每個程序不知何時執(zhí)行、何時暫停，即它們以不可預(yù)知的速度向前推進。但同時，操作系統(tǒng)應(yīng)保證程序的執(zhí)行結(jié)果是可再現(xiàn)的。即只要運行環(huán)境相同，一個作業(yè)的多次運行都會得到相同的結(jié)果。1.4操作系統(tǒng)的主要功能1.4.1處理機管理功能1.4.2存儲器管理功能1.4.3設(shè)備管理功能1.4.4文件系統(tǒng)管理1.4.5用戶接口1.4.1處理機管理功能

處理機是最重要的資源，現(xiàn)代操作系統(tǒng)允許多個程序共享處理機，按照某種算法（分時、優(yōu)先級）交替地使用處理機。處理機管理包括以下幾方面：進程控制進程同步（進程互斥方式、進程同步方式）進程通信調(diào)度1.4.2存儲器管理功能

第二重要資源。存儲器管理主要是為多道程序的運行提供良好的環(huán)境。存儲器管理要具備下列功能：內(nèi)存分配

內(nèi)存保護：使多道程序間互不干擾

地址映射：把程序中的邏輯地址映射為物理地址內(nèi)存擴充：用輔存擴充主存，實現(xiàn)“虛擬存儲器”

最龐大、瑣碎的部分，因為：

物理設(shè)備品種繁多、用法各異

各種外設(shè)能和主機并行工作主機與各類外設(shè)速度極不匹配，級差很大1.4.3設(shè)備管理功能

設(shè)備管理主要是完成用戶的I/O請求。它的主要功能包括：緩沖管理：為設(shè)備提供緩沖區(qū)以緩和CPU同設(shè)備的I/O速度不匹配的矛盾。

設(shè)備分配

設(shè)備處理1.4.4文件管理功能

文件管理主要是使用戶能方便、安全地使用各種信息資源。主要功能包括：

文件存儲空間的管理目錄管理文件的讀/寫管理和保護2.1進程的基本概念2.1.1前趨圖2.1.2程序的順序執(zhí)行及其特征2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)2.1.5進程控制塊2.1.1前趨圖（PrecedenceGraph）

是一個有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執(zhí)行的前后關(guān)系。P1P2P3P4P5P6P7P8P9結(jié)點有向邊直接前驅(qū)直接后繼初始結(jié)點終止結(jié)點重量例：具有九個結(jié)點的前趨圖PiPj前趨關(guān)系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9

S1S2S3前驅(qū)圖中不能存在循環(huán)關(guān)系。如：2.1.2程序的順序執(zhí)行及其特征各程序段間程序的順序執(zhí)行如圖：

在計算機系統(tǒng)中只有一個程序在運行，這個程序獨占系統(tǒng)中所有資源，其執(zhí)行不受外界影響。一道程序執(zhí)行完后另一道才能開始。I1P1O1I2P2O2作業(yè)1作業(yè)2一個程序段的多條語句的順序執(zhí)行：S1S2S3S1:a:=x+yS2:b:=a-5S3:c:=b+1程序順序執(zhí)行的特征：順序性：一個程序開始執(zhí)行必須要等到前一個程序已執(zhí)行完成。封閉性：程序一旦開始執(zhí)行，其計算結(jié)果不受外界因素影響?？稍佻F(xiàn)性：程序的結(jié)果與它的執(zhí)行速度無關(guān)（即與時間無關(guān)），只要給定相同的輸入，一定會得到相同的結(jié)果。2.1.3程序的并發(fā)執(zhí)行及其特征1.程序的并發(fā)執(zhí)行所謂程序的并發(fā)執(zhí)行是指：若干個程序同時在系統(tǒng)中執(zhí)行，這些程序的執(zhí)行在時間上是重疊的，一個程序的執(zhí)行尚未結(jié)束，另一個程序的執(zhí)行已經(jīng)開始。

I1I2I3C1C2C3P1P2P3I4C4P4一個程序段的多條語句的并發(fā)執(zhí)行：S1:a:=x+2S2:b:=y+5S3:c:=a+bS4:d:=c+6S1S3S4S2程序并發(fā)執(zhí)行的特征：間斷性由于資源共享和相互合作，并發(fā)執(zhí)行的程序間形成了相互制約關(guān)系，導(dǎo)致程序的運行過程出現(xiàn)“執(zhí)行—暫?！獔?zhí)行”的現(xiàn)象。失去封閉性程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的資源，因此這些資源的狀態(tài)將由多個程序來改變。不可再現(xiàn)性由失去封閉性導(dǎo)致。同樣的初始條件，一個程序的多次重復(fù)執(zhí)行，可得到不同的結(jié)果。

例：程序A、B，共享變量N。代碼如下：程序ABEGINREPEAT……N：=N+1……UNTILFALSEEND程序BBEGINREPEAT……PRINT(N)N:=0…UNTILFALSEEND兩個程序以不同速度運行，可能出現(xiàn)三種情況：N:=N+1在Print(N)和N:=0之前

——N值分別為N+1，N+1，0N:=N+1在Print(N)和N:=0之后

——N值分別為N,0,1N:=N+1在Print(N)和N:=0之間

——N值分別為N,N+1，0思考：任何并發(fā)執(zhí)行都是不可再現(xiàn)的嗎？并發(fā)執(zhí)行的條件：

并發(fā)執(zhí)行的條件：達到封閉性和可再現(xiàn)性。并發(fā)執(zhí)行失去封閉性的的原因是共享資源的影響，去掉這種影響就行了。1966年，由Bernstein給出并發(fā)執(zhí)行的條件。將程序中任一語句或程序段Pi劃分為兩個變量的集合，R(pi)和W(pi)。其中，

R(pi)={a1,a2,…an}，程序pi在執(zhí)行期間引用的（讀的）變量集，稱為“讀集”。

W(pi)={b1,b2,…bm}，程序pi在執(zhí)行期間改變的（寫的）變量集，稱為“寫集”。

Bernstein條件:

如果對于語句p1、p2，如果同時滿足以下三個條件：R(p1)∩W(p2)={}R(p2)∩W(p1)={}W(p1)∩W(p2)={}

則語句p1、p2可以并發(fā)執(zhí)行。例如，有如下四條語句：

S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1其中：R(S1)={x,y}W(S1)={a}R(S2)={z}W(S2)=R(S3)={a,b}W(S3)={c}R(S4)={c}W(S4)={w}對于S1和S2，有：

R(S1)∩W(S2)={}，R(S2)∩W(S1)={}，

W(S1)∩W(S2)={}結(jié)論：語句S1和S2滿足Bernstein條件，可以并發(fā)執(zhí)行。其他語句之間自己分析。2.1.4進程的特征與狀態(tài)1.進程的定義

進程是操作系統(tǒng)中最基本、重要的概念。是多道程序系統(tǒng)出現(xiàn)后，為了刻畫系統(tǒng)內(nèi)部出現(xiàn)的動態(tài)情況，描述系統(tǒng)內(nèi)部各道程序的活動規(guī)律引進的一個概念，所有多道程序設(shè)計操作系統(tǒng)都建立在進程的基礎(chǔ)上。較典型的進程定義有：

(1)進程是程序的一次執(zhí)行。

(2)進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。

(3)進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。

(4)進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。

(5)進程是一個具有一定獨立功能的程序關(guān)于某個集合的一次運行活動。(我國78年廬山研討會)

2.進程同程序的比較：進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進程是程序的執(zhí)行。通常進程不可在計算機之間遷移；而程序通常對應(yīng)著文件、靜態(tài)和可以復(fù)制。進程是暫時的，程序是永久的：進程是一個狀態(tài)變化的過程，是有一定生命期的；而程序可以作為一種軟件資料長久保存。進程與程序的組成不同：進程是由程序和數(shù)據(jù)、進程控制塊三部分組成的。進程與程序的對應(yīng)關(guān)系：同一程序同時運行于若干個數(shù)據(jù)集合上，它將屬于若干個不同的進程。也就是說同一程序可以對應(yīng)多個進程；一個進程的執(zhí)行也可以涉及到一個或幾個程序（調(diào)用）。3.進程的特征：結(jié)構(gòu)特征：由程序段、數(shù)據(jù)段、進程控制塊三部分組成；動態(tài)性：進程是程序的執(zhí)行；并發(fā)性：多個進程可同存于內(nèi)存中，能在一段時間內(nèi)同時運行；獨立性：獨立運行的基本單位，獨立獲得資源和調(diào)度的基本單位；異步性：各進程按各自獨立的不可預(yù)知的速度向前推進。4.進程的三種基本狀態(tài)不同系統(tǒng)設(shè)置的進程狀態(tài)數(shù)目不同。進程有三種基本狀態(tài)：

1)就緒狀態(tài)：進程已獲得除CPU以外的所有必要資源，只要得到CPU，便可立即執(zhí)行。2)執(zhí)行狀態(tài)：進程已得到CPU，其程序正在CPU上執(zhí)行。3)阻塞狀態(tài)：正在執(zhí)行的進程因某種事件(如I/O請求)的發(fā)生而暫時無法繼續(xù)執(zhí)行，只有等相應(yīng)事件完成后，才能去競爭CPU。進程的狀態(tài)變遷圖執(zhí)行五狀態(tài)進程模型進程正常結(jié)束，或因某種原因被取消后，OS釋放出的進程。剛剛建立的進程，還未送入就緒隊列。執(zhí)行新建態(tài)終止態(tài)5.

七狀態(tài)進程模型引入掛起狀態(tài)的原因：終端用戶的請求父進程請求負荷調(diào)節(jié)的需要操作系統(tǒng)的需要

“掛起”的實質(zhì)是使進程不能繼續(xù)執(zhí)行，即使掛起后的進程處于就緒狀態(tài)，它也不能參與對CPU的競爭。因此，稱被掛起的進程處于靜止?fàn)顟B(tài)，相反，沒被掛起的進程則處于活動狀態(tài)。而且，處于靜止?fàn)顟B(tài)的進程，只有通過“激活”動作，才能轉(zhuǎn)換成活動狀態(tài)。進程掛起后,程序代碼和數(shù)據(jù)集被調(diào)出到外存的交換區(qū)中,騰出來的內(nèi)存空間供其它進程使用。激活掛起事件發(fā)生事件發(fā)生等待事件掛起調(diào)度超時釋放激活掛起激活掛起事件發(fā)生事件發(fā)生等待事件掛起調(diào)度超時釋放激活掛起七狀態(tài)進程模型掛起就緒態(tài)掛起阻塞態(tài)就緒態(tài)阻塞態(tài)執(zhí)行態(tài)終止態(tài)新建態(tài)就緒態(tài)（ready）:進程在內(nèi)存且可立即進入運行狀態(tài)。阻塞態(tài)（blocked）:進程在內(nèi)存并等待某一個事件的出現(xiàn)。掛起就緒態(tài)（readysuspend）:進程在外存,但只要進入內(nèi)存,即可運行。掛起阻塞態(tài)（blockedsuspend）:進程在外存并等待某一個事件的出現(xiàn)?！舅伎碱}】有沒有這樣的狀態(tài)轉(zhuǎn)換，為什么？ 阻塞—運行就緒—阻塞2.1.5進程控制塊（ProcessControlBlock，PCB

）

1.進程控制塊的作用

進程控制塊的作用是使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù))，成為一個能獨立運行的基本單位，一個能與其它進程并發(fā)執(zhí)行的進程。或者說，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。進程與PCB是一一對應(yīng)的。

PCB應(yīng)常駐內(nèi)存。2.進程控制塊中的信息進程標(biāo)識符：用于惟一地標(biāo)識系統(tǒng)中的每個進程。另外，還可以用父進程的標(biāo)識符及子進程的標(biāo)識符來描述進程的家族關(guān)系。處理機狀態(tài)：用于CPU切換時保存現(xiàn)場和恢復(fù)現(xiàn)場，主要由處理機中各種寄存器的內(nèi)容組成。進程調(diào)度和控制信息：用于進程調(diào)度和控制，主要包括進程狀態(tài)、優(yōu)先級、等待和使用CPU的時間總和、程序和數(shù)據(jù)的地址、進程同步和通信信息、資源清單和進程隊列指針等。3.進程控制塊的組織方式圖2-7PCB鏈接隊列示意圖

在一個系統(tǒng)中通常有許多的PCB，稱為PCB集合。為了便于管理，系統(tǒng)必須用適當(dāng)?shù)姆绞綄CB組織起來，常用的方式有鏈接方式和索引方式。PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針…1)鏈接方式相同狀態(tài)的進程PCB組成一個鏈表，不同狀態(tài)對應(yīng)多個不同的鏈表?？罩羔?)索引方式執(zhí)行指針就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就緒表指針阻塞表指針對具有相同狀態(tài)的進程，分別設(shè)置各自的PCB索引表，表明PCB在PCB表中的地址。2.2進程控制2.2.1進程的創(chuàng)建2.2.2進程的終止2.2.3進程的阻塞與喚醒2.2.4進程的掛起與激活

進程控制是進程管理中最基本的功能，它用于創(chuàng)建和撤消進程，并對進程在整個生命周期中各種狀態(tài)之間的轉(zhuǎn)換進行有效控制。進程控制是由操作系統(tǒng)的內(nèi)核通過原語來實現(xiàn)的。原語：系統(tǒng)狀態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。(原語的執(zhí)行具有原子性，執(zhí)行時不可分割)。2.2.1進程的創(chuàng)建1.進程圖(ProcessGraph)：用于描述一個進程的家族關(guān)系的有向樹。

DEFGHBCIJKLMA祖先進程父進程子進程

子進程可以繼承父進程的所有資源，當(dāng)子進程被撤消時，應(yīng)將從父進程那里獲得的資源歸還給父進程。撤消父進程時也必須同時撤消其所有的子進程。2.引起創(chuàng)建進程的事件(1)用戶登錄。(2)作業(yè)調(diào)度。(3)提供服務(wù)。(4)應(yīng)用請求。3.進程的創(chuàng)建(CreationofProgress)(1)申請空白PCB。

(2)為新進程分配資源。

(3)初始化進程控制塊。

(4)將新進程插入就緒隊列。創(chuàng)建新進程通過進程創(chuàng)建原語creat（）來完成。進程創(chuàng)建原語的主要任務(wù)是創(chuàng)建進程控制塊PCB。入口查PCB鏈表有空PCB？取空PCB（i）將有關(guān)參數(shù)填入PCB（i）相應(yīng)項PCB（i）入就緒隊列PCB(i)入進程家族或進程鏈創(chuàng)建失敗返回創(chuàng)建原語流程圖NY2.2.2進程的終止

當(dāng)某進程實現(xiàn)完成任務(wù)正常結(jié)束時，或在運行過程中遇到某些異常情況（如越界錯誤、非法指令、運行超時等），或外界干預(yù)需要結(jié)束時，應(yīng)予以終止（撤消）。（參見P35）通過進程終止原語來終止進程。終止進程的實質(zhì)是收回PCB。進程的終止過程：

(1)查找對應(yīng)的PCB(2)終止該進程及子孫進程

(3)釋放資源

(4)釋放PCB

終止原語流程圖入口查進程鏈表或進程家族有此PCB嗎？釋放該進程所占有的資源出錯處理該PCB有子進程嗎？釋放該PCB結(jié)構(gòu)本身YYNN返回2.2.3進程的阻塞與喚醒1.進程的阻塞當(dāng)正在執(zhí)行的進程需要等待某種事件的完成或本身無新工作可做時，應(yīng)調(diào)用阻塞原語將自己從執(zhí)行狀態(tài)轉(zhuǎn)換成阻塞狀態(tài)。進程阻塞是進程的一種主動行為。通過阻塞原語block（）來完成。具體的操作過程是：停止進程的執(zhí)行，將其狀態(tài)改為阻塞狀態(tài)，并把它的PCB插入相應(yīng)的阻塞（等待）隊列，轉(zhuǎn)調(diào)度程序進行重新調(diào)度。阻塞原語流程圖保存當(dāng)前進程的CPU現(xiàn)場置該進程的狀態(tài)被阻塞進程入阻塞隊列轉(zhuǎn)進程調(diào)度入口2.進程的喚醒當(dāng)阻塞進程所等待的事件完成時，應(yīng)調(diào)用喚醒原語將該進程的狀態(tài)從阻塞狀態(tài)轉(zhuǎn)換成就緒狀態(tài)。通過喚醒原語wakeup（）來完成。

處于阻塞狀態(tài)的進程是絕不可能叫醒自己的，必須由它的合作進程用喚醒原語喚醒它。具體的操作過程是：在等待隊列中移出該進程的PCB，將其置成就緒狀態(tài)，并把它插入就緒隊列。喚醒原語流程圖從等待隊列中摘下被喚醒進程將被喚醒進程置為就緒態(tài)將被喚醒進程送入就緒隊列轉(zhuǎn)進程調(diào)度或返回入口2.2.4進程的掛起與激活1、進程的掛起當(dāng)出現(xiàn)了引起進程掛起的事件時，用戶請求將自己掛起，或者父進程請求掛起自己的子進程。系統(tǒng)通過掛起原語suspend（）將指定進程掛起。具體的執(zhí)行過程：檢查被掛起進程的狀態(tài)，如果處于活動就緒狀態(tài)，就將它改為靜止就緒；如果處于活動阻塞，則改為靜止阻塞。將PCB復(fù)制到指定的內(nèi)存區(qū)域供用戶或父進程考查。若掛起前進程正在執(zhí)行，則轉(zhuǎn)調(diào)度程序重新進行進程調(diào)度。2、進程的激活當(dāng)發(fā)生激活事件后，系統(tǒng)利用激活原語Active()將指定進程激活。具體的操作過程是：若進程處于靜止阻塞狀態(tài)，則將它轉(zhuǎn)換成活動阻塞狀態(tài)，否則將它轉(zhuǎn)換成活動就緒狀態(tài)。若進程轉(zhuǎn)換成活動就緒狀態(tài)，而系統(tǒng)又采用搶占調(diào)度策略，則應(yīng)檢查該進程是否有權(quán)搶占CPU，若有則應(yīng)進行進程調(diào)度。2.3進程同步2.3.1進程同步的基本概念2.3.2信號量機制2.3.3信號量的使用

進程同步是指對多個相關(guān)進程在執(zhí)行次序上進行協(xié)調(diào)。進程同步的主要任務(wù)是使并發(fā)執(zhí)行的諸進程之間能有效的共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。1.兩種形式的制約關(guān)系

間接相互制約關(guān)系互斥關(guān)系，資源共享關(guān)系直接相互制約關(guān)系同步關(guān)系，相互合作關(guān)系2.3.1進程同步的基本概念2.臨界資源

一次僅允許一個進程訪問的資源。如：進程Ａ、Ｂ共享一臺打印機，若讓它們交替使用則得到的結(jié)果肯定不是我們希望的。臨界資源可能是硬件，也可能是軟件：變量，數(shù)據(jù)，表格，隊列等。并發(fā)進程對臨界資源的訪問必須作某種限制，否則就可能出現(xiàn)錯誤，如：聯(lián)網(wǎng)售票，會出現(xiàn)與時間有關(guān)的錯誤。例：兩進程共享一個變量COUNTP1:R1:=COUNT;R1:=R1+1;COUNT:=R1;P2:P2:=COUNT;R2:=R2+1;COUNT:=R2;試比較兩進程順序執(zhí)行和并發(fā)執(zhí)行的結(jié)果。若P1、P2按如下順序并發(fā)執(zhí)行：P1:R1:=COUNT;P2:R2:=COUNT;P1:R1:=R1+1;COUNT:=R1;P2:R2:=R2+1;COUNT:=R2;

若P1、P2順序執(zhí)行：

P1:R1:=COUNT;R1:=R1+1;COUNT:=R1;P2:R2:=COUNT;R2:=R2+1;COUNT:=R2;3.臨界區(qū)(CriticalSection)

每個進程中，訪問臨界資源的那段代碼稱為臨界區(qū)。諸進程對臨界資源的互斥訪問就變?yōu)樵鯓邮怪T進程互斥地進入臨界區(qū)。

互斥的實質(zhì)就是同步，或者說，互斥是同步的一種特殊形式。

訪問臨界資源的循環(huán)進程描述如下：

REPEAT

ENTRYSECTIONCRITICALSECTIONEXITSECTIONREMAINDERSECTIONUNTILFALSE進入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)4.同步機制應(yīng)遵循的原則

用來實現(xiàn)互斥的同步機制必須遵循下述四條準則：

(1)空閑讓進。

(2)忙則等待。

(3)有限等待。

(4)讓權(quán)等待。2.3.2信號量機制

信號量機制是荷蘭學(xué)者Dijkstra在1965年提出的一種卓有成效的同步工具，在長期且廣泛的應(yīng)用中，已由早期的整型信號量發(fā)展為記錄型信號量，進而發(fā)展為信號量集。1.整型信號量

整型信號量是一個非負的共享整數(shù)，除了初始化外，它只能通過兩個標(biāo)準的原子操作wait和signal來訪問，即P、V操作。

wait和signal操作可描述為：

wait(S):whileS≤0dono-op

S∶=S-1;

signal(S):S∶=S+1;

整型信號量的主要問題是，只要S≤0，wait操作就會不斷地測試，因而，沒能做到“讓權(quán)等待”。2.記錄型信號量

記錄型信號量中除了一個整型變量value外，還增加了一個等待隊列指針L。記錄型信號量采用了記錄型的數(shù)據(jù)結(jié)構(gòu)，描述為：typesemaphore=record

value:integer;

L:listofprocess;

end

相應(yīng)的wait和signal操作（即P、V操作）可描述為：procedureP(S)

varS:semaphore;

begin

S.value:=S.value-1;

ifS.value＜0thenblock(S.L)

end

當(dāng)S.value＜0時，進程會立即將自己阻塞，因此解決了整型信號量的“忙等”問題，做到了“讓權(quán)等待”。該進程狀態(tài)置為阻塞狀態(tài)；放棄處理機；將該進程的PCB插入鏈表S.L中。procedureV(S)

varS:semaphore;

begin

S.value:=S.value+1;

ifS.value≤0thenwakeup(S.L)

end

喚醒S.L鏈表中的第一個等待進程；改變狀態(tài)為就緒態(tài)；將其插入就緒隊列中。

一個信號量通常對應(yīng)于一類臨界資源，在使用前，信號量必須經(jīng)過定義并賦適當(dāng)?shù)某踔?，初值表示系統(tǒng)中某類資源的數(shù)目。初值為1表示對臨界資源進行訪問，此時信號量轉(zhuǎn)化為互斥信號量。每次對信號量進行wait操作意味著申請一個單位的該類資源，signal操作意味著歸還一個單位的該類資源。當(dāng)S.value＞0時，它的值表示系統(tǒng)中該類資源當(dāng)前可用的數(shù)目；S.value≤0時，表示該類資源已分配完畢，其絕對值表示系統(tǒng)中因申請該類資源而阻塞在S.L隊列上的進程數(shù)目。

必須注意的幾個問題：2.3.3信號量的使用必須置一次且只能置一次初值初值為整數(shù)，且不能為負數(shù)

只能執(zhí)行P、V操作1.用信號量實現(xiàn)進程互斥P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)PA:…P(mutex);criticalsection;V(mutex);…PB:…P(mutex);criticalsection;V(mutex);…mutex用于實現(xiàn)互斥，初值為1。在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)之間。模型：模擬執(zhí)行：序號PAPBmutex說明011P(mutex)0PA進入，占資源2P(mutex)-1PB進入，無資源3V(mutex)0PA釋放資源，PB解封4V(mutex)1PB釋放資源0可反復(fù)執(zhí)行

對于兩個并發(fā)進程，互斥信號量的值僅取1、0和-1三個值：若mutex＝1表示沒有進程進入臨界區(qū)；若mutex＝0表示有一個進程進入臨界區(qū)；若mutex＝-1表示一個進程進入臨界區(qū)，另一個進程等待進入。當(dāng)實現(xiàn)n個進程并發(fā)時，互斥信號量的取值為1、0、-1、…、-(n-1)。

P、V操作必須成對出現(xiàn)：遺漏P(mutex)將不能保證互斥訪問，遺漏V(mutex)將不能再使用臨界資源之后將其釋放（給其他等待的進程）。PA:…L1：P(proceed)…2.用信號量實現(xiàn)同步PB:…L2：V(proceed)…proceed用于實現(xiàn)同步，初值為0。PA在L1點必須與PB在L2點同步，PA受PB的制約，而PB不受PA的制約，使非對稱的。

P、V操作必須成對出現(xiàn)，當(dāng)用于實現(xiàn)互斥時，它們同處于同一進程；當(dāng)用于實現(xiàn)同步操作時，則不在同一進程中出現(xiàn)。模型：3.利用信號量描述前趨關(guān)系

信號量可用來描述程序或語句之間的前趨關(guān)系。若Pi是Pj的直接前趨，即Pi→Pj，則可設(shè)置一個初值為0的公用信號量S，并將V(S)操作放在Pi后，而在Pj前插入P(S)操作，以保證Pi在Pj開始執(zhí)行之前完成。PiPjVara,b,c,d,e,f,g:semaphores;Beginparbeginbegins1;v(a);v(b);end;beginp(a);s2;v(c);end;beginp(c);s4;v(e);v(f);end;beginp(b);s3;v(d);end;beginp(e);s5;v(g);end;beginp(f);p(d);s6;v(h);end;beginp(g);p(h);s7;end;Parbeginends1s2s3s4s5s1s6s7abcdefgh例：2.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者—消費者問題2.4.2哲學(xué)家進餐問題2.4.3讀者——寫者問題2.4.1生產(chǎn)者—消費者問題放產(chǎn)品取產(chǎn)品一次只可放一個產(chǎn)品生產(chǎn)者消費者

只要倉庫未滿，生產(chǎn)者就可以把產(chǎn)品放入倉庫。只要倉庫未空，消費者就可以從倉庫中取走物品。問題描述：inout01234567891011in:下一個可供投放產(chǎn)品的緩沖區(qū),in:=(in+1)modn；

out:下一個可供獲取產(chǎn)品的緩沖區(qū),out:=(out+1)modn。若(in+1)modn=out，有界緩沖區(qū)滿；若in=out，有界緩沖區(qū)空。環(huán)形緩沖池設(shè)一個長度為n的有界緩沖區(qū)：（以n=12為例）問題分析：這是一個同步與互斥共存的問題。1.生產(chǎn)者—消費者問題是一個同步問題。即生產(chǎn)者和消費者之間滿足如下條件：消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的。生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的。故設(shè)置兩個信號量：empty：說明空緩沖區(qū)的數(shù)目，初值為有界緩沖區(qū)的大小N。full：說明已用緩沖區(qū)的數(shù)目，初值為０。

2.

由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進程和各消費者進程之間必須互斥執(zhí)行。故設(shè)置一個互斥信號量mutex，其初值為１。問題的解：Varmedex,empty,full:semaphore;buffer:array[0,1,…n-1]ofitem;in,out:integer;Beginmetex:=1;empty:=n;full:=0;in:=0;out:=0;Parbegin

procedure:……

consumer:……ParendendConsumer：

beginrepeat

P(full);P(mutex);

從Buffer[out]取產(chǎn)品;out=(out+1)modn;

V(mutex);V(empty);…

消費產(chǎn)品;…untilfalse;endProducter：

begin

repeat…

生產(chǎn)產(chǎn)品;

…

P(empty);P(mutex);

往Buffer[in]放產(chǎn)品;in=(in+1)modn;

V(mutex);V(full);untilfalse;end有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子。2.4.2哲學(xué)家就餐問題問題描述：每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉；吃完后繼續(xù)思考。為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子。問題的解：repeat

P(fork[i]);P(fork[(i+1)mod5])；

…

進食；

…

V(fork[i]);V(fork[(i+1)mod5])；

…

思考；

…untilfalse設(shè)fork[5]為5個信號量（分別表示每支筷子），初值均為1。此解可以保證互斥使用筷子，但會產(chǎn)生死鎖。為防止死鎖發(fā)生可采取的措施：

最多允許4個哲學(xué)家同時去拿左邊的筷子；僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子進餐；（

）給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之。信號量集——AND型信號量集AND型信號量集的基本思想：在一個原語中申請整段代碼需要的多個臨界資源，要么全部分配給它，要么一個都不分配。AND型信號量集P原語為Swait；

AND型信號量集V原語為Ssignal。采用AND信號量集解決哲學(xué)家就餐問題repeat

Swait(fork[i],fork[(i+1)mod5])；

…

進食；

…

Ssignal(fork[i],fork[(i+1)mod5])；

…

思考；

…untilfalse設(shè)fork[5]為5個信號量（分別表示每支筷子），初值為均1。2.4.3讀者-寫者問題問題描述：

有兩組并發(fā)進程——讀者和寫者，共享一組數(shù)據(jù)區(qū)。要求：允許多個讀者同時執(zhí)行讀操作；任一寫者在完成寫操作之前不允許其它讀者或?qū)懻吖ぷ?讀寫文件)；寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出。如果讀者來：若無讀者、寫者，則新讀者可以讀；若有寫者等待，但有其它讀者正在讀，則新讀者也可以讀；若有寫者寫，則新讀者等待。如果寫者來：若無讀者，則新寫者可以寫；若有讀者，則新寫者等待；若有其它寫者，則新寫者等待。問題分析：問題的解：整形變量readcount表示正在讀的讀者數(shù)目，初值為0。信號量w用于保證讀者和寫者、寫者和寫者之間的互斥,初值為1。信號量mutex用于保證對readcount這個臨界資源的互斥修改，初值為1。讀者：beginrepeat

P(mutex);readcount:=readcount+1;ifreadcount=1thenP(w);

V(mutex); …

執(zhí)行讀操作；

…

P(mutex);readcount:=readcount-1;ifreadcount=0thenV(w);

V(mutex);untilfalseend寫者：beginrepeat

P(w);

執(zhí)行寫操作；

V(w);untilfalseend【思考題】

桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個蘋果或放一個桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。試用P、V操作實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步與互斥。提示：設(shè)置一個信號量表示可否向盤中放水果，一個信號量表示可否取桔子，一個信號量表示可否取蘋果。問題的解：Daughter:repeatP(Sa)；取蘋果；

V(S);

吃蘋果;untilfalseSon:repeatP(So)；取桔子；

V(S);

吃桔子;untilfalseFather:repeatP(S);

將水果放入盤中;if桔子

thenV(So);elseV(Sa);untilfalse

設(shè)置三個信號量S、So、Sa，初值分別為1、0、0。分別表示可否向盤中放水果，可否取桔子，可否取蘋果。【思考題】

有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）；（2）－N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M；其中，N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與B的入庫過程。提示：設(shè)兩個信號量Sa、Sb。Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量；Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量設(shè)兩個信號量Sa、Sb，初值分別為M-1，N-1Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量設(shè)互斥信號量mutex，初值為1。問題的解：B產(chǎn)品入庫進程：repeat

P(Sb);P(mutex);B產(chǎn)品入庫

V(mutex);V(Sa);

…

消費產(chǎn)品;…untilfalseA產(chǎn)品入庫進程：repeat…

生產(chǎn)產(chǎn)品;…

P(Sa);

P(mutex);A產(chǎn)品入庫

V(mutex);

V(Sb);untilfalse2.5管程機制2.5.1管程的基本概念2.5.2利用管程解決生產(chǎn)者-消費者問題2.5.1管程的基本概念為什么引入管程？把分散在各進程中的臨界區(qū)集中起來進行管理；防止進程有意或無意的違法同步操作；便于用高級語言來書寫程序，也便于程序正確性驗證。管程的基本概念：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)。管程的特點：

(1)管程內(nèi)的局部變量只能被局部于管程內(nèi)的過程所訪問；反之亦然，即局部于管程內(nèi)的過程只能訪問管程內(nèi)的變量。

(2)任何進程只能通過調(diào)用管程提供的過程入口進入管程。

(3)任一時刻，最多只能有一個進程在管程中執(zhí)行。typemonitor-name=monitorvariabledeclarations

procedureentryP1(…);

begin…end;

procedureentryP2(…);

begin…end;

…

procedureentryPn(…);

begin…end;

begin

initializationcode;

end管程的語法局部于管程的共享變量說明對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程對局部于管程的數(shù)據(jù)設(shè)置初始值管程的組成部分共享數(shù)據(jù)…一組操作過程初始化代碼進入隊列條件(不忙)隊列管程的示意圖：

當(dāng)進程通過管程請求臨界資源未能滿足時，將排在隊列上等待。等待的原因可能有多個，為了區(qū)分它們，引入條件變量condition。每個condition表示一種等待原因。

針對條件變量x，x.wait將自己阻塞在x隊列中，x.signal將x隊列中的一個進程喚醒。條件變量：2.5.2利用管程解決生產(chǎn)者-消費者問題PC管程描述：TypeProducer-Consumer=monitorVarbuffer：array[0,…,n-1]ofitem；count，in，out：integer；notempty，notfull：condition；procedureentryput(item);beginifcount>=nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1；

ifnotempty.queuethennotempty.signal;end;procedureentryget(item);beginifcount<=0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1；

ifnotfull.queuethennotfull.signal;end;Beginin:=0;out:=0;count:=0Endproducer：beginrepeatproduceanitem；

PC.put(item)；

untilfalse；endconsumer：beginrepeat

PC.get(item)；

consumetheitem；

untilfalse;end生產(chǎn)者和消費者描述：2.6進程通信2.6.1進程通信的類型2.6.2消息緩沖隊列通信機制

進程之間互相交換信息的工作稱為進程通信。進程通信的類型：低級通信：歸結(jié)為進程之間的互斥和同步，一般只傳送少量信息（信號量）。缺點：效率低，通信對用戶不透明。高級通信：能夠高效傳輸大量數(shù)量數(shù)據(jù)的通信方式。又分為三類：共享存儲器系統(tǒng)、消息傳遞系統(tǒng)、管道通信系統(tǒng)。2.6.1進程通信的類型1.共享存儲器系統(tǒng)

相互通訊的進程通過共享數(shù)據(jù)結(jié)構(gòu)和共享存儲區(qū)進行通訊，可進一步分為：

基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式進程之間通過某種數(shù)據(jù)結(jié)構(gòu)，如緩沖池進行通信，屬于低級通信方式。如生產(chǎn)者-消費者問題中的有界緩沖區(qū)。

基于共享存儲區(qū)的通信方式為了傳送大量信息，在存儲器中劃出一塊共享存儲區(qū)，諸進程可通過對共享存儲區(qū)進行讀或?qū)憗韺崿F(xiàn)通信，屬高級通信方式。2.消息傳遞系統(tǒng)

使用最廣泛的一種進程通信機制。進程間的數(shù)據(jù)交換以消息或報文為單位，程序員直接利用一組通信命令（原語）來實現(xiàn)通信。操作系統(tǒng)隱藏了通信的實現(xiàn)細節(jié)，簡化了通信程序編制的復(fù)雜性。（1）直接通信方式兩條通信原語：Send（Receiver，message）;Receive（Sender，message）;

例如：Send（p2，m1）;Receive（p1，m1）;發(fā)送進程可直接將消息發(fā)送給目標(biāo)進程。消息傳遞系統(tǒng)的分類：——直接通信方式和間接通信方式repeat

…

produceaniteminnextp;

…

send(consumer,nextp);

untilfalse;利用直接通信原語解決生產(chǎn)者-消費者問題：repeat

receive(producer,nextc);

…

consumetheiteminnextc;

untilfalse;producer：consumer：

（2）間接通信方式

進程間發(fā)送或接收消息通過信箱進行，消息可被理解成信件。也稱信箱通信。兩條通信原語：

Send（mailbox，message）；

Receive（mailbox，message）；注意：用戶不必寫出接收進程標(biāo)識符，從而可以向不知名的進程發(fā)送消息；另外，消息在信箱中可以安全的保存，只允許核準的目標(biāo)用戶隨時讀取，可實現(xiàn)非實時通信。發(fā)送進程A

…郵箱體

郵箱頭接收進程B

信箱由信箱頭和由若干格子組成的信箱體組成。信箱中每個格子存放一封信，信箱中格子的數(shù)目和每格的大小在創(chuàng)建信箱時確定。進程間的通信要滿足如下條件：

a.

發(fā)送進程發(fā)送消息時，郵箱中至少要有一個空格存放該消息。

b.

接收進程接收消息時，郵箱中至少要有一個消息存在。3.管道（Pipe）通信系統(tǒng)

所謂管道，是指用于連接一個讀進程和一個寫進程以實現(xiàn)它們之間通信的一個共享文件，又稱pipe文件。發(fā)送進程以字符流形式把大量數(shù)據(jù)送入管道，接收進程從管道中接收數(shù)據(jù)，所以叫管道通信。管道的實質(zhì)是一個共享文件，基本上可借助于文件系統(tǒng)的機制實現(xiàn)，包括（管道）文件的創(chuàng)建、打開、關(guān)閉和讀寫。讀寫進程相互協(xié)調(diào)，必須做到：

互斥：進程對通信機構(gòu)的使用應(yīng)該互斥，一個進程正在使用某個管道寫入或讀出數(shù)據(jù)時，另一個進程就必須等待。

同步：管道長度有限,發(fā)送信息和接收信息之間要實現(xiàn)正確的同步關(guān)系。當(dāng)寫進程把一定數(shù)量的數(shù)據(jù)寫入pipe，就去睡眠等待，直到讀進程取走數(shù)據(jù)后，把它喚醒。

確定對方是否存在：發(fā)送者和接收者雙方必須能夠知道對方是否存在，如果對方已經(jīng)不存在，就沒有必要再發(fā)送信息。寫進程共享文件讀進程管道通信的思想：（1）發(fā)送進程可以源源不斷的從pipe一端寫入數(shù)據(jù)流，在規(guī)定的pipe文件的最大長度（如4096字節(jié)）范圍內(nèi)，每次寫入的信息長度是可變的；（2）接收進程在需要時可以從pipe的另一端讀出數(shù)據(jù)，讀出單位長度也是可變的。2.6.2消息緩沖隊列通信機制

消息緩沖隊列通信機制通過內(nèi)存中公用的消息緩沖區(qū)進行進程通信，屬于直接通信方式。發(fā)送進程利用send原語將消息直接發(fā)送給接收進程；接收進程利用receive原語接收消息。（1）消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)typemessageBuffer=record

sender；發(fā)送者ID;size；消息長度;text；消息正文;next；消息隊列指針;end1.消息緩沖隊列通信機制中的數(shù)據(jù)結(jié)構(gòu)（2）PCB中有關(guān)通信的數(shù)據(jù)項typePCB=record…mq;消息隊列首指針;mutex;消息隊列互斥信號量;sm;消息隊列資源信號量;…end2.用P、V操作來實現(xiàn)Send原語proceduresend(receiver,a)

begin

getbuf(a.size,i);

i.sender:=a.sender;i.size:=a.size;

i.text:=a.text;

i.next:=0;

getid(PCBset,receiver.j);

P(j.mutex);

insert(j.mq,i);

V(j.mutex);

V(j.sm);

end根據(jù)a.size申請緩沖區(qū)i;將發(fā)送區(qū)a中的信息復(fù)制到消息緩沖區(qū)之中;獲得接收進程內(nèi)部標(biāo)識符;將消息緩沖區(qū)插入消息隊列;3.用P、V操作來實現(xiàn)Receive原語procedurereceive(b)

begin

j:=internalname;

P(j.sm);

P(j.mutex);

remove(j.mq,i);

V(j.mutex);

b.sender:=i.sender;b.size:=i.size;

b.text:=i.text;

releasei;end

j為接收進程內(nèi)部的標(biāo)識符；將消息隊列中第一個消息移出；將消息緩沖區(qū)i中的信息復(fù)制到接收區(qū)b;

將消息緩沖i歸還給系統(tǒng);mqmutexsmSend(B,a)sender:Asize:5text:Hellosender:Asize:5text:Hellonext:0receive(b)sender:Asize:5text:Hello發(fā)送區(qū)a進程A進程B接收區(qū)bPCB(B)第一消息緩沖區(qū)ba2.7線程線程的引入:引入進程的目的是為了使多個程序并發(fā)執(zhí)行，以改善資源利用率、提高系統(tǒng)吞吐量。引入線程則是為了減少程序并發(fā)執(zhí)行時的所付出的時空開銷。進程的兩個基本屬性：進程是一個可擁有資源的基本單位。進程同時又是一個可獨立調(diào)度和分派的基本單位。線程的屬性:輕型實體：線程自己基本不擁有系統(tǒng)資源，只擁有少量必不可少的資源：程序計數(shù)器、一組寄存器、棧。獨立調(diào)度和分派的基本單位：在引入線程的OS中，線程是進程中的一個實體，是被系統(tǒng)獨立調(diào)度和分派的基本單位。可并發(fā)執(zhí)行：同一進程中的多個線程之間可以并發(fā)執(zhí)行，不同進程中的線程也能并發(fā)執(zhí)行。共享進程資源：它可與同屬一個進程的其它線程共享進程所擁有的全部資源。引入線程的好處:創(chuàng)建一個新線程花費時間少（結(jié)束亦如此）；兩個線程的切換花費時間少；因為同一進程內(nèi)的線程共享內(nèi)存和文件，因此它們之間相互通信無須調(diào)用內(nèi)核；適合多處理機系統(tǒng)。3.1處理機調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干原則高級調(diào)度：又稱為作業(yè)調(diào)度或長程調(diào)度。用于決定把后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進程、分配必要的資源，再將新創(chuàng)建的進程排在就緒隊列上，準備執(zhí)行。在批處理系統(tǒng)