On Fri, 25 May 2001, Simon Burge wrote:

> I'm curious as to what you have in mind here?  AFAICR, at least
> postgresql just requires a TAS function - how it's implemented doesn't
> matter.  Do you have any pointers to these "memory synchronization
> algorithms"?  I have a reference to a "lazy" TAS implementation[2] that
> still requires kernel assistance.  Other options are a TAS-style syscall
> (maybe even a MIPS-specific sysarch() call that mimics the Ultrix
> atomic_op() syscall that can also be used in compat_ultrix) or using
> SYSV semaphores.

As far as memory-based synchronization,
I don't have any references offhand, but something like:

check() { 
 for (i = 0, sum = 0; i < threads; i++) sum += flags[i];
 return sum;
}

fake_sc(*addr, val, mythread) {
 if (check() != 0) return failure;
 flags[mythread] = 1;
 if (check() == 1) { 
   *addr = val; result = success; 
 }
 else { 
   result = failure;
 }
 flags[mythread] = 0;
 return result;
}

client() {
 while (fake_sc(addr, val) == failure) yield();
}
                                                                                
might work (this is similar to ethernet) although you would like to
guarantee that progress would be made.  There are probably better
algorithms - I just wrote the above off the top of my head; something like
this might be cheaper than a system call, depending on how many threads
and how much contention you have.

I am sure you could do it with semaphores as well - you just need to be
careful that you don't go to (real) sleep forever waiting on a lock that
another thread owns.  

One of my favorite memory-based algorithms for non-locking synchronization
is a single-writer, multiple reader generational algorithm proposed by
Lampson; something like:

writer(v1, v2) 
{ 
  gen++; var1 = v1; var2 = v2; gen++;
}

reader()
{ 
  do { 
    old = gen; v1 = var1; v2 = var2;
  } while ((gen & 1) || gen != old);
}

Values are stable during intervals where the generation value is even and
unchanged. Note this is a spin-lock implementation which is fine for truly
parallel machines but not great for uniprocessor threads.

Anyway, it seems to me that the postgresql, etc. problems should be rather
solvable, with small bit of thought, and shouldn't require kernel changes,

Bob

p.s. disclaimer: for simplicity, I have omitted various code which would
make the above valid C, but the basic idea should be clear.