PRELOADER

当前文章 : 《进程同步之信号量机制》

10/8/2019 —— 

  操作系统 

进程同步之信号量机制

锁机制的弊端

有开锁和关锁原语，任何想进入临界区的进程都必须不停的循环检查锁的值，等待其变成0或者false。效率低下，浪费CPU资源。

P/V操作

P操作：

P(s):将信号量s的值减1，若结果小于0，则调用P(s)的进程被阻塞，并进入信号量s的阻塞队列；若结果大于等于0，则调用P(s)的进程继续执行。

V操作：

V(s):将信号量s的值加1，若结果小于等于0，则调用V(s)的进程从该信号量的阻塞队列中释放，唤醒一个处于等待状态的进程，将其转换为就绪状态，调用V(s)的进程继续运行；若结果大于0，则调用V(s)的进程继续运行。

总结：

P操作意味着进程申请一个资源，求而不得则阻塞进程；V操作意味着释放一个资源，若此时还有进程在等待获取该资源，则被唤醒。

若信号量的值为正数，该正数表示可对信号量进行的P操作次数，即可用的资源数。

若信号量的值为负数，其绝对值表示有多少个进程申请该资源而又不能得到，即信号量阻塞队列中等待该资源的进程个数。

生产者-消费者问题

描述：

n个生产者进程和m个消费者进程,连接在一块长度为k个单位的有界缓冲区上(故此问题又称有界缓冲问题)。其中,Pi和Ci都是并发进程，只要缓冲区未满，生产者P,生产的产品就可送人缓冲区;只要缓冲区不空,消费者进程C,就可从缓冲区取走并消费产品。

代码：

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
item B[k];//缓冲区，长度k
semaphonre empty = k;//可用的空缓冲区数
semaphonre full = 0//缓冲区内可用的产品数
semaphonre mutex = 1;//互斥信号量
int in = 0;//缓冲区放入位置
int out = 0;//缓冲区取出的位置

cobegin
//生产者生产产品
process procuder_i(){
     while(true){
          produce();//生产一个产品
          P(empty);//使用缓冲区的一个位置
          P(mutex);//互斥信号量，同时只能有一个进程对缓冲区进行操作
          append to B[in];//放入产品
          in = (in+1)%k;//更新缓冲区指针
          V(mutex);//释放互斥信号量
          V(full);//可用产品数+1
     }
}
//消费者消费产品
process consumer_j(){
     while(true){
          P(full);
          P(mutex);
          take() from B[out];//拿出产品
          out = (out+1)%k;
          V(mutex);
          V(empty);
          consume();
     }
}
coend

读者-写者问题

描述：

  • 允许多个读者进程同时读文件;
  • 只允许一个写者进程写文件;
  • 任何一个写者进程在完成写操作之前不允许其他读者或写者工作;
  • 写者执行写操作前,应让已有的写者和读者全部退出。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int readcount = 0; //读进程计数器
semaphore ws = 1,mutex = 1;
cobegin
process reader_i(){
     P(mutex);//对readcount的修改要互斥
     readcount++;
     if(readcount==1)P(ws);//只要有一个读者，就阻塞写者
     V(mutex);
     读文件;
     P(mutex);
     readcount--;
     if(readcount==0)V(ws);//没有读者，释放对写者的阻塞
     V(mutex);
}
process writer_j(){
     P(ws);//有写者，对读者和写者都互斥
     写文件;
     V(ws);
}
coend

哲学家就餐问题

描述：

有5个哲学家围坐在一圆桌旁,桌中央有一 盘通心面，每人面前有一只空盘子，每两人之间放一只筷子，如图2.12所示。每个哲学家的行为是思考，感到饥饿,然后吃通心面。为了吃面，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左手边和右手边去取筷子。

最简单解法：

1
2
3
4
5
6
7
8
void philmac(int i){
     思考;
     取chopsticks[i];
     取chopsticks[(i+1)%5];
     吃面;
     放chopsticks[i];
     放chopsticks[(i+1)%5];
}

引发问题：

若每个哲学家都取一个筷子，则每个哲学都会等待自己旁边的哲学家放下筷子，从而陷入死锁。

解决死锁的几种方法：

  • 至多允许4个哲学家同时吃面；
  • 奇数号先取左手边的筷子，偶数号取右手边的筷子；
  • 每个哲学家取到手边的两只筷子才吃，否则一只筷子也不取；