01月
19

发表于 • 字数统计 4754 • 被 1,801 人看爆

信号量

信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。

信号量机制

 进程间通信处理同步互斥的机制。信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。

PV操作

PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作

定义如下

设信号量为S，S可以取不同的整数，用来表示共享资源的使用情况或者指示协作进程之间交换的信息

P操作

每执行一次P操作其实就是意味请求分配一个资源

P(S) 
{
    S = S - 1;
    若S>=0，表示可用资源分配，进程继续执行
    若S<0，没有可分配的资源，将该进程状态置为等待状态(阻塞状态)，然后将该进程的PCB插入相应的S信号量等待队列末尾(其S的绝对值表示排在S信号量的等待队列中进程数目)，直到有其他进程在S上执行V操作为止。如：S为-1，则当有资源的话(有进程执行V操作)，则第一个唤醒该进程
}

V操作

每执行一次V操作，意味着进程释放了一个资源，并唤醒一个等待队列中进程

V(S) 
{
    S = S + 1;
    若S>0，则该进程继续执行
    若S<=0，表示还有进程在等待队列中，释放在S信号量队列中等待的第一个进程(按P操作的S值的绝对值，-1则第一个唤醒，和队列一样的思想先进先出)，将其状态改为就绪状态，并将其插入到就绪队列中；然后，继续执行该进程
}

注意：

  • 每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。
  • P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
  • 互斥信号量的初值一般为1。

示例1

假设有进程A、B竞争进入临界区，用P、V操作实现进程之间的互斥。其中，S的初值为1。分析下面两个进程P、V操作

进程A                               进程B：
P(S);                               P(S);
    临界区操作;                         临界区操作;
V(S);                               V(S);

分析：

  • 1.假设A进程先进入，先执行P操作申请资源，S = S - 1 = 0，未小于0，有资源可以继续执行，然后执行临界区操作
  • 2.这时，B进程进来了，执行P操作申请资源，S = S - 1 = -1，发现小于0，没资源了，就进入等待状态
  • 3.A进程这是执行到V操作，S = S + 1 = 0，发现S的值<=0，就知道有进程在等待队列，唤醒该进程并释放资源
  • 4.B进程被唤醒，进入就绪状态，由于之前已经执行过P操作，只是从等待队列中唤醒，无需再次执行P操作，直接执行临界区操作
  • 5.最后B执行V操作，S = S + 1 = 1，发现没有等待队列中没有需要唤醒的，B进程结束

示例2

有三个进程，进程get从输入设备上不断读取数据，并放入缓冲区buffer1;进程copy不断地将缓冲区buffer1中的内容复制到缓冲区buffer2;进程put则不断将buffer2中的内容在打印机上输出。该三个进程是同步进行

关系图如下：
PVOperate01.png

思路

信号量的设置

  • S1:初值为1，保证get进程能够从设备读数据到buffer1。
  • S2:初值为0，copy进程能否将buffer1的内容复制到buffer2。
  • S3:初值为0，put进程能否将buffer2的内容打印输出。
  • S4:初值为1，保证buffer2缓冲区可以使用

PV表示

get进程：
while(true) {
    ...
    P(S1);      //申请资源，S1 = S1 - 1 = 0，继续执行
    从输入设备向缓冲区buffer1读数据;
    V(S2);      //唤醒S2进程
}

copy进程
while(true) {
    P(S2);      //申请资源，判断是否buffer1是否有资源
    P(S4);      //唤醒buffer2进程，保证buffer2没有进程在使用
    将buffer1内容复制到buffer22;
    V(S1);      //释放S1资源，为get进程下次做准备，也就是相当于通知get进程
    V(S3);      //唤醒S3，为put进程赋予资源，通知put进程
}

put进程
while(true) {
    P(S3);      //判断是否有资源，看前面copy进程，也就是查看buffer2进程里是否有资源，否则就要进入等待队列
    将缓冲区buffer2内容再打印机上输出;
    V(S4);      //释放资源，表示buffer2缓冲区可用，相当于通知copy进程
}

例题2 生产者---消费者问题

设有一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来。缓冲区只容纳一个产品，生产者不断地生产者，然后往空缓冲区送产品；而消费者则不断地从缓冲区取出产品，并消费掉

关系图
PVOperate02.png

思路

  • 生产者不能往满地缓冲区放产品
  • 消费者不能从空地缓冲区取产品

信号量设置

  • 设置empty表示不能往满缓冲区放产品，空缓冲区数目，初值为1
  • 设置full表示不能从空缓冲区取产品，满缓冲区数目，初值为0

PV操作

P进程   生产者
while(true) {
    P(empty);           //判断缓冲区是否为空
    生产一个产品;
    送产品到缓冲区;     
    V(full);            //增加满缓冲区数目，相当于通知消费者可以从缓冲区取chanp
}

Q进程  消费者
while(true) {
    P(full);            //判断是否小于0
    从缓冲区取产品;
    V(empty);           //相当于通知生产者空缓冲区数目
}

例题3 多个生成者---消费者问题

设有若干个生产者P1,P2....若干个消费者Q1,Q2....，他们通过一个环形缓冲池联系

关系图
PVOperate03.png

思路

和上面生产者---消费者一样，只不过是环形
  • 生产者不能往“满”缓冲区中放产品，设置信号量empty,初值K，指示缓冲池空缓冲区数目
  • 消费者不能从“空”缓冲区中取产品，设置信号量full，初始值为0，指示缓冲池中的满缓冲数目
  • 缓冲池必须互斥访问，设置信号量mutex，初值为1
  • 整型量i，j，初值为0，分别用于指示空缓冲区和满缓冲区位置

PV操作

生产者进程P1，P2，...，Pn;
i = 0;
while(true) {
    生产产品;
    P(empty);       //判断缓冲区是否是满的
    P(mutex);       //判断是否有消费者在进程中，没有则并释放互斥信号，因为生产者与消费者不能同时访问
        往Buffer[i]中放产品;
        i = (i + 1) mod k;      //取余
    V(mutex);       //解除互斥信号
    V(full);        //表示满缓冲区数目，相当于通知消费者

}

消费者进程Q1，Q2，...，Qn;
j = 0;
while(true) {
    P(full);        //判断缓冲区是否为空，就是满缓冲区数目大于0
    P(mutex);       //判断是否有生产者在进程中，没有则释放互斥信号
        从buffer[j]取产品;
        j = (j + 1) mod k;   //取余
    V(mutex);       //解除互斥信号
    V(empty);       //通知生产者空缓冲区数目
    消费产品;
}

例题4

桌上有一个水果的盘子,一次只能放一个水果，父亲向盘中放苹果或橘子,女儿专吃苹果，儿子专吃橘子，试用pv操作写出他们能正确同步的过程。

思路

该问题其实和生产者---消费者问题一样
  • 爸爸是生产者
  • 一个盘子只能放一种水果
  • 父亲向盘中放苹果或橘子,女儿专吃苹果，儿子专吃橘子，互斥

信号量设置

设S代表盘子是否为空，初值为1；So示盘中是否有橘子,其初值为0；Sa表示盘中是否有苹果，其初值为0。

PV操作

爸爸
while(true) {
    P(S);           //判断盘子是否为空
    if(放入的是橘子) {
        V(So);          //通知儿子
    }
    else {
        V(Sa);          //通知女儿
    }
}

儿子
while(true) {
    P(So);      //判断是否为橘子
    吃橘子;
    V(S);       //通知爸爸盘子为空了

}

女儿
while(true) {
    P(Sa);      //判断是否为苹果
    吃苹果;
    V(S);       //通知爸爸盘子为空了

}

参考

分享到：