Operating Systems

Entry Section     → Request permission
Critical Section  → Access shared resource  
Exit Section      → Release permission
Remainder Section → Non-critical code

# Binary lock: locked (1) or unlocked (0)
mutex = 1

def acquire():
    while mutex == 0:
        pass  # busy wait
    mutex = 0  # lock it

def release():
    mutex = 1  # unlock it

# Usage
acquire()
# ... critical section ...
release()

# Counting semaphore: can be > 1
# Binary semaphore: 0 or 1 (like mutex)

class Semaphore:
    def __init__(self, value):
        self.value = value
    
    def wait(self):  # P operation
        while self.value <= 0:
            pass
        self.value -= 1
    
    def signal(self):  # V operation
        self.value += 1

# Producer-Consumer Example
empty = Semaphore(n)  # n empty slots
full = Semaphore(0)   # 0 full slots
mutex = Semaphore(1)  # mutual exclusion

# Producer
empty.wait()
mutex.wait()
# add item to buffer
mutex.signal()
full.signal()

# Consumer
full.wait()
mutex.wait()
# remove item from buffer
mutex.signal()
empty.signal()

Producer: Creates items, adds to buffer
Consumer: Removes items from buffer
Buffer: Fixed size (n slots)

Issues to handle:
- Producer waits if buffer full
- Consumer waits if buffer empty
- Only one accesses buffer at a time

Multiple readers can read simultaneously
Only one writer at a time
No reader while writing, no writer while reading

Solution: Use mutex for writers, allow multiple readers

5 philosophers, 5 forks
Each needs 2 forks to eat
Can cause deadlock if all pick left fork first

Solutions:
- Allow only 4 to sit
- Pick both forks atomically
- Odd picks left first, even picks right first

Process → Resource: Request edge
Resource → Process: Assignment edge

Deadlock if cycle exists (single instance per resource)

P1 → R1 → P2 → R2 → P1  ← DEADLOCK!

System checks if granting request leads to safe state
Safe state: Can complete all processes in some order

Banker's Algorithm:
- Available: Resources currently available
- Max: Maximum each process may need
- Allocation: Currently allocated
- Need = Max - Allocation

Safe sequence example:
Available = [3, 3, 2]
Can P1 finish? Need[P1] <= Available?
If yes, allocate, let finish, reclaim resources
Continue until all processes finish

Detection: Find cycles in resource graph

Recovery options:
- Terminate deadlocked processes
- Preempt resources
- Rollback to checkpoint

Ignore the problem!
Used when deadlock is rare and detection is expensive
Most OSes (Windows, Linux) use this approach