進程

進程的概念：進程是動態(tài)的，是程序的一次執(zhí)行過程。進程實體（進程映像）是靜態(tài)的

進程的幾個特性

動態(tài)性是指進程是程序的一次執(zhí)行過程，是動態(tài)的產(chǎn)生、變化和消亡的

并發(fā)性是指內(nèi)存中的多個進程實體，進程可并發(fā)的執(zhí)行

獨立性是指進程獨立運行、獨立獲取資源、獨立接受調(diào)度

異步性是指進程按照各自獨立、不可預(yù)知的速度推進，操作系統(tǒng)提供“進程同步機制”解決異步問題

結(jié)構(gòu)性指每個進程都有一個PCB，由程序段和數(shù)據(jù)段、PCB構(gòu)成。

?

進程的基本狀態(tài)

創(chuàng)建態(tài)、就緒態(tài)、運行態(tài)、阻塞態(tài)、終止態(tài)

運行、就緒、阻塞

運行狀態(tài)：有CPU和其他資源

就緒狀態(tài)：無CPU，有其他資源

阻塞態(tài)：無CPU，無其他資源

?

就緒態(tài)到運行態(tài)：進程被調(diào)度

運行態(tài)到就緒態(tài)：時間片到了，CPU被高優(yōu)先級進程搶占

運行態(tài)到阻塞態(tài)：等待系統(tǒng)資源的分配，或者等待某種事件發(fā)生（主動行為）

阻塞態(tài)到就緒態(tài)：資源分配到位，等待的事件發(fā)生（被動行為）

?

進程的控制：進程控制就是要實現(xiàn)進程狀態(tài)的轉(zhuǎn)換，用原語實現(xiàn)。

原語是一種特殊的程序，執(zhí)行具有原子性，就是說一氣呵成，不可中斷?？梢允褂藐P(guān)中斷和開中斷兩條特權(quán)指令是實現(xiàn)原子性。

?

創(chuàng)建原語：先申請空白PCB，再為新進程分配需要的資源，再初始化PCB，最后將PCB插入就緒隊列。

引起創(chuàng)建的事件有用戶登錄、作業(yè)調(diào)度、提供服務(wù)、應(yīng)用請求

?

撤銷原語：先從PCB集合中找到終止進程的PCB，進程正在運行，則立刻剝奪CPU，并將CPU分配給其他進程，并終止其所有的子進程（進程間的關(guān)系是樹形結(jié)構(gòu)），再將該進程所擁有的資源歸還給父進程或者操作系統(tǒng)，再將其PVB刪除。

引起進程終止的事件有正常結(jié)束（exit系統(tǒng)調(diào)用）、異常結(jié)束（整數(shù)除以0，非法使用特權(quán)指令）、外界干預(yù)（用戶自己殺掉）

?

阻塞原語和喚醒原語（需要成對使用）

阻塞原語：需要找到對應(yīng)的PCB，保護進程運行的現(xiàn)場，將PCB狀態(tài)信息設(shè)置為阻塞態(tài)，暫停進程運行，并將PCB插入等待隊列。

喚醒原語：需要在等待隊列中找到PCB，將PCB從等待隊列移除，將進程設(shè)置為就緒態(tài)。

?

切換原語（運行到就緒-就緒到運行）：先將運行環(huán)境信息（進程上下文）存入PCB，PCB移入相關(guān)的隊列，選擇另一個進程執(zhí)行，并更新其PCB，根據(jù)PCB恢復(fù)新進程所需的運行環(huán)境。

?

無論哪個進程控制原語，要做的無非三類事情：

更新PCB中的信息、將PCB插入合適的隊列、分配回收資源。

?

進程的組織方式：鏈式方式和索引方式

鏈式方式將按照狀態(tài)分為多個隊列，操作系統(tǒng)持有指向各個隊列的指針。

索引方式將按照進程狀態(tài)的不同，建立幾張索引表，操作系統(tǒng)持有指向各個索引表的指針。

?

進程的組成：PCB、程序段、數(shù)據(jù)段

PCB指的是進程描述信息（PID）、進程控制和管理信息、資源分配清單、處理機相關(guān)信息，他是給操作系統(tǒng)用的。

程序段指的是程序的代碼

數(shù)據(jù)段指的是運行中的各種數(shù)據(jù)，如定義的變量

程序段和數(shù)據(jù)段是進程自己用的

?

進程間的通信：共享存儲、消息傳遞、管道通信

共享存儲是指設(shè)置一個共享內(nèi)存的區(qū)域，并映射到進程的虛擬地址空間。共享空間互斥訪問（由進程自己互斥實現(xiàn)），采用基于數(shù)據(jù)結(jié)構(gòu)和基于存儲區(qū)的共享兩種方式實現(xiàn)。

消息傳遞傳遞結(jié)構(gòu)化的消息，系統(tǒng)提供發(fā)送和接受原語，采用直接通信方式和間接通信方式（信箱）

管道通信設(shè)置一個特殊的共享文件（管道），本質(zhì)上是內(nèi)存緩存區(qū)，一個管道只能半雙工通信，全雙工需要2個管道，各個進程互斥訪問管道（由操作系統(tǒng)實現(xiàn)），管道滿時，寫進程阻塞，管道空時，讀進程阻塞。

管道相比共享存儲優(yōu)勢在于可以允許一邊寫入，另一邊讀出，只要沒空就能讀，沒滿就能寫。

?

線程

線程的概念

線程是基本的CPU執(zhí)行單元，是程序執(zhí)行流的最小基本單位，各個線程之間可以并發(fā)，提升了系統(tǒng)的并發(fā)度。進程只作為除了CPU以外的系統(tǒng)資源分配單元，線程作為處理機的分配單元。也就是說，進程是資源分配的基本單位，線程是調(diào)度的基本單位。

引入線程后，并發(fā)性提高，系統(tǒng)開銷減小。

?

線程的實現(xiàn)方式：用戶級線程和內(nèi)核級線程

多線程模型分為一對一模型、多對一模型、多對多模型

一對一模型指的是用戶級線程對應(yīng)一個內(nèi)核級線程

優(yōu)點是各個線程分配到多核處理機并行執(zhí)行，并發(fā)度高

缺點是需要操作系統(tǒng)支持，開銷大

多對一模型指多個用戶線程映射到一個內(nèi)核級線程

優(yōu)點是線程管理的開銷小，缺點是并發(fā)度低，一個線程阻塞導(dǎo)致整個進程都阻塞

多對多模型指n個用戶級線程映射到m個內(nèi)核級線程，n>=m，他吸收了兩者的優(yōu)點。

內(nèi)核級線程才是處理機分配的單位

?

線程的組織與控制

主要由TCB（線程控制塊）和線程表

TCB內(nèi)容包含線程標識符（TID），程序計數(shù)器PC，其他寄存器，堆棧指針，線程運行狀態(tài)，優(yōu)先級。PC、寄存器，堆棧指針需要在進程調(diào)度時進行保存與恢復(fù)。

?

CPU調(diào)度

CPU三級調(diào)度：高級調(diào)度（作業(yè)調(diào)度）、低級調(diào)度（處理機調(diào)度）、中級調(diào)度（內(nèi)存調(diào)度）

高級調(diào)度是從外存的作業(yè)后備隊列中挑出一個作業(yè)調(diào)入內(nèi)存，并創(chuàng)建進程。每個作業(yè)只調(diào)入一次，調(diào)出一次。

低級調(diào)度是從就緒隊列中選取一個進程，將處理機分配，是操作系統(tǒng)中最基本的一種調(diào)度，頻率很高。

中級調(diào)度是內(nèi)存不夠時，將進程的數(shù)據(jù)調(diào)出外存，并設(shè)置為掛起狀態(tài)，被掛起的進程會組織成掛起隊列。中級調(diào)度則是按照某種策略，將掛起狀態(tài)的進程重新調(diào)入內(nèi)存。

?

調(diào)度的時機

可以進行調(diào)度的情況：

進程主動放棄處理機：進程正常終止，，發(fā)生異常而終止，主動請求阻塞

進程被動放棄處理機：分配的時間片用完，有更緊急的事情處理，有更高優(yōu)先級的進程進入就緒隊列

不能調(diào)度與切換的情況：

處理中斷的過程中，中斷處理過程復(fù)雜，很難切換。

在操作系統(tǒng)的內(nèi)核臨界區(qū)中。一般是訪問某種內(nèi)核數(shù)據(jù)結(jié)構(gòu)，普通的臨界區(qū)可以調(diào)度切換

在原子操作過程中，不可中斷。

進程切換是有代價的，過于頻繁切換調(diào)度會降低系統(tǒng)效率。

調(diào)度方式：非剝奪調(diào)度和剝奪調(diào)度（非搶占和搶占）

調(diào)度器/調(diào)度程序：決定調(diào)度算法和時間片大小。

在創(chuàng)建新進程、進程退出、進程阻塞、IO中斷發(fā)生時

?

閑逛進程：沒有其他就緒進程時運行閑逛進程（抖腿）

優(yōu)點級最低、可以是0地址指令、能耗低。

?

調(diào)度算法

CPU利用率：指CPU忙碌的時間占總時間的比例

利用率

系統(tǒng)吞吐量：指單位時間內(nèi)完成作業(yè)的數(shù)量

吞吐量

周轉(zhuǎn)時間：指作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止這段時間間隔

周轉(zhuǎn)時間 = 作業(yè)完成時間-作業(yè)提交時間

平均周轉(zhuǎn)時間

帶權(quán)周轉(zhuǎn)時間 = ，必然>=1

平均帶權(quán)周轉(zhuǎn)時間 =

?

等待時間：指進程和作業(yè)處于等待處理機狀態(tài)時間之和

等待時間 = 周轉(zhuǎn)時間-運行時間-IO時間

對于進程來說，等待時間就是指進程建立后等待被服務(wù)的時間之和。

對于作業(yè)來說，處理進程后的等待時間，還要加上作業(yè)在外存后備隊列等待的時間

?

響應(yīng)時間：指用戶提交請求到首次相應(yīng)所用的時間

?

先來先服務(wù)（FCFS）、短作業(yè)優(yōu)先（SJF）、高響應(yīng)比優(yōu)先（HRRN）

主要思考算法思想、算法規(guī)則、是用于作業(yè)調(diào)度還是進程調(diào)度、搶占式還是非搶占式、優(yōu)點和缺點、是否會饑餓

先來先服務(wù)：

從公平角度，按照作業(yè)到達的先后順序進行服務(wù)，作業(yè)調(diào)度和進程調(diào)度都可用，是非搶占式的算法。優(yōu)點是公平簡單，缺點是對長作業(yè)有利，對短作業(yè)不利。不會導(dǎo)致饑餓。

短作業(yè)優(yōu)先：

追求最少的平均等待時間、平均周轉(zhuǎn)時間。最短的作業(yè)/進程先得到服務(wù)，即可用在作業(yè)調(diào)度，也可用在進程調(diào)度。是非搶占的算法，但是也有搶占式版本的，即最短剩余時間優(yōu)先算法。每次調(diào)度選擇當前已到達的并且運行時間最短的作業(yè)。優(yōu)點是對短作業(yè)有利，對長作業(yè)不利，會產(chǎn)生饑餓現(xiàn)象。如果一直得不到服務(wù)，則稱為餓死。

在搶占式的短作業(yè)優(yōu)先算法中，每當一個新的進程進入隊列中時，需要進行一次調(diào)度，如果新到達的進程剩余時間比當前運行的進程剩余時間短，則搶占處理機，當前進程回到就緒隊列，完成一個進程時也需要進行調(diào)度。

如果題目未說明，則默認是非搶占式的。

高響應(yīng)比優(yōu)先：

綜合考慮作業(yè)和進程的等待時間和要求服務(wù)的時間。每次調(diào)度時計算各個作業(yè)/進程的響應(yīng)比，選擇響應(yīng)比最高的作業(yè)/進程。既可以用在進程調(diào)度，也可以用在作業(yè)調(diào)度。是非搶占式的算法。綜合了前兩個算法的優(yōu)先，不會產(chǎn)生饑餓。

響應(yīng)比 = ，響應(yīng)比>=1

每次作業(yè)完成時進行調(diào)度，主動放棄CPU調(diào)度，計算所有就緒進程的響應(yīng)比，選擇響應(yīng)比最高的進程上處理機。

?

這三種算法適用于早期的批處理系統(tǒng)，對用戶來說交互性很差。

?

l?時間片輪轉(zhuǎn)調(diào)度算法、優(yōu)先級調(diào)度算法、多級反饋隊列調(diào)度算法。

l?時間片輪轉(zhuǎn)算法

時間片輪轉(zhuǎn)調(diào)度算法的算法思想是每個進程都能公平的得到服務(wù)，輪流按照各個進程執(zhí)行時間片，如果進程在一個時間片內(nèi)沒有做完的話，則會剝奪處理機，并將進程重新放回就緒隊列隊尾重新排隊。時間片輪轉(zhuǎn)用于進程調(diào)度。因為只有作業(yè)放入內(nèi)存并且建立相應(yīng)的進程后，才能分配處理機時間片。該算法為搶占式的算法，由時鐘控制裝置發(fā)出時鐘中斷來通知時間片已到。該算法常用于分時操作系統(tǒng)，更注重響應(yīng)時間，不計算周轉(zhuǎn)時間。

具體情況下，設(shè)置時間片的大小為2，如果在某一時刻一個進程下處理機，同時一個新進程到達，則默認該新進程先進入就緒隊列，下來的進程則放在該新進程后面。

每當有新進程到時，將該進程插在就緒隊列的末尾。

如果運行中的進程所剩的時間片沒用完，運行完了后也會放棄處理機，并進行一次調(diào)度。

時間片輪轉(zhuǎn)算法不會導(dǎo)致饑餓。

優(yōu)點是公平，相應(yīng)快，適用于分時操作系統(tǒng)

缺點是高頻率的切換，會有一定的開銷。而且不會區(qū)分任務(wù)的緊急程度。

?

l?優(yōu)先級調(diào)度算法

優(yōu)先級調(diào)度算法的算法是為了根據(jù)任務(wù)的緊急程度來決定處理次序。

每個任務(wù)/進程都有各自的優(yōu)先級，調(diào)度時選擇優(yōu)先級最高的作業(yè)/進程。

既可以用于作業(yè)調(diào)度，也可以用于進程調(diào)度。甚至可以用在I/O調(diào)度當中。

是搶占式、非搶占式兩種都有。兩者的區(qū)別在于，非搶占式只需在進程主動放棄處理機時進行調(diào)度即可。搶占式還需要在就緒隊列變化時，檢查是否會發(fā)生搶占。

在非搶占式的算法中，進程會一次性執(zhí)行完。在調(diào)度的時候，會根據(jù)到達進程的優(yōu)先級進行調(diào)度，優(yōu)點級最大優(yōu)先調(diào)度。當優(yōu)先級相同的時候，則調(diào)度先到的進程。

在搶占式的算法中，當進程主動放棄處理機的時候進行一次調(diào)度，同時，當就緒隊列變化的時候也會檢查是否搶占。

在優(yōu)先級調(diào)度算法中，優(yōu)先級分為靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級。

靜態(tài)優(yōu)先級在創(chuàng)建進程的時候確定，之后則一直不變。

動態(tài)優(yōu)先級則是有一個初始值，根據(jù)情況動態(tài)地調(diào)整優(yōu)先級。

在優(yōu)先級的設(shè)置上，系統(tǒng)進程優(yōu)先級大于用戶進程，前臺進程的優(yōu)先級大于后臺進程。操作系統(tǒng)更偏好I/O型進程，與其相對的是CPU型進程。

在優(yōu)先級的調(diào)整上，如果某個進程在就緒隊列中等了太長時間，則可以適當提高一些優(yōu)先級。占用處理機過久的進程，會降低優(yōu)先級。頻繁進行I/O操作的進程，可以適當提升優(yōu)先級

優(yōu)先級調(diào)度算法的優(yōu)點是用優(yōu)先級區(qū)分緊急和重要程度，適用于實時操作系統(tǒng)。可以靈活調(diào)整各種作業(yè)/進程的偏好程度。缺點是如果有源源不斷的高優(yōu)先級的進程進來，則會導(dǎo)致饑餓。

優(yōu)先級調(diào)度算法會導(dǎo)致饑餓。

?

l?多級隊列反饋算法

多級隊列反饋算法是對其他調(diào)度算法的折中平衡。

多級隊列反饋算法將設(shè)置多級就緒隊列。各級隊列的優(yōu)先級從高到低，時間片從小到大。

新的進程到達是進入第一級隊列，按照先來先服務(wù)的原則，排隊等待時間片。若用完時間片進程還未結(jié)束，則進入下一級的隊列，如果已經(jīng)是最下級的隊列了，則將該進程放回該隊列隊尾。

只有k級隊列為空時，才能為k+1級隊列分配時間片。

該算法是搶占式的算法。在k級隊列進程運行過程中，若更上級（0-k-1）的隊列進入了一個新進程，新進程會搶占處理機，原來運行的進程會放回k級隊列隊尾。

優(yōu)點是對各類型的進程相對公平，每個新到達的進程都能快速得到相應(yīng)。短進程只用較少時間就能完成，不必實現(xiàn)估計進程的運行時間（避免用戶作假），可以靈活地調(diào)整各類進程的偏好程度。比如CPU密集型進程，I/O密集型進程。比如將因I/O阻塞的進程放回原隊列，使得保持較高的優(yōu)先級。

該算法會導(dǎo)致饑餓。

?

以上三種算法都適用于交互式系統(tǒng)

?

進程優(yōu)先級排序：系統(tǒng)進程（內(nèi)存管理進程）>交互式進程（游戲，打字軟件）>批處理進程（AI訓(xùn)練模型等）

?

?

?

上下文切換

上下文的概念

進程上下文的切換實際就是任務(wù)切換。當處理器決定運行其他任務(wù)時，需要保存該運行任務(wù)的狀態(tài)，也就是CPU處理器的全部內(nèi)容

同步與互斥（PV）

臨界資源和臨界區(qū)

臨界區(qū)是指的是訪問臨界資源的那段代碼

對于臨界資源的訪問，需要互斥的進行

需要遵守的原則：空閑讓進，也就是說臨界區(qū)空閑時，應(yīng)該允許一個進程訪問。忙則等待，臨界區(qū)正在被訪問時，其他試圖訪問的進程需要等待。有限等待，要在有限的時間內(nèi)進入臨界區(qū)，保證不會饑餓。讓權(quán)等待，進不了臨界區(qū)的進程要釋放處理機，防止忙等。

?

同步機制規(guī)則

單標志法，雙標志先檢查法，雙標志后檢查法，Peterson算法

單標志法在進入?yún)^(qū)只檢查，不上鎖。在退出區(qū)把臨界資源的使用權(quán)轉(zhuǎn)交給另一個進程。不遵守空閑讓進的原則。

雙標志先檢查法在進入?yún)^(qū)檢查后上鎖，退出區(qū)解鎖。不遵守忙則等待的原則。

雙標志后檢查法在進入?yún)^(qū)先加鎖后檢查，退出區(qū)解鎖。不遵守空閑讓進，有限等待的原則，可能導(dǎo)致饑餓。

Peterson算法在進入?yún)^(qū)主動謙讓，不遵循讓權(quán)等待的原則，會發(fā)生忙等。

硬件同步機制

中斷屏蔽方法、TestAndSet方法、Swap指令

中斷屏蔽方法使用開關(guān)中斷指令實現(xiàn)，簡單高效，只適用于單處理機。只適用于操作系統(tǒng)內(nèi)核進程。

Ts方法和swap方法通過old記錄是否已被上鎖，再將lock設(shè)置為true，檢查臨界區(qū)是否已被上鎖（若已被上鎖，則循環(huán)重復(fù)前幾步）優(yōu)點是實現(xiàn)簡單，適用于多處理機環(huán)境。缺點是不滿足讓權(quán)等待。

互斥鎖

在進入臨界區(qū)時獲得鎖，在推出臨界區(qū)時釋放鎖。缺點是忙等待，當其中一個進程在臨界區(qū)時，其他進程會連續(xù)調(diào)用acquire（）?；コ怄i適用于多處理機系統(tǒng)，一個線程可以在一個處理器上運行，不會影響其他進程的執(zhí)行。需要連續(xù)循環(huán)忙等的互斥鎖，都可以稱為自旋鎖。

信號量機制

用戶可以通過操作系統(tǒng)的一對原語來對信號量進行操作。信號量是一個變量，表示系統(tǒng)中某種資源的數(shù)量。一對原語：wait和signal也就是俗稱的PV操作。

在整型信號量的操作只有三種，初始化，P，V，存在的問題是不滿足讓權(quán)等待的原則，會發(fā)生忙等。

記錄型信號量用記錄型數(shù)據(jù)結(jié)構(gòu)表示信號量。記錄型信號量在資源不夠時，使得進程進入阻塞隊列。在釋放資源時將喚醒阻塞隊列的一個進程。該機制遵循了讓權(quán)等待的原則

S.Value表示某種資源數(shù)，S.L表示等待該資源的隊列

在P操作中，先value--，再執(zhí)行block原語

在V操作中，先value++，再執(zhí)行wakeup原語

可以用記錄型信號量實現(xiàn)系統(tǒng)資源的申請和釋放

可以用記錄型信號量實現(xiàn)進程互斥、進程同步

?

信號量機制

實現(xiàn)互斥方法：

分析并發(fā)進程的關(guān)鍵活動，劃定臨界區(qū)

設(shè)置互斥信號量mutex，初值為1

在進入?yún)^(qū)申請資源，在退出區(qū)釋放資源

對不同的臨界資源需要設(shè)置不同的信號量

P、V操作必須成對出現(xiàn)

?

實現(xiàn)同步方法：

分析什么地方需要實現(xiàn)同步關(guān)系，保證一前一后的兩個順序。

設(shè)置同步信號量S，初值為0

在前操作之后執(zhí)行V（S）

在后操作之前執(zhí)行P（S）

信號量S代表某種資源，剛開始是沒有這種資源的，P2需要這種資源，而這種資源只能由P1產(chǎn)生。

?

實現(xiàn)前驅(qū)關(guān)系

畫出前驅(qū)圖，把每個前驅(qū)關(guān)系看成一個同步問題

為每一對前驅(qū)關(guān)系各設(shè)置一個同步信號量

在前操作后對相應(yīng)的同步信號量執(zhí)行V操作

在后操作之前對相應(yīng)的同步信號量執(zhí)行P操作

?

管程

為什么要引入管程：解決復(fù)雜的PV操作

管程的定義

是一種特殊的軟件模塊

局部于管程的共享數(shù)據(jù)結(jié)構(gòu)說明

對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程（函數(shù)）

局部于管程的共享數(shù)據(jù)設(shè)置初始值的語句

有一個名字

每次僅允許一個進程在管程內(nèi)執(zhí)行某個內(nèi)部過程

?

需要在管程中定義共享數(shù)據(jù)，用于訪問該共享數(shù)據(jù)的入口。通過這些特定的入口才能訪問共享數(shù)據(jù)。管程有很多入口，每次只能開放其中一個入口，只能讓一個線程或進程進入?；コ馓匦允怯删幾g器負責(zé)實現(xiàn)的，可以在管程中設(shè)置條件變量及等待/喚醒操作以解決同步問題。

?

經(jīng)典的同步問題:

生產(chǎn)者消費者問題

多消費者問題

吸煙者問題

讀者寫者問題

哲學(xué)家進餐問題

?

死鎖

死鎖的原因

互相等待對方的資源，導(dǎo)致各進程都阻塞，都無法向前推進

死鎖一定是至少有兩個或者兩個的進程同時發(fā)生死鎖

饑餓是可能只有一個進程發(fā)生饑餓

死鎖和饑餓是操作系統(tǒng)的問題，死循環(huán)是管理者的問題

?

死鎖的必要條件

互斥條件：必須對互斥使用的資源爭搶才會導(dǎo)致死鎖

不剝奪條件：在資源未使用完之前，不能由其他進程強行奪走，只能主動釋放。

請求和保持條件：已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源被其他進程所占用，又對自己有的資源保持不放。

循環(huán)等待條件：存在一種資源的循環(huán)等待鏈，鏈中的進程已獲得的資源同時又被下一個進程所請求

發(fā)生死鎖一定是有循環(huán)等待，但是發(fā)生循環(huán)等待未必死鎖。

發(fā)生死鎖的條件：

對系統(tǒng)資源的爭奪、進程推進順序非法、信號量的使用不當

?

死鎖的處理方法

預(yù)防死鎖：破壞死鎖四個必要條件中的一個或幾個

避免死鎖：用某種方法防止系統(tǒng)進入不安全狀態(tài)。從而避免死鎖

死鎖的檢測和解除：允許死鎖的發(fā)生，操作系統(tǒng)會負責(zé)檢測死鎖的發(fā)生，然后采取某種辦法解除死鎖

?

不允許死鎖發(fā)生：靜態(tài)策略（預(yù)防死鎖）、動態(tài)策略（避免死鎖）

預(yù)防死鎖：

破壞互斥條件：將臨界資源改造為可共享使用的資源（spooling）

缺點是可行性不高，很多時候無法破壞互斥條件

破壞不剝奪條件：申請的資源得不到滿足的時候，立刻釋放所有的資源。申請的資源被其他進程占用時，由操作系統(tǒng)協(xié)助剝奪。

缺點是實現(xiàn)復(fù)雜，剝奪資源導(dǎo)致部分工作失效，反復(fù)申請和釋放導(dǎo)致系統(tǒng)開銷大，可能導(dǎo)致饑餓。

破壞請求和保持條件，運行前分配好所需要的資源，之后一起保持。缺點是資源利用率低，可能導(dǎo)致饑餓。

破壞循環(huán)和等待條件，給資源編號，必須按從小到大的順序申請資源。缺點是不方便增加新的設(shè)備，會導(dǎo)致資源浪費，用戶編程麻煩。

?

避免死鎖：

安全序列

安全序列是指系統(tǒng)按照這種序列分配資源，每個進程都能順利完成，只要找出一個安全序列，系統(tǒng)就是安全狀態(tài)，安全序列可能有多個。

系統(tǒng)處于安全狀態(tài)，一定不會發(fā)生死鎖，如果系統(tǒng)進入不安全狀態(tài)，未必會發(fā)生死鎖。

銀行家算法的核心思想是在資源分配前預(yù)先判定這次分配是否會導(dǎo)致系統(tǒng)進入不安全狀態(tài)。如果進入不安全狀態(tài)，則暫時不答應(yīng)這次請求，讓該進程先阻塞等待。

安全性算法的思想是先找出剩余可用資源能否滿足各進程的需求，如果可以則將該進程加入安全序列，并更新剩余可用資源，將該進程所持有的資源全部回收。不斷重復(fù)上述過程，看最終是否讓所有進程都加入安全序列。

假設(shè)系統(tǒng)有n個進程，m種資源。銀行家算法先建立最大需求矩陣MAX，已分配矩陣Allocation，需求矩陣Need，Max-Allocation=Need，還要建立長度為m的一維數(shù)組Available，表示系統(tǒng)還剩的可用資源。

進程P向系統(tǒng)請求資源時，用一個長度為m的一維數(shù)組Request，表示申請的各種資源量。用銀行家算法預(yù)判本次分配是否會導(dǎo)致系統(tǒng)進入不安全狀態(tài)。

如果Request<Need，便繼續(xù)，否則出錯。

如果Request<Available，便繼續(xù)，否則無可用資源，P需要等待

系統(tǒng)嘗試分配資源給P，并修改相應(yīng)數(shù)據(jù)。

執(zhí)行安全性算法，檢查此次分配后系統(tǒng)是否處于安全狀態(tài)，如果安全才正式分配，否則恢復(fù)相應(yīng)數(shù)據(jù)，讓P阻塞等待。

?

死鎖的檢測和解除：

死鎖檢測：用于檢測系統(tǒng)中是否發(fā)生了死鎖

用某種數(shù)據(jù)結(jié)構(gòu)保存資源的請求和分配信息

提供一種算法，利用上述信息檢測系統(tǒng)是否進入死鎖狀態(tài)。

兩種節(jié)點：進程節(jié)點和資源節(jié)點

兩種邊：進程節(jié)點-》資源節(jié)點：表示進程想申請幾個資源（每條邊一個）

資源節(jié)點-》進程節(jié)點：表示進程分配了幾個資源（每條邊一個）

能消除所有邊，則稱這個圖是可完全簡化的，一定沒有發(fā)生死鎖。

不能消除所有邊，那么就是發(fā)生了死鎖。

最終還連著的那些邊的那些進程就是處于死鎖狀態(tài)的進程

死鎖定理：如果某時刻系統(tǒng)的資源分配圖是不可完全簡化的，那么此時系統(tǒng)死鎖。

?

死鎖解除：認定系統(tǒng)發(fā)生了死鎖，利用該算法可以將系統(tǒng)從死鎖中解脫出來。

解除死鎖的辦法：

資源剝奪法：掛起某些死鎖進程，并將這些資源分配給其他死鎖進程。

撤銷進程法：強制撤銷部分甚至全部死鎖進程，剝奪該資源，實現(xiàn)簡單但是代價很大。

進程回退法：讓一個或者多個進程回退到足以避免死鎖的地步，要求系統(tǒng)記錄進程的歷史信息。