win8扁平化网站,前端网站开发一个月多少钱,dz整站网站建设,淘宝优惠券网站建设【MyDB】4-VersionManager 之 3-死锁及超时检测 死锁及超时检测案例背景LockTable锁请求与等待管理 addvm调用addputIntoList#xff0c;isInList#xff0c;removeFromList 死锁检测 hasDeadLock方法资源释放与重分配 参考资料 死锁及超时检测 本章涉及代码#xff1a;top/… 【MyDB】4-VersionManager 之 3-死锁及超时检测 死锁及超时检测案例背景LockTable锁请求与等待管理 addvm调用addputIntoListisInListremoveFromList 死锁检测 hasDeadLock方法资源释放与重分配 参考资料 死锁及超时检测 本章涉及代码top/xianghua/mydb/server/vm/LockTable.java 案例背景
学习如何使用 LockTable 进行锁管理、死锁检测与解决之前先了解一下死锁是如何发生的。假设我们有三个事务 T1、T2 和 T3它们分别要访问两个资源 R1 和 R2。事务的执行顺序如下
T1 锁定 R1然后尝试锁定 R2。T2 锁定 R2然后尝试锁定 R1。T3 尝试锁定 R1。
这种情况下T1 和 T2 之间会产生死锁而 T3 将会被阻塞在等待 R1 上。
执行过程
T1 锁定 R1 T1 请求锁定资源 R1。因为 R1 未被占用所以 LockTable 将 R1 锁定给 T1。T1 继续执行准备请求锁定 R2。 T2 锁定 R2 T2 请求锁定资源 R2。因为 R2 未被占用所以 LockTable 将 R2 锁定给 T2。T2 继续执行准备请求锁定 R1。 T1 请求锁定 R2 T1 请求锁定 R2。由于 R2 已被 T2 锁定T1 被加入到 R2 的等待队列中。 T2 请求锁定 R1 T2 请求锁定 R1。由于 R1 已被 T1 锁定T2 被加入到 R1 的等待队列中。现在形成了 T1 → R2 → T2 → R1 → T1 的循环等待导致死锁。 T3 尝试锁定 R1 T3 请求锁定 R1。由于 R1 已被 T1 锁定且 T2 在等待 R1T3 被加入到 R1 的等待队列中。
LockTable
上一章提到了2PL会阻塞事务直至持有锁的线程释放锁。这样就可能出现死锁。因此在MyDB中需要能检测死锁。
我们可以将事务之间的这种等待关系抽象成有向边例如 T j T_j Tj在等待 T i T_i Ti。这样无数的有向边就可以形成一个图不一定是连通图。检测死锁的话只需要查看图中是否有环。
就MyDB而言使用了一个LockTabel对象通过在内存中维护这张图而记录事务的等待关系。 注意x2u和wait是列表分别记录xid已经获得的资源的uid列表和正在等待某个uid的xid列表。 public class LockTable {private MapLong, ListLong x2u; // 某个XID已经获得的资源的UID列表private MapLong, Long u2x; // UID被某个XID持有private MapLong, ListLong wait; // 正在等待UID的XID列表private MapLong, Lock waitLock; // 正在等待资源的XID的锁private MapLong, Long waitU; // XID正在等待的UIDprivate Lock lock;...
}锁请求与等待管理 add
当一个事务请求获取某个资源时LockTable 首先会检查该资源是否已被其他事务持有。如果没有被持有资源将直接分配给请求的事务。如果资源已被占用事务将进入等待状态并存储在相应的等待队列中。 检查当前事务xid是否已经获得了数据uidisInList(x2u, xid, uid) 判断uid是否被其他xid持有u2x.containsKey(uid)假如未被其他xid持有则直接获得 u2x.put(uid, xid); // MapLong, Long u2x; UID被某个XID持有 putIntoList(x2u, xid, uid); //MapLong, List x2u 某个XID已经获得的资源的UID列表 被持有则等待向依赖等待图中添加当前等待关系即waitU.put(xid, uid);之后进行死锁检测hasDeadLock。如果检测到死锁就撤销这条边不允许添加并撤销该事务。 // 不需要等待则返回null否则返回锁对象// 会造成死锁则抛出异常public Lock add(long xid, long uid) throws Exception {// 1. 加锁lock.lock();try {// 2. xid是否已经获得了uid是则说明不需要等待返回nullif(isInList(x2u, xid, uid)) {return null;}// 3. uid是否被其他xid持有if(!u2x.containsKey(uid)) {// 3.1 uid未被其他xid持有则直接获得u2x.put(uid, xid);putIntoList(x2u, xid, uid);return null;}// 3.2 uid被其他xid持有则等待waitU.put(xid, uid);//putIntoList(wait, xid, uid);putIntoList(wait, uid, xid); // 这里是为了方便死锁检测因为死锁检测是从等待队列中选择一个xid来占用uidif(hasDeadLock()) {waitU.remove(xid);removeFromList(wait, uid, xid);throw Error.DeadlockException;}Lock l new ReentrantLock();l.lock();waitLock.put(xid, l);return l;} finally {lock.unlock();}}vm调用add
在vm中当某个事务xid需要资源uid时就会调用add可以看到add方法需要等待的时候会返回一个上了锁的Lock对象。调用方在获取到该对象时需要尝试获取该对象的锁由此实现阻塞线程的目的例如
Lock l lt.add(xid, uid);
if(l ! null) {l.lock(); // 阻塞在这一步l.unlock();
}putIntoListisInListremoveFromList
由于之前说过我们再复习一下LockTable中的x2u和wait是long-List
private MapLong, List x2u; // 某个XID已经获得的资源的UID列表
private MapLong, List wait; // 正在等待UID的XID列表
那当我们需要知道事务是否已经获得资源uid时由于x2u.get(xid)得到的时一个资源list因此需要使用inInList来判断uid是否在xid已经获得的资源list中。
同理当需要向x2u中添加某个xid已经获得的资源uid也不能直接添加而是要先获得x2u已经获得的资源的uid list之后再向其中添加就用到了putIntoList方法。
public class LockTable {private MapLong, ListLong x2u; // 某个XID已经获得的资源的UID列表private MapLong, Long u2x; // UID被某个XID持有private MapLong, ListLong wait; // 正在等待UID的XID列表private MapLong, Lock waitLock; // 正在等待资源的XID的锁private MapLong, Long waitU; // XID正在等待的UIDprivate Lock lock;...
}putIntoList /*** 将uid1添加到uid0对应的列表中* param listMap* param id0* param id1*/private void putIntoList(MapLong, ListLong listMap, long id0, long id1) {// 如果id0对应的列表不存在则创建一个新的列表if(!listMap.containsKey(id0)) {listMap.put(id0, new ArrayList());}// 将id1添加到id0对应的列表中listMap.get(id0).add(0, id1);}
isInList(listMap,id0,id1)id1是否在id0对应的列表中
/*** 判断id1是否在id0对应的列表中* param listMap* param id0* param id1* return*/private boolean isInList(MapLong, ListLong listMap, long id0, long id1) {ListLong l listMap.get(id0);if(l null) return false;IteratorLong i l.iterator();while(i.hasNext()) {long e i.next();if(e id1) {return true;}}return false;}removeFromList从uid0对应的列表中删除uid1 /*** 从uid0对应的列表中删除uid1* param listMap* param uid0* param uid1*/private void removeFromList(MapLong, ListLong listMap, long uid0, long uid1) {ListLong l listMap.get(uid0);if(l null) return;IteratorLong i l.iterator();while(i.hasNext()) {long e i.next();if(e uid1) {i.remove();break;}}if(l.size() 0) {listMap.remove(uid0);}}死锁检测 hasDeadLock方法
为了避免死锁LockTable 实现了基于深度优先搜索DFS的死锁检测机制。通过遍历事务依赖图系统可以检测到是否存在循环依赖从而识别死锁。
需要注意这个图不一定是连通图。思路就是为每个节点设置一个访问戳xidStamp都初始化为 -1随后遍历所有节点以每个非 -1 的节点作为根进行深搜并将深搜该连通图中遇到的所有节点都设置为同一个数字不同的连通图数字不同。这样如果在遍历某个图时遇到了之前遍历过的节点说明出现了环。 private MapLong, Integer xidStamp; // XID对应的stampprivate int stamp; // 当前stampprivate boolean hasDeadLock() {xidStamp new HashMap();stamp 1;for(long xid : x2u.keySet()) {Integer s xidStamp.get(xid);if(s ! null s 0) {continue;}stamp ;if(dfs(xid)) {return true;}}return false;}private boolean dfs(long xid) {Integer stp xidStamp.get(xid);if(stp ! null stp stamp) {return true;}if(stp ! null stp stamp) {return false;}xidStamp.put(xid, stamp);Long uid waitU.get(xid); // 得到事务xid等待的资源uidif(uid null) return false; // 没有等待的资源Long x u2x.get(uid); //找到占用资源uid的事务xassert x ! null;return dfs(x); // 继续搜索事务x}可以在LockTabelTest中运行testLockTable以检测死锁的发生 public void testLockTable() {LockTable lt new LockTable();try {lt.add(1, 1);} catch (Exception e) {Panic.panic(e);}try {lt.add(2, 2);} catch (Exception e) {Panic.panic(e);}try {lt.add(2, 1);} catch (Exception e) {Panic.panic(e);}try {lt.add(1, 2);} catch (Exception e) {Panic.panic(e);}assertThrows(RuntimeException.class, ()-lt.add(1, 2));}资源释放与重分配
在一个事务 commit 或者 abort 时就可以释放所有它持有的锁并将自身从等待图中删除。然后将资源锁重新分配给等待队列中的其他事务。
while 循环释放掉了这个线程所有持有的资源的锁这些资源可以被等待的线程所获取 public void remove(long xid) {lock.lock();try {// 1. 释放xid所占用的资源列表uidsListLong uids x2u.get(xid);if(uids ! null) {while(uids.size() 0) {Long uid uids.remove(0);selectNewXID(uid); // 从等待队列中选择一个xid来占用uid}}// 2. 在waitU(正在等待资源的xid)x2u(某个XID已经获得的资源的UID列表),waitLock中删除xid:waitU.remove(xid);x2u.remove(xid);waitLock.remove(xid);} finally {lock.unlock();}}selectNewXID
从 List 开头开始尝试解锁还是个公平锁。解锁时将该 Lock 对象 unlock 即可这样业务线程就获取到了锁就可以继续执行了。 // 从等待队列中选择一个xid来占用uidprivate void selectNewXID(long uid) {// u2x:uid被某个xid持有// 1. 从u2x中释放uid标记uid不再被xid占用u2x.remove(uid);// 2. 获取该uid的等待队列xidsListLong xids wait.get(uid); // wait:uid被哪些xid等待if(xids null) return;assert xids.size() 0;// 3. 从等待队列中选择一个xid来占用uidwhile(xids.size() 0) {long xid xids.remove(0);if(!waitLock.containsKey(xid)) {continue;} else {u2x.put(uid, xid);Lock lo waitLock.remove(xid);waitU.remove(xid);lo.unlock();break;}}if(xids.size() 0) wait.remove(uid);}参考资料
死锁及超时检测 | EasyDB (blockcloth.cn)
MYDB 7. 死锁检测与 VM 的实现 | 信也のブログ (shinya.click)
