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" <[EMAIL PROTECTED]>
To: "FPC developers' list" <fpc-devel@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" <[EMAIL PROTECTED]>
To: "FPC developers' list" <fpc-devel@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@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
