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