Solved

Atomic i++ in C

Posted on 2010-09-21
25
1,259 Views
Last Modified: 2012-05-10
Hi guys,

I need to ensure that a counter variable (say i) is not updated by more than one thread at a time. I have written a ring buffer and have one thread reading and one writing. The only time they cross swords is when they update the counter variable. I know I could use a mutex but I would much rather avoid using locks if at all possible for performance reasons.

Are there any alternatives to using a mutex here?
0
Comment
Question by:PMembrey
  • 10
  • 7
  • 4
  • +3
25 Comments
 
LVL 32

Expert Comment

by:phoffric
ID: 33725550
Some cpu have atomic operations. What cpu are you using? Dropping to assembly code (probably single instruction) may be the answer for an integral increment.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 33725666
For a ring buffer, there should be no need for atomicity since the writer always is at least one step ahead of the reader. There are two indexes, iw and ir, for the writer and reader, respectively. Each thread checks the other thread to avoid clashes.
0
 

Author Comment

by:PMembrey
ID: 33725763
I suspect the ring buffer implementation I borrowed wasn't particularly concerned with being multithreaded. Both the reader and writer modify the counter varliable.

Actually when I said I wrote it myself, I should have said that I modified an existing example ;-)

http://stackoverflow.com/questions/827691/how-do-you-implement-a-circular-buffer-in-c/827749#827749
0
 
LVL 86

Expert Comment

by:jkr
ID: 33725834
If you are on Windows, there's 'InterlockedIncrement()' (http://msdn.microsoft.com/en-us/library/ms683614%28VS.85%29.aspx), i.e.
LONG i = 0;



// ...



InterlockedIncrement(&i);

Open in new window

0
 

Author Comment

by:PMembrey
ID: 33725848
I'm running on Linux (at present the test machine is running Fedora 13) so unfortunately I can't use that API call :-/
0
 
LVL 86

Expert Comment

by:jkr
ID: 33725922
In this case, 'atomic.h' might be of some help in user space as well (see also http://www.ibm.com/developerworks/linux/library/l-linux-synchronization.html - "Anatomy of Linux synchronization methods"):
#include <asm/atomic.h>



//...



atomic_t i = ATOMIC_INIT(0);



//...



atomic_inc(&i);

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 33725925
See   atomic_inc( &my_counter );   http://www.ibm.com/developerworks/linux/library/l-linux-synchronization.htmlBut, do you have to use this
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 33725940
For gcc :
__sync_fetch_and_add(&i, 1);

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33725952
0
 

Author Comment

by:PMembrey
ID: 33725971
Infinity08 - this is also safe fo x86_64 as well as i386?

I would rather use something in GCC than third party....
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33725990
>> Infinity08 - this is also safe fo x86_64 as well as i386?

If it's not supported for a certain type on your architecture, your compiler should warn you about that.
For int's, I haven't had a problem so far.

For more information, read the link I posted :)
0
 
LVL 32

Expert Comment

by:phoffric
ID: 33726867
Using atomicity as requested leads to non-portable code (if that is an issue with you).http:#33725666 indicates that atomicity is not required for ring/circular buffers.You can get by with head/tail pointers.    http://en.wikipedia.org/wiki/Circular_buffer#Circular_buffer_mechanics    http://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_DistinctionThe "Always Keep One Slot Open" is a simple solution that always keeps one slot unallocated. This includes an example implementation in C. (No thread issues here.)Reading on, if you use an additional fill count (as your link suggests), then "This can require complex logic, especially if you are working with different threads."But reading on, there are other solutions that do not have the thread issues.There are other code solutions further down.
0
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 
LVL 17

Expert Comment

by:CSecurity
ID: 33774522
I think you want something like this:
#include <iostream.h>

#include <windows.h>



int IncrementByOneThread = 0;

bool is_free = true;



DWORD WINAPI thread1(LPVOID lparam)

{

	while(!is_free)

		Sleep(100);

	

	//lock to current thread

	is_free = false;

	

	cout<<"1st";

	IncrementByOneThread++;

	

	//unlock for other thread's user

	is_free = true;

	

	return 0;

}



DWORD WINAPI thread2(LPVOID lparam)

{

	while(!is_free)

		Sleep(100);

	

	//lock to current thread

	is_free = false;

	

	cout<<"2nd";

	IncrementByOneThread++;

	

	//unlock for other thread's user

	is_free = true;

	

	return 0;

}



int main()

{

	HANDLE HandleArr[2];

	

	HandleArr[0] = CreateThread(NULL, 0, thread1, NULL, 0, NULL);

	HandleArr[1] = CreateThread(NULL, 0, thread2, NULL, 0, NULL);

	

	WaitForMultipleObjects(2,HandleArr, TRUE, INFINITE);

	

	CloseHandle(HandleArr[0]);

	CloseHandle(HandleArr[1]);

	

	system("pause");

	return 0;

}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 33774843
Is it conceivable on Windows that for t1 line 9 has is_free==true and before hitting line 13, then t2's line 26 is executed and moves onto line 30?
0
 
LVL 32

Expert Comment

by:phoffric
ID: 33775704
For any OS the following is supposed to work no matter what scheduler surprises there are. See last 5 minutes of:
     http://www.academicearth.org/lectures/synchronization
Too-Much-Milk--3a.bmp
Too-Much-Milk--3b.bmp
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33776095
>> For any OS the following is supposed to work no matter what scheduler surprises there are.

Except if you're on a multi-core system and/or the compiler optimization messes things up ;)
0
 
LVL 32

Expert Comment

by:phoffric
ID: 33776184
In that case, after it doesn't work, then won't a membar fix the problem?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33776211
>> then won't a membar fix the problem?

Yes :)
0
 
LVL 32

Expert Comment

by:phoffric
ID: 33776286
So, all's well that ends well (with many exceptions) :)
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33776459
Heh. There are so many pitfalls when it comes to multi-thread and multi-process programming, that it's easy to either give the wrong advice, or to misinterpret advice. Solutions that are guaranteed to work without issues on one platform might not do so well on other systems.
0
 
LVL 11

Expert Comment

by:cup
ID: 33784549
If you are using windows, have a look at CRITICAL_SECTION, InitializeCriticalSection, EnterCriticalSection, LeaveCriticalSection and ExitCriticalSection: the SDK versions, not the MFC versions.  The MFC versions just use wait for single object.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 33821359
The spin-lock pseudo-code in the Too Much Milk slides is suitable for your critical region (in this case, i++). Very few cycles are wasted since the critical region is so small and provided that each thread is on a separate core. If the multi-threaded program resides on a single core processor, then a spin can consume an entire scheduling cycle.

On some processors, there are atomic operations that can do an i++. See, for example,
       type    __sync_fetch_and_add (type *ptr, type value);
   http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html

In this case, you would replace
   i++;
with
   __sync_fetch_and_add( &i , 1 );
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33821700
>> In this case, you would replace
>>    i++;
>> with
>>    __sync_fetch_and_add( &i , 1 );

I think that has already been suggested ;)  (and acknowledged by the author)
It feels like we've made full circle now heh.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 33822515
Sorry, Missed the __sync_fetch_and_add. :(  (it was such a tiny post)
But I should have searched for that function.
0
 

Author Closing Comment

by:PMembrey
ID: 33867062
Hi guys,

Really sorry for the delay on this - I've been away for a bit and I was sure I'd already accepted this as the answer.

Again, sorry for the delay...
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

758 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

21 Experts available now in Live!

Get 1:1 Help Now