Solved

Atomic increment

Posted on 2006-11-05
19
3,782 Views
Last Modified: 2007-12-19
From what I can tell, incrementing an integer variable is not atomic, and usually translates to 3 assembly instructions.  (move variable into register, increment variable, write variable back to memory.)

So, if I wanted to keep a counter variable in a multi-threaded environment, to determine how many times some function was called, I assume that using a simple global variable which is incremented by the function is not guarenteed to work properly.

Am I correct in this assumption?

If so, is there anyway to write an atomic increment in C without using a mutex?  
0
Comment
Question by:chsalvia
  • 5
  • 5
  • 3
  • +4
19 Comments
 
LVL 45

Expert Comment

by:Kdo
ID: 17878192
Hi chsalvia,

Here's a link to some code where this problem is already solved.  There's not a true atomic instuction, but this guy seems to have simulated it pretty well.

  http://www.mulle-kybernetik.com/artikel/Optimization/opti-4-atomic.html


Good Luck!
Kent
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 17878800
You are correct in and this is ideal place to use a spinlock. I hope you remember spinlocks from our previous discussions.
0
 
LVL 24

Accepted Solution

by:
fridom earned 50 total points
ID: 17879138
There is no direct way in C for that. However the diverse Operating Systems usually have on API function for atomic increments. This things have also found their way into libapr e.g.

Regards
Friedrich
0
 
LVL 22

Expert Comment

by:grg99
ID: 17880240
You could try something a bit kloodgey and see how well it works:

repeat

   OldValue = Counter;
   Counter = Counter + 1;

until Counter > OldValue;

..   That should ensure the counter gets incremented.

You'd better check it on some real running code as maybe we've introduced some other problem.


0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 17880252
Greg, that would still not handle lost updates ... two threads might be incrementing at the same time, one may overwrite the other's update - end result being that variable increments by one while actual value should have been +2
0
 
LVL 45

Expert Comment

by:Kdo
ID: 17880704

Hi Sunny, Greg, chsalvia,

I've never tried this, but depending on the flavor of unix, could one implement a single threaded increment with a call to signal()?  Signal() often blocks the same signal from occurring while the signal processor is running.



#include <signal.h>

//       typedef void (*sighandler_t)(int);
//       sighandler_t signal(int signum, sighandler_t handler);

//       Signal handler for atomic increment
void sighandler_t IncrementAtomic (int Address)  // Requires the variable be passes as an int
{
  ++((int *)Address);
}


Kent
0
 

Author Comment

by:chsalvia
ID: 17882355
>> You are correct in and this is ideal place to use a spinlock. I hope you remember spinlocks from our previous discussions.

Yes, it is essentially a busy wait, correct?  I just read an article about spin lock, and it seems to basically be a simple loop.  Although the article does not recommend trying to implement in spin lock in higher level languages.  It says spin locks should be implemented using assembly.

But how does a spin lock help to increment a variable atomically?  It seems that when a thread goes into a spin lock, it can't do anything else at all.  So how does the variable get incremented?
0
 
LVL 16

Assisted Solution

by:PaulCaswell
PaulCaswell earned 50 total points
ID: 17884371
Hi chsalvia,

I can think of a technique that can be repeated sufficiently to reduce the likelihood of a race to almost zero.

1. Check that the lock value is zero.
2. Add a precalculated random number to the value.
3. Wait a random (but small) amount of time.
4. Make sure the value is exactly what you expect.

You can chain these to several levels. The more levels, the more secure.

To avoid generating random numbers you can assign each thread a unique number to add.

Backing out can be a little complicated but I believe it is possible.

Without a truly atomic increment it is impossible to guarantee a lock but this technique can get close.

Code would look something like this:

static int spin = 0;

int lock ( int uniqueNumber )
{
 int locked = 0;
 if ( spin == 0 ) {
  spin += uniqueNumber;
  waitABit();
  if ( spin == uniqueNumber ) locked = 1;
 }
 return locked;
}

There are two places another thread could interfere. Both should be handled by this code.

Paul
0
 
LVL 45

Expert Comment

by:Kdo
ID: 17884433
Hi Paul.

Take the random number out of it.  Each thread gets its own number and adds that value.  If the values are relatively prime and at least 10E+7 then the likelihood of missing a lock are nearly zero.


Kent
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 16

Expert Comment

by:PaulCaswell
ID: 17885287
Hi Kent,

I prefer your signal method. :-)

Paul
0
 

Author Comment

by:chsalvia
ID: 17887219
Kdo,

So you're saying I could basically create a signal handler function as a means of to pull off an atomic increment?  That sounds like an interesting idea.  But what signal do I generate for this?  An alarm?

Also, how would I pass the value to be incremented to the signal?  When you call a signal, you do something like:

signal(SIGALRM, sig_handler_func);

But how do you pass an integer to sig_handler_func?

0
 

Author Comment

by:chsalvia
ID: 17887251
Paul,

Your method looks interesting.  Two questions:

Firstly, where does the actual increment fit into this?  I'd imagine you would increment the integer after you successfully achieve a lock?  So you would do:

static int spin = 0;
int lock ( int uniqueNumber )
{
 int locked = 0;
 if ( spin == 0 ) {
  spin += uniqueNumber;
  waitABit();
  if ( spin == uniqueNumber ) {
     locked = 1;
 }
 return locked;
}

/* try to get lock and then increment number */
for (;;) {
   if (lock(uniqueNumber)) {
      ++num;
      break;
    }
}

Is that how it would work?

Also, what is the difference between this method and just using a mutex?  Why not just do:

pthread_mutex_lock(&mutex);
++num;
pthread_mutex_unlock(&mutex);

I realize I originally asked how to do this *without* a mutex, but I'm wondering if there is any difference between your method and just using a mutex.  
0
 
LVL 45

Assisted Solution

by:sunnycoder
sunnycoder earned 50 total points
ID: 17888484
>But how does a spin lock help to increment a variable atomically?  It seems that when a thread goes into a spin lock,
>it can't do anything else at all.
It is busy waiting for a lock ... Instead of taking the thread off "ready to execute" list, put it on "waiting for some resource" list and then waking it up again when resource becomes available, the thread just spends its alloted CPU time slice doing a busy wait ... Since critical section is very small (just an increment), it is almost sure that thread which currently has the lock would have released it by the time this thread is rescheduled. This is the soonest possible it can get into CS and probably much faster than having it put off to a different queue and then woken up again.
Locks indeed are probably the best way to do this.

Kent,

What happens if what happens if two threads signal at the same time? Is signal mask process wide or thread wide in this case? Are sigaction APIs thread safe?

I am not sure of sigaction interface is safe for such use but signal interface was definitely not good enough.

No offence but I do not recommend synchronizing using signals. I had nightmarish time mixing threads and signals (and ofcourse there were other IPCs and synchronization mechanisms in use too) - do not remember the exact problems I faced but they were bad enough for me to remember the lesson ;-)

Either way, locking might be far more efficient than having to raise and catch a signal for incrementing a number

Cheers!
sunnycoder
0
 
LVL 45

Expert Comment

by:Kdo
ID: 17889005

Hi Sunny,

I posed it as a question because I'd never actually done it and it seemed like an interesting idea.

I suspect that it's implementation dependent.  Some operating systems interlock on signal processing so that only one instance of a specific signal can be active at any time.

Plus, it's not the most efficient way to do this, but it does seem interesting and possible.


Kent

0
 

Author Comment

by:chsalvia
ID: 17889955
I was looking at the gcc library, and they provide a atomic_t struct, which is passed to a function which increments the variable using inline assembly, like this:

#ifdef CONFIG_SMP
#define LOCK "lock ; "
#else
#define LOCK ""
#endif

typedef struct { volatile int counter; } atomic_t;

static __inline__ void atomic_inc(atomic_t *v)
{
      __asm__ __volatile__(
            LOCK "incl %0"
            :"=m" (v->counter)
            :"m" (v->counter));
}

I suppose the disadvantage here is that this is not portable.  But, would this still work if I replaced the integer with a 64-bit integer or made it unsigned?
0
 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 50 total points
ID: 17890057


Here's a pretty good page from the folks over at BSD.  

  http://people.freebsd.org/~kan/rtld1.diff



Kent
0
 

Author Comment

by:chsalvia
ID: 17891218
>> Here's a pretty good page from the folks over at BSD.  

Wow, that looks like an entirely custom mutex implementation.  Seems you could use that in place of POSIX mutexes.
0
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 17892618
>>Your method looks interesting.  Two questions:
It's a mechanism I've used before but only when mutex or semaphore isnt available and it CAN break.

I think you answered both your questions. :-)

Paul
0
 
LVL 5

Assisted Solution

by:migoEX
migoEX earned 50 total points
ID: 17898510
A different angle to attack the prolem: you can use per-thread counters, which can be incremented independantly. Then you will need to sum all the values in order to get the total number of invocations.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

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 writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.

707 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

14 Experts available now in Live!

Get 1:1 Help Now