上图是一道操作系统PV操作的习题，用Python解决之，建立一个线程模拟行人从北向南过桥，另一个线程模拟行人从南向北过桥，建立四个信号量，分别实现对桥、北桥段、南桥段和桥中央的互斥。

north_side = threading.Semaphore(1) #北桥段只能通过一人
north= threading.Semaphore(1)  #北向南一次只允许一人过桥
south_side = threading.Semaphore(1) #南桥段只能通过一人
south= threading.Semaphore(1)  #南向北一次只允许一人过桥
person = threading.Semaphore(2) #桥中央允许两人通过或歇息

随机生成20个线程（行人），观察行人过桥的状况，符合题目要求，运行结果如下图。

import threading,time,random
north_side = threading.Semaphore(1)
north= threading.Semaphore(1)
south_side = threading.Semaphore(1)
south= threading.Semaphore(1)
person = threading.Semaphore(2)

def north_south():
    t = threading.currentThread()
    north_side.acquire()

    north.acquire()
    print('行人%dnorth_south上北桥段\n'%t.ident)
    time.sleep(random.random())
    north.release()
    
    person.acquire()            
    print('行人%dnorth_south行至桥中央\n'%t.ident)
    time.sleep(random.random())
    person.release()

    south.acquire()            
    print('行人%dnorth_south上至南桥段\n'%t.ident)
    time.sleep(random.random())
    south.release()
    print('行人%dnorth_south下桥\n'%t.ident)
    north_side.release()
def south_north():
    t = threading.currentThread()
    south_side.acquire()
    south.acquire()
    print('行人%dsouth_north上南桥段\n'%t.ident)
    time.sleep(random.random())
    south.release()
    
    person.acquire()            
    print('行人%dsouth_north行至桥中央\n'%t.ident)
    time.sleep(random.random())
    person.release()

    north.acquire()            
    print('行人%dsouth_north上至北桥段\n'%t.ident)
    time.sleep(random.random())            
    north.release()
    print('行人%dsouth_north下桥\n'%t.ident)
    south_side.release()            

if __name__=='__main__':
    threads = []
    for i in range(20):        
        r=random.randint(0,1)
        if r==0:
            p = threading.Thread(target=north_south)
        else:
            p = threading.Thread(target=south_north)
        p.start()
        threads.append(p)
    for t in threads:
        t.join()
    

PV操作起源：

1962年，荷兰学者Dijksrta在参与X8计算机的开发中设计并实现了具有多道程序运行能力的操作系统——THE Multiprogramming System。为了解决这个操作系统中进程（线程）的同步与互斥问题，他巧妙地利用火车运行控制系统中的“信号灯”（semaphore，或叫“信号量”）概念加以解决。信号量的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，这个信号量的值仅能由PV操作来改变。

PV操作概念：

操作系统中的一种同步机制，实现对于并发进程中临界区的管理。

并发进程分为两种：

①无交互的并发进程：每个进程是相互独立的，谁也不影响谁，基本不会用到PV操作。

②有交互的并发进程：多个进程共享资源，一个进程的运行，有可能会被外界的原因而中断，且断点不固定。进程执行的相对速度不能由进程自己来控制，于是就会导致并发进程在共享资源的时出现与时间有关的错误。

临界区：并发进程中与共享变量有关的程序段都称为临界区。

P操作：申请资源操作。

V操作：释放资源操作。

信号量S：用来记录资源数量，看是否能满足申请资源的操作。例如：S=3 表示三个可用空闲资源，S<0表示可用空闲资源无，进程申请要进入等待队列中。

P(S)：

①将信号量S的值减1，即S=S-1；

②如果S>=0，则该进程继续执行；否则该进程置为等待状态。

V(S)：

①将信号量S的值加1，即S=S+1；

②该进程继续执行；如果该信号的等待队列中有等待进程就唤醒一等待进程。

用PV操作实现多线程的同步与互斥是非常简单的，只要考虑逻辑处理上合理严密而不用考虑具体技术细节，因此与写伪代码较为相似。比如有多个进程P1、P2、 ……PN。它们要互斥的访问一个资源。用PV操作来实现就非常方便直观。下面是PV操作代码：

设置信号量为S，初值为1。各进程的操作流程如下：

进程P1 进程P2 …… 进程Pn

P（S）； P（S）； P（S）；

访问资源； 访问资源； 访问资源；

V（S）； V（S）； V（S）；

可以看出PV操作会忽略具体的编程细节，让主要精力放在线程同步互斥的逻辑处理上。

PV操作实例：

公交车司机与售票员的问题：

1. 首先，我们在司机进程使用P操作（S1=S1-1=-1），现在是S1的值为-1，我们来查看P操作发现应该 挂起本进程，也就是说司机进程暂时挂起，我们进入到售票员进程。
2. 进入售票员进程后，我们先 关车门，然后我们进行V操作（S1=S1+1=0），发现满足V操作的else，我们首先唤醒司机进程，然后我们继续执行售票员进程。
3. 接着售票，售票后我们执行P操作（S2=S2-1=-1），发现满足P操作的else，我们暂时将售票员进程挂起。
4. 进入到司机进程。
5. 启动车辆，正常行驶，到站停车，执行V操作（S2=S2+1=0），发现S2满足V操作的else，唤醒售票员进程，同时继续执行本进程。
6. 但是，我们可以发现司机进程已经执行完了，但是等待队列中还有售票员进程，我们就进入到售票员进程
7. 在售票员进程中，开车门，上下客。整个司机与售票员问题结束。

PV操作例题：

桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

下面先考虑同步情况即所有“等待”情况：

第一．爸爸要等待盘子为空。

第二．儿子要等待盘中水果是桔子。

第三．女儿要等待盘中水果是苹果。

接下来来考虑要互斥处理的资源，看起来盘子好像是要作互斥处理的，但由于题目中的爸爸、儿子、女儿均只有一个，并且他们访问盘子的条件都不一样，所以他们根本不会同时去访问盘子，因此盘子也就不用作互斥处理了。分析至些，这个题目已经没有难度了，下面用PV原语给出答案：

先设置三个信号量，信号量Orange表示盘中有桔子，初值为0。信号量Apple表示盘中有苹果，初值为0。信号量EmptyDish表示盘子为空，初值为1。三个人的操作流程如下所示：

爸爸

P(EmptyDish)

if (rand()%2==0)

{  

  放桔子

  V(Orange)

}

else

{

  放苹果

   V(Apple)

}

儿子

P(Orange)

取桔子

V(EmptyDish)

女儿

P(Apple)

取苹果

V(EmptyDish)

总结：

1.在多线程编程中使用PV操作能忽略代码具体的实现细节，这样确保总体思路的正确性。

2.分析PV操作时紧紧抓住同步和互斥；

同步主要分析：谁在等待？等待什么？分析清楚了，同步就出来了；

互斥主要分析：那些资源是共享的，共享资源需进一步思考有没有必要互斥，比如果盘问题中果盘是共享资源，但是果盘操作并不需要互斥；

pv操作是对信号量s的操作,最初由著名的计算机科学家Dijkstra提出,这里的phev是荷兰语,一个对应减一操作,一个是加一操作.在理论界称为p和v,这个是实现的方法,在工程上就是wait和signal,这个是操作的名称,内部实现是一样的,可读性更好

这个是wait函数的实现,也就是p操作,信号量减一;

这个是signal操作,对信号量加一;

后面使用wait和signal代替p和v;wait和signal必须是原子操作(在这个操作执行的过程中不允许发生中断切换,整个操作必须完整的执行). 这个是它上课演示的例子:

mutex在英文中的意思是互斥.
一个进程独自执行

1. mutex最初为1,执行wait函数,先判断循环s<=0,不成立,执行减一操作,然后结束wait操作;,返回,进入临界区,此时mutex的值是0
2. 然后执行signal操作,mutex的值又变成1.
   mutex具有锁的功能,一个进程进入临界区,就会将mutex置为0,出了临界区把它变为1,0表示加锁,1表示解锁.

多个进程
3. 首先都会执行wait操作,但是因为wait操作,也就是p操作是一个原子操作,所以只能有一个进程在调用wait的时候mutex是1, 然后把这个信号量mutex置为0,相当于这个进程进行了加锁,其它的进程在循环判断的时候信号量mutex的值是0,循环条件成立,所以会在循环那个位置一直等待,也就是在wait函数那里一直等待,直到将mutex置为0的那个进程执行完毕,通过signal操作将mutex重新置为1,相当于解锁,此时前面在wait函数中等待的一个进程可以结束循环,将mutex重新置为0,这个新的进程获得了锁.

具有Counting semaphore(计数信号量)功能,将mutex设置为2的话,可以同时有两个进程进入到临界区中,控制进入临界区的进程的数量.信号量在整个过程中不是只有1和0两种状态.将初始的mutex设置为1,那么只有两种状态,称为Binary semaphore(二制信号量),就是一个互斥锁的特性,信号量是一种包含性的设计.

信号量的实现.

wait个signal操作是一个原子操作,硬件指令尽量原始化,尽量简单,指令的分类:RISC和CISC.信号量不是通过硬件系统直接实现的,而是通过操作系统借助于软件的方法来实现的.硬件提供了两种最基本的支持,Disable/Enable Interrupts(开关中断)和TestAndSet().

对于不能进入临界区的线程,会一直处在死循环中,CPU会一直被占用消耗,不做任何有意义的操作,这是一种浪费,这种无意义的等待称为Busy waitting(忙等),.忙等就是CPU不停的做一件毫无意义的事情,只是在等待某一个事件的发生,但是对CPU处于占用状态.这种设置实现的锁被称为
spin lock(自旋锁).

忙等处于run或者ready状态,

解决的方法是将忙等放在等待wait状态,知道锁被解开再唤醒.

重新定义信号量,信号量是一个结构,有两个部分组成,一个是一个值,一个是一个表示进程的PCB类型的指针,哟个这个指针来构造一个链表,穿起来等待的进程,当信号量发生变化时,从这个连上选择一个进程唤醒.避免忙等,通常将等待的设备穿起来.

有两个操作,一个Block(阻塞进程),一个Wakeup(唤醒进程)

基于Block和Wakeup的wait和signal的实现:

对比原来的实现:

原来的wait是先等再执行减操作,现在是先减再执行等操作,有区别,但是区别不大.同一种操作的不同实现.

以二制信号量为例进行分析:

初始的时候value的值是1,先执行减一操作,value的值变成0,然后判断当前的value的值是否小于0,如果小于0就把当前的进程加入到链表的尾部,然后执行block将当前的进程阻塞,进入waitting状态;如果条件小于0不成立,就结束wait操作,进入临界区.

当第二个进程进入时,此时的value的值是0,先执行减一操作,value的值变成-1,-1<0,条件成立,将当前进程添加到链表的尾部,然后让当前的进程处于waitting状态;

当第三个进程进入时,此时value的值是-1,先执行减一操作,此时value的值变成-2,-2<0,再将当前的进程加入到链表的尾部,同时让当前的进程进入waitting等待状态.

第四个第五个…每个进程进来先减一,判断小于0,将当前进程加入到链表的尾部,然后将当前的进程设置为等待状态

当value<0的时候,value的值的绝对值就是链表上的进程的个数.

分析解锁操作:

首先将value的值加一,然后判断value的值是否<=0.
如果value的值在前面加一后大于1,说明最开始value的值是0,也就是此时的链表上没有其它使用这个信号量的处于等待的进程;当value加一后仍然小于等0,说明此时一定还有其他进程等着这个信号量,然后从链表中取出一个进程,然后通过wakeup方法把这个进程唤醒,进程醒来后就退出了,获得了信号量,进入了临界区.

三类典型的问题:

• 生产者—消费者问题
• 读者—写者问题
• 哲学家就餐问题

• 生产者–消费者问题(最典型的问题)

最简单情形的描述:

两个进程,一个生产者,一个消费者,生产者产生数据,将数据放到两个进程共享的缓冲区中,消费者从缓冲区中取出数据,对数据进行消费(处理).

一个进程自己生产消费和变成两个进程一个生产一个消费,两者的并行性不同.生产者只要生产,消费者只要缓冲区有数据就可以消费.把串行的变成并行的,两两之间构成生产者-消费者,类似于计组中的流水线.流水线上每个组件的数目需要根据每个环节的难度强度.

缓冲区n个

定义三个信号量,mutex,full和empty,full表示有数据的格子的个数,初始时候没有数据,empty表示空的格子的个数.

生产者:

消费者:

mutex的作用:
保护进程共享缓冲区数据的作用,对共享的公共资源进行保护,保护buffer,获得互斥锁才能操作,完成操作后解锁.

最开始生产之生产,empty是n,wait(empty)不会阻塞,empty减一,进入缓冲区写数据,空格少了一个;
多个生产者生产数据,第n+1个生产者wait(empty)会阻塞.
保证不会出现多个生产者像一个格子写数据.