Site hosted by Angelfire.com: Build your free website today!

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

_ HW 6 due today (Friday)

_ Lab 4 due on Monday (please turn in on time!)

CMPSCI 377: Operating Systems Lecture 24, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Last Class: I/O Systems

_ I/O is expensive for several reasons:

{ Slow devices and slow communication links

{ Contention from multiple processes.

{ I/O is typically supported via system calls and interrupt handling,

which are slow.

_ Approaches to improving performance:

{ Reduce data copying by caching in memory

{ Reduce interrupt frequency by using large data transfers

{ O_oad computation from the main CPU by using DMA controllers.

{ Increase the number of devices to reduce contention for a single device

and thereby improve CPU utilization.

{ Increase physical memory to reduce amount of time paging and thereby

improve CPU utilization.

CMPSCI 377: Operating Systems Lecture 24, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today: Secondary Storage

Surface

Sectors / Blocks

Disk

Track / Cylinder

Head

_ Recall: to read or write a disk block:

{ Seek: (latency) position head over a track/cylinder. The seek time

depends on how fast the hardware moves the arm.

{ Rotational delay: (latency) time for the sector to rotate underneath

the head. Rotational delay depends upon how fast the disk spins.

{ Transfer time: (bandwidth) time to move the bytes from the disk to

memory

{ Disk I/O Time = seek + rotational delay + transfer.

CMPSCI 377: Operating Systems Lecture 24, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Typical Disk Parameters (2 years out of date)

Good PC disk High-end disk

Disk Capacity 4 GB 36.4 GB

platters per pack 10 10

tracks per surface 3832 11540

sectors per track 134 215

bytes per sector 512 732

revolutions per minute 7200 7200

average seek time 8.5 ms 7.5 ms

average rotational latency 4.17 ms 4.17 ms

bu_er to host burst transfer rate 20 MB/sec 200 MB/sec

bu_er size 1 MB 4 MB

size 3.5 inches 3.5 inches

CMPSCI 377: Operating Systems Lecture 24, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Access Time

_ Key: to get the quickest disk response time, we must minimize seek time

and rotational latency:

{ Make disks smaller

{ Spin disks faster

{ Schedule disk operations to minimize head movement

{ Lay out data on the disk so that related data are on nearby tracks.

{ Place commonly-used _les where on the disk?

{ We should also pick our sector size carefully:

_ If the sector size is too small, we will have a low transfer rate because

we will need to perform more seeks for the same amount of data.

_ If our sector size is too large, we will have lots of internal

fragmentation.

CMPSCI 377: Operating Systems Lecture 24, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Disk Head Scheduling

_ Typically several disk read requests have been made (by one process, by

several processes, or by the OS)

_ Idea: Permute the order of disk requests from the order that they arrive

from the users to an order that reduces the length and number of seeks.

1. First-come, _rst-served (FCFS)

2. Shortest seek time _rst (SSTF)

3. SCAN algorithm (0 to 100, 100 to 0, 0 to 100, ...). If there is no

request between current position and the extreme (0 or N), we don't

have to seek there.

4. C-SCAN circular scan algorithm (0 to 100, 0 to 100, ...)

CMPSCI 377: Operating Systems Lecture 24, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

FCFS Disk Head Scheduling

Example requests: 65, 40, 18, 78

1. FCFS - service the requests in the order that they come in

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

_ Order of seeks:

_ Distance of seeks:

_ When would you expect this algorithm to work well?

CMPSCI 377: Operating Systems Lecture 24, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

FCFS Disk Head Scheduling

Example requests: 65, 40, 18, 78

1. FCFS - service the requests in the order that they come in

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

_ Order of seeks: 65, 40, 18, 78

_ Distance of seeks: 35 + 25 + 22 + 60 = 142

_ When would you expect this algorithm to work well?

If the requests were near one-another.

CMPSCI 377: Operating Systems Lecture 24, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

SSTF Disk Head Scheduling

_ SSTF: always go to the next closest request

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

{ Order of seeks:

{ Distance of seeks:

{ Can implement this approach by keeping a doubly linked sorted list of

requests.

{ Is this e_cient enough?

{ Is it optimal?

{ Problems?

CMPSCI 377: Operating Systems Lecture 24, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

SSTF Disk Head Scheduling

_ SSTF: always go to the next closest request

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

{ Order of seeks: 40, 18, 65, 78

{ Distance of seeks: 10 + 22 + 47 + 13 = 92

{ Is this e_cient enough? Yes, the cost of computation is minor relative

to the seek time.

{ Is it optimal? No, it's greedy. Minimizes cost of next seek, but not

overall cost.

{ Problems? Potential for starvation

CMPSCI 377: Operating Systems Lecture 24, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

SCAN Disk Head Scheduling

_ SCAN: head moves back and forth across the disk (0 to 100, 100 to 0, 0

to 100, ...), servicing requests as it passes them

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

{ Order of seeks, assuming the head is currently moving to lower

numbered blocks:

{ Distance of seeks:

CMPSCI 377: Operating Systems Lecture 24, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

SCAN Disk Head Scheduling

_ SCAN: head moves back and forth across the disk (0 to 100, 100 to 0, 0

to 100, ...), servicing requests as it passes them

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

{ Order of seeks, assuming the head is currently moving to lower

numbered blocks: 18, 40, 65, 78

{ Distance of seeks: 12 + 22 + 25 + 13 = 72

{ Requires a sorted list of requests.

{ Simple optimization: do not go all the way to the edge of the disk each

time, but just as far as the last request.

CMPSCI 377: Operating Systems Lecture 24, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

C-SCAN Disk Head Scheduling

_ C-SCAN: circular scan algorithm (0 to 100, 0 to 100, ...)

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

{ Order of seeks:

{ Distance of seeks:

CMPSCI 377: Operating Systems Lecture 24, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

C-SCAN Disk Head Scheduling

_ C-SCAN: circular scan algorithm (0 to 100, 0 to 100, ...)

time

0 10 20 30 40 50 60 70 80 90 100

Track Positions on Disk

{ Order of seeks: 40, 65, 78, 18

{ Distance of seeks: 10 + 25 + 13 + 60 = 108

{ More uniform wait times for requests. Why? At the end of a pass,

most of the requests are at the other end. With SCAN, a request

might need to wait for 2 almost-complete sweeps of the disk before it

would get processed.

CMPSCI 377: Operating Systems Lecture 24, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Improving Disk Performance using Disk Interleaving

_ Problem: Contiguous allocation of _les on disk blocks only makes sense if

the OS can react to one disk response and issue the next disk command

before the disk spins past the next block.

_ Idea: Interleaving - Don't allocate blocks that are physically contiguous,

but those that are temporally contiguous relative to the speed with which

a second disk request can be received and the rotational speed of the

disk. Might use every second or third block.

CMPSCI 377: Operating Systems Lecture 24, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Improving Disk Performance using Read Ahead

_ Idea: read blocks from the disk ahead of user's request and place in

bu_er on disk controller.

_ Goal: reduce the number of seeks - read blocks that will probably be

used while you have them under the head.

_ We considered pre-fetching virtual pages into physical memory, but

decided that was di_cult to do well since the future is di_cult to predict.

Is disk read-ahead any better?

CMPSCI 377: Operating Systems Lecture 24, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Improving Disk Performance using Read Ahead

Yes, for sequentially accessed _les.

CMPSCI 377: Operating Systems Lecture 24, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Tertiary Storage

_ Lower cost devices than secondary storage (disks)

_ Typically Slower, BUT: larger and cheaper than disks

_ Used primarily for storing archival data or backups.

{ tape drives

{ Jazz and Zip drives

{ Optical disks: Write once read-many (WORM), CD-R, CD-RW

{ Robotic jukeboxes

_ Primary, secondary and tertiary devices form a storage hierarchy

CMPSCI 377: Operating Systems Lecture 24, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary

_ Disks are slow devices relative to CPUs.

_ For most OS features, we are very concerned about e_ciency.

_ For I/O systems, and disk, in particular, it is worthwhile to complicate

and slow down the OS if we can gain improvement in I/O times.

_ Review Questions:

{ What property of disks can we use to make the insertion, deletion, and

access to the lists of requests fast?

{ Rank the algorithms according to their expected seek time.

{ Is SCAN or SSTF fairer?

{ Is SCAN or C-SCAN fairer?

CMPSCI 377: Operating Systems Lecture 24, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary

_ Review Questions:

{ What property of disks can we use to make the insertion, deletion, and

access to the lists of requests fast?

Disk operations are very slow relative to the CPU/memory operations

required to maintain these lists.

{ Rank the algorithms according to their expected seek time.

C-SCAN > SCAN > SSTF (*** dependent on the query set)

{ Is SCAN or SSTF fairer?

SCAN

{ Is SCAN or C-SCAN fairer?

C-SCAN

CMPSCI 377: Operating Systems Lecture 24, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

_ Distributed File Systems (Chapter 17)

CMPSCI 377: Operating Systems Lecture 24, Page 21