Thread-safe caches - lisp

Robert Maas, see http://tinyurl.com/uh3t wrote:
>> From: Pascal Costanza <p...@p-cos.net>
>> Currently, ContextL caches are implemented using property lists.
>> However, there seem to be problem with concurrent accesses to those
>> caches when using multiple threads.
>> Does anyone know of a straightforward way to make property lists (or
>> association lists or hashtables) thread-safe in an
>> implementation-independent way, possibly using some kind of
>> compatibility layer?
>
> For the benefit of readers who are not familiar with ContextL, it
> would be helpful if you would formally describe the sorta-use-cases
> of the API you are attempting to make thread-safe. That is which
> operations upon the cache do you need to be "atomic" with respect
> to switching activity between different threads (or even worse,
> running two threads *simultaneously* on dual/multiple processors).
>
> For example, if process A modifies a cached item, then ten minutes
> later process B tries to read the same item, do you expect B to see
> the cached-modified version or is it permissible for B to still see
> the original value after all that time? There are too many
> questions like this for me to list a menu of yes/no requirements.
> Better you just define precisely what behaviour you expect to be
> totally reasonable in what way and what behaviour you would allow
> to be somewhat non-reasonable in what way and what unreasonable
> behaviour you would absolutely forbid.

That's not so straightforward. The implementation of ContextL is
(roughly) described in http://p-cos.net/documents/context-switch.pdf -
and I am talking about the caches that are mentioned in Section 3.1 in
that paper.

> My naive view is that you would most definitely need *some* type of
> thread-safe compatibility layer, but whether the provisions of the
> underlying CPU and/or CL-implementation would suffice already would
> depend on your specific requirements, which have not been stated
> clearly enough (even in your folloups) for my satisfaction.

Maybe it becomes clearer by reading that paper.

Anyway, I have found a solution to my problem. I'm using the
portable-threads library of the GBBopen project now, and I do proper
locking of the caches. Efficiency shouldn't suffer, because the locking
only occurs on the slow paths - the fast paths are not affected.

Because I use locking now, the possibility of cache entries not properly
being recorded shouldn't occur. Whether some data types are atomic or
not doesn't matter anymore either.

The discussions here in c.l.l helped a lot to get a better idea about
this whole issue.

The changes to ContextL are not in the official release yet, but you can
find them in the darcs repository.

Sorry if I can't be more specific...


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/

> From: Antony Sequeira <firstname.lastn...@gmail.com>
> Another point to remember is that being atomic at write is not
> enough in many practical situations (where you are not setting the
> value unconditionally).

I'm not quite sure what you're talking about there. Can you give a
simple example where there's only a single shared variable yet
conditional atomic-write of that variable isn't thread safe?

> For example according to the link Pascal posted, we can assume a
> boolean is atomic in Java without requiring extra work from the
> programmer, yet there is
> http://java.sun.com/j2se/1.5.0/docs/...icBoolean.html
> It may not be obvious why.

<cliche>The devil is in the details</cliche> I.e. look not just at
the name of the class, but the set of methods provided.
The key thing is that atomic read and write is *not* the only
method provided there. Also provided are two others which interlock
two separate operations into a single atomic operation (a "critical
section"):

(1)
public final boolean compareAndSet(boolean expect,
boolean update)
Atomically set the value to the given updated value if the
current value == the expected value.
Returns:
true if successful. False return indicates that the
actual value was not equal to the expected value.
If all it did was set to new value if it wasn't already that value,
simply setting it would do the trick. If all it did was set to new
value if it already was, NO-OP would suffice. Those are the only
two cases to consider as for side-effect itself. But there's also
the return value, which must be the result of test *immediately*
before (no interrupts between) the conditional setting. This (with
the constructor of course) is in fact sufficient to implement a
LOCK, as follows:
To create a LOCK which nobody has yet:
sharedLock = new AtomicBoolean(false); /* = default no-arg constructor */
To try to get a lock, and know whether you got it or not:
gotFlag = sharedLock.compareAndSet(false, true);
if (gotFlag) { Code for using the resource ... code (below) to release }
else { Code for re-trying or giving up etc. }
To release the lock, after you already know you got it:
happyFlag = sharedLock.compareAndSet(true, false);
if (!happyFlag) { Bug report, we thought we had the lock, but it went false }

Note that atomic-swap-local-with-shared-boolean is equivalent in
power, but is a single atomic machine instruction on some/most CPU
architectures. (Exercise for reader such as newcomer to software:
Emulate each in terms of the other.)

public final boolean getAndSet(boolean newValue)
Sets to the given value and returns the previous value.

(2)
Ah, that is more obviously equivalent to atomic-swap-local-with-shared-boolean.
For example: localBool = sharedLock.getAndSet(localBool);
That emulates swap in terms of getAndSet, and emulating the reverse
direction is nearly as trivial, no need for exercise for reader
unless very very beginner at software.


On the other hand, what about this??

public boolean weakCompareAndSet(boolean expect,
boolean update)
Atomically set the value to the given updated value if the
current value == the expected value. May fail spuriously.
Returns:
true if successful.

Now this really bothers me! First, assuming that the CPU can
implmement it via atomic swap register with memory, how can it
possibly fail except if the programmer totally goofed and didn't
code that mechanism? Second, what does "successful" mean? Does it
mean "should have made the update because the expect matched" or
"didn't spuriously fail" or both of those together i.e. false if it
spuriously failed or if no update was needed?
Finally, what kinds of spurious failage are possible here?
Does it set the variable even when the expect didn't match?
Does it fail to set the variable when the expect *did* match?
Does it return an inappropriate value even though the operation itself worked?
Does it throw an unchecked exception?
Does it garbage-collect the AtomicBoolean object so that later the JVM crashes?
Does it go into an infinite loop with all interrupts disabled needing cold boot?
Does it delete/dismount/trash the root directory and/or boot sector?
IMO This JavaDoc needs some serious re-thinking!

> From: Alexander Kjeldaas <alexander.kjeld...@gmail.com>
> A memory fence is an operation that simply means that the CPU
> will not reorder reads or writes across the fence.

<cliche>You learn something new almost every day</cliche>
Ah, thanks for the new concept I never heard of before.
(I never had the "opportunity" to try to write machine code for any
CPU that had the option of re-ordering memory operations. The
newest CPU I ever wrote machine code for was the 68000, a Mac Plus,
via Sesame C and Pocket Forth.)
Indeed that's a very simple/elegant/powerful/inexpensive feature.

Now a followup question: Suppose your CPU does *not* have any
atomic read+write operation (such as swap register<->memory),
guaranteed to complete in a single memory cycle. But you do have
memory fences. Suppose you have more than one CPU accessing the
same RAM. How do you implement a lock efficiently?

My first idea is to have a separate memory cell for each CPU that
might need to use the same lock, with pre-established priorities as
to who gets to use the resource if more than one CPU wants to use
it at the same time. Lower priority CPUs would try to get their
lock but then check if some higher priority CPU had gotten it in
the mean time, and wait until higher-CPU didn't have it before
actually using the resource themselves. Higher priority CPUs would
just grab the lock and not care if anybody lower was reporting to
have it, since lower-CPU wouldn't actually use it until *I*
released it. I don't know if this would really work.
Any comments or alternatives?

Now assuming the CPU does have adequate built-in mechanisms:
More generally, there seem to be two classifications of resources:
-1- Short duration use, like just a few clock cycles per use
-2- Long duration use, long enough that queue is more efficient than retestLoop
-A- Hardly ever a simultanous request for same resource
-B- Most of time the resources has multiple processses wanting it

As for what seems to me optimal solution for each of the four composite cases:
-1A- It suffices to use atomic-swap instruction to request lock,
and sleep-retry if it was busy already.
-1B- Difficult case, I have some composite ideas that might work.
-2A- It suffices to use a general lock mechanism, with a priori
knowledge of how long the other process is likely to use it,
with retry at random times approximately when the other
process is expected to be done.
-2B- You really need a formal scheduler to mediate all requests for
the resource. You put a request in the queue, with a callback for
when the resource will become ready.

For that difficult case 1B, one idea is to use the atomic lock a
few times just to see if we happened to catch it when it wasn't too
busy, but when it starts to look like we have a serious problem
with contention for that resource then we submit a formal request
to the resource mediator. The mediator gets a lock on the resource
and keeps it so long as any process has been sub-delegated that
resource and/or there are any other processes in the queue for it.
Only when the queue is empty, then release the lock for more
efficient use while load is low.

Caveat: I've never programmed any of this. I'm just brainstorming.
(I placed top five in Putnam contest, so I'm licensed to brainstorm!!)

Den Wed, 14 Nov 2007 11:26:50 -0800 skrev Robert Maas, see
http://tinyurl.com/uh3t:

> Now a followup question: Suppose your CPU does *not* have any atomic
> read+write operation (such as swap register<->memory), guaranteed to
> complete in a single memory cycle. But you do have memory fences.
> Suppose you have more than one CPU accessing the same RAM. How do you
> implement a lock efficiently?

You don't. Setting a fence is a per-CPU operation, it only means that the
CPU will be notified that the order is significant and won't try
optimising the operations by shuffling them.

Cheers,
Maciej