[concurrency-interest] Attempt at yet another mostly-concurrent result cache

Holger Hoffstätte holger at wizards.de
Tue Jan 9 12:43:18 EST 2007


One last time..

Joe Bowbeer wrote:
> I think a batch can always be lost between the time it is cached and
> the time it is synchronized:
> 
>   Batch prev = cache.putIfAbsent(batchKey, batch);
>   if (prev != null) batch = prev; // flip refs
>   // LOST HERE
>   synchronized (batch) { ... }

OK, I now understand why both of my versions can be affected by this. The
batch holder does not really solve the underlying problem; thanks. Seems
the loop is really the best way to go.

> You can plug the hole by retesting inside a loop:
> 
> BatchResult process(Message msg) {
>   String batchKey = msg.getBatchId();
>   while (true) {
>     Batch batch = cache.get(batchKey);
>     if (batch == null) {
>       batch = new Batch();
>       Batch prev = cache.putIfAbsent(batchKey, batch);
>       if (prev != null) batch = prev; // flip refs
>     }
>     // we have a batch that was cached at one time
>     synchronize (batch) {
>       if (batch != cache.get(batchKey))
>         continue;
>       batch.add(msg);
>       if (!batch.isReady())
>         return null;
>       cache.remove(batchKey);
>       return batch.toResult();
>     }
>   }
> }
> 
> If you added a Lock to Batch then you might be able to improve
> efficiency by locking the newly constructed Batch before adding it to
> the cache.  Then you'd be sure no other thread could steal your new
> batch before you got a chance to use it.
> 
> Note that adding a loop raises the possibility of starvation (live-lock).
> 
> (What's the best way to plug that hole?)

Assuming you mean the case where one thread hogs the Map by continuously
hitting the same Map segment:

  if (batch != cache.get(batchKey)) {
    Thread.sleep(1); // since yield can be a nop
    continue;
  }

but that seems counterproductive since the monitor won't be released for
the duration of the sleep, so more like this:

  boolean cachemiss = false;
  while (true)
  {
    if (cachemiss) {
      Thread.sleep(1);
    }
  ...
  if (batch != cache.get(batchKey)) {
    cachemiss = true;
    continue;
  }

If that was not what you meant re: starvation then this young Jedi could
need a hint. :)

Thanks much
Holger



More information about the Concurrency-interest mailing list