L-3.8: Semaphores | Wait, Signal Operation | Counting Semaphore | Example| Operating system

Name: L-3.8: Semaphores | Wait, Signal Operation | Counting Semaphore | Example| Operating system
Uploaded: 2018-02-28T09:25:35.000Z
Duration: 48 min 42 s

Semaphore in GATE and Competitive Exams

Introduction to Semaphore

The discussion begins with an introduction to semaphore, a tool used to prevent race conditions when synchronizing multiple processes.

Race conditions can lead to data loss, deadlocks, and other issues when multiple cooperative processes run simultaneously.

Definition and Types of Semaphore

A semaphore is defined as an integer variable utilized by concurrent processes for synchronization.

There are two main types of semaphores:

Counting Semaphore: Can take any integer value from negative infinity to positive infinity.

Binary Semaphore: Limited to two values, typically 0 and 1.

Critical Section and Operations

The critical section contains common code that multiple processes may access. Entry into this section requires executing specific entry and exit codes.

Key operations associated with semaphores include:

P() / Down / Wait: Used in the entry code.

V() / Up / Signal: Used in the exit code.

Understanding P() and V() Operations

The P() operation (or its synonyms Down/Wait) is executed first when a process attempts to enter the critical section.

If the critical section is free, multiple processes can attempt entry by executing the P() operation.

Example of Counting Semaphore Usage

An example illustrates how a counting semaphore works:

Initial semaphore value set at 3 allows three processes (P1, P2, P3) to enter the critical section sequentially without conflict.

Each time a process enters, it decrements the semaphore value. If it reaches zero or below during subsequent entries, further access will be denied until another process exits.

Understanding Semaphore Operations in Process Management

The Down Operation and Blocking Processes

When a new process (P4) attempts to enter the critical section, it decrements the semaphore value (S Value). If S Value is 0, it becomes -1, indicating that one more process has been blocked.

If S Value is less than 0 (e.g., -1), the process control block (PCB) of P4 is placed in a suspended list, effectively blocking it from entering the critical section.

The PCB contains essential information about the process such as its ID, priority, and open files. This data is stored when a process is blocked.

Similarly, if another process (P5) tries to enter while S Value remains negative (-2 after decrementing), it too will be added to the suspended list.

A semaphore value of -4 indicates that four processes are currently in a blocked state. If S Value reaches 0, no further processes can enter the critical section.

Unblocking Processes with Up Operation

When processes like P1, P2, or P3 exit the critical section, they must execute an exit code known as Up or V(), which increments S Value by 1.

For example, if P1 exits and runs Up code with an initial S Value of -2, it changes to -1. This indicates that there’s still one process in a blocked state.

After incrementing S Value to -1 and confirming it's still less than or equal to 0, one of the blocked processes must be selected from the suspended list for waking up.

The wake-up operation transitions a blocked process back into a ready queue but does not immediately place it into the critical section; this allows for re-attempting entry later.

Understanding Semaphore Operations in Process Management

Semaphore Value and Process Suspension

The value of the semaphore is initially set to 0. When checking if 0 is less than or equal to 0, it evaluates as true, allowing a process from the suspended list to be woken up.

The process P5 is selected from the suspended list and moved to the ready queue, enabling it to attempt entering the critical section.

Execution of Down and Up Operations

After processes P1 and P2 exit the critical section, only P3 remains inside. Now, P4 attempts to enter but must execute a Down operation first.

During its Down operation, if S value becomes -1 (indicating that another process is already in the critical section), P4 will be suspended again.

Exiting Critical Section

If P3 exits the critical section by executing an exit code that updates S value from 0 to 1, it confirms that no other processes are waiting since S was not negative.

With S updated to 1 after exiting, there are no processes in the suspended list; thus, no need for further operations when running Up.

Successful Entry into Critical Section

A semaphore value of 10 allows for up to 10 processes to enter the critical section successfully before any suspension occurs.

As each process enters, S decreases sequentially until reaching zero; once at zero, additional entries would lead to suspension of new requests.

Understanding Successful vs Unsuccessful Operations

An unsuccessful operation occurs when a process cannot enter due to being blocked (e.g., when trying a Down operation with S at zero).

If starting with an initial semaphore value of 10 and performing multiple operations (6 Down followed by 4 Up), one can calculate final values based on these actions.

Final Calculations on Semaphore Values

Starting with an initial semaphore value of 10: after executing six Down operations (reducing S by six), followed by four Up operations (increasing S by four), results in a final semaphore value of eight.

For another example where initial S is set at 17: after five Down operations reduce it significantly while three Up operations increase it slightly—culminating in a final value calculated as fourteen.

Key Takeaways on Semaphore Concepts