lockfree的本质是乐观锁。也就是说，它假设多数情况下，别人不会改变。一个通用的lockfree算法可描述如下：
　　lockfree_modify(DataT* data)
　　{
　　for (;;)
　　{
　　Save old state of data to a local variable;
　　do modify;
　　lock {
　　if (current state == old state)
　　commit modify & return;
　　}
　　}
　　}
　　可以看出，lockfree也是锁，只是将锁限制在一个最小的范围内（通常是一个原子操作）。由于仍然有锁，lockfree在多核下并不会比普通的锁高明多少，它也不能随cpu个数增加而获得呈线性scale的性能提升。
　　不过，lockfree有个最大的好处，就是不可能有死锁。因为对上面算法分析你可以知道，在某个线程modify失败，总意味着有另一个人成功了，整个程序总在一步步前进，而不是出现相互等待而产生饥饿的状况。
　　我们以stack为例，展示下lockfree的stack是怎样的：
　　class stack
　　{
　　public:
　　struct Node
　　{
　　Node* prev;
　　};
　　private:
　　Node* m_head;
　　public:
　　stack()
　　: m_head(NULL)
　　{
　　}
　　void push(Node* val)
　　{
　　for (;;)
　　{
　　Node* head = m_head;
　　val->prev = head;
　　if (InterlockedCompareExchangePointer((PVOID*)&m_head, val, head) == head)
　　return;
　　}
　　}
　　Node* pop()
　　{
　　for (;;)
　　{
　　Node* head = m_head;
　　if (head == NULL)
　　return NULL;
　　if (InterlockedCompareExchangePointer((PVOID*)&m_head, head->prev, head) == head)
　　return head;
　　}
　　}
　　};
　　嗯，看起来挺不错，代码还算优雅。。。不过遗憾的是，严谨的说其实上面的lockfree算法是有问题的。问题在哪里？在pop算法上。我们看lock范围内的语义：
　　if (InterlockedCompareExchangePointer((PVOID*)&m_head, head->prev, head) == head)
　　return head;
　　这句话用伪代码描述是：
　　lock {
　　if (m_head == head) {
　　m_head = head->prev;
　　return head;
　　}
　　}
　　问题在于，m_head指针的值没有发生变化，和整个stack没有发生变化，这两者等价吗？
　　不等价。完全可以发生一种情况就是，另一个线程执行了这样一段代码：
　　v1 = pop(); // v1是m_head
　　v2 = pop();
　　push(v1);
　　此时，m_head没有变化，但是m_head->prev不再是v2，而是v2->prev了。
　　那么怎么办？在说解决方案前，我们先再聊下上例中的stack::push。既然stack::pop有问题，那么stack::push呢？我们说，push算法的并没有什么问题。尽管同样的，m_head指针的值没有发生变化，并不意味着整个stack没有发生变化。但是对于push来说，它只关心m_head，而不关心其他东西，所以stack是否发生变化对其并无影响。
　　那么，应该如何解决pop算法遇到的问题？一个比较通用的方法，就是版本号。lockfree算法中，有一个术语叫tagged_ptr，其实本质上就是一个打了版本号的pointer：
　　struct tagged_ptr
　　{
　　void* p;
　　size_t tag;
　　};
　　每次要对p进行修改，都++tag。这样，判断是不是modify，只需要判断tag是否变化即可。

软考站考试大编辑推荐:
2009年下半年全国计算机软件水平考试报名时间	2009年软考重大变革系统分析师下半年停考
2009年下半年全国计算机软考科目及时间	2009年下半年全国计算机专业技术资格考试安排
2009年5月全国计算机软考水平考试真题及答案	2009年全国计算机软考考试大纲汇总
更多优质资料尽在考试大论坛 考试大在线题库	软考站点加入收藏夹