第2章 進(jìn)程和線程

第2章

進(jìn)程和線程本章內(nèi)容提要

進(jìn)程概念進(jìn)程的狀態(tài)和組成進(jìn)程管理線程進(jìn)程的同步和通信經(jīng)典進(jìn)程同步問(wèn)題管程進(jìn)程通信

2.1進(jìn)程概念2.1.1多道程序設(shè)計(jì)1．順序程序活動(dòng)的特點(diǎn)

●順序性●封閉性●可再現(xiàn)性2．多道程序設(shè)計(jì)

■程序并發(fā)執(zhí)行

●提高系統(tǒng)資源利用率

●增加作業(yè)吞吐量

多道程序設(shè)計(jì)3．程序并發(fā)執(zhí)行的特征①失去封閉性②程序與計(jì)算不再一一對(duì)應(yīng)③并發(fā)程序在執(zhí)行期間相互制約2.1.2進(jìn)程概念

1．進(jìn)程概念的引入多道程序并發(fā)執(zhí)行所引發(fā)的一系列新情況2．進(jìn)程概念●進(jìn)程最根本的屬性是動(dòng)態(tài)性和并發(fā)性進(jìn)程定義：程序在并發(fā)環(huán)境中的執(zhí)行過(guò)程進(jìn)程和程序的區(qū)別

（1）動(dòng)態(tài)性（2）并發(fā)性（3）非對(duì)應(yīng)性（4）異步性

進(jìn)程概念

3．進(jìn)程的基本特征

（1）動(dòng)態(tài)性（2）并發(fā)性（3）調(diào)度性2.2進(jìn)程的狀態(tài)和組成2.2.1進(jìn)程的狀態(tài)及其轉(zhuǎn)換

1．進(jìn)程的基本狀態(tài)●運(yùn)行狀態(tài)（Running）●就緒狀態(tài)（Ready）●阻塞狀態(tài)（Blocked）進(jìn)程的5種基本狀態(tài)及其轉(zhuǎn)換2．進(jìn)程狀態(tài)的轉(zhuǎn)換

（1）新建→就緒（2）就緒→運(yùn)行（3）運(yùn)行→阻塞（4）阻塞→就緒（5）運(yùn)行→就緒（6）運(yùn)行→終止2.2.2進(jìn)程描述1．進(jìn)程映像進(jìn)程映像通常就由程序、數(shù)據(jù)集合、棧和PCB等4部分組成

進(jìn)程映像模型

進(jìn)程描述2．進(jìn)程控制塊的組成進(jìn)程控制塊（PCB）也稱(chēng)進(jìn)程描述塊（ProcessDescriptor），它是進(jìn)程組成中最關(guān)鍵的部分，其中含有進(jìn)程的描述信息和控制信息，是進(jìn)程動(dòng)態(tài)特性的集中反映，是系統(tǒng)對(duì)進(jìn)程施行識(shí)別和控制的依據(jù)。

進(jìn)程描述進(jìn)程控制塊應(yīng)包含的主要內(nèi)容：進(jìn)程名特征信息進(jìn)程狀態(tài)信息調(diào)度優(yōu)先權(quán)通信信息現(xiàn)場(chǎng)保護(hù)區(qū)資源需求進(jìn)程實(shí)體信息族系關(guān)系其他信息

進(jìn)程描述3．進(jìn)程控制塊的作用每個(gè)進(jìn)程有惟一的進(jìn)程控制塊操作系統(tǒng)根據(jù)PCB對(duì)進(jìn)程實(shí)施控制和管理進(jìn)程的動(dòng)態(tài)、并發(fā)等特征是利用PCB表現(xiàn)出來(lái)的PCB是進(jìn)程存在的唯一標(biāo)識(shí)

2.2.3進(jìn)程隊(duì)列1．線性方式

PCB線性隊(duì)列示意圖

進(jìn)程隊(duì)列2．鏈接方式PCB鏈接隊(duì)列示意圖

PCB索引結(jié)構(gòu)示意圖

3．索引方式進(jìn)程隊(duì)列2.3進(jìn)程管理2.3.1進(jìn)程圖

進(jìn)程圖（ProcessGraph）是描述進(jìn)程族系關(guān)系的有向樹(shù)進(jìn)程創(chuàng)建的層次關(guān)系2.3.2進(jìn)程創(chuàng)建引發(fā)創(chuàng)建進(jìn)程的事件：調(diào)度新作業(yè)用戶(hù)登錄操作系統(tǒng)提供特定服務(wù)派生新進(jìn)程

進(jìn)程創(chuàng)建●創(chuàng)建新進(jìn)程時(shí)要執(zhí)行創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用（如UNIX/Linux系統(tǒng)中的fork）●其主要操作過(guò)程有如下四步：（1）申請(qǐng)一個(gè)空閑的PCB（2）為新進(jìn)程分配資源（3）將新進(jìn)程的PCB初始化（4）將新進(jìn)程加到就緒隊(duì)列中#include<unistd.h>#include<sys/types.h>#include<stdio.h>intmain(intargc,char*argv[]){ intpid; pid=fork(); /*創(chuàng)建一個(gè)子進(jìn)程*/ if(pid<0){ /*出現(xiàn)錯(cuò)誤。進(jìn)程ID號(hào)不可能小于0*/ fprintf(stderr,"ForkFailed"); /*輸出出錯(cuò)消息——ForkFailed*/ exit(-1); /*程序終止，返回碼-1*/ } elseif(pid==0){ /*下面是子進(jìn)程執(zhí)行*/ execlp("/bin/ls","ls",NULL); /*執(zhí)行目錄/bin下面的ls命令*/ } else{ /*下面是父進(jìn)程執(zhí)行*/wait(NULL); /*父進(jìn)程等待子進(jìn)程完成*/printf("ChildComplete"); /*輸出子進(jìn)程完成的信息*/exit(0); /*終止*/}}2.3.3進(jìn)程終止導(dǎo)致進(jìn)程終止的三種情況：

正常終止異常終止外部干擾

進(jìn)程終止終止進(jìn)程的主要操作過(guò)程如下：找到指定進(jìn)程的PCB終止該進(jìn)程的運(yùn)行回收該進(jìn)程所占用的全部資源終止其所有子孫進(jìn)程，回收它們所占用的全部資源。將被終止進(jìn)程的PCB從原來(lái)隊(duì)列中摘走2.3.4進(jìn)程阻塞進(jìn)程阻塞的過(guò)程如下：立即停止當(dāng)前進(jìn)程的執(zhí)行現(xiàn)行進(jìn)程的CPU現(xiàn)場(chǎng)保存現(xiàn)行狀態(tài)由“運(yùn)行”改為“阻塞”轉(zhuǎn)到進(jìn)程調(diào)度程序2.3.5進(jìn)程喚醒

喚醒原語(yǔ)執(zhí)行過(guò)程如下：把阻塞進(jìn)程從相應(yīng)的阻塞隊(duì)列中摘下將現(xiàn)行狀態(tài)改為就緒狀態(tài)，然后把該進(jìn)程插入就緒隊(duì)列中如果被喚醒的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí)更高，則設(shè)置重新調(diào)度標(biāo)志2.4線程2.4.1線程概念現(xiàn)代操作系統(tǒng)中，進(jìn)程只作為資源擁有者，而調(diào)度和運(yùn)行的屬性賦予新的實(shí)體——線程。線程（Thread）是進(jìn)程中實(shí)施調(diào)度和分派的基本單位

線程概念1．線程的組成每個(gè)線程有一個(gè)thread結(jié)構(gòu)，即線程控制塊，用于保存自己私有的信息，主要由以下4個(gè)基本部分組成：一個(gè)唯一的線程標(biāo)識(shí)符

一組寄存器

兩個(gè)棧指針

一個(gè)私有存儲(chǔ)區(qū)

thread結(jié)構(gòu)示意圖

線程的組成線程必須在某個(gè)進(jìn)程內(nèi)執(zhí)行一個(gè)進(jìn)程可以包含一個(gè)線程或多個(gè)線程單線程和多線程的進(jìn)程模型2．線程的狀態(tài)運(yùn)行狀態(tài)就緒狀態(tài)阻塞狀態(tài)終止?fàn)顟B(tài)3．線程的管理

線程創(chuàng)建線程終止線程等待線程讓權(quán)4．線程和進(jìn)程的關(guān)系

①一個(gè)進(jìn)程可以有多個(gè)線程，但至少要有一個(gè)線程；而一個(gè)線程只能在一個(gè)進(jìn)程的地址空間內(nèi)活動(dòng)。②資源分配給進(jìn)程，同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。③處理機(jī)分配給線程，即真正在處理機(jī)上運(yùn)行的是線程。④線程在執(zhí)行過(guò)程中需要協(xié)作同步。不同進(jìn)程的線程間要利用消息通信的辦法實(shí)現(xiàn)同步。5．引入線程的好處

①易于調(diào)度②提高并發(fā)性③開(kāi)銷(xiāo)少④利于充分發(fā)揮多處理器的功能2.4.2線程的實(shí)現(xiàn)●在用戶(hù)空間實(shí)現(xiàn)

優(yōu)點(diǎn)：切換速度快；調(diào)度算法可專(zhuān)用

；可運(yùn)行在任何操作系統(tǒng)上

缺點(diǎn)：阻塞問(wèn)題；多處理器利用問(wèn)題

●在核心空間實(shí)現(xiàn)優(yōu)點(diǎn)：克服了用戶(hù)級(jí)線程方式的兩個(gè)主要缺陷；本身也可以是多線程的

缺點(diǎn)：控制轉(zhuǎn)移開(kāi)銷(xiāo)大

▲組合方式

2.5進(jìn)程的同步和通信進(jìn)程間的相互關(guān)系主要分為如下三種形式：①互斥——競(jìng)爭(zhēng)同一資源而發(fā)生相互制約

②同步——協(xié)同完成一項(xiàng)任務(wù)

③通信——交換信息

2.5.1進(jìn)程的同步與互斥1．同步同步進(jìn)程通過(guò)共享資源來(lái)協(xié)調(diào)活動(dòng)，在執(zhí)行時(shí)間的次序上有一定約束。雖然彼此不直接知道對(duì)方的名字，但知道對(duì)方的存在和作用。在協(xié)調(diào)動(dòng)作的情況下，多個(gè)進(jìn)程可以共同完成一項(xiàng)任務(wù)。2．互斥在邏輯上這兩個(gè)進(jìn)程本來(lái)完全獨(dú)立，毫無(wú)關(guān)系，只是由于競(jìng)爭(zhēng)同一個(gè)物理資源而相互制約。它們的運(yùn)行不具有時(shí)間次序的特征互斥示例假定進(jìn)程Pa負(fù)責(zé)為用戶(hù)作業(yè)分配打印機(jī)，進(jìn)程Pb負(fù)責(zé)釋放打印機(jī)。系統(tǒng)中設(shè)立一個(gè)打印機(jī)分配表，由各個(gè)進(jìn)程共用。打印機(jī)分配表（初始情況）打印機(jī)分配表（出錯(cuò)情況）

打印機(jī)編號(hào)

分配標(biāo)識(shí)

用戶(hù)名

用戶(hù)定義的設(shè)備名

01MengPRINT1021LiuOUTPUT打印機(jī)編號(hào)

分配標(biāo)識(shí)用戶(hù)名用戶(hù)定義的設(shè)備名011021LiuOUTPUT競(jìng)爭(zhēng)條件（RaceCondition）兩個(gè)或多個(gè)進(jìn)程同時(shí)訪問(wèn)和操縱相同的數(shù)據(jù)時(shí)，最后的執(zhí)行結(jié)果取決于進(jìn)程運(yùn)行的精確時(shí)序。2.5.2臨界資源和臨界區(qū)1．臨界資源和臨界區(qū)臨界資源（CriticalResource）一次僅允許一個(gè)進(jìn)程使用的共享資源臨界區(qū)（CriticalSection），簡(jiǎn)稱(chēng)CS區(qū)在每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段程序2．進(jìn)程的一般結(jié)構(gòu)

典型進(jìn)程的一般結(jié)構(gòu)3．臨界區(qū)進(jìn)入準(zhǔn)則①單獨(dú)進(jìn)入②獨(dú)占該區(qū)③限時(shí)退出④主動(dòng)讓權(quán)進(jìn)程A和進(jìn)程B互斥使用臨界區(qū)的過(guò)程2.5.3互斥實(shí)現(xiàn)方式1．利用硬件方法解決進(jìn)程互斥問(wèn)題

▲禁止中斷

進(jìn)入臨界區(qū)之后立即關(guān)閉所有的中斷

▲專(zhuān)用機(jī)器指令TSL（TestandSetLock，即測(cè)試并上鎖）的指令：TSLRX，LOCK

匯編代碼示例

enter_region:TSLREGISTER,LOCKCMPREGISTER,#0JNEenter_regionRETleave_region:MOVELOCK,#0RET2．原語(yǔ)是機(jī)器指令的延伸，往往是為完成某些特定的功能而編制的一段系統(tǒng)程序。原語(yǔ)操作也稱(chēng)做“原子操作”（atomicaction），即一個(gè)操作中的所有動(dòng)作要么全做，要么全不做。執(zhí)行原語(yǔ)操作時(shí)，要屏蔽中斷，以保證其操作的不可分割性。3．利用軟件方法解決進(jìn)程互斥問(wèn)題可為每類(lèi)臨界區(qū)設(shè)置一把鎖，該鎖有打開(kāi)和關(guān)閉兩種狀態(tài)。關(guān)鎖原語(yǔ)lock(W):while(W==1);W=1;開(kāi)鎖原語(yǔ)unlock(W):w=0;

進(jìn)程A

……

lock(W);打印信息S;}CS區(qū)

unlock(W);……

進(jìn)程B

……

lock(W);打印信息S;}CS區(qū)

unlock(W);……用鎖實(shí)現(xiàn)進(jìn)程互斥設(shè)系統(tǒng)中有一臺(tái)打印機(jī)，有兩個(gè)進(jìn)程A和B都要使用它，以變量W表示鎖，預(yù)先把它的值置為0。

2.5.4信號(hào)量1．整型信號(hào)量P操作最初源于荷蘭語(yǔ)proberen，表示測(cè)試；V操作源于荷蘭語(yǔ)verhogen，表示增加。在有些書(shū)上將P操作稱(chēng)做wait或者DOWN操作，將V操作稱(chēng)做signal或者UP操作。對(duì)信號(hào)量的操作有以下限制：

①信號(hào)量可以初始化為一個(gè)非負(fù)值。 ②只能由P和V兩個(gè)操作來(lái)訪問(wèn)信號(hào)量。

整型信號(hào)量P和V操作都是原語(yǔ)偽代碼形式

P(S){V(S){ while(S≤0);S++; S--;}}

實(shí)現(xiàn)互斥的偽代碼形式

do{ P(mutex); 臨界區(qū) V(mutex); 其他代碼區(qū)}while(1);

信號(hào)量2．結(jié)構(gòu)型信號(hào)量結(jié)構(gòu)型信號(hào)量又稱(chēng)計(jì)數(shù)信號(hào)量，簡(jiǎn)稱(chēng)信號(hào)量一般是由兩個(gè)成員組成的數(shù)據(jù)結(jié)構(gòu)。其中一個(gè)成員是整型變量，表示該信號(hào)量的值；另一個(gè)是指向PCB的指針。typedefstruct{intvalue;structPCB*list;}semaphore;

結(jié)構(gòu)型信號(hào)量●信號(hào)量的值與相應(yīng)資源的使用情況有關(guān)●信號(hào)量的一般結(jié)構(gòu)及PCB隊(duì)列

對(duì)信號(hào)量的操作有如下嚴(yán)格限制：信號(hào)量可以賦初值，且初值為非負(fù)數(shù)。在使用過(guò)程中，信號(hào)量的值可以修改，但只能由P和V操作來(lái)訪問(wèn)，不允許通過(guò)其他方式來(lái)查看或操縱信號(hào)量。結(jié)構(gòu)型信號(hào)量P、V操作的定義

voidP(semaphoreS)voidV(semaphoreS){{S.value--;S.value++；if(S.value<0){if(S.value<=0){把這個(gè)進(jìn)程加到S.list隊(duì)列；從S.list隊(duì)列中移走進(jìn)程Q；block()；wakeup(Q)；}}}}

●在具體實(shí)現(xiàn)時(shí)應(yīng)注意，P,V操作都應(yīng)作為一個(gè)整體實(shí)施，不允許分割或相互穿插執(zhí)行

結(jié)構(gòu)型信號(hào)量

結(jié)構(gòu)型信號(hào)量

3．二值信號(hào)量

一種特例，它的值只能在0和1之間選擇

typedefstruct{enum{false,true}value;/*枚舉量*/structPCB*list;}B_semaphore;voidP_B(B_semaphoreS){if(S.value==true)S.value=false;else{把該進(jìn)程放入S.list隊(duì)列;block();}}voidV_B(B_semaphoreS){if(S.list==NULL)S.value=true;else{ 從S.list隊(duì)列中移走進(jìn)程Q;wakeup(Q);}}2.5.5信號(hào)量的一般應(yīng)用1．用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥

打印機(jī)分配表的互斥使用

Pa:Pb:……P(mutex)P(mutex)分配打印機(jī)釋放打印機(jī)（讀寫(xiě)分配表）（讀寫(xiě)分配表）V(mutex)V(mutex)……

用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥利用信號(hào)量實(shí)現(xiàn)互斥的一般模型是：

進(jìn)程P1進(jìn)程P2…進(jìn)程Pn………P(mutex);P(mutex);P(mutex);臨界區(qū)臨界區(qū)臨界區(qū)V(mutex);V(mutex);V(mutex);………用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥●注意點(diǎn)：①在每個(gè)程序中用于實(shí)現(xiàn)互斥的P(mutex)和V(mutex)必須成對(duì)出現(xiàn)，即先做P，進(jìn)入臨界區(qū)；后做V，退出臨界區(qū)。②互斥信號(hào)量mutex的初值一般為1。2．用信號(hào)量實(shí)現(xiàn)進(jìn)程簡(jiǎn)單同步

對(duì)緩沖區(qū)的同步使用問(wèn)題

簡(jiǎn)單供者和用者對(duì)緩沖區(qū)的使用關(guān)系

用信號(hào)量實(shí)現(xiàn)進(jìn)程簡(jiǎn)單同步供者和用者間要交換兩個(gè)消息：

緩沖區(qū)空緩沖區(qū)滿設(shè)置兩個(gè)信號(hào)量：

S1表示緩沖區(qū)是否空（0表示不空，1表示空）。S2表示緩沖區(qū)是否滿（0表示不滿，1表示滿）。規(guī)定S1和S2的初值分別為1和0用信號(hào)量實(shí)現(xiàn)進(jìn)程簡(jiǎn)單同步

供者進(jìn)程用者進(jìn)程L1:P(S1)L2:…啟動(dòng)讀卡機(jī)P(S2);…從緩沖區(qū)取出信息收到輸入結(jié)束中斷V(S1);V(S2);加工并且存盤(pán)gotoL1;gotoL2;用信號(hào)量實(shí)現(xiàn)進(jìn)程簡(jiǎn)單同步用P和V操作實(shí)現(xiàn)同步時(shí)應(yīng)注意如下三點(diǎn)：①分析進(jìn)程間的制約關(guān)系，確定信號(hào)量種類(lèi)。②信號(hào)量的初值與相應(yīng)資源的數(shù)量有關(guān)，也與P,V操作在程序代碼中出現(xiàn)的位置有關(guān)。③同一信號(hào)量的P,V操作要“成對(duì)”出現(xiàn)，但是，它們分別出現(xiàn)在不同的進(jìn)程代碼中。2.6經(jīng)典進(jìn)程同步問(wèn)題1．生產(chǎn)者-消費(fèi)者問(wèn)題生產(chǎn)者:能產(chǎn)生并釋放資源的進(jìn)程消費(fèi)者:單純使用（消耗）資源的進(jìn)程問(wèn)題表述

一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程（設(shè)每組有多個(gè)進(jìn)程）通過(guò)緩沖區(qū)發(fā)生聯(lián)系。生產(chǎn)者進(jìn)程將生產(chǎn)的產(chǎn)品（數(shù)據(jù)、消息等統(tǒng)稱(chēng)為產(chǎn)品）送入緩沖區(qū)，消費(fèi)者進(jìn)程從中取出產(chǎn)品。假定緩沖區(qū)共有N個(gè)，不妨把它們?cè)O(shè)想成一個(gè)環(huán)形緩沖池。生產(chǎn)者-消費(fèi)者問(wèn)題生產(chǎn)者-消費(fèi)者問(wèn)題環(huán)形緩沖池它們應(yīng)滿足如下同步條件：①任一時(shí)刻所有生產(chǎn)者存放產(chǎn)品的單元數(shù)不能超過(guò)緩沖區(qū)的總?cè)萘浚∟）。②所有消費(fèi)者取出產(chǎn)品的總量不能超過(guò)所有生產(chǎn)者當(dāng)前生產(chǎn)產(chǎn)品的總量。

生產(chǎn)者-消費(fèi)者問(wèn)題●設(shè)緩沖區(qū)的編號(hào)為0～N-1，in和out分別是生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程使用的指針，指向下面可用的緩沖區(qū)，初值都是0?！裨O(shè)置三個(gè)信號(hào)量：full：表示放有產(chǎn)品的緩沖區(qū)數(shù)，其初值為0。empty：表示可供使用的緩沖區(qū)數(shù)，其初值為N。mutex：互斥信號(hào)量，初值為1，表示各進(jìn)程互斥進(jìn)入臨界區(qū)，保證任何時(shí)候只有一個(gè)進(jìn)程使用緩沖區(qū)。

生產(chǎn)者-消費(fèi)者問(wèn)題生產(chǎn)者進(jìn)程Producer：消費(fèi)者進(jìn)程Consumer：while(TRUE){ while(TRUE){P(empty); P(full);P(mutex); P(mutex);產(chǎn)品送往buffer(in); 從buffer(out)中取出產(chǎn)品；in=(in+1)modN;out=(out+1)modN;/*以N為模*//*以N為模*/V(mutex); V(mutex);V(full); V(empty);} }2．讀者-寫(xiě)者問(wèn)題

讀者-寫(xiě)者問(wèn)題也是一個(gè)著名的進(jìn)程互斥訪問(wèn)有限資源的同步問(wèn)題。例如，一個(gè)航班預(yù)訂系統(tǒng)有一個(gè)大型數(shù)據(jù)庫(kù)，很多競(jìng)爭(zhēng)進(jìn)程要對(duì)它進(jìn)行讀、寫(xiě)。允許多個(gè)進(jìn)程同時(shí)讀該數(shù)據(jù)庫(kù)，但是在任何時(shí)候如果有一個(gè)進(jìn)程寫(xiě)（即修改）數(shù)據(jù)庫(kù)，那么就不允許其他進(jìn)程訪問(wèn)它——既不允許寫(xiě)，也不允許讀。

讀者-寫(xiě)者問(wèn)題

●信號(hào)量設(shè)置：

▲讀互斥信號(hào)量rmutex初值為1

▲寫(xiě)互斥信號(hào)量wmutex初值為1rmutex：讀者互斥地訪問(wèn)readcountwmutex：保證一個(gè)寫(xiě)者與其他讀者/寫(xiě)者互斥地訪問(wèn)共享資源★讀計(jì)數(shù)器readcount，整型變量，初值為0。

讀者-寫(xiě)者問(wèn)題

讀者Readers

while(TRUE){P(rmutex);readcount=readcount+1;if(readcount==1)P(wmutex);V(rmutex);執(zhí)行讀操作P(rmutex);readcount=readcount-1;if(readcount==0)V(wmutex);V(rmutex);使用讀取的數(shù)據(jù)}寫(xiě)者Writers

while(TRUE){P(wmutex);執(zhí)行寫(xiě)操作V(wmutex);}

▲這個(gè)算法隱含讀者的優(yōu)先級(jí)高于寫(xiě)者3．哲學(xué)家進(jìn)餐問(wèn)題五位哲學(xué)家圍坐在一張圓桌旁進(jìn)餐，每人面前有一只碗，各碗之間分別有一根筷子。每位哲學(xué)家在用兩根筷子夾面條吃飯前獨(dú)自進(jìn)行思考，感到饑餓時(shí)便試圖占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能強(qiáng)行從鄰座手中拿過(guò)筷子，而且必須用兩根筷子進(jìn)餐；餐畢，要把筷子放回原處并繼續(xù)思考問(wèn)題。

哲學(xué)家進(jìn)餐問(wèn)題

哲學(xué)家進(jìn)餐問(wèn)題===========================================#defineN5#defineLEFT(i-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2typedefstruct{/*定義結(jié)構(gòu)型信號(hào)量*/intvalue;structPCB*list;}semaphore;intstate[N];semaphoremutex=1;/*互斥進(jìn)入臨界區(qū)*/semaphores[N]; /*每位哲學(xué)家一個(gè)信號(hào)量*/

哲學(xué)家進(jìn)餐問(wèn)題voidphilosopher(inti){while(TRUE){think(); /*哲學(xué)家在思考問(wèn)題*/take_chopstick(i);/*拿到兩根筷子或者等待*/eat(); /*進(jìn)餐*/put_chopstick(i);/*把筷子放回原處*/}}voidtake_chopstick(inti){P(mutex);state[i]=HUNGRY;test(i);/*試圖拿兩根筷子*/V(mutex);P(s[i]);}

哲學(xué)家進(jìn)餐問(wèn)題voidput_chopstick(inti){P(mutex);state[i]=THINKING;test(LEFT); /*查看左鄰，現(xiàn)在能否進(jìn)餐*/test(RIGHT); /*查看右鄰，現(xiàn)在能否進(jìn)餐*/V(mutex);}voidtest(inti){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;V(s[i]);}}===============================================打瞌睡的理發(fā)師4．打瞌睡的理發(fā)師問(wèn)題理發(fā)店有一名理發(fā)師，一把理發(fā)椅和幾把座椅，等待理發(fā)者可坐在上面。如果沒(méi)有顧客到來(lái)，理發(fā)師就坐在理發(fā)椅上打盹。當(dāng)顧客到來(lái)時(shí)，就喚醒理發(fā)師。如果顧客到來(lái)時(shí)理發(fā)師正在理發(fā)，該顧客就坐在椅子上排隊(duì)；如果滿座了，他就離開(kāi)這個(gè)理發(fā)店，到別處去理發(fā)。

打瞌睡的理發(fā)師問(wèn)題理發(fā)師和每位顧客都分別是一個(gè)進(jìn)程

===============================#defineCHAIRS5typedefstruct{intvalue;structPCB*list;}semaphore;semaphorecustomers=0;semaphorebarbers=0;semaphoremutex=1;intwaiting=0;

voidbarber(void){while(TRUE){P(customers);/*如果沒(méi)有顧客，則理發(fā)師打瞌睡*/P(mutex);/*互斥進(jìn)入臨界區(qū)*/waiting--;V(barbers);/*一個(gè)理發(fā)師準(zhǔn)備理發(fā)*/V(mutex);/*退出臨界區(qū)*/cut_hair();/*理發(fā)（在臨界區(qū)之外）*/}}

打瞌睡的理發(fā)師問(wèn)題

打瞌睡的理發(fā)師問(wèn)題

voidcustomer(void){P(mutex); /*互斥進(jìn)入臨界區(qū)*/if(waiting﹤CHAIRS){waiting++;V(customers); /*若有必要，喚醒理發(fā)師*/V(mutex);/*退出臨界區(qū)*/P(barbers); /*如果理發(fā)師正忙著，則顧客打瞌睡*/get_haircut();}elseV(mutex); /*店里人滿了，不等了*/}2.7管程管程：一個(gè)管程定義一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程在其上執(zhí)行的一組操作，這組操作能使進(jìn)程同步和改變管程中的數(shù)據(jù)。由管程名稱(chēng)、局部于管程的共享數(shù)據(jù)的說(shuō)明、對(duì)數(shù)據(jù)進(jìn)行操作的一組過(guò)程和對(duì)該共享數(shù)據(jù)賦初值的語(yǔ)句四部分組成。管程的結(jié)構(gòu)

管程管程具有以下三個(gè)特性：①管程內(nèi)部的局部數(shù)據(jù)變量只能被管程內(nèi)定義的過(guò)程所訪問(wèn)，不能被管程外面聲明的過(guò)程直接訪問(wèn)。②進(jìn)程要想進(jìn)入管程，必須調(diào)用管程內(nèi)的某個(gè)過(guò)程。③一次只能有一個(gè)進(jìn)程在管程內(nèi)執(zhí)行，而其余調(diào)用該管程的進(jìn)程都被掛起，等待該管程成為可用的。即管程能有效地實(shí)現(xiàn)互斥。

管程▲實(shí)現(xiàn)互斥是由編譯程序完成▲為解決同步問(wèn)題，引入兩個(gè)條件變量x和y：conditionx,y;操作原語(yǔ)wait(x)：掛起等待條件x的調(diào)用進(jìn)程，釋放相應(yīng)的管程，以便供其他進(jìn)程使用。操作原語(yǔ)signal(x)：恢復(fù)執(zhí)行先前因在條件x上執(zhí)行wait而掛起的那個(gè)進(jìn)程。管程的職責(zé)與信號(hào)量的職責(zé)不同。帶條件變量的管程結(jié)構(gòu)

2.8進(jìn)程通信進(jìn)程通信——進(jìn)程間的信息交換低級(jí)進(jìn)程通信高級(jí)進(jìn)程通信▲共享存儲(chǔ)器方式：在內(nèi)存中分配一片空間作為共享存儲(chǔ)區(qū)

▲消息傳遞方式：以消息（Message）為單位在進(jìn)程間進(jìn)行數(shù)據(jù)交換

●直接通信方式●間接通信方式

▲管道文件方式：寫(xiě)者向管道文件中寫(xiě)入數(shù)據(jù)；讀者從該文件中讀出數(shù)據(jù)2.8.1消息傳遞系統(tǒng)允許進(jìn)程彼此進(jìn)行通信，而不必借助于共享數(shù)據(jù)提供兩個(gè)原語(yǔ)（系統(tǒng)調(diào)用

）

send和receive：send(destination,message)receive(source,message)

消息傳遞系統(tǒng)

消息傳送系統(tǒng)設(shè)計(jì)涉及同