信号量、PV操作以及四个经典进程同步问题

今天操作系统上完了一章，讲了几个经典的进程同步问题及其变形，代码阅读理解十分烧脑，课上反应不过来课下再细看，尽量将部分理解整理在这里。

信息量

本质

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

功能

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

PV操作

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

P（S）：
①将信号量S的值减1，即进行S = S-1；
②如果S < 0，则该进程进入阻塞队列；
③如果S >= 0, 则该进程继续执行。

执行一次P操作其实就是意味请求分配一个资源，所以针对②和③来说就好理解了，当信号量的值小于0，那么就表示没有可用资源，那么进程就只能进行等待其他拥有该资源的进程释放资源之后，才能进行执行；当信号量大于0的时候，那么表示还有足够的资源，所以，当前进程就可以继续执行。

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

执行一次V操作其实就是意味释放一个资源，所以针对②和③来说就好理解了，当信号量的值大于0，那么就表示有可用资源，那么表示信号量的资源足够进程进行申请，就不需要将进程进行放入到阻塞队列中；而当信号量小于0的时候，就表示针对这个信号量，还有其他的进程是已经进行了申请信号量的操作，而只是之前是无法满足进程获取资源的，简单点说，就是表示阻塞队列中还有其他的进程是执行了P操作，在等待信号量，所以，这样的话，就讲阻塞队列中的第一个等待信号量的进程进行处理即可。

经典进程同步问题

下面就是几个利用信号量来解决的经典进程同步问题，上课感觉十分烧脑，现在再重新审视一下。

一、生产者-消费者问题（有界缓冲区问题）

问题描述
生产者消费者问题本来是多线程同步问题，这里作为多进程考虑。简单来说就是两个进程共享固定大小缓冲区在实际运行时候会发生的问题。一个作为生产者产生数据到缓冲区中，一个作为消费者消耗这些数据。问题的关键是保证生产者不会再缓冲区满时加入数据，消费者也不会在缓冲区空时消耗数据。

解决思路
采用进程间通信的方式，即通过信号量来控制两个进程，使得对方在合适的时机进行休眠或唤醒。但要注意避免出现死锁，即两个进程都进入休眠且都在等待对方唤醒自己。

伪代码实现
1.只有一个缓冲区

2.多个缓冲区，且生产者消费者进程若干

items代表缓冲区已经使用的资源数，spaces代表缓冲区可用资源数
mutex代表互斥锁
buf[10] 代表缓冲区，其内容类型为item

in、out代表第一个资源和最后一个资源

var items = 0, space = 10, mutex = 1;
var in = 0, out = 0;
item buf[10] = { NULL };

producer {
    while( true ) {
        wait( space );  // 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前
        wait( mutex );  // 保证在product时不会有其他线程访问缓冲区

        // product
        buf.push( item, in );  // 将新资源放到buf[in]位置 
        in = ( in + 1 ) % 10;

        signal( mutex );  // 唤醒的顺序可以不同
        signal( items );  // 通知consumer缓冲区有资源可以取走
    }
}

consumer {
    while( true ) {
        wait( items );  // 等待缓冲区有资源可以使用
        wait( mutex );  // 保证在consume时不会有其他线程访问缓冲区

        // consume
        buf.pop( out );  // 将buf[out]位置的的资源取走
        out = ( out + 1 ) % 10;

        signal( mutex );  // 唤醒的顺序可以不同
        signal( space );  // 通知缓冲区有空闲位置
    }
}

不能颠倒两个wait的顺序，否则会出现死锁。例如(调换后)，将consumer的两个wait调换，在producer发出signal信号后，如果producer线程此时再次获得运行机会，执行完了wait(space)，此时，另一个consumer线程获得运行机会，执行了 wait(mutex) ，如果此时缓冲区为空，那么consumer将会阻塞在wait(items)，而producer也会因为无法获得锁的所有权所以阻塞在wait(mutex)，这样两个线程都在阻塞，也就造成了死锁。

二、读者写者问题问题

问题描述

一个数据文件或记录可被多个进程共享。
只要求读文件的进程称为“Reader进程”，其它进程则称为“Writer进程”。
允许多个进程同时读一个共享对象，但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。
“读者–写者问题”是保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。
读者写者问题分为两类：
①读者优先：当存在一个读者时，读者优先，写者会长时间等待。（即若写者在等待过程中有读者进入队列，则优先级会自动高于写者）
②写者优先：当写者提出存取共享对象要求后，已经开始读的进程让其读完，但不允许新读者进入。
③读写公平

解决思路
同样可以采取信号量来解决读写问题，有两种信号量的方法，即记录型信号量和信号量集，这里只先总结记录型信号量的解决方法。

伪代码实现

互斥信号量wmutex: 实现读写互斥、写写互斥，初值为1（类似于缓冲池，只有在第一个读、最后一个读和第一个写时候进行互斥保护）。
整型变量readcount: 表示正在读的进程数目;
由于只要有一个Reader进程在读，便不允许Writer进程写。所以，仅当readcount=0，即无Reader进程在读时，Reader才需要执行Wait(wmutex)操作。若Wait(wmutex)操作成功，Reader进程便可去读，相应地，做readcount+1操作。
同理，仅当Reader进程在执行了readcount减1操作后其值为0时，才需执行signal(wmutex)操作，以便让Write进程写。
互斥信号量rmutex: Reader进程间互斥访问readcount，初值为1（即保护readcount的作用）。

1.读者优先

2.写者优先

这里作下说明，前两个信号量分别是对读写计数器资源作互斥保护后两个信号量是对读写操作分别作互斥保护。而mutexPriority是为了当一个读者进入临界区后，将其余读者卡在远一点的关卡，使得这时有一个写者进入队列等待时，只需等待处于临界区的一个读者完毕即可使用资源，而不需要和其他读者竞争，起一个提权的作用。

三、哲学家进餐问题

问题描述
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭，哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
哲学家进餐问题
解决思路
问题的关键在于如何让一个哲学家拿走左右两个筷子而不造成“死锁”（都拿起左筷子等待抢夺右筷子，自私）、“饥饿”（都拿起左筷子后又同时放下，慷慨）、“干等”（独享，一人吃饭其他人干等着）状态。
解决方法有两种：
①破坏请求条件
②破坏环路

解决方法
1.服务生解法
一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。
2.资源分级解法
另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。

四、睡眠的理发师问题

问题描述

有一个理发师的椅子，和n个顾客的椅子
如果有顾客在椅子上等，那么理发师为他剪发，否则理发师就在自己的椅子上睡觉。
如果理发师在熟睡，那么顾客会叫醒理发师，否则顾客会看有没有空椅子，有的话，他坐下等，否则，他将离开理发店。

解决思路
使用三个信号量。信号量barber表示等待顾客的理发师数，并用作阻塞顾客进程，初值为0；信号量customers表示等待理发的顾客数，并用作阻塞理发师进程，初值为0；信号量mutex用于互斥访问count，初值为1，count是一个共享变量，对它操作时必须加锁。
控制变量count记录等待理发的顾客数，与customers相同，只因为customers是信号量无法被读出值。

伪代码实现

barber()
begin
         while(TRUE); //理完一人,还有顾客吗?
        P(cutomers); //若无顾客,理发师睡眠
        P(mutex); //进程互斥
        waiting := waiting – 1; //等候顾客数少一个
        V(barbers); //理发师去为一个顾客理发
        V(mutex); //开放临界区
        cut-hair( ); //正在理发
end


customer()
begin
          P(mutex); //进程互斥
          if (waiting<n)
         begin
             waiting := waiting+1; // 等候顾客数加1
             V(customers); //必要的话唤醒理发师
             V(mutex); //开放临界区
             P(barbers); //无理发师, 顾客坐着养神
             get-haircut( ); //一个顾客坐下等理/
        end
else
V(mutex); //人满了,走吧!
end

整理到这个问题时候我已经很迷了，对于mutex的作用一直不理解，现在暂时认为是保护count（waiting）的作用吧，日后再回头看。

这四个经典问题整理完毕用了快一上午的时间…自己实在太菜有些上课理解了的东西现在就不清楚了，还要查各种资料，引用的参考资料过多这里就不列出来了…这里仅供日后回顾学习参考使用。