Solved

simple race condition in c

Posted on 2012-03-27
15
568 Views
Last Modified: 2012-04-08
Hi all,
I'm trying to write a simple program on race condition, but when i try to run for about 5000 times, the output seems to still the same.
according to the below program, it should have times that it might print:
Counter value: 1
Counter value: 1

instead of:
Counter value: 1
Counter value: 2

Can anyone figure the issues, or maybe explain?
Thanks.

#include <stdio.h>
#include <pthread.h>

int counter = 0;

void *compute()
{
	counter++;
	printf("Counter value: %d\n", counter);
}

int main() 
{
	pthread_t thread1, thread2;

	pthread_create(&thread1, NULL, compute, NULL);
	pthread_create(&thread2, NULL, compute, NULL);

   	pthread_join( thread1, NULL);
   	pthread_join( thread2, NULL);

	exit(0);
}

Open in new window

0
Comment
Question by:crazy4s
  • 6
  • 4
  • 2
  • +2
15 Comments
 
LVL 40

Accepted Solution

by:
evilrix earned 125 total points
ID: 37772530
Well, one of the defining characteristics of a race condition is the behaviour is completely non-deterministic. It may very well run with identical results 1 million times and then the next run might give totally different results. Because the defining factor is time it all depends on what the CPU is doing at the time and the priority ordering it gives each thread (and probably lots of other factors as well).

Try building it in release and not debug mode (ie, with optimization) that may very well make a difference (but it also might not).

FWIW; your code looks like a classic race condition to me.
0
 

Author Comment

by:crazy4s
ID: 37772560
hmm or do you have any example of race condition for me for reference?
unfortunately i couldn't find any sample code that has race condition in c:(
0
 
LVL 86

Assisted Solution

by:jkr
jkr earned 125 total points
ID: 37772699
evilrix is right about the "classic race condition", yet your example "suffers" from one effect: On x86 platforms, your increment operation will most likely be optimized to one atomic assembly statement that simply won't misbehave like a race condition.

If you need an effective example, take a look at http://www.minek.com/files/unix_examples/race.html - you should easily be able to rewrite that 'fork()'ing code to threads.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 37772715
And instead of writing out single integer values write out long strings. That will give you more change of seeing "garbled" output because each quantum is attempting to do a whole lot more and so the chances of seeing the problem are increased.
0
 
LVL 86

Expert Comment

by:jkr
ID: 37772773
That's what the example that I linked does ;o)
0
 

Author Comment

by:crazy4s
ID: 37772774
hmm i made some changes to the sample code, but not sure whether is it correct to do it in this way, but i seems to get the same output:(

#include <stdio.h>
#include <pthread.h>

void *compute(void *str)
{
	char *ptr;
	int c;
	setbuf(stdout, NULL);
	for (ptr = str; c = *ptr++; )
		putc(c, stdout);
}


int main(int argc, char *argv[]) 
{
	pthread_t thread1, thread2;

	pthread_create(&thread1, NULL, compute, "Output from thread1");
	pthread_create(&thread2, NULL, compute, "Output from thread2");

   	pthread_join( thread1, NULL);
   	pthread_join( thread2, NULL);

	exit(0);
}

Open in new window

0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 125 total points
ID: 37772784
Much depends on what code is being generated. On some platforms, with certain compilers (and compiler options), the generated code might be such that the race condition is less likely to manifest itself, or even completely removed.

However, just to confirm that your code DOES have a race condition : when I ran your code, I got a "1,1" output after just 89 times, and got 4 times a "2,1" output before that. Note that another possibility is a "2,2" output.

The generated code looked like this (with some potential issues pointed out - assuming only one thread switch) :

        movl    counter(%rip), %eax   ; thread switch after this instruction : both threads increment from 0 to 1, so both threads print 1
        addl    $1, %eax              ; thread switch after this instruction : both threads increment from 0 to 1, so both threads print 1
        movl    %eax, counter(%rip)   ; thread switch after this instruction : increment happens twice before printing, so both threads print 2
        movl    counter(%rip), %edx   ; thread switch after this instruction : printing done the other way around, ie. first 2 then 1 (idem for the next few instructions before the call instruction)
        movl    $.LC0, %eax
        movl    %edx, %esi
        movq    %rax, %rdi
        movl    $0, %eax
        call    printf

Open in new window


Try looking at the code generated on your platform to get a better idea of the likelihood of the race condition manifesting itself.
0
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 8

Assisted Solution

by:eager
eager earned 125 total points
ID: 37778116
Each time you run your program, there is exactly one opportunity to encounter a data race.  Running the same program over and over is unlikely to make any difference in how it performs.

The window for seeing any evidence of a race is very small.  To see this, one thread needs to interrupt the other in that small window.  Since both threads are running at the same priority, without any waits, it is unlikely that this would happen.

If you are running on a single-processor system, it's likely that the program is fully deterministic and there is no opportunity for one thread to interrupt the execution of another.  

If you want to simulate a data race condition, you need to set up the program so that it is possible for one thread to interrupt another.  And then you need to do this many many times.  For example, you might insert a random delay in the compute function so that it is possible that it might be preempted.  Run this is a loop, not just one time.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 37778243
>> Each time you run your program, there is exactly one opportunity to encounter a data race.

That's misleading. If the same unprotected critical section of code is entered may times by 2 or more threads each entrance is a race condition event. There may be only one race condition (in terms of the code) but that race condition can be encountered numerous times.

>> If you are running on a single-processor system, it's likely that the program is fully deterministic

That really makes no difference what so ever. The CPU allocates a time slice to each thread (called a quantum). If it just so happens that every time the program runs those quantums are always allocated at exactly the same time the result will appear to be deterministic. If; however, those quantums are not allocated at exactly the same time (because the CPU is busy allocating a time-slice to a different thread in a different process for example), then the result may very well appear non-deterministic. In both cases; however, the code *is* non-deterministic because in both cases there is the possibility for the out come to be different.

The fact that you have more than one CPU does not change this. In fact, quite the opposite; it could actually make the code appear to be more deterministic because other processes are less likely to steal quantums from your process.

>> For example, you might insert a random delay in the compute function

But that wouldn't be non-deterministic that would just be pseudo random and it would also be expected because you've coded it to behave in a random way. Even if there wasn't a race condition you'd see pseudo non-deterministic results. A race-condition exists only because two or more threads are "racing" to access a resource and which one gets there first is non-deterministic with the determinism not directly influenced by your program.

Put another way, there is a difference between stimulating and simulating non-deterministic behaviour. If you're not sure what the difference is I can heartily recommend the book Debugging Rules by David J. Agans, where he explains why simulating a problem is not the same a stimulating it and why the former will not help you when trying to fix a problem.
0
 
LVL 8

Expert Comment

by:eager
ID: 37778388
elvirix -- in such a small program the time slice is so much larger than the time for the thread to execute that it is unlikely that it would ever be interrupted.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 37780391
I don't think I disagreed with that point, did I?
0
 
LVL 8

Expert Comment

by:eager
ID: 37780461
That was the point -- this tiny example of a data race is almost impossible to demonstrate a problem.  

There's no need for a race to be deterministic.  In practice, none are, since if the race conditions were deterministic, they would either always occur or never.  

Given single processors, priority dispatch (without preemption), and no stalls in the threads, it is almost impossible for a single-processor system running this little program to encounter a data race. The only way you might have this little program show a data race is if two processors dispatched two threads simultaneously.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 37780767
>> There's no need for a race to be deterministic.
I didn't say they are deterministic, did I?

http:#a37772530 : "Well, one of the defining characteristics of a race condition is the behaviour is completely non-deterministic."

If it was deterministic it wouldn't be a race condition. A race is not a race if the same runner is always guaranteed to win :)

>> The only way you might have this little program show a data race is if two processors dispatched two threads simultaneously.

That is just not true. Regardless of the number of processes available the code contains a race condition that could (which is not the same as will) manifest.

Let's consider an abstract example (and assume a single cpu pre-emptive environment) with 2 threads and assume it will only count up to 9:

First run:

thread A outputs 0,1,2,3,4 <context switch>
thread B outputs 0,1,2,3,4,5,6 <context switch>
thread A outputs 5,6,7,8,9 <context switch>
thread B outputs 7,8,9 <context switch>

So output is: 01234012345656789789

Second run:

thread A outputs 0,1,2,3,4,5,6 <context switch>
thread B outputs 0,1,2,3,4 <context switch>
thread A outputs 7,8,9 <context switch>
thread B outputs 5,6,7,8,9 <context switch>

So output is: 01234560123478956790

Now, let's compare the results

01234012345656789789
01234560123478956790

They are different. Why? Because the context switch happened at different times (because the CPU was busy doing different things during each run). It may also be true that on each run we get identical results because the cpu was able to allocate identical quantums but that doesn't make the result deterministic; the consistency was by luck and not design.

Now, in the case where there is more than one CPU there is actually less chance of this process being allocated different quantums because the other cpu(s) can handle other processes in parallel (in other words this process is more likely to get allocated all the quantum in needs without other processes interfering). Of course, this is up to the OS scheduler and I am not saying this will happen, only that the potential exists.

>> The only way you might have this little program show a data race is if two processors dispatched two threads simultaneously.

This may be true if each thread can complete its task in a single quantum or if the cpu always allocates identical quantums (see my point about about multiple cpus) to each thread during each time slice but the fact is you cannot determine this; hence, the result in still non-deterministic. Either way, there is still a race condition no matter how many cpus there are.

Introducing a random element doesn't actually help because although the result will appear non-deterministic that isn't the same as seeing the race-condition in action. You have exactly the same probability that the race condition will manifest either way but what you are doing is simulating the non-deterministic behaviour by introducing your own element of randomness.

The problem with this is you'd see the same "random" result without a race condition if you introduce this extra random element. Only if your original code would be guaranteed to run deterministically if the race-condition was fixed would you have successfully simulated.

Stimulation: changing the environment but not the code to reproduce a defect
Simulation: changing the code and behaviour to reproduce a defect

The difference may appear semantic but it's not. When you simulate a defect you are seeing the result of your contrived changes and (quite possibly) not the original problem. If you change the code to force the defect and fix what appears to be the problem when you revert your code back you have no idea that the original problem is fixed because (a) you have no way to force the original problem to manifest and (b) because you don't know if you fixed the real problem or the problem you simulated. In other words, the result of simulation is that you have as much chance of seeing the deterministic result of your code change to introduce a random element that you do seeing the manifestation of the non-deterministic race-condition.

It is important to understand the difference between a race condition (which is truly non-deterministic) and adding a random element to your code. The former is truly non-deterministic because it is completely outside the control of my program. The latter is not non-deterministic because the code change is forcing the random behaviour. Not only is does this make the random-like behaviour expected (so in a way it is deterministic) but if I know the algorithm that was used to generate the random element I can consistently predict the result each and every time (assuming the race condition doesn't kick in). The same is not true for a race condition where the result is truly non-deterministic and can never be predicted.

The problem with race conditions is that due to the fact they are non-deterministic there is no easy deterministic way to force them to happen, this is why they are so difficult to identify, reproduce and fix and why they are do hard to get your head around (and explain properly) :(
0
 
LVL 8

Expert Comment

by:eager
ID: 37782252
What does any of this have to to with the question?
0
 
LVL 40

Expert Comment

by:evilrix
ID: 37782265
Nothing directly to do with the question; every thing to do with ensuring the asker isn't given incorrect information. Your original assertions are misleading. That said, since the question is about race conditions and this discussion topic is about race conditions I'd say that it's all useful information for the asker.
0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now