Classic problems (producer-consumer, readers-writers, dining philosophers) in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the Producer-Consumer Problem

In the classic producer-consumer problem, what is the main purpose of using a buffer between the producer and consumer?

A To prevent the consumer from producing items faster than the producer

B To store produced items temporarily until the consumer is ready to consume them

C To allow the producer to consume items directly without waiting

D To synchronize the producer and consumer by making them run sequentially

💡 Hint

Think about why the producer and consumer might not work at the same speed.

The buffer acts as temporary storage so the producer can keep producing even if the consumer is not ready yet. This helps balance the speed difference between them.

📋 Factual

intermediate

Readers-Writers Problem: Priority Types

Which type of priority in the readers-writers problem can cause writers to starve if many readers keep accessing the resource?

A Reader priority

B No priority (fair scheduling)

C Writer priority

D Random priority

💡 Hint

Consider what happens if readers are always allowed first.

Reader priority lets readers access the resource whenever they want, which can block writers indefinitely if readers keep coming.

🔍 Analysis

advanced

Dining Philosophers: Deadlock Scenario

In the dining philosophers problem, what situation leads to a deadlock?

A Philosophers share forks without any restrictions

B Philosophers pick up forks randomly without waiting

C Philosophers eat without picking up any forks

D All philosophers pick up their left fork simultaneously and wait for the right fork

💡 Hint

Think about what happens if everyone holds one fork and waits for the other.

If all philosophers pick up their left fork at the same time, they all wait for the right fork, which is held by their neighbor, causing a deadlock.

❓ Comparison

advanced

Comparing Solutions to Readers-Writers Problem

Which solution to the readers-writers problem ensures no starvation for both readers and writers?

A Fair solution using a queue to order requests

B Writer priority solution

C Allowing unlimited readers and writers simultaneously

D Reader priority solution

💡 Hint

Consider a method that treats readers and writers equally over time.

A fair solution uses a queue to handle requests in order, preventing starvation of either readers or writers.

❓ Reasoning

expert

Resolving Deadlock in Dining Philosophers

Which strategy effectively prevents deadlock in the dining philosophers problem?

A Philosophers eat without using forks

B Philosophers always pick up the right fork first, then the left fork

C Allow philosophers to pick up both forks only if both are available simultaneously

D Philosophers pick up forks one at a time without checking availability

💡 Hint

Think about how to avoid holding one fork while waiting for another.

By requiring philosophers to pick up both forks at once or none, the system avoids the circular wait condition that causes deadlock.

Practice

1. Which classic problem in operating systems involves multiple processes sharing a fixed number of resources and needing to avoid deadlock while accessing them?

easy

A. Sleeping Barber problem

B. Producer-Consumer problem

C. Readers-Writers problem

D. Dining Philosophers problem

Solution

1. Step 1: Understand the problem context

   The Dining Philosophers problem models philosophers sitting around a table sharing forks (resources) and needing to avoid deadlock.

2. Step 2: Match problem to description

   It specifically deals with multiple processes sharing limited resources and avoiding deadlock.

3. Final Answer:

   Dining Philosophers problem -> Option D

4. Quick Check:

   Deadlock with shared resources = Dining Philosophers [OK]

Hint: Deadlock with shared forks? Think Dining Philosophers [OK]

Common Mistakes:

• Confusing Producer-Consumer with resource deadlock
• Mixing Readers-Writers with resource sharing deadlock
• Choosing unrelated problems like Sleeping Barber

2. Which synchronization primitive is commonly used to solve the Producer-Consumer problem?

easy

A. Semaphore

B. Mutex

C. Barrier

D. Spinlock

Solution

1. Step 1: Identify synchronization needs in Producer-Consumer

   Producer-Consumer requires controlling access to a shared buffer and signaling availability.

2. Step 2: Match synchronization primitive

   Semaphores are used to count available slots and items, making them ideal here.

3. Final Answer:

   Semaphore -> Option A

4. Quick Check:

   Counting resources = Semaphore [OK]

Hint: Counting resources? Use Semaphore [OK]

Common Mistakes:

• Choosing Mutex which only locks/unlocks without counting
• Selecting Barrier which is for thread synchronization phases
• Confusing Spinlock with counting mechanism

3. Consider the Readers-Writers problem where multiple readers can read simultaneously but writers require exclusive access. If two readers and one writer request access at the same time, which scenario is correct?

medium

A. Both readers and writer access the resource simultaneously

B. Only one reader accesses the resource, writer waits

C. Both readers access simultaneously, writer waits

D. Writer accesses first, readers wait

Solution

1. Step 1: Recall Readers-Writers access rules

   Multiple readers can read at the same time, but writers need exclusive access.

2. Step 2: Apply rules to scenario

   When readers and writer request simultaneously, readers get access first, writer waits.

3. Final Answer:

   Both readers access simultaneously, writer waits -> Option C

4. Quick Check:

   Readers share, writer exclusive = readers first [OK]

Hint: Readers share access; writers wait for exclusivity [OK]

Common Mistakes:

• Allowing writer and readers simultaneously
• Restricting readers to one at a time
• Letting writer go first without readers finishing

4. In a solution to the Dining Philosophers problem, a programmer uses a simple lock for each fork but notices the system deadlocks. What is the most likely cause?

medium

A. All philosophers pick up their left fork simultaneously and wait for the right fork

B. Philosophers pick up forks randomly causing starvation

C. Philosophers release forks too early

D. Fork locks are not acquired atomically

Solution

1. Step 1: Understand deadlock in Dining Philosophers

   Deadlock occurs if all philosophers hold one fork and wait for the other indefinitely.

2. Step 2: Identify cause from options

   All picking left fork simultaneously and waiting for right fork causes circular wait and deadlock.

3. Final Answer:

   All philosophers pick up their left fork simultaneously and wait for the right fork -> Option A

4. Quick Check:

   Circular wait with forks = deadlock [OK]

Hint: Deadlock if all pick same fork first [OK]

Common Mistakes:

• Assuming random picking causes deadlock
• Thinking releasing forks early causes deadlock
• Ignoring atomicity of lock acquisition

5. You want to design a system where multiple producers generate data and multiple consumers process it, but the buffer size is limited. Which approach best prevents data loss and ensures synchronization?

hard

A. Allow producers to overwrite data if buffer is full

B. Use semaphores to track empty and full buffer slots with mutex for buffer access

C. Use only mutex locks for both producers and consumers

D. Use busy waiting loops for producers and consumers

Solution

1. Step 1: Identify synchronization needs

   Producers and consumers share a limited buffer; must avoid overwriting and race conditions.

2. Step 2: Choose synchronization method

   Semaphores count empty/full slots; mutex ensures exclusive buffer access, preventing data loss and race.

3. Final Answer:

   Use semaphores to track empty and full buffer slots with mutex for buffer access -> Option B

4. Quick Check:

   Counting slots + exclusive access = semaphores + mutex [OK]

Hint: Combine semaphores and mutex for safe buffer use [OK]

Common Mistakes:

• Using only mutex causes blocking but no counting
• Overwriting data loses information
• Busy waiting wastes CPU and causes inefficiency