一、信号量
- 信号量是一个与队列有关的整型变量。
- 可以初始化成非负数；
- semWait操作使信号量减1。若值为负数，则执行semWait的进程阻塞，否则继续执行；
- semSignal操作使信号量加1。若值小于或等于0，则被semWait操作阻塞的进程被解除阻塞。
信号量原语semWait和semSignal的定义
strcut semaphore{
int count;
aueueType queue;
};
void semWait(semaphore s) {
s.count--;
if(s.count < 0) {
place this process in s.queue;
block this process;
}
}
void semSignal(semaphore s) {
s.count ++;
if(s.count <= 0) {
remove a process P from s.queue;
place process P on ready list;
}
}
信号量实现互斥
const int n;
semaphore s = 1;
void P(int i) {
while(true) {
semWait(s);
operate;
semSignal(s);
}
}
void main() {
parbegin(P(1), P(2), ...,P(n));
}
总结
信号量
- 一个信号量可用于n个进程的同步互斥；且只能由semWait、semSignal操作修改。
- 用于互斥时，S初值为1，取值为1~ - (n-1) （相当于临界区的通行证，实际上也是资源个数）
S=1：临界区可用
S=0：已有一进程进入临界区
S<0：临界区已被占用，|S|个进程正等待进入 - 用于同步时，S初值>=0
S>=0:表示可用资源个数
S<0: 表示该资源的等待队列长度
semWait、semSignal操作
- semWait(S)：请求分配一个资源。
- semSignal(S)：释放一个资源。
- semWait、semSignal操作必须成对出现。
- 用于互斥时，位于同一进程内；
- 用于同步时，交错出现于两个合作进程内。
- 多个semWait操作的次序不能颠倒，否则可能导致死锁。
- 多个semSignal操作的次序可任意。
二、生产者/消费者问题
问题描述：
有一个或多个生产者生产某种类型的数据，并放置在缓冲区中；
有一个消费者从缓冲区中取数据，每次取一项；
系统保证避免对缓冲区的重复操作，即任何时候只有一个主体（生产者或消费者）可以访问缓冲区;
缓存已满时，生产者不能继续添加数据；
缓存已空时，消费者不能继续移走数据。
producer:
while(true) {
/* produce item v */
while((in + 1) % n == out) //等待缓存有空位
/* doing nothing */
b[in] = v;
in = (in + 1) % n;
}
consumer:
while(true) {
while(in == out) //此时缓存为空，等待生产者生产放入缓存后才可消费
/* doing nothing */
w = b[out];
out = (out + 1) % n;
/* consume item w */
}
有限缓冲区：
使用信号量解决有限缓冲区生产者消费者问题:
n 表示已生产产品的数量
s 用来控制互斥
e 表示空闲空间数目
semaphore n = 0, s = 1, e = buf - size;
void producer() {
while(true) {
produce();
semWait(e);
semWait(s);
append();
semSignal(s);
semSignal(e);
}
}
void consumer() {
while(true) {
semWait(n);
semWait(s);
take();
semSignal(s);
semSignal(e);
consume();
}
}
例题
- 桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹果。
分析：
生产者－消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类（苹果和香蕉），但每类消费者只消费其中固定的一种产品（儿子消费香蕉，女儿消费苹果）。
数据结构： semaphore dish, apple, banana;
dish: 表示盘子是否为空,用于控制互斥
apple：表示盘子中是否有苹果，初始值为0
banana:表示盘子中是否有香蕉，初始值为0
process father() {
semWait(dish);
put the apple in the dish;
semSignal(apple);
}
process mother() {
semWait(dish);
put the banana in the dish;
semSignal(banana);
}
process son() {
semWait(banana);
get the banana from the dish;
semSignal(dish);
}
process daughter() {
semWait(apple);
get the apple from the dish;
semSignal(dish);
}
- 在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次拣一子，当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试用信号量协调两个进程的并发执行。
分析：
实际上就是两个进程的同步问题，也就是拣了一个白棋子才能拣一个黑棋子，两者成合作关系
数据结构：semaphore s1, s2;
s1 和s2 分别表示可拣白子和黑子，不失一般性，若令先拣白子。初值， s1=1； s2=0；
process p1() {
while(true){
semWait(s1);
Pick a white chessman;
semSignal(s2);
}
}
process p2() {
while(true){
semWait(s2);
Pick a white chessman;
semSignal(s1);
}
}
- 假设一个阅览室有100个座位，没有座位时读者在阅览室外等待；每个读者进入阅览室时都必须在阅览室门口的一个登记本上登记座位号和姓名，然后阅览，离开阅览室时要去掉登记项。每次只允许一个人登记或去掉登记。用信号量操作描述读者的行为。
分析：
实际上是一个非常简单的同步-互斥问题，登记时需要保证互斥，室内人数在100之内时，无需等待，大于100人是，开始需要等待室内有人出来后方可有人入室
数据结构：
strcut {
char name[10];
int number;
} a[100]; //表示进入阅览室的小朋友
semaphore mutex, seatcount;
mutex: 用来控制互斥，初始值为1
seatcount： 对空座位进行计数，初始值为100；
初始化入室人员信息
for(int i = 0; i < 100; i++){
a[i].number = i;
a[i].name = null;
}
process readeri(char readername[]) {
semWait(seatcount); //等待空余作为，若人数未满100，则直接进入，到达100，则等待
semWait(mutex); //控制互斥
/* 进入是登记 */
for(int i = 0; i < 100; i++)
if(a[i].name == null){ //找到名字为空的座位
a[i].name = readername;
break;
}
reader get the seat nember i;
semSiganl(mutex);
go into the reading room and sit down at the seat number i.
/* 离开时登记 */
semWait(mutex);
a[i].name = null;
semSignal(mutex);
semSignal(seatcount);
leave reading room;
}
二、读/写者问题
描述：
有一个由多个进程共享的数据区，一些进程只读取这个数据区中的数据，一些进程只往数据区中写数据。并须满足以下条件：
任意多的读进程可以同时读文件；
一次只有一个写进程可以写文件；
如果一个写进程正在写文件，那么禁止任何读进程读文件。
读者优先
分析：
当一个读进程开始访问数据区时，只要至少有一个读进程正在读，就为读进程保留对这个数据区的控制权，因此，写进程有可能处于饥饿状态。
数据结构：
readcount: 控制wsem的的设置
wsem： 当没有读进程正在读时，第一个试图读的读进程需要在wsem上等待； 当至少有一个读进程在读时，随后的读进程无需等待直接进入。
x: 用于确保readcount被正确更新。
int readcount;
semphore x = 1, wsem = 1;
void reader() {
while (true) {
semWait(x);
readcount++;
if(readcount==1)
semWait(wsem); //如果是第一个读者，则要控制wsem
semSignal(x);
READUNIT();
semWait(x);
readcount--;
if(readcount==0)
semSignal(wsem);
semSignal(x);
}
}
void writer(){
while (true) {
semWait(wsem);
WRITEUNIT();
semSignal(wsem);
}
}
实例：
独木桥问题：东、西向汽车过独木桥。桥上无车时允许一方汽车过桥，待全部过完后才允许另一方汽车过桥。用信号量操作写出同步算法。(提示：参考读者优先的解法)
数据结构：
mutex1/mutex2: 用于确保count1/count2被准备更新
count1/count2: 控制wait的设置
wait: 当没有车同向的车通过独木桥时，第一辆通过的车需要在wait上等待； 当至少有一辆同向的车通过时，随后同方向的车无需等待直接进入。
semaphore wait=1, mutex1=1, mutex2=1;
int count1=0, count2=0;
process P east(){
semWait(mutex1);
count1++;
if(count1==1) semWait(wait);
semSignal(mutex1);
through the singal-log bridge；
semWait(mutex1);
count1--;
if(count1==0) semSignal(wait);
semSignal(mutex1);
}
process P west(){
semWait(mutex2);
count2++;
if(count2==1) semWait(wait);
semSignal(mutex2);
through the singal-log bridge；
semWait(mutex2);
count2--;
if(count2==0) semSignal(wait);
semSignal(mutex2);
}
待整理。。。
