2.1進(jìn)程的基本概念

要點(diǎn)

1.分析程序執(zhí)行順序、以及并發(fā)的特征

2.進(jìn)程的概念硼控、特征與狀態(tài)

3.進(jìn)程控制塊及其組織

1）引入前趨圖

描述進(jìn)程執(zhí)行前后關(guān)系的圖

有向無(wú)循環(huán)圖(DAG)

Pi結(jié)點(diǎn)：描述一個(gè)程序段、進(jìn)程临庇、或一條語(yǔ)句酪碘。

有向邊“->”：結(jié)點(diǎn)之間的偏序或前序關(guān)系

Pi->Pk，則Pi是Pk的直接前趨休蟹，Pk是Pi的直接后繼。

2）程序順序執(zhí)行時(shí)的特征

(1)順序性? 處理機(jī)的操作嚴(yán)格按程序規(guī)定順序執(zhí)行

(2)封閉性 程序一旦開(kāi)始執(zhí)行日矫，其計(jì)算結(jié)果不受外界因素影響赂弓。

(3)可再現(xiàn)性 程序執(zhí)行只要初始條件一樣，不論如何停頓哪轿，重復(fù)執(zhí)行多少次結(jié)果都一樣盈魁。

多個(gè)程序如果無(wú)序并發(fā)，得到的只能是混亂的執(zhí)行結(jié)果窃诉，

多道程序運(yùn)行杨耙，走走停停的可能順序有很多種，符合前趨圖的關(guān)系才是合理并發(fā)飘痛。

4）間斷性(運(yùn)行表現(xiàn))

????多道->程序并發(fā)執(zhí)行->要共享系統(tǒng)的資源 ->形成相互制約的關(guān)系->??相互制約導(dǎo)致并發(fā)程序具有“執(zhí)行—暫桶唇牛—執(zhí)行”這種間斷性的活動(dòng)規(guī)律。

進(jìn)程的定義:

OS利用“進(jìn)程實(shí)體”控制程序執(zhí)行就產(chǎn)生了“進(jìn)程”敦冬。

進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程辅搬，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。

①結(jié)構(gòu)性特征脖旱，進(jìn)程的根本——PCB

②動(dòng)態(tài)性? ?進(jìn)程實(shí)質(zhì)上是進(jìn)程實(shí)體的一次有生命期的執(zhí)行過(guò)程堪遂。程序只是靜態(tài)的一組有序指令。

③并發(fā)性? 多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中萌庆，在一段時(shí)間內(nèi)同時(shí)運(yùn)行溶褪。有PCB的程序才能并發(fā)。

④獨(dú)立性

⑤異步性

補(bǔ)充:區(qū)別進(jìn)程與程序

1）動(dòng)與靜：

進(jìn)程是動(dòng)態(tài)的践险，程序是靜態(tài)的：程序是有序代碼的集合猿妈；進(jìn)程是程序的執(zhí)行。

2）永久與暫時(shí)：

進(jìn)程是暫時(shí)的巍虫，程序是永久的：進(jìn)程是一個(gè)狀態(tài)變化的過(guò)程彭则，程序可長(zhǎng)久保存。

3）結(jié)構(gòu)：

l進(jìn)程的組成包括程序占遥、數(shù)據(jù)和進(jìn)程控制塊（進(jìn)程各種控制信息）俯抖。

4）進(jìn)程與程序的對(duì)應(yīng)關(guān)系：

都可1對(duì)n。通過(guò)多次執(zhí)行瓦胎，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程芬萍；通過(guò)調(diào)用關(guān)系尤揣，一個(gè)進(jìn)程可包括多個(gè)程序。

進(jìn)程的基本狀態(tài)：

? ? ? ? 進(jìn)程執(zhí)行時(shí)的間斷性柬祠，決定了其具有多種狀態(tài)北戏。把握各進(jìn)程所屬的狀態(tài)對(duì)進(jìn)程控制至關(guān)重要。

進(jìn)程的的三種基本狀態(tài)：就緒狀態(tài)漫蛔，執(zhí)行狀態(tài)最欠，阻塞狀態(tài)。

就緒狀態(tài)(Ready)：進(jìn)程已經(jīng)獲得了所需的資源惩猫，只要得到了CPU就可以立即執(zhí)行，通常情況下系統(tǒng)中會(huì)有多個(gè)就緒進(jìn)程蚜点，處在就緒隊(duì)列轧房。

執(zhí)行狀態(tài)(Running)：進(jìn)程已經(jīng)獲得CPU，正處在執(zhí)行狀態(tài)绍绘。

阻塞狀態(tài)(Blocked)：正在執(zhí)行的進(jìn)程由于發(fā)生某事而無(wú)法繼續(xù)執(zhí)行奶镶，（請(qǐng)求I/O、申請(qǐng)緩沖陪拘、時(shí)間片到）便放棄處理機(jī)而處于暫停的狀態(tài)厂镇。

各種狀態(tài)下的進(jìn)程隊(duì)列

單處理機(jī)系統(tǒng)，執(zhí)行態(tài)的進(jìn)程只有一個(gè)左刽；

就緒態(tài)捺信、阻塞態(tài)的進(jìn)程可有多個(gè)。一般講它們分別排稱(chēng)一個(gè)隊(duì)列欠痴，稱(chēng)就緒隊(duì)列迄靠、阻塞隊(duì)列。

阻塞隊(duì)列有的會(huì)根據(jù)不同原因再排成多個(gè)隊(duì)列喇辽。

三狀態(tài)轉(zhuǎn)換圖：

掛起狀態(tài)：因某些需要掌挚，需要經(jīng)一些進(jìn)程掛起而不接受調(diào)度。

進(jìn)程控制塊：為了描述和及控制進(jìn)程的運(yùn)行菩咨，系統(tǒng)為每個(gè)進(jìn)程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)--進(jìn)程控制塊PCB（Process Control Block）吠式。系統(tǒng)總是通過(guò)PCB來(lái)對(duì)進(jìn)程進(jìn)行控制，PCB是

進(jìn)程存在的唯一標(biāo)志抽米。

?進(jìn)程控制塊PCB：

分析OS調(diào)度某進(jìn)程的過(guò)程

查該進(jìn)程的PCB特占，獲取其狀態(tài)、優(yōu)先級(jí)

根據(jù)PCB保存的處理機(jī)狀態(tài)信息云茸，恢復(fù)現(xiàn)場(chǎng)

根據(jù)PCB中程序和數(shù)據(jù)的內(nèi)存始址摩钙，找到其程序和數(shù)據(jù)

執(zhí)行中的同步信號(hào)等也要查閱PCB，暫停時(shí)進(jìn)程執(zhí)行的處理機(jī)環(huán)境保存回PCB查辩。

進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志：

進(jìn)程創(chuàng)建時(shí)胖笛，PCB建立并伴隨進(jìn)程運(yùn)行的全過(guò)程网持，直到進(jìn)程撤消而撤消。PCB就象我們的戶(hù)口长踊。

進(jìn)程管理和控制的最重要的數(shù)據(jù)結(jié)構(gòu)

那么功舀，PCB里面有什么？存放在哪?怎么組織這么多程序的PCB身弊？

PCB中包含的信息：

（1）進(jìn)程標(biāo)識(shí)符

每個(gè)進(jìn)程都必須有一個(gè)唯一的標(biāo)識(shí)符：

內(nèi)部標(biāo)示符：唯一的數(shù)字序號(hào)辟汰，方便系統(tǒng)使用

外部標(biāo)示符：方便用戶(hù)使用，用戶(hù)進(jìn)程訪(fǎng)問(wèn)某進(jìn)程時(shí)使用

（2）處理機(jī)狀態(tài)

主要由處理機(jī)的各種寄存器中的內(nèi)容組成阱佛，被中斷時(shí)這些信息要存放到PCB帖汞。

通用寄存器：用戶(hù)程序訪(fǎng)問(wèn)的，暫存信息

指令計(jì)數(shù)器：下一條指令地址

程序狀態(tài)字PSW：一些狀態(tài)信息

用戶(hù)棧指針：每個(gè)用戶(hù)進(jìn)程都有的存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址的一組系統(tǒng)棧凑术。

（3）進(jìn)程調(diào)度信息

進(jìn)程狀態(tài)翩蘸；

進(jìn)程優(yōu)先級(jí)；

進(jìn)程調(diào)度所需的其他信息：調(diào)度算法相關(guān)信息淮逊；

事件：狀態(tài)轉(zhuǎn)換有關(guān)的事件催首；

（4）進(jìn)程控制信息

程序和數(shù)據(jù)的地址（單個(gè)進(jìn)程）——數(shù)據(jù)所在的內(nèi)外存地址

進(jìn)程同步和通信機(jī)制（多進(jìn)程間）——同步和通信機(jī)制的信號(hào)量、消息隊(duì)列指針等

資源清單

鏈接指針（PCB的組織）——本PCB所在隊(duì)列的下一個(gè)進(jìn)程PCB首地址泄鹏。

2）PCB信息的存放

系統(tǒng)運(yùn)行中有若干個(gè)程序的PCB郎任，它們常駐內(nèi)存的PCB區(qū)。采用的數(shù)據(jù)結(jié)構(gòu)：PCB結(jié)構(gòu)體备籽，PCB鏈表或隊(duì)列舶治。

3）PCB的組織方式

鏈接方式：

同一狀態(tài)的PCB，依靠鏈接指針鏈接成隊(duì)列车猬。就緒隊(duì)列歼疮；若干個(gè)阻塞隊(duì)列；空白隊(duì)列（PCB區(qū)的空PCB塊）

索引方式：

同狀態(tài)的PCB同樣集中記錄诈唬，但以索引表的方式記錄PCB的地址韩脏。用專(zhuān)門(mén)的單元記錄各索引表的首地址。

2.2進(jìn)程控制

進(jìn)程控制一般由OS的內(nèi)核中的原語(yǔ)（Primitive）實(shí)現(xiàn)铸磅，原子操作（Action Operation）在執(zhí)行過(guò)程中不允許被中斷赡矢。

進(jìn)程控制的基本過(guò)程：

進(jìn)程的創(chuàng)建

進(jìn)程的終止

進(jìn)程的阻塞與喚醒

進(jìn)程的掛起和激活

系統(tǒng)中運(yùn)行的進(jìn)程并不都是孤立的，有的進(jìn)程運(yùn)行后阅仔，會(huì)調(diào)用其他進(jìn)程來(lái)執(zhí)行吹散，這樣就組成了進(jìn)程間的父子關(guān)系。

1.進(jìn)程的創(chuàng)建

1）一個(gè)進(jìn)程創(chuàng)建另一進(jìn)程的事件（原因）

用戶(hù)登錄：分時(shí)情況下用戶(hù)的請(qǐng)求

作業(yè)調(diào)度：批處理中

提供服務(wù)：運(yùn)行中的用戶(hù)程序提出功能請(qǐng)求八酒，要?jiǎng)?chuàng)建服務(wù)進(jìn)程（如打印服務(wù)）

應(yīng)用請(qǐng)求：應(yīng)用程序自己創(chuàng)建進(jìn)程空民，完成特定功能的新進(jìn)程。（木馬程序）

2）創(chuàng)建過(guò)程

原語(yǔ)是由若干指令構(gòu)成的原子操作過(guò)程，作為整體實(shí)現(xiàn)功能界轩，不可被打斷画饥。

進(jìn)程創(chuàng)建的步驟，即操作系統(tǒng)調(diào)用原語(yǔ)Create()按下述步驟創(chuàng)建新進(jìn)程浊猾。

（1）申請(qǐng)空白PCB

（2）為進(jìn)程分配資源

（3）初始化進(jìn)程控制塊

（4）將新進(jìn)程插入就緒隊(duì)列

進(jìn)程的阻塞與喚醒（原語(yǔ)Block(),Wakeup()必須成對(duì)使用）

（1）請(qǐng)求系統(tǒng)服務(wù)

（2）啟動(dòng)某種操作

（3）新數(shù)據(jù)尚未到達(dá)

（4）無(wú)新工作可做

進(jìn)程的掛起與激活

（1）檢查被掛起進(jìn)程的狀態(tài)抖甘，活動(dòng)就緒則改為靜止就緒，活動(dòng)阻塞則改為靜止阻塞

（2）將該P(yáng)CB復(fù)制到內(nèi)存（方便檢查）/外存（對(duì)換）指定區(qū)域

（3）若掛起的進(jìn)程是執(zhí)行態(tài)葫慎，則需重新進(jìn)行進(jìn)程調(diào)度衔彻。

關(guān)于調(diào)度

進(jìn)程控制中，狀態(tài)轉(zhuǎn)換和調(diào)度密切相關(guān)偷办。

運(yùn)行態(tài)進(jìn)程的改變必然產(chǎn)生調(diào)度行為

只要產(chǎn)生新就緒態(tài)進(jìn)程艰额，就需考慮調(diào)度策略

只要是采用搶占式調(diào)度，要檢查新就緒進(jìn)程是否可搶占CPU椒涯，引起新的調(diào)度柄沮。

2.3進(jìn)程同步

進(jìn)程同步的主要任務(wù)就是對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能夠有效的共享資源和相互合作逐工。從而使程序的執(zhí)行具有可再現(xiàn)性。

進(jìn)程間的兩種制約關(guān)系：

間接制約：多出現(xiàn)在同一系統(tǒng)中漂辐，如兩個(gè)進(jìn)程共享打印機(jī)資源泪喊。

直接制約：如進(jìn)程A要給進(jìn)程B輸入數(shù)據(jù)。

臨界資源：如打印機(jī)髓涯，磁帶機(jī)等袒啼。

人們把每個(gè)進(jìn)程中訪(fǎng)問(wèn)臨界資源的那段代碼成為臨界區(qū)，將檢查某資源是否被訪(fǎng)問(wèn)的代碼成為進(jìn)入?yún)^(qū)纬纪，訪(fǎng)問(wèn)后將臨界區(qū)標(biāo)志恢復(fù)為未被訪(fǎng)問(wèn)的代碼叫做退出區(qū)蚓再。

1.進(jìn)程同步的基本概念

1）進(jìn)程同步的主要任務(wù)：

? ?使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性包各。

2）臨界資源

一次僅允許一個(gè)進(jìn)程使用的資源摘仅。

生產(chǎn)者—消費(fèi)者問(wèn)題：

一群生產(chǎn)者進(jìn)程生產(chǎn)產(chǎn)品供給消費(fèi)者進(jìn)程消費(fèi)，在兩者之間設(shè)置具有n個(gè)緩沖區(qū)的緩沖池问畅，生產(chǎn)者進(jìn)程所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中娃属，消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。

生產(chǎn)者和消費(fèi)者都以異步方式運(yùn)行护姆，但它們之間必須保持同步：沒(méi)有產(chǎn)品不能取矾端，沒(méi)有空間不能放。也不能同時(shí)對(duì)一個(gè)空間進(jìn)行取和放

生產(chǎn)一個(gè)卵皂，消費(fèi)一個(gè)秩铆，還有的產(chǎn)品數(shù)應(yīng)是5。本例順序得到結(jié)果4灯变，生產(chǎn)方會(huì)認(rèn)為還可以繼續(xù)生產(chǎn)n-4個(gè)殴玛。比實(shí)際需求的n-5多生產(chǎn)的一個(gè)必然會(huì)覆蓋一個(gè)舊產(chǎn)品捅膘。若后兩句交換順序得到結(jié)果又是6，消費(fèi)方則會(huì)錯(cuò)誤的向下多消費(fèi)一個(gè)族阅。

同步與互斥：

互斥：在操作系統(tǒng)中篓跛，當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)使用臨界資源時(shí)，另一個(gè)進(jìn)程必須等待坦刀，直到占用臨界資源的進(jìn)程退出臨界區(qū)愧沟，我們稱(chēng)進(jìn)程之間的這種相互制約關(guān)系為“互斥”。

同步：多個(gè)相互合作的進(jìn)程鲤遥，在一些關(guān)鍵點(diǎn)上可能需要互相等待或互相交換信息沐寺，這種相互制約關(guān)系稱(chēng)為進(jìn)程同步關(guān)系「悄危可理解為“有序”混坞。

3）臨界區(qū)

每個(gè)進(jìn)程中訪(fǎng)問(wèn)臨界資源的那段代碼叫臨界區(qū)。為了正確同步钢坦，對(duì)臨界區(qū)的代碼要增加控制

進(jìn)入?yún)^(qū)：對(duì)欲訪(fǎng)問(wèn)的臨界資源進(jìn)行檢究孕。若此刻未被訪(fǎng)問(wèn)，設(shè)正在訪(fǎng)問(wèn)的標(biāo)志

臨界區(qū)：訪(fǎng)問(wèn)臨界資源的代碼爹凹。

退出區(qū)：將正在訪(fǎng)問(wèn)的標(biāo)志恢復(fù)為未被訪(fǎng)問(wèn)的標(biāo)志

剩余區(qū)：其余部分

4）同步機(jī)制應(yīng)遵循的規(guī)則

每個(gè)進(jìn)程中訪(fǎng)問(wèn)臨界資源的那段代碼叫臨界區(qū)厨诸。為了正確同步，對(duì)臨界區(qū)的代碼要增加控制禾酱。同步機(jī)制應(yīng)該遵循的規(guī)則：

空閑讓進(jìn)微酬，忙則等待，有限等待颤陶，讓權(quán)等待颗管。

信號(hào)量機(jī)制：

1 整型信號(hào)量：

1.信號(hào)量定義為一個(gè)整型量；

2.根據(jù)初始情況賦相應(yīng)的值滓走；

3.僅能通過(guò)兩個(gè)原子操作來(lái)訪(fǎng)問(wèn)垦江。

最初由Dijkstra把整型變量定義為一個(gè)用于表資源數(shù)目的整型量S，它與一般整型量不同搅方，僅可通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作（P疫粥、V操作）wait(S)和Signal（S）來(lái)訪(fǎng)問(wèn)。

操作描述：

wait(S):while S<=0 do no-op;//如果資源為空腰懂，則循環(huán)等待

S:=S-1;//一旦有資源則使用資源梗逮，資源數(shù)目減一

signal(S): S:=S+1;//生產(chǎn)資源。

2 記錄型信號(hào)量：

該機(jī)制中除了一個(gè)表示資源數(shù)目的變量Value之外绣溜，還增加了一個(gè)進(jìn)程鏈表L慷彤，用于鏈接上述所有等待的進(jìn)程

該記錄型的數(shù)據(jù)結(jié)構(gòu)表示為：

type semaphore = record

value:integer;

L:list of process

end

則wait(S)和Signal(S)操作可描述為：

procedure wait(S)//請(qǐng)求資源

var S：semaphore;//聲明一個(gè)數(shù)據(jù)結(jié)構(gòu)

begin

S.value = S.value - 1;//請(qǐng)求一個(gè)單位資源，S.value的絕對(duì)值表示已阻塞的進(jìn)程數(shù)目。

if S.value < 0 then block(S.L);//如果該資源已分配完畢底哗，則讓其阻塞岁诉，放棄處理機(jī)，并插入到信號(hào)量鏈表

end

procedure signal(S)//釋放資源

var S: semaphore;

begin

S.value = S.value + 1;//釋放一個(gè)單位資源跋选，若釋放后S.value仍然是負(fù)值則說(shuō)明仍有進(jìn)程在等待涕癣，則喚醒S.L鏈表中的第一個(gè)等待進(jìn)程

if S.value <= 0 then wakeup(S.L);

end

若S.value初值為1，則信號(hào)量轉(zhuǎn)為互斥信號(hào)量前标，只允許一個(gè)進(jìn)程訪(fǎng)問(wèn)臨界資源坠韩。

民航售票系統(tǒng)問(wèn)題

n個(gè)售票處。每個(gè)售票處通過(guò)終端訪(fǎng)問(wèn)系統(tǒng)的公用數(shù)據(jù)區(qū)

假定公用數(shù)據(jù)區(qū)中分別用Ri表示某時(shí)間i次航班的現(xiàn)存票數(shù)炼列。

Pi表示某售票處的處理進(jìn)程只搁，試用信號(hào)量實(shí)現(xiàn)進(jìn)程間的互斥關(guān)系。

Var? s: semaphore?:=1;

?????? begin

??????? parbegin

??????????? process Pi:

begin

repeat

P(s);

按旅客定票要求找到Ri

IF

Ri >=1

then

??? Ri =Ri -1;

? 輸出一張票俭尖；

End

if

V(s);

輸出“票已售完”氢惋；

until

false;

? end

???????????? parend

????? end

3 AND型信號(hào)量

上述各進(jìn)程問(wèn)題針對(duì)進(jìn)程之間共享一個(gè)臨界資源而言。但有些時(shí)候一個(gè)進(jìn)程需要獲得兩三個(gè)資源方可執(zhí)行稽犁。設(shè)進(jìn)程A,B都要求訪(fǎng)問(wèn)數(shù)據(jù)D和E焰望。則為這兩個(gè)臨界資源分別設(shè)置互斥的信號(hào)量Dmutex，Emutex = 1;則在兩個(gè)進(jìn)程中都需要對(duì)Dmutex和Emutex進(jìn)行操作已亥，即

process A： process B：

wait(Dmutex); wait(Emutex);

wait(Emutex); wait(Dmutex);

但這樣交替執(zhí)行四個(gè)操作的時(shí)候熊赖，會(huì)發(fā)生死鎖。故該AND同步機(jī)制的基本思想就是將進(jìn)程所需資源一次性分配給進(jìn)程陷猫，使用完后一起釋放秫舌。即在wait操作中增加

AND的條件的妖，成為AND同步绣檬，或成為同步wait操作，即Swait():

Swait(S1,S2,……,Sn)

if Si >= 1 and …… and Sn >= 1 then

for i:= 1 to n do

Si:= Si - 1;

endfor

else

//等待

endif

Ssignal(S1,S2,……,Sn)

for i:= 1 to n do

Si:= Si + 1;

//喚醒等待進(jìn)程

endfor

4 信號(hào)量集

變量和信號(hào)量

buffer: array [ 0, …, n-1] of item;

in, out: integer :=0, 0;

不使用Counter變量嫂粟，而是用信號(hào)量

Var? mutex,empty, full:

semaphore :=1,n, 0;

記錄型變量一次只能獲得或釋放一個(gè)單位資源娇未，當(dāng)一次需要N個(gè)單位資源的時(shí)候顯得低效。因此星虹，當(dāng)資源數(shù)量低于某一下限值時(shí)便不予以分配零抬。因此Swait操作可描述如下

，S為信號(hào)量宽涌，d為需求值平夜，t為下限值。Swait可描述為

Swait(S1,t1,d1,...,Sn,tn,dn)

if S1 >= t1 and ... Sn >= tn then

for i:=1 to n do

Si:=Si - di;

endfor

else

//阻塞等待

endif

for i:=1 to n do

Si:=Si + di;

//釋放資源

endfor;

Ssignal(S1,t1,d1,...,Sn,tn,dn)

利用信號(hào)量實(shí)現(xiàn)的前趨關(guān)系：

如圖

Var a,b,c,d,e,f,g: semaphore:=0,0,0,0,0,0,0;

begin

parbegin

begin S1; signal(a);signal(b);end;

begin wait(a);S2;signal(c);signal(d);end;

begin wait(b);S3;signal(e);end;

begin wait(c);S4;signal(f);end;

begin wait(d);S5;signal(g);end;

begin wait(e);wait(f);wait(g);S6;end;

parend

end

管程機(jī)制

管程是由代表共享資源的數(shù)據(jù)結(jié)構(gòu)卸亮，以及由對(duì)該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施操作的一組過(guò)程所組成的資源管理程序忽妒，共同構(gòu)成的一個(gè)操作系統(tǒng)的資源管理模塊。

管程由四部分組成：

1 管程的名稱(chēng)

2 局部于管程內(nèi)部的數(shù)據(jù)結(jié)說(shuō)明

3 對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程

4 對(duì)局部于管程內(nèi)部的共享資源設(shè)置初始化值的語(yǔ)句

條件變量：管程中對(duì)每個(gè)條件變量都須予以說(shuō)明：

Var x,y:conditon

x.wait;//正在調(diào)用管程的進(jìn)程因x條件的需要被阻塞或掛起。調(diào)用x.wait將自己插入到x條件的等待隊(duì)列上段直，并釋放管程吃溅，直到x條件變化。

x.signal;//正在調(diào)用管程的進(jìn)程發(fā)現(xiàn)x條件發(fā)生變化鸯檬，則調(diào)用x.signal决侈，重新啟動(dòng)一個(gè)因x條件而阻塞或掛起的進(jìn)程

管程(monitor)機(jī)制

1.管程的組成

2.管程的特點(diǎn)

3.管程的同步控制（條件變量）

類(lèi)比生產(chǎn)者—消費(fèi)者問(wèn)題

需要封裝什么？

1.多進(jìn)程需訪(fǎng)問(wèn)的變量：

§buffer喧务，in赖歌，out；

§empty蹂楣，full俏站；

2.對(duì)變量做的操作：

§向buffer放/取產(chǎn)品，移動(dòng)指針in痊土，out肄扎；

§控制放或取的信號(hào)量操作wait、signal赁酝；

管程的組成：

1.一組局部變量

2.對(duì)局部變量操作的一組過(guò)程

3.對(duì)局部變量進(jìn)行初始化的語(yǔ)句犯祠。（聯(lián)想面向?qū)ο笾械念?lèi)）

管程特點(diǎn)

任何進(jìn)程只能通過(guò)調(diào)用管程提供的過(guò)程入口才能進(jìn)入管程訪(fǎng)問(wèn)共享數(shù)據(jù)；

就如同使用臨界資源酌呆，就要先通過(guò)其信號(hào)量的申請(qǐng)衡载。

任何時(shí)刻，僅允許一個(gè)進(jìn)程在管程中執(zhí)行某個(gè)內(nèi)部過(guò)程隙袁。

如何實(shí)現(xiàn)同步痰娱？

對(duì)共享變量互斥操作：

? 管程的特點(diǎn)直接實(shí)現(xiàn)了該要求，進(jìn)程一次一個(gè)進(jìn)入管程調(diào)用內(nèi)部過(guò)程操作共享變量菩收。

管程的互斥訪(fǎng)問(wèn)完全由編譯程序在編譯時(shí)自動(dòng)添上梨睁，無(wú)須程序員關(guān)心，能保證正確娜饵。

操作的同步控制：

靠條件變量的操作管理實(shí)現(xiàn)坡贺。

? 進(jìn)入管程但不能獲取資源操作的過(guò)程將阻塞，并在滿(mǎn)足條件時(shí)被喚醒執(zhí)行箱舞。

條件變量

（主要作用就是進(jìn)程同步的阻塞和喚醒控制）

局部于管程的變量有兩種：

普通變量

條件變量（用于控制進(jìn)程阻塞和喚醒）

類(lèi)似信號(hào)量變量遍坟，但不取具體值；相當(dāng)于每個(gè)阻塞隊(duì)列的隊(duì)列指針晴股。

對(duì)條件變量的操作需結(jié)合對(duì)普通變量的條件判斷愿伴，從而控制進(jìn)程狀態(tài)。

管程的優(yōu)點(diǎn)

保證進(jìn)程互斥地訪(fǎng)問(wèn)共享變量电湘，并方便地阻塞和喚醒進(jìn)程隔节。管程可以以函數(shù)庫(kù)的形式實(shí)現(xiàn)万搔。相比之下，管程比信號(hào)量好控制官帘。

管程可增強(qiáng)模塊的獨(dú)立性：系統(tǒng)按資源管理的觀點(diǎn)分解成若干模塊瞬雹，用數(shù)據(jù)表示抽象系統(tǒng)資源，使同步操作相對(duì)集中刽虹，從而增加了模塊的相對(duì)獨(dú)立性

引入管程可提高代碼的可讀性酗捌，便于修改和維護(hù)，正確性易于保證：采用集中式同步機(jī)制涌哲。一個(gè)操作系統(tǒng)或并發(fā)程序由若干個(gè)這樣的模塊所構(gòu)成胖缤，一個(gè)模塊通常較短，模塊之間關(guān)系清晰阀圾。

管程的缺點(diǎn)

大多數(shù)常用的編程語(yǔ)言中沒(méi)有實(shí)現(xiàn)管程哪廓，如果某種語(yǔ)言本身不支持管程，那么加入管程是很困難的初烘。

雖然大多數(shù)編程語(yǔ)言也沒(méi)有實(shí)現(xiàn)信號(hào)量涡真，但可將P、V操作作為一個(gè)獨(dú)立的子例程或操作系統(tǒng)的管理程序調(diào)用加入肾筐。

進(jìn)程通信

? 進(jìn)程通信是指進(jìn)程之間的信息交換哆料。

一、低級(jí)通信——進(jìn)程之間的互斥和同步

? 信號(hào)量機(jī)制是有效的同步工具吗铐，但作為通信工具缺點(diǎn)如下：

(1)效率低（通信量少）

(2)通信對(duì)用戶(hù)不透明（程序員實(shí)現(xiàn)东亦，操作系統(tǒng)只提供共享存儲(chǔ)器供代碼操作）

二、高級(jí)進(jìn)程通信

? 用戶(hù)直接利用操作系統(tǒng)提供的一組通信命令唬渗，高效地傳送大量數(shù)據(jù)的通信方式典阵。

? 操作系統(tǒng)隱藏了進(jìn)程通信的細(xì)節(jié)，對(duì)用戶(hù)透明镊逝，減少了通信程序編制上的復(fù)雜性壮啊。

1.進(jìn)程通信的類(lèi)型

高級(jí)通信機(jī)制可歸結(jié)為四大類(lèi)

①共享存儲(chǔ)器系統(tǒng)（操作存儲(chǔ)區(qū)方式）

? 相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)，進(jìn)程之間能夠通過(guò)這些空間進(jìn)行通信蹋半。

a.基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（低級(jí)）

b.基于共享存儲(chǔ)區(qū)的通信方式（高級(jí)）

②消息傳遞系統(tǒng)（發(fā)--收方式）

最廣泛使用的一種他巨，進(jìn)程間的數(shù)據(jù)交換充坑，以格式化的消息為單位减江。屏蔽底層復(fù)雜操作。

單機(jī)：操作系統(tǒng)底層編程中的消息傳遞系統(tǒng)調(diào)用捻爷；

計(jì)算機(jī)網(wǎng)絡(luò)：消息稱(chēng)為報(bào)文辈灼。程序員直接利用系統(tǒng)提供的一組通信命令(原語(yǔ))進(jìn)行通信。（④客戶(hù)機(jī)-服務(wù)器系統(tǒng)）

③管道通信（中間文件方式）

所謂“管道”也榄，是指用于連接一讀進(jìn)程和一寫(xiě)進(jìn)程以實(shí)現(xiàn)通信的一個(gè)共享文件巡莹，又名pipe文件司志。

向共享文件輸入的寫(xiě)進(jìn)程以字符流形式將大量的數(shù)據(jù)送入管道；而接收管道輸出的讀進(jìn)程則從管道中接收(讀)數(shù)據(jù)降宅。

首創(chuàng)于UNIX系統(tǒng)骂远。其管道機(jī)制需提供三方面的協(xié)調(diào)能力：互斥、同步腰根、確定對(duì)方是否存在激才。

④Client-Server system

套接字（Socket）

一個(gè)套接字就是一個(gè)通信標(biāo)識(shí)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)，包含了通信目的的地址额嘿，端口號(hào)瘸恼，傳輸層協(xié)議、進(jìn)程所在的網(wǎng)絡(luò)地址册养，以及針對(duì)C\S程序提供的不同系統(tǒng)調(diào)用（API函數(shù)）等东帅。

系統(tǒng)中所有的連接都持有唯一的一對(duì)套接字及端口連接，從而方便地區(qū)分來(lái)自不同應(yīng)用程序進(jìn)程或網(wǎng)絡(luò)連接的通信球拦，確保通信雙方間邏輯鏈路的唯一性靠闭。

遠(yuǎn)程過(guò)程調(diào)用（遠(yuǎn)程方法調(diào)用）

RPC?有很多正面的應(yīng)用，比如網(wǎng)絡(luò)文件系統(tǒng)NFS坎炼、Web

Service等阎毅，也是網(wǎng)絡(luò)安全中容易被攻擊的技術(shù)。

Remote Procedure Call点弯，遠(yuǎn)程過(guò)程調(diào)用扇调。也就是說(shuō)，調(diào)用過(guò)程代碼并不是在調(diào)用者本地運(yùn)行抢肛，而是要實(shí)現(xiàn)調(diào)用者與被調(diào)用者二地之間的連接與通信狼钮。

RPC的基本通信模型是基于Client/Server進(jìn)程間相互通信模型的一種同步通信形式；它對(duì)Client提供了遠(yuǎn)程服務(wù)的過(guò)程抽象捡絮，其底層消息傳遞操作對(duì)Client是透明的熬芜。

2.消息傳遞通信的實(shí)現(xiàn)方法

1）直接通信方式

? 發(fā)送進(jìn)程利用OS所提供的發(fā)送命令（原語(yǔ)），直接把消息發(fā)送給目標(biāo)進(jìn)程福稳。此時(shí)涎拉，發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式提供對(duì)方的標(biāo)識(shí)符。通常利用系統(tǒng)通信命令（原語(yǔ)）：

2）間接通信方式

? 基于共享數(shù)據(jù)結(jié)構(gòu)的實(shí)體用來(lái)暫存發(fā)送給目標(biāo)進(jìn)程的消息的圆；接收進(jìn)程則從該實(shí)體中鼓拧，取出對(duì)方發(fā)送給自己的消息。通常把這種實(shí)體稱(chēng)為信箱越妈。

消息在信箱中可以安全地保存季俩，只允許核準(zhǔn)的目標(biāo)用戶(hù)隨時(shí)讀取。既可實(shí)時(shí)通信梅掠，又可非實(shí)時(shí)通信酌住。

3.消息傳遞系統(tǒng)的實(shí)現(xiàn)

? 單機(jī)和網(wǎng)絡(luò)環(huán)境下的高級(jí)進(jìn)程通信廣泛采用“消息傳遞”方式店归，需要考慮的問(wèn)題：

①通信鏈路的建立

計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境下，用原語(yǔ)顯式建立/拆除鏈路

單機(jī)系統(tǒng)只須利用系統(tǒng)原語(yǔ)酪我，進(jìn)程間鏈路由系統(tǒng)自動(dòng)管理消痛。

②消息格式

單機(jī)系統(tǒng)，發(fā)送與接收進(jìn)程在同一臺(tái)機(jī)器都哭，環(huán)境相同故格式簡(jiǎn)單肄满；

網(wǎng)絡(luò)環(huán)境下，受不同目標(biāo)機(jī)器的環(huán)境和長(zhǎng)距離信息傳輸?shù)纫蛩氐挠绊懼侍危⒏袷捷^復(fù)雜稠歉，消息常是“大頭+正文”

③同步方式

即考慮平時(shí)閑著，還是平時(shí)忙碌汇陆？

發(fā)送進(jìn)程阻塞怒炸、接收進(jìn)程阻塞（無(wú)緩沖緊密同步）發(fā)送進(jìn)程不阻塞、接收進(jìn)程阻塞（服務(wù)器程序）發(fā)送進(jìn)程和接收進(jìn)程均不阻塞（緩沖隊(duì)列）

4.消息緩沖隊(duì)列通信機(jī)制

①不需管理鏈路

②定義簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（亦即消息格式）

本機(jī)通信消息結(jié)構(gòu)簡(jiǎn)單毡代，如下：

type message

buffer = record

? sender;?? 發(fā)送者進(jìn)程標(biāo)識(shí)符

? size;?? 消息長(zhǎng)度

? text;?? 消息正文

? next;?? 指向下一消息緩沖區(qū)的指針

end

③實(shí)現(xiàn)發(fā)送和接收的操作原語(yǔ)

procedure send(receiver, a)

???begin

??????? getbuf(a.size, i);?根據(jù)a.size申請(qǐng)緩沖區(qū)

??????? i.sender :=a.sender;? 將發(fā)送區(qū)a中的信息復(fù)制到 i

??????? i.size :=a.size;

??????? i.text :=a.text;

??????? i.next :=0;

獲取接收進(jìn)程內(nèi)部標(biāo)識(shí)符

? ??? getid(PCB set, receiver, j);

? ?? insert(j.mq,i); 將消息緩沖區(qū)插入目標(biāo)消息隊(duì)列

???end

線(xiàn)程

1阅羹、認(rèn)識(shí)線(xiàn)程

多線(xiàn)程系統(tǒng)中，同一個(gè)進(jìn)程中的多個(gè)線(xiàn)程

共享進(jìn)程資源

可并發(fā)執(zhí)行

2.線(xiàn)程的屬性

? 多線(xiàn)程O(píng)S中教寂，一個(gè)進(jìn)程包括多個(gè)線(xiàn)程捏鱼，每個(gè)線(xiàn)程都是利用CPU的基本單位。

輕型實(shí)體：只需一點(diǎn)必不可少的酪耕、能保證獨(dú)立運(yùn)行的資源导梆。（TCB）

獨(dú)立調(diào)度和分派的基本單位：調(diào)度切換迅速且開(kāi)銷(xiāo)小∮厮福可并發(fā)執(zhí)行

共享進(jìn)程資源：同進(jìn)程中的線(xiàn)程可共享相同的進(jìn)程地址空間看尼、已打開(kāi)文件、信號(hào)量機(jī)構(gòu)等盟步。

3.線(xiàn)程的信息

狀態(tài)參數(shù)? ?標(biāo)識(shí)符藏斩、運(yùn)行狀態(tài)、優(yōu)先級(jí)却盘、寄存器狀態(tài)狰域、堆棧、專(zhuān)有存儲(chǔ)器黄橘、信號(hào)屏蔽等兆览。

運(yùn)行狀態(tài)? ?執(zhí)行、就緒旬陡、阻塞

多線(xiàn)程編程過(guò)程是類(lèi)似的：

可用win32

API編寫(xiě)C風(fēng)格程序

C的main既是規(guī)定了主線(xiàn)程的代碼拓颓。啟動(dòng)程序時(shí)语婴，系統(tǒng)根據(jù)main地址描孟，啟動(dòng)主線(xiàn)程驶睦。

在主線(xiàn)程代碼某處利用線(xiàn)程創(chuàng)建函數(shù)即可創(chuàng)建線(xiàn)程；給創(chuàng)建函數(shù)編寫(xiě)線(xiàn)程功能代碼匿醒；

利用其他一系列函數(shù)使系統(tǒng)管理多個(gè)線(xiàn)程场航。

也可用封裝好的類(lèi)庫(kù)，如JAVA廉羔，MFC

4.

線(xiàn)程的創(chuàng)建和終止

? 在多線(xiàn)程O(píng)S中溉痢，應(yīng)用程序啟動(dòng)時(shí)，通常只有一個(gè)線(xiàn)程(初始化線(xiàn)程)在執(zhí)行憋他，它根據(jù)需要再創(chuàng)建若干線(xiàn)程孩饼。

創(chuàng)建新線(xiàn)程

? 利用線(xiàn)程創(chuàng)建函數(shù)(或系統(tǒng)調(diào)用)，提供相應(yīng)參數(shù)竹挡。線(xiàn)程創(chuàng)建函數(shù)執(zhí)行完后镀娶，返回一個(gè)線(xiàn)程標(biāo)識(shí)符供以后使用。

線(xiàn)程被終止：

? 不立即釋放資源揪罕，只有當(dāng)進(jìn)程中的其它線(xiàn)程執(zhí)行分離函數(shù)后梯码，資源才分離出來(lái)能被其它線(xiàn)程利用。

? 被終止而未釋放資源的線(xiàn)程仍可被需要它的線(xiàn)程調(diào)用好啰，使其重新恢復(fù)運(yùn)行轩娶。

5.多線(xiàn)程系統(tǒng)中的進(jìn)程

進(jìn)程只是用于分配系統(tǒng)資源

包括多個(gè)線(xiàn)程

不是執(zhí)行實(shí)體，線(xiàn)程在進(jìn)程范圍內(nèi)作為執(zhí)行實(shí)體框往。

6.線(xiàn)程的管理

同步和通信機(jī)制

1）互斥鎖

比較簡(jiǎn)單的鳄抒，控制線(xiàn)程互斥訪(fǎng)問(wèn)資源；

適用于高頻度使用的關(guān)鍵共享數(shù)據(jù)和程序段椰弊；

unlock和lock兩個(gè)鎖操作原語(yǔ)嘁酿；

2）條件變量

與互斥鎖一起使用

鎖保證互斥進(jìn)入臨界區(qū)，但利用條件變量使線(xiàn)程阻塞

注意不滿(mǎn)足條件時(shí)男应，wait條件變量：

釋放互斥鎖

進(jìn)程阻塞在條件變量指向隊(duì)列中

被喚醒后要重新再設(shè)互斥鎖

3）信號(hào)量

私用信號(hào)量（privatesamephore）

用于同進(jìn)程的線(xiàn)程間同步闹司，數(shù)據(jù)結(jié)構(gòu)存放在應(yīng)用程序的地址空間。屬于特定進(jìn)程沐飘，OS感知不到其存在游桩。

公用信號(hào)量（publicsamephore）

用于不同進(jìn)程間或不同進(jìn)程中線(xiàn)程的同步，數(shù)據(jù)結(jié)構(gòu)由OS管理耐朴，存放在受保護(hù)的系統(tǒng)存儲(chǔ)區(qū)借卧。

二、線(xiàn)程的實(shí)現(xiàn)方式

1.內(nèi)核線(xiàn)程KST(kernel-level thread)

依賴(lài)于內(nèi)核筛峭，利用系統(tǒng)調(diào)用由OS內(nèi)核在內(nèi)核空間完成創(chuàng)建铐刘、撤消、切換等線(xiàn)程工作影晓。

時(shí)間片分配給線(xiàn)程镰吵，所以多線(xiàn)程的進(jìn)程獲得更多CPU時(shí)間檩禾。

2.用戶(hù)線(xiàn)程ULT(user-level thread)

無(wú)須利用系統(tǒng)調(diào)用，不依賴(lài)于OS核心疤祭。進(jìn)程利用線(xiàn)程庫(kù)函數(shù)創(chuàng)建盼产、同步、調(diào)度和管理控制用戶(hù)線(xiàn)程勺馆。

調(diào)度由應(yīng)用軟件內(nèi)部進(jìn)行戏售，通常采用非搶先式和更簡(jiǎn)單的規(guī)則，也無(wú)需用戶(hù)態(tài)/核心態(tài)切換草穆，速度比kst快灌灾。

3.組合方式

內(nèi)核支持多KST線(xiàn)程的管理，同時(shí)也允許用戶(hù)應(yīng)用程序級(jí)的線(xiàn)程管理悲柱。