MCS自旋锁

Linux内核MCS锁机制的实现原理
四种自旋锁原理详解

// mcs.h
#ifndef __MCS_H__
#define __MCS_H__#include #ifdef __cplusplus
extern "C" {
#endif // __cplusplusstruct mcs_node_t_
{struct mcs_node_t_ **lock;        // ptr to tail of queuestruct mcs_node_t_  *next;        // ptr to successor in queueHANDLE               readyFlag;   // set after lock is released by predecessorHANDLE               nextFlag;    // set after 'next' ptr is set by successor
};typedef struct mcs_node_t_     mcs_local_node_t;
typedef struct mcs_node_t_*    mcs_lock_t;void mcs_lock_acquire(mcs_lock_t *lock, mcs_local_node_t *node);int mcs_lock_try_acquire(mcs_lock_t *lock, mcs_local_node_t *node);void mcs_lock_release(mcs_local_node_t *node);void mcs_node_transfer(mcs_local_node_t *new_node, mcs_local_node_t *old_node);#ifdef __cplusplus
}
#endif // __cplusplus#endif // !__MCS_H__

// mcs.c
#include "mcs.h"
#include inline void mcs_flag_set(HANDLE *flag)
{HANDLE e = (HANDLE)(int64_t)InterlockedCompareExchange64((volatile int64_t *)flag, (int64_t)-1, (int64_t)0);if (((HANDLE)(int)0 != e) && ((HANDLE)(int)-1 != e)){// 唤醒等待在e上的线程SetEvent(e);}
}inline void mcs_flag_wait(HANDLE *flag)
{if ((int64_t)0 == InterlockedExchangeAdd64((volatile int64_t *)flag, (int64_t)0)){HANDLE e = CreateEvent(NULL, FALSE, FALSE, NULL);if (e){if ((int64_t)0 == InterlockedCompareExchange64((volatile int64_t *)flag, (int64_t)e, (int64_t)0)){WaitForSingleObject(e, INFINITE);}CloseHandle(e);}}
}/*** 获取锁* 先将lock的值赋值为node* 返回值pred如果为NULL表示当前锁处于空闲状态, 加锁成功* 不为NULL时表示有人使用, 更新pred->next* * 问题1：node->next == 0, 为什么不会切断链表* 因为lock的值也在同步更新* 假设三个线程同时调用, 线程1最先获取到锁, 线程2,3的node分别为node2, node3** 当线程3调用mcs_lock_acquire时lock的值为node2, 所以是对node2操作, 更新lock的值为node3, 同时将node3插入到node2后面* 此时链表为 node1->node2->node3*/
void mcs_lock_acquire(mcs_lock_t *lock, mcs_local_node_t *node)
{mcs_local_node_t *pred;node->lock = lock;node->nextFlag = 0;node->readyFlag = 0;node->next = 0;pred = (mcs_local_node_t *)InterlockedExchangePointer((volatile PVOID *)lock, (PVOID)node);if (0 != pred){InterlockedExchangePointer(((volatile PVOID*)&pred->next), ((PVOID)node));mcs_flag_set(&pred->nextFlag);mcs_flag_wait(&node->readyFlag);}
}int mcs_lock_try_acquire(mcs_lock_t *lock, mcs_local_node_t *node)
{node->lock = lock;node->nextFlag = 0;node->readyFlag = 0;node->next = 0;return ((PVOID)InterlockedCompareExchangePointer(((volatile PVOID*)lock), ((PVOID)node), ((PVOID)0)) == (PVOID)0) ? 0 : EBUSY;
}/*** 释放锁* * 1、获取当前节点的下一个等待节点* 如果下一个节点为空, *	  如果lock == node表示当前只有自己使用锁, 直接返回*    如果lock != node表示此时有人尝试获取锁并且已经修改了lock的值处于wait状态，所以需要更新next的值，调用mcs_flag_wait是等待pred->next更新完成* 不为空时, 此时node == node1(因为node1获取到锁, 能继续往下调用mcs_lock_release)，下一个节点就是node2* * 最后通知next, 解除线程阻塞*/
void mcs_lock_release(mcs_local_node_t *node)
{mcs_lock_t *lock = node->lock;mcs_local_node_t *next =(mcs_local_node_t *)InterlockedExchangeAdd64((((volatile int64_t*)&node->next)), (((int64_t)0)));if (0 == next){/* no known successor */if (node == (mcs_local_node_t *)InterlockedCompareExchangePointer(((volatile PVOID*)lock), ((PVOID)0), ((PVOID)node))){/* no successor, lock is free now */return;}/* wait for successor */mcs_flag_wait(&node->nextFlag);next = (mcs_local_node_t *)InterlockedExchangeAdd64((((volatile int64_t*)&node->next)), (((int64_t)0))); /* MBR fence */}else{/* Even if the next is non-0, the successor may still be trying to set the next flag on us, therefore we must wait. */mcs_flag_wait(&node->nextFlag);}/* pass the lock */mcs_flag_set(&next->readyFlag);
}void mcs_node_transfer(mcs_local_node_t *new_node, mcs_local_node_t *old_node)
{new_node->lock = old_node->lock;new_node->nextFlag = 0;new_node->readyFlag = 0;new_node->next = 0;if ((mcs_local_node_t *)InterlockedCompareExchangePointer(((volatile PVOID*)new_node->lock), ((PVOID)new_node), ((PVOID)old_node))!= old_node){while (0 == old_node->next){Sleep(0);}mcs_flag_wait(&old_node->nextFlag);new_node->next = old_node->next;new_node->nextFlag = old_node->nextFlag;}
}

// main.cpp
#include 
#include 
#include "mcs.h"using namespace std;mcs_lock_t globalLock;int64_t counter;void work_thread()
{while (true){mcs_local_node_t node;mcs_lock_acquire(&globalLock, &node);if (counter > 1000 * 1000) {mcs_lock_release(&node);break;}++counter;std::cout << GetCurrentThreadId() << ": " << counter << std::endl;mcs_lock_release(&node);Sleep(10);}
}int main()
{std::thread thread(std::bind(work_thread));while (true){mcs_local_node_t node;mcs_lock_acquire(&globalLock, &node);if (counter > 1000 * 1000) {mcs_lock_release(&node);break;}++counter;std::cout << GetCurrentThreadId() << ": " << counter << std::endl;mcs_lock_release(&node);Sleep(10);}thread.join();return 0;
}

此代码移植自pthread-win32

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！