在之前的課程中，我們已經(jīng)學(xué)習(xí)了進(jìn)程相關(guān)的知識(shí)。進(jìn)程是計(jì)算機(jī)程序被執(zhí)行的一個(gè)實(shí)例（instance）碟贾，一個(gè)進(jìn)程可能由一個(gè)或多個(gè)線程（thread）組成，同時(shí)執(zhí)行指令轨域。在這一章我們將學(xué)習(xí)線程的知識(shí)袱耽，包括如何寫一個(gè)多線程的程序，如何處理多線程引發(fā)的問題干发。

線程是啥朱巨？線程（thread） 的正式英語名稱是“thread of execution”。它代表一列有順序的枉长，需要 CPU執(zhí)行的指令冀续，可以隨時(shí)被內(nèi)核開始、中斷或繼續(xù)運(yùn)行必峰。
線程使用棧來記憶如何從函數(shù)中返回洪唐，以及存儲(chǔ)變量和參數(shù)等等。在多線程狀態(tài)下吼蚁，每個(gè)線程擁有一個(gè)自己的棧和程序計(jì)數(shù)?（PC）凭需，而堆，地址空間和全局變量則是多個(gè)線程共用的肝匆。每個(gè)線程對(duì)應(yīng)一個(gè)叫做** 線程控制塊（Thread Control Block粒蜈，TCB） **的數(shù)據(jù)結(jié)構(gòu)，里面存儲(chǔ)了這個(gè)線程的棧指針旗国、程序計(jì)數(shù)?枯怖、處理?狀態(tài)、線程標(biāo)識(shí)符（類似于進(jìn)程標(biāo)識(shí)符粗仓，是系統(tǒng)中唯一標(biāo)明這個(gè)線程的一個(gè)數(shù)字）等等嫁怀。

我們過去應(yīng)用多進(jìn)程是為了使得多個(gè)程序并發(fā)，改善資源利用效率借浊。但是各個(gè)進(jìn)程之間不共享內(nèi)存地址塘淑，給我們造成了許多不便。使用多線程則可以避免這些問題蚂斤。不同線程之間共享地址空間存捺，只是棧和程序計(jì)數(shù)器不同，因此兩個(gè)線程間通信也較為容易。更為重要的是捌治，在不同進(jìn)程間切換時(shí)岗钩，由于進(jìn)程地址空間不同，我們需要清空翻譯快表和基于邏輯地址的高速緩沖存儲(chǔ)器肖油，這一過程會(huì)使我們的程序運(yùn)行效率大打折扣兼吓；線程間切換就沒有這個(gè)問題，對(duì)于提高程序運(yùn)行效率大有裨益森枪。

當(dāng)然有得必有失视搏，下面這首小詩就表現(xiàn)出了多線程程序的問題：

一個(gè)程序員遇到了一個(gè)難題
她決定用多線程來解決
于是現(xiàn)在兩個(gè)問題了她有

本來詩的最后一句應(yīng)該是“于是現(xiàn)在她有了兩個(gè)問題”，但我們得到的結(jié)果卻是“于是現(xiàn)在兩個(gè)問題了她有”县袱。多線程經(jīng)常面臨的問題是多個(gè)線程的運(yùn)行順序是不確定的浑娜，且當(dāng)它們同時(shí)修改一個(gè)變量時(shí)我們最終得到的結(jié)果也是不確定的。為了控制多線程運(yùn)行的結(jié)果式散，我們將在這一章引入互斥和同步的概念筋遭，并介紹實(shí)現(xiàn)互斥和同步的方法。不過在開始介紹有關(guān)互斥和同步的概念以前暴拄，讓我們先來夯實(shí)基礎(chǔ)漓滔，學(xué)習(xí)線程的不同類型、Linux 對(duì)于線程的實(shí)現(xiàn)和 Linux Pthread 庫包含的函數(shù)乖篷。

不同系統(tǒng)中對(duì)于線程的實(shí)現(xiàn)主要分三種類型：

• 內(nèi)核級(jí)線程
• 用戶級(jí)線程
• 混合式線程

要強(qiáng)調(diào)一點(diǎn)次和，就是這里的內(nèi)核級(jí)和用戶級(jí)指的 并不是 線程的特權(quán)等級(jí)！一個(gè)用戶進(jìn)程建立的線程還是只有原來這個(gè)進(jìn)程的特權(quán)等級(jí)那伐，不能執(zhí)行只有內(nèi)核才能執(zhí)行的指令。用戶級(jí)和內(nèi)核級(jí)指的是這個(gè)線程是會(huì)被用戶進(jìn)程還是內(nèi)核調(diào)度石蔗。

我們雖然還沒有學(xué)到任務(wù)調(diào)度的算法罕邀，但我們已經(jīng)知道，系統(tǒng)會(huì)用某種方式調(diào)度不同的任務(wù)养距，使他們在處理器上交替運(yùn)行诉探，這個(gè)過程就是內(nèi)核對(duì)于任務(wù)的調(diào)度。一個(gè)內(nèi)核級(jí)的線程就將在系統(tǒng)中獲得被調(diào)度的權(quán)限棍厌，在這種情況下肾胯，如果一個(gè)進(jìn)程有兩個(gè)線程，那么這兩個(gè)線程會(huì)被獨(dú)立地調(diào)度耘纱，因此這個(gè)進(jìn)程占取的處理器時(shí)間就是這兩個(gè)線程占取的處理器時(shí)間之和敬肚。

在內(nèi)核級(jí)線程模型中，一個(gè)線程如果進(jìn)行 I/O 操作而被阻塞束析，那么這個(gè)進(jìn)程剩余的線程還可以繼續(xù)運(yùn)行艳馒，因此線程的狀態(tài)不等于進(jìn)程的狀態(tài)。同樣地，如果一個(gè)線程給自己的進(jìn)程發(fā)送 sleep 信號(hào)弄慰，這個(gè)線程依然可以繼續(xù)運(yùn)行第美。

與內(nèi)核級(jí)相對(duì)的用戶級(jí)線程就沒有這種權(quán)限了。

如果一個(gè)系統(tǒng)使用用戶級(jí)線程的模式陆爽，那么它就只會(huì)調(diào)度進(jìn)程什往，進(jìn)程內(nèi)部再自行調(diào)度線程。這就是說

• 屬于同一個(gè)進(jìn)程的兩個(gè)線程永遠(yuǎn)不會(huì)同時(shí)在兩個(gè)處理器上運(yùn)行慌闭；
• 進(jìn)程也不會(huì)因?yàn)槎喾殖隽藥讉€(gè)線程就獲得更多的處理器時(shí)間别威。

更糟糕的是，如果一個(gè)線程由于 I/O 或其它原因被阻塞贡必，那么整個(gè)進(jìn)程就都會(huì)被阻塞兔港；而在內(nèi)核級(jí)線程的模型中，一個(gè)線程被阻塞后其它線程還可以繼續(xù)運(yùn)行仔拟∩婪看到這里你可能會(huì)問，這種用戶級(jí)線程對(duì)于分出線程的進(jìn)程來講有什么好處呢利花？

相對(duì)于分出子進(jìn)程運(yùn)行同樣的內(nèi)容科侈，用戶級(jí)線程的優(yōu)勢是顯而易見的——多個(gè)線程間可以共享地址空間，減少通信帶來的麻煩炒事。
相對(duì)于內(nèi)核級(jí)線程來講臀栈，用戶級(jí)線程有兩個(gè)優(yōu)點(diǎn)。

• 一方面挠乳，它減少了線程間上下文切換的代價(jià)权薯。內(nèi)核級(jí)線程被系統(tǒng)調(diào)度，因此同一進(jìn)程中不同線程間的上下文切換也會(huì)導(dǎo)致用戶態(tài)向內(nèi)核態(tài)的轉(zhuǎn)換睡扬，這就包含了從一個(gè)用戶線程進(jìn)入內(nèi)核線程盟蚣，再進(jìn)入另一個(gè)用戶級(jí)線程的繁瑣過程。用戶級(jí)線程由于不涉及用戶態(tài)向內(nèi)核態(tài)的轉(zhuǎn)換卖怜，也就沒有這些缺點(diǎn)屎开。
• 另一方面，同一進(jìn)程不同用戶級(jí)線程間的調(diào)度完全由用戶進(jìn)程本身決定马靠，用戶進(jìn)程就可以用自己的調(diào)度算法選擇最優(yōu)的調(diào)度方法奄抽；內(nèi)核級(jí)線程在這方面就沒有這種優(yōu)勢——內(nèi)核對(duì)于用戶級(jí)進(jìn)程來講相當(dāng)于一個(gè)黑箱，我們無法知道里面運(yùn)行的是何種調(diào)度算法甩鳄，因此不能預(yù)測或控制它的效率逞度。

學(xué)完了內(nèi)核級(jí)線程和用戶級(jí)線程，你可能會(huì)問一個(gè)問題：有沒有一種線程的設(shè)計(jì)方法妙啃，能綜合內(nèi)核級(jí)線程和用戶級(jí)線程的優(yōu)點(diǎn)呢第晰？這就是混合式線程。在混合式線程中，用戶即可以建立用戶級(jí)線程茁瘦，也可以通過系統(tǒng)調(diào)用建立內(nèi)核級(jí)線程品抽。假設(shè)一個(gè)進(jìn)程建立了 N 個(gè)用戶級(jí)線程，M 個(gè)內(nèi)核級(jí)線程甜熔，那么 圆恤，且用戶可以自己調(diào)整用戶級(jí)進(jìn)程向內(nèi)核級(jí)線程的映射。這種方法使對(duì)應(yīng)著同一個(gè)內(nèi)核級(jí)線程的用戶級(jí)線程之間的切換更加高效腔稀，同時(shí)又使一個(gè)進(jìn)程能夠獲得更多處理器時(shí)間盆昙、不會(huì)被一個(gè)線程阻塞。

這種線程模型的缺點(diǎn)就在于它非常復(fù)雜焊虏、不利于實(shí)現(xiàn)淡喜。FreeBSD 和 NetBSD 兩個(gè)系統(tǒng)都曾經(jīng)使用過華盛頓大學(xué)在一篇論文中提出的混合式線程模型，但它們現(xiàn)在都已經(jīng)放棄了這種模型诵闭；大部分 Linux 系統(tǒng)中使用的也是較為簡單的內(nèi)核級(jí)線程模型炼团。在這一章中，可以假設(shè)我們所講的線程都是內(nèi)核級(jí)線程疏尿，而非用戶級(jí)線程瘟芝。

在命名線程模型時(shí),我們也可以用不同模型中內(nèi)核級(jí)線程和用戶級(jí)線程之間的對(duì)應(yīng)關(guān)系來區(qū)別這些模型。

• 內(nèi)核級(jí)線程模型中,由于每個(gè)線程都是一個(gè)可以被內(nèi)核調(diào)度的任務(wù),用戶級(jí)線程與內(nèi)核級(jí)線程的對(duì)應(yīng)關(guān)系是1:1的,我們就叫它1:1線程模型;
• 與之形成對(duì)比的是用戶級(jí)線程模型,在這種模型中一個(gè)進(jìn)程中的多個(gè)用戶級(jí)線程都被映射到一個(gè)可以調(diào)度的任務(wù)中因此用戶級(jí)線程與內(nèi)核級(jí)線程的對(duì)應(yīng)關(guān)系是N:1的,我們就叫它N:1模型;
• 最后,混合式線程模型中,一個(gè)進(jìn)程可以建立N個(gè)用戶級(jí)線程和M個(gè)內(nèi)核級(jí)線程,因此它就被稱為N:M模型褥琐。

練習(xí)：

競爭與互斥

上一節(jié)我們學(xué)習(xí)了如何寫一個(gè)簡單的多線程程序锌俱。多線程雖然方便快捷，但是問題也不少敌呈。在第一節(jié)的小詩中我們已經(jīng)見識(shí)到了多線程執(zhí)行順序的不確定性所帶來的問題贸宏；多線程程序還面臨著另一個(gè)問題：由于不同線程間共享內(nèi)存地址空間，一旦兩個(gè)線程同時(shí)試圖修改同一個(gè)地址磕洪，我們就面臨著 資源競爭（race condition）锚赤，而競爭的結(jié)果是不確定的。這一節(jié)我們來見識(shí)一下資源競爭帶來的問題褐鸥。

出于某種原因，你需要將一個(gè)整數(shù)從零逐個(gè)增加到一千萬赐稽。為了節(jié)約時(shí)間叫榕，我們將使用兩個(gè)線程分別增加這個(gè)整數(shù)。我們有如下代碼：

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

int *number;

void *adding(void *arg){
  for(int i = 0; i < 5000000; i++){
    (*(int *)arg)++;
  }
  return NULL;
}
void *adding(void *arg);
int main(){
  number = malloc(sizeof(int));
  pthread_t p[2];
  pthread_create(&p[0], 0, adding, number);
  pthread_create(&p[1], 0, adding, number);
  pthread_join(p[0], (void**)NULL);
  pthread_join(p[1], (void**)NULL);
  printf("%d\n", *number);
  return 0;
}

編譯執(zhí)行之后,我們的程序會(huì)在屏幕上打印出什么呢?會(huì)是一個(gè) 1000000010000000 么? 么姊舵？或者程序崩潰因?yàn)槟悴荒芡瑫r(shí)修改同一片內(nèi)存晰绎？答案是：都不是，我們都不確定會(huì)打印出什么括丁。結(jié)果一定是 50000005000000 到 1000000010000000 之間的一個(gè)數(shù)荞下。

我們增加 number 的方法是使用 += 操作符。問題在于，這個(gè)指令并不是不可拆分的（atomic）尖昏。如果你學(xué)過一些計(jì)算機(jī)組成原理仰税，你可能知道，這個(gè)指令實(shí)際上是 CPU 先將這個(gè)數(shù)字讀取到寄存?中抽诉，然后增加1陨簇，然后寫回內(nèi)存。在這個(gè)過程中迹淌，很可能出現(xiàn)的一個(gè)情況是當(dāng)一個(gè)線程從內(nèi)存中讀取這個(gè)整數(shù)之后河绽，還尚未增加或者寫回它，另一個(gè)線程也從內(nèi)存中讀取了它唉窃。這樣兩個(gè)線程寫回內(nèi)存的值其實(shí)是一樣的耙饰。也就是說，兩個(gè)線程同時(shí)抓取內(nèi)存資源時(shí)若無一定先后順序纹份，會(huì)造成資源競爭苟跪。

牛奶過量

上一節(jié)中我們定義了資源競爭出現(xiàn)的條件，這一節(jié)中我們就來介紹一下解決資源競爭的方法矮嫉。在講解這一部分內(nèi)容時(shí)削咆，教授經(jīng)常使用的一個(gè)例子就是牛奶過量問題（Too Much Milk）。

假設(shè)你和你媽每天早晨都要喝牛奶蠢笋，有一天你回家發(fā)現(xiàn)冰箱里沒有牛奶了拨齐，于是你出去買牛奶；等你回到家昨寞、打開冰箱瞻惋，卻發(fā)現(xiàn)已經(jīng)有一盒牛奶了，因?yàn)槟銒寢尣恢滥闳ベI牛奶了援岩，所以也去買了一盒牛奶歼狼。這樣有了兩盒牛奶，你們就不一定能在牛奶過期以前把它們?nèi)亢韧炅讼砘场Ｎ覀兛梢园奄I牛奶這一行為看做臨界區(qū)羽峰，它必須遵守由 Dijkstra 提出的臨界區(qū)調(diào)度的三個(gè)原則：

1. 一次只有一個(gè)線程執(zhí)行臨界區(qū)的指令；
2. 如果一個(gè)線程已經(jīng)在執(zhí)行臨界區(qū)指令則其它線程必須等待添瓷；
3. 一個(gè)等待中的線程在有限的等待時(shí)間后會(huì)進(jìn)入臨界區(qū)梅屉；

前兩條原則保證了線程的安全性，第三條保證了程序運(yùn)行的活性（即鳞贷，程序不會(huì)在某個(gè)指令永遠(yuǎn)的卡着魈馈）。

為了實(shí)現(xiàn)上面三條原則搀愧，我們需要一種通知另一個(gè)線程的辦法惰聂；現(xiàn)實(shí)生活中我們可以在冰箱上留一個(gè)便簽疆偿，寫上“我去買牛奶了”，對(duì)方就不會(huì)再買牛奶了搓幌，我們可以嘗試把這個(gè)過程寫成代碼：

int note = 0;
int milk = 0;
if (!milk ) {         //A
    if (!note) {      //B
        note = 1;     //C
        milk++;       //D
        note = 0;     //E
    }
}

現(xiàn)在加入我們有兩個(gè)線程執(zhí)行這段代碼杆故，會(huì)不會(huì)出現(xiàn)問題呢？讓我們將這兩個(gè)線程命名為 1鼻种，2反番；我們用數(shù)字角標(biāo)表示這個(gè)指令是由哪個(gè)線程執(zhí)行的，那么下面這個(gè)指令序列就會(huì)給我們造成問題：A_1 ,B_1,A_2 ,B_2 ,C_1 ,D_1,E_1 ,C_2 ,D_2 ,E_2叉钥。

兩個(gè)線程分別判斷沒有牛奶也沒有字條以后分別進(jìn)入了買牛奶的過程罢缸，這樣盡管我們有了字條，還是買了兩盒牛奶投队，違反了第一條原則枫疆。

這里我們面臨的主要問題是人的行為是連續(xù)的，所以我們不會(huì)在發(fā)現(xiàn)沒有紙條之后離開一段時(shí)間再去留下紙條敷鸦、買牛奶（當(dāng)然息楔，如果你非要這么干那也沒有辦法），但線程可能在任何指令處被系統(tǒng)調(diào)度?打斷扒披，所以我們不能保證上面這段代碼在兩個(gè)線程中運(yùn)行的結(jié)果值依。

怎樣才能解決上面提到的問題呢？上面的問題似乎主要來源于一點(diǎn)碟案，就是我們先檢查了 note 的值愿险、后將 note 值設(shè)為1 。如果在這兩個(gè)指令之間另一個(gè)線程查看了 note 的值就不會(huì)知道我們已經(jīng)決定去買牛奶了价说。因此我們可以先寫字條辆亏，然后再查看對(duì)方是否已經(jīng)留下字條來決定我們是否去買牛奶：

int note1 = 1; //線程2會(huì)把這一行替換為 note2 = 1;
               //并把下面的 if 判斷換為判斷 note1 是否為 1
if (!milk) {
    if (!note2) {
        milk++;
    }
}
note1 = 0;

很可惜，這種方法會(huì)違反第三條原則鳖目，因?yàn)槿绻€程 1 和線程 2 分別檢查發(fā)現(xiàn)沒有牛奶扮叨，然后分別發(fā)現(xiàn)對(duì)方已經(jīng)留下字條，那么就沒有人會(huì)去買牛奶了领迈。我們希望如果兩個(gè)線程中有一個(gè)在發(fā)現(xiàn)對(duì)方已經(jīng)留下字條后再等待一會(huì)兒彻磁，之后重新查看冰箱里是否有牛奶。這就給了我們下面這種解決方法：

• 線程 1 執(zhí)行的代碼與前面差別不大:

int note1 = 1;
if (!milk) {
    if (!note2) {
        milk++;
    }
}
note1 = 0;

• 線程 2 執(zhí)行的代碼卻與前面的有一定的差別：

int note2 = 1;
while (note1){
    ;
}
if (!milk) {
    milk++;
}
note2 = 0;

這段代碼可以確保在沒有牛奶的情況下狸捅，有且只有一個(gè)人回去買牛奶衷蜓。如果你不信的話我們可以來分析一下這兩個(gè)線程的運(yùn)行過程。

• 假如線程 1 先開始運(yùn)行薪贫，那么線程 1 就會(huì)先將 note1 設(shè)為 ，之后分為兩種情況刻恭，

• 如果線程 2 在線程 1 買牛奶以前就開始運(yùn)行瞧省，那么 note2 也會(huì)被設(shè)為 1扯夭，然后線程 2 就會(huì)卡在 whileloop 中，直到系統(tǒng)調(diào)度使得線程 1 繼續(xù)運(yùn)行鞍匾，線程 1 發(fā)現(xiàn) note2 為1 交洗，就不會(huì)買牛奶，而直接將 note1 設(shè)為 0橡淑，這時(shí)線程 2 就可以繼續(xù)運(yùn)行构拳，去買牛奶。
• 另一種情況是梁棠，線程 2 在線程 1 買完牛奶后再進(jìn)入系統(tǒng)置森，那么它就會(huì)直接跳過 while loop，發(fā)現(xiàn)已經(jīng)有牛奶符糊，就會(huì)拿走字條凫海。

• 最后一種情況是，線程 2 先進(jìn)入系統(tǒng)男娄，那它就會(huì)直接去買牛奶行贪，這時(shí)線程 1 如果進(jìn)入發(fā)現(xiàn)有牛奶或有字條就會(huì)直接拿走字條。因此我們可以保證有且只有一個(gè)人會(huì)買牛奶模闲。

上面這種算法實(shí)際上就是 Peterson 算法建瘫，我們在這里不作介紹，有興趣的同學(xué)可以在網(wǎng)上查看這個(gè)算法的應(yīng)用尸折。從上面這個(gè)例子中我們可以看出啰脚，在并發(fā)多線程中實(shí)現(xiàn)互斥是比較復(fù)雜的。我們上面提到的方法雖然確實(shí)保證了中間的臨界區(qū)只有一段代碼運(yùn)行翁授，但它只適用于 2 個(gè)線程拣播，如果我們想將它推廣到多個(gè)進(jìn)程那么問題就會(huì)更加復(fù)雜，而且如果我們想用兩個(gè)線程執(zhí)行同一段代碼收擦，那么上面代碼中的note1,note2就不適用了贮配，因?yàn)檫\(yùn)行中的線程不會(huì)知道自己是 1 還是 2。接下來的章節(jié)我們會(huì)介紹兩種更為簡便實(shí)用的概念：鎖和條件變量塞赂。

鎖

為了實(shí)現(xiàn)互斥泪勒，我們需要簡便的方法來判定一個(gè)線程是否有權(quán)利執(zhí)行一段臨界區(qū)的代碼。鎖就是這樣一種方法：為了防止你媽媽和你同時(shí)去買牛奶宴猾，你可以在去買牛奶以前給冰箱上個(gè)鎖圆存，這樣你媽媽看到冰箱已經(jīng)上鎖就知道，你一定已經(jīng)去買牛奶了仇哆。在程序中沦辙，鎖也是這樣一種存在——我們?yōu)楸Ｗo(hù)一些共享的數(shù)據(jù)而建立一個(gè)鎖，每次修改這些數(shù)據(jù)以前都先試圖獲得鎖讹剔，成功獲得鎖后再進(jìn)入臨界區(qū)修改數(shù)據(jù)油讯。
在這里我們需要強(qiáng)調(diào)一點(diǎn)：鎖是用來鎖住數(shù)據(jù)的详民，而不是用來鎖住代碼的。你的每個(gè)鎖一定會(huì)有它保護(hù)的共享數(shù)據(jù)陌兑，所有調(diào)用和修改該數(shù)據(jù)的操作都會(huì)被鎖保護(hù)沈跨。如果你發(fā)現(xiàn)自己想不明白自己寫的代碼中的鎖在保護(hù)哪些數(shù)據(jù)，那么你可能需要重新設(shè)計(jì)鎖了兔综。

鎖最常用的地方是在一個(gè)共享的對(duì)象中饿凛。雖然 C 不是一門面向?qū)ο蟮恼Z言，但我們?nèi)匀豢梢杂盟鼇韺?shí)現(xiàn)面向?qū)ο蟮乃枷耄含F(xiàn)在就讓我們來用一個(gè)面向?qū)ο蟮睦觼韼阏J(rèn)識(shí)鎖的應(yīng)用软驰。假設(shè)我們已經(jīng)實(shí)現(xiàn)了一個(gè)鎖struct lock和用來獲得鎖涧窒、解鎖的函數(shù)void lock_acquire(struct lock *my_lock);和void lock_unlock(struct lock *my_lock);

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct word{
    struct lock *word_lock;
    char *word;
    int count;
}

int count_word(struct word *my_word){
    lock_acquire(my_word->word_lock);
    my_word->count += 1;
    lock_unlock(my_word->word_lock);
    return 0;
}

int modify_word(struct word *my_word, char *new_word){
    lock_acquire(my_word->word_lock);
    my_word->word = realloc(my_word->word, (strlen(new_word)+1)*sizeof(char));
    strcpy(my_word->word, new_word);
    lock_unlock(my_word->word_lock);
    return 0;
}

這里struct word中的word_lock保護(hù)了struct word中的兩個(gè)成員,word和count，在我們需要修改這兩個(gè)變量時(shí)碌宴，我們都必須先獲得鎖杀狡，然后再修改其中的值。

鎖的用法是比較好理解的贰镣，現(xiàn)在我們需要考慮的是如何實(shí)現(xiàn)一個(gè)這樣的鎖呜象。
你可能很容易就能想到上一節(jié)中買牛奶的例子：如果我們用一個(gè)位表示目前鎖是否被持有， 0表示空閑碑隆，1表示被持有恭陡，那我們就可以在發(fā)現(xiàn)這一位為 時(shí)將其設(shè)為 ，成功獲得鎖上煤。

但這樣有一個(gè)問題：如果在一個(gè)線程檢查這一位為0后立刻被內(nèi)核中斷休玩、切換至下一個(gè)線程，下一個(gè)線程查看這一位為 0劫狠，獲得了鎖翎冲，執(zhí)行臨界區(qū)代碼至一半碍讨，又被切換回原來的線程黄橘，原來的線程也認(rèn)為鎖是空閑的信不，因此將其設(shè)為1 ，獲得鎖后運(yùn)行臨界區(qū)懦砂。這樣我們就有兩個(gè)線程同時(shí)執(zhí)行臨界區(qū)代碼蜒犯，鎖就形同虛設(shè)了。

為了避免上面提到的這種問題荞膘，我們希望讀取和設(shè)置值能成為一個(gè)不可分割的操作罚随，這樣就沒有第二個(gè)進(jìn)程可以插進(jìn)這兩個(gè)操作之間了。這就是 測試并設(shè)置指令（Test and Set）羽资。這一指令由硬件提供淘菩，它會(huì)讀取一個(gè)內(nèi)存位置的值，然后將 存入這個(gè)位置屠升。這樣潮改，如果我們將一個(gè)整數(shù)設(shè)為 费奸，然后在試圖獲得鎖用 Test and Set 將它設(shè)為 1，在返回值為 0時(shí)成功獲得鎖进陡，并在解鎖時(shí)將這個(gè)值重新設(shè)為 ，這個(gè)整數(shù)就可以成為一個(gè)鎖微服。

struct lock{
    int value;
}

void lock_acquire(struct lock *my_lock){
    while (test_and_set(&my_lock->value))
        ;
    return;
}

void lock_unlock(struct lock *my_lock){
    my_lock->value = 0;
    return;
}

上面的代碼就是一種實(shí)現(xiàn)鎖的方法趾疚；由于不能獲得鎖的線程會(huì)在 while loop 中不斷循環(huán)，這種實(shí)現(xiàn)方法被很形象地稱為 自旋鎖（Spinlock）,以蕴。這種方法有一個(gè)顯而易見的缺點(diǎn)糙麦，那就是它的效率很低，假設(shè)一個(gè)線程企圖獲得一個(gè)另一個(gè)線程已經(jīng)持有的鎖時(shí)丛肮，它會(huì)不斷循環(huán)赡磅，浪費(fèi)處理器時(shí)間。因此宝与，自旋鎖只適用于已知單個(gè)線程持有鎖時(shí)間很短的情況焚廊。

為了解決上面提到的效率低的問題，我們可以把未能成功獲得鎖的線程加入到這個(gè)鎖的等待名單上习劫，在持有鎖的線程解鎖時(shí)再選擇一個(gè)線程獲得鎖咆瘟。為了實(shí)現(xiàn)這一功能，我們就需要使用下面的章節(jié)中我們要講到的條件變量诽里。

練習(xí)：對(duì)換自旋鎖

條件變量

在講到鎖的時(shí)候我們已經(jīng)提到袒餐，在一個(gè)鎖已經(jīng)被一個(gè)線程持有時(shí)，我們應(yīng)該把想要獲得這個(gè)鎖的線程加入等待名單谤狡，然后阻塞這些線程灸眼，在解鎖時(shí)從等待名單中選擇一個(gè)線程解鎖，從而提高運(yùn)行效率墓懂。你可能已經(jīng)注意到焰宣，這個(gè)過程跟我們之前提到的互斥有所不同——互斥的定義是一段代碼不能同時(shí)被兩個(gè)線程運(yùn)行，而我們現(xiàn)在希望達(dá)到的目的是使得兩個(gè)線程不能同時(shí)運(yùn)行兩段需要鎖的代碼拒贱，因此我們需要一個(gè)工具通知一個(gè)線程另一個(gè)線程已經(jīng)解鎖宛徊，然后讓想要獲得鎖的線程按一定順序獲得鎖、分別運(yùn)行逻澳。這種協(xié)調(diào)多個(gè)線程運(yùn)行速度的行為被稱作 同步（synchronization）

在某個(gè)條件不成立時(shí)闸天，需要該條件成立的線程可以對(duì)與這個(gè)條件相對(duì)應(yīng)的條件變量調(diào)用 wait()函數(shù)， wait() 函數(shù)會(huì)將這個(gè)線程加入等待名單斜做，并進(jìn)入阻塞態(tài)苞氮，并自動(dòng)解鎖；當(dāng)某個(gè)線程修改這個(gè)條件涉及到的變量時(shí)瓤逼，線程必須自行調(diào)用 signal()或 broadcast()笼吟。 signal()和 broadcast()的區(qū)別是 signal()只會(huì)將等待名單上一個(gè)線程喚醒库物，由阻塞態(tài)變?yōu)榫途w態(tài)，而broadcast()會(huì)將等待名單上所有線程都有阻塞態(tài)變?yōu)榫途w態(tài)贷帮。收到信號(hào)的線程回到就緒態(tài)的線程此時(shí)仍然處于wait()函數(shù)中 沒有返回戚揭，當(dāng)內(nèi)核選擇繼續(xù)運(yùn)行該線程時(shí)，線程會(huì)獲得其 原來持有的鎖撵枢，然后再從wait()函數(shù)返回民晒。

你可能注意到 wait()和signal() 這兩個(gè)函數(shù)恰好和Unix系統(tǒng)中等待子進(jìn)程結(jié)束的 wait() 函數(shù)和修改進(jìn)程對(duì)信號(hào)的處理方式的 signal() 函數(shù)的命名沖突了，因此我們不能直接叫它們 wait()和 signal()锄禽。在下面的實(shí)例中潜必，我們會(huì)管這兩個(gè)函數(shù)叫 void cond_var_wait(struct cond_var *variable,struct spinlock *lock)和 void cond_var_signal(struct cond_var *variable)。假設(shè)我們已經(jīng)實(shí)現(xiàn)了這兩個(gè)函數(shù)沃但，以及一個(gè)條件變量的結(jié)構(gòu) struct cond_var 磁滚，一個(gè)自旋鎖 struct spinlock ，以及用來獲得自旋鎖和解鎖自旋鎖的函數(shù) void spinlock_acquire(struct spinlock *lock);和void spinlock_unlock(struct spinlock *lock); ∠恚現(xiàn)在我們就來看一看鎖結(jié)構(gòu)的實(shí)現(xiàn)垂攘。

struct my_lock{
    int value;
    struct spinlock *spin;
    struct cond_var *condition;
}

我們先來定義一個(gè)數(shù)據(jù)結(jié)構(gòu)。struct my_lock 是我們新定義的鎖淤刃，它包含三個(gè)成員： value 與前兩節(jié)中我們定義的自旋鎖中的 value功能相同搜贤，其值為 1時(shí)表示鎖已被一個(gè)進(jìn)程持有，其值為0 時(shí)表示鎖空閑钝凶；spin 是一個(gè)自旋鎖仪芒，用來保護(hù) struct my_lock的內(nèi)部結(jié)構(gòu)；condition 是一個(gè)指向我們自己定義的條件變量結(jié)構(gòu)的指針耕陷，它與這個(gè)鎖相匹配掂名，用來在鎖已被持有時(shí)使想要獲得鎖的線程等待。下面我們就來寫獲得鎖的 void acquire_my_lock(struct my_lock *lock)函數(shù)與解鎖的void unlock_my_lock(struct my_lock *lock)函數(shù)哟沫。

void acquire_my_lock(struct my_lock *lock){
    spinlock_acquire(lock->spin);
    while (lock->value) {
        cond_var_wait(lock->condition);
    }
    lock->value = 1;
    spinlock_unlock(lock->spin);
}

void unlock_my_lock(struct my_lock *lock){
    spinlock_acquire(lock->spin);
    lock->value = 0;
    cond_var_signal(lock->condition);
    spinlock_unlock(lock->spin);
}

由于我們用自旋鎖保護(hù)鎖的內(nèi)部狀態(tài)饺蔑，在想要獲得鎖的時(shí)候，我們必須先獲得鎖內(nèi)部的自旋鎖嗜诀，然后才能獲得查看猾警、修改鎖的內(nèi)部狀態(tài)的權(quán)限。你可能會(huì)問一個(gè)問題：既然我們?nèi)匀灰米孕i來鎖住struct my_lock的內(nèi)部狀態(tài)隆敢，那這種鎖的效率為什么會(huì)比普通的自旋鎖高呢发皿？這個(gè)問題的答案與鎖的持有時(shí)間有關(guān)。

首先拂蝎，除了自旋鎖以外穴墅，我們幾乎只有一種其它實(shí)現(xiàn)鎖的辦法，那就是禁用中斷——在禁用中斷的情況下，我們不會(huì)收到系統(tǒng)的計(jì)時(shí)器或任何硬件發(fā)來的中斷玄货，因此我們的代碼在獲得鎖后一定可以作為一個(gè)整體執(zhí)行完成皇钞。然而，禁用中斷這種做法比自旋鎖更不被提倡松捉，因?yàn)樵诮弥袛嗟倪^程中夹界，我們可能失去硬件發(fā)來的 I/O 中斷等重要的信息。盡管我們在少數(shù)情況下必須禁用中斷隘世，在持續(xù)時(shí)間未知的情況下我們還是不希望使用禁用中斷的手段達(dá)到鎖的效果掉盅。

因此，我們只有盡量縮短持有自旋鎖的時(shí)間以舒。我們無法控制一個(gè)線程持有一個(gè)鎖的時(shí)間，但我們知道慢哈，一個(gè)線程花在獲得鎖的函數(shù)里的時(shí)間是固定且較短的蔓钟。因此我們用一個(gè)自旋鎖來保護(hù)鎖的內(nèi)部狀態(tài)，而不是直接在 while loop 里反復(fù)檢查鎖的狀態(tài)卵贱。

在上面很短的代碼中滥沫，有一點(diǎn)我們要特別提醒你注意：我們在一個(gè) while loop 中執(zhí)行cond_var_wait(lock->condition);，而不是在一個(gè) if 語句后執(zhí)行键俱。我們將具體講解這一做法的原因兰绣。

void cond_var_wait(struct cond_var *condition, struct spinlock *lock){
    TCB *curr = current_thread();
    struct list_elem *new_waiter = calloc(1, sizeof(struct list_elem));
    new_waiter->thread = curr;
    new_waiter->next = NULL;
    struct list_element *temp = condition->waiters;
    if (!temp) {
        condition->waiters = new_waiter;
    } else {
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = new_waiter;
    }
    disable_interrupt();
    spinlock_unlock(lock);
    thread_block(curr);
    spinlock_acquire(lock);
    enable_interrupt();
}

void cond_var_signal(struct cond_var *condition){
    if(!condition->waiters) return;
    struct list_element *head = condition->waiters;
    condition->waiters = head->next;
    thread_unblock(head->TCB);
    free(head);
}

條件變量理解測試

void cond_var_wait(struct cond_var *condition, struct spinlock *lock){
    TCB *curr = current_thread();
    struct list_elem *new_waiter = calloc(1, sizeof(struct list_elem));
    new_waiter->thread = curr;
    new_waiter->next = NULL;
    struct list_element *temp = condition->waiters;
    if (!temp) {
        condition->waiters = new_waiter;
    } else {
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = new_waiter;
    }
    disable_interrupt();
    spinlock_unlock(lock);
    thread_block(curr);
    spinlock_acquire(lock);
    enable_interrupt();
}

void cond_var_signal(struct cond_var *condition){
    if(!condition->waiters) return;
    struct list_element *head = condition->waiters;
    condition->waiters = head->next;
    thread_unblock(head->TCB);
    free(head);
}

信號(hào)量

在前面的章節(jié)中，我們講解了互斥和同步這兩個(gè)概念编振，以及用來實(shí)現(xiàn)互斥和同步的鎖和條件變量∽罕纾現(xiàn)在我們來講一個(gè)介于鎖和條件變量之間的工具，信號(hào)量踪央。信號(hào)量（semaphore） 在被初始化時(shí)帶有一個(gè)自定的非負(fù)整數(shù)值和一個(gè)空的等待名單臀玄，之后線程可以對(duì)這個(gè)信號(hào)量進(jìn)行兩個(gè)操作 P() 與 V() 。 P() 會(huì)等待信號(hào)量的值變?yōu)檎龜?shù)畅蹂，然后將信號(hào)量的值減1 健无； P() 是一個(gè)不可分割的操作，因此我們不用擔(dān)心檢查信號(hào)量的值變?yōu)檎龜?shù)后會(huì)有其它線程先把信號(hào)量的值降低到0 液斜。 V() 會(huì)將信號(hào)量的值加 累贤，如果此時(shí)信號(hào)量的等待名單上有線程，則喚醒其中一個(gè)少漆。

我們可以看到臼膏，信號(hào)量的兩個(gè)操作似乎與條件變量的 wait() 和 signal() 非常相似，但它其實(shí)更適合被用來實(shí)現(xiàn)互斥示损。我們可以在初始化時(shí)將它的值設(shè)為1 讶请，這時(shí) P() 就相當(dāng)于 acquire_lock() ， V() 就相當(dāng)于 unlock_lock() 。由于初始值為1 夺溢，且 P() 是一個(gè)不可分割的操作论巍，我們知道同時(shí)只能有一個(gè)線程會(huì)成功地從 P() 返回，進(jìn)入臨界區(qū)风响。這個(gè)線程完成臨界區(qū)代碼后可以調(diào)用 V() 嘉汰，使信號(hào)量的值重新變?yōu)? ，這時(shí)下一個(gè)線程又可以進(jìn)入臨界區(qū)状勤。

如果我們想要用信號(hào)量來模仿條件變量的用法鞋怀，那就比較困難了。信號(hào)量與條件變量的一大區(qū)別在于條件變量 沒有內(nèi)部狀態(tài)持搜。比如密似，如果一個(gè)線程調(diào)用了 signal() ，此時(shí)沒有變量在等待這個(gè)條件發(fā)生變化葫盼，那么這個(gè) signal() 就不會(huì)產(chǎn)生任何影響残腌。在條件變?yōu)椴怀闪⒑螅乱粋€(gè)來等待這個(gè)條件的線程不會(huì)因?yàn)榍懊嬖?jīng)有線程調(diào)用過 signal() 就不等待贫导。

信號(hào)量就不同了抛猫。如果一個(gè)信號(hào)量的初始值為0 ，一個(gè)線程在沒有線程在 P() 中等待時(shí)調(diào)用了 V() 孩灯，信號(hào)量的值就會(huì)被增加至1 闺金。這時(shí)如果有一個(gè)線程調(diào)用 P() ，則它無需經(jīng)過任何等待峰档，因?yàn)榍懊婢€程的歷史被信號(hào)量保留了下來败匹。

信號(hào)量與條件變量相比還有一個(gè)缺點(diǎn)，那就是條件變量在等待時(shí)會(huì)將保護(hù)共享數(shù)據(jù)的鎖自動(dòng)解鎖讥巡，但 P()沒有這個(gè)功能哎壳，因此我們一般會(huì)在調(diào)用 P() 以前解鎖，否則其它線程就無法修改共享數(shù)據(jù)尚卫，造成永遠(yuǎn)等待的局面归榕。

所幸，還是有一種可以用信號(hào)量模仿條件變量的方法的吱涉。這種方法由 Andrew Birrell 在微軟 Windows 支持條件變量以前實(shí)現(xiàn)刹泄。下面我們寫的代碼沒有包含有關(guān)的數(shù)據(jù)結(jié)構(gòu)和函數(shù)的定義，你可以聯(lián)系前幾節(jié)講的鎖和條件變量的定義和這一節(jié)講的信號(hào)量的定義怎爵、將這段代碼當(dāng)做偽代碼來理解：

void cond_var_wait(struct cond_var *condition, struct lock *my_lock){
    struct semaphore *my_sema;
    semaphore_init(my_sema, 0); // 將信號(hào)量初始值設(shè)為 1
    // 將信號(hào)量加入條件變量的等待名單
    append_to_list(condition->waiters, my_sema);
    lock_unlock(my_lock);
    semaphore_P(my_sema);
    lock_acquire(my_lock);
}

void cond_var_signal(struct cond_var *condition){
    if (condition->waiters) {
        semaphore_V(remove_from_list(condition->waiters));
    }
}

從上面的代碼中我們可以看出，用信號(hào)量可以實(shí)現(xiàn)互斥和同步的功能鳖链，但這兩種用法背后的想法是截然不同的墩莫，剛剛接觸多線程編程的人很容易混淆這兩種用法狂秦。如果你覺得自己對(duì)于同步和互斥的概念的理解仍然不透徹推捐，那么我們就建議你使用鎖和條件變量，以鞏固你對(duì)于互斥和同步的認(rèn)識(shí)牛柒。

Pthread 庫中的鎖和條件變量

前幾節(jié)中我們講了如何實(shí)現(xiàn)鎖和條件變量；這些知識(shí)雖然能幫助你對(duì)鎖和條件變量有更深的認(rèn)識(shí)椭更，但除非你在設(shè)計(jì)一個(gè)操作系統(tǒng)蛾魄，否則你是不需要自己實(shí)現(xiàn)鎖和條件變量的。如果你在寫一個(gè)用戶級(jí)別的程序，那么你需要的就只是了解 Linux 中提供了哪些已經(jīng)實(shí)現(xiàn)好的鎖和條件變量茉稠。這一節(jié)中，我們就來講一講 Linux Pthread 庫中包含的鎖和條件變量的相關(guān)函數(shù)而线。

死鎖

死鎖的引入

顧名思義，死鎖死鎖肯定與鎖有關(guān)膀篮，我們知道引入鎖又是為了解決多進(jìn)程或多線程之間的同步與互斥問題嘹狞，那么到底怎樣的情形才會(huì)產(chǎn)生死鎖呢？
典型的兩種死鎖情形：

• 線程自己將自己鎖住
  一般情況下,如果同一個(gè)線程先后兩次調(diào)用lock,在第二次調(diào)?用時(shí),由于鎖已經(jīng)被占用,該線程會(huì)掛起等待占用鎖的線程釋放鎖,然而鎖正是被自己占用著的,該線程又被掛起而沒有機(jī)會(huì)釋放鎖,因此 就永遠(yuǎn)處于掛起等待狀態(tài)了,于是就形成了死鎖(Deadlock)誓竿。

• 多線程搶占鎖資源被困
  又如線程A獲 得了鎖1,線程B獲得了鎖2,這時(shí)線程A調(diào)用lock試圖獲得鎖2,結(jié)果是需要掛起等待線程B釋放 鎖2,而這時(shí)線程B也調(diào)用lock試圖獲得鎖1,結(jié)果是需要掛起等待線程A釋放鎖1,于是線程A和B都 永遠(yuǎn)處于掛起狀態(tài)了磅网，死鎖再次形成。

計(jì)算機(jī)系統(tǒng)中的死鎖

1筷屡、資源分類
（一）可重用性資源和消耗性資源
可重用資源：可供用戶重復(fù)使用多次的資源涧偷。

性質(zhì)：

• 每一個(gè)可重用性資源中的單元只能分配給一個(gè)進(jìn)程（或線程）使用，不允許多個(gè)進(jìn)程（或線程）共享毙死。
• 可重用性資源的使用順序： 請求資源—->使用資源—->釋放資源
• 系統(tǒng)中每一類可重用性資源中的單元數(shù)目是相對(duì)固定的燎潮，進(jìn)程（或線程）在運(yùn)行期間既不能創(chuàng)建也不能刪除它。

可消耗性資源：又稱臨時(shí)性資源扼倘，是由進(jìn)程（或線程）在運(yùn)行期間動(dòng)態(tài)的創(chuàng)建和消耗的确封。

性質(zhì)：

• 每一類可消耗性資源的單元數(shù)目在進(jìn)程（或線程）運(yùn)行期間是可以不斷變化的，有時(shí)可能為0.
• 進(jìn)程，或線程）在運(yùn)行過程中可以不斷的創(chuàng)建可消耗性資源的單元爪喘，將它們放入該資源類的緩沖區(qū)中颜曾，以增加該資源類的單元數(shù)目。
• 進(jìn)程（或線程）在運(yùn)行過程中可請求若干個(gè)可消耗性資源腥放，用于進(jìn)程（或線程）自己的消耗不再將它們返回給該資源類中泛啸。
  可消耗性資源通常是由生產(chǎn)者進(jìn)程（或線程）創(chuàng)建，由消費(fèi)者進(jìn)程（或線程）消耗秃症。

（二）可搶占性資源和不可搶占性資源

• 可搶占性資源：?某進(jìn)程（或線程）在獲得該類資源后候址，該資源可以被其他進(jìn)程（或線程）或系統(tǒng)搶占。
  CPU和主存均屬于可搶占性資源种柑。
• 不可搶占性資源：?系統(tǒng)一旦把某資源分配該進(jìn)程（或線程）之后，就不能強(qiáng)行收回荠雕，只能在進(jìn)程（或線程）用完之后自行釋放炸卑。
  磁帶機(jī)、打印機(jī)等都屬于不可搶占性資源五续。

引起死鎖的原因

（一）競爭不可搶占資源引起死鎖
如：共享文件時(shí)引起死鎖
系統(tǒng)中擁有兩個(gè)進(jìn)程P1和P2疙驾，它們都準(zhǔn)備寫兩個(gè)文件F1和F2它碎。而這兩者都屬于可重用和不可搶占性資源链韭。如果進(jìn)程P1在打開F1的同時(shí)，P2進(jìn)程打開F2文件旋讹，當(dāng)P1想打開F2時(shí)由于F2已結(jié)被占用而阻塞，當(dāng)P2想打開1時(shí)由于F1已結(jié)被占用而阻塞睦疫，此時(shí)就會(huì)無線等待下去，形成死鎖葫松。

（二）競爭可消耗資源引起死鎖
如：進(jìn)程通信時(shí)引起死鎖
系統(tǒng)中擁有三個(gè)進(jìn)程P1腋么、P2和P3圣勒，m1圣贸、m2吁峻、m3是3可消耗資源锡搜。進(jìn)程P1一方面產(chǎn)生消息m1，將其發(fā)送給P2辟狈，另一方面要從P3接收消息m3哼转。而進(jìn)程P2一方面產(chǎn)生消息m2壹蔓，將其發(fā)送給P3披摄，另一方面要從P1接收消息m1疚膊。類似的寓盗，進(jìn)程P3一方面產(chǎn)生消息m3傀蚌，將其發(fā)送給P1，另一方面要從P2接收消息m2销部。
如果三個(gè)進(jìn)程都先發(fā)送自己產(chǎn)生的消息后接收別人發(fā)來的消息舅桩，則可以順利的運(yùn)行下去不會(huì)產(chǎn)生死鎖擂涛，但要是三個(gè)進(jìn)程都先接收別人的消息而不產(chǎn)生消息則會(huì)永遠(yuǎn)等待下去，產(chǎn)生死鎖排监。

（三）進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

上圖中，如果按曲線1的順序推進(jìn)棋蚌，兩個(gè)進(jìn)程可順利完成；如果按曲線2的順序推進(jìn)盛垦，兩個(gè)進(jìn)程可順利完成颊埃；如果按曲線3的順序推進(jìn)竟秫，兩個(gè)進(jìn)程可順利完成肥败；如果按曲線4的順序推進(jìn)馒稍，兩個(gè)進(jìn)程將進(jìn)入不安全區(qū)D中证膨，此時(shí)P1保持了資源R1央勒，P2保持了資源R2崔步，系統(tǒng)處于不安全狀態(tài)，如果繼續(xù)向前推進(jìn)列林，則可能產(chǎn)生死鎖者甲。

死鎖的定義过牙、必要條件和處理方法

1、死鎖的定義：如果一組進(jìn)程（或線程）中的每一個(gè)進(jìn)程（或線程）都在等待僅由該組進(jìn)程中的其他進(jìn)程（或線程）才能引發(fā)的事件舶赔，那么該組進(jìn)程（或線程）是死鎖的（Deadlock）竟纳。
2锥累、產(chǎn)生死鎖的必要條件
（1）互斥條件语淘。進(jìn)程（線程）所申請的資源在一段時(shí)間內(nèi)只能被一個(gè)進(jìn)程（線程）鎖占用惶翻。
（2）請求和保持條件吕粗。進(jìn)程（線程）已經(jīng)占有至少一個(gè)資源，但又提出了新的資源請求垃沦，而該資源卻被其他進(jìn)程（線程）占用肢簿。
（3）不可搶占條件（不可剝奪條件）池充。進(jìn)程（線程）已獲得的資源在未使用完之前不能被搶占收夸。
（4）循環(huán)等待條件（環(huán)路等待條件）。在發(fā)生死鎖時(shí)咽瓷，必然存在一個(gè)進(jìn)程（線程）—-資源的循環(huán)鏈茅姜。
3钻洒、處理死鎖的方法
（1）預(yù)防死鎖称诗。破壞死鎖產(chǎn)生的必要條件中的一個(gè)或多個(gè)粪狼。注意再榄，互斥條件不能被破壞困鸥，否則會(huì)造成結(jié)果的不可再現(xiàn)性。
（2）避免死鎖猬腰。在資源分匹配過程中姑荷，防止系統(tǒng)進(jìn)入不安全區(qū)域鼠冕。
（3）檢測死鎖。通過檢測機(jī)構(gòu)檢測死鎖的發(fā)生博脑，然后采取適當(dāng)措施解除死鎖泞边。
（4）解除死鎖繁堡。在檢測機(jī)構(gòu)檢測死鎖發(fā)生后椭蹄，采取適當(dāng)措施解除死鎖绳矩。

利用銀行家算法避免死鎖

1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)
（1）可利用資源向量Available[m]应媚。m為系統(tǒng)中的資源種類數(shù)中姜，如果向量Available[j] = K,則表示系統(tǒng)中Rj類資源由K個(gè)丢胚。
（2）最大需求矩陣Max[n][m]。m為系統(tǒng)中的資源種類數(shù)勘高，n為系統(tǒng)中正在運(yùn)行的進(jìn)程（線程）數(shù)层亿，如果Max[i][j] = K,則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K個(gè)匿又。
（3）分配矩陣Allocation[n][m]碌更。m為系統(tǒng)中的資源種類數(shù)，n為系統(tǒng)中正在運(yùn)行的進(jìn)程（線程）數(shù)旭绒，如果Allocation[i][j] = K,則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K個(gè)重父。
（4）需求矩陣Need[n][m]房午。m為系統(tǒng)中的資源種類數(shù)郭厌，n為系統(tǒng)中正在運(yùn)行的進(jìn)程（線程）數(shù)折柠，如果Need[i][j] = K,則表示進(jìn)程i還需要Rj類資源K個(gè)。
以上三個(gè)矩陣間的關(guān)系：
Need[i][j] = Max[i][j] - Allocation[i][j]

2缘眶、銀行家算法
設(shè)Request( i)是進(jìn)程Pi的請求向量巷懈，如果Request(i) [j] = K,表示進(jìn)程Pi需要K個(gè)Rj類型的資源顶燕。
（1）如果Request(i) [j] <= Need[i][j],轉(zhuǎn)向步驟（2）涌攻。
（2）如果Request(i) [j] <= Available[j] ,轉(zhuǎn)向步驟（3）恳谎。
（3）系統(tǒng)嘗試著把資源分給進(jìn)程Pi。
Available[j] = Available[j] - Request(i) [j];
Allocation[i][j] = Allocation[i][j] + Request(i) [j];
Need[i][j] = Need[i][j] - Request(i) [j];
（4）系統(tǒng)執(zhí)行安全性算法鸵膏，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)怎炊。

3、安全性算法
（1）設(shè)置兩個(gè)向量：
1》工作向量Work[m],它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目,初始值Work = Available非区。
2》Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程院仿，使其運(yùn)行完成。開始時(shí)Finish[i] = false颠放，當(dāng)有足夠的資源分配給進(jìn)程時(shí)Finish[i] = true碰凶。
（2）從進(jìn)程（線程）集合中找到一個(gè)能滿足下述條件的進(jìn)程（線程）。
1》Finish[i] = false
2》Need[i][j] <= Work[j]砾莱，如果找到轉(zhuǎn)到步驟3》腊瑟，沒找到轉(zhuǎn)到步驟4》闰非。
3》Work[j] = Work[j] + Allocation[i][j] ;
Finish[i] = true;
go to step 2;
4》如果所有進(jìn)程（線程）的Finish[i] = true都滿足，表示系統(tǒng)處于安全狀態(tài)纱控，反之系統(tǒng)處于不安全狀態(tài)胚迫。
https://blog.csdn.net/hj605635529/article/details/69214903
文章摘自計(jì)算機(jī)操作系統(tǒng)（第四版）楊小丹書籍