Transcript Memory Management

FILE SYSTEM
CONSISTENCY AND
EFFICIENCY
CHAPTER 4-3
FILE-SYSTEM CONSISTENCY
• Issue
1. O/S reads blocks
2. Modifies them in RAM
3. Writes them out later
• If a crash happens between 2 and 3
• File system could be inconsistent
• All blocks are not equal. Especially critical are:
• i-node block, directory blocks, blocks containing free list
CHECKING FOR BLOCK
INCONSISTENCY
• fsck in UNIX
• Build two tables
• Each contains counter for each block, initially set to 0
• Table 1 counts times each block is present in a file
• Table 2 counts times each block is present in free list
RECALL DISK STRUCTURE
• ss
RECALL FREE SPACE MANAGEMENT
RECALL SIMPLIFIED I-NODE
RECALL DIRECTORY STRUCTURE
I-Node Number
Link Count (avail. from
i-node)
File Name
2803054
32
.
242146
5
..
180334
3
apache2
131171
10
X11
180334
1
zerox
...
...
TABLE 1
PRESENCE OF A BLOCK IN A FILE
• Read i-nodes
• Starting from an i-node, trace out all blocks in
corresponding file, incrementing corresponding
block counter.
block numbers
times in use
0
1
2
3
4
5
6
7
8
9
1
1
1
1
0
0
0
1
2
1
...
TABLE 2
PRESENCE OF FREE BLOCK
• Examine free list or bit map
• Increment counter in Table 2 if block occurs in free
list or bit map
block numbers
times on free list
POSSIBILITIES
a)
b)
c)
d)
Consistent:
Missing data block: Block 2 occurs in neither table. Add missing block to free list.
Duplicate block in free list: Block 4 occurs twice in free list. Rebuild free list.
Duplicate data block: Block 5 is present in two files. Copy Block 5 to newly allocated
free block. Make i-node of one of the files point to the new block.
CHECKING FOR LINK INCONSISTENCY
(1)
• Link counts in i-nodes start at 1 when a file is
created and incremented for each hard link
• Because of hard-links, files may appear in multiple
directories
• Make Table: {i-node:num_dir_containing file}
• Recursively descend the directory tree
• For every i-node in every directory,
• Traverse i-nodes comparing counters in table with
link counts in i-nodes
CHECKING FOR LINK INCONSISTENCY
(2)
Two types of errors:
1. Link count in i-node exceeds the number of directory
entries for that i-node
• Even if all files are removed from the directory, count will
exceed 0 and i-node will not be removed
• Wastes space allocated for files not in use
• Fix: reset link count in i-node to correct value
2. Directory entries for i-node exceed link count in i-node
•
•
•
•
link count will go to zero before directory is empty.
when in-node link count == 0, file system releases its blocks
Now directory points to an unused in-node
Fix: reset link count in i-node to correct value
FILE SYSTEM PERFORMANCE
• Disk
• Transfer rate per 32 bit word is only ~ ¼ as fast as RAM
• But factor in track seek time and sector rotational delay
• 6 orders of magnitude slower than RAM for a single word
• Rule of Thumb for a single Word
• Ram operates in the nanosecond range
• Disk operates in the millisecond range
BLOCK CACHE
• Hash device and disk address
• Table points to linked list of disk blocks kept in RAM
• Use modified LRU to evict blocks
• Is block likely to be used again?
• Is block essential to consistency of file system (i-node, directory, etc.)
1. Bring in new block: evict head if necessary, place at rear
2. Ref block in cache: remove from current position, place at rear
REDUCE DISK ARM MOTION (1)
• Place consecutive blocks close to on another on
disk
• Bit Map of Free Blocks
• Blocks in proximity can be chosen because bit map is in RAM
ordered by block number
• Linked List of Free Blocks
• Part of the list itself is on disk
• Attempt to place consecutive blocks in a file on the same
cylinder
REDUCE DISK ARM MOTION (2)
• File access requires i-node access, then block access
• I-nodes are usually at the front (recall disk structure)
• Average distance between i-node and its block is half the number of
tracks/cylinders
• Two fixes
• place i-nodes in the middle
• Group i-nodes, blocks, free-list together
DEFRAGMENTATION
• Initially
• programs, files required by o/s are consecutive
• free space is consecutive
• Over time
• Files are created, modified, removed
• Disk becomes fragmented
• Solution
• reorder files and free space to make them as contiguous as
possible
SOLID STATE DISKS
• Everything changes with ssd
• No disk arm to optimize
• Random access is as fast as sequential access
• But All Technology Bites Back
• Each block can be written only a limited number of times
• Now algorithms must spread wear evenly across the device
ONE MIGHT THINK
• Research into file systems is finished
• Given the antiquity of the i-nodes
• Given my enthusiasm for the scalable nature of Unix
• Not So, especially given the current importance of
data
• Backups, versioning, security, cloud systems are all areas of
research