Page 1

Secondary Storage Management

Disks — just like memory, only different
◆ Why have disks?
» We’ll never have enough memory
1

❖ memory — 341 KB/dollar or $3/MB

❖ disks — 33 MB/dollar or $0.03/MB
➭ disks as short term storage
❖ swap space for virtual memory system
Secondary Storage Management

http://www.cse.unl.edu/~goddard/Courses/CSCE451

» Memory is volatile
➭ disks as long term storage
❖ files
[email protected]

2
Operating Systems Principles

Steve Goddard

Lecture 15
CSCE 451/851

CSCE 451/851
Steve Goddard
CSCE 451/851
Steve Goddard Lecture 15 Page 2
 Anatomy of a Disk Anatomy of a Disk
Basic components Example: Seagate 9GB Fast/Wide/Differential SCSI disk

Track Block/Sector ◆ Specs:

» 12 platters » 11 arms
s–1 0
1 » 22 heads » 4,735 tracks
Head
2 » variable # of sectors/track » 512 bytes/sector
... Cylinder » 7,200 RPM
❖ average latency: 4.2 ms.
» Seek times
❖ track-to-track: 1 ms
❖ average: 7.9 ms
Surface Platter » 40MB/s peak transfer rate

Spindle

3 4

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 3 Steve Goddard Lecture 15 Page 4
 Disk Operations Disk Addressing
Data transfer in units of sectors Mapping a 3-D structure to a 1-D structure
Surface
Random access devices with non-uniform access times

◆ Present disk with a sector address Track

» DA = (drive, surface, track, sector) ?
◆ Head moved to appropriate track 0 n
» “seek time” Sector
◆ The appropriate head is enabled
◆ Wait for the sector to appear under ◆ Mapping criteria t–1 ... 1 0
the head
» “rotational latency” » block n+1 should be a close p–1
...

...
s–1 0 1
◆ Read/write the sector as possible to block n
1
» “transfer time”
0

5 6

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 5 Steve Goddard Lecture 15 Page 6
 Disk Addressing Disk Addressing
The impact of a good/bad file mapping Cylinder-based mappings
◆ Consider the time required to read/write a 1 MB file stored in
contiguous locations in the OS file block array ... ...
» File requires 2,048 sectors
◆ Array elements map to contiguous sectors on disk track 0 track 0 track 0 ... track 0 track 1 track 1 ...
surface 0 surface 1 surface 2 surface p–1 surface 0 surface 1
» Middle of the disk
2,048
❖ 7.9 + 4.2 + 8.3
3,712
= 12.1 + 4.6 = 16.7 ms cylinder 0 cylinder 1
Transfer time = (time per rev) × (# of revs required)
» Outside of disk ◆ Sector address to block list
2,048 mapping
❖ 7.9 + 4.2 + 8.3 = 12.1 + 1.1 = 13.3 ms
14,848
» Center of disk » s sectors
❖ 7.9 + 4.2 + 8.3
2,048
= 12.1 + 18.3 = 30.4 ms
» p platters
928
◆ Array elements map to random sectors on disk (surface j, track i, sector k) = k + s(j + ip)
» 2,048× (7.9 + 4.2) = 24.8 secs!
7 8

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 7 Steve Goddard Lecture 15 Page 8
 Disk Space Management Device Directory
Device Directory Allocated space representations

◆ A block(s) on disk containing... ◆ Single-level directory

» data structures storing names, locations, lengths, owner, etc. » easy to build
of all files on disk » all file names must be unique
❖ a symbol table
» data structures storing free block list ◆ Two-level directory
» a separate directory for each
◆ Stored at a fixed location on disk user/project/group
◆ Directory operations ◆ Trees
» search (find a file) » Delete a file ◆ Acyclic graphs
❖ linear search » List contents of a directory
❖ binary search » problems with...
» Backup ❖ aliases
❖ hash table
❖ file deletion
» Create a file
❖ backups

9 10

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 9 Steve Goddard Lecture 15 Page 10
 Device Directory Device Directory
Free list representation Other free list representation schemes
◆ Bit vector: 111111111111111001110101011101111... ◆ In-situ linked lists
» If bit i = 0 then block i is free, if i = 1 then it is allocated
» Simple to use but this can be a big vector:
❖ 17.5 million elements for a 9 GB disk (2.2 MB worth of bits)

» However, if free sectors are uniformly distributed across the

disk then the expected number of bits that must be scanned ◆ Grouped lists
before finding a “0” is
n/r
where Next
group
n = total number of blocks on the disk, block
r = number of free blocks
❖ If a disk is 90% full, then the average number of bits to be scanned is
10, independent of the size of the disk
11 12

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 11 Steve Goddard Lecture 15 Page 12
 File Allocation Methods File Allocation Methods
Contiguous allocation Linked allocation

◆ Directory entry specifies starting block & length

◆ Placement ◆ Files stored as a linked list of blocks
» First-fit, best-fit, ... ◆ Directory entry is a pointer to the first & last file blocks
◆ Pluses ◆ Minuses ◆ Pluses ◆ Minuses
» Best file read/write » Fragmentation! » Easy to create, grow & » Impossible to do true random
performance » Problems with file growth shrink files access
» Efficient sequential & ❖ Pre-allocation? » No fragmentation » Reliability
random access ❖ On-demand allocation? ❖ Break one link in the chain and...

13 14

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 13 Steve Goddard Lecture 15 Page 14
 File Allocation Methods Indexed Allocation
Indexed allocation Handling large files

◆ Linked index blocks

◆ Create a non-data block for each file called the index block
» A list of pointers to file blocks
◆ Directory entry is a pointer to the index block
◆ Multilevel index blocks
◆ Pluses ◆ Minuses
» Easy to create, grow & » Overhead of storing index
shrink files when files are small
» No fragmentation » How to handle large files?
» Supports direct access
15 16

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 15 Steve Goddard Lecture 15 Page 16
 Indexed Allocation Indexed Allocation in UNIX
Indexed allocation in UNIX Multilevel, indirection, index blocks
1st Level
◆ Small files Device Indirection
Directory Block n
» A single index block Data
Blocks

n2
Data
Blocks
2nd Level
Indirection
Block
◆ Medium size files n3
» An indirection block Data
Blocks

3rd Level
Indirection
Block

17 18

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 17 Steve Goddard Lecture 15 Page 18
 Disk Head Scheduling Disk Head Scheduling
Maximizing disk throughput Examples

◆ In a multiprogramming/timesharing environment, disk ◆ Assume a queue of requests exists to read/write tracks:

I/O requests are queued up » 150 16 147 14 72 83 and the head is on track 65

Disk
0 25 50 75 100 125 150

CPU
Other
I/O

◆ The OS maximizes disk I/O throughput by minimizing

head movement through disk head scheduling ◆ FCFS scheduling results in the head moving 550 tracks
» Can we do better?
19 20

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 19 Steve Goddard Lecture 15 Page 20
 Disk Head Scheduling Disk Head Scheduling
Minimizing head movement Optimal scheduling

◆ Greedy scheduling: shortest seek time first ◆ Rearrange queue from: 150 16 147 14 72 83
» Rearrange queue from: 150 16 147 14 72 83 To: 16 14 72 83 147 150
To: 72 83 147 150 16 14
0 25 50 75 100 125 150
0 25 50 75 100 125 150

◆ SCAN scheduling
» Move the head in one direction until all requests have been
◆ SSTF results in the head moving 221 tracks serviced and then reverse
» Can we do better? » Results in the head moving 187 tracks

21 22

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 21 Steve Goddard Lecture 15 Page 22
 Disk Head Scheduling Speeding Up Disk I/O
Other variations Disk architectures
◆ C-SCAN scheduling (“Circular”-SCAN) ◆ Disk striping
» Move the head in one direction until an edge of the disk is
reached and then reset to the opposite edge » Blocks broken into sub-blocks that are stored on separate disks
❖ similar to memory inter-leaving
0 25 50 75 100 125 150
» Provides for higher disk bandwidth through a larger effective
block size

1 2 3

◆ LOOK scheduling
» C-SCAN except the head is reset when no more requests exist
between the current head position and the approaching edge of
the disk
23 24

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 23 Steve Goddard Lecture 15 Page 24
 Speeding Up Disk I/O RAID Disks
Disk architectures Improving reliability & availability
◆ RAID (redundant array of inexpensive disks) disks ◆ Block interleaved parity striping
» Bit-wise striping of the disks (RAID-3) or » Allows one to recover from the crash of any one disk
» Block-wise striping of the disks (RAID-5)
» Example: storing 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3
» Provides better performance & reliability
◆ Example: storing the bit-string 101 Layout on a 1000 1011 1110 0001
1001 1100 1111 0010
non-RAID disk: 1 0 1 0 1101 0000 0011
1 2 3 Block 1 Block 2 Block 3 Block 4

1111 0000 0011 0101 1001

RAID 1111 1111 0011 0101 0110
layout: 0000 0000 0011 0101 0110
1xxxx 0xxxx 1xxxx Block 1 Block 1 Block 1 Block 1 Block 1
xxxxx xxxxx xxxxx Disk 1 Disk 2 Disk 3 Disk 4 Disk 5
xxxxx xxxxx xxxxx
25 26

CSCE 451/851 CSCE 451/851

Steve Goddard Lecture 15 Page 25 Steve Goddard Lecture 15 Page 26