jonathan@dsg.stanford.edu writes:

>>Not all of them. If you do a top/bottom design with lockless
>>synchronization then you don't ever have to yield in interrupt
>>context and you never (rather than rarely) spin in interrupt
>>context.
>
> Coming up with good, machine-independent (MI) atomic primitives for
> non-blocking synchronization is a real challenge. I recall debugging
> an multiple-68040-based SMP machine, where we used the '040s to get
> CAS2.

This is true. There's always lamport's algorithm, but that's hardly
what I'd call efficient.

> Point being, designing NBS algorithms for an MI OS kernel means we
> need to choose MI atomic operations,and that's difficult.

You can do it without atomic operations, but it requires being able to
code some fairly sophisticated non-atomic stuff based on Lamport's
work. 

> (Bershad's Restartable Atomic Sequences (RAS) are sometimes offered
> here, but that's a featurefor userspace code, not kernel-space
> code).

Yes.

The trick is to use non-atomic but fully ordered operations[1] in a
handshaking protocol. If done right, you make it a set of macros that
only have to be implemented once for each architecture and then you
rely on developers using those for communicating between the halfs.


[1] "fully ordered" in the weak sense that if processor A writes two
memory locations, first X and then Y, then processor B never sees the
new value of Y before it sees the new value of X.  You can do it with
weaker requirements, but the algorithms get more complicated.