Thread: no lock, not volatile, compiler optimization causing a deadlock??

  1. #1
    Alessio Stella
    Join Date
    May 2008
    Location
    Italy, Bologna
    Posts
    251
    consider this example (with pthreads)

    Code:
    Thread1
    ..
    while(quit) {do things without using quit}
    ..
    
    Thread 2
    ..
    quit++;
    ..
    In this very simple case one might think it is not necessary to protect quit with mutex cause a rush condition might only delay of one iteration
    the exit by the while
    BUT
    The compiler (not testing wether quit is used by other threads) might optimize storing the value of quit once at the beginning of the loop into a register and so Thread1 might deadlock?

    Would it be sufficient to declare quit volatile? (read below correction1)
    Or would it be necessary the use of a pthread_mutex_lock() unlock()? Would the use of lock/unlock ensure the compiler would not do that optimization?? (read below correction2)

    Code:
    Correction 1
    
    volatile int quit;
    
    Thread1
    ..
    while(quit) {do things without using quit}
    ..
    
    Thread 2
    ..
    quit++;
    ..
    Code:
    
    Correction2
    
    
    Thread1
    ..
       ..lock..
       quitV=quit;
       ..unlock..
    while(quitV) 
    {
      do things without using quit
       ..lock..
       quitV=quit;
       ..unlock..
    }
    ..
    
    Thread 2
    ..
    ..lock..
    quit++;
    ..unlock..
    ..
    i guess volatile has more to deal with single-thread hardware interfacing to devices mapped in memory (where the device "plays the role of a second thread")
    so i guess in a pthread context, if a correction is needed, Correction 2 is the appropriate?
    Last edited by mynickmynick; 07-16-2008 at 08:06 PM.

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Volatile will prevent the compiler optimization and resultant deadlock, but I think without additional measures, while(quit) may not evaluate to false for some time after the other thread has changed the value.

    You may want to wait for somebody else to confirm that, cause I don't have much experience with multithreading.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by King Mir View Post
    Volatile will prevent the compiler optimization and resultant deadlock, but I think without additional measures, while(quit) may not evaluate to false for some time after the other thread has changed the value.
    Not sure what you mean by that, but the value will change "immediately" (as in within a few dozen nanoseconds on a modern machine) in the memory, and if there are multiple cores/processors, the other processor will be told "if you have cached the memory that has address equal to &quit, please remove it from your cache and read back from main memory, as it may have changed" (or, in processor terms, "invalidate the cacheline of &quit"). All of this shouldn't take more than 0.1 microsecond or so.

    Obviously, a modern processor can probably execute something like 100 instructions in 0.1 microsecond, so in that respect, it is "quite some time" - however, if it's just coming up to the "while(!quit)" piece of code, and the other processor has already written a new value to the quit variable, then it will just stall the processor until it can read the new value of quit, so it's not going to do another iteration after quit has been written. Guaranteed.

    Obviously, if we have JUST read the quit as "false" when it gets written by another processor to "true", another full iteration of the loop will be done until next time we read quit again.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Alessio Stella
    Join Date
    May 2008
    Location
    Italy, Bologna
    Posts
    251
    ok thanks very interesting
    But you both focused only on the first correction (volatile)

    I am more interested to know in detail what happens with the second correction (lock/unlock without volatile) : does this prevent the compiler probable optimization of not updating the value (storing it only at first iteration inside a register)?

    thank you!

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by mynickmynick View Post
    ok thanks very interesting
    But you both focused only on the first correction (volatile)

    I am more interested to know in detail what happens with the second correction (lock/unlock without volatile) : does this prevent the compiler optimization of not updating the value?
    A global variable can be changed by any function called, so the compiler can not (unless it's going to break itself) let the code keep a value in a register across function calls [unless it can see all of the code and understands that it doesn't change the global variable in some way], so that's probably what happens.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Alessio Stella
    Join Date
    May 2008
    Location
    Italy, Bologna
    Posts
    251
    Quote Originally Posted by matsp View Post
    A global variable can be changed by any function called, so the compiler can not (unless it's going to break itself) let the code keep a value in a register across function calls [unless it can see all of the code and understands that it doesn't change the global variable in some way], so that's probably what happens.

    --
    Mats
    i would agree but in a pthread context might be the compiler assumes (following POSIX standard) that if a variable is not protected by mutex (surrounded by lock/unlock) then it is not shared-> So, like in a single-thread-program, that global variable cannot be changed outside of that while(){iteration} (no matter if appearing elsewhere in the functions) -> So it can be cached once with no update at each iteration -> causing a deadlock!!
    Last edited by mynickmynick; 07-17-2008 at 04:29 AM.

  7. #7
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    No. I really don't believe it will assume such a think. Mutexes have a performance downside, so it wouldn't make you use them.
    Volatile is used to fix the I/O problem with devices appearing to be memory locations. It could be used to fix the above problem, but I don't believe so. I haven't seen anywhere recommending using volatile global variables with threads. If the normal variables didn't work, then it would be an everyday problem.

    Also, note that the compiler sees a call like pthread_create/pthread_join in the main program. If it wanted to optimize a global variable it would have to see a the function call in the main program. Read the function and see that it has a loop. And then maybe optimize it. Since all these things are hidden from the main program with a function call the compiler won't make any optimization.
    It could make optimizations, but it would first have to know that it deals with threads. In that case it wouldn't put global variables in registers, since that might cause deadlocks.
    Try it with a code if you want. But personally it seems strange to me for the compiler to make the above wrong optimization.

    Note that the difference with I/O devices, and the necesity of volatile, is that they appear in the program as memory locations! If you read the program that is what you will understand if you didn't know anything more. Reading a program with threads you would understand that there is a function pthread_create/pthread_join that does something. You wouldn't assume it creates thread. Seeing it with the "compiler eyes" if you know what I mean...
    Last edited by C_ntua; 07-17-2008 at 05:08 AM.

  8. #8
    Alessio Stella
    Join Date
    May 2008
    Location
    Italy, Bologna
    Posts
    251
    thanks for the hints on volatile

    i understand
    i am not saying the compiler is likely to do it
    i am just saying some compilers might do it under high optim. precomp. directives

    pthread_mutex_lock/unlock are part of the POSIX standard so i think a compiler might make assumptions based on that. You can have a look at thsi link suggested in another thread by another member of thsi forum: http://www.opengroup.org/onlinepubs/...html#tag_04_10

  9. #9
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> Is it garaunteed that between pthread_mutex_lock()/unlock() any variable access is not done via cache but is always updated by memory?
    >> I am more interested to know in detail what happens with the second correction
    Quote Originally Posted by Codeplug
    http://cboard.cprogramming.com/showp...5&postcount=23
    Put it this way - if your system doesn't abide by 4.10, then it isn't a Posix compliant system

    In practice, compilers just don't hoist variables into registers across opaque function calls - because it's too difficult to guarantee that the opaque function will not have some side-effect on the variable.
    Modern compilers have to take multi-threading into account - which means there are other potential "side-effects" to consider which are outside the realm of the C and C++ standard (today anyway).
    The same thing goes for any windows compiler with calls to Win32 synchronization primitives.

    gg

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by mynickmynick View Post
    pthread_mutex_lock/unlock are part of the POSIX standard so i think a compiler might make assumptions based on that. You can have a look at thsi link suggested in another thread by another member of thsi forum: http://www.opengroup.org/onlinepubs/...html#tag_04_10
    I very much doubt that the compiler knows anything about pthread functions in themselves. They are just functions that the compiler understands how to call - the compiler deos not know what goes on inside the function, or that it has any particular purpose.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Post about correctness, necessity, and rules: http://cboard.cprogramming.com/showt...831#post772831

    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Turn Off Optimization?
    By danlee58 in forum C Programming
    Replies: 6
    Last Post: 12-10-2008, 03:52 AM
  2. MSDN volatile sample
    By George2 in forum C++ Programming
    Replies: 38
    Last Post: 01-05-2008, 06:59 AM
  3. added start menu crashes game
    By avgprogamerjoe in forum Game Programming
    Replies: 6
    Last Post: 08-29-2007, 01:30 PM
  4. Replies: 16
    Last Post: 10-29-2006, 05:04 AM
  5. OpenScript2.0 Compiler
    By jverkoey in forum C++ Programming
    Replies: 3
    Last Post: 10-30-2003, 01:52 PM