Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!ucsd!sdcsvax!deh0654@sjfc.UUCP
From: deh0654@sjfc.UUCP (Dennis Hamilton)
Newsgroups: comp.os.research
Subject: Re: O/S's using bit maps for free disk block lists?
Message-ID: <4829@sdcsvax.UCSD.EDU>
Date: 31 Mar 88 21:57:04 GMT
Sender: nobody@sdcsvax.UCSD.EDU
Organization: Saint John Fisher College, Rochester, NY
Lines: 36
Approved: comp-os-research@ucsd.edu

[ This will be the last bit-mapped allocation posting, unless something ]
[ really new appears.  --DL                                             ]

The CP/M operating system used bit maps, and it was very efficient on small-
memory machines using slow floppy disks, for example.  The bit map is not 
stored on the disk however -- it is constructed from allocation tables every
time the disk is "mounted."  That way, there is no problems about using a
bit map that has been invalidated by a crash (or at least, fewer problems).
The CP/M directory structure lists the allocated blocks for each file, using
directory overflow records if necessary, for large or strange, sparse files
whose virtual blocks are not all allocated.

The biggest problem with the CP/M scheme has to do with shared physical blocks.
The file erase function updated the bit map and invalidated the directory slot
of the erased (actually, released) file, but it wouldn't notice if any blocks
were shared with another file.  This allows re-allocation of shared blocks when
they are really not available.  There are remedies, and some utility software
is careful to force the equivalent of a remount every time that erasure is
done, so that the bit map will be correctly reconstituted.

Apart from the time needed to reconstruct a bit map every time a disk volume
is mounted, the only other problem that tended to reduce performance was the
need to consult directories so often, especially for file allocation overflow
records.  This was improved in later versions by improved directory caching and
knowing which devices were non-removable.

A very nice quality of the CP/M scheme was the ability to handle sparsely
allocated large virtual files.  That, and sharing of blocks seems actually to
go smoother than the linking in allocation lists that is typical of MSDOS and
other systems.  But as far as performance goes, caching is becoming so easy
that it would seem to overcome most performance objections to any method (except, possibly, in terms of ability to handle recoveries after crashes).

Dennis E. Hamilton

--
	-- orcmid {uucp: ... !rochester!sjfc!deh0654
		   vanishing into a twisty little network of nodes all alike}