Page 391 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes the third logical block in 22, and so on. One way to achieve these runs is to allocate disk storage
several blocks at a time, if possible.
The blocks in a file are described by a sequence of records, each one describing a sequence of
logically contiguous blocks. For a file with no holes in it, there will be only one such record.
Files that are written in order from beginning to end all belong to this category. For a file with
one hole in it (e.g., only blocks 0–49 and blocks 60–79 are defined), there will be two records.
Such a file could be produced by writing the first 50 blocks, then seeking forward to logical
block 60 and writing another 20 blocks. When a hole is read back, all the missing bytes are zeros.
Each record begins with a header giving the offset of the first block within the file. Next comes
the offset of the first block not covered by the record. In the example above, the first record would
have a header of (0, 50) and would provide the disk addresses for these 50 blocks. The second
one would have a header of (60, 80) and would provide the disk addresses for these 20 blocks.
Each record header is followed by one or more pairs, each giving a disk address and run length. The
disk address is the offset of the disk block from the start of its partition; the run length is the number
of blocks in the run. As many pairs as needed can be in the run record. Use of this scheme for a
three-run, nine-block file is illustrated in Figure. 13.7.

Figure 13.7: An MFT Record for a Three-run, Nine-block File

In this figure we have an MFT record for a short file (short here means that all the information
about the file blocks fits in one MFT record). It consists of the three runs of consecutive blocks
on the disk. The first run is blocks 20-23, the second is blocks 64-65, and the third is blocks 80-
82. Each of these runs is recorded in the MFT record as a (disk address, block count) pair. How
many runs are there depends on how good a job the disk block allocator did in finding runs
of consecutive blocks when the file was created. For a n-block file, the number of runs can be
anything from 1 up to and including n.

Several comments are worth making here. First, there is no upper limit to the size of files that
can be represented this way. In the absence of address compression, each pair requires two
64-bit numbers in the pair for a total of 16 bytes. However, a pair could represent 1 million or
more consecutive disk blocks. In fact, a 20 MB file consisting of 20 separate runs of 1 million
1 KB blocks each fits easily in one MFT record, whereas a 60 KB file scattered into 60 isolated
blocks does not.

Second, while the straightforward way of representing each pair takes 2 × 8 bytes, a compression
method is available to reduce the size of the pairs below 16. Many disk addresses have multiple

384 LOVELY PROFESSIONAL UNIVERSITY