Prev: Assistance Needed: Setf
Next: LISP-in-a-box or CLISP memory constraints?
From: Rob Thorpe on 20 Oct 2006 10:22
Someone pointed out an interesting problem to me that applies to JVMs,
I'd be interested to understand how multi-threaded lisps deal with it.

Lets say there is a variable "foo". It is assigned to by something
like (setf foo (complex-stuff)). Consider the situation where two
processors are used both running threads from the same program. Also,
lets assume that the processors do not gaurantee the order of stores.
In "complex-stuff" a data-structure is created to be assigned to foo.
Imagine another thread reads foo just as this is happening. If the
order of stores isn't gauranteed then the data-structure being created
by "complex-stuff" might not be complete from the point of view of this
second thread. Potentially the memory may not even be initialized.

How do lisp runtimes deal with this problem?

From: Lars Rune Nøstdal on 20 Oct 2006 10:33
On Fri, 20 Oct 2006 07:22:15 -0700, Rob Thorpe wrote:

> Someone pointed out an interesting problem to me that applies to JVMs,
> I'd be interested to understand how multi-threaded lisps deal with it.
>
> Lets say there is a variable "foo". It is assigned to by something
> like (setf foo (complex-stuff)). Consider the situation where two
> processors are used both running threads from the same program. Also,
> lets assume that the processors do not gaurantee the order of stores.
> In "complex-stuff" a data-structure is created to be assigned to foo.
> Imagine another thread reads foo just as this is happening. If the
> order of stores isn't gauranteed then the data-structure being created
> by "complex-stuff" might not be complete from the point of view of this
> second thread. Potentially the memory may not even be initialized.
>
> How do lisp runtimes deal with this problem?

If I understand this question correctly this is a general problem that
isn't JVM- or Lisp-specific.

What one does is use "mutual exclusion" for sections of code that access
shared data. See: http://en.wikipedia.org/wiki/Mutex

--
Lars Rune Nøstdal
http://lars.nostdal.org/

From: Rob Thorpe on 20 Oct 2006 11:06
Lars Rune Nøstdal wrote:
> On Fri, 20 Oct 2006 07:22:15 -0700, Rob Thorpe wrote:
>
> > Someone pointed out an interesting problem to me that applies to JVMs,
> > I'd be interested to understand how multi-threaded lisps deal with it.
> >
> > Lets say there is a variable "foo". It is assigned to by something
> > like (setf foo (complex-stuff)). Consider the situation where two
> > processors are used both running threads from the same program. Also,
> > lets assume that the processors do not gaurantee the order of stores.
> > In "complex-stuff" a data-structure is created to be assigned to foo.
> > Imagine another thread reads foo just as this is happening. If the
> > order of stores isn't gauranteed then the data-structure being created
> > by "complex-stuff" might not be complete from the point of view of this
> > second thread. Potentially the memory may not even be initialized.
> >
> > How do lisp runtimes deal with this problem?
>
> If I understand this question correctly this is a general problem that
> isn't JVM- or Lisp-specific.
>
> What one does is use "mutual exclusion" for sections of code that access
> shared data. See: http://en.wikipedia.org/wiki/Mutex

Yes, I realise that. What I'm trying to understand is what it means
for memory allocation specifically.

One way to treat it correctly would be to have one heap for all objects
shared between processors and to mutex the heap. This would be
inefficient though because of the amount of waiting it would require.

Another approach would be to have mini-heaps on a per-thread basis.
When some memory is needed it is first taken from this thread-local
heap. But this doesn't seem to solve the problem completely. In the
example above the data-structure created by "complex-stuff" could be
put in the thread-local heap. But later it's assigned to a variable
visible in other threads - ie to "foo". As far as I can see before
this happens all pending stores on the data must be completed.

How do lisps do this?

From: pTymN on 20 Oct 2006 11:10
Interesting question, I've been curious about this too.

From: Joe Marshall on 20 Oct 2006 13:01

Rob Thorpe wrote:
>
> Yes, I realise that. What I'm trying to understand is what it means
> for memory allocation specifically.
>
> One way to treat it correctly would be to have one heap for all objects
> shared between processors and to mutex the heap. This would be
> inefficient though because of the amount of waiting it would require.
>
> Another approach would be to have mini-heaps on a per-thread basis.
> When some memory is needed it is first taken from this thread-local
> heap. But this doesn't seem to solve the problem completely. In the
> example above the data-structure created by "complex-stuff" could be
> put in the thread-local heap. But later it's assigned to a variable
> visible in other threads - ie to "foo". As far as I can see before
> this happens all pending stores on the data must be completed.
>
> How do lisps do this?

Modern processors that can perform out-of-order writes usually have
some way to ensure that pending writes have been flushed before
performing critical operations. In a single processor system, there
shouldn't be a problem because the processor ought to mask the
out-of-order writes from its own view of the world (that is, the writes
will appear to have occurred in order with regard to reads as far as
the processor is concerned, regardless of what happened in the memory
system).

As far as multiple processors on shared memory go, the issue is more
complicated. I believe there are `write gate' instructions that force
the processor to flush the pending writes. These could be used to
ensure that the data structure is fully written before exposing a
pointer to it. There are also mechanisms in the memory system that
allow you to inform the processor that out-of-order reads and writes
are prohibited (it would be bad for a memory-mapped device if things
didn't happen in order). Multiprocessors have ways of `snooping' on
other processors' caches, too. This allows the other processors to
agree on a last-written value.

 |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Assistance Needed: Setf
Next: LISP-in-a-box or CLISP memory constraints?