The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Multi-threaded programming

This may not be the ideal forum for this question, but as it's so easy to shoot from the hip on JOS pages, I will fire away anyway...

I have started looking at some multi-threaded programming. I understand that the 'volatile' keyword (C/C++) must be used with all variables that can be manipulated by multiple threads, with the intention being as follows:
* In a single-threaded app, most variables are made more efficient by placing them in registers rather than in memory.
* The above causes problems in multi-threaded apps because each thread may try to manipulate memory locations to modify a variable, but underneath the compiler has actually made things more 'efficient' by getting only the CPU registers to be modified. What this means is that the individual threads are working on completely separate registers rather than on the same physical memory location.
* This situation is fixed by using the 'volatile' keyword to tell the compiler that we do not want more efficient code, but we prefer that the variable is actually manipulated directly in memory.

Whewwww... so my question is this... The compiler is usually smart enough to know when to make variables volatile (mem only) or non-volatile (registry) on a single-threaded application. So how come the compiler is not smart enough to do this for multi-threaded apps? After all, each thread is programmed into the application and the various variables it manipulates can be seen to be used by only a single or multiple threads...?
ThreadMan
Wednesday, September 29, 2004
 
 
Oops... I wrote 'registry' in the above, instead of 'registers'. So please don't get me completely misunderstood here. (Shows you that I've obviously spent too much time doing registry stuff as of late).
ThreadMan
Thursday, September 30, 2004
 
 
The short answer is that it's infeasible to do the analysis of your program to determine which variables might be modified in more than one thread. Simple scalar variables you could mostly work out automatically, but any pointer in your program could be pointing at any arbitrary buffer in memory, which might also be pointed at by another pointer somewhere else.

Just so you know, there's a lot more to multi-threaded programming than the "volatile" keyword.

-Mark
Mark Bessey Send private email
Thursday, September 30, 2004
 
 
You're right, the compiler *should* be smart enough to recognize a variable that's used globally across threads. But C (and C++) is a very primitive language, little more than glorified assembler; it does give you complete control over everything going on in the program but the price for that control is the lack of other support you mention. If you want more intelligence in the development language, use a high level language.

(Note: I'm exaggerating slightly to make a point, but imho C++ is the language of last resort, not the default first choice for all development)
Tom H
Thursday, September 30, 2004
 
 
There is a deeper problem in here, being that the C++ standart has no reference to multi-threaded programming in any way.

Refer to http://open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1680.pdf for more information.

About the compiler being 'smart' about volatile. It is impossible... Since multiple threads could have pointers pointing to the same location, the compiler cannot assume nothing. As in many cases, aliasing shows its ugly head...
Whatever
Thursday, September 30, 2004
 
 
Volatile has nothing to do with threading.  Volatile only prevents the compiler from eliding accesses.  For instance, if you write the code:

static int i;
i = 5;
i = 5;

The compiler can drop one of the writes.  If i were declared volatile, this would not be legal.  But this has nothing to do with when the value of i is visible from another thread.  You need to use synchronization primitives when writing multi-threaded apps.  There is no way around it.  This has been discussed more times than I can count on c.l.c++.m: http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&c2coff=1&threadm=d6651fb6.0207010554.793e6f6%40posting.google.com&rnum=2&prev=/groups%3Fhl%3Den%26lr%3D%26ie%3DUTF-8%26c2coff%3D1%26q%3Dvolatile%2Bthread%2Bcomp.lang.c%252B%252B.moderated%2Bkanze%26btnG%3DSearch
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&c2coff=1&threadm=c3ofnd%248k5%242%40glue.ucr.edu&rnum=8&prev=/groups%3Fhl%3Den%26lr%3D%26ie%3DUTF-8%26c2coff%3D1%26q%3Dvolatile%2Bthread%2Bcomp.lang.c%252B%252B.moderated%2Bkanze%26btnG%3DSearch
Brian Send private email
Thursday, September 30, 2004
 
 
"So how come the compiler is not smart enough to do this for multi-threaded apps?"

The difference between a single-threaded application and a multi-threaded application is a call the operating system.  It's a runtime issue, not a compile-time issue. 

"After all, each thread is programmed into the application and the various variables it manipulates can be seen to be used by only a single or multiple threads...?"

How are threads programmed into the application?  There is no language construct for threads.  You just call the OS and the OS re-enters your application code in a different thread.
Almost Anonymous Send private email
Thursday, September 30, 2004
 
 
>So how come the compiler is not smart enough to do this for multi-threaded apps?

Also, I don't think you've thought this through enough.  For a variable to be accessible by multiple threads, it has to be either global or have its address taken at some point.  In each case, this prevents it from being placed in a register.  In any event, thinking about this in terms of registers and the like is way too low level.  It's all about language and platform guarantees, nothing more.
Brian Send private email
Thursday, September 30, 2004
 
 
"I understand that the 'volatile' keyword (C/C++) must be used with all variables that can be manipulated by multiple threads"

I really don't believe that.  The C++ threads posted above provide two basic viewpoints on volatile:

1)  it's necessary, even when using sycnhronization primitives
2)  volatile is useless for threads; compilers must guarantee thread-safety with synchronization primitives.

Personally, I just believe 2 based on experience.  Making code volatile-correct all the way down to the object and class level, in addition to using synchronization primitives, is just too hard and unmaintainable.  And there's no reason why a good compiler can't detect the use of synchronization primitives for a given platform.

Logically, if a compiler optimizes away memory accesses but doesn't account for threads, then it is not an optimizing compiler--it's generating incorrect code based on bad assumptions.
indeed Send private email
Thursday, September 30, 2004
 
 
OK, after doing more research I still have no answer...

My example:

class Shared {
  int var;
}

Shared *pShared = new Shared;

void thread1() {
  ....
  pShared->var = 5;
}

void thread2() {
  ....
  pShared->var = 8;
}

****

Now, ignore that there is no synchronisation between threads in the above code. My interest is purely at what volatile does, and I want to see who can give a smart and concise answer....

In the above code, if the compiler thinks that the variable would be more efficient in a register, then ALL users of pShared class would use the same *register*. Likewise, if I made the variable volatile, then ALL users of pShared class would use the same *memory location* where the variable resides.

So, again, what is the purpose of 'volatile'????
ThreadMan
Friday, October 01, 2004
 
 
Not for threads. I believe volatile was added to C for such things as memory-mapped IO, where assignments have a side effect.
scruffie Send private email
Friday, October 01, 2004
 
 
"Volatile" means "this memory location may change without the processor being involved".

And yes, you use it when assignments/reads to "memory" have side effects like driving devices or polling sensors.
Katie Lucas
Friday, October 01, 2004
 
 
Volatile is one of the techniques used to prevent race conditions for variables that are manipulated by code from different threads. By making sure that the value of a variable is being read (or written) in its location in main memory (or cache, i think, depending on the processor's memory model) race conditions are minimized.
SeanH
Friday, October 01, 2004
 
 
"In the above code, if the compiler thinks that the variable would be more efficient in a register, then ALL users of pShared class would use the same *register*."

No.  Each thread has a context--a machine state, if you will; and thus, the set of registers for each thread is different during its execution timeslice.  The value will not reside in the same _logical_ register.
indeed Send private email
Friday, October 01, 2004
 
 
Katie has the correct answer. Volatile only has meaning when dealing with some hardware that may change a memory location without CPU intervention.

Therefore, Volatile has nothing to do with threading. This is like some strange urban legend propagated by VxWorks geezers. No one knows where this myth originated, or why they put credance in it, yet it persists today.

When you are performing multi-threaded operations on some global, you need to protect access to that data using a semaphore, a conditional or some other access protection provided by the OS.

One more thinb about volatile: If you're dealing with hardware, and some sort of DMA arrangement, you need to worry about mapping that memory as either non-cached, or manage the cache within the device IO calls.
hoser Send private email
Friday, October 01, 2004
 
 
The "urban legend" was probably started because if your needs are simple enough, volatile might be sufficient.  But like you say, any "real" multithreaded program probably needs Mutexes/Semaphores/CriticalSections, or Interlocked* at the very least.  Using volatile for multithreading is a bad habit to get into.  It doesn't protect you against hardware instruction reordering, nor is it much help in maintaining data structure integrity.
Brian Send private email
Friday, October 01, 2004
 
 
"No.  Each thread has a context--a machine state, if you will; and thus, the set of registers for each thread is different during its execution timeslice.  The value will not reside in the same _logical_ register.
indeed
Friday, October 01, 2004"

Mr/Mrs 'indeed' appears to me to have the ONLY decent answer. A lot of the rest of you simply don't appear to understand the fine issues of multi-threading and put it down to 'myths'. I think this says a lot about the professionals in the industry.

To put into my own words using 'indeed's solution, without 'volatile' a variable in a multi-threaded app may be placed into a register. And due to context switching, this register value will be different from ThreadA to ThreadZ. Using volatile forces the variable to memory which is common to all threads.

Which leads me to the second question... why can the compiler not do this automatically. The compiler DOES know about every thread that could/will be created. My guess is the following:
* In sections of the code that are absolute, in the sense that there is no conditional behaviour that would stop the creation of multiple threads, the compiler is smart enough to automatically make the relevant variables 'volatile'.
* In sections of the code that are conditional, for example 'start Thread2 if user clicks ButtonA', the occurance of multiple threads is no longer a definitive. In this case, the compiler edges on the side of safety and makes the appropriate variables registery efficient. It is then the task of the programmer to decide if certain variables should be made 'volatile'. This is also the reason where smart pointers for volatility come in.

BTW Mr/Mrs 'indeed' are you able to state how many years you've been in the business and if you do very high-level type work. It is interesting to note what experience a person with the correct answers has got.
ThreadMan
Friday, October 01, 2004
 
 
To get the right answer you need zero years of experience. All you need to do is RTFM.

"The volatile type qualifier was introduced by the ANSI Standard to permit the use of memory-mapped variables, that is, variables whose value changes autonomously based on input from hardware."

That's from a TUTORIAL.

    Flava Flav!
Flava Flav
Friday, October 01, 2004
 
 
"To put into my own words using 'indeed's solution, without 'volatile' a variable in a multi-threaded app may be placed into a register. And due to context switching, this register value will be different from ThreadA to ThreadZ. Using volatile forces the variable to memory which is common to all threads."

I think the point is, you shouldn't be relying on volatile for multi-threading at all.  If two threads need access to the same variable, they should be a in a critical section.  Otherwise you will have race conditions, volatile or not.  I have never seen volatile used in any multithreaded application, which is not surprising because that's not actually what it's designed for.

"why can the compiler not do this automatically. The compiler DOES know about every thread that could/will be created."

How does the compiler know about every thread that could be created?  We are talking about a C compiler here -- it's only a short level above assembly.  Any function *could* be the start of a thread -- how does the compiler know?  Your suggestions on how the compiler could guess would severely limit possible optimizations.

Use critical sections, leave volitile alone.
Almost Anonymous Send private email
Saturday, October 02, 2004
 
 
From http://www.cuj.com/documents/s=7998/cujcexp1902alexandr/

--/ snip /--

* Inside a critical section defined by a mutex, only one thread has access. Consequently, inside a critical section, the executing code has single-threaded semantics. The controlled variable is not volatile anymore — you can remove the volatile qualifier.

* Outside a critical section, any thread might interrupt any other at any time; there is no control, so consequently variables accessible from multiple threads are volatile. This is in keeping with the original intent of volatile — that of preventing the compiler from unwittingly caching values used by multiple threads at once.

--/ snip /--

So the point is, volatile does nothing inside of a critical section.  And, as we all know, if you have two threads accessing the same data, you should access that data in some type of critical section.  So no need for volatile.
Almost Anonymous Send private email
Saturday, October 02, 2004
 
 
"ThreadMan" if you're asking a question, then several people have given you all the information you need.

From here, you can carry on the arguement with yourself.
hoser Send private email
Saturday, October 02, 2004
 
 
> The compiler DOES know about every thread that could/will be created.

I think that compilers don't: threads are started by the O/S and/or by the run-time library APIs, which the compiler itself doesn't know.
Christopher Wells Send private email
Saturday, October 02, 2004
 
 
Y'know, if I'd know better, I'd just ignore this thread on threads started by ThreadMan.  Call it a weakness.

What does volatile do? Consider the simple code:

extern int x

int foo(void) {
  for(x=0; x<16; x++)
  return x;
}

The asm generated loads x into a register, loops until 15 and returns x. The register value is incremented, and the memory location for x is only accessed once: at the beginning of the loop.

if volatile were added to the var x, as:
extern volatile int x;

Then x is loaded into the register for incrementing AND once more prior to returning.

So, each time x is mentioned, the actual memory location for x is accessed, rather than possibly working from the register to which x was loaded.

volatile means that whenever you read or write x, to use x literally.

And yes, if a software developer were using unsynchronized globals across threads, that engineer would require the keyword volatile.  Shortly thereafter, said developer should be shot.
hoser Send private email
Saturday, October 02, 2004
 
 
"To put into my own words using 'indeed's solution, without 'volatile' a variable in a multi-threaded app may be placed into a register. And due to context switching, this register value will be different from ThreadA to ThreadZ. Using volatile forces the variable to memory which is common to all threads."

Well, I don't think that's necessarily true.  The big debate is really whether compiler support is an absolute must for proper multi-threading; and I think it is.

That is to say:  a compiler can and should, and probably will, statically analyze your program to determine what functions are being run as threads, and what variables are shared between those threads.  At the very least it will ensure that variables locked by critical sections are not cached in registers.

Otherwise volatile will be necessary even when you use critical sections.  Consider the following code:

int _shared_data = 0;
Mutex _shared_mutex;

void threadA(void*)
{
  while(true)
  {
      _shared_mutex.lock();
      _shared_data++;
      ThreadSafeOutput( _shared_data );
      _shared_mutex.unlock();
  }
}

void threadB( void* )
{
  while(true)
  {
      _shared_mutex.lock();
      _shared_data--;
      ThreadSafeOutput( _shared_data );
      _shared_mutex.unlock();
  }
}

Assume that threadA and threadB are run as separate threads of execution.  The compiler may be able to determine that, in threadA, _only_ threadA modifies _shared_data, and therefore it can be cached in a register.  The same goes for threadB. 

So according to the principle of reloading memory with volatile, _shared_data should in theory be declared volatile--even though it is wrapped in a mutex access.

But I don't think that's the case in practice.  In fact, it's entirely impractical to require volatile of any variable that is accessed on a thread, _even_ if it is locked by a critical section.

Imagine if, instead of a simple atomic, _shared_data represented some subsystem of objects.  You would have to make it "volatile-correct" all the way down to the leaf nodes in the object composition.  If you know anything about volatile the qualifier, it's basically like const--and every C++ programmer knows the perils of creating and maintaining strict const-correctness.

Let's say _shared_data looks like this instead:

class Foo
{
public:

  Foo() : _me(0) { }

  void increment() { _me++; }
  void decrement() { _me--; }
  int get() const { return _me; }

private:

  int _me;
};

And so the above code becomes:

Foo _shared_data;
Mutex _shared_mutex;

void threadA(void*)
{
  while(true)
  {
      _shared_mutex.lock();
      _shared_data.incrementMe();
      ThreadSafeOutput( _shared_data.get() );
      _shared_mutex.unlock();
  }
}

void threadB( void* )
{
  while(true)
  {
      _shared_mutex.lock();
      _shared_data.decrementMe();
      ThreadSafeOutput( _shared_data.get() );
      _shared_mutex.unlock();
  }
}

Now, in this instance _shared_data is not volatile, and the compiler could statically analyze its member functions and cache _me in a register.  So according to the theoretical requirement for volatile-correctness, we'd have to change Foo to look like this:

class Foo
{
public:

  Foo() : _me(0) { }

  void increment() volatile  { _me++; }
  void decrement() volatile  { _me--; }
  int get() const volatile { return _me; }

private:

    int _me;
};

And then declare Foo volatile:

volatile Foo;

I hope you can see where this becomes impractical.  Volatile is a performance hit, so applying it to every level of an object subsystem (ie, what if Foo references objects?) will be extremely expensive.

Furthermore, many classes in the STL don't define volatile member functions, so calls to classes like vector<> (container classes) won't be compatible with your threading code, _even when used within a critical section_.

The compiler in the above code must be able to statically analyze threadA and threadB and note the presence of a mutex, and apply register caching semantics appropriately.  volatile is too complex as an implementation device for thread-safety, and cannot be required in practice for thread-safe code.

Just so you understand me:  _when using critical sections, which is what you should do_, volatile is not necessary.  And as hoser pointed out, the matter of whether to use volatile on unsynchronized code is moot; you should simply be using critical sections for access to shared data.
indeed Send private email
Monday, October 04, 2004
 
 
"Well, I don't think that's necessarily true.  The big debate is really whether compiler support is an absolute must for proper multi-threading; and I think it is."

C/C++ have no compiler support for multi-threading, and yet most multithreading code is in C/C++.  So I can't see how compiler support is an _absolute must_ for proper multi-threading.
Almost Anonymous Send private email
Monday, October 04, 2004
 
 
Correction on my post:

x is not accessed once "at the beginning of the loop", it is accessed once for READ at the beginning of the loop. Each time through the loop it is accessed for write.

If the keyword volatile is used, then the value x is accessed for read every time the comparison is made for the loop, whereas without volatile, the comparison is made using the register value.

Anyhow, having said all that, the compiler does not create different code with library functions are used which perform mutex locking (just to be sure, I tried it).

If you modify an extern global, the compiler is commited to updating the value of that global *no matter what*. I could onlt see a compiler optimizing a global if the keyword static were used, then the compiler would know that the scope of that module baseed global is limited and could get smart about who has access.

"So according to the principle of reloading memory with volatile, _shared_data should in theory be declared volatile--even though it is wrapped in a mutex access."

This is incorrect. 
1. _shared_data is always updated when written to in either function.
2. The mutex insures that read operations are safe within the lock.

The rest is moot.
hoser Send private email
Monday, October 04, 2004
 
 
"C/C++ have no compiler support for multi-threading"

Are you sure?  How do you know?  I don't think I've seen very much use of volatile in any MSDN samples; certainly not volatile-correctness on a deep level.

I do know that the standard says virtually nothing about multi-threading.  The Usenet threads posted above make a very valid point that multi-threaded code is not, in fact, standard C++--at least not in its observable execution.
indeed Send private email
Monday, October 04, 2004
 
 
> C/C++ have no compiler support for multi-threading, and yet most multithreading code is in C/C++.

I wonder whether "the compiler" decides to not enregister any variable's value across any function call (including e.g. a function call to EnterCriticalSection etc)?
Christopher Wells Send private email
Monday, October 04, 2004
 
 
Well scratch registers are normally destroyed during a function call (the caller could overwrite them).  So a function call probably is probably enough to reset any kind of register allocation of variables.
Almost Anonymous Send private email
Monday, October 04, 2004
 
 
The compiler MUST commit the value prior to calling another function (the exceptions being static prefixed and/or inline functions), since:

1. The calling function may modify the value.
2. There is no guarantee that the register, even if scratch, won't be used by the next function.
hoser Send private email
Monday, October 04, 2004
 
 
And, if you generate the asm, you can see that the compiler does.
hoser Send private email
Monday, October 04, 2004
 
 
> There is no guarantee that the register, even if scratch, won't be used by the next function.

Well, there may be: the Windows __stdcall convention, for example, guarantees to preserve the EBP, EBX, ESI and EDI registers.

> The compiler MUST commit the value prior to calling another function.

That pretty well explains why calling a[ny] synch function obviates the need for volatile (without the compiler's knowing about multithreading).
Christopher Wells Send private email
Monday, October 04, 2004
 
 
Almost Anonymous refers to  http://www.cuj.com/documents/s=7998/cujcexp1902alexandr/ and then concludes that volatile is worthless: "So the point is, volatile does nothing inside of a critical section.  And, as we all know, if you have two threads accessing the same data, you should access that data in some type of critical section.  So no need for volatile."

But, this is exactly the *opposite* of what the web page he refers to suggests:
>Summary
>When writing multithreaded programs, you can use volatile >to your advantage. You must stick to the following rules:
>    * Define all shared objects as volatile.
>    * Don't use volatile directly with primitive types.
>    * When defining shared classes, use volatile member >functions to express thread safety.
>If you do this, and if you use the simple generic >component LockingPtr, you can write thread-safe code and >worry much less about race conditions, because the >compiler will worry for you and will diligently point out >the spots where you are wrong.
Exception guy Send private email
Wednesday, October 06, 2004
 
 
From the article... (and yes, from here I think I'm beating a dead horse)

"Inside a critical section defined by a mutex, only one thread has access. Consequently, inside a critical section, the executing code has single-threaded semantics. The controlled variable is not volatile anymore — you can remove the volatile qualifier."

"In short, data shared between threads is conceptually volatile outside a critical section, and non-volatile inside a critical section."

The author goes a long way to show how marvelous the LockingPtr class is, when in reality, all he is doing is doing a const_cast inside its ctor. Whooppee.

Which is easier? That huge explanation of LockingPTr or:

pthread_mutex_lock(&mtx);
// do stuff...
pthread_mutex_unlock(&mtx);

We can argue at length regarding which is a better method, without any true metrics to say. But suppose I concede his method.

He is still not advocating the use of volatile to expose unprotected globals to the multithreaded wild. He still describes a method which merely abstracts the usage of mutex locking and is using the volatile keyword as a means for compile-time thread error checking (in a constr-correctness type usage); not for catching a variable state change without mutex locks.

Are we done yet?
hoser Send private email
Wednesday, October 06, 2004
 
 
I had a chance to ponder the notion that stdcall might require for register values to remain unmodified through function calls. This is rather interesting, it means that if I were to modify the scratch register, then I have to push the caller's value to stack, do my thing - perhaps calling other functions - and then restore the scratch register when I'm done.

Of course the optimization may be had if I don't do anything to the scratch register(s), and the caller's intermediate results are never modified. Now the compiler designer has some new challenges and opportunities. Interesting.

No doubt that OS internals for implementing events and semaphores use the volatile keyword.
hoser Send private email
Wednesday, October 06, 2004
 
 
If the function has pointers (in local/automatic variables, or that are passed to it as parameters) then it can load these into BX/ESI/EDI and not reload them after each subroutine call. Similarly, the __thiscall (C++) convention uses ECX for the 'this' pointer, and callees guarantee to preserve ECX.

It's a bit like preserving registers in an interrupt service routine.
Christopher Wells Send private email
Wednesday, October 06, 2004
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz