数据库读写锁的实现(C++)
一、基本概念
在数据库中,对某数据的两个基本操作为写和读,分布有两种锁控制:排它锁(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: 为此事件目前所操作的对象列表
三、源代码
本程序为所的锁管理接口,所以封装成类,方便程序调用。程序源码可以点击这里下载。
数据结构如下:
class LMer { private: struct object { string objectName; string curXLockTrans; queue<string> waitingTransList; set<string> shareList; }; struct transId { string tranId; set<object*> curLockObjList; }; map<string, object*> mObjectList; map<string, transId*> mTransId; public: LMer(){} string LMer::handleInput(vector<string>& vInput); void LMer::handleAction(string sAction, transId* trId, object* obj, string& result); void LMer::diviTransID(transId* trId, object* pObj, string& result); };逻辑结构实现如下:
string LMer::handleInput(vector<string>& vInput) { string result = ""; //二参数输入 if (vInput.size() == 2) { //进程存在,进入下一步 map<string, transId*>::iterator transIt = mTransId.find(vInput[1]); if (transIt != mTransId.end()) { //是否结束事件(结束事件队列中所有事件) if (vInput[0] == "End") { result += "\tTransaction "+ vInput[1] +" ended\n\t\t\t"; //解绑进程所有事物 set<object*>::iterator obj_index; while(transIt->second->curLockObjList.size() != 0) { obj_index = transIt->second->curLockObjList.begin(); diviTransID(transIt->second, *obj_index, result); } //清空请求事件 mTransId.erase(transIt); } } else if(vInput[0] == "Start")//为start,创立进程 { transId* pTransId = new transId(); pTransId->tranId = vInput[1]; //将此进程加入进程树中 mTransId[vInput[1]] = pTransId; result += "Transaction " + vInput[1] +" started\n"; } } else //三参数输入 { //创建新操作对象 if(mObjectList.find(vInput[2]) == mObjectList.end()) { object* pObjectIndex = new object(); pObjectIndex->objectName = vInput[2]; pObjectIndex->curXLockTrans = ""; mObjectList[vInput[2]] = pObjectIndex; } if (vInput[0] == "Unlock") { //解锁trans->obj diviTransID(mTransId[vInput[1]], mObjectList[vInput[2]], result); } else//进行常规处理(Xlock、Slock) { //进行处理 handleAction(vInput[0], mTransId[vInput[1]], mObjectList[vInput[2]], result); } } return result; } void LMer::handleAction(string sAction, transId* trId, object* obj, string& result) { //检查是否有占用 if (sAction == "SLock") { if (obj->curXLockTrans == "") { obj->shareList.insert(trId->tranId); trId->curLockObjList.insert(obj); result += "S-Lock granted to "+ trId->tranId +"\n"; } else//被占用 { obj->shareList.insert(trId->tranId); result += "Waiting for lock (X-lock held by: "+ obj->curXLockTrans +")\n"; } } else if(sAction == "XLock") { //未有写操作 if (obj->curXLockTrans == "") { int shareNum = obj->shareList.size(); if (shareNum > 1) { string sTemp = ""; for (set<string>::iterator it_index = obj->shareList.begin(); it_index != obj->shareList.end(); it_index++) { sTemp += " " + *it_index; } obj->waitingTransList.push(trId->tranId); result += "Waiting for lock (S-lock held by:" + sTemp + "\n"; } else if (shareNum == 1) { //update if (*(obj->shareList.begin()) == trId->tranId) { obj->curXLockTrans = trId->tranId; obj->shareList.clear(); result += "Upgrade to XLock granted\n"; } else { obj->waitingTransList.push(trId->tranId); result += "Waiting for lock (S-lock held by:" + *(obj->shareList.begin()) + ")\n"; } } else if (shareNum == 0) { obj->curXLockTrans = trId->tranId; trId->curLockObjList.insert(obj); result += "XLock granted\n"; } } else//当前存在写操作 { obj->waitingTransList.push(trId->tranId); result += "Waiting for lock (X-lock held by: "+ obj->curXLockTrans +")\n"; } } } void LMer::diviTransID(transId* trId, object* pObj, string& result) { if(pObj->curXLockTrans != "") { //对写操作解绑 if (pObj->curXLockTrans == trId->tranId) { pObj->curXLockTrans = ""; trId->curLockObjList.erase(pObj); result += "Lock released\n\t\t\t"; } else { result += "I can not find the transaction.\n\t\t\t"; } }//对共享读集合解绑 else { set<string>::iterator shareIndex = pObj->shareList.find(trId->tranId); if (shareIndex != pObj->shareList.end()) { pObj->shareList.erase(shareIndex); trId->curLockObjList.erase(pObj); result += "Lock released\n\t\t\t"; } else { result += "I can not find the transaction.\n\t\t\t"; } } //查看写等待队列 if (pObj->waitingTransList.size() != 0) { pObj->curXLockTrans = pObj->waitingTransList.front(); pObj->waitingTransList.pop(); result += "X-Lock on "+ pObj->objectName +" granted to "+ pObj->curXLockTrans +"\n"; }//查看共享队列 else if (pObj->shareList.size() != 0) { string temp = ""; for(set<string>::iterator it_index = pObj->shareList.begin(); it_index != pObj->shareList.end(); it_index++) { temp += " " + *it_index; } result += "S-Lock on "+ pObj->objectName +" granted to "+ temp +"\n"; } }
四、程序运行
程序数据输入如下:
运行后得到结果如下:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。