Semaphores (counting and binary) in Operating Systems - Step-by-Step Execution

Concept Flow - Semaphores (counting and binary)

Start

↓

Check semaphore value

↓

Decrement semaphore

→Allow access

↓

Block process

→Wait for semaphore increment

↓

End

The semaphore controls access by checking its value. If positive, it decrements and allows access; if zero, the process waits until the semaphore is incremented.

Execution Sample

Operating Systems

semaphore = 2
process1: wait(semaphore)
process2: wait(semaphore)
process3: wait(semaphore)
process1: signal(semaphore)

Three processes try to enter a critical section controlled by a semaphore initialized to 2.

Analysis Table

Step	Process	Semaphore Value Before	Action	Semaphore Value After	Process State
1	process1	2	wait: value>0, decrement	1	enters critical section
2	process2	1	wait: value>0, decrement	0	enters critical section
3	process3	0	wait: value=0, blocks	0	blocked, waiting
4	process1	0	signal: increment	1	exits critical section
5	process3	1	unblocked, wait: value>0, decrement	0	enters critical section

💡 All processes have entered or are waiting; semaphore controls access by blocking when value is zero.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
semaphore	2	1	0	0	1	0
process1 state	waiting	in critical section	in critical section	in critical section	exited	exited
process2 state	waiting	in critical section	in critical section	in critical section	in critical section	in critical section
process3 state	waiting	waiting	waiting (blocked)	waiting (blocked)	waiting (blocked)	in critical section

Key Insights - 3 Insights

Why does process3 block at step 3 even though it called wait?

At step 3 in the execution_table, the semaphore value is 0, so process3 cannot decrement it and must wait until another process signals (increments) the semaphore.

What happens to the semaphore value when a process signals?

As shown at step 4, signaling increments the semaphore value by 1, allowing blocked processes to proceed.

How does a binary semaphore differ from a counting semaphore in this flow?

A binary semaphore only allows values 0 or 1, so it controls access for one process at a time, while a counting semaphore can have values greater than 1 to allow multiple simultaneous accesses.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the semaphore value and what happens to process3?

A Semaphore is 2; process3 enters critical section

B Semaphore is 0; process3 blocks waiting

C Semaphore is 1; process3 enters critical section

D Semaphore is 0; process3 exits

💡 Hint

Check the 'Semaphore Value Before' and 'Process State' columns at step 3 in execution_table.

At which step does the semaphore value increase?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look for the 'signal' action in the 'Action' column in execution_table.

If the semaphore was initialized to 1 instead of 2, what would happen at step 2?

A process2 would block waiting

B process2 would enter critical section

C process3 would enter critical section

D semaphore value would be 2

💡 Hint

Refer to the semaphore value changes in variable_tracker and how wait works when value is 0.

Concept Snapshot

Semaphore controls access to resources.
Counting semaphore: value ≥ 0, allows multiple accesses.
Binary semaphore: value 0 or 1, allows single access.
wait() decrements if >0, else blocks.
signal() increments and may unblock waiting processes.

Full Transcript

Semaphores are tools to control access to shared resources. They hold a value representing available resources. When a process wants access, it calls wait(). If the semaphore value is greater than zero, wait() decrements it and allows the process to enter. If zero, the process blocks until another process calls signal(), which increments the semaphore and may unblock waiting processes. Counting semaphores allow multiple simultaneous accesses, while binary semaphores allow only one. This flow ensures safe access and prevents conflicts.

Practice

1. What is the main purpose of a semaphore in operating systems?

easy

A. To manage user passwords

B. To increase the speed of the CPU

C. To store data permanently

D. To control access to shared resources and prevent conflicts

Solution

1. Step 1: Understand the role of semaphores

   Semaphores are synchronization tools used to manage access to shared resources in concurrent systems.

2. Step 2: Identify the correct purpose

   The main goal is to avoid conflicts by controlling how many processes can access a resource at once.

3. Final Answer:

   To control access to shared resources and prevent conflicts -> Option D

4. Quick Check:

   Semaphore controls resource access = A [OK]

Hint: Semaphores manage resource access to avoid conflicts [OK]

Common Mistakes:

• Confusing semaphores with memory storage
• Thinking semaphores speed up CPU
• Mixing semaphores with security functions

2. Which of the following is the correct way to initialize a binary semaphore with an initial value of 1?

easy

A. semaphore = Semaphore(0)

B. semaphore = Semaphore(2)

C. semaphore = Semaphore(1)

D. semaphore = Semaphore(-1)

Solution

1. Step 1: Recall binary semaphore initialization

   A binary semaphore can only have values 0 or 1, where 1 means resource is available.

2. Step 2: Choose the correct initial value

   Initializing with 1 means the resource is free initially, so Semaphore(1) is correct.

3. Final Answer:

   semaphore = Semaphore(1) -> Option C

4. Quick Check:

   Binary semaphore init with 1 = D [OK]

Hint: Binary semaphore starts at 1 to allow one user [OK]

Common Mistakes:

• Using 0 which blocks access initially
• Using negative values which are invalid
• Using values greater than 1 for binary semaphore

3. Consider a counting semaphore initialized to 3. If three processes call wait() on it, what will be the semaphore's value afterwards?

medium

A. 0

B. -3

C. 3

D. 1

Solution

1. Step 1: Understand counting semaphore behavior

   Each wait() call decreases the semaphore value by 1 if the resource is available.

2. Step 2: Calculate the new value after three waits

   Starting at 3, after three wait() calls, value = 3 - 3 = 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   3 - 3 waits = 0 [OK]

Hint: Subtract one per wait call from initial count [OK]

Common Mistakes:

• Thinking semaphore goes negative immediately
• Confusing wait() with signal() effects
• Assuming semaphore resets automatically

4. A programmer wrote this code snippet using a binary semaphore:

semaphore = Semaphore(1)
semaphore.wait()
semaphore.wait()
semaphore.signal()

What is the problem with this code?

medium

A. It releases the semaphore twice causing an error

B. It causes a deadlock because the second wait() blocks indefinitely

C. It initializes the semaphore incorrectly

D. It does not use signal() after the first wait()

Solution

1. Step 1: Analyze the semaphore initial value and wait calls

   The semaphore starts at 1, so the first wait() decreases it to 0 (resource taken).

2. Step 2: Understand the effect of the second wait()

   The second wait() tries to decrease from 0, so it blocks waiting for signal().

3. Final Answer:

   It causes a deadlock because the second wait() blocks indefinitely -> Option B

4. Quick Check:

   Second wait on zero blocks = deadlock A [OK]

Hint: Second wait on binary semaphore without signal blocks [OK]

Common Mistakes:

• Thinking signal() is called twice
• Assuming semaphore initializes incorrectly
• Ignoring blocking behavior of wait()

5. You have a counting semaphore initialized to 5 to control access to a printer shared by multiple users. If 7 users try to access the printer simultaneously, how does the semaphore manage access?

hard

A. Allows 5 users to access immediately; 2 users wait until others release

B. Allows all 7 users to access simultaneously

C. Blocks all users until the semaphore is reset

D. Allows only 1 user at a time regardless of initial value

Solution

1. Step 1: Understand counting semaphore limits

   A counting semaphore with initial value 5 allows up to 5 concurrent accesses.

2. Step 2: Analyze user access requests

   When 7 users request access, 5 proceed immediately; the remaining 2 must wait for signal() calls.

3. Final Answer:

   Allows 5 users to access immediately; 2 users wait until others release -> Option A

4. Quick Check:

   Counting semaphore limits concurrent users = B [OK]

Hint: Counting semaphore limits concurrent access to initial count [OK]

Common Mistakes:

• Assuming all users access simultaneously ignoring limits
• Confusing counting semaphore with binary semaphore
• Thinking semaphore blocks all users at once