进程线程的同步机制
什么是进程/线程间同步机制
多进程的系统中避免不了进程间的相互关系。其实,如果类比于我们的现实生活,我们可以找到很多例子:
如果两个人有一个共同的支付宝,同时取走里面的所有钱,那么这些钱该给谁?
小明和小红同时买某趟火车的最后一张票,那么这个票属于谁?
…………
其实生活中这样的例子比比皆是;要讲线程同步,那么我们就不得不讲什么是线程互斥:
两个或两个以上的进程,不能同时进入关于同一组共享变量的临界区域,否则可能发生与时间有关的错误,这种现象被称作进程互斥· 也就是说,一个进程正在访问临界资源,另一个要访问该资源的进程必须等待。
进程互斥是进程之间发生的一种间接性作用,一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段称为临界区。两个进程不能同时进入临界区,否则就会导致数据的不一致,产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则:任意时刻只能允许一个进程处于同一共享变量的临界区,而且不能让任一进程无限期地等待。
竞争:多个线程或者进程在读写一个共享数据时结果依赖于它们执行的相对时间,这种情形叫做竞争。
竞争条件:多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关,称为竞争条件。
进程同步是进程之间直接的相互作用,是合作进程间有意识的行为,典型的例子是公共汽车上司机与售票员的合作。只有当售票员关门之后司机才能启动车辆,只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地,两个进程之间有时也有这样的依赖关系,因此我们也要有一定的同步机制保证它们的执行次序。
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-->
相关推荐
小实验一:编写一个没有线程同步机制的程序,调试程序,观察在执行程序的过程中,出现的问题并解答原因 小实验二:使用Windows互斥信号量操作函数解决上述线程并发问题,并分析、尝试和讨论线程执行体中有关信号量...
线程同步的几种方式的c++方法,Mutex,Event,Semaphore等
现在流行的进程线程同步互斥的控制机制,其实是由最原始最基本的4种方法实现的。由这4种方法组合优化就有了.Net和Java下灵活多变的,编程简便的线程进程控制手段。
操作形同实验——进程同步和互斥 (1) 通过编写程序实现进程同步和...(2) 了解Windows2000/XP中多线程的并发执行机制,线程间的同步和互斥。 (3) 学习使用Windows2000/XP中基本的同步对象,掌握相应的API函数。
d: 经典线程同步互斥问题 e: 使用关键段解决子线程互斥问题 f: 利用事件实现线程同步问题 g: 利用互斥量来解决线程同步互斥问题 h: problem1 生产者消费者问题 (1生产者 1消费者 1缓冲区) problem1 more ...
实际上,不仅线程间需要同步,进程间、信号间等等都需要同步机制。 因此,所有“多个控制流,共同操作一个共享资源”的情况,都需要同步。 数据混乱原因: 1. 资源共享(独享资源则不会) 2. 调度随机(意味着...
现在流行的进程线程同步互斥的控制机制,其实是由最原始最基本的4种方法实现的。由这4种方法组合优化就有了.Net和Java下灵活多变的,编程简便的线程进程控制手段。这4种方法具体定义如下在《操作系统教程》ISBN7-...
互斥以排他方式防止共享数据被并发修改。互斥锁是一个二元变量,其状态为开锁(允许0)和上锁(禁止1),将某个共享资源与某个特定互斥锁...(2)只有锁定该互斥锁的进程才能释放该互斥锁。其它线程的释放操作无效。
进程同步是操作系统学习过程中非常重要的一部分内容,同时也非常困难,在学习...本实验的目的是在理解了课本内容的基础上,通过上机,观察实验现象,并对问题进行研究,让我们在实践中对线程同步机制有一个更好的了解。
1。生产者消费者问题(信号量+mutex) 参考教材中的生产者消费者算法,创建5个进程,其中两个进程为生产者进程,...编写一个写者优先解决读者写者问题的程序,其中读者和写者均是多个进程,用信号量作为同步互斥机制。
本文主要分析了linux下的线程同步机制,并附有源码解析,同时针对linux和windows的线程机制进行了对比分析,更利于深入理解线程、进程同步机制。
1。生产者消费者问题(信号量+mutex) 参考教材中的生产者消费者算法,创建5个进程,其中两个进程为生产者进程,...编写一个写者优先解决读者写者问题的程序,其中读者和写者均是多个进程,用信号量作为同步互斥机制。
1. 在windows 下编写一个控制台应用...在windows 环境下编写一个控制台应用程序,输出系统中正在运行的进程的信息,包括进程号、进程所运行的程序、进程的启动时间、在核心态下消耗的时间以及在用户态下消耗的时间。
上一章介绍了如何使用允许线程保留在用户方式中的机制来实现线程同步的方法。用户方 式同步的优点是它的同步速度非常快。如果强调线程的运行速度,那么首先应该确定用户方式 的线程同步机制是否适合需要。
由于线程采用并发运行机制,因此当进程运行时,其各线程的运行进度可能不一致,所以需要对各个线程的运行过程进行同步。其中常用的控制线程同步的机制有下面几种:互斥对象,事件对象,信号量,临界区等等。
一、引言 在现代操作系统里,同一时间可能有多个内核执行流在执行,因此内核其实象多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上,更需要一些同步机制来同步...
进程同步相关的习题 很具有代表性 希望各位能受益不少 主要是信号量机制 PV原语等知识
用多进程同步方法演示“生产者-消费者”问题 1、设计目的:通过研究Linux的进程机制和信号量,实现生产者消费者问题的并发控制。 2、说明:有界缓冲区内设有20个存储单元,放入取出的产品设定为1-20个整数。 3、设计...