ADVANCED OPERATING SYSTEM

Module-1 DEADLOCK – DETECTION AND PREVENTION

1.1 Deadlocks
Definition of Deadlock
A deadlock is a situation in an operating system where a set of processes are permanently
blocked because each process is waiting for a resource that is held by another process in the
same set. Since none of the processes can proceed, the system comes to a standstill.

Deadlock Characteristics (Necessary Conditions)

Deadlock occurs only if all the following four conditions hold simultaneously (Coffman
conditions):

1. Mutual Exclusion
o At least one resource must be held in a non-shareable mode.
o Only one process can use the resource at a time.
2. Hold and Wait
o A process holding at least one resource is waiting to acquire additional
resources held by other processes.
3. No Preemption
o Resources cannot be forcibly taken from a process.
o They must be released voluntarily.
4. Circular Wait
o A set of processes are waiting in a circular chain.
o Each process waits for a resource held by the next process in the cycle.

Deadlock Prevention
Deadlock prevention ensures that at least one of the four necessary conditions is violated.

Methods:

1. Eliminate Mutual Exclusion

o Make resources sharable where possible (e.g., read-only files).
2. Eliminate Hold and Wait
o Require processes to request all resources at once before execution.
3. Eliminate No Preemption
 o
If a process requests a resource that is unavailable, it releases all currently held
resources.
4. Eliminate Circular Wait
o Impose a strict ordering of resource allocation.

Deadlock Avoidance
Deadlock avoidance ensures that the system will never enter an unsafe state.

Banker’s Algorithm

Banker’s Algorithm is a resource allocation and deadlock avoidance algorithm.

Key Idea:

 System checks whether granting a resource request keeps the system in a safe state.
 If yes → allocate resources
 If no → process must wait

Data Structures Used:

 Available: Number of available resources

 Max: Maximum demand of each process
 Allocation: Currently allocated resources
 Need = Max - Allocation

Steps:

1. Check request ≤ Need

2. Check request ≤ Available
3. Temporarily allocate resources
4. Check if system remains in safe state
5. If safe → confirm allocation, else rollback

Deadlock Detection and Recovery

Deadlock Detection

System allows deadlock to occur and then detects it.

 Uses Wait-For Graph (for single instance resources)

 Or detection algorithm using:
o Allocation
o Request
 o Available

Detection Steps:

1. Identify processes waiting for resources

2. Check for cycle in resource allocation graph
3. If cycle exists → deadlock detected

Deadlock Recovery

After detection, system recovers using:

1. Process Termination
o Abort all deadlocked processes OR
o Abort one process at a time until deadlock is removed
2. Resource Preemption
o Take resources from some processes
o Allocate to others
o Requires rollback mechanism
3. Rollback
o Restore processes to previous safe checkpoint

Conclusion
Deadlock is a critical problem in operating systems that halts process execution. It can be
handled through prevention, avoidance (Banker’s Algorithm), detection, and recovery
techniques depending on system design requirements.
Module-2 INPUT OUTPUT MECHANISMS

2.1 I/O Subsystem (Input/Output Subsystem)

1. General Structure of I/O Subsystem

The I/O subsystem provides an interface between CPU, memory, and external devices.

Structure includes:

 User-level I/O software (application interface)

 Device-independent I/O software
 Device drivers
 Interrupt handlers
 Hardware controllers

Flow:

Application → OS I/O System → Device Driver → Controller → Device

2. Polled Mode vs Interrupt-Driven I/O

Polled I/O (Busy Waiting)

 CPU continuously checks device status.

 CPU wastes time waiting.

Advantages:

 Simple design
 Easy to implement

Disadvantages:

 Inefficient CPU usage

 Wastes processing time

Interrupt-Driven I/O

 Device sends interrupt when ready.

 CPU performs other tasks meanwhile.
Advantages:

 Efficient CPU utilization

 Suitable for slow devices

Disadvantages:

 More complex
 Interrupt overhead

3. Programmed I/O (PIO) vs Direct Memory Access

(DMA)
Programmed I/O (PIO)

 CPU directly controls data transfer.

 Data moves between device and CPU registers.

Features:

 CPU involved in every transfer

 Low performance

Direct Memory Access (DMA)

 DMA controller transfers data directly between device and memory.

 CPU is free during transfer.

Features:

 High speed
 Efficient for large data transfer

DMA Process:

1. CPU initializes DMA

2. DMA takes control
3. Data transferred directly
4. Interrupt sent after completion
4. Application I/O Interface
(a) Block Devices

 Data transferred in blocks (fixed size)

 Example: HDD, SSD
 Supports random access

(b) Character Devices

 Data transferred character by character

 Example: keyboard, mouse
 Sequential access only

5. I/O Modes
(a) Blocking I/O

 Process waits until I/O completes.

 Simple but slow.

(b) Non-blocking I/O

 Process continues execution without waiting.

 Uses polling or status check.

(c) Asynchronous I/O

 Process continues execution.

 Gets notification after completion.

(d) Vectored I/O

 Multiple I/O buffers handled in a single system call.

 Improves efficiency.
6. Principles of I/O Software
Goals:

 Device independence
 Efficiency
 Uniform interface
 Error handling
 Buffering support

7. Interrupt Handlers
Goals:

 Identify interrupt source

 Save CPU state
 Execute service routine
 Restore CPU state

Characteristics:

 Fast execution
 Priority-based handling

8. Device Drivers
 Software that controls specific hardware devices.
 Translates OS commands into device-specific actions.

Functions:

 Initialization
 Read/write operations
 Error handling
9. Device-Independent I/O Software
 Works across all devices.
 Provides uniform interface.

Functions:

 Naming devices
 Protection
 Buffering
 Allocation

10. Secondary Storage Structure

Disk Structure

 Disk contains platters, tracks, sectors, and cylinders.

Components:

 Platter → circular disk

 Track → circular path
 Sector → smallest storage unit
 Cylinder → set of tracks

11. Disk Scheduling Algorithms

(1) FCFS (First Come First Serve)

 Requests served in order.

 Simple but high seek time.

(2) SSTF (Shortest Seek Time First)

 Nearest request served first.

 Reduces seek time.

(3) SCAN (Elevator Algorithm)

 Disk arm moves in one direction servicing requests.

  Then reverses direction.

(4) C-SCAN

 Like SCAN but returns to start after reaching end.

 Provides uniform waiting time.

(5) LOOK / C-LOOK

 Similar to SCAN but only goes up to last request.

12. Other Issues

(a) Caching

 Stores frequently used data in fast memory.

 Improves performance.

(b) Scheduling

 Determines order of I/O requests.

 Reduces latency.

(c) Spooling

 Stores data temporarily before processing.

 Example: printer queue.

(d) Performance

Depends on:

 Seek time
 Rotational delay
 Transfer rate
 Scheduling algorithm
11. Disk Scheduling Algorithms (In Depth)

Introduction

Disk scheduling is the method used by the Operating System to decide the order in which
disk I/O requests are serviced. Since disk access time is high due to mechanical movement
(seek time + rotational delay), scheduling algorithms are used to reduce total seek time and
improve performance.

(1) FCFS (First Come First Serve)

Definition
In FCFS, disk requests are served in the order in which they arrive, without any optimization.

Working Principle
 Requests are placed in a queue.
 Head moves sequentially as per request arrival order.

Example
Disk queue: 82, 170, 43, 140, 24, 16, 190
Initial head position: 50

Movement:

50 → 82 → 170 → 43 → 140 → 24 → 16 → 190

Advantages
 Very simple
 No starvation

Disadvantages
 High seek time
 Poor performance for large workloads
(2) SSTF (Shortest Seek Time First)

Definition
SSTF selects the request that is closest to the current head position.

Working Principle
 At each step, choose the nearest disk request.

Example
Queue: 82, 170, 43, 140, 24, 16, 190
Head = 50

Step-by-step:

50 → 43 → 24 → 16 → 82 → 140 → 170 → 190

Advantages
 Reduces seek time compared to FCFS
 Improves throughput

Disadvantages
 May cause starvation of far requests
 Not fair for all processes

(3) SCAN (Elevator Algorithm)

Definition
In SCAN, the disk arm moves in one direction servicing requests until it reaches the end, then
reverses direction.

Working Principle
 Like an elevator moving up and down.
 Services requests in its path.

Example
Queue: 82, 170, 43, 140, 24, 16, 190
Head = 50, direction → right

Assume disk size = 0–199

Movement:

50 → 82 → 140 → 170 → 190 → (end 199) → 43 → 24 → 16

Advantages
 Better than SSTF in fairness
 No starvation

Disadvantages
 Slightly higher seek time at edges
 Middle requests may wait longer

(4) C-SCAN (Circular SCAN)

Definition
C-SCAN is a modified SCAN where the head moves in one direction only. After reaching the
end, it jumps back to the beginning.

Working Principle
 Services requests in one direction only.
 After reaching end → returns to start without servicing.

Example
Queue: 82, 170, 43, 140, 24, 16, 190
Head = 50, direction → right

Movement:

50 → 82 → 140 → 170 → 190 → (jump to 0) → 16 → 24 → 43

Advantages
 More uniform waiting time than SCAN
 Fair to all requests
Disadvantages
 Extra seek time during return jump

(5) LOOK and C-LOOK

(A) LOOK Algorithm

Definition
LOOK is similar to SCAN but the disk arm does not go to the end of the disk. It only goes
as far as the last request.

Example
Queue: 82, 170, 43, 140, 24, 16, 190
Head = 50, direction → right

Movement:

50 → 82 → 140 → 170 → 190 → 43 → 24 → 16

(Stops at last request, not at disk end)

Advantages
 Reduces unnecessary movement
 More efficient than SCAN

(B) C-LOOK Algorithm

Definition
C-LOOK is a circular version of LOOK where the head moves in one direction only and
jumps to the lowest request.

Example
Queue: 82, 170, 43, 140, 24, 16, 190
Head = 50

Movement:
50 → 82 → 140 → 170 → 190 → jump → 16 → 24 → 43

Advantages
 Most efficient circular method
 Reduces unnecessary travel

📊 Comparison Table (Very Important for

Exams)
Algorithm Seek Time Fairness Starvation Movement Type

FCFS High High No Sequential

SSTF Low Low Yes Nearest

SCAN Medium High No Bi-directional

C-SCAN Medium High No One-direction circular

LOOK Low High No Optimized SCAN

C-LOOK Lowest High No Optimized circular

Module-3 FILE MANAGEMENT, CRASH RECOVERY AND

SECURITY

3.1 File System, Directory, Storage, and Security

1. File Concept

A file is a named collection of related data stored on secondary storage. It is the basic unit of
storage in an operating system.

Characteristics:

 Persistent storage (data remains after power off)

 Identified by name
 Has attributes (metadata)

File Structure:
  Sequence of bytes / records / blocks

2. File Attributes (Metadata)

Metadata is information about a file.

Includes:

 File name
 File size
 File type
 Location
 Creation/modification time
 Permissions (read/write/execute)

3. File Types

1. Regular files – text, programs

2. Directory files – contain file names
3. Special files – device files (in UNIX)
o Character devices
o Block devices

4. File Operations

Common operations on files:

 Create
 Open
 Read
 Write
 Seek
 Delete
 Close
 Rename

5. File Access Methods

(1) Sequential Access

  Data is accessed in order
 Like tape recording

Example: reading a text file line by line

(2) Direct (Random) Access

 File is divided into blocks
 Any block can be accessed directly

Example: database systems

(3) Indexed Access

 Uses index table to access data quickly
 Combines sequential + direct access

6. Directory Structure

(1) Single-Level Directory

 One directory for all files
 Simple but naming conflicts occur

(2) Two-Level Directory

 Separate directory for each user
 Better organization

(3) Tree-Structured Directory

 Hierarchical structure (most common)
 Root → subdirectories → files

(4) DAG Directory

 Allows sharing of files using links
 No cycles allowed

(5) General Graph Directory

  Allows cycles (complex structure)

7. File System Structure

A file system is organized into layers:

1. Application programs
2. Logical file system
3. File-organization module
4. Basic file system
5. I/O control
6. Storage devices

8. File Allocation Methods

(1) Contiguous Allocation

 Files stored in continuous blocks

Formula:

Start block + length

Advantages:

 Fast access
 Simple

Disadvantages:

 External fragmentation
 File size must be known

(2) Linked Allocation

 Each block points to next block

Advantages:

 No fragmentation
 Dynamic size
Disadvantages:

 Slow random access

 Pointer overhead

(3) Indexed Allocation

 Index block stores addresses of all file blocks

Advantages:

 Supports direct access

 No external fragmentation

Disadvantages:

 Index overhead

9. Free Space Management

(1) Bit Vector (Bitmap)

 Each block represented by 0 or 1
 0 = free, 1 = occupied

Advantage:

 Simple and efficient

(2) Linked List

 Free blocks linked together

Advantage:

 No extra memory needed

Disadvantage:

 Slow traversal
(3) Grouping
 Stores addresses of free blocks in groups

Advantage:

 Faster allocation than linked list

10. File System Naming & Metadata

 File names are used for identification
 Metadata stored in file control block (FCB)

11. Directory Name Space

(1) Hierarchies
 Tree structure
 Root-based navigation

(2) DAG (Directed Acyclic Graph)

 Supports file sharing using links

(3) Hard Link

 Points directly to file inode
 File deleted only when all hard links removed

(4) Soft Link (Symbolic Link)

 Pointer to file name
 Can cross file systems
 Broken if original file deleted

12. Access Control

Used to protect files from unauthorized access.

Methods:
 Read (R)
 Write (W)
 Execute (X)

13. Existence & Concurrency Control

 Ensures multiple users access safely

 Prevents data inconsistency

Techniques:

 File locking
 Mutual exclusion

14. UNIX File System (Case Study)

Features:

 Everything is a file
 Hierarchical directory structure
 Uses inode structure

File System Components:

 Inode (metadata storage)

 Data blocks
 Directory entries

15. File System Crash Recovery

(1) Ordered Writes

 Data written in correct sequence
 Ensures consistency

(2) Write-Ahead Logging (WAL)

 Changes written to log before actual disk update
 Helps recovery after crash
16. Security & Protection

Security Environment
Protects system from unauthorized access and threats.

Design Principles of Security

 Least privilege
 Defense in depth
 Fail-safe defaults
 Access control

Protection Mechanism
(1) Protection Domain

 Set of resources a process can access

(2) Access Control List (ACL)

 Specifies permissions for each user

Example:
File A:

 User1 → read/write
 User2 → read only

17. UNIX System Calls

Used to interact with OS.

Examples:
 open()
 read()
  write()
 close()
 fork()
 exec()

18. Shell

 Command interpreter in UNIX

 Interface between user and kernel

Functions:

 Executes commands
 Script execution
 Process control

19. Privileged Instructions

 Instructions executed only in kernel mode

 Cannot be used by user programs

Examples:

 I/O control instructions

 Memory management
 Interrupt handling