術(shù)語
- 進(jìn)度圖 進(jìn)度圖是將 n 個(gè)并發(fā)進(jìn)程的執(zhí)行模型化為一條 n 維笛卡爾空間中的軌跡線魄衅，每條軸 k 對(duì)應(yīng)于線程 k 的進(jìn)度峭竣，每個(gè)進(jìn)度對(duì)應(yīng)一條指令。
- 臨界區(qū) 某個(gè)線程操作共享變量 cnt 內(nèi)容的一串指令
- 不安全區(qū) 兩個(gè)臨界區(qū)的交集形成的狀態(tài)空間區(qū)域稱為不安全區(qū)
- 安全軌跡區(qū) 繞開不安全區(qū)的軌跡線
-
信號(hào)量 是一個(gè)具有非負(fù)整數(shù)值的全局變量晃虫，只能由兩種特殊的操作 P(s)（測(cè)試減一） 和 V(s)（增加加一） 來處理皆撩，這兩個(gè)操作都是原子的，不可分割的
臨界區(qū)與安全軌跡線
為了保證線程化程序的正確執(zhí)行（實(shí)際上是任何共享全局?jǐn)?shù)據(jù)結(jié)構(gòu)的冰法程序的正確執(zhí)行）我們必須以某種方式同步線程哲银，使它們總是有一條安全軌跡線扛吞，一個(gè)經(jīng)典的方法是基于信號(hào)量的思想。
使用信號(hào)量來實(shí)現(xiàn)互斥
基本思想是將每個(gè)共享變量與一個(gè)信號(hào)量 s(初始化為一個(gè)整數(shù) n) 聯(lián)系起來盘榨，然后用 P(s) 和 V(s) 操作將相應(yīng)的臨界區(qū)包圍起來喻粹。
s 的初始值決定了這個(gè)資源可以同時(shí)被 n 個(gè)進(jìn)程使用
n=1 時(shí)的信號(hào)量成為互斥鎖(mutex)，P(s) 和 V(s)相應(yīng)的成為加鎖和解鎖草巡，信號(hào)量操作確保了對(duì)臨界區(qū)的互斥訪問守呜。
使用信號(hào)量來調(diào)度共享資源
除了提供互斥之外，信號(hào)量的另外一個(gè)重要作用是用來調(diào)度對(duì)共享資源的訪問山憨，即一個(gè)線程用信號(hào)量來通知另一個(gè)線程查乒，線程狀態(tài)中的某個(gè)條件已經(jīng)為真了。
生產(chǎn)者-消費(fèi)者問題
生產(chǎn)者消費(fèi)者問題也稱為有限緩沖問題郁竟，是一個(gè)多線程同步問題的經(jīng)典案例玛迄。該問題描述了共享固定大小緩沖區(qū)的兩個(gè)線程——即所謂的“生產(chǎn)者”和“消費(fèi)者”——在實(shí)際運(yùn)行時(shí)會(huì)發(fā)生的問題。生產(chǎn)者的主要作用是生成一定量的數(shù)據(jù)放到緩沖區(qū)中棚亩，然后重復(fù)此過程蓖议。與此同時(shí)，消費(fèi)者也在緩沖區(qū)消耗這些數(shù)據(jù)讥蟆。該問題的關(guān)鍵就是要保證生產(chǎn)者不會(huì)在緩沖區(qū)滿時(shí)加入數(shù)據(jù)勒虾，消費(fèi)者也不會(huì)在緩沖區(qū)中空時(shí)消耗數(shù)據(jù)。
要解決該問題瘸彤，就必須讓生產(chǎn)者在緩沖區(qū)滿時(shí)休眠（要么干脆就放棄數(shù)據(jù)）捌归，等到下次消費(fèi)者消耗緩沖區(qū)中的數(shù)據(jù)的時(shí)候润梯，生產(chǎn)者才能被喚醒议经，開始往緩沖區(qū)添加數(shù)據(jù)。同樣玻靡，也可以讓消費(fèi)者在緩沖區(qū)空時(shí)進(jìn)入休眠，等到生產(chǎn)者往緩沖區(qū)添加數(shù)據(jù)之后中贝。
經(jīng)典進(jìn)程同步問題1：生產(chǎn)者-消費(fèi)者問題
semaphore mutex=1; //臨界區(qū)互斥信號(hào)量
semaphore empty=n; //空閑緩沖區(qū)
semaphore full=0; //緩沖區(qū)初始化為空
producer () { //生產(chǎn)者進(jìn)程
while(1){
produce an item in nextp; //生產(chǎn)數(shù)據(jù)
P(empty); //獲取空緩沖區(qū)單元
P(mutex); //進(jìn)入臨界區(qū).
add nextp to buffer; //將數(shù)據(jù)放入緩沖區(qū)
V(mutex); //離開臨界區(qū),釋放互斥信號(hào)量
V(full); //滿緩沖區(qū)數(shù)加1
}
}
consumer () { //消費(fèi)者進(jìn)程
while(1){
P(full); //獲取滿緩沖區(qū)單元
P(mutex); // 進(jìn)入臨界區(qū)
remove an item from buffer; //從緩沖區(qū)中取出數(shù)據(jù)
V (mutex); //離開臨界區(qū)囤捻，釋放互斥信號(hào)量
V (empty) ; //空緩沖區(qū)數(shù)加1
consume the item; //消費(fèi)數(shù)據(jù)
}
}
讀者寫者問題
有讀者和寫者兩組并發(fā)進(jìn)程，共享一個(gè)文件雄妥，當(dāng)兩個(gè)或以上的讀進(jìn)程同時(shí)訪問共享數(shù)據(jù)時(shí)不會(huì)產(chǎn)生副作用最蕾，但若某個(gè)寫進(jìn)程和其他進(jìn)程（讀進(jìn)程或?qū)戇M(jìn)程）同時(shí)訪問共享數(shù)據(jù)時(shí)則可能導(dǎo)致數(shù)據(jù)不一致的錯(cuò)誤依溯。因此要求：①允許多個(gè)讀者可以同時(shí)對(duì)文件執(zhí)行讀操作老厌；②只允許一個(gè)寫者往文件中寫信息；③任一寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ骼杪虎軐懻邎?zhí)行寫操作前枝秤，應(yīng)讓已有的讀者和寫者全部退出。
經(jīng)典進(jìn)程同步問題2：讀者-寫者問題
int count = 0; //用于記錄當(dāng)前的讀者數(shù)量
semaphore mutex = 1; //用于保護(hù)更新count變量時(shí)的互斥
semaphore rw=1; //用于保證讀者和寫者互斥地訪問文件
semaphore w=1; //用于實(shí)現(xiàn)“寫優(yōu)先”
writer(){
while(1){
P(w); //在無寫進(jìn)程請(qǐng)求時(shí)進(jìn)入
P(rw); //互斥訪問共享文件
writing; //寫入
V(rw); // 釋放共享文件
V(w) ; //恢復(fù)對(duì)共享支件的訪問
}
}
reader () { //讀者進(jìn)程
while (1){
P (w) ; // 在無寫進(jìn)程請(qǐng)求時(shí)進(jìn)入
P (mutex); // 互斥訪問count變量
if (count==0) //當(dāng)?shù)谝粋€(gè)讀進(jìn)程讀共享文件時(shí)
P(rw); //阻止寫進(jìn)程寫
count++; //讀者計(jì)數(shù)器加1
V (mutex) ; //釋放互斥變量count
V(w); //恢復(fù)對(duì)共享文件的訪問
reading; //讀取
P (mutex) ; //互斥訪問count變量
count--; //讀者計(jì)數(shù)器減1
if (count==0) //當(dāng)最后一個(gè)讀進(jìn)程讀完共享文件
V(rw); //允許寫進(jìn)程寫
V (mutex); //釋放互斥變量count
}
}
