Multi threading support was Re:[fpc-devel]Russianlocale information not compatiblewithFPClocale variables

[Boian Mitov]

Here is example of just simple linear chain:

A -> B -> C ->D

In this case there are no even any splits or merges, and yet the problems 
become obvious.

A can start sending data to B
and D can start sending let say clock events to C

Each component has to run in a separated thread as A may be capturing data 
from a device or receiving it from the web and unzipping it. B may be 
filtering the dada, C maybe performing 2D or 3D graphic transformation, and 
D maybe is compressing and storing the data in a file. Obviously you need 
them to run on separated cores if possible, and be locked the minimal amount 
of time.

Our granularity mechanism is a to lock the A component when changing data in 
it, then unlock it and lock the connection A->B send the data to B then 
unlock the connection and lock B to deliver the data to it and unlock it 
immediately and it continues.
This way each thread own only one lock at the time and eliminates the 
deadlock danger.
Otherwise deadlocks are inevitable :-( .

Our previous design was to have a master lock we ware obtaining then tracing 
and locking the chain we ware to deliver to, then unlocking the master lock 
and delivering trough the chain and then unlocking it in left to right 
fashion. Obviously a sick design born from a sick mind (i.e. mine ;-) ), 
hopefully at some point I figured I am insane, and obvious improvement :-D .

As you can see there are obvious scenarios where the granularity approach 
seems to be the only reasonable one.

  With best regards,
    Boian Mitov

--------------------------------------------------------------------
Mitov Software
http://www.mitov.com
--------------------------------------------------------------------


----- Original Message ----- 
From: "Boian Mitov" <mitov at mitov.com>
To: "FPC developers' list" <fpc-devel at lists.freepascal.org>
Sent: Friday, August 01, 2008 12:00 AM
Subject: Re: Multi threading support was Re:[fpc-devel]Russianlocale 
information not compatiblewithFPClocale variables


>    Hi Helmut,
>
> This is great for relatively simple system with number of shared objects.
> In our case we have a graph of up to hundreds of objects and not all of 
> them are connected (i.e. there are multiple independent graphs). The 
> connections can be changed while the graphs are working, and all 
> components can send data in any direction. and we need the components to 
> do their job in separated threads. I have experimented with multiple 
> approaches over the last 5 years, all the way up to this year we used a 
> relatively small number of locks based on the chains in the graph. It 
> never worked well until we finally switched to full granularity 3 months 
> ago. For first time we see an very high throughput, and no deadlocks :-) . 
> Simple strategies are great, and what you describe is what we usually do 
> in relatively simple applications with limited threads and shared 
> resources, but it is not universal solution, and unfortunately is not 
> always applicable. Other solutions need to exist, to solve different 
> scenarios.
>
>  With best regards,
>    Boian Mitov
>
> --------------------------------------------------------------------
> Mitov Software
> http://www.mitov.com
> --------------------------------------------------------------------
>
>
> ----- Original Message ----- 
> From: "Helmut Hartl" <helmut.hartl at firmos.at>
> To: "FPC developers' list" <fpc-devel at lists.freepascal.org>
> Sent: Thursday, July 31, 2008 11:06 PM
> Subject: RE: Multi threading support was Re: [fpc-devel]Russianlocale 
> information not compatible withFPClocale variables
>
>
> Just some additional testing info and things to think about.
>
> *) Performance of non granular locks is poor.
> *) Creating 50K+ of lock instances makes the OS behave strange,
> so to fine granualer does not help either :-)
>
> Simplest working Deadlock Avoidance strategys is:
>
> Lock all resources at the same time in the same order.
>
> Thread x
> LOCK A
>  LOCK B
>   LOCK C
> ... Work ....
>   UNLOCK C
>  UNLOCK B
> UNLOCK A
>
> Thread x
> LOCK B
>  LOCK C
>   ... Work ...
>  UNLOCK C
> UNLOCK B
>
> This way deadlocks are impossible.
>
> As this is sometimes not possible - we use deadlock detection in our
> software.
> (as classical database servers are doing it :-))
>
> I describe it brief:
>
> Everytime we lock in a thread we post a event to an non-blocking queue
> (Michael&Scott),
> similar on unlocking. The MS Queue is fast and does not block. At the
> other side we
> Detect the deadlocks by time (like a asynchrounous logger).
> All our Locked operations are designed to take a small amount of
> time (say some milliseconds). When we detect a nonpairing timedifference
> of say one second, we found the deadlock and have to correct the code.
>
> This is a debugging tool, wich does not save design time. But saves huge
> amount of time
> searching for deadlocks.
>
> IMHO a full graph-theoretic cyclic redundancy check would be to much
> waste of time - inefficient.
>
> Another aproach would be STM. (software transactional memory).
>
> For theory about locks:
>
> Hector Garcia Molina, j.Ullman, J. Widom / DATABASE Systems the complete
> Book.
>
> Or hardcore: http://www.cs.rochester.edu/~scott/
>
> Greets,
>
> helmut
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> http://lists.freepascal.org/mailman/listinfo/fpc-devel
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> http://lists.freepascal.org/mailman/listinfo/fpc-devel