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)
As well as tracking which blocks are associated with each file we also need
to have some way of tracking the free blocks so that we can allocate them as
necessary.
Two methods are in common use.
Using this method some of the free blocks (which will no longer be free!) are given over to holding disc block numbers that are free. The blocks that contain the free block numbers are linked together so we end up with a linked list of free blocks.
We can calculate the maximum number of blocks we need to hold a complete free
list (i.e. an empty disc) using the following reasoning.
· Assume that we need a 16-bit number to store a block number (that is block numbers can be in the range 0 to 65535).
· Assume that we are using a 1K block size.
· A block can hold 512 block addresses. That is, 1024*8 [number of bits in a byte] / 16 [bits needed for a block address]
· Assume that one of the addresses is used as a pointer to the next block.
· For a 20Mb disc we need, at most, 41 blocks to hold all the free block numbers. That is, 20*1024 [maximum number of blocks] / 511 [number of disc addresses in a block].
We can generalise this and say
Maximum Number of Blocks =
ROUNDUP((SizeOfDisc * K) / ( ( (K * BitsPerByte) / BitsForDiscAddress) -1) )
Where
SizeOfDisc : Size of the disc in MB (20 in the above example)
K : 1024 (i.e. 1K)
BitsPerByte : 8 (usual number of bits in a byte)
BitsForDiscAddress : Bits required to hold disc block number (16 in the above example)
(Note : this formula could be simplified , but it is presented as it is so it can be read in conjunction with the notes).
And ROUNDUP is a function that rounds up to the nearest integer
Using this scheme a bit map is used to keep track of the free blocks. That
is, there is a bit for each block on the disc. If the bit is 1 then the block
is free. If the bit is zero, the block is in use (of course, these conventions
can be reversed).
To put it another way, a disc with n blocks requires a bit map with n entries.
If we consider a 20Mb disc with 1K blocks then we can calculate the number
of blocks needed to hold the disc map.
· A 20Mb disc has 20480 (20 * 1024) blocks.
· We need 20480 bits for the map, or 2560 (20480 / 8) bytes.
· A block can store 1024 bytes so we need 2.5 blocks (2560 / 1024) blocks to hold a complete bit map of the disc. This would obviously be rounded up to 3.
We can generalise this to
Maximum Number of Blocks =
ROUNDUP ((SizeOfDisc * K) / BitsPerByte / K)
Where the variables have the same meaning as above.
(Note : this formula could be simplified , but it is presented as it is so it
can be read in conjunction with the notes).
Generally, the bit map scheme requires a lesser number of blocks than the linked
list scheme. This is hardly surprising as the bit map scheme only uses one bit
per block, whereas the linked list scheme uses sixteen bits per block.
Only when the disc is nearly full does the linked list version need fewer blocks. This is due to the fact that the bit map scheme requires a constant number of blocks but the number of blocks required by the linked list scheme decreases as the disc gets fuller.
If you have the inclination, the above discussions have been implemented on a spreadsheet (which is available via the web site for this course). This allows you to compare the two methods we have discussed and also allows you to adjust the parameters to see the effect it has.
The only advantage that a linked list scheme has over a bit map scheme is when
only a small amount of memory can be given over to keeping track of free blocks.
Assume, the operating system can only allow one (free list) block to be held
in memory and that the disc is nearly full.
Using a bit map scheme, there is a good chance that the block held in memory will indicate that every block is being used. This means a disc access must be done in order to get the next part of the bit map. With a linked list scheme, once a block containing pointers of free blocks has been brought into memory then we will be able to allocate 511 blocks before doing another disc access.
| Last Page | Back to Main Index | Next Page |
Last Updated : 23/01/2002