Semaphore is a synchronization mechanism that is commonly used in operating systems to manage access to shared resources among multiple processes or threads. In this tutorial, we will discuss the concept of semaphore in detail, including its definition, types, and examples.
📘 Definition of Semaphore
A semaphore is an integer variable that is used to control access to shared resources. It acts as a gatekeeper that allows only one process or thread to access the shared resource at a time. Semaphores are typically implemented as a data structure that contains a counter and a queue of waiting processes or threads.
📘 Types of Semaphore
There are two types of semaphore: binary semaphore and counting semaphore.
✔ Binary Semaphore
A binary semaphore can have only two values, 0 and 1. It is used to manage access to a single resource that can be accessed by only one process or thread at a time. A binary semaphore is also called a mutex (short for mutual exclusion).
Example
Consider a printer that can be used by only one process at a time. A binary semaphore can be used to control access to the printer. When a process wants to use the printer, it first acquires the semaphore. If the semaphore value is 0, it means the printer is in use, and the process is added to the queue of waiting processes. If the semaphore value is 1, the process can access the printer and sets the semaphore value to 0. When the process is done, it releases the semaphore, setting the value back to 1, allowing another process to access the printer.
Here's an example of how to use a binary semaphore in C:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
sem_t binary_semaphore;
void* thread_func(void* arg) {
sem_wait(&binary_semaphore); // acquire the semaphore
printf("Thread %d entered critical section\n", *((int*) arg));
sleep(1);
printf("Thread %d exiting critical section\n", *((int*) arg));
sem_post(&binary_semaphore); // release the semaphore
return NULL;
}
int main() {
pthread_t threads[5];
int thread_ids[5] = {1, 2, 3, 4, 5};
sem_init(&binary_semaphore, 0, 1); // initialize binary semaphore to 1
for (int i = 0; i < 5; i++) {
pthread_create(&threads[i], NULL, thread_func, &thread_ids[i]);
}
for (int i = 0; i < 5; i++) {
pthread_join(threads[i], NULL);
}
sem_destroy(&binary_semaphore); // destroy the semaphore
return 0;
}
Mutual Exclusion
Mutual exclusion refers to the property of a system where only one process can access a shared resource at a time. A binary semaphore is a synchronization primitive that can be used to implement mutual exclusion in a system.
In a binary semaphore, the value can be either 0 or 1. When a process wants to access a shared resource, it first checks the value of the binary semaphore. If the value is 0, the process can acquire the semaphore and access the resource. If the value is 1, the process must wait until the semaphore value becomes 0 before it can acquire the semaphore and access the resource.
To ensure mutual exclusion, a process should release the semaphore after it has finished accessing the shared resource. When a process releases the semaphore, it sets the value of the semaphore to 1, indicating that the resource is now available for other processes to access.
Here's an example of how mutual exclusion can be implemented using a binary semaphore:
e
// Initialize the binary semaphore to 1
binary_semaphore mutex = 1;
// Process A wants to access the shared resource
wait(mutex);
// Critical section - Process A accesses the shared resource\
signal(mutex);
// Process B wants to access the shared resource
wait(mutex);
// Critical section - Process B accesses the shared resource
signal(mutex);
In the example above, wait(mutex) and signal(mutex) are the operations used to acquire and release the binary semaphore, respectively. When a process calls wait(mutex), it blocks until the value of mutex becomes 0. Once the process has finished accessing the shared resource, it calls signal(mutex) to set the value of mutex back to 1, indicating that the resource is now available for other processes to access.
✔ Counting Semaphore
A counting semaphore can have any non-negative integer value. It is used to manage access to a pool of resources that can be accessed by multiple processes or threads at a time.
Example
Consider a database that can be accessed by multiple processes at the same time. A counting semaphore can be used to control access to the database. The semaphore value represents the number of available database connections. When a process wants to access the database, it first acquires the semaphore. If the semaphore value is greater than 0, it means there are available connections, and the process can access the database. The semaphore value is decremented, indicating that one connection has been used. When the process is done, it releases the semaphore, incrementing the value back, allowing another process to access the database.
Here's an example of how to use a counting semaphore in C:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
sem_t counting_semaphore;
void* thread_func(void* arg) {
sem_wait(&counting_semaphore); // acquire the semaphore
printf("Thread %d entered critical section\n", *((int*) arg));
sleep(1);
printf("Thread %d exiting critical section\n", *((int*) arg));
sem_post(&counting_semaphore); // release the semaphore
return NULL;
}
int main() {
pthread_t threads[5];
int thread_ids[5] = {1, 2, 3, 4, 5};
sem_init(&counting_semaphore, 0, 3);
// initialize counting semaphore to 3
for (int i = 0; i < 5; i++) {
pthread_create(&threads[i], NULL, thread_func, &thread_ids[i]);
}
for (int i = 0; i < 5; i++) {
pthread_join(threads[i], NULL);
}
sem_destroy(&counting_semaphore); // destroy the semaphore
return 0;
}
✔ Mutex Semaphore
A mutex semaphore is a type of semaphore that is used to provide mutual exclusion. It ensures that only one process or thread can access a shared resource at a time. Mutexes are often used to protect critical sections of code, which are parts of a program that must be executed atomically, meaning that they cannot be interrupted by another process or thread.
Here's an example of how to use a mutex semaphore in C:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
sem_t mutex_semaphore;
void* thread_func(void* arg) {
sem_wait(&mutex_semaphore); // acquire the semaphore
printf("Thread %d entered critical section\n", *((int*) arg));
sleep(1);
printf("Thread %d exiting critical section\n", *((int*) arg));
sem_post(&mutex_semaphore); // release the semaphore
return NULL;
}
int main() {
pthread_t threads[5];
int thread_ids[5] = {1, 2, 3, 4, 5};
sem_init(&mutex_semaphore, 0, 1); // initialize mutex semaphore to 1
for (int i = 0; i < 5; i++) {
pthread_create(&threads[i], NULL, thread_func, &thread_ids[i]);
}
for (int i = 0; i < 5; i++) {
pthread_join(threads[i], NULL);
}
sem_destroy(&mutex_semaphore); // destroy the semaphore
return 0;
}
Note that these are simple examples for demonstration purposes only, and real-world scenarios may require more complex implementations.
✔ Semaphore Operations
There are two basic operations that can be performed on semaphores: wait() and signal().
wait(): The wait() operation decrements the semaphore value. If the value is negative, the calling process or thread is added to the queue of waiting processes or threads.
signal(): The signal() operation increments the semaphore value. If there are any processes or threads waiting on the semaphore, one of them is selected and removed from the queue, and its wait operation is undone.
Example -
Here's an example where semaphore operations are performed in Python:
import threading
# Initialize semaphore with value 2
semaphore = threading.Semaphore(2)
# Define a function that will be executed by a thread
def print_numbers():
# Acquire semaphore
semaphore.acquire()
print(threading.current_thread().getName() + ' acquired semaphore')
for i in range(1, 6):
print(threading.current_thread().getName() + ': ' + str(i))
# Release semaphore
semaphore.release()
print(threading.current_thread().getName() + ' released semaphore')
# Create two threads that will execute the function
thread1 = threading.Thread(target=print_numbers)
thread2 = threading.Thread(target=print_numbers)
# Start the threads
thread1.start()
thread2.start()
# Wait for the threads to finish
thread1.join()
thread2.join()
In this example, a semaphore is initialized with a value of 2. Two threads are created that will execute the print_numbers() function. Before the function prints the numbers, it first acquires the semaphore by calling semaphore.acquire(). This blocks the thread if the semaphore value is zero, otherwise, it decrements the semaphore value by one and allows the thread to continue. After printing the numbers, the function releases the semaphore by calling semaphore.release(), which increments the semaphore value by one.
Since the semaphore value is initially 2, both threads can acquire the semaphore and execute the function simultaneously. However, if a third thread tries to acquire the semaphore while the other two threads are still holding it, it will be blocked until one of the other threads releases the semaphore. This ensures that no more than two threads can execute the print_numbers() function concurrently.
Semaphore is a synchronization mechanism that is used to manage access to shared resources in operating systems. Semaphores can be implemented as binary or counting semaphores, depending on the type of resources being managed. The wait() and signal() operations are used to acquire and release semaphores. Semaphores are an essential tool for preventing race conditions and ensuring correct synchronization among processes or threads.
📘 Advantages of Semaphore
Semaphores provide several advantages, including:
Synchronization: Semaphores provide a way to synchronize access to shared resources, ensuring that only one process or thread can access the resource at a time.
Prevent Deadlocks: Semaphores can be used to prevent deadlocks, which occur when two or more processes are blocked waiting for each other to release resources.
Efficiency: Semaphores are efficient, as they can be implemented using simple hardware or software constructs.
Flexibility: Semaphores can be used to manage access to any type of resource, including hardware devices, files, or network connections.
📘 Disadvantages of Semaphore
Despite their many advantages, semaphores also have some disadvantages, including:
Complexity: Semaphores can be complex to implement and debug, especially in large systems with many processes or threads.
Priority Inversion: In some cases, semaphores can cause priority inversion, where a low-priority process or thread holds a semaphore that is needed by a higher-priority process or thread.
Deadlocks: While semaphores can prevent deadlocks in some cases, they can also introduce deadlocks if not used correctly.
✔ Important Semaphore Questions
Question 1:
Consider a system with three processes P1, P2, and P3, each of which needs three resources to complete. The resources are initially allocated as shown below, where the numbers in the brackets represent the number of resources available in each instance of the resource. The processes are assumed to run concurrently.
Available resources: [1 1 2]
Allocation: [1 0 1] [1 2 0] [0 1 1]
Maximum needs: [2 1 1] [2 2 0] [1 1 1]
The system is currently deadlocked. To resolve the deadlock using a semaphore, how many semaphores are needed?
Answer : Two
Explanation: To resolve the deadlock using a semaphore, we can use two semaphores. Let's call them semaphore A and semaphore B. Initially, semaphore A is initialized to 1 and semaphore B is initialized to 0. Each process will wait on semaphore A before requesting resources and will signal semaphore B when it has finished using resources. If a process cannot get all the resources it needs, it will release the resources it has and wait on semaphore B. When a process releases resources, it signals semaphore A. The order in which the processes are scheduled does not matter as long as each process waits on semaphore A before requesting resources and signals semaphore B when it has finished using resources.
Question 2:
Consider a system with two processes P1 and P2 and two resources R1 and R2. The initial state is shown below, where the numbers in the brackets represent the number of resources available in each instance of the resource. The processes are assumed to run concurrently.
Available resources: [1 1]
Allocation: [1 0] [0 1]
Maximum needs: [1 1] [1 1]
Assume that the semaphore implementation of wait() and signal() operations are used to ensure mutual exclusion.
Which of the following statements is true?
A) This system is in a safe state.
B) This system is in an unsafe state.
C) This system may or may not be in a safe state.
D) This system is deadlocked.
Answer :
A) This system is in a safe state.
Explanation: In this system, each process needs only one resource, and there are two resources available. Therefore, it is impossible for both processes to be blocked waiting for resources at the same time, and the system is in a safe state. The semaphore implementation of wait() and signal() operations ensures mutual exclusion, which means that only one process can access a resource at a time. Therefore, there is no possibility of a deadlock in this system.
In conclusion, semaphores are an important synchronization mechanism in operating systems that can be used to manage access to shared resources. By understanding the types of semaphores and their operations, developers can design and implement efficient and effective synchronization strategies that ensure correct behavior of concurrent processes or threads.
Thanks for reading, and happy coding!
Understanding Semaphore in Operating Systems: Definition, Types, and Examples -> Understanding Deadlock Prevention and Booting Process in Operating Systems