第9章：同步互斥
背景
現(xiàn)實生活中的同步問題
臨界區(qū)
方法1：禁用硬件中斷
方法2：基于軟件的解決方法
方法3：更高級的抽象方法
9.1 背景
同步互斥是操作系統(tǒng)當(dāng)中協(xié)調(diào)進程之間動作和相互關(guān)系的一種機制酿傍。
并發(fā)進程的正確性
- 獨立進程：
不和其他進程共享資源或狀態(tài)
確定性–輸入狀態(tài)決定結(jié)果
可重現(xiàn)–能夠重現(xiàn)起始條件
調(diào)度順序不重要 - 并發(fā)進程：
在多個進程間共享資源
不確定性
不可重現(xiàn) - 并發(fā)進程的正確性：
執(zhí)行進程是不確定性和不可重現(xiàn)的
程序錯誤可能是間歇性發(fā)生的 - 進程并發(fā)執(zhí)行的好處
進程需要與計算機中的其他進程和設(shè)備進行協(xié)作
好處1：共享資源
好處2：加速
I/O操作和CPU計算可以重疊（并行）
程序可劃分成多個模塊放在多個處理器上并行執(zhí)行
好處3：模塊化
將大程序分解成小程序
使系統(tǒng)易于復(fù)用和擴展
并發(fā)創(chuàng)建新進程時的標識分配
- 程序可以調(diào)用函數(shù)fork()來創(chuàng)建一個新的進程
操作系統(tǒng)需要分配一個新的并且唯一的進程ID
在內(nèi)核中沮协，這個系統(tǒng)調(diào)用會運行 new_pid = next_pid++
翻譯成機器指令
兩個進程并發(fā)執(zhí)行時的預(yù)期結(jié)果（假定是 next_pid = 100）
一個進程得到的ID應(yīng)該是100
另一個進程的ID應(yīng)該是101
next_pid應(yīng)該增加到102 - 新進程標識中的可能錯誤：
兩個不同的新進程分配了一樣的new_pid簇秒，且next_pid只增加了1
原子操作（Atomic Operation）
defs：原子操作是指一次不存在任何中斷或失敗的操作
要么操作成功完成
要么操作沒有執(zhí)行
不會出現(xiàn)部分執(zhí)行的狀態(tài)
操作系統(tǒng)需要利用同步機制在并發(fā)執(zhí)行的同時挎塌，保證一些操作是原子操作
9.2 現(xiàn)實生活中的同步問題
- 互斥（mutual exclusion）
一個進程占用資源支竹，其他進程不能使用，必須等待適應(yīng)資源的進程釋放 - 死鎖（deadlock）
多個進程各占用部分資源，形成循環(huán)等待 - 饑餓（starvation）
其他進程可能輪流占用資源，一個進程一直得不到資源 -
進程的交互關(guān)系：相互感知程度
9.3 臨界區(qū)（critical section）
- 臨界區(qū)（critical section）
進程訪問臨界資源的一段需要互斥執(zhí)行的代碼 - 進入?yún)^(qū)（entry section）
檢查可否進入臨界區(qū)的一段代碼
如可進入栽燕，設(shè)置相應(yīng)“正在訪問臨界區(qū)”標志 - 退出區(qū)（exit section）
清除“正在訪問臨界區(qū)”狀態(tài) - 剩余區(qū)（remainder section）
代碼中的其余部分 - 臨界區(qū)訪問規(guī)則
- 空閑則入：
沒有進程在臨界區(qū)時，任何進程可進入 - 忙則等待：
有進程在臨界區(qū)時，其他進程均不能進入臨界區(qū) - 有限等待：
等待進入臨界區(qū)的進程不能無限等待 - 讓權(quán)等待（可選）：
不能進入臨界區(qū)的進程應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）
臨界區(qū)的實現(xiàn)方法
- 禁用中斷
- 軟件方法
- 更高級的抽象方法
禁用中斷
- 其他進程無法打擾正在運行的進程碍岔，當(dāng)前進程對臨界區(qū)資源的訪問也就不會有問題浴讯。但對系統(tǒng)的中斷響應(yīng)會有影響。
- 在硬件還沒有支持的時候付秕，嘗試用共享變量協(xié)調(diào)的方式來做兰珍，比較復(fù)雜
- 借用操作系統(tǒng)的支持，來使應(yīng)用提供同步的服務(wù)询吴。由于引入管理者，進程間不對等協(xié)調(diào)
9.4 禁用硬件中斷
- 沒有中斷亮元，沒有上下文切換猛计，因此沒有并發(fā)，整個系統(tǒng)由當(dāng)前進程獨占
硬件將中斷處理延遲到中斷被啟用之后
現(xiàn)代計算機體系結(jié)構(gòu)都提供指令來實現(xiàn)禁用中斷
進入臨界區(qū)
禁止所有中斷爆捞，并保存標志
離開臨界區(qū)
使能所有中斷奉瘤，并恢復(fù)標志 - 缺點
禁用中斷中，進程無法被停止
如果進程執(zhí)行出了問題煮甥，那整個系統(tǒng)都沒有辦法回來
整個系統(tǒng)都會為此停下來
可能導(dǎo)致其他進程處于饑餓狀態(tài)
臨界區(qū)可能很長
無法確定響應(yīng)中斷所需的時間（可能存在硬件影響）
要小心使用
9.5 基于軟件的同步方法
在兩個進程之間盗温，通過共享變量的訪問，來實現(xiàn)線程之間的同步
線程可通過共享一些共有變量之間來同步它們的行為
- 第一次嘗試
共享變量
int turn = 0
turn == i//表示允許進入臨界區(qū)的線程
1
2
線程Ti的代碼
do {
while (turn != i);//條件不成立就可以進入臨界區(qū)
critical section
trun = j;
remainder section
} while (1);
1
2
3
4
5
6
若turn不是i成肘，則相當(dāng)于我本身是i卖局。允許另外一個線程進入臨界區(qū)，i不允許進入臨界區(qū)双霍，這時它就一直等待砚偶，等待另一個線程把它改成i
當(dāng)turn變成i之后，它能進去執(zhí)行臨界區(qū)的代碼洒闸，執(zhí)行完畢退出后染坯，在退出區(qū)，它把turn改成j丘逸，也就是另一個線程的ID
滿足“忙則等待”单鹿，但是有時不滿足“空閑則入”
Ti不在臨界區(qū)，Tj想要繼續(xù)運行深纲，但是必須等待Ti進入臨界區(qū)后
- 第二次嘗試
共享變量
int flag[2];
flag[0] = flag[1] = 0;
flag[i] == 1;//表示線程Ti是否在臨界區(qū)
1
2
3
線程Ti的代碼
do {
while (flag[j] == 1);
flag[i] = 1;
critical section
flag[i] = 0;
remainder section
} while (1);
1
2
3
4
5
6
7
如果flag[j]不是1仲锄，則另一個線程不在臨界區(qū)，這時把自己的標識改成1囤萤，進入臨界區(qū)昼窗，出來了把自己的標識置為0
不滿足“忙則等待”
- 第三次嘗試
共享變量
int flag[2];
flag[0] = flag[1] = 0;
flag[i] == 1;//表示線程Ti想要進入臨界區(qū)
1
2
3
線程Ti的代碼
do {
flag[i] = 1;
while (flag[j] == 1);
critical section
flag[i] = 0;
remainder section
} whlie (1);
1
2
3
4
5
6
7
滿足“忙則等待”，但是不滿足“空閑則入”
Peterson算法
滿足線程Ti和Tj之間互斥的基于軟件的解決方法
共享變量
int turn;
boolean flag[];//表示進程是否準備好進入臨界區(qū)
1
2
進入?yún)^(qū)代碼
flag[i] = true;
turn = j;
while (flag[j] && turn ==j) //兩個條件只要一個不滿足就能進去
1
2
3
退出區(qū)代碼
flag[i] = false;
1
線程Ti的代碼
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = false;
remainder section
} while (1);
1
2
3
4
5
6
7
8
Dekkers算法
線程Ti的代碼
flag[0] := false;
flag[1] := false;
turn := 0;//orl
do {
flag[i] = true;
while flag[j] == true {
if turn != i {
flag[i] := false
while turn != i{}
flag[i] := true
}
}
critical section
turn := j
flag[i] = false;
remainder section
} while (true);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N線程的軟件方法（Eisenberg 和 McGuire）
特點：
- 復(fù)雜：
需要兩個進程間的共享數(shù)據(jù)項
需要忙等待
浪費CPU時間
9.6 更高級的抽象方法
- 硬件提供了一些同步原語
中斷禁用涛舍，院子操作指令等 - 操作系統(tǒng)提供更高級的編程抽象來簡化進程同步
例如：鎖澄惊、信號量
用硬件原語來構(gòu)建
鎖（lock）
鎖是一個抽象的數(shù)據(jù)結(jié)構(gòu)
- 一個二進制變量（鎖定/解鎖）
Lock :: Acquire() - 鎖被釋放前一直等待，然后得到鎖
Lock :: Release()
釋放鎖，喚醒任何等待的進程
使用鎖來控制臨界區(qū)訪問
lock_next_pid -> Acquire();
new_pid = next_pid++;
lock_next_pid -> Release();
1
2
3
原子操作指令
- 現(xiàn)代CPU體系結(jié)構(gòu)都提供一些特殊的原子操作指令
測試和置位（Test-and-Set）指令
從內(nèi)存單元中讀取值
測試該值是否為1（然后返回真或假）
內(nèi)存單元值設(shè)置為1 - 交換指令（exchange）
交換內(nèi)存中的兩個值
使用TS指令實現(xiàn)自旋鎖（spinlock）
class Lock {
int value = 0;//初始化鎖里的初值為0
}
Lock :: Acquire() {
while （test-and-set（value））;//spin
//構(gòu)造它的請求操作原語掸驱，即用TS指令去把value的值讀出來肛搬，并且往里寫1。
//如果是1毕贼，則這個操作就相當(dāng)于是個檢查温赔，如果是0，則設(shè)為1鬼癣，循環(huán)結(jié)束陶贼。
}
1
2
3
4
5
6
7
8
如果鎖被釋放，那么TS指令讀取0并將值設(shè)置1
鎖被設(shè)置為忙并且需要等待完成
如果鎖處于忙狀態(tài)待秃，那么TS指令讀取1并將值設(shè)置為1不改變鎖的狀態(tài)并且需要循環(huán)
Lock :: Release() {
value = 0;
}
1
2
3
- 特點：
線程在等待的時候消耗CPU時間
無忙等待鎖
- 忙等待
Lock :: Acquire() {
while （test-and-set（value））;//spin
}
Lock :: Release() {
value = 0;
}
1
2
3
4
5
6
- 無忙等待
class Lock {
int value = 0;
WaitQueue q;//在鎖的數(shù)據(jù)結(jié)構(gòu)里加上一個等待隊列拜秧，即等待這個鎖的相應(yīng)的進程所排的隊列
}
Lock :: Acquire() {
while （test-and-set（value））;{
and this TCB to wait queue q;
schedule();
}
}
1
2
3
4
5
6
7
8
9
10
11
若查詢一次之后，里面是1章郁，就將當(dāng)前線程放到等待隊列枉氮，同時執(zhí)行調(diào)度程序，此時其他程序可以繼續(xù)執(zhí)行
一旦切換回來暖庄，輪到該線程再運行時聊替，即有釋放鎖操作，將該線程從等待狀態(tài)變成就緒狀態(tài)培廓，此時再去查惹悄，若此時它的狀態(tài)是解鎖的狀態(tài)，則請求完成医舆，進入臨界區(qū)
Lock :: Release() {
value = 0;//表示釋放鎖
remove one thread t from q;
wakeup(t);//將線程從等待隊列放到就緒隊列俘侠。等待時，就處于放棄CPU使用權(quán)的狀態(tài)蔬将，實現(xiàn)了讓權(quán)等待
}
1
2
3
4
5
原子操作指令鎖的特征
- 優(yōu)點
運用于單處理器或者共享主存的多處理器中任意數(shù)量的進程同步
中斷禁用只適用于單處理機
簡單并且容易證明
支持多臨界區(qū) - 缺點
忙等待消耗處理器時間
可能導(dǎo)致饑餓
進程離開臨界區(qū)時有多個等待進程的情況
并沒有做到按先來后到的順序來使用資源爷速，因為在鎖的請求操作當(dāng)中，放到就緒隊列之后會再去檢查霞怀。若在檢查的時候資源出于空閑狀態(tài)惫东，那就申請到了”惺回來的時候廉沮，實際上各個線程把就緒隊列排定的順序并不見得是申請鎖的順序
擁有臨界區(qū)的低優(yōu)先級進程
請求訪問臨界區(qū)的高優(yōu)先級進程獲得處理器并等待臨界區(qū)
低優(yōu)先級等待CPU，高優(yōu)先級等待臨界區(qū)資源
同步方法總結(jié)
- 鎖是一種高級的同步抽象方法
互斥可使用鎖來實現(xiàn)
需要硬件支持 - 常用的三種同步實現(xiàn)方法
禁用中斷（僅限于單處理器）
軟件方法（復(fù)雜）
原子操作指令（單處理器或多處理器均可）
