Transcript seek time

NETW 3005
Mass Storage
(How discs work)
Notice
• I was unaware just how much was
missing in the printed notes.
• As a partial remedy for that, the lecture
slides will appear on the web within the
next week.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
2
Reading
• For this lecture, you should have read
Chapter 12 (Sections 1-4).
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
3
Last lecture: I/O systems
• Hardware: ports, buses, controllers
• Application I/O interface
• Kernel I/O services
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
4
This lecture: How disks work
•
•
•
•
•
The mechanics of disks
Disk scheduling
Formatting and booting
Disk reliability: bad blocks, RAIDs
Swap space management
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
5
The mechanics of disks
• A disk drive consists of
– a number of platters
– with two surfaces each
– arranged on a rotating spindle
– with a head for each surface.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
6
Some terminology
• A single disk platter has two surfaces.
• Each surface is organised into concentric
circles called tracks.
• All tracks of the same radius form a
cylinder.
• Each track is divided into sectors.
• A sector is the smallest addressable part
of the disk.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
7
The mechanics of disks
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
8
Addressing
• Information on the disk is referenced by
a multi-part address which includes:
– drive number,
– cylinder number,
– surface number and,
– sector number.
Cylinders are vertically formed by tracks. In other words,
track 12 on platter 0 plus track 12 on platter 1 etc. is cylinder
12. The number of cylinders of a disk drive exactly equals
the number of tracks on a single surface in the drive.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
9
Access time has two major components
•Seek time is the time taken to move the heads
to the cylinder containing the desired sector.
•Rotational latency is the time taken to rotate
the desired sector to the disk head.
More terminology
• The heads all move together, accessing
a cylinder of the disk.
• To access a particular sector, the heads
are moved to the appropriate cylinder,
the correct head is enabled, and the
head waits until the correct sector
comes under it.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
11
Disk scheduling
• kernel’s I/O subsystem schedules pool of
pending I/O requests .
• Imagine a queue of I/O requests to a given
disk.
• Ordering these requests in different ways
will result in different head seek times.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
12
Algorithms for disk scheduling
•
Criteria for evaluating algorithms:
– Seek time
– Fairness (in particular, starvation)
1. FCFS
2. Shortest seek-time first scheduling
3. SCAN
4. C SCAN
5. C LOOK
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
13
FCFS scheduling
• Treat I/O requests in FCFS order.
Calculation of the seek time for the schedule given
on the next slide
(98 - 53) + (183 - 98) + (183 - 37) + (122 - 37)
+ (122 - 14) + (124 - 14) + (124 - 65) + (67 - 65)
= 640 cylinders
Here we do not calculate the time but only the number
of cylinders' the head is moving – that gives us the distance
which is directly proportional to seek time
i.e if the distance is increasing seek time is also increasing
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
14
Illustration shows total head
movement of 640 cylinders.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
15
Advantages and disadvantages?
• Advantages?
– no starvation: every request is serviced
– Simple to implement.
• Disadvantages?
–
big swing in head seek.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
16
Shortest seek-time first scheduling
• At any moment, choose the request with
the shortest distance from the current
head position.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
17
Illustration shows total head
movement of 236 cylinders.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
18
Advantages and disadvantages?
Seek time for SSTF is calculated as follows:
(65 - 53) + (67 - 65) + (67 - 37) + (37 - 14) + (98 - 14)
+ (122 - 98) + (124 - 122) + (183 - 124)
= 236 this is some many cylinder movements not time
• Advantages?
– You get much shorter seek times this way,
because you’re eliminating the big swings.
(At least, you’ll only get them if there’s
nothing closer.)
• Disadvantages?
– Starvation is a possibility.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
19
SCAN scheduling
• Start the disk at one end, and move right
to the other end, servicing all the I/O
requests you get to on your way. Then
start in the other direction.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
20
Illustration shows total head
movement of 208 cylinders.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
21
•(53 - 37) + (37 - 14) + (65 - 14) + (67 - 65)
+
•(98 - 67) + (122 - 98) + (124 - 122) + (183 124)
•= 208
Advantages and disadvantages?
• Advantages?
– Avoids starvation
• Disadvantages?
– Requests for the middle of the disk are
advantaged over those at the ends.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
23
C-SCAN scheduling
• Like SCAN, but when the head gets to
one end, it goes straight to the other
end without servicing any requests.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
24
C-SCAN scheduling
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
25
Advantages and disadvantages?
• Advantages?
– No region of the disk are favored.
• Disadvantages?
requires one long seek after finished
going up
have to go back to the beginning
C-SCAN scheduling
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
26
C-LOOK scheduling
• Like C-SCAN, except that rather than
going to the ends of the disk, we only go
as far as the furthest request in each
direction.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
27
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
28
Advantages and disadvantages?
• Advantages?
– No region of the disk are favored
• Disadvantages?
more inclined to serve the middle cylinder
requests
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
29
Comparison of Disk Scheduling
Algorithms
Priority scheduling
• We might not want to treat all these
requests as equal, e.g. page-faultgenerated requests might need to be
handled first.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
31
Selecting a Disk-Scheduling Algorithm
• FCFS- Ideal for LOW Load Disk Schedule.
• SSTF – ideal for Linked and indexed allocation
technique to reduce the head seek time.
• SCAN and C-SCAN- ideal for heavy load on the
disk.
• C – scan is ideal for contiguous allocation
technique
• Either SSTF or LOOK reasonable choice for the
default algorithm.
Where should index blocks be stored?
• Near the blocks containing the file’s
data.
Where should directories be stored?
•In the middle of the partition is a good idea,
so you never have more than half the disk to
scan.
•Or near the FAT.
•Best to cache recently-used directory info
as well.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
33
Disk formatting
• Low-level formatting: normally done in
the factory.
• Creates the sectors on the disk, and fills
each with an initial data structure:
– A header and trailer, containing information
used by the disk controller - e.g. sector
number, error-correcting code (ECC).
– A data area (usually 512 bytes).
Header
Sector
No
Data ( 512 bytes)
NETW3005 (Operating Systems)
Trailer( ECC)
Lecture 11 - How discs work/44
34
Disk formatting
• Partitioning: done by the operating
system.
• Logical formatting: making an (empty)
file system.
File System
NTFS
NETW3005 (Operating Systems)
FAT 32
Lecture 11 - How discs work/44
35
Bad blocks
• A bad sector is a sector on a computer's disk
drive that cannot be used due to permanent
damage .
Bad blocks are blocked in the FAT – table
The Controller maintains list of bad blocks and spare
blocks right from Low Level formatting .
Controller can replace each bad sector with one of the
spare sector
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
36
Problems with sparing?
• Sector sparing could invalidate any
optimization by the operating systems
disk scheduling algorithm
•Sector slipping: shuffling all the data on
disk to make room for the spare block right
next to the one it’s replacing.
•Provision of spare sectors in each cylinders
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
37
Error recovery and RAIDs
• RAID is the organization of multiple disks
into a large, high performance logical disk.
• Each block of data is broken into subblocks, with one sub-block stored on each
disk.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
38
RAIDs
• Mirroring: each disk holds all the data.
• Block interleaved parity. A parity bit for
the group of sub-blocks is written to a
special parity block. If one of the subblocks is lost, it can be recovered from
the other sub-blocks plus the parity
block.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
39
10011100
01101100
11110000
11110000
10011100
=01101100
Primary
Boot
strap
loader
L
O
A
D
S
Secondary boot
loader
Booting a system
LOADS THE OS
INTO THE MAIN
MEMORY
Swap space management
•Swap space holds entire process or page or segment which
Is swapped out to the backing store from main memory
Swap space
implementation
File System
swap space is simply
a large file within file system
Special raw partition
swap space
Is
Blocks in the raw partition
me OSs can swap in both file space and raw swap partitions, e.g. So
Navigating takes more Speed of access is
Time
better than file system
Next Lecture
!Revision!
Make sure you come along
(Exam hints are possible)
Is SSTF optimal?
• No – it is too short-sighted, i.e. no lookahead.
• It is possible to develop an optimal
algorithm, but the time taken to calculate it
means it’s not really worth it.
• For example if the head moves to 37 then
14 and then 65, 67 and so on seek time
will be less
• (53 - 37) + (37 - 14) + (65 - 14) + (67 - 65) + (98 - 67) +
(122 - 98) + (124 - 122) + (183 - 124) = 208
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
44
1 xor 1 = 0
1 xor 0 = 1
0 xor 0 = 0
1110 xor 1001 = 0111
8 bits including
7 bits of data parity
(number of 1s)
even
odd
0000000 (0)
1010001 (3)
1101001 (4)
1111111 (7)
00000000
11010001
01101001
11111111
10000000
01010001
11101001
01111111
Booting a system
• In fact, the initial program is often very
small.
• Often it just loads a bigger bootstrap
program, and this program does the
rest.
• The program will be stored at a fixed
location on the disk, called the boot
block.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
47
Swap-space management
• memory management often uses a
backing store to hold data from
processes being multitasked.
• We could implement swap space simply
as a file within a directory structure.
• Problems with this approach?
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
48
Swap-space management
• A more frequent solution is to create a
special partition for swap space.
• The disk allocation algorithm on this
partition is optimised for speed, rather
than memory efficiency.
• Some OSs can swap in both file space
and raw swap partitions, e.g. Solaris 2.
NETW3005 (Operating Systems)
Lecture 11 - How discs work/44
49