无锁编程之自旋锁的C++实现
#include "util.h"
#include "atomic.h"
#include "spinlock.h"
void TASLock::lock()
{
while (state.getAndSet(true)) {}
}
void TASLock::unlock()
{
state.set(false);
}
void TTASLock::lock()
{
while (true)
{
while (state.get()) {}
if (!state.getAndSet(true))
return;
}
}
void TTASLock::unlock()
{
state.set(false);
}
void FIFOTicketLock::lock()
{
int myTicket = ticket.getAndIncrement();
while (myTicket != token) {}
}
void FIFOTicketLock::unlock()
{
token++;
}
void BackoffLock::lock()
{
// 等待的时间可以任意设置
Backoff backoff;
while (true)
{
while (state.get()) {}
if (!state.getAndSet(true))
return;
else
backoff.backoff();
}
}
void BackoffLock::unlock()
{
state.set(false);
}
// 定义Cache线的宽度，不同类型的CPU可能不同
#define CACHE_LINE_WIDTH 4
ALock::ALock(int capacity)
{
size = capacity;
flag = new bool[size * CACHE_LINE_WIDTH];
flag[0] = true;
for (int i = 1; i < size; i++)
flag[i * CACHE_LINE_WIDTH] = false;
}
ALock::~ALock()
{
delete[] flag;
}
int ALock::mySlotIndex = 0;
void ALock::lock()
{
int slot = tail.getAndIncrement() % size;
mySlotIndex = slot;
while (!flag[slot * CACHE_LINE_WIDTH]) {}
}
void ALock::unlock()
{
int slot = mySlotIndex;
flag[slot * CACHE_LINE_WIDTH] = false;
slot = (slot+1) % size;
flag[slot * CACHE_LINE_WIDTH] = true;
}
MCSLock::MCSLock():tail(0)
{
}
MCSLock::QNode MCSLock::myNode;
void MCSLock::lock()
{
myNode.next = 0;
QNode * pred = tail.getAndSet(&myNode);
if (pred != 0)
{
myNode.locked = true;
pred->next = &myNode;
while (myNode.locked) {}
}
}
void MCSLock::unlock()
{
if (myNode.next == 0)
{
if (tail.compareAndSet(&myNode, 0))
return;
// wait until predecessor fills in its next field
while (myNode.next == 0) {}
}
// 一个线程访问另一个线程的TLS空间时，必须保证后者没有结束
myNode.next->locked = false;
myNode.next = 0;
}
TOLock::TOLock():tail(0)
{
}
TOLock::QNode TOLock::AVAILABLE;
TOLock::QNode * TOLock::myNode = 0;
// 姑且用CPU的时钟周期作为时间单位
// 本函数需要申请、释放内存，因此很耗时
// 前面线程超时后，后面线程要帮它释放内存，导致后面线程也超时
bool TOLock::tryLock(TIME_TYPE cycle)
{
QNode * qnode = new QNode;
qnode->pred = 0;
myNode = qnode;
QNode * myPred = tail.getAndSet(qnode);
if (myPred == 0) return true;
TIME_TYPE endTime = get_clock() + cycle;
do {
QNode * predPred = myPred->pred;
if (predPred == &AVAILABLE)
{
// 如果释放锁的线程不在队尾，在此释放内存
delete myPred;
return true;
}
else if (predPred != 0)
{
// 如果超时的线程不在队尾，在此释放内存
delete myPred;
myPred = predPred;
}
} while (!timeout(endTime));
// 如果超时的线程在队尾，在此释放内存
if (tail.compareAndSet(qnode, myPred))
delete qnode;
else
qnode->pred = myPred;
return false;
}
void TOLock::lock()
{
QNode * qnode = new QNode;
qnode->pred = 0;
myNode = qnode;
QNode * myPred = tail.getAndSet(qnode);
if (myPred == 0) return;
do {
QNode * predPred = myPred->pred;
if (predPred == &AVAILABLE)
{
// 如果释放锁的线程不在队尾，在此释放内存
delete myPred;
return;
}
if (predPred != 0)
{
// 如果超时的线程不在队尾，在此释放内存
delete myPred;
myPred = predPred;
}
} while (true);
}
void TOLock::unlock()
{
// 如果释放锁的线程在队尾，在此释放内存
if (tail.compareAndSet(myNode, 0))
delete myNode;
else
myNode->pred = &AVAILABLE;
}
TO2Lock::TO2Lock():tail(0)
{
}
TO2Lock::QNode TO2Lock::AVAILABLE;
TO2Lock::QNode TO2Lock::myNode;
bool TO2Lock::tryLock(TIME_TYPE cycle)
{
// 如果上次加锁超时，等待后续线程将其踢出队列
while (myNode.pred != 0) {}
QNode * myPred = tail.getAndSet(&myNode);
if (myPred == 0) return true;
TIME_TYPE endTime = get_clock() + cycle;
do {
QNode * predPred = myPred->pred;
if (predPred == &AVAILABLE)
{
// 如果释放锁的线程不在队尾，在此踢出队列
myPred->pred = 0;
return true;
}
else if (predPred != 0)
{
// 如果超时的线程不在队尾，在此踢出队列
myPred->pred = 0;
myPred = predPred;
}
} while (!timeout(endTime));
// 如果超时的线程不在队尾，则等后续线程踢出队列
if (!tail.compareAndSet(&myNode, myPred))
myNode.pred = myPred;
return false;
}
void TO2Lock::lock()
{
QNode * myPred = tail.getAndSet(&myNode);
if (myPred == 0) return;
do {
QNode * predPred = myPred->pred;
if (predPred == &AVAILABLE)
{
// 如果释放锁的线程不在队尾，在此踢出队列
myPred->pred = 0;
return;
}
else if (predPred != 0)
{
// 如果超时的线程不在队尾，在此踢出队列
myPred->pred = 0;
myPred = predPred;
}
} while (true);
}
void TO2Lock::unlock()
{
// 如果释放锁的线程不在队尾，则等后续线程踢出队列
if (!tail.compareAndSet(&myNode, 0))
{
myNode.pred = &AVAILABLE;
// 必须等后续线程访问完了，本线程才能退出
// 否则后续线程会访问无效空间
while (myNode.pred != 0) {}
}
}
CompositeLock::CompositeLock(int _size):tail(0)
{
size = _size;
waiting = new QNode[size];
for (int i = 0; i < size; i++)
{
waiting[i].state.set(FREE);
waiting[i].pred = 0;
}
}
CompositeLock::~CompositeLock()
{
delete[] waiting;
}
CompositeLock::QNode * CompositeLock::myNode = 0;
bool CompositeLock::tryLock(TIME_TYPE cycle)
{
TIME_TYPE endTime = get_clock() + cycle;
QNode * node = acquireQNode(endTime);
if (node == 0) return false;
QNode * pred = spliceQNode(node);
if (pred == 0)
{
myNode = node;
return true;
}
else
return waitForPredecessor(pred, node, endTime);
}
void CompositeLock::unlock()
{
// 通知下一个线程进入互斥区，由下一个线程释放节点
myNode->state.set(RELEASED);
myNode = 0;
}
CompositeLock::QNode * CompositeLock::acquireQNode(TIME_TYPE endTime)
{
// 等待的时间可以任意设置
Backoff backoff;
// 随机获取一个节点
QNode * node = &waiting[get_clock() % size];
QNode * currTail;
int currStamp = 0;
while (true)
{
// 如果节点空闲就立即返回
if (node->state.compareAndSet(FREE, WAITING))
return node;
currTail = tail.get(currStamp);
State state = (State)node->state.get();
if (state == ABORTED || state == RELEASED)
{
if (node == currTail)
{
QNode * myPred = 0;
if (state == ABORTED)
myPred = node->pred;
if (tail.compareAndSet(currTail, myPred, currStamp, currStamp+1))
{
node->state.set(WAITING);
return node;
}
}
}
// 节点不空闲则等待
backoff.backoff();
// 测试是否超时
if (timeout(endTime)) return 0;
}
}
CompositeLock::QNode * CompositeLock::spliceQNode(QNode * node)
{
// 这个函数原本可以用getAndSet实现，为了修改邮戳只好牺牲了
// 这个循环不大可能超时，除非一直有人修改队尾
QNode * currTail;
int currStamp = 0;
do
{
currTail = tail.get(currStamp);
} while (!tail.compareAndSet(currTail, node, currStamp, currStamp+1));
return currTail;
}
bool CompositeLock::waitForPredecessor(QNode * pred, QNode * node, TIME_TYPE endTime)
{
State predState = (State)pred->state.get();
while (predState != RELEASED)
{
if (predState == ABORTED)
{
QNode * temp = pred;
pred = pred->pred;
temp->state.set(FREE);
}
// 如果超时则设置为ABORTED
if (timeout(endTime))
{
node->pred = pred;
node->state.set(ABORTED);
return false;
}
predState = (State)pred->state.get();
}
pred->state.set(FREE);
myNode = node;
return true;
}
#define FASTPATH_LOCK 0x80000000 // 窃取最高位作为快速加锁的标识
bool CompositeFastPathLock::tryLock(TIME_TYPE cycle)
{
if (fastPathLock()) return true;
if (!CompositeLock::tryLock(cycle)) return false;
while ((tail.getStamp() & FASTPATH_LOCK) != 0) {}
return true;
}
bool CompositeFastPathLock::fastPathLock()
{
int oldStamp, newStamp;
QNode * qnode = tail.get(oldStamp);
if (qnode !