• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1376
  • Last Modified:

Atomic i++ in C

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
PMembrey
Asked:
PMembrey
  • 10
  • 7
  • 4
  • +3
1 Solution
 
phoffricCommented:
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
 
phoffricCommented:
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
 
PMembreyAuthor Commented:
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
jkrCommented:
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
 
PMembreyAuthor Commented:
I'm running on Linux (at present the test machine is running Fedora 13) so unfortunately I can't use that API call :-/
0
 
jkrCommented:
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
 
phoffricCommented:
See   atomic_inc( &my_counter );   http://www.ibm.com/developerworks/linux/library/l-linux-synchronization.htmlBut, do you have to use this
0
 
Infinity08Commented:
For gcc :
__sync_fetch_and_add(&i, 1);

Open in new window

0
 
PMembreyAuthor Commented:
Infinity08 - this is also safe fo x86_64 as well as i386?

I would rather use something in GCC than third party....
0
 
Infinity08Commented:
>> 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
 
phoffricCommented:
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
 
CSecurityCommented:
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
 
phoffricCommented:
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
 
phoffricCommented:
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
 
Infinity08Commented:
>> 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
 
phoffricCommented:
In that case, after it doesn't work, then won't a membar fix the problem?
0
 
Infinity08Commented:
>> then won't a membar fix the problem?

Yes :)
0
 
phoffricCommented:
So, all's well that ends well (with many exceptions) :)
0
 
Infinity08Commented:
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
 
cupCommented:
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
 
phoffricCommented:
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
 
Infinity08Commented:
>> 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
 
phoffricCommented:
Sorry, Missed the __sync_fetch_and_add. :(  (it was such a tiny post)
But I should have searched for that function.
0
 
PMembreyAuthor Commented:
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 10
  • 7
  • 4
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now