Semaphores in Linux

futuregod

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.

[img]http://adserver.adtechus.com/adserv/3.0/5159/425847/0/170/ADTECH;loc=300;key=key1+key2+key3+key4;grp=[group][/img]
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
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);
keyUsed for identifying the semaphore.nsemsNumber of semaphores needed in the set.semflgIndicates 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
NOTE: Actually IPC_PRIVATE is defined as ((__key_t) 0). This can be found under the header file ipc.h
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/16030/showart_1713876.html