The two measures of helpfulness are speed of compaction and simplicity of implementation, with speed being the more important of the two.
The most helpful is the index linked list method, because of the simplicity of manipulating the linked list in primary storage and the minimal number of disk blocks that need to be accessed.
Second most helpful is the index node method, which requires that the compaction algorithm read the index-nodes from the disk, causing more disk I-O than does the index linked list method. In addition, changing the index nodes to reflect the new disk block assignments is moderately more complicated than it is for the index linked list method.
Third most helpful, or least helpful, is the linked list method, which requires the compaction algorithm access every block in the file system, independently of whether or not the block is actually relocated. Writing the new block information is moderately more complex that it is for index nodes, because it is essentially equivalent to relocating a linked list. Alternatively, you could argue that writing the new block information is simpler in the linked list method because it is a pure linked list, while the index node method is a mixture of linked lists and arrays.
Yes, it is. A write-though cache solves the problem updating the disk with writes in a timely fashion, but it doesn't address the issue of what blocks should be dropped when the buffer cache is full. The LRU strategy is a good approximation to an optimal block replacement strategy, but it doesn't provide timely write updates to disk. When combined, the strengths of each technique compliment the weaknesses of the other.
/usr/bin/xterm. Assume the file exits and there are no links.
Starting at the known location of the directory root (/), look up the
i-node number associated with the file usr. The i-node associated with
usr indicates, among other things, that it's a directory, and the location
of its first disk block. The usr directory contains the i-node number
associated with the file /usr/bin, and the i-node itself indicates that
it's a directory and the location of its first disk block. The /usr/bin
directory indicates the i-node number for /usr/bin/xterm, and the
associated i-node indicates that it's an executable file, and the location of
its first disk block.
The i-nodes themselves are stored in tables spread through-out the file system, although it's most likely that the i-nodes for heavily used directories are cached in primary memory.
The principle advantage would be simpler disk-block cache management and a smaller cache. Cache management is simpler because access to disk block i pretty much guarantees that disk block i + 1 will be accessed next, making pre-fetch an effective technique for getting good performance. Because pre-fetch works so well, the cache size can be reduced without effecting the hit rate.
The principle disadvantage is the performance that results from doing random
access. There are two main performance hits. First, a process doing random
would need to call a seek()-like routine before each file access, which
doubles the number of system calls per read. In addition, the cache hit
rate goes down because sequential pre-fetch is no longer effective, and
the cache is too small to provide an acceptable hit rate. Increasing the
cache size improves the hit rate, but does nothing about the other forms of
overhead (the extra system call and ineffectual pre-fetching).
Because the penalty for assuming random and getting sequential is much less than the penalty for assuming sequential and getting random, most operating systems assume random.
This page last modified on 3 April 2000.