🌟 UNIT III — INTERPROCESS COMMUNICATION

(IPC) & DEADLOCK

1. Concurrency
Concurrency means **multiple processes or threads executing at the
same time** and possibly sharing resources.
* Two processes accessing the same file
* Two threads updating a bank balance
1. **Race condition** – output depends on execution order
2. **Deadlock** – two processes wait forever
3. **Starvation** – a process never gets a resource
4. **Data inconsistency** – if no synchronization
5. **Resource conflicts** – multiple processes want same
memory/file

2. Critical Section Problem

Critical Section** is a part of a program where shared resources are
accessed.
Only **one process** should enter the critical section at a time.
*Requirements (3 MUST conditions)*
1. **Mutual Exclusion** – only 1 process inside
2. **Progress** – process outside cannot block others
3. **Bounded Waiting** – no infinite waiting
 Two ATM servers updating bank balance → must avoid double
withdrawal.
3. Synchronization Primitives**

A. Semaphores
A **Semaphore** is an integer variable used to control access to
shared resources.
**Types**
1. **Binary Semaphore (0 or 1)** – acts like a lock
2. **Counting Semaphore** – allows multiple processes

### **Example (Binary Semaphore)**

wait(S) → enter critical section
signal(S) → exit critical section

**B. Mutex**
A Mutex (Mutual Exclusion Lock) allows only one process/thread at a
time.

**Example**
Thread locks file → edits → unlocks.
C. Monitors**
A monitor is a synchronization mechanism that contains:

* Mutual exclusion automatically

* Condition variables for waiting

**Example**
Java monitor (synchronized keyword)
*4. Synchronization Problems**

**A. Producer–Consumer Problem**

**Definition**
Producer creates items → Consumer uses them
Shared buffer of limited size.

**Diagram**
Producer ---> [ BUFFER ] ---> Consumer

1. Producer puts data

2. Consumer removes data
3. Buffer cannot overflow
4. Consumer waits if empty
5. Semaphore or mutex used
**B. Reader–Writer Problem**
**Definition**
Multiple readers can read simultaneously,
but **only one writer** can write.

**Example**
* Reading articles (many readers)
* Editing article (one writer)

**C. Dining Philosophers Problem**

**Definition**
5 philosophers share 5 chopsticks → must avoid deadlock.
**Example**
* Each philosopher needs 2 chopsticks
* If everyone picks left chopstick → deadlock
* Solutions: numbering, waiters, semaphores

**5. Inter-Process Communication (IPC)*

**Definition**
IPC allows processes to **communicate** and **share data.**
**A. Message Passing**
1. No shared memory
2. Uses send() and receive()
3. Simple for distributed systems
4. Safe
5. Slower than shared memory
**Example**
Chat applications send messages between processes.
**B. Shared Memory**
**Features**
1. Processes share a memory region
2. Very fast
3. Requires synchronization
4. Used in games, databases
5. Risk of data conflict if careless
6. Deadlocks**
**Definition**
Deadlock occurs when **two or more processes wait forever** for
resources.

**Deadlock Conditions (Coffman’s Conditions)**

(All four must hold)
1. **Mutual Exclusion**
* Resource shared by 1 process only
2. **Hold and Wait**
* Process holds one resource and waits for another
3. **No Preemption**
* Resource cannot be forcibly taken
4. **Circular Wait**
* P1 waits for P2, P2 waits for P3 … Pn waits for P1
**Example**
P1 holds printer, needs scanner
P2 holds scanner, needs printer → deadlock
7. Deadlock Prevention
Break at least **one** of the four conditions.
1. **Disallow Mutual Exclusion** – make resources sharable
2. **No Hold and Wait** – request all resources together
3. **Allow Preemption** – take resource back
4. **Break Circular Wait** – priority ordering

8. Deadlock Avoidance (Banker's Algorithm)

**Definition**
Ensures system never enters unsafe state.
**Steps (simple words)**
1. Banks checks resource request
2. If granting keeps system safe → allow
3. Else → wait
4. Avoids circular wait
5. Used in databases

9. Deadlock Detection
**Steps**
1. Check circular wait
2. Build Resource Allocation Graph
3. Detect cycles
4. Identify deadlocked processes
5. Report to OS

10. Deadlock Recovery

### **Methods**

1. **Terminate processes**
2. **Rollback work**
3. **Resource preemption**
4. **Kill lowest priority process**
5. **Free resources and restart**

**Case Studies**

**1. IPC in Banking System**

1. ATM servers share customer data

2. Shared memory or message queues
3. Synchronization avoids double withdrawal
4. Deadlock avoided using locks
5. Ensures consistency of account balance

**2. Deadlock in Railway Scheduling**

1. Two trains waiting for each other on single track

2. Circular wait
3. Solution: track reservation
4. Priority or preemption
5. Railway controller uses deadlock avoidance
 🌟 UNIT IV — MEMORY MANAGEMENT

1. Introduction to Memory Management

**Definition
Memory Management is the function of OS that **manages how
memory is allocated, used, and freed** during program execution.

**Why it is needed? (5 points)**

1. **Efficient memory use**
2. **Prevent memory waste**
3. **Allow multiple programs to run**
4. **Avoid crashes due to insufficient memory**
5. **Speed up CPU performance**
**Example**
Running Chrome + VS Code + Media Player → OS must manage
memory for each.

2. Contiguous & Non-Contiguous Memory Allocation

A. Contiguous Memory Allocation**

Programs are stored in **one continuous block** of memory.

**Features (5 points)**
1. Fast access
2. Simple to implement
3. External fragmentation occurs
4. Limits multiprogramming
5. Uses Fixed/Variable partitions

**Example**
Old OS like MS-DOS used contiguous memory.
 B. Non-Contiguous Memory Allocation
Process is divided into parts stored **in different locations** in
memory.

Features
1. No continuous block required
2. Less fragmentation
3. Supports paging, segmentation
4. Better memory utilization
5. More complex
3. Fragmentation
A. Internal Fragmentation**
Internal fragmentation is the wasted space within a memory block that
has been allocated to a process
Unused space **inside** an allocated block.
Example: Block = 10 KB, process = 7 KB → 3 KB waste.

B. External Fragmentation**
Free memory is in **small scattered holes**.
External fragmentation is a memory management problem where free
memory is broken into small, non-contiguous "holes."
5 Key Points**
1. Common in contiguous allocation
2. Wastes RAM
3. Reduces performance
4. Compaction is used to reduce it
5. Paging removes external fragmentation

4. Memory Allocation Strategies

A. First Fit
Allocate the **first** hole that is large enough.
Example: Holes = 10, 20, 5, 12 → process needs 8 → allocate in 10.

Advantages
1. Fast
2. Simple
3. Less searching
4. Good for general use
B. Best Fit
Allocate the **smallest hole** that is large enough.
Example: Holes = 10, 20, 5, 12 → process needs 8 → allocate 10.

Advantages
1. Less internal fragmentation
2. More efficient space
3. Good for small jobs

C. Worst Fit
Allocate the **largest** available hole.
Example: Holes = 10, 20, 5, 12 → process needs 8 → allocate 20.

Advantages
1. Leaves big free blocks
2. Reduces fragmentation in some cases

5. Memory Partitioning
A. Fixed Partitions
Features (5 points)
1. Memory divided before execution
2. Each partition has fixed size
3. Simple
4. Fast
5. Internal fragmentation occurs
B. Dynamic Partitions
**Features
1. Size created during execution
2. Flexible
3. Less internal fragmentation
4. Uses first/best/worst fit
5. External fragmentation occurs
6. Paging
**Definition**
Paging divides the process into **equal-sized pages** and memory
into **frames**. Paging is an operating system memory management
technique that divides both processes and physical memory into fixed-
size blocks, called pages and frames, respectively.

**5 points**
1. Removes external fragmentation
2. Page size is fixed
3. Frames = same size as pages
4. OS maintains Page Table
5. Used in modern OS

**Page Table Structure**

* Page Number
* Frame Number
* Valid/Invalid bit
* Protection bits
**Example**
Process of 4000B, page size 1000B → 4 pages.
7. Segmentation
**Definition**
Segmentation divides program into **logical units** like:
* Code
* Data
* Stack
* Functions

**Diagram**

Process:
[CODE]
[DATA]
[STACK]

**Features (5 points)**
1. Variable size segments
2. Logical view
3. No internal fragmentation
4. External fragmentation possible
5. Supports protection and sharing
8. Virtual Memory
**Definition**
Virtual Memory allows OS to run programs **bigger than RAM**
using secondary storage (disk).

**Features (5 points)**
1. Uses Demand Paging
2. Allows multitasking
3. Efficient memory use
4. Uses Page Tables
5. Slows down if overloaded

**Example**
Laptop with 8GB RAM running 12GB program.
9. Demand Paging
**Definition**
Load **only required pages** into memory when needed.
**Steps**
1. Page fault occurs
2. OS loads page from disk
3. Updates page table
4. Resumes process
5. Improves memory use

10. Page Replacement Algorithms

A. FIFO (First In First Out)

**Definition**
Oldest page is replaced first.

**Example**
Pages: 1 2 3 4 1 → replace 1 (oldest)

**B. LRU (Least Recently Used)**

**Definition**
Replace page which is least recently accessed.

**Example**
Used order: 4,2,1 → replace 1

**C. Optimal Replacement**

**Definition**
Replace page that **will not be used for the longest time** in future.
**Advantage**
Least page faults
(But not practical)

11. Thrashing
**Definition**
Too many page faults → CPU spends time swapping instead of
executing.

**Causes**
1. Low RAM
2. Too many processes
3. Large program
4. Poor page replacement
5. Overuse of virtual memory

12. Case Study – Intel Pentium Memory Management**

Points
1. Supports paging + segmentation
2. Uses multi-level page tables
3. Provides virtual memory
4. Uses TLB (Translation Lookaside Buffer)
5. Efficient protection and sharing
UNIT V — FILE AND DISK MANAGEMENT

1. File Management
A **file** is a collection of related data stored on disk.
The OS manages all files in the system.

1.1 File Operations

OS provides the following basic file operations:
1. Create
Make a new file (example: [Link]).
2. Open
Open a file for reading/writing.
3. Read
Read data from the file.
4. Write
Write data to the file.
5. Close
Close file after use.
6. Delete
Remove file from disk.

📌 Example:
When you save a Word file, OS performs: create → write → close.

1.2 Directory Structure

A **directory** stores information about files.
⭐ Types of directory structures:

1. Single-Level Directory
* One directory for all users.
* Simple but confusing for large systems.
 2. Two-Level Directory
* Separate directory for each user.
* Avoids name conflicts.

3. Tree-Structured Directory
* Folder inside folder (like Windows).
* Most common.
4. Acyclic Graph Directory
* Same file can be in multiple folders (shortcuts).

5. General Graph Directory

* Allows shared files with links.

📌 Simple Diagram – Tree Structure

Root
├── Documents
│ ├── [Link]
│ └── [Link]
├── Downloads
│ └── [Link]
└── Pictures
└── [Link]
1.3 File System Structure
A file system is how OS stores and organizes files on disk.
⭐ Components:
1. **Boot block** – Starts the OS.
2. **Superblock** – Information about file system size, type.
3. **Inode / File Control Block (FCB)** – Metadata of files.
4. **Data blocks** – Actual file data.
5. **Directory structure** – Folder layout.

📌 Example
EXT4 (Linux) uses *inodes*, NTFS uses *MFT*.

1.4 File Organization & Access Methods**

⭐ Types:

1. **Sequential Access**
* Read data one-by-one.
* Like audio/video files.
2. **Direct Access**
* Directly jump to any block.
* Like databases.

3. **Indexed Access**
* Uses index table to locate data.
* Like a book index.
📌 Example

Music player → sequential access

Database → direct access

1.5 File Allocation Methods

How files are stored on disk.

1. Contiguous Allocation
* Files stored in continuous blocks.
* Fast access.
* Causes *external fragmentation*.
 2. Linked Allocation
* Each block points to the next.
* No fragmentation.
* Slow for random access.

3. Indexed Allocation
* An index block stores all block addresses.
* No fragmentation.
* Efficient for large files.
### 📌 Simple Diagram – Indexed
[Link]
Index Block → [5, 9, 12, 14]

2. Secondary Storage Management (Disk Management)**

2.1 Disk Structure

Disk consists of:
1. **Platters**
2. **Tracks**
3. **Sectors**
4. **Cylinders**
5. **Disk Controller**
### 📌 Simple Diagram
Platter
├── Track 0
├── Track 1
├── Track 2
└── Sectors

2.2 Disk Scheduling Algorithms

Used to improve reading/writing efficiency.

1. FCFS (First Come First Serve)

* Processed in order of arrival.
* Simple but slow.

2. SSTF (Shortest Seek Time First)

* Nearest request served first.
* Faster but may cause starvation.

3. SCAN (Elevator Algorithm)

* Head moves like elevator: one direction → reverse.
* Fairer.
 4. C-SCAN (Circular SCAN)
* Moves in one direction only.
* When end reached, jumps to start.

5. LOOK & C-LOOK

* Like SCAN but stops at last request instead of disk end.

2.3 Disk Reliability

Disk reliability involves:

1. **Redundancy** (RAID)
2. **Backups**
3. **Error Detection**
4. **Bad block handling**
5. **Duplicate metadata**

2.4 Disk Formatting

Two types:
1. **Low-level formatting**
Creates physical sectors.
2. **High-level formatting**
Creates file system (NTFS, FAT, EXT4).

2.5 Boot Block

* Special block that contains bootloader.
* Helps OS start when system is powered on.

### 📌 Example
Windows → uses **MBR** / **EFI**
2.6 Bad Blocks
Bad sectors = damaged disk areas.
Handling methods:
1. OS marks block as "bad"
2. Data shifted to spare block
3. SMART monitoring
4. Disk check tools repair logical errors

3. File Systems in OS
1. FAT (File Allocation Table)
* Used in pendrives, SD cards.

2. NTFS
* Used in Windows.
* Supports security permissions.

3. EXT (EXT2/3/4)
* Default in Linux.

4. HFS / APFS
* Used in macOS and iOS.

# **Case Studies**

### ⭐ **1. Study of Linux File System**

Linux uses:
* EXT4 filesystem
* Inodes
* Journaling
* /root, /home, /boot directory structure

### 📌 Example Folder Structure

/
├── home
├── boot
├── etc
├── usr
└── var

### ⭐ **2. Study of Android File System**

Android uses:
* **EXT4 / F2FS**
* `/system` – OS files
* `/data` – user apps
* `/cache` – temporary files
* `/sdcard` – user storage