Concurrency in operating systems involves multiple processes or threads executing simultaneously. This can lead to complex issues that need to be managed to ensure system stability and efficiency. In this section, we will explore some classic concurrency problems, their implications, and solutions.
Key Concepts
- Race Condition: A situation where the behavior of software depends on the sequence or timing of uncontrollable events such as thread execution order.
- Deadlock: A state where two or more processes are unable to proceed because each is waiting for the other to release a resource.
- Starvation: A situation where a process is perpetually denied necessary resources to proceed.
- Critical Section: A part of the code that accesses shared resources and must not be concurrently executed by more than one thread.
Classic Concurrency Problems
- The Producer-Consumer Problem
Description: This problem involves two types of processes: producers that generate data and place it in a buffer, and consumers that take data from the buffer. The challenge is to ensure that producers do not add data to a full buffer and consumers do not remove data from an empty buffer.
Solution: Use semaphores to synchronize access to the buffer.
Example Code:
import threading
import time
import random
buffer = []
buffer_size = 10
empty = threading.Semaphore(buffer_size)
full = threading.Semaphore(0)
mutex = threading.Lock()
def producer():
while True:
item = random.randint(1, 100)
empty.acquire()
mutex.acquire()
buffer.append(item)
print(f"Produced: {item}")
mutex.release()
full.release()
time.sleep(random.random())
def consumer():
while True:
full.acquire()
mutex.acquire()
item = buffer.pop(0)
print(f"Consumed: {item}")
mutex.release()
empty.release()
time.sleep(random.random())
producer_thread = threading.Thread(target=producer)
consumer_thread = threading.Thread(target=consumer)
producer_thread.start()
consumer_thread.start()
- The Dining Philosophers Problem
Description: Five philosophers sit around a table with a fork between each pair. They alternate between thinking and eating. A philosopher needs both forks to eat. The challenge is to prevent deadlock and ensure that no philosopher starves.
Solution: Use a strategy to ensure that no two neighbors pick up forks at the same time.
Example Code:
import threading
import time
class Philosopher(threading.Thread):
def __init__(self, name, left_fork, right_fork):
threading.Thread.__init__(self)
self.name = name
self.left_fork = left_fork
self.right_fork = right_fork
def run(self):
while True:
print(f"{self.name} is thinking.")
time.sleep(random.random())
print(f"{self.name} is hungry.")
self.dine()
def dine(self):
fork1, fork2 = self.left_fork, self.right_fork
while True:
fork1.acquire(True)
locked = fork2.acquire(False)
if locked: break
fork1.release()
print(f"{self.name} swaps forks.")
fork1, fork2 = fork2, fork1
else:
return
self.eating()
fork2.release()
fork1.release()
def eating(self):
print(f"{self.name} starts eating.")
time.sleep(random.random())
print(f"{self.name} finishes eating and leaves to think.")
forks = [threading.Lock() for _ in range(5)]
philosophers = [Philosopher(f"Philosopher {i}", forks[i % 5], forks[(i + 1) % 5]) for i in range(5)]
for p in philosophers:
p.start()
- The Readers-Writers Problem
Description: This problem involves a shared resource (e.g., a database) that can be read by multiple readers simultaneously but must be written by only one writer at a time. The challenge is to ensure that readers do not read while a writer is writing and vice versa.
Solution: Use reader and writer locks to manage access.
Example Code:
import threading
import time
readers = 0
resource_lock = threading.Lock()
readers_lock = threading.Lock()
def reader():
global readers
while True:
readers_lock.acquire()
readers += 1
if readers == 1:
resource_lock.acquire()
readers_lock.release()
print("Reading...")
time.sleep(random.random())
readers_lock.acquire()
readers -= 1
if readers == 0:
resource_lock.release()
readers_lock.release()
time.sleep(random.random())
def writer():
while True:
resource_lock.acquire()
print("Writing...")
time.sleep(random.random())
resource_lock.release()
time.sleep(random.random())
reader_threads = [threading.Thread(target=reader) for _ in range(5)]
writer_threads = [threading.Thread(target=writer) for _ in range(2)]
for t in reader_threads + writer_threads:
t.start()Practical Exercises
Exercise 1: Implement the Producer-Consumer Problem
Task: Modify the producer-consumer example to handle multiple producers and consumers.
Solution:
import threading
import time
import random
buffer = []
buffer_size = 10
empty = threading.Semaphore(buffer_size)
full = threading.Semaphore(0)
mutex = threading.Lock()
def producer(id):
while True:
item = random.randint(1, 100)
empty.acquire()
mutex.acquire()
buffer.append(item)
print(f"Producer {id} produced: {item}")
mutex.release()
full.release()
time.sleep(random.random())
def consumer(id):
while True:
full.acquire()
mutex.acquire()
item = buffer.pop(0)
print(f"Consumer {id} consumed: {item}")
mutex.release()
empty.release()
time.sleep(random.random())
producer_threads = [threading.Thread(target=producer, args=(i,)) for i in range(3)]
consumer_threads = [threading.Thread(target=consumer, args=(i,)) for i in range(3)]
for t in producer_threads + consumer_threads:
t.start()Exercise 2: Solve the Dining Philosophers Problem with a Different Strategy
Task: Modify the dining philosophers example to use a different strategy to prevent deadlock, such as using a waiter.
Solution:
import threading
import time
class Philosopher(threading.Thread):
def __init__(self, name, left_fork, right_fork, waiter):
threading.Thread.__init__(self)
self.name = name
self.left_fork = left_fork
self.right_fork = right_fork
self.waiter = waiter
def run(self):
while True:
print(f"{self.name} is thinking.")
time.sleep(random.random())
print(f"{self.name} is hungry.")
self.dine()
def dine(self):
with self.waiter:
with self.left_fork:
with self.right_fork:
self.eating()
def eating(self):
print(f"{self.name} starts eating.")
time.sleep(random.random())
print(f"{self.name} finishes eating and leaves to think.")
forks = [threading.Lock() for _ in range(5)]
waiter = threading.Lock()
philosophers = [Philosopher(f"Philosopher {i}", forks[i % 5], forks[(i + 1) % 5], waiter) for i in range(5)]
for p in philosophers:
p.start()Conclusion
In this section, we explored classic concurrency problems such as the Producer-Consumer Problem, the Dining Philosophers Problem, and the Readers-Writers Problem. We discussed their implications and provided solutions using synchronization mechanisms like semaphores and locks. Understanding these problems and their solutions is crucial for managing concurrency in operating systems effectively. In the next module, we will delve into file structures, exploring file systems, directory structures, file management, and file security and permissions.
Fundamentals of Operating Systems
Module 1: Introduction to Operating Systems
- Basic Concepts of Operating Systems
- History and Evolution of Operating Systems
- Types of Operating Systems
- Main Functions of an Operating System
Module 2: Resource Management
Module 3: Concurrency
- Concepts of Concurrency
- Threads and Processes
- Synchronization and Mutual Exclusion
- Classic Concurrency Problems