Chapter Four

Device
Management

By: Sinodos G.
Introduction
 The role of the operating system in computer I/O is to manage and
control I/O operations and I/O devices.
 The control of devices connected to the computer is a major
concern of operating-system designers.
 Because I/O devices vary so widely in their function and speed
(consider a mouse, a hard disk, and a CD-ROM), varied methods
are needed to control them.
 These methods form the I/O subsystem of the kernel, which
separates the rest of the kernel from the complexities of managing
I/O devices.

2
 I/O Devices
 Devices that engage in I/O with computer systems can be
roughly grouped into three categories:
1. Human readable:
• Suitable for communicating with the computer user.
Ex: Printer, video display, keyboard, mouse, etc.

2. Machine readable:
• Suitable for communicating with electronic equipment.
Ex: Disk drive, controller, etc.

3. Communication:
• Suitable for communicating with remote devices.
Ex: Modem

3
I/O Device Differences
 Among the key differences of I/O devices are the following:
• Data rate: There may be differences of several orders of magnitude
between the data transfer rates.
• Application: The use to which a device is put has an influence on
the software and policies in the OS and supporting utilities.
• Complexity of control: A printer requires a relatively simple
control interface whereas a disk is much more complex.
• Unit of transfer: Data may be transferred as a stream of bytes or
characters (e.g., terminal I/O) or in larger blocks (e.g., disk I/O).
• Data representation: Different data encoding schemes are used by
different devices.
• Error conditions: The nature of errors differs widely from one
device to another.

4
Cont’d …
 Functions of device manager
• Monitor status of all devices
• Enforce pre-set polices in all devices
• Deals with allocation of devices to process
• Deals with deallocation
• Example: of devices (all input and output devices)

5
Organization of the I/O Function
 There are three fundamentally different techniques of I/O performed
to exchange information between user and process.
• Programmed I/O
• Interrupt-driven I/O
• Direct memory access (DMA)

6
 Programmed I/O
 A technique or approach that we use to transfer data between the
processor and the I/O module.
 Used to send and write data from I/O and to store [write] on the
memory using the CPU instruction.
 The processor issues an I/O command, on behalf of a process, to an
I/O module; that process then busy waits for the operation to be
completed before proceeding.

 Programmed I/O is simple but has the disadvantage of tying up the

CPU full time until all the I/O is done.
 In an embedded system, where the CPU has nothing else to do,
busy waiting is fine.
 However, in more complex systems, where the CPU has other work
to do, busy waiting is inefficient.
7
Example:-

CPU Issue a read command from I/O

Read the status of I/O data

Check if ready or not

CPU read the Data

CPU write to memory

Check if write or not

Example of Programmed I/O

8
Cont’d . . .
 Objective
• To write data from I/O to memory
• The processor fully dedicates itself in transferring the data
between I/O and memory.

 Advantage
• Simple
• It transfers data at a high rate

 Disadvantage
• CPU has to wait for I/O module
• it can’t get involved in any other activity during data
transfer.

9
 Interrupt-Driven I/O

 Called as the suspicious of process

 The processor issues an I/O command on behalf of a process.

 There are two possibilities:-

 If the I/O instruction from the process is nonblocking, then the processor
continues to execute instructions from the process that issued the I/O
command.

 If the I/O instruction is blocking, then the next instruction that the
processor executes is from the OS, which will put the current process in a
blocked state and schedule another process.
10
Cont’d . . .

Basic Operations of Interrupt

Advantages
• CPU issues read command. • Fast
• I/O module gets data from • efficient
peripheral whilst CPU does
other work. Disadvantages
• can be hard to
• I/O module interrupts CPU. get various
• CPU requests data. pieces to work
well together
• I/O module transfers data. • usually done by
the hardware
manufacturer

11
 Direct Memory Access (DMA)
 Controls the exchange of data between main memory and an I/O.
 The processor sends a request for the transfer of a block of data to the
DMA module, and is interrupted only after the entire block has been
transferred.
 The DMA unit is capable of simulating the processor and, indeed, of
taking over control of the system bus just like a processor.
 It needs to do this to transfer data to and from memory over the
system bus.
 When the transfer is complete, the DMA module sends an interrupt
signal to the processor.
 Thus, the processor is involved only at the beginning and end of the
transfer.

12
Cont’d . . .

13
Device Drivers
There are two types of device drivers. These are:-
 Block device:
• Stores information in fixed-size blocks, each one with its own
address.
• Common block sizes range from 512 to 65,536 bytes.
• All transfers are in units of one or more entire (consecutive) blocks.
Ex: Disks

 Character device:
• Delivers or accepts a stream of characters, without regard to any
block structure.
• It is not addressable.
Ex: Printer, mouse

14
 Buffering
• A buffer is a memory area that stores data being transferred between
two devices or between a device and an application.

• Buffering is done for three reasons:

 to cope with a speed mismatch between the producer and consumer
of a data stream.
 Single buffer, double buffer, and circular buffer.

 to provide adaptations for devices that have different data-transfer

sizes.
 to support copy semantics for application I/O.

15
Disk Structure

• Disks come in a variety of types.

• The most common ones are the magnetic hard disks.
• Magnetic disks provide the bulk of mass storage for modern
computer systems.

• Each disk platter has a flat circular shape, like a CD.

• The two surfaces of a platter are covered with a magnetic material.
• We store information by recording it magnetically on the platters.

• A read-write head “flies” just above each surface of every platter.

• The heads are attached to a disk arm that moves all the heads as
a unit.

16
 Disk Structure …

• The surface of a platter is

logically divided into
circular tracks, which are
subdivided into sectors.

• The set of tracks that are

at one arm position
makes up a cylinder.

Fig. Structure of magnetic disks (Hard disk drive)

17
Disk Performance Parameters

 When the disk drive is operating, the disk is rotating at constant

speed.
 To read or write, the head must be positioned at the desired track and
at the beginning of the desired sector on that track.
• Seek time: is the time required to move the disk arm to the required
cylinder.
• Rotational Delay (Rotational latency): is the time required for the
desired sector to rotate to the disk head.
• Transfer time: is the time required for the actual data transfer.
• Access time: is the time it takes to get into position to read or write.

Access time = seek time + rotational latency

18
Disk Scheduling Algorithm
 used for disk scheduling.
 At run-time I/O request for the disk track come from the process.
 OS has to choose an order to serve the request.
 We can improve access time by scheduling the servicing of disk I/O
requests in a good order.
 Several algorithms exist to schedule the servicing of disk I/O requests
• First-Come First-Served scheduling,
• Shortest Seek Time First scheduling,
• SCAN scheduling,
• C-SCAN scheduling, and
• C-LOOK scheduling
Objective
• To reduce the total seek time.
19
FCFS
 As the name suggests, this algorithm entertains The request are
addressed in the order they arrived in the disk queue
 It is the simplest disk scheduling algorithm.

Advantages:-
 It is simple, easy to understand and implement.
 It does not cause starvation to any request.

Disadvantages:-
 It results in increased total seek time.
 It is inefficient.

20
Example:-
Example: Assume a disk with 200 cylinders (0-199), and disk queue
with request for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124,
65, 67 in that order.

Suppose, now the head is initially at cylinder 53.

Then calculate the total head movement, using FCFS Algorithm.

21
 Solution - FCFS

Total head movements incurred while servicing these requests

= (98 – 53) + (183 – 98) + (183 – 41) + (122 – 41) + (122 – 14) + (124 – 14) + (124 – 65) + (67 – 65)
= 45 + 85 + 142 + 81 + 108 + 110 + 59 + 2
= 632

22
 Example 2:

Example: Assume a disk with 200 cylinders (0-199), and disk queue with request
for I/O to blocks on cylinders 98, 183, 37, 122, 14, 124, 65, 67 in that order.

Suppose, now the head is initially at cylinder 53.

Then calculate the total head movement, using FCFS Algorithm.

Total head movement =

640 cylinders

23
SSTF Scheduling
 SSTF stands for Shortest Seek Time First.
 services that request next which requires least number of head
movements from its current position regardless of the direction.
 It breaks the tie in the direction of head movement.
Advantages-
• It reduces the total seek time as compared to FCFS.
• It provides increased throughput.
• It provides less average response time and waiting time.

 Disadvantages-
• There is an overhead of finding out the closest request.
• The requests which are far from the head might starve for the CPU.
• It provides high variance in response time and waiting time.

24
Example:
Consider a disk queue with
requests for I/O to blocks on
cylinders 98, 183, 41, 122,
14, 124, 65, 67.

The head is initially at

cylinder number 53. The
cylinders are numbered
from 0 to 199. find the total
head movement using SSTF
Total head movements incurred while servicing these requests
= (65 – 53) + (67 – 65) + (67 – 41) + (41 – 14) + (98 – 14) + (122 – 98) + (124 –
122) + (183 – 124)
= 12 + 2 + 26 + 27 + 84 + 24 + 2 + 59
= 236
25
Example 2:

Example: Assume a disk with

200 cylinders (0-199), and disk
queue with request for I/O to
blocks on cylinders 98, 183, 37,
122, 14, 124, 65, 67 in that order.

Suppose, now the head is initially

at cylinder 53.
Then calculate the total head
movement, using FCFS Algorithm.

Total head movement = 236 cylinders

26
SCAN Scheduling
 As the name suggests, this algorithm scans all the cylinders of the
disk back and forth.
 Head starts from one end of the disk and move towards the other
end servicing all the requests in between.
 After reaching the other end, head reverses its direction and move
towards the starting end servicing all the requests in between.
 The same process repeats.
 SCAN Algorithm is also called as Elevator Algorithm.
 This is because its working resembles the working of an elevator.

27
 Advantages-
 It is simple, easy to understand and implement.
 It does not lead to starvation.
 It provides low variance in response time and waiting time.

 Disadvantages-
 It causes long waiting time for the cylinders just visited by the head.
 It causes the head to move till the end of the disk even if there are no
requests to be serviced.

28
Example:
 Consider a disk
queue with requests
for I/O to blocks on
cylinders 98, 183,
41, 122, 14, 124, 65,
67. The head is
initially at cylinder Total head movements
number 53 and The = (65 – 53) + (67 – 65) + (98 – 67) +
cylinders are (122 – 98) + (124 – 122) + (183 –
numbered from 0 to 124) + (199 – 183) + (199 – 41) + (41
– 14)
199. Or
= 12 + 2 + 31 + 24 + 2 + 59 + 16 +
 find The total head 158 + 27 = (199 – 53) + (199 – 14)
= 331 = 146 + 185
movement SCAN = 331
Algorithm

29
Example 2:

Example: Assume a disk with 200
cylinders (0-199), and disk queue
with request for I/O to blocks on
cylinders 98, 183, 37, 122, 14, 124,
65, 67 in that order.

Suppose, now the head is initially at

cylinder 53.
Then calculate the total head
movement, using SCAN Algorithm.

Total head movement = 208 cylinders

30
C-SCAN Algorithm
 Circular-SCAN Algorithm is an improved version of the SCAN Algorithm.
 Head starts from one end of the disk and move towards the other end
servicing all the requests in between.
 After reaching the other end, head reverses its direction.
 It then returns to the starting end without servicing any request in
between.
 The same process repeats.

31
Advantages-
 reduce waiting time for the cylinders
 It provides uniform waiting time.
 It provides better response time.

Disadvantages-
 It causes more seek movements as compared to SCAN Algorithm.
 It causes the head to move till the end of the disk even if there are no
requests to be serviced.

32
Example
Consider a disk queue with requests for I/O
to blocks on cylinders 98, 183, 41, 122, 14,
124, 65, 67.
The head is initially at cylinder number 53.
The cylinders are numbered from 0 to 199.

Find The total head movement using C-

SCAN scheduling algorithm

= (199 – 53) + (199 – 0) + (41 – 0)

= 146 + 199 + 41
= 386

33
Question

End of Chapter 4,

Next  Chapter 5

34