第9章：同步互斥

背景
現(xiàn)實(shí)生活中的同步問(wèn)題
臨界區(qū)
方法1：禁用硬件中斷
方法2：基于軟件的解決方法
方法3：更高級(jí)的抽象方法

9.1 背景

同步互斥是操作系統(tǒng)當(dāng)中協(xié)調(diào)進(jìn)程之間動(dòng)作和相互關(guān)系的一種機(jī)制。

并發(fā)進(jìn)程的正確性

• 獨(dú)立進(jìn)程：
  不和其他進(jìn)程共享資源或狀態(tài)
  確定性–輸入狀態(tài)決定結(jié)果
  可重現(xiàn)–能夠重現(xiàn)起始條件
  調(diào)度順序不重要
• 并發(fā)進(jìn)程：
  在多個(gè)進(jìn)程間共享資源
  不確定性
  不可重現(xiàn)
• 并發(fā)進(jìn)程的正確性：
  執(zhí)行進(jìn)程是不確定性和不可重現(xiàn)的
  程序錯(cuò)誤可能是間歇性發(fā)生的
• 進(jìn)程并發(fā)執(zhí)行的好處
  進(jìn)程需要與計(jì)算機(jī)中的其他進(jìn)程和設(shè)備進(jìn)行協(xié)作
  好處1：共享資源
  好處2：加速
  I/O操作和CPU計(jì)算可以重疊（并行）
  程序可劃分成多個(gè)模塊放在多個(gè)處理器上并行執(zhí)行
  好處3：模塊化
  將大程序分解成小程序
  使系統(tǒng)易于復(fù)用和擴(kuò)展

并發(fā)創(chuàng)建新進(jìn)程時(shí)的標(biāo)識(shí)分配

• 程序可以調(diào)用函數(shù)fork()來(lái)創(chuàng)建一個(gè)新的進(jìn)程
  操作系統(tǒng)需要分配一個(gè)新的并且唯一的進(jìn)程ID
  在內(nèi)核中，這個(gè)系統(tǒng)調(diào)用會(huì)運(yùn)行 new_pid = next_pid++
  翻譯成機(jī)器指令
  兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)的預(yù)期結(jié)果（假定是 next_pid = 100）
  一個(gè)進(jìn)程得到的ID應(yīng)該是100
  另一個(gè)進(jìn)程的ID應(yīng)該是101
  next_pid應(yīng)該增加到102
• 新進(jìn)程標(biāo)識(shí)中的可能錯(cuò)誤：
  兩個(gè)不同的新進(jìn)程分配了一樣的new_pid，且next_pid只增加了1

原子操作（Atomic Operation）

defs：原子操作是指一次不存在任何中斷或失敗的操作
要么操作成功完成
要么操作沒(méi)有執(zhí)行
不會(huì)出現(xiàn)部分執(zhí)行的狀態(tài)
操作系統(tǒng)需要利用同步機(jī)制在并發(fā)執(zhí)行的同時(shí)，保證一些操作是原子操作

9.2 現(xiàn)實(shí)生活中的同步問(wèn)題

• 互斥（mutual exclusion）
  一個(gè)進(jìn)程占用資源，其他進(jìn)程不能使用，必須等待適應(yīng)資源的進(jìn)程釋放
• 死鎖（deadlock）
  多個(gè)進(jìn)程各占用部分資源，形成循環(huán)等待
• 饑餓（starvation）
  其他進(jìn)程可能輪流占用資源，一個(gè)進(jìn)程一直得不到資源

• 進(jìn)程的交互關(guān)系：相互感知程度

  
  

9.3 臨界區(qū)（critical section）

• 臨界區(qū)（critical section）
  進(jìn)程訪問(wèn)臨界資源的一段需要互斥執(zhí)行的代碼
• 進(jìn)入?yún)^(qū)（entry section）
  檢查可否進(jìn)入臨界區(qū)的一段代碼
  如可進(jìn)入，設(shè)置相應(yīng)“正在訪問(wèn)臨界區(qū)”標(biāo)志
• 退出區(qū)（exit section）
  清除“正在訪問(wèn)臨界區(qū)”狀態(tài)
• 剩余區(qū)（remainder section）
  代碼中的其余部分
• 臨界區(qū)訪問(wèn)規(guī)則

1. 空閑則入：
   沒(méi)有進(jìn)程在臨界區(qū)時(shí)，任何進(jìn)程可進(jìn)入
2. 忙則等待：
   有進(jìn)程在臨界區(qū)時(shí)，其他進(jìn)程均不能進(jìn)入臨界區(qū)
3. 有限等待：
   等待進(jìn)入臨界區(qū)的進(jìn)程不能無(wú)限等待
4. 讓權(quán)等待（可選）：
   不能進(jìn)入臨界區(qū)的進(jìn)程應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）

臨界區(qū)的實(shí)現(xiàn)方法

1. 禁用中斷
2. 軟件方法
3. 更高級(jí)的抽象方法

禁用中斷

• 其他進(jìn)程無(wú)法打擾正在運(yùn)行的進(jìn)程，當(dāng)前進(jìn)程對(duì)臨界區(qū)資源的訪問(wèn)也就不會(huì)有問(wèn)題。但對(duì)系統(tǒng)的中斷響應(yīng)會(huì)有影響。
• 在硬件還沒(méi)有支持的時(shí)候，嘗試用共享變量協(xié)調(diào)的方式來(lái)做，比較復(fù)雜
• 借用操作系統(tǒng)的支持，來(lái)使應(yīng)用提供同步的服務(wù)。由于引入管理者，進(jìn)程間不對(duì)等協(xié)調(diào)

9.4 禁用硬件中斷

• 沒(méi)有中斷，沒(méi)有上下文切換，因此沒(méi)有并發(fā)，整個(gè)系統(tǒng)由當(dāng)前進(jìn)程獨(dú)占
  硬件將中斷處理延遲到中斷被啟用之后
  現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)都提供指令來(lái)實(shí)現(xiàn)禁用中斷
  進(jìn)入臨界區(qū)
  禁止所有中斷，并保存標(biāo)志
  離開臨界區(qū)
  使能所有中斷，并恢復(fù)標(biāo)志
• 缺點(diǎn)
  禁用中斷中，進(jìn)程無(wú)法被停止
  如果進(jìn)程執(zhí)行出了問(wèn)題，那整個(gè)系統(tǒng)都沒(méi)有辦法回來(lái)
  整個(gè)系統(tǒng)都會(huì)為此停下來(lái)
  可能導(dǎo)致其他進(jìn)程處于饑餓狀態(tài)
  臨界區(qū)可能很長(zhǎng)
  無(wú)法確定響應(yīng)中斷所需的時(shí)間（可能存在硬件影響）
  要小心使用

9.5 基于軟件的同步方法

在兩個(gè)進(jìn)程之間，通過(guò)共享變量的訪問(wèn)，來(lái)實(shí)現(xiàn)線程之間的同步
線程可通過(guò)共享一些共有變量之間來(lái)同步它們的行為

• 第一次嘗試
  共享變量

int turn = 0
turn == i//表示允許進(jìn)入臨界區(qū)的線程 
1
2
線程Ti的代碼
do {
    while (turn != i);//條件不成立就可以進(jìn)入臨界區(qū)
    critical section
    trun = j;
    remainder section
}  while (1);
1
2
3
4
5
6

若turn不是i，則相當(dāng)于我本身是i。允許另外一個(gè)線程進(jìn)入臨界區(qū)，i不允許進(jìn)入臨界區(qū)，這時(shí)它就一直等待，等待另一個(gè)線程把它改成i
當(dāng)turn變成i之后，它能進(jìn)去執(zhí)行臨界區(qū)的代碼，執(zhí)行完畢退出后，在退出區(qū)，它把turn改成j，也就是另一個(gè)線程的ID
滿足“忙則等待”，但是有時(shí)不滿足“空閑則入”
Ti不在臨界區(qū)，Tj想要繼續(xù)運(yùn)行，但是必須等待Ti進(jìn)入臨界區(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，則另一個(gè)線程不在臨界區(qū)，這時(shí)把自己的標(biāo)識(shí)改成1，進(jìn)入臨界區(qū)，出來(lái)了把自己的標(biāo)識(shí)置為0
不滿足“忙則等待”

• 第三次嘗試
  共享變量

int flag[2];
flag[0] = flag[1] = 0;
flag[i] == 1;//表示線程Ti想要進(jìn)入臨界區(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[];//表示進(jìn)程是否準(zhǔn)備好進(jìn)入臨界區(qū)
1
2
進(jìn)入?yún)^(qū)代碼
flag[i] = true;
turn = j;
while (flag[j] && turn ==j) //兩個(gè)條件只要一個(gè)不滿足就能進(jìn)去
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）

特點(diǎn)：

• 復(fù)雜：
  需要兩個(gè)進(jìn)程間的共享數(shù)據(jù)項(xiàng)
  需要忙等待
  浪費(fèi)CPU時(shí)間

9.6 更高級(jí)的抽象方法

• 硬件提供了一些同步原語(yǔ)
  中斷禁用，院子操作指令等
• 操作系統(tǒng)提供更高級(jí)的編程抽象來(lái)簡(jiǎn)化進(jìn)程同步
  例如：鎖、信號(hào)量
  用硬件原語(yǔ)來(lái)構(gòu)建

鎖（lock）

鎖是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu)

• 一個(gè)二進(jìn)制變量（鎖定/解鎖）
  Lock :: Acquire()
• 鎖被釋放前一直等待，然后得到鎖
  Lock :: Release()
  釋放鎖，喚醒任何等待的進(jìn)程

使用鎖來(lái)控制臨界區(qū)訪問(wèn)

lock_next_pid -> Acquire();
new_pid = next_pid++;
lock_next_pid -> Release();
1
2
3

原子操作指令

• 現(xiàn)代CPU體系結(jié)構(gòu)都提供一些特殊的原子操作指令
  測(cè)試和置位（Test-and-Set）指令
  從內(nèi)存單元中讀取值
  測(cè)試該值是否為1（然后返回真或假）
  內(nèi)存單元值設(shè)置為1
• 交換指令（exchange）
  交換內(nèi)存中的兩個(gè)值

使用TS指令實(shí)現(xiàn)自旋鎖（spinlock）

class Lock {
    int value = 0;//初始化鎖里的初值為0
}
Lock :: Acquire() {
    while （test-and-set（value））;//spin
    //構(gòu)造它的請(qǐng)求操作原語(yǔ)，即用TS指令去把value的值讀出來(lái)，并且往里寫1。
    //如果是1，則這個(gè)操作就相當(dāng)于是個(gè)檢查，如果是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

• 特點(diǎn)：
  線程在等待的時(shí)候消耗CPU時(shí)間

無(wú)忙等待鎖

• 忙等待

Lock :: Acquire() {
    while （test-and-set（value））;//spin
}
Lock :: Release() {
    value = 0;
}
1
2
3
4
5
6

• 無(wú)忙等待

class Lock {
    int value = 0;
    WaitQueue q;//在鎖的數(shù)據(jù)結(jié)構(gòu)里加上一個(gè)等待隊(duì)列，即等待這個(gè)鎖的相應(yīng)的進(jìn)程所排的隊(duì)列
}
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)前線程放到等待隊(duì)列，同時(shí)執(zhí)行調(diào)度程序，此時(shí)其他程序可以繼續(xù)執(zhí)行
一旦切換回來(lái)，輪到該線程再運(yùn)行時(shí)，即有釋放鎖操作，將該線程從等待狀態(tài)變成就緒狀態(tài)，此時(shí)再去查，若此時(shí)它的狀態(tài)是解鎖的狀態(tài)，則請(qǐng)求完成，進(jìn)入臨界區(qū)

Lock :: Release() {
    value = 0;//表示釋放鎖
    remove one thread t from q;
    wakeup(t);//將線程從等待隊(duì)列放到就緒隊(duì)列。等待時(shí)，就處于放棄CPU使用權(quán)的狀態(tài)，實(shí)現(xiàn)了讓權(quán)等待
}
1
2
3
4
5

原子操作指令鎖的特征

• 優(yōu)點(diǎn)
  運(yùn)用于單處理器或者共享主存的多處理器中任意數(shù)量的進(jìn)程同步
  中斷禁用只適用于單處理機(jī)
  簡(jiǎn)單并且容易證明
  支持多臨界區(qū)
• 缺點(diǎn)
  忙等待消耗處理器時(shí)間
  可能導(dǎo)致饑餓
  進(jìn)程離開臨界區(qū)時(shí)有多個(gè)等待進(jìn)程的情況
  并沒(méi)有做到按先來(lái)后到的順序來(lái)使用資源，因?yàn)樵阪i的請(qǐng)求操作當(dāng)中，放到就緒隊(duì)列之后會(huì)再去檢查。若在檢查的時(shí)候資源出于空閑狀態(tài)，那就申請(qǐng)到了?；貋?lái)的時(shí)候，實(shí)際上各個(gè)線程把就緒隊(duì)列排定的順序并不見得是申請(qǐng)鎖的順序
  擁有臨界區(qū)的低優(yōu)先級(jí)進(jìn)程
  請(qǐng)求訪問(wèn)臨界區(qū)的高優(yōu)先級(jí)進(jìn)程獲得處理器并等待臨界區(qū)
  低優(yōu)先級(jí)等待CPU，高優(yōu)先級(jí)等待臨界區(qū)資源

同步方法總結(jié)

• 鎖是一種高級(jí)的同步抽象方法
  互斥可使用鎖來(lái)實(shí)現(xiàn)
  需要硬件支持
• 常用的三種同步實(shí)現(xiàn)方法
  禁用中斷（僅限于單處理器）
  軟件方法（復(fù)雜）
  原子操作指令（單處理器或多處理器均可）