• About deadlocks and race conditions in parallel programming..

    From Wisdom90@21:1/5 to All on Mon Feb 3 16:57:48 2020
    Hello...


    About deadlocks and race conditions in parallel programming..

    I have just read the following paper:

    Deadlock Avoidance in Parallel Programs with Futures

    https://cogumbreiro.github.io/assets/cogumbreiro-gorn.pdf

    So as you are noticing you can have deadlocks in parallel programming
    by introducing circular dependencies among tasks waiting on future
    values or you can have deadlocks by introducing circular dependencies
    among tasks waiting on windows event objects or such synchronisation
    objects, so you have to have a general tool that detects deadlocks,
    but if you are noticing that the tool called Valgrind for C++
    can detect deadlocks only happening from Pthread locks , read
    the following to notice it:

    http://valgrind.org/docs/manual/hg-manual.html#hg-manual.lock-orders

    So this is not good, so you have to have a general way that permits
    to detect deadlocks on locks , mutexes, and deadlocks from introducing
    circular dependencies among tasks waiting on future values or deadlocks
    you may have deadlocks by introducing circular dependencies among tasks
    waiting on windows event objects or such synchronisation objects etc.
    this is why i have talked before about this general way that detects
    deadlocks, and here it is, read my following thoughts:

    Yet more precision about the invariants of a system..

    I was just thinking about Petri nets , and i have studied more
    Petri nets, they are useful for parallel programming, and
    what i have noticed by studying them, is that there is two methods
    to prove that there is no deadlock in the system, there is the
    structural analysis with place invariants that you have to
    mathematically find, or you can use the reachability tree, but we have
    to notice that the structural analysis of Petri nets learns you more,
    because it permits you to prove that there is no deadlock in the system,
    and the place invariants are mathematically calculated by the following
    system of the given Petri net:

    Transpose(vector) * Incidence matrix = 0

    So you apply the Gaussian Elimination or the Farkas algorithm to
    the incidence matrix to find the Place invariants, and as you will
    notice those place invariants calculations of the Petri nets look
    like Markov chains in mathematics, with there vector of probabilities
    and there transition matrix of probabilities, and you can, using
    Markov chains mathematically calculate where the vector of probabilities
    will "stabilize", and it gives you a very important information, and
    you can do it by solving the following mathematical system:

    Unknown vector1 of probabilities * transition matrix of probabilities =
    Unknown vector1 of probabilities.

    Solving this system of equations is very important in economics and
    other fields, and you can notice that it is like calculating the
    invariants , because the invariant in the system above is the
    vector1 of probabilities that is obtained, and this invariant,
    like in the invariants of the structural analysis of Petri nets,
    gives you a very important information about the system, like where
    market shares will stabilize that is calculated this way in economics.

    About reachability analysis of a Petri net..

    As you have noticed in my Petri nets tutorial example (read below),
    i am analysing the liveness of the Petri net, because there is a rule
    that says:

    If a Petri net is live, that means that it is deadlock-free.

    Because reachability analysis of a Petri net with Tina
    gives you the necessary information about boundedness and liveness
    of the Petri net. So if it gives you that the Petri net is "live" , so
    there is no deadlock in it.

    Tina and Partial order reduction techniques..

    With the advancement of computer technology, highly concurrent systems
    are being developed. The verification of such systems is a challenging
    task, as their state space grows exponentially with the number of
    processes. Partial order reduction is an effective technique to address
    this problem. It relies on the observation that the effect of executing transitions concurrently is often independent of their ordering.

    Tina is using “partial-order” reduction techniques aimed at preventing combinatorial explosion, Read more here to notice it:

    http://projects.laas.fr/tina/papers/qest06.pdf

    About modelizations and detection of race conditions and deadlocks
    in parallel programming..

    I have just taken further a look at the following project in Delphi
    called DelphiConcurrent by an engineer called Moualek Adlene from France:

    https://github.com/moualek-adlene/DelphiConcurrent/blob/master/DelphiConcurrent.pas

    And i have just taken a look at the following webpage of Dr Dobb's journal:

    Detecting Deadlocks in C++ Using a Locks Monitor

    https://www.drdobbs.com/detecting-deadlocks-in-c-using-a-locks-m/184416644

    And i think that both of them are using technics that are not as good
    as analysing deadlocks with Petri Nets in parallel applications ,
    for example the above two methods are only addressing locks or mutexes
    or reader-writer locks , but they are not addressing semaphores
    or event objects and such other synchronization objects, so they
    are not good, this is why i have written a tutorial that shows my
    methodology of analysing and detecting deadlocks in parallel
    applications with Petri Nets, my methodology is more sophisticated
    because it is a generalization and it modelizes with Petri Nets the
    broader range of synchronization objects, and in my tutorial i will add
    soon other synchronization objects, you have to look at it, here it is:

    https://sites.google.com/site/scalable68/how-to-analyse-parallel-applications-with-petri-nets

    You have to get the powerful Tina software to run my Petri Net examples
    inside my tutorial, here is the powerful Tina software:

    http://projects.laas.fr/tina/

    Also to detect race conditions in parallel programming you have to take
    a look at the following new tutorial that uses the powerful Spin tool:

    https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html

    This is how you will get much more professional at detecting deadlocks
    and race conditions in parallel programming.


    Thank you,
    Amine Moulay Ramdane.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)