OUC 操作系統(tǒng) 第二章 進(jìn)程管理

1、1第二章第二章 進(jìn)程管理進(jìn)程管理第一節(jié)第一節(jié) 進(jìn)程的基本概念進(jìn)程的基本概念第二節(jié)第二節(jié) 進(jìn)程控制進(jìn)程控制第三節(jié)第三節(jié) 進(jìn)程同步進(jìn)程同步第四節(jié)第四節(jié)經(jīng)典進(jìn)程同步問題經(jīng)典進(jìn)程同步問題第五節(jié)第五節(jié)管程管程第六節(jié)第六節(jié)進(jìn)程通信進(jìn)程通信第七節(jié)第七節(jié)線程線程重點(diǎn)第一節(jié)第一節(jié)進(jìn)程的基本概念進(jìn)程的基本概念程序的順序執(zhí)行及特征程序的順序執(zhí)行及特征前趨圖前趨圖程序的并發(fā)執(zhí)行及特征程序的并發(fā)執(zhí)行及特征進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài)進(jìn)程控制塊進(jìn)程控制塊2在單道系統(tǒng)中，程序的執(zhí)行是順序的即必須在一個(gè)程序執(zhí)行完后，才允許另一個(gè)程序執(zhí)行在多道程序環(huán)境下，允許多個(gè)程序并發(fā)執(zhí)行。即允許暫停一個(gè)程序的執(zhí)行，而轉(zhuǎn)去執(zhí)行另一個(gè)程序

2、程序的這兩種執(zhí)行方式間有著顯著的不同3 在多道程序設(shè)計(jì)環(huán)境下，內(nèi)存中允許有多個(gè)程序存在，它們輪流地使用著CPU。4不同環(huán)境下程序的執(zhí)行特性不同環(huán)境下程序的執(zhí)行特性1 1、程序順序執(zhí)行的特征程序順序執(zhí)行的特征程序順序執(zhí)行的特征：程序順序執(zhí)行的特征：順序性順序性每一個(gè)操作必須在下一個(gè)操作開始之前結(jié)束每一個(gè)操作必須在下一個(gè)操作開始之前結(jié)束封閉性封閉性程序運(yùn)行時(shí)獨(dú)占全機(jī)資源，資源的狀態(tài)只有本程程序運(yùn)行時(shí)獨(dú)占全機(jī)資源，資源的狀態(tài)只有本程序才能改變序才能改變可再現(xiàn)性可再現(xiàn)性只要初始條件和運(yùn)行環(huán)境相同，當(dāng)程序重復(fù)執(zhí)行只要初始條件和運(yùn)行環(huán)境相同，當(dāng)程序重復(fù)執(zhí)行時(shí)，都將獲得相同的結(jié)果。時(shí)，都將獲得相同的結(jié)果。5

3、2、前趨圖、前趨圖前趨圖：有向無環(huán)圖前趨圖：有向無環(huán)圖(DAG)作用：作用：用于描述程序段或進(jìn)程間執(zhí)行的前后用于描述程序段或進(jìn)程間執(zhí)行的前后順序。順序。結(jié)點(diǎn)：結(jié)點(diǎn)：表示程序段或進(jìn)程，或一條語句表示程序段或進(jìn)程，或一條語句有向邊：有向邊：表示結(jié)點(diǎn)之間的偏序表示結(jié)點(diǎn)之間的偏序(前驅(qū)前驅(qū))關(guān)系關(guān)系6 X前驅(qū)圖的例子： S1：a = x + 2; S2: b = y + 4; S3：c = a + b; S4：d = c + b;73、程序的并發(fā)執(zhí)行、程序的并發(fā)執(zhí)行8I1C1P1I2I3C2P2C3P3n并發(fā)執(zhí)行時(shí)的前趨圖并發(fā)執(zhí)行時(shí)的前趨圖u有三個(gè)程序：I=輸入，C=計(jì)算, P=打印9并發(fā)執(zhí)行時(shí)的特征

4、并發(fā)執(zhí)行時(shí)的特征l間斷性間斷性“停停走走停停走走”l失去封閉性失去封閉性原因：多個(gè)程序共享資源原因：多個(gè)程序共享資源l不可再現(xiàn)性不可再現(xiàn)性例如例如:有兩個(gè)循環(huán)程序有兩個(gè)循環(huán)程序A和和B，共享一個(gè)變量，共享一個(gè)變量n。程序。程序A每執(zhí)行一次時(shí)，都要做每執(zhí)行一次時(shí)，都要做n=n+1;程序程序B每執(zhí)行一次時(shí)，都每執(zhí)行一次時(shí)，都要執(zhí)行要執(zhí)行Print(n)；然后將；然后將n置成置成0。程序。程序A和和B并發(fā)執(zhí)行時(shí)，并發(fā)執(zhí)行時(shí)，可能出現(xiàn)的情況如下：可能出現(xiàn)的情況如下：1、n=n+1在在print(n)和和n=0之前，得到的之前，得到的n值為值為n+1,n+1,02、n=n+1在在print(n)和和n=

5、0之后，得到的之后，得到的n值為值為n,0,13、n=n+1在在print(n)和和n=0之間，得到的之間，得到的n值為值為n,n+1,0順序程序與并發(fā)程序的比較順序程序與并發(fā)程序的比較 順序程序順序程序 并發(fā)程序并發(fā)程序 執(zhí)行過程執(zhí)行過程 順序執(zhí)行交替執(zhí)行封閉性封閉性 獨(dú)占資源具有封閉性共享資源不具有封閉性可再現(xiàn)性可再現(xiàn)性x程序間關(guān)系程序間關(guān)系 x間接制約或直接制約10在多道程序下，程序并發(fā)執(zhí)行，因此失去封閉性，致使程序出現(xiàn)不可再現(xiàn)性，這樣程序執(zhí)行就失去意義。所以通常意義下的程序不能參與并發(fā)執(zhí)行。為使程序能并發(fā)運(yùn)行，且對(duì)并發(fā)程序進(jìn)行描述和控制。在OS中，以“程序”為基礎(chǔ)，又引入了“進(jìn)程”這一

6、新的概念。114、進(jìn)程的特征與狀態(tài)、進(jìn)程的特征與狀態(tài)進(jìn)程的定義與特征進(jìn)程的定義與特征進(jìn)程的基本狀態(tài)進(jìn)程的基本狀態(tài)進(jìn)程的掛起狀態(tài)進(jìn)程的掛起狀態(tài)12為什么引入進(jìn)程？為什么引入進(jìn)程？刻畫系統(tǒng)的動(dòng)態(tài)性，發(fā)揮系統(tǒng)的并發(fā)性，提高資刻畫系統(tǒng)的動(dòng)態(tài)性，發(fā)揮系統(tǒng)的并發(fā)性，提高資源利用率。源利用率。解決共享性，正確描述程序的執(zhí)行狀態(tài)。解決共享性，正確描述程序的執(zhí)行狀態(tài)。特征：特征：結(jié)構(gòu)性結(jié)構(gòu)性(PCB)動(dòng)態(tài)性動(dòng)態(tài)性并發(fā)性并發(fā)性獨(dú)立性獨(dú)立性異步性異步性13進(jìn)程的定義與特征進(jìn)程的定義與特征結(jié)構(gòu)特征 進(jìn)程實(shí)體 = 程序 + 進(jìn)程控制塊(PCB)14Windows 中的進(jìn)程1516進(jìn)程A進(jìn)程B進(jìn)程進(jìn)程A A執(zhí)行完后寄存器

7、的狀態(tài)進(jìn)程進(jìn)程B B執(zhí)行完后寄存器的狀態(tài)恢復(fù)進(jìn)程進(jìn)程A A上次執(zhí)行完時(shí)寄存器的狀態(tài)進(jìn)程進(jìn)程A的的PCB暫存進(jìn)程進(jìn)程A A執(zhí)行完時(shí)寄存器的狀態(tài)進(jìn)程進(jìn)程B的的PCB動(dòng)態(tài)性動(dòng)態(tài)性進(jìn)程實(shí)質(zhì)是進(jìn)程實(shí)體的一次執(zhí)行過程體現(xiàn)在 “由創(chuàng)建而生，由調(diào)度而執(zhí)行，由撤銷而亡”并發(fā)性并發(fā)性多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，并發(fā)執(zhí)行程序(沒建立PCB)是無法并發(fā)執(zhí)行的。17獨(dú)立性獨(dú)立性進(jìn)程實(shí)體是一個(gè)獨(dú)立運(yùn)行、獨(dú)立分配資源、獨(dú)立接受調(diào)度的基本單位。凡未建立PCB的程序都不能作為一個(gè)獨(dú)立單位參與運(yùn)行。異步性異步性進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度執(zhí)行(即按異步方式運(yùn)行)。18進(jìn)程進(jìn)程是一個(gè)動(dòng)態(tài)的概念是一個(gè)動(dòng)態(tài)的概念程序的一次執(zhí)行。一個(gè)

8、程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。進(jìn)程的定義進(jìn)程的定義進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。通常，也把“進(jìn)程實(shí)體”簡(jiǎn)稱為“進(jìn)程”19進(jìn)程和程序的區(qū)別與聯(lián)系進(jìn)程和程序的區(qū)別與聯(lián)系n區(qū)別區(qū)別 進(jìn)程是動(dòng)態(tài)概念，強(qiáng)調(diào)的是執(zhí)行，有創(chuàng)建、有撤銷，存在是暫時(shí)的； 程序是一靜態(tài)概念，程序是指令的有序集合，“永遠(yuǎn)”存在；進(jìn)程具有并發(fā)性，而程序沒有；進(jìn)程是接受計(jì)算機(jī)資源的基本單位，程序不是。n聯(lián)系聯(lián)系n進(jìn)程是程序在數(shù)據(jù)集上的一次執(zhí)行；n一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程，一個(gè)進(jìn)程可包括多個(gè)程序。20小結(jié)：對(duì)小結(jié)：對(duì)

9、“進(jìn)程進(jìn)程”這一概念如何理解這一概念如何理解動(dòng)態(tài)的組成n給程序附加上PCB，形成了進(jìn)程實(shí)體PCB的作用n保存執(zhí)行過程中的一些信息，再次執(zhí)行時(shí)恢復(fù)這些信息，以保證執(zhí)行的正確性。也可用于OS控制和描述進(jìn)程的執(zhí)行。21進(jìn)程的基本狀態(tài)進(jìn)程的基本狀態(tài)就緒狀態(tài)（就緒狀態(tài)（ReadyReady）得到了除得到了除CPUCPU以外的所有必要資源以外的所有必要資源執(zhí)行狀態(tài)（執(zhí)行狀態(tài)（RunningRunning）已獲得處理機(jī)，程序正在被執(zhí)行已獲得處理機(jī)，程序正在被執(zhí)行阻塞狀態(tài)（阻塞狀態(tài)（BlockedBlocked）因等待某事件發(fā)生而暫時(shí)無法繼續(xù)執(zhí)行，從因等待某事件發(fā)生而暫時(shí)無法繼續(xù)執(zhí)行，從而放棄處理機(jī)，使程序執(zhí)

10、行處于暫停狀態(tài)而放棄處理機(jī)，使程序執(zhí)行處于暫停狀態(tài)中斷中斷接納接納完成完成進(jìn)程調(diào)度進(jìn)程調(diào)度事件發(fā)生事件發(fā)生等待某事件等待某事件新進(jìn)程新進(jìn)程結(jié)束結(jié)束就緒就緒執(zhí)行執(zhí)行阻塞阻塞22進(jìn)程的掛起狀態(tài)進(jìn)程的掛起狀態(tài)掛起狀態(tài)的引入掛起狀態(tài)的引入父進(jìn)程考查和修改、協(xié)調(diào)子進(jìn)程間的活動(dòng)父進(jìn)程考查和修改、協(xié)調(diào)子進(jìn)程間的活動(dòng)操作系統(tǒng)協(xié)調(diào)資源使用或進(jìn)行記賬操作系統(tǒng)協(xié)調(diào)資源使用或進(jìn)行記賬終端用戶的請(qǐng)求終端用戶的請(qǐng)求負(fù)荷調(diào)節(jié)的需要，如實(shí)時(shí)緊急任務(wù)負(fù)荷調(diào)節(jié)的需要，如實(shí)時(shí)緊急任務(wù)激活激活掛起掛起調(diào)度調(diào)度掛起掛起I/O釋放釋放I/O釋放釋放I/O請(qǐng)求請(qǐng)求激活激活掛起掛起靜止靜止就緒就緒靜止靜止阻塞阻塞活動(dòng)活動(dòng)就緒就緒執(zhí)行執(zhí)行活動(dòng)

11、活動(dòng)阻塞阻塞235、進(jìn)程控制塊、進(jìn)程控制塊PCB(ProcessControlBlock)PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。是進(jìn)程是進(jìn)程存在的唯一標(biāo)志。存在的唯一標(biāo)志。作用：作用：是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)的程序，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。位置：位置：PCB存放在存放在OS中專門開辟的中專門開辟的PCB區(qū)內(nèi)區(qū)內(nèi)2425PCB中

12、的信息中的信息l進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符：唯一的標(biāo)識(shí)一個(gè)進(jìn)程：唯一的標(biāo)識(shí)一個(gè)進(jìn)程 內(nèi)部標(biāo)識(shí)（內(nèi)部標(biāo)識(shí)（OS） 外部標(biāo)識(shí)（由創(chuàng)建者提供，由字母數(shù)字組成）外部標(biāo)識(shí)（由創(chuàng)建者提供，由字母數(shù)字組成）Unix/Linux下的進(jìn)程標(biāo)識(shí)符是什么樣的？ps ef26kill -9 12189Windows下的進(jìn)程標(biāo)識(shí)符是什么樣的？27外部標(biāo)識(shí)符外部標(biāo)識(shí)符使用使用“內(nèi)部標(biāo)識(shí)符內(nèi)部標(biāo)識(shí)符”控制控制處理機(jī)狀態(tài)處理機(jī)狀態(tài)： 由由CPUCPU的各種寄存器中的內(nèi)容組成。的各種寄存器中的內(nèi)容組成。 通用通用R R 指令計(jì)數(shù)器指令計(jì)數(shù)器PC PC 程序狀態(tài)字程序狀態(tài)字PSW PSW 用戶棧指針用戶棧指針2829l進(jìn)程調(diào)度信息進(jìn)程

13、調(diào)度信息： 進(jìn)程狀態(tài)進(jìn)程狀態(tài) 進(jìn)程優(yōu)先級(jí)進(jìn)程優(yōu)先級(jí) 其它信息其它信息 等待事件（阻塞原因）等待事件（阻塞原因）l進(jìn)程控制信息進(jìn)程控制信息： 程序和數(shù)據(jù)的地址程序和數(shù)據(jù)的地址 同步和通信機(jī)制同步和通信機(jī)制 資源清單資源清單 鏈接指針鏈接指針進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式PCBPCB數(shù)目數(shù)目一個(gè)系統(tǒng)中的一個(gè)系統(tǒng)中的PCBPCB數(shù)目可為數(shù)十個(gè)、數(shù)百個(gè)甚至數(shù)千個(gè)數(shù)目可為數(shù)十個(gè)、數(shù)百個(gè)甚至數(shù)千個(gè)鏈接方式鏈接方式把具有同一狀態(tài)的把具有同一狀態(tài)的PCBPCB，鏈接成一個(gè)隊(duì)列，鏈接成一個(gè)隊(duì)列就緒隊(duì)列、若干個(gè)阻塞隊(duì)列、空隊(duì)列就緒隊(duì)列、若干個(gè)阻塞隊(duì)列、空隊(duì)列索引方式索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立相應(yīng)

14、的索引表系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立相應(yīng)的索引表就緒索引表、阻塞索引表等，索引表在內(nèi)存的首地址記就緒索引表、阻塞索引表等，索引表在內(nèi)存的首地址記錄在內(nèi)存的一些專用單元中。錄在內(nèi)存的一些專用單元中。3031執(zhí)行指針執(zhí)行指針就緒隊(duì)列指針就緒隊(duì)列指針阻塞隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針空閑隊(duì)列指針執(zhí)行指針執(zhí)行指針就緒隊(duì)列指針就緒隊(duì)列指針阻塞隊(duì)列指針阻塞隊(duì)列指針PCB鏈接隊(duì)列示意圖鏈接隊(duì)列示意圖按索引方式組織按索引方式組織PCB第二節(jié)第二節(jié) 進(jìn)程的控制進(jìn)程的控制進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程撤消進(jìn)程撤消進(jìn)程阻塞進(jìn)程阻塞進(jìn)程喚醒進(jìn)程喚醒進(jìn)程掛起與激活進(jìn)程掛起與激活32進(jìn)程控制是進(jìn)程管理最基本的功能：進(jìn)程控制是進(jìn)程管

15、理最基本的功能： (1) (1) 用于創(chuàng)建新進(jìn)程用于創(chuàng)建新進(jìn)程 (2) (2) 終止一個(gè)已完成的進(jìn)程終止一個(gè)已完成的進(jìn)程 (3) (3) 終止一個(gè)無法運(yùn)行下去的進(jìn)程終止一個(gè)無法運(yùn)行下去的進(jìn)程 (Kill)(Kill) (4) (4) 負(fù)責(zé)進(jìn)程的狀態(tài)轉(zhuǎn)換負(fù)責(zé)進(jìn)程的狀態(tài)轉(zhuǎn)換 ( (就緒就緒執(zhí)行執(zhí)行) )33進(jìn)程圖進(jìn)程圖 描述一個(gè)進(jìn)程家族關(guān)系的有向樹有向樹子進(jìn)程可以繼承繼承父進(jìn)程的所有資源所有資源(打開的文件、分配的緩沖區(qū)等)撤銷子進(jìn)程時(shí)，把它從父進(jìn)程那里獲得的資源還給父進(jìn)程撤銷父進(jìn)程時(shí)，要同時(shí)撤銷它所有的子進(jìn)程34ABCDEF父進(jìn)程子進(jìn)程在在PCB中設(shè)置中設(shè)置家族關(guān)系表項(xiàng)：家族關(guān)系表項(xiàng)：記錄父進(jìn)程

16、，及記錄父進(jìn)程，及所有的子進(jìn)程所有的子進(jìn)程1、進(jìn)程創(chuàng)建、進(jìn)程創(chuàng)建35引起創(chuàng)建進(jìn)程的事件引起創(chuàng)建進(jìn)程的事件l用戶登錄用戶登錄l用戶從終端登錄，為其建立進(jìn)程(分時(shí)系統(tǒng))l作業(yè)調(diào)度作業(yè)調(diào)度l把作業(yè)裝入內(nèi)存 (批處理系統(tǒng))l提供服務(wù)提供服務(wù)l為某個(gè)請(qǐng)求創(chuàng)建專門的進(jìn)程。例如用戶打印時(shí)，創(chuàng)建打印進(jìn)程l應(yīng)用請(qǐng)求應(yīng)用請(qǐng)求l建子進(jìn)程，以并發(fā)完成工作，加速任務(wù) (由應(yīng)用程序創(chuàng)建)36申請(qǐng)空的申請(qǐng)空的PCB請(qǐng)求創(chuàng)建進(jìn)程請(qǐng)求創(chuàng)建進(jìn)程為新進(jìn)程分配資源為新進(jìn)程分配資源初始化初始化PCB插入到就緒隊(duì)列插入到就緒隊(duì)列就緒隊(duì)列就緒隊(duì)列(申請(qǐng)唯一的標(biāo)識(shí)符，從PCB集合中取空白項(xiàng))(將所需信息填入PCB：標(biāo)識(shí)符、處理機(jī)狀態(tài)、進(jìn)程狀

17、態(tài)、優(yōu)先級(jí)等等)(如果就緒隊(duì)列能容納新進(jìn)程的話)l進(jìn)程的創(chuàng)建流程進(jìn)程的創(chuàng)建流程(分配內(nèi)存，OS要知道新進(jìn)程的大小)2、進(jìn)程撤消、進(jìn)程撤消引起進(jìn)程終止的事件引起進(jìn)程終止的事件正常結(jié)束：執(zhí)行到最后的結(jié)束指令、中斷正常結(jié)束：執(zhí)行到最后的結(jié)束指令、中斷異常結(jié)束：出現(xiàn)錯(cuò)誤或因故障而被迫終止異常結(jié)束：出現(xiàn)錯(cuò)誤或因故障而被迫終止外界干擾：進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行外界干擾：進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行進(jìn)程撤消的過程進(jìn)程撤消的過程一個(gè)進(jìn)程可以向其父進(jìn)程申請(qǐng)撤消自己；一個(gè)進(jìn)程可以向其父進(jìn)程申請(qǐng)撤消自己；也可以因父進(jìn)程的被撤銷而被同時(shí)撤消。也可以因父進(jìn)程的被撤銷而被同時(shí)撤消。37l進(jìn)程終止的流程38從從PCB集合中

18、找到集合中找到相應(yīng)進(jìn)程的相應(yīng)進(jìn)程的PCB,讀出其狀態(tài)讀出其狀態(tài)停止執(zhí)行，停止執(zhí)行，置調(diào)度標(biāo)志為置調(diào)度標(biāo)志為true進(jìn)程正在執(zhí)行？進(jìn)程正在執(zhí)行？YN終止所有子進(jìn)程終止所有子進(jìn)程有子進(jìn)程？有子進(jìn)程？YN歸還所占的資源歸還所占的資源(給父進(jìn)程或給父進(jìn)程或OS)把把PCB從隊(duì)列中從隊(duì)列中移走移走39PDPBPEPCPFPAPIPHPGPJPKPLPMPN3、進(jìn)程阻塞、進(jìn)程阻塞引起阻塞的事件引起阻塞的事件請(qǐng)求系統(tǒng)服務(wù)請(qǐng)求系統(tǒng)服務(wù)OS不能立即滿足(打印機(jī)被別人使用)啟動(dòng)某種操作啟動(dòng)某種操作I/O操作后才能繼續(xù)執(zhí)行數(shù)據(jù)尚未到達(dá)數(shù)據(jù)尚未到達(dá)進(jìn)程合作時(shí)，只有新數(shù)據(jù)到達(dá)才能繼續(xù)執(zhí)行無新工作可做無新工作可做一些具有

19、特定功能的系統(tǒng)進(jìn)程系統(tǒng)進(jìn)程，完成任務(wù)后就把自己阻塞起來，等待新任務(wù)到來(如發(fā)送數(shù)據(jù)進(jìn)程)40l進(jìn)程的阻塞流程 (進(jìn)程自己阻塞自己進(jìn)程自己阻塞自己)41立即停止執(zhí)行立即停止執(zhí)行改變狀態(tài)為改變狀態(tài)為“阻塞阻塞”插入到阻塞隊(duì)列插入到阻塞隊(duì)列就緒隊(duì)列選擇新的就緒進(jìn)程CPU4、進(jìn)程喚醒、進(jìn)程喚醒引起喚醒的事件引起喚醒的事件與引起阻塞的事件相對(duì)應(yīng)與引起阻塞的事件相對(duì)應(yīng)進(jìn)程喚醒的過程進(jìn)程喚醒的過程阻塞進(jìn)程所期待的事件出現(xiàn)，有關(guān)的進(jìn)程調(diào)用喚醒阻塞進(jìn)程所期待的事件出現(xiàn)，有關(guān)的進(jìn)程調(diào)用喚醒原語，將等待該事件的進(jìn)程喚醒原語，將等待該事件的進(jìn)程喚醒將將PCB從阻塞隊(duì)列中移出，修改從阻塞隊(duì)列中移出，修改PCB中的狀態(tài)信

20、息，中的狀態(tài)信息，再將其插入到就緒進(jìn)程隊(duì)列中再將其插入到就緒進(jìn)程隊(duì)列中阻塞與喚醒要匹配使用，以免造成阻塞與喚醒要匹配使用，以免造成“永久阻塞永久阻塞”425、進(jìn)程掛起與激活、進(jìn)程掛起與激活進(jìn)程掛起進(jìn)程掛起檢查被掛進(jìn)程的狀態(tài)，改為相應(yīng)的掛起狀態(tài)檢查被掛進(jìn)程的狀態(tài)，改為相應(yīng)的掛起狀態(tài)把進(jìn)程的把進(jìn)程的PCB復(fù)制到指定的區(qū)域復(fù)制到指定的區(qū)域最后，轉(zhuǎn)向調(diào)度程序重新調(diào)度最后，轉(zhuǎn)向調(diào)度程序重新調(diào)度進(jìn)程激活進(jìn)程激活先將進(jìn)程從外存調(diào)入內(nèi)存先將進(jìn)程從外存調(diào)入內(nèi)存檢查該進(jìn)程的現(xiàn)行狀態(tài)，改為相應(yīng)的活動(dòng)狀態(tài)檢查該進(jìn)程的現(xiàn)行狀態(tài)，改為相應(yīng)的活動(dòng)狀態(tài)根據(jù)優(yōu)先級(jí)確定是否需要重新調(diào)度根據(jù)優(yōu)先級(jí)確定是否需要重新調(diào)度(搶占調(diào)度？搶

21、占調(diào)度？)阻塞、喚醒一般由阻塞、喚醒一般由OS實(shí)現(xiàn)，而掛起與激活可由用戶實(shí)現(xiàn)，而掛起與激活可由用戶干預(yù)干預(yù)43第三節(jié)第三節(jié)進(jìn)程互斥與同步進(jìn)程互斥與同步基本概念基本概念臨界區(qū)（臨界段）臨界區(qū)（臨界段）信號(hào)量機(jī)制信號(hào)量機(jī)制信號(hào)量的應(yīng)用信號(hào)量的應(yīng)用44進(jìn)程同步的主要任務(wù)進(jìn)程同步的主要任務(wù)使并發(fā)執(zhí)行的諸進(jìn)程之間有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。451、基本概念、基本概念兩種形式的制約關(guān)系兩種形式的制約關(guān)系直接相互制約：源于進(jìn)程間的合作直接相互制約：源于進(jìn)程間的合作間接相互制約：源于進(jìn)程對(duì)資源的共享間接相互制約：源于進(jìn)程對(duì)資源的共享進(jìn)程同步進(jìn)程同步合作完成同一個(gè)任務(wù)的多個(gè)進(jìn)程，在執(zhí)

22、行速度或某合作完成同一個(gè)任務(wù)的多個(gè)進(jìn)程，在執(zhí)行速度或某些時(shí)序點(diǎn)上必須相互協(xié)調(diào)的合作關(guān)系。些時(shí)序點(diǎn)上必須相互協(xié)調(diào)的合作關(guān)系。進(jìn)程互斥進(jìn)程互斥一個(gè)進(jìn)程正在訪問一個(gè)進(jìn)程正在訪問臨界資源臨界資源，另一個(gè)要訪問該資源，另一個(gè)要訪問該資源的進(jìn)程必須等待。的進(jìn)程必須等待。462、臨界區(qū)（臨界段）、臨界區(qū)（臨界段）臨界資源臨界資源一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源訪問時(shí)，必須采用“互斥”方式47進(jìn)程同步著名例子：生產(chǎn)者消費(fèi)者問題48AB緩沖區(qū)要求：要求：不允許生產(chǎn)者A向已經(jīng)滿滿的緩沖區(qū)放產(chǎn)品放產(chǎn)品不允許消費(fèi)者B從空空的緩沖區(qū)拿產(chǎn)品拿產(chǎn)品模擬方法：緩沖區(qū)：數(shù)組 0,1,n-1，循環(huán)隊(duì)列下一個(gè)產(chǎn)品應(yīng)該放在什么位置

23、：in=0, ,n-1下一個(gè)產(chǎn)品應(yīng)該從什么位置拿：out=0, ,n-1緩沖區(qū)里還有多少產(chǎn)品： counter=0, ,n49放一個(gè)新產(chǎn)品：in := (in + 1) mod n;拿走一個(gè)產(chǎn)品：out := (out + 1) mod n;什么時(shí)候緩沖區(qū)滿了：counter = n什么時(shí)候緩沖區(qū)空了：counter = 050inout51上面的過程在并發(fā)執(zhí)行時(shí)會(huì)出錯(cuò)上面的過程在并發(fā)執(zhí)行時(shí)會(huì)出錯(cuò)原因：兩者共享變量原因：兩者共享變量counter機(jī)器語言描述：機(jī)器語言描述： mov ax, counter mov ax, counter mov bx, countermov bx, count

24、er inc ax inc ax dec bxdec bx mov counter, ax mov counter, ax movmov counter, bxcounter, bxcounter = 5counter = 5 生產(chǎn)者、消費(fèi)者順序執(zhí)行一次，生產(chǎn)者、消費(fèi)者順序執(zhí)行一次， 結(jié)果是結(jié)果是5 5交替執(zhí)行時(shí)的情況：交替執(zhí)行時(shí)的情況： mov ax, counter (ax = 5) mov ax, counter (ax = 5) inc ax (ax = 6)inc ax (ax = 6) mov bx, counter (bx = 5)mov bx, counter (bx = 5)

25、 dec bx (bx = 4) dec bx (bx = 4) mov counter, ax (counter = 6) mov counter, ax (counter = 6) movmov counter, bx (counter = 4) counter, bx (counter = 4) 結(jié)果是結(jié)果是4 452剛才的例子說明什么問題？剛才的例子說明什么問題？程序執(zhí)行失去了再現(xiàn)性：結(jié)果可能是4或5或6解決思路解決思路把counter當(dāng)作臨界資源處理令兩個(gè)程序互斥訪問它53臨界區(qū)臨界區(qū)每個(gè)進(jìn)程中訪問臨界資源的代碼段如何實(shí)現(xiàn)互斥地訪問臨界資源：如何實(shí)現(xiàn)互斥地訪問臨界資源：保證各進(jìn)程互斥

26、地進(jìn)入（執(zhí)行）自己的臨界區(qū)，便可實(shí)現(xiàn)對(duì)臨界資源的互斥訪問。54上廁所問題臨界資源的訪問55解決方法解決方法進(jìn)入臨界區(qū)前，檢查臨界資源是否正在被使用/訪問。兩個(gè)步驟兩個(gè)步驟沒被使用，則設(shè)置“使用”標(biāo)志，然后使用使用完了，設(shè)置“未用”標(biāo)志，讓別人可以使用56criticalsection;/臨界區(qū)臨界區(qū)repeatuntilfalse;entrysection /進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)exitsection/退出區(qū)退出區(qū)remaindersection;/剩余區(qū)剩余區(qū)設(shè)變量S，標(biāo)志counter是否正在被使用。生產(chǎn)者：生產(chǎn)者： 消費(fèi)者：消費(fèi)者： . . . . . .57while S=0 do no-op

27、;S := S - 1;while S=0 do no-op;S := S - 1;counter = counter + 1;counter = counter - 1;. . .S := S + 1;. . . . .S := S + 1;. . .并發(fā)執(zhí)行的時(shí)候會(huì)出新問題！并發(fā)執(zhí)行的時(shí)候會(huì)出新問題！由上可見，在程序中設(shè)置一個(gè)變量，用來標(biāo)志另一個(gè)變量或資源是否被使用是行不通的。所以，OS需要提供一個(gè)專門的進(jìn)程同步機(jī)制，來解決這個(gè)問題。58同步應(yīng)遵循的規(guī)則同步應(yīng)遵循的規(guī)則空閑讓進(jìn)空閑讓進(jìn)忙則等待忙則等待有限等待有限等待避免“死等”讓權(quán)等待讓權(quán)等待不能進(jìn)入臨界區(qū)時(shí)，立即釋放處理機(jī)，避免“忙等”

28、。593、信號(hào)量機(jī)制、信號(hào)量機(jī)制卓有成效的進(jìn)程同步工具提出提出1965. 荷蘭 Dijkstra60Dijkstra經(jīng)典語錄編程的藝術(shù)就是處理復(fù)雜性的藝術(shù)。 簡(jiǎn)單是可靠的先決條件。1972年圖靈獎(jiǎng)演講：優(yōu)秀的程序員很清楚自己的能力是有限的，所以他對(duì)待編程任務(wù)的態(tài)度是完全謙卑的，特別是，他們會(huì)象逃避瘟疫那樣逃避 “聰明的技巧”。計(jì)算機(jī)科學(xué)是應(yīng)用數(shù)學(xué)最難的一個(gè)分支，所以如果你是一個(gè)蹩腳的數(shù)學(xué)家，最好留在原地，繼續(xù)當(dāng)你的數(shù)學(xué)家。1.實(shí)際上如果一個(gè)程序員先學(xué)了BASIC，那就很難教會(huì)他好的編程技術(shù)了：作為一個(gè)可能的程序員，他們的神經(jīng)已經(jīng)錯(cuò)亂了，而且無法康復(fù)。61(19302002)信號(hào)量的發(fā)展信號(hào)量的

29、發(fā)展整型信號(hào)量 記錄型信號(hào)量 AND型信號(hào)量 信號(hào)量集基本思想基本思想使用信號(hào)量標(biāo)記臨界資源是否被使用注意注意檢查和釋放信號(hào)量的任務(wù)由OS完成應(yīng)用程序中可調(diào)用相應(yīng)的原語，以完成對(duì)信號(hào)量的檢查和釋放621 1、整型信號(hào)量、整型信號(hào)量基本思想基本思想改變整型變量S的值，以標(biāo)記臨界資源的使用情況信號(hào)量的值只能用wait(S)和signal(S)來訪問S的初始值為1或更大。wait(S)、signal(S)是原子操作，執(zhí)行時(shí)不可中斷。原子操作，執(zhí)行時(shí)不可中斷。( (又被稱作又被稱作P P、V V操作操作) )63整型信號(hào)量機(jī)制的缺點(diǎn)整型信號(hào)量機(jī)制的缺點(diǎn)只要信號(hào)量S=0，就會(huì)不停地測(cè)試。因此，未遵循“讓

30、權(quán)等待讓權(quán)等待”準(zhǔn)則“忙等忙等”。故而，引入故而，引入“記錄型信號(hào)量機(jī)制記錄型信號(hào)量機(jī)制”，避免，避免 “忙等忙等”現(xiàn)象?，F(xiàn)象。642 2、記錄型信號(hào)量、記錄型信號(hào)量基本思想基本思想用一個(gè)整型變量value表示資源的數(shù)目，還用一個(gè)鏈表L將等待訪問該資源的進(jìn)程組成阻塞隊(duì)列數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義 type semaphore = record value : integer; /資源數(shù)目(資源信號(hào)量) L : List of process; /等待進(jìn)程隊(duì)列 end65l wait(S)wait(S)操作：操作： var S: semaphore; begin S.value := S.valu

31、e 1; / / 如果資源分配完畢，如果資源分配完畢， / / 自我阻塞自我阻塞, , 并進(jìn)入并進(jìn)入隊(duì)列隊(duì)列 / S.L/ S.L進(jìn)行等待進(jìn)行等待 if S.value0 then block(S.L); end;66lsignal (S)操作：操作： var S: semaphore; begin S.value := S.value + 1; /如果如果S.value=0, /表示仍有等待的進(jìn)程，表示仍有等待的進(jìn)程， /則喚醒一個(gè)則喚醒一個(gè) if S.value=0 then wakeup(S.L); end;注意注意： S.value=1 and and Sn=1 then for i:

32、= 1 to n do Si := Si 1; end for else 將進(jìn)程阻塞，放入第一個(gè)發(fā)現(xiàn)si=ti and and if Si=ti and and sn=tn thensn=tn then for i:=1 to n for i:=1 to n dodo Si := Si Si := Si di;di; end for; end for; else else 將進(jìn)程阻塞，放入第一個(gè)發(fā)現(xiàn)si1)或互斥信號(hào)量(S=1)Swait(S,1,0) n特殊且有用的信號(hào)量功能類似于“開關(guān)”。nS=1時(shí)，允許多個(gè)進(jìn)程執(zhí)行某特定的代碼。置S=0后，阻止任何程序執(zhí)行該段代碼。75信號(hào)量機(jī)制的用途一

33、般有兩種信號(hào)量機(jī)制的用途一般有兩種用于用于“互斥互斥”：多個(gè)進(jìn)程互斥地訪問共享資源：多個(gè)進(jìn)程互斥地訪問共享資源用于用于“協(xié)調(diào)協(xié)調(diào)”：協(xié)調(diào)進(jìn)程間的執(zhí)行次序：協(xié)調(diào)進(jìn)程間的執(zhí)行次序 （實(shí)現(xiàn)進(jìn)程間的協(xié)調(diào)，即實(shí)現(xiàn)前驅(qū)關(guān)系）（實(shí)現(xiàn)進(jìn)程間的協(xié)調(diào)，即實(shí)現(xiàn)前驅(qū)關(guān)系）764、信號(hào)量的應(yīng)用、信號(hào)量的應(yīng)用1 1、利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥、利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥如何讓多個(gè)進(jìn)程互斥訪問一個(gè)臨界資源？方法方法設(shè)一個(gè)信號(hào)量mutex ，令其初始值為1(互斥信號(hào)量) ，用它控制進(jìn)程的訪問。將各進(jìn)程訪問臨界資源的代碼放入wait(mutex)和signal(mutex)之間。7778wait(mutex);signal(mutex

34、);臨界區(qū)：使用臨界區(qū)：使用/訪問臨界訪問臨界資源資源(共享變量共享變量)的代碼的代碼Var mutex:semaphore := 1; /定義信號(hào)量定義信號(hào)量 repeatUntil false;repeatwait(mutex);signal(mutex);臨界區(qū)：使用臨界區(qū)：使用/訪問臨界訪問臨界資源資源(共享變量共享變量)的代碼的代碼Until false;注意：注意：利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥時(shí)，wait、signal 一般要成對(duì)出現(xiàn)缺少缺少wait：導(dǎo)致系統(tǒng)混亂。缺少缺少signal：使阻塞進(jìn)程無法被喚醒。2 2、利用信號(hào)量實(shí)現(xiàn)進(jìn)程訪問有限數(shù)量的共享資源、利用信號(hào)量實(shí)現(xiàn)進(jìn)程訪問有限數(shù)量

35、的共享資源如果共享資源的數(shù)量有限（設(shè)1），如何控制多個(gè)進(jìn)程對(duì)它們的訪問？方法方法設(shè)一個(gè)信號(hào)量mutex ，令其初始值等于共享資源的數(shù)量 ，用它控制進(jìn)程的訪問。將各進(jìn)程訪問共享資源的代碼放入wait(mutex)和signal(mutex)之間。7980wait(mutex);signal(mutex);使用使用/訪問共享訪問共享資源資源(共享變量共享變量)的代碼的代碼Var mutex:semaphore := 資源數(shù)量資源數(shù)量; /定義信號(hào)量定義信號(hào)量 repeatUntil false;repeatwait(mutex);signal(mutex);使用使用/訪問共享訪問共享資源資源(共享

36、變量共享變量)的代碼的代碼Until false; 注意事項(xiàng)與使用互斥信號(hào)量時(shí)相同注意事項(xiàng)與使用互斥信號(hào)量時(shí)相同3 3、利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系、利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系n例例1 1：設(shè)并發(fā)執(zhí)行的兩個(gè)進(jìn)程：設(shè)并發(fā)執(zhí)行的兩個(gè)進(jìn)程P1P1、P2P2 P1：S1; P2：S2; 要求：要求：S1在S2之前執(zhí)行 81 P1：S1; P2：wait(mutex); signal(mutex); S2;82S1S2方法：方法：設(shè)置信號(hào)量 mutex=0 (why?)前驅(qū)圖：前驅(qū)圖：mutexn例例2 2：利用信號(hào)量實(shí)現(xiàn)語句間的前趨關(guān)系：利用信號(hào)量實(shí)現(xiàn)語句間的前趨關(guān)系83S1S3S2S4S5S6abcdfgeV

37、ar a,b,c,d,e,f,g:semaphore := 0,0,0,0,0,0,0;begin S1; signal(a); signal(b); end;begin wait(a); S2; signal(c); signal(d); end;begin wait(b); S3; signal(e); end;begin wait(c);S4; signal(f); end;begin wait(d); S5; signal(g); end;begin wait(e); wait(f); wait(g); S6; end;信號(hào)量小結(jié)信號(hào)量小結(jié)信號(hào)量分類：信號(hào)量分類：互斥的信號(hào)量：它的互斥

38、的信號(hào)量：它的wait、signal在在同一同一個(gè)進(jìn)程中個(gè)進(jìn)程中同步的信號(hào)量：它的同步的信號(hào)量：它的wait、signal在在不同不同的進(jìn)程中的進(jìn)程中信號(hào)量的意義：信號(hào)量的意義：S0：S表示可用資源的個(gè)數(shù)表示可用資源的個(gè)數(shù)S=0：S表示無資源，無等待進(jìn)程表示無資源，無等待進(jìn)程S=1，說明還允許新讀者，則將L減1，并繼續(xù)執(zhí)行下一步否則，說明已有RN個(gè)讀者在讀，則阻塞并等待Var L,mxVar L,mx：semaphoresemaphore：=RN,1;=RN,1;讀者進(jìn)程：讀者進(jìn)程：beginbegin repeat repeat swait (L,1,1); swait (L,1,1); s

39、wait (mx,1,swait (mx,1,0 0); ); 讀操作讀操作; ; ssignal (L,1); ssignal (L,1); until false; until false;end;end;如果已有一個(gè)寫者在寫，則有mx=0如果已有至少一個(gè)讀者在讀，則有LRN存在以上兩種情況之一時(shí)，本寫者阻塞并等待否則表示，沒有其他寫者在寫，并且沒有讀者在讀，則置mx=0，并繼續(xù)下一步注：該句只檢查是否有讀者在讀，并不修改L的值103寫者進(jìn)程：寫者進(jìn)程：begin repeat swait (mx,1,1,L,RN,0); 寫操作寫操作; ssignal (mx,1); until fal

40、se;end; 檢查是否有寫者在寫 (只檢查,不修改mx的值)第五節(jié)第五節(jié) 管程機(jī)制管程機(jī)制 管程的基本概念管程的基本概念 管程應(yīng)用分析管程應(yīng)用分析1041、管程的基本概念、管程的基本概念采用信號(hào)量同步機(jī)制編寫并發(fā)程序，對(duì)于信號(hào)量的采用信號(hào)量同步機(jī)制編寫并發(fā)程序，對(duì)于信號(hào)量的操作將被分散于各個(gè)進(jìn)程中。操作將被分散于各個(gè)進(jìn)程中。缺點(diǎn)：缺點(diǎn)：易讀性差，不利于修改和維護(hù)，正確性難以易讀性差，不利于修改和維護(hù)，正確性難以保證保證管程的產(chǎn)生管程的產(chǎn)生1971，Dijkstra：“秘書秘書”進(jìn)程進(jìn)程1973，Hansan：管程：管程105管程定義管程定義一個(gè)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)和能被并發(fā)進(jìn)程所執(zhí)行的一一組操作

41、組操作(操作這些數(shù)據(jù)結(jié)構(gòu))，這組操作能使進(jìn)程同步進(jìn)程同步，還可改變管程中的數(shù)據(jù)改變管程中的數(shù)據(jù)管程的基本思想管程的基本思想封裝 (類似面向?qū)ο?管程的組成管程的組成管程里的共享變量對(duì)該共享變量進(jìn)行操作的過程(函數(shù))數(shù)據(jù)初始化106107l 管程的特點(diǎn)管程的特點(diǎn)封裝性封裝性內(nèi)部的共享變量在管程外不可見內(nèi)部的共享變量在管程外不可見內(nèi)部過程內(nèi)部過程(函數(shù)函數(shù))只能訪問內(nèi)部的共享變量只能訪問內(nèi)部的共享變量互斥互斥各進(jìn)程必須互斥進(jìn)入管程各進(jìn)程必須互斥進(jìn)入管程阻塞隊(duì)列阻塞隊(duì)列內(nèi)部設(shè)有阻塞隊(duì)列，以及相應(yīng)的阻塞和喚醒內(nèi)部設(shè)有阻塞隊(duì)列，以及相應(yīng)的阻塞和喚醒操作操作為實(shí)現(xiàn)進(jìn)程同步,管程中使用wait、signal

42、為區(qū)分阻塞原因，管程中使用“條件變量”條件變量條件變量是一種特殊的數(shù)據(jù)類型是一種特殊的數(shù)據(jù)類型使用時(shí)類似如下的定義方法：使用時(shí)類似如下的定義方法： var c: condition var c: condition；對(duì)于條件變量可以執(zhí)行對(duì)于條件變量可以執(zhí)行waitwait和和signalsignal操作操作108109c.wait 將被阻塞的進(jìn)程放入與條件變量將被阻塞的進(jìn)程放入與條件變量c關(guān)聯(lián)的阻塞隊(duì)關(guān)聯(lián)的阻塞隊(duì)列中列中c.signal 喚醒與條件變量喚醒與條件變量c關(guān)聯(lián)的阻塞隊(duì)列中的第一個(gè)進(jìn)關(guān)聯(lián)的阻塞隊(duì)列中的第一個(gè)進(jìn)程，如果沒有被阻塞的，它不做任何操作程，如果沒有被阻塞的，它不做任何操作注：

43、這與信號(hào)量機(jī)制中的注：這與信號(hào)量機(jī)制中的wait和和signal有所不同有所不同條件變量的使用條件變量的使用1102、管程應(yīng)用分析、管程應(yīng)用分析生產(chǎn)者生產(chǎn)者-消費(fèi)者問題消費(fèi)者問題l在管程里定義兩個(gè)過程(函數(shù))put(item) l生產(chǎn)者利用它向緩沖區(qū)放一個(gè)產(chǎn)品get(item) l消費(fèi)者利用它從緩沖區(qū)取一個(gè)產(chǎn)品l利用整型變量count標(biāo)記緩沖區(qū)中產(chǎn)品的數(shù)量lcount=n時(shí)，生產(chǎn)者需等待定義管程如下定義管程如下type pc = monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull,notempty : con

44、dition; procedure put(item) begin if count=n then notfull.wait; bufferin:=item; in :=(in + 1) mod n; count := count + 1; if notempty.queue then notempty.signal; end;111l緩沖區(qū)已滿，緩沖區(qū)已滿，把進(jìn)程阻塞到把進(jìn)程阻塞到“等待投放產(chǎn)品等待投放產(chǎn)品”的的阻塞阻塞隊(duì)列隊(duì)列中中l(wèi)如果如果“等待消等待消費(fèi)費(fèi)”隊(duì)列中還有隊(duì)列中還有被阻塞的進(jìn)程，被阻塞的進(jìn)程，就從中喚醒一個(gè)就從中喚醒一個(gè)l定義兩個(gè)條件定義兩個(gè)條件變量變量lnotfull：表示

45、：表示“緩沖區(qū)不滿緩沖區(qū)不滿”，即可以投，即可以投放產(chǎn)品的條件放產(chǎn)品的條件lnotempty：表：表示示“緩沖區(qū)不緩沖區(qū)不空空”，即可以，即可以取產(chǎn)品的條件取產(chǎn)品的條件 procedure get(item) begin if count=0 then notempty.wait; item := bufferout; out := (out + 1) mod n; count := count 1; if notfull.queue then notfull.signal; end; begin in := out := 0; count:=0; end;end type;112 初始化數(shù)據(jù)

46、l生產(chǎn)者生產(chǎn)者 begin repeat 生產(chǎn)一個(gè)item; pc.put (item); until false; end;l消費(fèi)者消費(fèi)者 begin repeat pc.get(item); 消費(fèi)掉產(chǎn)品item; until false; end;113第六節(jié)第六節(jié)進(jìn)程通信進(jìn)程通信進(jìn)程通信的概念進(jìn)程通信的概念進(jìn)程通信的類型進(jìn)程通信的類型消息傳遞通信的實(shí)現(xiàn)方法消息傳遞通信的實(shí)現(xiàn)方法消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題消息緩沖隊(duì)列通信機(jī)制消息緩沖隊(duì)列通信機(jī)制1141、進(jìn)程通信的概念、進(jìn)程通信的概念進(jìn)程通信進(jìn)程通信，是指進(jìn)程之間的信息交換，是指進(jìn)程之間的信息交換低級(jí)通信低級(jí)通

47、信（互斥、同步）（互斥、同步）利用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程間的數(shù)據(jù)傳遞利用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程間的數(shù)據(jù)傳遞缺點(diǎn)：效率低；對(duì)用戶不透明缺點(diǎn)：效率低；對(duì)用戶不透明高級(jí)通信高級(jí)通信（進(jìn)程通信）（進(jìn)程通信）進(jìn)程之間利用進(jìn)程之間利用OS提供的一組通信命令，高效地提供的一組通信命令，高效地傳送大量數(shù)據(jù)的信息交換方式傳送大量數(shù)據(jù)的信息交換方式優(yōu)點(diǎn)：高效，方便，簡(jiǎn)化了通信程序的設(shè)計(jì)優(yōu)點(diǎn)：高效，方便，簡(jiǎn)化了通信程序的設(shè)計(jì)1152、進(jìn)程通信的類型、進(jìn)程通信的類型116高級(jí)通信機(jī)制的類型高級(jí)通信機(jī)制的類型共享存儲(chǔ)器系統(tǒng)共享存儲(chǔ)器系統(tǒng)管道通信系統(tǒng)管道通信系統(tǒng)消息傳遞系統(tǒng)消息傳遞系統(tǒng)共享存儲(chǔ)器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式進(jìn)程

48、共享某些數(shù)據(jù)結(jié)構(gòu)(如隊(duì)列) 程序員必須負(fù)責(zé)同步管理所以低效低效，只適合傳輸少量數(shù)據(jù)傳輸少量數(shù)據(jù)基于共享存儲(chǔ)區(qū)的通信方式屬于高級(jí)通信方式劃出一塊共享存儲(chǔ)區(qū)劃出一塊共享存儲(chǔ)區(qū)，進(jìn)程通過對(duì)存儲(chǔ)區(qū)中數(shù)據(jù)的讀寫來通信117管道通信系統(tǒng)首創(chuàng)于UNIX系統(tǒng)管道是一個(gè)共享文件（pipe文件），用于連結(jié)一個(gè)發(fā)送進(jìn)程和一個(gè)接收進(jìn)程，以實(shí)現(xiàn)通信發(fā)送進(jìn)程和接收進(jìn)程利用管道進(jìn)程通信管道機(jī)制還提供三個(gè)方面的協(xié)調(diào)能力互斥一個(gè)進(jìn)程讀/寫管道，其他進(jìn)程必須等待同步發(fā)送進(jìn)程寫入一定數(shù)量的數(shù)據(jù)后便阻塞，接收進(jìn)程取走后再喚醒接收進(jìn)程遇到空管道時(shí)，也阻塞確定對(duì)方都存在后，才進(jìn)行通信118消息傳遞系統(tǒng)進(jìn)程間交換的數(shù)據(jù)是有格式的，稱為me

49、ssage（網(wǎng)絡(luò)通信中，稱為報(bào)文）OS提供了相應(yīng)的通信命令有兩種方式直接通信方式間接通信方式1193、消息傳遞通信的實(shí)現(xiàn)方法、消息傳遞通信的實(shí)現(xiàn)方法直接通信方式直接通信方式發(fā)送進(jìn)程利用發(fā)送進(jìn)程利用OS提供的發(fā)送原語，直接把消息發(fā)提供的發(fā)送原語，直接把消息發(fā)送給目標(biāo)進(jìn)程送給目標(biāo)進(jìn)程Send(Receiver,message)、Receive(Sender,message)利用直接通信原語，解決生產(chǎn)者消費(fèi)者問題：利用直接通信原語，解決生產(chǎn)者消費(fèi)者問題：生產(chǎn)者生產(chǎn)者消費(fèi)者消費(fèi)者120repeatproduceaniteminnextp;send(consumer,nextp);untilfalse;

50、repeatreceive(producer,nextc);consumeaniteminnextc;untilfalse;121間接通信方式間接通信方式l進(jìn)程之間通過共享數(shù)據(jù)結(jié)構(gòu)進(jìn)程之間通過共享數(shù)據(jù)結(jié)構(gòu)信箱信箱，以消息暫存，以消息暫存方式實(shí)現(xiàn)的通信方式實(shí)現(xiàn)的通信l操作原語操作原語l信箱的創(chuàng)建、撤消；消息的發(fā)送、接收信箱的創(chuàng)建、撤消；消息的發(fā)送、接收l信箱的創(chuàng)建和擁有者信箱的創(chuàng)建和擁有者lOS或用戶（通信）進(jìn)程或用戶（通信）進(jìn)程l信箱的種類信箱的種類l私用信箱、公用信箱、共享信箱私用信箱、公用信箱、共享信箱l利用信箱通信時(shí)，發(fā)送和接收進(jìn)程之間的關(guān)系利用信箱通信時(shí)，發(fā)送和接收進(jìn)程之間的關(guān)系l一對(duì)

51、一、多對(duì)一、一對(duì)多、多對(duì)多一對(duì)一、多對(duì)一、一對(duì)多、多對(duì)多4、消息緩沖隊(duì)列通信機(jī)制、消息緩沖隊(duì)列通信機(jī)制提出者：提出者：Hansan通過內(nèi)存中的公用通過內(nèi)存中的公用消息緩沖區(qū)消息緩沖區(qū)進(jìn)行進(jìn)程通信進(jìn)行進(jìn)程通信廣泛應(yīng)用于本地進(jìn)程間通信發(fā)送原語發(fā)送原語send(receiver,a)a：發(fā)送區(qū)的地址：發(fā)送區(qū)的地址接收原語接收原語receive(b)b：接收區(qū)的地址：接收區(qū)的地址122123（1）消息緩沖區(qū)中的數(shù)據(jù)結(jié)構(gòu)：）消息緩沖區(qū)中的數(shù)據(jù)結(jié)構(gòu)：typemessagebuffer=recordsender；發(fā)送進(jìn)程標(biāo)識(shí)符發(fā)送進(jìn)程標(biāo)識(shí)符size；消息長(zhǎng)度消息長(zhǎng)度text；消息正文消息正文next；指向下

52、一個(gè)消息緩沖區(qū)的指針指向下一個(gè)消息緩沖區(qū)的指針end（2）PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)：中有關(guān)通信的數(shù)據(jù)項(xiàng)：typePCB=recordmq；消息隊(duì)列首指針消息隊(duì)列首指針mutex；消息隊(duì)列互斥信號(hào)量；消息隊(duì)列互斥信號(hào)量sm；消息隊(duì)列資源信號(hào)量消息隊(duì)列資源信號(hào)量end124進(jìn)程進(jìn)程ASend(B，a)Sender=ASize=5Text=Hello發(fā)送區(qū)a進(jìn)程進(jìn)程BReceive(b)Sender=ASize=5Text=Hello接收區(qū)bmqmutexsmPCB(B)Sender=ASize=5Text=HelloNext=0第七節(jié)第七節(jié) 線程的基本概念線程的基本概念線程的基本概念線程的基本概念

53、線程間的同步和通信線程間的同步和通信內(nèi)核支持線程和用戶級(jí)線程內(nèi)核支持線程和用戶級(jí)線程線程控制線程控制1251、線程的引入、線程的引入進(jìn)程（進(jìn)程（6060年代）年代）目的目的使多個(gè)程序并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量使多個(gè)程序并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量定義定義在在OSOS中能中能擁有資源擁有資源和和獨(dú)立運(yùn)行獨(dú)立運(yùn)行的基本單位的基本單位局限性局限性創(chuàng)建、撤消與切換時(shí)空開銷大，限制了并發(fā)程度的提高創(chuàng)建、撤消與切換時(shí)空開銷大，限制了并發(fā)程度的提高線程（線程（8080年代）年代）目的目的減少并發(fā)時(shí)付出的時(shí)空開銷，使系統(tǒng)具有更好的并發(fā)性減少并發(fā)時(shí)付出的時(shí)空開銷，使系統(tǒng)具有更好的并發(fā)性基本思想

54、基本思想“輕裝上陣輕裝上陣”將進(jìn)程的兩個(gè)屬性分離將進(jìn)程的兩個(gè)屬性分離線程線程獨(dú)立調(diào)度的基本單位，進(jìn)程獨(dú)立調(diào)度的基本單位，進(jìn)程擁有資源的單位擁有資源的單位126127輕型實(shí)體輕型實(shí)體線程幾乎不占資源線程幾乎不占資源(TCB等等)獨(dú)立調(diào)度的基本單位獨(dú)立調(diào)度的基本單位切換迅速且開銷小切換迅速且開銷小可并發(fā)執(zhí)行可并發(fā)執(zhí)行共享進(jìn)程的資源共享進(jìn)程的資源同一進(jìn)程內(nèi)的線程共享進(jìn)程的資源同一進(jìn)程內(nèi)的線程共享進(jìn)程的資源可以創(chuàng)建、撤銷另一個(gè)線程可以創(chuàng)建、撤銷另一個(gè)線程2、線程的屬性、線程的屬性FlashGetFlashGet中的線程中的線程1283、線程的狀態(tài)、線程的狀態(tài)每個(gè)線程都利用每個(gè)線程都利用TCB和一組狀態(tài)

55、參數(shù)進(jìn)行描述和一組狀態(tài)參數(shù)進(jìn)行描述狀態(tài)參數(shù)狀態(tài)參數(shù)寄存器狀態(tài)、堆棧、運(yùn)行狀態(tài)、優(yōu)先級(jí)寄存器狀態(tài)、堆棧、運(yùn)行狀態(tài)、優(yōu)先級(jí)運(yùn)行狀態(tài)運(yùn)行狀態(tài)就緒狀態(tài)、執(zhí)行狀態(tài)、阻塞狀態(tài)就緒狀態(tài)、執(zhí)行狀態(tài)、阻塞狀態(tài)1291304、線程的創(chuàng)建和終止、線程的創(chuàng)建和終止l 在多線程在多線程OS環(huán)境下，應(yīng)用程序啟動(dòng)后，通常僅環(huán)境下，應(yīng)用程序啟動(dòng)后，通常僅有一個(gè)線程在執(zhí)行，稱為有一個(gè)線程在執(zhí)行，稱為“初始化線程初始化線程”，它可，它可創(chuàng)建新線程。創(chuàng)建新線程。l 終止線程的方式有兩種終止線程的方式有兩種 線程完成自己的工作后主動(dòng)退出線程完成自己的工作后主動(dòng)退出 運(yùn)行中出現(xiàn)錯(cuò)誤，或由于某種原因，而被其它運(yùn)行中出現(xiàn)錯(cuò)誤，或由于某種原

56、因，而被其它線程強(qiáng)行終止線程強(qiáng)行終止1315、多線程、多線程OS中的進(jìn)程中的進(jìn)程l 多線程多線程OS中的中的進(jìn)程進(jìn)程有以下屬性有以下屬性進(jìn)程不是一個(gè)可執(zhí)行的實(shí)體，而是作為資進(jìn)程不是一個(gè)可執(zhí)行的實(shí)體，而是作為資源分配的單位源分配的單位可包括多個(gè)線程可包括多個(gè)線程互斥鎖功能類似互斥信號(hào)量條件變量通常與互斥鎖一起使用，以防止單純使用互斥鎖時(shí)產(chǎn)生死鎖信號(hào)量機(jī)制私用信號(hào)量同一進(jìn)程內(nèi)線程同步公用信號(hào)量不同進(jìn)程間或不同進(jìn)程中線程的同步1326、線程間的同步、線程間的同步線程和進(jìn)程的區(qū)別與聯(lián)系線程和進(jìn)程的區(qū)別與聯(lián)系調(diào)度調(diào)度線程是調(diào)度的基本單位線程是調(diào)度的基本單位進(jìn)程是資源擁有的基本單位進(jìn)程是資源擁有的基本單位

57、擁有資源擁有資源線程不擁有系統(tǒng)資源，但可以訪問其隸屬進(jìn)程的系統(tǒng)資源，從而獲得線程不擁有系統(tǒng)資源，但可以訪問其隸屬進(jìn)程的系統(tǒng)資源，從而獲得系統(tǒng)資源系統(tǒng)資源并發(fā)性并發(fā)性支持多線程的支持多線程的OS中，不僅不同進(jìn)程的線程之間可以并發(fā)，同一進(jìn)程內(nèi)中，不僅不同進(jìn)程的線程之間可以并發(fā)，同一進(jìn)程內(nèi)的線程之間也可并發(fā)的線程之間也可并發(fā)系統(tǒng)開銷系統(tǒng)開銷進(jìn)程切換時(shí)的時(shí)空開銷大進(jìn)程切換時(shí)的時(shí)空開銷大線程切換時(shí)，只需保存和設(shè)置少量信息，因此開銷很小線程切換時(shí)，只需保存和設(shè)置少量信息，因此開銷很小1331347、內(nèi)核支持線程和用戶級(jí)線程、內(nèi)核支持線程和用戶級(jí)線程l 不同的不同的OS實(shí)現(xiàn)線程的方式不同實(shí)現(xiàn)線程的方式不同內(nèi)

58、核支持線程內(nèi)核支持線程線程的控制由內(nèi)核完成，內(nèi)核設(shè)立線程的控制由內(nèi)核完成，內(nèi)核設(shè)立TCB以控制線程以控制線程線程是調(diào)度的單位線程是調(diào)度的單位注：分時(shí)系統(tǒng)中，包含線程多的進(jìn)程，運(yùn)行的時(shí)間相對(duì)注：分時(shí)系統(tǒng)中，包含線程多的進(jìn)程，運(yùn)行的時(shí)間相對(duì)多多用戶級(jí)線程用戶級(jí)線程僅存在用戶空間中，僅存在用戶空間中，不需內(nèi)核直接參與不需內(nèi)核直接參與控制，切換更快控制，切換更快進(jìn)程仍是調(diào)度的單位進(jìn)程仍是調(diào)度的單位注：分時(shí)系統(tǒng)中，包含線程多的進(jìn)程，每個(gè)線程運(yùn)行的注：分時(shí)系統(tǒng)中，包含線程多的進(jìn)程，每個(gè)線程運(yùn)行的時(shí)間相對(duì)少時(shí)間相對(duì)少135用戶級(jí)線程的實(shí)現(xiàn)用戶級(jí)線程的實(shí)現(xiàn)運(yùn)行時(shí)系統(tǒng)運(yùn)行時(shí)系統(tǒng)(RuntimeSystem)用于

59、管理和控制線程的函數(shù)用于管理和控制線程的函數(shù)(過程過程)的集合的集合包括創(chuàng)建和撤消線程的函數(shù)、包括創(chuàng)建和撤消線程的函數(shù)、線程同步和通信的函數(shù)、線程同步和通信的函數(shù)、實(shí)現(xiàn)線程調(diào)度的函數(shù)等實(shí)現(xiàn)線程調(diào)度的函數(shù)等所有函數(shù)都駐留在用戶空間，并作為用戶級(jí)線程與內(nèi)所有函數(shù)都駐留在用戶空間，并作為用戶級(jí)線程與內(nèi)核之間的接口核之間的接口正因?yàn)橛羞@些函數(shù)，才能使用戶級(jí)線程與內(nèi)核無關(guān)正因?yàn)橛羞@些函數(shù)，才能使用戶級(jí)線程與內(nèi)核無關(guān)136內(nèi)核控制線程內(nèi)核控制線程又稱為又稱為L(zhǎng)WP（輕型進(jìn)程）（輕型進(jìn)程）有自己的數(shù)據(jù)結(jié)構(gòu)，如線程標(biāo)識(shí)符、優(yōu)先級(jí)、有自己的數(shù)據(jù)結(jié)構(gòu)，如線程標(biāo)識(shí)符、優(yōu)先級(jí)、狀態(tài)等狀態(tài)等每個(gè)進(jìn)程可擁有多個(gè)每個(gè)進(jìn)程可

60、擁有多個(gè)LWP，它們共享進(jìn)程所擁有的資，它們共享進(jìn)程所擁有的資源源可通過系統(tǒng)調(diào)用獲得內(nèi)核提供的服務(wù)可通過系統(tǒng)調(diào)用獲得內(nèi)核提供的服務(wù)只要將用戶級(jí)線程連接到一個(gè)只要將用戶級(jí)線程連接到一個(gè)LWP上，該線程便具有上，該線程便具有了內(nèi)核支持線程的所有屬性了內(nèi)核支持線程的所有屬性137利用利用LWP作為中間系統(tǒng)作為中間系統(tǒng)任務(wù)任務(wù)1任務(wù)任務(wù)2任務(wù)任務(wù)3用戶級(jí)線程LWP內(nèi)核線程CPU小結(jié)(1)進(jìn)程的概念和定義前驅(qū)圖如何畫前驅(qū)圖如何畫進(jìn)程的特征進(jìn)程的基本狀態(tài)及轉(zhuǎn)換進(jìn)程的基本狀態(tài)及轉(zhuǎn)換PCBPCB的作用的作用進(jìn)程、程序的聯(lián)系與區(qū)別進(jìn)程、程序的聯(lián)系與區(qū)別138小結(jié)(2)進(jìn)程的創(chuàng)建、撤銷、終止進(jìn)程同步、信號(hào)量、臨界