从硬件同步原语看非阻塞同步以及Java中的应用

  非阻塞同步:基于冲突检测的乐观并发策略,通俗讲就是先进行操作,如果没有其他线程争用共享数据,那操作就成功了,如果争用数据有冲突那就采用其他的补偿措施(最常见的就是不断重试直到成功),这种乐观的并发策略使得很多线程不需要因为竞争失败直接挂起,这种同步措施称为非阻塞同步。下面我们就从硬件原语开始了解非阻塞同步,并看一看在Java中非阻塞同步的一些应用。

一、从硬件原语上理解同步(非特指Java)

  同步机制是多处理机系统的重要组成部分,其实现方式除了关系到计算的正确性之外还有效率的问题。同步机制的实现通常是在硬件提供的同步指令的基础上,在通过用户级别软件例程实现的。上面说到的乐观策略实际上就是建立在硬件指令集的基础上的(我们需要实际操作和冲突检测是原子性的),一般有下面的常用指令:测试并设置(test_and_set)、获取并增加(fetch_and_increment)、原子交换(Atomic_Exchange)、比较并交换(CAS)、加载连接条件存储(LL/SC),下面我们会讲到这些以及通过这些硬件同步原语实现的旋转锁和栅栏同步。

1、基本硬件原语

  在多处理机中实现同步,所需的主要功能是一组能以原子操作读出并修改存储单元的硬件原语。如果没有这种操作,建立基本的同步原语的代价会非常大。基本硬件原语有几种形式提供选择,他们都能以原子操作的方式读改存储单元,并指出进行的操作是否能以原子形式进行,这些原语作为基本构建提供构造各种各样的用户及同步操作。

  一个典型的例子就是原子交换(Atomic Exchange),他的功能是将一个存储单元中的值和一个寄存器的值进行交换。我们看看这个原语怎样构造一个我们通常意义上说的简单的锁。

  假设现在我们构造这样一个简单的锁:其值为0表示锁是开的(锁可用),为1表示上锁(不可用)。当处理器要给该锁上锁的时候,将对应于该锁的存储单元的值与存放在某个寄存器中的1进行交换。如果别的处理器已经上了锁,那么交换指令返回的值为1否则为0。返回0的时候,因为是原子交换,锁的值就会从0变为1表示上锁成功;返回1,原子交换锁的值还是1,但是返回1表示已经被上了锁。 我们考虑使用这个锁:假设两个处理器同时进行交换操作(原子交换),竞争的结果就是,只有一个处理器会先执行成功而得到返回值0,而另一个得到的返回值为1表示已经被上锁。从这些我们可以看出,采用原子交换指令是实现同步的关键:这个原子交换操作的不可再分的,两个交换操作将由写顺序机制确定先后顺序,这也保证了两个线程不能同时获取同步变量锁。

  除此之外,还有别的原语可以实现同步(关键都在于能以原子的方式读-改-写存储单元的值)。例如:测试并置定(test_and_set)(先测试一个存储单元的值,如果符合条件就修改其值),另一个同步原语是读取并加1(fetch_and_increment))(返回存储单元的值并自动增加该值)。(看到这里可以回忆一下Java中的CAS操作的实现以及在Java中的实现原理)

  那么,上面的基本原语操作又是怎样实现的呢,这在一条指令中完成上述操作显然是困难的(在一条不可中断的指令中完成一次存储器的读改写,而且要求不允许其他的访存操作还要避免死锁)。现在的计算机上采用一对指令来实现上述的同步原语。该指令对由两条特殊的指令组成,一条是特殊的load指令(LL指令),另一条是特殊的store指令(SC)。指令的执行顺序是:如果LL指令指明的存储单元的值在SC对其进行写之前被其他的指令改写过,则第二条指令执行失败,如果在两条指令之间进行切换也会导致执行SC失败,而SC指令将通过返回一个值来指出该指令操作是否成功(如果返回的1表示执行成功,返回0表示失败)。为什么说这对指令相当于原子操作呢,这指的是是所有其他处理器进行的操作或者在这对指令之前执行或者在其后执行,不存在两条指令之间进行,所以在这一对指令之间不存在任何其他处理器改变相应存储单元的值。

  下面是一段实现对R1指出的存储单元进行的原子交换操作

1 try:OR R3,R4,R0 //R4中为交换值,将该值送入R3 2 LL R2,0(R1) //将0(R1)中的值取到R2 3 SC R3,0(R1) //若0(R1)中的值与R3中的值相同,则置R3的值为1,否则为0 4 BEQZ R3,try //R3的值为0表示存失败,转移重新尝试 5 MOV R4,R2 //成功,将取出的值送往R4

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwffpz.html