Semaphore

Introduction

As all threads share the same address space and they have access to the same data and variables. When two or more threads tries to update a global variable at the same time, their actions may overlap which can cause the global state of that variable to be incorrectly modified. This scenario may occur rarely but can result in very dangerous bug and can result in system failure. Semaphore is one way to solve this problem.

The semaphore is a synchronization technique used in programming to protect shared resources (e.g., variables, data structures, memory segment etc.) from access by multiple threads at the same time.

In simple words, a semaphore acts like a traffic light at an intersection. It allows one process to access a shared resource at a time and prevents other processes from accessing it until it is released.

A semaphore is similar to an integer variable, but its operations (increment and decrement) are guaranteed to be atomic. This means that multiple threads can increment or decrement the semaphore without interference. Conventionally, a semaphore with a value of zero is considered “locked” or “in use,” while a positive value indicates availability. Semaphores never have a negative value.

When the value of semaphore is 0 then it means that all resources are currently in use. If any process or thread that wants to access the resource will have to wait until a resource becomes available. In other words, a semaphore with a value of 0 is said to be “locked” or “in use.”

When the value of semaphore is 1 or greater, it means that at least one resource is available, and a process or thread can access it immediately. For example, if a semaphore is initialized with a value of 1, it means that only one process or thread can access the resource at a time, but the resource is immediately available for use. If the semaphore value is greater than 1, it means that multiple resources are available, and multiple processes or threads can access them simultaneously.

Example

Let us now understand the semaphore with some real-life examples:

• Printer: Multiple users may request to print a document at the same time. To avoid conflicts and ensure that the printer is used efficiently, a semaphore can be used to regulate access to the printer. When a user wants to print a document, they must acquire the semaphore, which indicates that the printer is available. Once the document is printed, the semaphore is released, allowing another user to access the printer.

• Database Management: In a database management system, multiple users may need to access the same database simultaneously. To ensure that the database is accessed in a consistent and reliable manner, a semaphore can be used to regulate access to the database. Each user must acquire the semaphore before accessing the database, and release it once they’re finished, ensuring that no two users can access the database simultaneously and that the data remains consistent.

Let us now try to understand semaphore using a code.

Problem: There are two users who are continuously printing numbers. User A is printing odd numbers while user B is printing even numbers. We want that the printer should print the numbers in sequence.

Solution: As user A & B have common resource i.e. printer so we need to add a locking mechanism on printer. If we use a semaphore then there is possibility that the same user might get the same semaphore again so, we will take two semaphores here.

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

sem_t sem_even;
sem_t sem_odd;

void* printEven(void* arg) {
    int i;
    for (i = 2; i <= 100; i += 2) {
        // Wait for odd to complete before printing even
        sem_wait(&sem_even);  // Wait for even semaphore to be available
        printf("%d ", i);
        // Signal odd to print next
        sem_post(&sem_odd);  Signal to odd semaphore that even is done
    }
    pthread_exit(NULL);
}

void* printOdd(void* arg) {
    int i;
    for (i = 1; i <= 99; i += 2) {
        // Wait for even to complete before printing odd
        sem_wait(&sem_odd); // Wait for odd semaphore to be available
        printf("%d ", i);
        // Signal even to print next
        sem_post(&sem_even);  Signal to even semaphore that odd is done
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t thread1, thread2;

    // Initialize semaphores
    sem_init(&sem_even, 0, 0);
    sem_init(&sem_odd, 0, 1);  // Odd will starts first, so initialize it with 1

    // Create threads
    pthread_create(&thread1, NULL, printEven, NULL);
    pthread_create(&thread2, NULL, printOdd, NULL);

    // Wait for threads to complete
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    // Destroy semaphores
    sem_destroy(&sem_even);
    sem_destroy(&sem_odd);

    return 0;
}

In this code, we define two semaphores called sem_even and sem_odd, one for each user. We initialize sem_odd to 1 and sen_even to 0, indicating that user A can start printing first.

In the printOdd() function, we check for the sem_odd semaphore. As during initialization, we have initialized it with 1 so it will get the semaphore. It will print and give signal to sem_even.

IN printEven() function, we will check the sem_even semaphore first. It will be 0 and will become 1 only when user A have printed some odd number. As soon as user B gets the signal using sem_even then it will print an even number and will give signal to user A.

Types of semaphore

Semaphore are of two types a). Binary Semaphore b). Counting Semaphore. Lets discuss them in detail

Binary Semaphore: A binary semaphore is a type of semaphore that has only two states: 0 and 1. It is often used to control access to a shared resource in a concurrent system, where the resource can be accessed by only one process or thread at a time. When the semaphore is in the “locked” state (0), it means that the resource is currently in use and cannot be accessed by any other process or thread. When the semaphore is in the “unlocked” state (1), it means that the resource is available and can be accessed by a process or thread. Below are two examples

1. Traffic light: A traffic light can be seen as a binary semaphore, where the “red” signal represents the “locked” state and the “green” signal represents the “unlocked” state. When the traffic light is red, it means that the intersection is currently in use by another vehicle and cannot be accessed by any other vehicle. When the traffic light turns green, it means that the intersection is available and can be accessed by a vehicle.
2. Elevator: An elevator can be controlled using a binary semaphore, where the “occupied” state represents the “locked” state and the “unoccupied” state represents the “unlocked” state. When the elevator is occupied and moving, it cannot be accessed by any other person. When the elevator arrives at a floor and the doors open, it is in the “unlocked” state and can be accessed by a person to enter and use the elevator. Once the doors close and the elevator starts moving, it enters the “locked” state again until it reaches the next floor.

Counting Semaphore: A counting semaphore is a synchronization mechanism that allows multiple threads to access a shared resource in a controlled way. Unlike binary semaphores, counting semaphores can have a value greater than 1, which means that they can allow multiple threads to access the resource simultaneously, up to a maximum limit specified by the semaphore’s value. Here are two examples of counting semaphores:

1. Connection Pool: In a database system, a connection pool is a cache of database connections that can be reused by multiple threads. To ensure that the maximum number of connections is not exceeded, a counting semaphore can be used to limit the number of concurrent connections. The semaphore value is set to the maximum number of connections that can be created, and each time a thread requests a connection, the semaphore is decremented. If the semaphore value is zero, the thread will block until a connection becomes available again. When a connection is released, the semaphore is incremented, allowing another thread to acquire the connection.
2. Print Queue: In a computer network, a print queue is a list of print jobs waiting to be processed by a printer. To prevent the printer from being overwhelmed with too many print jobs at once, a counting semaphore can be used to limit the number of print jobs that can be processed simultaneously. The semaphore value is set to the maximum number of print jobs that the printer can handle, and each time a print job is submitted to the queue, the semaphore is decremented. If the semaphore value is zero, the print job will be blocked until another job finishes printing and the semaphore value is incremented again.

References:

• Wikipedia -Semaphore

Related Post:

• Design Patterns for Embedded C/C++
• Spin Lock