Writing deadlock proof code


  • 0
    B

    How do you write code that is sure not to run into deadlock condition?


  • 2
    C

    in this order:
    1) by not using any semaphores or mutexes (synchronization primitives) if not really required
    this sounds crazy, but many concurrent programs do not require concurrency, it's simply done because of convenience or a lack of knowledge about alternatives. For example, a simple file serving HTTP server can be implemented with overlapping I/O which is in many cases more effective and simpler to use. That said, if you start bringing caches and server side scripts into play, things are of different nature.

    Further there are lock less concepts for many low level buffers, for example if you need to communicate with hardware. How ever, lock less is very hard to get right in C, C++, due to instruction reordering, memory model (caches) in multi core applications etc...

    2) or by not using multiple synchronization primitives
    if one semaphore or one critical section is enough, that should be the way to go.

    3) or by not acquiring synchronization primitives in a nested manner
    avoid

    a.lock()
    b.lock()
    b.unlock()
    a.unlock()
    

    note, this sometimes happens in a nested call graph, so, it's not always easy to detect, so discipline and static code analysis are really helping here.

    4) or by nesting synchronization primitives but only acquiring them in the same order

    void doA() {
    a.lock()
    b.lock()
    ...
    }
    
    void doB() {
    b.lock()
    a.lock()
    ...
    }
    

    doB should aquire in the same order as doA

    a.lock()
    b.lock()
    

    and free them in the opposite order as they were acquired

    or by some algorithm that detects dead locks and sets one party back (as for example relational databases do)
    they basically build allocation graphs and detect cycles as such cycles are dead locks:
    e.g.
    Thread A want's a and has b, Thread B want's b and has a, A<-b, B<-a, A->a, B->b ==> A->a->B->b->A (cycle)

    an alternative would be to have such a Mutex manager in place and ask before locking if a required lock would create a cycle and only lock if that isn't the case... what to do if it would create a lock... etc. etc. etc.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.