This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
Blocks of a file could be represented using linked lists. All that needs to be held is the address of the first block that the file occupies. Each block of the file contains not only data but also a pointer to the next block. The diagram below shows such an implementation for two files.
|
The advantages of this method include
· Every block can be used, unlike a scheme that insists that every file is contiguous.
· No space is lost due to external fragmentation (although there is internal fragmentation within the file, which can lead to performance issues).
· The directory entry only has to store the first block. The rest of the file can be found from there.
· The size of the file does not have to be known beforehand (unlike a contiguous file allocation scheme).
· When more space is required for a file any block can be allocated (e.g. the first block on the free block list).
The disadvantages of this method include
· Random access is very slow (as it needs many disc reads to access a random point in the file). In fact, the implementation described above is really only useful for sequential access.
· Space is lost within each block due to the pointer. This does not allow the number of bytes to be a power of two. This is not fatal, but does have an impact on performance.
· Reliability could be a problem. It only needs one corrupt block pointer and the whole system might become corrupted (e.g. writing over a block that belongs to another file).
We can eliminate the problem of wasting space by having to store a pointer and the problem of not having random access by taking the pointer from each block and storing them in an index or table and placing this in memory. Below is a diagram showing how the files (A and B) would be represented using a linked list allocation with an index.
 |
If we consider file B, it occupies blocks 11, 2, 14 and 8, but as the pointers are in memory random access is much faster as a given offset can be located by using only memory accesses until the correct block has been reached.
The main disadvantage is that the entire table must be in memory all the time. For a large disc with, say, 500,000 1K blocks (500MB) the table will have 500,00 entries.
| Last Page | Back to Main Index | Next Page |
Last Updated : 23/01/2002