Semaphores

Semaphores are a fundamental concept in operating systems, used for process synchronization, particularly in concurrent programming scenarios where multiple processes or threads access shared resources. They were introduced by Dutch computer scientist Edsger Dijkstra in the late 1960s.

Definition: A semaphore is essentially a variable or abstract data type used to control access to a common resource by multiple processes or threads in a concurrent system. It acts as a signaling mechanism for processes or threads to coordinate their activities and avoid race conditions.

Types of Semaphores: 

There are two primary types of semaphores:

Binary Semaphores: Also known as mutex (mutual exclusion) semaphores, these have two states: 0 and 1. They are typically used to control access to a single resource, ensuring that only one process or thread can access the resource at a time.

Counting Semaphores: These can have an integer value greater than or equal to zero. They are used to control access to multiple instances of a resource or a pool of resources. Counting semaphores allow for more complex synchronization schemes.

Operations on Semaphores: Semaphores support two primary operations:

Wait (P) Operation: This operation decrements the value of the semaphore. If the resulting value is negative, the process or thread executing the wait operation is blocked until the semaphore's value becomes non-negative.

Signal (V) Operation: This operation increments the value of the semaphore. If there are processes or threads blocked on the semaphore, one of them is woken up.

Use Cases: Semaphores are widely used in operating systems and concurrent programming for various purposes, including:

Synchronizing access to shared resources such as files, memory, and devices.

Implementing producer-consumer problems.
Coordinating multiple processes or threads to avoid race conditions.
Implementing critical sections and ensuring mutual exclusion.

Implementation: Semaphores can be implemented using various mechanisms, such as hardware instructions, software constructs, or a combination of both. In most modern operating systems, semaphores are implemented as part of the operating system's kernel and are accessible through system calls.

Conclusion: Semaphores play a crucial role in ensuring proper synchronization and coordination in operating systems and concurrent programming. By using semaphores effectively, developers can design robust and efficient concurrent systems while avoiding issues such as race conditions and deadlock.

Here's a simple C program that demonstrates the use of semaphores for synchronizing access to a shared resource between two threads. In this example, we'll use semaphores to control access to a shared counter variable:

#include <stdio.h>

#include <pthread.h>

#include <semaphore.h>

#define NUM_THREADS 2

int counter = 0; // Shared counter variable

sem_t semaphore; // Semaphore for synchronization

// Thread function to increment the counter

void* increment_counter(void* arg) {

    for (int i = 0; i < 5; i++) {

        sem_wait(&semaphore); // Wait on the semaphore P

        counter++; // Critical section: Increment the counter

        printf("Counter value: %d\n", counter);

        sem_post(&semaphore); // Release the semaphore V

    }

    pthread_exit(NULL);

}

int main() {

    pthread_t threads[NUM_THREADS];

    // Initialize the semaphore with initial value 1

    sem_init(&semaphore, 0, 1);

    // Create two threads to increment the counter

    for (int i = 0; i < NUM_THREADS; i++) {

        pthread_create(&threads[i], NULL, increment_counter, NULL);

    }

    // Join the threads

    for (int i = 0; i < NUM_THREADS; i++) {

        pthread_join(threads[i], NULL);

    }

    // Destroy the semaphore

    sem_destroy(&semaphore);

    return 0;

}

Counter value: 1

Counter value: 2

Counter value: 3

Counter value: 4

Counter value: 5

Counter value: 6

Counter value: 7

Counter value: 8

Counter value: 9

Counter value: 10

Note: you can run this code without semaphores and see how the race condition is affecting.

Remember to compile this program with the following command: 

gcc your_program.c -lpthread -lrt
 

Explanation:

• We define a shared counter variable counter and a semaphore semaphore.
• The increment_counter function is the thread function. It increments the counter in a loop for a certain number of iterations.
• Inside the loop, threads first wait on the semaphore using sem_wait to enter the critical section.
• Inside the critical section, the counter is incremented and printed.
• After completing the critical section, threads release the semaphore using sem_post.
• In the main function, we initialize the semaphore, create two threads using pthread_create, and join them using pthread_join.
• Finally, we destroy the semaphore using sem_destroy.

This program ensures that only one thread can access the critical section (incrementing the counter) at a time, thus preventing race conditions and ensuring that the counter is incremented correctly.

Here's the syntax of pthread_create:
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);
thread: Pointer to a pthread_t variable where the thread identifier will be stored.

attr: Pointer to a pthread_attr_t structure specifying various attributes for the thread (can be NULL for default attributes).

start_routine: Pointer to the function that will be executed by the thread.
arg: Pointer to the argument that will be passed to the start_routine function.

Here's the syntax of pthread_join:
int pthread_join(pthread_t thread, void **value_ptr);
thread: The thread to wait for. It is of type pthread_t.
value_ptr: Pointer to a location where the exit status of the thread will be stored. It is of type void**.

The return value of pthread_join indicates success (0) or an error code if there was a problem waiting for the thread.

Here is the syntax of sem_init:

int sem_init(sem_t *sem, int pshared, unsigned int value);

sem: This is a pointer to a semaphore object of type sem_t. It points to the semaphore that you want to initialize.

pshared: This argument specifies whether the semaphore is shared between processes or not. If pshared is 0, the semaphore is shared between threads of the same process (local to the process). If pshared is nonzero, the semaphore can be shared between multiple processes. However, in POSIX systems, interprocess semaphores are not typically supported, so you should always pass 0 for this argument.

value: This is the initial value of the semaphore. It specifies the maximum number of threads that can concurrently access the critical section protected by the semaphore. For binary semaphores (mutexes), which allow only one thread to access the critical section at a time, you typically initialize the semaphore with the value 1.

sem_destroy:
int sem_destroy(sem_t *sem);
sem: This is a pointer to the semaphore object of type sem_t that you want to destroy.

This function is used to destroy a semaphore that was previously initialized using sem_init. After calling sem_destroy, the semaphore object becomes uninitialized, and it should not be used further without being re-initialized.

Return Value:Both sem_init and sem_destroy return 0 upon success. If there's an error, they return -1, and errno is set to indicate the error.

sem_wait and sem_post are functions used to perform operations on POSIX semaphores. They are crucial for synchronizing access to shared resources in multithreaded programs. 

sem_wait:

int sem_wait(sem_t *sem);

sem: This is a pointer to the semaphore object of type sem_t on which the wait operation is performed.

sem_wait decrements (locks) the semaphore pointed to by sem. If the semaphore's value is greater than zero, the value of the semaphore is decremented, and the function returns immediately, allowing the calling thread to proceed to the critical section. If the semaphore's value is zero, sem_wait blocks the calling thread until the semaphore's value becomes greater than zero. Once the thread wakes up and the semaphore's value is decremented, it is allowed to proceed.

sem_post:
int sem_post(sem_t *sem);

sem: This is a pointer to the semaphore object of type sem_t on which the post operation is performed.

sem_post increments (unlocks) the semaphore pointed to by sem. If there are threads blocked on this semaphore, one of them is woken up, and its wait operation (sem_wait) is completed. If there are no threads blocked, the value of the semaphore is simply incremented, allowing subsequent calls to sem_wait to proceed without blocking.

Return Value:

Both sem_wait and sem_post return 0 upon success. If there's an error, they return -1, and errno is set to indicate the error.

//*********************************************************

// C program Implementation - binary semaphore

//*********************************************************

#include <stdio.h>

#include <pthread.h>

#include <semaphore.h>

// Define a shared resource and a binary semaphore

int shared_resource = 0;

sem_t mutex;

// Function to simulate accessing the shared resource

void* access_resource(void* thread_name) {

    char* name = (char*) thread_name;

    printf("%s is trying to access the resource.\n", name);

    // Acquire the semaphore (P operation)

    sem_wait(&mutex);

    // Critical section: Accessing the shared resource

    printf("%s has acquired the resource and is performing some operation.\n", name);

    // Simulating some work being done by the thread

    for (int i = 0; i < 3; i++) {

        printf("%s is working...\n", name);

        shared_resource+=1;

    }

    printf("%s has finished its operation.\n", name);

    // Release the semaphore (V operation)

    sem_post(&mutex);

    printf("%s has released the resource.\n", name);

    pthread_exit(NULL);

}

int main() {

    // Initialize the semaphore

    sem_init(&mutex, 0, 1); // Initial value of 1

    // Create threads to access the shared resource

    pthread_t thread1, thread2;

    pthread_create(&thread1, NULL, access_resource, (void*)"Thread 1");

    pthread_create(&thread2, NULL, access_resource, (void*)"Thread 2");

    // Join threads

    pthread_join(thread1, NULL);

    pthread_join(thread2, NULL);

    // Destroy the semaphore

    sem_destroy(&mutex);

    printf("All threads have finished.\n");

    printf("Shared Resource Value=%d",shared_resource);

    return 0;

}

 

//**************************************************************************

In this example, we’ll simulate a scenario where two threads increment and decrement a shared integer value using semaphores for synchronization.

• We create a shared integer variable sharedValue.
• Two threads (incThread and decThread) increment and decrement sharedValue.
• The semaphore ensures that only one thread can modify sharedValue at a time.
• sem_wait blocks the thread if the semaphore value is 0, and sem_post increments the semaphore value. 

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

int sharedValue = 0;
sem_t semaphore;

void* incrementThread(void* arg) {
    sem_wait(&semaphore); // Wait for semaphore
    sharedValue++;
    printf("Incremented: %d\n", sharedValue);
    sem_post(&semaphore); // Signal semaphore
    pthread_exit(NULL);
}

void* decrementThread(void* arg) {
    sem_wait(&semaphore); // Wait for semaphore
    sharedValue--;
    printf("Decremented: %d\n", sharedValue);
    sem_post(&semaphore); // Signal semaphore
    pthread_exit(NULL);
}

int main() {
    sem_init(&semaphore, 0, 1); // Initialize semaphore

    pthread_t incThread, decThread;
    pthread_create(&incThread, NULL, incrementThread, NULL);
    pthread_create(&decThread, NULL, decrementThread, NULL);

    pthread_join(incThread, NULL);
    pthread_join(decThread, NULL);

    sem_destroy(&semaphore); // Destroy semaphore

    return 0;
}

 

Incremented: 1
Decremented: 0