Allocation Methods
An allocation method refers to how disk blocks are
allocated for files:
Contiguous allocation
Linked allocation
Indexed allocation
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
Contiguous Allocation
(block size = 512)
Mapping from logical to physical
LA/512
LA: disk data address as offset in block numbers.
Block to be accessed = Q + starting address
Displacement into block = R
Contiguous Allocation of Disk Space
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
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
Free space 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
FAT (File Allocation Table) variation
Beginning of volume has table, indexed by block number
Much like a linked list, but faster on disk and cacheable
New block allocation simple
Linked Allocation
Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk
pointer
block =
Linked Allocation (Cont.)
Simple – need only starting address
Free-space management system – no
waste of space
pointer
No random access block =
Mapping Q
LA/511
Block to be accessed is the Qth block
in the linked chain of blocks
representing the file.
Displacement into block = R + 1
File-allocation table (FAT) – disk-space
allocation used by MS-DOS and OS/2.
Linked Allocation
File-Allocation Table
Allocation Methods - Indexed
Indexed allocation
Each file has its own index block(s) of pointers to its data blocks
Logical view
index table
Example of Indexed Allocation
Indexed Allocation (Cont.)
Need index table
Random access
Dynamic access without external fragmentation, but have overhead of index block
Mapping from logical to physical in a file of maximum size of 256K bytes and block size
of 512 bytes. We need only 1 block for index table
Q
LA/512
R
Q = displacement into index
table R = displacement into
block
Indexed Allocation – Mapping (Cont.)
Mapping from logical to physical in a file of unbounded length (block size of 512 words)
Linked scheme – Link blocks of index table (no limit on size)
Q1
LA / (512 x 511)
R1
Q1 = block of index
table
R1 is used as follows:
Q2
R1 / 512
R2
Q2 = displacement into block of index table
R2 displacement into block of file:
Indexed Allocation – Mapping (Cont.)
Two-level index (4K blocks could store 1,024 four-byte pointers in outer index -> 1,048,567 data
blocks and file size of up to 4GB)
Q1
LA / (512 x 512)
R1
Q1 = displacement into outer-
index
R1 is used as follows:
Q2
R1 / 512
R2
Q2 = displacement into block of index table
R2 displacement into block of file:
Indexed Allocation – Mapping (Cont.)
outer-index
index table file
starting block number of the index of index table.
Combined Scheme: UNIX UFS
(4K bytes per block, 32-bit addresses)
Note: More index
blocks than can
be addressed
with 32-bit file
pointer
Performance
Best method depends on file access type
Contiguous great for sequential and random
Linked good for sequential, not random
Declare access type at creation -> select either contiguous or linked
Indexed more complex
Single block access could require 2 index block reads then data block read
Clustering can help improve throughput, reduce CPU overhead
Performance (Cont.)
Adding instructions to the execution path to save one disk I/O is
reasonable
Intel Core i7 Extreme Edition 990x (2011) at 3.46Ghz = 159,000 MIPS
[Link]
Typical disk drive at 250 I/Os per second
159,000 MIPS / 250 = 630 million instructions during one disk I/O
Fast SSD drives provide 60,000 IOPS
159,000 MIPS / 60,000 = 2.65 millions instructions during one disk I/O