進(jìn)程管理1進(jìn)程的基本概念2進(jìn)程控制3進(jìn)程互斥和同步4進(jìn)程通信5進(jìn)程調(diào)度6死鎖7線程8Linux中的進(jìn)程管理進(jìn)程管理1進(jìn)程的基本概念7.1進(jìn)程的基本概念7.1.1程序的順序執(zhí)行和并發(fā)執(zhí)行1．程序的順序執(zhí)行所謂程序的順序執(zhí)行是指該程序獨(dú)占整個(gè)系統(tǒng)中的所有資源，處理機(jī)嚴(yán)格按照程序所規(guī)定的順序進(jìn)行操作，只有在前一個(gè)操作執(zhí)行完后，才進(jìn)行后繼操作。7.1進(jìn)程的基本概念7.1.1程序的順序執(zhí)行和并發(fā)程序的順序執(zhí)行有以下特征。（1）順序性。（2）封閉性。（3）可再現(xiàn)性。程序的順序執(zhí)行有以下特征。2．多道程序設(shè)計(jì)的引入執(zhí)行環(huán)境具有下述3個(gè)特點(diǎn)。（1）獨(dú)立性。（2）隨機(jī)性。（3）資源共享。2．多道程序設(shè)計(jì)的引入3．程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行可總結(jié)為：一組在邏輯上互相獨(dú)立的程序或程序段在執(zhí)行過(guò)程中其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始的執(zhí)行方式。3．程序的并發(fā)執(zhí)行程序并發(fā)執(zhí)行時(shí)具有如下特征。（1）間斷性。（2）失去封閉性。（3）不可再現(xiàn)性。程序并發(fā)執(zhí)行時(shí)具有如下特征。7.1.2進(jìn)程的定義和特征1．進(jìn)程的定義進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。7.1.2進(jìn)程的定義和特征2．進(jìn)程的特征（1）結(jié)構(gòu)特征（2）動(dòng)態(tài)性（3）并發(fā)性（4）獨(dú)立性（5）異步性2．進(jìn)程的特征7.1.3進(jìn)程的狀態(tài)及其轉(zhuǎn)換1．進(jìn)程的基本狀態(tài)（1）就緒狀態(tài)當(dāng)進(jìn)程已分配到除處理機(jī)以外的所有必要的資源后，只要再獲得處理機(jī)便可立即執(zhí)行，這時(shí)進(jìn)程的狀態(tài)稱為就緒狀態(tài)。7.1.3進(jìn)程的狀態(tài)及其轉(zhuǎn)換（2）執(zhí)行狀態(tài)執(zhí)行狀態(tài)是指進(jìn)程已獲得處理機(jī)、其程序正在執(zhí)行的狀態(tài)。（3）阻塞狀態(tài)正在執(zhí)行的進(jìn)程因發(fā)生某事件而暫時(shí)無(wú)法繼續(xù)執(zhí)行時(shí)，便放棄處理機(jī)而處于暫停狀態(tài)，這種暫停狀態(tài)被稱為阻塞狀態(tài)。（2）執(zhí)行狀態(tài)2．進(jìn)程的狀態(tài)轉(zhuǎn)換圖7.1進(jìn)程的3種基本狀態(tài)及其轉(zhuǎn)換2．進(jìn)程的狀態(tài)轉(zhuǎn)換圖7.1進(jìn)程的3種基本狀態(tài)及其轉(zhuǎn)換7.1.4進(jìn)程的結(jié)構(gòu)1．進(jìn)程的實(shí)體（1）進(jìn)程控制塊（PCB）（2）程序段（3）數(shù)據(jù)段7.1.4進(jìn)程的結(jié)構(gòu)2．進(jìn)程控制塊進(jìn)程控制塊是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。PCB中記錄了操作系統(tǒng)所需的，用于描述進(jìn)程進(jìn)展情況及控制進(jìn)程運(yùn)行所需的全部信息。PCB是進(jìn)程存在的惟一標(biāo)志。一般把PCB存放在操作系統(tǒng)專門開辟的PCB區(qū)內(nèi)。2．進(jìn)程控制塊在進(jìn)程控制塊中，主要包括下述4方面的信息。（1）進(jìn)程描述信息進(jìn)程標(biāo)識(shí)符。每個(gè)進(jìn)程都有惟一的進(jìn)程標(biāo)識(shí)符，用以識(shí)別不同的進(jìn)程。用戶名或用戶標(biāo)識(shí)號(hào)。每個(gè)進(jìn)程都隸屬于某個(gè)用戶，有利于資源共享與保護(hù)。家族關(guān)系。標(biāo)識(shí)進(jìn)程之間的家族關(guān)系。在進(jìn)程控制塊中，主要包括下述4方面的信息。（2）處理機(jī)狀態(tài)信息通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字（PSW）、用戶棧指針等（3）進(jìn)程調(diào)度信息進(jìn)程狀態(tài)。指明進(jìn)程的當(dāng)前狀態(tài)，以作為進(jìn)程調(diào)度和進(jìn)程對(duì)換時(shí)的依據(jù)。（2）處理機(jī)狀態(tài)信息進(jìn)程優(yōu)先級(jí)。用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)，優(yōu)先級(jí)別高的進(jìn)程先獲得處理機(jī)。進(jìn)程調(diào)度所需的其他信息。如進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等。事件。指進(jìn)程被阻塞的原因。進(jìn)程優(yōu)先級(jí)。用于描述進(jìn)程使用處理機(jī)的優(yōu)（4）進(jìn)程控制信息程序和數(shù)據(jù)的地址。指出該進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從中找到其程序和數(shù)據(jù)。進(jìn)程同步和通信機(jī)制。指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)所必須的機(jī)制，如消息隊(duì)列指針、信號(hào)量等。這些數(shù)據(jù)應(yīng)全部或部分地存放在PCB中。（4）進(jìn)程控制信息資源清單。它是一張列出了除CPU之外的進(jìn)程所需的全部資源和已經(jīng)分配給該進(jìn)程的資源清單。鏈接指針。它給出了本進(jìn)程（PCB）所在隊(duì)列的下一個(gè)進(jìn)程的PCB首地址。在一個(gè)系統(tǒng)中，通常擁有數(shù)十個(gè)、數(shù)百個(gè)乃至數(shù)千個(gè)PCB。為了對(duì)PCB進(jìn)行有效地管理，系統(tǒng)應(yīng)把所有的PCB用適當(dāng)?shù)姆绞浇M織起來(lái)。目前常用的PCB組織方式有鏈接方式和索引方式兩種。資源清單。它是一張列出了除CPU之外的進(jìn)①鏈接方式圖7.2PCB鏈接隊(duì)列示意圖①鏈接方式圖7.2PCB鏈接隊(duì)列示意圖②索引方式圖7.3PCB索引方式示意圖②索引方式圖7.3PCB索引方式示意圖7.2進(jìn)程控制7.2.1操作系統(tǒng)內(nèi)核為了防止操作系統(tǒng)及關(guān)鍵數(shù)據(jù)（如PCB等）受到用戶程序有意無(wú)意的破壞，通常將處理機(jī)的執(zhí)行狀態(tài)分成系統(tǒng)態(tài)和用戶態(tài)兩種。7.2進(jìn)程控制7.2.1操作系統(tǒng)內(nèi)核（1）系統(tǒng)態(tài)。它具有較高特權(quán)，能執(zhí)行一切指令，訪問(wèn)所有寄存器和存儲(chǔ)區(qū)。（2）用戶態(tài)。這是具有較低特權(quán)的執(zhí)行狀態(tài)，只能執(zhí)行規(guī)定的指令，訪問(wèn)指定的寄存器和存儲(chǔ)區(qū)。（1）系統(tǒng)態(tài)。它具有較高特權(quán)，能執(zhí)行一切指令，訪問(wèn)所有寄存器（3）操作系統(tǒng)內(nèi)核： 在進(jìn)行層次設(shè)計(jì)時(shí)，通常將一些與硬件緊密相關(guān)的模塊，諸如中斷處理程序、常用的設(shè)備驅(qū)動(dòng)程序以及運(yùn)行頻率較高的模塊（如時(shí)鐘管理、進(jìn)程調(diào)度和公共基本操作模塊）都安排在緊靠硬件的軟件層次中，并使之常駐內(nèi)存，以提高操作系統(tǒng)的運(yùn)行效率，通常把這一部分稱為操作系統(tǒng)的內(nèi)核（Kernel）。（3）操作系統(tǒng)內(nèi)核：7.2.2進(jìn)程控制的概念進(jìn)程控制是進(jìn)程和處理機(jī)管理的一個(gè)重要任務(wù)。所謂進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段來(lái)創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程在各種狀態(tài)之間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)資源共享的目的。7.2.2進(jìn)程控制的概念7.2.3進(jìn)程的創(chuàng)建與撤消1．進(jìn)程的創(chuàng)建2．進(jìn)程的撤消7.2.3進(jìn)程的創(chuàng)建與撤消7.2.4進(jìn)程的阻塞與喚醒1．進(jìn)程的阻塞2．進(jìn)程的喚醒7.2.4進(jìn)程的阻塞與喚醒7.3進(jìn)程互斥和同步7.3.1進(jìn)程互斥1．互斥的概念所謂進(jìn)程互斥是指當(dāng)有若干進(jìn)程都要使用某一共享資源時(shí)，任何時(shí)刻最多允許一個(gè)進(jìn)程使用，其他要使用該資源的進(jìn)程必須等待，直到占用該資源者釋放了該資源為止。7.3進(jìn)程互斥和同步7.3.1進(jìn)程互斥2．臨界資源操作系統(tǒng)中將一次只允許一個(gè)進(jìn)程訪問(wèn)的資源稱為臨界資源。2．臨界資源3．臨界區(qū)（CriticalSection）把進(jìn)程中訪問(wèn)臨界資源的那段程序代碼段稱為臨界區(qū)。為實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)，應(yīng)保證諸進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。必須在臨界區(qū)前面增加一段用于進(jìn)行上述檢查的代碼，我們把這段代碼段稱為進(jìn)入?yún)^(qū)（EntrySection）；相應(yīng)地，在臨界區(qū)后面也要加上一段稱為退出區(qū)（ExitSection）的代碼，用于將臨界區(qū)正被訪問(wèn)的標(biāo)志恢復(fù)為未被訪問(wèn)的標(biāo)志。3．臨界區(qū)（CriticalSection）一個(gè)含有訪問(wèn)某一臨界資源的循環(huán)進(jìn)程可描述如下：

while(TRUE){entrysectioncriticalsectionexitsectionremaindersection}一個(gè)含有訪問(wèn)某一臨界資源的循環(huán)進(jìn)程可描述如下：4．同步機(jī)制應(yīng)遵循的準(zhǔn)則（1）空閑讓進(jìn)。（2）忙則等待。（3）讓權(quán)等待。（4）有限等待。4．同步機(jī)制應(yīng)遵循的準(zhǔn)則7.3.2進(jìn)程同步1．同步的概念把異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約，使得各進(jìn)程按一定的速度執(zhí)行的過(guò)程稱為進(jìn)程間的同步。具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間互相發(fā)送的信號(hào)稱為消息或事件。7.3.2進(jìn)程同步2．同步與互斥的關(guān)系進(jìn)程的同步與進(jìn)程的互斥都涉及到并發(fā)進(jìn)程共享資源的問(wèn)題，進(jìn)程的互斥實(shí)際上是進(jìn)程同步的一種特殊情況。有時(shí)也把進(jìn)程的互斥與進(jìn)程的同步統(tǒng)稱為進(jìn)程的同步。2．同步與互斥的關(guān)系7.3.3信號(hào)量機(jī)制1．記錄型信號(hào)量

structsemaphore{intvalue；PCB*L；}S；7.3.3信號(hào)量機(jī)制2．P、V原語(yǔ)操作除了給信號(hào)量S初始化外，信號(hào)量的數(shù)值域僅能由P、V原語(yǔ)操作改變（P和V分別是荷蘭語(yǔ)Passeren和Verhoog的第一個(gè)字母，相當(dāng)于英文的Pass和Increment的意思）。2．P、V原語(yǔ)操作P原語(yǔ)操作的主要?jiǎng)幼魇牵海?）S.value減1；（2）若S.value減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；（3）若S.value減1后小于零，則該進(jìn)程被阻塞，進(jìn)入與該信號(hào)量相對(duì)應(yīng)的等待隊(duì)列L中，然后轉(zhuǎn)進(jìn)程調(diào)度。P原語(yǔ)操作的功能框圖如圖7.8。P原語(yǔ)操作的主要?jiǎng)幼魇牵簣D7.8P原語(yǔ)操作功能圖7.8P原語(yǔ)操作功能V原語(yǔ)操作的主要?jiǎng)幼魇牵海?）S.value加1；（2）若S.value加1后結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；（3）若S.value加1后結(jié)果小于或等于零，則從該信號(hào)量的等待隊(duì)列L中喚醒一個(gè)等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。V原語(yǔ)操作的功能框圖如圖7.9。V原語(yǔ)操作的主要?jiǎng)幼魇牵簣D7.9V原語(yǔ)操作功能圖7.9V原語(yǔ)操作功能7.3.4進(jìn)程互斥和同步的實(shí)現(xiàn)1．進(jìn)程互斥的實(shí)現(xiàn)2．進(jìn)程同步的實(shí)現(xiàn)7.3.4進(jìn)程互斥和同步的實(shí)現(xiàn)7.4進(jìn)程通信

通信（Communication）意味著在進(jìn)程間傳送數(shù)據(jù)。也把進(jìn)程間控制信息的交換稱為低級(jí)通信，而把進(jìn)程間大批量數(shù)據(jù)的交換稱為高級(jí)通信。7.4進(jìn)程通信通信（Commun7.4.1進(jìn)程通信的類型1．共享存儲(chǔ)器系統(tǒng)共享存儲(chǔ)器系統(tǒng)為了傳送大量數(shù)據(jù)，在存儲(chǔ)器中劃出一塊共享存儲(chǔ)區(qū)，諸進(jìn)程可通過(guò)對(duì)共享存儲(chǔ)區(qū)進(jìn)行讀數(shù)據(jù)或?qū)憯?shù)據(jù)以實(shí)現(xiàn)通信。7.4.1進(jìn)程通信的類型2．消息傳遞系統(tǒng)分為以下兩種。（1）直接通信方式發(fā)送進(jìn)程可將消息直接發(fā)送給接收進(jìn)程，即將消息掛在接收進(jìn)程的消息緩沖隊(duì)列上，而接收進(jìn)程可從自己的消息緩沖隊(duì)列中取得消息。（2）間接通信方式發(fā)送進(jìn)程將消息發(fā)送到指定的信箱中，而接收進(jìn)程從信箱中取得消息。2．消息傳遞系統(tǒng)3．管道通信系統(tǒng)在UNIX操作系統(tǒng)中，開創(chuàng)了一種借助文件和文件系統(tǒng)形成的一種通信方式。所謂管道是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程，以實(shí)現(xiàn)它們之間通信的共享文件，又稱pipe文件。向管道提供輸入的發(fā)送進(jìn)程，以字符流方式將大量的數(shù)據(jù)送入管道，而接收進(jìn)程從管道中接收數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故稱為管道通信。3．管道通信系統(tǒng)7.4.2消息緩沖隊(duì)列通信機(jī)制1．消息緩沖隊(duì)列通信機(jī)制簡(jiǎn)介由于消息緩沖機(jī)制中所使用的緩沖區(qū)為公用緩沖區(qū)，因此使用消息緩沖機(jī)制傳送數(shù)據(jù)時(shí)，兩通信進(jìn)程必須滿足如下條件。7.4.2消息緩沖隊(duì)列通信機(jī)制第一，在發(fā)送進(jìn)程把寫入消息的緩沖區(qū)掛入消息隊(duì)列時(shí)，應(yīng)禁止其他進(jìn)程對(duì)該消息隊(duì)列的訪問(wèn)，否則，將引起消息隊(duì)列的混亂。同理，當(dāng)接收進(jìn)程正從消息隊(duì)列中取消息時(shí)，也應(yīng)禁止其他進(jìn)程對(duì)該隊(duì)列的訪問(wèn)。第二，當(dāng)緩沖區(qū)中無(wú)消息存在時(shí)，接收進(jìn)程不能接收到任何消息；而發(fā)送進(jìn)程是否可以發(fā)送消息，則只由發(fā)送進(jìn)程是否能夠申請(qǐng)到緩沖區(qū)決定。第一，在發(fā)送進(jìn)程把寫入消息的緩沖區(qū)掛入消息隊(duì)列時(shí)2．消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)（1）消息緩沖區(qū)

typedefstructmessagebuffer{sender； //發(fā)送者進(jìn)程標(biāo)識(shí)符

size； //消息長(zhǎng)度

text； //消息正文

next； //指向下一個(gè)消息緩沖區(qū)的指針}2．消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)（2）PCB中有關(guān)進(jìn)程通信的數(shù)據(jù)項(xiàng)

typedefstructmessageblock{…mq； //消息隊(duì)列隊(duì)首指針

mutex；//消息隊(duì)列互斥信號(hào)量，初值為1

sm； //消息隊(duì)列資源信號(hào)量，用于消息隊(duì)列中的消息計(jì)數(shù)，初值為0…}（2）PCB中有關(guān)進(jìn)程通信的數(shù)據(jù)項(xiàng)7.5進(jìn)程調(diào)度7.5.1進(jìn)程調(diào)度的概念1．高級(jí)、中級(jí)和低級(jí)調(diào)度（1）高級(jí)調(diào)度高級(jí)調(diào)度通常也稱作業(yè)調(diào)度，用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，準(zhǔn)備執(zhí)行。7.5進(jìn)程調(diào)度7.5.1進(jìn)程調(diào)度的概念（2）中級(jí)調(diào)度中級(jí)調(diào)度大多針對(duì)于分時(shí)系統(tǒng)，是按一定的算法在內(nèi)存和外存之間進(jìn)行進(jìn)程對(duì)換，目的在于緩和內(nèi)存的緊張。（3）低級(jí)調(diào)度 低級(jí)調(diào)度用于將內(nèi)存中就緒隊(duì)列中的作業(yè)分配處理機(jī)，使其執(zhí)行。（2）中級(jí)調(diào)度2．進(jìn)程調(diào)度的方式進(jìn)程調(diào)度通常有以下兩種方式。（1）非剝奪方式（2）剝奪方式3．進(jìn)程調(diào)度的功能4．進(jìn)程調(diào)度算法的性能評(píng)價(jià)2．進(jìn)程調(diào)度的方式7.5.2進(jìn)程調(diào)度算法1．先來(lái)先服務(wù)調(diào)度算法在進(jìn)程調(diào)度中，采用FCFS算法時(shí)，進(jìn)程調(diào)度程序從就緒進(jìn)程隊(duì)列中，選擇一個(gè)最先進(jìn)入隊(duì)列的進(jìn)程，把處理機(jī)分配給它，讓它進(jìn)入執(zhí)行狀態(tài)。公平性，并且實(shí)現(xiàn)也比較容易，這是它的優(yōu)點(diǎn)。但是，它的缺點(diǎn)是實(shí)際上不公平，它比較有利于長(zhǎng)進(jìn)程，而不利于短進(jìn)程。7.5.2進(jìn)程調(diào)度算法2．短進(jìn)程優(yōu)先調(diào)度算法短進(jìn)程優(yōu)先（SPF）調(diào)度算法，是指對(duì)執(zhí)行時(shí)間短的進(jìn)程優(yōu)先調(diào)度的算法。SPF是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或因等待某事件發(fā)生而放棄處理機(jī)時(shí)，再重新調(diào)度。2．短進(jìn)程優(yōu)先調(diào)度算法采用SPF算法，平均周轉(zhuǎn)時(shí)間比FCFS調(diào)度算法有很多改善，這是它的優(yōu)點(diǎn)。SPF調(diào)度算法的缺點(diǎn)是如下所述。第一，對(duì)長(zhǎng)進(jìn)程非常不利。第二，緊迫進(jìn)程不能及時(shí)處理。第三，執(zhí)行時(shí)間的估計(jì)值不準(zhǔn)確。采用SPF算法，平均周轉(zhuǎn)時(shí)間比FCFS調(diào)度算法有很多改善，這3．高優(yōu)先級(jí)優(yōu)先調(diào)度算法考慮到系統(tǒng)中的緊迫進(jìn)程能得到優(yōu)先處理，引入了高優(yōu)先級(jí)優(yōu)先（HPF）調(diào)度算法，處理機(jī)總是分配給就緒進(jìn)程隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程。進(jìn)程的優(yōu)先級(jí)可采用靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)兩種，優(yōu)先級(jí)可由用戶自定或由系統(tǒng)確定。3．高優(yōu)先級(jí)優(yōu)先調(diào)度算法4．時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法的基本思想是將CPU的處理時(shí)間分成固定大小的時(shí)間片。如果一個(gè)進(jìn)程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時(shí)間片，但未完成要求的任務(wù)，則它自行釋放自己所占有的CPU，而排到就緒隊(duì)列的末尾，等待下一次調(diào)度。同時(shí)，進(jìn)程調(diào)度程序又去調(diào)度當(dāng)前就緒隊(duì)列中的第一個(gè)進(jìn)程。4．時(shí)間片輪轉(zhuǎn)法5．多級(jí)反饋隊(duì)列調(diào)度算法其基本思想如下所述。（1）系統(tǒng)按優(yōu)先級(jí)設(shè)置N個(gè)就緒進(jìn)程隊(duì)列，第一級(jí)隊(duì)列的優(yōu)先級(jí)最高，其余隊(duì)列的優(yōu)先級(jí)逐個(gè)降低，第N級(jí)隊(duì)列的優(yōu)先級(jí)最低。5．多級(jí)反饋隊(duì)列調(diào)度算法7.6死鎖在多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行，共享系統(tǒng)資源，從而提高了資源利用率和系統(tǒng)吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖。所謂死鎖，是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而形成一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。7.6死鎖在多道程序系統(tǒng)中，多個(gè)進(jìn)程7.6.1產(chǎn)生死鎖的原因和必要條件1．產(chǎn)生死鎖的原因產(chǎn)生死鎖的主要原因可歸結(jié)為以下兩點(diǎn)。（1）競(jìng)爭(zhēng)資源（2）進(jìn)程推進(jìn)順序不當(dāng)7.6.1產(chǎn)生死鎖的原因和必要條件2．產(chǎn)生死鎖的必要條件（1）互斥條件一個(gè)資源在一段時(shí)間內(nèi)只能被一個(gè)進(jìn)程所使用，具有排它性。（2）請(qǐng)求和保持條件一個(gè)進(jìn)程在請(qǐng)求新資源而阻塞時(shí)，對(duì)已獲得資源又保持不放。2．產(chǎn)生死鎖的必要條件（3）不剝奪條件進(jìn)程已獲得的資源，在未使用完之前不能被剝奪，只能在使用完時(shí)由自己釋放。（4）環(huán)路等待條件在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈。即進(jìn)程集合{P1，P2，…，Pn}中的P1正在等待P2占用的資源，P2正在等待P3占用的資源，…，Pn正在等待P1占用的資源。（3）不剝奪條件只要同時(shí)具備上述4個(gè)必要條件，系統(tǒng)就會(huì)發(fā)生死鎖，只要上述條件之一不滿足，系統(tǒng)就不會(huì)發(fā)生死鎖。只要同時(shí)具備上述4個(gè)必要條件，系統(tǒng)就會(huì)發(fā)生死鎖，3．處理死鎖的方法由于死鎖狀態(tài)的出現(xiàn)會(huì)給整個(gè)系統(tǒng)帶來(lái)嚴(yán)重的后果，所以如何解決死鎖問(wèn)題引起了人們的普遍關(guān)注。目前常用的方法有以下3種。3．處理死鎖的方法（1）預(yù)防死鎖為了使系統(tǒng)中不發(fā)生死鎖現(xiàn)象，在系統(tǒng)設(shè)計(jì)初期即選擇一些限制條件，來(lái)破壞產(chǎn)生死鎖的4個(gè)必要條件之一或其中幾個(gè)。這樣，系統(tǒng)中就不會(huì)出現(xiàn)死鎖現(xiàn)象。這種方法對(duì)預(yù)防死鎖的發(fā)生非常有效，但有可能降低系統(tǒng)資源的利用率。（1）預(yù)防死鎖（2）避免死鎖由于一方面預(yù)防死鎖的方法會(huì)降低系統(tǒng)資源利用率，另一方面死鎖的必要條件的存在未必就一定會(huì)使系統(tǒng)發(fā)生死鎖，因此為提高系統(tǒng)資源的利用率，可采用避免死鎖。避免死鎖并不嚴(yán)格限制死鎖必要條件的存在，而是在資源的動(dòng)態(tài)分配過(guò)程中，使用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的最終出現(xiàn)。（2）避免死鎖（3）檢測(cè)和解除死鎖由于死鎖產(chǎn)生的概率總是比較小的，所以在一些相對(duì)簡(jiǎn)單的系統(tǒng)中，為節(jié)省預(yù)防或避免死鎖中所增加的系統(tǒng)開銷，系統(tǒng)中允許出現(xiàn)死鎖狀態(tài)。在這種系統(tǒng)中，專門設(shè)置了一個(gè)檢測(cè)機(jī)構(gòu)，可以隨時(shí)檢測(cè)出死鎖的發(fā)生，并能確定與死鎖有關(guān)的進(jìn)程和資源，然后采用適當(dāng)?shù)姆椒ń獬到y(tǒng)中的死鎖狀態(tài)。（3）檢測(cè)和解除死鎖常用的解除死鎖的方法有兩種：一是強(qiáng)制性地撤銷一些死鎖進(jìn)程，并剝奪它們的資源給其他的進(jìn)程；另一種是使用一個(gè)有效的掛起和解除掛起機(jī)構(gòu)來(lái)掛起一些進(jìn)程，以便從被掛起進(jìn)程中剝奪一些資源，用來(lái)解除死鎖。常用的解除死鎖的方法有兩種：一是強(qiáng)制性地撤銷一些7.6.2預(yù)防死鎖1．打破“請(qǐng)求和保持”條件打破“請(qǐng)求和保持”條件，即把進(jìn)程運(yùn)行中所要求的所有資源在進(jìn)程開始運(yùn)行之前，一次性地分配給進(jìn)程，只要有一種資源不能滿足，該進(jìn)程就必須等待。這樣，進(jìn)程在運(yùn)行過(guò)程中就不再需要新的資源，這種方法又稱為預(yù)先靜態(tài)分配法。7.6.2預(yù)防死鎖2．打破“不剝奪”條件打破“不剝奪”條件，即強(qiáng)迫那些請(qǐng)求新資源而沒有立即得到滿足的進(jìn)程釋放它已保持的其他資源。這意味著一個(gè)進(jìn)程在運(yùn)行過(guò)程可以暫時(shí)釋放已占有的資源，即允許其他進(jìn)程剝奪使用該資源，從而破壞了“不剝奪”條件的出現(xiàn)。2．打破“不剝奪”條件3．打破“環(huán)路等待”條件死鎖產(chǎn)生時(shí)，一定存在一種進(jìn)程和資源的循環(huán)鏈。打破“環(huán)路等待”條件就是在資源的分配過(guò)程中，對(duì)資源的請(qǐng)求做出某種限制，使環(huán)路不可能出現(xiàn)。3．打破“環(huán)路等待”條件7.7線程

7.7.1線程的引入由于進(jìn)程是一個(gè)資源擁有者，所以在進(jìn)程的創(chuàng)建、撤消和調(diào)度切換以及進(jìn)程的同步與通信中，系統(tǒng)必須付出較大的時(shí)空開銷。正因?yàn)槿绱?，在系統(tǒng)中所設(shè)置的進(jìn)程數(shù)目不宜過(guò)多，進(jìn)程切換的頻率也不宜過(guò)高，這也就限制了并發(fā)程度的進(jìn)一步提高。7.7線程7.7.1線程的引入由以上對(duì)進(jìn)程的分析可知，如果將進(jìn)程的上述兩個(gè)屬性分開，由操作系統(tǒng)分開處理，將使多個(gè)程序更好地并發(fā)執(zhí)行，同時(shí)又可減少系統(tǒng)的開銷。也就是說(shuō)，對(duì)于作為調(diào)度和分派的基本單位，不同時(shí)作為擁有資源的單位；而對(duì)于擁有資源的基本單位，又不對(duì)之進(jìn)行頻繁的切換。正是在這種思想的指導(dǎo)下，形成了線程（Thread）的概念。由以上對(duì)進(jìn)程的分析可知，如果將進(jìn)程的上述兩個(gè)屬性分在引入線程的操作系統(tǒng)中，線程是進(jìn)程中的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。它的執(zhí)行環(huán)境很小，除了自身必需的堆棧、寄存器、優(yōu)先級(jí)等私有資源外，共享其所屬進(jìn)程的資源。在引入線程的操作系統(tǒng)中，線程是進(jìn)程中的一個(gè)實(shí)體，7.7.2線程與進(jìn)程的比較（1）擁有資源（2）調(diào)度（3）并發(fā)性（4）系統(tǒng)開銷7.7.2線程與進(jìn)程的比較7.7.3線程的屬性線程具有如下屬性。（1）線程有控制表。（2）線程共享所屬進(jìn)程的資源。（3）線程是處理機(jī)的獨(dú)立調(diào)度單位，多個(gè)線程可以并發(fā)執(zhí)行。（4）線程有動(dòng)態(tài)性。7.7.3線程的屬性7.7.4線程的狀態(tài)及其轉(zhuǎn)換（1）就緒狀態(tài)。線程已具備了執(zhí)行的條件，等待線程調(diào)度程序調(diào)度。（2）備用狀態(tài)。由調(diào)度程序選定為一個(gè)執(zhí)行對(duì)象。（3）轉(zhuǎn)換狀態(tài)。若線程已準(zhǔn)備好執(zhí)行，但突然資源不可用，從而成為轉(zhuǎn)換狀態(tài)。7.7.4線程的狀態(tài)及其轉(zhuǎn)換（4）運(yùn)行狀態(tài)。獲得CPU正在執(zhí)行。（5）等待狀態(tài)。正在執(zhí)行的線程，由于某種原因（如I/O操作）不能繼續(xù)運(yùn)行下去。（6）終止?fàn)顟B(tài)。線程已執(zhí)行完成。線程的狀態(tài)及其轉(zhuǎn)換如圖7.14所示。（4）運(yùn)行狀態(tài)。獲得CPU正在執(zhí)行。圖7.14線程的狀態(tài)及其轉(zhuǎn)換圖7.14線程的狀態(tài)及其轉(zhuǎn)換7.8Linux中的進(jìn)程管理7.8.1Linux進(jìn)程概述1．進(jìn)程實(shí)體的組成Linux進(jìn)程由3部分組成：正文段、用戶數(shù)據(jù)段和系統(tǒng)數(shù)據(jù)段，如圖7.15所示。7.8Linux中的進(jìn)程管理7.8.1Linux進(jìn)程圖7.15Linux進(jìn)程組成圖7.15Linux進(jìn)程組成2．進(jìn)程的狀態(tài)進(jìn)程是一個(gè)動(dòng)態(tài)的概念，在其運(yùn)行的整個(gè)生命周期中可根據(jù)具體情況不斷改變其狀態(tài)。Linux進(jìn)程主要有如下幾種狀態(tài)。（1）運(yùn)行狀態(tài)（task_running）（2）等待狀態(tài)（3）暫停狀態(tài)（task_stopped）（4）僵死狀態(tài)（task_zombie）2．進(jìn)程的狀態(tài)圖7.16Linux進(jìn)程狀態(tài)轉(zhuǎn)換圖7.16Linux進(jìn)程狀態(tài)轉(zhuǎn)換7.8.3Linux的進(jìn)程調(diào)度7.8.4Linux進(jìn)程的同步和通信1．信號(hào)機(jī)制2．管道機(jī)制3．消息隊(duì)列4.共享內(nèi)存5.信號(hào)量7.8.3Linux的進(jìn)程調(diào)度進(jìn)程管理1進(jìn)程的基本概念2進(jìn)程控制3進(jìn)程互斥和同步4進(jìn)程通信5進(jìn)程調(diào)度6死鎖7線程8Linux中的進(jìn)程管理進(jìn)程管理1進(jìn)程的基本概念7.1進(jìn)程的基本概念7.1.1程序的順序執(zhí)行和并發(fā)執(zhí)行1．程序的順序執(zhí)行所謂程序的順序執(zhí)行是指該程序獨(dú)占整個(gè)系統(tǒng)中的所有資源，處理機(jī)嚴(yán)格按照程序所規(guī)定的順序進(jìn)行操作，只有在前一個(gè)操作執(zhí)行完后，才進(jìn)行后繼操作。7.1進(jìn)程的基本概念7.1.1程序的順序執(zhí)行和并發(fā)程序的順序執(zhí)行有以下特征。（1）順序性。（2）封閉性。（3）可再現(xiàn)性。程序的順序執(zhí)行有以下特征。2．多道程序設(shè)計(jì)的引入執(zhí)行環(huán)境具有下述3個(gè)特點(diǎn)。（1）獨(dú)立性。（2）隨機(jī)性。（3）資源共享。2．多道程序設(shè)計(jì)的引入3．程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行可總結(jié)為：一組在邏輯上互相獨(dú)立的程序或程序段在執(zhí)行過(guò)程中其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始的執(zhí)行方式。3．程序的并發(fā)執(zhí)行程序并發(fā)執(zhí)行時(shí)具有如下特征。（1）間斷性。（2）失去封閉性。（3）不可再現(xiàn)性。程序并發(fā)執(zhí)行時(shí)具有如下特征。7.1.2進(jìn)程的定義和特征1．進(jìn)程的定義進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。7.1.2進(jìn)程的定義和特征2．進(jìn)程的特征（1）結(jié)構(gòu)特征（2）動(dòng)態(tài)性（3）并發(fā)性（4）獨(dú)立性（5）異步性2．進(jìn)程的特征7.1.3進(jìn)程的狀態(tài)及其轉(zhuǎn)換1．進(jìn)程的基本狀態(tài)（1）就緒狀態(tài)當(dāng)進(jìn)程已分配到除處理機(jī)以外的所有必要的資源后，只要再獲得處理機(jī)便可立即執(zhí)行，這時(shí)進(jìn)程的狀態(tài)稱為就緒狀態(tài)。7.1.3進(jìn)程的狀態(tài)及其轉(zhuǎn)換（2）執(zhí)行狀態(tài)執(zhí)行狀態(tài)是指進(jìn)程已獲得處理機(jī)、其程序正在執(zhí)行的狀態(tài)。（3）阻塞狀態(tài)正在執(zhí)行的進(jìn)程因發(fā)生某事件而暫時(shí)無(wú)法繼續(xù)執(zhí)行時(shí)，便放棄處理機(jī)而處于暫停狀態(tài)，這種暫停狀態(tài)被稱為阻塞狀態(tài)。（2）執(zhí)行狀態(tài)2．進(jìn)程的狀態(tài)轉(zhuǎn)換圖7.1進(jìn)程的3種基本狀態(tài)及其轉(zhuǎn)換2．進(jìn)程的狀態(tài)轉(zhuǎn)換圖7.1進(jìn)程的3種基本狀態(tài)及其轉(zhuǎn)換7.1.4進(jìn)程的結(jié)構(gòu)1．進(jìn)程的實(shí)體（1）進(jìn)程控制塊（PCB）（2）程序段（3）數(shù)據(jù)段7.1.4進(jìn)程的結(jié)構(gòu)2．進(jìn)程控制塊進(jìn)程控制塊是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。PCB中記錄了操作系統(tǒng)所需的，用于描述進(jìn)程進(jìn)展情況及控制進(jìn)程運(yùn)行所需的全部信息。PCB是進(jìn)程存在的惟一標(biāo)志。一般把PCB存放在操作系統(tǒng)專門開辟的PCB區(qū)內(nèi)。2．進(jìn)程控制塊在進(jìn)程控制塊中，主要包括下述4方面的信息。（1）進(jìn)程描述信息進(jìn)程標(biāo)識(shí)符。每個(gè)進(jìn)程都有惟一的進(jìn)程標(biāo)識(shí)符，用以識(shí)別不同的進(jìn)程。用戶名或用戶標(biāo)識(shí)號(hào)。每個(gè)進(jìn)程都隸屬于某個(gè)用戶，有利于資源共享與保護(hù)。家族關(guān)系。標(biāo)識(shí)進(jìn)程之間的家族關(guān)系。在進(jìn)程控制塊中，主要包括下述4方面的信息。（2）處理機(jī)狀態(tài)信息通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字（PSW）、用戶棧指針等（3）進(jìn)程調(diào)度信息進(jìn)程狀態(tài)。指明進(jìn)程的當(dāng)前狀態(tài)，以作為進(jìn)程調(diào)度和進(jìn)程對(duì)換時(shí)的依據(jù)。（2）處理機(jī)狀態(tài)信息進(jìn)程優(yōu)先級(jí)。用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)，優(yōu)先級(jí)別高的進(jìn)程先獲得處理機(jī)。進(jìn)程調(diào)度所需的其他信息。如進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等。事件。指進(jìn)程被阻塞的原因。進(jìn)程優(yōu)先級(jí)。用于描述進(jìn)程使用處理機(jī)的優(yōu)（4）進(jìn)程控制信息程序和數(shù)據(jù)的地址。指出該進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從中找到其程序和數(shù)據(jù)。進(jìn)程同步和通信機(jī)制。指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)所必須的機(jī)制，如消息隊(duì)列指針、信號(hào)量等。這些數(shù)據(jù)應(yīng)全部或部分地存放在PCB中。（4）進(jìn)程控制信息資源清單。它是一張列出了除CPU之外的進(jìn)程所需的全部資源和已經(jīng)分配給該進(jìn)程的資源清單。鏈接指針。它給出了本進(jìn)程（PCB）所在隊(duì)列的下一個(gè)進(jìn)程的PCB首地址。在一個(gè)系統(tǒng)中，通常擁有數(shù)十個(gè)、數(shù)百個(gè)乃至數(shù)千個(gè)PCB。為了對(duì)PCB進(jìn)行有效地管理，系統(tǒng)應(yīng)把所有的PCB用適當(dāng)?shù)姆绞浇M織起來(lái)。目前常用的PCB組織方式有鏈接方式和索引方式兩種。資源清單。它是一張列出了除CPU之外的進(jìn)①鏈接方式圖7.2PCB鏈接隊(duì)列示意圖①鏈接方式圖7.2PCB鏈接隊(duì)列示意圖②索引方式圖7.3PCB索引方式示意圖②索引方式圖7.3PCB索引方式示意圖7.2進(jìn)程控制7.2.1操作系統(tǒng)內(nèi)核為了防止操作系統(tǒng)及關(guān)鍵數(shù)據(jù)（如PCB等）受到用戶程序有意無(wú)意的破壞，通常將處理機(jī)的執(zhí)行狀態(tài)分成系統(tǒng)態(tài)和用戶態(tài)兩種。7.2進(jìn)程控制7.2.1操作系統(tǒng)內(nèi)核（1）系統(tǒng)態(tài)。它具有較高特權(quán)，能執(zhí)行一切指令，訪問(wèn)所有寄存器和存儲(chǔ)區(qū)。（2）用戶態(tài)。這是具有較低特權(quán)的執(zhí)行狀態(tài)，只能執(zhí)行規(guī)定的指令，訪問(wèn)指定的寄存器和存儲(chǔ)區(qū)。（1）系統(tǒng)態(tài)。它具有較高特權(quán)，能執(zhí)行一切指令，訪問(wèn)所有寄存器（3）操作系統(tǒng)內(nèi)核： 在進(jìn)行層次設(shè)計(jì)時(shí)，通常將一些與硬件緊密相關(guān)的模塊，諸如中斷處理程序、常用的設(shè)備驅(qū)動(dòng)程序以及運(yùn)行頻率較高的模塊（如時(shí)鐘管理、進(jìn)程調(diào)度和公共基本操作模塊）都安排在緊靠硬件的軟件層次中，并使之常駐內(nèi)存，以提高操作系統(tǒng)的運(yùn)行效率，通常把這一部分稱為操作系統(tǒng)的內(nèi)核（Kernel）。（3）操作系統(tǒng)內(nèi)核：7.2.2進(jìn)程控制的概念進(jìn)程控制是進(jìn)程和處理機(jī)管理的一個(gè)重要任務(wù)。所謂進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段來(lái)創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程在各種狀態(tài)之間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)資源共享的目的。7.2.2進(jìn)程控制的概念7.2.3進(jìn)程的創(chuàng)建與撤消1．進(jìn)程的創(chuàng)建2．進(jìn)程的撤消7.2.3進(jìn)程的創(chuàng)建與撤消7.2.4進(jìn)程的阻塞與喚醒1．進(jìn)程的阻塞2．進(jìn)程的喚醒7.2.4進(jìn)程的阻塞與喚醒7.3進(jìn)程互斥和同步7.3.1進(jìn)程互斥1．互斥的概念所謂進(jìn)程互斥是指當(dāng)有若干進(jìn)程都要使用某一共享資源時(shí)，任何時(shí)刻最多允許一個(gè)進(jìn)程使用，其他要使用該資源的進(jìn)程必須等待，直到占用該資源者釋放了該資源為止。7.3進(jìn)程互斥和同步7.3.1進(jìn)程互斥2．臨界資源操作系統(tǒng)中將一次只允許一個(gè)進(jìn)程訪問(wèn)的資源稱為臨界資源。2．臨界資源3．臨界區(qū)（CriticalSection）把進(jìn)程中訪問(wèn)臨界資源的那段程序代碼段稱為臨界區(qū)。為實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)，應(yīng)保證諸進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。必須在臨界區(qū)前面增加一段用于進(jìn)行上述檢查的代碼，我們把這段代碼段稱為進(jìn)入?yún)^(qū)（EntrySection）；相應(yīng)地，在臨界區(qū)后面也要加上一段稱為退出區(qū)（ExitSection）的代碼，用于將臨界區(qū)正被訪問(wèn)的標(biāo)志恢復(fù)為未被訪問(wèn)的標(biāo)志。3．臨界區(qū)（CriticalSection）一個(gè)含有訪問(wèn)某一臨界資源的循環(huán)進(jìn)程可描述如下：

while(TRUE){entrysectioncriticalsectionexitsectionremaindersection}一個(gè)含有訪問(wèn)某一臨界資源的循環(huán)進(jìn)程可描述如下：4．同步機(jī)制應(yīng)遵循的準(zhǔn)則（1）空閑讓進(jìn)。（2）忙則等待。（3）讓權(quán)等待。（4）有限等待。4．同步機(jī)制應(yīng)遵循的準(zhǔn)則7.3.2進(jìn)程同步1．同步的概念把異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約，使得各進(jìn)程按一定的速度執(zhí)行的過(guò)程稱為進(jìn)程間的同步。具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間互相發(fā)送的信號(hào)稱為消息或事件。7.3.2進(jìn)程同步2．同步與互斥的關(guān)系進(jìn)程的同步與進(jìn)程的互斥都涉及到并發(fā)進(jìn)程共享資源的問(wèn)題，進(jìn)程的互斥實(shí)際上是進(jìn)程同步的一種特殊情況。有時(shí)也把進(jìn)程的互斥與進(jìn)程的同步統(tǒng)稱為進(jìn)程的同步。2．同步與互斥的關(guān)系7.3.3信號(hào)量機(jī)制1．記錄型信號(hào)量

structsemaphore{intvalue；PCB*L；}S；7.3.3信號(hào)量機(jī)制2．P、V原語(yǔ)操作除了給信號(hào)量S初始化外，信號(hào)量的數(shù)值域僅能由P、V原語(yǔ)操作改變（P和V分別是荷蘭語(yǔ)Passeren和Verhoog的第一個(gè)字母，相當(dāng)于英文的Pass和Increment的意思）。2．P、V原語(yǔ)操作P原語(yǔ)操作的主要?jiǎng)幼魇牵海?）S.value減1；（2）若S.value減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；（3）若S.value減1后小于零，則該進(jìn)程被阻塞，進(jìn)入與該信號(hào)量相對(duì)應(yīng)的等待隊(duì)列L中，然后轉(zhuǎn)進(jìn)程調(diào)度。P原語(yǔ)操作的功能框圖如圖7.8。P原語(yǔ)操作的主要?jiǎng)幼魇牵簣D7.8P原語(yǔ)操作功能圖7.8P原語(yǔ)操作功能V原語(yǔ)操作的主要?jiǎng)幼魇牵海?）S.value加1；（2）若S.value加1后結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；（3）若S.value加1后結(jié)果小于或等于零，則從該信號(hào)量的等待隊(duì)列L中喚醒一個(gè)等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。V原語(yǔ)操作的功能框圖如圖7.9。V原語(yǔ)操作的主要?jiǎng)幼魇牵簣D7.9V原語(yǔ)操作功能圖7.9V原語(yǔ)操作功能7.3.4進(jìn)程互斥和同步的實(shí)現(xiàn)1．進(jìn)程互斥的實(shí)現(xiàn)2．進(jìn)程同步的實(shí)現(xiàn)7.3.4進(jìn)程互斥和同步的實(shí)現(xiàn)7.4進(jìn)程通信

通信（Communication）意味著在進(jìn)程間傳送數(shù)據(jù)。也把進(jìn)程間控制信息的交換稱為低級(jí)通信，而把進(jìn)程間大批量數(shù)據(jù)的交換稱為高級(jí)通信。7.4進(jìn)程通信通信（Commun7.4.1進(jìn)程通信的類型1．共享存儲(chǔ)器系統(tǒng)共享存儲(chǔ)器系統(tǒng)為了傳送大量數(shù)據(jù)，在存儲(chǔ)器中劃出一塊共享存儲(chǔ)區(qū)，諸進(jìn)程可通過(guò)對(duì)共享存儲(chǔ)區(qū)進(jìn)行讀數(shù)據(jù)或?qū)憯?shù)據(jù)以實(shí)現(xiàn)通信。7.4.1進(jìn)程通信的類型2．消息傳遞系統(tǒng)分為以下兩種。（1）直接通信方式發(fā)送進(jìn)程可將消息直接發(fā)送給接收進(jìn)程，即將消息掛在接收進(jìn)程的消息緩沖隊(duì)列上，而接收進(jìn)程可從自己的消息緩沖隊(duì)列中取得消息。（2）間接通信方式發(fā)送進(jìn)程將消息發(fā)送到指定的信箱中，而接收進(jìn)程從信箱中取得消息。2．消息傳遞系統(tǒng)3．管道通信系統(tǒng)在UNIX操作系統(tǒng)中，開創(chuàng)了一種借助文件和文件系統(tǒng)形成的一種通信方式。所謂管道是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程，以實(shí)現(xiàn)它們之間通信的共享文件，又稱pipe文件。向管道提供輸入的發(fā)送進(jìn)程，以字符流方式將大量的數(shù)據(jù)送入管道，而接收進(jìn)程從管道中接收數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故稱為管道通信。3．管道通信系統(tǒng)7.4.2消息緩沖隊(duì)列通信機(jī)制1．消息緩沖隊(duì)列通信機(jī)制簡(jiǎn)介由于消息緩沖機(jī)制中所使用的緩沖區(qū)為公用緩沖區(qū)，因此使用消息緩沖機(jī)制傳送數(shù)據(jù)時(shí)，兩通信進(jìn)程必須滿足如下條件。7.4.2消息緩沖隊(duì)列通信機(jī)制第一，在發(fā)送進(jìn)程把寫入消息的緩沖區(qū)掛入消息隊(duì)列時(shí)，應(yīng)禁止其他進(jìn)程對(duì)該消息隊(duì)列的訪問(wèn)，否則，將引起消息隊(duì)列的混亂。同理，當(dāng)接收進(jìn)程正從消息隊(duì)列中取消息時(shí)，也應(yīng)禁止其他進(jìn)程對(duì)該隊(duì)列的訪問(wèn)。第二，當(dāng)緩沖區(qū)中無(wú)消息存在時(shí)，接收進(jìn)程不能接收到任何消息；而發(fā)送進(jìn)程是否可以發(fā)送消息，則只由發(fā)送進(jìn)程是否能夠申請(qǐng)到緩沖區(qū)決定。第一，在發(fā)送進(jìn)程把寫入消息的緩沖區(qū)掛入消息隊(duì)列時(shí)2．消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)（1）消息緩沖區(qū)

typedefstructmessagebuffer{sender； //發(fā)送者進(jìn)程標(biāo)識(shí)符

size； //消息長(zhǎng)度

text； //消息正文

next； //指向下一個(gè)消息緩沖區(qū)的指針}2．消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)（2）PCB中有關(guān)進(jìn)程通信的數(shù)據(jù)項(xiàng)

typedefstructmessageblock{…mq； //消息隊(duì)列隊(duì)首指針

mutex；//消息隊(duì)列互斥信號(hào)量，初值為1

sm； //消息隊(duì)列資源信號(hào)量，用于消息隊(duì)列中的消息計(jì)數(shù)，初值為0…}（2）PCB中有關(guān)進(jìn)程通信的數(shù)據(jù)項(xiàng)7.5進(jìn)程調(diào)度7.5.1進(jìn)程調(diào)度的概念1．高級(jí)、中級(jí)和低級(jí)調(diào)度（1）高級(jí)調(diào)度高級(jí)調(diào)度通常也稱作業(yè)調(diào)度，用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，準(zhǔn)備執(zhí)行。7.5進(jìn)程調(diào)度7.5.1進(jìn)程調(diào)度的概念（2）中級(jí)調(diào)度中級(jí)調(diào)度大多針對(duì)于分時(shí)系統(tǒng)，是按一定的算法在內(nèi)存和外存之間進(jìn)行進(jìn)程對(duì)換，目的在于緩和內(nèi)存的緊張。（3）低級(jí)調(diào)度 低級(jí)調(diào)度用于將內(nèi)存中就緒隊(duì)列中的作業(yè)分配處理機(jī)，使其執(zhí)行。（2）中級(jí)調(diào)度2．進(jìn)程調(diào)度的方式進(jìn)程調(diào)度通常有以下兩種方式。（1）非剝奪方式（2）剝奪方式3．進(jìn)程調(diào)度的功能4．進(jìn)程調(diào)度算法的性能評(píng)價(jià)2．進(jìn)程調(diào)度的方式7.5.2進(jìn)程調(diào)度算法1．先來(lái)先服務(wù)調(diào)度算法在進(jìn)程調(diào)度中，采用FCFS算法時(shí)，進(jìn)程調(diào)度程序從就緒進(jìn)程隊(duì)列中，選擇一個(gè)最先進(jìn)入隊(duì)列的進(jìn)程，把處理機(jī)分配給它，讓它進(jìn)入執(zhí)行狀態(tài)。公平性，并且實(shí)現(xiàn)也比較容易，這是它的優(yōu)點(diǎn)。但是，它的缺點(diǎn)是實(shí)際上不公平，它比較有利于長(zhǎng)進(jìn)程，而不利于短進(jìn)程。7.5.2進(jìn)程調(diào)度算法2．短進(jìn)程優(yōu)先調(diào)度算法短進(jìn)程優(yōu)先（SPF）調(diào)度算法，是指對(duì)執(zhí)行時(shí)間短的進(jìn)程優(yōu)先調(diào)度的算法。SPF是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或因等待某事件發(fā)生而放棄處理機(jī)時(shí)，再重新調(diào)度。2．短進(jìn)程優(yōu)先調(diào)度算法采用SPF算法，平均周轉(zhuǎn)時(shí)間比FCFS調(diào)度算法有很多改善，這是它的優(yōu)點(diǎn)。SPF調(diào)度算法的缺點(diǎn)是如下所述。第一，對(duì)長(zhǎng)進(jìn)程非常不利。第二，緊迫進(jìn)程不能及時(shí)處理。第三，執(zhí)行時(shí)間的估計(jì)值不準(zhǔn)確。采用SPF算法，平均周轉(zhuǎn)時(shí)間比FCFS調(diào)度算法有很多改善，這3．高優(yōu)先級(jí)優(yōu)先調(diào)度算法考慮到系統(tǒng)中的緊迫進(jìn)程能得到優(yōu)先處理，引入了高優(yōu)先級(jí)優(yōu)先（HPF）調(diào)度算法，處理機(jī)總是分配給就緒進(jìn)程隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程。進(jìn)程的優(yōu)先級(jí)可采用靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)兩種，優(yōu)先級(jí)可由用戶自定或由系統(tǒng)確定。3．高優(yōu)先級(jí)優(yōu)先調(diào)度算法4．時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法的基本思想是將CPU的處理時(shí)間分成固定大小的時(shí)間片。如果一個(gè)進(jìn)程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時(shí)間片，但未完成要求的任務(wù)，則它自行釋放自己所占有的CPU，而排到就緒隊(duì)列的末尾，等待下一次調(diào)度。同時(shí)，進(jìn)程調(diào)度程序又去調(diào)度當(dāng)前就緒隊(duì)列中的第一個(gè)進(jìn)程。4．時(shí)間片輪轉(zhuǎn)法5．多級(jí)反饋隊(duì)列調(diào)度算法其基本思想如下所述。（1）系統(tǒng)按優(yōu)先級(jí)設(shè)置N個(gè)就緒進(jìn)程隊(duì)列，第一級(jí)隊(duì)列的優(yōu)先級(jí)最高，其余隊(duì)列的優(yōu)先級(jí)逐個(gè)降低，第N級(jí)隊(duì)列的優(yōu)先級(jí)最低。5．多級(jí)反饋隊(duì)列調(diào)度算法7.6死鎖在多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行，共享系統(tǒng)資源，從而提高了資源利用率和系統(tǒng)吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖。所謂死鎖，是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而形成一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。7.6死鎖在多道程序系統(tǒng)中，多個(gè)進(jìn)程7.6.1產(chǎn)生死鎖的原因和必要條件1．產(chǎn)生死鎖的原因產(chǎn)生死鎖的主要原因可歸結(jié)為以下兩點(diǎn)。（1）競(jìng)爭(zhēng)資源（2）進(jìn)程推進(jìn)順序不當(dāng)7.6.1產(chǎn)生死鎖的原因和必要條件2．產(chǎn)生死鎖的必要條件（1）互斥條件一個(gè)資源在一段時(shí)間內(nèi)只能被一個(gè)進(jìn)程所使用，具有排它性。（2）請(qǐng)求和保持條件一個(gè)進(jìn)程在請(qǐng)求新資源而阻塞時(shí)，對(duì)已獲得資源又保持不放。2．產(chǎn)生死鎖的必要條件（3）不剝奪條件進(jìn)程已獲得的資源，在未使用完之前不能被剝奪，只能在使用完時(shí)由自己釋放。（4）環(huán)路等待條件在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈。即進(jìn)程集合{P1，P2，…，Pn}中的P1正在等待P2占用的資源，P2正在等待P3占用的資源，…，Pn正在等待P1占用的資源。（3）不剝奪條件只要同時(shí)具備上述4個(gè)必要條件，系統(tǒng)就會(huì)發(fā)生死鎖，只要上述條件之一不滿足，系統(tǒng)就不會(huì)發(fā)生死鎖。只要同時(shí)具備上述4個(gè)必要條件，系統(tǒng)就會(huì)發(fā)生死鎖，3．處理死鎖的方法由于死鎖狀態(tài)的出現(xiàn)會(huì)給整個(gè)系統(tǒng)帶來(lái)嚴(yán)重的后果，所以如何解決死鎖問(wèn)題引起了人們的普遍關(guān)注。目前常用的方法有以下3種。3．處理死鎖的方法（1）預(yù)防死鎖為了使系統(tǒng)中不發(fā)生死鎖現(xiàn)象，在系統(tǒng)設(shè)計(jì)初期即選擇一些限制條件，來(lái)破壞產(chǎn)生死鎖的4個(gè)必要條件之一或其中幾個(gè)。這樣，系統(tǒng)中就不會(huì)出現(xiàn)死鎖現(xiàn)象。這種方法對(duì)預(yù)防死鎖的發(fā)生非常有效，但有可能降低系統(tǒng)資源的利用率。（1）預(yù)防死鎖（2）避免死鎖由于一方面預(yù)防死鎖的方法會(huì)降低系統(tǒng)資源利用率，另一方面死鎖的必要條件的存在未必就一定會(huì)使系統(tǒng)發(fā)生死鎖，因此為提高系統(tǒng)資源的利用率，可采用避免死鎖。避免死鎖并不嚴(yán)格限制死鎖必要條件的存在，而是在資源的動(dòng)態(tài)分配過(guò)程中，使用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的最終出現(xiàn)。（2）避免死鎖（3）檢測(cè)和解除死鎖由于死鎖產(chǎn)生的概率總是比較小的，所以在一些相對(duì)簡(jiǎn)單的系統(tǒng)中，為節(jié)省預(yù)防或避免死鎖中所增加的系統(tǒng)開銷，系統(tǒng)中允許出現(xiàn)死鎖狀態(tài)。在這種系統(tǒng)中，專門設(shè)置了一個(gè)檢測(cè)機(jī)構(gòu)，可以隨時(shí)