我怎么使用任意字符串锁在C++?
-
03-07-2019 - |
题
让我们说我有多线程C++的程序,处理请求的形式功能呼叫 handleRequest(string key)
.每一个呼叫 handleRequest
发生在一个单独的线,并且有任意大数量的可能值 key
.
我希望将以下行为:
- 同时呼吁
handleRequest(key)
序列化的时候,他们有相同的价值key
. - 全球化最小。
身体的 handleRequest
可能是这样的:
void handleRequest(string key) {
KeyLock lock(key);
// Handle the request.
}
问题: 我怎么会实现 KeyLock
来获得所需的行为?
一个天真的实现可能开始这样的:
KeyLock::KeyLock(string key) {
global_lock->Lock();
internal_lock_ = global_key_map[key];
if (internal_lock_ == NULL) {
internal_lock_ = new Lock();
global_key_map[key] = internal_lock_;
}
global_lock->Unlock();
internal_lock_->Lock();
}
KeyLock::~KeyLock() {
internal_lock_->Unlock();
// Remove internal_lock_ from global_key_map iff no other threads are waiting for it.
}
...但是这需要一个全球性的锁定在开始和结束的每一请求,并建立一个独立的 Lock
对象为每一请求。如果竞争是高的之间的调用 handleRequest
, 那可能不是一个问题,但它可能对一个很大的开销如果争低。
解决方案
你可以做一些类似的是什么,你已在你的问题,但不是一个单一的global_key_map有些(可能是在一系列或矢量)-哪一个用于确定一些简单的散列函数。
这种方式,而不是一个单一的全球锁定你的传播,在几个独立的。
这是一种模式,常常用于存储器分配(我不知道,如果该模式有一个名字-它应该)。当请求,一些确定哪游泳池的分配将来自(通常尺寸的请求,但其他参数可以因素以及),那么只有那游泳池需要被锁定。如果分配的请求从另外一个线程,将使用不同的游泳池,有没有锁的竞争。
其他提示
这将取决于平台,但这两种技术,我会尝试将是:
- 使用名为互斥/同步 对象,其中object name=关键
- 使用文件系统基于锁定,你在哪里 尝试创建一个不可分享的 临时文件的关键名称。如果已经存在(=已 锁定)这将失败和你 必须调查重试
这两种技术将取决于详细的操作系统。实验,看看哪些工作。.
也许是一个 std::map<std::string, MutexType>
将你想要什么,在哪里 MutexType
是互斥你想要的。你可能会包访问的地图在另一个互斥,以确保没有其他线插在同一时间(以及记得以执行检查之后再次互斥被锁定,以确保另一个线没有加入的关键,同时等待在互斥!).
同样的原则可以适用于其他任何同步的方法,例如一个关键部分。
提高颗粒度,并锁定整个关键的范围
这是一个变化对迈克的回答,而不是在那里拥有几个流体锁定的地图你有一个单一的固定阵列锁定适用于关键的范围,而不是单一的钥匙。
简化例子:创列256锁在启动时,随后使用第一个字节的关键,以确定索引的锁可以获取(即所有的钥匙开始'k'将把守 locks[107]
).
维持的最佳吞吐量你应该分析分配钥匙和争用率。这种方法的好处是零动态的分配和简单的清理;你还可以避免两步锁。缺点是潜在的竞争峰如果关键的偏斜分布变得过时。
之后考虑这个问题,另一个办法可能是这样的:
- 在
handleRequest
, 创建一个Callback
执行实际工作。 - 创建一个
multimap<string, Callback*> global_key_map
, 保护通过一个互斥。 - 如果一线看到
key
已经正在处理的,它增加了它Callback*
来的global_key_map
并返回。 - 否则,它呼吁其立即回,然后调回,已经显示在此期间对相同的密钥。
实现这样的事情:
LockAndCall(string key, Callback* callback) {
global_lock.Lock();
if (global_key_map.contains(key)) {
iterator iter = global_key_map.insert(key, callback);
while (true) {
global_lock.Unlock();
iter->second->Call();
global_lock.Lock();
global_key_map.erase(iter);
iter = global_key_map.find(key);
if (iter == global_key_map.end()) {
global_lock.Unlock();
return;
}
}
} else {
global_key_map.insert(key, callback);
global_lock.Unlock();
}
}
这个具有优势的释放线,否则将等待的一个关键锁,但除此之外,它几乎是一样的天真的解决方案我在这个问题。
这可能是结合给出的答案通过Mike B和康斯坦丁,虽然。
/**
* StringLock class for string based locking mechanism
* e.g. usage
* StringLock strLock;
* strLock.Lock("row1");
* strLock.UnLock("row1");
*/
class StringLock {
public:
/**
* Constructor
* Initializes the mutexes
*/
StringLock() {
pthread_mutex_init(&mtxGlobal, NULL);
}
/**
* Lock Function
* The thread will return immediately if the string is not locked
* The thread will wait if the string is locked until it gets a turn
* @param string the string to lock
*/
void Lock(string lockString) {
pthread_mutex_lock(&mtxGlobal);
TListIds *listId = NULL;
TWaiter *wtr = new TWaiter;
wtr->evPtr = NULL;
wtr->threadId = pthread_self();
if (lockMap.find(lockString) == lockMap.end()) {
listId = new TListIds();
listId->insert(listId->end(), wtr);
lockMap[lockString] = listId;
pthread_mutex_unlock(&mtxGlobal);
} else {
wtr->evPtr = new Event(false);
listId = lockMap[lockString];
listId->insert(listId->end(), wtr);
pthread_mutex_unlock(&mtxGlobal);
wtr->evPtr->Wait();
}
}
/**
* UnLock Function
* @param string the string to unlock
*/
void UnLock(string lockString) {
pthread_mutex_lock(&mtxGlobal);
TListIds *listID = NULL;
if (lockMap.find(lockString) != lockMap.end()) {
lockMap[lockString]->pop_front();
listID = lockMap[lockString];
if (!(listID->empty())) {
TWaiter *wtr = listID->front();
Event *thdEvent = wtr->evPtr;
thdEvent->Signal();
} else {
lockMap.erase(lockString);
delete listID;
}
}
pthread_mutex_unlock(&mtxGlobal);
}
protected:
struct TWaiter {
Event *evPtr;
long threadId;
};
StringLock(StringLock &);
void operator=(StringLock&);
typedef list TListIds;
typedef map TMapLockHolders;
typedef map TMapLockWaiters;
private:
pthread_mutex_t mtxGlobal;
TMapLockWaiters lockMap;
};