操作系统 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);
  }
}