Deadlocks; Memory Management

Deadlocks

What is a Deadlock?

A deadlock is a situation where a set of processes is permanently blocked because each process is holding a resource and waiting for a resource held by another process.

Example:

Process A holds Resource 1, waiting for Resource 2
Process B holds Resource 2, waiting for Resource 1
→ DEADLOCK: Neither can proceed

Coffman's Four Necessary Conditions for Deadlock

Condition	Description
Mutual Exclusion	Resources cannot be shared (one process at a time)
Hold and Wait	Process holds resource while waiting for others
No Preemption	Resources cannot be forcibly taken; must be released voluntarily
Circular Wait	Circular chain: P1 waits P2's resource, P2 waits P3's, ..., Pn waits P1's

All four conditions must hold simultaneously for deadlock

Deadlock Handling Methods

1. Deadlock Prevention

Prevent one of the four necessary conditions:

Eliminate Mutual Exclusion: Share resources (not always possible)
Eliminate Hold and Wait: Process must request all resources at once (or release before requesting more)
Allow Preemption: OS can forcibly take resources from waiting processes
Eliminate Circular Wait: Order resources; processes must request in increasing order

2. Deadlock Avoidance

Dynamically analyze resource allocation to ensure system never enters deadlock state.

Banker's Algorithm:

Like a bank approving loans — only approve if system stays "safe"
Safe State: There exists a sequence in which all processes can complete
If next allocation might lead to unsafe state → deny request

3. Deadlock Detection

Allow deadlock to occur, then detect and recover.

Detection: Draw Resource Allocation Graph (RAG)

If RAG has a cycle → deadlock (for single-instance resources)

Recovery methods:

Process termination — kill one or all deadlocked processes

Resource preemption — take resources from some processes

4. Deadlock Ignorance (Ostrich Algorithm)

Pretend deadlocks don't occur — "bury your head in sand".

Used by most OS (Unix, Windows) for infrequent deadlocks
Reboot the system if deadlock occurs

Memory Management

Why Memory Management?

Multiple processes must share memory
Each process needs its own address space
Protect one process's memory from another
Efficiently allocate and deallocate memory

Memory Allocation Methods

22.1 Contiguous Memory Allocation

Fixed Partitioning:

Memory divided into fixed-size partitions
Each process gets one partition
Problem: Internal Fragmentation — wasted space within partition if process is smaller

Dynamic Partitioning:

Partitions created as needed, sized to process needs

Problem: External Fragmentation — free space scattered in small chunks

Fragmentation

Type	Description	Solution
Internal Fragmentation	Wasted space within an allocated partition (process smaller than partition)	Smaller fixed partitions or dynamic allocation
External Fragmentation	Enough total free memory exists but scattered in non-contiguous chunks	Compaction, Paging

External Fragmentation Example:

Memory: [P1: 40KB] [Free 10KB] [P2: 20KB] [Free 15KB] [P3: 30KB] [Free 8KB]
Total free: 33KB    But a 30KB process cannot fit (no single 30KB block)

Compaction: Move processes to consolidate free space → expensive!

Memory Allocation Algorithms

When a new process needs memory, which free block to allocate?

Algorithm	Description	Advantage	Disadvantage
First Fit	Allocate first block large enough	Fast	May leave large holes
Best Fit	Allocate smallest sufficient block	Least waste	Slow; creates tiny unusable fragments
Worst Fit	Allocate largest available block	Leaves larger remaining holes	Often worst overall
Next Fit	First fit starting from last allocation point	Fast	Less initial waste