互斥与同步

信号量

信号量：只能进行三种操作，即初始化，递减和增加，这三种操作都是原子操作，递减相当于阻塞一个进程，递增相当于解除一个进程的阻塞。

互斥量：类似二元信号量，关键区别在于为其加锁（置0）和解锁（置1）的进程必须为同一个进程

条件变量：用来阻塞进程或线程，知道特定的条件为真

管程：

事件标志：

信箱/信息：

自旋锁：

强信号量：使用先进先出的规则释放进程

弱信号量：没有规定进程从队列移除的信号量

非二元信号量也成为计数信号量，一般信号量

const int n=process_number; semaphore s=1; void P(i) { while(true) { semWait(s); /*临界区*/; semSignal(s); /*其余部分*/； } } void main() { Parbegin(P(1),P(2),...P(n)); }

生产者/消费者问题

缓冲区无限

producer; while(true) { /*生产v*/; b[in]=v; in++; } consumer; while(true) { while(in<=out) /*不做任何事*/; w=b[out]; out++; /*消费w*/; }

二元信号量（无限缓冲区）

int n;//n=in-out binary_semaphore s=1;//判断临界区是否为空 binary_semaphore delay=0;//同步缓冲区。告知对方缓冲区情况 void producer() { while(true) { produce(); semWaitB(s); append(); n++; if(n==1) semSignalB(delay); semSignalB(s); } } void consumer() { semWait(delay); while(true) { semWaitB(s); take(); n--； semSignalB(s);//这个时候生产者可以进入缓冲区 consume(); if(n==0)semWaitB(delay);//会发生死锁 } } void main() { n=0; parbegin(producer,consumer); }

计数信号量（缓冲区无限）

semaphore n=0;//控制“超前消费”，同步信号量 semaphore s=1;//控制进入临界区 void produce() { while(true) { produce(); semWait(s); append(); semSignal(s); semSignal(n); } } void consumer() { while(true) { semWait(n);//先同步信号量 semWait(s); take(); semSignal(s); consume(); } }

缓冲区有限

producer; while(true) { /*生产v*/; while() b[in]=v; in++; } consumer; while(true) { while(in<=out) /*不做任何事*/; w=b[out]; out++; /*消费w*/; }

计数信号量

semaphore n=0;//控制“超前消费”，同步信号量 semaphore s=1;//控制进入临界区,异步信号量通常置为1 semaphore e=sizeofbuffer; void produce() { while(true) { produce(); semWait(e); semWait(s); append(); semSignal(s); semSignal(n); } } void consumer() { while(true) { semWait(n);//先同步信号量 semWait(s); take(); semSignal(s); semSignal(e); consume(); } }

读者/写者问题

多个读者可以同时读取数据，多个写者不能同时写数据。除了第一个读者后续读者不需要申请进入临界区可以直接进入

读者： while(true) { P(mutex);//读者进入，申请修改读者数量 readcount++; if(readcount==1) P(w); V(mutex); P(mutex);//读者离开，，申请修改读者数量 readcount--; if(readcount==0) V(w); V(mutex); } 写者：//可能会产生饥饿 while(true) { P(w); 写 V(w); } 解决办法一：写者优先方案一 相当于排队时写者可以一起连续排，读者不行 读者： while(true) { P(S); P(mutex);//读者进入，申请修改读者数量 readcount++; if(readcount==1) P(w); V(mutex); V(S); 读； P(mutex);//读者离开，，申请修改读者数量 readcount--; if(readcount==0) V(w); V(mutex); } 写者： while(true) { P(wmutex);//写者进入，申请修改写者数量 writecount++; if(writecount==1) P(S); V(wmutex); P(w); 写 V(w); P(wmutex);//写者离开，申请修改写者数量 writecount--; if(writecount==0) V(S); V(wmutex); } 解决方案：写者优先方案二 读者： while(true) { P(Z); P(S); P(mutex);//读者进入，申请修改读者数量 readcount++; if(readcount==1) P(w); V(mutex); V(S); V(Z); 读； P(mutex);//读者离开，，申请修改读者数量 readcount--; if(readcount==0) V(w); V(mutex); } 写者： while(true) { P(wmutex);//写者进入，申请修改写者数量 writecount++; if(writecount==1) P(S); V(wmutex); P(w); 写 V(w); P(wmutex);//写者离开，申请修改写者数量 writecount--; if(writecount==0) V(S); V(wmutex); } int readcount; semaphore x=1,wsem=1;