2

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

lock method:

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

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

Full code:

#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);
}
1

1 Answer 1

1

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

Sign up to request clarification or add additional context in comments.

6 Comments

that was simple and it works even with O3 flag. But I thought volatile had to do with preventing the compiler from optimizing instructions on a single variable. But here we have an indirect dependency. May be my understanding of volatile keyword is wrong. Could you please elaborate on this?
@arunmoezhi: Writes and reads of volatile qualified objects are considered part of the "externally visible" effects of the program. So if your program writes to volatile variable a before reading volatile variable b, the write and read must occur in that order. Note however that this doesn't stop the CPU from reordering the memory accesses out from under you, if your architecture allows such a thing...
@caf: Thanks for the reply. "So if your program writes to volatile variable a before reading volatile variable b, the write and read must occur in that order". Are you saying that even if the read and write occur on different volatile variables, the order in which they occur is preserved?
@arunmoezhi: Yes, because that's the order in which they're executed on the abstract machine, and all accesses to volatile qualified objects are considered part of the program's observable behaviour.
harbison and steele p91/92 - "refs to and mods of volatile objects must not be optimized across seq points." seq points are defined at publications.gbdirect.co.uk/c_book/chapter8/… (but i can't find in that link where they tie this to volatile). anwyay, h&s is an excellent book you should have if you are asking these kind of questions.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.