Transcript 1.01

CS307 Operating Systems
Mass-Storage Systems
Fan Wu
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Fall 2011
Chapter 12: Mass-Storage Systems
 Overview of Mass Storage Structure
 Disk Structure
 Disk Attachment
 Disk Scheduling
 Disk Management
 RAID Structure
Operating Systems
2
Objectives
 Describe the physical structure of secondary storage devices and the
resulting effects on the uses of the devices
 Explain the performance characteristics of mass-storage devices
 Discuss operating-system services provided for mass storage, including
RAID
Operating Systems
3
Moving-head Disk Mechanism
Operating Systems
4
The First Commercial Disk Drive
1956
IBM RAMDAC computer
included the IBM Model
350 disk storage system
5M (7 bit) characters
50 x 24” platters
Access time = < 1 second
Operating Systems
5
Modern Disk Drive
A Western Digital 3.5 inch
250 GB SATA HDD
Operating Systems
6
Different Sized Disk Drives
Operating Systems
7
Read-Write Arm and Head
Head stack
Operating Systems
Read-write head
8
Overview of Mass Storage Structure
 Magnetic disks provide bulk of secondary storage of modern computers

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
the disk head (rotational latency)
 Drive attached to computer via I/O bus

Busses vary, including EIDE, ATA, SATA, USB, Fibre Channel, SCSI,
SAS, Firewire

Host controller in computer uses bus to talk to disk controller built
into drive
Operating Systems
9
Magnetic Tape
 Was early secondary-storage medium

Evolved from open spools to cartridges
 Relatively permanent and holds large quantities of data
 Access time slow
 Random access ~1000 times slower than disk
 Mainly used for backup, storage of infrequently-used data, transfer medium
between systems
 Kept in spool and wound or rewound past read-write head
 Once data under head, transfer rates comparable to disk

140MB/sec and greater
 200GB to 1.5TB typical storage
 Common technologies are LTO-{3,4,5} and T10000
Operating Systems
12
Solid-State Drive (SSD)
SSDs use microchips which retain data in non-volatile
memory chips and contain no moving parts
Operating Systems
13
Disk Structure
7
cylinder
0
sector
8
15
6
5
14
9
13
10
0
1
2
Operating Systems
3
4
4
5
6
7
2
11
12
block
1
3
8
9
14
10
11
12
13
14
15
……
Disk Structure (Cont.)
 Disk drives are addressed as large 1-dimensional arrays of logical blocks,
where the logical block is the smallest unit of transfer

512 bytes logical block size
 The 1-dimensional array of logical blocks is mapped into the sectors of the
disk sequentially

Sector 0 is the first sector of the first track on the outermost cylinder

Mapping proceeds in order through that track, then the rest of the tracks
in that cylinder, and then through the rest of the cylinders from
outermost to innermost

Difficulty in mapping from logical to physical address:

Except for bad sectors

Non-constant # of sectors per track via constant angular velocity
Operating Systems
15
Disk Scheduling (Cont.)
 There are many sources of disk I/O request

OS, System processes, Users processes
 OS maintains queue of requests, per disk or device
 Idle disk can immediately work on I/O request, busy disk means work must
queue

Optimization algorithms only make sense when a queue exists
 The operating system is responsible for using hardware efficiently — for the
disk drives, this means having a fast access time and disk bandwidth

Minimize seek time  seek distance

What about rotational latency?

Difficult for OS to calculate
 Several algorithms exist to schedule the servicing of disk I/O requests
 We illustrate scheduling algorithms with a request queue (0-199)
98, 183, 37, 122, 14, 124, 65, 67
Operating Systems
16
Head pointer 53
Disk-Scheduling Algorithms
 First-Come, First-Served (FCFS) Scheduling
 Shortest Seek Time First (SSTF) Scheduling
 SCAN Scheduling
 C-SCAN Scheduling
 LOOK/C-LOOK Scheduling
Operating Systems
17
FCFS Scheduling
Total head movement: 640 cylinders
Operating Systems
18
SSTF Scheduling
 Shortest Seek Time First selects the request with the minimum seek time
from the current head position
Total head movement: 236 cylinders.
Operating Systems
20
SCAN
 The disk arm starts at one end of the disk, and moves toward the other end,
servicing requests until it gets to the other end of the disk, where the head
movement is reversed and servicing continues.
Total head movement: 236 cylinders
Operating Systems
22
C-SCAN
 The head moves from one end of the disk to the other, servicing requests
as it goes. When it reaches the other end, it immediately returns to the
beginning of the disk, without servicing any requests on the return trip.
Total head movement: 382 cylinders
Operating Systems
24
C-LOOK
 Arm only goes as far as the last request in each direction, then reverses
direction immediately, without first going all the way to the end of the disk
Total head movement: 354 cylinders
Operating Systems
26
Test Yourself
 Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4999. The
drive is currently serving a request at cylinder 143, and the previous request
was at cylinder 125. The queue of pending requests, in FIFO order, is:

86,1470,913,1774,948,1509,1022,1750,130
 Starting from the current head position, what is the total distance (in
cylinders) that the disk arm moves to satisfy all the pending requests for
each of the following disk-scheduling algorithms?
a)
SSTF
b)
C-LOOK
Operating Systems
27
Selecting a Disk-Scheduling Algorithm
 SSTF is common and has a natural appeal
 SCAN and C-SCAN perform better for systems that place a heavy load on
the disk

Less starvation
 LOOK and C-LOOK have a little improvement over SCAN and C-SCAN
Operating Systems
28
RAID Structure
 Redundant Arrays of Inexpensive Disks (RAIDs)
 RAID – multiple disk drives provides reliability via redundancy

Mirroring


duplicate every disk
Parity bit
 Parallel access to multiple disk improves performance

Bit-level striping


split the bits of each byte across multiple disks
block-level striping

blocks of a file are striped across multiple disks
 RAID is arranged into seven different levels
Operating Systems
33
RAID Levels
C: a second copy
P: error-correcting bit
Operating Systems
34
RAID Levels (Cont.)
Block Striping
Striped Mirroring
P1
Operating Systems
P2
35
P3
Memory-style ErrorCorrecting Code
(ECC)
RAID Levels (Cont.)
bit-interleaved parity
block-interleaved parity
block-interleaved distributed
parity
Operating Systems
36
RAID Levels (Cont.)
 RAID 6: P + Q redundancy

Reed-Solomon codes

2 bits of redundant data are stored for every 4 bits of data

can tolerate two disk failures
Operating Systems
37
Disk Attachment
 Host-attached storage accessed through I/O ports talking to I/O busses
 SCSI itself is a bus, up to 16 devices on one cable, SCSI initiator requests
operation and SCSI targets perform tasks

Each target can have up to 8 logical units (disks attached to device
controller)
 FC is high-speed serial architecture

Can be switched fabric with 24-bit address space – the basis of storage
area networks (SANs) in which many hosts attach to many storage
units
Operating Systems
40
Network-Attached Storage
 Network-attached storage (NAS) is storage made available over a network
rather than over a local connection (such as a bus)

Remotely attaching to file systems
 NFS and CIFS are common protocols
 Implemented via remote procedure calls (RPCs) between host and storage
over typically TCP or UDP on IP network
 iSCSI protocol uses IP network to carry the SCSI protocol

Remotely attaching to devices (blocks)
Operating Systems
42
Storage Area Network
 Common in large storage environments
 Multiple hosts attached to multiple storage arrays - flexible
Operating Systems
43
Homework
 Reading

Chapter 12
Operating Systems
45