操作系统 Chap.7 信号量的应用
1. 前文回顾
本部分针对信号量的说明在 Operating System Chap.6 同步机制 中有较为详尽的讲解, 本处仅为简单回顾.
我们在前文中提及了 信号量(Semaphore) 这一重要概念. 它分为以下两类:
- 二元信号量(Binary Semaphore)
- 计数信号量(Counting Semaphore)
此外, 信号量自带的队列机制使得其能够抛却传统互斥锁的忙等机制, 利用系统的阻塞 / 中断机制解决关键区域的问题.
2. 引入
我们从两种问题谈起:
2.1 The Restroom Problem
此即 公共卫生间问题 (有点粗俗哈) , 其问题假设如下:
Given a single-spot restroom, write the function for using the restroom
一个厕所就一个隔间, 写一个该隔间的使用算法.
这其实就是我们上一章节中提及的关键区域的具象化. 我们已经利用信号量解决了这个问题, 用一个二元信号量, 做一个互斥锁即可.
Semaphore S = 1; // shared among customers (processes)
use_restroom() {
wait(S); // try to enter the restroom; = lock()
Use the restroom //critical section
signal(S); // leave the restroom; = unlock()
}
2.2 The Bar Problem
此即 酒吧问题 , 其问题假设如下:
Capacity = 100
Many customers try to enter the bar concurrently
Please write code to make sure customers<=100
哎, 问题不一样了, 现在有100个位子, 要保证进入酒吧的人能够始终小于等于100个, 写一个算法.
这时候上文的二元信号量 / 亦或互斥锁, 就不是很好用了, 它只能保证对某个资源的互斥利用, 但对于这种大量资源的管理问题, 并不是它的专项.
3. 信号量的使用
我们有问题了, 现在进入本文的正题, 信号量的多种适用场景.
3.1 确保执行顺序(Enforcing Orders)
在这里, 我们给两个例子:
Process 0: Statment A;
Process 1: Statment B;
如何保证语句A在语句B之前执行?
Semaphore S = 0; //Shared
//Process 0
A;
signal(S);
//Process 1
wait(S);
B;
复杂一点?
- Process 0:
- Statment A1;
- Statment A2;
- Process 1:
- Statment B1;
- Statment B2;
确保执行顺序: A1 -> B1 -> B2 -> A2
Semaphore S1 = 0;
Semaphore S2 = 0;
//Process 0
A1;
signal(S1);
wait(S2);
A2;
//Process 1
wait(S1);
B1;
B2;
signal(S2);
通过多个信号量的组合使用, 能够实现不同进程中不同语句的顺序执行.
3.2 消费者问题(Producer - Customer Problem)
考虑本章中最重要的主题, 消费者问题 .
One slot; multi Producers keep producing items, while multi Consumers keep consumes items
我们线考虑比较简单的情况, 一个槽位, 多个生产者在生产, 而多个消费者也在消耗, 怎么控制?
我们将问题拆分一下, 就能想明白这个问题:
- 对于生产者, 它要干啥? 一直生产, 直到槽位被占满, 阻塞.
- fillSlot();
- 对于消费者, 它要干啥? 清空槽位上的物品, 直到槽位空, 阻塞.
- removeItem();
Semaphore S_slot = 1;
Semaphore S_item = 0;
//Producer
while(true){
wait(S_slot);
fillSlot();
signal(S_item);
}
//Customer
while(true){
wait(S_item);
removeItem();
signal(S_slot);
}
好的, 现在问题更复杂了, 多个槽呢?
这被称为 Multi-slot Producer-Customer Problem . 是个挺重要的问题.
由于槽位变多了, 显然需要一个新的数据结构进行对多槽位的表达:
最合适的数据结构是一个环状结构, 首尾相接.(循环链表)
现在我们把多槽表示出来, 生产者和消费者要干的事情就跟之前没有区别了.
//Producer
sem_wait(&slots);
mutex_lock(&mutex);
buffer[pi] = data;
pi = (pi + 1) % N;
mutex_unlock(&mutex);
sem_post(&items);
//Customer
sem_wait(&items);
mutex_lock(&mutex);
result = buffer[ci];
ci = (ci +1) % N;
mutex_unlock(&mutex);
sem_post(&slots);
正规一点的代码如下:
monitor ProducerConsumer
condition cv_full, cv_cempty;
int count;
procedure produce();
{
while (count == N)
wait(cv_full); // if buffer is full, block
put_item(widget); // put item in buffer
count = count + 1; // increment count of full slots
if (count == 1) signal(cv_empty); // if buffer was empty, wake consumer
}
procedure consume();
{
while (count == 0)
wait(cv_empty); // if buffer is empty, block
remove_item(widget); // remove item from buffer
count = count - 1; // decrement count of full slots
if (count == N-1) signal(cv_full); // if buffer was full, wake producer
}
3.3 Barrier Problem
亦称 栅栏问题 .
Goal: given a number, N, of processes, each process has to wait at some point of its program until all processes reach the point
给N个进程, 每个进程在某一点, 必须等待, 直到其他所有的进程都运行到这个点为止.
n = the number of threads
count = 0
mutex = Semaphore(1)
barrier = Semaphore(0)
Barrier() {
wait(mutex)
//Operations to shared data
count += 1
if (count == n)
for( i=0; i<n; ++i)
signal(barriar)
signal(mutex)
wait(barriar)
}
另一种解决方案如下:
n = the number of threads
count = 0
mutex = Semaphore(1)
barrier = Semaphore(0)
Barrier(){
wait(mutex)
count = count + 1
signal(mutex)
if count == n:
signal(barrier)
wait(barrier)
signal(barrier)
}
考虑一下, 这种方案中, 有没有可能两个进程运行到if语句, 都发现count == n?
这种情况是可能的, 但事实上, 多出的一次signal操作不会引起任何bug, 因为这代表着两个进程都临近停止点.
如果实在看不惯这种事情的发生, 可以将if语句放入mutex的管理区域.
3.4 Writer-Reader Problem
即 一写多读问题 , 这事在操作系统中可太常见了对吧.
- 读线程只读
- 写线程会编辑
- 写进程必须对对象占有独占访问权, 即写的时候不能读
- 读进程没有个数限制
//Shared
int readcnt; /* Initially = 0 */
semaphore r, whole; /* Initially = 1 */
//Writers
void writer(void)
{
while (1) {
wait(whole);
/* Critical section */
/* Writing here */
signal(whole);
}
}
//Readers
void reader(void)
{
while (1) {
/*Increment readcnt*/
wait(r); /*Only one reader a time*/
readcnt++;
if (readcnt == 1) /* First reader in */
wait(whole); /* Lock out writers */
signal(r);
/* Read; mutliple readers may be here */
wait(r);
readcnt--;
if (readcnt == 0) /* Last out */
signal(whole); /* Let in writers */
signal(r);
}
}
请务必重视上方这段代码, 它很重要.
作出一些解释:
- 写进程:
- 进入前确保所有读者已经退出读区域
- 退出后通知所有读者可以进入
- 读进程:
- 第一个进入的进程必须确保写进程没有在操作数据
- 最后一个退出的进程必须通知写进程可以操作数据了
至此, 对于信号量的应用差不多说完了.
本篇博文是对上一篇博文, 同步方式的一个补充章, 主要是一些现实中会遇到的问题.
这篇博文就到这里~