I/O scheduling | Operating System - Computer Science Engineering (CSE) PDF Download

How are I/O operations performed?

Operating System has a certain portion of code that is dedicated to managing Input/Output in order to improve the reliability and the performance of the system. A computer system contains CPUs and more than one device controllers connected to a common bus channel, generally referred to as the device driver. These device drivers provide an interface to I/O devices for communicating with the system hardware promoting ease of communication providing access to shared memory.
Common Bus Controller

I/O Requests in operating systems:
I/O Requests are managed by Device Drivers in collaboration with some system programs inside the I/O device. The requests are served by OS using three simple segments :

• I/O Traffic Controller: Keeps track of the status of all devices, control units, and communication channels.
• I/O scheduler: Executes the policies used by OS to allocate and access the device, control units, and communication channels.
• I/O device handler: Serves the device interrupts and heads the transfer of data.

I/O Scheduling in operating systems:
Scheduling is used for efficient usage of computer resources avoiding deadlock and serving all processes waiting in the queue. To know more about CPU Scheduling refer to CPU Scheduling in Operating Systems.

I/O Traffic Controller has 3 main tasks :

• The primary task is to check if there’s at least one path available.
• If there exists more than one path, it must decide which one to select.
• If all paths are occupied, its task is to analyze which path will be available at the earliest.

I/O Scheduler functions similar to Process scheduler, it allocates the devices, control units, and communication channels. However, under heavy load of I/O requests, Scheduler must decide what request should be served first and for that we multiple queues to be managed by OS.

The major difference between Process scheduler< and I/O scheduler is that I/O requests are not preempted: Once the channel program has started, it’s allowed to continue to completion. Although it is feasible because programs are relatively short (50 to 100 ms). Some modern OS allows I/O Scheduler to serve and higher priority requests. In simpler words, If an I/O request has higher priority then they are served before other I/O requests with lower priority. I/O scheduler works in coordination with the I/O traffic controller to keep track of which path is being served for the current I/O request.

I/O Device Handler manages the I/O interrupts (if any) and scheduling algorithms. Few I/O handling algorithms are :

• FCFS [First come first server].
• SSTF [Shortest seek time first].
• SCAN
• Look
  • N-Step Scan
  • C-SCAN
  • C-LOOK

Every scheduling algorithm aims to minimize arm movement, mean response time, variance in response time. An overview of all I/O scheduling algorithms are described below :

1. First Come First Serve [FCFS]
It is one of the simplest device-scheduling algorithm since it is easy to program and essentially fair to users (I/O devices). The only barrier could be the high seek time, so any other algorithm that can surpass the minimum seek time is suitable for scheduling.

2. Shortest Seek Time First [SSTF]
It uses the same ideology as the Shortest Job First in process scheduling, where shortest processes are served first and longer processes have to wait for their turn. Comparing the SJF concept in I/O scheduling, the request with track closest to one being served (The one with the shortest distance to travel on disk) is next to be satisfied. The main advantage over FCFS is that it minimizes overall seek time. It favors easy-to-reach requests and postpone traveling to those that are out of the way.

3. SCAN Algorithm
SCAn uses a status flag which tells the direction of the arm, it tells whether the arm is moving towards the center of the disk or to the other side. This algorithm moves arm from the end of the disk to the center track servicing every request in its way. When it reaches innermost track, it reverses the direction and moves towards outer tracks on the disk, again servicing every request in its path.

4. LOOK [Elevator Algorithm]
It’s a variation of SCAN algorithm, here arm doesn’t necessarily go all the way to either side on disk unless there are requests pending. It looks ahead for a request before servicing it. A big question arises is “Why should we use LOOK over SCAN?”. The major advantage of LOOK over SCAN is that it discards the indefinite delay of I/O requests.

5. Other variations of SCAN

• N-Step Scan: It holds all the pending requests until the arm starts its way back. New requests are grouped for the next cycle of rotation.
• C-SCAN [Circular SCAN] : It provides a uniform wait time as the arm serves requests on its way during the inward cycle. To know more, refer Difference between SCAN and C-SCAN.
• C-LOOK [Optimized version of C-SCAN]: Arm doesn’t necessarily return to the lowest-numbered track, it returns from the lowest request to be served. It optimized the C-SCAN as the arm doesn’t move to the end of the disk if not required. To know more, refer to the Difference between C-LOOK and C-SCAN.