存档

‘未分类’ 分类的存档

mark

2012年2月26日 sigma 没有评论 4,997 views
分类: 未分类 标签:

MIPS中LL/SC指令介绍

2011年12月14日 sigma 1 条评论 19,681 views

注:本文主要参考了IBM的《Linux 的 Spinlock 在 MIPS 多核处理器中的设计与实现》一文,需要更详细的关于spinlock的实现可以看前述文章。

在多线程程序中,为了实现对共享变量的互斥访问,一般都会用spinlock实现,而spinlock需要一个TestAndSet的原子操作。而这种原子操作是需要专门的硬件支持才能完成的,在MIPS中,是通过特殊的Load,Store操作LL(Load Linked,链接加载)以及SC(Store Conditional,条件存储)完成的。

LL 指令的功能是从内存中读取一个字,以实现接下来的 RMW(Read-Modify-Write) 操作;SC 指令的功能是向内存中写入一个字,以完成前面的 RMW 操作。LL/SC 指令的独特之处在于,它们不是一个简单的内存读取/写入的函数,当使用 LL 指令从内存中读取一个字之后,比如 LL d, off(b),处理器会记住 LL 指令的这次操作(会在 CPU 的寄存器中设置一个不可见的 bit 位),同时 LL 指令读取的地址 off(b) 也会保存在处理器的寄存器中。接下来的 SC 指令,比如 SC t, off(b),会检查上次 LL 指令执行后的 RMW 操作是否是原子操作(即不存在其它对这个地址的操作),如果是原子操作,则 t 的值将会被更新至内存中,同时 t 的值也会变为1,表示操作成功;反之,如果 RMW 的操作不是原子操作(即存在其它对这个地址的访问冲突),则 t 的值不会被更新至内存中,且 t 的值也会变为0,表示操作失败。

SC 指令执行失败的原因有两种:

  • 在 LL/SC 操作序列的过程中,发生了一个异常(或中断),这些异常(或中断)可能会打乱 RMW 操作的原子性。
  • 在多核处理器中,一个核在进行 RMW 操作时,别的核试图对同样的地址也进行操作,这会导致 SC 指令执行的失败。

在IBM的那篇文章中,并没有说明SC是如何实现RMW是否有冲突的操作的。在一般实现中,处理器有两个专门的域给LL和SC指令,即上文中的“不可见的bit位”以及保存ll操作地址的“寄存器”。再LL之后,处理器会监测各种事件,当发生异常或者有别的处理器对该地址发了invalid请求时,会将不可见的bit位重置,从而导致后面的SC失败。

由于这样的bit位只有一位,存ll的寄存器也只有一个,因此,LL/SC无法实现嵌套,也即无法实现嵌套锁,这是程序员使用LL/SC所需要注意的。

分类: 技术相关, 未分类 标签: , , ,

博客国内访问量突破1万,国际访问量突破2千,Mark

2011年5月23日 sigma 11 条评论 8,701 views

今天蓦然发现博客国内访问量突破一万了,国际也突破两千了,乘此机会写篇日志mark下,顺便记录下这个博客的历史。

建立时间:2010年9月20号(突然发现这是我科的校庆日,莫非冥冥之中自有天意)

截止今天(2011年5月24日):

共有文章101篇,包括本文共有102篇,去除其中的一篇hello world以及从live space导入的just for test,文章数恰好100篇。

总评论数为529,单篇评论数最多为47

单篇文章最高浏览量为:2929,页面总浏览量为28815

博客订阅量为:51

友链数为:15

Alaxe全球排名为749829,国内排名为42817

最近一月的访客数为:5123

最近一个月来自搜索引擎的访问比例为:26.23%

 

分类: 未分类 标签: , , , ,

存储一致性之释放一致性(Release Consistency)

2011年5月6日 sigma 1 条评论 28,304 views

倘若在弱一致性中,存储器能够区分进入还是离开临界区的话,应用起来会更有效。鉴于此,我们需要两种类型而非一个同步变量或操作。

释放一致性(Gharachorloo等,1990)提供了这样两种操作:

•获取(acquire)操作是用于通知数据存储进程进入临界区的操作。

•释放(release)操作是表明进程刚退出临界区。

释放一致性本质上和弱一致性相同,但是同步访问必须仅是处理机一致的。同步操作被分裂成获得(acquire)和释放(release)操作。

共享存储器在遵守以下规定时就是释放一致的:

  1. 在访问共享变量前,进程所有先前的获取操作都必须成功地完成;
  2. 在允许释放操作前,进程先前的所有读写操作都必须完成;
  3. 获取操作和释放操作必须是顺序一致的(这是胡老师《共享存储体系结构》一书的讲法,夏老师课件里讲的是顺序一致,具体哪种有待考证)。

存储器和软件的协议说明,当软件执行获取操作时,存储器会根据需要确保被保护数据的所有本地拷贝被更新为最新数据,并和远程数据拷贝保持一致。当执行释放操作时,修改的被保护变量要传送到其他机器上。执行获取操作并不能保证本地所作的修改会立即传送到其他本地拷贝。类似地,执行释放操作也不会必然地从其它拷贝引入所做的改变。

上图是释放一致性下的一个有效事件顺序。进程P1执行获取操作,两次改变共享变量x的值,然后执行释放操作。进程P2执行获取操作,并读取x。它应在释放操作时得到x的值为b(除非P2的获取操作先于P1的获取操作)。若P2的获取操作在P1的释放操作之前,则它必须等待到P1执行了释放操作。因为P3在读共享变量前没有执行获取操作,存储器不必给它x的当前值,因此返回a是允许的。

释放一致性分为渴望释放一致和懒惰释放一致性:

渴望释放一致性在执行释放操作后,执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机。因为没有办法判断它们是否确实需要它,为安全起见,它们将获得所有修改过的数据。尽管这样将所有数据传输出去的方法很直接,但通常不够有效。

在懒惰释放一致性中,在执行释放时,不发送任何数据。相反,在执行获取操作时,处理机试图从拥有这些变量的机器上取得它们的最新值。时间戳协议可用来确定需传送哪些变量。

存储一致性之弱一致性(Weak Consistency)

2011年5月6日 sigma 1 条评论 29,429 views

弱一致性WC(Week Consistency)模型的提出,是人们观察到大多数并行程序排定几个进程对数据存取次序时都需要使用同步操作;而在同步操作之间,一个进程所进行的数据存取操作次序对其他进程会是不可见的。例如,某进程对同步变量实施加锁后进入临界段,已在临界段内所做的存储器数据读写操作,由于互斥性其他进程根本看不到,更不用说读写操作次序了。

只是在此进程解锁退出临界段,其对共享变量所做的修改结果应立即被其他进程所看到,基于上述观察,我们可放宽对非同步读写操作次序的限制而只对同步存储器操作施加顺序一致性,来解决存储器一致性问题。

Dubois等(1986)定义这种使用同步变量来部分地定义的一致性模型为弱一致性:

weak consistency, by saying that it has three properties:

  1. Accesses to synchronization variables are sequentially consistent.
  2. No access to a synchronization variable is allowed to be performed until all previous writes have completed everywhere.
  3. No data access ( read or write ) is allowed to be performed until all previous accesses to synchronization variables have been performed.

中译为:

弱一致性,它有三个属性:

a. 对同步变量的访问是顺序一致的;

b. 在所有先前的写操作完成之前,不能访问同步变量;

c. 在先前所有同步变量的访问完成前,不能访问(读或写)数据。

弱一致性要求同步访问(访问要求执行同步操作)是顺序一致的。在一个同步访问可以被执行之前,所有以前正常的数据访问必须完成。在一个正常的数据访问可以被执行之前,所有以前同步访问必须完成。这实质上把一致性问题留给程序员决定。在一个同步操作之后,内存将立即是一致的。

第一点指出所有过程以相同顺序看到对同步变量进行的所有操作。即,如果进程P1调用synchronize(S1),与此同时进程P2调用synchronize(S2),那么,实际效果好象是synchronize(S1)发生在synchronize(S2) 之前,或synchronize(S2)发生在synchronize(S1) 之前,但所有进程看到同样的顺序。实际上,一个同步变量的访问将立即被广播出去。在广播发送结束之前,任意其他进程不能访问其他同步变量。

第二点指出访问同步变量“刷新了管道”,它强迫在所有拷贝上完成所有程序中的写操作。其中包括正在执行的、部分完成的或已经在某些本地拷贝上完成却未在其它拷贝上完成的写操作。同步访问开始前,应保证先前所有的写操作已完成。在更新共享数据后做同步操作,进程可迫使将新值传遍到该存储的所有其它本地拷贝。

第三点指出访问一般(即非同步)变量,不管是读是写,只有在所有前序的同步操作结束后方可进行。在读共享数据前做同步操作,可以保证进程读到最新值。

从应用的角度来说,软件和存储器的协议指出,只有当访问同步变量时,存储器才需更新;新的写操作可以在前一写操作完成之前开始,在一些情况下可完全避免写。当然,此协议加重了编程人员的负担,但换来了优越的性能。

不同于以往的存储器模型,它是对一组操作的一致性约束,而不是单独的读或写。当很少单独而基本上以簇的形式(短时间内有很多访问,每一访问时间都不长)访问共亨变量时,这个模型更为有用。

弱一致性存在这样的问题,即当访问同步变量时,存储器并不知道这是因为进程已完成对共享数据的写操作还是要开始读共享数据。因此,它必须执行这两种情况要求的操作,也就是它要确保本地启动的写操作都已完成(即发送到其他所有的拷贝),同时还要收集其他机器执行的写操作。

弱一致性的示意图如下:

无觅相关文章插件,快速提升流量