Thread: threads and synchronization

  1. #1
    Registered User Drogin's Avatar
    Join Date
    Oct 2005
    Location
    Norway
    Posts
    105

    threads and synchronization

    Hi everyone.

    Let's say I am to make my own mutex, lets call it lock / unlock.
    Then have the following code:
    (And please, this is only a very c-looking pseudo-code. Don't bother saying how the code is or what the point of it is. Its just an example in pseudo-code. No smart ass comments, please.)
    Code:
    struct lock_l l; // Lock
    int global; // Global
    
    thread1() {
    
      // Do some local non-essential work
    
      // Enter mutex
      lock(&l);
      global = 0;
      unlock(&l);
    
      // Do some local non essential work.
    }
    
    thread2() {
      lock(&l); 
      // Do something with global
      unlock(&l);
    }

    So, thread 1 just sets global to 0.
    Thread 2 do some very important calculation on this variable.

    Now , what prevents the compiler-optimizer from changing thread1 to this, moving global = 0; outside the lock. :
    Code:
    thread1() {
      global = 0;
      // Enter mutex
      lock(&l);
      unlock(&l);
    }
    Is this what memory barriers instructions are for? Or this those only for hardware reordering?
    How can I be 100% sure the opitimizer will NOT move statements in between my 2 self made mutex-functions, outside them?
    Last edited by Drogin; 09-26-2010 at 08:00 AM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    No smart ass comments, please.)
    I agree! The dumb ass comments are WAAY funnier!

  3. #3
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    Drogin,

    According to Paul S. Wang, on page 46, "The computational steps in a function are expressed by a sequence of statements that perform in ways predefined by the language. The statements are executed one by one in the given order when the program runs." So for purposes of your question, no level of optimization will ever violate the order in which "...computational steps..." are given.

    The process of optimization is described by Wang as an optional phase that "...improves the efficiency of generated code for speed and compactness." I recall a discussion in operating system utilities about it once. The professor was contrasting the space required to literally unravel a C coded loop into a linear sequence in Assembly (space consuming, but relatively easy), and he mentioned how optimization would affect it. Rearranging the steps of an algorithm would be considered a different algorithm (assuming it accomplished anything that is).

    The "construct" that prevents the "...compiler-optimizer..." from transposing steps (statements) is that it would not be the algorithm it was initially supplied (it's specification/design document), although I can imagine some funnies from mis-handling machine executables by swapping around portions of a file -- exactly what some viruses do...in order to amend code to an existing program. Those involving command.com come to mind from the late nineteen eighties.

    What brings up the question? One of my mathematics professors would say that material can be found on page 2 of the preface...in reference to the assumptions/propositions which were being conveyed while introducing an idea which was a consequence on page 5 of chapter twenty-three. It didn't seem like it exceeded a PG-13 rating when I asked what brought it up lol....

    Best Regards,

    New Ink -- Henry
    Last edited by new_ink2001; 09-26-2010 at 08:53 AM. Reason: spelling and semantics
    Kept the text books....
    Went interdisciplinary after college....
    Still looking for a real job since 2005....

    During the interim, I may be reached at ELance, vWorker, FreeLancer, oDesk and WyzAnt.

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Sorry if it sounds like (or is) a smart ass comment, but why do you care at all about the order of this code:

    Code:
    lock(&l);
    global = 0;
    unlock(&l);
    and don't care about the order of, for example, this:

    Code:
    Initialize();
    if (global == 1)
    {
       ...
    }
    if (global == 5)
    {
       ...
    }
    Finalize();
    I'm sure there is a similar piece of code, hidden somewhere in your program.

  5. #5
    Registered User Drogin's Avatar
    Join Date
    Oct 2005
    Location
    Norway
    Posts
    105
    I might not have understood you correctly, but stick with me and see if this addresses your previous post:
    In this article:
    Volatile: Almost Useless for Multi-Threaded Programming – Intel Software Network Blogs

    There is an example where the GCC optimizer on -O2 does reordering of statements.
    Code:
        volatile int Ready;       
    
        int Message[100];      
    
        void foo( int i ) {      
    
            Message[i/10] = 42;      
    
            Ready = 1;      
    
        }
    It's trying to do something very reasonable in multi-threaded programming: write a message and then send it to another thread. The other thread will wait until Ready becomes non-zero and then read Message. Try compiling this with "gcc -O2 -S" using gcc 4.0, or icc. Both will do the store to Ready first, so it can be overlapped with the computation of i/10. The reordering is not a compiler bug. It's an aggressive optimizer doing its job.
    So if this is indeed the case, and ready =1, might be reordered to happen before message[i/10] = 42, then what prevents the compiler from reordering something in between 2 mutex-functions outside them?

    Is this what for instance the intel x86 memory fence instructions are for? Or do they only stop hardware reordering?
    Last edited by Drogin; 09-26-2010 at 09:15 AM.

  6. #6
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    It is all about the final effect. It does not matter whether you set Result to 1 first, or Message to 42 - the result is the same. Those instructions are not relevant to each other, and compiler knows about it.

    In the case of functions, it is a bit more complicated, because the compiler does not know what those functions do, and it would be dangerous for him to reorder them, because the function 'lock' could be a function that reads the value of 'global'.
    (I always might be wrong).

  7. #7
    Registered User Drogin's Avatar
    Join Date
    Oct 2005
    Location
    Norway
    Posts
    105
    Aha, so you are saying function-calls are natural compiler barriers that prevents compiler-optimization reordering?
    Last edited by Drogin; 09-26-2010 at 09:32 AM.

  8. #8
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    I don't know what the standard says about the order of statements, but since the environment is supposed to be single-threaded (???) everything may happen - compiler thinks it runs in a single thread, and you should expect the same results.

    The compiler could make a deep analysis upon the given function, inline it, reorder instructions, etc. But since you need platform dependent code for lock/unlock (inline assembly, external functions) you should be safe. Still, you should be careful.

    I might be wrong.

    Btw, I've seen a similar Lock/Set/Unlock code in Boost C++ Lib, so I would leave it as it is.

    Edit:
    If the compiler does not know what the function does (it's external), it should never change its order. Still, might reorder and mix instructions.
    Last edited by kmdv; 09-26-2010 at 09:47 AM.

  9. #9
    Registered User Drogin's Avatar
    Join Date
    Oct 2005
    Location
    Norway
    Posts
    105
    That is what I'm asking
    Is there something(like a memory fence instruction in x86) I can put inside the lock / unlock functions in my mutex, to prevent the compiler-optimizer from moving statements in the critical region outisde it?
    And is something like this even needed, or is function-calls alone natural compiler barriers/fences that prevents compiler-level reordering?


    I'm writing my own operating system, so using C++ libraries is out of the question
    And this is in the C - forum
    Last edited by Drogin; 09-26-2010 at 09:51 AM.

  10. #10
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    I know it's C, I just said I had seen a similar code in a wide-spread library which works properly.

    I don't know why the optimizer would care about the inline assembly, yet analyze its instructions. Inline assembly is usually not optimized at all. To be sure about the reordering, I would just make those functions external, to make the compiler know nothing about their code (you have probably already done it, if it is a bigger project).

  11. #11
    Registered User Drogin's Avatar
    Join Date
    Oct 2005
    Location
    Norway
    Posts
    105
    I think is is very close to what I was asking:

    * The GNU inline assembler statement
    Code:
    asm volatile("" ::: "memory");
    or even
    Code:
    __asm__ __volatile__ ("" ::: "memory");
    forbids GCC compiler to reorder read and write commands around it.
    So, I guess this must be included in lock() and unlock(), then I should be atleast safe from compiler reordering, yes?

  12. #12
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Sorry, I don't know the AT&T syntax so I will not help you.

    then I should be atleast safe from compiler reordering, yes?
    I think you can be safe even without it. Just make them external as I proposed in my previous post. I haven't met any function reordering when working with GCC (not to be confused with instruction reordering).

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Making an OS in C++ is not impossible. I'm just saying.
    Anyway, the current standards of C (and C++) says nothing of threading. Nonetheless, good compilers nowadays do tend to take multithreading into account.
    To make a lock, you really need to do some atomic reading/writing of a variable. Lock would increment the variable and unlock would decrement. But that's pretty much all I know of rolling out my own mutex.
    You really should look into an in-depth topic about the subject.

    External functions as in different source files will not work. Compiler optimizations will take of that.
    Putting them inside a DLL or some other form of pre-compiled code which the compiler cannot look into will make sure the compiler cannot reorder it.
    You should probably look into the multithreading world of memory barriers, atomic operations, etc. I don't know enough of the subject to help you unfortunately.
    Last edited by Elysia; 09-26-2010 at 12:32 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Definately, you can't make a (simple ofc) OS unless you have a good background of low level programming. Try to write your own bootsector, and do some basic output. And make it single threaded. Then, try to get deeper into multithreading, but at first, write some multithreaded applications on your own to get familiar with these. Too much to write.

  15. #15
    Registered User Drogin's Avatar
    Join Date
    Oct 2005
    Location
    Norway
    Posts
    105
    I know of the atomic setting and checking of a variable, ususally done with xchng instruction on X86, and basic mutex theory and usage.

    What I was wondering of, was how to avoid compiler level reordering.
    I too belive simply calling an external function will not work.
    It might work on a specific optimization level, but I belive some optimizers, especially when given the right flags, can peak through even external functions to determine optimization.
    If this happens, I would be in the ........ again.

    However, I checked out the linux kernel source code, and found this:
    Code:
     static inline void barrier(void)
      {
             asm volatile("" : : : "memory");
     }
    Which is exactly what I want - Make the compiler think this code is UNKNOWN, no matter what, thus creating a compiler barrier.

    Edit: I have already made a working bootloader. And a scheduler, context switch, and working on locks now..
    Last edited by Drogin; 09-26-2010 at 01:08 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need Help: Multi-threading and Synchronization
    By Anom in forum C Programming
    Replies: 7
    Last Post: 12-08-2009, 05:34 PM
  2. Synchronization Question
    By CyrexCore2k in forum C Programming
    Replies: 4
    Last Post: 05-01-2008, 02:51 AM
  3. using this as synchronization object
    By George2 in forum C# Programming
    Replies: 0
    Last Post: 03-22-2008, 07:49 AM
  4. Replies: 0
    Last Post: 10-06-2007, 01:25 PM
  5. Thread synchronization Assignment help!!
    By rossi143 in forum C Programming
    Replies: 2
    Last Post: 03-25-2007, 07:07 AM