[操作系统]Week 6 Note

6.5 Semaphores 信号量

Dijkstra提出——信号量机制

• 信号量：
  1. 整形信号量
  2. 记录型信号量
  3. AND型信号量、信号量集
  4. 二值信号量

1、用法

S信号量只能进行两种不可分割的原子操作：wait(S)和signal(S)（最开始叫作P()和V()）

Counting semaphore 计数信号量 （整数信号量）

Binary semaphore 二值信号量 （0或1） – 即互斥锁（mutex locks）

2、实现

Define a semaphore as a record ：

typedef struct {
int value;
struct process *list;
} semaphore;

typedef struct {
int value;
struct process *list;
} semaphore;

Two operations:

block() – 将调用操作的过程放在适当的等待队列上。

• running → waiting

wakeup() –删除等待队列中的进程之一并将其放入就绪队列。

• waiting→ready

wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}

wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}

signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}

signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}

3、wait和signal的操作讨论

• 通常用信号量表示资源或临界区
• 信号量的物理含义
  • S.value >0 表示有S.value个资源可用；
  • S.value=0 表示无资源可用或表示不允许进程再进入临界区；
  • S.value<0 则|S.value|表示在等待队列中进程的个数或表示等待进入临界区的进程个数。
• wait(S)≡P(S) ≡ down(S) ： 表示申请一个资源
• signal(S)≡V(S) ≡ up(S) ： 表示释放一个资源
• wait、signal操作必须成对出现，有一个wait操作就一定有一个signal操作。一般情况下：当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现。
• 如果两个wait操作相邻，那么它们的顺序至关重要，而两个相邻的signal操作的顺序无关紧要。一个同步wait操作与一个互斥wait操作在一起时，同步wait 操作在互斥wait操作前。
• wait、signal操作的优缺点
  • 优点：简单，而且表达能力强。
  • 缺点：不够安全；wait、signal操作使用不当会出现死锁；实现复杂。

4、死锁和饥饿

死锁–两个或多个进程无限期地等待一个事件，该事件仅由一个等待的进程引起。

6.6 经典同步问题

1、生产者-消费者问题

• 生产者-消费者问题是最著名的同步问题，它描述一组生产者（P1 ……Pm）向 一组消费者（C1……Cq）提供消息。它们共享一个有限缓冲池（bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息。
• 生产者-消费者问题是许多相互合作进程的一种抽象。

do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);

do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);

do {
wait(full);
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);

do {
wait(full);
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);