Transcript Document

Operating Systems
Operating Systems
Unit 9:
– Disk Performance
Optimization
– File Systems
Introduction
• Secondary storage is common bottleneck
– Improvements in secondary storage
performance significantly boost overall
system performance
• Physical aspects
– moving head disk storage
– access optimization
• Logical aspects
– file system organization
COP 5994 - Operating Systems
2
Moving-Head Disk Storage
COP 5994 - Operating Systems
3
Disk Surface: traditional
COP 5994 - Operating Systems
4
Disk Surface: modern
• Zone Density Recording
– fixed sector size (512 bytes)
– variable number of sectors
per track
• outside: zone 0
• transfer rate decrease as zone increases
COP 5994 - Operating Systems
5
Components of disk access
COP 5994 - Operating Systems
6
Disk Speed Examples
COP 5994 - Operating Systems
7
Disk Scheduling Evaluation
Criteria
• Throughput
– Number of requests serviced per unit of time
• Mean response time
– Average time waiting for request to be
serviced
• Variance of response times
– Measure of the predictability of response
times
– also: starvation
COP 5994 - Operating Systems
8
Scenario: Disk request
pattern
COP 5994 - Operating Systems
9
Seek Optimization Strategies
COP 5994 - Operating Systems
10
First-Come-First-Served (FCFS)
– Pro: fair, no starvation, low overhead
– Cons: Potential for extremely low throughput
COP 5994 - Operating Systems
11
Shortest-Seek-Time-First
(SSTF)
– Pro: high throughput, lower response times
– Cons: high variance, possible starvation
COP 5994 - Operating Systems
12
SCAN Disk Scheduling
– Pro: improved variance in response times
– Cons: possible starvation, middle tracks
preferred
COP 5994 - Operating Systems
13
C-SCAN Disk Scheduling
– Pro: improved variance in response times
– Cons: possible starvation
COP 5994 - Operating Systems
14
FSCAN and N-Step SCAN
• Groups requests into batches
– FSCAN: “freeze” the disk request queue
periodically, service only those requests in
the queue at that time
– N-Step SCAN: Service only the first n
requests in the queue at a time
• Pros: prevent indefinite postponement,
reduce variance of response times
COP 5994 - Operating Systems
15
LOOK and C-LOOK
• LOOK: Improvement on SCAN
scheduling
– Does move the disk arm to the outer edges
of the disk if no requests for those regions
are pending
– Pro: more efficient (less head movement)
• C-LOOK improves C-SCAN scheduling
– Combination of LOOK and C-SCAN
– Pro: Lower variance of response times
at the expense of throughput
COP 5994 - Operating Systems
16
Rotational Optimization Strategies
• SLTF
– Shortest-latency-time-first
– On a given cylinder, service request with shortest
rotational latency first
• SPTF
– Shortest-positioning-time-first
– positioning time: seek time plus rotational latency
• SATF
– Shortest-access-time-first
– Access time: positioning time plus transmission time
COP 5994 - Operating Systems
17
SLTF Scheduling
requests are serviced in the indicated order regardless of the order in which they arrived
COP 5994 - Operating Systems
18
SPTF Scheduling
Order: B then A
– Pro: good performance
– Cons: possible starvation
COP 5994 - Operating Systems
19
SATF Scheduling
Order: B then A
– Pro: good performance
– Cons: possible starvation
COP 5994 - Operating Systems
20
Another example: SPTF Scheduling
Order: B then A
COP 5994 - Operating Systems
21
SATF Scheduling: different order
Order: A then B
COP 5994 - Operating Systems
22
Optimization Strategies
Weakness
• require knowledge of
– disk performance characteristics
– physical disk geometry
• which might not be readily available due
to error-correcting data and transparent
reassignment of bad sectors
COP 5994 - Operating Systems
23
Other Disk Performance
Techniques
• Multiple copies of frequently-accessed data
– Access the copy that is closest to read-write head
– Can incur significant storage overhead
• Record blocking
– Read/write multiple records as single block of data
• Disk arm anticipation
– move disk arm to location of next access
– If the disk arm incorrectly predicts future disk
accesses, performance can significantly degrade
COP 5994 - Operating Systems
24
Caching and Buffering
• Store copy of disk data in faster memory
– Location:
• main memory
• disk controller
• onboard disk
• Read access:
– Vastly faster access times than access to disk
– Depends on cache-hit ratio
COP 5994 - Operating Systems
25
Caching and Buffering
• Write access:
– cache acts as buffer to delay writing of data
until disk is under light load
– caching model:
• Write-back caching
– Data not written to disk immediately
– Flushed periodically
• Write-through caching
– Writes to disk and cache simultaneously
– Reduces performance compared to write-back, but
guarantees consistency
COP 5994 - Operating Systems
26
RAID: Redundant Arrays of Independent
Disks
– Data stored in strips
• Spread across set of disks
– Strips form stripes
• Set of strips at same location on each disk
– Fine-grained strip
• Yields high transfer rates
– (many disks service request at once)
• Array can only process one request at once
– Coarse-grained strips
• Might fit an entire file on one disk
• Allow multiple requests to be filled at once
COP 5994 - Operating Systems
27
RAID strips and stripes
Strips and stripe created from a single file in RAID systems
COP 5994 - Operating Systems
28
RAID drawbacks
• disks have MMTF (mean time to failure)
• more disks decreases MMBF (between)
• RAID allows data duplication feature
– mirroring
– strip-based ECC
COP 5994 - Operating Systems
29
RAID levels
COP 5994 - Operating Systems
30
File System
Organizes files and manages access to
data
• Responsible for file management,
auxiliary storage management, file
integrity mechanisms and access
methods
• Primarily concerned with managing disk
storage space
COP 5994 - Operating Systems
31
File Systems characteristics
• device independence
– use file names rather than physical device
ids
• backup and recovery capabilities
– to prevent either accidental loss or malicious
destruction of information
• encryption and decryption capabilities
– to make information useful only to its
intended audience
COP 5994 - Operating Systems
32
Basic File System Concept: Directory
• contains names and locations of other files:
– to organize and quickly locate files
• entry stores information such as:
–
–
–
–
–
–
File name
Location
Size
Type
Accessed
Modified and creation times
COP 5994 - Operating Systems
33
Common: Hierarchical File System
COP 5994 - Operating Systems
34
File System Concept: Link
• Directory entry that references a data file or
directory located in a different directory
– Facilitates data sharing and can make it easier for
users to access files located throughout a file
system’s directory structure
• Soft link:
– entry containing the pathname for another file
• Hard link
– entry that specifies the location of the file (typically
a block number) on the storage device
– needs updating when file moves
COP 5994 - Operating Systems
35
File System Concept:
Metadata
• Information that protects integrity of file
system
– Cannot be modified directly by users
• example: file systems superblock
– stores critical information that protects the
integrity of the file system:
• The file system identifier
• The location of the storage device’s free blocks
– storage device holds redundant copies of
superblock
COP 5994 - Operating Systems
36
File System Concept: File
Descriptor
• file open operation returns a file
descriptor
– index to open-file table
• all file access through the file descriptor
• open-file table contains file control block:
– file attributes:
•
•
•
•
symbolic name
location in secondary storage
access control data
etc.
COP 5994 - Operating Systems
37
File System Concept:
Mounting
• Combines multiple file systems into one
• Mount point:
– directory where the mounted file system is inserted
• Mount table:
– information about the location of mount points and
the devices to which they point
• When the native file system encounters a
mount point, it uses the mount table to
determine the device and type of the mounted
file system
COP 5994 - Operating Systems
38
Mounting
Links: only soft links across mounted file
systems
COP 5994 - Operating Systems
39
File Allocation
• Problem similar to memory organization
• contiguous allocation schemes have
generally been replaced by more
dynamic noncontiguous allocation
– Files tend to grow or shrink over time
– Users rarely know in advance how large
their files will be
COP 5994 - Operating Systems
40
Contiguous File Allocation
• Place file data at contiguous addresses on
disk
– Advantages
• Successive logical records typically are physically adjacent
to one another
– Disadvantages
• External fragmentation
• Poor performance can result if files grow and shrink over
time
• If a file grows beyond the size originally specified and no
contiguous free blocks are available, it must be transferred
to a new area of adequate size, leading to additional I/O
operations.
COP 5994 - Operating Systems
41
Non-Contiguous File
Allocation
• linked-list
• tabular
• indexed
COP 5994 - Operating Systems
42
Linked-List Noncontiguous File Allocation
block based:
– data
– pointer to
next
block
COP 5994 - Operating Systems
43
Linked-List Noncontiguous File Allocation
• Locating a record
– linked list must be searched from the
beginning
– if blocks are dispersed throughout the
storage device (which is normal), the search
process can be slow as block-to-block seeks
occur
• Insertion and deletion are done by
modifying the pointer in the previous
block
COP 5994 - Operating Systems
44
Linked-List Noncontiguous File Allocation
• Large block sizes
– Can result in significant internal
fragmentation
• Small block sizes
– May cause file data to be spread across
multiple blocks dispersed throughout the
storage device
– Poor performance as the storage device
performs many seeks to access all the
records of a file
COP 5994 - Operating Systems
45
Tabular Noncontiguous File Allocation
• directory entry
lists first block of
file
• table cell stores
link to next block
• empty table cell
marks end of file
ex.: FAT file system
COP 5994 - Operating Systems
46
Tabular Noncontiguous File Allocation
• Pros:
– reduces the number of lengthy seeks
required to access a particular record
– table can be cached so that the chain of
blocks that compose a file can be traversed
quickly
• Cons:
– cell entry size/block size dictates file system
size
– table can grow too large to cache
COP 5994 - Operating Systems
47
Indexed Noncontiguous File Allocation
• directory entry
lists index
block(s)
• index blocks
lists data
blocks
• index block
reserves last
few entries for
more index
blocks
COP 5994 - Operating Systems
48
Indexed Noncontiguous File Allocation
• Pros:
– Searching takes place in the index blocks
• File systems typically place index blocks
near the data blocks they reference, so
the data blocks can be accessed quickly
after their index block is loaded
COP 5994 - Operating Systems
49
Unix Indexed Noncontiguous File
Allocation
• multi-level
index
blocks
COP 5994 - Operating Systems
50
Free Space Management
• manage the storage device’s free space
• Free list:
– Linked list of blocks containing locations of free
blocks
– Blocks are allocated from the beginning of free
list
– Pro: low overhead
– Con: blocks are non-contiguous
COP 5994 - Operating Systems
51
Free Space Management via bitmap
COP 5994 - Operating Systems
52
Free Space Management
• Advantage of bitmaps over free lists:
– The file system can quickly determine if
contiguous blocks are available at certain
locations on secondary storage
• Disadvantage of bitmaps:
– The file system may need to search the
entire bitmap to find a free block, resulting in
substantial execution overhead
COP 5994 - Operating Systems
53
Data Integrity Protection
• System crashes, natural disasters and
malicious programs can destroy
information
• Protection:
– backup and recovery
• physical backup
• logical backup
• incremental backup
– RAID
– transaction based file systems
COP 5994 - Operating Systems
54
Journaling File Systems
– Windows: NTFS
– Linux: ext3
• file system operations are logged as
transactions
• compromise:
– log only metadata transactions
COP 5994 - Operating Systems
55
Agenda for next week:
– Chapter 16 & 18:
• Networking
• Distributed File Systems
– Read ahead !
COP 5994 - Operating Systems
56