操作系统Operating Systems进程同步与信号量Processes Synchronization and Semaphore

进程合作：多进程共同完成一个任务

从纸上到实际：生产者− − 消费者实例

共享数据

#define BUFFER_SIZE 10

typedef struct { . . . } item;

item buffer[BUFFER_SIZE];

int in = out = counter = 0; 注意：这些都是用户态程序!

生产者进程

while (true) {

while(counter== BUFFER_SIZE);

buffer[in] = item;

in = (in + 1) % BUFFER_SIZE;

counter++;

}

消费者进程

while (true) {

while(counter== 0);

item = buffer[out];

out = (out + 1) % BUFFER_SIZE;

counter--;

}

找到哪些地方要停，什么时候再走?

需要让"进程走走停停"来保证多进程合作的合理有序

这就是进程同步

生产者进程

while (true) {

while(counter== BUFFER_SIZE); 缓存区满，生产者要停

buffer[in] = item;

in = (in + 1) % BUFFER_SIZE;

counter++;

} 发信号让消费者再走…

消费者进程

while (true) {

while(counter== 0) ; 缓存区空，消费者要停

item = buffer[out];

out = (out + 1) % BUFFER_SIZE;

counter--;

} 发信号让生产者再走…

只发信号还不能解决全部问题

(1) 缓冲区满以后生产者P ₁ 生产一个item 放入，会sleep信号

(2) 又一个生产者P ₂ 生产一个item 放入，会sleep

(3) 消费者C 执行1 次循环，counter==BUFFER_SIZE-1 ，发信号给P ₁ ，P ₁ wakeup

(4) 消费者C 再执行1 次循环，counter==BUFFER_SIZE-2 ，P ₂ 不能被唤醒

从信号到信号量

不只是等待信号、发信号? 对应睡眠和唤醒!

还应该能记录一些信息

能记录有"2 个进程等待"就可以了…

(1) 缓冲区满， P ₁ 执行， P ₁ sleep ，记录下 个进程等待

(2) P ₂ 执行， P ₂ sleep ，记录下 个进程等待

(3) C 执行 1 次循环，发现 个进程等待， wakeup 1 个

(4) C 再执行 1 次循环，发现 ? 个进 程等待， 再 ?

(5) C 再执行 1 次循环， 怎么办 ? 此时再来 P ₃ 怎么办 ?

什么是信号量? 记录一些信息( 量) ，并根据这个信息决定睡眠还是唤醒( 信号) 。

信号量开始工作…

初始时 sem = ?

(1) 缓冲区满， P ₁ 执行， P ₁ sleep sem = -1 什么含义?

(2) P ₂ 执行，P ₂ sleep sem = -2

(3) C 执行 1 次循环，wakeup P ₁ sem = -1

(4) C 再执行 1 次循环，wakeup P ₂ sem = 0

(5) C 再执行 1 次循环， sem = 1 什么含义?

(6) P ₃ 执行，P ₂ 继续执行 sem = 0

总结一下：这个整数什么时候-1? 什么时候+1?什么时候睡眠? 什么时候唤醒?

什么是信号量? 信号量的定义…

信号量: 1965 年，由荷兰学者Dijkstra 提出的一种特殊整型变量，量用来记录，信号用来sleep 和wakeup

struct semaphore

{

int value; // 记录资源个数

PCB *queue;// 记录等待在该信号量上的进程

}

P(semaphore s); // 消费资源

V(semaphore s); // 产生资源

P 的名称来源于荷兰语的proberen ，即test

V 的名称也来源于荷兰语verhogen(increment)

P(semaphore s)

{

s.value--;

if(s.value < 0) {

sleep(s.queue); }

}

用信号量解生产者− −消费者问题

int fd = open("buffer.txt");

write(fd, 0, sizeof(int)); // 写in

write(fd, 0, sizeof(int)); // 写out 用文件定义共享缓冲区

semaphore full = 0;

semaphore empty = BUFFER_SIZE; // 信号量的定义和初始化

semaphore mutex = 1;

Producer(item) {

P(empty);

P(mutex);

读入in; 将item 写入到in 的位置上;

V(mutex);

V(full); }

Consumer() {

P(full);

P(mutex);

读入out; 从文件中的out位置读出到item; 打印item;

V(mutex);

V(empty); }

信号量临界区保护Critical Section

共同修改信号量引出的问题

初始情况

empty = -1; //这是什么含义?

Producer(item) {

P(empty);

...}

生产者P ₁

register = empty;

register = register - 1;

empty = register;

生产者P ₂

register = empty;

register = register - 1;

Empty = register;

一个可能的执行( 调度)

P ₁ .register = empty;

P ₁ .register = P ₁ .register - 1;

P ₂ .register = empty;

P ₂ .register = P ₂ .register - 1;

empty = P ₁ .register;

empty = P ₂ .register; 最终的empty 等于多少? 对吗?

竞争条件(Race Condition)

竞争条件: 和调度有关的共享数据语义错误

第i次执行

P ₁ .register = empty;

P ₁ .register = P ₁ .register - 1;

P ₂ .register = empty;

P ₂ .register = P ₂ .register - 1;

empty = P ₁ .register;

empty = P ₂ .register;

第j 次执行

P ₁ .register = empty;

P ₁ .register = P ₁ .register - 1;

empty = P ₁ .register;

P ₂ .register = empty;

P ₂ .register = P ₂ .register - 1;

empty = P ₂ .register;

错误由多个进程并发操作共享数据引起

错误和调度顺序有关，难于发现和调试

解决竞争条件的直观想法

在写共享变量empty时阻止其他进程也访问empty

仍是那个执行序列

P ₁ .register = empty;

P ₁ .register = P ₁ .register - 1;

P ₂ .register = empty;

P ₂ .register = P ₂ .register - 1;

empty = P ₁ .register;

empty = P ₂ .register;

生产者P ₁

检查并给empty上锁

P ₁ .register = empty;

P ₁ .register = P ₁ .register - 1;

生产者P ₂

检查empty 的锁 ?                 一段代码一次只允许一个进程进入

生产者P ₁

empty = P ₁ .register;

给empty 开锁

生产者P ₂

检查并给empty 上锁

P ₂ .register = empty;

P ₂ .register = P ₂ .register - 1;

empty = C.register;

给empty

临界区(Critical Section)

临界区: 一次只允许一个进程进入的该进程的那一段代码

一个非常重要的工作: 找出进程中的临界区代码 读写信号量的代码一定是临界区…

临界区代码的保护原则

基本原则：互斥进入: 如果一个进程在临界区中执行，则其他进程不允许进入

这些进程间的约束关系称为 互斥(mutual exclusion)

这保证了是临界区

好的临界区保护原则

有空让进: 若干进程要求进入空闲临界区时，应尽快使一进程进入临界区

有限等待: 从进程发出进入请求到允许进入，不能无限等待

进入临界区Peterson

结合了标记和轮转两种思想

Peterson算法的正确性

满足互斥进入:

如果两个进程都进入，则flag[0]=flag[1]=true ，turn==0==1 ，矛盾!

满足有空让进:

如果进程P 1 不在临界区，则flag[1]=false ，或者turn=0 ，都P 0 能进入!

满足有限等待:

P 0 要求进入，flag[0]=true ；后面的P 1 不可能一直进入，因为P 1 执行一次就会让turn=0

多个进程怎么办? − − 面包店算法

仍然是标记和轮转的结合

如何轮转: 每个进程都获得一个序号，序号最小的进入

如何标记: 进程离开时序号为0 ，不为0 的序号即标记

面包店: 每个进入商店的客户都获得一个号码，号码最小的先得到服务；号码相同时，名字靠前的先服务。

面包店算法的正确性

互斥进入: P _i 在临界区内，P _k 试图进入，一定有(num[i], i)<(num[k],k) ，P k 循环等待。

有空让进: 如果没有进程在临界区中，最小序号的进程一定能够进入。

有限等待: 离开临界区的进程再次进入一定排在最后(FIFO) ，所以任一个想进入进程至多等n

临界区保护的另一类解法…

再想一下临界区： 只允许一个进程进入， 进入另一个进程意味着什么?

被调度: 另一个进程只有被调度才能执行，才可能进入临界区，如何阻止调度?

• 什么时候不好使?
• 多CPU( 多核)…

问题：为什么不好使?

临界区保护的硬件原子指令法

进程P _i

while(TestAndSet(&lock)) ;

临界区

lock = false;

剩余区

想一想: 多CPU 情况好不好使?