Transcript Systems Architecture, Fifth Edition

Chapter Goals
• Describe the components and functions of a file
management system
• Compare the logical and physical organization of
files and directories
• Explain how secondary storage locations are
allocated to files and describe the data structures
used to record those allocations
Systems Architecture, Fifth Edition
2
Chapter Goals (continued)
• Describe file manipulation operations, including
open, close, read, delete, and undelete operations
• List access controls that can be applied to files and
directories
• Describe security, backup, recovery, and fault
tolerance methods and procedures
• Compare and contrast storage area networks and
network-attached storage
Systems Architecture, Fifth Edition
3
File Management Systems
(FMS)
• Collection of system software that manages all
aspects of user and program access to secondary
storage
• Usually part of the operating system
• Translates operations into commands to physical
storage devices
• Implemented in four layers (command layer, file
control, storage I/O control, and secondary storage
devices)
Systems Architecture, Fifth Edition
4
Bridges between logical and
physical views of secondary
storage
Allocates secondary storage
locations to individual files
and directories
Includes software modules
for device drivers for each
storage device or device
controller, interrupt
handlers, buffers and cache
managers
Systems Architecture, Fifth Edition
5
Logical and Physical
Storage Views
• Logical view
– Collection of files organized within directories and
storage volumes
• Physical view
– Collection of physical storage locations organized
as a linear address space
Systems Architecture, Fifth Edition
6
Systems Architecture, Fifth Edition
7
The file is subdivided into multiple records and each
record is composed of multiple fields.
Systems Architecture, Fifth Edition
8
Logical File Structure
• Is independent of the physical device on which it
is stored
• Also includes physical data access considerations,
such as sequential access, indexed access, or some
other
• There are also data encoding issues including the
data structures and coding methods used to
represent individual fields
• And don’t forget encryption and compression
Systems Architecture, Fifth Edition
9
File Content and Type
• FMS supports limited number of file types:
– Executable programs (.exe and .dll)
– Operating system commands (.bat)
– Textual or unformatted binary data (.txt)
• Modern FMSs can define new file types and install
utility programs to manipulate them (file association)
Systems Architecture, Fifth Edition
10
File Types
• Normally declared when a file is created and:
– Stored within a directory, or
– Declared through a filename convention
• Determine:
– Physical organization of data items and data
structures within secondary storage
– Operations that may be performed upon the file
– Filename restrictions
Systems Architecture, Fifth Edition
11
Systems Architecture, Fifth Edition
12
Systems Architecture, Fifth Edition
13
Directory Content and Structure
• Contains information about files and other
directories, typically name, file type, location,
size, ownership, access controls, and time stamps
• Old MS-DOS used 8.3 naming convention
• Newer NTFS allows 255 Unicode characters
• Access controls include List, Read, Modify,
Change, Edit, Delete, etc.
• Time stamps include file creation date, last
modified date, when file last read, …
Systems Architecture, Fifth Edition
14
Hierarchical Directory Structure
• Directories can contain other directories, creating
a tree structure, but cannot be contained within
more than one parent
• Ways that names of access paths can be specified:
– Complete path (fully qualified reference)
– Relative path
• Each storage device has a root directory
Systems Architecture, Fifth Edition
15
Active
(working)
directory
Systems Architecture, Fifth Edition
16
Graph Directory Structure
• More flexible than hierarchical directory structure
– Files and subdirectories can be contained within
multiple directories
– Directory links can form a cycle
Systems Architecture, Fifth Edition
17
Systems Architecture, Fifth Edition
18
Storage Allocation
• Secondary storage devices
– The data structures and procedures used to manage
secondary storage devices is similar to memory
management, except:
– Large number of storage locations; low frequency
of allocation changes
• Secondary storage devices are divided into
allocation units
Systems Architecture, Fifth Edition
19
Allocation Units
• Smallest number of secondary storage bytes that
can be allocated to a file; cannot be smaller than
unit of data transfer between storage device and
controller (block); often smallest storage size is
usually a multiple of block transfer size
• Assigned/reclaimed by FMS as files and
directories are created or expanded/shrink or are
deleted
• Size difficult to change once set
Systems Architecture, Fifth Edition
20
Allocation Unit Size
• Tradeoffs
– Efficient use of secondary storage space for files
– Size of storage allocation data structures
– Efficiency of storage allocation procedures
• Benefit of smaller units:
– More efficient use of storage space
• Benefit of larger units:
– Allow smaller storage allocation data structures
Systems Architecture, Fifth Edition
21
Storage Allocation Tables
• Data structures that record which allocation units
are free and which belong to files
• Format and content vary across FMSs
• Can contain linked lists in simpler FMSs or
indices or other complex data structures in more
complex FMSs
• Examples include bitmaps, tables, linked lists, B+
trees
Systems Architecture, Fifth Edition
22
Systems Architecture, Fifth Edition
23
Free allocation units are
assigned to a hidden system
file called SysFree.
Systems Architecture, Fifth Edition
24
All of a file allocation’s units are “chained” together
in sequential order by a series of pointers. This is
close to an example of a bitmap, such as in FAT.
Systems Architecture, Fifth Edition
25
B+ Tree (NTFS)
100
<100
>=100
30
125
155
181
etc.
3
5 10
30 38
Systems Architecture, Fifth Edition
101 109 120
128 133 140
26
Blocking
• Logical record grouping within physical records
• Described by a numeric ratio of logical records to
physical records (blocking factor)
Systems Architecture, Fifth Edition
27
Blocking
factor = 4:3
Blocking
factor = 2:3
Usually the logical number is a whole
multiple of the physical number.
Systems Architecture, Fifth Edition
28
Buffering
• Temporary storage of data as it moves between
programs and secondary storage devices
– Physical records are stored in the buffer as they are
read from secondary storage
– FMS extracts logical records from buffers and
copies them to data area of the application program
• Each buffer is the size of one allocation unit
• Improves I/O performance if enough are used
Systems Architecture, Fifth Edition
29
Systems Architecture, Fifth Edition
30
Computing Record Location
• For a record r, we must compute where it is in the
file.
– Which allocation records (physical record) do we
need?
– What is offset within that physical record?
Allocation unit offset 
Systems Architecture, Fifth Edition
(Record number - 1)  Record size
Allocation unit size
31
Example
• We want to load File3 (from Table 12-1).
Allocation units (block size) are 512 bytes; Record
size = 55 bytes
• Table 12-1 tells us that the first allocation unit is
unit 5
• System loads 512 bytes into buffer and moves first
55 bytes to application program
Systems Architecture, Fifth Edition
32
Example Continued
•
•
•
•
Now we want the second record. Where is it?
(Pointer – 1) x RecordSize / BlockSize
= (2-1) x 55 / 512 = 0 remainder 55
So second record is still in this first block but
starting at byte 55 (which is in the buffer)
• What if we want the 37th record?
• (37-1) x 55 / 512 = 3 remainder 444 (typo in book)
Systems Architecture, Fifth Edition
33
Example Continued
• So since the answer is 3 remainder 444, you need
to get the 4th block (because blocks are numbered
0, 1, 2, 3, …) and then start reading from the 444th
byte
• Using Table 12-2, the 4th block is block number
19
Systems Architecture, Fifth Edition
34
File Manipulation
• Exact set of service layer functions varies among
FMSs, but typically includes create, copy, move,
delete, read, and write
• Application programs interact directly with FMS
through OS service layer
• Users interact indirectly with FMS through
command layer
Systems Architecture, Fifth Edition
35
File Open and Close Operations
• File open
– Causes FMS to find the file, verify access
privileges, allocate buffers, and update internal
table of open files
• File close
– Causes FMS to flush buffer content to the storage
device, release buffers, update file time stamps, and
update table of open files
Systems Architecture, Fifth Edition
36
Delete and Undelete Operations
• Delete
– Does not immediately remove files; some content
remains on secondary storage unit all allocation
units have been reassigned and overwritten
– File content can be visible to intruders
• Undelete
– Can be used to reconstruct directory and storage
allocation table contents
Systems Architecture, Fifth Edition
37
Access Controls
• Granted by file owners and system administrators
for reading, writing, and executing files
• Provide security at the expense of additional FMS
overhead
Systems Architecture, Fifth Edition
38
File Migration, Backup, and
Recovery
• Provided by most FMSs to protect files against
damage or loss
Systems Architecture, Fifth Edition
39
File Migration
(Version Control)
• Automatic storage and backup of old file versions
• Balances storage cost of each file version with
anticipated user demand for that version
Systems Architecture, Fifth Edition
40
Original
Copy that has been updated
to reflect new data
Systems Architecture, Fifth Edition
41
File Backup
• Protects against data loss (file content, directory
content, and storage allocation tables)
• Store backup copies on a different storage device
in a different physical location
• Manual or automatic
• Full or incremental
Systems Architecture, Fifth Edition
42
Transaction Logging
• Automatically records all changes to file content
and attributes in a separate storage area; also
writes them to the file’s I/O buffer
• Provides high degree of protection against data
loss due to program or hardware failure
• Imposes a performance penalty; used only when
costs of data loss are high
Systems Architecture, Fifth Edition
43
File Recovery
• Automated and manual components
• Can search backup logs for copies of lost or
damaged files
• Can perform consistency checking and repair
procedures for crashed system or physically
damaged storage device
Systems Architecture, Fifth Edition
44
Disk Scheduling
• A disk drive has multiple requests for read or
write operations
• How does the disk scheduler schedule the
read/write operations?
• Various techniques include: FCFS (First Come
First Served), SSTF (Shortest Seek Time First),
Scan, and Look
Systems Architecture, Fifth Edition
45
Disk Scheduling
• Assume the following disk sector requests:
98, 183, 37, 122, 14, 124, 65, 57
FCFS
SSTF
Scan
C-Scan
Look
C-Look
Systems Architecture, Fifth Edition
Head is at 53
46
Fault Tolerance
• Methods of securing file content against hardware
failure
–
–
–
–
–
File backup
Recovery
Transaction logging
Mirroring
RAID (Redundant Array of Inexpensive Disks)
Systems Architecture, Fifth Edition
47
Mirroring
• All disk write operations are made concurrently to
two different storage devices
• Provides high degree of protection against data
loss with no performance penalty if implemented
in hardware
• Disadvantages
– Cost of redundant disk drives
– Higher cost of disk controllers that implement
mirroring
Systems Architecture, Fifth Edition
48
RAID
• Disk storage technique that improves performance
and fault tolerance
• All levels except RAID 1 use data striping
– Breaks a unit of data into smaller segments and
stores them on multiple disks
• Multiple levels can be layered to combine their
best features (e.g. RAID 10)
• Can be implemented in hardware or software
Systems Architecture, Fifth Edition
49
Storage Consolidation
• Overcomes inefficiencies of direct-attached
storage (DAS) in multiple-server environments
• Common approaches
– Storage area network (SAN) - an architecture to
attach remote computer storage devices to servers
such that the devices appear as locally connected
– Network-attached storage (NAS) – in contrast to
SAN, uses file-based protocols such as NFS where
it is clear the storage is remote
Systems Architecture, Fifth Edition
50
Storage Consolidation
Storage Area Network (SAN)
Network-Attached Storage (NAS)
• High-speed interconnection among
general-purpose servers and one or
more storage servers
• Block-oriented access
• Common in multi-server
environments with mainframes or
supercomputers (large enterprises)
and substantial overlap among
server storage needs
• Expensive to purchase and
administer, but avoid costs of
duplicate storage and storage
administration
• Dedicated to managing one or more
file systems
• Accessed by other servers and
clients over a local or wide area
network
• File-oriented access (rather than
block-oriented access)
• Common when geographically
dispersed servers need access to a
common file system
• Cheaper to acquire than SAN, but at
the price of lower performance
Systems Architecture, Fifth Edition
51
Systems Architecture, Fifth Edition
52
Systems Architecture, Fifth Edition
53
Storage Consolidation
• Most systems use SCSI protocol to connect
storage devices to servers
• To allow SAN extension over IP networks, many
use iSCSI or Fibre Channel over IP
• SANs often use a Fibre Channel fabric technology
Systems Architecture, Fifth Edition
54
Fibre Channel
• Three major Fibre Channel architectures
– Point to point
– Arbitrated loop (similar to Token Ring)
– Switched fabric (similar to Ethernet but with Fibre
Channel switches instead of LAN switches)
• Can operate over twisted pair and fiber
• Throughput speeds from 100 Mbps to 2 Gbps
Systems Architecture, Fifth Edition
55
Fibre Channel
• Five layers
–
–
–
–
–
FC0 – physical layer
FC1 – data link (8B/10B)
FC2 – network layer (core FC protocols)
FC3 – common services layer (such as RAID)
FC4 – protocol mapping layer (encapsulates SCSI)
Systems Architecture, Fifth Edition
56
Example File Systems
•
•
•
•
FAT (File Allocation Table)
FAT16
FAT32 (up through Windows Me)
NTFS (New Technology File System, beginning
with Windows NT and continuing with Windows
2000, XP, 2003, 2008, and Vista)
• UNIX file system
• HFS (Hierarchical File System) (MACs and
possible UNIX)
Systems Architecture, Fifth Edition
57
NTFS
• Supports
–
–
–
–
High-speed directory and file operations
Ability to handle large disks, files, directories
Secure file and disk content
Reliability and fault tolerance
• NTFS organizes secondary storage as a set of
volumes
• A volume is a partition on a disk
Systems Architecture, Fifth Edition
58
NTFS
• Volumes contain a collection of storage allocation
units called clusters
• Cluster size can be 512, 1024, 2048, or 4096 bytes
• Cluster size is set up during installation
• Each cluster is identified by a 64-bit logical cluster
number (LCN)
• A volume can be as large as 4096 x 264 bytes
Systems Architecture, Fifth Edition
59
NTFS
• A volume’s master directory is stored in a data
structure called the master file table (MFT)
• MFT contains a sequential set of file records, one
for each file on the volume
• All volume contents are stored as files, including
user files, the MFT itself, and other volume
management files such as the root directory,
storage allocation table, bootstrap program, and
bad cluster table
Systems Architecture, Fifth Edition
60
NTFS
• The first 16 MFT entries are reserved for the MFT
• All subsequent entries numbered 16 and higher
store records about user files
• A file is an object with a collection of attributes
such as name, restrictions, security descriptors,
and the data itself (essentially a large attribute)
• Directory contents stored using B+ tree
• See Burd pages 495-497 for further details
Systems Architecture, Fifth Edition
61
Summary
•
•
•
•
•
•
•
File management systems
Directory content and structure
Storage allocation
File manipulation
Access controls
File migration, backup, and recovery
Storage consolidation
Systems Architecture, Fifth Edition
62