注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

白鸟无言

Welcome to theWraith's space

 
 
 

日志

 
 

MySql中互斥量mutex的实现  

2008-12-27 23:04:14|  分类: 技术 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

数据库中的Mutex量指的是一种用于保护一些临界资源的使用的信号量。当有线程需要使用这些临界资源时,会请求获得mutex量,请求成功的线程进入临界区,而请求失败的线程只能等待它释放这个mutex。互斥信号量在计算机软件层面以上可以看作是实现并发操作的一个原子动作,但在数据库(操作系统)这种高并发多线程的基础软件中,需要精心设计以获得高吞吐量和良好响应时间。

Mysql中的mutex实现机制大致描述如下(基于Windows操作系统):

数据结构:在mutex结构中,有:

Ø        event:操作系统提供的信号量;

Ø        lock_word:锁,这是一个机器字长的数,为1说明mutex有人使用,为0则没有。

Ø        waiters:标志有无人在等待这个mutex,同样是机器字长的数

Ø        list:一个list把系统所有的mutex连起来,这里不用关注

Ø        其它一些debugInfo,不用关注。

同时MySql维护一个全局等待队列sync_primary_wait_array,在当中有:

Ø        array:一个cell数组,每个cell中是一个等待对象的描述,包括等待类型request_type,等待对象指针object、等待线程ID,waiting布尔量表示是否在等待,这个数组在全局等待队列sync_primary_wait_array初始化时被初始化为系统最大线程数目大小。

Ø        os_mutex:一个操作系统提供的互斥量,使用它保护这个全局等待队列。

Ø        其它信息,不用关注。

 

 

 

当一个线程开始请求一个mutex,它按照以下步骤来进行:

1)TestAndSet,使用一条汇编指令来尝试获得这个mutex,这个动作是计算机原子的。

2)如果操作成功,则mutex中的lock_word被置成1,本线程返回,可以进行临界区操作。

3)如果失败,开始一个spinLock的过程(所谓spin就是指去扭转一个门把手,如果扭不开把手会转回来,然后就继续去扭直到它开为止,很形象的一个过程,呵呵),不停循环并且读lock_ward的值,发现为0了(注意,是脏读,所以去TestAndSet仍然可能失败)则再次去执行TestAndSet。若置位成功了,则返回。

4)spinLock循环到了一定次数,不能继续spin下去了,否则太消耗CPU资源,此时本线程睡眠,醒来后再尝试一次TestAndSet,若成功了,则返回。

5)进入全局等待队列sync_primary_wait_array中,通过队列中的os_mutex保证此时在队列中的操作是唯一的。找到一个空的Cell,把它的对象指针object指向自己,等待线程ID设为自己的ID号,request_type设置为MUTEX,waiting设为FALSE,同时调用操作系统接口reset互斥量mutex上的event(API: ResetEvent),退出全局等待队列。

6)把mutex中的waiters设为1,标志有人在等待这个mutex,这个动作使用了一个volatile 的指针来改这个值,以保证这个值被立即写回内存。

7)这时再尝试去做几次TestAndSet(垂死挣扎^_^),若成功了,回去把全局等待队列sync_primary_wait_array中自己刚拿到的cell清空掉,并返回。

8)进入全局等待队列sync_primary_wait_array,把自己的cell里的waiting标识为TRUE,拿到event后退出全局队列。

9)等待在这个event上直到被唤醒(API:WaitForSingleObject),被唤醒后立即进入全局等待队列里放掉自己的cell,再继续从1)开始。

 

 

接下来是线程释放mutex的步骤:

1)ResetLock,同样使用一条汇编指令将mutex中的lock_word设置为0;

2)检查mutex上的waiters是否为1,如果是,则执行下面3)4)两步的唤醒例程,否则返回。

3)先将waiters设置为0,这同样使用一个volatile的指针来做。

4)将mutex上的event唤醒(API:SetEvent)。

 

分析:

       MySql的mutex实现依据如下思想:先反复尝试一小段时间(spin);若不成功,不能继续无止境地浪费CPU,只好进入休眠;休眠一段时间醒来还是获得不了,则只好等待释放mutex的人来将自己唤醒。Mutex的实现需要小心两种情况:1是出现mutex保护失败,两个线程同时获得了临界区。在这套实现机制中,明显在spin和Sleep的过程中获得的mutex是安全的,因为它们是通过汇编原语来得到的mutex,而一旦进入event等待再被唤醒的人也必须重新使用TestAndSet来获得mutex,所以这种情况是不可能的。2是某个线程被永远“遗忘”在获得mutex的过程内,成为了死线程。在spin和sleep的过程中是不可能的,因为线程会主动醒来不断尝试。而线程如果进入了event等待,那么它也一定会在将来被另一个线程唤醒。(但是请注意,这是按我们上面的序列来执行的理论情况,人真的能相信计算机的行为吗?后面会有答案的)下面先证明这点:

在一个线程A进入event等待前,它做了这样的步骤:

1.        resetEvent

2.        将waiter置为1

3.        再去尝试几下

4.        等待在event上

在这个过程结束后,是不可能出现没有其它任何线程在持有这个mutex而event仍然不是signal状态的。因为线程A在将waiter置为1后又去尝试了几次,这时仍然是得不到的(垂死挣扎是关键1)!明显这时候肯定还有一个线程B在持有这个mutex,而这个线程B在结束的时候,是不可能不看到这个waiter为1的(因为waiter的修改是用了volatile的声明指针)。这时这个线程B肯定要去调用一次setEvent(关键2),从而保证了A线程不可能被“遗忘”。

但是线程在看到waiter为1的时候,是不能保证确实有其它线程在等待event的。考虑这样一个序列:

Ø        一个线程A请求获得mutex,在到达步骤6之前,mutex被B持有。

Ø        在A执行6之前的时间,B释放了mutex,这时B读到的waiters还是0,B直接返回。

Ø        A把waiters设置为1,然后再去垂死挣扎做TestAndSet,这时由于B已经释放了mutex,A成功,A放掉自己的cell并返回。这时waiter的值为1,而mutex上是没有人在等待这个event的。当A放mutex的时候,会去唤醒event,但这没有什么问题,因为当线程发现自己有可能要等待的时候,是会重新在步骤5)里面resetEvent的。

看起来这个mutex是安全的了吧?错!这个序列行为理论上是安全的,但计算机可未必一定按你想像的去做...在MySql的源代码中就有一段说明,众所周知,在超线程的CPU上指令的执行是可能乱序执行的,只要这个乱序行为的指令不具有代码相关性。在释放mutex的步骤中的1)和2),这两条指令就没有代码相关性,如果在做1)的动作前2)超前被执行了的话,上面所有的假设都成了水月镜花......这时候考虑一个序列:

Ø        一个线程A持有着mutex,另一个线程B开始申请。

Ø        在B执行6之前,A先执行了释放步骤中的2),此时waiters是0,这时A的时间片到了,A被切换。

Ø        B一路执行下去,由于A没有resetLock,B是无法成功了,只好去等待在event上

Ø        A回来resetLock,它的堆栈现场里waiters还是0,A潇洒的离开了。于是B就悲剧地永远等在了event上,如果再也没有其它线程来申请这个mutex的话。

为了避免这个情况,MySql只得使用后台线程来定期检查这个全局队列(其实这也是全局队列需要存在的必要原因),发现有被“遗忘”的线程则去唤醒它。

可见数据库中的mutex是一个需要考虑硬件实现,并且要考虑多种资源的平衡因素的关键性数据结构。但MySql的实现个人认为过于复杂了,Mutex作为一个可以看作是数据库级别的最轻量级并发控制器,不应该被考虑用于平均时间过长的临界区。性能才是mutex应该衡量的最关键因素。

  评论这张
 
阅读(1503)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017