[RC5] LIFO? Is this true?
sanford at msn.fullfeed.com
Sat May 16 02:38:59 EDT 1998
At 12:14 PM 5/11/1998 , Eric Gindrup wrote:
> Locking entire shared files is a terrible idea. This locking
> technique locks the entire buff-in down during a fetch or during a
> "get a new block to crack". Locking the entire file defeats the
> advantage of multithreading the clients. All clients that finish a
> block during a fetch have to wait until the fetch is completed to
> get a new block *even if the block they get isn't a newly fetched
Not true. You don't lock the file for a complete fetch/flush. You lock it
for each access: RemoveABlock, AddABlock. Because of the structure
(implied or otherwise) of the file, it is necessary to lock out all other
users when adding or removing a block. If the blocks were just being read
or modified, then a record-level locking scheme would increase performance.
The clients, by being multi-threaded, can still remain busy while the
thread that adds and removes blocks from the buff-* files is patiently
waiting for access to the files (you can lock/unlock files several hundred
times a second, so it's not a long wait). As long as the I/O thread can do
it's RemoveABlock from buff-in and it's AddABlock to buff-out before the
Compute thread finishes another block, it's no big deal.
> Clients "should" do record-level locking. Unfortunately on MS OSes,
> the finest OS-supported locking is one cluster which is much larger
> than a block record in the buff-* files. Other OSes don't seem to
> have this idiotic limitation.
Also not true. Since MS-DOS 3.1, there has been an API call (provided by
SHARE.EXE or network software) to lock any length byte range on any byte
offset in a file. There are no cluster or record locking API calls. In
Win32, see the "LockFile" API call.
> Appending is a trivial operation in a lot of real filesystems.
> Prepending is not. Implementing the buff-* files as LIFOs was
> trivial when the v1 and v2 clients were specified. Implementing the
> buff-* files as FIFOs would have required more development time
> because verifying any code, even CompSci101 data structures,
> requires more time than not having to verify it. At the time this
> architectural decision was made, time was better spent on other
Prepending is unnecessary to support LIFO. I can't think of anything that
prepending would be useful for, thus explaining it's non-existence in most
operating systems (it could be implemented just as easily as appending is).
Even though the current LIFO scheme has an implied data-structure, it is
still a data structure and in many ways is just as hard to code as an
explicit linked-list stack would be. Also, the buff-* files have a file
header in them anyway. Obviously, what's done is done and it is certainly
not worth any effort to change it. Any buff-* file format change requires
replacing all the clients in shared environments (simultaneously). I'm
just a simple system programmer, so I enjoy discussing shared-access file
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5