第二章 進程的描述與控制

第二章進程的描述與控制

軟件工程學院計算機應用系目錄1.進程的基本概念2.進程控制

3.進程同步4.經典進程同步問題5.進程通信6.線程的基本概念

是一個有向無循環(huán)圖，圖中每個結點表示一個語句、一段程序或一個進程1.前驅圖有向邊<Vi,Vj>表示Vj僅在

Vi執(zhí)行完后才能開始執(zhí)行

S1S3S7S6S4S2S52.1進程的基本概念順序執(zhí)行的特征順序性封閉性可再現性：程序的運行結果與其推進速度無關例：程序段

read(disk,&a,4);/*從磁盤讀a*/c=a+2;printf(“c=%f\n”,c);2.程序的順序執(zhí)行→I→C→PI→C→P3.程序的并發(fā)執(zhí)行（1）概念（2）特征間斷(異步)性：“運行－暫停－運行”；失去封閉性不可再現性：進程的運行結果與其推進速度有關。

2.1進程的基本概念4.進程的定義及特征簡單定義：一個程序的一次運行過程。特征：動態(tài)性：進程最基本的特征結構特征：＝程序＋數據＋PCB

321該程序所需的相關數據(變量、工作空間，緩沖區(qū)等)該程序的執(zhí)行上下文(Context)一個可執(zhí)行的程序2.1進程的基本概念獨立性：是系統(tǒng)進行資源分配和調度的獨立單位，是能獨立運行的基本單位并發(fā)性：程序在建立進程后并發(fā)運行異步性：進程以不可預知的速度向前推進

進程特征定義：可并發(fā)執(zhí)行的程序在一個數據集合上的一次運行過程，是系統(tǒng)進行資源分配和調度的一個獨立單位。2.1進程的基本概念(1)從定義上看，進程是程序處理數據的過程，而程序是一組指令的有序集合；(2)進程具有動態(tài)性、并發(fā)性、獨立性和異步性等，而程序不具有這些特性；(3)從進程結構特性上看，它包含程序、數據和PCB；(4)進程和程序并非一一對應：通過多次執(zhí)行，一個程序可對應多個進程；通過調用關系，一個進程可執(zhí)行多個程序。進程與程序的區(qū)別2.1進程的基本概念就緒狀態(tài)：進程分配到必要的資源，等待獲得CPU執(zhí)行的狀態(tài)。組織成一個或多個就緒隊列。運行狀態(tài)：進程分配到必要的資源，在CPU上執(zhí)行時的狀態(tài)阻塞狀態(tài)（等待狀態(tài)）：正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)。組織成一個或多個阻塞隊列。5.進程的狀態(tài)（1）三種基本狀態(tài)進程三種基本狀態(tài)的轉換運行就緒阻塞等待事件

(系統(tǒng)服務請求，如請求I/O)被調度或分派時間片用完事件發(fā)生進程三種基本狀態(tài)的轉換：思考問題：1.在進程狀態(tài)轉換時，下列哪一種狀態(tài)轉換是不可能發(fā)生的？

A)就緒態(tài)→運行態(tài)B)運行態(tài)→就緒態(tài)

C)運行態(tài)→等待態(tài)D)阻塞態(tài)→運行態(tài)答案：D2．某進程在運行過程中需要等待從磁盤上讀入數據，此時該進程的狀態(tài)將（）。

A.從就緒變?yōu)檫\行B.從運行變?yōu)榫途w

C.從運行變?yōu)樽枞鸇.從阻塞變?yōu)榫途w答案：C2.1進程的基本概念引人掛起狀態(tài)的原因：（1）操作系統(tǒng)的需要；（2）終端用戶的需要；（3）父進程請求；（4）負荷調節(jié)的需要。進程狀態(tài)的轉換：（2）掛起狀態(tài)：靜止狀態(tài)靜止就緒靜止阻塞掛起掛起激活激活（1）活動就緒靜止就緒（2）活動阻塞靜止阻塞（3）靜止就緒活動就緒（4）靜止阻塞活動阻塞(5)運行狀態(tài)靜止就緒掛起具有掛起狀態(tài)的進程狀態(tài)轉換活動就緒運行活動阻塞靜止阻塞靜止就緒wakeup(喚醒)事件發(fā)生掛起suspend時間片完被調度scheduler激活

active掛起

suspend激活

active掛起

suspend等待事件

sleep事件發(fā)生wakeup(喚醒)2.1進程的基本概念（3）創(chuàng)建狀態(tài)和終止狀態(tài)（1）NULL創(chuàng)建（2）創(chuàng)建活動就緒（3）創(chuàng)建靜止就緒（4）執(zhí)行終止補充：進程管理功能：（1）進程控制：控制進程狀態(tài)轉換；（2）進程同步：進程間運行順序的協(xié)調：互斥方式；同步方式： （3）進程通信：進程間的信息交換直接通信；間接通信。

（4）進程調度：進程間競爭臨界資源進程間相互合作2.1進程的基本概念程序：描述進程要完成的功能數據集合：包含程序運行所需的數據和工作區(qū)進程控制塊（PCB）：包含進程的描述信息和控制信息，是進程動態(tài)特性的反映5.進程控制塊PCB程序和數據集合是進程的實體進程控制塊是進程存在的唯一標志進程控制塊是由OS維護的用來記錄進程相關信息的一塊內存。2.1進程的基本概念進程標識符：內部標識符、外部標識符處理機狀態(tài)信息：（1）通用寄存器；（2）段寄存器；（3）指令計數器；（4）程序狀態(tài)字(PSW)；進程控制塊（PCB)內容32位CPU有8個32位的通用寄存器EAX、EBX、ECX、EDX、ESI、EDI、EBP和ESP

。EAX：稱為累加器，可用于乘、除、輸入/輸出等操作；EBX:稱為基地址寄存器,可作為存儲器指針來使用；ECX:稱為計數寄存器,控制循環(huán)次數；EDX:稱為數據寄存器,在進行乘、除運算時，作為默認的操作數參與運算，也可用于存放I/O的端口地址。ESI：變址寄存器，是內存移動和比較操作的源地址寄存器；EDI：變址寄存器，是內存移動和比較操作的目標地址寄存器EBP：指針寄存器，存放堆棧幀的始址；ESP:指針寄存器，當前堆棧棧頂位置。段寄存器是根據內存分段的管理模式而設置的。內存單元的物理地址由段寄存器的值和一個偏移量組合而成。32位CPU有6個，16位CPU有4個

。CS：代碼段寄存器，其值為代碼段的段地址；DS：數據段寄存器，其值為數據段的地址；ES：附加段寄存器，其值為附加數據段的地址；SS：堆棧段寄存器，其值為堆棧段的地址；FS：附加段寄存器，其值為附加數據段的地址；GS：附加段寄存器，其值為附加數據段的地址。

中斷允許位、陷入標志、任務嵌套標志、特權標志、溢出標志、符號標志、零標志、進位標志等2.1進程的基本概念進程控制信息：（1）程序和數據地址；（2）進程同步和通信信息；（3）資源清單；（4）鏈接指針進程控制塊內容鏈接方式：索引方式進程控制塊的組織方式（1）就緒鏈表；（2）執(zhí)行進程；（3）阻塞鏈表；（4）空白鏈表。進程調度信息：（1）進程狀態(tài)；（2）進程優(yōu)先級；（3）事件；（4）其他信息2.2進程控制進程控制的功能完成進程狀態(tài)的轉換。原語(primitive)：由若干條指令構成的“原子操作(atomicoperation)”過程，完成某種特定的功能，作為一個整體而不可分割－－要么全都完成，要么全都不做。OS的內核

為了對進程控制，系統(tǒng)中必須設置一個機構，它具有創(chuàng)建撤消以及進程通訊和資源管理等功能，這樣結構稱為OS的內核(kernel)。2.2進程控制用于進程控制的原語有：(1)創(chuàng)建進程原語 (2)終止進程原語

(3)掛起進程原語 (4)激活進程原語

(5)阻塞進程原語 (6)喚醒進程原語

進程圖概念：

描述系統(tǒng)中進程的家族關系的有向圖。2.系統(tǒng)啟動過程：機器加電，系統(tǒng)復位：CPU初始化（CS=F000H，IP=FFF0H）Cpu執(zhí)行第一條指令：JMP（ROMBIOS中的啟動程序入口加電自檢POST初始化顯卡、顯示BIOS信息、檢測CPU的類型和工作頻率、測試主機所有的內存；檢測系統(tǒng)中的標準硬件設備：硬盤、CD-ROM、軟驅、串行接口和并行接口等連接的設備；檢測和配置即插即用設備、更新擴展系統(tǒng)配置數據)系統(tǒng)啟動過程：執(zhí)行19H中斷：BOIS帶的系統(tǒng)初始引導程序讀入引導盤的第一個扇區(qū)到內存：若是硬盤：主引導程序+硬盤分區(qū)表讀入可引導分區(qū)第一個扇區(qū)Linux系統(tǒng)啟動過程：執(zhí)行bootsect.s程序：1）將自身從0x7C00處移動到0x90000處；2）調用BIOS13H中斷讀入setup.s程序到0x90200處；3）讀入磁盤驅動器參數4）加載system模塊到0x1000處5）跳轉到setup.s程序執(zhí)行。Linux系統(tǒng)啟動過程：執(zhí)行setup.s程序：1）從BIOS中讀取系統(tǒng)數據到0x90000處；2）將system模塊從0x10000移動到0x0000處；3）加載段描述符：中斷描述符表寄存器、全局描述符表寄存器；4）重新對中斷進行編程；5）轉換到保護模式運行：將控制寄存器CR0的位0置1即可；6）跳轉到system模塊執(zhí)行；（該模塊包括head.s,main.c程序，內核模塊等）系統(tǒng)啟動過程：執(zhí)行head.s程序：1）設置各個數據段寄存器；2）設置中斷描述符表；設置全局描述符表；3）設置頁目錄表；設置4張頁表；4）設置頁目錄基址寄存器CR3；5）啟動使用分頁處理：CR0的位31為1；6）跳轉到main.c執(zhí)行；head.s執(zhí)行后的內存映像：系統(tǒng)啟動過程：執(zhí)行main.c利用setup.s程序取得的系統(tǒng)參數設置系統(tǒng)的根文件設備號及一些內存全局變量建立可分頁主內存區(qū)的內存塊位示圖初始化設備：塊設備、字符設備、tty初始化調度程序相關的數據結構：如任務數組、全局描述符表、時鐘中斷處理句柄等初始化緩沖管理：如建立空閑緩沖區(qū)鏈表等初始化硬盤、軟驅管理等，并開啟中斷系統(tǒng)啟動過程：執(zhí)行main.c轉移到用戶模式運行任務（進程）0任務0調用fork()創(chuàng)建進程1進程1執(zhí)行init()程序Init()：1）調用setup()，讀取硬盤參數包括分區(qū)表信息，建立虛擬盤，安裝根文件系統(tǒng)設備；

2）用讀寫方式打開“/dev/tty00”（終端控制臺）

3）創(chuàng)建login進程等待用戶登錄；

4）登錄成功后調用fork()創(chuàng)建shell進程運行/bin/sh程序用戶登錄。作業(yè)調度。3.引起創(chuàng)建進程的事件：

(3)提供服務。

(4)應用請求。

4.創(chuàng)建進程原語的工作大致描述為：

申請空白PCB；為新進程分配資源；(3)初始化進程控制塊PCB；

(4)將新進程插入就緒隊列。

調用alloc_task_struct()分配兩個頁面存放task_struct及系統(tǒng)堆棧調用get_pid()獲得新建子進程PID1、調用copy_files()復制父進程已經打開的文件控制結構；2、調用copy_fs()復制父進程的根目錄、安裝點等；3、調用copy_sighand()復制父進程信號處理函數；4、調用copy_mm()復制父進程用戶地址空間調用copy_thread()復制系統(tǒng)堆棧調用wake_up_process()將子進程插入可運行進程隊列3.終止進程原語正常結束2)異常結束3)外界干預引起進程終止的事件：

OS父進程終止父進程請求（1）根據被終止進程的標識符，從PCB集合中檢索出該進程的PCB，獲得該進程的狀態(tài)（2）若被終止進程正處于執(zhí)行狀態(tài)，應立即終止該進程的執(zhí)行，并置調度標志為真。（3）若該進程還有子孫進程，終止其所有子孫進程。（4）回收資源（5）回收PCB進程終止的過程：

請求系統(tǒng)服務2)啟動某種操作3)新數據尚未到達4)無新工作可做：服務進程4.阻塞與喚醒原語引起進程阻塞與喚醒的事件：

停止當前進程執(zhí)行，并修改進程狀態(tài)：由“執(zhí)行”改為“阻塞”；2)將PCB插入阻塞隊列；

3)轉調度程序重新進行調度。

進程阻塞過程：

1)把被阻塞的進程從等待該事件的阻塞隊列中移出修改PCB中的進程狀態(tài)：由阻塞改為就緒3)將該PCB插入到就緒隊列中進程喚醒過程：

5.掛起與激活原語用戶進程請求將自己掛起(2)父進程請求將自己的某個子進程掛起(3)父進程或用戶進程請求激活指定進程，內存空間允許引起進程掛起和激活的事件

：

修改被掛起進程的狀態(tài)：若處于活動就緒狀態(tài)，若處于活動阻塞狀態(tài)，若進程處于運行狀態(tài)，將該進程的PCB復制到某指定的內存區(qū)域可能會被換出到外存4)若被掛起的進程正在執(zhí)行，則轉調度程序重新調度進程掛起過程

：

便將其改為靜止就緒；便將其改為靜止阻塞；便將其改為靜止就緒；將進程從外存調入內存；修改進程狀態(tài)：若是靜止就緒，便將之改為活動就緒；若為靜止阻塞，便將之改為活動阻塞。3）修改PCB中進程的程序和數據的地址；4）將PCB插入相關隊列。進程激活的過程

：

2.3進程同步

臨界資源進程間的制約關系（1）間接制約：相互競爭－－獨占分配到的部分或全部共享資源，“互斥”系統(tǒng)中一次僅允許一個進程使用的一類資源。打印機，卡片輸入機，磁帶機、共享變量等。互斥：指的是對某個系統(tǒng)資源，一個進程正在使用它，另外一個想用它的進程就必須等待，而不能同時使用；

（2）直接制約：相互協(xié)作－－等待來自其他進程的信息，“同步”,即保證進程間的前驅后繼關系。共享變量的修改沖突例：民航售票系統(tǒng)，n個售票處

/*ProcessPi,i=1,2,...,n*/…../*按訂票要求找到數據庫中的共享數據x[k]*//*x[k]存放某月某日某次航班的現有票數*/R=x[k];/*現有票數*/

if(R>=1){R--;

x[k]=R;

輸出一張機票；

}else

顯示“票已售完”；臨界區(qū)的互斥訪問過程：臨界區(qū)：進程中訪問臨界資源的程序段。同類臨界區(qū)：對同一臨界資源進行操作的程序段。entrysection進入區(qū)exitsection退出區(qū)

criticalsection(臨界區(qū)）

remaindersection（剩余區(qū)）臨界區(qū)(criticalsection)：進程中訪問臨界資源的一段代碼。進入區(qū)(entrysection)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)的一段代碼。退出區(qū)(exitsection)：釋放臨界資源的一段代碼剩余區(qū)(remaindersection)：代碼中的其余部分?？臻e讓進：其他進程均不處于臨界區(qū)；忙則等待：已有進程處于其臨界區(qū)；有限等待：等待進入臨界區(qū)的進程不能"死等"；讓權等待：不能進入臨界區(qū)的進程，應釋放CPU（如轉換到阻塞狀態(tài)）同步機制應遵循的準則有兩個進程P0,P1：設立一個公用整型變量turn：描述允許進入臨界區(qū)的進程標識，假設初始化turn=0，表示首先輪到P0訪問臨界資源。進程互斥的軟件方法算法1：互斥算法while(turn!=0);criticalsectionturn=1;remaindersectionP0的代碼：while(turn!=1);criticalsectionturn=0;remaindersectionP1的代碼：缺點：強制輪流進入臨界區(qū)，沒有考慮進程的實際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；違背了空閑讓進、讓權等待的原則。設立一個標志數組flag[2]：描述進程是否已在臨界區(qū)，初值均為0(FALSE)，表示進程都不在臨界區(qū)。算法2：P0:while(flag[1]);

flag[0]=1;

臨界區(qū)

flag[0]=0;P1:while(flag[0]);

flag[1]=1;

臨界區(qū)

flag[1]=0;違背了忙則等待原則；違背了讓權等待原則設立一個標志數組flag[2]：描述進程是否希望進入臨界區(qū)，初值均為0(FALSE)，表示進程都不希望進入臨界區(qū)算法3：P0:flag[0]=1;while(flag[1]);臨界區(qū)

flag[0]=0;P1:flag[1]=1;while(flag[0]);臨界區(qū)

flag[1]=0;違背了空閑讓進、有限等待、讓權等待原則設立一個標志數組flag[2]：描述進程是否希望進入臨界區(qū)，初值均為0(FALSE)，表示進程都不希望進入臨界區(qū)。intturn=0,表示首先輪到P0進入臨界區(qū)。算法4：P0:

flag[0]=1;turn=1;

while(flag[1]&&turn==1);臨界區(qū)

flag[0]=0;P1:flag[1]=1;turn=0;

while(flag[0]&&turn==0);臨界區(qū)

flag[1]=0;每一類臨界資源設置一把鎖lock。lock表示資源的兩種狀態(tài)：TRUE表示正被占用（關鎖狀態(tài)）；FALSE表示空閑（開鎖狀態(tài)）進程互斥的鎖操作方法加鎖操作開鎖操作執(zhí)行臨界區(qū)程序臨界區(qū)太長時，降低了中斷響應速度；加鎖時CPU不斷測試，處于忙等待；不能實現多處理機系統(tǒng)中同類臨界區(qū)互斥；優(yōu)點：簡單、可靠鎖操作方法用開、關中斷實現鎖操作關中斷開中斷執(zhí)行臨界區(qū)程序缺點：信號量(semaphore)

1.整型信號量最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。又分別稱為P、V操作。

wait和signal操作可描述為：

wait(S)或P(S):whileS≤0dono-op；S∶=S-1;

signal(S)或V(S):S∶=S+1;

缺點：存在“忙等”現象。信號量(semaphore)信號量數據結構：typedefstruct{intvalue;/*信號量的值*/PCB*L;/*進程阻塞隊列隊首指針*/}semaphore;

2.記錄型信號量Value:初始化為一個非負整數值，表示空閑資源總數－－若為非負值表示當前的空閑資源數，若為負值其絕對值表示當前等待臨界資源的進程個數。L：初值為空P原語wait(S){S->value--;if(S->value<0)thenBlock(S->L);}semaphore*S;V原語signal(S){S->value++;if(S->value<=0)thenWakeup(S->L);}為臨界資源設置一個互斥信號量mutex(MUTualExclusion)，其初值為1；在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間；必須成對使用P和V原語，P、V原語不能次序錯誤、重復或遺漏利用信號量實現互斥：Semaphore

mutex=1P（mutex）criticalsectionV（mutex）remaindersection信號量實現互斥模型：

semaphoremutex={1,NULL};

cobeginprogrampi{while(1){P(mutex)；

criticalsectionforpi;/*進程pi臨界區(qū)*/V(mutex)；

remaindersectionforpi;}}

coend例：民航售票系統(tǒng)，n個售票處

semaphoremutex={1,NULL};

cobeginprogrampi{………R=x[k];/*現有票數*/

if(R>=1){R--;

x[k]=R;

輸出一張機票；

}

else{顯示“票已售完”；

}}coend例：民航售票系統(tǒng)，n個售票處

semaphoremutex={1,NULL};

cobeginprogrampi{………P(mutex)；

R=x[k];/*現有票數*/

if(R>=1){R--;x[k]=R;V(mutex)；輸出一張機票；

}

else{

顯示“票已售完”；

}}coend例：民航售票系統(tǒng)，n個售票處

semaphoremutex={1,NULL};

cobeginprogrampi{………P(mutex)；

R=x[k];/*現有票數*/

if(R>=1){R--;x[k]=R;V(mutex)；輸出一張機票；

}

else{V(mutex)；

顯示“票已售完”；

}}coend設置一個同步信號量proceed1，其初值為0利用信號量實現同步

semaphoreproceed1={0,NULL};

cobegin

進程p1………P(proceed1)；

………

進程p2………V(proceed1)；

……….

coend

教材P54：圖2-12前驅圖：S1S2S3S4S5S6abcdefga,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0cobegins1:{s1;v(a);v(b);}s2:{p(a);s2;v(c);v(d);}s3:{p(b);s3;v(e);}

s4:{p(c);s4;v(f);}s5:{p(d);s5;v(g);}s6:{p(e);p(f);p(g);s6;}coend

例：一輛公共汽車上，司機和售票員進程的同步

program司機{啟動車輛;正常行車；

到站停車；}program售票員{關閉車門;售票

打開車門;}

分析：同步關系：（1）售票員關閉車門→司機啟動車輛（2）司機到站停車→售票員打開車門例：一輛公共汽車上，司機和售票員進程的同步

semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};到站停車→打開車門關閉車門→啟動車輛

program司機{啟動車輛;正常行車；

到站停車；}program售票員{關閉車門;售票

打開車門;}

例：一輛公共汽車上，司機和售票員進程的同步

semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};

cobeginprogram司機{while(1){

P(drive_sem)；

/*等待關門*/startacar;driving;/*正常行車*/stopping;V(conductor_sem)；/*喚醒開門*/}}

到站停車→打開車門關閉車門→啟動車輛

program售票員{while(1){closethedoor;V(drive_sem)；

/*喚醒司機開車*/selltickets;/*售票*/

P(conductor_sem)；

/*等待停車*/openthedoor;}}coend（1）確定進程：包括進程的數量、進程的工作內容。（2）確定進程同步互斥關系：根據進程間是競爭臨界資源還是相互合作處理上的前后關系，來確定進程間是互斥還是同步。（3）確定信號量：根據進程間的同步互斥關系確定信號量個數、含義、初始值，各進程需要對信號量進行的PV操作。（4）用類程序語言描述算法。使用信號量解決進程同步問題的步驟：

1.生產者－消費者問題(theproducer-consumerproblem)問題描述：若干進程通過有限的共享緩沖區(qū)交換數據。其中，"生產者"進程不斷寫入，而"消費者"進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。0123…4N-12.4經典進程同步問題

inout分析：確定進程：進程數量及工作內容；確定進程間的關系：

（1）互斥：多個進程間互斥使用同一個緩沖池；

（2）同步：當緩沖池空時，消費者必須阻塞等待；當緩沖池滿時，生產者必須阻塞等待。設置信號量：Mutex：用于訪問緩沖池時的互斥，初值是1Full：“滿緩沖”數目，初值為0；Empty：“空緩沖"數目，初值為N。full+empty=N

＃defineN100

＃defineMAXLEN80typedefstruct{intnum;chararray[MAXLEN];}Message;semaphoremutex={1,NULL};semaphoreempty={N,NULL};

semaphorefull={0,NULL};Messagebuffers[N];

intin=0,out=0;

算法描述：cobeginprogramproduceri{Messagep_puf;while(1){produceamessageinp_buf;P(empty)；

P(mutex)；buffers[in]=p_bufin=(in+1)%N;V(mutex)；

V(full)；}}programconsumerj{Messagec_buf;while(1){P(full)；

P(mutex)；

c_buf=buffers[out]；out=(out+1)%N;V(mutex)；

V(empty)；

consumethemessageinc_buf;}}coend如果將消費者的兩個P操作對調？生產者i

消費者j生產出一產品；

P（mutex）；P（empty

）；

P（full）；P（mutex

）

；從緩沖區(qū)取出一產品；將該產品放入緩沖區(qū)；

V（mutex）；V（mutex

）；

V（empty）；

V（full

）

；消費該產品；P（full）；P（mutex）；如果將消費者的兩個V操作對調？？生產者i

消費者j生產出一產品；

P（full）；P（empty

）；

P（mutex）；P（mutex

）

；從緩沖區(qū)取出一產品；將該產品放入緩沖區(qū)；

V（empty）；V（mutex

）；

V（mutex）；

V（full

）

；消費該產品；V（mutex）；V（empty）；2.哲學家進餐問題問題描述：

有五個哲學家坐在一張圓桌旁，在圓桌上有五個盤子也五只筷子，他們的生活方式就是交替地進行思考和進餐。平時，一個哲學家進行思考，饑餓時取其左右兩只筷子，只有拿到這兩只筷子是才能進餐；進餐完畢，放下筷子繼續(xù)思考。

semaphorechopstick[0…4]={1,NULL};cobegin

programphilosopher（i）{

P(chopstick[i])；P(chopstick[i+1]mod5);eating;V(chopstick[i])；

V(chopstick[i+1]mod5);}

coend

算法描述：

semaphorechopstick[0…4]={1,NULL};

semaphoresm={4,NULL};

cobegin

programphilosopher（i）{P(sm)；

P(chopstick[i])；P(chopstick[i+1]mod5);eating;V(chopstick[i])；

V(chopstick[i+1]mod5);

V（sm）；}

coend

算法描述：3.讀者－寫者問題(thereaders-writersproblem)問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個當有寫者在寫數據時，其他寫者和讀者必須等待；

當有讀者在讀數據時，其他寫者必須等待；但其他讀者可以同時讀數據。

3.讀者－寫者問題(thereaders-writersproblem)采用信號量機制：信號量wmutex表示“允許寫”，互斥使用數據，初值是1。公共整形變量Readcount表示“正在讀”的讀者數，初值是0；信號量Rmutex：實現多個讀者對Readcount的互斥操作，初值是1。

wmutex:semaphore=1//讀者與寫者之間、寫者與寫者之間互斥使用共享數據readcount:int=0;//當前正在讀的讀者數量

rmutex:semaphore=1//多個讀者互斥使用//readcount算法：Cobegin:

Reader:beginRepeat

wait(rmutex)ifreadcount=0thenwait(wmutex);readcount++;signal(rmutex);

reading…wait(rmutex);readcount--;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;end;writer:beginrepeat:

wait(wmutex);writing…signal(wmutex);

untilfalseend;coend;3.寫者優(yōu)先的讀者－寫者問題問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個互斥寫、讀寫互斥

寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）

共享讀

wmutex:semaphore=1//讀者與寫者之間、寫者與寫者之間互斥使用共享數據S：semaphore=1//當至少有一個寫者準備訪問共享數據時，它可使后續(xù)的讀者等待寫完成S2：semaphore＝1//阻塞第二個以后的等待讀者Readcount,writecount:int=0,0;//當前讀者數量、

寫者數量mutex1:semaphore=1//多個讀者互斥使用readcountmutex2:semaphore=1//多個寫者互斥使用writecount算法：Cobegin:Reader:beginRepeatwait(S2);

wait(S);wait(mutex1)ifreadcount=0thenwait(wmutex);readcount++;signal(mutex1);signal(S);signal(S2);

reading…wait(mutex1);readcount--;ifreadcount=0thensignal(wmutex);signal(mutex1);untilfalse;begin;writer:beginrepeat;wait(mutex2);ifwritecount=0thenwait(S);writecount++;signal（mutex2）;wait(wmutex);writing…signal(wmutex);wait(mutex2);writecount--;ifwritecount=0thensignal(S);signal（mutex2）;untilfalse;end;coend;＝》例1某小型超級市場，可容納50人同時購物。入口處有足夠的籃子，每個購物者可拿一只籃子入內購物。出口處結帳，并歸還籃子（出、入口禁止多人同時通過）。試用信號量和P、V操作寫出購物者的同步算法。這是個典型的進程互斥問題解答:①所用信號量設置如下：Ⅰ）資源信號量S，初值為50，用以保證最多可以有50個購物者同時進入超市。Ⅱ）互斥信號量mutex，初值為1，用以保證同時只能有一個購物者進程進入出入口拿起籃子或者結帳后放下籃子。②用信號量機制給出的每個購物者購物過程的算法描述如下：購物者i（解法一）購物者i（解法二）：

P（S）；

P（S）；P（mutex）；

P（mutex1）；從入口處進超市，并取一只籃子；同左；V（mutex）；

V（mutex1）；

進超市內選購商品；同左；

P（mutex）；

P（mutex2）；

到出口結帳，并歸還籃子；同左

；

V（mutex）；

V（mutex2）；

從出口離開超市；同左；

V（S）；

V（S）；↓↓結束.結束.

出入口在一起：出入口不在一起：＝》例2：桌上有個只能盛得下一個水果的空盤子。爸爸可向盤中放蘋果或桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定：當盤子空時，一次只能放入一個水果供吃者取用。試用信號量和P、V操作實現爸爸、兒子和女兒這三個循環(huán)進程之間的同步。

本題屬于生產者——消費者問題的變形，相當于一個能生產兩種產品的生產者（爸爸）向兩個消費者（兒子和女兒）提供產品的同步問題。因此，可參考生產者與消費者問題的解法。

解答：①所用信號量設置如下：Ⅰ）同步信號量empty，初值為1，表示盤子是空的，即兒子或女兒已把盤中的水果取走。

Ⅱ）同步信號量orange，初值為0，表示爸爸尚未把桔子放入盤中。Ⅲ）同步信號量apple，初值為0，表示爸爸尚未把蘋果放入盤中。

②使用信號量機制的三個進程的同步描述如下：

爸爸進程（P）：

兒子進程（C1）：

女兒進程（C2）：P（empty）；

P（orange）；

P（apple）；將水果放入盤中；

從盤中取出桔子；

從盤中取出蘋果；若放入的是桔子，

V（empty）；

V（empty）；則V（orange）；吃桔子；

吃蘋果；否則，V（apple）；1.管程的引人：2.管程的基本概念：

管程的定義：一個管程定義了一個數據結構和能為并發(fā)進程所執(zhí)行（在該數據結構上）的一組操作，這組操作能同步進程和改變管程中的數據。管程的組成：局部于管程的共享變量的說明；對該數據結構進行操作的一組過程；初始化局部變量的語句。

2.5管程機制

2.管程的基本概念：

管程的特性：模塊化；信息隱蔽性；規(guī)定進程互斥進入管程。3.條件變量：每個獨立的條件變量是和進程需要等待的某種原因（或說條件）相聯(lián)系的，當定義一個條件變量時，系統(tǒng)就建立一個相應的等待隊列。關于條件變量的兩個操作：C.wait:

阻塞調用進程，并使管程可用；C.signal:

喚醒相應條件變量上的等待進程。4.利用管程解決生產者--消費者問題：管程定義：

typePC=monitor in,out,count:int;

buffer[n]:item;

notfull,notempty:condition; procedureput(item)procedureget(item){{ifcount>=nthenifcount<=0then

notfull.wait;notempty.wait;

buffer(in)=item;nextc=buffer(out);in=(in+1)modn;out=(out+1)modn;count=count+1;count=count-1;

notempty.signal;notfull.signal;}}Beginin=out=count=0;end4.利用管程解決生產者--消費者問題：生產者和消費者的算法描述：

procedureproducerprocedureconsumer{{

while(true)while(true){{produceranitem;PC.get(item);

PC.put(item);consumetheitem;}}}}

P(PCmutex);PC.put(item);V(PCmutex);管程結構示意圖：

進程等待隊列局部數據定義條件C1隊列

條件變量

初始化語句C1.wait

過程1

過程2條件Cn隊列…

過程nCn.wait

入管程出管程C1.signalCn.signal

管程

管程等待區(qū)

2.6進程通信

低級通信：高級通信：一、進程間通信的類型：是指進程間的信息交換。效率低；通信對用戶不透明。用戶直接利用操作系統(tǒng)所提供的一組通信命令，高效地傳送大量數據的一種通信方式。二、高級通信類型1共享存儲器系統(tǒng)通信(Shared-MemorySystem)2管道(pipe)通信3消息傳遞系統(tǒng)通信(MessagepassingSystem)

1共享存儲器系統(tǒng)通信通過共享某些數據結構或共享存儲器實現進程之間的信息交換。可分成兩種類型：基于共享數據結構的通信方式：低級通信基于共享存儲區(qū)的通信方式：高級通信通信過程：linux中相應系統(tǒng)調用（1）申請共享存儲分區(qū)；shmget（）（2）將共享存儲分區(qū)映射到shmat（）本進程地址空間中；（3）進行數據讀寫；（4）釋放共享存儲分區(qū)；shmdt（）共享存儲器系統(tǒng)通信方式的特點：

最大的特點是沒有中間環(huán)節(jié)，直接把共享內存映射到不同進程的虛擬地址空間中，進程可直接進行訪問，通信直接快速。該通信機制沒有提供進程同步機制。管道：用于連接一個讀進程和一個寫進程，以實現它們之間通信的共享文件（pipe文件，又稱為FIFO文件）

無名管道：int

pipe(intfd[2]),用于父子或兄弟進程間通信有名管道：

int

mkfifo(constchar*pathname,mode_tmode)用于任意進程間通信（又稱FIFO通信）2管道（pipe）通信兩種實現機制：FIFO文件的讀出和寫入：嚴格遵循先進先出，不支持文件定位操作。管道通信應注意的問題：2.管道通信機制：無名管道的使用：舉例：Linux中利用無名管道實現進程間的通信。父進程創(chuàng)建子進程，子進程向管道中寫一條消息，而父進程從管道中讀出該信息： #include<stdio.h> #include<unistd.h> #include<signal.h> main() { intpid1,fd[2]; charbuf[50]; pipe(fd);2.管道通信機制：if((pid1=fork())<0){ printf("forkerror.\n"); exit(1);} if(pid1==0){ lockf(fd[0],1,0); write(fd[1],"Iamchild.\n",15); lockf(fd[0],0,0); exit(0);}else{ wait(0); lockf(fd[1],1,0); read(fd[0],buf,15);lockf(fd[0],0,0); printf("%s",buf); exit(0); }}3消息傳遞系統(tǒng)在消息傳遞系統(tǒng)中，進程間的數據交換是以消息(message，在計算機網絡中又稱報文)為單位。程序員直接利用系統(tǒng)提供的一組通訊命令（原語）來實現通訊。（1）消息格式：消息頭消息正文消息頭：存放消息傳輸時所需的控制信息。消息類型：定長消息；變長消息。直接通信方式（消息緩沖隊列機制）：發(fā)送進程直接將消息發(fā)送給接收進程，并將它掛在接收進程的消息緩沖隊列上。接收進程從消息緩沖隊列中取得消息。故稱為消息緩沖機制。（2）消息傳遞系統(tǒng)實現類型：發(fā)送進程發(fā)送區(qū)設置公用緩沖區(qū)復制消息接收隊列掛入取消息消息緩沖區(qū)復制接收進程接收區(qū)消息緩沖機制（直接通信）兩通信進程必須滿足下列條件：互斥：在發(fā)送進程把消息寫入緩沖區(qū)和把緩沖區(qū)掛入消息隊列時，應禁止其他進程對緩沖區(qū)消息隊列的訪問。同理，接收進程取消息時也禁止其他進程訪問緩沖區(qū)消息隊列。同步：