ID generator with local static variable - thread-safe?

Will the following piece of code work as expected in a multi-threaded scenario?

int getUniqueID() { static int ID=0; return ++ID; }

It's not necessary that the IDs to be contiguous - even if it skips a value, it's fine. Can it be said that when this function returns, the value returned will be unique across all threads?

--------------Solutions-------------

No, it won't. Your processor will need to do the following steps to execute this code:

  • Fetch value of ID from memory to a register
  • Increment the value in the register
  • Store the incremented value to memory

If a thread switch occurs during this (non atomic) sequence, the following can happen:

  • Thread a fetches the value 1 to a register
  • Thread a increments the value, so the register now contains 2
  • Context switch
  • Thread b fetches the value 1 (which is still in memory)
  • Context switch
  • Thread a stores 2 to memory and returns
  • Context switch
  • Thread b increments the value it has stored in its register to 2
  • Thread b (also) stores the value 2 to memory and returns 2

So, both threads return 2.

No, there is still a potential for races, because the increment is not necessarily atomic. If you use an atomic operation to increment ID, this should work.

++ is not necessarily atomic, so no, this is not thread-safe. However, a lot of C runtimes provide atomic versions, eg __sync_add_and_fetch() for gcc and InterlockedIncrement() on Windows.

If you just need some monotonically increasing (or very close to it) numbers across N threads, consider this (k is some number such that 2^k > N):

int getUniqueIDBase()
{
static int ID=0;
return ++ID;
}

int getUniqueID()
{
return getUniqueIDBase() << k + thread_id;
}

getUniqueID has some at least two race conditions. While initializing ID and when incrementing ID. I've rewritten the function to show the data races more clearly.

int getUniqueID()
{
static bool initialized = false;
static int ID;
if( !initialized )
{
sleep(1);
initialized = true;

sleep(1);
ID = 1;
}

sleep(1);
int tmp = ID;

sleep(1);
tmp += 1;

sleep(1);
ID = tmp;

sleep(1);
return tmp;
}

Incrementing is deceptive, it looks so small as to assume it is atomic. However it is a load-modify-store operation. Load the value from memory to a CPU register. inc the register. Store the register back to memory.

Using the new c++0x you could just use the std::atomic type.

int getUniqueID()
{
static std::atomic<int> ID{0};
return ++ID;
}

NOTE: technically I lied. zero initialized globals (including function statics) can be stored in the bss memory and will not need to be initialized once the program starts. However, the increment is still an issue.

Note: The word almost is used because a global variable will be initialized at process start (i.e. its constructor will be called before entering main) whereas the static variable inside a function will be initialized the first time the statement is executed.

Your question is wrong from the start:

ID generator with local static variable - thread-safe?

In C/C++, a variable that is static inside a function or inside a class/struct declaration behaves (almost) like a global variable, not a local stack-based one.

The following code:

int getUniqueID()
{
static int ID=0;
return ++ID;
}

Would be (almost) similar to the pseudo-code :

private_to_the_next_function int ID = 0 ;

int getUniqueID()
{
return ++ID;
}

with the pseudo-keyword private_to_the_next_function making the variable invisible to all other functions but getUniqueId...

Here, static is only hiding the variable, making its access from other functions impossible...

But even hidden, the variable ID remains global: Should getUniqueId be called by multiple threads, ID will be as thread safe as other global variables, that is, not thread-safe at all.

Edit : Lifetime of variables

After reading comments, I felt I was not clear enough with my answer. I am not using global/local notions for their scope signification, but for their lifetime signification:

A global will live as long as the process is running, and a local, which is allocated on the stack, will start its life when entering the scope/function, and will cease to exist the moment the scope/function is exited. This means a global will retain its value, while a local will not. This also means a global will be shared between threads, while a local will not.

Add to it the static keyword, which has different meanings depending on the context (this is why using static on global variables and on functions in C++ is deprecated in favour of anonymous namespaces, but I disgress).

When qualifying a local variable, this local ceases to behave like a local. It becomes a global hidden inside a function. So it behaves as if the value of a local variable was magically remembered between the function calls, but there's not magic: The variable is a global one, and will remain "alive" until the end of the program.

You can "see" this by logging the creation and destruction of an object declared static inside a function. The construction will happen when the declaration statement will be executed, and the destruction will happen at the end of the process:

bool isObjectToBeConstructed = false ;
int iteration = 0 ;

struct MyObject
{
MyObject() { std::cout << "*** MyObject::MyObject() ***" << std::endl ; }
~MyObject() { std::cout << "*** MyObject::~MyObject() ***" << std::endl ; }
};

void myFunction()
{
std::cout << " myFunction() : begin with iteration " << iteration << std::endl ;

if(iteration < 3)
{
++iteration ;
myFunction() ;
--iteration ;
}
else if(isObjectToBeConstructed)
{
static MyObject myObject ;
}

std::cout << " myFunction() : end with iteration " << iteration << std::endl ;
}

int main(int argc, char* argv[])
{
if(argc > 1)
{
std::cout << "main() : begin WITH static object construction." << std::endl ;
isObjectToBeConstructed = true ;
}
else
{
std::cout << "main() : begin WITHOUT static object construction." << std::endl ;
isObjectToBeConstructed = false ;
}

myFunction() ;

std::cout << "main() : end." << std::endl ;
return 0 ;
}

If you launch the executable without parameters, the execution will never go through the static object declaration, and so, it will never be constructed nor destructed, as shown by the logs:

main() : begin WITHOUT static object construction.
myFunction() : begin with iteration 0
myFunction() : begin with iteration 1
myFunction() : begin with iteration 2
myFunction() : begin with iteration 3
myFunction() : end with iteration 3
myFunction() : end with iteration 2
myFunction() : end with iteration 1
myFunction() : end with iteration 0
main() : end.

But if you launch it with a parameter, then the object will be constructed at the third recursive call of myFunction, and destroyed only at the end of the process, as seen by the logs:

main() : begin WITH static object construction.
myFunction() : begin with iteration 0
myFunction() : begin with iteration 1
myFunction() : begin with iteration 2
myFunction() : begin with iteration 3
*** MyObject::MyObject() ***
myFunction() : end with iteration 3
myFunction() : end with iteration 2
myFunction() : end with iteration 1
myFunction() : end with iteration 0
main() : end.
*** MyObject::~MyObject() ***

Now, if you play with the same code, but calling myFunction through multiple threads, you'll have race conditions on the constructor of myObject. And if you call this myObject methods or use this myObject variables in myFunction called by multiple threads, you'll have race conditions, too.

Thus, the static local variable myObject is simply a global object hidden inside a function.

Category:c# Time:2010-04-24 Views:1

Related post

  • Are function static variables thread-safe in GCC? 2009-08-13

    In the example code void foo() { static Bar b; ... } compiled with GCC is it guaranteed that b will be created and initialized in a thread-safe manner ? In gcc's man page, found the -fno-threadsafe-statics command line option: Do not emit the extra c

  • Are final static variables thread safe in Java? 2010-03-09

    I've read around quite a bit but haven't found a definitive answer. I have a class that looks like this: public class Foo() { private static final HashMap<String, HashMap> sharedData; private final HashMap myRefOfInnerHashMap; static { // time-

  • MSpec: How to make static variables thread-safe? 2012-01-18

    I'm using MSpec for my latest project, and overall I'm really happy with it. However, I do have an issue with concurrency when my tests run in paralel and I'm wondering if anybody has run into this issue or, even better, has a solution? MSpec heavily

  • Are static variables thread-safe? C# 2011-08-04

    I want to create a class which stores DataTables, this will prevent my application to import a list of details each time I want to retrieve it. Therefore this should be done once, I believe that the following code does so, but I am not sure if it is

  • Function-Local Static variable For Unique Id Generation 2010-11-21

    Possible Duplicate: ID generator with local static variable - thread-safe? Would the following function return a unique number every time it is called? What about in a multi-threaded scenario? int returnUniqueNumber() { static int i = 0; ++i; return

  • How to define thread-local local static variables? 2011-09-30

    How to define local static variables (that keeps its value between function calls) that are not shared among different threads? I am looking for an answer both in C and C++ --------------Solutions------------- on Windows using Windows API: TlsAlloc()

  • Why doesn't C# support local static variables like C does? 2009-06-26

    Why doesn't C# have local static variables like C? I miss that!! --------------Solutions------------- You can simulate using a delegate.. Here is my sample code.. public Func<int> Increment() { int num = 0; return new Func<int>(() => {

  • Are static methods thread safe 2009-07-07

    I have a static timer class which will be called by ANY webpage to calculate how long each page has taken to be constructed. My question is are Static classes thread safe? In my example will concurrent users cause a problem with my start and stop tim

  • Local static variables in Timer.Tick event (Stopping a Timer) 2009-07-09

    I have a timer on a page in ASP.NET. After a certain period of time elapses, I want to disable the timer. I want to put a static variable in the timers tick event that will track how many seconds have elapsed. My question is, will this work? If user

  • Deadlock occurs in Function Scoped Static variables (Thread Unsafe in VC++) 2010-02-26

    The question is how function-level statics are constructed when the function is called on multiple threads? Problem Description: Deadlock occurs and my application doesn't get terminated. During initialization of local static variable it tries to acq

  • is local static variable provided by embedded compilers? 2010-02-11

    im working on a c lib which would be nice to also work on embedded systems but im not very deep into embedded development so my question are most embedded compilers able to cope with local static variables - which i would then just assume in further

  • Are table variables thread safe on sql server 2008 r2? 2011-08-26

    For example, I am going to use the following table variable inside one of my stored procedures; DECLARE @MyTempTable TABLE ( someField int, someFieldMore nvarchar(50) ) Is this variable thread safe? if multiple request comes at the same time, do you

  • Simulating a 'local static' variable in python 2009-01-20

    Consider the following code: def CalcSomething(a): if CalcSomething._cache.has_key(a): return CalcSomething._cache[a] CalcSomething._cache[a] = ReallyCalc(a) return CalcSomething._cache[a] CalcSomething._cache = { } This is the easiest way I can thin

  • Is getting and setting a simple static properties thread safe? 2010-08-19

    Possible Duplicate: Are C# auto-implemented static properties thread-safe? In the following example class static class Shared { public static string[] Values { get; set; } } many reader threads read the Values string array periodically, while from ti

  • Does a function local static variable prevent function inlining? 2011-08-18

    I'm writing an attribute shim to get the raw c-string from a library's string implementation. This specific string class, say string_t has members length() and data(). When length() == 0 data() == nullptr. Now I am using an api that doesn't like null

  • Does clang++ do threadsafe initialisation of local static variables? 2011-09-14

    Does clang++ do threadsafe initialisation of local static variables? GCC does, unless you turn it off with the misleadingly named -fno-threadsafe-statics. I'm using Apple clang version 2.0 (tags/Apple/clang-139) (based on LLVM 2.9svn). --------------

  • Is local static variable initialization thread-safe in C++11? 2011-11-12

    I know this is an often asked question, but as there are so many variants, I'd like to re-state it, and hopefully have an answer reflecting the current state. Something like Logger& g_logger() { static Logger lg; return lg; } Is the constructor o

  • Are static const variables thread-safe? 2010-07-13

    I'm wondering whether static constant variables are thread-safe or not? Example code snippet: void foo(int n) { static const char *a[] = {"foo","bar","egg","spam"}; if( ... ) { ... } } --------------Solutions------------- To be really safe you should

  • Are non-synchronised static methods thread safe if they don't modify static class variables? 2011-03-02

    I was wondering if you have a static method that is 'not' synchronised, but does 'not' modify any static variables is it thread-safe? What about if the method creates local variables inside it? For example, is the following code thread-safe? public s

Copyright (C) pcaskme.com, All Rights Reserved.

processed in 2.562 (s). 13 q(s)