[操作系统] 相互排斥:软件解决方案
互斥:软件解决方法
算法一
算法思路
预留一个全局内存区域,并标记为turn
。进程(P0
或P1
)想进入它的临界区执行时,要先检查turn
的内容。若turn
的值等于进程号,则该进程可以进入它的临界区;否则该进程被强制等待。等待进程重复地读取turn
的值。直到被允许进入临界区。这一过程称为忙等待(busy waiting) 或 自旋等待(spin waiting),进程在获得临界区的访问权并完成访问后,必须为另一个进程更新turn
的值。
P0
:
while(turn != 0) {/* busy waiting */}
/* critical section */
turn = 1;
P1
:
while(turn != 1) {/* busy waiting */}
/* critical section */
turn = 0;
缺陷
- 进程必须严格交替(
P0
临界区执行完后才会更新turn
值,使得P1
跳出忙等待状态,同理P0
也需等待P1
临界区执行完)使用它们的临界区,因此执行的步调由两个进程较慢的进程决定。
例如:若P0
在1小时内仅使用临界区1次,而P1
要以1000次/小时的速率使用临界区,则P1
就必须适应P0
的节奏。
BUG
- 若一个进程终止,则另一个进程就会被永久阻塞。无论进程是在临界区内终止还是在临界区之外终止,都会发生这种情况。
例如:P0
在执行到第二行代码(临界区内)时终止,此时turn
值为0
且此后不会被更新,因此P1
将永久处于忙等待状态;P0
在执行到第三行代码(临界区外)时终止,此时turn
值为1
,于是P1
进入临界区,执行完后便将turn
值置为0
,而P0
进程因为终止便不会再更新turn
值,因此P1
将永久处于忙等待状态。
算法二
算法一仅由一个共享的仲裁变量去实现进程间的互斥,因此进程之间必须严格交替执行,进程之间的依赖关系过强
算法二为每一个进程都配备了专门的”钥匙“,这里定义一个bool
数组flag
,flag[0]
与P0
关联,flag[1]
与P1
关联,每个进程可检查但不能改变另一个进程的flag
值
算法思路
一个进程要进入临界区时,它会周期性地检查另一个进程的flag
,直到其值为false
,这表明另一个进程不在临界区内。检查进程立即设置自己的flag
为true
,进入自己的临界区。离开临界区时,将自己的flag
设置为false
。
P0
:
while(flag[1]) {/* busy waiting */}
flag[0] = true;
/* critical section */
flag[0] = false;
P1
:
while(flag[0]) {/* busy waiting */}
flag[1] = true;
/* critical section */
flag[1] = false;
进步
- 若一个进程在临界区外终止,包括设置
flag
代码时,则另一个进程不会被阻塞。
例如:当P1
在执行完第4行代码后终止,此后flag[1]
将一直保持false
,因此P0
将永远不会进入忙等待状态即说明其不会被阻塞
BUG
- 若一个进程在临界区内,或在进入临界区之前已将
flag
设置为true
时终止,则另一个进程就会永久阻塞 -
没有保证互斥!!
例如:P1
执行完第4行代码后,于是P0
跳出忙等待状态,但P0
还未来得及执行第二行代码(将flag[0]
设置为true
)P1
便又进入了临界区,随后P0
也进入临界区,便产生了访问冲突
下面采用Java多线程编程模拟算法二并验证BUG-2
package TEST;
public class Multithreading {
public static void main(String[] args) {
Process p0 = new Process("P0", 0, 0);
Process p1 = new Process("P1", 1, 1);
p0.start();
p1.start();
}
}
class Process extends Thread {
private static int var;
private int var_right;
private static boolean[] flag = new boolean[2];
private String name;
private int cnt_test = 100;
private int No;
private int No_other;
public Process(String name, int No, int var_right) {
super();
this.name = name;
this.No = No;
this.var_right = var_right;
this.No_other = (No + 1) % 2;
}
public void run() {
for(int i = 0; i < cnt_test; i++) {
while(flag[No_other]) { /* busy waiting */ }
flag[No] = true;
/*--- critical section begin---*/
var = var_right;
System.out.println(this.name + ":" + (var == var_right? var : "##"));
/*--- critical section end---*/
flag[No] = false;
}
}
}
两个线程任务是,将公共变量var
赋值为本线程对应正确的值var_right
,并输出当前var
的值,若两个线程保证互斥则var
总是等于var_right
(Condition ‘var == var_right’ is always ‘true’)即不会输出##
运行结果如下:
P0:0
P1:##
P0:0
P1:1
P0:0
P1:##
P0:0
P1:##
P0:0
P0:0
P0:0
P1:##
P1:##
P0:0
P1:1
P1:1
P0:##
P1:1
P1:1
P1:1
P0:##
P0:##
P1:1
P0:0
P1:1
P1:##
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P0:##
P1:1
P0:##
P1:1
P1:##
P0:0
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P1:##
P0:0
P1:1
P0:0
P1:1
P1:##
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P1:1
P0:0
P1:1
P0:0
P0:0
P1:1
P1:1
P1:1
P0:0
P1:##
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:1
P1:##
P0:0
P1:1
P1:1
P0:0
P1:##
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:##
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P1:1
P0:##
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:1
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
Process finished with exit code 0
可见采用算法二两个线程之间发生了不少次的访问冲突(输出##
)
算法三
算法二由于执行速率不匹配的原因,导致两个进程同时处在临界区的位置,所以算法二的方案失败
算法三通过简单地交换两条语句来解决这一问题
算法思路
将控制其他进程持续忙等待的语句提到了检查flag
值之前,确保了同一时刻只有一个进程进入临界区
P0
:
flag[0] = true;
while(flag[1]) {/* busy waiting */}
/* critical section */
flag[0] = false;
P1
:
flag[1] = true;
while(flag[0]) {/* busy waiting */}
/* critical section */
flag[1] = false;
进步
- 解决算法二造成的访问冲突问题,确保了互斥性
BUG
- 与算法二一样,某一进程在临界区内或在设置
flag
为true
时终止,会引起其他进程永久阻塞 - 若每个进程在执行
while
语句前都将flag
设置为true
,则每个进程都会认为另一个进程已经进入临界区,进而引发死锁
例如:P0
执行完第一行代码后还未来得及执行while
语句,P1
也执行完了第一行代码,此时flag[0]
与flag[1]
的值都为true
,因此两个进程都无法跳出忙等待的状态,从而造成死锁
下面采用Java多线程编程模拟算法三并验证BUG-2
package TEST;
public class Multithreading {
public static void main(String[] args) {
Process p0 = new Process("P0", 0, 0);
Process p1 = new Process("P1", 1, 1);
p0.start();
p1.start();
}
}
class Process extends Thread {
private static int cnt_busy_wait = 0;
private static int var;
private int var_right;
private static boolean[] flag = new boolean[2];
private String name;
private int cnt_test = 100;
private int No;
private int No_other;
public Process(String name, int No, int var_right) {
super();
this.name = name;
this.No = No;
this.var_right = var_right;
this.No_other = (No + 1) % 2;
}
public void run() {
for(int i = 0; i < cnt_test; i++) {
flag[No] = true;
while(flag[No_other]) {
/* busy waiting */
System.out.println(this.name + " BusyWaiting: " + (++cnt_busy_wait));
if(cnt_busy_wait > 999) return;
}
/*--- critical section begin---*/
var = var_right;
System.out.println(this.name + ":" + (var == var_right? var : "##"));
/*--- critical section end---*/
flag[No] = false;
}
}
}
运行结果如下:
P0:0
P1 BusyWaiting: 1
P1 BusyWaiting: 3
P1 BusyWaiting: 4
P1 BusyWaiting: 5
P0 BusyWaiting: 2
P0 BusyWaiting: 7
P0 BusyWaiting: 8
P0 BusyWaiting: 9
P0 BusyWaiting: 10
P1 BusyWaiting: 6
P1 BusyWaiting: 12
P1 BusyWaiting: 13
P0 BusyWaiting: 11
... ...
P1 BusyWaiting: 995
P1 BusyWaiting: 996
P1 BusyWaiting: 997
P1 BusyWaiting: 998
P1 BusyWaiting: 999
P1 BusyWaiting: 1000
P0 BusyWaiting: 967
Process finished with exit code 0
可见结果只被正确输出了一次,此后两线程皆处在忙等待状态,形成死锁
算法四
算法三中,一个进程在设置其状态时是不知道另一个进程的状态的。由于每一个进程坚持要进入临界区,导致死锁发生
算法四在算法三的基础上引入**“谦让”**的机制,在忙等待中随时重设flag
,一定程度上避免了死锁发生
算法思路
当出现死锁情况时(两者都进入忙等待状态),P0
进程将flag[0]
置为false
并在该状态延迟1秒,P1
便可在这1秒之内跳出忙等待状态,从而避免了死锁的情况
P0
:
flag[0] = true;
while(flag[1])
{
flag[0] = false;
delay(1); // dalay 1 sec
flag[0] = true;
}
/* critical section */
flag[0] = false;
P1
:
flag[1] = true;
while(flag[0])
{
flag[1] = false;
delay(1); // dalay 1 sec
flag[1] = true;
}
/* critical section */
flag[1] = false;
进步
- 一定程度的避免了死锁的出现
缺陷
- 当两个进程自上而下的语句几乎同时被执行时,则两者都不会进入临界区。严格来说,这不是死锁,因为两个进程执行速率的相对变化会打破这种状况,允许其中一个进程进入临界区,这种状态称为活锁(livelock)(尽管该场景不会维持很长时间,但仍然是一种有可能发生的情形)
Dekker 算法
算法四可能会出现 “互相谦让” 的情况
Dekker算法通过turn
变量表示哪个进程有权进入它的临界区,避免了**“互相谦让”**的情况
算法思路
当P0
要进入它的临界区时,将其flag
设置为true
,然后检查P1
的flag
。若为false
,P0
可以立即进入它的临界区;否则,P0
要检查turn
,若发现turn
为0
,则P0
要持续周期性地检查P1
的flag
。而P1
需要延期执行并将flag
设置为false
,让P0
执行。P0
完成临界区执行后,将其flag
设置为false
以释放临界区,并将turn
设置为1
,把权力转交给P1
bool flag[2];
int turn;
void P0()
{
while (true)
{
flag[0] = true;
while (flag[1])
{
if (turn == 1)
{
flag[0] = false;
while(turn == 1) { /* busy waiting */ }
flag[0] = true;
}
}
/* critical section */
turn = 1;
flag[0] = false;
}
}
void P1()
{
while (true)
{
flag[1] = true;
while (flag[0])
{
if (turn == 0)
{
flag[1] = false;
while (turn == 0) { /* busy waiting */ }
flag[1] = true;
}
}
/* critical section */
turn = 0;
flag[1] = false;
}
}
int main()
{
flag[0] = false;
flag[1] = false;
turn = 1;
parbegin(P0, P1); // concurrent execution
return 0;
}
Peterson 算法
Dekker 算法解决了互斥问题,但复杂的程序很难实现且其正确性也很难证明。Peterson提出了一个简单且精致的算法。和前面一样,全局数组变量flag
表明每个互斥进程的位置,全局变量turn
解决同时发生的冲突。
bool flag[2];
int turn;
void P0()
{
while(true)
{
flag[0] = true;
turn = 1;
while(flag[1] && turn == 1) {/* busy waiting */}
/* critical section */
flag[0] = false;
}
}
void P1()
{
while(true)
{
flag[1] = true;
turn = 0;
while(flag[0] && turn == 0) {/* busy waiting */}
/* critical section */
flag[1] = false;
}
}
int main()
{
flag[0] = false;
flag[1] = false;
parbegin(P0, P1); // concurrent execution
return 0;
}
最后两种正确算法相关内容(验证、说明等)待更新… …
上一篇: 2.进程同步和互斥
下一篇: 进程互斥的硬件解决方案
推荐阅读
-
操作系统 - 相互排斥的定义和实施
-
实施相互排斥的软件方法
-
[操作系统] 相互排斥:软件解决方案
-
FreeRTOS 操作系统学习 - 相互排斥 - 相互排斥的使用
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)