信号量PV操作、消费者生产者问题

Semantics and implementation

Posted by Jerry on March 24, 2017

a semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system such as a multiprogramming operating system.

信号量

信号量,是一种抽象数据类型(ADT),用来解决在并行系统中多进程之间资源竞争、资源互斥(mutual exclusion Resource)问题。信号量是一种很好的方法阻止竞争条件(race conditions),它能保证程序不会产生由竞争条件产生的问题。允许任意资源计数的信号量称为计数信号量,而限制为0和1(或锁定/解锁,不可用/可用)的信号量称为二进制信号量,用于实现锁定。

当用于控制对资源池的访问时,信号量仅跟踪有多少资源是可用的; 它没有跟踪具体是哪些资源可用。一些其他机制(可能涉及更多的信号量)可用来选择特定的免费资源。

临界区

临界区是指一个访问共用资源的程序片段,而这些共用资源又无法同时被多个线程访问。

临界区规定:每次只准许一个进程进入临界区,进入后不允许其他进程进入。调度法则为(百度百科):

1、如果有若干进程要求进入空闲的临界区,一次仅允许一个进程进入。

2、任何时候,处于临界区内的进程不可多于一个。如已有进程进入自己的临界区,则其它所有试图进入临界区的进程必须等待。

3、进入临界区的进程要在有限时间内退出,以便其它进程能及时进入自己的临界区。

4、如果进程不能进入自己的临界区,则应让出CPU,避免进程出现“忙等”现象。

P V操作

信号量S有两种操作称为P和V操作,操作V增加信号量S,操作P减少信号量S 信号量S的值代表当前有多少数量的资源可用,P操作使进程等待直到有可用的受保护的资源,而V操作刚好相反,它作用是当某个进程对该资源使用完毕,使得资源再次可用。信号量S的值只能被P或者V操作修改,其他任何情况下S值不能改变。 简单的方式理解wait(P)和signal(V)操作:

  • wait:如果信号量S的值为非负,则减少S,如果信号量当前为负数,则进行执行阻塞(blocked,例如添加到信号量队列中去)直到S的大于或者等于1;否则进行将继续执行,该进程占有一个资源单元。
  • signal:使S的值添加1,在添加1之后,如果添加1之前S为负数(意味着有进程正在等待资源),使得一个阻塞进程(blocked process,随机从信号量队列中选择一个进程)从等待状态进入就绪状态。

操作的原子性(atomic operation),对于其他进程来说,这些操作是不可分割的。下面的PV操作中中括号中的操作原子操作。

function V(semaphore S, integer I):
    [S ← S + I]

function P(semaphore S, integer I):
    repeat:


    
        [if S ≥ I:
        S ← S − I
        break]

关于PV操作容易产生的一些疑问: 1,S大于0那就表示有临界资源可供使用,为什么不唤醒进程? S大于0的确表示有临界资源可供使用,也就是说这个时候没有进程被阻塞在这个资源上,所以不需要唤醒。

2,S小于0应该是说没有临界资源可供使用,为什么还要唤醒进程? V原语操作的本质在于:一个进程使用完临界资源后,释放临界资源,使S加1,以通知其它的进程,这个时候如果S<0,表明有进程阻塞在该类资源上,因此要从阻塞队列里唤醒一个进程来“转手”该类资源。比如,有两个某类资源,四个进程A、B、C、D要用该类资源,最开始S=2,当A进入,S=1,当B进入S=0,表明该类资源刚好用完, 当C进入时S=-1,表明有一个进程被阻塞了,D进入,S=-2。当A用完该类资源时,进行V操作,S=-1,释放该类资源,因为S<0,表明有进程阻塞在该类资源上,于是唤醒一个。

3,如果是互斥信号量的话,应该设置信号量S=1,但是当有5个进程都访问的话,最后在该信号量的链表里会有4个在等待,也是说S=-4,那么第一个进程执行了V操作使S加1,释放了资源,下一个应该能够执行,但唤醒的这个进程在执行P操作时因S<0,也还是执行不了,这是怎么回事呢? 当一个进程阻塞了的时候,它已经执行过了P操作,并卡在临界区那个地方。当唤醒它时就立即进入它自己的临界区,并不需要执行P操作了,当执行完了临界区的程序后,就执行V操作。

4,S的绝对值表示等待的进程数,同时又表示临界资源,这到底是怎么回事? 当信号量S小于0时,其绝对值表示系统中因请求该类资源而被阻塞的进程数目.S大于0时表示可用的临界资源数。注意在不同情况下所表达的含义不一样。当等于0时,表示刚好用完。

信号量几个应用

简单例子(trivial example)

一个变量A和一个布尔变量S,A被通过只有S为true的时候,因此S是A的一个信号量。 也可以想象成一个交通信号灯S(A stoplight signal),只有S为绿色,才让火车进入火车站,如果为黄色或者红色则禁止火车进入火车站。

登录队列

系统能支持10个用户(即信号量S=10)同时登录,何时有用户登录,则P操作被调用,信号量S减少1,何时有用户登出则调用V操作,信号量S增加1代表一个登录槽(login slot)可用。当S为0,任何希望登录系统的用户必须等待,直到S>0,登录请求等待队列是一个FIFO(先进先出)队列。互斥(mutual exclusion)用于确保请求是按照顺序排队。无论何时S>0(说明有可用的登录槽),则一个登录请求出队,允许该请求的用户登录系统。

生产者-消费者问题

在生产者-消费者问题中,一个进程(producer)生成数据项,然后另一个进程(consumer)接受数据,使用数据。它们之间通信使用一个大小为N的队列,而且所遵循的条件如下:

  • 如果队列为空,消费者必须等待生产者生成数据
  • 如果队列满了,生产者必须等待消费去消费数据 信号量可以通过跟踪队列状态,两种不同的信号量—— EmptyCount(队列中空的个数或者说可用的个数)和FullCount(队列中已有的元素数量) 使用二进制信号量useQueue确保队列本身的状态的完整性不受影响,例如由两个生产者尝试将item同时添加到空队列,从而破坏其内部状态。或者,可以使用互斥体来代替二进制信号量。 emptyCount最初为N,fullCount最初为0,而useQueue最初为1。 生产者重复执行以下操作:
produce:
    P(emptyCount)
    P(useQueue)
    putItemIntoQueue(item)
    V(useQueue)
    V(fullCount)

消费者重复执行以下操作:

consume:
    P(fullCount)
    P(useQueue)
    item ← getItemFromQueue()
    V(useQueue)
    V(emptyCount)

参考资料

  1. https://en.wikipedia.org/wiki/Semaphore_(programming)
  2. http://blog.csdn.net/liushuijinger/article/details/7586656