一、基本概念
在数据库中,对某数据的两个基本操作为写和读,分布有两种锁控制:排它锁(X锁)、共享锁(S锁)。
排它锁(x锁):若事务T对数据D加X锁,则其它任何事务都不能再对D加任何类型的锁,直至T释放D上的X锁;
一般要求在修改数据前要向该数据加排它锁,所以排它锁又称为写锁。
共享锁(s锁):若事务T对数据D加S锁,则其它事务只能对D加S锁,而不能加X锁,直至T释放D上的S锁;
一般要求在读取数据前要向该数据加共享锁, 所以共享锁又称读锁。
程序所收到的请求包括以下五种:Start、End、XLock、SLock、Unlock
Start:开启相应的事件请求
End: 关闭相应的事件请求
XLock: 对数据对象D添加X锁,进行写操作(当事件以对数据A加入S锁时,此时可升级为X锁)
SLock: 对数据对象D添加S锁,进行读操作
Unlock: 对数据对象D进行解锁(对数据D的X/S锁解绑,并检查等待队列)
本程序并不进行死锁检测以及死锁预防,对于等待队列采取FIFO原则进行。
二、数据结构
读写锁维护一个数据D的状态表,标记当前数据D的实时状态,锁表的信息随着事务的执行动态更新,反映当前的锁状态。
其数据结构如下图所示:
其中:mObjectList:为map结构的对象树,可方便快速查找相应对象。
objectName:为对象数据D的名称
curXLockTrans: 为当前写操作的事件
waitingTransList: 为写等待队列
shareList: 为共享集(当curXLockTrans不为空时,变为共享等待队列)
事件ID的数据结构如下:
其中:mTransId: 为map结构的事件树,可以快速的查找相应事件
tranId: 为事件名称
curLockObjList: 为此事件目前所操作的对象列表
三、源代码
本程序为所的锁管理接口,所以封装成类,方便程序调用。程序源码可以点击这里下载。
数据结构如下:
1 class LMer { 2 3 private: 4 5 struct object 6 { 7 string objectName; 8 string curXLockTrans; 9 queue<string> waitingTransList; 10 set<string> shareList; 11 }; 12 13 struct transId 14 { 15 string tranId; 16 set<object*> curLockObjList; 17 }; 18 19 map<string, object*> mObjectList; 20 map<string, transId*> mTransId; 21 22 public: 23 24 LMer(){} 25 string LMer::handleInput(vector<string>& vInput); 26 void LMer::handleAction(string sAction, transId* trId, object* obj, string& result); 27 void LMer::diviTransID(transId* trId, object* pObj, string& result); 28 };
逻辑结构实现如下:
1 string LMer::handleInput(vector<string>& vInput) 2 { 3 string result = ""; 4 //二参数输入 5 if (vInput.size() == 2) 6 { //进程存在,进入下一步 7 map<string, transId*>::iterator transIt = mTransId.find(vInput[1]); 8 if (transIt != mTransId.end()) 9 { 10 //是否结束事件(结束事件队列中所有事件) 11 if (vInput[0] == "End") 12 { 13 result += "tTransaction "+ vInput[1] +" endednttt"; 14 //解绑进程所有事物 15 set<object*>::iterator obj_index; 16 while(transIt->second->curLockObjList.size() != 0) 17 { 18 obj_index = transIt->second->curLockObjList.begin(); 19 diviTransID(transIt->second, *obj_index, result); 20 } 21 //清空请求事件 22 mTransId.erase(transIt); 23 } 24 } 25 else if(vInput[0] == "Start")//为start,创立进程 26 { 27 transId* pTransId = new transId(); 28 pTransId->tranId = vInput[1]; 29 //将此进程加入进程树中 30 mTransId[vInput[1]] = pTransId; 31 result += "Transaction " + vInput[1] +" startedn"; 32 } 33 } 34 else //三参数输入 35 { //创建新操作对象 36 if(mObjectList.find(vInput[2]) == mObjectList.end()) 37 { 38 object* pObjectIndex = new object(); 39 pObjectIndex->objectName = vInput[2]; 40 pObjectIndex->curXLockTrans = ""; 41 mObjectList[vInput[2]] = pObjectIndex; 42 } 43 44 if (vInput[0] == "Unlock") 45 { 46 //解锁trans->obj 47 diviTransID(mTransId[vInput[1]], mObjectList[vInput[2]], result); 48 } 49 else//进行常规处理(Xlock、Slock) 50 { 51 //进行处理 52 handleAction(vInput[0], mTransId[vInput[1]], mObjectList[vInput[2]], result); 53 } 54 } 55 56 return result; 57 } 58 59 void LMer::handleAction(string sAction, transId* trId, object* obj, string& result) 60 { 61 //检查是否有占用 62 if (sAction == "SLock") 63 { 64 if (obj->curXLockTrans == "") 65 { 66 obj->shareList.insert(trId->tranId); 67 trId->curLockObjList.insert(obj); 68 result += "S-Lock granted to "+ trId->tranId +"n"; 69 } 70 else//被占用 71 { 72 obj->shareList.insert(trId->tranId); 73 result += "Waiting for lock (X-lock held by: "+ obj->curXLockTrans +")n"; 74 } 75 } 76 else if(sAction == "XLock") 77 { 78 //未有写操作 79 if (obj->curXLockTrans == "") 80 { 81 int shareNum = obj->shareList.size(); 82 if (shareNum > 1) 83 { 84 string sTemp = ""; 85 for (set<string>::iterator it_index = obj->shareList.begin(); 86 it_index != obj->shareList.end(); it_index++) 87 { 88 sTemp += " " + *it_index; 89 } 90 obj->waitingTransList.push(trId->tranId); 91 result += "Waiting for lock (S-lock held by:" + sTemp + "n"; 92 } 93 else if (shareNum == 1) 94 { 95 //update 96 if (*(obj->shareList.begin()) == trId->tranId) 97 { 98 obj->curXLockTrans = trId->tranId; 99 obj->shareList.clear(); 100 result += "Upgrade to XLock grantedn"; 101 } 102 else 103 { 104 obj->waitingTransList.push(trId->tranId); 105 result += "Waiting for lock (S-lock held by:" + *(obj->shareList.begin()) + ")n"; 106 } 107 } 108 else if (shareNum == 0) 109 { 110 obj->curXLockTrans = trId->tranId; 111 trId->curLockObjList.insert(obj); 112 result += "XLock grantedn"; 113 } 114 } 115 else//当前存在写操作 116 { 117 obj->waitingTransList.push(trId->tranId); 118 result += "Waiting for lock (X-lock held by: "+ obj->curXLockTrans +")n"; 119 } 120 } 121 } 122 123 void LMer::diviTransID(transId* trId, object* pObj, string& result) 124 { 125 if(pObj->curXLockTrans != "") 126 { 127 //对写操作解绑 128 if (pObj->curXLockTrans == trId->tranId) 129 { 130 pObj->curXLockTrans = ""; 131 trId->curLockObjList.erase(pObj); 132 result += "Lock releasednttt"; 133 } 134 else 135 { 136 result += "I can not find the transaction.nttt"; 137 } 138 }//对共享读集合解绑 139 else 140 { 141 set<string>::iterator shareIndex = pObj->shareList.find(trId->tranId); 142 if (shareIndex != pObj->shareList.end()) 143 { 144 pObj->shareList.erase(shareIndex); 145 trId->curLockObjList.erase(pObj); 146 result += "Lock releasednttt"; 147 } 148 else 149 { 150 result += "I can not find the transaction.nttt"; 151 } 152 } 153 //查看写等待队列 154 if (pObj->waitingTransList.size() != 0) 155 { 156 pObj->curXLockTrans = pObj->waitingTransList.front(); 157 pObj->waitingTransList.pop(); 158 result += "X-Lock on "+ pObj->objectName +" granted to "+ pObj->curXLockTrans +"n"; 159 }//查看共享队列 160 else if (pObj->shareList.size() != 0) 161 { 162 string temp = ""; 163 for(set<string>::iterator it_index = pObj->shareList.begin(); 164 it_index != pObj->shareList.end(); it_index++) 165 { 166 temp += " " + *it_index; 167 } 168 result += "S-Lock on "+ pObj->objectName +" granted to "+ temp +"n"; 169 } 170 }
四、程序运行
程序数据输入如下:
运行后得到结果如下:
原文链接: https://www.cnblogs.com/michaelGD/archive/2013/01/24/2844340.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/76607
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!