Tagged: semaphores

Tackling the reader-writer problem with Semaphores

Any one who has come across Process Synchronization must have read about the famous reader-writer problem. Let me put the problem in an easier way.  Consider Adu, Shankie and Somu wants to edit on the same shared file. All are connected to the same file somehow and needs access to it. Say all three of them wants to read it. There is no harm for all of them to read it at the same time. Now, imagine a situation when Shankie wants to write into the file and others want  to read. It is not correct for Somu and Adu to read a file while Shankie is editing it. He may be erasing some lines and might be adding more. Either Adu and Somu must read first and then allow Shankie to write or vice versa. Problem becomes terrible when Somu also decides to write. Somu edited half the file and she saved and left. At the same time Shankie had opened it before and he saves after Somu saves. All the changes made by Somu will be gone when Shankie saves the file.

This is a classic Synchronization problem associated with multi-programming or multi-threading. Here is the statement :

Many threads must access the same shared memory at one time, some reading and some writing, with the constraint that no process may access the share for reading
or writing while another process is in the act of writing to it.

Here is an implementation of the reader-writer problem using semaphores in linux.

writer()
{
wait(wrt);
signal(wrt);
}
reader()
{
wait(mutex);
readcount++;
if(readcount ==1)
wait(wrt);
signal(mutex);
//Do the reading
wait(mutex);
readcount--;
if(readcount == 0)
signal(wrt);
signal(mutex);
}

You can check out the following link  for the whole code.

https://github.com/sreepriya/Process-Synchronisation/blob/master/reader_writer.c

Synchronisation with Semaphores

Process synchronization is a major task of any operating system. And mutual exclusion is a major aspect of process synchronization. Mutual exclusion as the term says is the  ability to exclude all other processes from a course of action while one process is granted that ability. There are so many ways to conduct mutual exclusion in a system. It includes hardware and software solutions.
A semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment.

It can be considered as  a counter variable that gives the status of the resources. If the count is greater than zero, it shows the number of resources available free. If semaphore value is zero, the resource is busy or used by some other process.  Semaphores basically implements two kinds of functions : wait() and signal().

The following is a small description of how the process synchronization is done using semaphore.

#include<stdio.h>
#include<pthread.h>
#define MAX 10000
int count = 0;

int main(){
    void *add(void* ptr);
    pthread_t thread1,thread2;
//Creating two threads that calls the function add with argument
//as the thread number.
    pthread_create(&amp;thread1,NULL,add,(void*)1);
    pthread_create(&amp;thread2,NULL,add,(void*)2);
//Joining the threads with the main thread of the function
    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);
//Checking the output
    if(count != 2*MAX){
        printf("\n BOOM!! Count is : %d",count);
    }
//Expected output
    else 
        printf("\n Correct!! count is : %d",count);
    return 0;

}
//Function to increment count. Here count and MAX are 
//global variables. They form the critical section.
void* add(void *ptr){
    int i,tmp;
    int tnum=(int)ptr;
    for(i=0; i &lt; MAX ;i++){
        count++;
    }

}

The expected output is 20000 as the count will be incremented by both the processes. But the output is not 20000. I got the following :

 BOOM!! Count is : 13222

This happens because the critical section is not synchronized properly. Let us see how semaphore can be used to solve this.


#include<semaphore.h>
#include&lt<stdio.h>
#include&lt<pthread.h>
#define MAX 10000
int count = 0;
// Creating a semaphore called mutex
sem_t mutex;

int main(){
    void *add(void* ptr);
//initialising the semaphore to 1. The zero says that 
//there can be multiple threads.
    sem_init(&amp;mutex,0,1);
    pthread_t thread1,thread2;
    pthread_create(&amp;thread1,NULL,add,(void*)1);
    pthread_create(&amp;thread2,NULL,add,(void*)2);
    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);
    if(count != 2*MAX){
        printf("\n BOOM!! Count is : %d",count);
    }
    else 
        printf("\n Correct!! count is : %d",count);
    sem_destroy(&amp;mutex);
    return 0;
}
void* add(void *ptr){
    int i,tmp;
    int tnum=(int)ptr;
    for(i=0; i &lt; MAX ;i++){
//Calling wait() function on the semaphore. This blocks other 
//process to access the count variable when one 
//process is using it. 
        sem_wait(&amp;mutex);
        count++;
//Signal() given to mutex semaphore. Now other threads may access 
//the data inside.
        sem_post(&amp;mutex);
    }
}

When you run the code, you get the expected output as follows:

Correct!! count is : 20000

The semaphores don’t follow busy waiting technique. Instead it uses sleep and wakeup technique.