进程线程的同步机制

进程线程的同步机制

什么是进程/线程间同步机制

多进程的系统中避免不了进程间的相互关系。其实，如果类比于我们的现实生活，我们可以找到很多例子：

如果两个人有一个共同的支付宝，同时取走里面的所有钱，那么这些钱该给谁？

小明和小红同时买某趟火车的最后一张票，那么这个票属于谁？

…………

其实生活中这样的例子比比皆是；要讲线程同步，那么我们就不得不讲什么是线程互斥：

两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥· 也就是说，一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。
      进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段称为临界区。两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则：任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。

竞争：多个线程或者进程在读写一个共享数据时结果依赖于它们执行的相对时间，这种情形叫做竞争。

竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关，称为竞争条件。

进程同步是进程之间直接的相互作用，是合作进程间有意识的行为，典型的例子是公共汽车上司机与售票员的合作。只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。 

Bernstein条件：并发进程的无关性是进程与时间无关的一个充分条件，这一条件在1966年首先由Bernstein提出，称为Bernstein条件。

间满足以下3条关系：

(1) R(p1) ∩ W(p2) = ∅

(2) R(p2) ∩ W(p1) = ∅

(3) W(p1) ∩ W(p2) = ∅

例如：p1：y=z+y；p2： z=x+z，假设x=1，y=2，z=3

如果先运行p1，则最后的结果是x=1，y=5，z=4；如果先运行p2，则x=1，y=6，z=4。两次的结果不一样，即程序不可再现，所以p1，p2不能并行的执行。

借用上面的例子，p1:y=z+y,那么p1的读集为 R(p1)={z,y},p1的写集为 W(p1)={y}。

对进程S1、S2，Bernstein条件要求R(S1)∩W(S2)∪W(S1)∩R(S2)∪W(S1)∩W(S2)={}。

多个程序段其实只有一部分代码会引起竞争条件——进程中间对共享数据进行访问的区域（这部分区域就是临界区）

在实际情况下，我们要避免竞争条件，保证一段时间内，临界区只被一个进程占有；

process进入临界区的条件：

1、互斥使用；

2、有空让进；前进性

3、有限等待；

 

（互斥、不空置、不饿死）

 

进程同步方案1(软件方案)

（Peterson’s Solution）

Person's solution 是用来一种基于软件的解决关键区域问题的算法（critical-section). 

它并非完美的，有可能不正确地工作。解决的问题存在局限性：解决两个进程同步的问题。 （简单，很原始，学习起来也是很轻松的）

我们可以类比到现实生活中的十字路口问题：只有两个进程——（横向、纵向），为了保证车辆的有序进行，我们可以才有红绿灯——Peterson’s Solution

考虑条件1：临界区是否为空（客观条件）

交叉路口中，红绿灯就是横向纵向的共享信号；

——只有等到绿灯，才能行进；

考虑条件2：进程意愿（客观条件）

然而十字路口的红灯并不能判断纵横车道是否有车，但是在解决方案中，我们必须进行一个标识，如果想进入临界区，则设置一个flag为true，一个进程要进入临界区，首先看看其他进程的flag是否为true，如果其他为ture，就先让其他进；

两个条件必须同时考虑：只考虑1——不满足互斥条件；只考虑2——不满足前进条件（两个进程如果一直让对方的结果是两个都不能进）

do {flag[i] = true;turn = j;while (flag[j] && turn == j);critical sectionflag[i] = false;remainder section} while (true);

 

面包店算法（多进程方案）

在多个进程竞争的情况下，使用面包点算法；

概括：进入临界区之前，每个进程分配一个数字，具有最小数字的进程进入临界区

分配的数字怎么来：分配的数字按不减的方式产生（数字有可能相同），每个进程自行产生，在数字相同的情况下，按下标排列；

Notation<=lexicographical order (ticket #,process id #)

(a,b)<(c,d) a<c or if a=c and b<d

Data:

booleen choosing -----判断是否需要排队；

Number 排队次序；

 

do{

Choosing[i] = true;

Number[i] = max(number[0],number[1]………………);

Choosing[i] = false;

For (j = 0;j<n;j++){

While(choosing[j]);

While((number[j]!=0)&&((number[i],j)<(number[j],i))));

}

Critical section

Number[i] = 0;

remainder section;

}

 

其他算法：Elsenberg alorithm

 

进程同步方案2(硬件方案)

系统对临界区提供硬件支持：

a) 单处理器系统——屏蔽中断：临界区在使用时，关闭中断

不适用于多处理器系统：往往会带来很大的性能损失；

单处理器使用：很多日常任务，都是靠中断的机制来触发的，比如时钟，如果使用屏蔽中断，会影响时钟和系统效率，而且用户进程的使用可能很危险！

使用范围：内核进程（少量使用）

b) 原子硬件指令支持：

测试设置指令：

Process P1{

While(TestAndSet(lock));——临界区入口;保证临界区中只有一个进程

(critical section)

Lock = false;

}

交换指令：

Void Swap(boolean &a,booleann &b)

(多处理器的情况下，测试设置指令和交换指令并不能保证互斥)

 

所以说，软件和硬件方案都是有一定缺陷的，那么我们还有什么更好的方法么，当然啦~~~~~下回我们介绍个非常重要的概念——信号量；

预知后事如何，请听下回分解！

<!--EndFragment-->