User level semaphores

Multicore computers as found today can share memory. Semaphores are
popular for building other synchronization and communication primitives.
But as found on most operating systems, they require entering the kernel
even if it is not necessary. In many cases, two process will be running each one
in its own core and one would put a ticket in a semaphore before the other would
try to acquire it. Why should they enter the kernel in that case?
Linux includes futexes, with the same rationale, but they are not reliable and, therefore,
cannot be used for real applications.


In the operating system we are building, NIX, we have included user-level semaphores
using this interface:



extern int altsems(int *ss[], int n);
extern int downsem(int *s, int dontblock);
extern void upsem(int *s);


Up and down are similar to other interfaces. They rely on atomic increment and
decrement operations to update the semaphore (an integer value) without races.
However, if a process finds during a down that it should block, it would enter
the kernel and sleep. If another process increments the semaphore and finds that
someone was awaken (because it was negative), it enters the kernel to awake
the sleeper. With some book-keeping, operations may proceed in many cases without paying
the cost of entering and exiting the kernel.


Altsems is a novel operation. It tries to perform simultaneous downs on an array of
semaphores, using the same approach described above. Only one of them will proceed,
but the process does not know which one until it returns. This is useful to implement
user-level channels, equipped with an alt operation to send or receive from multiple
channels.