读写锁

Locker: 谁拥有锁。例如Transaction、Thread。

Lock: 锁。一个有状态的对象。

Locked Object: 需要多线程并发访问,所以被用锁保护的对象,如table、data record。

相容性

R

W

R

O

X

W

X

X

读写锁的实现多种多样,而posix标准关于细节上却写的很含糊。所以每拿到一个读写锁的实现的时候,我要先考虑如下疑问:

  1. Release preference: 如果一个writer释放它所拥有的写锁,此时既有reader也有writer在等锁,那么谁将获得锁? reader? writer? 还是无论类型,谁先请求谁就先得到?
  2. 读写优先级:如果一个locker已经拥有读锁,一个locker来请求写锁,那么必然会被阻塞。此后,另一个locker来请求读锁,那么它能立即获得读锁吗?
  3. 降级:如果一个locker已经获得写锁,它想换成读锁。那么释放写锁和获取读锁这两个操作是原子的吗?(很少用,所以下面不考虑它)
  4. 升级:如果一个locker已经获得读锁,它想升级成写锁。此时已经有其它的locker也在请求锁,这个locker是否具有优先于其它locker的权利立马获得写锁?

读锁升级操作很容易造成死锁,假设有两个locker A、B都已获得读锁,然后A申请升级,此时还不能得到锁,因为B的锁还没释放。之后B也去申请升级,那么就死锁了。

对于事物处理系统,一般来说,读数据的时候,自动获取读锁,写数据的时候自动获取写锁,如果要达到可串行化的隔离度,那么所有的锁都保持到存储过程结束才释放。如果不明白读写锁的升级操作的可怕之处,那么死锁将会四处潜伏。

下面以一段基于BerkeleyDB的代码为例:

void myfunc(DB_TXN* txn){
    DBT key,value;
    key=…..;
    //读出来。此时拿的是读锁。
    db->get(db, txn,&key,&value,0);
    //修改
    *((int*)value.data)=0;
    //写回去。此时需要申请写锁。
    db->put(db, txn,&key,&value,0);
}

如果有两个线程试图同时执行上面这个函数,则有可能会发生死锁。为此,Berkeley DB为get方法提供了一个flags字段,DB_RMW,如果以这样的方式去读数据

db->get(db, txn,&key,&value,'DB_RMW');

那么此时拿的就是写锁而不是读锁。

但是实际上,我们开发的时候需要把复杂的逻辑抽象成多个函数然后串行执行。那么前面的函数怎么会知道后面的函数是否会执行put操作呢??难道要在函数声明中写“调用过我之后就不允许再调用xxx、xxx、xxx和xxxx函数”??为了彻底的防止因读写锁升级而造成的死锁,那么就必须在每个存储过程一开始的时候,先确定自己会修改哪些表的哪些行。实际上有些函数的实现远远不像它名字所暗示的那样,例如int getRoleLevel(long roleid)。 它是根据角色信息获取人物等级。然而读取人物数据的时候会检查封禁时间,如果到期会解除封禁,于是就会写数据。而这一点只有实现封禁操作的人才知道,其它人不知道会这样。况且,这样的功能往往是到了后期才以补丁的方式出现在代码中,十分可怕。getXXX未必就真的不会写数据库!

如果locker拿不到读锁,那么有两种可能性:

  1. 有其它locker已经拿到写锁。
  2. 有其它locker已经拿到读锁,并且已经有其它locker在等待写锁。

如果locker拿不到写锁,那么只有一种可能性,有其它locker拥有这个锁。(无论是读还是写)。

出现等待环是死锁产生的必要条件。而等待只发生在两种情况:

  1. 请求一个现在不拥有的锁
  2. 读锁升级为写锁

对于第二种情况,如果在某个函数中发生了锁升级操作,那么就意味着这个函数本身就一定不支持多个线程并发执行(否则我们就需要deadlock detector)。而对于第一种情况,采用和mutex同样的策略,只要拿锁顺序的顺序是一致的,就不会出现循环等待。

之前我总是从事务的角度考虑。事务可以分为ACID 4个方面去分析。但是其实对于key-value DB来说,很难说清楚C是什么。而D,其实都不怎么关心。通常来说都是delay write。最近又看到一个概念,soft transactional memory。也许可以把key value数据库拆成硬盘数据如何索引、不同层级的存储器之间如何cache和如何实现soft transactional memory这么三个方面去考虑

最近还在想,关于同步原语。之前一直在用C++,五花八门的同步方式,但是基本都是mutex、cond var的组合或变种罢了。但是凭什么一切同步方式都要基于他俩呢? 其实最初,在单CPU上,mutex用的也是compare-and-swap这样的原子操作实现的啊。所以有很多文章在讲如何通过扩展同步原语的集合,例如JDK本身对整数提供了compareAndSet方法,来做到lock free。 其实lock free和wait free是两个很让人容易混淆的概念,在IBM的网站上有篇文章讲的比较细,https://www.ibm.com/developerworks/java/library/j-jtp11234/,compare-and-swap模式、ABA问题、lock free和wait free的区别,等等。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥