Very Computer

I'd like to hear some of the threads community's thoughts on implementing
robust mutexes in shared memory.  I've read Dave's comments in the FAQ (Q88)
http://www.lambdacs.com/FAQ.html#Q88
but I don't want to give up on this problem (he says it's "impossible").
I'm not proposing a solution (I don't have one), but I would like to put
forth some thoughts on the problem in hopes someone else may have a
solution.

I believe I've solved the problem of initialization, the possibility that
multiple processes could initialize the shared memory segment
simultaneously, by using open(2) with O_CREAT and O_EXCL.  The process that
creates the shared memory file initializes the mutex within; no one else
ever does.

The main issue I'm concerned with, though, is the possibility that a process
could die while holding a mutex lock.  Dave says you'd have to write your
own implementation of a read lock to allow a third party process to monitor
processes claiming to have the lock.  But at the end of the day, you're
going to have to  use a pthread primitive somewhere.  So the question is,
how do you unlock a mutex when the process that locked it dies with it
locked?  Overwrite it with zeros?

Maybe you could use a semaphore with a maximum count of one.  It would seem
those are easier to steal.  Once a determination was made that the owner
process is no longer around (see below), then the babysitter process or
thread making this determination could decrement the semaphore on the
deceased's behalf.

Then there's the issue of determining whether a process claiming ownership
of the lock really has it. This one is tough.  To get anywhere, you'd at
least nead a PID that you can try to kill(2) with "0" to test its process'
existence, but how do you protect the four bytes of PID from being read
while they were in the process of being written?  And what happens if the
process dies after it gets the lock, but before it writes its PID there?
Then, if you could "kill" the other process, how can you be sure it's not
someone's shell or something that happened to reuse the same PID as the
process which may have died a month ago?

I'm going to do some investigation into all the things in Unix that are
totally fail-safe and try to combine them in such a way as to provide robust
shared mutexes.  For instance, a record lock on a file will _always_ be
removed when the locking process dies.  That's the sort of thing I'm looking
for ways to take advantage of.

Any ideas?

john

Quote:>I'd like to hear some of the threads community's thoughts on implementing
>robust mutexes in shared memory.

Personally, I think you're going to run out of luck trying
to add tollerance to process crashing when pthreads were
not designed with this in mind.

Also, you might consider a complete change of tack - e.g.
perhaps instead of sharing data, you could have a
server process which handled that, and all the other
processes (clients) access the data only by some form of
IPC with the server. The server could then tidy-up if
a client dies, and perhaps the clients could be tollerent
of restarting the server if it dies? Depends on amount
of data, frequency of access, etc...

--
Andrew Gabriel
Consultant Software Engineer

|> I'd like to hear some of the threads community's thoughts on implementing
|> robust mutexes in shared memory.  I've read Dave's comments in the FAQ (Q88)
|> http://www.lambdacs.com/FAQ.html#Q88
|> but I don't want to give up on this problem (he says it's "impossible").
|> I'm not proposing a solution (I don't have one), but I would like to put
|> forth some thoughts on the problem in hopes someone else may have a
|> solution.
|>
|> I believe I've solved the problem of initialization, the possibility that
|> multiple processes could initialize the shared memory segment
|> simultaneously, by using open(2) with O_CREAT and O_EXCL.  The process that
|> creates the shared memory file initializes the mutex within; no one else
|> ever does.
|>
|> The main issue I'm concerned with, though, is the possibility that a process
|> could die while holding a mutex lock.  Dave says you'd have to write your
|> own implementation of a read lock to allow a third party process to monitor
|> processes claiming to have the lock.  But at the end of the day, you're
|> going to have to  use a pthread primitive somewhere.  So the question is,
|> how do you unlock a mutex when the process that locked it dies with it
|> locked?  Overwrite it with zeros?
|>
|> Maybe you could use a semaphore with a maximum count of one.  It would seem
|> those are easier to steal.  Once a determination was made that the owner
|> process is no longer around (see below), then the babysitter process or
|> thread making this determination could decrement the semaphore on the
|> deceased's behalf.
|>
|> Then there's the issue of determining whether a process claiming ownership
|> of the lock really has it. This one is tough.  To get anywhere, you'd at
|> least nead a PID that you can try to kill(2) with "0" to test its process'
|> existence, but how do you protect the four bytes of PID from being read
|> while they were in the process of being written?  And what happens if the
|> process dies after it gets the lock, but before it writes its PID there?
|> Then, if you could "kill" the other process, how can you be sure it's not
|> someone's shell or something that happened to reuse the same PID as the
|> process which may have died a month ago?
|>
|> I'm going to do some investigation into all the things in Unix that are
|> totally fail-safe and try to combine them in such a way as to provide robust
|> shared mutexes.  For instance, a record lock on a file will _always_ be
|> removed when the locking process dies.  That's the sort of thing I'm looking
|> for ways to take advantage of.
|>
|> Any ideas?
|>
|> john

If you're using processes (the original heavyweight threads) you could use
the following.  If a process dies while holding the exclusive lock, an
error is returned on subsequent lock requests.

Joe Seigh

#include <fcntl.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/mode.h>

int initialize(int *semid, char *path, char id) {
        key_t   key;
        unsigned short  val[3]={1, 0, 0};

        if ((key=ftok(path, id))<0)
                return -1;

        if ((*semid=semget(key, 3, IPC_CREAT|IPC_EXCL|S_IRUSR|S_IWUSR))>=0) {
                semctl(*semid, 0, SETALL, val);
        }
        else
                if (errno==EEXIST) {
                        if ((*semid=semget(key, 3, S_IRUSR|S_IWUSR))<0) {
                                return -1;
                        }
                }
                else {
                        return -1;
                }
        return 0;

Quote:}

Quote:}

Quote:}

Quote:}

Quote:}

Quote:}

j> I'd like to hear some of the threads community's thoughts on
j> implementing robust mutexes in shared memory.  I've read Dave's
j> comments in the FAQ (Q88) http://www.lambdacs.com/FAQ.html#Q88 but
j> I don't want to give up on this problem (he says it's
j> "impossible").

In brief, Dave is right, and you'll waste your time if you don't give
up now.  Sorry, but life is hard.

        <b

--
Let us pray:

Quote:> The main issue I'm concerned with, though, is the possibility that a process
> could die while holding a mutex lock.  Dave says you'd have to write your
> own implementation of a read lock to allow a third party process to monitor
> processes claiming to have the lock.  But at the end of the day, you're
> going to have to  use a pthread primitive somewhere.  So the question is,
> how do you unlock a mutex when the process that locked it dies with it
> locked?  Overwrite it with zeros?

Quote:> Maybe you could use a semaphore with a maximum count of one.  It would seem
> those are easier to steal.  Once a determination was made that the owner
> process is no longer around (see below), then the babysitter process or
> thread making this determination could decrement the semaphore on the
> deceased's behalf.

Quote:> Then there's the issue of determining whether a process claiming ownership
> of the lock really has it. This one is tough.  To get anywhere, you'd at
> least nead a PID that you can try to kill(2) with "0" to test its process'
> existence, but how do you protect the four bytes of PID from being read
> while they were in the process of being written?  And what happens if the
> process dies after it gets the lock, but before it writes its PID there?
> Then, if you could "kill" the other process, how can you be sure it's not
> someone's shell or something that happened to reuse the same PID as the
> process which may have died a month ago?

Quote:> I'm going to do some investigation into all the things in Unix that are
> totally fail-safe and try to combine them in such a way as to provide robust
> shared mutexes.  For instance, a record lock on a file will _always_ be
> removed when the locking process dies.  That's the sort of thing I'm looking
> for ways to take advantage of.

If what you want is "less than absolutely 100% guaranteed totally fail-safe",
then where's your dividing line? Maybe a mutex and shared memory is "good
enough", because the chances of one process blowing up with a mutex held are
"manageably low" in the context of immediate concern. Maybe your
semaphore/manager idea is "good enough". There's no one absolute answer for all
possible circumstances.

Quote:> Any ideas?

Seriously, if what you want is "reasonably fail-safe" communication between
parallel entities, forget about the performance advantages of shared memory and
mutexes. They're in a different world, and you can't live in both. Stick with
separate address spaces, and pass messages between them. You can validate the
messages, and ignore bad data. If one partner dies, you can detect that and
recover, with no chance of corruption to the surviving partners. (Unless, of
course, the partners are running the same code, in which case they have the
same bug just waiting for the right time to visit.)

/---------------------------[ Dave Butenhof ]--------------------------\

| 110 Spit Brook Rd ZKO2-3/Q18       http://members.aol.com/drbutenhof |
| Nashua NH 03062-2698  http://www.awl.com/cseng/titles/0-201-63392-2/ |
\-----------------[ Better Living Through Concurrency ]----------------/

Quote:Dave Butenhof writes:

People wanting to recover from dead threads sounds _so_ much like my
students wanting to catch an Assertion failure exception it's not funny.

:-(

Dale

Quote:> > Any ideas?

> Yeah. Give up. ;-)

> Seriously, if what you want is "reasonably fail-safe" communication between
> parallel entities, forget about the performance advantages of shared memory and
> mutexes. They're in a different world, and you can't live in both. Stick with
> separate address spaces, and pass messages between them. You can validate the
> messages, and ignore bad data. If one partner dies, you can detect that and
> recover, with no chance of corruption to the surviving partners. (Unless, of
> course, the partners are running the same code, in which case they have the
> same bug just waiting for the right time to visit.)

Does anyone have any ideas how a seperate address space implementation compares
with a shared memory implementation? Are we talking 10 or a 100 times slower? If
messages can be passed back and forth via shared memory (assume lost messages are
ok) wouldn't the big hit be context switches? On an MP machine this seems like no
big deal. Comments?

Regards,
Christopher Helck

: I'd like to hear some of the threads community's thoughts on implementing
: robust mutexes in shared memory.  
--- usw deleted --

Hey, you know alot of the concepts that you are visiting in are
already investigated and applied in transaction processing systems.
If you want a good discussion of locking and recovery in shared memory
regions, I'd highly recommend a peruse of this text.  You should own
this text anyways (!) since its a wonderful read with lots of pointers
to topics in the academic literature:

        Transaction Processing:   Concepts and Techniques
        Jim Gray / Andreas Reuter
        Morgan-Kauffman
        ISBN 1-55860-190-2

There are several implementations of recoverable shared memory that
you can go look at:

The BSD DB 2.0 toolkit    http://www.sleepycat.com

RVM (recoverable virtual memory) library,  used in the Coda filesystem.
        http://www.coda.cs.cmu.edu/

Neither of these implementations offer lock-state recovery on restart,
although you could implement that by simplying write-ahead logging
lock states to a separate journal and reply on application recovery.

Have fun!

-- Jim

--
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Jim Doyle                         Boston University   Information Technology

                                                      tel. (617)-353-8248
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-++--+-+-+-+-+-+-

c> Does anyone have any ideas how a seperate address space
c> implementation compares with a shared memory implementation?

This isn't a terribly useful question, as people tend to use very
different coding styles for shared memory vs. message passing
applications.  However, you can naively expect the cost of message
passing to be somewhere between a smallish factor (2 or so) and an
order of magnitude higher than for shared memory.  Much of this
expense comes from the extra copying and context switching you have to
do when passing messages.

        <b

--
Let us pray:

Quote:> [...]

> Does anyone have any ideas how a seperate address space implementation compares with
> a shared memory implementation? Are we talking 10 or a 100 times slower? If messages
> can be passed back and forth via shared memory (assume lost messages are ok)
> wouldn't the big hit be context switches? On an MP machine this seems like no big
> deal. Comments?

And, remember -- if you pass messages in shared memory, they're subject to corruption.
Not just the messages themselves, but the control information you use to find and link
the messages. Sure, it's easier to deal with than possible corruption of ALL data --
but you're not safe from corruption.

Also, when using shared memory you still need to synchronize access. Unless you use
messages to do that (a sort of software token ring?), you'll have synchronization in
shared memory as well: either pshared mutexes, semaphores, or even a simple hardware
test-and-set lock. In any case, THOSE are all shared data, and subject to corruption.
In other words, you've gotten back part of the performance of using threads and shared
memory, while giving up most of the safety you got by giving up performance. That
doesn't sound like a good tradeoff to me, although it might be reasonable in some
circumstances.

/---------------------------[ Dave Butenhof ]--------------------------\

| 110 Spit Brook Rd ZKO2-3/Q18       http://members.aol.com/drbutenhof |
| Nashua NH 03062-2698  http://www.awl.com/cseng/titles/0-201-63392-2/ |
\-----------------[ Better Living Through Concurrency ]----------------/

|>
|> > [...]
|> >
|> > Does anyone have any ideas how a seperate address space implementation compares with
|> > a shared memory implementation? Are we talking 10 or a 100 times slower? If messages
|> > can be passed back and forth via shared memory (assume lost messages are ok)
|> > wouldn't the big hit be context switches? On an MP machine this seems like no big
|> > deal. Comments?
|>
|> There are too many possible permutations to give a single answer. The difference in
|> performance will depend on what communication mechanism you use, and how well that's
|> implemented. The best way to get an answer is to prototype and benchmark the
|> implementation in which you're interested!
|>
|> And, remember -- if you pass messages in shared memory, they're subject to corruption.
|> Not just the messages themselves, but the control information you use to find and link
|> the messages. Sure, it's easier to deal with than possible corruption of ALL data --
|> but you're not safe from corruption.
|>
|> Also, when using shared memory you still need to synchronize access. Unless you use
|> messages to do that (a sort of software token ring?), you'll have synchronization in
|> shared memory as well: either pshared mutexes, semaphores, or even a simple hardware
|> test-and-set lock. In any case, THOSE are all shared data, and subject to corruption.
|> In other words, you've gotten back part of the performance of using threads and shared
|> memory, while giving up most of the safety you got by giving up performance. That
|> doesn't sound like a good tradeoff to me, although it might be reasonable in some
|> circumstances.
|>
|> /---------------------------[ Dave Butenhof ]--------------------------\

|> | 110 Spit Brook Rd ZKO2-3/Q18       http://members.aol.com/drbutenhof |
|> | Nashua NH 03062-2698  http://www.awl.com/cseng/titles/0-201-63392-2/ |
|> \-----------------[ Better Living Through Concurrency ]----------------/
|>
There may two separate issues being discussed here.  The one I though
that was being discussed was whether you could recover from an
abnormally terminated or a hung thread.  You can, but you have to go
about things in certain ways.

The issue you seem to be discussing whether you can trust your own
code.  That's being a little paranoid.  Are you an X-phile?  Do you
watch X-files a lot?  I'm not sure that you can trust any of the
unices any more so.  I'm not aware of any bug free unix out there at
this time.

Also, unix only supports a few data structures directly.  If it's not
one of those, the application has to manipulate the data structure
itself, so there's no escaping the "trust" problem.

The only reason I know of for using non shared memory is for fault
tolerance, the source of the fault being the hardware.  Certain kinds
of hardware errors could affect a larger region of memory than just
the operands of the currently executing instruction.  Executing in
separate memory spaces helps isolate the error since the memory space
granularity is as least as large as the extend of any hardware
fault.  Of course, this only helps if the error occurs while a user
process is running, not while you're in the kernel.

Joe Seigh

j> [...] The one I thought that was being discussed was whether you
j> could recover from an abnormally terminated or a hung thread.  You
j> can, but you have to go about things in certain ways.

Dave and I have made clear several times that you cannot recover from
a thread within a single process dying at random.  If you have memory
shared between several processes and one of those processes goes away,
you can indeed recover, provided you've gone to considerable lengths
to structure your system appropriately.

        <b

--
Let us pray:

[...]

% |> test-and-set lock. In any case, THOSE are all shared data, and subject to corruption.
% |> In other words, you've gotten back part of the performance of using threads and shared
% |> memory, while giving up most of the safety you got by giving up performance. That
% |> doesn't sound like a good tradeoff to me, although it might be reasonable in some
% |> circumstances.

[...]

% The issue you seem to be discussing whether you can trust your own
% code.  That's being a little paranoid.  Are you an X-phile?  Do you

I think he's discussing whether you can trust code that you know has
abended.

% The only reason I know of for using non shared memory is for fault
% tolerance, the source of the fault being the hardware.

I didn't realise that hardware failures made this sort of fine distinction.
--

Patrick TJ McPhee
East York  Canada

...
|> % The only reason I know of for using non shared memory is for fault
|> % tolerance, the source of the fault being the hardware.
|>
|> I didn't realise that hardware failures made this sort of fine distinction.

Well, on mainframes and fault tolerant computers, they do, and it can
get rather elaborate.

For instance, if a processor failed while it was executing a store
instruction.  the entire block of storage that the cpu does its
storage accesses with could be suspect, not just the word within it
being updated by the store instruction.

On IBM mainframes, this was called a "storage logical" machine
check.  The word size would be 4 bytes, the extent of possible
"storage logical" damages would be typically the cache line, 128
bytes on some processor models.

The granularity of virtual memory was 4096 bytes, so you never had to
worry about "storage logical" damage from another process.  The
memory extents that could be damaged never overlapped for non-shared
memory.

This scheme allowed you to compartmentalize damage if that's what
you wanted to do.

Joe Seigh

j> Well, on mainframes and fault tolerant computers, they do, and it
j> can get rather elaborate.

It may have escaped your notice, but nobody who posts questions to
this group is using such systems.  You might want to adjust the
comments you make to fit the contexts in which people will try to
place them.

        <b

--
Let us pray: