Unit 5

I/O Management and Disk Scheduling

I/O Devices
1. Definition

I/O (Input/Output) devices are hardware components that allow a computer system to receive
input from the user or external environment and provide output back to the user or another
system.

2. Types of I/O Devices

I/O devices can be categorized into:

 Input Devices: Devices that send data into the computer.

Examples: Keyboard, Mouse, Scanner, Microphone
 Output Devices: Devices that receive data from the computer.
Examples: Monitor, Printer, Speaker
 Input/Output Devices: Devices that can both send and receive data.
Examples: Hard Disk, Touchscreen, USB Flash Drive

3. Characteristics of I/O Devices

 Speed: Different devices operate at different speeds.

 Data Transfer Mode: Some transfer one character at a time, others transfer blocks.
 Access Mode: Some devices use random access (e.g., hard disks), others sequential
(e.g., magnetic tape).
 Data Format: Data may need to be converted between formats (e.g., analog to
digital).

4. Communication Between CPU and I/O Devices

 Ports: Interfaces through which the CPU communicates with devices.

 Buses: Shared communication pathways (data bus, address bus, control bus).
 Device Controllers: Special hardware components that manage specific devices and
act as intermediaries between devices and the CPU.

5. Device Controllers
Each I/O device is managed by a device controller, which includes:

 Control Registers: To send commands

 Status Registers: To receive status or error info
 Data Buffer: Temporary storage for data transfer

The OS communicates with the controller to start and monitor operations.

6. I/O Communication Techniques

 Programmed I/O: The CPU waits while the I/O operation completes (polling
method).
 Interrupt-Driven I/O: The CPU continues other tasks and is interrupted when the
I/O is done.
 Direct Memory Access (DMA): The device transfers data directly to/from memory
without CPU involvement. It is used for high-speed data transfer.

7. Device Drivers

 A device driver is a software program that allows the OS to communicate with a

hardware device.
 It translates high-level OS commands into low-level hardware-specific commands.
 Every device type (and model) typically has its own driver.

8. Responsibilities of the OS in I/O Device Management

 Buffering: Temporarily holding data during transfer to match speed differences.

 Caching: Keeping copies of frequently accessed data in faster memory.
 Spooling: Managing queues of I/O requests (e.g., for printers).
 Error Handling: Detecting and correcting I/O errors.
 Scheduling: Choosing the order of I/O operations when multiple requests exist.

I/O Subsystems
1. Definition

The I/O subsystem is a part of the operating system responsible for managing all
input/output operations. It acts as an intermediary between user-level processes and the
hardware devices.
It provides a uniform interface to interact with a variety of I/O devices while abstracting
device-specific details.

2. Components of the I/O Subsystem

The I/O subsystem consists of the following key components:

a. I/O Scheduling

 Determines the order in which I/O requests are processed.

 Important for improving overall system performance.
 Common in disk scheduling to reduce seek time.

b. Buffering

 Temporary storage used during data transfer between devices and memory.
 Helps deal with speed mismatches between producer (CPU) and consumer (device).
 Types: Single buffering, double buffering, circular buffering.

c. Caching

 Stores frequently accessed data in a faster storage medium (e.g., RAM).

 Reduces the need to access slower devices repeatedly.

d. Spooling

 Stands for Simultaneous Peripheral Operations On-Line.

 Used to queue data for devices that cannot handle interleaved requests (e.g., printers).
 Allows jobs to be processed in the background.

e. Device Drivers

 Software components that translate generic I/O instructions into device-specific

operations.
 Each device has its own driver, which the OS uses to control the device.

3. Role of the I/O Subsystem

 Abstracts device details from user-level processes.

 Manages I/O requests, converting them into device-level operations.
 Handles errors and retries failed I/O operations.
 Implements protection mechanisms to ensure device access is controlled and safe.
 Improves performance via scheduling, buffering, and caching.
4. Advantages of Using an I/O Subsystem

 Simplifies user-level programming by hiding hardware details.

 Enables device independence—programs can run with different devices without
modification.
 Enhances efficiency through parallelism (overlapping CPU and I/O operations).
 Facilitates better error detection and recovery.

5. Interaction Between Components

When a user process makes an I/O request:

1. The OS routes the request to the appropriate device driver.

2. The driver communicates with the device controller.
3. Buffering and caching may be used during the data transfer.
4. Interrupts notify the OS when the operation is complete.
5. The OS informs the user process.

I/O Buffering
1. Definition

I/O Buffering is a technique used in operating systems where a region of memory (called a
buffer) is used as a temporary storage area for data being transferred between two devices or
between a device and an application.

It helps manage differences in speed between the producer (e.g., CPU) and consumer (e.g.,
I/O device) and ensures smoother data transfer.

2. Purpose of Buffering

 Match speed differences between devices and CPU

 Reduce waiting time for the CPU or device
 Improve system performance through overlapping I/O and computation
 Minimize the number of direct device accesses

3. Types of Buffering
a. Single Buffering

 Only one buffer is used between the I/O device and memory.
 While the buffer is being filled or emptied, the process must wait.
 Simple but may lead to idle CPU or device time.

b. Double Buffering (Ping-Pong Buffering)

 Two buffers are used. While one is being filled, the other can be emptied.
 Allows overlapping of I/O and processing.
 Reduces waiting time and increases efficiency.

c. Circular Buffering (Multibuffering)

 More than two buffers are used in a circular queue structure.

 Suitable for systems where data arrives continuously (e.g., video streaming).
 Helps avoid overflow or underflow conditions.

4. How Buffering Works

1. A buffer is allocated in memory.

2. Data from an input device is written into the buffer.
3. Once the buffer is full (or a portion is ready), data is transferred to the application.
4. For output, the application writes to the buffer, and the device reads from it.

This allows one operation (e.g., input) to occur while another (e.g., processing) proceeds in
parallel.

5. Buffering in Input vs Output

 Input Buffering: Temporarily stores incoming data before it's consumed by the
application.
Example: Keystrokes from a keyboard are buffered before reaching a text editor.
 Output Buffering: Temporarily holds data from the application before it's sent to the
output device.
Example: Data to be printed is buffered before being sent to the printer.

6. Advantages of Buffering

 Increases throughput of the system

 Reduces idle time for CPU and I/O devices
 Allows asynchronous data transfer
 Supports real-time applications with smoother performance
7. Disadvantages

 Consumes memory
 Adds complexity to I/O management
 May lead to latency if not managed properly

Disk Storage
1. Overview

Disk storage refers to the use of magnetic disks to store data persistently. These disks are
commonly used as secondary storage in computer systems.

2. Disk Structure

 A disk is divided into platters, each with tracks.

 Tracks are further divided into sectors, the smallest unit of storage on a disk.
 Multiple tracks at the same radius on different platters form a cylinder.
 The disk head moves across tracks to perform read/write operations.

3. Components

 Platter: A circular disk coated with magnetic material.

 Spindle: Rotates the platters at a constant speed (e.g., 5400 RPM, 7200 RPM).
 Read/Write Head: Positioned on a movable arm, reads and writes data.
 Actuator Arm: Moves the head to the desired track.
 Controller: Manages data transfer between the disk and the computer.

4. Access Time

The total time to access data on disk includes:

 Seek Time: Time taken to move the head to the required track.
 Rotational Latency: Time taken for the desired sector to rotate under the head.
 Transfer Time: Time to read/write the data once the head is in position.

Disk Scheduling
1. Need for Disk Scheduling

 Multiple I/O requests may be waiting for disk access.

 Proper scheduling can reduce seek time, improve throughput, and maximize
system performance.
2. Disk Scheduling Algorithms

a. FCFS (First Come First Serve)

 Requests are served in the order they arrive.

 Simple but can cause long wait times and large seek times.

b. SSTF (Shortest Seek Time First)

 Chooses the request closest to the current head position.

 Reduces total seek time but may cause starvation of distant requests.

c. SCAN (Elevator Algorithm)

 The disk arm moves in one direction, servicing all requests, then reverses.
 Fair and better performance than FCFS and SSTF.

d. C-SCAN (Circular SCAN)

 Like SCAN, but after reaching one end, the arm returns to the beginning without
servicing requests on the return trip.
 Provides uniform wait time.

e. LOOK

 Similar to SCAN, but the arm only goes as far as the last request in each direction.

f. C-LOOK

 Like C-SCAN, but the arm returns to the first request instead of going to the start of
the disk.

3. Comparison of Algorithms

Algorithm Pros Cons

FCFS Simple Poor performance with high seek time

SSTF Efficient Can lead to starvation

SCAN Fair, improved performance Higher variance in response time

C-SCAN Uniform wait time May involve unnecessary movement

LOOK Efficient, avoids unnecessary travel Slightly more complex

C-LOOK Uniform wait time Not always best for real-time systems
4. Selection Criteria for Disk Scheduling

 Seek time optimization

 Fairness (avoid starvation)
 Real-time requirements
 Request arrival patterns
 Workload type (e.g., batch vs interactive)

Problem Setup
 Request queue: 98, 183, 37, 122, 14, 124, 65, 67
 Initial head position: 53
 Disk range: 0 – 199

1. FCFS (First Come First Serve)

Order of servicing: 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

Seek operations:

 |53 − 98| = 45
 |98 − 183| = 85
 |183 − 37| = 146
 |37 − 122| = 85
 |122 − 14| = 108
 |14 − 124| = 110
 |124 − 65| = 59
 |65 − 67| = 2

Total seek time = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders

Average seek time = 640 / 8 = 80 cylinders

2. SSTF (Shortest Seek Time First)

Initial head: 53
Request closest to 53: 65
Next closest: 67 → 37 → 14 → 98 → 122 → 124 → 183

Order of servicing: 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

Seek operations:

 |53 − 65| = 12
 |65 − 67| = 2
 |67 − 37| = 30
 |37 − 14| = 23
 |14 − 98| = 84
 |98 − 122| = 24
 |122 − 124| = 2
 |124 − 183| = 59

Total seek time = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders

Average seek time = 236 / 8 = 29.5 cylinders

3. SCAN (Elevator Algorithm)

Initial direction: Head moves toward 0 (lower cylinders)

Order: 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183

Seek operations:

 |53 − 37| = 16
 |37 − 14| = 23
 |14 − 0| = 14
 |0 − 65| = 65
 |65 − 67| = 2
 |67 − 98| = 31
 |98 − 122| = 24
 |122 − 124| = 2
 |124 − 183| = 59

Total seek time = 16 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59 = 236 cylinders

Average seek time = 236 / 8 = 29.5 cylinders

4. C-SCAN (Circular SCAN)

Initial direction: Head moves toward 0
After reaching 0, it jumps to 199 and continues from there.

Order: 37 → 14 → 0 → (jump to 199) → 183 → 124 → 122 → 98 → 67 → 65

Seek operations:

 |53 − 37| = 16
  |37 − 14| = 23
 |14 − 0| = 14
 |0 − 199| = 199 (circular jump)
 |199 − 183| = 16
 |183 − 124| = 59
 |124 − 122| = 2
 |122 − 98| = 24
 |98 − 67| = 31
 |67 − 65| = 2

Total seek time = 16 + 23 + 14 + 199 + 16 + 59 + 2 + 24 + 31 + 2 = 386 cylinders

Average seek time = 386 / 8 = 48.25 cylinders

5. LOOK
Initial direction: Toward 0
Head only goes as far as the furthest request (14), then reverses.

Order: 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183

Seek operations:

 |53 − 37| = 16
 |37 − 14| = 23
 |14 − 65| = 51
 |65 − 67| = 2
 |67 − 98| = 31
 |98 − 122| = 24
 |122 − 124| = 2
 |124 − 183| = 59

Total seek time = 16 + 23 + 51 + 2 + 31 + 24 + 2 + 59 = 208 cylinders

Average seek time = 208 / 8 = 26 cylinders

Summary Table
Algorithm Total Seek Time Average Seek Time
FCFS 640 80
SSTF 236 29.5
SCAN 236 29.5
C-SCAN 386 48.25
LOOK 208 26
RAID (Redundant Array of Independent Disks)
1. Definition

RAID is a data storage virtualization technology that combines multiple physical disk drives
into one logical unit to improve performance, increase storage capacity, and provide
redundancy for fault tolerance.

Originally, RAID stood for Redundant Array of Inexpensive Disks, but today it's more
commonly referred to as Independent Disks.

2. Objectives of RAID

 Improved Performance: By reading/writing data in parallel across multiple disks.

 Fault Tolerance: By storing redundant data (parity or mirroring) so that data is not
lost if a disk fails.
 Increased Capacity: By combining multiple disks into one logical volume.

3. RAID Levels

RAID 0 (Striping)

 Data is divided into blocks and distributed (striped) across multiple disks.
 No redundancy — if one disk fails, all data is lost.
 High performance, no fault tolerance.

Use case: High-speed applications where data loss is acceptable.

RAID 1 (Mirroring)

 Data is duplicated (mirrored) on two disks.

 If one disk fails, the other contains a complete copy.
 High reliability, lower storage efficiency (50% capacity usage).

Use case: Critical data storage where redundancy is important.

RAID 5 (Striping with Parity)

 Data and parity (error checking information) are striped across all disks.
 Can tolerate the failure of one disk.
 Efficient use of disk space, good read performance, moderate write performance.
Use case: General-purpose servers, database systems.

RAID 6 (Striping with Double Parity)

 Like RAID 5, but with two sets of parity, allowing the failure of two disks.
 More fault-tolerant than RAID 5.
 Slower writes due to extra parity calculations.

Use case: Mission-critical applications requiring high fault tolerance.

RAID 10 (RAID 1 + RAID 0, also called RAID 1+0)

 Combines mirroring and striping.

 Provides redundancy and performance.
 Requires at least 4 disks.

Use case: High-performance databases and applications with heavy I/O.

4. Comparison Table

RAID Level Min. Disks Fault Tolerance Storage Efficiency Read Speed Write Speed

RAID 0 2 None 100% High High

RAID 1 2 1 disk 50% High Medium

RAID 5 3 1 disk (N−1)/N High Medium

RAID 6 4 2 disks (N−2)/N Medium Low

RAID 10 4 Up to 2 disks 50% Very High High

5. Advantages of RAID

 Increased data reliability and availability

 Improved performance (especially in RAID 0, 5, 10)
 Can be implemented via hardware or software

6. Disadvantages of RAID

 Increased cost due to multiple disks

 Complexity in setup and management
  Some RAID levels (e.g., RAID 5/6) have write penalty due to parity calculation
 Not a substitute for backups — RAID protects against hardware failure, not data
corruption or deletion

[Link] System
Definition

A file system is the method and data structure that an operating system uses to manage files
on a disk or partition. It controls how data is stored, organized, accessed, and retrieved.

2. File Concept
What is a File?

A file is a collection of related data stored on a storage device. It acts as the basic unit of
storage for data, programs, and documents.

File Attributes

Each file has associated metadata called file attributes, such as:

 Name: Identifier used by users

 Type: e.g., .txt, .exe, .jpg
 Location: Physical address on the disk
 Size: Current file size in bytes
 Protection: Access permissions (read, write, execute)
 Time and Date: Creation, modification, and last access times

File Operations

Operating systems provide a set of operations to manage files:

 Create: Allocate space and metadata

 Open/Close: Prepare file for reading/writing
 Read/Write: Transfer data between memory and file
 Delete: Remove file and free space
 Rename: Change file identifier
 Truncate: Delete file contents but keep metadata

3. File Organization
File organization refers to the way records are stored within a file. It impacts performance,
storage efficiency, and access time.

a. Sequential File Organization

 Records are stored in sequential order (by key or time of entry).

 Reading must be done sequentially.
 Best suited for batch processing (e.g., payroll).

Advantages:

 Simple and efficient for large volume data processing.

Disadvantages:

 Insertion and deletion are inefficient.

 Random access is slow.

b. Direct (or Random) File Organization

 Records are stored at calculated locations using a hash function.

 Allows direct access to records.

Advantages:

 Fast access and retrieval.

 Suitable for real-time applications.

Disadvantages:

 Collisions in hash values require resolution.

 Complex management.

c. Indexed File Organization

 Uses an index to map keys to the physical location of records.

 Like a book index pointing to page numbers.

Advantages:

 Efficient for both sequential and direct access.

 Suitable for applications with frequent searches.

Disadvantages:
  Extra overhead for maintaining the index.
 Slower for simple sequential reads compared to purely sequential organization.

4. File Access Mechanisms

Access mechanisms define how data is read from or written to a file.

a. Sequential Access

 Data is accessed in order, one record after the other.

 Common for text editors, compilers.

Example: Reading a log file line-by-line.

b. Direct (or Random) Access

 Data is accessed by specifying the exact location (offset).

 Suitable for databases and multimedia.

Example: Jumping to the 5th record in a file.

c. Indexed Access

 Uses an index table to locate the desired record.

 Combines features of sequential and direct access.

Example: Searching for a word in a dictionary app.

Summary Table
Feature Sequential Direct Indexed
Access Type Linear By position By index + offset
Access Speed Slow for random Fast Moderate to fast
Insertion/Deletion Inefficient Efficient Moderate
Use Cases Logs, reports Databases Libraries, indexes

1. File Directories
What is a Directory?

A directory is a special type of file that contains metadata about other files and directories. It
acts like a folder that organizes files in a hierarchical structure.

Purpose of Directories

 To organize files for easy access and management.

 To maintain file attributes such as file name, location, size, etc.
 To provide a path structure to locate files efficiently.

Directory Structure Types

a. Single-Level Directory

 All files are contained in one directory.

 Simple but not scalable for multiple users or large number of files.
 File name collisions are common.

b. Two-Level Directory

 Separate directories for each user.

 User directories contain that user’s files.
 Avoids name collisions among users.

c. Tree-Structured Directory

 Directories can contain files and other directories (subdirectories).

 Forms a hierarchical tree structure.
 Used by most modern OS (e.g., Windows, Linux).

d. Acyclic-Graph Directory

 Allows sharing of files/directories by having links.

 Can have multiple parent directories (hard links).

e. General Graph Directory

 Allows cycles (with symbolic links), which need special handling to avoid infinite
loops.

Directory Operations
  Create/Delete directory
 Add/Delete file
 Search for file
 Traverse directories

2. File Sharing
Purpose of File Sharing

Allows multiple users or processes to access the same file concurrently, improving
collaboration and resource utilization.

File Sharing Methods

a. Read-only Sharing

 Multiple users can read the file simultaneously.

 No write conflicts.

b. Read-Write Sharing

 Users can read and write the file.

 Requires mechanisms to prevent data corruption.

Issues in File Sharing

 Consistency: Ensuring all users see the latest updates.

 Synchronization: Managing concurrent access (locks, semaphores).
 Security and Protection: Controlling access rights to prevent unauthorized use.

File Sharing Mechanisms

a. Access Control

 Assigns permissions (read, write, execute) to users/groups.

b. File Locking

 Locks the file or parts of it during write operations to prevent conflicts.

c. Record Locking

 Locks only specific records within a file, allowing finer control.

d. Copy-on-Write

 Creates private copies for users to edit, then merges changes.

Summary Table

Feature Description

Directory Types Single-level, Two-level, Tree, Graph

Sharing Methods Read-only, Read-write

Sharing Issues Consistency, Synchronization, Security

Protection Access control, File/Record locking

File System Implementation Issues

Implementing a file system involves various challenges to ensure efficient, reliable, and
secure file storage and access. The main issues are:

1. File Metadata Management

 Storing file attributes such as file name, type, size, creation/modification timestamps,
and permissions.
 Metadata must be updated correctly with each file operation.
 Typically stored in structures like inodes (in Unix/Linux) or File Control Blocks
(FCBs).

2. Mapping Files to Disk Blocks

 Files are stored in disk blocks (fixed-size units).

 The file system must map logical file data to physical disk blocks.
 Common techniques include:
o Contiguous Allocation: Stores files in consecutive blocks. Simple and fast
but leads to fragmentation.
 o Linked Allocation: Each block points to the next. No fragmentation but poor
random access performance.
o Indexed Allocation: Uses an index block that holds pointers to all file blocks,
allowing direct access.

3. Free Space Management

 The system must keep track of free disk space for new file allocations.
 Common methods:
o Bit Vector: Each bit represents a disk block (0 = free, 1 = occupied).
o Linked List: Free blocks linked together.
o Grouping: Stores addresses of free blocks in groups.
o Counting: Keeps track of number of free blocks together.

4. Directory Implementation

 Directory entries must map file names to metadata and disk locations.
 Implemented as:
o Linear lists: Simple but slow search for large directories.
o Hash tables: Faster search, but more complex.
 Must handle addition, deletion, and renaming of files.

5. File Access Control and Security

 Implementing protection mechanisms like access permissions.

 Managing user and group rights.
 Ensuring unauthorized users cannot read/write files.

6. Performance Optimization

 Efficient disk scheduling and buffering to reduce seek and latency.

 Caching frequently accessed data and metadata in memory.
 Minimizing fragmentation to maintain fast access.

7. Reliability and Recovery

 Handling system crashes, power failures without losing data.

 Use of journaling or log-based file systems to record changes before applying.
 Backup and restore mechanisms.
8. Support for Large Files and Large Number of Files

 File system must scale to handle:

o Large files (multi-gigabyte or terabyte range).
o Large directories with thousands or millions of files.
 Efficient indexing and block mapping schemes required.

9. File Sharing and Concurrency Control

 Handling concurrent access to files.

 Synchronization mechanisms to prevent data corruption (file locking, record locking).
 Ensuring consistency and isolation in multi-user environments.

10. Portability and Compatibility

 File system design should consider portability across different hardware and OS.
 Compatibility with existing file systems and data formats for migration.

Summary Table
Issue Description
Metadata Management Storing/updating file attributes
Disk Block Mapping Allocating disk blocks efficiently
Free Space Management Tracking available disk space
Directory Implementation Efficient file name to metadata mapping
Access Control & Security Implementing permissions and protection
Performance Optimization Buffering, caching, reducing fragmentation
Reliability & Recovery Crash recovery, journaling
Scalability Supporting large files and directories
File Sharing & Concurrency Synchronization, locking
Portability & Compatibility Support across platforms and file system types

File System Protection and Security

1. What is File System Protection?

Protection in a file system ensures that files and directories are accessed and modified only
by authorized users and programs, preventing unauthorized access and data corruption.

2. Goals of File System Protection

 Prevent unauthorized access to files

 Control user permissions on files and directories
 Ensure data integrity and confidentiality
 Support multiple users with different access levels
 Prevent accidental or malicious modification/deletion

3. Types of File Access Rights

Common access permissions include:

Permission Meaning

Read (r) Ability to read the file contents

Write (w) Ability to modify or delete the file

Execute (x) Ability to run the file (if executable)

Append Ability to add data to the end of file

4. Protection Mechanisms

a. Access Control Lists (ACLs)

 Each file/directory has a list specifying users and their allowed operations.
 Example: User A can read/write; User B can read only.

b. User/Group/Other Permissions

 Users are categorized as owner, group, or others.

 Permissions are assigned separately for each category.
 Typical in Unix/Linux systems, e.g., rwxr-xr--.

c. Password Protection

 Files or directories may require authentication to access.

 Used in some systems and applications.
5. Authentication and Authorization

 Authentication confirms user identity (passwords, biometrics).

 Authorization determines what resources the authenticated user can access.

6. File Encryption

 Encrypt files to ensure data confidentiality.

 Only users with correct keys can read the contents.
 Protects data from unauthorized access even if physical storage is compromised.

7. File Locking

 Prevents multiple users from writing to the same file simultaneously.

 Types:
o Shared lock (multiple readers, no writers)
o Exclusive lock (one writer, no readers)

8. Audit and Logging

 Keeps track of file access, modifications, and security violations.

 Helps in detecting unauthorized access and forensic analysis.

9. Backup and Recovery

 Protect data by regular backups.

 Quickly restore files after accidental or malicious damage.

Summary Table

Protection Aspect Description

Access Rights Read, write, execute permissions

Access Control Lists Fine-grained user-specific permissions

User/Group/Other Model Unix-style permission grouping

Authentication User identity verification

Encryption Data confidentiality via encoding

 Protection Aspect Description

File Locking Prevents conflicting concurrent access

Auditing Monitoring and logging access

Backup Data protection via periodic copies