操作系统原理进程管理课件

第二章

进程管理进程的概念进程的控制进程同步及经典同步问题进程间的高级通信进程与线程的区别2023/7/25

02:03操作系统|进程管理

22.1 前趋图和程序执行前趋图的定义前趋图（ProcedenceGraph）是一个有向无循环图DAG（DirectedAcyclicGraph）。结点：语句、程序段或进程。初始节点终止节点边：执行顺序。重量：程序量或执行时间。2023/7/25

02:03操作系统|进程管理

31234567例：有7个结点的前趋图。P={P1，P2，P3，P4，P5，P6，P7}→={（P1，P2），（P1，P3），（P1，P4），（P2，P5），（P3，P5），（P4，P6），（P5，P7），（P6，P7）}2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

4程序的顺序执行一个复杂的程序通常可以分为若干程序段，并且必须按照某种先后次序来执行。例1：输入——计算——打印例2：语句执行顺序S1：a：=x+yS2：b：=a–5S3：c：=b+12.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

5顺序执行程序的特点：程序的顺序性。程序在运行时独占主机资源。程序的执行结果与其执行速度无关。程序执行时的初始条件相同，其结果必相同。2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

6程序的并发执行程序执行环境独立性，逻辑上是独立的。随机性：输入和执行开始时间都是随机的。资源共享：资源共享导致对进程执行速度的制约。2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

7程序的并发执行并发执行是指两个程序执行时间上是重叠的。凡是能由一组并发程序完成的任务，都能由相应的单个程序完成。例1：有一批程序，而每个程序需输入，计算，打印三项操作。其程序段并发执行的前趋图:I1→I2→I3→I4→ ↘↘↘↘ C1→C2→C3→C4→ ↘↘↘↘ P1→P2→P3→P4→2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

8

例2．BeginintegerN:=0; Cobegin ProgramA:begin ProgramB:begin

L1:N:=N+1; L2:Print(N);N:=0; GotoL1； GotoL2；

End End Coend End当N=5时，如果N=N+1在print（N）和N:=0

前 中间 后打印 6 5 5执行后N= 0 0 12.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

9例3．设有堆栈S，栈指针top，栈中存放相应的数据块地址，程序popaddr（top）从栈中取地址，pushaddr（blk）将地址放入栈S中。voidpopaddr(top) {voidpushaddr(blk){

top--;

*top=blk; r=*top; top++; return(r)} }先执行popaddr的top--，接着执行pushaddr的*top=blk2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

10程序并发执行过程及条件（Bernstein条件）

S0; Cobegin S1；S2；S3；……；Sn; Coend Sn+1;

S1、S2、……、Sn可以由同一程序段中的不同语句组成。2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

11

将任一语句划分为两个变量的集合R（Si）和W（Si）:

读集R（Si）={a1，a2，……，am}

写集W（Si）={b1，b2，……，bn}

如对语句S1和S2有：

R（S1）∩W（S2）={Ф} W（S1）∩R（S2）={Φ} W（S1）∩W（S2）={Φ}

成立，则语句S1和S2可并发执行。2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

12例1．

语句c=a–b和w=c+1 R（c=a–b）={a,b} W（c=a–b）={c} R（w=c+1）={c} W（w=c+1）={w} R（w=c+1）∩W（c=a–b）={c}

语句c=a–b和w=c+1不能并发执行。2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

13例2．S1:a=x+y S2:b=z+1 S3:c=a–b S4:w=a+c+1R（S1）={x,y} W（S1）={a} R（S2）={z} W（S2）={b} R（S3）={a,b} W（S3）={c} R（S4）={a,c} W（S4）={w}

语句S1和S2能并发执行。语句S1和S3，S2和S3，S3和S4不能并发执行。

S1 S3→ S4S22.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

14资源共享资源共享是指系统中的硬件资源和软件资源不再由单个用户所独占，而为n个用户共同使用。由系统进行统一分配（硬件）和由程序自行使用（数据集，变量、队列等）程序并发执行与资源共享之间互为存在条件。2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

15程序并发执行的特点失去程序的封闭性和可再现性程序与计算不再一一对应程序并发执行的相互制约执行——暂停——执行2.1 前趋图和程序执行2023/7/25

02:03操作系统|进程管理

162.2 进程的概念进程的定义进程的定义:进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立的基本单位。进程的特征动态性并发特征独立特征异步特征机构特征2023/7/25

02:03操作系统|进程管理

17进程与程序的关系

进程 程序

概念动态实体， 静态实体， 强调执行过程 是指令的有序集合

特征并发性、独立性、 无并行特征， 异步性， 是静止的 是竞争计算机系统 资源的基本单位两者联系不同的进程可以共享同一个程序， 只要对应的数据集不同2.2 进程的概念2023/7/25

02:03操作系统|进程管理

18进程的组成（进程上下文）PCB程序

数据进程控制块PCB描述信息控制信息资源管理信息CPU现场保护：对CPU的处理2.2 进程的概念2023/7/25

02:03操作系统|进程管理

19PCB的组织方式链接方式将具有相同状态的PCB，用其中的链接字，链接成一个队列。2.2 进程的概念2023/7/25

02:03操作系统|进程管理

20索引方式根据进程的状态，建立索引表。2023/7/25

02:03操作系统|进程管理

212.3 进程状态及其控制进程状态一个进程的生命期可以划分为一组状态，这些状态刻画了这个进程。系统根据PCB结构中的状态值控制进程。就绪状态（Ready）执行状态（Running）等待状态（阻塞状态Blocked）新（New）状态终止状态（TerminatedorExit）2023/7/25

02:03操作系统|进程管理

22挂起状态（Suspend）把一个进程挂起使之处于静止状态，以便研究它的执行情况获对它进行修改。用户终端需要；父进程的需要：考查、修改获协调各子进程时；OS的需要：改善系统运行性能，调节负荷；对换的需要：缓和内存紧张的情况；2.3 进程状态及其控制2023/7/25

02:03操作系统|进程管理

23进程状态转换三种基本状态：执行状态（Executing）就绪状态（Ready）阻塞状态（Blocked）或等待（Wait）

阻塞状态就绪状态

执行状态调度I/O请求进程唤醒时间片到新状态结束后备队列新状态结束状态2.3 进程状态及其控制2023/7/25

02:03操作系统|进程管理

242023/7/25

02:03操作系统|进程管理

25细化的进程状态图（增加挂起）活动阻塞执行状态活动就绪静止就绪静止阻塞调度唤醒I/O请求激活激活挂起挂起挂起唤醒2.3 进程状态及其控制2023/7/25

02:03操作系统|进程管理

26活动就绪（Readya）和活动阻塞（Blockeda）静止就绪（Readys）和静止阻塞（Blockeds）2.3 进程状态及其控制2023/7/25

02:03操作系统|进程管理

27一个状态转换和进程转换的例子进程AI/O驱动中断处理进程BI/O现场保护和阻塞A启动I/O调度，恢复B现场I/O中断现场保护中断处理A就绪调度，恢复A现场退出（收回资源，调度）注：红色表示处于“管态”2.3 进程状态及其控制2023/7/25

02:03操作系统|进程管理

282.4 进程控制进程间的关系非结构系统（UnstructuredSystem）树形结构系统（Tree-StructuredSystem）:

一个进程能创建另一个进程，形成进程家族。2023/7/25

02:03操作系统|进程管理

29操作系统内核（Kernel）支撑功能中断处理时钟管理原语操作：完成特定功能的一段程序。原语在执行期间是不可分割的。资源管理功能进程管理存储器管理设备管理

2.4 进程控制2023/7/25

02:03操作系统|进程管理

30进程的创建引起进程创建的事件用户登录作业调度提供服务应用请求(应用程序创建)创建过程Create()申请空白PCB：新标识和PCB为新进程分配资源：批处理型和交互型作业初始化进程控制块新进程插入就绪队列2023/7/25

02:03操作系统|进程管理

31创建原语（CreatePrimitive）VoidCreate(n,S0,P0,M0,R0,acc){ i=getinternalname(n); id(i)=n; priority(i)=P0; cpupstate(i)=S0; mainstore(i)=M0; resources(i)=R0; status(i)=“readys”; setaccountingdata; insert(RL,i);}

2.4 进程控制2023/7/25

02:03操作系统|进程管理

32进程的终止进程终止的事件正常结束：Holt指令（引发中断）异常结束：越界错误保护错非法指令错特权指令错运行超时等待超时算术运算错I/O故障外界干预：人工或系统干预、父进程请求、父进程终止2023/7/25

02:03操作系统|进程管理

33撤消原语（DestroyPrimitive）Voiddestroy(n){ sched=false; i=getinternalname(n); Kill(i); Ifschedthenscheduler; }

2.4 进程控制2023/7/25

02:03操作系统|进程管理

34Kill过程：1、从PCB中读出进程状态；2、终止进程并设置调度标志为真；3、终止所有子进程；4、释放拥有的全部资源并归还父进程或系统；5、将终止进程从所在队列（PCB）中移出2023/7/25

02:03操作系统|进程管理

35进程阻塞引起进程阻塞的事件1、请求系统服务2、启动某种操作3、数据尚未到达4、无新工作可做阻塞原语的主要工作停止目前工作，存CPU下场到PCB中；将PCB中的现行状态由“执行”改为“阻塞”；将PCB插入相应的阻塞队列中将CPU的控制权交下一就绪状态的进程

2.4 进程控制2023/7/25

02:03操作系统|进程管理

36阻塞原语（BlockPrimitive）Void block(n){ i=getinternalname(n); stop(i); status(i)=“blockeda”; insert(WL(r),i); scheduler; }

2.4 进程控制2023/7/25

02:03操作系统|进程管理

37进程的唤醒进程唤醒的事件唤醒原语（WakeupPrimitive）Voidwakeup(n){ i=getinternalname(n); remove(WL(r),i); status=“ready”; insert(RL,i); scheduler; }

2.4 进程控制2023/7/25

02:03操作系统|进程管理

38进程的挂起（Suspend）挂起方式1、把发出本原语的进程自身挂起；2、挂起指定进程名（子进程）的进程；3、把某进程及其全部或部分子孙一起挂起。挂起操作检查被挂起进程的状态，根据原状态设置挂起后的状态把PCB复制到特定的内存区域若挂起前该进程正在执行，则由调度程序进行重新调度。

2.4 进程控制2023/7/25

02:03操作系统|进程管理

39方式2挂起原语（SuspendPrimitive）Voidsuspend(n,a){ i=getinternalname(n); s=status(i); ifs=“executing”thenstop(i); a=copyPCB(i); status(i)=ifs=“blockeda”then“blockeds”; else“readys”; ifs=“executing”thenscheduler; }

2.4 进程控制2023/7/25

02:03操作系统|进程管理

40进程的激活进程激活过程激活原语（ActivatePrimitive）由创建原语创建的进程处于“静止就绪“状态，后跟一个激活原语，使之变为活跃就绪，就能引起CPU的重新调度。

2.4 进程控制2023/7/25

02:03操作系统|进程管理

41Voidactivate(n){ i=getinternalname(n); status(i)=ifstatus=“readys”then“readya”; else“blockeda”; ifstatus(i)=“readya”thenscheduler;}

2.4 进程控制2023/7/25

02:03操作系统|进程管理

422.5 进程同步并发引起的操作系统的改变操作系统必须记住各种活跃的进程必须为每个进程分配和释放各种资源保护每个进程的数据和物理资源进程的结果必须与执行速度无关2023/7/25

02:03操作系统|进程管理

43进程间的制约进程中的资源竞争（间接）进程间通过共享的合作（直接）进程间通过通信的合作（直接）进程间的制约临界区临界资源（CriticalResource）：一次仅允许一个进程使用的资源。

2.5 进程同步2023/7/25

02:03操作系统|进程管理

44例1：两个进程对同一变量count访问和修改，P1：

count+=1; P2：

count-=1;若count=5。P1：

R1=count; R1=R1+1; count=R1;P2：

R2=count; R2=R2-1; count=R2;若顺序执行P1、P2，则count=5。

2.5 进程同步2023/7/25

02:03操作系统|进程管理

45P1： R1=count; P1： R1=count;P2： R2=count; R1=R1+1;P1： R1=R1+1; P2： R2=count; count=R1; R2=R2–1;P2： R2=R2–1; count=R2; count=R2;P1： count=R1;若执行顺序如上， 若执行顺序如上，则count=4 则count=6。

2.5 进程同步2023/7/25

02:03操作系统|进程管理

46与时间有关的错误:理发师问题发师床X顾客床Y理发馆理发椅顾客床有人唤醒顾客理发去发师床睡NY被唤醒理发师发师床有人唤醒发师理发去顾客床睡NY被唤醒顾客床有人离开NY顾客理发师读Y 顾客读Y

写X 读X

写Y2023/7/25

02:03操作系统|进程管理

47cobeginprocess1;process2：coend

2.5 进程同步临界区：不允许多个并发进程交叉执行的一段程序process1：beginL1：entrysectionCS1;exitsectionRemainderofrocess1;GotoL1;endprocess2：beginL2：entrysectionCS2;exitsectionRemainderofrocess2;GotoL1;end2023/7/25

02:03操作系统|进程管理

48互斥不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。临界区调度原则空闲让进忙则等待有限等待让权等待

2.5 进程同步2023/7/25

02:03操作系统|进程管理

49互斥的软件实现算法1:

进程Pi，Pj共享临界资源R。Turn：进程编号。算法1：共享一个公用整型变量turnvoidPi(){…… while(true){

while(turn!=i);//资源被j进程用，空转

criticalsection

turn=j; //把资源控制权交给j remaindersection }}

2.5 进程同步2023/7/25

02:03操作系统|进程管理

50算法2：用数组代替算法一中的turnintflag[n]={0,0…,0};voidPi(){while(true){for(j=0;j<n;j++)if(flag[j])j=0;//资源被用，空转

flag[i]=1;//让i

进程获得资源

criticalsection

flag[i]=0; //放弃资源控制权

remaindersection}}

2.5 进程同步2023/7/25

02:03操作系统|进程管理

51算法3：intflag[n]={0,0…,0};voidPi(){while(true){ flag[i]=1;

for(j=0;j<n;j++)if(flag[j])j=0;

criticalsection

flag[i]=0; remaindersection}}

2.5 进程同步2023/7/25

02:03操作系统|进程管理

52算法4：进程共享两个公用变量boolean[]flag=newboolean[2];intturn=0;publicvoidP0(){while(true){flag[0]=true;turn=1;while(flag[1]&&turn==1)；

<criticalsection>;flag[0]=false;<remainder>;}}publicvoidP1(){while(true){flag[1]=true;turn=0;while(flag[0]&&turn==0);<criticalsection>;flag[1]=false;<remainder>；}}

2.5 进程同步2023/7/25

02:03操作系统|进程管理

53publicstaticvoidmain(){flag[0]=false;flag[1]=false;parbegin(P0,P1);}

2.5 进程同步2023/7/25

02:03操作系统|进程管理

54算法5：对临界区S设置一个变量状态W，W=0表示资源可用，W=1表示资源已被占用。例：BeginintegerW=0; Cogegin Begin L1：lockW; CS1; UnlockW; Remainderofprocess1; GotoL1; End Begin L2：lockW; CS2; UnlockW; Remainderofprocess2; GotoL2; End Coend End

2.5 进程同步2023/7/25

02:03操作系统|进程管理

55关锁原语lockW： ifW=1then begin block(n); insert(WL,n); scheduler; end else W=1;

2.5 进程同步2023/7/25

02:03操作系统|进程管理

56开锁原语unlockW：ifWL<>NULLthen begin remove(WL,q); status(q)=“ready”; insert(RL,q); end else W=0;

2.5 进程同步2023/7/25

02:03操作系统|进程管理

572.6 信号量机制及其应用整型信号量机制信号量(sem)sem>=0:表示可供并发进程使用的资源实体的个数sem<0:表示正在等待使用临界区的进程数。Sem的值只能由P、V操作改变。P：wait(s)V：signal(s)按信号量数值分为二元信号量和一般信号量。2023/7/25

02:03操作系统|进程管理

58Wait（P）和signal（V）原语Wait(s)原语structsemaphore{intcount;QueueTypeQueue;}voidwait(s){s.count--;if(s.count<0){placethisprocessins.queue;blockthisprocess;}}

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

59signal原语voidsignal(s){s.count++;if(s.count<=0){removeaprocessPfroms.queue;placeprocessPonreadylist;}}

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

60利用信号量实现互斥publicclassmutualexclusion{staticfinalintn=<numberofprocesses>;semaphores=newsemaphore(1);publicvoidP(inti){while(true){wait(s);<criticalsection>;signal(s);<remainder>;}}publicstaticvoidmain(){parbegin(P(1),P(2),...,P(n));}}

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

61利用信号量描述前趋关系P1：S1P2：S2S1——>S2则设置信号量s=0，P1：S1；signal(s)；P2：Wait(s)；S2；

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

621234567abcdefgh例：根据前趋图写出可并发执行的程序：

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

63vara,b,c,d,e,f,g,h:semaphore:=0,0,0,0,0,0,0,0;begin parbegin beginS1;signal(a);signal(b);signal(c);end beginwait(a);S2;signal(d);end beginwait(b);S3;signal(e);end beginwait(c);S4;signal(f);end beginwait(d);S5;signal(g);end beginwait(e);wait(f);S6;signal(h);end beginwait(g);wait(h);S7;end parendend

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

64信号量集机制AND型信号量集机制问题引入进程A、B访问共享数据D和E

信号量Dmutex=1，Emutex=1processA: wait(Dmutex); wait(Emutex);

processB: wait(Emutex); wait(Dmutex);

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

65A、

B交替执行：processA: wait(Dmutex); 则Dmutex=0processB:wait(Emutex); 则Emutex=0processA: wait(Emutex); 则Emutex=-1，阻塞processB: wait(Dmutex); 则Dmutex=-1，阻塞发生死锁。

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

66AND同步机制的思想Swait(S1,S2,…,Sn){ if(S1>=1&&S2>=1&&…&&Sn>=1) for(i=1;i<=n;i++) Si--; else{

将进程插入第i（Si<1）个等待队列;

设置该进程的程序计数器到Swait操作的开始;}}

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

67Ssignal(S1,S2,…,Sn){ for(i=1;i<=n;i++){ Si++;

将所有等待Si资源的进程移到就绪队列。

}}

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

68一般“信号量”机制Swait(S1,t1,d1;…;Sn,tn,dn){ if(S1>=t1&&S2>=t2&&…&&Sn>=tn) for(i=1;i<=n;i++) Si–=di; else{

将执行进程插入第i（Si<ti）个等待队列;

设置该进程的程序计数器到Swait操作的开始;}}

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

69Ssignal(S1,d1,…;Sn,dn){ for(i=1;i<=n;i++){ Si+=di;

将所有等待Si资源的进程移到就绪队列;}}

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

70特例：

Swait(S,d,d)：一个信号量，可每次申请d个资源；

Swait(S,1,1)：记录型信号量（S>1）或互斥信号量（S=1）；

Swait(S,1,0)：当S>=1，允许多个进程进入某临界区；当S=0后，阻止任何进程进入临界区。

2.6 信号量机制及其应用2023/7/25

02:03操作系统|进程管理

71

例2：打印进程与计算进程的同步问题

设：SA—

打印进程的私有信号量，初值为0，

当SA=1

时表示可以打印。

SB—

计算进程的私有信号量，初值为0，

当SB=0时表示可以放入计算结果。缓冲区计算打印机缓冲区打印进程计算进程SASB缓冲区缓冲区缓冲区同步的概念2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

72•••

计算结果放入缓冲区；T2:signal(SA)；L1:wait（SB）；•••

显然，进程CP与进程IOP相互制约：①只有CP执行到T2，IOP才能执行T1。（T2T1）②只有IOP执行到L2，CP才能执行L1。（L2L1）计算进程与打印进程同步的模型计算进程CP打印进程IOP•••T1:wait（SA）；

从缓冲区取结果；L2:signal（SB）；•••SA，SB初值为02.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

73异步环境相互合作的一组并发进程，其中每一进程都能以各自独立的，不可预知的速度向前推进。进程同步相互合作的进程之间需要交换一定的信息，当某进程未获得其合作进程发来的信息之前，该进程等待，直到该信息到来时才被唤醒继续执行，从而保证诸进程的协调运行。2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

74生产者—消费者问题综述问题描述通过由n个环形缓冲区构成的缓冲池，把生产者P1，P2，……，PM和一群消费者C1，C2，……，CK联系起来。算法描述2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

752023/7/25

02:03操作系统|进程管理

76变量定义：beginVarmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

77parbeginproducer: begin repeat producenextproduct;

wait(empty); wait(mutex);

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

signal(full); signal(mutex); untilfalse; end2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

78consumer:begin repeat

wait(full); wait(mutex);

nextc:=buffer(out); out:=(out+1)modn;

signal(empty); signal(mutex); consumetheiteminnextc; untilfalse; end parend end2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

79wait(empty) empty>=0 则数据送入缓冲区

empty<0 被阻塞（满）signal(empty) empty>0 empty<=0 释放一个空缓冲区，唤醒一个阻塞的生产者进程2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

80wait(full) full>=0 则从缓冲区取走数据

full<0 被阻塞（空）signal(full) full>0 full<=0 数据装入缓冲区，唤醒一个 阻塞的消费者进程2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

81注意：互斥和同步信号量的原语必须成对出现。signal操作的次序无关紧要，但wait操作的次序不能颠倒，否则会造成死锁。用AND信号量解决生产者——消费者问题2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

82用AND信号量解决生产者——消费者问题parbeginproducer: begin repeat producenextp; Swait(empty,mutex); buffer(in):=nextp; in:=(in+1)modn; Ssignal(mutex,full); untilfalse; end2023/7/25

02:03操作系统|进程管理

83哲学家进餐问题2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

84publicclassdiningphilosophers{ semaphore[]fork=newsemaphore[5](1); inti;2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

85 publicvoidphilosopher(inti){ while(true){ think();

wait(fork[i]); wait(fork[(i+1)%5]);

eat();

signal(fork[(i+1)%5]); signal(fork[i]); } }2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

86publicstaticvoidmain(){ parbegin(philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4)); }}2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

87解决死锁的方法：至多允许四个哲学家同时进餐。仅当哲学家的左右两支叉子均可用时，才进餐。（用AND信号量机制解决哲学家进餐问题。）奇数号哲学家先拿左边的叉子，偶数号哲学家先拿右边的叉子。2.7

经典进程同步问题2023/7/25

02:03操作系统|进程管理

88读者——写者问题

读者进程:可以同时读一个共享资源;

写者进程:互斥的存取共享对象;

读写进程同步:必须保证一个写进程与其它进程互斥地访问共享资源.Readcount:描述读者数目的临界资源.publicclassReadersAndWriters{ intreadcount; semaphorermutex=newsemaphore(1); semaphorewmutex=newsemaphore(1);2023/7/25

02:03操作系统|进程管理

89publicvoidreader(){

while(true){ wait(rmutex); if(readcount==0) wait(wmutex); readcount++; signal(rmutex); READUNIT(); wait(rmutex); readcount--; if(readcount==0) signal(wmutex); signal(rmutex); }}2023/7/25

02:03操作系统|进程管理

90publicvoidwriter(){ while(true){ wait(wmutex); WRITEUNIT(); signal(wmutex); } }2023/7/25

02:03操作系统|进程管理

912.8 管程机制管程的基本概念管程的定义：一个管程定义了一个数据结构和能为迸发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据。这些数据及操作对进程是透明的，局部于管程的数据结构只能被该管程的过程访问。管程组成：1、局部共享变量说明，2、内部对数据结构的操作，3、局部数据的置初值。 任何进程访问共享资源，只能通过调用管程中的过程（管程名.过程名）,而管程每次只允许一个进程进入管程，从而实现进程互斥条件变量：2023/7/25

02:03操作系统|进程管理

92管程的语法说明：一个进程访问临界资源TYPESSU=MonitorVarbusy:boolean;nobusy:condition;definerequire,returnProcedurerequireBeginifbusythennobusy.waitbusy:=trueEnd;ProcedurereturnBeginbusy:=false;nobusy.signal;End//initializationcodeBegin busy:=false;End2023/7/25

02:03操作系统|进程管理

932.8 管程机制条件变量：利用管程实现同步时，必须设置同步原语操作（wait和signal），由管程调用实现阻塞和唤醒。为了区别阻塞的原因，引入条件变量（在管程中说明），由条件变量来调用Wait、Signal原语操作。

conditionVARx,y:condition

……x.wait;y.signal在管程中，y.signal操作的作用是启动一个被阻塞的进程，但如果阻塞队列没有进程时，y.signal不产生任何操作。如果进程Q处于阻塞队列的首部，当前进程P执行了y.signal，管程的处理方式1、P等待，直至Q离开管程或等待另一条件；2、Q等待，直至P离开管程或等待另一条件；2023/7/25

02:03操作系统|进程管理

942.8 管程机制用管程解决生产者-消费者问题TypePC=monitorVarin,out,count:integer;Buffer:array[0,…,n-1]ofitem;Full,Empty:condition;ProcedureEntryput(item)beginifcount>=nthen Full.wait;Buffer(in):=nextp;in:=(in+1)modn;count:=count+1;IfEmpty.queuethen Empty.signalendProcedureEntryget(item)beginifcount<=0then Empty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifFull.queuethen Full.signalendBeginin:=0;out:=0;count:=0;end2023/7/25

02:03操作系统|进程管理

95Producer:Beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endConsumer:BeginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end2.8 管程机制2023/7/25

02:03操作系统|进程管理

96进程通信

进程之间的信息交换称为进程通信。1、低级通信：（信息量少）同步与互斥的进程间通过修改信号量,其缺点:1、效率低，2、不透明。2、高级通信：（大量数据）通过操作系统提供的一组通信命令，高效地传送大量数据，通信过程对用户透明。优点：1、数据量大，2、减少通信程序编制上的复杂性。2023/7/25

02:03操作系统|进程管理

97进程通信进程通讯类型共享存储系统、消息传递系统、管道通信系统共享存储系统（Shared-MemorySystem）：由通信进程共享某些数据结构或共享存储区。基于共享数据结构的通信方式：公用数据结构的设置及对进程间同步的处理，都必须由程序员管理，操作系统只提供共享存储器，因此效率低，只适用少量数据传递。基于共享存储区的通信方式：进程在通信前，先向系统申请共享存储区（系统划分）中的一个分区，并指定关键字（若该分区已为其它进程拥有，则向申请者返回描述符），由申请者把获得的共享存储分区连接到自己进程。适用于大量数据传递。2023/7/25

02:03操作系统|进程管理

98管道通信管道（pipe）指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件。例：UNIX的管道管道按FIFO方式单向传送消息。Pipe文件写端fd[1]读端fd[0]2.9 进程通信管道机制必须具备:（1）互斥、（2）同步、（3）确定对方存在。2023/7/25

02:03操作系统|进程管理

99OS发送命令（直接通信方式）发送进程直接利用OS所提供的命令，把消息发送给目标进程。要求发送进程和接收进程必须以显示方式提供对方的标识符。

OS通常提供以下两类通信原语：

Send(ReceiverID,message);Receive(SenderID,message);消息传递通信的实现方法2023/7/25

02:03操作系统|进程管理

100信箱（间接通信方式）

间接通信方式：进程之间的通信需要通过作为共享数据结构的实体作为暂存发送进程发送给目标进程的消息。

当两个进程间需要通信时，由发送进程创建一个与接收进程相连的信箱。发送进程把消息送到信箱，接收进程从信箱中取走消息。信箱头：名称，大小，方向，进程名等；信箱体：由若干格子组成，每一格存放一条消息。双向信箱信箱溢出2023/7/25

02:03操作系统|进程管理

101信箱创建与撤消:系统提供相关原语,用于信箱的创建、撤消和消息的发送、接收。消息的发送和接收：必须使用共享信箱，利用通信原语进行通信。Send(mailbox,message);Receive(mailbox,message);信箱类型私用信箱：用户创建,拥有者可读，其他人只可发。公用信箱：采用输入/输出双向通信链路，由OS创建。被核准进程可发、可收。共享信箱：由进程创建并指明共享进程名。发送进程和接受进程的对应关系：一对一、一对多、多对一、多对多。2023/7/25

02:03操作系统|进程管理

102通信链路：在发送进程和接受进程之间必须建立一条通信链路。一种是显示的由“建立连接”命令（原语）请求系统为之创建，使用完后，也用显示方式拆除。另一种是利用系统提供的发送命令（原语），系统自动建立和拆除。通信链路（communicationlink）显式和隐式链路点-点连接通信链路、多点连接链路单向和双向通信链路无容量和有容量通信链路消息传递系统中的若干问题2023/7/25

02:03操作系统|进程管理

103消息的格式：在消息传递系统中，必须具有一定的消息格式。通常可把一个消息分为消息头和消息正文两部份。消息头主要包括消息在传输时所需的控制信息，消息正文则是实际发送数据。消息的格式有定长（短消息）和变长（长消息）两种。2023/7/25

02:03操作系统|进程管理

104消息的格式2023/7/25

02:03操作系统|进程管理

105进程同步方式发送进程阻塞、接收进程阻塞。发送进程与接收进程之间无缓冲，两进程平时都处于阻塞。发送进程不阻塞、接收进程阻塞。发送进程不阻塞，接收进程平时处于阻塞，由发送进程唤醒。发送进程、接收进程均不阻塞。2023/7/25

02:03操作系统|进程管理

106消息缓冲队列通信机制通信原语

Send(Receiver,message); Receive(Sender,message);消息缓冲区Typemessagebuffer=record Sender； Size ；

Text ；

Next ；

end2023/7/25

02:03操作系统|进程管理

107PCB中有关通信的数据项TypeProcessControlblock=record … mq ；消息队列首指针

mutex；消息队列互斥信号量

sm ；消息队列资源信号量

… end2023/7/25

02:03操作系统|进程管理

108消息缓冲通信模型send(B,a)sender:Asize:5text:Hello进程Areceive(b)sender:Asize:5text:Hello进程Bmqmutexsmsender:Asize:5text:Hellonext:0PCB(B)第一消息缓冲区发送区a接收区b进程Asend(B,a)asender:Asize:5text:Hel