第2章進程管理

第二章進程管理2.1進程的基本概念2.2進程控制2.3進程同步2.4經(jīng)典進程的同步問題2.6進程通信2.7線程2.1進程的基本概念

進程是操作系統(tǒng)中最基本、最重要的概念.

為什么引入“進程”概念?程序≠進程?直接原因:多道程序系統(tǒng)出現(xiàn)

手段：程序的并發(fā)執(zhí)行若干個程序同時在系統(tǒng)中執(zhí)行，這些程序的執(zhí)行在時間上是重疊的，一個程序的執(zhí)行尚未結(jié)束，另一個程序的執(zhí)行已經(jīng)開始目的：充分利用系統(tǒng)資源

=

引入“進程”原因:描述和管理并發(fā)執(zhí)行為什么引入“進程”？程序順序執(zhí)行程序順序執(zhí)行:

#include“myhead.h”

int

main(int

argc,char*argv[]){……

while(TRUE){從終端等待讀入數(shù)據(jù)到i;根據(jù)i數(shù)據(jù)進行計算;取出計算結(jié)果并寫到磁帶上;}return0;}

特征：順序性,封閉性,可再現(xiàn)性I1C1P1I2C2P2ICP程序：指令或語句序列，體現(xiàn)了某種算法，所有程序是順序的順序環(huán)境：在計算機系統(tǒng)中只有一個程序在運行，這個程序獨占系統(tǒng)中所有資源，其執(zhí)行不受外界影響為什么引入“進程”？程序段并發(fā)執(zhí)行I1C1P1程序段并發(fā)執(zhí)行:

ICPT程序段ICP

#include“myhead.h”

int

main(int

argc,char*argv[]){……

while(TRUE){從終端等待讀入數(shù)據(jù)到i;根據(jù)i數(shù)據(jù)進行計算;取出計算結(jié)果并寫到磁帶上;}return0;}

I2C2P2I3C3P3間斷性失去封閉性不可再現(xiàn)性可再現(xiàn)性并發(fā)性某種封閉？進程

較典型的進程定義有：(1)進程是程序的一次執(zhí)行。(2)進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。(3)進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。在引入了進程實體的概念后，我們可以把傳統(tǒng)OS中的進程定義為：“進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位”。進程特征結(jié)構(gòu)特征：由程序段、數(shù)據(jù)段、進程控制塊三部分組成動態(tài)性：進程是程序的執(zhí)行并發(fā)性：多個進程可同存于內(nèi)存中，能在一段時間內(nèi)同時運行獨立性：獨立運行的基本單位，獨立獲得資源和調(diào)度的基本單位。異步性：各進程按各自獨立的不可預(yù)知的速度向前推進進程同程序的比較？程序是指令的有序集合，其本身沒有任何運行的含義，是一個靜態(tài)的概念。而進程是程序在處理機上的一次執(zhí)行過程，它是一個動態(tài)的概念。程序可以作為一種軟件資料長期存在，而進程是有一定生命期的。程序是永久的，進程是暫時的。進程更能真實地描述并發(fā)，而程序不能進程具有創(chuàng)建其他進程的功能，而程序沒有同一程序同時運行于若干個數(shù)據(jù)集合上，它將屬于若干個不同的進程。也就是說同一程序可以對應(yīng)多個進程

進程的分類：系統(tǒng)進程用戶進程（系統(tǒng)進程優(yōu)先于用戶進程）進程結(jié)構(gòu)進程實體=

程序段+相關(guān)數(shù)據(jù)段+PCB(進程控制塊)進程:是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位進程映象(進程結(jié)構(gòu))用戶程序段用戶數(shù)據(jù)段進程控制塊PCB(執(zhí)行上下文)控制進程所需的數(shù)據(jù)(進程屬性)，包括:進程標識符信息（內(nèi)、外、用戶等）處理器狀態(tài)信息（寄存器、PC、PSW、堆棧指針等）進程調(diào)度信息（狀態(tài)、優(yōu)先級、事件、其它信息）進程控制信息（程序/數(shù)據(jù)外存地址、資源清單、PCB鏈接指針、同步與通信機制等）進程控制塊（ProcessControlBlock）作用：是使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù))，成為一個能獨立運行的基本單位，一個能與其它進程并發(fā)執(zhí)行的進程。概念:系統(tǒng)為了管理進程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進程的外部特征，描述進程的運動變化過程OS利用PCB來控制和管理進程。PCB是系統(tǒng)感知進程存在的唯一標志。進程與PCB是一一對應(yīng)的。進程控制塊中的信息進程標識符系統(tǒng)給每個進程定義了一個標識該進程的非負整數(shù)，稱作進程標識符。當某一進程終止后，其標識符可以重新用作另一進程的標識符。不過，一個標識符所代表的進程在任何時刻都是惟一的。處理機狀態(tài)處理機的各種寄存器中的內(nèi)容。以便于進程從斷點繼續(xù)執(zhí)行。①通用寄存器②指令計數(shù)器③程序狀態(tài)字PSW④用戶棧指針進程控制塊中的信息進程調(diào)度信息與進程調(diào)度和進程對換有關(guān)，包括：①進程狀態(tài)，②進程優(yōu)先級，③所需的其它信息，④事件，即阻塞原因。

進程控制信息①程序和數(shù)據(jù)的地址②進程同步和通信機制③資源清單④鏈接指針進程控制塊中的信息進程標識符內(nèi)部標識符。OS為每個進程賦予惟一的數(shù)字標識符,系統(tǒng)使用。外部標識符。由創(chuàng)建者提供，由用戶(進程)在訪問該進程時使用。處理機狀態(tài)處理機的各種寄存器中的內(nèi)容。以便于進程從斷點繼續(xù)執(zhí)行。①通用寄存器②指令計數(shù)器③程序狀態(tài)字PSW④用戶棧指針進程調(diào)度信息與進程調(diào)度和進程對換有關(guān)，包括：①進程狀態(tài)，②進程優(yōu)先級，③所需的其它信息，④事件，即阻塞原因。進程控制信息①程序和數(shù)據(jù)的地址②進程同步和通信機制③資源清單④鏈接指針進程控制塊的組織方式

PCB表：系統(tǒng)把所有PCB組織在一起，并把它們放在內(nèi)存的固定區(qū)域，就構(gòu)成了PCB表

PCB表的大小決定了系統(tǒng)中最多可同時存在的進程個數(shù)，稱為系統(tǒng)的并發(fā)度（注：多道程序中的多道與系統(tǒng)并發(fā)度不同）

PCB怎么組織在一起的？PCB表的數(shù)據(jù)結(jié)構(gòu)？進程控制塊的組織方式1)鏈接方式

1、相同狀態(tài)的進程PCB組成一個鏈表，不同狀態(tài)對應(yīng)多個不同的鏈表2、就緒鏈表、阻塞鏈表進程控制塊的組織方式2)索引方式對具有相同狀態(tài)的進程，分別設(shè)置各自的PCB索引表，表明PCB在PCB表中的地址回顧為什么引入“進程”概念?進程的特征、定義進程控制塊的作用、包括的信息、組織形式目的：“進程”概念進程的狀態(tài)及轉(zhuǎn)換進程有三種基本狀態(tài)（不同系統(tǒng)設(shè)置的進程狀態(tài)數(shù)目不同）。就緒狀態(tài)(Ready)運行狀態(tài)（Running）阻塞狀態(tài)（Wait/Blocked）執(zhí)行態(tài)（Running）： 進程占有CPU，并在CPU上執(zhí)行就緒態(tài)（Ready）：

一個進程已經(jīng)具備執(zhí)行條件，但由于無CPU暫時不能執(zhí)行的狀態(tài)（當調(diào)度給其CPU時，立即可以執(zhí)行）阻塞態(tài)（Blocked）：等待態(tài)、掛起態(tài)、封鎖態(tài)凍結(jié)態(tài)、睡眠態(tài)

指進程因等待某種事件的發(fā)生而暫時不能執(zhí)行的狀態(tài)（即使CPU空閑，該進程也不可執(zhí)行）執(zhí)行就緒阻塞進程的狀態(tài)及其轉(zhuǎn)換

進程狀態(tài)轉(zhuǎn)換：在進程執(zhí)行過程中，由于進程自身進展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換

就緒—執(zhí)行

執(zhí)行—就緒

執(zhí)行—阻塞

阻塞—就緒進程轉(zhuǎn)換就緒-->執(zhí)行調(diào)度程序選擇一個新的進程執(zhí)行執(zhí)行-->就緒執(zhí)行進程用完了時間片執(zhí)行進程被中斷，因為一高優(yōu)先級進程處于就緒狀態(tài)進程轉(zhuǎn)換（續(xù)1）執(zhí)行-->阻塞當一進程必須等待時OS尚未完成服務(wù)對一資源的訪問尚不能進行初始化I/O且必須等待結(jié)果等待某一進程提供輸入(IPC)阻塞-->就緒當所等待的事件發(fā)生時其他狀態(tài)：新狀態(tài)，終止狀態(tài)掛起狀態(tài)，將就緒/阻塞分活動，靜止（調(diào)節(jié)負載，對換，父進程，操作系統(tǒng)，終端用戶）新建狀態(tài)OS已完成為創(chuàng)建一進程所必要的工作已構(gòu)造了進程標識符已創(chuàng)建了管理進程所需的表格但還沒有允許成為就緒進程(尚未同意)因為資源有限終止狀態(tài)終止后進程移入該狀態(tài)它不再有執(zhí)行資格表格和其它信息暫時由輔助程序保留五狀態(tài)進程模型七狀態(tài)進程模型活動掛起事件發(fā)生事件發(fā)生等待事件掛起調(diào)度超時釋放活動掛起新狀態(tài)轉(zhuǎn)換(中期調(diào)度)活動阻塞-->靜止阻塞（掛起）當所有進程都阻塞，OS會安排空間讓一就緒進程進入內(nèi)存靜止阻塞-->靜止就緒（釋放）當?shù)却氖录l(fā)生時(狀態(tài)信息已在OS中)靜止就緒-->活動就緒（激活）當內(nèi)存中沒有就緒進程時活動就緒-->靜止就緒(掛起，較少見）當沒有被阻塞的進程，而為了性能上的考慮，必須釋放一些內(nèi)存時圖2-6具有掛起狀態(tài)的進程狀態(tài)圖某進程在運行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時該進程的狀態(tài)將（）。A、從就緒變?yōu)檫\行B、從運行變?yōu)榫途wC、從運行變?yōu)樽枞鸇、從阻塞變?yōu)榫途w有沒有以下這些狀態(tài)轉(zhuǎn)換，為什么？1)等待—運行；2)就緒—等待如果系統(tǒng)中有N個進程，執(zhí)行的進程最多幾個，最少幾個；就緒進程最多幾個最少幾個；阻塞進程最多幾個，最少幾個？2.2進程控制

進程控制就是對系統(tǒng)中的所有進程實施管理，創(chuàng)建、撤消進程以及完成進程各狀態(tài)之間的轉(zhuǎn)換。進程控制一般由原語來實現(xiàn)。

原語

primitiveor

atomicaction定義：是一種特殊的系統(tǒng)功能調(diào)用，它可以完成一個特定的功能，其特點是原語執(zhí)行時不可被中斷。特點：原子操作，不可分割，要么全做，要么全不做。由若干多機器指令構(gòu)成的完成某種特定功能的一段程序，它的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷。常用的進程控制原語

創(chuàng)建原語終止原語阻塞原語、喚醒原語

fork，execexitwait系統(tǒng)調(diào)用？進程樹？進程樹父子進程：繼承資源；歸還資源。進程樹在UNIX系統(tǒng)中，只有0進程是在系統(tǒng)引導(dǎo)時被創(chuàng)建的。在系統(tǒng)初啟時由0進程利用fork()創(chuàng)建1進程，以后0進程變成對換進程，1進程成為系統(tǒng)中的始祖進程。系統(tǒng)中除0進程外的所有進程都是用fork()創(chuàng)建的。

進程創(chuàng)建-原因系統(tǒng)內(nèi)核需要:用戶登錄,作業(yè)調(diào)度,提供服務(wù)用戶應(yīng)用請求:進程自己要求創(chuàng)建，如父進程創(chuàng)建子進程，創(chuàng)建輸入進程、處理進程、輸出進程并發(fā)執(zhí)行，以加速任務(wù)完成。進程創(chuàng)建-過程申請空白PCB，賦予一個進程內(nèi)部標識符為新進程分配資源如內(nèi)存初始化進程控制塊將新進程插入就緒隊列

思考為什么創(chuàng)建進程要用原語來實現(xiàn)？fork()：創(chuàng)建一個新進程的函數(shù)參數(shù)定義：intfork()系統(tǒng)調(diào)用格式：pid=fork()fork()返回值：0，>0，-1

用戶使用系統(tǒng)調(diào)用fork創(chuàng)建一個進程。核心為完成系統(tǒng)調(diào)用fork要進行幾步操作。（1）分配新的內(nèi)存塊和內(nèi)核數(shù)據(jù)結(jié)構(gòu)（2）復(fù)制原來的進程到新的進程（3）向運行進程集添加新的進程（4）將控制返回給兩個進程PC…..pid=fork();if(pid==0)

執(zhí)行子進程代碼；elseif(pid>0)

執(zhí)行父進程代碼；else

創(chuàng)建失敗處理；

fork()調(diào)用前父進程PC…..pid=fork();if(pid==0)

執(zhí)行子進程代碼；elseif(pid>0)

執(zhí)行父進程代碼；else

創(chuàng)建失敗處理；其它代碼；PC…..pid=fork();if(pid==0)

執(zhí)行子進程代碼；elseif(pid>0)

執(zhí)行父進程代碼；else

創(chuàng)建失敗處理；其它代碼；fork()調(diào)用后父進程子進程程序fork函數(shù)實例#include<stdio.h>#include<unistd.h>main(){

pid_t

pid;

printf(“nowonlyoneprocess\n”);

printf(“callingfork…\n”);

pid=fork();

if(!pid)

printf(“Iamachild\n”); elseif(pid>0)

printf(“I’mtheparent,childhaspid%d\n”,pid); else

printf(“Forkfail!\n”);}進程運行

exec函數(shù)把一個新程序裝入調(diào)用進程的內(nèi)存空間，來改變調(diào)用進程的執(zhí)行代碼，從而形成新進程。如果exec調(diào)用成功，調(diào)用進程將被覆蓋，然后從新程序的入口開始執(zhí)行，這樣就產(chǎn)生了一個新的進程，但是它的進程標識符與調(diào)用進程相同。

這就是說，exec并沒有建立一個與調(diào)用進程并發(fā)的新進程，而是用新進程取代了原來的進程。所以，在exec調(diào)用成功后，沒有任何數(shù)據(jù)返回，這和fork是不一樣的。它有六種調(diào)用的形式，隨著系統(tǒng)的不同并不完全相同。#include<unistd.h>int

execl(constchar*pathname,constchar*arg0,.../*(char*)0*/);int

execv(constchar*pathname,char*constargv

[]);int

execle(constchar*pathname,constchar*arg0,.../*(char*)0,char*constenvp[]*/);int

execve(constchar*pathname,char*constargv

[],char*constenvp

[]);int

execlp(constchar*filename,constchar*arg0,.../*(char*)0*/);int

execvp(constchar*filename,char*constargv

[]);六個函數(shù)返回：若出錯則為-1，若成功則不返回1.將指定的程序復(fù)制到調(diào)用它的進程2.將指定的字符串數(shù)組作為參數(shù)傳遞給這個程序3.運行這個程序。一個程序中運行另一個程序#include<unistd.h>#include<stdio.h>main(){ char*arglist[3]; arglist[0]=“l(fā)s”; arglist[1]=“-l”; arglist[2]=NULL;

execvp(“l(fā)s”,arglist);}#include<unistd.h>#include<stdio.h>main(){

execl(“l(fā)s”,”ls”,”-l”,NULL);}

系統(tǒng)調(diào)用exec和fork時經(jīng)常結(jié)合使用，父進程fork一個子進程，在子進程中調(diào)用exec來替換子進程的執(zhí)行圖像，并發(fā)地執(zhí)行一些操作。進程終止-原因

正常結(jié)束，異常結(jié)束，外界干預(yù)進程終止-過程？進程終止-過程根據(jù)被終止進程的標識符，從PCB集合中檢索出該進程的PCB將進程所擁有的資源交給父進程或系統(tǒng)進程釋放PCB

進程可使用系統(tǒng)調(diào)用exit()終止自己除了使用exit函數(shù)來終止進程外，當進程運行完程序到達main()函數(shù)末時，進程會自動終止。當進程在main()函數(shù)內(nèi)執(zhí)行return語句時，它也會終止。進程的阻塞與喚醒阻塞：當一個進程所期待的某一事件尚未出現(xiàn)時，該進程調(diào)用阻塞原語將自己阻塞。進程阻塞是進程的自身的一種主動行為。喚醒：處于阻塞狀態(tài)的進程是絕不可能叫醒它自己的，它必須由它的合作進程或系統(tǒng)進程用喚醒原語喚醒它。

阻塞與喚醒為一對作用相反的操作。進程阻塞

自己阻塞自己。處于運行狀態(tài)的進程，在其運行過程中期待某一事件發(fā)生，如等待鍵盤輸入、等待磁盤數(shù)據(jù)傳輸完成、等待其它進程發(fā)送消息，當被等待的事件未發(fā)生時，由進程自己執(zhí)行阻塞原語，使自己由運行態(tài)變?yōu)樽枞麘B(tài)。

進程喚醒

被阻塞進程所期待的事件發(fā)生，或數(shù)據(jù)已到達，則該進程應(yīng)被喚醒。喚醒進程為：由事件發(fā)生進程喚醒被阻塞進程或由系統(tǒng)進程喚醒阻塞與喚醒為一對作用相反的操作。思考請設(shè)想一下進程在什么情況下會變?yōu)樽枞麪顟B(tài)？阻塞進程在什么情況下會被喚醒？誰來喚醒它？wait函數(shù)是實現(xiàn)進程同步的簡單手段。調(diào)用wait的進程進入睡眠狀態(tài)直到它的一個子進程退出時或收到一個不能被忽略的信號時被喚醒。如果調(diào)用發(fā)出時，已經(jīng)有退出的子進程(這時子進程的狀態(tài)是僵死狀態(tài))，該調(diào)用立即返回。wait()函數(shù)#include<sys/types.h>#include<sys/wait.h>pid_t

wait(int*statloc);函數(shù)返回：若成功則為進程ID，若出錯則為-12.3進程同步直接的相互制約(資源共享)和間接的相互制約(進程間合作)

同步和互斥并發(fā)控制的內(nèi)容競爭共享某些資源----進程互斥協(xié)作完成任務(wù)----進程同步通過通信進行協(xié)作----進程通信進程的同步（直接作用）進程的同步：synchronism

指系統(tǒng)中多個進程中發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項任務(wù)。具體說，一個進程運行到某一點時要求另一伙伴進程為它提供消息，在未獲得消息之前，該進程處于等待狀態(tài)，獲得消息后被喚醒進入就緒態(tài)

由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這些資源，進程的這種關(guān)系為進程的互斥

進程的互斥（間接作用）mutualexclusion

臨界資源

criticalresource：一次僅允許一個進程訪問的資源。進程ＡＢ共享一臺打印機，若讓它們交替使用？臨界資源可以是軟件資源嗎？生產(chǎn)者-消費者01234n-1inoutintn,in=out=0,counter=0;itembuffer[n];空：in=out滿:(in+1)modn=out生產(chǎn)者producer:doproduceanitem;whilecounter=ndono-op;

buffer[in]=nextp;in=(in+1)modn;

counter++;while(1);消費者consumer:dowhilecounter=0dono-op;

nextc=buffer[out];out=(out+1)modn;

counter--;consumeanitem;while(1)變量counter就是臨界資源.假設(shè)counter=5.counter++;register1=counter;register1=register1+1;counter=register1;counter--;register2=counter;register2=register-1;counter=register2;結(jié)果：counter=5假設(shè)counter=5.

register1∶=counter;(register1=5)register1∶=register1+1;(register1=6)register2∶=counter;(register2=5)register2∶=register2-1;(register2=4)counter∶=register1;(counter=6)counter∶=register2;(counter=4)

結(jié)果：counter≠5,發(fā)生錯誤。臨界區(qū)criticalsection：在每個程序中，訪問臨界資源的那段程序。

若能保證每個進程互斥地進入自己的臨界區(qū)==就可實現(xiàn)進程對臨界資源的互斥訪問。怎樣保證并發(fā)進程對臨界資源的互斥訪問？解決互斥訪問?

一個進程訪問臨界資源的程序段：…….

criticalsection;

remaindersection;…………….

exitsectionentrysection資源可用嗎？等/占釋放資源解決互斥的準則

空閑讓進：當無進程在互斥區(qū)時，任何有權(quán)使用互斥區(qū)的進程可進入忙則等待：不允許兩個以上的進程同時進入互斥區(qū)有限等待：任何進入互斥區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足

讓權(quán)等待：處于阻塞狀態(tài)的進程應(yīng)放棄占用CPU，以使其他進程有機會得到CPU的使用權(quán)信號量機制整型信號量記錄型信號量AND型信號量信號量集資源數(shù)量+1釋放Signal-V資源可用？Y資源數(shù)量-1等待N占用Wait-P原子操作應(yīng)用環(huán)境

一個進程訪問臨界資源的程序段：…….

criticalsection;

remaindersection;…………….

Signal(S)Wait(S)資源可用嗎？等/占釋放資源用P、V操作解決進程間互斥問題P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)整型信號量

wait(S):whileS≤0dono-opS∶=S-1;

signal(S):S∶=S+1;忙等記錄型信號量引入信號量數(shù)據(jù)結(jié)構(gòu),定義如下：

struct

semaphore{

intvalue;

Lqueue;}信號量說明：

semaphores;記錄型信號量wait(S)

{

s.value=s.value-1;if(s.value<0){block(S,L)； }}

signal(S){

s.value=s.value+1;if(s.value<=0){wakeup(S,L);}}

將該進程狀態(tài)置為等待狀態(tài)；將該進程的PCB插入相應(yīng)的等待隊列末尾s.queue;喚醒相應(yīng)等待隊列s.queue中等待的一個進程；改變其狀態(tài)為就緒態(tài)；并將其插入就緒隊列該機制遵循了“讓權(quán)等待”準則記錄型信號量

S.value＜0時，|S.value|表示在該信號量鏈表中已阻塞進程的數(shù)目;

S.value≥0時，S.value表示可用的資源的數(shù)目

signal(S)后，S.value==0，有什么含義？

思考：對于兩個并發(fā)進程，互斥信號量s.value的取值范圍是什么，有什么含義？N個并發(fā)進程呢？信號量互斥信號量：申請或釋放資源使用權(quán)資源信號量：申請或歸還資源，表示系統(tǒng)中某類資源的可用個數(shù)信號量的使用：

必須置一次且只能置一次初值初值不能為負數(shù)

只能執(zhí)行P、V操作信號量的應(yīng)用利用信號量實現(xiàn)進程互斥

利用信號量實現(xiàn)前趨關(guān)系利用信號量實現(xiàn)前趨關(guān)系

利用了wait(s),signal(s)原子地、相反操作特點beginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;…..進程互斥互斥信號量mutex這里的臨界資源是什么？經(jīng)典的生產(chǎn)者─消費者問題臨界資源：n個緩沖區(qū)，互斥信號量mutex表使用權(quán)生產(chǎn)者進程不能往“滿”的緩沖區(qū)中放產(chǎn)品，信號量full表“滿”的數(shù)量消費者進程不能從“空”的緩沖區(qū)中取產(chǎn)品，信號量empty表“空”的數(shù)量數(shù)據(jù)結(jié)構(gòu)

semaphoremutex=1,empty=n,full=0;

item[n]buffer;

intin=0,out=0;生產(chǎn)者

{doproduceraniteminnextp;

P(empty);

P(mutex);

buffer(in)=nextp;in=(in+1)modn

V(mutex);

V(full);while(1);}消費者{do

P(full);

P(mutex);

nextp=buffer(out);out=(out+1)modn

V(mutex);

V(empty);consumetheitem;while(1);}P.V操作討論1、信號量的物理含義：P(S):表示申請一個資源V(S)表示釋放一個資源。

信號量的初值應(yīng)該大于等于0。S>0表示有S個資源可用S=0表示無資源可用S<0則|S|表示S等待隊列中的進程個數(shù)2、P.V操作必須成對出現(xiàn)當為互斥操作時，它們同處于同一進程；當為同步操作時，則不在同一進程中出現(xiàn)；如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要,一個同步P操作與一個互斥P操作在一起時，同步P操作在互斥P操作前，而兩個V操作無關(guān)緊要3、P.V操作的優(yōu)缺點優(yōu)點：簡單，而且表達能力強（用P.V操作可解決任何同步互斥問題）缺點：不夠安全；P.V操作使用不當會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜2.4.2哲學家進餐問題

1.利用記錄型信號量解決哲學家進餐問題經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時間內(nèi)只允許一位哲學家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構(gòu)成信號量數(shù)組。其描述如下：

Varchopstick:array［0,…,4］ofsemaphore;所有信號量均被初始化為1，第i位哲學家的活動可描述為：

repeat wait(chopstick［i］); wait(chopstick［(i+1)mod5］); … eat;… signal(chopstick［i］); signal(chopstick［(i+1)mod5］); … think;untilfalse;可采取以下幾種解決方法：(1)至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。(2)僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。(3)規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學家則相反。按此規(guī)定，將是1、2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即五位哲學家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學家能獲得兩只筷子而進餐。2.4.3讀者-寫者問題1.利用記錄型信號量解決讀者-寫者問題

為實現(xiàn)Reader與Writer進程間在讀或?qū)憰r的互斥而設(shè)置了一個互斥信號量Wmutex。另外，再設(shè)置一個整型變量Readcount表示正在讀的進程數(shù)目。由于只要有一個Reader進程在讀，便不允許Writer進程去寫。因此，僅當Readcount=0,表示尚無Reader進程在讀時，Reader進程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當Reader進程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行signal(Wmutex)操作，以便讓Writer進程寫。又因為Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個互斥信號量rmutex。讀者-寫者問題可描述如下：Var

rmutex,wmutex:semaphore∶=1,1;

Readcount:integer∶=0;begin

parbegin

Reader:beginrepeat

wait(rmutex);ifreadcount=0thenwait(wmutex);

Readcount∶=Readcount+1;

signal(rmutex);…performreadoperation;…

wait(rmutex);

readcount∶=readcount-1;ifreadcount=0thensignal(wmutex);

signal(rmutex);untilfalse;endwriter:beginrepeat

wait(wmutex);performwriteoperation;

signal(wmutex);untilfalse;end

parend

end2.5進程的同步機制──管程管程的提出采用PV同步機制來編寫并發(fā)程序，對于共享變量及信號量變量的操作將被分散于各個進程中缺點：（１）易讀性差，因為要了解對于一組共享變量及信號量的操作是否正確，則必須通讀整個系統(tǒng)或者并發(fā)程序（２）不利于修改和維護，因為程序的局部性很差，所以任一組變量或一段代碼的修改都可能影響全局（３）正確性難以保證，因為操作系統(tǒng)或并發(fā)程序通常很大，要保證這樣一個復(fù)雜的系統(tǒng)沒有邏輯錯誤是很難的管程：一種同步機制管程定義:指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組過程或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作系統(tǒng)按資源管理的觀點分解成若干模塊，用數(shù)據(jù)表示抽象系統(tǒng)資源，同時分析了共享資源和專用資源在管理上的差別，按不同的管理方式定義模塊的類型和結(jié)構(gòu)，使同步操作相對集中，從而增加了模塊的相對獨立性管程的四個組成部分：管程的名稱局部于管程內(nèi)的共享數(shù)據(jù)結(jié)構(gòu)說明對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程/函數(shù)初始化語句管程的形式TYPEmonitor_name=MONITOR;共享變量說明

define本管程內(nèi)所定義、本管程外可調(diào)用的過程（函數(shù)）名字表

use本管程外所定義、本管程內(nèi)將調(diào)用的過程（函數(shù)）名字表PROCEDURE過程名（形參表）；過程局部變量說明；BEGIN

語句序列；END;......FUNCTION函數(shù)名（形參表）：值類型； 函數(shù)局部變量說明；

BEGIN

語句序列；

END;......BEGIN

共享變量初始化語句序列；END;共享數(shù)據(jù)一組操作過程/函數(shù)

…………初始化代碼條件隊列進入其它隊列

管程的三個主要的特性：（一）模塊化，一個管程是一個基本程序單位，可以單獨編譯（二）抽象數(shù)據(jù)類型，管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進行操作的代碼（三）信息掩蔽，管程是半透明的，管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的

管程有如下幾個要素：（一）管程中的共享變量在管程外部是不可見的，外部只能通過調(diào)用管程中所說明的外部過程（函數(shù)）來間接地訪問管程中的共享變量（二）為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進入（三）管程通常是用來管理資源的，因而在管程中應(yīng)當設(shè)有進程等待隊以及相應(yīng)的等待及喚醒操作管程和進程的異同點：（1）設(shè)置進程和管程的目的不同（2）系統(tǒng)管理數(shù)據(jù)結(jié)構(gòu)進程：PCB

管程：等待隊列（3）管程被進程調(diào)用（4）管程是操作系統(tǒng)的固有成分，無創(chuàng)建和撤消2.6進程通信

P.V操作實現(xiàn)的是進程之間的低級通訊，所以P.V為低級通訊原語。它只能傳遞簡單的信號，不能傳遞交換大量信息，效率低 如果要在進程間傳遞大量信息則要用Send/Receive原語（高級通訊原語）2.6.1概述進程通信的方式共享存儲器系統(tǒng)消息傳遞系統(tǒng)管道通信系統(tǒng)進程通信的方式共享存儲器：1、共享數(shù)據(jù)結(jié)構(gòu)如有界緩沖區(qū)，低效，適合于少量信息2、共享存儲區(qū)相互通信的進程間設(shè)有公共內(nèi)存，一組進程向該公共內(nèi)存中寫，另一組進程從公共內(nèi)存中讀，通過這種方式實現(xiàn)兩組進程間的信息交換消息傳遞：系統(tǒng)為進程提供了兩個高級通訊原語send和receivesend：

當要進行消息傳遞時執(zhí)行sendreceive：

當接收者要接收消息時執(zhí)行receive

按實現(xiàn)方式的不同，分為直接通信與間接通信。直接指將消息發(fā)送后，掛到接收進程的消息緩沖隊列上，而間接則通過中間實體—信箱。共享文件模式：

管道通信，即pipe文件。寫進程往里寫數(shù)據(jù)，以字符流形式大量傳送。讀進程從管道中接收數(shù)據(jù)。管道—臨界資源，利用管程來管理。管道通信必須提供以下幾方面的能力：1、互斥2、同步3、對方是否存在。管

道

簡單地說，管道就是連接一個程序的輸出和另一個程序的輸入的單向通道。

#ls–l|more這里建立了這樣的一個管道：獲取ls-l的輸出，再將它作為more命令的輸入。形象地說，就是數(shù)據(jù)沿著管道從左邊流到了右邊。

當進程創(chuàng)建一個管道的時候，系統(tǒng)內(nèi)核同時為該進程設(shè)立了一對文件句柄(一個流)，一個用來從該管道獲取數(shù)據(jù)(read)，另一個則用作管道的輸出(write)。

#include<unistd.h>int

pipe(int

filedes[2]);返回：若成功則為0，若出錯則為-1用C建立和使用管道

1.pipe函數(shù)

pipe函數(shù)用來建立管道。管道操作的情況主要有下面三種：(1)讀管道：讀操作按數(shù)據(jù)到達的順序讀取數(shù)據(jù)。(2)寫管道：寫入管道的數(shù)據(jù)按到達次序排列。

(3)管道的關(guān)閉：如果管道的讀端口關(guān)閉，那么在該管道上的發(fā)出寫操作調(diào)用的進程將接收到一個SIGPIPE信號。關(guān)閉寫端口是給讀端口一個文件結(jié)束符的惟一方法。對于寫端口關(guān)閉后，在該管道上的read調(diào)用將返回0。單個進程中的管道幾乎沒有任何用處。通常，調(diào)用pipe的進程接著調(diào)用fork，這樣就創(chuàng)建了從父進程到子進程或反之的IPC通道。fork之后做什么取決于我們想要有的數(shù)據(jù)流的方向。對于從父進程到子進程的管道，父進程關(guān)閉管道的讀端（fd[0]），子進程則關(guān)閉寫端（fd[1]）。對于從子進程到父進程的管道，父進程關(guān)閉fd[1]，子進程關(guān)閉fd[0]。當管道的一端被關(guān)閉后，下列規(guī)則起作用：當讀一個寫端已被關(guān)閉的管道時，在所有數(shù)據(jù)都被讀取后，read返回0，以指示達到了文件結(jié)束處。如果寫一個讀端已被關(guān)閉的管道，則產(chǎn)生信號SIGPIPE。例#include "ourhdr.h"

intmain(void){ int n,fd[2];

pid_t

pid; char line[MAXLINE];

if(pipe(fd)<0) err_sys("pipeerror");

if((pid=fork())<0) err_sys("forkerror");elseif(pid>0){ /*parent*/ close(fd[0]); write(fd[1],"helloworld\n",12);

}else{ /*child*/ close(fd[1]); n=read(fd[0],line,MAXLINE); write(STDOUT_FILENO,line,n); }

exit(0);}消息傳遞模式消息緩沖在內(nèi)存中開設(shè)緩沖區(qū)，發(fā)送進程將消息送入緩沖區(qū)，接收進程接收傳遞來的緩沖區(qū)信箱通信直接方式：發(fā)送進程發(fā)消息時要指定接收進程的名字，反過來，接收時要指明發(fā)送進程的名字

Send(receiver,message)

Receiver(sender,message)間接方式：發(fā)送進程發(fā)消息時不指定接收進程的名字，而是指定一個中間媒介，即信箱。進程間通過信箱實現(xiàn)通信

發(fā)送原語：send(MB,Message)

接收原語：receive(MB,Message)消息緩沖隊列通信機制發(fā)送進程：申請消息緩沖區(qū)初始化消息緩沖區(qū)插入到接受進程消息緩沖隊列接收進程：從消息隊列摘下消息緩沖區(qū)取出消息歸還資源消息緩沖區(qū)結(jié)構(gòu)：

typemessagebuffer=record sender;發(fā)送者進程標識符

size;消息長度text;消息正文

next;指向下一個消息緩沖區(qū)的指針

end

proceduresend(receiver,a)begin

getbuf(a.size,i);根據(jù)a.size申請緩沖區(qū)；

i.sender∶=a.sender;將發(fā)送區(qū)a中的信息復(fù)制到消息緩沖區(qū)之中；

i.size∶=a.size;

i.text∶=a.text;

i.next∶=0;

getid(PCBset,receiver.j);獲得接收進程內(nèi)部標識符；

wait(j.mutex);

insert(j.mq,i);將消息緩沖區(qū)插入消息隊列；

signal(j.mutex);

signal(j.sm);end3.接收原語接收原語描述如下：procedurereceive(b)beginj∶=internalname;j為接收進程內(nèi)部的標識符；

wait(j.sm);

wait(j.mutex);

remove(j.mq,i);將消息隊列中第一個消息移出；

signal(j.mutex);

b.sender∶=i.sender;將消息緩沖區(qū)i中的信息復(fù)制到接收區(qū)b;

b.size∶=i.size;

b.text∶=i.text;endLinux中通信消息隊列、信號量、共享內(nèi)存，統(tǒng)稱為IPCIPC對象在內(nèi)核中使用標識符，在程序中通過關(guān)鍵字引用構(gòu)造關(guān)鍵字ftok();#include<sys/types.h>#include<sys/ipc.h>key_t

ftok(char*pathname,char

proj);例：key_t

mykey;mykey=ftok(".",’a’);共享內(nèi)存（Linux）1、shmget()：創(chuàng)建、獲得一個共享存儲區(qū)。系統(tǒng)調(diào)用格式：shmid=shmget(key,size,flag)其中，key是共享存儲區(qū)的名字；size是其大小（以字節(jié)計）；flag是用戶設(shè)置的標志，如IPC_