Chapter 10: Mass-Storage Systems

 Overview of Mass Storage Structure

 Disk Structure

 Disk Attachment

 Disk Scheduling

 Disk Management

 Swap-Space Management

 RAID Structure

 Stable-Storage Implementation

10.1
 Overview of Mass Storage Structure

 Magnetic disks provide bulk of secondary storage of modern computers

 Transfer rate is rate at which data flow between drive and computer

 Access time has two major components

 Seek time is the time for the disk are to move the heads to the cylinder
containing the desired sector.

 Rotational latency is the additional time waiting for the disk to rotate the
desired sector to the disk head.

10.2
Moving-head Disk Mechanism

10.3
 Disk Structure

 Disk drives are addressed as large 1-dimensional arrays of logical blocks, where

the logical block is the smallest unit of transfer

 The 1-dimensional array of logical blocks is mapped into the sectors of the disk

sequentially

 Sector 0 is the first sector of the first track on the outermost cylinder

 Mapping proceeds in order through that track, then the rest of the tracks in that

cylinder, and then through the rest of the cylinders from outermost to innermost

10.7
 Disk Scheduling
 The operating system is responsible for using hardware efficiently —

for the disk drives,

 Minimize seek time

 Disk bandwidth is the total number of bytes transferred, divided by

the total time between the first request for service and the

completion of the last transfer

10.8
 Disk Scheduling (Cont.)
 I/O request includes input or output mode, disk address, memory
address, number of sectors to transfer

 OS maintains queue of requests, per disk or device

 Several algorithms exist to schedule the servicing of disk I/O requests

 We illustrate scheduling algorithms with a request queue (0-199)

98, 183, 37, 122, 14, 124, 65, 67

Head pointer 53

10.9
 FCFS
Illustration shows total head movement of 640 cylinders

10.10
 SSTF
 Shortest Seek Time First selects the request with the minimum seek
time from the current head position

 SSTF scheduling is a form of SJF scheduling; may cause starvation

of some requests

 Illustration shows total head movement of 236 cylinders

10.11
SSTF (Cont.)

10.12
 SCAN

 The disk arm starts at one end of the disk, and moves toward the other end,
servicing requests until it gets to the other end of the disk, where the head
movement is reversed and servicing continues.

 SCAN algorithm Sometimes called the elevator algorithm

 Illustration shows total head movement of 208 cylinders

10.13
SCAN (Cont.)

10.14
 C-SCAN

 The head moves from one end of the disk to the other, servicing requests as it
goes

 When it reaches the other end, however, it immediately returns to the

beginning of the disk, without servicing any requests on the return trip

10.15
C-SCAN (Cont.)

10.16
 C-LOOK
 LOOK a version of SCAN, C-LOOK a version of C-SCAN

 Arm only goes as far as the last request in each direction, then reverses direction immediately, without first
going all the way to the end of the disk

 Total number of cylinders?

10.17
C-LOOK (Cont.)

10.18
 Selecting a Disk-Scheduling Algorithm
 SSTF is common and has a natural appeal

 SCAN and C-SCAN perform better for systems that place a heavy load on the disk
 Less starvation

 Performance depends on the number and types of requests

 Requests for disk service can be influenced by the file-allocation method

 And metadata layout

 The disk-scheduling algorithm should be written as a separate module of the operating system, allowing it
to be replaced with a different algorithm if necessary

 Either SSTF or LOOK is a reasonable choice for the default algorithm

 What about rotational latency?

 Difficult for OS to calculate

 How does disk-based queueing effect OS queue ordering efforts?

10.19
 Disk Management
 Low-level formatting, or physical formatting — Dividing a disk into sectors that the disk controller can read and
write
 Each sector can hold header information, plus data, plus error correction code (ECC)
 Usually 512 bytes of data but can be selectable
 To use a disk to hold files, the operating system still needs to record its own data structures on the disk
 Partition the disk into one or more groups of cylinders, each treated as a logical disk
 Logical formatting or “making a file system”
 To increase efficiency most file systems group blocks into clusters
 Disk I/O done in blocks
 File I/O done in clusters
 Raw disk access for apps that want to do their own block management, keep OS out of the way (databases for
example)
 Boot block initializes system
 The bootstrap is stored in ROM
 Bootstrap loader program stored in boot blocks of boot partition
 Methods such as sector sparing used to handle bad blocks

10.20
Booting from a Disk in Windows

10.21
 Swap-Space Management
 Swap-space — Virtual memory uses disk space as an extension of main memory
 Less common now due to memory capacity increases

 Swap-space location:
 can be carved out of the normal file system
 or it can be in a separate disk partition (raw)
 Swap-space management
 4.3BSD allocates swap space when process starts; holds text segment (the program) and data
segment
 Kernel uses swap maps to track swap-space use
 Solaris 2 allocates swap space only when a dirty page is forced out of physical memory, not when
the virtual memory page is first created
 File data written to swap space until write to file system requested
 Other dirty pages go to swap space due to no other home
 Text segment pages thrown out and reread from the file system as needed

 What if a system runs out of swap space?

 Some systems allow multiple swap spaces

10.22
Data Structures for Swapping on
Linux Systems

10.23
File-System Interface
 File-System Interface

 File Concept

 Access Methods

 Directory Structure

 File-System Mounting

 File Sharing

 Protection

10.25
 File Concept
 Contiguous logical address space

 Types:

 Data

 numeric

 character

 binary

 Program

10.26
 File Attributes
 Name – only information kept in human-readable form
 Identifier – unique tag (number) identifies file within file system
 Type – needed for systems that support different types
 Location – pointer to file location on device
 Size – current file size
 Protection – controls who can do reading, writing, executing
 Time, date, and user identification – data for protection, security,
and usage monitoring

 Information about files are kept in the directory structure,

which is maintained on the disk

10.27
 File Operations
 File is an abstract data type
 Create
 Write
 Read
 Reposition within file
 Delete
 Truncate

 Open(Fi) – search the directory structure on disk for entry Fi, and move the content of entry to memory

 Close (Fi) – move the content of entry Fi in memory to directory structure on disk

10.28
File Types – Name, Extension

10.29
 Access Methods
 Sequential Access
 read next-reads the next portion of the file and automatically

advances a file pointer

 write next – appends to the end of the file and advances to the

end of the newly written material (the new end of file).

 reset- file can be reset to the beginning, and on some systems, a

program may be able to skip forward or backward n records

10.30
Sequential-access File

10.31
 Access Methods
Direct Access

read n

write n

position to n

read next

write next

rewrite n

n = relative block number

10.32
Simulation of Sequential Access on a Direct-access File

10.33
Example of Index and Relative Files

10.34
A Typical File-system Organization-
Directory Structure

Both the directory structure and the files reside on disk

10.35
Operations Performed on Directory
 Search for a file
 Create a file
 Delete a file
 List a directory
 Rename a file
 Traverse the file system

10.36
Organize the Directory (Logically) to Obtain

 Efficiency – locating a file quickly

 Naming – convenient to users

 Two users can have same name for different files

 The same file can have several different names

 Grouping – logical grouping of files by properties, (e.g., all Java programs, all games,
…)

10.37
 Single-Level Directory

 A single directory for all users

Naming problem

Grouping problem

10.38
 Two-Level Directory
 Separate directory for each user

 Path name
 Can have the same file name for different user
 Efficient searching
 No grouping capability
 Cannot create sub directories

10.39
Tree-Structured Directories

10.40
 Directory Organization

Both the directory structure and the files reside on disk

10.41
Operations Performed on Directory
 Search for a file
 Create a file
 Delete a file
 List a directory
 Rename a file
 Traverse the file system

10.42
Organize the Directory (Logically) to Obtain

 Efficiency – locating a file quickly

 Naming – convenient to users

 Two users can have same name for different files

 The same file can have several different names

 Grouping – logical grouping of files by properties, (e.g., all Java programs, all games,
…)

10.43
 Single-Level Directory

 A single directory for all users

Naming problem

Grouping problem

10.44
 Two-Level Directory
 Separate directory for each user

 Path name
 Can have the same file name for different user
 Efficient searching
 No grouping capability
 Cannot create sub directories

10.45
Tree-Structured Directories

10.46
 File System Mounting
 A file system must be mounted before it can be accessed

 A unmounted file system is mounted at a mount point

10.47
Mount Point

10.48
 File Sharing
 Sharing of files on multi-user systems is desirable

 Sharing may be done through a protection scheme

 On distributed systems, files may be shared across a network

 Network File System (NFS) is a common distributed file-sharing method

10.49
 File Sharing – Multiple Users
 User IDs identify users, allowing permissions and protections to be per-user

 Group IDs allow users to be in groups, permitting group access rights

10.50
 File Sharing
 Uses networking to allow file system access between systems
 FTP
 distributed file systems
 world wide web
 Client-server model allows clients to mount remote file systems from servers
 Server can serve multiple clients
 Client and user-on-client identification is insecure or complicated

10.51
 File Sharing
 NFS is standard UNIX client-server file sharing protocol
 CIFS is standard Windows protocol-The Common Internet File System (CIFS)

 Distributed Information Systems (distributed naming services) such as LDAP, DNS, NIS, Active Directory
implement unified access to information needed for remote computing

 Lightweight Directory Access Protocol(LDAP)

 Domain Name System(DNS)
 Network Information Service(NIS)

10.52
 Protection
 File owner/creator should be able to control:
 what can be done
 by whom
 Types of access
 Read
 Write
 Execute
 Append
 Delete
 List

10.53
 Access Lists and Groups
 Mode of access: read, write, execute
 Three classes of users
RWX
a) owner access 7  111
RWX
b) group access 6  110
RWX
c) public access 1  001
 Ask manager to create a group (unique name), say G, and add
some users to the group.
 For a particular file (say game) or subdirectory, define an
appropriate access.
owner group public

chmod 761 game

10.54
 File-System Structure
 File structure

 Logical storage unit

 Collection of related information

 File system resides on secondary storage (disks)

 File system organized into layers

 File control block – storage structure consisting of information about a file

10.57
Layered File System

10.58
 File System Layers
(Cont.)
 Logical file system manages metadata information

 Translates file name into file number, file handle, location by

maintaining file control blocks (inodes in UNIX)

 Directory management

 Protection

 File organization module understands files, logical address,

and physical blocks

 Translates logical block # to physical block #

 Manages free space, disk allocation

12.
10.59
 File System
Layers
 Basic file system given command like “retrieve block 123” translates to

device driver
 Also manages memory buffers and caches (allocation, freeing, replacement)

 Buffers hold data in transit

 Caches hold frequently used data

 Device drivers manage I/O devices at the I/O control layer

 Given commands like “read drive1, cylinder 72, track 2, sector 10, into
memory location 1060” outputs low-level hardware specific commands to
hardware controller

12.
10.60
A Typical File Control Block

10.61
 Directory
Implementation
 Linear list of file names with pointer to the data blocks

 Simple to program

 Time-consuming to execute

 Linear search time

 Could keep ordered alphabetically via linked list or use B+ tree

 Hash Table – linear list with hash data structure

 Decreases directory search time

 Collisions – situations where two file names hash to the same

location

 Only good if entries are fixed size, or use chained-overflow method

12.
10.62
 Allocation Methods
 An allocation method refers to how disk blocks are allocated for files:

 Contiguous allocation

 Linked allocation

 Indexed allocation

10.63
 Contiguous Allocation
 Each file occupies a set of contiguous blocks on the disk

 Simple – only starting location (block #) and length (number of blocks) are required

 Random access

 Wasteful of space (dynamic storage-allocation problem)

 Files cannot grow

10.64
Contiguous Allocation of Disk Space

10.65
 Extent-Based Systems
 Many newer file systems (I.e. Veritas File System) use a modified contiguous allocation
scheme

 Extent-based file systems allocate disk blocks in extents

 An extent is a contiguous block of disks

 Extents are allocated for file allocation
 A file consists of one or more extents.

10.66
 Linked Allocation
 Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.

block = pointer

10.67
 Allocation Methods -
Linked
 Linked allocation – each file a linked list of blocks
 File ends at nil pointer
 No external fragmentation
 Each block contains pointer to next block
 No compaction, external fragmentation
 Freespace management system called when new block
needed
 Improve efficiency by clustering blocks into groups but
increases internal fragmentation
 Reliability can be a problem
 Locating a block can take many I/Os and disk seeks

12.
10.68
Linked Allocation

10.69
File-Allocation Table

10.70
 Indexed Allocation
 Brings all pointers together into the index block.
 Logical view.

index table

10.71
Example of Indexed Allocation

10.72
 Free-Space Management
 Bit vector (n blocks)

0 1 2 n-1
…

1  block[i] free
bit[i] =
0  block[i] occupied

10.73
Free-Space Management (Cont.)
 Linked list (free list)
 Cannot get contiguous space easily
 No waste of space

 Grouping
N-1 =FREE BLOCKS, last nth block contain address of
another n free blocks

 Counting
 address of the first free block and the number n of free
contiguous block that follow th first block

10.74
 File Sharing
 Sharing of files on multi-user systems is desirable

 Sharing may be done through a protection scheme

 On distributed systems, files may be shared across a network

 Network File System (NFS) is a common distributed file-sharing method

10.75
 File Sharing – Multiple Users
 User IDs identify users, allowing permissions and protections to be per-user

 Group IDs allow users to be in groups, permitting group access rights

10.76
File Sharing – Remote File Systems
 Uses networking to allow file system access between systems
 Manually via programs like FTP
 Automatically, seamlessly using distributed file systems
 Semi automatically via the world wide web

 Client-server model allows clients to mount remote file systems

from servers
 Server can serve multiple clients
 Client and user-on-client identification is insecure or
complicated
 NFS is standard UNIX client-server file sharing protocol

 Distributed Information Systems (distributed naming services)

such as LDAP, DNS, NIS, Active Directory implement unified
access to information needed for remote computing

10.77
 Protection
 File owner/creator should be able to control:
 what can be done
 by whom
 Types of access
 Read
 Write
 Execute
 Append
 Delete
 List

10.78
 Access Lists and Groups
 Mode of access: read, write, execute
 Three classes of users
RWX
a) owner access 7  111
RWX
b) group access 6  110
RWX
c) public access 1  001
 Ask manager to create a group (unique name), say G, and add
some users to the group.
 For a particular file (say game) or subdirectory, define an
appropriate access.
owner group public

chmod 761 game

Attach a group to a file
chgrp G game

10.79
I/O Hardware

10.80
10.81
Application I/O interface

10.82