Semaphores (counting and binary) in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Counting Semaphore Behavior

What happens when a counting semaphore initialized to 3 is signaled (V operation) twice after three wait (P) operations have already been performed?

A The semaphore value becomes 5, which is invalid because it exceeds the initial count.

B The semaphore value remains 0, so no additional wait operations can proceed without blocking.

C The semaphore value becomes 2, allowing two more wait operations without blocking.

D The semaphore value becomes 1, allowing one more wait operation without blocking.

💡 Hint

Remember that signaling a counting semaphore increments its value, allowing more processes to enter the critical section.

A counting semaphore initialized to 3 starts with a value of 3. After three wait operations, the value decreases to 0. Two signal operations increment it by 2, resulting in a value of 2. This means two more wait operations can proceed without blocking.

📋 Factual

intermediate

Binary Semaphore Characteristics

Which of the following statements correctly describes a binary semaphore?

A It can only have values 0 or 1 and is used to enforce mutual exclusion.

B It automatically resets to 0 after each signal operation.

C It allows multiple processes to enter the critical section simultaneously.

D It can have any non-negative integer value and is used to count resources.

💡 Hint

Think about the simplest semaphore used for locking.

A binary semaphore only takes values 0 or 1 and is typically used to ensure that only one process accesses a critical section at a time, enforcing mutual exclusion.

🚀 Application

advanced

Semaphore Usage in Producer-Consumer Problem

In a producer-consumer problem using semaphores, which semaphore should the consumer wait on before consuming an item?

A The semaphore counting the number of empty slots in the buffer.

B The semaphore counting the number of full slots in the buffer.

C A binary semaphore used to protect the buffer access.

D A semaphore initialized to zero that counts the number of producers.

💡 Hint

Consumers can only consume if there is at least one item available.

The consumer must wait on the semaphore that counts full slots to ensure there is an item to consume. Waiting on empty slots or a binary semaphore for mutual exclusion does not guarantee availability of items.

🔍 Analysis

advanced

Deadlock Scenario with Semaphores

Which of the following semaphore usage patterns can cause a deadlock?

A A counting semaphore is initialized to a value greater than the number of processes.

B A process signals a semaphore before waiting on it.

C A binary semaphore is used to protect a critical section accessed by one process only.

D Two processes each wait on a semaphore held by the other, causing circular wait.

💡 Hint

Consider what happens when two processes wait indefinitely for each other.

Deadlock occurs when two or more processes wait forever for resources held by each other, creating a circular wait condition. This happens if each process waits on a semaphore the other holds.

❓ Reasoning

expert

Effect of Incorrect Semaphore Initialization

What is the most likely outcome if a binary semaphore used for mutual exclusion is incorrectly initialized to 2 instead of 1?

A Multiple processes may enter the critical section simultaneously, breaking mutual exclusion.

B The semaphore will cause a deadlock immediately after the first wait operation.

C The semaphore will automatically reset to 1 after the first signal operation.

D The semaphore will behave like a counting semaphore with no effect on mutual exclusion.

💡 Hint

Think about what happens if the lock allows more than one holder.

If a binary semaphore is initialized to 2, it allows two processes to enter the critical section simultaneously, violating mutual exclusion and potentially causing race conditions.

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