问题描述
几年前,我举办了一次操作系统研讨会.我的任务是创建一个使用尽可能少的信号量进行进程同步的算法.它应该看起来像这样:
a few years ago I had an Operating Systems seminar. I had been tasked to create an algorithm for process synchronization using as few semaphores as possible. It should have looked like this:
P1-> P2-> P3-> P4-> P5
P1 -> P2 -> P3 -> P4 -> P5
P(n)-处理
一次只运行一个进程,并且需要严格排序.
Only one process running at a time and strict ordering was needed.
去年,我提供了使用3个信号量的解决方案(有效地创建了一个障碍).这是我的算法:
Last year I came with solution using 3 semaphores (effectively creating a barrier).Here is my algorithm:
P S1 S1 S1 S1
4W1 W0 W0 W0 W0
4S0 P S2 S2 S2
3W2 W1 W1 W1
3S1 P S1 S1
2W1 W0 W0
2S0 P S2
W2 W1
S1 P
(执行从上到下,每个通道是一个进程)P-需要序列化的实际工作
W(n)-Waitn
S(n)-signaln
4W1的意思是做4个wait1s"
wait1和signal1与semaphore1一起运行,依此类推...
(execution is from top to bottom, each lane is a single process)P - real work which needs to be done serialized
W(n) - waitn
S(n) - signaln
4W1 means "do 4 wait1s"
wait1 and signal1 operates with semaphore1 and so on...
算法说明:
- 每个过程通道都开始
- 第一个进程将运行,其他进程将执行signal1()
- 除第一个进程外,其他所有进程都将等待semaphore0(正在执行wait0)
- 在process1等待4个信号1之后,它发送4个signal0,从而创建了一个屏障,因为其他进程在等待第一个信号成功完成.
问题是我不知道如何使用2个信号灯使它工作.
The problem is I can't figure out how to make it work using 2 semaphores.
PS:这不是一项任务,这是一个困扰我很久的问题.
PS: this is not an assignment, it's a problem that's been lying in my head for too long.
推荐答案
使用2个信号量无法完成.最少3个.
It can't be done using 2 semaphores. 3 is minimum.
这篇关于使用2个信号量进行严格的N进程同步的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!