2.1 進程與線程

2.1.1 進程的概念與特征

1.進程的概念：

多個程序并發(fā)運行燎悍，它們失去封閉性虑凛，且具有間斷性和不可再現(xiàn)性的特征梅鹦，所以引入進程（Process）的概念谬返，描述和控制程序的并發(fā)執(zhí)行，實現(xiàn)了操作系統(tǒng)的并發(fā)性和共享性匹中。

配置專門的數(shù)據(jù)結(jié)構(gòu)—進程控制塊（Process Control Block夏漱，PCB）保證并發(fā)的程序獨立地運行，PCB描述進程的基本情況和運行狀態(tài)顶捷，以此來進行控制和管理進程挂绰。由程序段、相關(guān)數(shù)據(jù)段和PCB三部分構(gòu)成了進程映像（進程實體）服赎。進程的創(chuàng)建與撤銷的實質(zhì)是創(chuàng)建與撤銷進程映像中的PCB葵蒂，但進程映像是靜態(tài)的，進程是動態(tài)的重虑，而PCB是進程唯一存在的標志践付。

進程有多種定義方式，比較典型的是：

1）進程是程序的一次執(zhí)行過程缺厉；

2）進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動永高；

3）進程時具有獨立功能的程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位提针。

系統(tǒng)資源是指處理機命爬、存儲器和其他設(shè)備服務(wù)于某個進程的“時間片”，以進程為單位將這些時間片分配給不同進程辐脖。

2.進程的特征

進程與程序是兩個不同的概念饲宛，基本特征有：

1）動態(tài)性：是程序的一次執(zhí)行，有創(chuàng)建嗜价、活動艇抠、暫停幕庐、中止等過程，有一定的生命周期家淤，是最基本的特征异剥。

2）并發(fā)性：多個進程實體同時存于內(nèi)存中，在一段時間內(nèi)同時運行絮重，引入進程的目的就是使程序并發(fā)執(zhí)行届吁，提高資源利用率。

3）獨立性：進程實體是一個能獨立運行绿鸣、獨立獲取資源和接受獨立接受調(diào)度的基本單位，未建立PCB的程序暂氯，不能作為一個獨立的單位參與運行潮模。

4）異步性：進程按個自獨立的、不可預(yù)知的速度向前推進痴施，異步性導(dǎo)致結(jié)果的不可再現(xiàn)性擎厢，在操作系統(tǒng)中應(yīng)配置相應(yīng)的進程同步機制。

5）結(jié)構(gòu)性：每個進程都配置一個PCB對其進行描述辣吃，進程實體由程序段动遭、數(shù)據(jù)段和進程控制塊三部分組成。

2.1.2 進程的狀態(tài)與轉(zhuǎn)換

進程的5個狀態(tài)：

1）運行態(tài)：進程在處理機上運行神得，在單處理機環(huán)境下厘惦，每個時刻最多只有一個進程處于運行狀態(tài)。

2）就緒態(tài)：進程獲取了除處理機外的一切所需資源哩簿，一旦處理機就緒宵蕉，便可立即運行，多個處于就緒態(tài)的進程可以形成一個就緒隊列节榜。

3）阻塞態(tài)：又稱等待態(tài)羡玛，進程正在等待某資源可用或輸入/輸出完成而暫停運行。

4）創(chuàng)建態(tài)：正在被創(chuàng)建宗苍，尚未轉(zhuǎn)到就緒態(tài)稼稿。創(chuàng)建的過程先申請一個PCB，向PCB中寫入控制和管理進程的信息讳窟，然后為其分配資源让歼，最后轉(zhuǎn)入就緒態(tài)。

5）結(jié)束態(tài)：進程因為正常結(jié)束或中斷而退出運行挪钓，系統(tǒng)先置進程為結(jié)束態(tài)是越，然后釋放和回收資源。

就緒態(tài)和等待態(tài)的區(qū)別：就緒態(tài)是只等待處理機碌上，而等待態(tài)是等待除處理機外的其他資源倚评，兩個完全不同浦徊。

5個狀態(tài)的轉(zhuǎn)換過程：

就緒轉(zhuǎn)運行：就緒的進程獲得處理機資源后轉(zhuǎn)為運行態(tài)。

運行轉(zhuǎn)就緒：運行的進程在將處理機時間片用完之后天梧，讓出處理機盔性，轉(zhuǎn)為就緒態(tài)。

運行轉(zhuǎn)阻塞：進程請求某一資源的使用或等待某一事件的發(fā)生呢岗，從運行轉(zhuǎn)換為阻塞態(tài)冕香。

阻塞轉(zhuǎn)就緒：進程請求的資源得到分配時或事件完成時，中斷處理程序必須把相應(yīng)進程的狀態(tài)轉(zhuǎn)換為就緒態(tài)后豫。

運行變阻塞是主動的行為悉尾，阻塞變成就緒是被動行為。

2.1.3 進程控制

進程控制主要是對進程實施有效的管理挫酿，具有創(chuàng)建新進程构眯、撤銷已有進程、實現(xiàn)進程狀態(tài)轉(zhuǎn)換等功能早龟，進程控制用的程序段稱為原語惫霸，它在執(zhí)行期間不允許中斷，是一個不可分割的單位葱弟。

1.進程的創(chuàng)建：

運行一個進程（父進程）創(chuàng)建另一個進程（子進程）壹店，子進程可以繼承父進程所擁有的資源，當子進程被撤銷時芝加，應(yīng)將資源全部還給父進程硅卢，而撤銷父進程，必須撤銷子進程藏杖。

操作系統(tǒng)創(chuàng)建新進程的過程（創(chuàng)建原語）：

1）分配進程識別號和申請PCB老赤；

2）分配資源，若資源不夠進程處于阻塞狀態(tài)制市，等待資源抬旺；

3）初始化PCB，主要包括初始化標志信息祥楣，初始化處理機狀態(tài)信息开财、初始化處理機控制信息、設(shè)置優(yōu)先級误褪；

4）進程進入就緒隊列等待被調(diào)度運行责鳍。

2.進程的終止：

引起進程終止的原因：正常結(jié)束，進程運行完畢正常退出兽间；異常結(jié)束历葛，發(fā)生了某種異常事件導(dǎo)致進程不能繼續(xù)運行，如存儲區(qū)越界、非法指令恤溶、運行超時等乓诽；外界干預(yù)，進程應(yīng)外界的請求而終止運行咒程，如操作員或操作系統(tǒng)的干預(yù)鸠天、父進程請求和父進程終止。

終止進程過程（撤銷原語）：

1）根據(jù)被終止進程的標示符帐姻，檢索PCB稠集，從中讀出該進程的狀態(tài)；

2）若進程處于執(zhí)行狀態(tài)饥瓷，立即終止剥纷，將資源重新分配；

3）若其還有子孫進程呢铆，終止子孫進程筷畦；

4）將子孫進程的資源歸還父進程或操作系統(tǒng)；

5）將PCB刪除刺洒。

3.進程的阻塞和喚醒：

在執(zhí)行過程中，若期待的事件未發(fā)生吼砂，系統(tǒng)執(zhí)行阻塞原語（block）逆航，轉(zhuǎn)為阻塞態(tài)，屬于主動行為渔肩，阻塞原語執(zhí)行過程如下：

1）根據(jù)進程標示號找到PCB因俐；

2）若為運行態(tài)，保護現(xiàn)場周偎，轉(zhuǎn)為阻塞態(tài)抹剩，停止運行；

3）把該PCB插入相應(yīng)事件的等待隊列蓉坎，將處理機資源交給其他就緒程序澳眷。

當所期待的事情發(fā)生時，調(diào)用喚醒原語（wakeup）蛉艾，等待進程喚醒钳踊，喚醒過程：

1）在該事件的等待隊列中找到PCB；

2）從等待隊列移出勿侯，轉(zhuǎn)換為就緒態(tài)拓瞪；

3）把PCB插入就緒隊列，等待調(diào)度執(zhí)行助琐。

block和wakeup必須成對使用祭埂，前者是自我調(diào)用，后者是被其他調(diào)用兵钮。

4.進程切換

進程是在操作系統(tǒng)內(nèi)核的支持下完成的蛆橡，與內(nèi)核緊密相關(guān)舌界。進程切換是指處理機從一個進程的運行轉(zhuǎn)到另一個進程上運行，在此過程中進程運行的環(huán)境產(chǎn)生了實質(zhì)性的變化航罗，過程如下：

1）保存處理機上下文禀横，包括程序計數(shù)器和其他寄存器；

2）更新PCB信息粥血；

3）把進程的PCB移入相應(yīng)的隊列柏锄，如就緒隊列或阻塞隊列；

4）選擇另一個進程執(zhí)行复亏，并更新PCB趾娃；

5）更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)；

6）恢復(fù)處理機上下文缔御。

注意：進程切換與處理機模式切換是不同的抬闷，模式切換時，處理機邏輯上可能還在同一進程中運行耕突。若進程因中斷或異常進入核心態(tài)運行笤成，執(zhí)行完又回到用戶態(tài)繼續(xù)執(zhí)行該進程，操作系統(tǒng)只需恢復(fù)進程進入內(nèi)核前所保存的CPU現(xiàn)場眷茁，無需改變當前進程的環(huán)境信息炕泳；但切換進程，運行環(huán)境信息也需要改變上祈。

調(diào)度與切換的區(qū)別：調(diào)度指決定資源分配給哪個進程的行為培遵，是一種決策行為；切換是指實際分配的行為登刺，是執(zhí)行行為籽腕。

2.1.4 進程的組織

進程是一個獨立的運行單位，也是資源分配和調(diào)度的基本單位纸俭。由三部分組成皇耗，最核心的是PCB。

1.進程控制塊

創(chuàng)建時揍很，新建PCB廊宪，存儲進程運行狀態(tài)和優(yōu)先級，常駐內(nèi)存女轿，任意時刻都可存取箭启，并在進程結(jié)束時刪除，PCB是進程實體的一部分蛉迹，是進程存在的唯一標志傅寡，系統(tǒng)通過PCB表來管理和控制進程。

當操作系統(tǒng)欲調(diào)度某進程運行時，從該進程的PCB中查出運行狀態(tài)和優(yōu)先級荐操；在調(diào)度到某進程之后芜抒，根據(jù)其PCB中所保存的處理機狀態(tài)信息，設(shè)置恢復(fù)現(xiàn)場托启，并根據(jù)PCB中存儲的程序和數(shù)據(jù)的地址宅倒，找到程序和數(shù)據(jù)；在運行過程中屯耸，需要和與之相關(guān)的進程進行同步拐迁、通信或訪問文件時，也需訪問PCB疗绣；當進程由于某種原因而暫停運行時线召，又需將其斷點的處理機環(huán)境保存在PCB中。在整個進程運行的生命周期中多矮，系統(tǒng)唯有經(jīng)過PCB才能感知該進程的存在缓淹。

下圖是一個PCB實例：

1）進程描述信息。進程標識符：各個進程的唯一標志塔逃。用戶標識符：標示進程所屬的用戶讯壶，為共享和保護服務(wù)。

2）進程控制和管理信息湾盗。進程當前狀態(tài)：描述進程的狀態(tài)信息伏蚊，作為處理機分配調(diào)度的依據(jù)。進程優(yōu)先級：描述搶占處理機的優(yōu)先級淹仑。

3）資源分配清單，說明有關(guān)內(nèi)存地址空間或虛擬地址空間的狀況肺孵，所打開文件的列表和所使用的輸入/輸出設(shè)備信息匀借。

4）處理機相關(guān)信息，主要指處理機中各寄存器的值平窘，當進程被切換時吓肋，處理機狀態(tài)信息都必須保存在相應(yīng)的PCB中，方便重新執(zhí)行瑰艘。

為了方便進程的調(diào)度和管理是鬼，需要將各進程的PCB用適當?shù)姆椒ńM織起來，常用的組織方式有鏈接方式和索引方式紫新，鏈式是將同一狀態(tài)的PCB鏈接成一個隊列均蜜，不同狀態(tài)對應(yīng)不同隊列，也可把阻塞原因不同的隊列根據(jù)其原因分成若干個芒率。索引方式是將同一狀態(tài)的進程組織在一個索引表中囤耳，索引表的表項指向相應(yīng)的PCB，不同狀態(tài)對應(yīng)不同索引表。

2.程序段

能被進程調(diào)度程序調(diào)度到CPU執(zhí)行的程序代碼段充择，程序可被多個進程共享德玫。

3.數(shù)據(jù)段

一個進程的數(shù)據(jù)段，可以是進程對應(yīng)的程序加工處理的原始數(shù)據(jù)椎麦，也可以是程序執(zhí)行后產(chǎn)生的中間或最終結(jié)果數(shù)據(jù)宰僧。

2.1.5 進程的通信

通信指進程之間信息的交換，PV是低級通信方式观挎，高級通信方式是以較高的效率傳輸大量數(shù)據(jù)的通信方式琴儿，有以下三類：

1.共享存儲：進程之間存在一塊可直接訪問的共享空間，對這個空間的讀/寫操作實現(xiàn)進程之間的信息交換键兜，在讀/寫操作時凤类，需要用同步互斥（P/V操作）進行控制。共享存儲又分兩種：低級方式的共享基于數(shù)據(jù)結(jié)構(gòu)的共享普气；高級方式的共享基于存儲區(qū)的共享谜疤，操作系統(tǒng)只提供空間和工具，交換由用戶自己安排完成现诀。

注意夷磕，用戶進程空間一般是獨立的，運行期間一般不能訪問其他進程空間仔沿，要想讓兩個用戶進程共享空間坐桩，必須通過特殊的系統(tǒng)調(diào)用實現(xiàn)，而進程內(nèi)的線程是自然共享進程空間的封锉。

2.消息傳遞

在消息傳遞系統(tǒng)中绵跷，進程間的數(shù)據(jù)交換以格式化的消息（Message）為單位的。若通信的進程之間不存在可直接訪問的共享空間成福，則必須利用操作系統(tǒng)提供的消息傳遞方法實現(xiàn)進程通信碾局。進程通過系統(tǒng)提供的發(fā)送消息原語與接收消息原語進行數(shù)據(jù)交換。

1）直接通信方式奴艾。發(fā)送進程直接把消息發(fā)送給接收進程净当，并將它掛在接收進程的消息緩沖隊列上，接收進程從消息緩沖隊列中取得消息蕴潦，如下圖像啼。

2）間接通信方式。發(fā)送進程把消息發(fā)送到某個中間實體潭苞，接收進程從中間實體取得消息睬涧。中間實體一般稱為信箱响逢，這種通信方式又稱為信箱通信方式趣倾。該通信方式廣泛應(yīng)用于計算機網(wǎng)絡(luò)中衷掷，稱為電子郵件系統(tǒng)蜜猾。

3.管道通信

管道通信是消息傳遞的一種特殊方式，管道指用于連接一個讀進程和一個寫進程以實現(xiàn)它們通信的一個共享文件（pipe文件）振诬。向pipe提供輸入的發(fā)送進程（寫進程）蹭睡，以字符流形式將大量的數(shù)據(jù)送入寫管道；接收管道輸出的接收進程（讀進程）則從管道中接收（讀）數(shù)據(jù)赶么。為了協(xié)調(diào)雙方的通信肩豁，管道機制必須提供互斥、同步辫呻、確定對方存在的協(xié)調(diào)能力清钥。

管道只能采用半雙工通信——某一時刻只能單向傳輸，要實現(xiàn)父子進程雙向互動放闺，要定義兩個管道祟昭。它通過限制管道大小和規(guī)定讀進程比寫進程快克服使用文件進行通信的缺點。

管道可以理解為共享存儲的優(yōu)化和發(fā)展怖侦。在共享存儲中篡悟，某進程要訪問共享存儲空間，必須沒有其他進程在該共享存儲空間進行讀/寫操作匾寝。否則會被阻塞搬葬。在管道通信中存儲空間進化成緩沖區(qū)，允許一邊寫入艳悔，另一邊讀出急凰，只要緩沖區(qū)中有數(shù)據(jù)，數(shù)據(jù)就能被進程讀出猜年，不用擔心其他進程正在讀數(shù)據(jù)而阻塞抡锈。

2.1.6 線程概念和多線程模型

1.線程的基本概念

引入進程是為了使多道程序并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量乔外；引入線程為了減少程序在并發(fā)執(zhí)行時所付出的時空開銷袁稽，提高并發(fā)執(zhí)行的性能擒抛。

線程是一個輕量級進程，是一個基本的CPU執(zhí)行單元歹撒，也是程序執(zhí)行流的最小單元，它由線程ID诊胞、程序計數(shù)器、寄存器集合和堆棧組成迈着。線城是進程中的一個實體咬清，是被系統(tǒng)獨立調(diào)度和分派的基本單位旧烧，線程可與同屬一個進程的其它線程共享資源掘剪。一個線程可以創(chuàng)建和撤銷另一個線程夺谁，同一進程中的多個線程可以并發(fā)執(zhí)行予权。線程之間有相互制約扫腺，所以線程運行會呈現(xiàn)間斷性村象。線程的狀態(tài)也有就緒厚者、阻塞账忘、運行鳖擒。

進程只作為除CPU外的系統(tǒng)資源的分配單元蒋荚，線程作為處理機的分配單元惊奇，一個進程內(nèi)部有多個線程颂郎，線程的切換位于同一個進程內(nèi)祖秒，需要的時空開銷很小。

2.線程和進程的比較

1）調(diào)度：無線程時抬纸，進程是擁有資源和獨立調(diào)度的基本單位湿故，有線程時，線程是獨立調(diào)度的基本單位墅茉，但進程依舊是擁有資源的基本單位。同一進程中洋机，線程的切換不會引起進程的切換绷旗，在不同進程中進行線程切換，則會引起進程切換膀懈。

2）擁有資源：進程擁有資源启搂，線程不擁有資源，但線程可以訪問其奴隸進程的系統(tǒng)資源疑苫，若線程也是擁有資源的單位，則切換線程時需要較大的時空開銷挺勿。

3）并發(fā)性：進程之間可以并發(fā)執(zhí)行不瓶，多個線程之間也可并發(fā)執(zhí)行。

4）系統(tǒng)開銷：創(chuàng)建撤銷進程時所需開銷麦备，比對線程進行同樣操作時所需的開銷大。

5）地址空間和其他資源（如打開的文件）：進程的地址空間相互獨立鞋诗，同一進程的線程共享同一地址空間削彬。

6）通信方面：進程間的通信（IPC）需要進程同步和互斥手段的輔助，保證數(shù)據(jù)一致雁刷，線程間的通信通過直接讀/寫進程數(shù)據(jù)段實現(xiàn)责语。

3.線程的屬性

1）輕型實體：不擁有系統(tǒng)資源坤候，有標識符、線程控制塊徒河，線程控制塊記錄了線程執(zhí)行的寄存器和棧等現(xiàn)場狀況。

2）同一個服務(wù)被不同用戶調(diào)用時棒厘，操作系統(tǒng)把它們創(chuàng)建成不同的線程。

3）進程中的線程共享此進程的資源何乎。

4）線程是處理機的調(diào)度單位，線程可并發(fā)各墨。

5）線程被創(chuàng)建之后，開始它的生命周期黎做，會經(jīng)歷阻塞態(tài)、就緒態(tài)和運行態(tài)的變化宏所。

4.線程的實現(xiàn)方式

線程分為用戶級線程（User-Level Thread，ULT）和內(nèi)核級線程（Kernel-Level Thread盖腕，KLT）（內(nèi)核支持的線程）。

用戶級線程中听隐，線程管理由應(yīng)用程序完成，內(nèi)核意識不到線程的存在沪么。應(yīng)用程序通過使用線程庫設(shè)計成多線程程序，從單線程開始殉摔，在該線程中開始運行，在其運行的任何時刻彻采，通過調(diào)用線程庫中的派生例程創(chuàng)建新線程。如下圖（a）特笋。

內(nèi)核級線程中虎囚，管理由內(nèi)核完成，應(yīng)用程序沒有進行線程管理的代碼蒲列，只有一個內(nèi)核級線程的編程接口。內(nèi)核為其進程及內(nèi)部的每個線程維護上下文信息抵赢，調(diào)度也在內(nèi)核基于線程架構(gòu)的基礎(chǔ)上完成。如下圖（b）彩匕。

一些系統(tǒng)使用組合方式實現(xiàn)。創(chuàng)建在用戶空間中完成，調(diào)度和同步在應(yīng)用程序中進行奠货。應(yīng)用程序中的多個用戶線程被映射到內(nèi)核級線程上。如下圖（c）

5.多線程模型

1）多對一：多個用戶級線程映射到一個內(nèi)核級線程，線程管理在用戶空間內(nèi)完成杉编，用戶線程對操作系統(tǒng)不透明嘶朱。這樣做的優(yōu)點是：線程管理在用戶空間內(nèi)進行，效率高财异。缺點是：線程在使用內(nèi)核服務(wù)時被阻塞视事，整個進程都會被阻塞跌穗；多個線程不能并行地運行在多處理機上。

2）一對一：每個用戶級線程映射到相應(yīng)單獨的內(nèi)核級線程上。這樣做的優(yōu)點是：當一個線程被阻塞時佩微，允許另一個線程繼續(xù)執(zhí)行，并發(fā)能力強奶卓。缺點是：每創(chuàng)建一個用戶級線程都需要創(chuàng)建一個內(nèi)核級線程，開銷大瑟幕。

3）多對多：n個用戶級線程映射到m個內(nèi)核級線程上（m≤n）。是上兩個模型的折中站削，集兩者所長。

2.2 處理機調(diào)度

2.2.1 調(diào)度的概念

1.基本概念

處理機調(diào)度是對處理機進行分配园细，即從就緒隊列中按照一定的算法蛛勉，選擇一個進程毡熏，將處理機分配給它使用，實現(xiàn)進程并發(fā)執(zhí)行财搁。是操作系統(tǒng)的基礎(chǔ)，是操作系統(tǒng)設(shè)計的核心問題。

2.調(diào)度的層次

三級調(diào)度：

1）作業(yè)調(diào)度（高級調(diào)度）：按照一定原則從外存上處于后備狀態(tài)的作業(yè)中挑選作業(yè)，給他們分配資源丹弱，建立進程蜓洪，使它們獲得競爭處理機的權(quán)利。多道批處理系統(tǒng)中大多配置，其它操作系統(tǒng)不需配置裳仆，執(zhí)行頻率低，幾分鐘一次液南。

2）終極調(diào)度（內(nèi)存調(diào)度）：提高內(nèi)存利用率和吞吐量统扳，將暫時不運行的進程調(diào)至外存，成為掛起態(tài)，當具備運行條件時粗合，從外存調(diào)度到內(nèi)存萍嬉，成為就緒態(tài)。

3）進程調(diào)度（低級調(diào)度）：按照算法從就緒隊列中選取進程隙疚，分配給其處理機壤追，操作系統(tǒng)都配置供屉，且調(diào)度頻率高行冰，幾十毫秒一次溺蕉。

3.三級調(diào)度的聯(lián)系

作業(yè)調(diào)度為進程活動做準備，進程調(diào)度使進程正车孔觯活動疯特，中級調(diào)度掛起暫時不能運行的進程，處于之間肛走；三者調(diào)度頻率依次上升辙芍；進程調(diào)度最基本，不可或缺羹与。

2.2.2 調(diào)度的時機故硅、切換與過程

現(xiàn)代操作系統(tǒng)中，不能進行進程的調(diào)度與切換的情況有：

1）處理中斷的過程中：處理中斷的過程復(fù)雜纵搁，難以做到進程切換吃衅，在中斷執(zhí)行時，處理器資源不應(yīng)被剝奪腾誉。

2）進程在操作系統(tǒng)內(nèi)核程序的臨界區(qū)中：進入臨界區(qū)后需要獨占式的訪問共享數(shù)據(jù)徘层，必須加鎖。

3）其它需要完全屏蔽中斷的原子操作過程：如加鎖利职、解鎖趣效、中斷現(xiàn)場保護、恢復(fù)等猪贪。

若在上述過程中發(fā)生了引起調(diào)度的條件跷敬，不能馬上進行調(diào)度與切換，應(yīng)置系統(tǒng)的請求調(diào)度標志热押，上述過程完成后再進行西傀。

應(yīng)進行調(diào)度與切換的情況：

1）發(fā)生引起調(diào)度條件且當前進程無法繼續(xù)運行下去，立即調(diào)度和切換桶癣。若操作系統(tǒng)只在這種情況下進行調(diào)度拥褂，屬于非剝奪調(diào)度。

2）中斷處理結(jié)束或自陷處理結(jié)束后牙寞，返回被中斷進程的用戶態(tài)程序執(zhí)行現(xiàn)場前饺鹃，若置上請求調(diào)度標志，則可馬上進行調(diào)度與切換间雀。若操作系統(tǒng)支持這種狀態(tài)下的運行調(diào)度程序悔详，則實現(xiàn)了剝奪方式調(diào)度。

進程切換在調(diào)度完成后立刻發(fā)生雷蹂，要求保存原進程當前切換點的現(xiàn)場信息伟端，恢復(fù)被調(diào)度進程的現(xiàn)場信息。現(xiàn)場切換時匪煌，操作系統(tǒng)內(nèi)核將原進程的現(xiàn)場信息推入當前進程的內(nèi)核堆棧來保存它們责蝠，并更新堆棧指針党巾。內(nèi)核完成從新進程的內(nèi)核棧中裝入新進程的現(xiàn)場信息、更新當前運行進程空間指針霜医、重設(shè)PC寄存器等相關(guān)工作之后齿拂，開始運行新的進程。

2.2.3 進程調(diào)度方式

當某個進程正在處理機上執(zhí)行時肴敛，若有某個更為重要或緊迫的進程需要處理署海，進程調(diào)度的方式，分兩種：

1）非剝奪調(diào)度方式（非搶占方式）：等待正在執(zhí)行的進程執(zhí)行完畢或進入阻塞狀態(tài)時医男，把處理機分配給更為重要的進程砸狞。優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷少镀梭，適用于大多數(shù)批處理系統(tǒng)刀森；缺點是不能用于分時系統(tǒng)和大多數(shù)的實時系統(tǒng)。

2）剝奪調(diào)度方式（搶占方式）：立即暫停正在執(zhí)行的進程报账，將處理機分配給優(yōu)先級更高的進程研底。優(yōu)點是提高系統(tǒng)吞吐和響應(yīng)效率；缺點是對資源的剝奪要設(shè)置更合理的規(guī)則透罢。

2.2.4 調(diào)度的基本準則

不同調(diào)度算法有不同的特性榜晦，為了比較算法性能，人們提出了評價準則羽圃。

1）CPU利用率：要保持CPU始終處于利用率高的狀態(tài)乾胶。

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

3）周轉(zhuǎn)時間：從作業(yè)提交到作業(yè)完成所經(jīng)歷的時間统屈，是作業(yè)等待胚吁、在就緒隊列中排隊牙躺、在處理機上運行愁憔、輸入/輸出操作所花費的時間的總和。

周轉(zhuǎn)時間公式：周轉(zhuǎn)時間=作業(yè)完成時間—作業(yè)提交時間

平均周轉(zhuǎn)時間（多個作業(yè)周轉(zhuǎn)時間的平均值）：

平均周轉(zhuǎn)時間=（作業(yè)1的周轉(zhuǎn)時間+……+作業(yè)n的周轉(zhuǎn)時間）/n

帶權(quán)周轉(zhuǎn)時間是指作業(yè)周轉(zhuǎn)時間與實際作業(yè)時間的比值：

帶權(quán)周轉(zhuǎn)時間=（作業(yè)周轉(zhuǎn)時間）/（作業(yè)實際運行時間）

平均帶權(quán)周轉(zhuǎn)時間是指多個作業(yè)帶權(quán)周轉(zhuǎn)時間的平均值：

平均帶權(quán)周轉(zhuǎn)時間=（作業(yè)1的帶權(quán)周轉(zhuǎn)時間+……+作業(yè)n帶權(quán)周轉(zhuǎn)時間）/n

4）等待時間：指進程處于等處理機狀態(tài)的時間之和孽拷，等待時間越長吨掌，用戶滿意度越低。處理機調(diào)度算法實際上并不影響作業(yè)執(zhí)行或輸入/輸出操作的時間脓恕，只影響作業(yè)在就緒隊列中等待所花的時間膜宋。因此，衡量一個調(diào)度算法的優(yōu)劣炼幔，常常只需考察等待時間秋茫。

5）響應(yīng)時間：從用戶提交請求到系統(tǒng)首次產(chǎn)生響應(yīng)所用的時間。在交互式系統(tǒng)乃秀，用響應(yīng)時間作為衡量調(diào)度算法的重要準則之一肛著。

2.2.5 典型的調(diào)度算法

1.先來先服務(wù)（FCFS）調(diào)度算法

最簡單圆兵，即可用于作業(yè)調(diào)度，又可用于進程調(diào)度枢贿。在作業(yè)調(diào)度中殉农，算法按照在隊列里的順序，調(diào)入內(nèi)存局荚，分配資源超凳，創(chuàng)建進程并放入就緒隊列。

屬于不可剝奪算法耀态，表面上看公平轮傍，但有時作業(yè)等待時間過長，因此它不能作為分時系統(tǒng)和實時系統(tǒng)的主要調(diào)度策略首装。但可與其它策略聯(lián)合使用金麸，如在以優(yōu)先級為調(diào)度策略中，優(yōu)先級相同簿盅，以先到先服務(wù)為策略挥下。

FCFS調(diào)度算法的特點是簡單，但效率低桨醋；對長作業(yè)比較有利棚瘟，對短作業(yè)不利；有利于繁忙型作業(yè)喜最，而不利于I/O繁忙型作業(yè)偎蘸。

2.短作業(yè)優(yōu)先（SJF）調(diào)度算法

從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行瞬内；短進程優(yōu)先（SPF）調(diào)度算法從就緒隊列中選擇一個估計運行時間最短的進程迷雪，為其分配處理機，使之立即執(zhí)行虫蝶，直到進程完成或阻塞章咧，之后釋放處理機。

SJF調(diào)度算法也存在缺點：

1）對長作業(yè)不利：長作業(yè)的周轉(zhuǎn)時間會增加能真，甚至有些長作業(yè)不會被處理赁严，因為可能一直有后到的短作業(yè)優(yōu)先被處理。

2）該算法完全未考慮作業(yè)的緊迫程度粉铐，不能保證急迫的任務(wù)被優(yōu)先處理疼约。

3）由于作業(yè)的長短是根據(jù)用戶所提供的估計執(zhí)行時間而定，而用戶會縮短作業(yè)的估計運行時間蝙泼，可能不能真正做到短作業(yè)優(yōu)先調(diào)度程剥。SJF的平均等待時間、平均周轉(zhuǎn)時間最少汤踏。

3.優(yōu)先級調(diào)度算法

又稱優(yōu)先權(quán)調(diào)度算法织鲸，即可用于作業(yè)調(diào)度哨免，又可用于進程調(diào)度。優(yōu)先級用于描述作業(yè)運行的緊迫程度昙沦。

在作業(yè)調(diào)度中琢唾，每次從作業(yè)后備隊列中選取優(yōu)先級最高的一個或幾個，調(diào)入內(nèi)存盾饮，分配資源采桃，創(chuàng)建進程并放入就緒隊列。在進程調(diào)度中丘损，每次從就緒隊列中選取優(yōu)先級最高的進程普办，分配處理機，執(zhí)行徘钥。

根據(jù)能否搶占正在執(zhí)行的進程衔蹲，分為非剝奪式優(yōu)先級調(diào)度算法，先等待正在運行的作業(yè)運行完畢或這阻塞呈础，之后再執(zhí)行舆驶；剝奪式優(yōu)先級調(diào)度算法，暫停正在執(zhí)行的任務(wù)而钞，執(zhí)行優(yōu)先級高的任務(wù)沙廉。

根據(jù)優(yōu)先級是否可改，分為靜態(tài)和動態(tài)優(yōu)先級臼节，靜態(tài)是優(yōu)先級一直不變撬陵，動態(tài)是優(yōu)先級在任務(wù)執(zhí)行過程中，根據(jù)動態(tài)情況調(diào)整優(yōu)先級网缝。

優(yōu)先級高低比較：

1）系統(tǒng)＞用戶巨税。

2）交互＞非交互。

3）I/O（頻繁用I/O）型＞計算（頻繁用CPU）型粉臊。

4.高響應(yīng)比優(yōu)先調(diào)度算法

主要用于作業(yè)調(diào)度草添，是對FCFS和SJF的一種綜合平衡，同時考慮了每個作業(yè)的等待時間和估計的運行時間维费，每次進行調(diào)度時果元，先計算響應(yīng)比，找出最高的犀盟，優(yōu)先運行。

響應(yīng)比R=（等待時間+要求服務(wù)時間）/要求服務(wù)時間

根據(jù)公式：

1）作業(yè)的等待時間相同時蝇狼，要求服務(wù)時間越短阅畴，響應(yīng)比越高，越有利于短作業(yè)迅耘。

2）要求服務(wù)時間相同時贱枣，作業(yè)的響應(yīng)比由其等待時間決定监署，等待時間越長，其響應(yīng)比越高纽哥，因而它實現(xiàn)的是先來先服務(wù)钠乏。

3）對于長作業(yè)，作業(yè)的響應(yīng)比可以隨等待時間的增加而提高春塌，等待時間足夠長時晓避，其響應(yīng)比便可升到很高，從而也可獲得處理機只壳，因此俏拱，克服了饑餓狀態(tài)，兼顧了長作業(yè)吼句。

5.時間片輪轉(zhuǎn)調(diào)度算法

適用于分時系統(tǒng)锅必，就緒進程按到達時間排隊，依次給每個進程分配一個時間片惕艳，輪流進行執(zhí)行搞隐。時間片的長短由響應(yīng)時間、進程數(shù)目远搪、處理能力等因素決定尔许。

6.多級反饋隊列調(diào)度算法（融合算法）

是時間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法的綜合與發(fā)展。

算法實現(xiàn)思想如下：

1）設(shè)置多個就緒隊列终娃，并為各個隊列賦予不同的優(yōu)先級味廊，優(yōu)先級依次降低。

2）給不同優(yōu)先級隊列分配的時間片不同棠耕。優(yōu)先級越高余佛，時間片越小。

3）新進程進入內(nèi)存后窍荧，首先將它放入第一季隊列（優(yōu)先級最高）的末尾辉巡，按FCFS原則調(diào)度。當輪到該進程執(zhí)行時蕊退，若它能在該時間片內(nèi)完成郊楣，可撤離系統(tǒng)；若未完成瓤荔，該進程轉(zhuǎn)入第二次隊列末尾净蚤，以此類推。

4）僅當?shù)谝患夑犃袨榭諘r输硝，調(diào)度程序才調(diào)度第2級隊列中的進程運行今瀑，以此類推。若處理機正在執(zhí)行第i隊列中的某一進程，此時有優(yōu)先級更高的進程進入隊列橘荠，則此時新進程搶占處理機屿附，而正在運行的進程則被進程調(diào)度程序放在第i隊列的末尾。

優(yōu)勢有如下幾點：

1）終端型作業(yè)用戶：短作業(yè)優(yōu)先哥童。

2）短批處理作業(yè)用戶：周轉(zhuǎn)時間較短挺份。

3）長批處理作業(yè)用戶：經(jīng)過前面幾個隊列得到部分執(zhí)行，不會長期得不到處理贮懈。

2.3 進程同步

2.3.1 進程同步的基本概念

為了協(xié)調(diào)不同進程之間的相互制約關(guān)系匀泊，引入進程同步任连。進程同步簡單理解就是進程的執(zhí)行需要先后執(zhí)行穴翩，保證結(jié)果的正確。

1.臨界資源

一次僅允許一個進程使用的資源稱為臨界資源嘱能，如打印機撬呢，變量或數(shù)據(jù)等伦吠，具有當前進程的獨占性，必須互斥的訪問魂拦。在進程中訪問臨界資源的代碼稱為臨界區(qū)毛仪。臨界資源的訪問分4個過程。

1）進入?yún)^(qū)：為了進入臨界區(qū)使用臨界資源芯勘，進入時要檢查是否可進箱靴，若能進，需設(shè)置正在訪問臨界區(qū)的標志荷愕，防止其它進程進入臨界區(qū)衡怀。

2）臨界區(qū)：訪問臨界資源的代碼，又稱臨界段安疗。

3）退出區(qū)：將正在訪問臨界區(qū)的標志清除抛杨。

4）剩余區(qū)：代碼中的其余部分。

2.同步

也稱直接制約關(guān)系荐类，為完成某個任務(wù)創(chuàng)建多個進程怖现，這些進程執(zhí)行有先后順序，才能保證結(jié)果的正確性玉罐。制約關(guān)系源于它們之間相互合作屈嗤。

3.互斥

也稱間接制約關(guān)系，一個進程進入臨界區(qū)時吊输，此時臨界資源被當前進程獨占饶号，其它進程只能等待。

為禁止多個進程同時進入臨界區(qū)璧亚，同步機制應(yīng)遵循以下準則：

1）空閑讓進：臨界區(qū)空閑時讨韭，可以允許一個請求的進程立即進入臨界區(qū)脂信。

2）忙則等待：臨界區(qū)內(nèi)有進程時癣蟋，其它必須等待透硝。

3）有限等待：對請求訪問的進程，保證其在有限時間內(nèi)進入臨界區(qū)疯搅。

4）讓權(quán)等待：進程不能進入臨界區(qū)時濒生，立即釋放處理器。

2.3.2 實現(xiàn)臨界區(qū)互斥的基本方法

1.軟件實現(xiàn)方法

在進入?yún)^(qū)設(shè)置并檢查一些標志來標明是否有進程在臨界區(qū)中幔欧，若已有罪治，在進入?yún)^(qū)通過循環(huán)檢查進行等待，進程離開臨界區(qū)后則在退出區(qū)修改標志礁蔗。

1）算法一：單標志法觉义。設(shè)置一個公用整型變量turn，指示被允許進入臨界區(qū)的進程編號浴井，turn=n晒骇，允許進程n進入。該算法可以保證一次一個進程進入臨界區(qū)磺浙，但兩個進程必須交替進入洪囤，若某個不再進，另一個也無法進撕氧，造成資源浪費瘤缩。

2）算法二：雙標志法先檢查÷啄啵基本思想是進程進入臨界區(qū)之前剥啤，檢查臨界區(qū)是否被占用（先檢查對方的進程狀態(tài)標志，在置自己的標志）不脯。需設(shè)置一個數(shù)據(jù)flag[i]府怯，若為False，表示i進程未進入臨界區(qū)跨新，True富腊，進入。

優(yōu)點：不用交替進入域帐，可連續(xù)使用赘被；缺點：進程i和進程j可能同時進入臨界區(qū)。在檢查對方的flag后和切換自己的flag前有一段時間肖揣，都通過檢查民假，導(dǎo)致同時進入。

3）算法三：雙標志法后檢查龙优。先將自己的標志設(shè)為True羊异，再檢測對方的狀態(tài)標志，若對方為True，則進程等待野舶，否則進入臨界區(qū)易迹。這樣會導(dǎo)致兩個進程同時想進入臨界區(qū)，但發(fā)現(xiàn)對方也想進平道，兩個進程互相謙讓睹欲，導(dǎo)致誰也進不了。

4）算法四：Peterson‘s Algorithm一屋。為防止兩個進程為進入臨界區(qū)而無限期等待窘疮，設(shè)置變量turn，每個進程先設(shè)置自己的標志后再設(shè)置turn標志冀墨，再同時檢測另一個進程狀態(tài)標志和不允許進入標志闸衫，保證只允許一個進程進入臨界區(qū)。

是算法一和算法三的結(jié)合诽嘉，用flag解決互斥訪問蔚出，turn解決饑餓現(xiàn)象。

2.硬件實現(xiàn)方法

計算機提供了特殊的硬件指令含懊，允許對一個字中的內(nèi)容進行檢測與修正身冬，通過硬件實現(xiàn)稱為低級方法（元方法）

（1）中斷屏蔽方法

當一個進程正在使用處理機執(zhí)行臨界區(qū)代碼時，禁止一切中斷是防止其它進程進入臨界區(qū)的最好方法岔乔，我們稱這種行為為屏蔽中斷酥筝、關(guān)中斷。限制了處理機交替執(zhí)行程序的能力雏门，效率會降低嘿歌。對內(nèi)核來說，在執(zhí)行指令期間茁影，關(guān)中斷很方便宙帝，但不能將關(guān)中斷的權(quán)力交給用戶。

（2）硬件指令方法

TestAndSet指令：是原子操作募闲，功能是讀出指定標志后把標志設(shè)置為真步脓。可以為每個臨界資源設(shè)置共享布爾變量lock浩螺，表示資源的兩種狀態(tài)靴患，true表示正在被占用，初值為false要出。

應(yīng)為每個臨界資源設(shè)置一個共享變量lock鸳君，初值為false；每一個進程中設(shè)置一個局部變量key患蹂，用于與lock交換信息或颊。進入臨界區(qū)前砸紊，先利用Swap指令交換lock與key的內(nèi)容，然后檢查key的狀態(tài)囱挑；有進程在臨界區(qū)時醉顽，重復(fù)交換和檢查過程。

硬件方法的優(yōu)點：適用于任意數(shù)目的進程看铆；簡單徽鼎、易驗證其正確性盛末〉耄可以支持進程內(nèi)有多個臨界區(qū)，只需為每個臨界區(qū)設(shè)置一個布爾變量悄但。

硬件方法的缺點：等待進入臨界區(qū)時耗費處理機時間棠隐，不能實現(xiàn)讓權(quán)等待。從等待進程中隨機選擇一個進入臨界區(qū)檐嚣，但可能有進程一直不能被選上助泽，導(dǎo)致饑餓現(xiàn)象。

2.3.3 信號量

信號量機制是一種功能較強的機制嚎京，可用來解決互斥與同步問題嗡贺，只能被兩個標準的原語wait（S）和signal（S）訪問，也可記為“P操作（申請資源）”與“V操作（釋放資源）”鞍帝。

1.整型信號量

被定義為一個用于表示資源數(shù)目的整型量S诫睬，wait操作中，信號量S≤0帕涌，就會不斷地測試摄凡，因此該機制使進程處于“忙等的狀態(tài)”。

2.記錄型信號量蚓曼，不存在“忙等”現(xiàn)象亲澡，除一個需要一個整型變量之外，再增加一個進程鏈表L纫版，用于鏈接所有等待該資源的進程床绪。可描述為：wait操作其弊，S.value表示進程請求一個該類資源癞己，當S.value＜0時，表示資源已經(jīng)被分完瑞凑，因此調(diào)用block原語末秃，進行自我阻塞，放棄處理機籽御，并將進程插入到該類資源的等待序列练慕，該機制遵循了“讓權(quán)等待”的原則惰匙。

signal操作，表示進程釋放一個資源铃将，使系統(tǒng)中可分配的該資源數(shù)增1项鬼，若加1后S.value（可用的資源數(shù)）≤0，表示等待該資源的進程被阻塞劲阎，調(diào)用wakeup原語進行喚醒绘盟。

3.利用信號量實現(xiàn)同步

信號量機制能用于解決進程間的各種同步問題。設(shè)S為進程1與進程2的公共信號量悯仙，初值為0龄毡。進程2中要使用進程1運行的結(jié)果，若進程2先執(zhí)行锡垄，進程2會被阻塞沦零，當進程1執(zhí)行完畢后，進程2會被置就緒態(tài)货岭，繼續(xù)執(zhí)行路操。

4.利用信號量實現(xiàn)進程互斥

信號量機制也能很方便解決互斥問題。設(shè)S為進程1與進程2互斥的信號量千贯，S的初值為1屯仗。把臨界區(qū)置于P(S)和V(S)之間。當臨界區(qū)空閑時搔谴，進入臨界區(qū)的進程執(zhí)行P操作置S為0魁袜；再有進程執(zhí)行P操作會被阻塞。

總的來說己沛，同步問題中慌核，用前要P，用后要V申尼，兩者之間緊夾動作垮卓。

5.利用信號量實現(xiàn)前驅(qū)關(guān)系

信號量也可用來描述程序之間或語句之間的前驅(qū)關(guān)系，有幾對先后順序师幕，就應(yīng)設(shè)置幾個信號量粟按，初值都為0，再通過判斷信號量的值霹粥，實現(xiàn)先后關(guān)系的確定灭将。

6.分析進程同步和互斥問題的方法步驟

1）關(guān)系分析：找出問題中的進程數(shù)，分析同步與互斥關(guān)系后控。

2）整理思路：找出解決問題的關(guān)鍵點庙曙，根據(jù)流程確定P、V操作的順序浩淘。

3）設(shè)置信號量：根據(jù)上面兩步捌朴，設(shè)置需要的信號量吴攒，確定初值，完善整理砂蔽。

2.3.4 管程

在信號量機制中洼怔，大量的P、V操作容易導(dǎo)致系統(tǒng)死鎖左驾。于是镣隶，引入新的進程同步工具—管程，它的特性保證了進程互斥诡右，無需程序員自己實現(xiàn)互斥安岂，降低死鎖發(fā)生的可能性。

1.管程的定義

用數(shù)據(jù)結(jié)構(gòu)描述硬件和軟件資源稻爬，忽略它們內(nèi)部結(jié)構(gòu)和實現(xiàn)細節(jié)嗜闻，把對該數(shù)據(jù)結(jié)構(gòu)實施的操作定義為一組過程，進程對資源的申請和釋放通過這組過程實現(xiàn)桅锄，這組過程可以通過機制保證進程對資源的互斥訪問，數(shù)據(jù)結(jié)構(gòu)與過程組成的資源管理程序稱為管程（monitor）样眠。

管程由四部分組成：名稱友瘤；局部于管程內(nèi)部的共享結(jié)構(gòu)數(shù)據(jù)說明；對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程（或函數(shù)）檐束；對局部于管程內(nèi)部的共享數(shù)據(jù)設(shè)置初始值的語句辫秧。

管程很像一個類：

1）管程把對共享資源的操作封裝起來，管程內(nèi)的共享數(shù)據(jù)結(jié)構(gòu)只能被管程內(nèi)的過程所訪問被丧。一個進程只有通過調(diào)用管程內(nèi)的過程才能進入管程訪問共享資源盟戏。對于上例，外部進程只能通過調(diào)用take_away()過程來申請一個資源甥桂；歸還資源也一樣柿究。

2）每次只允許一個進程進入管程，實現(xiàn)互斥黄选。多個進程同時調(diào)用take_away（）蝇摸，give_back（），則只有某個進程運行完它調(diào)用的過程后办陷，下個進程才能開始它自己的調(diào)用過程貌夕。

2.條件變量

當一個進程進入管程后被阻塞，直到阻塞的原因解除時民镜，在此期間啡专，如果該進程不釋放管程，其它進程無法進入管程制圈。所以將阻塞原因定義為條件變量（condition）们童。原因有多個辱揭，在管程中設(shè)置多個條件變量。每個條件變量保存了一個等待隊列病附，用于記錄因該條件變量而阻塞的所有進程问窃，對條件變量只能進行兩種操作，wait和signal完沪。

x.wait：當x對應(yīng)的條件不滿足時域庇，正在調(diào)用管程的進程調(diào)用x.wait將自己插入x條件的等待隊列，并釋放管程覆积，此時其它進程可以使用該管程听皿。

x.signal：x對應(yīng)的條件發(fā)生了變化，則調(diào)用x.signal宽档，喚醒一個因x條件而阻塞的進程尉姨。

條件變量和信號量的比較：

相似點：條件變量的wait/signal操作類似于信號量的P/V操作，可以實現(xiàn)進程的阻塞/喚醒吗冤。

不同點：條件變量是“沒有值”的又厉，僅實現(xiàn)了“排隊等待”功能；而信號量是“有值”的椎瘟，信號量的值反映了剩余資源數(shù)覆致，在管程中，剩余資源數(shù)用共享數(shù)據(jù)結(jié)構(gòu)記錄肺蔚。

2.3.5 經(jīng)典同步問題

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

問題描述：一組生產(chǎn)者進程和一組消費者進程共享一個初始為空煌妈、大小為n的緩沖區(qū)，只有緩沖區(qū)沒滿時宣羊，生產(chǎn)者才能把消息放入緩沖區(qū)璧诵，否則必須等待；只有緩沖區(qū)不空時仇冯，消費者才能從中取出消息之宿，否則必須等待。由于緩沖區(qū)是臨界資源赞枕，它只允許一個生產(chǎn)者放入消息澈缺，或一個消費者從中取出消息。

問題分析：

1）關(guān)系分析：生產(chǎn)者和消費者對緩沖區(qū)互斥訪問炕婶，但兩者又是相互協(xié)作關(guān)系姐赡，生產(chǎn)之后才能消費，也是同步關(guān)系柠掂。

2）整理思路：兩個進程同時存在互斥和同步關(guān)系项滑，需要解決兩者的PV操作問題。

3）信號量設(shè)置：mutex為互斥信號量涯贞，用于控制互斥訪問緩沖池枪狂，初始為1危喉；full記錄當前緩沖池中狀態(tài)為滿的緩沖區(qū)數(shù)，初始為0州疾。empty記錄緩沖區(qū)為空的緩沖區(qū)數(shù)辜限，初始為n。

seamphore mutex=1;       //臨界區(qū)互斥信號量
    seamphore empty=n;   //空閑緩沖區(qū)
    seamphore full=0;    //緩沖區(qū)初始化為空
    producer(){          //生產(chǎn)者進程
        while(1){
            produce an item in nextp;   // 生產(chǎn)數(shù)據(jù)
            P(empty);（用什么严蓖，p一下）     // 獲取空緩沖區(qū)單元
            P(mutex);（互斥夾緊）         // 進入臨界區(qū)
            add nextp to buffer;  （行為）//將數(shù)據(jù)放入緩沖區(qū)
            V(mutex);（互斥夾緊）         // 離開臨界區(qū)薄嫡，釋放互斥信號量
            V(full);（提供什么，V一下）     //滿緩沖區(qū)數(shù)加1
        }
    }
    consumer(){      //消費者進程
        while(1){
            P(full);    //獲取滿緩沖區(qū)單元
            P(mutex);  //進入臨界區(qū)
            remove an item from buffer;  // 從緩沖區(qū)取出數(shù)據(jù)
            V(mutex);    // 離開臨界區(qū)颗胡，釋放互斥信號量
            V(empty);    // 空緩沖區(qū)數(shù)加 1
            consume the item;   //消費數(shù)據(jù)
        }
    }

該類問題要注意對緩沖區(qū)大小為n的處理毫深，當緩沖區(qū)中有空時，便可對empty變量執(zhí)行P操作毒姨，取走產(chǎn)品后哑蔫，執(zhí)行V操作釋放空閑區(qū)。對empty和full的P必須放在對mutex的P之前弧呐。釋放信號量時闸迷，mutex、full先釋放哪一個無所謂泉懦。

2.復(fù)雜的生產(chǎn)者-消費者問題

問題描述：有一盤子稿黍，每次只能向其中放入一個水果，爸爸專放蘋果崩哩，媽媽專放橘子，兒子專吃橘子言沐，女兒專吃蘋果邓嘹，只有當盤子空時才放，當盤中僅有自己吃的水果時险胰，才取汹押。

問題分析：

1）關(guān)系分析：每次只能放一種水果，爸爸媽媽是互斥的關(guān)系起便，爸爸和女兒棚贾，媽媽和兒子是同步的關(guān)系。

2）思路整理：兩個生產(chǎn)者和兩個消費者連接到大小為1的緩沖區(qū)上榆综。

3）信號量設(shè)置：將plate設(shè)置成互斥信號量妙痹，初值為1，表示允許放入鼻疮。apple表示盤子中是否有蘋果怯伊，初值為0，orange表示盤子中是否有橘子判沟，初值為0耿芹。

semapore plate=1,apple=0,orange=0;
    dad(){
        while(1){
            prepare an apple;
            P(plate);   //互斥向盤中取崭篡、放水果
            put the apple on the plate;  //向盤中放蘋果
            V(apple);   // 允許取蘋果
        }
    }
    mom(){
        while(1){
            prepare an orange;
            P(plate);
            put the orange on the plate;
            V(orange);
        }
    }
    son(){
        while(1){
            P(orange);  //互斥從盤中取橘子
            take an orange from the plate;
            V(plate);  //允許向盤中放、取水果
            eat the orange;
        }
    }
    daughter(){
        while(1){
            P(apple);
            take an aplle from the plate;
            V(plate);
            eat the apple;
        }
    }

3.讀者-寫者問題

問題描述：有讀者和寫者兩組并發(fā)進程吧秕，共享一個文件琉闪，當兩個或兩個以上的讀進程同時訪問共享數(shù)據(jù)時不會產(chǎn)生副作用，但若某個寫進程和其他進程同時訪問共享數(shù)據(jù)時則可能導(dǎo)致數(shù)據(jù)不一致的錯誤砸彬，因此：

1） 允許多個讀者可以同時對文件執(zhí)行讀操作颠毙；

2） 只允許一個寫者往文件中寫信息；

3） 任一寫者在完成寫操作之前不允許其他讀者進程或?qū)懻哌M程工作拿霉；

4） 寫者執(zhí)行寫操作前吟秩，應(yīng)讓已有的讀者和寫者全部退出。

問題分析：

1）關(guān)系分析：讀者绽淘、寫者互斥涵防，寫者、寫者互斥沪铭，讀者壮池、讀者不互斥。

2）思路整理：寫者和任何進程互斥杀怠，用P椰憋、V操作解決；讀者需實現(xiàn)與寫者互斥赔退，與其它讀者同步橙依，需要用到計數(shù)器，判斷當前是否有讀者讀文件硕旗。不同讀者對計數(shù)器的訪問也是互斥的窗骑。

3）信號量設(shè)置：count為計數(shù)器，記錄當前讀者數(shù)量漆枚，初值為0创译；mutex為互斥信號量，保護更新count變量時的互斥墙基；設(shè)置互斥信號量rw软族，用于保護讀者和寫者的互斥訪問。

int count=0;
    semaphore mutex=1;
    semaphore rw=1;
    writer(){
        while(1){
            P(rw);   // 互斥訪問共享文件
            writing
            V(rw); // 釋放共享文件
        }
    }
    reader(){
        while(1){
            P(mutex);   // 互斥訪問 count 變量
            if(count==0)  // 當?shù)谝粋€讀進程讀共享文件時
                P(rw)  // 阻止寫進程
            count++;
            V(mutex);   // 釋放互斥變量 count
            reading;
            P(mutex); 
            count--;
            if(count==0)   // 當最后一個讀進程讀完共享文件
                V(rw);  // 允許寫進程寫
            V(mutex);
        }
    }

此種方式下残制，可能導(dǎo)致寫進程長時間等待甚至出現(xiàn)“餓死”的情況立砸。改變上面這種讀進程優(yōu)先，讓寫進程優(yōu)先痘拆，需要再增加一個信號量仰禽，并在上面的 writer() 和 reader() 函數(shù)中各增加一對PV操作。如下：

int count=0;
    semaphore mutex=1;
    semaphore rw=1;
    semaphore w=1; // 實現(xiàn)寫者優(yōu)先
    writer(){
        while(1){
            P(w);  // 在無寫進程請求時進入
            P(rw);   // 互斥訪問共享文件
            writing
            V(rw); // 釋放共享文件
            V(w);   // 恢復(fù)對共享文件的訪問
        }
    }
    reader(){
        while(1){
            P(w);  
            P(mutex);   // 互斥訪問 count 變量
            if(count==0)  // 當?shù)谝粋€讀進程讀共享文件時
                P(rw)  // 阻止寫進程
            count++;
            V(mutex);   // 釋放互斥變量 count
            V(w);
            reading;
            P(mutex); 
            count--;
            if(count==0)   // 當最后一個讀進程讀完共享文件
                V(rw);  // 允許寫進程寫
            V(mutex);
        }
    }

此種算法又叫做讀寫公平法。

4.哲學(xué)家進餐問題

問題描述：一張圓桌上坐著5名哲學(xué)家吐葵，每兩名哲學(xué)家之間的桌子上擺著一根筷子规揪，兩根筷子之間是一碗米飯。哲學(xué)家傾注畢生精力于思考和進餐温峭，哲學(xué)家思考時不影響其他人猛铅。只有當哲學(xué)家饑餓時，才試圖拿起左凤藏、右兩根筷子——一根一根地拿起奸忽。若筷子已在他人手上，則需要等待揖庄。饑餓的哲學(xué)家只有同時拿到了兩根筷子才能開始進餐栗菜，進餐完畢，放下筷子繼續(xù)思考蹄梢。

問題分析：

1）關(guān)系分析：左右鄰座對其中間的筷子的訪問是互斥關(guān)系疙筹。

2）整理思路：哲學(xué)家拿到左右兩根筷子不造成死鎖或饑餓現(xiàn)象，解決方法有兩個：第一個同時讓他們拿兩根筷子禁炒，第二個對每個哲學(xué)家的動作制定規(guī)則而咆。

3）信號量設(shè)定：互斥信號量數(shù)組chopstick[5]={1，1幕袱，1暴备，1，1}们豌，哲學(xué)家按順序編號0-4涯捻，哲學(xué)家i左邊筷子編號為i，哲學(xué)家右邊筷子編號為（i+1）%5.

semaphore chopstick[5]={1,1,1,1,1};
    Pi(){
        do{
            P(chopstick[i]);  //取左邊筷子
            P(chopstick[(i+1)%5]);// 取右邊筷子
            eat;
            V(chopstick[i]);  //放回左邊筷子
            V(chopstick[(i+1)%5]);// 放回右邊筷子
            think;
        }while(1);
    }

此算法存在的問題就是望迎，當5名哲學(xué)家都想要進餐并分別拿起左邊的筷子時汰瘫，所有的筷子將被拿光，等到他們再想拿起右邊的筷子時擂煞，就會發(fā)生全被阻塞，出現(xiàn)死鎖趴乡。若要避免此種情況对省，可以增加限制條件，如至多允許4名哲學(xué)家同時進餐晾捏；僅當一名哲學(xué)家左右兩邊筷子都可以用時蒿涎，才允許他抓起筷子；對哲學(xué)家順序編號惦辛，奇數(shù)號哲學(xué)家先拿起左邊筷子劳秋，然后拿起右邊的，而偶數(shù)哲學(xué)家相反。

用正確的規(guī)則如下：假設(shè)采用第二種方法玻淑，當一名哲學(xué)家左右兩邊的筷子都可用時嗽冒，才允許他抓起筷子。

semaphore chopstick[5]={1,1,1,1,1};
    semaphore mutex=1;
    Pi(){
        do{
            P(mutex);  // 在取筷子前獲得互斥量
            P(chopstick[i]);  //取左邊筷子
            P(chopstick[(i+1)%5]);// 取右邊筷子
            V(mutex);  // 釋放取筷子的信號量
            eat;
            V(chopstick[i]);  //放回左邊筷子
            V(chopstick[(i+1)%5]);// 放回右邊筷子
            think;
        }while(1);
    }

5.吸煙者問題

問題描述：假設(shè)一個系統(tǒng)有三個抽煙者進程和一個供應(yīng)者進程补履。每個抽煙者不停地卷煙并抽掉它添坊，但要卷起一支煙，抽煙者需要三種材料：煙草箫锤、紙和膠水贬蛙。三個抽煙者中，第一個擁有煙草谚攒，第二個擁有紙阳准，第三個擁有膠水。供應(yīng)者進程無限地提供三種材料馏臭，供應(yīng)者每次將兩種材料放到桌子上野蝇，擁有剩下那種材料的抽煙者卷一根煙并抽掉它，并給供應(yīng)者一個信號告訴已完成位喂，此時供應(yīng)者就會將另外兩種材料放到桌子上浪耘，循環(huán)反復(fù)如此。

問題分析：

1）關(guān)系分析：供應(yīng)者與三個抽煙者是同步關(guān)系塑崖。三個抽煙者互斥七冲。

2）整理思路：供應(yīng)者作為生產(chǎn)者向三個抽煙者提供材料橘霎。

3）信號量設(shè)置：offer1蹂楣、offer2朽合、offer3分別表示煙草和紙組合的資源履澳、煙草和膠水組合的資源骄呼、紙和膠水組合的資源苍鲜，finish用于互斥進行抽煙動作胸囱。

int random;  // 存儲隨機數(shù)
    semaphore offer1=0;
    semaphore offer2=0;
    semaphore offer3=0;
    semaphore finish=0;
    process P1(){//供應(yīng)者
        while(1){
            random=a random num;
            random=random%3;
            if(random==0)
                V(offer1);  // 提供煙草和紙
            else if(random==1)
                V(offer2);  // 提供煙草和膠水
            else
                V(offer3); //提供紙和膠水
            put on ;  // 將材料放在桌子上
            P(finish);
        }
    }
    process P2(){//擁有煙草者
        while(1){
            P(offer3);
            working;  // 拿起紙和膠水洽瞬，卷成煙嗡髓，抽掉
            V(finish);
        }
    }
    process P3(){//擁有紙者
        while(1){
            P(offer2);
            working;  // 拿起煙草和膠水操漠，卷成煙，抽掉
            V(finish);
        }
    }
    process P4(){//擁有膠水者
        while(1){
            P(offer1);
            working;  // 拿起紙和煙草饿这，卷成煙浊伙，抽掉
            V(finish);
        }
    }

2.4 死鎖

2.4.1 死鎖的概念

1.死鎖的定義

多道程序系統(tǒng)中，雖然提高了系統(tǒng)的處理能力长捧，但多個進程競爭同一資源會造成僵局嚣鄙，我們稱這種僵局為死鎖。

2.死鎖產(chǎn)生的原因

（1）系統(tǒng)資源的競爭

不可剝奪的資源數(shù)量小于進程數(shù)串结，此時對其的競爭可能會引起死鎖哑子，但對可剝奪資源的競爭是不會引起死鎖的舅列。

（2）進程推進順序非法

進程在運行過程中，請求和釋放資源的順序不當卧蜓，當兩個進程擁有不同資源時帐要，這兩個進程互相申請對方擁有資源時，產(chǎn)生死鎖烦却。

信號量使用不當也會造成死鎖宠叼，此時進程間彼此相互等待對方發(fā)來的消息，也會引起死鎖其爵。

（3）死鎖產(chǎn)生的必要條件

有四個冒冬，任意一個不成立，死鎖就不會發(fā)生：

（1）互斥條件：進程要求所分配資源進行排他性控制摩渺，若有進程申請此資源简烤，則只能等待。

（2）不剝奪條件：資源未被使用完時摇幻，不會被奪走横侦，只能由該進程釋放。

（3）請求并保持條件：進程已經(jīng)保持了至少一個資源绰姻，但又提出了新的資源請求枉侧，該資源等待，同時不釋放已經(jīng)保持的資源狂芋。

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

2.4.2 死鎖的處理策略

必須破壞上述四個條件之一帜矾，或允許死鎖產(chǎn)生翼虫，且能檢測出死鎖，并有能力實現(xiàn)恢復(fù)屡萤。

1.預(yù)防死鎖：設(shè)置某些限制條件珍剑，破壞產(chǎn)生死鎖產(chǎn)生的必要條件。

2.避免死鎖：在資源分配過程中死陆，用某種方法防止系統(tǒng)進入不安全狀態(tài)招拙，從而避免死鎖。

3.死鎖的檢測及解除：允許發(fā)生死鎖措译，但及時檢測發(fā)現(xiàn)死鎖迫像，并采取某個措施解除死鎖。

預(yù)防死鎖和避免死鎖都屬于事先預(yù)防策略瞳遍，預(yù)防的限制條件較嚴格，實現(xiàn)簡單菌羽，但導(dǎo)致效率低掠械；避免死鎖的限制條件相對寬松，資源分配后需要通過算法來判斷是否進入不安全狀態(tài)，實現(xiàn)復(fù)雜猾蒂。

各種資源的比較：

2.4.3 預(yù)防死鎖

防止死鎖的發(fā)生只需破壞死鎖產(chǎn)生的4個必要條件之一即可均唉。

1.破壞互斥條件：若允許系統(tǒng)資源都能共享使用，系統(tǒng)不會死鎖肚菠，但有些資源不能同時訪問舔箭，有些場合需要保護某種資源的互斥性。

2.破壞不剝奪條件：當某個進程保持了某個資源蚊逢，它申請新的資源得不到滿足時层扶，它必須釋放已經(jīng)保持的所有資源，以后需要時再申請烙荷。這種策略會增加系統(tǒng)開銷镜会，降低系統(tǒng)吞吐量，所以這種方法常用于狀態(tài)易于保存和恢復(fù)的資源终抽，如CPU的寄存器及內(nèi)存資源戳表。

3.破環(huán)請求并保持條件：采用預(yù)先靜態(tài)分配方法，即進程在運行前一次申請完它所需要的全部資源昼伴，在資源未滿足前匾旭，不把它投入運行。一旦投入運行圃郊，資源一直歸它所有价涝，不再提出其它資源請求，保證不死鎖描沟。此策略會導(dǎo)致系統(tǒng)資源被浪費飒泻，并且由于個別資源長期被某個進程占用，導(dǎo)致饑餓現(xiàn)象吏廉。

4.破壞循環(huán)等待條件：采用順序資源分配法泞遗，先給資源編號，規(guī)定進程必須按照編號申請資源席覆，同類資源一次申請完成史辙，例如，某個進程申請5號資源佩伤，它以后只能申請5號之后的資源聊倔。這種策略的問題是編號必須相對穩(wěn)定，限制了新類型設(shè)備的增加生巡，且會經(jīng)常發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定順序不同的情況耙蔑，造成資源浪費。

2.4.4 避免死鎖

在資源動態(tài)分配過程中孤荣，防止系統(tǒng)進入不安全的狀態(tài)甸陌，避免死鎖的發(fā)生须揣，限制弱，系統(tǒng)性能高钱豁。

1.系統(tǒng)安全狀態(tài)

安全狀態(tài)是指系統(tǒng)能按照某種進程推進順序為每個進程分配所需資源耻卡，直至滿足每個進程對資源的最大需求，使每個進程都可順序完成牲尺，反之則稱為不安全狀態(tài)卵酪。系統(tǒng)進入不安全狀態(tài)時，可能導(dǎo)致死鎖谤碳。

2.銀行家算法

思想是把操作系統(tǒng)視為銀行家溃卡，資源相當于資金，請求分配資源相當于申請貸款估蹄。進程運行之前先聲明對各種資源的最大需求量塑煎，當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過該進程聲明的最大需求量臭蚁，若能滿足則按當前的申請量分配資源最铁，否則要推遲分配。

（1）數(shù)據(jù)結(jié)構(gòu)描述

可利用資源向量Available：含有m個元素的數(shù)組垮兑，其中每個元素代表一類可用的資源數(shù)目冷尉。

最大需求矩陣Max：n*m矩陣，定義系統(tǒng)中n個進程中的每個進程對m類資源的最大需求系枪。簡單來說雀哨，一行代表一個進程，一列代表一類資源私爷。

分配矩陣：Allocation：n*m矩陣雾棺，定義系統(tǒng)中每類資源當前分配給每個進程的資源數(shù)。

需求矩陣：Need：n*m矩陣衬浑，定義每個進程接下來還需多少資源捌浩。

三個矩陣關(guān)系：Need=Max-Allocation

一般情況下，Max和Allocation是已知條件工秩，求Need是第一步尸饺。

（2）銀行家算法描述：

先Request，若Request的量≤Need的量成立（不成立助币，則認為出錯浪听。），再判斷Request的量≤Available的量成立（若不成立眉菱，該進程必須等待）迹栓，系統(tǒng)嘗試將資源分配給進程，并修改下面數(shù)據(jù)結(jié)構(gòu)的數(shù)值俭缓，其中：

Available=Available-Request迈螟；Allocation=Allocation+Request叉抡；Need=Need-Request。

最后答毫，系統(tǒng)執(zhí)行安全性算法，檢測此次資源分配后季春，系統(tǒng)是否處于安全狀態(tài)洗搂，若安全，則正式分配载弄，不安全耘拇，放棄分配，讓進程等待宇攻。

（3）安全性算法

設(shè)置工作向量Work惫叛，有m個元素，表示剩余的可用資源數(shù)逞刷，安全性算法開始時嘉涌，work=available。

步驟一：初始時安全序列為空夸浅；

步驟二：從Need矩陣中找出符合下面條件的行：該行對應(yīng)的進程不在安全序列中仑最，而且該行小于等于Work向量，找到后帆喇，把對應(yīng)進程加入安全序列警医，若找不到，執(zhí)行步驟四坯钦；

步驟三：進程進入安全序列后预皇，可順利執(zhí)行，直至完成婉刀，并釋放分配給它的資源吟温，執(zhí)行Work=Work+Allocation，返回步驟二路星；

步驟四：若此時安全序列中已有所有進程溯街，則系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)洋丐。

2.4.5 死鎖檢測和解除

系統(tǒng)在分配資源時不采取任何措施呈昔，應(yīng)會提供死鎖檢測和解除的手段。

1.資源分配圖

圓圈代表一個進程友绝，框代表一類資源堤尾。由于一種類型的資源可能有多個，框中的一個圓圈代表一類資源中的一個資源迁客。從進程到資源的有向邊稱為請求邊郭宝，表示申請資源辞槐；從資源到進程的邊稱為分配邊，表示資源分配給進程粘室。

2.死鎖定理

簡化資源分配圖可檢測系統(tǒng)狀態(tài)S是否為死鎖狀態(tài)榄檬。簡化方法如下：

1）在資源分配圖中，找出既不阻塞衔统，又不孤點的進程（找出一條有向邊與它相連鹿榜，且該有向邊對應(yīng)資源的申請數(shù)量小于等于系統(tǒng)中已有的空閑資源數(shù)量），若所有連接該進程的邊均滿足上述條件锦爵，則這個進程能繼續(xù)運行直至完成舱殿，然后釋放它所占有的資源。之后消去它所有的請求邊和分配邊险掀，使之稱為孤立的點沪袭。總結(jié)為找圈消邊樟氢。

2）進程所釋放的資源冈绊，可以喚醒某些因等待這些資源而阻塞的進程，原來阻塞進程可能變?yōu)榉亲枞M程嗡害。根據(jù)1）中的方法進行簡化焚碌，若能消除所有邊，稱該圖是可完全可以簡化的霸妹。S為死鎖的條件是當且僅當S狀態(tài)的資源分配圖是不可完全簡化的十电，稱為死鎖條件。

3.死鎖解除

1）資源剝奪法：掛起某些死鎖的進程叹螟，并搶占它的資源鹃骂，將這些資源分配給其它的死鎖進程。但應(yīng)防止被掛起的進程長時間得不到資源而處于資源匱乏的狀態(tài)罢绽。

2）撤銷進程法：強制撤銷部分甚至全部死鎖進程并剝奪這些進程的資源畏线。撤銷的原則可以按進程優(yōu)先級和撤銷進程代價的高低進行。

3）進程回退法：讓若干個進程回退到足以回避死鎖的地步良价，進程回退時自愿放棄資源而非被剝奪寝殴。要求系統(tǒng)保持進程的歷史信息，設(shè)置還原點明垢。