Lock-free operations

Lock-free operations

Posted Feb 28, 2008 11:48 UTC (Thu) by forthy (guest, #1525)
Parent article: KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

There are a number of ways to do efficient lock-free operations even without resorting to a locked operation in some circumstances. Take e.g. the single-writer, single-reader queue with a finite size: All you need is a circular buffer and two pointers. The writer only writes to the end of the queue and updates only the high pointer after writing. The reader reads from the start of the queue and updates the low pointer after reading.

Or allocation/freeing of objects in a multi-processor system: Each core frees only those objects it allocated itself. Other cores can post "free this object" into a single-writer, single-reader queue, or mark objects as free and have them scanned while idle. You can even use a linked list if you keep at least one deleted object alive to avoid the empty-linked-list queue condition.

Another point is certainly serialization and deferring actions. One thing that comes in mind here is the user-kernel communication. In Linux, the user invokes a context switch into the kernel for every system call, and to make this context switch light-weight, the system call uses the user process, so in fact there are many kernel threads, which will require synchronization (in early Linux days, there was the BKL, so the kernel was serialized). If you change the syscall interface to a command queue (think of the X server), you can probably afford a more heavy-weight context switch, and less kernel threads. This however significantly changes the interface paradigm to the kernel - Unix-like syscalls do not fit well. Even the X server has too many functions which require round-trips. The upside of this change is that a network transparent kernel interface becomes feasible - and performance in clusters would improve significantly.

---

(Log in to post comments)