Concurrent programming question

Coders forum. Discuss techniques, swap code snippets, ask for help etc. relating to all forms of software development.
Post Reply
User avatar
_TinOmen_
Baaaa!
Baaaa!
Posts: 745
Joined: Wed Feb 12, 2003 10:52 pm 0
Location: Stockholm, Sweden
Contact:

Concurrent programming question

Post by _TinOmen_ »

I haven't been using many threads in my programs until now.

So being a newbie, I wonder is this statement correct:

In concurrent programming, every access (read or write) to shared memory absolutely must be guarded with a mutex (or a similar mechanism)?

If it's too complex to explain, then feel free to just reply with a amazon-link to a book I should read :)
User avatar
the2bears
Baaaaaa!
Baaaaaa!
Posts: 3686
Joined: Wed Oct 27, 2004 9:30 pm 0
Location: The City by the Bay
Contact:

Post by the2bears »

The short answer is "no", every access need not. But as you suspect, it's a more complex answer depending on what you're trying to accomplish, what the needs of the moment are.

Java Thread Programming is the best book I've read on concurrent programming *in general*, with obvious examples and ideas specific to Java.

Bill
the2bears - the indie shmup blog
User avatar
Jimaroid
Baaaaaaa!
Baaaaaaa!
Posts: 5146
Joined: Fri May 09, 2003 12:21 pm 0
Location: Dundee

Post by Jimaroid »

Nope. Ask yourself this, if that statement were true, how would you implement a mutex? At some level, the mutex needs some shared data representing its state. So do you mutex your mutex? No because that would be infinitely recurring madness...

Think about the atomicity of data. In very rough terms you need to synchronise access to shared data if it is subject to modification by more than one operation. A single shared boolean value requires no synchronisation, to read and write it is a single atomic operation. You will always read the correct value at a single point in time. E.g., you can only read a 1 or 0, there is no inbetween.

Synchronisation is required when the data in question is subject to change at some point in time between the start and end of its access. E.g., a string. A string is a collection of atomic values and it's safe for two threads to both access a single (byte) character at the "same" time, however, the danger here is that the string as a whole is modified over a period of time by many operations. So how can you be sure you're reading the string without it being modified underneath you? That's where synchronisation is required.

From this point it gets trickier to explain without a few thousand more words. Unfortunately, I can't remember what books I used to rely on so I hope I've been of some help.
User avatar
_TinOmen_
Baaaa!
Baaaa!
Posts: 745
Joined: Wed Feb 12, 2003 10:52 pm 0
Location: Stockholm, Sweden
Contact:

Post by _TinOmen_ »

jimaroid: Aha. Thanks for that explaination.

So if I change my original statement to mean "non-atomic access to data" the statement will be true?
Or that over-simplifying again :)

the2bears: Thanks, I will take a look at that book. I'm working with Pascal and C, but I'm sure the general concepts are the same in Java.
Last edited by _TinOmen_ on Mon May 15, 2006 7:30 pm 0, edited 1 time in total.
Will
Baaa!
Baaa!
Posts: 115
Joined: Fri Nov 28, 2003 1:20 pm 0

Post by Will »

I'm no expert, but I disagree.

In the case of a multiprocessor system, you must ensure that you are reading the most up to date value, which may be lurking in a write cache on another processor. So you still need aquire a lock to ensure correct memory visibility between processors.

comp.programming.threads is a great resource for this kind of question.
User avatar
Jimaroid
Baaaaaaa!
Baaaaaaa!
Posts: 5146
Joined: Fri May 09, 2003 12:21 pm 0
Location: Dundee

Post by Jimaroid »

Pretty much true, although your "or a similar mechanism" is a very wide and encompassing clause.

The reason for that being synchronisation objects are not the only way to control the processing of shared data. Mutexes can in fact be a very inefficient way of controlling access to data because threads effectively have to spin in a tight loop waiting for something to change - a waste of processing time. On single CPU systems this isn't too big a deal because threads can't really "idle busy" but when you start thinking about real concurrent multi-cpu systems you'll find that synchronisation objects like mutexes can be pretty evil little things. That's when you have to start looking at data pipelining or queuing to keep everything ticking along efficiently.

But I'm rambling. :)

Edit: Will, good point but thats where things go outside the realm of atomic operations and get super complicated really quickly. I was aiming for theory more than technicality in this case.
User avatar
_TinOmen_
Baaaa!
Baaaa!
Posts: 745
Joined: Wed Feb 12, 2003 10:52 pm 0
Location: Stockholm, Sweden
Contact:

Post by _TinOmen_ »

This book seems interesting:

"Multi-Core Programming"

Published by Intel and out in June.
User avatar
tufty
Sheepie Whore
Sheepie Whore
Posts: 12524
Joined: Fri Jan 07, 2005 4:52 pm 0
Location: French Alps

Post by tufty »

Jimaroid wrote:At some level, the mutex needs some shared data representing its state. So do you mutex your mutex? No because that would be infinitely recurring madness...
I thought most, if not all, mutex implementations used operations that guarantee he atomicness of the set / unset.

See `man atomic` and, for example, the implementation of include/atomic.h in the freebsd source for your platform of choice, eg http://fxr.watson.org/fxr/source/sparc6 ... e/atomic.h

from freebsd 6 "man atomic"

Code: Select all

     /* Try to obtain mtx_lock once. */
     #define _obtain_lock(mp, tid)                                           \
             atomic_cmpset_acq_ptr(&(mp)->mtx_lock, MTX_UNOWNED, (tid))

     /* Get a sleep lock, deal with recursion inline. */
     #define _get_sleep_lock(mp, tid, opts, file, line) do {                 \
             uintptr_t _tid = (uintptr_t)(tid);                              \
                                                                             \
             if (!_obtain_lock(mp, tid)) {                                   \
                     if (((mp)->mtx_lock & MTX_FLAGMASK) != _tid)            \
                             _mtx_lock_sleep((mp), _tid, (opts), (file), (line));\
                     else {                                                  \
                             atomic_set_ptr(&(mp)->mtx_lock, MTX_RECURSE);   \
                             (mp)->mtx_recurse++;                            \
                     }                                                       \
             }                                                               \
     } while (0)


I believe linux uses atomic_dec_and_test() and atomic_inc_and_test() to implement mutex locking and unlocking, but it's been a while since I delved into the linux source. OSX uses OSAtomicTestAndSetBarrier and OSAtomicTestAndClearBarrier, IIRC

Simon
Last edited by tufty on Tue May 16, 2006 1:05 pm 0, edited 1 time in total.
"massive retard™", "full of shit™", "tiny bitch™", "retarted™", "a bit of a one trick pony™", "petty™", "simple minded idealistic twat™", "miserable humourless fucker™"
User avatar
Jimaroid
Baaaaaaa!
Baaaaaaa!
Posts: 5146
Joined: Fri May 09, 2003 12:21 pm 0
Location: Dundee

Post by Jimaroid »

tufty wrote:
Jimaroid wrote:At some level, the mutex needs some shared data representing its state. So do you mutex your mutex? No because that would be infinitely recurring madness...
I thought most, if not all, mutex implementations used operations that guarantee he atomicness of the set / unset.
Err, eh? I think you missed my point.
User avatar
tufty
Sheepie Whore
Sheepie Whore
Posts: 12524
Joined: Fri Jan 07, 2005 4:52 pm 0
Location: French Alps

Post by tufty »

Jimaroid wrote:
tufty wrote:
Jimaroid wrote:At some level, the mutex needs some shared data representing its state. So do you mutex your mutex? No because that would be infinitely recurring madness...
I thought most, if not all, mutex implementations used operations that guarantee he atomicness of the set / unset.
Err, eh? I think you missed my point.
D'oh! Yes, I think I did.

Ignore me, I'll go back to lurking...

Simon
"massive retard™", "full of shit™", "tiny bitch™", "retarted™", "a bit of a one trick pony™", "petty™", "simple minded idealistic twat™", "miserable humourless fucker™"
Post Reply