Disk Scheduling
Disk Scheduling
• Disk Structure
• Disk Scheduling
Mass‐Storage Structure
Introduction
• The main requirement of secondary storage is to
be able to store a very large amount of data
permanently.
• One of the earliest secondary‐storage media is the
magnetic tape.
tape However,
However it was too slow in
comparison with the access time of main
memory.
• Magnetic disks provide the bulk of secondary
storage for modern computer systems.
Overview of Mass Storage Structure
• Magnetic disks provide bulk of secondary
g of modern computers
storage p
– Drives rotate at 60 to 250 times per second
– Transfer rate is rate at which data flow between
drive and computer
– Positioning time (random‐access time) is time to
move disk arm to desired cylinder (seek time) and
time for desired sector to rotate under
nder the disk head
(rotational latency)
– Head crash results from disk head making contact
with
i h the
h disk
di k surface
f
• That’s bad
• Disks can be removable
• Drive attached to computer via I/O bus
Mass‐Storage Structure
Disk Structure
• A magnetic disk system has several disk platters.
Each disk platter has a flat circular shape,
shape like a
phonograph record. A magnetic material, similar
to that of a magnetic
g tape
p or floppyppy diskette,,
covers its two surfaces. Information is recorded
on the surfaces.
Moving‐head
Moving head Disk Mechanism
Lec 5 Operating Systems 6
Mass‐Storage Structure
Disk Structure
• When the disk is in use, a drive motor spins it at a
high speed (for example, 60 revolutions per
second) There is a read‐write
second). read write head positioned
just above the surface of the platter.
• The disk surface is logically divided into tracks,
which are subdivided into sectors. The system
stores information by recording it magnetically on
the sector under the read‐write head.
Mass‐Storage Structure
Disk Structure
Disk Structure
• Disk drives are addressed as large 1‐dimensional arrays
of logical blocks, where the logical block is the smallest
unit
it off ttransfer
f
– Low‐level formatting creates logical blocks on physical
media
• The 1‐dimensional array of logical blocks is mapped
into the sectors of the disk sequentially
– SSector
t 0 isi the
th first
fi t sector
t off the
th first
fi t ttrackk on th
the
outermost cylinder
– Mapping proceeds in order through that track, then the
rest of the tracks in that cylinder
cylinder, and then through the rest
of the cylinders from outermost to innermost
– Logical to physical address should be easy
Mass‐Storage Structure
Disk Structure
• The time it takes to access a sector depends on three
parameters, the seek time, latency time, and transfer
time.
• Seek time is the time it takes to move the read
read‐write
write head
to the correct track while the latency time is the time it
takes for the sector to rotate under the head.
• Transfer time is the time it takes to actually transfer data
between disk and main memory.
Mass‐Storage Structure
Disk Structure
• To access a sector, the system must specify the
cylinder or track number, a surface number, and a
sector number.
b Th the
Thus, h system views
i the
h disk
di k as
a three‐dimensional array of sectors.
Exercise
Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors
per track. 512 bytes of data are stored in a bit serial manner in a sector. The
capacity
p y of the disk pack
p and the number of bits required
q to specify
p ya
particular sector in the disk are respectively:
Solution:
Capacity of the disk = 16 surfaces X 128 tracks X 256 sectors X 512 bytes = 256 Mbytes.
To calculate number of bits required to access a sector,
we need to know total number of sectors.
Total number of sectors = 16 surfaces X 128 tracks X 256 sectors = 2^19
So the number of bits required to access a sector is 19.
Mass‐Storage
Mass Storage Structure
Disk Scheduling
• Scheduling Algorithms
1. FCFS Scheduling
2
2. SSTF Scheduling
3. SCAN Scheduling
4. C-SCAN Scheduling
g
5. LOOK Scheduling
Disk scheduling
• When a read/write job is requested, the disk may
currently be busy
• All pending jobs are placed in a disk queue
– could be scheduled to improve the utilization
• Disk scheduling increases the disk’s bandwidth
BYU CS 345 Disc Scheduling 16
Disk Scheduling
• The operating system is responsible for using hardware efficiently — for
the
h ddiskk d
drives, this
h means hhaving a ffast access time and d high
h h disk
d k
bandwidth
• Access time has two major components
– Seek
S k time
ti i the
is th time
ti for
f the
th disk
di k are to
t move theth heads
h d to t the
th
cylinder containing the desired sector
– Rotational latency is the additional time waiting for the disk to rotate
the desired sector to the disk head
• Minimize seek time
– Seek time ≈ seek distance
– Disk bandwidth is the total number of bytes transferred,
transferred divided by
the total time between the first request for service and the
completion of the last transfer
Mass‐Storage
Mass Storage Structure
Disk Scheduling
1. FCFS Scheduling
• The simplest form of scheduling is the first-
come first-served
first served (FCFS).
(FCFS)
Example:
• Assume that the read-write head is currently
at track 53. Consider now an ordered disk
queue with requests involving tracks
98 183,
98, 183 37,
37 122,
122 14,
14 124,
124 65,
65 and
d 67
Disk Scheduling
First‐In/First‐Out FIFO
Head at 53 98 183 37 122 14 124 65 67
0 14 37 53 65 67 98 122 124 183 199
45
45
85
+ 85
146
+ 146
85
+ 85
108
+ 108
110
+ 110
59
+ 59
2 + 2
= 640
FCFS ‐ Problem
• The problem with this schedule is illustrated by
the wild swing from 122 to 14 and back to 124.
FCFS mayy therefore not p
provide the best ((average)
g )
service.
2 SSTF Scheduling
2.
•The shortest seek time first selects the request with the
minimum seek time from the current head position.
position This
means that the system moves the head to the closest track in
the request queue.
Example:
Assume that the read‐write head is currently at track 53.
Consider now an ordered disk queue with requests involving
tracks 98,
98 183,
183 37,
37 122,
122 14,
14 124,
124 65,
65 and 67.
67
Disk Scheduling
Shortest Seek Time First ‐ SSTF
Head at 53 98 183 37 122 14 124 65 67
0 14 37 53 65 67 98 122 124 183 199
12
12
2
+ 2
30
+ 30
23
+ 23
84
+ 84
24
+ 24
2 + 2
59
+ 59
= 236
SSTF Disk Scheduling
• This scheduling method results in a total head
movement of 236 tracks. This algorithm would
result in a substantial improvement in average
disk service.
• The problem with SSTF scheduling is that it may
cause starvation of some requests. In theory, a
continual stream of requests near one another
could arrive, causing the request for a farther
track to wait indefinitely.
SCAN Scheduling
•The read‐write head starts at one end of the disk, and moves
toward the other end, servicing requests as it reaches each
t k until
track, til it gets
t to
t the
th other
th end d off the
th disk.
di k At the
th other
th
end, the direction of head movement reverses and servicing
continues. The head continuously scans the disk from end to
end.
•The SCAN algorithm is sometimes called the elevator
algorithm, since it is similar to the behavior of elevators as
they service requests to move from floor to floor in a building.
Disk Scheduling ‐ SCAN
Example:
Assume that the read‐write head is currently at
track 53 (going to the direction of track 0). Consider
now an ordered disk queue with requests involving
t k 98,
tracks 98 183,
183 37,
37 122,
122 14,
14 124,
124 65,
65 and d 67.
67
Disk Scheduling
Scan
Head at 53 98 183 37 122 14 124 65 67
0 14 37 53 65 67 98 122 124 183 199
16
16
+ 23
23
+ 14
14
+ 65
65
+ 2
2 + 31
31
+ 24
24
+ 2
2 + 59
59
= 236
C‐SCAN
C SCAN Scheduling
•The Circular‐SCAN algorithm is a variant of the SCAN
algorithm As does SCAN scheduling,
algorithm. scheduling CC‐SCAN
SCAN scheduling
moves the head from one end of the disk to the other,
servicing requests as it goes. When it reaches the other
end, however, it immediately returns to the beginning of
the disk without servicing any requests on the return trip.
C‐SCAN scheduling essentially treats the disk as though it
were circular, with the last track adjacent to the first one.
C‐SCAN (Cont.)
Illustration shows total head movement of 382 cylinders
C‐SCAN
C SCAN Scheduling
Computing for the total head movement:
f
from 53 to
t 65 = 65 ‐ 53 = 12
from 65 to 67 = 67 ‐ 65 = 2
from 67 to 98 = 98 ‐ 67 = 31
from 98 to 122 = 122 ‐ 98 = 24
from 122 to 124 = 124 ‐ 122 = 2
f
from 124
2 to 183
83 = 183
83 ‐ 124
2 = 599
from 183 to 199 = 199‐183 = 16
From 199 to 0 = 199‐0
199 0 = 199
from 0 to 14 = 14 ‐ 0 = 14
from 14 to 37 = 37 ‐ 14 = 23
Total head movement = 382 tracks
LOOK Scheduling
•In SCAN and C‐SCAN scheduling, the head always moves
from one end of the disk to the other.
•The head is only moved as far as the last request in each
direction As soon as there are no requests in the current
direction.
direction, the head movement is reversed.
•These versions of SCAN and C‐SCAN scheduling are
called LOOK (“look” for a request before moving in that
direction) and C‐LOOK scheduling.
Disk Scheduling
Look
Head at 53 98 183 37 122 14 124 65 67
0 14 37 53 65 67 98 122 124 183 199
16
16
23
+ 23
51
+ 51
2 + 2
31
+ 31
24
+ 24
2 + 2
59
+ 59
= 208
C‐LOOK (Cont)
( )
34
Exercise ‐ 1
Suppose that a disk drive has 5,000 cylinders,
numbered as 0 to 4999
4999. The drive is currently serving
a request at cylinder 143 and the previous request
was at cylinder
y 125. The queue
q off pending
p g requests
q is:
86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
What is the distance to satisfy these requests using the
following algorithms?
(1) FCFS
(2) SSTF
(3) SCAN
(4) LOOK
(5) C‐LOOK
(6) C‐SCAN
Solution ‐1
1
The FCFS algorithm just follows the order of the requests given. The FCFS
schedule is:
143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
The total distance is: 7,081
The SSTF algorithm starts a cylinder 143 and from there successively selects
the shortest request from its current location. The SSTF schedule is:
143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774
The total distance is: 1,745
The SCAN algorithm continues in the direction of the head servicing requests until the
end d off th
the disk.
di k It th
then reverses, catching
t hi allll requests
t bbackk tto th
the other
th end
d off th
the
disk. The head continuously scans back and forth across the disk. The SCAN schedule
is:
143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86
The total distance is: 9,769
The LOOK algorithm is just like the SCAN algorithm, except the disk head only goes as
far as the last request in each direction. The LOOK schedule is:
143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86
The total distance is: 3,319
The C‐LOOK algorithm is a circular version of the LOOK algorithm. It doesn't scan
on the way back to the beginning of the disk, rather operates in a circular
f hi
fashion. The
h C‐LOOK
C OO schedule
h d l is:
i
143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130
The total distance is: 3,363
The C‐SCAN
Th C SCAN sc hedule
h d l isi 143,
143 913,948,1022,1470,1509,1750,1774,4999,
913 948 1022 1470 1509 1750 1774 4999
0,86,130. The total seek distance is 9985.
Exercise 2
Given a disk unit with 200 tracks, numbered from 0 to 199. At time 0 there is a queue
of read requests, the head is positioned over track 89 and “moving towards” the
l
lower tracks.
k The
h disk
di k queue off pending
di requests is
i (given
( i iin order
d off arrival)
i l)
2, 156, 78, 192, 19, 127, 90, 100
Two further requests on track numbers 140 and 60 arrive when servicing the request
for track number 127. Startingg from the current head position
p of 89 for SSTF and
SCAN disk scheduling algorithms:
(i) Draw a diagram showing the disk head movements.
(ii) Total distance (in tracks) that the disk head moves to satisfy all the 10 requests.
(iii) The aaverage
erage n
number
mber of tracks
tracks.
Solution ‐2
2
Exercise 3
Given a disk with 200 tracks, numbered from 0 to 199. It takes 1 ms for the disk
Read/Write head to travel from the current track to the next one, and that it is
originally
i i ll positioned
ii d at trackk 89 and
d “moving
“ i towards”
d ” the
h lower
l tracks.
k
These requests arrive at the following times as shown in the table below:
a)) Draw
D di
diagrams showing
h i the h order
d iin which
hi h the
h
above 10 requests are processed, under each of
these disk scheduling algorithms?
((i)) SCAN
(ii) LOOK
b) Compute the Total Service Time of all these
requests for each disk scheduling algorithms;
ignore the transfer time and latency time?
Solution – 3
Exercise 4
Assume a moving arm disk with 200 cylinders numbered from 0 to 199. Show on a
diagram how the following requests {10, {10 130,
130 100,
100 40,
40 10,
10 180,
180 10,
10 130} are processed
according to FCFS policy. Assume that initially the disk head is at cylinder 120.
b) What is the total distance (in cylinders) that the disk arm moves to satisfy all pending
requests?
c) Assume that the seek time between two consecutive cylinders is 0.1 ms and the transfer
time for each request cylinder is 1 ms and the latency time is negligible, what is the
Average Service Time when serving the above requests using FCFS policy?
Solution ‐ 4
Service Time = number of cylinders * seek time + number of request * transfer time
Service Time = 810 * 0.1 + 8 * 1 = 81 ms
AST = 81 / 8 = 10.125 ms
Disk Size
• Consider a disk with 16 platters (heads) and 400 cylinders. It is
divided into four 100-cylinder
100 cylinder zones with the cylinders in
different zones containing 160, 200, 240, 280 sectors,
respectively. Each sector is 512 bytes, average seek time
between adjacent cylinders is 1 ms, and the disk rotates at 7200
RPM. Calculate (a) disk size (b) max data transfer rate.
44
Disk Size ‐ Solution
• (a)
( ) The size off a zone is p
platters × cylinders
y × sectors/track
/ ×
bytes/sector.
– Capacity of zone 1: 16 × 100 × 160 × 512 = 131072000 bytes
– Capacity
p y off zone 2: 16 × 100 × 200 × 512 = 163840000 bytes
y
– Capacity of zone 3: 16 × 100 × 240 × 512 = 196608000 bytes
– Capacity of zone 4: 16 × 100 × 280 × 512 = 229376000 bytes
– Sum = 131072000 + 163840000 + 196608000 + 229376000 =
720896000
• (b) The maximum data transfer rate will be when the
cylinders
y in the outermost zone (zone
( 4)) are being
g
read/written. In that zone, in one second, 280 sectors are
read 120 times (7200 RPM is 120 rotations/sec). Thus the
max data rate is 280 × 120 × 512 = 17,203,200 bytes/sec.
45
Exercise
Disk requests come into the disk driver for cylinders: 10, 22, 20, 2, 40, 6, 38, in
that order.
order The disk has 60 total cylinders and the disk head is currently
positioned over cylinder 20. A seek takes 10 milliseconds per cylinder moved.
What is the sequence of reads and total seek time using each of the following
algorithms?
a) FCFS
b) SSTF
c) C‐SCAN
C SCAN ( initially moving upwards)
Solution
First‐come, first‐served:
First‐come
10, 22, 20, 2, 40, 6, 38
10 + 12 + 2 + 18 + 38 + 34 +32 = 146 cylinders = 1460 milliseconds.
ii. Shortest Seek Time First:
20, 22, 10, 6, 2, 38, 40
0 + 2 + 12 + 4 + 4 + 36 + 2 = 60 cylinders = 600 milliseconds.
iii. C‐SCAN (initially moving upwards):
20, 22, 38, 40, 10, 6, 2
0 + 2 + 16 + 2 + 30 + 4 + 4 = 58 cylinders = 580 milliseconds
Questions
Q1. A disk has 16 sectors of 1024 bytes on each track.
Q1 track Suppose the disk rotation is
at 600 rpm, how long does it take to
a. read an entire track
[Link] is the volume of data that can be stored on disk if it has 10 tracks
Q2. On a certain disk drive we have observed a 1millisecond seek time per cylinder of
movement Given that we have one reading head for each disk and requests are
movement.
pending to read from cylinder numbers 15,20, 10, 3 and 5. If the arm currently is
located on cylinder 20 which of the followi ng would yield the fastest retrieval.
a. First come first served
b. Elevator algorithm if we were following to first move towards higher
cylinder number and then return.
c. Nearest cylinder first strategy is used.