MODULE-6

One of the important jobs of an Operating System is to manage various I/O devices including
mouse, keyboards, touch pad, disk drives, display adapters, USB devices, Bit-mapped screen,
LED, Analog-to-digital converter, On/off switch, network connections, audio I/O, printers
etc.
An I/O system is required to take an application I/O request and send it to the physical
device, then take whatever response comes back from the device and send it to the
application. I/O devices can be divided into two categories –
 Block devices − A block device is one with which the driver communicates by
sending entire blocks of data. For example, Hard disks, USB cameras, Disk-On-Key
etc.
 Character devices − A character device is one with which the driver communicates
by sending and receiving single characters (bytes, octets). For example, serial ports,
parallel ports, sounds cards etc.

Device Controllers

Device drivers are software modules that can be plugged into an OS to handle a particular
device. Operating System takes help from device drivers to handle all I/O devices.

The Device Controller works like an interface between a device and a device driver. I/O units
(Keyboard, mouse, printer, etc.) typically consist of a mechanical component and an
electronic component where electronic component is called the device controller.

There is always a device controller and a device driver for each device to communicate with
the Operating Systems. A device controller may be able to handle multiple devices. As an
interface its main task is to convert serial bit stream to block of bytes, perform error
correction as necessary.

Any device connected to the computer is connected by a plug and socket, and the socket is
connected to a device controller. Following is a model for connecting the CPU, memory,
controllers, and I/O devices where CPU and device controllers all use a common bus for
communication.
Synchronous vs asynchronous I/O

 Synchronous I/O − In this scheme CPU execution waits while I/O proceeds
 Asynchronous I/O − I/O proceeds concurrently with CPU execution

Communication to I/O Devices (I/O Organization)

The CPU must have a way to pass information to and from an I/O device. There are three
approaches available to communicate with the CPU and Device.

 Special Instruction I/O

 Memory-mapped I/O
 Direct memory access (DMA)

Special Instruction I/O

This uses CPU instructions that are specifically made for controlling I/O devices. These
instructions typically allow data to be sent to an I/O device or read from an I/O device.

Interrupts I/O
An alternative scheme for dealing with I/O is the interrupt-driven method. An interrupt is a
signal to the microprocessor from a device that requires attention.

A device controller puts an interrupt signal on the bus when it needs CPU’s attention when
CPU receives an interrupt, It saves its current state and invokes the appropriate interrupt
handler using the interrupt vector (addresses of OS routines to handle various events). When
the interrupting device has been dealt with, the CPU continues with its original task as if it
had never been interrupted.

Direct Memory Access (DMA)

Slow devices like keyboards will generate an interrupt to the main CPU after each byte is
transferred. If a fast device such as a disk generated an interrupt for each byte, the operating
system would spend most of its time handling these interrupts. So a typical computer uses
direct memory access (DMA) hardware to reduce this overhead.

Direct Memory Access (DMA) means CPU grants I/O module authority to read from or write
to memory without involvement. DMA module itself controls exchange of data between main
memory and the I/O device. CPU is only involved at the beginning and end of the transfer
and interrupted only after entire block has been transferred.

Direct Memory Access needs a special hardware called DMA controller (DMAC) that
manages the data transfers and arbitrates access to the system bus. The controllers are
programmed with source and destination pointers (where to read/write the data), counters to
track the number of transferred bytes, and settings, which includes I/O and memory types,
interrupts and states for the CPU cycles.
The operating system uses the DMA hardware as follows −

Step Description

1 Device driver is instructed to transfer disk data to a buffer address X.

2 Device driver then instruct disk controller to transfer data to buffer.

3 Disk controller starts DMA transfer.

4 Disk controller sends each byte to DMA controller.

DMA controller transfers bytes to buffer, increases the memory address, decreases
5
the counter C until C becomes zero.

6 When C becomes zero, DMA interrupts CPU to signal transfer completion.

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 :
1. I/O Traffic Controller: Keeps track of the status of all devices, control units, and
communication channels.
2. I/O scheduler: Executes the policies used by OS to allocate and access the device,
control units, and communication channels.
3. 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.
Scheduling in computing is the process of allocating resources to carry out tasks.
Processors, network connections, or expansion cards are examples of the resources. The
tasks could be processes, threads, or data flows.

A process referred to as a scheduler is responsible for scheduling. Schedulers are frequently

made to keep all computer resources active (as in load balancing), efficiently divide up
system resources among multiple users, or reach a desired level of service.
I/O Scheduler functions similarly to Process scheduler, it allocates the devices, control
units, and communication channels. However, under a 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 a Process scheduler< and an 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 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. The 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.

I/O buffering and its Various Techniques

A buffer is a memory area that stores data being transferred between two devices or between
a device and an application. Uses of I/O Buffering :
 Buffering is done to deal effectively with a speed mismatch between the producer and
consumer of the data stream.
 A buffer is produced in main memory to heap up the bytes received from modem.
 After receiving the data in the buffer, the data get transferred to disk from buffer in a
single operation.
 This process of data transfer is not instantaneous, therefore the modem needs another
buffer in order to store additional incoming data.
 When the first buffer got filled, then it is requested to transfer the data to disk.
 The modem then starts filling the additional incoming data in the second buffer while the
data in the first buffer getting transferred to disk.
 When both the buffers completed their tasks, then the modem switches back to the first
buffer while the data from the second buffer get transferred to the disk.
 The use of two buffers disintegrates the producer and the consumer of the data, thus
minimizes the time requirements between them.
 Buffering also provides variations for devices that have different data transfer sizes.

Types of various I/O buffering techniques:

1. Single buffer: A buffer is provided by the operating system to the system portion of
the main memory.
2. Block oriented device –
 System buffer takes the input.
 After taking the input, the block gets transferred to the user space by the process and then
the process requests for another block.
 Two blocks works simultaneously, when one block of data is processed by the user
process, the next block is being read in.
 OS can swap the processes.
 OS can record the data of system buffer to user processes.
3. Stream oriented device –
 Line- at a time operation is used for scroll made terminals. User inputs one line at a time,
with a carriage return signaling at the end of a line.
 Byte-at a time operation is used on forms mode, terminals when each keystroke is
significant.

2. Double buffer
4. Block oriented –
 There are two buffers in the system.
 One buffer is used by the driver or controller to store data while waiting for it to be taken
by higher level of the hierarchy.
 Other buffer is used to store data from the lower level module.
 Double buffering is also known as buffer swapping.
 A major disadvantage of double buffering is that the complexity of the process get
increased.
 If the process performs rapid bursts of I/O, then using double buffering may be deficient.
Stream oriented –
 Line- at a time I/O, the user process need not be suspended for input or output, unless
process runs ahead of the double buffer.
 Byte- at a time operations, double buffer offers no advantage over a single buffer of twice
the length.
 3. Circular buffer
:
 When more than two buffers are used, the collection of buffers is itself referred to as a
circular buffer.
 In this, the data do not directly passed from the producer to the consumer because the
data would change due to overwriting of buffers before they had been consumed.
 The producer can only fill up to buffer i-1 while data in buffer i is waiting to be
consumed.

RAID
RAID is a technique that makes use of a combination of multiple disks instead of using a
single disk for increased performance, data redundancy, or both. The term was coined by
David Patterson, Garth A. Gibson, and Randy Katz at the University of California,
Berkeley in 1987.
Data Redundancy
Data redundancy, although taking up extra space, adds to disk reliability. This means, that
in case of disk failure, if the same data is also backed up onto another disk, we can retrieve
the data and go on with the operation. On the other hand, if the data is spread across
multiple disks without the RAID technique, the loss of a single disk can affect the entire
data.
Key Evaluation Points for a RAID System
 Reliability: How many disk faults can the system tolerate?
 Availability: What fraction of the total session time is a system in uptime mode, i.e.
how available is the system for actual use?
 Performance: How good is the response time? How high is the throughput (rate of
processing work)? Note that performance contains a lot of parameters and not just the
two.
 Capacity: Given a set of N disks each with B blocks, how much useful capacity is
available to the user?
RAID is very transparent to the underlying system. This means, that to the host system, it
appears as a single big disk presenting itself as a linear array of blocks. This allows older
technologies to be replaced by RAID without making too many changes to the existing
code.

Different RAID Levels

1. RAID-0 (Stripping)
2. RAID-1 (Mirroring)
3. RAID-2 (Bit-Level Stripping with Dedicated Parity)
4. RAID-3 (Byte-Level Stripping with Dedicated Parity)
5. RAID-4 (Block-Level Stripping with Dedicated Parity)
6. RAID-5 (Block-Level Stripping with Distributed Parity)
7. RAID-6 (Block-Level Stripping with two Parity Bits)

Raid Controller
1. RAID-0 (Stripping)
 Blocks are “stripped” across disks.

RAID-0

 In the figure, blocks “0,1,2,3” form a stripe.

 Instead of placing just one block into a disk at a time, we can work with two (or more)
blocks placed into a disk before moving on to the next one.

Raid-0

Evaluation
 Reliability: 0
There is no duplication of data. Hence, a block once lost cannot be recovered.
 Capacity: N*B
The entire space is being used to store data. Since there is no duplication, N disks each
having B blocks are fully utilized.
Advantages
1. It is easy to implement.
2. It utilizes the storage capacity in a better way.
Disadvantages
1. A single drive loss can result in the complete failure of the system.
2. Not a good choice for a critical system.
2. RAID-1 (Mirroring)
 More than one copy of each block is stored in a separate disk. Thus, every block has
two (or more) copies, lying on different disks.

Raid-1

 The above figure shows a RAID-1 system with mirroring level 2.

 RAID 0 was unable to tolerate any disk failure. But RAID 1 is capable of reliability.
Evaluation
Assume a RAID system with mirroring level 2.

 Reliability: 1 to N/2
1 disk failure can be handled for certain because blocks of that disk would have
duplicates on some other disk. If we are lucky enough and disks 0 and 2 fail, then
again this can be handled as the blocks of these disks have duplicates on disks 1 and 3.
So, in the best case, N/2 disk failures can be handled.
 Capacity: N*B/2
Only half the space is being used to store data. The other half is just a mirror of the
already stored data.
Advantages
1. It covers complete redundancy.
2. It can increase data security and speed.
Disadvantages
1. It is highly expensive.
2. Storage capacity is less.
3. RAID-2 (Bit-Level Stripping with Dedicated Parity)
 In Raid-2, the error of the data is checked at every bit level. Here, we use Hamming
Code Parity Method to find the error in the data.
 It uses one designated drive to store parity.
 The structure of Raid-2 is very complex as we use two disks in this technique. One
word is used to store bits of each word and another word is used to store error code
correction.
 It is not commonly used.
Advantages
1. In case of Error Correction, it uses hamming code.
2. It Uses one designated drive to store parity.
Disadvantages
1. It has a complex structure and high cost due to extra drive.
2. It requires an extra drive for error detection.

4. RAID-3 (Byte-Level Stripping with Dedicated Parity)

 It consists of byte-level striping with dedicated parity striping.
 At this level, we store parity information in a disc section and write to a dedicated
parity drive.
 Whenever failure of the drive occurs, it helps in accessing the parity drive, through
which we can reconstruct the data.

Raid-3

 Here Disk 3 contains the Parity bits for Disk 0, Disk 1, and Disk 2. If data loss occurs,
we can construct it with Disk 3.
Advantages
1. Data can be transferred in bulk.
2. Data can be accessed in parallel.
Disadvantages
1. It requires an additional drive for parity.
2. In the case of small-size files, it performs slowly.

5.RAID-4 (Block-Level Stripping with Dedicated Parity)

Raid-4

 Instead of duplicating data, this adopts a parity-based approach.

 In the figure, we can observe one column (disk) dedicated to parity.
 Parity is calculated using a simple XOR function. If the data bits are 0,0,0,1 the parity
bit is XOR(0,0,0,1) = 1. If the data bits are 0,1,1,0 the parity bit is XOR(0,1,1,0) = 0.
A simple approach is that an even number of ones results in parity 0, and an odd
number of ones results in parity 1.

Raid-4

 Assume that in the above figure, C3 is lost due to some disk failure. Then, we can
recompute the data bit stored in C3 by looking at the values of all the other columns
and the parity bit. This allows us to recover lost data.
Evaluation
 Reliability: 1
RAID-4 allows recovery of at most 1 disk failure (because of the way parity works). If
more than one disk fails, there is no way to recover the data.
 Capacity: (N-1)*B
One disk in the system is reserved for storing the parity. Hence, (N-1) disks are made
available for data storage, each disk having B blocks.
Advantages
1. It helps in reconstructing the data if at most one data is lost.
Disadvantages
1. It can’t help in reconstructing when more than one data is lost.

6. RAID-5 (Block-Level Stripping with Distributed Parity)

 This is a slight modification of the RAID-4 system where the only difference is that
the parity rotates among the drives.

Raid-5

 In the figure, we can notice how the parity bit “rotates”.

 This was introduced to make the random write performance better.
Evaluation
 Reliability: 1
RAID-5 allows recovery of at most 1 disk failure (because of the way parity works). If
more than one disk fails, there is no way to recover the data. This is identical to RAID-
4.
 Capacity: (N-1)*B
Overall, space equivalent to one disk is utilized in storing the parity. Hence, (N-1)
disks are made available for data storage, each disk having B blocks.
Advantages
1. Data can be reconstructed using parity bits.
2. It makes the performance better.
Disadvantages
1. Its technology is complex and extra space is required.
2. If both discs get damaged, data will be lost forever.

7. RAID-6 (Block-Level Stripping with two Parity Bits)

 Raid-6 helps when there is more than one disk failure. A pair of independent parities
are generated and stored on multiple disks at this level. Ideally, you need four disk
drives for this level.
 There are also hybrid RAIDs, which make use of more than one RAID level nested
one after the other, to fulfill specific requirements.

Raid-6

Advantages
1. Very high data Accessibility.
2. Fast read data transactions.
Disadvantages
1. Due to double parity, it has slow write data transactions.
2. Extra space is required.
Advantages of RAID
 Data redundancy: By keeping numerous copies of the data on many disks, RAID can
shield data from disk failures.
 Performance enhancement: RAID can enhance performance by distributing data
over several drives, enabling the simultaneous execution of several read/write
operations.
 Scalability: RAID is scalable, therefore by adding more disks to the array, the storage
capacity may be expanded.
 Versatility: RAID is applicable to a wide range of devices, such as workstations,
servers, and personal PCs
Disadvantages of RAID
 Cost: RAID implementation can be costly, particularly for arrays with large capacities.
 Complexity: The setup and management of RAID might be challenging.
 Decreased performance: The parity calculations necessary for some RAID
configurations, including RAID 5 and RAID 6, may result in a decrease in speed.
 Single point of failure: RAID is not a comprehensive backup solution, while offering
data redundancy. The array’s whole contents could be lost if the RAID controller
malfunctions.

Disk Scheduling Algorithms: is done by operating systems to schedule I/O requests arriving
for the disk. Disk scheduling is also known as I/O Scheduling.
Importance of Disk Scheduling in Operating System
 Multiple I/O requests may arrive by different processes and only one I/O request can be
served at a time by the disk controller. Thus other I/O requests need to wait in the waiting
queue and need to be scheduled.
 Two or more requests may be far from each other so this can result in greater disk arm
movement.
 Hard drives are one of the slowest parts of the computer system and thus need to be
accessed in an efficient manner.
Here, we will cover the following Topics in Disk Scheduling.
 Important Terms Associated with Disk Scheduling
 Disk Scheduling Algorithms
 FCFS (First Come First Serve)
 SSTF (Shortest Seek Time First)
 SCAN (Elevator Algorithm)
  C-SCAN (CIrcular SCAN)
 LOOK
 C-LOOK
 RSS
 LIFO (Last-In First-Out)
 N-Step SCAN
 F-SCAN

Key Terms Associated with Disk Scheduling

 Seek Time: Seek time is the time taken to locate the disk arm to a specified track where
the data is to be read or written. So the disk scheduling algorithm that gives a minimum
average seek time is better.
 Rotational Latency: Rotational Latency is the time taken by the desired sector of the
disk to rotate into a position so that it can access the read/write heads. So the disk
scheduling algorithm that gives minimum rotational latency is better.
 Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating
speed of the disk and the number of bytes to be transferred.
 Disk Access Time:
Disk Access Time = Seek Time + Rotational Latency + Transfer Time
Total Seek Time = Total head Movement * Seek Time

Disk Access Time and Disk Response Time

 Disk Response Time: Response Time is the average time spent by a request waiting to
perform its I/O operation. The average Response time is the response time of all
requests. Variance Response Time is the measure of how individual requests are
serviced with respect to average response time. So the disk scheduling algorithm that
gives minimum variance response time is better.
Disk Scheduling Algorithms
There are several Disk Several Algorithms. We will discuss each one of them.

FCFS (First Come First Serve)

FCFS is the simplest of all Disk Scheduling Algorithms. In FCFS, the requests are
addressed in the order they arrive in the disk queue. Let us understand this with the help of
an example.

First Come First Serve

Example:
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is: 50
So, total overhead movement (total distance covered by the disk arm) =
(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) =642

Advantages of FCFS
Here are some of the advantages of First Come First Serve.
 Every request gets a fair chance
 No indefinite postponement
Disadvantages of FCFS
Here are some of the disadvantages of First Come First Serve.
 Does not try to optimize seek time.
 May not provide the best possible service.
SSTF (Shortest Seek Time First)
In SSTF (Shortest Seek Time First), requests having the shortest seek time are executed
first. So, the seek time of every request is calculated in advance in the queue and then they
are scheduled according to their calculated seek time. As a result, the request near the disk
arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the
average response time and increases the throughput of the system. Let us understand this
with the help of an example.

Example:

Shortest Seek Time First

Suppose the order of request is- (82,170,43,140,24,16,190)

And current position of Read/Write head is: 50 So,
total overhead movement (total distance covered by the disk arm) =
(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) =208

Advantages of Shortest Seek Time First

Here are some of the advantages of Shortest Seek Time First.
 The average Response Time decreases
 Throughput increases
Disadvantages of Shortest Seek Time First
Here are some of the disadvantages of Shortest Seek Time First.
 Overhead to calculate seek time in advance
 Can cause Starvation for a request if it has a higher seek time as compared to incoming
requests
 The high variance of response time as SSTF favors only some requests
SCAN
In the SCAN algorithm the disk arm moves in a particular direction and services the
requests coming in its path and after reaching the end of the disk, it reverses its direction
and again services the request arriving in its path. So, this algorithm works as an elevator
and is hence also known as an elevator algorithm. As a result, the requests at the midrange
are serviced more and those arriving behind the disk arm will have to wait.
Example:

SCAN Algorithm

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write

arm is at 50, and it is also given that the disk arm should move “towards the larger
value”.
Therefore, the total overhead movement (total distance covered by the disk arm) is
calculated as
= (199-50) + (199-16) = 332

Advantages of SCAN Algorithm

Here are some of the advantages of the SCAN Algorithm.
 High throughput
 Low variance of response time
 Average response time
Disadvantages of SCAN Algorithm
Here are some of the disadvantages of the SCAN Algorithm.
 Long waiting time for requests for locations just visited by disk arm
C-SCAN
In the SCAN algorithm, the disk arm again scans the path that has been scanned, after
reversing its direction. So, it may be possible that too many requests are waiting at the other
end or there may be zero or few requests pending at the scanned area.
These situations are avoided in the CSCAN algorithm in which the disk arm instead of
reversing its direction goes to the other end of the disk and starts servicing the requests
from there. So, the disk arm moves in a circular fashion and this algorithm is also similar to
the SCAN algorithm hence it is known as C-SCAN (Circular SCAN).

Example:

Circular SCAN

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write

arm is at 50, and it is also given that the disk arm should move “towards the larger
value”.
So, the total overhead movement (total distance covered by the disk arm) is calculated as:
=(199-50) + (199-0) + (43-0) = 391

Advantages of C-SCAN Algorithm

Here are some of the advantages of C-SCAN.
 Provides more uniform wait time compared to SCAN.
LOOK
LOOK Algorithm is similar to the SCAN disk scheduling algorithm except for the
difference that the disk arm in spite of going to the end of the disk goes only to the last
request to be serviced in front of the head and then reverses its direction from there only.
Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of
the disk.
Example:

LOOK Algorithm

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write

arm is at 50, and it is also given that the disk arm should move “towards the larger
value”.
So, the total overhead movement (total distance covered by the disk arm) is calculated as:
= (190-50) + (190-16) = 314
C-LOOK
As LOOK is similar to the SCAN algorithm, in a similar way, C-LOOK is similar to the
CSCAN disk scheduling algorithm. In CLOOK, the disk arm in spite of going to the end
goes only to the last request to be serviced in front of the head and then from there goes to
the other end’s last request. Thus, it also prevents the extra delay which occurred due to
unnecessary traversal to the end of the disk.
Example:
1. Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write
arm is at 50, and it is also given that the disk arm should move “towards the larger
value”

C-LOOK

So, the total overhead movement (total distance covered by the disk arm) is calculated as
= (190-50) + (190-16) + (43-16) = 341

THANK YOU