I/O Techniques and Disk Scheduling

1. Techniques for I/O Transfer

The central challenge in I/O is managing the vast speed difference between the fast CPU and the much slower peripheral devices. A data transfer that takes the CPU a few nanoseconds might take a disk drive several milliseconds. How the system bridges this gap defines the I/O technique.

Programmed I/O (Polling)

This is the most basic method. The CPU has direct control over the I/O process. To transfer data, the CPU executes a program that:

1. Places data in a device register or reads data from it.
2. Continuously checks a status flag on the I/O device controller to see if it is ready for the next operation (e.g., "Is the printer finished with the last character?"). This is called polling.

The main drawback is its inefficiency. The CPU spends all its time in a tight loop waiting for the slow I/O device, unable to perform any other useful work. It's like repeatedly asking a friend "Are you ready yet?" instead of doing something else while you wait.

Interrupt-driven I/O

This method improves upon polling by allowing the CPU to perform other tasks while the I/O device is busy.

1. The CPU initiates an I/O operation and then switches to executing another process.
2. When the I/O device has completed its operation, its controller sends an interrupt signal to the CPU.
3. The CPU suspends its current task, saves its state, and executes a special routine called an Interrupt Service Routine (ISR) to handle the data transfer.
4. Once the ISR is complete, the CPU restores its state and resumes the interrupted task.

This is far more efficient as the CPU is not wasted in a waiting loop. However, the CPU is still directly involved in moving every single word of data between the I/O module and memory. For large data transfers, the overhead of frequent interrupts and context switches can still be substantial.

Direct Memory Access (DMA)

DMA provides the most efficient solution for large data transfers. It involves a special-purpose processor called a DMA Controller (DMAC) that takes over the responsibility of transferring data directly between an I/O device and main memory, without involving the CPU.

The process works as follows:

1. When the CPU needs to transfer a block of data, it issues a command to the DMAC. This command includes the source address, destination address, and the total number of bytes to transfer.
2. The CPU is now free to execute other programs.
3. The DMAC manages the entire transfer. It requests control of the system bus from the CPU (often called "cycle stealing") to move data word by word from the peripheral to memory.
4. Once the entire block transfer is complete, the DMAC sends a single interrupt to the CPU to signal completion.

This offloads the entire data transfer task from the CPU, freeing it up for computational work. The CPU is only involved at the very beginning (to initiate) and the very end (to be notified).

To get a detailed, practical understanding of how DMA works, including its different modes of operation, the following video is an excellent resource.

2. Disk Scheduling Algorithms

In a multiprogramming system, it's common for multiple processes to queue up I/O requests for the disk simultaneously. Since the disk's read/write head can only be at one position at a time, the operating system must decide the order in which to service these requests. This decision-making process is called disk scheduling.

The primary goal of disk scheduling is to minimize seek time, which is the time it takes to move the read/write head to the correct track (or cylinder). As seek time is often the largest component of disk access time, efficient scheduling can significantly improve system throughput.

Let's analyze the standard disk scheduling algorithms using a common GATE-style example.

• Request Queue: 98, 183, 37, 122, 14, 124, 65, 67
• Total Tracks: 0-199
• Initial Head Position: 53

FCFS (First-Come, First-Served)

This is the simplest algorithm. It services requests in the exact order they arrive in the queue.

• Movement: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
• Pros: It's fair; no request will starve.
• Cons: It's often highly inefficient, as it can cause wild swings of the disk arm, leading to high total seek time.

You can see a full calculation for this algorithm in the GATE Wallah video.

SSTF (Shortest Seek Time First)

This algorithm selects the request that is closest to the current head position, thus minimizing seek time for the next immediate step. It is a greedy approach.

• Movement from 53:
  • The closest request to 53 is 65.
  • From 65, the closest is 67.
  • From 67, the closest is 37.
  • ... and so on.
• Pros: Significantly reduces average seek time compared to FCFS.
• Cons: Can lead to starvation. Requests at the extremes of the disk might be repeatedly ignored if a steady stream of requests arrives near the current head position.

SCAN (The Elevator Algorithm)

The SCAN algorithm works like an elevator. The disk arm starts at one end of the disk and moves towards the other end, servicing requests in its path. When it reaches the end, it reverses direction and repeats the process.

• Movement from 53 (moving towards higher tracks): 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (end of disk) → 37 → 14.
• Pros: Avoids starvation and provides more uniform wait times than SSTF.
• Cons: The head travels to the very end of the disk even if there are no pending requests in that direction.

LOOK

LOOK is a smarter version of SCAN. The head only moves as far as the last request in each direction, and then reverses. It "looks" for a request before moving to the very end of the disk.

• Movement from 53 (moving towards higher tracks): 53 → 65 → 67 → 98 → 122 → 124 → 183 (last request) → 37 → 14.
• This avoids the unnecessary travel from 183 to 199.

C-SCAN (Circular SCAN)

C-SCAN provides more uniform wait times. The head moves from one end to the other, servicing requests. When it reaches the end, it immediately returns to the beginning of the disk without servicing any requests on the return trip, and then starts scanning again. This treats the tracks as a circular list.

• Movement from 53: 53 → 65 → ... → 183 → 199 → 0 (jumps to the start) → 14 → 37.
• Pros: Provides better response time uniformity, as requests at the end of the scan don't have to wait for the head to service the entire return trip.

C-LOOK

This is the LOOK version of C-SCAN. The head only scans as far as the last request in its path, then jumps to the first request at the other end of the queue and starts scanning again.

• Movement from 53: 53 → 65 → ... → 183 (last request) → 14 (jumps to first request in the other direction) → 37.
• This is often one of the most practical and balanced algorithms.

Finally, to test your understanding, consider this classic GATE question. In a system with a uni-programmed OS (only one user process can be active at a time), what is the expected performance improvement if the disk scheduler is changed from FCFS to SSTF?

The answer is 0% improvement. Why? In a uni-programmed system, there is only one process making I/O requests. This means the disk request queue will never have more than one request at a time. With only one request, every scheduling algorithm (FCFS, SSTF, SCAN, etc.) behaves identically. There is no choice to be made, so changing the algorithm has no effect. This highlights the importance of understanding the underlying OS concepts.

Conclusion

This lesson completes our journey through Computer Organization and Architecture. We have bridged the gap between the CPU and the outside world by exploring how data is transferred and how access to shared devices like disks is managed.

Key Takeaways:

• I/O Techniques manage the speed gap between the CPU and peripherals.
  • Programmed I/O: Simple, but the CPU is 100% busy polling the device.
  • Interrupt-driven I/O: More efficient as the CPU can do other work, but it's still involved in the data transfer itself.
  • DMA: Most efficient for large transfers, as a dedicated controller handles the entire process, only interrupting the CPU upon completion.
• Disk Scheduling Algorithms aim to minimize seek time by intelligently ordering a queue of disk requests.
  • FCFS: Fair but inefficient.
  • SSTF: Greedy and efficient but can cause starvation.
  • SCAN/LOOK: Elevator-like motion, prevents starvation.
  • C-SCAN/C-LOOK: Circular motion, provides more uniform wait times.

With this, you have a solid understanding of how a computer system is organized, from the control unit and data path, through the memory hierarchy, and out to the peripheral devices.

In our next lesson, we will pivot from hardware to software. We begin Module 6: Programming in C & Recursion, starting with the fundamentals of the C language. This will lay the groundwork for our future studies in Data Structures and Algorithms.