Transcript Chapter_12

Mass-Storage Structure
CS 540 – Chapter 12
Kate Dehbashi
Anna Deghdzunyan
Fall 2010
Dr. Behzad
Agenda

Review



Overview




Magnetic Disks
Magnetic Tapes
Disk Structure
Disk Attachment




File System
Parts of File System
Host-attached
Network-attached
Storage-Area Networks
Disk Scheduling


Scheduling Algorithms
Selection of an algorithm
Agenda (Cont.)

Disk Management




Disk Formatting
Boot Block
Bad-Block Recovery
Swap-Space Management



How is it used
Where is it located
How is it managed
Review

File System





Method of storing and organizing computer
files and their data
Storage
Organization
Manipulation
Retrieval

Maintain physical location
Review (Cont.)

Parts of File System

Interface


Implementation


User and programmer interface to the file system
Internal data structure and algorithms used to implement the
interface
Storage Structure





Physical structure
Disk scheduling algorithms
Disk formatting
Disk reliability
Stable-storage implementation
Overview


Magnetic Disks
Magnetic Tape
Magnetic Disks

Structure








Platter
Track
Sector
Cylinder
Disk arm
Read-write head
Rotates 60-200 times/second
Disk Speed


Transfer rate
Positioning time


Seek time
Rotational latency
Magnetic Disks (Cont.)

Head Crash



Disk head making contact with the disk surface
Permanent damage
Removable Magnetic Disks

Floppy


I/O bus



Drive attached to computer via set of wires
Busses vary, including EIDE, ATA, SATA, USB, Fiber Channel,
SCSI, Fire wire
Disk Controller


Head sits directly on the surface  Slow rotation and lower disk space
Cache memory
Host controller
First HDD – IBM RAMAC 1956
1.5 square meters (16 sq ft).
$3200.00
Magnetic Tape

Early secondary-storage medium


Holds large quantities of data




Random access ~1000 times slower than disk
Once data under head, transfer rates comparable to disk
Modern Usage


LTO-5 (2010) 1.5 TB uncompressed data (book: 20-200GB)
Access time slow


First used in1951 as a computer storage
Backup, archive
For large amount of data tape can be substantially less expensive
than disk
Common technologies


4mm, 8mm, 19mm
LTO (Linear Tape-Open), SDLT (Digital Linear Tape)
LTO-2
¼ , ½ inch
SDLT
Disk Structure

Addressing


One-dimensional array of blocks
Logical Block



Smallest unit of transfer
512 bytes
Blocks maps to sectors sequentially


Sector 0: first sector, first track, outmost cylinder
Mapping order



Track
Rest of the tracks in the same cylinder
Rest of the cylinders from outermost to innermost
Disk Structure (Cont.)

Logical block number


Cylinder#, track#, sector#
In practice it is difficult to perform


Defective sectors
Sectors/track is not constant

CLV (Constant Linear Velocity)



Constant density of bits/track
Variable rotational speed
CAV (Constant Angular Velocity)


Constant rotational speed
Variable density of bits per track
Disk Attachment

Host-Attached Storage (DAS)

Accessed through local I/O ports



Wide variety of storage devices


HDD, RAID Arrays, CD/DVD Drives and Tape
Network-Attached Storage (NAS)



IDE, ATA, SATA
SCSI, FC
NAS
ISCSI
Storage-Area Network (SAN)


SAN
infiniBand
Host-Attached Storage
SCSI

SCSI (Small Computer System Interface)





Large variety of devices
16 devices per cable
Controller card (SCSI Initiator)
SCSI target
8 logical units per target
Host-Attached Storage
FC

FC (Fiber Channel)



High-speed serial architecture
Optical cable, four-conductor copper cable
Switched fabric (FC - SW)





All devices are connected to fiber channel switches
24-bit address space  multiple hosts and storage
devices
Dominate in future
Basic of SANs
Arbitrated Loop (FC – AL)



126 devices
All devices are in a loop or ring
Historically lower cost but rarely used now
FC – Topologies
Network-Attached Storage

NAS



Storage system
Accessed remotely over a data network
Clients access via remote-procedure-call interface





UNIX: NFS
Windows: CIFS
RPCs carried via TCP/UDP
Convenient way for all clients to share a pool of
storage
NAS VS local-attached


Same ease of naming and access
Less efficient and lower performance
Network-Attached Storage (Cont.)

ISCSI –





Internet Small Computing System Interface
Latest NAT protocol
IP-based storage networking protocol
Uses IP network to carry SCSI Protocol
Clients are able to send SCSI commands to
remote targets
TCP ports 860 and 3260
Storage-Area Networks

SAN





Private network connecting servers and
storage devices
Uses storage protocols instead of networking
protocols
Multiple hosts and storage can attach to the
same SAN  flexibility
SAN Switch allows/prohibits client access
(exp.)
FC is the most common SAN interconnect
Storage-Area Networks (Cont.)

InfiniBand


Special-purpose bus architecture
Supports high-speed interconnection network



Up to 2.5 gbps
64,000 addressable devices
Supports QoS and Failover
Disk Scheduling

Disk Drive Efficiency

Access time



Seek time
Rotational latency
Bandwidth

Bytes transferred / Δt


Δt: Completion time of the last transfer – first request for
service time
Improve?

Scheduling the servicing of I/O requests
in a good order
Disk Scheduling (Cont.)

I/O request procedure


System Call Sent by the process to the OS
System Call information





Input/output
Disk address
Memory address
Number of sectors to be transferred
If disk available  access
else  Queue
Disk Scheduling (Cont.)

Algorithms





FCFS
SSTF
SCAN
C-SCAN
LOOK/CLOOK
Disk Scheduling (Cont.)

FCFS (First come First Served)
640 cylinder
moves
Disk Scheduling (Cont.)

SSTF (Shortest Seek Time First)
 Service requests close to the current head position
 Starvation
236 cylinder
moves
Disk Scheduling (Cont.)

SCAN (Elevator Alg.)
 Head starts at one end and goes to the other end
 Services each request on the current track
236 cylinder
moves
Disk Scheduling (Cont.)

CSCAN



Variant of SCAN
More uniform wait time
When head reaches the end, immediately moves to the
beginning without servicing any request
360 cylinder
moves
Disk Scheduling (Cont.)

LOOK/CLOOK
 Head goes as far as the last request in each direction
322 cylinder
moves
Disk Scheduling (Cont.)

Selection of an algorithm Factors



SSTF is common and better performance than FCFS
SCAN, CSCAN perform better for systems that place a
heavy load on the disk No starvation
Scheduling alg. Performance (example1)



Number of requests
Types of requests
Requests for disk service can be influenced by


The file-allocation method (example2)
Location of directories and indexed blocks

Caching directories and indexed blocks in the
main memory reduces arm movement (example3)
Disk Scheduling (Cont.)

Selection of an algorithm



Separate module of the OS  can be replaced if
necessary
Default: SSTF/LOOK
Rotational Delay Perspective



Modern disks do not disclose the physical location of
logical blocks
Disk controller takes over OS to choose the alg.
Problem?


If only I/O  OK
But there are other constraints

Example: request for paging (example)
Disk Management

Disk Formatting



Boot Block


Low-level
Logical
Bootstrap
Bad-Block Recovery



Manually
Sector Sparing (Forwarding)
Sector Slipping
Disk Formatting

Low-Level Formatting (Physical Formatting)

Header, Trailer


Sector Number
ECC



Data-Area


Error detection
Soft error recovery
512 bytes
Logical Formatting

Partition



One or more group of cylinders
Each partition is treated as a separate disk (example)
Logical Formatting

Storing of initial file system



Cluster



Map of allocated and free space
An initial empty Directory
Blocks are put together to increase efficiency
Disk I/O done via blocks/File I/O done via clusters
Raw disk

Some programs use the disk partition as a large sequential array of
logic blocks bypassing the file system services
Boot Block

Bootstrap Program


Initial program to start a computer system
Initializes aspects of the system




Starts the OS



CPU registers
Device controllers
Contents of the main memory
Finds the OS Kernel on disk and loads it into the memory
Jumps to an initial address to begin the OS exec.
Stored in ROM



No need for initialization
No virus
Problem? Hard to update  solution: save the bootstrap
loader in the ROM, full bootstrap on boot blocks (fixed
location on HDD)
Booting from a Disk in Windows 2000
Bad-Block Recovery

Complete Disk Failure


Replace the disk
Bad Sector Handling

Manually



Sector Sparing (Forwarding)









SCSI
Controller maintains a bad sector list
List is initialized during the low-level
formatting
Controller sets aside spare sectors to replace
bad sectors logically (Example)
Problem? Invalidate optimization done by disk
scheduling alg.
Solution? Spare sectors on each cylinder
Sector Slipping


IDE: format, chkdsk
Special entry into FAT
Move down every sector tom empty the next sector to the bad sector
Example
Soft-error: repairable by disk controller through ECC
Hard-error: lost data  back up
Swap-Space Management


In modern Operating Systems, “Paging”
and “Swapping” are used interchangeably
Virtual memory uses disk space as an
extension of the main memory


Performance decreases. why?
Swap-space management goal

To get the best throughput for the
virtual memory system
Swap-Space Management (Cont.)

How is it used?

Depends on memory management alg.



Swapping: Load entire process into disk
Paging: Stores pages
Amount of swap space needed depends on








Amount of physical memory
Amount of virtual memory
Way virtual memory is used
Ranges from few MB to GB
Better to overestimate why? No process is aborted
Solaris: swap space = amount by which VM exceeds pageable
physical memory
Linux: swap space = double the amount of
physical memory
Multiple swap spaces
Swap-Space Management (Cont.)

Where is it located on disk?

In the normal file system



Large file within the file system
File-system routines can be used
Easy to implement but inefficient


Separate disk partition







Takes time to traverse the directory structure
Raw partition
Swap space storage manager
Uses alg. Optimized for speed rather than storage efficiency
why?
Trade-off between speed and fragmentation  acceptable
(data life is short)
Fixed amount of space is set aside during partitioning
Adding more space requires re-partitioning
Linux: Supports both

Who decides?
Swap-Space Management (Cont.)

How is it managed?

Unix



Traditional: copy the entire processes
Newer: combination of swapping & paging
Solaris1



File-system: text-segment pages containing code
Swap-space: pages of anonymous memory
such as stack or heap
Modern versions only allocate the swap space if
page is forced out of the main memory
Swapping on Linux System
References





Wikipedia.com
PCTechGuide.com
USRobotics.com
allSAN.com
Xenon.com.au