In the vast digital landscape where software systems communicate and execute concurrently, the need for synchronization arises to ensure smooth and reliable operation. Among the myriad of tools available for this purpose, one stalwart stands out: the semaphore. Semaphores, though conceptually simple, play a crucial role in coordinating access to shared resources in multi-threaded environments. A semaphore is a data structure consisting of an integer and the atomic usage operations “reserve/try” and “release”. It is particularly suitable for managing limited (countable) resources that are to be accessed by several processes or threads, such as producers and consumers, as well as for coordinating asynchronous processes. In contrast to a lock or mutex, the activity carriers that “reserve” and “release” do not have to be identical.
How Semaphor Works
Invented by Dutch computer scientist Edsger Dijkstra in the 1960s, the semaphore is a synchronization primitive used to control access to a shared resource by multiple processes or threads. At its core, a semaphore is a non-negative integer variable accompanied by two atomic operations: wait() (also known as P() or down()) and signal() (also known as V() or up()).
In most cases, the integer (counter) is initialized at the start of the semaphore with the numerical value of the maximum available resources or the maximum number of processes that can use the resource at the same time. A process that wants to access the resource must first call the “Reserve/Try” operation, and then, if it no longer needs the resource, the “Release” operation. For each reservation, the counter is counted down by 1, and when it is released, it is increased again by 1. The counter must not fall below 0: If a reservation is made at 0, the reserving process waits until another process has released resources. There are also implementations that count negatively. This can be used to show how many processes are waiting for release.
---
Semaphores can be used in programming for process synchronization, i.e. to solve tasks in which the parallel execution of several processes/threads requires a timing of the executions. They are generally used to create an order in which many threads share these scarce elements for a limited number of resources (e.g. resource: “CPU core”, count: 4). This can also be used to encapsulate access to shared data (resource: “access right to the data”, number: only one at a time). Semaphors can also be used for communication between threads. They then usually serve as counters for available information packets. Here, the semaphore is started with “0 packets available”, and then counted up (and down to 0 again).
Wait (P) Operation: When a process wishes to access a shared resource, it must first execute the wait() operation on the semaphore associated with that resource. If the semaphore value is positive, indicating that the resource is available, the process decrements the semaphore value and proceeds with accessing the resource. If the semaphore value is zero or negative, the process is blocked until the semaphore value becomes positive again.
Signal (V) Operation: After a process finishes using a shared resource, it executes the signal() operation on the semaphore to indicate that the resource is now available. This increments the semaphore value, potentially unblocking other processes waiting to access the resource.
Interactions of parallel processes
In the parallel or temporally interlinked execution of processes, implicit or explicit interactions occur.
With implicit interactions, a process is not aware that the execution of actions is influencing another process. This is the case, for example, if a process calls a system service that the operating system cannot immediately process completely because other processes have occupied the required resources. The process cannot continue its actions until the system service has been executed. Here, the process interaction becomes visible as a blocking function call. A process does not have to and cannot take special precautions against blockage due to implicit interactions.
Explicit interactions between processes are:
Competition
Processes compete with each other when they simultaneously access a resource (e.g., memory structure, connection, device) that is only available in limited numbers and where the use of a copy is only possible exclusively by a process, otherwise erroneous results or inconsistent states will occur, i.e., if there are critical sections in the programs of the processes.
Cooperation
Processes cooperate when they consciously coordinate their actions, e.g. because they are in a client/contractor relationship.
Both reserving and releasing must be atomic operations. If a reservation cannot be satisfied, it can simply block it (obtaining the resource via race condition among those waiting), the semaphore can queue (usually blocking) or reject it (non-blocking). Often, only one copy of the equipment is available (so-called mutual exclusion), the semaphore then causes the timing of the process actions to be coordinated. In the event of a competitive situation, a somehow designed sequentialization of the execution (of the critical sections) ensures that the equipment is not used by several processes in an arbitrary way. In the case of a cooperation situation, sequentialization is also used to ensure that the processes work together (e.g., that a contractor does not already try to work on something even though the customer has not yet placed an order).
Applications of Semaphores
Concurrency Control: Semaphores are widely used to manage critical sections of code where multiple threads must not execute simultaneously to prevent race conditions and ensure data integrity.
Resource Allocation: In scenarios where resources such as shared memory, files, or hardware devices need to be accessed by multiple processes, semaphores ensure orderly access and prevent conflicts.
Producer-Consumer Problem: Semaphores provide an elegant solution to synchronization problems like the producer-consumer scenario, where multiple producers generate data and multiple consumers consume it concurrently.
Thread Synchronization: In multi-threaded applications, semaphores synchronize the execution of threads, enabling them to cooperate and coordinate their activities effectively.
An implementation of the semaphore mechanisms is conceptually located in the operating system, as it must work closely with the process management. Indivisibility can then be achieved on monoprocessor systems, for example, by means of an interruption lock. In the case of multiprocessor systems, the instruction sequences of the semaphore operations must be bracketed by spinlocks. A realization by the operating system also makes it possible for several processes with their actually disjoint address spaces to share a semaphore.
If semaphores are offered by a thread package that runs in the user address space (user-level threads), the realization of indivisibility is more complex. It has to take into account any interruptions and depends on what information about user-level threads is available in the core.
Challenges and Best Practices
While semaphores are powerful synchronization tools, their misuse can lead to subtle bugs such as deadlocks and livelocks. Careful design and implementation are crucial to ensure the correctness and efficiency of semaphore-based synchronization mechanisms. Here are some best practices:
Avoiding Deadlocks: Always acquire semaphores in the same order to prevent circular wait conditions, and ensure that semaphores are released after use to avoid resource starvation.
Limiting Critical Sections: Keep critical sections guarded by semaphores as short as possible to minimize contention and improve performance.
Resource Management: Properly initialize and manage semaphore counts to prevent underflow or overflow situations, which can lead to unexpected behavior.
Code Examples of Semaphores
The examples are with C and C++. Below is an example of how counting semaphores can be implemented and used in C language using the POSIX threads library (pthread.h):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <stdio.h> #include <pthread.h> #include <semaphore.h> #define NUM_THREADS 5 sem_t semaphore; void* thread_function(void* arg) { // Wait on the semaphore sem_wait(&semaphore); // Critical section printf("Critical section protected by semaphore\n"); // Signal the semaphore sem_post(&semaphore); return NULL; } int main() { pthread_t threads[NUM_THREADS]; // Initialize semaphore with an initial value sem_init(&semaphore, 0, 2); // Allow 2 threads to access the critical section simultaneously // Create threads for (int i = 0; i < NUM_THREADS; ++i) { pthread_create(&threads[i], NULL, thread_function, NULL); } // Join threads for (int i = 0; i < NUM_THREADS; ++i) { pthread_join(threads[i], NULL); } // Destroy semaphore sem_destroy(&semaphore); return 0; } |
Below is an example of a counting semaphore implemented in C++ using the thread and mutex standard libraries:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream> #include <thread> #include <mutex> #include <condition_variable> class Semaphore { public: Semaphore(int count) : count_(count) {} void acquire() { std::unique_lock<std::mutex> lock(mutex_); while (count_ == 0) { // Wait until count is nonzero condition_.wait(lock); } count_--; } void release() { std::lock_guard<std::mutex> lock(mutex_); count_++; condition_.notify_one(); } private: std::mutex mutex_; std::condition_variable condition_; int count_; }; Semaphore semaphore(2); // Allow 2 threads to access the critical section simultaneously void thread_function(int id) { semaphore.acquire(); // Critical section std::cout << "Thread " << id << " enters the critical section" << std::endl; std::this_thread::sleep_for(std::chrono::seconds(1)); // Simulate some work semaphore.release(); } int main() { std::thread threads[5]; // 5 threads will be created // Create threads for (int i = 0; i < 5; ++i) { threads[i] = std::thread(thread_function, i + 1); } // Join threads for (int i = 0; i < 5; ++i) { threads[i].join(); } return 0; } |
The Semaphore class provides acquire() and release() methods to acquire and release the semaphore, respectively.
In the main() function, a Semaphore object is created with an initial count of 2, allowing two threads to access the critical section simultaneously.
The thread_function simulates a critical section by printing a message indicating that a thread has entered the critical section and then sleeps for 1 second to simulate some work.
Each thread acquires the semaphore before entering the critical section and releases it after leaving the critical section.
The main() function creates five threads that execute the thread_function, simulating concurrent access to the critical section.
In ESP-IDF (Espressif IoT Development Framework) for ESP32 development, you can implement a counting semaphore using the FreeRTOS semaphore API, which is built into the framework. Below is an example of how you can create and use a counting semaphore in C for ESP-IDF:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <stdio.h> #include "freertos/FreeRTOS.h" #include "freertos/task.h" #include "freertos/semphr.h" SemaphoreHandle_t semaphore; void task1(void *pvParameters) { while (1) { if (xSemaphoreTake(semaphore, portMAX_DELAY) == pdTRUE) { // Critical section printf("Task 1 enters the critical section\n"); vTaskDelay(pdMS_TO_TICKS(1000)); // Simulate some work printf("Task 1 exits the critical section\n"); xSemaphoreGive(semaphore); } vTaskDelay(pdMS_TO_TICKS(1000)); // Delay between accesses } } void task2(void *pvParameters) { while (1) { if (xSemaphoreTake(semaphore, portMAX_DELAY) == pdTRUE) { // Critical section printf("Task 2 enters the critical section\n"); vTaskDelay(pdMS_TO_TICKS(1000)); // Simulate some work printf("Task 2 exits the critical section\n"); xSemaphoreGive(semaphore); } vTaskDelay(pdMS_TO_TICKS(1000)); // Delay between accesses } } void app_main() { semaphore = xSemaphoreCreateCounting(2, 2); // Allow 2 tasks to access the critical section simultaneously xTaskCreatePinnedToCore(task1, "Task 1", 4096, NULL, 1, NULL, 0); // Create Task 1 xTaskCreatePinnedToCore(task2, "Task 2", 4096, NULL, 1, NULL, 1); // Create Task 2 } |
We include necessary FreeRTOS headers for semaphore and task handling.
We define two tasks, task1 and task2, which simulate concurrent tasks accessing a critical section.
Each task attempts to take the semaphore using xSemaphoreTake() before entering the critical section and releases it afterward using xSemaphoreGive().
The app_main function initializes the semaphore using xSemaphoreCreateCounting() and creates the tasks using xTaskCreatePinnedToCore().
The semaphore is created with an initial count of 2 and a maximum count of 2, allowing two tasks to access the critical section simultaneously.
In Java, you can implement a counting semaphore using the Semaphore class from the java.util.concurrent package.
In Python, you can implement a counting semaphore using the threading module, which provides synchronization primitives such as Semaphore.
In Ruby, you can implement a counting semaphore using its built-in synchronization primitives, such as Mutex and ConditionVariable.
PHP, being a scripting language primarily used for web development, doesn’t have built-in support for low-level concurrency primitives like counting semaphores. However, you can achieve similar synchronization behavior using higher-level constructs like mutexes and condition variables.
