Question about JavaSpaces functionality

[Patricia Shanahan <pa...@acm.org>]

The current FastList implementation stops a scan when it reaches a node 
that was the tail at a critical point in the head() call that started 
the scan.

As far as I can tell, the benefit is that it ensures that every scan 
reaches a finite set of nodes, even if other threads are continually 
adding new nodes to the list.

I expect this passes through to the Outrigger JavaSpaces implementation, 
ensuring that every search will terminate. Otherwise, a search for a 
non-existent entry could go on forever, as long as new entries are being 
added as fast as the search processes them.

Is this correct?

I'm interested in this issue because maintaining that property costs 
extra logic in IterableFastList. It would be simpler to let the scan go 
on until it reaches a node with a null next pointer, indicating the 
current end of the list.

Patricia

Re: Question about JavaSpaces functionality

[Dan Creswell <da...@gmail.com>]

Correct, you've got to have a way to terminate the search predictably and
reliably. The overall algorithm looks something like:

(1) Start tracking newly written entry's
(2) Scan all existing entry's for a match
(3) When (2) completes, determine if we should continue waiting for matches
from (1) or exit.

Obviously there are plenty of places this can terminate early. You might get
a newly written entry match before you've even started a scan. You might get
part way through a scan and then find a match etc etc

The property you've identified below is related to (2) above.

You don't have to do things entirely this order. You can for example start
tracking newly written entry's just before reaching the end of the list
though that's quite tricky to do given other threads can be adding or indeed
removing on the list. Note also there's a point where if you're listening
for newly written entry's and scanning the list you could be mostly doing
duplicate searches of the same entrys.

Dan.

On 24 December 2010 04:29, Patricia Shanahan <pa...@acm.org> wrote:

> The current FastList implementation stops a scan when it reaches a node
> that was the tail at a critical point in the head() call that started the
> scan.
>
> As far as I can tell, the benefit is that it ensures that every scan
> reaches a finite set of nodes, even if other threads are continually adding
> new nodes to the list.
>
> I expect this passes through to the Outrigger JavaSpaces implementation,
> ensuring that every search will terminate. Otherwise, a search for a
> non-existent entry could go on forever, as long as new entries are being
> added as fast as the search processes them.
>
> Is this correct?
>
> I'm interested in this issue because maintaining that property costs extra
> logic in IterableFastList. It would be simpler to let the scan go on until
> it reaches a node with a null next pointer, indicating the current end of
> the list.
>
> Patricia
>