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

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

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

[No00003C]操作系统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--;

} 发信号让生产者再走…

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

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

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

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

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

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

从信号到信号量

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

还应该能记录一些信息

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

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

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

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

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

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

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

信号量开始工作…

初始时 sem = ?

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

(2) P 2 执行,P 2 sleep sem = -2

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

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

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

(6) P 3 执行,P 2 继续执行 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 1

register = empty;

register = register - 1;

empty = register;

生产者P 2

register = empty;

register = register - 1;

Empty = register;

一个可能的执行( 调度)

P 1 .register = empty;

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

P 2 .register = empty;

P 2 .register = P 2 .register - 1;

empty = P 1 .register;

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

竞争条件(Race Condition)

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

第i次执行

P 1 .register = empty;

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

P 2 .register = empty;

P 2 .register = P 2 .register - 1;

empty = P 1 .register;

empty = P 2 .register;

第j 次执行

P 1 .register = empty;

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

empty = P 1 .register;

P 2 .register = empty;

P 2 .register = P 2 .register - 1;

empty = P 2 .register;

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

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

解决竞争条件的直观想法

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

仍是那个执行序列

P 1 .register = empty;

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

P 2 .register = empty;

P 2 .register = P 2 .register - 1;

empty = P 1 .register;

empty = P 2 .register;

生产者P 1

检查并给empty上锁

P 1 .register = empty;

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

生产者P 2

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

生产者P 1

empty = P 1 .register;

给empty 开锁

生产者P 2

检查并给empty 上锁

P 2 .register = empty;

P 2 .register = P 2 .register - 1;

empty = C.register;

给empty

临界区(Critical Section)

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

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

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

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

临界区代码的保护原则

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

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

这保证了是临界区

好的临界区保护原则

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

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

进入临界区Peterson

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

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

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

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

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

仍然是标记和轮转的结合

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

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

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

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

面包店算法的正确性

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

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

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

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

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

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

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

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

问题:为什么不好使?

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

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

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

进程P i

while(TestAndSet(&lock)) ;

临界区

lock = false;

剩余区

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

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

上一篇:java获取程序执行时间


下一篇:Leetcode First Bad Version