C++多线程中的Peterson算法

Question

C++多线程中的Peterson算法

3

我用C++实现了Peterson算法的简单版本，实现了多线程。这个程序通过两个线程改变字符串。但是我得不到最终结果。我错在哪里了？

using namespace std;

int flag[2]={0,1};
int turn;

void* first(void* data){
    flag[0]=1;
    turn=1;
    while(flag[1] && turn==1){}
    string &str=*(static_cast<string*>(data));
    if(str!=""){
        if(str=="abcd"){
            str="Hello";
        }
    }
    flag[0]=0;
    pthread_exit(NULL);
}

void* second(void* data){
    flag[1]=1;
    turn=0;
    while(flag[0] && turn==0){}
    string &str=*(static_cast<string*>(data));
    if(str!=""){
        if(str=="wxyz"){
            str="abcd";
        }
    }
    flag[1]=0;
    pthread_exit(NULL);
}

int main(){
    int rc=0;
    string s = "wxyz";
    pthread_t t;

    rc=pthread_create(&t,NULL,first,static_cast<void*>(&s));
    if(rc!=0){
        cout<<"error!";
        exit(rc);
    }
    rc=pthread_create(&t,NULL,second,static_cast<void*>(&s));
    if(rc!=0){
        cout<<"error!";
        exit(rc);
    }

    while(flag[0] && flag[1]!=0){}
    cout<<s;

    pthread_exit(NULL);
    return 0;
}

- Adnan

3个回答

0

重构为使用原子操作。请注意显式屏障以确保在线程间读取/写入（非原子）字符串的正确顺序。

也许有人想要检查我的逻辑是否正确？

#include <iostream>
#include <thread>
#include <atomic>
#include <memory>

using namespace std;

// atomic types require the compiler to issue appropriate
// store-release/load-acquire ordering
std::atomic<int> flag[2]={{0},{1}};
std::atomic<int> turn;


void first(std::string& str){
    flag[0]=1;
    turn=1;
    while(flag[1] && turn==1){}
    std::atomic_signal_fence(std::memory_order_acquire);
    if(str!=""){
        if(str=="abcd"){
            str="Hello";
            std::atomic_signal_fence(std::memory_order_release);
        }
    }
    flag[0]=0;
}

void second(std::string& str){
    flag[1]=1;
    turn=0;
    while(flag[0] && turn==0){}
    std::atomic_signal_fence(std::memory_order_acquire);
    if(str!=""){
        if(str=="wxyz"){
            str="abcd";
            std::atomic_signal_fence(std::memory_order_release);
        }
    }
    flag[1]=0;
}

int main(){
    string s = "wxyz";

    auto t1 = std::thread(first, std::ref(s));
    auto t2 = std::thread(second, std::ref(s));

    for( ; flag[0] && flag[1]; )
        ;

    std::atomic_signal_fence(std::memory_order_acquire);
    cout << s << endl;

    t1.join();
    t2.join();
    return 0;
}

期望输出：

wxyz

注：

现代内存架构与该算法发明时大不相同。在现代芯片上，对内存的读写并不会在您预期的时间发生，有时甚至根本不会发生。

取消您接下来3小时的约会，观看这个关于此主题的精彩演讲：

https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2

- Richard Hodges

在原子“flag”声明中删除“=”符号。我尝试了一下，得到的输出是“abcd”和“wxyz”。即使内存栅栏也无法创建所需的结果。我会等待更多建议，也许有关于栅栏的更正意见。 - Adnan

我不明白为什么"abcd"不是一个合理预期的结果。主线程几乎没有与其它线程同步吗？如果两个线程都没有启动，主线程可以打印吗？如果任何一个线程单独启动，它可以无竞争地进行进展。 - Yakk - Adam Nevraumont

哦——其中一个开始为真！这太出乎意料了。嗯，得想一想它的作用。也许没什么重要的。 - Yakk - Adam Nevraumont

当first线程从未开始时，让second线程运行到完成。然后让主线程运行直至join。现在让first线程运行，或让first在线程second完成后运行。我看到有多种可能的字符串输出，所以不确定为什么应该是特定的一种输出。 - Yakk - Adam Nevraumont

“first”线程和“main”线程应该在“second”线程之后加入，我认为这样才能得到我们想要的输出。 - Adnan

0

我必须让线程等待，直到线程first完成，因此我创建了单独的线程，t用于first，u用于second，并通过pthread_join使main等待线程完成。这消除了需要main自旋的需求。

更改：

pthread_t t,u;
pthread_create(&t,NULL,first,static_cast<void*>(&s));
pthread_create(&u,NULL,second,static_cast<void*>(&s));
pthread_join(u,NULL);
pthread_join(t,NULL);
//while(flag[0] && flag[1]!=0){}
cout<<s;

函数中的原子栅栏仍然存在，因为它们确保指令有序执行。

OUTPUT
abcd

并且

Hello

虽然改变pthread_create的first和second的顺序总是输出Hello，但它破坏了第一个线程等待第二个线程完成的想法。因此，我认为上述更改将是解决方案。

- Adnan

flag[0]=1; turn=1; while(flag[1] && turn==1){} -- 这不是C++中的原子栅栏。这是竞争条件，根据C++11标准，您的代码执行未定义行为。实际上，在C++11中，编译器可以假设对全局数据的非同步访问是无竞争条件的，并且加载可以被缓存。您的代码需要使用栅栏、原子操作和/或互斥锁才能成为合法的C++11代码。 - Yakk - Adam Nevraumont

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yakk - Adam Nevraumont · Accepted Answer

在C++11之前，C++没有线程模型。在C++11之后，您的代码对同一变量进行无序访问会导致竞争条件。

竞争条件会导致未定义的行为。

更改std::string不是原子操作。在其他线程正在读取或写入它时，您不能安全地进行更改。

在C++11中，std的线程原语比上述原始pthread代码更好，除非您无法模拟非常罕见的功能。