[RC5] LIFO? Is this true?

Sanford Olson 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 
>     one*.

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 
>     endeavours.

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
structures. *grin*

- Sanford 
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list