Transcript Free-Space Management

11.5 Free-Space Management
 Bit vector (n blocks)
0 1
2
n-1
bit[i] =

…
1  block[i] free
0  block[i] occupied
The first non-0 word (one word may be 8, 16, or 32 bits) is scanned
to find the first 1 bit, which is the location of the first free block.
Its block number calculation is:
(number of bits per word) *(number of 0-value words) +offset of first 1 bit
Operating System Principles
11.1
Silberschatz, Galvin and Gagne ©2005
Free-Space Management
 Bit map requires extra space

Example:
block size = 29 bytes = 512 bytes
disk size = 230 bytes (1 gigabyte)
n = 230/29 =221 bits (or 218 bytes = 28 K bytes = 256K bytes)

Example:
block size = 1024 bytes = 210 bytes
disk size = 40 GB =10 * 232 bytes
n =10*232 / 210 = 10* 222 bits
(or 10*219 bytes = 5*2*219 bytes = 5 * 220 bytes = 5M bytes)
 Clustering the blocks in groups of four reduces this number to 64KB
 Easy to get contiguous files
Operating System Principles
11.2
Silberschatz, Galvin and Gagne ©2005
Free-Space Management
 Linked list (free list)

Linking together all the free disk
blocks, keeping a pointer to the
first free block in a special
location on the disk and cache it
in memory. The first block
contains a pointer to the next
free disk block, and so on.

Cannot get contiguous space
easily

No waste of space
Operating System Principles
11.3
Silberschatz, Galvin and Gagne ©2005
Free-Space Management
 Grouping

A modification of the linked free-list

Stores the address of n free blocks in the first free block.



The first n-1 of these blocks are actually free

The last block contains the address of another n free blocks, and so
on.
The addresses of a large number of free blocks can be found quickly now.
Counting

A modification of the linked free-list

Keeps the address of the first free block and the number n of free
contiguous blocks that follow the first block. Each entry in the free space
list then consists of a disk address and a count.

Useful when space is allocated with the contiguous-allocation
algorithm or through clustering
Operating System Principles
11.4
Silberschatz, Galvin and Gagne ©2005
Free-Space Management (extra material)
 Need to protect:

Pointer to free list

Bit map
 Must be kept on disk
 Copy in memory and disk may differ
 Cannot allow for block[i] to have a situation where bit[i] = 1 in
memory and bit[i] = 0 on disk

Solution:
 Set bit[i] = 1 in disk
 Allocate block[i]
 Set bit[i] = 1 in memory
Operating System Principles
11.5
Silberschatz, Galvin and Gagne ©2005
11.6 Efficiency and Performance
 Efficiency dependent on:

disk allocation and directory algorithms

types of data kept in file’s directory entry
 In UNIX, the file system’s performance is improved by pre-allocating the
inodes and spreading them across the volume, and by keeping a file’s
data blocks near that file’s inode block to reduce seek time.

BSD UNIX varies the cluster size as a file grows to reduce internal
fragmentation.
 Consideration of kept data in a file’s directory entry

Last write date, last access date
 Size of pointers in the allocation list will limit the length of a file

Need to plan for changing technology (FAT from 12 to16 to 32)
 Early Solaris needs to reboot the system to change system table sizes
Operating System Principles
11.6
Silberschatz, Galvin and Gagne ©2005
Efficiency and Performance
 Performance

Most disk controllers include local memory to form on-board
cache that is large enough to store entire tracks at a time

Buffer cache – separate section of main memory for blocks that
will be used shortly

A page cache caches pages rather than disk blocks using
virtual memory techniques

free-behind and read-ahead – techniques to optimize
sequential access


Free-behind removes a page from the buffer as soon as the
next page is requested

With read-ahead, a requested page and several
subsequent pages are read and cached
improve PC performance by dedicating section of memory as
virtual disk, or RAM disk
Operating System Principles
11.7
Silberschatz, Galvin and Gagne ©2005
Page Cache
 Memory-mapped I/O uses a page cache
 Routine I/O through the file system uses the buffer (disk) cache
 unified virtual memory: Many OS’s use page caching to cache both
process pages and file data
 This leads to the following figure
Operating System Principles
11.8
Silberschatz, Galvin and Gagne ©2005
A unified buffer cache uses the same page
cache to cache both memory-mapped
pages and ordinary file system I/O
double
caching
I/O Without a Unified Buffer Cache
Operating System Principles
11.9
I/O using a Unified Buffer Cache
Silberschatz, Galvin and Gagne ©2005
Issues
 Whether writes to the file system occur synchronously or
asynchronously
 Synchronous writes: the calling routine must wait for the data to
reach the disk drive before it can proceed
 Asynchronous writes: done the majority of the time. Data are stored
in the cache, and control return to the caller. Metadata writes can
be synchronous.
 Interactions among the page cache, the file system, and the disk drivers
 When data are written to a disk file, the pages are buffered in the
cache, and the disk driver sorts its output queue according to disk
address, to minimize disk-head seeks and to write data at times
optimized for disk rotation
 Thus, output to the disk through the file system is often faster than
input for large transfers
Skip: last paragraph of p. 417
Operating System Principles
11.10
Silberschatz, Galvin and Gagne ©2005
10.7 Recovery
 Consistency checking – compares data in directory structure with data
blocks on disk, and tries to fix inconsistencies

fsck in UNIX, chkdsk in MS-DOS

A special program is run at reboot time to check for and correct disk
inconsistencies

The allocation and free-space management algorithms dictate what
type of problems the checker can find and how successful it will fix
them
 Use system programs to back up data from disk to another storage
device (floppy disk, magnetic tape, other magnetic disk, optical)

Full back and incremental backup

Full back and each day back up all files that have changed since the
full backup

Full back may have to saved forever
 Recover lost file or disk by restoring data from backup
Operating System Principles
11.11
Silberschatz, Galvin and Gagne ©2005
10.8 Log Structured File Systems
 Log-based transaction-oriented (or journaling) file systems
record each update to the file system as a transaction
 To avoid irreparable inconsistency, all metadata changes are
written sequentially to a log. Each set of operations for performing
a specific task is a transaction.

A transaction is considered committed once it is written to the
log, and the system call can return to the user process

However, the file system may not yet be updated. These log
entries are replayed across the actual file system structures.
Operating System Principles
11.12
Silberschatz, Galvin and Gagne ©2005
Log Structured File Systems
 The transactions in the log are asynchronously written to the
file system

When the file system is modified, the transaction is
removed from the log file, which is actually a circular
buffer
 If the file system crashes, all remaining transactions in the log
must still be performed

When a transaction was aborted, not committed before the
system crashed, any changes from such a transaction to the file
system must be undone.
 The costly synchronous random metadata writes are turned into much
less costly synchronous sequential writes to the logging area. They
are replayed asynchronously via random writes to the appropriate
structures. So, file creation and deletion are performed much faster.
Operating System Principles
11.13
Silberschatz, Galvin and Gagne ©2005