生产者、消费者问题
1、互斥关系:生产者进程和消费者进程对缓冲池的访问互斥。
2、同步关系:缓冲池未满生产者才能向其中放入产品;缓冲池非空消费者才能从其中取出产品。
1. 利用记录型信号量解决
semaphore mutex = 1, empty = n, full = 0; // 分别代表对缓冲池互斥访问,缓冲池中空缓冲区数量和满缓冲区数量
cobegin
producer() {
while(true){
生产一个产品
Swait(empty, mutex);
向缓冲池放入一个产品
Ssignal(mutex, full);
}
}
consumer() {
while(true){
Swait(full, mutex);
从缓冲池取走一个产品
Ssignal(mutex, empty);
消费一个产品
}
}
coend
2. 利用AND信号量解决
semaphore mutex = 1, empty = n, full = 0;// 分别代表对缓冲池互斥访问,缓冲池中空缓冲区数量和满缓冲区数量
cobegin
producer() {
while(true){
生产一个产品
wait(empty);
wait(mutex);
向缓冲池放入一个产品
signal(mutex);
signal(full);
}
}
consumer() {
while(true){
wait(full);
wait(mutex);
从缓冲池取走一个产品
signal(mutex);
signal(empty);
消费一个产品
}
}
coend
哲学家进餐问题
只有互斥关系,没有同步关系
三种解决方式
- 至多只允许4个人同时拿起左边的筷子,确保至少一个人能够吃上饭;
- 只有左右两边的筷子都能使用时,才允许拿起筷子进餐;
- 奇数号哲学家先拿左边的筷子再拿右边的筷子,偶数号哲学家先拿右边的筷子再拿左边的筷子;
至多4人同时拿起左边筷子
semaphore chopstick = {1, 1, 1, 1, 1}; // 每根筷子对应一个互斥信号量
semaphore count = 4; // 至多4人同时拿起左边筷子
cobegin
Pi() {
while(true) {
思考
wait(count); // 同时拿起左边筷子的人不能超过4个
wait(chopstick[i]); // 拿起左边的筷子
wait(chopstick[(i+1)%5]); //拿起右边的筷子
吃饭
signal(chopstick[(i+1)%5]);
signal(chopstick[i);
signal(count);
}
}
coend
只有左右两边的筷子都能使用时,才允许拿起筷子进餐
semaphore chopstick = {1, 1, 1, 1, 1}; // 每根筷子对应一个互斥信号量
cobegin
Pi() {
while(true){
思考
Swait(chopstick[i], chopstick[(i+1)%5]);
吃饭
Ssignal( chopstick[(i+1)%5], chopstick[i]);
}
}
coend
奇数号哲学家先拿左边的筷子再拿右边的筷子,偶数号哲学家操作相反
semaphore chopstick = {1, 1, 1, 1, 1}; // 每根筷子对应一个互斥信号量
cobegin
Pi() {
while(true){
思考
if (i % 2 == 1) { // 奇数号科学家先左后右
wait(chopstick[i]);
wait(chopstick[(i+1)%5];
吃饭
signal(chopstick[(i+1)%5];
signal(chopstick[i]);
}
else {// 奇数号科学家先右后左
wait(chopstick[(i+1)%5];
wait(chopstick[i]);
吃饭
signal(chopstick[i]);
signal(chopstick[(i+1)%5];
}
}
}
coend
读者、写者问题
互斥关系:读写互斥、写者互斥
我们还需要一个rcount
整形变量记录读者的数量用来维持读写互斥,为实现对其互斥访问,还需要一个互斥信号量。
记录型信号量思路
int rcount = 0; // 记录读者数量
semaphore rmutex = 1, wmutex = 1; // 对rcount互斥访问信号量,写者互斥信号量
cobegin
Reader() {
while(true){
wait(rmutex);
if (rcount == 0) {
wait(wmutex);
}
rcount += 1;
signal(rmutex);
读操作
wait(rmutex);
rcount -= 1;
if (rcount == 0) {
signal(wmutex);
}
signal(rmutex);
}
}
Writer() {
while(true){
wait(wmutex);
写操作
signal(wmutex);
}
}
coend
信号量集解决至多只允许RN个读者在读
引入一个新的信号量L,初始值为RN,每当有读者进入时通过wait(L,1,1)让L减1,有RN个读者进入时,L为0,无法进入。
int RN;
semaphore L = RN, mx = 1; // L记录还能进入得读者数量,mx实现读写互斥和写者间互斥
cobegin
Reader(){
while(true){
Swait(L, 1, 1); // L减一
Swait(mx, 1, 0); // 开关,mx为1时可以读,mx为0代表在写
读操作
Ssignal(L,1);
}
}
Writer(){
while(true){
Swait(mx, 1, 1; L, RN, 0); // 只有无写者操作进行(mx=1)以及没有读者操作进行(L=RN)时才能进行写操作
写操作
Ssignal(mx, 1);
}
}
coend
三种特殊的信号量集
-
Swait(S,d,d)
,只有一个信号量S,每次只允许申请d个资源,资源数少于d个时不予分配; -
Swait(S,1,1)
,S>1时,相当于一般的记录型信号量;S=1时,相当于互斥信号量; -
Swait(S,1,0)
,相当于一个开关,S>=1时允许多个进程(读者)进入临界区;S=0时,阻止任何进程进入临界区;