Solved

Atomic i++ in C

Posted on 2010-09-21
25
1,289 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
Efficient way to get backups off site to Azure

This user guide provides instructions on how to deploy and configure both a StoneFly Scale Out NAS Enterprise Cloud Drive virtual machine and Veeam Cloud Connect in the Microsoft Azure Cloud.

 
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
 
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

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
mixing C++ and C code elegantly 10 158
Super Scope, DHCP 5 78
Memory going from 12gb to 64gb or 96gb. worth it? 15 177
NEED HELP WITH VISUAL STUDIO 2017 (beginner) 6 40
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…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

831 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