Synchronization Strategies

Problem definition:

Multithreaded programming is difficult; more so than many other aspects of programming.


Strategies for effective synchronized programming

From SunirShah's work term report 2 (cf. note on his name page)

From PaulMcKenney's "Parallel Patterns for Synchronization on Shared-Memory Multiprocessors" available at http://c2.com/ppr/mutex/mutexpat.html

Other


Ways to keep a data structure in shared memory in a consistent state, even when multiple threads try to update it

There are many techniques for guaranteeing that readers will see a consistent state for that data structure.

summarizing and quoting from "Obstruction-Free Synchronization: Double-Ended Queues as an Example" Maurice Herlihy, Victor Luchangco, Mark Moir http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf

(EditHint: do we have 4 pages for the above 4 "types" of synchronization ?)


Synchronization usually requires GlobalConsensus.

(2004-05-17: moved text to GlobalConsensus)


See also ExtremeProgrammingChallengeFourteen, RaceCondition, DeadLock

This is all very well and good for threads, but does anyone have good ideas for NetworkSynchronization??

SendReceiveReply. A network connection is a kind of well-synchronised message queue anyway...

Some of the ideas at WaitFreeSynchronization seem relevant.


On a multiprocessor system, there are only 3 ways to design a subroutine intended to modify an object in shared memory (right ?):


(moved from CodeLocking -- I'm pretty sure this is *not* an example of CodeLocking. What kind of synchronization is this ? Move it to the relevant page.)

(Is WaitFreeSynchronization the right place for this ?)

We have the problem that we're writing in a language with no internal locking constructs - C. We have objects that can be in multiple linked lists, and occasionally have to be removed from all the linked lists, and then the object itself needs to be removed. What pattern can we use for this reasonably common(?) problem? In a bit more detail, what we are working on is an IrcServer?, there is a mapping of channels a user is on, and users on a channel both pointing to a struct which contains the information about that user on that channel. Now we might have looked up the user by "users on this channel" if for instance the user was booted from the channel, or we might have looked up "channels this user is on" if for example the user has quit. How can we remove the object from both linked lists without DeadLocking? -- PerryLorier

Now all your operations are either no-ops or single-writes and therefore atomic. Unless I haven't understood your problem, which is possible.

MichaelWill?: C has no internal locking constructs but you can use the pthreads library which offers semaphores, mutexes etc.


http://en.wikipedia.org/wiki/Double_checked_locking_pattern


CategoryConcurrency CategoryConcurrencyPatterns

EditText of this page (last edited January 26, 2009) or FindPage with title or text search