技术专题

操作系统-同步互斥

2009年9月15日 阅读(203)

并发执行,在我们串行执行的pc上的含义,是指两部分的程序代码,可能以任意的次序执行。如果它们对共享对象进行了修改,如果汇编指令的执行顺序不同,就可能产生不同的结果,这样就有问题,必须对程序的执行过程进行控制。这个本质也提供了一种我们分析一段程序是否需要人工控制的标准:考虑两个程序的汇编级的指令混合,结果会如何?

进程之间的关系主要有两种,同步与互斥。所谓互斥,是指散步在不同进程之间的若干程序片断,当某个进程运行其中一个程序片段时,其它进程就不能运行它们之中的任一程序片段,只能等到该进程运行完这个程序片段后才可以运行。所谓同步,是指散步在不同进程之间的若干程序片断,它们的运行必须严格按照规定的某种先后次序来运行,这种先后次序依赖于要完成的特定的任务。也就是说同步是指两个进程为完成某项任务,必须进行协作,有前后次序的等待关系。 

互斥:是指某一资源同时只允许一个访问者对其进行访问,具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序,即访问是无序的。当多个进程访问或操作同一个数据,且执行结果与访问的特定顺序有关,称为竞争条件。为了防止这种竞争,必须确保一段时间内只有一个进程能够操作这个数据。为了实现这种保证,就需要一定形式的进程间同步。实现互斥有这样一些方法,禁止中断,执行测试和设置操作,禁止调度,使用信号量。

同步:是指在互斥的基础上(大多数情况),通过其它机制实现访问者对资源的有序访问。在大多数情况下,同步已经实现了互斥,特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

同步机制有critical sections(关键区域、临界区域),mutex(互斥器),semaphore(信号量),event(事件)。  
临界区:通过对多线程的串行化来访问公共资源或一段代码,速度快,适合控制数据访问。
互斥量:为协调共同对一个共享资源的单独访问而设计的。
信号量:为控制一个具有有限数量用户资源而设计,允许多个线程同时使用共享资源,这与操作系统中的PV操作相同。
事 件:用来通知线程有一些事件已发生,从而启动后继任务的开始。

临界区,进程中有一个代码段,在该段中,进程可能改变共同变量,当某一个进程进入临界区后,不允许其他进程再进入。因此临界区的执行在时间上互斥。

互斥器,跟临界区很相似,只有拥有互斥对象的线程才具有访问资源的权限,由于互斥对象只有一个,因此就决定了任何情况下此共享资源都不会同时被多个线程 所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出,以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同 一应用程序不同线程中实现资源的安全共享,而且可以在不同应用程序的线程之间实现对资源的安全共享。

信号量,允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore()创建信号量 时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数,每增加一个线程对共享资源的访问,当前可用资源计数 就会减1,只要当前可用资源计数是大于0的,就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目, 不能在允许其他线程的进入,此时的信号量信号将无法发出。线程在处理完共享资源后,应在离开的同时通过ReleaseSemaphore()函数将当前可 用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。

所谓的信号量,是一份数据,通过对它进行两个操作,一个是设置信号量signal,另一个是wait。当进程执行wait操作时,检查信号量的值,如果不为正,则它必须等待,等待完毕后会重设信号量使其值非正。而signal操作则完成信号的释放,使其值为正,从而让wait结束等待。等待可以通过忙等待实现,或者将它切换到阻塞状态。信号量机制的实现,依赖于wait和signal两个动作必须原子执行。这就等于把wait和signal做成临界区,对于单处理器可以通过在wait或者signal时,禁止中断来实现临界区。多个处理器情况下就不可以了。wait意味着该程序要等待,直到另一个进程执行signal为止。信号量与pv操作的过程基本一致。

事件

 

这样一些机制是由一些基本的通讯原语实现的,比如开锁和关锁,pv操作。

lock和unlock使用一个共享变量x代表临界资源的一个状态。x=0(临界资源可用)1(临界资源不可用),使用过程如下:
1.检查x的值,如果x==1,则陷入无限等待,返回继续检查;当x==0,表示资源可用,置x=1
2.进入临界区,访问临界区资源
3.释放临界区资源,置x=0

pv操作,更复杂,它可以避免无限等待,而使进程陷入阻塞状态。整个过程如下:
p操作P(s)
1.s=s-1
2.如果s>=0 表示有资源,则进程继续执行;如果s<0,则表示无资源,执行原语的进程被置为阻塞状态,并使其在s信号量的队列中等待,直到其他进程执行v操作释放它为止。

v操作V(s)
1.s=s+1
2.如果s>0 该进程继续执行;如果s<=0 则释放s信号量队列的排头等待者,并清楚其阻塞状态,转为就绪状态,执行V(s)者继续运行。(因为如果s<=0,说明在进程执行期间,有新的进程被阻塞,处在等待状态)

需要注意的是,pv操作都是低级通讯原语,也就是说在执行中各个动作都是不可分割的,不允许任何进程中断它的操作,这就保证了同时只有一个进程对信号量s进行p或者v操作。pv操作实际上是实现进程同步与互斥的一个基本工具。

lock和unlock可以看成是s初始为1的pv操作。pv操作放到一块,可以建立临界区,放到不同的地方,可以保证这两个地方执行的先后顺序。通过对一段程序,建立同一个s的pv操作

P(S)

V(S)可以建立临界区,这样就实现了互斥。

变换一下

P(s1)
A…
————–
B….
V(S1)

置S1初始为0,就可以保证A等待B执行完毕之后执行,由此可以实现同步。

 转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/709717672009815114239205/

You Might Also Like