想出了这样一个算法，屡试不爽，却不知是否真可行

想出了这么一个算法，屡试不爽，却不知是否真可行
定义了一个类T：

class T
{
    DWORD threadID;
    int threadDeep;
public:
    T():threadID(NULL),threadDeep(0){}
    void Wait();
    void End();
}

void T::Wait()
{
    DWORD id = ::GetCurrentThreadId();
    if(threadID==id)
    {
        ++threadDeep;
        return;
    }
START:;
    while(threadID)::Sleep(0);
    threadID = id;
    ::Sleep(0);//关键
    if(threadID!=id)goto START;
}
void T::End()
{
    if(::GetCurrentThreadId()==threadID)
    {
        if(--threadDeep < 0)
        {
            threadID = NULL;
            threadDeep = 0;
        }
    }
}
T t;

然后在多个线程中都要重复执行如下语句

t.Wait();
DoSomething();//该算法能否保证在同一时间只有一个线程执行此语句？
t.End();

此算法能不能实现此段临界区？请说明理由。 算法 临界区 多线程
[解决办法]
不能
    DWORD id = ::GetCurrentThreadId();
    if(threadID==id)
    {
        ++threadDeep;
        return;
    }
//上面的代码是允许已进入临界区的线程多次wait，与互斥无关。

START:;
    while(threadID)::Sleep(0);
    threadID = id;
    ::Sleep(0);//关键
    if(threadID!=id)goto START;

//Sleep(0); 
// 用Sleep不能完全解决这个问题，多核没有其他等待的线程Sleep(0)差不多等于空操作
// 这里其实只需要一个原子操作
START:;
while (InterlockedCompareExchange(&threadID, id, 0) != 0)
::Sleep(0);
[解决办法]
不行，请看下面运行可能性：

void T::Wait()
{
    DWORD id = ::GetCurrentThreadId();
    if(threadID==id)
    {
        ++threadDeep;
        return;
    }
START:;
    while(threadID)::Sleep(0);
    // 线程1、2同时运行到这里
    threadID = id;
    ::Sleep(0);//关键
    if(threadID!=id)goto START;
}

然后...

void T::Wait()
{
    DWORD id = ::GetCurrentThreadId();
    if(threadID==id)
    {
        ++threadDeep;
        return;
    } 
 
START:;
    while(threadID)::Sleep(0);
    // 线程2暂停在这里
    threadID = id;
    ::Sleep(0);//关键
    if(threadID!=id)goto START;
    // 线程1运行到这里，已经返回了
}

下面，线程2开始运行，也通过了。线程1、2都可以DoSomething。
楼主这种类似于double-check的例子，让我想到另一个高效的同步例子，记忆错了，以为在网上看到，搜了长时间也没结果，原来是在《程序员的自我修养》上看到的，代码如下：

volate T* pInst = 0;
T* GetInstance()
{
    if (pInst == NULL)
    {
        lock();
        if (pInst == NULL)
            vpInst = new T;
        unlock();
    }
    return pInst;
}

[解决办法]
LZ啊，这代码你自己试过吗？class定义完都忘了加分号，害得我半天才找出来

为了便于重现，我在你的定义里面加了两个sleep（真正有效的locker的行为不会因为增加sleep而出错吧），大家试试看会不会连着打印多个begin，是不是屡试不爽？

不多，才50个线程

#include <iostream>
#include <windows.h>
#include <process.h>
#include <assert.h>
using namespace std;

class T
{
DWORD threadID;
int threadDeep;
public:
T():threadID(NULL),threadDeep(0){}
void Wait();
void End();
};

void T::Wait()
{
DWORD id = ::GetCurrentThreadId();
if(threadID==id)
{
++threadDeep;
return;
}
START:;
while(threadID)::Sleep(0);
::Sleep(1000); //增加::Sleep(1000)
threadID = id;
::Sleep(0);//关键
if(threadID!=id)goto START;
::Sleep(1000);//增加::Sleep(1000)
}
void T::End()
{
if(::GetCurrentThreadId()==threadID)
{
if(--threadDeep < 0)
{
threadID = NULL;
threadDeep = 0;
}
}
}
T t;


unsigned int __stdcall Fn(void *pArguments)
{
t.Wait();
cout<<"begin"<<endl;
Sleep(10000);
cout<<"end"<<endl;
t.End();
return 0;
} 

#define THREAD_COUNT 50
int main()
{
HANDLE handles[THREAD_COUNT] = { NULL };
for (int i = 0; i < THREAD_COUNT; i++)
{
unsigned int tid = 0;
handles[i] = 
(HANDLE)_beginthreadex(0, 0, &Fn, 0, 0, &tid);
assert(handles[i]);
}
for (int i = 0; i < THREAD_COUNT; i++)
{
::WaitForSingleObject(handles[i], INFINITE);
}
system("pause");
return 0;
}

[解决办法]
思路正确的，不过细节还有问题。
1、

START:;
    while(threadID)::Sleep(0);
    threadID = id;
    ::Sleep(0);//关键
    if(threadID!=id)goto START;

37楼有分析原因了。
锁不能完全用软件实现的，至少要硬件支持特定原子操作（如CAS-compare and swap)，操作系统都要依赖的。8楼就给了例子。

2、
在pc架构上已正确。但要适应其它架构，还要考虑内存栅栏(memorybarrier)，windows 就有读、写、读写三种栅栏api。


虽然这个锁机制没什么实际用处，但递归锁的实现可以借鉴，为不支持递归的互斥机制增加该功能。
如进程共享互斥所用的全局mutex等。。之前也这样弄过，使用很方便。

[解决办法]
细节方面还有这个

void T::End()
{
    if(::GetCurrentThreadId()==threadID)
    {
        if(--threadDeep < 0)
        {
            //这两句顺序交换
            threadID = NULL;
            threadDeep = 0;
        }
    }
}

[解决办法]
37楼 ++
楼主逻辑还需改进哦，
若n个线程同时执行到threadID = id;其中一个线程k继续执行，并成功得到资源，而另一个稍慢s线程还处于threadID = id;处，这时
线程s执行，那么导致得到资源线程id变成线程s的id，这个就错误了。
[解决办法]
不行的啦。37楼已然解释了其中的一种错误情况。简单想，去掉为一个线程多次调用wait（）所加的逻辑，这个同步的想法是使用一个全局变量，记录当前进入关键代码段的线程ID。该全局变量为0，说明没有线程进入关键代码段；反之，说明已经有线程进入了关键代码段。这样，任何一个线程在进入关键代码段前先查看一下该全局变量，如果发现该全局变量已经不是0了，就调用sleep(0)放弃自己所占有的CPU资源。

这段代码的根本问题是没有保证对于该全局变量的访问是同步的。例如这一段：
-

START:; 
    while(threadID)::Sleep(0); 
    threadID = id; 
    ::Sleep(0);//关键 
    if(threadID!=id)goto START; 

无法保证一个线程在判断了if(threadID!=id)为真时，刚好另一个线程在执行threadID=id;而对threadID进行修改。

查看更多 下一篇