信号量与PV操作课件

{produce an item in nextp};//生产一个产品

if (counter==k) //缓冲满时，生产者睡眠

sleep(producer);

buffer[in]=nextp;//将一个产品放入缓冲区

in=(in+1)%k; //指针推进

counter++; //缓冲内产品数加1
{consume the item in nextc};//消耗产品

}
}
生产者-消费者问题的算法描述(4)
生产者和消费者进程对counter 的交替执行会使其结果不唯一
生产者和消费者进程的交替执 行会导致进程永远等待
竞争条件(Race Condition)
counter++ could be implemented as
register1 = counter register1 = register1 + 1 count = register1 counter-- could be implemented as
register2 = counter register2 = register2 - 1 counter = register2 Consider this execution interleaving with “counter = 5” initially: S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 - 1 {register2 = 4} S4: producer execute counter = register1 {counter = 6 } S5: consumer execute counter = register2 {counter = 4}

信号量和PV操作解决机票问题(2)
• • • • • • • • • • • • • • • • ARRAY[1..m] integer; /*表示 种票* 表示m Var A : ARRAY[1..m] OF integer; /*表示m种票*/ ARRAY[1..m] semaphore; /*表示每种票的变量临 表示每种票的变量临* s : ARRAY[1..m] OF semaphore; s[j] := 1; /*表示每种票的变量临*/ /*界资源都设一个信号量 Cobegin /*界资源都设一个信号量 process Pi Xi:integer; var Xi:integer; begin L 1: 按旅客定票要求找到A[j] A[j]； 按旅客定票要求找到A[j]； P(s[j]) A[j]; Xi := A[j]; Xi>=1 if Xi>=1 Xi:=Xi- A[j]:=Xi; V(s[j]); 输出一张票； end; then begin Xi:=Xi-1; A[j]:=Xi; V(s[j]); 输出一张票； end; V(s[j]);输出票已售完；end; else begin V(s[j]);输出票已售完；end; goto L1; end; end; coend; coend;
3.3.2 信号量与P、V操作—同步工具
信号量与P 信号量与P、V操作的定义 操作的定义
（E.W.Dijkstra）原始定义（书上：整形信号量） • 信号量s是一个非负整形变量，除初始化外，仅能通 过P、V操作所访问（改变） • P(s)操作：当信号量s大于0时，把信号量s减1，否 则调用P(s)的进程等待直到信号量s大于0。 • V(s)操作：把信号量s加1 用类PASCAL语言描述PV操作的功能如下： 用类PASCAL语言描述PV操作的功能如下： PASCAL语言描述PV操作的功能如下 P(s)： s≤0 P(s)：while s≤0 do null operation =ss：=s-1； V(;1；

在计算机操作系统中，PV操作是进程管理中的难点。

首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：P（S）：①将信号量S的值减1，即S=S-1；②如果S≥0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

V（S）：①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。

PV操作属于进程的低级通信。

什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。

信号量的值与相应资源的使用情况有关。

当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。

注意，信号量的值仅能由PV操作来改变。

一般来说，信号量S≥0时，S表示可用资源的数量。

执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。

而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S≤0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

利用信号量和PV操作实现进程互斥的一般模型是：进程P1 进程P2 ……进程Pn………………P（S）；P（S）；P（S）；临界区；临界区；临界区；V（S）；V（S）；V（S）；……………………其中信号量S用于互斥，初值为1。

使用PV操作实现进程互斥时应该注意的是：（1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。

若有多个分支，要认真检查其成对性。

（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。

（3）互斥信号量的初值一般为1。

利用信号量和PV操作实现进程同步PV操作是典型的同步机制之一。

其中
•W(s.list)和R(s.list)是操作系统的基本系统调用， •W(s.list)表示把调用它的进程置成等待信号量s状态， 并移入s信号量队列，同时释放CPU，转向进程调度； •R(s.list)表示释放一个等待s信号量的进பைடு நூலகம்，转换成 就绪态并且移入就绪队列，执行该操作的进程继续执 行（时间片未到期）或者转向进程调度（时间片已到 期）。 •进程从队列中移出时的次序按照FCFS算法，被阻塞的 时间越长的进程越优先出队，一避免饥饿现象。
信号量的分类 •信号量按其用途分为2种： 公用信号量：初值常常为1，用来实现进程间的互斥。相关进 程均可对其执行P、V操作。 私有信号量：初值常常为可用资源数，多用来实现进程同步。 拥有该信号量的一类进程可以对其执行P操作，而另一类进程 可以对其执行V操作，多用于并发进程的同步。 •信号量按照取值可以分为两种： 二元信号量： 仅允许取0和1，主要用于解决进程互斥； 一般信号量（计数信号量）：允许取任意整数值，主要用于 解决进程同步问题。
} coend
A[m]; int A[m]; semaphore s; s = 1; cobegin
A[m]; int A[m]; s[m]; semaphore s[m]; j=0 j<m; For(int j=0;j<m;j++) { s[j] := 1; ] cobegin process Pi(){ Xi; int Xi; 按旅客定票要求找到 A[j] P(s[j]) Xi= A[j]; A[j]; If(Xi>=1 If(Xi>=1){ Xi=XiA[j]=Xi; Xi=Xi-1; A[j]=Xi; V(s[j]); V(s[j]); 输出一张票 ； ；