System V IPC:Semaphores

In the previous post, I have described about the Mutexes and Condition Variables of the pthread library. Truly speaking, they don't actually give full support to synchronization. For instance, take the well known Readers-Writers problem, in which any number of readers can read the shared data at once. Can this be implemented by Mutexes alone?? The answer is absolutely no!

So, there comes the Semaphores into the picture.

What is a semaphore?

A semaphore is just like a mutex, but it gives access to shared memory to desired number of processes. Each semaphore will be initialized with a positive value, and this value is decreased or increased by desired amount by each process. When the value reaches zero or when the amount to be decremented takes the value of the semaphore to a negative value the process has to wait( this is optional which we will be seeing shortly), until some other process increments the value.

A mutex is like a semaphore whose initial value is 1

Still confused with the difference between these two? Then click here. It explains nicely with different examples.

System calls related to Semaphores:

Through out this post, our discussion will be about these three Important System calls:

• semget()
• semop()
• semctl()

---

Where they are stored?

These semaphores are maintained in arrays (not individually) by the kernel. It stores all these values in a special data structure called semid_ds which is a C struct defined as follows:

struct semid_ds {
     struct ipc_perm sem_perm;       /* permissions */
     time_t          sem_otime;      /* last semop time */
     time_t          sem_ctime;      /* last change time */
     struct sem      *sem_base;      /* ptr to first semaphore in array*/
     struct wait_queue *eventn;
     struct wait_queue *eventz;
     struct sem_undo  *undo;         /* undo requests on this array */
     ushort          sem_nsems;      /* no. of semaphores in array */
        };

Now, don't get panicked by seeing the above structure. This is only for your information. Most of them are irrelevant, but some of them are important.

Most of the information about the struct is understood from the comments. The first one stores information about the permissions of the semaphore set like who can read, write and execute the semaphore.
The second and third are the last time when the operations were performed on the semaphore(done by semop()) set and the modified time(done by semget() and semctl()).
The fourth one is a pointer to first semaphore in the array. All but last one are irrelevant for now and the last one stores the number of semaphores in the array

The semaphore struct:

Previously, we have seen the structure for a semaphore set. Now, here is the structure of each semaphore:

struct sem {
            short   sempid;         /* pid of last operation */
            ushort  semval;         /* current value */
            ushort  semncnt;        /* num procs awaiting increase in semval */
            ushort  semzcnt;        /* num procs awaiting semval = 0 */
        };  

I hope you wont be worrying because this is not so big as previous one :P. As I said before, this is only for information. After all being a computer science student, we shouldn't be so abstract!! ;).

Now, let us enter into the description of the main System calls. Starting with semget().

---

semget():

The prototype of this system call is as follows:

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

Now, the first argument is a unique number generated from ftok() system call. Its prototype is as follows:

key_t ftok(const char *path, int id)

The path can be any path for a given directory. The id is a number which we give as argument. It functions such that when we give the same path name and id every time, it always gives the same number. In other words, it generates unique value for a given (path,id) pair.

Usage:

key_t G;
G=ftok(".",  12);

Now, G has a some value stored in it. Observe that, the dot which we gave refers to the current directory.(to avoid complications).

This value is passed as the first argument. The second argument is the number of semaphores you want to create in the semaphore set.

The third one, is a bit complex. It is the flags that can be passed. It accepts two flags. IPC_CREAT and IPC_EXCL.

IPC_CREAT:

This flag is used to tell the kernel to create a semaphore set, if it doesn't exists already.

IPC_EXCL:

This flag is used along with the above one, so that the function fails to create a semaphore set if it already exists.

The permissions:

In general, we also specify the permission mode along with the above flags when the semaphore set is being created for the first time. The general mode which we specify is 0660.

0660?

The meaning of the above numbers is simple. If you observe that in Linux every file has file permissions for owner , group and public. There are 3 bits(read, write, execute) for each of them making a total of 9 bits.

Now, to give r,w,x permissions to only the owner, we need to set only the first three bits while the remaining should be cleared making the value 7(111)0(000)0(000).

In the similar manner, 660 means 110 110 000. If we decode it, we find that we are giving read and write permissions on the semaphore set for both the owner and the group which he belongs to.

To give the permissions to public also we specify, 666. Sounds simple right?

All the flags are ORed with each other when specifying multiple flags.

Usage:

int sem_id=semget(key_value, no_of_sems, IPC_CREAT|0660);

I forgot to say an important thing, the return value! It is actually the unique ID for the given semaphore set, which can be used in the later time to perform operations on that set.

---

semctl():

Just creating the semaphore set is not enough. We have to initialize all the semaphores with some positive values(or may be even zero). This can be done using semctl() system call.The prototype is as follows:

int semctl ( int semid, int semnum, int cmd, union semun arg )

The first argument is the semid which is obtained from semget() system call. The second one is the number of the semaphore in the semaphore set to which you want to initialize the values. It starts from 0. i.e., 0 being the first semaphore in the set.

The third argument is again some what complex. Although there are 10 different commands for this argument, i am gonna explain only the essential ones which are 4 only.

Before saying about these commands, we need to examine the last argument. It is a union of type semun. The structure is as follows:

union semun {
                int val;                /* value for SETVAL */
                struct semid_ds *buf;   
                ushort *array;          /* array for GETALL & SETALL */
                struct seminfo *__buf;  
                void *__pad;
        };

As you see from the comments, only two of them are useful for now, namely the integer val and the int array array.

Now, let us discuss about the four important commands.

SETVAL:

When the third argument is SETVAL, then the value of the semaphore pointed by the semnum is set to the value specified in the val field of the semun union.(Confused?)

For example, if you want to set the 4th semaphore of the semaphore set with ID 1234, with the value say 6, then we need to write the following statements.

union semun tmp;
tmp.val=6;
semctl(1234, 3, SETVAL, tmp);

The above statements perform the desired operations. In simpler way, SETVAL is used to set the value of individual semaphore.

GETVAL:

The GETVAL is used to get the value of a specified semaphore in the set.

For example, we want to retrieve the value of 2nd semaphore of the semaphore set with ID 3456. Then, the following statement should be written.

int value=semctl(3456, 1, GETVAL, 0);

This returns the value into the value type. Note that since here, there is no need of the union, we specify it to bve zero.

SETALL:

When you want to set all the values of the semaphore at once, you can use this command. It takes the Integer array pointed by array in the semun union and sets the values of each semaphore.

For example, you want to initialize, a semaphore set whose ID is 1234 having 4 semaphores, to 2,5,8,3 respectively. Then the instructions used are:

union semun tmp;
ushort g[]={2,5,8,3};
tmp.array=g;
semctl(1234, 4, SETALL, tmp);

This performs the desired operation.

GETALL:

When you want to retrieve the values of all semaphores, then you use this command. It is same as previous one except that after the function call with this command the array of semun has the values of all the semaphores.

---

semop():

Now, there comes the important one. After creating and initializing the semaphore set, you wish to use them in process synchronization. This can be done with the semop() system call. It has the following prototype.

int semop ( int semid, struct sembuf *sops, unsigned nsops)

The first argument is the semaphore ID on which you want to perform the opearitons. The second argument is a pointer to a struct of type sembuf. It has the following fields:

 struct sembuf {
         ushort  sem_num;        /* semaphore index in array */
         short   sem_op;         /* semaphore operation */
         short   sem_flg;        /* operation flags */
        };

The usage of this system call is much simpler than one might be expecting. You should be initializing this struct in order to perform the operations.
The first field is the index of the semaphore on which you want to perform the operations.
The second one being the amount by which you want to increment or decrement(specify a negative value) the value of the semaphore.
The third one is the operation flags. It generally takes two flags, IPC_NOWAIT and IPC_UNDO. The first one is important for us.

IPC_NOWAIT

When this flag is specified, the process never tries to sleep, if the operation it performs on a semaphore makes the value to negative. If no flag is specified, then the process sleeps until, it can perform the operation.

For example, the value of 3rd semaphore of a semaphore set with ID 1234 is 5 and a process wants to decrement it by 6, then since the value becomes negative(-1), when this is performed, the process actually gets blocked(depending on the operation flag) until some other process increments the value of the semaphore atleast by 1. If you want the process to be blocked then you need to write the following statements:

struct sembuf tmp;
tmp.sem_num=2; //for 3rd semaphore
tmp.sem_op=-6;
tmp.sem_flg=0;//if you don't want the process to be blocked then specify IPC_NOWAIT

semop(1234, &tmp, 1);

Actually, I forgot to explain the 3rd argument. It is the number of operations you want to perform on the semaphore set. In the above case it is 1. If you want to perform multiple operations, you just need to create an array of sembufs and pass the size of the array as the 3rd argument to the semop function. This is left as an exercise for the reader.

---

Abstraction:

If you want to write a program using these semaphores, I am sure that you get pissed of easily, because you need to write many instructions for a small operation. Abstraction sometimes helps to overcome these problems. Now, don't think what is this one? I am technically saying to define each function for the operations you want to perform.

Here are my functions(you can define your own functions also, but they look nearly like mine ), which are pretty much useful and easily understandable.

#include<stdio.h>
#include<stdlib.h>
#include<sys/sem.h>
#include<sys/types.h>
#include<sys/ipc.h>
#include<pthread.h>
int ID;
union semun {
 int val;
 struct semid_ds *buf;
 unsigned short int *array;
 };
int state=1;
int sem_init(int no_of_sems, int common_intial_value)
{
 key_t h=ftok(".", state++);

 int sem_id=semget(h, no_of_sems, IPC_CREAT|0666);
 if(sem_id==-1)
 {
  printf("Semaphore init error\n");
  exit(1);
 }
 union semun tmp;
 tmp.val=common_intial_value;

 for(int i=0; i<no_of_sems; i++)
  semctl(sem_id, i, SETVAL, tmp);
 return sem_id;
}



int sem_init_diff_val(int no_of_sems, int *array)
{
 key_t h=ftok(".", state++);
 int sem_id=semget(h, no_of_sems, IPC_CREAT|0666);
 if(sem_id==-1)
 {
  printf("Semaphore init error\n");
  exit(1);
 }
 union semun tmp;//.array=array;
 tmp.array=(unsigned short int*)array;
 semctl(sem_id, 0, SETALL, tmp);
 return sem_id;
}



void sem_change(int sem_id, int sem_no, int amount)
{
 struct sembuf tmp;
 tmp.sem_num=sem_no;
 tmp.sem_flg=0;
 tmp.sem_op=amount;
 if(semop(sem_id, &tmp, 1)==-1)
  {
   printf("Sem_op error\n");
   exit(1);
  }
}

int sem_try_change(int sem_id, int sem_no, int amount)
{
 struct sembuf tmp;
 tmp.sem_num=sem_no;
 tmp.sem_flg=IPC_NOWAIT;
 tmp.sem_op=amount;
 return semop(sem_id, &tmp, 1);
  
}

---

Conversion between mutex code and semaphores code:

You may be confused with the above functions. Let me convert each mutex function into its equivalent semaphore function.

pthread_mutex_t A,B,C; -----> int sem_ID; //sem_id for three semaphores set
pthread_mutex_init(&A,NULL);
pthread_mutex_init(&B,NULL);
pthread_mutex_init(&C,NULL);

is same as

sem_ID=sem_init(3, 1);

pthread_mutex_lock(&A); -----> sem_change(sem_ID, 0, -1);
pthread_mutex_lock(&B); -----> sem_change(sem_ID, 1, -1);
pthread_mutex_lock(&C); -----> sem_change(sem_ID, 2, -1);

pthread_mutex_unlock(&A); -----> sem_change(sem_ID, 0, 1);
pthread_mutex_unlock(&B); -----> sem_change(sem_ID, 1, 1);
pthread_mutex_unlock(&C); -----> sem_change(sem_ID, 2, 1);

pthread_mutex_trylock(&A); -----> sem_try_change(sem_ID, 0, 1);
pthread_mutex_trylock(&B); -----> sem_try_change(sem_ID, 1, 1);
pthread_mutex_trylock(&C); -----> sem_try_change(sem_ID, 2, 1);

The conversion of condition variables is left as an exercise for the reader. :)

---

In the above program, you need to declare the union semun. I thought it was a predefined union. But the documentation was saying us to define it. If you further see, there is a state variable, which always increments when a new semaphore is created. This is just to make sure not to generate the same key_t value when we are creating new semaphore sets.
One last thing is that, the above code is yet to be checked for bugs, Although it was working fine with small number of threads.

---

Additional References:

http://www.cs.cf.ac.uk/Dave/C/node26.html
http://linux.die.net/man/7/svipc
http://cse.yeditepe.edu.tr/~sbaydere/spring2012/cse331/files/SystemVIPC.pdf

---

<<Prev Next>>