操作系统-经典进程同步问题

经典进程同步问题

关于进程同步有一系列经典问题,比较代表性的有

  • 生产者——消费者
  • 读者——写者
  • 哲学家进餐问题

生产者——消费者问题

  1. 利用记录型信号量解决生产者-消费者问题

假定生产者消费者之间的公用缓冲池具有n个缓冲区,互斥信号量mutex实现诸进程对缓冲池的互斥使用,empty、full表示缓冲池中空缓冲区和满缓冲区的数量。

假设:缓冲池未满,生产者可将消息送入缓冲池;缓冲池未空,消费者则可以从缓冲池取走一个消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// in为进队列的下标,out为消费队列的下标
int in=0,out=0;
// 循环队列
item buffer[n];
// mutex互斥锁,empty:剩余可用的队列空间,full当前已有的产品数量
semaphore mutex=1,empty=n,full=0;
void proceducer(){
do{
// 生产了一个产品nextp
producer an item nextp;
...
// 如果是empty为0,则进程会被放进等待的队列中
wait(empty);
// 获得一个锁的东西,比如此时有消费者在buffer中获取产品,则也会被放进等待队列中,直到被释放
wait(mutex);
// 已取得锁,可以将产品放进in的位置
buffer[in]=nextp;
// 将该buffer当循环队列使用,计算下次放进去队列的下标
in:=(in+1)%n;
// 释放该锁,使消费者可以获得该互斥锁
signal(mutex);
// full表示有多少个产品,signal表示对full++,此时多了一个产品,则唤醒(通知)在等待队列中的消费者可以进行消费了
signal(full);
}while(true);
}

void consumer(){
do {
// 判断队列是否为空,为空则将进程放进阻塞队列中,直到proceducer()有新的产品被生产了,然后通知该阻塞的队列的进程,也就本进程了
wait(full);
// 获取操作队列的锁
wait(mutex);
// 获取产品
nextc=buffer[out];
// 循环队列,获取下一个出队列的下标
out=(out+1)%n;
// 释放队列的锁,通知生产者可以操作队列了
signal(mutex);
// empty++,队列增加了一个位置,通知生产在阻塞队列的进程可以生产了
signal(empty);
// 消费。。
consumer the item in nextc;
} while(true);
}

// main
void main(){
cobegin
proceducer(); consumer();
coend
}
  1. 利用AND信号量解决生存者-消费者问题

几乎与上述描述一致,这里用AND信号量解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// in为进队列的下标,out为消费队列的下标
int in=0,out=0;
// 循环队列
item buffer[n];
// mutex互斥锁,empty:剩余可用的队列空间,full当前已有的产品数量
semaphore mutex=1,empty=n,full=0;
void proceducer(){
do{
// 创建新产品
producer an item nextp;
// AND信号量,这里复习一下Swait是什么
// 一个死循环,然后判断是否所有条件都满足(大于等于1),只要有其中一个条件不满足,就会将该进程放进等待或者阻塞队列中
// 当满足条件了,会对swait中的参数进行减一操作,对empty减一,就是空闲数-1
Swait(empty,mutex);
// 把新生产的产品放进去队列
buffer[in]=nextp;
// 计算下标
in:=(in+1)%n;
// AND信号量的操作,也复习一下
// 对Ssignal中的所有参数进行加一操作
// 并唤醒等待或阻塞的进程
Ssignal(mutex,full);
} while(true);
}

void consumer(){
do {
// 上述一样,当full(未消费的产品数)大于等于1
// 且mutex互斥锁没有被占用时
// 取得资源的使用权,否则阻塞
Swait(full,mutex);
nextc=buffer[out];
out=(out+1)%n;
// 对mutex跟empty进行加一操作,表示释放资源
// 并且唤醒在等待empty跟mutex的进程
Ssignal(mutex,empty);
consumer the item in nextc;
}while(true);
}
  1. 利用管程

在利用管程方法来解决生产者—消费者的问题时,首先为他们建立一个管程,并命名为producerconsumer,简称pc,其中包含两个过程

  1. put(x)过程。将产品放进去缓冲池中,需要count<=N
  2. get(x)过程。从缓冲池中取出一个产品,需要count>1

对于条件变量notfull和notempty,分别有两个过程cwait和csignal对它们进行操作

  1. cwait(condition)过程:当管程被一个进程占用时,其它进程调用该过程时阻塞,并挂在condition的队列上
  2. csignal(condition)过程:唤醒在cwait执行后阻塞的条件condition队列上的进程,如果进程不止一个,则选择其中一个唤醒,队列为空则无操作返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Monitor producerconsumer{
item buffer[N];
int in,out;
// 条件变量
// notfull,没有空余的区域
// notempty,队列为空
condition notfull,notempty;
int count;
public:
void put(item x){
// 当队列中的数据以达到最大值
// 则将本进程放进等待队列中阻塞
if(count>=N)cwait(notfull);
buffer[in]=x;
in=(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);
}
// init
{ in=0;out=0;count=0; }
}PC;

在利用管程解决生产者-消费者时,其中的生产者消费者可描述为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void producer(){
item x;
while(true){
produce an item in nextp;
PC.put(x);
}
}

void consumer(){
item x;
while(true){
PC.get(x);
consume the item in nextc;
}
}

void main(){
cobegin;
producer(); consumer();
coend;
}

哲学家进餐问题

利用记录型信号量解决问题

可以用一个信号量表示一只筷子,五个信号量构成一个数组

1
semaphore chopstick[5]={1,1,1,1,1}

1
2
3
4
5
6
7
8
9
10
11
12
13
do{
// 拿左手边的筷子,如果没有则阻塞
wait(chopstick[i]);
// 拿右手边的筷子,如果没有则阻塞
wait(chopstick[(i+1)%5];

// 拿到筷子了,吃饭。。

// 释放左手边的筷子
signal(chopstick[i]);
// 释放右手边的筷子
signal(chopstick[(i+1)%5];
}

上述解法可保证不会有两个相邻的哲学家同时进餐,但却有可能引起死锁。假如五位哲学家同时极饿而各自拿起左边的筷子时,都将因为无筷子可拿而无限期地等待。对于这样的死锁问题,可采取一下几种解决方法:

  1. 至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用完时能释放他用过的两只筷子,从而使更多的哲学家能够进餐
  2. 仅当哲学家的左、右两只筷子均可用时,才允许他拿起筷子进餐
  3. 规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子,而偶数号哲学家则相反。按照这规定,将是1、2号哲学家竞争1号筷子,3、4号竞争3号筷子。即五位哲学家都先竞争奇数号筷子,获得后再去竞争偶数号筷子,最后总有一位哲学家能获得两只筷子而进餐。

利用AND信号量机制

从上述可以知道,第二个解决方案

  1. 仅当哲学家的左、右两只筷子均可用时,才允许他拿起筷子进餐
1
2
3
4
5
6
7
8
9
10
semaphore chopstick chopstick[5]={1,1,1,1,1}
do {
...
// think
...
Sswait(chopstick[(i+1)%5],chopstick[i]);
// eat
...
Ssignal(chopstick[(i+1)%5],chopstick[i]);
} while(true)

读者-写者问题

也就是对某个文件进行read,write操作,read操作可以多个进程同时执行,但是write只能允许一个进程执行并且此时不允许read操作以及write操作,否则回引起混乱

利用记录型信号量解决问题

为实现reader与writer进程间在读或写时的互斥信号量Wmutex。另外,再设置一个整形变量Readcount表示正在读的进程数目,由于只要有一个reader进程在读,就不允许writer进程去写。因此,仅当readcount=0,reader进程才需要执行wait(wmutex)操作。当reader执行了readcount减1的操作后其值为0时,才需要执行signal(Wmutex),以便让writer进程写操作。因为readcount是一个临界值,所以需要设置一个互斥锁rmutex

注意⚠️:这里注意两个信号量,rmutex表示对readcount临界资源的互斥锁,而wmutex表示对被读写的资源的一个互斥锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 两个信号量
semaphore rmutex=1,wmutex=1;
// 记录获得读锁的进程数
int readcount=0;
void reader(){
do{
// 阻塞等待readcount的互斥锁
wait(rmutex);
// 当readcount为0时,代表没有进程在进行读操作
// 那么有可能此时该资源正在被写
// 所以需要等待该资源的锁
if(readcount==0) wait(wmutex);
// 获得资源的锁后,说明写操作已经结束了
// 可以进行一些操作了
// 对readcount++操作,表示此时多了一个进程进行读操作
readcount++;
// 此时可以将rmutex锁释放了
// 因为同一时间可以有多个进程进行读操作
// 若没有释放rmutex锁的话
// 别的进程则无法获取到该锁
// 进而退化成,读操作也是互斥了的
signal(rmutex);
// ..读操作

// ..读完
// 读完之后获取readcount锁
// 因为需要对readcount进行减1的操作
wait(rmutex);
readcount--;
// 如果当没有进程在读时,那么可以释放该资源的互斥锁了
// 因为只要有1个进程在读,那么就无法进行写操作
// 所以当readcount为0时,则可以释放该锁
// 便可以唤醒writer进程,进行写操作
if(readcount==0) signal(wmutex);
// 对readcount--完后,就可以释放该锁了
signal(rmutex);
}while(true);
}
// writer进程
void writer(){
do{
// 等待该资源的互斥锁
wait(wmutex);
// .. 写操作
// 释放
signal(wmutex);
}while(true);
}

利用信号量集机制解决读者-写者问题

这里与上述的问题不同,它增加了一个限制,最多只允许RN个读者同时读,为此又引入一个信号量L,并赋予其初值RN,通过执行wait(L,1,1)操作来控制读者的数目,每当有一个读者进入时,要先执行wait(L,1,1)操作,使L的值减1。当有RN个读者进入读后,L便减为0,当第RN+1个读者想要进入读时,则会阻塞。

RN: 表示限制的读进程数
mux: 表示对资源的写锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int RN;
semaphore L=RN,mx=1;
void reader(){
do{
// 获取读锁
// 读锁资源总共L个,一次最少获取资源1个,本次获取1个资源
Swait(L,1,1);
// 这里表示所有进程都可以获取锁
// mx--
Swait(mx,1,0);
// 读操作...
// 释放资源
Ssignal(L,1);
}while(true);
}
void writer(){
do{
// 等待读锁,获取全部的读资源锁
Swait(mx,1,1,L,RN,0);
// 写操作...
// 写完释放写锁
Ssignal(mx,1);
}while(true);
}

Swait(S,1,0)当S>=1时,允许多个进程进入某特定区,当S变为0后,则阻止任何进程进入特定区