CHAPTER 7: DEADLOCKS

What is Deadlock?

A situation where processes are stuck waiting for each other to release
resources indefinitely.

Four Necessary Conditions for Deadlock:

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

Resource Allocation Graph (RAG)

• Processes: Circles (P1, P2, ...)
• Resources: Squares (R1, R2, ...)
• Request Edge: Pi → Rj
• Assignment Edge: Rj → Pi
Cycle in Graph:
• Single instance: Cycle = Deadlock
• Multiple instances: Cycle = Possible deadlock

Banker's Algorithm (Deadlock Avoidance)

Step-by-Step:
1. Calculate Need = Max - Allocation
2. Check Request ≤ Need and Request ≤ Available
3. Temporarily allocate resources
4. Run Safety Algorithm:
o Work = Available
o Finish[i] = false
 o Find process with Need[i] ≤ Work
o Work = Work + Allocation[i]
o Finish[i] = true
5. If all Finish[i] = true → Safe
Example: Safe Sequence Calculation (Provided in detail in previous
steps)

Deadlock Detection Algorithm

1. Work = Available
2. Finish[i] = false if Allocation[i] ≠ 0
3. Find i such that Finish[i] = false and Request[i] ≤ Work
4. Update Work and Finish[i]
5. Repeat step 3 until no process found
6. If Finish[i] = false → Deadlock

Methods for Handling Deadlocks

• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection
• Deadlock Recovery

CHAPTER 8: MAIN MEMORY

🖌 Address Binding
• Compile Time: Fixed addresses
• Load Time: Relocatable
• Execution Time: Dynamic (MMU)

Logical vs Physical Address

 • Logical (Virtual): CPU-generated
• Physical: Actual memory location

Paging

• Divides memory into pages (logical) and frames (physical)

Address Translation Example:
• Logical Address = 13
• Page size = 4 bytes → Page = 3, Offset = 1
• Frame[3] = 20 → Physical Address = 20 + 1 = 21

Internal Fragmentation Example

• Process size = 72,766 bytes
• Page size = 2,048 bytes
• Pages needed = 36
• Last page wasted = 2,048 - 1,086 = 962 bytes

Dynamic Storage Allocation

• First Fit, Best Fit, Worst Fit
• Compaction: Rearrange memory to remove fragmentation

🗐 Paging Policies
• Frame Allocation: Equal, Proportional
• Page Replacement: FIFO, LRU, Optimal

Swapping

• Moves entire processes in/out of memory to free space

CHAPTER 9: VIRTUAL MEMORY

Concept
 • Allows programs to run with more memory than physically available

Demand Paging

• Load pages only when needed

Page Fault Handling Steps:
1. Trap to OS
2. Validate page
3. Find free frame
4. Load from disk
5. Update page table
6. Restart instruction

🗓 Effective Access Time (EAT)

Formula:
EAT = (1 - p) × memory access + p × (page fault overhead + swap out + swap
in)

🗒 Page Replacement Algorithms

• FIFO: Replace oldest page

• LRU: Replace least recently used page
• Optimal: Replace page needed farthest in future
• Clock (Second-Chance): Use reference bit
LRU Example: Step-by-step page fault counting (Included in previous
steps)

Thrashing
• Too many page faults
Avoid:
• Working Set Model
 • Page-Fault Frequency Control

Memory-Mapped Files

• Map file contents into virtual memory for fast access

Kernel Memory Allocation

• Buddy System
• Slab Allocator

CHAPTER 10: INPUT/OUTPUT (I/O) SYSTEMS

I/O Hardware Basics

• Devices: keyboard, mouse, disk, printer

• Connected via Ports, Buses, and Controllers

Device Drivers
• Software that talks to I/O hardware
• Provides a uniform interface to OS

Communication Techniques

Method Explanation

Polling CPU checks device repeatedly (inefficient)

Interrupts Device alerts CPU when ready (better)

DMA Direct Memory Access: data goes device ↔ memory (fastest)

DMA 6-Step Process:

1. OS creates command block with source/destination

2. Sends to DMA controller
3. Controller takes bus
4. Transfers data
 5. Returns bus
6. Sends interrupt to CPU

Types of Devices

Type Example Notes

Block Disk Read/write in blocks

Character Keyboard Stream data

Network NIC Uses socket API

Clocks & Timers

• Provide time, interrupts, and periodic tasks

I/O Methods

Type Description

Blocking Wait until I/O done

Non-blocking Returns immediately

Asynchronous I/O in background, process continues

Vectored I/O
• Multiple reads/writes in one system call
• Reduces overhead, faster

Kernel I/O Subsystem

Component Function

Buffering Temp storage during transfer

Caching Store frequently accessed data

Spooling Queue data for slow devices (e.g. printer)

Scheduling Manage order of requests

 Error Handling & Protection

• Retry on failures, log errors

• Only kernel can perform I/O (for safety)

I/O via System Calls

• Example: read(), write(), open()

Power Management

• Saves energy by turning off unused devices

• Android: wake locks, device trees, power collapse

STREAMS (Unix)

• Full-duplex communication with:

o Stream Head → Application
o Driver End → Device
o Modules in between

⟳ Comparison of I/O Techniques

Method CPU Usage Efficient Best For

Polling High Low Fast devices

Interrupts Medium Good General devices

DMA Low Best Large transfers (e.g. disk I/O)

CHAPTER 11: FILE-SYSTEM INTERFACE

File Concept
• A file is a named collection of related information stored on
secondary storage.
 • Types: text, binary, executable, etc.

File Attributes

Attribute Meaning

Name Human-readable identifier

Type File format or function

Location Disk address (pointer)

Size Current file size in bytes

Protection Access control (read/write/execute)

Time, Date, User ID Used for logging and permissions

File Operations
• Create: Make a new file
• Write: Save data into file
• Read: Load data from file
• Seek: Move read/write pointer
• Delete: Remove file
• Open/Close: Prepare file for use / finish using file

Open File Management

• Open-file table: List of active files
• File pointer: Keeps track of current read/write position
• Locking: Prevents data corruption (shared/exclusive)

File Structure
• Byte stream (text)
• Record-based (fixed/variable length)
• Complex (e.g. loadable program)
⬮️ Access Methods

Type Description

Sequential Read/write in order

Direct Jump to block number

Indexed Use index to locate data

Disk & Directory Structure

• Disk → Partition → Volume → File System

• Directory: Special file that stores metadata of other files

Directory Types:

• Single-Level
• Two-Level
• Tree-Structured
• Acyclic Graph
• General Graph

File Mounting

• File system must be mounted at a mount point before use.

File Sharing
• Share files across local or network
• Controlled using User ID and Group ID

Protection

• Access rights: Read, Write, Execute, Append, Delete, List

Access Control Example:

chmod 755 filename

# Owner: rwx, Group: r-x, Others: r-x
 Free-Space Management

• Bitmaps
• Linked List
• Grouping
• Counting
Bitmap Example:
Aurora = 0 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 1
Unallocated spaces: Blocks 0, 1, 2, 5, 7, 12, 13, 16, 17, 18
File Allocation Example:
• Neuron file (5 blocks) using Index Allocation:
Index Block -> Points to Blocks 3, 4, 6, 8, 9
• Remaining Available Blocks: 0, 1, 2, 5, 7, 12, 13, 16, 17, 18
• Stardust file (4 blocks) using Contiguous Allocation:
Check for continuous free blocks (no sufficient continuous space based on
bitmap example)

End of Combined OS Notes