筆記主要來自西安電子科技大學(xué)出版的《計(jì)算機(jī)操作系統(tǒng)》一書,侵刪
第二章進(jìn)程的描述與控制
2.1(前驅(qū)圖和程序執(zhí)行)
前驅(qū)圖:一個有向無循環(huán)圖,結(jié)點(diǎn)是進(jìn)程/程序段/一條語句鹦蠕,邊是兩個結(jié)點(diǎn)之間的偏序或前驅(qū)關(guān)系梆靖。(知道前驅(qū)圖所描述的程序執(zhí)行步驟即可)
程序的順序執(zhí)行:
- 特征:順序性控汉、封閉性、可再現(xiàn)性
程序并發(fā)執(zhí)行:多個程序在同一時(shí)間間隔內(nèi)交替執(zhí)行
- 特點(diǎn):間斷性返吻、失去封閉性姑子、不可再現(xiàn)性。
2.2(進(jìn)程的描述)
進(jìn)程的不同定義:
- 定義1:程序的一次執(zhí)行過程测僵。
- 定義2:進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程街佑,是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)立單位。(獲取CPU的使用權(quán))
- 定義3:由程序段捍靠、相關(guān)數(shù)據(jù)段舆乔、PCB組成的進(jìn)程實(shí)體,簡稱進(jìn)程剂公。(結(jié)構(gòu)特征)
進(jìn)程的特征:動態(tài)性希俩、并發(fā)性、獨(dú)立性纲辽、異步性颜武。
進(jìn)程的基本狀態(tài):
-
三基本狀態(tài):就緒狀態(tài)、執(zhí)行狀態(tài)拖吼、阻塞狀態(tài)鳞上。(常加入 創(chuàng)建狀態(tài) 和 終止?fàn)顟B(tài) 以增強(qiáng)管理的靈活性)
三基本狀態(tài)的轉(zhuǎn)換:
三基本狀態(tài)的轉(zhuǎn)換 - 掛起狀態(tài):進(jìn)程被掛起->進(jìn)入靜止?fàn)顟B(tài)(一般是負(fù)荷調(diào)節(jié)或其他進(jìn)程/用戶/操作系統(tǒng)的需要)
-
引入掛起原語操作后三個進(jìn)程狀態(tài)的轉(zhuǎn)換
不允許CPU一直空閑,CPU一空閑就要調(diào)用準(zhǔn)備就緒的進(jìn)程吊档。
圖片.png
進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu):一般分四類(內(nèi)存表篙议、設(shè)備表、文件表怠硼、進(jìn)程表)
PCB(進(jìn)程控制模塊):用于進(jìn)程管理的進(jìn)程表鬼贱,是進(jìn)程存在的唯一信息。(進(jìn)程管理一般就是對一堆PCB進(jìn)行增刪查改等操作) - 包括的信息:進(jìn)程標(biāo)識符香璃、處理機(jī)狀態(tài)这难、進(jìn)程調(diào)度信息、進(jìn)程控制信息
- 組織方式:
線性方式:系統(tǒng)中的所有PCB都組織在一張線性表上葡秒。
鏈接方式:把具有相同狀態(tài)進(jìn)程的PCB分別通過PCB中的鏈接字鏈接成一個隊(duì)列姻乓。
索引方式:根據(jù)所有進(jìn)程狀態(tài)的不同嵌溢,建立幾張索引表。
2.3(進(jìn)程控制)
進(jìn)程控制一般由OS的內(nèi)核中的原語來實(shí)現(xiàn)的蹋岩。
進(jìn)程控制包括:創(chuàng)建新進(jìn)程赖草、終止已完成的進(jìn)程、將異常進(jìn)程置于阻塞狀態(tài)剪个。
處理機(jī)的兩種狀態(tài):核心態(tài)(系統(tǒng)態(tài)秧骑,高執(zhí)行權(quán))、用戶態(tài)(低執(zhí)行權(quán))禁偎。
OS內(nèi)核:基于硬件的第一次軟件擴(kuò)充腿堤,常駐內(nèi)存阀坏。
原語:由若干指令組成如暖,用于完成一定功能的一個過程。(不可分割)
(為什么忌堂、怎么做格式)
進(jìn)程的創(chuàng)建:
- 進(jìn)程圖:描述進(jìn)程間關(guān)系的一棵有向樹
- 引起創(chuàng)建進(jìn)程的事件:用戶登錄盒至、作業(yè)調(diào)度、提供服務(wù)士修、應(yīng)用請求
- 進(jìn)程的創(chuàng)建:申請空白PCB、為新進(jìn)程分配其運(yùn)行所需的資源、初始化PCB膀曾、新進(jìn)程插入就緒隊(duì)列
進(jìn)程的終止:
- 引起進(jìn)程終止的事件:正常結(jié)束叁熔、異常結(jié)束、外界干預(yù)
- *終止過程:調(diào)用終止原語
若處于執(zhí)行狀態(tài)沸移,則終止該進(jìn)程的執(zhí)行痪伦,置調(diào)度標(biāo)志為真
終止進(jìn)程,包括其子孫進(jìn)程
歸還資源給父進(jìn)程或系統(tǒng)
將被終止進(jìn)程(PCB)從所在隊(duì)列或鏈表中移出
進(jìn)程的阻塞與喚醒:
- *引起事件:請求資源失敗雹锣、等待某操作完成网沾、新數(shù)據(jù)未到達(dá)、等待新任務(wù)到達(dá)蕊爵。
**阻塞過程:調(diào)用阻塞原語block
停止執(zhí)行辉哥,將現(xiàn)行狀態(tài)有“執(zhí)行”改為“阻塞”,并插入阻塞隊(duì)列 - *喚醒過程:調(diào)用喚醒原語wakeup
將事件從阻塞隊(duì)列中移出攒射,將現(xiàn)行狀態(tài)由“阻塞”改為“就緒”醋旦,將該P(yáng)CB插入到就緒隊(duì)列中
進(jìn)程的掛起與激活:
- *掛起過程:調(diào)用阻塞原語suspend(內(nèi)存->外存)
就緒狀態(tài)->靜止就緒,阻塞狀態(tài)->靜止阻塞 - *激活過程:調(diào)用阻塞原語active(外存->內(nèi)存)
靜止就緒->就緒狀態(tài)会放,靜止阻塞->活動阻塞
2.4進(jìn)程同步
進(jìn)程同步作用:保證多個進(jìn)程能夠有條不紊地進(jìn)行浑度。
進(jìn)程同步是指某些進(jìn)程之間在邏輯上的相互制約的關(guān)系
兩種形式的相互制約關(guān)系
- 間接形式的制約關(guān)系(共享資源)
*臨界資源互斥訪問,由系統(tǒng)實(shí)施分配鸦概,不允許用戶進(jìn)程直接使用 - 直接相互制約關(guān)系(相互合作)
臨界資源:一次僅允許一個進(jìn)程訪問的資源
臨界區(qū):進(jìn)程中訪問臨界資源的那段代碼
while(TRUE)
{
進(jìn)入?yún)^(qū)->檢查是否被訪問
臨界區(qū)
退出區(qū)->恢復(fù)為未訪問的標(biāo)志
剩余區(qū)
}
同步機(jī)制遵循的規(guī)則:
- 空閑讓進(jìn)
- 忙則等待
- 有限等待(以免陷入“死鎖”)
- 讓權(quán)等待(及時(shí)釋放處理機(jī)箩张,以免進(jìn)入:死等狀態(tài))
信號量機(jī)制:
- 整形信號量(信號量類型甩骏,是一個數(shù)據(jù)類型,代表資源的數(shù)量的一個整數(shù))
有P操作(wait操作先慷,申請一個資源)饮笛、V操作(signal操作,釋放一個資源)论熙,兩者成對出現(xiàn)
(整形信號量的P福青、V操作未實(shí)現(xiàn)“讓權(quán)等待”原則,是缺點(diǎn)脓诡,實(shí)際少用)
P操作
wait(S){
while(S<=0);
S--;
}
V操作
signal(S){
S++;
}
- 記錄型信號量(在整形信號量的基礎(chǔ)上增加一個進(jìn)程表指針list无午,用于鏈接所有等待的進(jìn)程)
//數(shù)據(jù)項(xiàng)描述:
typedef struct{
int value;
int struct process_control_block *list;
}semaphore;
//wait(S)和signal(S)操作描述:
wait(semaphore *S){
S->value--;
if(S->value < 0) block(S->list);//阻塞原語
}
signal(semaphore *S){
S->value++;
if(S->value <= 0) wakeup(S->list);//喚醒原語
}
S->value > 0 時(shí)S->value描述可用資源數(shù)
S->value < 0 時(shí)S->value描述阻塞資源數(shù)
S->value = 0 時(shí)可用、阻塞資源數(shù)均為0
S->value初值為1祝谚,則變?yōu)榛コ庑盘柫?/p>
- AND型信號量(與整形和記錄型相比宪迟,性能稍遜)
(當(dāng)一個進(jìn)程需要獲得兩個或更多的共享資源時(shí),用互斥實(shí)現(xiàn)容易引發(fā)死鎖交惯,因此要用AND型信號量解決)
基本思想:將進(jìn)程在整個運(yùn)行過程中需要的所有資源次泽,一次性全部地分配給進(jìn)程,待進(jìn)程使用完后再一起釋放席爽。
Swait(S1,S2,...,Sn){
while(TRUE){
if(Si >= 1 && ... && Sn >= 1){
for(i = 1;i <= n;i++) Si--;
break;
}
else{
//阻塞該進(jìn)程意荤,將該進(jìn)程涉及的信號量恢復(fù)為該進(jìn)程開始前的狀態(tài)
}
}
}
Ssignal(S1,S2,...,Sn){
while(TRUE){
for(i = 1;i <= n;i++){
Si++;
//將與Si信號量有關(guān)的阻塞進(jìn)程全部變?yōu)榫途w狀態(tài)
}
}
}
- 信號量集
每次Swait/Ssignal操作可以對某類資源進(jìn)行多個單位的申請或釋放(對AND信號量機(jī)制加以擴(kuò)充)
規(guī)定資源的分配下限值ti和對該資源的需求值di,當(dāng)才時(shí)分配資源只锻,每次分配進(jìn)行Si=Si-di操作
//對應(yīng)的Swait和Ssignal格式:
Swait(S1,t1,d1,...,Sn,tn,dn);
Ssignal(S1,d1,...,Sn,dn);
//一般信號量集的幾種特殊情況:
Swait(S,d,d) //信號量集中只有一個信號量S玖像,允許每次申請d個資源,當(dāng)現(xiàn)有資源數(shù)少于d時(shí)齐饮,不予分配
Swait(S,1,1) //蛻化為一般的記錄型信號量(S>1)或互斥信號量(S=1)
Swait(S,1,0) //當(dāng)S >= 1時(shí)允許多個進(jìn)程進(jìn)入某特定區(qū)捐寥,當(dāng)S = 0時(shí)阻止任何進(jìn)程進(jìn)入特定區(qū)
信號量的應(yīng)用:
- 利用信號量實(shí)現(xiàn)進(jìn)程互斥(類似于競爭/間接制約)
P、V成對出現(xiàn)在同一進(jìn)程中
每個臨界資源設(shè)置互斥信號量mutex沈矿,初值為1上真,將臨界區(qū)置于wait(mutex)和signal(mutex)間操作 - 利用信號量實(shí)現(xiàn)進(jìn)程同步(類似于合作/直接制約)
P、V成對出現(xiàn)在不同進(jìn)程中 - 利用信號量實(shí)現(xiàn)前驅(qū)關(guān)系
有幾個前驅(qū)設(shè)幾個進(jìn)程羹膳,前驅(qū)結(jié)點(diǎn)有多少P睡互,后繼結(jié)點(diǎn)就有多少V
解決進(jìn)程同步問題的一般步驟:(可以在書上P65-P72找例子輔助理解)
- 并發(fā)的進(jìn)程是什么(父給蘋果/桔子,兒吃蘋果陵像,女兒吃桔)
- 找到制約關(guān)系->定義信號量以及初始值(盤不滿父才放就珠,盤不空且有蘋果兒才吃,盤不空且有桔女兒才吃->s(盤剩余容量)醒颖,s0(蘋果數(shù))妻怎,s1(桔子數(shù)),若有要求三個進(jìn)程互斥可再加mutex(每個進(jìn)程都PV))
- 描述并發(fā)進(jìn)程的活動(P泞歉、V操作描述)
管程機(jī)制:(和信號量有同等的表達(dá)能力逼侦,但性能稍遜)
定義:一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過程一并稱為管程
(任一時(shí)刻管程中只能有一個活躍進(jìn)程匿辩,自動實(shí)現(xiàn)臨界區(qū)的互斥)
引入目的:使并發(fā)編程更容易、保證正確性(使用信號量機(jī)制很容易產(chǎn)生死鎖等問題)
相關(guān)的大致實(shí)現(xiàn):管程引入了條件變量(condition)以及兩個相關(guān)操作wait和signal使得進(jìn)程在無法繼續(xù)運(yùn)行時(shí)阻塞
聲明條件變量:condition x,y,...
執(zhí)行x.wait操作 :引起進(jìn)程阻塞榛丢,排在等待x的隊(duì)列中
執(zhí)行x.signal操作:喚醒等待x隊(duì)列中的隊(duì)首進(jìn)程
條件變量與信號量機(jī)制不同铲球,不是計(jì)數(shù)器
2.5經(jīng)典進(jìn)程同步問題
用哪種的P操作就用哪種的V操作對應(yīng)好
生產(chǎn)者-消費(fèi)者問題
用記錄型信號量要注意不能改變P操作的順序(先empty再mutex),V操作的順序隨意
用AND有效可以解決死鎖問題
哲學(xué)家進(jìn)餐問題
①用非AND信號量解決(最多4人同時(shí)拿筷子/只有左右筷子可用才能進(jìn)餐/奇數(shù)位先拿左邊的筷子偶數(shù)位先拿右邊的筷子)
②用記錄型信號量模擬AND信號量解決(用鎖人代替鎖筷子)
③用AND信號量解決
讀者-寫者問題1(實(shí)現(xiàn)讀寫互斥晰赞、寫寫互斥稼病、讀讀同時(shí)):
用記錄型信號量解決
設(shè)置兩個互斥信號量rmutex、wmutex掖鱼,另設(shè)一整型變量readcount
wmutex負(fù)責(zé)實(shí)現(xiàn)讀寫互斥(順便實(shí)現(xiàn)了寫寫互斥)
readcount表示讀者數(shù)然走,由0變1時(shí)要P(wmutex)(第一個讀者),由1變0要V(wmutex)(最后一個讀者)戏挡,其它情況不用處理
rmutex負(fù)責(zé)實(shí)現(xiàn)多個讀者改變r(jià)eadcount時(shí)的互斥進(jìn)行
用信號量集機(jī)制解決
設(shè)置兩個信號量L芍瑞、mx,另設(shè)一整形變量RN增拥;初值L=RN表示最多允許RN個讀者同時(shí)讀
Swait(L,1,1)與Ssignal(L,1)負(fù)責(zé)讀者的人數(shù)限制工作
Swait(mx,1,0)負(fù)責(zé)實(shí)現(xiàn)讀與寫互斥(申請到mx至少為1即目前無寫者)
Swait(mx,1,1;L,RN,0)負(fù)責(zé)寫與寫啄巧、寫與讀互斥(該語句表示僅當(dāng)無writer在寫又無reader在讀才通過)
寫者最后要Ssignal(mx,1)釋放資源
讀者-寫者問題2(在1的基礎(chǔ)上加上寫者的優(yōu)先級):
在讀者-寫者問題1中的記錄型解決方案中寻歧,
讀者訪問開始后要等到其后續(xù)的所有讀者訪問完才能釋放資源給寫者掌栅,
若讀者源源不斷進(jìn)入會導(dǎo)致寫者遲遲不能訪問臨界資源的情況出現(xiàn),
現(xiàn)在要求寫者排隊(duì)要訪問臨界資源時(shí)后續(xù)的讀者不能“插隊(duì)”码泛,
就好像給寫者加上一定的“優(yōu)先級”(其實(shí)算不上優(yōu)先級猾封,只是確保多并發(fā)過程中不被插隊(duì)而已)
做法:
在問題1的基礎(chǔ)上再設(shè)置信號量S
對于讀者,在第一次對rmutex的PV操作外加一層對S的PV操作(貼合的一層)
對于寫者噪珊,在對wmutex的PV操作外加一層對S的PV操作(貼合的一層)
解釋:
這樣當(dāng)前一批讀者都進(jìn)行完第一次對rmutex的PV操作后晌缘,讓出空閑的S給某個寫者去P
當(dāng)前一批讀者繼續(xù)后面的資源訪問時(shí),后一批讀/寫者會由于第一次PV操作中P不到S而等待(S給某個寫者P掉了)
最后當(dāng)前一批讀者都訪問完資源后V出wmutex痢站,寫者再去P掉wmutex開始訪問臨界資源(此前一直在等待wmutex)
當(dāng)寫者訪問完臨界資源后磷箕,V出S和wmutex,后一批讀/寫者才能有機(jī)會訪問臨界區(qū)
還有關(guān)于寫者的絕對優(yōu)先級問題阵难,即當(dāng)寫者需要訪問臨界資源時(shí)其它的所有讀者都要停下它們當(dāng)前的進(jìn)程(無論執(zhí)行哪一步)
這個問題的解法略
2.6進(jìn)程通信
進(jìn)程通信:進(jìn)程間的信息交換
進(jìn)程的互斥與同步是低級進(jìn)程通信:效率低岳枷、通信對用戶不透明
高級進(jìn)程通信:效率高、通信對用戶透明
進(jìn)程通信的四個類型:共享存儲器系統(tǒng)呜叫、管道通信系統(tǒng)空繁、消息傳遞系統(tǒng)、客戶-服務(wù)器系統(tǒng)
- 共享存儲器系統(tǒng):
基于共享存儲數(shù)據(jù)結(jié)構(gòu)的通信方式:就像生產(chǎn)者消費(fèi)者中的緩存區(qū)朱庆,系統(tǒng)只提供了一共享存儲器盛泡,使用于少量通信(低效、不透明)
基于共享存儲區(qū)的通信方式:系統(tǒng)提供了共享存儲區(qū)娱颊,通信時(shí)向系統(tǒng)申請分區(qū)再進(jìn)行讀寫(高效傲诵、速度快) - 管道通信系統(tǒng):
管道:連接一個讀進(jìn)程和一個寫進(jìn)程之間通信的共享文件
功能:大量的數(shù)據(jù)發(fā)收
提供三方面的協(xié)調(diào)能力:同步凯砍、互斥、確定對方是否存在 - 消息傳遞系統(tǒng)(目前的主要通信方式):
信息單位:報(bào)文
分為兩類:直接通信方式拴竹、間接通信方式
特點(diǎn):具有透明性果覆、屬于高級通信方式 - 客戶機(jī)-服務(wù)器系統(tǒng):
當(dāng)前網(wǎng)絡(luò)環(huán)境的主流通信方式
三種實(shí)現(xiàn)方法:嵌套字、遠(yuǎn)程過程調(diào)用殖熟、遠(yuǎn)程方法調(diào)用
消息傳遞通信的實(shí)現(xiàn)方式:
- 直接傳遞系統(tǒng)
原語:send(receiver, message);
receive(sender, message);
消息格式:消息頭(含控制信息)局待、消息內(nèi)容、定長消息菱属、變長消息
進(jìn)程同步方式:發(fā)送接收進(jìn)程阻塞钳榨、發(fā)送不阻接收阻、發(fā)送接收都不阻塞
通信鏈路:顯式建立(進(jìn)程做)纽门、隱式建立(系統(tǒng)做)
鏈路類型:點(diǎn)對點(diǎn)鏈路和多點(diǎn)鏈路(連接方式)薛耻、單/雙向(通信方式)、有/無容量(容量) - 間接傳遞系統(tǒng)(信箱通信)
原語:Send(mailbox, message);
Receive(mailbox, message);
信息的創(chuàng)建與撤銷:信箱名+屬性(信箱類型)+共享者名字
信箱類型:公赏陵、私饼齿、共享
發(fā)送-接收進(jìn)程間的關(guān)系:一對一、一對多蝙搔、多對一缕溉、多對多
優(yōu)點(diǎn):讀/寫時(shí)間上的隨機(jī)性
消息傳遞系統(tǒng)實(shí)例:
數(shù)據(jù)結(jié)構(gòu):
//消息緩沖區(qū)
typedef struct message_buffer{
int sender; //發(fā)送者進(jìn)程標(biāo)識符
int size; //消息長度
int *text; //消息正文
struct message_buffer *next; //指向下一個消息緩沖區(qū)的指針
}
//PCB有關(guān)數(shù)據(jù)項(xiàng)
typedef struct processcontrol_block{
...
struct message_buffer *mq; //消息隊(duì)列首地址
semaphore mutex; //消息隊(duì)列互斥信號量
semaphore sm; //消息隊(duì)列資源信號量
...
}PCB;
*原語部分
//發(fā)送原語
void send(receiver, a){ //receiver為接受進(jìn)程標(biāo)識符,a為發(fā)送區(qū)首址
getbuf(a.size, i); //根據(jù)a.size申請緩沖區(qū)
i.sender = a.sender;
i.size = a.size;
copy(i.text, a.text); //將發(fā)送區(qū)a中的信息復(fù)制到消息緩沖區(qū)i中
i.next = 0;
getid(PCBset, receiver.j); //獲得接收進(jìn)程內(nèi)部的標(biāo)識符
wait(j.mutex);
insert(&j.mq, i); //將消息緩沖區(qū)插入消息隊(duì)列
signal(j.mutex);
signal(j.sm);
}
//接收原語
void receive(b){
j = internal name; //j為接收進(jìn)程內(nèi)部的標(biāo)識符
wait(j.sm);
wait(j.mutex);
remove(j.mq, i); //將消息隊(duì)列中第一個消息移出
signal(j.mutex);
b.sender = i.sender;
b.size = i.size;
copy(b.text, i.text); //將消息緩沖區(qū)i中的信息復(fù)制到接收區(qū)b
releasebuf(i); //釋放消息緩沖區(qū)
}
2.7線程的基本概念
引入線程吃型,進(jìn)程是資源分配獨(dú)立單位证鸥,線程是系統(tǒng)獨(dú)立調(diào)度和分派的基本單位
線程的實(shí)現(xiàn):
用戶級線程不依賴內(nèi)核,內(nèi)核級線程依賴內(nèi)核
切換速度:用戶級線程>內(nèi)核級線程>進(jìn)程
后略