Peterson的算法的行为为各种优化标志 [英] Peterson's Algorithm's behavior for various optimization flags

问题描述

我想检查gcc和icc的各种优化选项的行为。
Took Peterson的2 Thread互斥算法。如果锁定方法中的行a和行b（在注释中）的执行顺序被交换，则此算法可能失败。
使用带有-O0标志的icc或gcc进行编译可生成正确的结果。
使用带有-O3标志的icc编译产生不正确的结果。
用gcc编译-O3标志不产生任何结果。程序挂起。
所以我的猜测是与-O3标志gcc和icc已优化锁定方法，并假设在线a和线b之间没有依赖。因此，两者都产生错误的结果。
这种依赖性对于编译器来说很难找到，所以有一种方法（pragmas像ivdep）告诉编译器关于特定代码块中的依赖，所以我们仍然可以使用-O3标志为代码的其他部分

I wanted to check the behaviour of gcc and icc for various optimization options. Took Peterson's 2 Thread mutex algorithm. This algorithm can fail if the order of execution of line a and line b (in comments) in lock method are swapped. Compilation with icc or gcc with -O0 flag produces correct results. Compilation with icc with -O3 flag produces incorrect results. Compilation with gcc with -O3 flag produces nothing. Program hangs. So my guess is with -O3 flag both gcc and icc had optimized the lock method and assumed that there is no dependency between line a and line b. Hence both produced wrong results. Such dependency are hard for compilers to find, so is there a way (pragmas like ivdep) to tell the compiler about the dependencies in specific code blocks, so that we can still use -O3 flag for other sections of the code

锁定方法：

void lock(int me)
{
    int other;
    other = 1-me;
    flag[me] = 1; //Line a
    victim = me;  //Line b
    while(flag[other]==1 && victim == me)
    {
    }
}

如果交换了线a和线b的执行顺序，则违反MUTEX的示例：

Example for MUTEX violation if order of execution of line a and line b are swapped:

T0 0 sets victim=0
T1 1 sets victim=1
T2 1 sets flag[1]=1
T3 1 checks flag[0]. flag[0] not yet set.
T4 1 enters CS
T5 0 sets flag[0]=1 and checks flag[1]. It is set but victim=1.
T6 0 also enters cs

完整代码：

#include<stdio.h>
#include<pthread.h>
#include<stdlib.h>
#include<time.h>
#include<stdint.h>
int flag[2];
int victim;
int sharedCounter=0;

void lock(int me)
{
    int other;
    other = 1-me;
    flag[me] = 1;
    victim = me;
    while(flag[other]==1 && victim == me)
    {
    }
}

void unlock(int me)
{
    flag[me]=0;
}

void *peterson(void *ptr)
{
    int tId,i;
    tId = (int ) (intptr_t) ptr;
    for(i=0;i<200;i++)
    {
        lock(tId);
        sharedCounter++;
        printf("%d\t",sharedCounter);
        sleep(1/10);
        unlock(tId);
    }
}

main()
{
    int i;
    for(i=0;i<2;i++)
    {
        flag[i]= 0;
    }
    pthread_t t[2];
    for(i=0;i<2;i++)
    {
        pthread_create(&t[i],NULL,peterson,(void *) (intptr_t) i);
    }

    for(i=0;i<2;i++)
    {
        pthread_join(t[i],NULL);
    }
    printf("shared Counter:%d\n",sharedCounter);
    exit(0);
}

推荐答案

将变量声明为将阻止对这些变量的读取或写入的重新排序。

Declaring variables as "volatile" will prevent reordering of reads or writes of these variables only.

这篇关于Peterson的算法的行为为各种优化标志的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！