Prev: solutions manual
Next: Parma Polyhedra Library 0.11
From: Srinu on 4 Aug 2010 09:43
Dear All,

I was looking into multiprogramming. After some studies, I thought of
a simple template for designing multiprogram code.

Many times in multiprogramming, we need to use mutex. generally we
choose critical section in our code which if left unprotected, may
give erroneous results because of race condition. Now question is
which piece of my code is critical? In some machines, simultaneous
read to a memory location is not a problem but write is. In some
machines, simultaneous read is also a problem. This suggests that
keeping all these into consideration, we need to choose our critical
section. I was in search for a simple method to choose my critical
sections.

After reading Hoare's paper (C. A. R. Hoare, Towards a Theory of
Parallel Programming, 1971), where he has advocated to use "with r do
C" and "with r when B do C", I thought

"Where ever a shared memory location is being accessed (either read or
write), protect it by mutex" -- this is my critical section.

The above idea, if taken as a template, I can easily choose my
critical section "Where ever a shared memory location is being
accessed" and protect it with mutex. I hope in this case, my
multiprogram will be error free.

Will this wok in all cases? Is there any problem with this approach or
disadvantages?

Sincerely,
Srinivas Nayak
From: Tim Little on 4 Aug 2010 21:30
On 2010-08-04, Srinu <sinu.nayak2001(a)gmail.com> wrote:
> "Where ever a shared memory location is being accessed (either read
> or write), protect it by mutex" -- this is my critical section.

This interacts extremely poorly with the typical threaded programming
model in which almost every memory location is shared with other
threads. It would not be practical to protect every access to every
such memory location with a mutex. It may not even be sufficient, for
example with an update operation that involves two (or more) accesses,
both accesses must usually be part of the same critical section and
not two separate sections.

In practice, a programmer must determine which of the theoretically
shared memory locations (i.e. nearly all of them) are actually
contended given the design, and protect those in a manner that ensures
correctness. Usually the programming environment will provide some
multiprogramming primitives to help with this. In general though, a
mutex is just one of a number of low-level primitives, and not always
the most suitable for every task.


- Tim
From: Srinu on 5 Aug 2010 01:35
Dear Tim,

I agree with your comment. Theoretically correct.

In many cases with threading, we generally share a few variables among
threads for a task, though in principle they are free to share the
whole address space. As you said it is true that we must protect only
these contended variables. By saying "every access", I mean "wherever
there is a read operation or write operation (using high level
programming language construct)". You are correct in saying that...it
is unwise to protect all of the low level access/update operations on
the memory location.

And one more important thing is that, --I forgot to mention-- we need
to maintain the system Invariant as well. I mean whenever there are
two shared variables and there values are dependent on each other,
then update/access of both of them shall be in one critical section.

Once we keep this thing in mind, I think my template will work...what
you think? I was fearing if my critical sections will be too coarse
grained.

Sincerely,
Srinivas Nayak
From: Tim Little on 6 Aug 2010 22:27
On 2010-08-05, Srinu <sinu.nayak2001(a)gmail.com> wrote:
> Once we keep this thing in mind, I think my template will
> work...what you think? I was fearing if my critical sections will be
> too coarse grained.

Coarse graining is more usually a performance consideration than a
correctness one, and like any performance consideration should usually
be addressed after correctness is established. Then again, if
performance weren't a major consideration you would likely not be
using shared-memory multiprogramming at all.

Like most performance issues, it frequently depends upon details of
implementation.


- Tim
 | 
Pages: 1
Prev: solutions manual
Next: Parma Polyhedra Library 0.11