操作系統(tǒng)基本原理包含以下 5 大管理总放。

我們先來說說進(jìn)程管理蛤虐。

因?yàn)樘幚頇C(jī)是計(jì)算機(jī)系統(tǒng)的核心資源获印，所以整個(gè)操作系統(tǒng)的重心是處理機(jī)管理品山。

處理機(jī)管理中最基本的胆建、最重要的概念是進(jìn)程。進(jìn)程是系統(tǒng)并發(fā)執(zhí)行的體現(xiàn)肘交。

進(jìn)程控制塊 PCB 是進(jìn)程存在的唯一標(biāo)志涝登， PCB 描述了進(jìn)程的基本情況，具體內(nèi)容可分為調(diào)度信息和執(zhí)行信息兩大部分效诅。調(diào)度信息供進(jìn)程調(diào)度使用胀滚，包括進(jìn)程當(dāng)前的一些基本屬性 ; 執(zhí)行信息即現(xiàn)場，描述了進(jìn)程的執(zhí)行情況 填帽。 PCB 隨著進(jìn)程的建立而產(chǎn)生蛛淋，隨著進(jìn)程的完成而消亡。

順序程序是指程序中若干操作必須按照某種先后次序來執(zhí)行篡腌，并且每次操作前后的數(shù)據(jù)、狀態(tài)之間都有一定的關(guān)系勾效。早期的程序設(shè)計(jì)一般都是按順序執(zhí)行的嘹悼。

多道程序系統(tǒng)，有以下特點(diǎn)：

1. 資源共享层宫。這樣可以提高資源利用率杨伙，是由多道程序共用。
2. 并發(fā)執(zhí)行萌腿。允許一個(gè)用戶程序內(nèi)部完成不同操作的程序段之間并行運(yùn)行限匣；允許操作系統(tǒng)內(nèi)部不同的程序之間并行運(yùn)行。物理上講：內(nèi)存中保存多個(gè)程序毁菱，I/O 設(shè)備被多個(gè)程序交替地共享使用米死；在多處理機(jī)系統(tǒng)的情形下，表現(xiàn)為多個(gè)程序在各自的處理機(jī)上運(yùn)行贮庞，執(zhí)行時(shí)間是重疊的峦筒。單處
   理機(jī)系統(tǒng)時(shí)，程序的執(zhí)行表現(xiàn)為多道程序交替地在處理機(jī)上相互空插運(yùn)行窗慎。

程序的并行執(zhí)行和資源共享之間是相輔相成的：

1. 只有允許程序并行執(zhí)行物喷，才可能存在資源共享的問題卤材；
2. 只有有效地實(shí)現(xiàn)資源共享，才可能使得程序并行執(zhí)行峦失。

實(shí)際情況是：大多數(shù)程序段要求操作在時(shí)間上是有序的扇丛，也就是說有些操作必須在其他操作之前，但其中有些操作卻可以同時(shí)進(jìn)行尉辑，這時(shí)就可以采用并發(fā)操作晕拆。

1 進(jìn)程狀態(tài)轉(zhuǎn)換

由于進(jìn)程運(yùn)行的間斷性，決定了進(jìn)程至少具有以下三種狀態(tài)：

1. 就緒狀態(tài)材蹬。當(dāng)進(jìn)程已分配了除 CPU 以外的所有必要的資源后实幕，只要能再獲得處理機(jī)，便能立即執(zhí)行堤器，這時(shí)的進(jìn)程狀態(tài)就稱為就緒狀態(tài)昆庇。在一個(gè)系統(tǒng)中，可以有多個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)闸溃，通常把它們排成一列整吆，稱為就緒隊(duì)列。
2. 執(zhí)行狀態(tài)辉川。是指進(jìn)程已獲得處理機(jī)表蝙，正在執(zhí)行。在單處理機(jī)系統(tǒng)中乓旗，只能有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)府蛇。如果是多處理機(jī)，就可以多個(gè)進(jìn)程處于執(zhí)行狀態(tài)屿愚。
3. 阻塞狀態(tài)指進(jìn)程因發(fā)生某事件（如請求 I/O汇跨、申請緩沖空間等）而暫停執(zhí)行時(shí)的狀態(tài)，也就是說妆距，進(jìn)程的執(zhí)行受到了阻塞穷遂，也可以稱其為“等待”狀態(tài)或“睡眠”狀態(tài)。通常把它們排成一列娱据，稱為阻塞隊(duì)列蚪黑。

進(jìn)程的狀態(tài)會隨著自身的推進(jìn)或外界條件的變化而變化。

注意： 任何一個(gè)結(jié)束阻塞的進(jìn)程必須先變成就緒狀態(tài)沸伏，待分配到處理器后才能運(yùn)行。

2 掛起狀態(tài)

引入掛起狀態(tài)的原因：

1. 對換的需要动分。為了緩解內(nèi)存緊張毅糟，而將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程換至外存上，使進(jìn)程又處于一種有別于阻塞狀態(tài)的新狀態(tài)澜公。
2. 終端用戶的請求姆另。當(dāng)終端用戶在自己的程序運(yùn)行期間，發(fā)現(xiàn)有可疑問題時(shí)坟乾，往往希望使自己的進(jìn)程暫停下來迹辐。
3. 父進(jìn)程的請求。父進(jìn)程常常希望能掛起自己的子進(jìn)程甚侣，以便考查和修改子進(jìn)程明吩，或者協(xié)調(diào)各子進(jìn)程間的活動。
4. 負(fù)荷調(diào)節(jié)的需要殷费。當(dāng)實(shí)時(shí)系統(tǒng)中的工作負(fù)荷較重時(shí)印荔，有可能影響到對實(shí)時(shí)任務(wù)的控制，可由系統(tǒng)把一些不重要的進(jìn)程掛起详羡，以保證系統(tǒng)正常運(yùn)行仍律。
5. 操作系統(tǒng)的需要。操作系統(tǒng)希望掛起某些進(jìn)程实柠，以便檢查運(yùn)行中資源的使用情況及進(jìn)行記賬水泉。

掛起狀態(tài)有以下這些特性：

1. 原來處于就緒狀態(tài)的進(jìn)程，被掛起后主到，就進(jìn)入“靜止就緒” 狀態(tài)茶行；原來處于阻塞狀態(tài)的進(jìn)程，被掛起后登钥，就進(jìn)入“靜止阻塞” 狀態(tài)。
2. “靜止阻塞” 狀態(tài)的進(jìn)程娶靡，恢復(fù)后牧牢，進(jìn)入“活躍阻塞” 狀態(tài)。
3. 進(jìn)程可以由其自身掛起姿锭，也可由用戶或操作系統(tǒng)等對象將該進(jìn)程掛起塔鳍。其目的都在于阻止進(jìn)程繼續(xù)運(yùn)行，被掛起的進(jìn)程只能用顯式方式來激活呻此，以便從掛起狀態(tài)中解脫出來轮纫。
4. 靜止就緒態(tài)表明進(jìn)程具備運(yùn)行條件但目前在二級存儲器 ( 輔存 ) 中，只有當(dāng)它被對換到內(nèi)存時(shí)才能被調(diào)度執(zhí)行焚鲜。
5. 靜止阻塞態(tài)則表明進(jìn)程正在等待某一個(gè)事件且在二級存儲器中掌唾。

新的模型是把三態(tài)模型中的等待態(tài)改名為活躍阻塞態(tài)放前，就緒態(tài)改名為活躍就緒態(tài)，然后新增了與掛起相關(guān)的兩種狀態(tài)（靜止就緒態(tài)和靜止阻塞態(tài)）糯彬。

3 進(jìn)程互斥與同步

進(jìn)程互斥指的是：一組并發(fā)進(jìn)程中一個(gè)或多個(gè)程序段凭语，因共享某一共有資源而導(dǎo)致必須以互斥的方式訪問。也就是說撩扒，互斥指的是要保證臨界資源在某一時(shí)刻只被一個(gè)進(jìn)程訪問似扔。互斥即資源競爭關(guān)系。

進(jìn)程同步指的是：各進(jìn)程異步執(zhí)行搓谆，但必須按一定的制約順序和速度執(zhí)行炒辉。同步是進(jìn)程間協(xié)作關(guān)系。

臨界資源指的是：一次僅允許一個(gè)進(jìn)程使用的資源泉手。比如黔寇，物理設(shè)備如打印機(jī)、磁帶機(jī)等螃诅，某些軟件的變量啡氢、數(shù)據(jù)、表格等术裸。

臨界區(qū)指的是：一個(gè)進(jìn)程訪問臨界資源的那段程序代碼倘是。
進(jìn)程互斥加入臨界區(qū)概念之后，可以這樣描述：禁止兩個(gè)或兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入訪問同一臨界資源的臨界區(qū)袭艺。因此必須有專門的同步機(jī)制來協(xié)調(diào)它們搀崭。

協(xié)調(diào)準(zhǔn)則如下：

1. 空閑讓進(jìn) - 無進(jìn)程處于臨界區(qū)時(shí)，這時(shí)猾编，有進(jìn)程要求進(jìn)入臨界區(qū)瘤睹，則立即準(zhǔn)其進(jìn)入；
2. 忙則等待 - 當(dāng)已有進(jìn)程進(jìn)入其臨界區(qū)時(shí)答倡，其他試圖進(jìn)入該臨界區(qū)的進(jìn)程必須等待轰传，確保各進(jìn)程必須互斥地進(jìn)入臨界區(qū)；
3. 有限等待 - 有有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū)時(shí)瘪撇，應(yīng)該在有限的時(shí)間內(nèi)使某一進(jìn)程進(jìn)入臨界區(qū)获茬，而不是它們相互等待導(dǎo)致誰也進(jìn)不了臨界區(qū)；
4. 讓權(quán)等待 - 信號量可以有效地實(shí)現(xiàn)進(jìn)程的同步和互斥倔既。

在操作系統(tǒng)中恕曲，信號量是一個(gè)整數(shù)。當(dāng)信號量大于等于 0 時(shí)渤涌，代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)佩谣；當(dāng)信號量小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。建立一個(gè)信號量必須說明所建的信號量所代表的意義和設(shè)置初始值实蓬，以及建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)茸俭，以便指向那些等待使用該臨界區(qū)的進(jìn)程吊履。

信號量操作： P 操作和 V 操作。它們都是不可分割的原子操作瓣履，也稱為原語率翅。原語操作指的是，在執(zhí)行期間不允許發(fā)生中斷袖迎。

P(sem) 操作會將信號量 sem 值減 1冕臭，如果操作前 sem 值為負(fù)數(shù)，那么調(diào)用 P 操作的進(jìn)程將暫停執(zhí)行燕锥，直到另一個(gè)進(jìn)程對同一信號量做 V 操作辜贵。 V(sem) 操作會是將信號量 sem 值加 1，若 sem 的值<=0归形，操作系統(tǒng)會從與 sem 有關(guān)的隊(duì)列中選一個(gè)進(jìn)程托慨，喚醒它。

總結(jié)如下：

1. 信號量 : 是一種特殊的變量暇榴，表現(xiàn)形式是一個(gè)整型 S 和一個(gè)隊(duì)列厚棵；
2. P操作 : S = S -1，若 S <0蔼紧，進(jìn)程暫停執(zhí)行婆硬，進(jìn)入等待隊(duì)列；
3. V操作 : S = S +1奸例，若 S <=0彬犯，則喚醒等待隊(duì)列中的一個(gè)進(jìn)程 。

P 是減 1查吊，消耗資源谐区；V 是加 1，釋放資源逻卖。

P(sem) 操作定義：

P(sem)  {
  sem = sem - 1;
  if ( sem < 0 )
    進(jìn)程進(jìn)入等待狀態(tài);
  else 
    繼續(xù)進(jìn)行;
 } 

V(sem) 操作定義：

V(sem) {
  sem = sem + 1;
  if（ sem ≤ 0）
    喚醒隊(duì)列中的一個(gè)等待進(jìn)程;
  else 
    繼續(xù)進(jìn)行;
}

3.1 互斥控制

利用 P宋列、 V 原語和信號量可以方便地解決并發(fā)進(jìn)程在臨界區(qū)的互斥問題。

假設(shè)信號量 mutex 是用于互斥的信號量评也，初值為 1虚茶，表示沒有并發(fā)進(jìn)程使用該臨界區(qū)。
于是各并發(fā)進(jìn)程的臨界區(qū)可改寫成下列形式的代碼段：

P(信號量 S)仇参；
  臨界區(qū)
V(信號量 S)；

1. 由于只允許一個(gè)進(jìn)程進(jìn)入婆殿，因此信號量 S 的初值應(yīng)該為 1诈乒。 信號量 S 的初值表示可以允許多少個(gè)進(jìn)程進(jìn)入；
2. 當(dāng) S < 0 時(shí)婆芦，其絕對值就是等待使用臨界資源的進(jìn)程總數(shù)怕磨，也就是等待隊(duì)列中的進(jìn)程數(shù)喂饥。而當(dāng)一個(gè)進(jìn)程從臨界區(qū)出來時(shí)（即釋放臨界資源），執(zhí)行 V 操作 ( S = S +1 ) 肠鲫，如果等待隊(duì)列中還有進(jìn)程需要進(jìn)入臨界區(qū) ( S<=0 ) 员帮，則調(diào)入 ( 喚醒 )一個(gè)新的進(jìn)程進(jìn)入該臨界區(qū)。

3.2 同步控制

要用 P导饲， V 操作實(shí)現(xiàn)進(jìn)程同步捞高，需要引入私有信號量。注意：私有信號量只與制約進(jìn)程和被制約進(jìn)程有關(guān)渣锦，而不是與整組并發(fā)進(jìn)程硝岗。與此相對，進(jìn)程互斥使用的信號量為公用信號量袋毙。

首先為各并發(fā)進(jìn)程設(shè)置私用信號量型檀，然后為私有信號量賦初值，最后利用 P听盖， V 原語和私用信號量定義各進(jìn)程的執(zhí)行順序胀溺。

最簡單的同步控制是進(jìn)程 A 在另一個(gè)進(jìn)程 B 到達(dá) L2 以前，不應(yīng)前進(jìn)到超過點(diǎn) L1皆看。

要確保進(jìn)程 B 執(zhí)行 V 操作之前仓坞，不讓進(jìn)程 A 的運(yùn)行超過 L1 ，就要設(shè)置信號量 S 的初值為 0 悬蔽。 這樣扯躺，如果進(jìn)程 A 先執(zhí)行到 L1 ，那么執(zhí)行 P 操作 ( S = S - 1 ) 后蝎困，則 S < 0 录语，就停止執(zhí)行，讓其進(jìn)入阻塞狀態(tài)禾乘。直到進(jìn)程 B 執(zhí)行到 L2 時(shí)澎埠，再執(zhí)行 V 操作 ( S = S +1 ) ，喚醒進(jìn)程 A 讓其繼續(xù)執(zhí)行 始藕。

3.3 生產(chǎn)者－消費(fèi)者問題

“生產(chǎn)者－消費(fèi)者” 是經(jīng)典的同步問題蒲稳。要求存后再取，取后再存伍派，即存在兩個(gè)制約關(guān)系（緩存區(qū)如果滿了江耀，就停止生產(chǎn)；而緩存區(qū)如果空了诉植，則停止消費(fèi)）祥国。

生產(chǎn)者 - 消費(fèi)者問題不僅要解決生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程的同步關(guān)系，還要處理緩沖區(qū)的互斥關(guān)系，因此需要 3 個(gè)信號量來實(shí)現(xiàn)：

如果對緩沖區(qū)的讀寫無須進(jìn)行互斥控制的話漠嵌，那么就不需要 mutex 的互斥信號量了哼拔。

假設(shè)我們只對生產(chǎn)者與消費(fèi)者進(jìn)行同步控制，那么程序如下细层。

生產(chǎn)者程序 ：

loop
  生產(chǎn)一個(gè)物品;
  P(empty); //空閑的緩沖區(qū)數(shù)量 - 1
  物品存入緩沖區(qū);
  V(full);//填充的緩沖區(qū)數(shù)量 + 1
endloop

消費(fèi)者程序 ：

loop
  P(full);//填充的緩沖區(qū)數(shù)量 - 1
  從緩沖區(qū)中取出物品;
  V(empty);//空閑的緩沖區(qū)數(shù)量 +1
  使用它;
endloop

1. 信號量與 PV 操作是用來解決并發(fā)問題中的互斥與同步兩個(gè)關(guān)系惜辑。因此，在并發(fā)分析時(shí)疫赎，應(yīng)該先從尋找互斥與同步關(guān)系開始盛撑。這個(gè)分析過程可以參考簡單互斥 、 簡單同步以及生產(chǎn)者 - 消費(fèi)者問題 捧搞。
2. 通常來說抵卫，一個(gè)互斥或一個(gè)同步關(guān)系可以使用一個(gè)信號量來解決，但要注意一些經(jīng)常會被忽略的隱藏同步關(guān)系胎撇。例如介粘，在生產(chǎn)者 - 消費(fèi)者問題中，就存在兩個(gè)同步關(guān)系晚树，一個(gè)是判斷是否還有足夠的空間給生產(chǎn)者存放產(chǎn)物姻采，另一個(gè)是判斷是否有足夠的產(chǎn)物讓消費(fèi)者使用。
3. 信號量的初值通常就是表示可用的資源數(shù)爵憎。而且通常對于初始為 0 的信號量慨亲，會先做 V 操作，比如生產(chǎn)者 - 消費(fèi)者問題中的 full 信號量（表示已填充的緩沖區(qū)數(shù)量）宝鼓。
4. 在資源使用之前刑棵，會使用 P 操作，表示占用資源愚铡；在資源使用完之后铐望，會使用 V 操作，表示釋放資源。在互斥關(guān)系中正蛙， PV 操作是在一個(gè)進(jìn)程中成對出現(xiàn)的；而在同步關(guān)系中营曼，則 PV 操作是在兩個(gè)進(jìn)程甚至是多個(gè)進(jìn)程中成對出現(xiàn)的乒验。

3.4 實(shí)際應(yīng)用

假設(shè)，在某并發(fā)系統(tǒng)中蒂阱，有一個(gè)發(fā)送進(jìn)程 A 锻全、 一個(gè)接收進(jìn)程 B 、 一個(gè)環(huán)形緩沖區(qū) BUFFER 录煤、 信號量 S1 和 S2鳄厌。 發(fā)送進(jìn)程不斷地產(chǎn)生消息并寫入緩沖區(qū) BUFFER ，接收進(jìn)程不斷地從緩沖區(qū) BUFFER 中取消息妈踊。假設(shè)發(fā)送進(jìn)程和接收進(jìn)程可以并發(fā)地執(zhí)行了嚎，那么，當(dāng)緩沖區(qū)的容量為 N 時(shí)廊营，如何使用 PV 操作才能保證系統(tǒng)能夠正常工作歪泳。發(fā)送進(jìn)程 A 和接收進(jìn)程 B 的工作流程如圖 8 所示。請?jiān)趫D 8 中的 ①~④ 處填寫正確的操作露筒。

顯然呐伞，這是一個(gè) “ 生產(chǎn)者 - 消費(fèi)者 ” 問題，這個(gè)問題通常需要 3 個(gè)信號量來實(shí)現(xiàn) : 兩個(gè)用來管理緩沖區(qū)同步慎式，信號量 empy 表示空閑緩沖區(qū)數(shù)量伶氢，初值為緩沖區(qū)最大數(shù) N ，信號量 full 表示已填充緩沖區(qū)數(shù)量瘪吏，初值為 0癣防； 第三個(gè)信號量用于管理互斥，由信號量 mutex 保證只有一個(gè)進(jìn)程在寫緩沖區(qū)肪虎，初值為 1劣砍。 但在本系統(tǒng)中，進(jìn)程 A 和進(jìn)程 B 允許并發(fā)地訪問緩沖區(qū)扇救，因此無須管理互斥刑枝，因此只需定義兩個(gè)信號量 : S 1和 S2 ，初值為 N 的 S1 在此承擔(dān)的是信號量 empty 的功能迅腔，初值為 0 的 S2 則承擔(dān)了信號量 full 的功能装畅。

在這套并發(fā)系統(tǒng)的基礎(chǔ)上，如果系統(tǒng)中有多個(gè)發(fā)送進(jìn)程和接收進(jìn)程沧烈，進(jìn)程間的工作流程如圖 10 所示掠兄。發(fā)送進(jìn)程產(chǎn)生消息并順序地寫入環(huán)形緩沖區(qū) BUFFER，接收者進(jìn)程順序地從 BUFFER中取消息，且每條消息只能讀取一次為了保證進(jìn)程間的正確通信蚂夕，增加了信息量 SA 和 SB 迅诬。請說明信息量 SA 和 SB 的物理意義，并把信息量 SA 和 SB 正確應(yīng)用到流程中婿牍。

這里的關(guān)鍵點(diǎn)是系統(tǒng)中允許有多個(gè)發(fā)送進(jìn)程和接收進(jìn)程侈贷，推斷系統(tǒng)需要完成的控制是： 發(fā)送進(jìn)程順序?qū)懭耄邮者M(jìn)程順序讀取等脂，而且每條消息都只能夠讀取一次俏蛮。這顯然是兩個(gè)互斥的問題，即多個(gè)發(fā)送進(jìn)程在寫緩沖區(qū)時(shí)是互斥關(guān)系上遥，多個(gè)接收進(jìn)程讀緩沖區(qū)也是互斥關(guān)系搏屑。因此，信號量 SA 和 SB 用于分別實(shí)現(xiàn)這兩個(gè)互斥控制粉楚。

1. 發(fā)送進(jìn)程 : 在進(jìn)程產(chǎn)生消息之后準(zhǔn)備寫入緩沖區(qū)時(shí)辣恋，這時(shí)就需要進(jìn)行互斥判斷，而直到完成 “ i=(i+1)modN ” 操作后解幼，才完成緩沖區(qū)操作抑党。
2. 接收進(jìn)程 : 由于接收進(jìn)程是負(fù)責(zé)讀數(shù)據(jù)的，如果數(shù)據(jù)區(qū)是空的則應(yīng)該等待撵摆，因此必須先完成 P(S2) 操作底靠，來決定其是否需要阻塞。如果沒有阻塞時(shí)特铝，再進(jìn)入臨界區(qū)暑中；而 “ 對讀取的消息進(jìn)行處理 ” 已顯然在臨界區(qū)之外，因此在這之前插入V(SB)鲫剿。

4 前趨圖

前趨圖是一個(gè)由結(jié)點(diǎn)和有向邊構(gòu)成的有向無循環(huán)圖鳄逾。該圖通常用于表現(xiàn)事務(wù)之間先后順
序的制約關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可以表示一個(gè)語句灵莲、一個(gè)程序段或是一個(gè)進(jìn)程雕凹，結(jié)點(diǎn)間的有
向邊表示兩個(gè)結(jié)點(diǎn)之間存在的前趨關(guān)系。

比例：在計(jì)算機(jī)中政冻，經(jīng)常采用流水線方式執(zhí)行指令枚抵，每一條指令都可以分解為取指（取出指令）、分析和執(zhí)行三步明场。取指操作為 Ai汽摹，分析操作為 Bi 和執(zhí)行操作為 Ci(i=1,2,3)。圖 6 所示即為三個(gè)任務(wù)各程序段并發(fā)執(zhí)行的前驅(qū)圖苦锨。

image.png

圖中 A1 沒有前趨結(jié)點(diǎn)逼泣，稱為開始結(jié)點(diǎn)趴泌，它不受任何制約，可以直接執(zhí)行拉庶；而 B1 與 A2 只能在 A1 執(zhí)行完成之后才能開始嗜憔，而 B2 必須在 B1 與 A2 完成之后才能開始； C3 沒有后繼結(jié)點(diǎn)砍的，稱為終止結(jié)點(diǎn)痹筛。

在前趨圖中，執(zhí)行先后順序的制約關(guān)系可分為兩種：

1. 直接制約 - 一個(gè)操作中廓鞠，多個(gè)步驟之間的制約關(guān)系，也可以說是“同步的進(jìn)程之間的制約關(guān)系”谣旁。如圖 6 所示床佳， A1、 B1榄审、 C1 是一條指令的取指砌们、分析、執(zhí)行的三個(gè)步驟搁进，
   所以它們之間是直接制約關(guān)系浪感。
2. 間接制約 - 多個(gè)操作之間相同步驟的制約關(guān)系，也可以說是“互斥的進(jìn)程之間的制約關(guān)系”饼问。如圖 6 所示影兽， A1、 A2莱革、 A3 之間就存在間接制約的關(guān)系峻堰。

以下是 PV 操作與前趨圖結(jié)合的示例。假設(shè)進(jìn)程 P1盅视、P2捐名、P3、P4 和 P5 的前趨圖如圖 7 所示：

若用 PV 操作控制進(jìn)程 P1~P5 并發(fā)執(zhí)行的過程闹击，則需要設(shè)置5個(gè)信號量 S1镶蹋、S2、S3赏半、S4 和 S5 贺归，進(jìn)程間同步所使用的信號量標(biāo)注在圖 7 中的邊上，且信號量 S1~S5 的初值都等于零除破，初始狀態(tài)下進(jìn)程 P1 開始執(zhí)行牧氮。則該如何設(shè)置信號量來控制這些進(jìn)程？

根據(jù)前趨圖瑰枫，得知進(jìn)程之間的約束關(guān)系為：

1. P1 執(zhí)行后踱葛，才能開始執(zhí)行 P2 與 P3丹莲；
2. P2 執(zhí)行后，才能開始執(zhí)行 P4尸诽；
3. P2甥材、P3 執(zhí)行后，才能開始執(zhí)行 P5性含。

這里的信號量用于進(jìn)程同步洲赵。前趨圖的進(jìn)行信號量使用規(guī)則如下：

1. 進(jìn)程開始執(zhí)行前，必須對前趨圖中指向自己的信號量執(zhí)行 P 操作商蕴，等待前一個(gè)進(jìn)程完成叠萍。比如進(jìn)程 P2，指向自己的信號量為 S1绪商，那么就必須先執(zhí)行 P(S1) 操作苛谷；
2. 進(jìn)程結(jié)束后，必須執(zhí)行對前趨圖中的出口信號量格郁，執(zhí)行 V 操作腹殿，給后一個(gè)進(jìn)程的執(zhí)行創(chuàng)建條件。比如進(jìn)程 P1 執(zhí)行后例书，它的出口有兩條線锣尉，信號量分別為 S1 與 S2，那么就需要對這兩個(gè)信號量都執(zhí)行 V 操作决采。

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

進(jìn)程調(diào)度即處理器調(diào)度（又稱上下文轉(zhuǎn)換）自沧，它的主要功能是確定在什么時(shí)候分配處理器，并確定分給哪一個(gè)進(jìn)程织狐，即讓正在執(zhí)行的進(jìn)程改變狀態(tài)轉(zhuǎn)入就緒隊(duì)列的隊(duì)尾暂幼，再由調(diào)度原語取出就緒隊(duì)列的隊(duì)首進(jìn)程，并執(zhí)行它移迫。

引起進(jìn)程調(diào)度的原因有以下幾類：

1. 正在執(zhí)行的進(jìn)程執(zhí)行完畢旺嬉。
2. 執(zhí)行中的進(jìn)程自己調(diào)用阻塞原語將自己阻塞起來進(jìn)入睡眠狀態(tài)。
3. 執(zhí)行中的進(jìn)程調(diào)用了 P 原語操作厨埋，然后因資源不足而被阻塞邪媳；或調(diào)用 V 原語操作激活了等待資源的進(jìn)程隊(duì)列。
4. 在分時(shí)系統(tǒng)中荡陷，當(dāng)一個(gè)進(jìn)程用完了一個(gè) CPU 時(shí)間片雨效。
5. 就緒隊(duì)列中某個(gè)進(jìn)程的優(yōu)先級變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級，也將引起進(jìn)程調(diào)度废赞。

對于不同的系統(tǒng)與目標(biāo)徽龟，會采取不同的進(jìn)程調(diào)度算法：

1. 先來先服務(wù)（ First Come and First Serverd， FCFS）調(diào)度算法唉地，又稱先進(jìn)先出（ First In and First Out据悔， FIFO）传透。比如就緒隊(duì)列，會按照先來后到原則排隊(duì)极颓。
2. 優(yōu)先數(shù)調(diào)度朱盐。優(yōu)先數(shù)反映了進(jìn)程優(yōu)先級，就緒隊(duì)列按優(yōu)先數(shù)排隊(duì)菠隆。有兩種確定優(yōu)先級的方法兵琳，即靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級。靜態(tài)優(yōu)先級是指進(jìn)程的優(yōu)先級在進(jìn)程開始執(zhí)行前確定骇径，執(zhí)行過程中不變躯肌；而動態(tài)優(yōu)先級則可以在進(jìn)程執(zhí)行過程中改變優(yōu)先級。
3. 輪轉(zhuǎn)法（ Round Robin）破衔。就緒隊(duì)列按 FCFS 方式排隊(duì)羡榴。每個(gè)進(jìn)程執(zhí)行一次占有處理器時(shí)間都不能超過規(guī)定的時(shí)間單位（時(shí)間片）；如果超過运敢，則自行釋放自己所占有的 CPU 資源，然后排到就緒隊(duì)列的末尾忠售，等待下一次調(diào)度传惠。同時(shí)，進(jìn)程調(diào)度程序又去取當(dāng)前就緒隊(duì)列中的第一個(gè)進(jìn)程稻扬，放入處理器執(zhí)行卦方。

在進(jìn)程管理的實(shí)現(xiàn)中，如果設(shè)計(jì)不當(dāng)泰佳，就會出現(xiàn)死鎖盼砍。

6 死鎖

當(dāng)若干個(gè)進(jìn)程互相爭用對方已占有的資源，導(dǎo)致無限期地等待逝她，不能向前推進(jìn)的情況浇坐，就會造成“死鎖”。例如黔宛， P1 進(jìn)程占有資源 R1近刘， P2 進(jìn)程占有資源 R2，這時(shí)臀晃， P1 又需要資源 R2觉渴， P2 也需要資源 R1，它們在互相等待對方占有的資源時(shí)徽惋，又無法釋放自己占有的資源案淋，從而使雙方都進(jìn)入了無限等待狀態(tài)。

歸納來說险绘，就是多個(gè)進(jìn)程之間互相等待對方的資源踢京，而在得到對方資源之前又不釋放自己的資源誉碴，這樣，就會造成循環(huán)等待漱挚，這就是死鎖翔烁。如果一個(gè)進(jìn)程在等待一個(gè)永遠(yuǎn)不可能發(fā)生的事件，就會造成死鎖旨涝。

死鎖是系統(tǒng)的一種出錯狀態(tài)蹬屹，它不僅會浪費(fèi)大量的系統(tǒng)資源，甚至還會導(dǎo)致整個(gè)系統(tǒng)的崩潰白华，所以死鎖是應(yīng)該盡量預(yù)防和避免的慨默。

產(chǎn)生死鎖的主要原因是共享資源不足，資源分配策略和進(jìn)程的推進(jìn)順序不當(dāng)造成的弧腥。系統(tǒng)資源既可能是可重復(fù)使用的永久性資源厦取，也可能是消耗性的臨時(shí)資源。

6.1 產(chǎn)生死鎖的必要條件

產(chǎn)生死鎖的必要條件是：互斥條件管搪、保持和等待條件虾攻、不剝奪條件和環(huán)路等待條件。

1. 互斥條件 : 即一個(gè)資源每次只能被一個(gè)進(jìn)程使用更鲁；
2. 保持與等待條件 : 有一個(gè)進(jìn)程已獲得了某些資源霎箍，但因請求其他資源而被阻塞時(shí)，又對所獲得的資源保持不放澡为；
3. 不可搶占條件 : 有些系統(tǒng)資源是不可搶占的漂坏，當(dāng)某個(gè)進(jìn)程已獲得這種資源后系統(tǒng)不能強(qiáng)行收回，只能由進(jìn)程使用完資源后自己釋放媒至；
4. 循環(huán)等待條件 : 若干個(gè)進(jìn)程形成環(huán)形鏈顶别，每個(gè)都占用對方要申請的下一個(gè)資源。

6.2 銀行家算法

銀行家算法指的是拒啰，當(dāng)進(jìn)程請求資源時(shí)驯绎，系統(tǒng)將按照如下原則分配資源 :

1. 當(dāng)一個(gè)進(jìn)程對資源的最大需求量不超過系統(tǒng)中的可用資源數(shù)時(shí)，就接納該進(jìn)程图呢；
2. 進(jìn)程可以分期請求資源条篷，但請求的總數(shù)不能超過該進(jìn)程對資源的最大需求量；
3. 當(dāng)系統(tǒng)現(xiàn)有的資源不能滿足進(jìn)程所需要的資源數(shù)時(shí)蛤织，會推遲分配該進(jìn)程的請求赴叹，但總能使進(jìn)程在有限的時(shí)間內(nèi)得到相應(yīng)資源；
4. 當(dāng)系統(tǒng)現(xiàn)有的資源能滿足進(jìn)程所需要的資源數(shù)時(shí)指蚜，必須測試系統(tǒng)現(xiàn)存的資源能否真的能滿足該進(jìn)程所需的最大資源數(shù)乞巧，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配摊鸡；

假設(shè)系統(tǒng)中有三類互斥資源 R1绽媒、R2 和 R3 蚕冬，可用資源數(shù)分別是 9、8 和 5是辕。 在 T0 時(shí)刻系統(tǒng)中有 P1囤热、P2、P3获三、P4 和 P5 五個(gè)進(jìn)程旁蔼，這些進(jìn)程對資源的最大需求量和已分配資源數(shù)如表 1 所示。進(jìn)程按照 P1→P2→P4→P5→P3 序列執(zhí)行疙教，系統(tǒng)狀態(tài)安全嗎 ? 如果按P2→P4→ P5→P1→P3 的序列呢 ?

從表 1 中可以看出棺聊，還有 2 個(gè) R1 （9-1-2-2-1-1=2）未分配，1個(gè) R2 （8-2-1-1-2-1=1）未分配贞谓，而 R3 全部分配完畢（5-1-1-3=0）限佩。

按照 P1 → P2 → P4 →P5→P3 的順序執(zhí)行時(shí)，首先執(zhí)行 P1 裸弦，這時(shí)由于其R1祟同、 R2 和 R3 的資源數(shù)都未分配夠，因而開始申請資源理疙，得到還未分配的 2 個(gè) R1 耐亏，1個(gè) R2 。但其資源仍不足 ( 因?yàn)闆]有可用的 R3 資源 ) 沪斟，從而進(jìn)入阻塞狀態(tài)，并且這時(shí)所有資源都已經(jīng)分配完畢暇矫。因此主之，后續(xù)的進(jìn)程都無法得到能夠完成任務(wù)的資源，全部進(jìn)入阻塞李根，這時(shí)死鎖就發(fā)生了槽奕。

而如果按照 P2 → P4 →P5→ P1 →P3 的序列執(zhí)行時(shí)：

1. 首先執(zhí)行 P2 ，它還差1個(gè) R2 資源房轿，系統(tǒng)中剛好還有 1 個(gè)未分配的 R2 粤攒，因此滿足其要求，進(jìn)程能夠順利結(jié)束囱持，并釋放出所占用的資源：2個(gè) R1 夯接、2個(gè) R2、1 個(gè) R3 纷妆。這時(shí)盔几，未分配的資源為 4 個(gè) R1（2+2） 、2 個(gè) R2 掩幢、1 個(gè) R3 逊拍。
2. 然后執(zhí)行 P4 上鞠，它還差一個(gè) R3 ，而這時(shí)系統(tǒng)中剛好有一個(gè)未分配的 R3 芯丧，因此滿足其要求芍阎，也能夠順利結(jié)束，并釋放出所占用的資源缨恒。這時(shí)谴咸，未分配的資源為 5個(gè) R1（4+1） 、4個(gè) R2（2+2） 肿轨、1個(gè) R3 寿冕。
3. 接著執(zhí)行 P5，它需要 2 個(gè) R1椒袍、3 個(gè) R2 以及 1 個(gè) R3驼唱，這些資源都滿足，所以也會順利結(jié)束驹暑，并釋放出所占用的資源玫恳。這時(shí)，未分配的資源為 8個(gè) R1（5+3） 优俘、8個(gè) R2（4+4） 京办、5個(gè) R3（4+1） 。
   根據(jù)這樣的方式推下去帆焕，會發(fā)現(xiàn)按這種序列可以順利地完成所有的進(jìn)程惭婿，而不會出現(xiàn)死鎖現(xiàn)象。

6.3 解決死鎖的策略

處于死鎖狀態(tài)的進(jìn)程不能繼續(xù)執(zhí)行但又占用了系統(tǒng)資源叶雹，從而阻礙其他作業(yè)的執(zhí)行财饥。因此必須解決死鎖。解決死鎖的策略為：

1. 死鎖預(yù)防 : 破壞導(dǎo)致死鎖必要條件中的任意一個(gè)就可以預(yù)防死鎖折晦。例如钥星，采用資源靜態(tài)分配法，要求用戶申請資源時(shí)一次性申請所需要的全部資源满着，這就破壞了保持和等待條件 ;采用資源有序分配法將資源分層谦炒，得到上一層資源后， オ 能夠申請下一層資源风喇，它破壞了環(huán)路等待條件宁改。預(yù)防通常會降低系統(tǒng)的效率 。
2. 死鎖避免 : 避免是指進(jìn)程在每次申請資源時(shí)判斷這些操作是否安全魂莫，例如透且，使用銀行家算法。死鎖避免算法的執(zhí)行會增加系統(tǒng)的開銷 。
3. 死鎖檢測 : 死鎖預(yù)防和避免都是事前措施秽誊，而死鎖的檢測則是判斷系統(tǒng)是否處于死鎖狀態(tài)鲸沮，如果是，則執(zhí)行死鎖解除策略 锅论。
4. 死鎖解除 : 這是與死鎖檢測結(jié)合使用的讼溺，它使用的方式是剝奪。即將某進(jìn)程所擁有的資源強(qiáng)行收回最易，分配給其他的進(jìn)程 怒坯。

實(shí)際上，系統(tǒng)出現(xiàn)死鎖的概率很小藻懒，故從系統(tǒng)所花的代價(jià)上來看剔猿，采用死鎖發(fā)生后的檢測與解除策略要比采用死鎖發(fā)生前的預(yù)防與避免策略代價(jià)要小一些。所以嬉荆，推薦采用死鎖發(fā)生后的檢測與恢復(fù)策略归敬。

7 管程與線程

管程由管程名 、 局部子管程的變量說明 鄙早、 使用共享資源并在數(shù)據(jù)集上進(jìn)行操作的若干過程汪茧，以及對變量賦初值的語句等4個(gè)基本部分組成。

每一個(gè)管程管理一個(gè)臨界資源限番。當(dāng)有多個(gè)進(jìn)程調(diào)用某管程時(shí)舱污，僅允許一個(gè)進(jìn)程進(jìn)入管程，其他調(diào)用者必須等待弥虐，也就是申請進(jìn)程必須互斥地進(jìn)入管程扩灯。方法是通過調(diào)用特定的管程入口進(jìn)入管程，然后通過管程中的一個(gè)過程使用臨界資源霜瘪。當(dāng)某進(jìn)程通過調(diào)用請求訪問某臨界資源而未能滿足時(shí)驴剔，管程調(diào)用相應(yīng)同步原語使該進(jìn)程進(jìn)入等待狀態(tài)，并將它放入等待隊(duì)列粥庄。當(dāng)使用臨界資源的進(jìn)程訪問完該臨界資源并釋放之后，管程又調(diào)用相應(yīng)的同步原語喚醒等待隊(duì)列中的隊(duì)首進(jìn)程豺妓。為了表示不同的等待原因惜互，設(shè)置條件變量，條件變量是與普通變量不同的變量琳拭，條件變量不能取任何值训堆，只是一個(gè)排隊(duì)棧。

線程是進(jìn)程的活動成分白嘁，是處理器分配資源的最小單位坑鱼，它可以共享進(jìn)程的資源與地址空間，通過線程的活動，進(jìn)程可以提供多種服務(wù) ( 對服務(wù)器進(jìn)程而言 ) 或?qū)嵭凶尤蝿?wù)并行 ( 對用戶進(jìn)程而言 ) 鲁沥。每個(gè)進(jìn)程創(chuàng)建時(shí)只有一個(gè)線程（主線程）呼股，根據(jù)需要在運(yùn)行過程中創(chuàng)建更多的線程。顯然画恰，只有主線程的進(jìn)程才是傳統(tǒng)意義下的進(jìn)程內(nèi)核負(fù)責(zé)線程的調(diào)度彭谁，線程的優(yōu)先級可以動態(tài)地改變。

采用線程機(jī)制的最大優(yōu)點(diǎn)是節(jié)省開銷允扇，傳統(tǒng)的進(jìn)程創(chuàng)建子進(jìn)程的辦法內(nèi)存開銷大缠局，而且創(chuàng)建時(shí)間也長。

在多線程系統(tǒng)中考润，一個(gè)進(jìn)程可以由一個(gè)或多個(gè)線程構(gòu)成狭园，每一個(gè)線程可以獨(dú)立運(yùn)行，每個(gè)進(jìn)程的線程共享這個(gè)進(jìn)程的地址空間糊治。有多種方法可以實(shí)現(xiàn)多線程系統(tǒng)唱矛，一種方法是核心級線程，另一種方法是用戶級線程俊戳，也可以把兩者組合起來揖赴。

多線程實(shí)現(xiàn)的并行避兔了進(jìn)程間并行的缺點(diǎn) : 創(chuàng)建線程的開銷比創(chuàng)建進(jìn)程要小，同一進(jìn)程的線程共享進(jìn)程的地址空間抑胎，所以線程切換 ( 處理器調(diào)度 ) 比進(jìn)程切換快燥滑。例如， WindowsServer 內(nèi)核采用基于優(yōu)先級的方案選定線程執(zhí)行的次序阿逃。高優(yōu)先級的線程會比低優(yōu)先級的線程先執(zhí)行铭拧，內(nèi)核周期性地改變線程的優(yōu)先級，以確保所有線程均能執(zhí)行恃锉。