Semaphore in OS-

Before you go through this article, make sure that you have gone through the previous article on Semaphores in OS.

We have discussed-

• A semaphore is a simple integer variable used to provide synchronization among the processes.
• There are mainly two types of semaphores-

In this article, we will discuss practice problems based on counting semaphores.

PRACTICE PROBLEMS BASED ON COUNTING SEMAPHORES IN OS-

Problem-01:

A counting semaphore S is initialized to 10. Then, 6 P operations and 4 V operations are performed on S. What is the final value of S?

Solution-

We know-

• P operation also called as wait operation decrements the value of semaphore variable by 1.
• V operation also called as signal operation increments the value of semaphore variable by 1.

Thus,

Final value of semaphore variable S

= 10 – (6 x 1) + (4 x 1)

= 10 – 6 + 4

= 8

Problem-02:

A counting semaphore S is initialized to 7. Then, 20 P operations and 15 V operations are performed on S. What is the final value of S?

Solution-

We know-

• P operation also called as wait operation decrements the value of semaphore variable by 1.
• V operation also called as signal operation increments the value of semaphore variable by 1.

Thus,

Final value of semaphore variable S

= 7 – (20 x 1) + (15 x 1)

= 7 – 20 + 15

= 2

Problem-03:

A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e. wait) on a counting semaphore S and invokes the V operation (i.e. signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?

1. -2
2. -1
3. 1
4. 2

Solution-

The given question may be pictorially represented as-

Initially, counting semaphore S is initialized with value 2.

Now, We have been asked the maximum possible value of x after all the processes complete execution.

Clearly,

• Processes W and X increments the value of x.
• Processes Y and Z decrements the value of x.

To obtain the maximum value of x, the processes must execute in such a way that-

• Only the impact of the processes W and X remains on the value of x.
• The impact of processes Y and Z gets lost on the value of x.

This is achieved as-

Step-01:

• Process W arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 1.
• It reads the value x = 0.
• It gets preempted.

Step-02:

• Process Y arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 0.
• It reads the value x = 0.
• It decrements the value of x by 2. Now, x = 0 – 2 = -2.
• It writes the value x = -2 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 1.
• Now, execution of process Y is completed.

Step-03:

• Process Z arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 0.
• It reads the value x = -2.
• It decrements the value of x by 2. Now, x = – 2 – 2 = -4.
• It writes the value x = -4 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 1.
• Now, execution of process Z is completed.

Step-04:

• Process W gets scheduled again.
• It resumes its execution from where it left.
• Before preemption it had already read the value x = 0.
• Now, it increments the value of x by 1. Now, x = 0 + 1 = 1.
• It writes the value x = 1 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 2.
• Now, execution of process W is completed.

Step-05:

• Process X arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 1.
• It reads the value x = 1.
• It increments the value of x by 1. Now, x = 1 + 1 = 2.
• It writes the value x = 2 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 2.
• Now, execution of process X is completed.

Thus,

• Final value of x = 2.
• This is the maximum possible value of x that can be achieved after executing all the 4 processes.
• Option (D) is correct.

Problem-04:

In problem-03, what is the minimum possible value of x after all processes complete execution?

1. -4
2. -2
3. 2
4. 4

Solution-

To obtain the minimum value of x, the processes must execute in such a way that-

• Only the impact of the processes Y and Z remains on the value of x.
• The impact of processes W and X gets lost on the value of x.

This can be achieved if processes execute in the following manner-

Step-01:

• Process Y arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 1.
• It reads the value x = 0.
• It gets preempted.

Step-02:

• Process W arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 0.
• It reads the value x = 0.
• It increments the value of x by 1. Now, x = 0 + 1 = 1.
• It writes the value x = 1 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 1.
• Now, execution of process W is completed.

Step-03:

• Process X arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 0.
• It reads the value x = 1.
• It increments the value of x by 1. Now, x = 1 + 1 = 2.
• It writes the value x = 2 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 1.
• Now, execution of process X is completed.

Step-04:

• Process Y gets scheduled again.
• It resumes its execution from where it left.
• Before preemption it had already read the value x = 0.
• Now, it decrements the value of x by 2. Now, x = 0 – 2 = -2.
• It writes the value x = -2 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 2.
• Now, execution of process Y is completed.

Step-05:

• Process Z arrives.
• It executes the wait(S) operation and the value of S decrements by 1. Now, S = 1.
• It reads the value x = -2.
• It decrements the value of x by 2. Now, x = -2 – 2 = -4.
• It writes the value x = -4 in the memory.
• It executes the signal(S) operation and the value of S increments by 1. Now, S = 2.
• Now, execution of process Z is completed.

Thus,

• Final value of x = -4.
• This is the minimum possible value of x that can be achieved after executing all the 4 processes.

Thus, Option (A) is correct.

To watch video solutions and practice other problems,

Watch this Video Lecture

Next Article- Binary Semaphores

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Process Synchronization-

Before you go through this article, make sure that you have gone through the previous article on Process Synchronization.

We have discussed-

• Process Synchronization provides a synchronization among the processes.
• Synchronization mechanisms allow the processes to access critical section in a synchronized manner.
• This avoids the inconsistent results.

Semaphores in OS-

• A semaphore is a simple integer variable.
• It is used to provide synchronization among multiple processes running concurrently.

Types of Semaphores-

There are mainly two types of semaphores-

1. Counting Semaphores
2. Binary Semaphores or Mutexes

In this article, we will discuss about Counting Semaphores.

Learn about Binary Semaphores.

Counting Semaphores-

A counting semaphore is implemented as-

struct semaphore
{
   int value;
   Queue type L;
}

Wait (semaphore s)
{
   s.value = s.value - 1;
   if (s.value < 0)
   {
      put process (PCB) in L;
      sleep();
   }
   else
      return;
}

Signal (semaphore s)
{
   s.value = s.value + 1;
   if (s.value <=0 )
   {
       select a process (PCB) from L;
       wake up();
   }
}

Explanation-

The above implementation of counting semaphore has been explained in the following points-

Point-01:

A counting semaphore has two components-

• An integer value
• An associated waiting list (usually a queue)

Point-02:

The value of counting semaphore may be positive or negative.

• Positive value indicates the number of processes that can be present in the critical section at the same time.
• Negative value indicates the number of processes that are blocked in the waiting list.

Point-03:

• The waiting list of counting semaphore contains the processes that got blocked when trying to enter the critical section.
• In waiting list, the blocked processes are put to sleep.
• The waiting list is usually implemented using a queue data structure.
• Using a queue as waiting list ensures bounded waiting.
• This is because the process which arrives first in the waiting queue gets the chance to enter the critical section first.

Point-04:

• The wait operation is executed when a process tries to enter the critical section.
• Wait operation decrements the value of counting semaphore by 1.

Then, following two cases are possible-

Case-01: Counting Semaphore Value >= 0

• If the resulting value of counting semaphore is greater than or equal to 0, process is allowed to enter the critical section.

Case-02: Counting Semaphore Value < 0

• If the resulting value of counting semaphore is less than 0, process is not allowed to enter the critical section.
• In this case, process is put to sleep in the waiting list.

Point-05:

• The signal operation is executed when a process takes exit from the critical section.
• Signal operation increments the value of counting semaphore by 1.

Then, following two cases are possible-

Case-01: Counting Semaphore <= 0

• If the resulting value of counting semaphore is less than or equal to 0, a process is chosen from the waiting list and wake up to execute.

Case-02: Counting Semaphore > 0

• If the resulting value of counting semaphore is greater than 0, no action is taken.

Point-06:

• By adjusting the value of counting semaphore, the number of processes that can enter the critical section can be adjusted.
• If the value of counting semaphore is initialized with N, then maximum N processes can be present in the critical section at any given time.

Point-07:

• To implement mutual exclusion, the value of counting semaphore is initialized with 1.
• It ensures that only one process can be present in the critical section at any given time.

Point-08:

In a system,

• Consider n units of a particular non-shareable resource are available.
• Then, n processes can use these n units at the same time.
• So, the access to these units is kept in the critical section.
• The value of counting semaphore is initialized with ‘n’.
• When a process enters the critical section, the value of counting semaphore decrements by 1.
• When a process exits the critical section, the value of counting semaphore increments by 1.

Point-09:

• Other names by which wait operation may be referred : Down operation, P operation.
• Other names by which signal operation may be referred : Up operation, V operation, Release operation.

To gain better understanding about Counting Semaphores,

Watch this Video Lecture

Next Article- Practice Problems On Counting Semaphores

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.