Organization of the file system
The structure of the file system on the disk. Before we consider the structure
of the data file system on the disk should consider allocating disk space
algorithms and ways to address free of occupation and of memory. Methods for
allocating disk space The key question implement way of linking files from the
disk blocks. In OS used multiple methods of file disk space. For each method of
the containment units file data can be drawn from the entries in the directory,
a symbolic name of the corresponding file. Allocation of continuous sequence of
blocks The easiest way is to store each file as a continuous sequence of disk
blocks. With continuous location of the file is the address and length (in the
blocks). File, starting with a block b, then took Blocks b +1, b +2, ... b + n-1.
The scheme has two advantages. First, it is easy to realize, as the whereabouts
of the file is a matter, which is the first unit. Second, it provides a good
performance, because an entire file can be viewed in one disk operation.
Continuing the allocation is used in IBM OS / CMS, in the OS RSX-11 (for binary
file), and a number of others. The main problem, making this option available,
little difficult to find a place for the new file. In operating the disc is a
combination of free and some employees fragments. The problem of continuous
location can be considered as a special case of a more general problem of
allocating n blocks from the list of free holes. The most common strategy to
solve this problem is first fit, best fit, and worst fit (cf. with the problem
of allocating memory). Thus, the method suffers from external fragmentation,
depending on the size of disk, and the average size of the file, to a greater or
lesser extent. Furthermore, the continuous distribution of the external memory
is not applicable until not known to the maximum file size. Sometimes the size
of the output file is easy to evaluate (to copy). More often, however, this is
difficult to do. If space is not enough, the custom program can be paused,
assuming the allocation of additional seats for the file in a subsequent restart.
Some OS using a modified version of the continuous provision of basic blocks +
file backup units. But with the allocation of blocks from the Reserve raises the
same problem as a challenge in the provision of the continuum drive now blocks
from the body of reserve units. Binding list Method of distribution units in the
form of a coherent list solves the fundamental problem of continuous allocation,
ie eliminates external fragmentation. Each file-coherent list of disk blocks.
Writing in the directory contains a reference to the first and last blocks of
the file. Each block contains a pointer on the next block.