30 張圖詳解操作系統(tǒng)總結(jié)！

一、概述

基本特征

1. 并發(fā)

并發(fā)是指宏觀上在一段時(shí)間內(nèi)能同時(shí)運(yùn)行多個(gè)程序，而并行則指同一時(shí)刻能運(yùn)行多個(gè)指令。

并行需要硬件支持，如多流水線、多核處理器或者分布式計(jì)算系統(tǒng)。

操作系統(tǒng)通過(guò)引入進(jìn)程和線程，使得程序能夠并發(fā)運(yùn)行。

2. 共享

共享是指系統(tǒng)中的資源可以被多個(gè)并發(fā)進(jìn)程共同使用。

有兩種共享方式：互斥共享和同時(shí)共享。

互斥共享的資源稱為臨界資源，例如打印機(jī)等，在同一時(shí)刻只允許一個(gè)進(jìn)程訪問(wèn)，需要用同步機(jī)制來(lái)實(shí)現(xiàn)互斥訪問(wèn)。

3. 虛擬

虛擬技術(shù)把一個(gè)物理實(shí)體轉(zhuǎn)換為多個(gè)邏輯實(shí)體。

主要有兩種虛擬技術(shù)：時(shí)（時(shí)間）分復(fù)用技術(shù)和空（空間）分復(fù)用技術(shù)。

多個(gè)進(jìn)程能在同一個(gè)處理器上并發(fā)執(zhí)行使用了時(shí)分復(fù)用技術(shù)，讓每個(gè)進(jìn)程輪流占用處理器，每次只執(zhí)行一小個(gè)時(shí)間片并快速切換。

虛擬內(nèi)存使用了空分復(fù)用技術(shù)，它將物理內(nèi)存抽象為地址空間，每個(gè)進(jìn)程都有各自的地址空間。地址空間的頁(yè)被映射到物理內(nèi)存，地址空間的頁(yè)并不需要全部在物理內(nèi)存中，當(dāng)使用到一個(gè)沒(méi)有在物理內(nèi)存的頁(yè)時(shí)，執(zhí)行頁(yè)面置換算法，將該頁(yè)置換到內(nèi)存中。

4. 異步

異步指進(jìn)程不是一次性執(zhí)行完畢，而是走走停停，以不可知的速度向前推進(jìn)。

基本功能

1. 進(jìn)程管理

進(jìn)程控制、進(jìn)程同步、進(jìn)程通信、死鎖處理、處理機(jī)調(diào)度等。

2. 內(nèi)存管理

內(nèi)存分配、地址映射、內(nèi)存保護(hù)與共享、虛擬內(nèi)存等。

3. 文件管理

文件存儲(chǔ)空間的管理、目錄管理、文件讀寫管理和保護(hù)等。

4. 設(shè)備管理

完成用戶的 I/O 請(qǐng)求，方便用戶使用各種設(shè)備，并提高設(shè)備的利用率。

主要包括緩沖管理、設(shè)備分配、設(shè)備處理、虛擬設(shè)備等。

系統(tǒng)調(diào)用

如果一個(gè)進(jìn)程在用戶態(tài)需要使用內(nèi)核態(tài)的功能，就進(jìn)行系統(tǒng)調(diào)用從而陷入內(nèi)核，由操作系統(tǒng)代為完成。

Linux 的系統(tǒng)調(diào)用主要有以下這些：

大內(nèi)核和微內(nèi)核

1. 大內(nèi)核

大內(nèi)核是將操作系統(tǒng)功能作為一個(gè)緊密結(jié)合的整體放到內(nèi)核。

由于各模塊共享信息，因此有很高的性能。

2. 微內(nèi)核

由于操作系統(tǒng)不斷復(fù)雜，因此將一部分操作系統(tǒng)功能移出內(nèi)核，從而降低內(nèi)核的復(fù)雜性。移出的部分根據(jù)分層的原則劃分成若干服務(wù)，相互獨(dú)立。

在微內(nèi)核結(jié)構(gòu)下，操作系統(tǒng)被劃分成小的、定義良好的模塊，只有微內(nèi)核這一個(gè)模塊運(yùn)行在內(nèi)核態(tài)，其余模塊運(yùn)行在用戶態(tài)。

因?yàn)樾枰l繁地在用戶態(tài)和核心態(tài)之間進(jìn)行切換，所以會(huì)有一定的性能損失。

中斷分類

1. 外中斷

由 CPU 執(zhí)行指令以外的事件引起，如 I/O 完成中斷，表示設(shè)備輸入/輸出處理已經(jīng)完成，處理器能夠發(fā)送下一個(gè)輸入/輸出請(qǐng)求。此外還有時(shí)鐘中斷、控制臺(tái)中斷等。

2. 異常

由 CPU 執(zhí)行指令的內(nèi)部事件引起，如非法操作碼、地址越界、算術(shù)溢出等。

3. 陷入

在用戶程序中使用系統(tǒng)調(diào)用。

二、進(jìn)程管理

進(jìn)程與線程

1. 進(jìn)程

進(jìn)程是資源分配的基本單位。

進(jìn)程控制塊 (Process Control Block, PCB) 描述進(jìn)程的基本信息和運(yùn)行狀態(tài)，所謂的創(chuàng)建進(jìn)程和撤銷進(jìn)程，都是指對(duì) PCB 的操作。

下圖顯示了 4 個(gè)程序創(chuàng)建了 4 個(gè)進(jìn)程，這 4 個(gè)進(jìn)程可以并發(fā)地執(zhí)行。

2. 線程

線程是獨(dú)立調(diào)度的基本單位。

一個(gè)進(jìn)程中可以有多個(gè)線程，它們共享進(jìn)程資源。

QQ 和瀏覽器是兩個(gè)進(jìn)程，瀏覽器進(jìn)程里面有很多線程，例如 HTTP 請(qǐng)求線程、事件響應(yīng)線程、渲染線程等等，線程的并發(fā)執(zhí)行使得在瀏覽器中點(diǎn)擊一個(gè)新鏈接從而發(fā)起 HTTP 請(qǐng)求時(shí)，瀏覽器還可以響應(yīng)用戶的其它事件。

3. 區(qū)別

Ⅰ 擁有資源

進(jìn)程是資源分配的基本單位，但是線程不擁有資源，線程可以訪問(wèn)隸屬進(jìn)程的資源。

Ⅱ 調(diào)度

線程是獨(dú)立調(diào)度的基本單位，在同一進(jìn)程中，線程的切換不會(huì)引起進(jìn)程切換，從一個(gè)進(jìn)程中的線程切換到另一個(gè)進(jìn)程中的線程時(shí)，會(huì)引起進(jìn)程切換。

Ⅲ 系統(tǒng)開銷

由于創(chuàng)建或撤銷進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O 設(shè)備等，所付出的開銷遠(yuǎn)大于創(chuàng)建或撤銷線程時(shí)的開銷。類似地，在進(jìn)行進(jìn)程切換時(shí)，涉及當(dāng)前執(zhí)行進(jìn)程 CPU 環(huán)境的保存及新調(diào)度進(jìn)程 CPU 環(huán)境的設(shè)置，而線程切換時(shí)只需保存和設(shè)置少量寄存器內(nèi)容，開銷很小。

Ⅳ 通信方面

線程間可以通過(guò)直接讀寫同一進(jìn)程中的數(shù)據(jù)進(jìn)行通信，但是進(jìn)程通信需要借助 IPC。

進(jìn)程狀態(tài)的切換

• 就緒狀態(tài)（ready）：等待被調(diào)度

• 運(yùn)行狀態(tài)（running）

• 阻塞狀態(tài)（waiting）：等待資源

應(yīng)該注意以下內(nèi)容：

• 只有就緒態(tài)和運(yùn)行態(tài)可以相互轉(zhuǎn)換，其它的都是單向轉(zhuǎn)換。就緒狀態(tài)的進(jìn)程通過(guò)調(diào)度算法從而獲得 CPU 時(shí)間，轉(zhuǎn)為運(yùn)行狀態(tài)；而運(yùn)行狀態(tài)的進(jìn)程，在分配給它的 CPU 時(shí)間片用完之后就會(huì)轉(zhuǎn)為就緒狀態(tài)，等待下一次調(diào)度。

• 阻塞狀態(tài)是缺少需要的資源從而由運(yùn)行狀態(tài)轉(zhuǎn)換而來(lái)，但是該資源不包括 CPU 時(shí)間，缺少 CPU 時(shí)間會(huì)從運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)。

進(jìn)程調(diào)度算法

不同環(huán)境的調(diào)度算法目標(biāo)不同，因此需要針對(duì)不同環(huán)境來(lái)討論調(diào)度算法。

1. 批處理系統(tǒng)

批處理系統(tǒng)沒(méi)有太多的用戶操作，在該系統(tǒng)中，調(diào)度算法目標(biāo)是保證吞吐量和周轉(zhuǎn)時(shí)間（從提交到終止的時(shí)間）。

1.1 先來(lái)先服務(wù) first-come first-serverd（FCFS）

非搶占式的調(diào)度算法，按照請(qǐng)求的順序進(jìn)行調(diào)度。

有利于長(zhǎng)作業(yè)，但不利于短作業(yè)，因?yàn)槎套鳂I(yè)必須一直等待前面的長(zhǎng)作業(yè)執(zhí)行完畢才能執(zhí)行，而長(zhǎng)作業(yè)又需要執(zhí)行很長(zhǎng)時(shí)間，造成了短作業(yè)等待時(shí)間過(guò)長(zhǎng)。

1.2 短作業(yè)優(yōu)先 shortest job first（SJF）

非搶占式的調(diào)度算法，按估計(jì)運(yùn)行時(shí)間最短的順序進(jìn)行調(diào)度。

長(zhǎng)作業(yè)有可能會(huì)餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因?yàn)槿绻恢庇卸套鳂I(yè)到來(lái)，那么長(zhǎng)作業(yè)永遠(yuǎn)得不到調(diào)度。

1.3 最短剩余時(shí)間優(yōu)先 shortest remaining time next（SRTN）

最短作業(yè)優(yōu)先的搶占式版本，按剩余運(yùn)行時(shí)間的順序進(jìn)行調(diào)度。當(dāng)一個(gè)新的作業(yè)到達(dá)時(shí)，其整個(gè)運(yùn)行時(shí)間與當(dāng)前進(jìn)程的剩余時(shí)間作比較。如果新的進(jìn)程需要的時(shí)間更少，則掛起當(dāng)前進(jìn)程，運(yùn)行新的進(jìn)程。否則新的進(jìn)程等待。

2. 交互式系統(tǒng)

交互式系統(tǒng)有大量的用戶交互操作，在該系統(tǒng)中調(diào)度算法的目標(biāo)是快速地進(jìn)行響應(yīng)。

2.1 時(shí)間片輪轉(zhuǎn)

將所有就緒進(jìn)程按 FCFS 的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把 CPU 時(shí)間分配給隊(duì)首進(jìn)程，該進(jìn)程可以執(zhí)行一個(gè)時(shí)間片。當(dāng)時(shí)間片用完時(shí)，由計(jì)時(shí)器發(fā)出時(shí)鐘中斷，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾，同時(shí)繼續(xù)把 CPU 時(shí)間分配給隊(duì)首的進(jìn)程。

時(shí)間片輪轉(zhuǎn)算法的效率和時(shí)間片的大小有很大關(guān)系：

• 因?yàn)檫M(jìn)程切換都要保存進(jìn)程的信息并且載入新進(jìn)程的信息，如果時(shí)間片太小，會(huì)導(dǎo)致進(jìn)程切換得太頻繁，在進(jìn)程切換上就會(huì)花過(guò)多時(shí)間。

• 而如果時(shí)間片過(guò)長(zhǎng)，那么實(shí)時(shí)性就不能得到保證。

2.2 優(yōu)先級(jí)調(diào)度

為每個(gè)進(jìn)程分配一個(gè)優(yōu)先級(jí)，按優(yōu)先級(jí)進(jìn)行調(diào)度。

為了防止低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)等不到調(diào)度，可以隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級(jí)。

2.3 多級(jí)反饋隊(duì)列

一個(gè)進(jìn)程需要執(zhí)行 100 個(gè)時(shí)間片，如果采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，那么需要交換 100 次。

多級(jí)隊(duì)列是為這種需要連續(xù)執(zhí)行多個(gè)時(shí)間片的進(jìn)程考慮，它設(shè)置了多個(gè)隊(duì)列，每個(gè)隊(duì)列時(shí)間片大小都不同，例如 1,2,4,8,..。進(jìn)程在第一個(gè)隊(duì)列沒(méi)執(zhí)行完，就會(huì)被移到下一個(gè)隊(duì)列。這種方式下，之前的進(jìn)程只需要交換 7 次。

每個(gè)隊(duì)列優(yōu)先權(quán)也不同，最上面的優(yōu)先權(quán)最高。因此只有上一個(gè)隊(duì)列沒(méi)有進(jìn)程在排隊(duì)，才能調(diào)度當(dāng)前隊(duì)列上的進(jìn)程。

可以將這種調(diào)度算法看成是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的結(jié)合。

3. 實(shí)時(shí)系統(tǒng)

實(shí)時(shí)系統(tǒng)要求一個(gè)請(qǐng)求在一個(gè)確定時(shí)間內(nèi)得到響應(yīng)。

分為硬實(shí)時(shí)和軟實(shí)時(shí)，前者必須滿足絕對(duì)的截止時(shí)間，后者可以容忍一定的超時(shí)。

進(jìn)程同步

1. 臨界區(qū)

對(duì)臨界資源進(jìn)行訪問(wèn)的那段代碼稱為臨界區(qū)。

為了互斥訪問(wèn)臨界資源，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前，需要先進(jìn)行檢查。

//?entry?section
//?critical?section;
//?exit?section

2. 同步與互斥

• 同步：多個(gè)進(jìn)程因?yàn)楹献鳟a(chǎn)生的直接制約關(guān)系，使得進(jìn)程有一定的先后執(zhí)行關(guān)系。

• 互斥：多個(gè)進(jìn)程在同一時(shí)刻只有一個(gè)進(jìn)程能進(jìn)入臨界區(qū)。

3. 信號(hào)量

信號(hào)量（Semaphore）是一個(gè)整型變量，可以對(duì)其執(zhí)行 down 和 up 操作，也就是常見的 P 和 V 操作。

• down ? : 如果信號(hào)量大于 0 ，執(zhí)行 -1 操作；如果信號(hào)量等于 0，進(jìn)程睡眠，等待信號(hào)量大于 0；

• up ?：對(duì)信號(hào)量執(zhí)行 +1 操作，喚醒睡眠的進(jìn)程讓其完成 down 操作。

down 和 up 操作需要被設(shè)計(jì)成原語(yǔ)，不可分割，通常的做法是在執(zhí)行這些操作的時(shí)候屏蔽中斷。

如果信號(hào)量的取值只能為 0 或者 1，那么就成為了 ? 互斥量（Mutex） ?，0 表示臨界區(qū)已經(jīng)加鎖，1 表示臨界區(qū)解鎖。

typedef?int?semaphore;
semaphore?mutex?=?1;
void?P1()?{
????down(&mutex);
????//?臨界區(qū)
????up(&mutex);
}

void?P2()?{
????down(&mutex);
????//?臨界區(qū)
????up(&mutex);
}

使用信號(hào)量實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問(wèn)題

問(wèn)題描述：使用一個(gè)緩沖區(qū)來(lái)保存物品，只有緩沖區(qū)沒(méi)有滿，生產(chǎn)者才可以放入物品；只有緩沖區(qū)不為空，消費(fèi)者才可以拿走物品。

因?yàn)榫彌_區(qū)屬于臨界資源，因此需要使用一個(gè)互斥量 mutex 來(lái)控制對(duì)緩沖區(qū)的互斥訪問(wèn)。

為了同步生產(chǎn)者和消費(fèi)者的行為，需要記錄緩沖區(qū)中物品的數(shù)量。數(shù)量可以使用信號(hào)量來(lái)進(jìn)行統(tǒng)計(jì)，這里需要使用兩個(gè)信號(hào)量：empty 記錄空緩沖區(qū)的數(shù)量，full 記錄滿緩沖區(qū)的數(shù)量。其中，empty 信號(hào)量是在生產(chǎn)者進(jìn)程中使用，當(dāng) empty 不為 0 時(shí)，生產(chǎn)者才可以放入物品；full 信號(hào)量是在消費(fèi)者進(jìn)程中使用，當(dāng) full 信號(hào)量不為 0 時(shí)，消費(fèi)者才可以取走物品。

注意，不能先對(duì)緩沖區(qū)進(jìn)行加鎖，再測(cè)試信號(hào)量。也就是說(shuō)，不能先執(zhí)行 down(mutex) 再執(zhí)行 down(empty)。如果這么做了，那么可能會(huì)出現(xiàn)這種情況：生產(chǎn)者對(duì)緩沖區(qū)加鎖后，執(zhí)行 down(empty) 操作，發(fā)現(xiàn) empty = 0，此時(shí)生產(chǎn)者睡眠。消費(fèi)者不能進(jìn)入臨界區(qū)，因?yàn)樯a(chǎn)者對(duì)緩沖區(qū)加鎖了，消費(fèi)者就無(wú)法執(zhí)行 up(empty) 操作，empty 永遠(yuǎn)都為 0，導(dǎo)致生產(chǎn)者永遠(yuǎn)等待下，不會(huì)釋放鎖，消費(fèi)者因此也會(huì)永遠(yuǎn)等待下去。

#define?N?100
typedef?int?semaphore;
semaphore?mutex?=?1;
semaphore?empty?=?N;
semaphore?full?=?0;

void?producer()?{
????while(TRUE)?{
????????int?item?=?produce_item();
????????down(&empty);
????????down(&mutex);
????????insert_item(item);
????????up(&mutex);
????????up(&full);
????}
}

void?consumer()?{
????while(TRUE)?{
????????down(&full);
????????down(&mutex);
????????int?item?=?remove_item();
????????consume_item(item);
????????up(&mutex);
????????up(&empty);
????}
}

4. 管程

使用信號(hào)量機(jī)制實(shí)現(xiàn)的生產(chǎn)者消費(fèi)者問(wèn)題需要客戶端代碼做很多控制，而管程把控制的代碼獨(dú)立出來(lái)，不僅不容易出錯(cuò)，也使得客戶端代碼調(diào)用更容易。

c 語(yǔ)言不支持管程，下面的示例代碼使用了類 Pascal 語(yǔ)言來(lái)描述管程。示例代碼的管程提供了 insert() 和 remove() 方法，客戶端代碼通過(guò)調(diào)用這兩個(gè)方法來(lái)解決生產(chǎn)者-消費(fèi)者問(wèn)題。

monitor?ProducerConsumer
????integer?i;
????condition?c;

????procedure?insert();
????begin
????????//?...
????end;

????procedure?remove();
????begin
????????//?...
????end;
end?monitor;

管程有一個(gè)重要特性：在一個(gè)時(shí)刻只能有一個(gè)進(jìn)程使用管程。進(jìn)程在無(wú)法繼續(xù)執(zhí)行的時(shí)候不能一直占用管程，否則其它進(jìn)程永遠(yuǎn)不能使用管程。

管程引入了 ? 條件變量 ? 以及相關(guān)的操作：wait() 和 signal() 來(lái)實(shí)現(xiàn)同步操作。對(duì)條件變量執(zhí)行 wait() 操作會(huì)導(dǎo)致調(diào)用進(jìn)程阻塞，把管程讓出來(lái)給另一個(gè)進(jìn)程持有。signal() 操作用于喚醒被阻塞的進(jìn)程。

使用管程實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問(wèn)題

//?管程
monitor?ProducerConsumer
????condition?full,?empty;
????integer?count?:=?0;
????condition?c;

????procedure?insert(item:?integer);
????begin
????????if?count?=?N?then?wait(full);
????????insert_item(item);
????????count?:=?count?+?1;
????????if?count?=?1?then?signal(empty);
????end;

????function?remove:?integer;
????begin
????????if?count?=?0?then?wait(empty);
????????remove?=?remove_item;
????????count?:=?count?-?1;
????????if?count?=?N?-1?then?signal(full);
????end;
end?monitor;

//?生產(chǎn)者客戶端
procedure?producer
begin
????while?true?do
????begin
????????item?=?produce_item;
????????ProducerConsumer.insert(item);
????end
end;

//?消費(fèi)者客戶端
procedure?consumer
begin
????while?true?do
????begin
????????item?=?ProducerConsumer.remove;
????????consume_item(item);
????end
end;

經(jīng)典同步問(wèn)題

生產(chǎn)者和消費(fèi)者問(wèn)題前面已經(jīng)討論過(guò)了。

1. 哲學(xué)家進(jìn)餐問(wèn)題

五個(gè)哲學(xué)家圍著一張圓桌，每個(gè)哲學(xué)家面前放著食物。哲學(xué)家的生活有兩種交替活動(dòng)：吃飯以及思考。當(dāng)一個(gè)哲學(xué)家吃飯時(shí)，需要先拿起自己左右兩邊的兩根筷子，并且一次只能拿起一根筷子。

下面是一種錯(cuò)誤的解法，如果所有哲學(xué)家同時(shí)拿起左手邊的筷子，那么所有哲學(xué)家都在等待其它哲學(xué)家吃完并釋放自己手中的筷子，導(dǎo)致死鎖。

#define?N?5

void?philosopher(int?i)?{
????while(TRUE)?{
????????think();
????????take(i);???????//?拿起左邊的筷子
????????take((i+1)%N);?//?拿起右邊的筷子
????????eat();
????????put(i);
????????put((i+1)%N);
????}
}

為了防止死鎖的發(fā)生，可以設(shè)置兩個(gè)條件：

• 必須同時(shí)拿起左右兩根筷子；

• 只有在兩個(gè)鄰居都沒(méi)有進(jìn)餐的情況下才允許進(jìn)餐。

#define?N?5
#define?LEFT?(i?+?N?-?1)?%?N?//?左鄰居
#define?RIGHT?(i?+?1)?%?N????//?右鄰居
#define?THINKING?0
#define?HUNGRY???1
#define?EATING???2
typedef?int?semaphore;
int?state[N];????????????????//?跟蹤每個(gè)哲學(xué)家的狀態(tài)
semaphore?mutex?=?1;?????????//?臨界區(qū)的互斥，臨界區(qū)是?state?數(shù)組，對(duì)其修改需要互斥
semaphore?s[N];??????????????//?每個(gè)哲學(xué)家一個(gè)信號(hào)量

void?philosopher(int?i)?{
????while(TRUE)?{
????????think(i);
????????take_two(i);
????????eat(i);
????????put_two(i);
????}
}

void?take_two(int?i)?{
????down(&mutex);
????state[i]?=?HUNGRY;
????check(i);
????up(&mutex);
????down(&s[i]);?//?只有收到通知之后才可以開始吃，否則會(huì)一直等下去
}

void?put_two(i)?{
????down(&mutex);
????state[i]?=?THINKING;
????check(LEFT);?//?嘗試通知左右鄰居，自己吃完了，你們可以開始吃了
????check(RIGHT);
????up(&mutex);
}

void?eat(int?i)?{
????down(&mutex);
????state[i]?=?EATING;
????up(&mutex);
}

//?檢查兩個(gè)鄰居是否都沒(méi)有用餐，如果是的話，就?up(&s[i])，使得?down(&s[i])?能夠得到通知并繼續(xù)執(zhí)行
void?check(i)?{?????????
????if(state[i]?==?HUNGRY?&&?state[LEFT]?!=?EATING?&&?state[RIGHT]?!=EATING)?{
????????state[i]?=?EATING;
????????up(&s[i]);
????}
}

2. 讀者-寫者問(wèn)題

允許多個(gè)進(jìn)程同時(shí)對(duì)數(shù)據(jù)進(jìn)行讀操作，但是不允許讀和寫以及寫和寫操作同時(shí)發(fā)生。

一個(gè)整型變量 count 記錄在對(duì)數(shù)據(jù)進(jìn)行讀操作的進(jìn)程數(shù)量，一個(gè)互斥量 count_mutex 用于對(duì) count 加鎖，一個(gè)互斥量 data_mutex 用于對(duì)讀寫的數(shù)據(jù)加鎖。

typedef?int?semaphore;
semaphore?count_mutex?=?1;
semaphore?data_mutex?=?1;
int?count?=?0;

void?reader()?{
????while(TRUE)?{
????????down(&count_mutex);
????????count++;
????????if(count?==?1)?down(&data_mutex);?//?第一個(gè)讀者需要對(duì)數(shù)據(jù)進(jìn)行加鎖，防止寫進(jìn)程訪問(wèn)
????????up(&count_mutex);
????????read();
????????down(&count_mutex);
????????count--;
????????if(count?==?0)?up(&data_mutex);
????????up(&count_mutex);
????}
}

void?writer()?{
????while(TRUE)?{
????????down(&data_mutex);
????????write();
????????up(&data_mutex);
????}
}

以下內(nèi)容由 @Bandi Yugandhar 提供。

The first case may result Writer to starve. This case favous Writers i.e no writer, once added to the queue, shall be kept waiting longer than absolutely necessary(only when there are readers that entered the queue before the writer).

int?readcount,?writecount;???????????????????//(initial?value?=?0)
semaphore?rmutex,?wmutex,?readLock,?resource;?//(initial?value?=?1)

//READER
void?reader()?{

?down(&readLock);?????????????????//??reader?is?trying?to?enter
?down(&rmutex);??????????????????//???lock?to?increase?readcount
??readcount++;?????????????????
??if?(readcount?==?1)??????????
???down(&resource);??????????????//if?you?are?the?first?reader?then?lock??the?resource
?up(&rmutex);??????????????????//release??for?other?readers
?up(&readLock);?????????????????//Done?with?trying?to?access?the?resource


//reading?is?performed


?down(&rmutex);??????????????????//reserve?exit?section?-?avoids?race?condition?with?readers
?readcount--;???????????????????????//indicate?you're?leaving
??if?(readcount?==?0)??????????//checks?if?you?are?last?reader?leaving
???up(&resource);??????????????//if?last,?you?must?release?the?locked?resource
?up(&rmutex);??????????????????//release?exit?section?for?other?readers
}

//WRITER
void?writer()?{
??
??down(&wmutex);??????????????????//reserve?entry?section?for?writers?-?avoids?race?conditions
??writecount++;????????????????//report?yourself?as?a?writer?entering
??if?(writecount?==?1)?????????//checks?if?you're?first?writer
???down(&readLock);???????????????//if?you're?first,?then?you?must?lock?the?readers?out.?Prevent?them?from?trying?to?enter?CS
??up(&wmutex);??????????????????//release?entry?section


?down(&resource);????????????????//reserve?the?resource?for?yourself?-?prevents?other?writers?from?simultaneously?editing?the?shared?resource
??//writing?is?performed
?up(&resource);????????????????//release?file


??down(&wmutex);??????????????????//reserve?exit?section
??writecount--;????????????????//indicate?you're?leaving
??if?(writecount?==?0)?????????//checks?if?you're?the?last?writer
???up(&readLock);???????????????//if?you're?last?writer,?you?must?unlock?the?readers.?Allows?them?to?try?enter?CS?for?reading
??up(&wmutex);??????????????????//release?exit?section
}

We can observe that every reader is forced to acquire ReadLock. On the otherhand, writers doesn’t need to lock individually. Once the first writer locks the ReadLock, it will be released only when there is no writer left in the queue.

From the both cases we observed that either reader or writer has to starve. Below solutionadds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.

int?readCount;??????????????????//?init?to?0;?number?of?readers?currently?accessing?resource

//?all?semaphores?initialised?to?1
Semaphore?resourceAccess;???????//?controls?access?(read/write)?to?the?resource
Semaphore?readCountAccess;??????//?for?syncing?changes?to?shared?variable?readCount
Semaphore?serviceQueue;?????????//?FAIRNESS:?preserves?ordering?of?requests?(signaling?must?be?FIFO)

void?writer()
{?
????down(&serviceQueue);???????????//?wait?in?line?to?be?servicexs
????//?
????down(&resourceAccess);?????????//?request?exclusive?access?to?resource
????//?
????up(&serviceQueue);???????????//?let?next?in?line?be?serviced

????//?
????writeResource();????????????//?writing?is?performed
????//?

????//?
????up(&resourceAccess);?????????//?release?resource?access?for?next?reader/writer
????//?
}

void?reader()
{?
????down(&serviceQueue);???????????//?wait?in?line?to?be?serviced
????down(&readCountAccess);????????//?request?exclusive?access?to?readCount
????//?
????if?(readCount?==?0)?????????//?if?there?are?no?readers?already?reading:
????????down(&resourceAccess);?????//?request?resource?access?for?readers?(writers?blocked)
????readCount++;????????????????//?update?count?of?active?readers
????//?
????up(&serviceQueue);???????????//?let?next?in?line?be?serviced
????up(&readCountAccess);????????//?release?access?to?readCount

????//?
????readResource();?????????????//?reading?is?performed
????//?

????down(&readCountAccess);????????//?request?exclusive?access?to?readCount
????//?
????readCount--;????????????????//?update?count?of?active?readers
????if?(readCount?==?0)?????????//?if?there?are?no?readers?left:
????????up(&resourceAccess);?????//?release?resource?access?for?all
????//?
????up(&readCountAccess);????????//?release?access?to?readCount
}

進(jìn)程通信

進(jìn)程同步與進(jìn)程通信很容易混淆，它們的區(qū)別在于：

• 進(jìn)程同步：控制多個(gè)進(jìn)程按一定順序執(zhí)行；

• 進(jìn)程通信：進(jìn)程間傳輸信息。

進(jìn)程通信是一種手段，而進(jìn)程同步是一種目的。也可以說(shuō)，為了能夠達(dá)到進(jìn)程同步的目的，需要讓進(jìn)程進(jìn)行通信，傳輸一些進(jìn)程同步所需要的信息。

1. 管道

管道是通過(guò)調(diào)用 pipe 函數(shù)創(chuàng)建的，fd[0] 用于讀，fd[1] 用于寫。

#include?
int?pipe(int?fd[2]);

它具有以下限制：

• 只支持半雙工通信（單向交替?zhèn)鬏敚?/span>

• 只能在父子進(jìn)程或者兄弟進(jìn)程中使用。

2. FIFO

也稱為命名管道，去除了管道只能在父子進(jìn)程中使用的限制。

#include?
int?mkfifo(const?char?*path,?mode_t?mode);
int?mkfifoat(int?fd,?const?char?*path,?mode_t?mode);

FIFO 常用于客戶-服務(wù)器應(yīng)用程序中，F(xiàn)IFO 用作匯聚點(diǎn)，在客戶進(jìn)程和服務(wù)器進(jìn)程之間傳遞數(shù)據(jù)。

3. 消息隊(duì)列

相比于 FIFO，消息隊(duì)列具有以下優(yōu)點(diǎn)：

• 消息隊(duì)列可以獨(dú)立于讀寫進(jìn)程存在，從而避免了 FIFO 中同步管道的打開和關(guān)閉時(shí)可能產(chǎn)生的困難；

• 避免了 FIFO 的同步阻塞問(wèn)題，不需要進(jìn)程自己提供同步方法；

• 讀進(jìn)程可以根據(jù)消息類型有選擇地接收消息，而不像 FIFO 那樣只能默認(rèn)地接收。

4. 信號(hào)量

它是一個(gè)計(jì)數(shù)器，用于為多個(gè)進(jìn)程提供對(duì)共享數(shù)據(jù)對(duì)象的訪問(wèn)。

5. 共享存儲(chǔ)

允許多個(gè)進(jìn)程共享一個(gè)給定的存儲(chǔ)區(qū)。因?yàn)閿?shù)據(jù)不需要在進(jìn)程之間復(fù)制，所以這是最快的一種 IPC。

需要使用信號(hào)量用來(lái)同步對(duì)共享存儲(chǔ)的訪問(wèn)。

多個(gè)進(jìn)程可以將同一個(gè)文件映射到它們的地址空間從而實(shí)現(xiàn)共享內(nèi)存。另外 XSI 共享內(nèi)存不是使用文件，而是使用內(nèi)存的匿名段。

6. 套接字

與其它通信機(jī)制不同的是，它可用于不同機(jī)器間的進(jìn)程通信。

三、內(nèi)存管理

虛擬內(nèi)存

虛擬內(nèi)存的目的是為了讓物理內(nèi)存擴(kuò)充成更大的邏輯內(nèi)存，從而讓程序獲得更多的可用內(nèi)存。

為了更好的管理內(nèi)存，操作系統(tǒng)將內(nèi)存抽象成地址空間。每個(gè)程序擁有自己的地址空間，這個(gè)地址空間被分割成多個(gè)塊，每一塊稱為一頁(yè)。這些頁(yè)被映射到物理內(nèi)存，但不需要映射到連續(xù)的物理內(nèi)存，也不需要所有頁(yè)都必須在物理內(nèi)存中。當(dāng)程序引用到不在物理內(nèi)存中的頁(yè)時(shí)，由硬件執(zhí)行必要的映射，將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。

從上面的描述中可以看出，虛擬內(nèi)存允許程序不用將地址空間中的每一頁(yè)都映射到物理內(nèi)存，也就是說(shuō)一個(gè)程序不需要全部調(diào)入內(nèi)存就可以運(yùn)行，這使得有限的內(nèi)存運(yùn)行大程序成為可能。例如有一臺(tái)計(jì)算機(jī)可以產(chǎn)生 16 位地址，那么一個(gè)程序的地址空間范圍是 0~64K。該計(jì)算機(jī)只有 32KB 的物理內(nèi)存，虛擬內(nèi)存技術(shù)允許該計(jì)算機(jī)運(yùn)行一個(gè) 64K 大小的程序。

分頁(yè)系統(tǒng)地址映射

內(nèi)存管理單元（MMU）管理著地址空間和物理內(nèi)存的轉(zhuǎn)換，其中的頁(yè)表（Page table）存儲(chǔ)著頁(yè)（程序地址空間）和頁(yè)框（物理內(nèi)存空間）的映射表。

一個(gè)虛擬地址分成兩個(gè)部分，一部分存儲(chǔ)頁(yè)面號(hào)，一部分存儲(chǔ)偏移量。

下圖的頁(yè)表存放著 16 個(gè)頁(yè)，這 16 個(gè)頁(yè)需要用 4 個(gè)比特位來(lái)進(jìn)行索引定位。例如對(duì)于虛擬地址（0010 000000000100），前 4 位是存儲(chǔ)頁(yè)面號(hào) 2，讀取表項(xiàng)內(nèi)容為（110 1），頁(yè)表項(xiàng)最后一位表示是否存在于內(nèi)存中，1 表示存在。后 12 位存儲(chǔ)偏移量。這個(gè)頁(yè)對(duì)應(yīng)的頁(yè)框的地址為 （110 000000000100）。

頁(yè)面置換算法

在程序運(yùn)行過(guò)程中，如果要訪問(wèn)的頁(yè)面不在內(nèi)存中，就發(fā)生缺頁(yè)中斷從而將該頁(yè)調(diào)入內(nèi)存中。此時(shí)如果內(nèi)存已無(wú)空閑空間，系統(tǒng)必須從內(nèi)存中調(diào)出一個(gè)頁(yè)面到磁盤對(duì)換區(qū)中來(lái)騰出空間。

頁(yè)面置換算法和緩存淘汰策略類似，可以將內(nèi)存看成磁盤的緩存。在緩存系統(tǒng)中，緩存的大小有限，當(dāng)有新的緩存到達(dá)時(shí)，需要淘汰一部分已經(jīng)存在的緩存，這樣才有空間存放新的緩存數(shù)據(jù)。

頁(yè)面置換算法的主要目標(biāo)是使頁(yè)面置換頻率最低（也可以說(shuō)缺頁(yè)率最低）。

1. 最佳

OPT, Optimal replacement algorithm

所選擇的被換出的頁(yè)面將是最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)，通?？梢员ＷC獲得最低的缺頁(yè)率。

是一種理論上的算法，因?yàn)闊o(wú)法知道一個(gè)頁(yè)面多長(zhǎng)時(shí)間不再被訪問(wèn)。

舉例：一個(gè)系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并有如下頁(yè)面引用序列：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

開始運(yùn)行時(shí)，先將 7, 0, 1 三個(gè)頁(yè)面裝入內(nèi)存。當(dāng)進(jìn)程要訪問(wèn)頁(yè)面 2 時(shí)，產(chǎn)生缺頁(yè)中斷，會(huì)將頁(yè)面 7 換出，因?yàn)轫?yè)面 7 再次被訪問(wèn)的時(shí)間最長(zhǎng)。

2. 最近最久未使用

LRU, Least Recently Used

雖然無(wú)法知道將來(lái)要使用的頁(yè)面情況，但是可以知道過(guò)去使用頁(yè)面的情況。LRU 將最近最久未使用的頁(yè)面換出。

為了實(shí)現(xiàn) LRU，需要在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表。當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí)，將這個(gè)頁(yè)面移到鏈表表頭。這樣就能保證鏈表表尾的頁(yè)面是最近最久未訪問(wèn)的。

因?yàn)槊看卧L問(wèn)都需要更新鏈表，因此這種方式實(shí)現(xiàn)的 LRU 代價(jià)很高。

4，7，0，7，1，0，1，2，1，2，6

3. 最近未使用

NRU, Not Recently Used

每個(gè)頁(yè)面都有兩個(gè)狀態(tài)位：R 與 M，當(dāng)頁(yè)面被訪問(wèn)時(shí)設(shè)置頁(yè)面的 R=1，當(dāng)頁(yè)面被修改時(shí)設(shè)置 M=1。其中 R 位會(huì)定時(shí)被清零?？梢詫㈨?yè)面分成以下四類：

R=0，M=0
R=0，M=1
R=1，M=0
R=1，M=1

當(dāng)發(fā)生缺頁(yè)中斷時(shí)，NRU 算法隨機(jī)地從類編號(hào)最小的非空類中挑選一個(gè)頁(yè)面將它換出。

NRU 優(yōu)先換出已經(jīng)被修改的臟頁(yè)面（R=0，M=1），而不是被頻繁使用的干凈頁(yè)面（R=1，M=0）。

4. 先進(jìn)先出

FIFO, First In First Out

選擇換出的頁(yè)面是最先進(jìn)入的頁(yè)面。

該算法會(huì)將那些經(jīng)常被訪問(wèn)的頁(yè)面換出，導(dǎo)致缺頁(yè)率升高。

5. 第二次機(jī)會(huì)算法

FIFO 算法可能會(huì)把經(jīng)常使用的頁(yè)面置換出去，為了避免這一問(wèn)題，對(duì)該算法做一個(gè)簡(jiǎn)單的修改：

當(dāng)頁(yè)面被訪問(wèn) (讀或?qū)? 時(shí)設(shè)置該頁(yè)面的 R 位為 1。需要替換的時(shí)候，檢查最老頁(yè)面的 R 位。如果 R 位是 0，那么這個(gè)頁(yè)面既老又沒(méi)有被使用，可以立刻置換掉；如果是 1，就將 R 位清 0，并把該頁(yè)面放到鏈表的尾端，修改它的裝入時(shí)間使它就像剛裝入的一樣，然后繼續(xù)從鏈表的頭部開始搜索。

6. 時(shí)鐘

Clock

第二次機(jī)會(huì)算法需要在鏈表中移動(dòng)頁(yè)面，降低了效率。時(shí)鐘算法使用環(huán)形鏈表將頁(yè)面連接起來(lái)，再使用一個(gè)指針指向最老的頁(yè)面。

分段

虛擬內(nèi)存采用的是分頁(yè)技術(shù)，也就是將地址空間劃分成固定大小的頁(yè)，每一頁(yè)再與內(nèi)存進(jìn)行映射。

下圖為一個(gè)編譯器在編譯過(guò)程中建立的多個(gè)表，有 4 個(gè)表是動(dòng)態(tài)增長(zhǎng)的，如果使用分頁(yè)系統(tǒng)的一維地址空間，動(dòng)態(tài)增長(zhǎng)的特點(diǎn)會(huì)導(dǎo)致覆蓋問(wèn)題的出現(xiàn)。

分段的做法是把每個(gè)表分成段，一個(gè)段構(gòu)成一個(gè)獨(dú)立的地址空間。每個(gè)段的長(zhǎng)度可以不同，并且可以動(dòng)態(tài)增長(zhǎng)。

段頁(yè)式

程序的地址空間劃分成多個(gè)擁有獨(dú)立地址空間的段，每個(gè)段上的地址空間劃分成大小相同的頁(yè)。這樣既擁有分段系統(tǒng)的共享和保護(hù)，又擁有分頁(yè)系統(tǒng)的虛擬內(nèi)存功能。

分頁(yè)與分段的比較

• 對(duì)程序員的透明性：分頁(yè)透明，但是分段需要程序員顯式劃分每個(gè)段。

• 地址空間的維度：分頁(yè)是一維地址空間，分段是二維的。

• 大小是否可以改變：頁(yè)的大小不可變，段的大小可以動(dòng)態(tài)改變。

• 出現(xiàn)的原因：分頁(yè)主要用于實(shí)現(xiàn)虛擬內(nèi)存，從而獲得更大的地址空間；分段主要是為了使程序和數(shù)據(jù)可以被劃分為邏輯上獨(dú)立的地址空間并且有助于共享和保護(hù)。

四、設(shè)備管理

磁盤結(jié)構(gòu)

• 盤面（Platter）：一個(gè)磁盤有多個(gè)盤面；

• 磁道（Track）：盤面上的圓形帶狀區(qū)域，一個(gè)盤面可以有多個(gè)磁道；

• 扇區(qū)（Track Sector）：磁道上的一個(gè)弧段，一個(gè)磁道可以有多個(gè)扇區(qū)，它是最小的物理儲(chǔ)存單位，目前主要有 512 bytes 與 4 K 兩種大??；

• 磁頭（Head）：與盤面非常接近，能夠?qū)⒈P面上的磁場(chǎng)轉(zhuǎn)換為電信號(hào)（讀），或者將電信號(hào)轉(zhuǎn)換為盤面的磁場(chǎng)（寫）；

• 制動(dòng)手臂（Actuator arm）：用于在磁道之間移動(dòng)磁頭；

• 主軸（Spindle）：使整個(gè)盤面轉(zhuǎn)動(dòng)。

磁盤調(diào)度算法

讀寫一個(gè)磁盤塊的時(shí)間的影響因素有：

• 旋轉(zhuǎn)時(shí)間（主軸轉(zhuǎn)動(dòng)盤面，使得磁頭移動(dòng)到適當(dāng)?shù)纳葏^(qū)上）

• 尋道時(shí)間（制動(dòng)手臂移動(dòng)，使得磁頭移動(dòng)到適當(dāng)?shù)拇诺郎希?/span>

• 實(shí)際的數(shù)據(jù)傳輸時(shí)間

其中，尋道時(shí)間最長(zhǎng)，因此磁盤調(diào)度的主要目標(biāo)是使磁盤的平均尋道時(shí)間最短。

1. 先來(lái)先服務(wù)

FCFS, First Come First Served

按照磁盤請(qǐng)求的順序進(jìn)行調(diào)度。

優(yōu)點(diǎn)是公平和簡(jiǎn)單。缺點(diǎn)也很明顯，因?yàn)槲磳?duì)尋道做任何優(yōu)化，使平均尋道時(shí)間可能較長(zhǎng)。

2. 最短尋道時(shí)間優(yōu)先

SSTF, Shortest Seek Time First

優(yōu)先調(diào)度與當(dāng)前磁頭所在磁道距離最近的磁道。

雖然平均尋道時(shí)間比較低，但是不夠公平。如果新到達(dá)的磁道請(qǐng)求總是比一個(gè)在等待的磁道請(qǐng)求近，那么在等待的磁道請(qǐng)求會(huì)一直等待下去，也就是出現(xiàn)饑餓現(xiàn)象。具體來(lái)說(shuō)，兩端的磁道請(qǐng)求更容易出現(xiàn)饑餓現(xiàn)象。

3. 電梯算法

SCAN

電梯總是保持一個(gè)方向運(yùn)行，直到該方向沒(méi)有請(qǐng)求為止，然后改變運(yùn)行方向。

電梯算法（掃描算法）和電梯的運(yùn)行過(guò)程類似，總是按一個(gè)方向來(lái)進(jìn)行磁盤調(diào)度，直到該方向上沒(méi)有未完成的磁盤請(qǐng)求，然后改變方向。

因?yàn)榭紤]了移動(dòng)方向，因此所有的磁盤請(qǐng)求都會(huì)被滿足，解決了 SSTF 的饑餓問(wèn)題。

五、鏈接

編譯系統(tǒng)

以下是一個(gè) hello.c 程序：

#include?

int?main()
{
????printf("hello,?world\n");
????return?0;
}

在 Unix 系統(tǒng)上，由編譯器把源文件轉(zhuǎn)換為目標(biāo)文件。

gcc?-o?hello?hello.c

這個(gè)過(guò)程大致如下：

預(yù)處理階段：處理以 # 開頭的預(yù)處理命令；

編譯階段：翻譯成匯編文件；

匯編階段：將匯編文件翻譯成可重定位目標(biāo)文件；

鏈接階段：將可重定位目標(biāo)文件和 printf.o 等單獨(dú)預(yù)編譯好的目標(biāo)文件進(jìn)行合并，得到最終的可執(zhí)行目標(biāo)文件。

靜態(tài)鏈接

靜態(tài)鏈接器以一組可重定位目標(biāo)文件為輸入，生成一個(gè)完全鏈接的可執(zhí)行目標(biāo)文件作為輸出。鏈接器主要完成以下兩個(gè)任務(wù)：

• 符號(hào)解析：每個(gè)符號(hào)對(duì)應(yīng)于一個(gè)函數(shù)、一個(gè)全局變量或一個(gè)靜態(tài)變量，符號(hào)解析的目的是將每個(gè)符號(hào)引用與一個(gè)符號(hào)定義關(guān)聯(lián)起來(lái)。

• 重定位：鏈接器通過(guò)把每個(gè)符號(hào)定義與一個(gè)內(nèi)存位置關(guān)聯(lián)起來(lái)，然后修改所有對(duì)這些符號(hào)的引用，使得它們指向這個(gè)內(nèi)存位置。

目標(biāo)文件

• 可執(zhí)行目標(biāo)文件：可以直接在內(nèi)存中執(zhí)行；

• 可重定位目標(biāo)文件：可與其它可重定位目標(biāo)文件在鏈接階段合并，創(chuàng)建一個(gè)可執(zhí)行目標(biāo)文件；

• 共享目標(biāo)文件：這是一種特殊的可重定位目標(biāo)文件，可以在運(yùn)行時(shí)被動(dòng)態(tài)加載進(jìn)內(nèi)存并鏈接；

動(dòng)態(tài)鏈接

靜態(tài)庫(kù)有以下兩個(gè)問(wèn)題：

• 當(dāng)靜態(tài)庫(kù)更新時(shí)那么整個(gè)程序都要重新進(jìn)行鏈接；

• 對(duì)于 printf 這種標(biāo)準(zhǔn)函數(shù)庫(kù)，如果每個(gè)程序都要有代碼，這會(huì)極大浪費(fèi)資源。

共享庫(kù)是為了解決靜態(tài)庫(kù)的這兩個(gè)問(wèn)題而設(shè)計(jì)的，在 Linux 系統(tǒng)中通常用 .so 后綴來(lái)表示，Windows 系統(tǒng)上它們被稱為 DLL。它具有以下特點(diǎn)：

• 在給定的文件系統(tǒng)中一個(gè)庫(kù)只有一個(gè)文件，所有引用該庫(kù)的可執(zhí)行目標(biāo)文件都共享這個(gè)文件，它不會(huì)被復(fù)制到引用它的可執(zhí)行文件中；

• 在內(nèi)存中，一個(gè)共享庫(kù)的 .text 節(jié)（已編譯程序的機(jī)器代碼）的一個(gè)副本可以被不同的正在運(yùn)行的進(jìn)程共享。

六、死鎖

必要條件

• 互斥：每個(gè)資源要么已經(jīng)分配給了一個(gè)進(jìn)程，要么就是可用的。

• 占有和等待：已經(jīng)得到了某個(gè)資源的進(jìn)程可以再請(qǐng)求新的資源。

• 不可搶占：已經(jīng)分配給一個(gè)進(jìn)程的資源不能強(qiáng)制性地被搶占，它只能被占有它的進(jìn)程顯式地釋放。

• 環(huán)路等待：有兩個(gè)或者兩個(gè)以上的進(jìn)程組成一條環(huán)路，該環(huán)路中的每個(gè)進(jìn)程都在等待下一個(gè)進(jìn)程所占有的資源。

處理方法

主要有以下四種方法：

• 鴕鳥策略

• 死鎖檢測(cè)與死鎖恢復(fù)

• 死鎖預(yù)防

• 死鎖避免

鴕鳥策略

把頭埋在沙子里，假裝根本沒(méi)發(fā)生問(wèn)題。

因?yàn)榻鉀Q死鎖問(wèn)題的代價(jià)很高，因此鴕鳥策略這種不采取任務(wù)措施的方案會(huì)獲得更高的性能。

當(dāng)發(fā)生死鎖時(shí)不會(huì)對(duì)用戶造成多大影響，或發(fā)生死鎖的概率很低，可以采用鴕鳥策略。

大多數(shù)操作系統(tǒng)，包括 Unix，Linux 和 Windows，處理死鎖問(wèn)題的辦法僅僅是忽略它。

死鎖檢測(cè)與死鎖恢復(fù)

不試圖阻止死鎖，而是當(dāng)檢測(cè)到死鎖發(fā)生時(shí)，采取措施進(jìn)行恢復(fù)。

1. 每種類型一個(gè)資源的死鎖檢測(cè)

上圖為資源分配圖，其中方框表示資源，圓圈表示進(jìn)程。資源指向進(jìn)程表示該資源已經(jīng)分配給該進(jìn)程，進(jìn)程指向資源表示進(jìn)程請(qǐng)求獲取該資源。

圖 a 可以抽取出環(huán)，如圖 b，它滿足了環(huán)路等待條件，因此會(huì)發(fā)生死鎖。

每種類型一個(gè)資源的死鎖檢測(cè)算法是通過(guò)檢測(cè)有向圖是否存在環(huán)來(lái)實(shí)現(xiàn)，從一個(gè)節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，對(duì)訪問(wèn)過(guò)的節(jié)點(diǎn)進(jìn)行標(biāo)記，如果訪問(wèn)了已經(jīng)標(biāo)記的節(jié)點(diǎn)，就表示有向圖存在環(huán)，也就是檢測(cè)到死鎖的發(fā)生。

2. 每種類型多個(gè)資源的死鎖檢測(cè)

上圖中，有三個(gè)進(jìn)程四個(gè)資源，每個(gè)數(shù)據(jù)代表的含義如下：

• E 向量：資源總量

• A 向量：資源剩余量

• C 矩陣：每個(gè)進(jìn)程所擁有的資源數(shù)量，每一行都代表一個(gè)進(jìn)程擁有資源的數(shù)量

• R 矩陣：每個(gè)進(jìn)程請(qǐng)求的資源數(shù)量

進(jìn)程 P1 和 P2 所請(qǐng)求的資源都得不到滿足，只有進(jìn)程 P3 可以，讓 P3 執(zhí)行，之后釋放 P3 擁有的資源，此時(shí) A = (2 2 2 0)。P2 可以執(zhí)行，執(zhí)行后釋放 P2 擁有的資源，A = (4 2 2 1) 。P1 也可以執(zhí)行。所有進(jìn)程都可以順利執(zhí)行，沒(méi)有死鎖。

算法總結(jié)如下：

每個(gè)進(jìn)程最開始時(shí)都不被標(biāo)記，執(zhí)行過(guò)程有可能被標(biāo)記。當(dāng)算法結(jié)束時(shí)，任何沒(méi)有被標(biāo)記的進(jìn)程都是死鎖進(jìn)程。

尋找一個(gè)沒(méi)有標(biāo)記的進(jìn)程 Pi，它所請(qǐng)求的資源小于等于 A。

如果找到了這樣一個(gè)進(jìn)程，那么將 C 矩陣的第 i 行向量加到 A 中，標(biāo)記該進(jìn)程，并轉(zhuǎn)回 1。

如果沒(méi)有這樣一個(gè)進(jìn)程，算法終止。

3. 死鎖恢復(fù)

• 利用搶占恢復(fù)

• 利用回滾恢復(fù)

• 通過(guò)殺死進(jìn)程恢復(fù)

死鎖預(yù)防

在程序運(yùn)行之前預(yù)防發(fā)生死鎖。

1. 破壞互斥條件

例如假脫機(jī)打印機(jī)技術(shù)允許若干個(gè)進(jìn)程同時(shí)輸出，唯一真正請(qǐng)求物理打印機(jī)的進(jìn)程是打印機(jī)守護(hù)進(jìn)程。

2. 破壞占有和等待條件

一種實(shí)現(xiàn)方式是規(guī)定所有進(jìn)程在開始執(zhí)行前請(qǐng)求所需要的全部資源。

3. 破壞不可搶占條件

4. 破壞環(huán)路等待

給資源統(tǒng)一編號(hào)，進(jìn)程只能按編號(hào)順序來(lái)請(qǐng)求資源。

死鎖避免

在程序運(yùn)行時(shí)避免發(fā)生死鎖。

1. 安全狀態(tài)

圖 a 的第二列 Has 表示已擁有的資源數(shù)，第三列 Max 表示總共需要的資源數(shù)，F(xiàn)ree 表示還有可以使用的資源數(shù)。從圖 a 開始出發(fā)，先讓 B 擁有所需的所有資源（圖 b），運(yùn)行結(jié)束后釋放 B，此時(shí) Free 變?yōu)?5（圖 c）；接著以同樣的方式運(yùn)行 C 和 A，使得所有進(jìn)程都能成功運(yùn)行，因此可以稱圖 a 所示的狀態(tài)時(shí)安全的。

定義：如果沒(méi)有死鎖發(fā)生，并且即使所有進(jìn)程突然請(qǐng)求對(duì)資源的最大需求，也仍然存在某種調(diào)度次序能夠使得每一個(gè)進(jìn)程運(yùn)行完畢，則稱該狀態(tài)是安全的。

安全狀態(tài)的檢測(cè)與死鎖的檢測(cè)類似，因?yàn)榘踩珷顟B(tài)必須要求不能發(fā)生死鎖。下面的銀行家算法與死鎖檢測(cè)算法非常類似，可以結(jié)合著做參考對(duì)比。

2. 單個(gè)資源的銀行家算法

一個(gè)小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，算法要做的是判斷對(duì)請(qǐng)求的滿足是否會(huì)進(jìn)入不安全狀態(tài)，如果是，就拒絕請(qǐng)求；否則予以分配。

上圖 c 為不安全狀態(tài)，因此算法會(huì)拒絕之前的請(qǐng)求，從而避免進(jìn)入圖 c 中的狀態(tài)。

3. 多個(gè)資源的銀行家算法

上圖中有五個(gè)進(jìn)程，四個(gè)資源。左邊的圖表示已經(jīng)分配的資源，右邊的圖表示還需要分配的資源。最右邊的 E、P 以及 A 分別表示：總資源、已分配資源以及可用資源，注意這三個(gè)為向量，而不是具體數(shù)值，例如 A=(1020)，表示 4 個(gè)資源分別還剩下 1/0/2/0。

檢查一個(gè)狀態(tài)是否安全的算法如下：

• 查找右邊的矩陣是否存在一行小于等于向量 A。如果不存在這樣的行，那么系統(tǒng)將會(huì)發(fā)生死鎖，狀態(tài)是不安全的。

• 假若找到這樣一行，將該進(jìn)程標(biāo)記為終止，并將其已分配資源加到 A 中。

• 重復(fù)以上兩步，直到所有進(jìn)程都標(biāo)記為終止，則狀態(tài)時(shí)安全的。

如果一個(gè)狀態(tài)不是安全的，需要拒絕進(jìn)入這個(gè)狀態(tài)。