【操作系统】 经典的进程同步问题
生产者-消费者问题
一组生产者和一组消费者公用一段缓冲区, 生产者不断地生产产品放入缓冲区, 只有当缓冲区未满时生产者才能放入产品,否则需要等待. 消费者不断地从缓冲区拿出产品, 只有当缓冲区非空时才能拿出产品, 否则也需等待. 由于缓冲区为临界资源, 所以需要生产者和消费者对其互斥访问.
1. 利用记录型信号量解决生产者-消费者问题
利用empty和full信号量分别表示缓冲区空和满的数量, 用mutex实现多个进程对缓冲区的互斥访问.
代码描述
int in=0,out=0;
item buffer[n];
semaphore mutex =1,empty = n,full = 0;
void producer(){
do{
producer an item nextp;
···
wait(empty);
wait(mutex);
buffer[in] = nextp;
in = (in+1)%n;
signal(mutex);
signal(full);
}while(TRUE)
}
void consumer(){
do{
wait(full);
wait(mutex);
nextc = buffer[out];
out = (out+1) %n;
signal(mutex);
signal(empty);
}while(TRUE)
}
注:
- 每个程序中的wait(mutex)和signal(mutex)需要成对出现.
- 不同程序中对empty和full的wait和signal也需成对出现
- 多个wait顺序不能颠倒, 否则可能会引起死锁.
2. 利用AND信号量解决生产者-消费者问题
用 Swait(empty, mutex) 替换wait(empty) 和wait(mutex);
用 Ssignal(mutex, full) 来替代signal(mutex) 和 signal(full)等
将成对出现的wait()和signal()用Swait()和Ssignal()代替
3. 利用管程
首先建立一个管程命名为producerconsumer , 其中包括两个过程
- put(x), 生产者利用该过程将生产的产品放入缓冲池, 并利用count表示已有产品数目, 如果count >= N时表示缓冲池已满需等待
- get(x), 消费者利用该过程取出产品到x, 如果count <= 0 表示缓冲池已空, 需要等待.
并建立condition notfull和notempty条件变量, cwait和csignal过程对其操作
- cwait(condition) 当前进程因为condition原因被阻塞, 将自己插入到condition的等待队列上, 并释放管程, 直到X的条件变化.
- csignal(condition) 唤醒在cwait执行后阻塞在条件condition队列上的一个进程, 如果为空则不操作
管程可描述如下
Monitor producerconsumer
{
item buffer[N];
int in, out;
condition notfull, notempty;
int count;
public:
void put(item x)
{
if(count >= N)
cwait(notfull);
buffer[int] = x;
int = (in + 1) % N;
count++;
csignal(notempty);
}
void get(item x)
{
if (count <= 0)
cwait(notempty);
x = buffer[out];
out = (out + 1) % N;
count--;
csignal(notfull);
}
{
in = 0;
out = 0;
count = 0;
}
}PC;
生产者和消费者可描述为
void producer()
{
item x;
while(TRUE)
{
...
produce an item in nextp;
PC.put(x);
}
}
void consumer()
{
item x;
while(TRUE)
{
item x;
while(TRUE)
{
PC.get(x);
consume the item in nextc;
....
}
}
}
哲学家进餐问题
五个哲学家共用一张圆桌, 分别坐在周围的五把椅子上, 在桌上有5个碗和五个筷子.
一个哲学家进行思考, 饥饿时便试图取用其左右最靠近他们的筷子, 只有他拿到两只筷子才能进餐, 进餐完后放下筷子继续思考.
1. 利用记录型信号量解决哲学家进餐问题
经过分析可知, 桌子上的筷子为临界资源, 同一时间只允许一个哲学家使用.
设置五个信号量构成的数据表示五根筷子
semaphore chopstack[5]= {1,1,1,1,1}
第i位哲学家的活动可以描述为
do{
wait(chopstack[i]);
wait(chopstack[(i + 1) % 5];
eat
signal(chopstack[i]);
signal(chopstack[(i + 1) % 5);
}while(TRUE);
假设五位哲学家同时饥饿并同时拿起了左边的筷子, 之后再去拿右边的筷子时, 会导致一个严重的问题.
因为他们桌子上已经没有筷子了, 五个哲学家只会无限期的等待. 对于这样的死锁问题 可以采用如下的解决方法
- 最多只允许四位哲学家去拿左边的筷子, 从而能够保证一定有一位哲学家可以就餐, 并在就餐完毕后释放两只筷子, 从而避免死锁.
- 只有哲学家同时获的了左边和右边的筷子时他才能继续进餐, 否则他要放下所有筷子.
- 规定奇数号的哲学家先拿他左边的筷子, 偶数号的哲学家先拿右边的筷子, 这样总会有一个哲学家获得两个筷子而避免死锁.
2. 利用AND信号量机制解决哲学家就餐问题
如同上述的第二种解决方法 , 只有一次获取了两个筷子才能继续进餐, 否则要放下所有的筷子.
semaphore chopstack[5]= {1,1,1,1,1}
do{
...
think
Swait(chopstick(i + 1) % 5, chopstack[i]);
eat
...
Signal(chopstick(i + 1) % 5, chopstack[i]);
}
读者写者问题
一个数据文件可以被多个进程共享, 把只要读的进程成文"reader", 把其他进程成为"writer".
因为读操作不会导致文件数据混乱, 而写操作会引起读写混乱.
所以只允许多个reader读进程读问同一个资源.
不允许一个writer写资源而其他reader读资源. 或是多个writer同时写资源.
利用记录型信号量解决读者写者问题
因为读写互斥 写写互斥, 读读不互斥, 所以需要一个wmutex来限制写操作. 设置一个readcount来表示正在读的reader数量,
reader开始时只有readcount = 0 时获取一次wmutex即可,之后readcount++, 结束时readcount–, 如果readcount = 0 时才释放wmutex.
因为readcount也需要互斥访问, 所以对相应的readcount++ 和readcount–操作也需要互斥信号量rmutex
semaphore remutex = 1, wmutex = 1;
int readcount = 0;
void reader()
{
do {
wait(rmutex);
if(readcout == 0)
wait(wmutex);
readcount++;
signal(remutex);
. ....
perform read operation;
...
wait(remutex);
readcount--;
if(readcount == 0)
signal(wmutex);
signal(rmutex);
}while(TRUE);
}
void wirter()
{
do{
wait(wmutex);
perform write opertion;
signal(wmutex);
}while(TRUE);
}
参考文献
计算机操作系统第四版