2.3.6 Free-block management
Outline:
- free list is implemented as a B tree (its root block is in
block 2 of the file)
- with cache (free-list-cache, one per segment)
- cache gets filled (to 1/2 full) when it empty and a block is needed;
it gets flushed (to 1/2 full) when its about to overflow.
- cache can be filled either from the free-list-tree or if that’s
empty, the file is extended.
- cache filling is now done efficiently using scan-delete. This
also means that only one disk write will be done per
fill (in most cases).
- cache filling is interlocked so only one process can be filling the
cache at a time.
- currently cache emptying is inefficient as each write of of a block
to the tree causes an I/O [deferred writes is intended to fix this]
Current problems:
Last week (1/8) we concluded that (all efforts to date
notwithstanding) there were still failure cases in free-block
management under concurrent operation, because of problems like:
- multiple processes can eat up however many blocks are in the cache,
meaning we still haven’t handled the case where a PUT to the free list
causes a block split (necessitating a recursive call to FREE-BLOCK).
- Conversely, it is possible for the cache to become overfilled
by a cache filling operation, if in the meantime OTHER processes fill
the cache with deleted blocks.
- We need to be sure in general that concurrent fills and/or empties
don’t overfill or over-drain the cache.
On the positive side, we realized that we NEED NOT allow enough
free blocks for a free-list insert to split the whole tree – any
split except the leaf split can simply be postponed if there isn’t a
free block available at that time! (And similarly for any insert-updates
that happen to be triggered by free-list accesses.)
Come to think of it, if we happen to run out of blocks during a
free-list insert, its OK to let the insert fail, we just lose one disk
block!! That may just be the answer!!