Semaphores in Linux

by Vikram Shukla
05/24/2007

Multithreaded applications are part and parcel of day-to-day commercial application. It would be difficult to imagine any full fledged application running commercially that is not multithreaded. Applications must use the multithreaded approach to improve on the performance of the application or systems. However, most beautiful things in life do not come without a price. Likewise, if the multithreaded feature needs to be used by the application, then it comes with a set of issues, such as deadlocks, race conditions, incorrect behavior of threads, etc. To overcome these issues, the OS provides a set of tools like Mutex, semaphores, signals and barriers that are handy in solving multithreaded multiprocessed issues. This article discusses one of these tool, semaphores, and provides some insight about them.

Introduction to Semaphores

Semaphores can be thought of as simple counters that indicate the status of a resource. This counter is a protected variable and cannot be accessed by the user directly. The shield to this variable is provided by none other than the kernel. The usage of this semaphore variable is simple. If counter is greater that 0, then the resource is available, and if the counter is 0 or less, then that resource is busy or being used by someone else. This simple mechanism helps in synchronizing multithreaded and multiprocess based applications. Semaphores were invented and proposed by Edsger Dijkstra, and still used in operating systems today for synchronization purposes. The same mechanism is now available for application developers too. Its one of the most important aspects of interprocess communication.

Semaphores can be either binary or counting, depending on the number of shared resources. If a single shared resource is used, then we would require just one semaphore for synchronization purposes. In that case, the semaphore is referred as a binary semaphore. In all other cases, where the number of resources shared across users are greater than one, you would use multiple semaphores, in which case they are referred as counting semaphores.

Semaphores basically implement two kinds of operations. One to wait on the semaphore variable and another that signals the semaphore variable. Since semaphores are nothing but a counter, the following algorithm depicts these two semaphore operations:

Assume :
s is the semaphore variable
W(s) denotes waiting on the semaphore
P(s) means signaling the availability of semaphore

Algorithm :

W(s) 
 while  (s<=0)    {
   //do  nothing 
}
s=s-1;
P(s)
s=s+1;

From the above algorithm, it could be easily understood that waiting on a semaphore does nothing more than decreasing the semaphore counter by 1. Signaling the semaphore is exactly the opposite, increasing the semaphore counter by 1.

Let's see some of the structures and functions that are used internally by the Linux kernel to implement the functionality of semaphores. Semaphores use the following two structures internally :

struct semaphore
{ 
 atomic_t count;
 int sleepers;
 wait_queue_head_t  wait;
}
struct rw_semaphore
{
 _s32 activity
 spinlock_t wait_lock;
 struct list_head  wait_list;
};

This structure, however has undergone some change in the latest kernels. It has been included with additional member variables as shown below:

struct rw_semaphore {
   signed  long count;
   #define RWSEM_UNLOCKED_VALUE 0x00000000
   #define RWSEM_ACTIVE_BIAS 0x00000001
   #define RWSEM_ACTIVE_MASK 0x0000ffff
   #define RWSEM_WAITING_BIAS (-0x00010000)
   #define RWSEM_ACTIVE_READ_BIAS RWSEM_ACTIVE_BIAS
   #define RWSEM_ACTIVE_WRITE_BIAS (RWSEM_WAITING_BIAS +  RWSEM_ACTIVE_BIAS) spinlock_t wait_lock;
    struct  list_head wait_list;
   #if RWSEM_DEBUG
    int debug;
   #endif
};

The basic functions that implement the semaphore operation at the kernel level can be found under the /asm/semaphore.h and /asm/rwsem.h header files:

• __down(struct semaphore *): This function checks to see if the semaphore is greater than zero. If so, it decrements the semaphore count and returns. If not, it sleeps and tries again later.
• __up(struct semaphore *): This function increments the semaphore count, thus awakening any process waiting on the semaphore.
• __down_trylock(struct semaphore *): This function checks to see if the semaphore is available. If not, then the function would return and is thus categorized as a non-blocking function.
• __down_interruptible(struct semaphore *): The action of this function is similar to __down with a difference, it can be interrupted by a signal. Should it be interrupted by a signal, it would return -EINTR. The __down version blocks signals while running.
• The other functions such as __down_read (locks the semaphore for reading), __down_write (locks the semaphore for writing) , __up_read (frees the semaphore after reading), and __up_write (frees the semaphore after writing) permit more that one reader to access a protected resource, but only one writer to update.

Distributions of Semaphores

The current Unix environment comes with two types of semaphores: System V and POSIX. In general, the older Unix-based systems uses the System V version and the current Linux-based systems use the POSIX version. However, the general behavior and technology of semaphores does not change irrespective of the version used. Let's look at the interfaces, and how they work on these two different versions of semaphores.

System V Semaphores

The interface and usage of System V semaphores is cluttered with unnecessary complications. For example, the semaphore created is not just a single counter (value) but rather a set of semaphore counters (values). This introduces the concept that the semaphore object created consists of 0 to n semaphores in a set with an identical semaphore ID. The function that achieves this is:

int semget(key_t key, int nsems, int semflg);

key

Used for identifying the semaphore.

nsems

Number of semaphores needed in the set.

semflg

Indicates the how semaphore needs to be created. It could be one of the following types:

• IPC_CREAT: Creates a new semaphore if the key does not already exist.
• IPC_EXCL: If the key exists, it will cause the function to fail.

The key, of type key_t, could have any meaningful value as provided by the user or programmer or generated by the ftok() call. However, System V semaphores provide a different key, which is identified by IPC_PRIVATE. When this key is used, every time a semget() call is made, it creates a new set of semaphores identified by the semaphore ID. The following code snippet shows how to create a new semaphore at every call of the semget function.

{
 int semid;
 semid=semget(IPC_PRIVATE,  1,IPC_CREAT);
 if  (semid<0) 
 {
  perror("Semaphore creation failed  Reason:");
 }
}

NOTE: Actually IPC_PRIVATE is defined as ((__key_t) 0). This can be found under the header file ipc.h