Results of Locking Poll

[Hokey]

There has almost been a small mail discusison going on between me, John
Bass, and gentleman named Radek (at HP in Germany) regarding these issues.
Here is the letter John recently sent to us.  Some of my comments are
interspersed.

> Date: Sat, 20 Oct 84 12:30:32 pdt
> From: wucs!ihnp4!hpda!dmsd!bass
> To: hpda!hpfcla!hpbbn!hpbbla!radek
> Subject: Re:  shared locking
> Cc: hpda!hpfcla!ihnp4!wucs!gang!plus5!hokey
> 
>>  Date: Fri, 19 Oct 84 03:04:16 pdt
>>  From: hpda!hpfcla!hpbbn!hpbbla!radek
>>  To: hpbbn!hpfcla!hpda!dmsd!bass
>>  Subject: shared locking
>>  Cc: hpbbn!hpfcla!ihnp4!wucs!gang!plus5!hokey
>>  
>>  Hi John,
>>  
>>  about 88% of the people, who answered to Hokey Stenn's survey,
>>  wish to have shared file & record locking, in addition to
>>  exclusive locks.
>>  
>>  As far I know, you expressed some concerns about the feasibility
>>  to implement this feature.
>>  
>>  Would you be so kind and tell me the major issues on that?
>>  
>>  Thanks.
>>  
>>  
>>  Radek Linhart			Hewlett-Packard GmbH
>>  dmsd!hpda!hpfcla!hpbbn!radek	P.O. Box 1430
>>  				D-7030 Boeblingen 1
>>  phone +49 7031 142052		W. Germany
>>  
> 
> Hi Radek,
> 
> 	I don't know anything about Hokey Stenn's questions or responses.
> I do know that when people are told that they MUST/CAN have shared locks the
> response is nearly 100% that they are required ... but when you ask why,
> what for, and how used ... the answers are nearly 100% confusion.
> 
> 	Your request has been the first on this issue in many months.
> There are many issues that say a general locking scheme should
> not have shared locks ... all of which revolve around a combination of
> implementation issues , usage senarios, and safety/protection of the
> typical MIS Dept programmer.
> 
> 	Lockf record locks are simply SEMAPHORES that use files as the
> resource name space. They are good for handling typical semaphore problems.
> Lockf (or other general semaphore scheme) doesn't replace (or allow building)
> a data base file system using transactional access -- particularly n-way trees
> and multiple keys.. 
> 
> 	First there are AT LEAST two major forms of shared locks, and several
> minor forms.
> 
> 	1) A process needs to update a record in a database. The record is
> 	to be updated via operator interaction over an unconstrained time
> 	period ... it is necessary that other processes have unrestricted
> 	read access. Thus the interactive process locks the record as
> 	"shared", reads the record, edits it, and rewrites the record
> 	as a critical region. The critical region is normally formed by
> 	relocking the record as non-shared, writing the data, and unlocking
> 	the record. Depending on how the record is processed the write
> 	operation may be a critical region in some systems (IE the inode is
> 	locked for the duration of the read/write system call). This is neither
> 	required or generally implemented for ALL classes of files.
[ This type of operation is often seen in airline reservation systems and
the like.  One solution is to read-lock the record, read and unlock the
record, do the work, write lock the record, and see if the record was
"significantly" changed in the interim.  If not, write and release the
record.  Otherwise, release the write-lock and tell the operator to try
again. ]
> 
> 	2) A process requires multiple data segements to PIECE togather
> 	a data item ... it is critical to maintain PHASE with all data
> 	items ... the general ledger, receivables, inventory ... etc update
> 	problem ... AND ... traversal of an n-way tree or complex data base
> 	structure. Here the reader locks all required segments as shared to
> 	maintain order while fereting out complex data sources. The sharing
> 	is used to allow other readers to access the data ... but to block
> 	writers.
> 
> NOTE that 1 implies a single process can read share lock a resource and
> 	has the unrevokable right to transition to non-shared at will.
> 
> NOTE that 2 implies all processes may lock a read shared resource and
> 	that there is no right to transition to non-shared status.
> 
> 	Thus at minimum there are 4 resource states, unlocked, non-shared,
> update-shared, and read-shared. There are also an interesting
> set of contention states that lead to deadlocks and race conditions.
> The code to implement is highly system and use dependent and it
> is NOT a portable construct. I have modeled some portions of the code,
> but can not in my own mind rationally address the tradeoffs without
> addressing specific data based implementations and usage patterns.
> In effect I feel that any result will be neither general or portable.
> Most results will lead novice programmers (and most other programmers that
> don't grasp concurrency well) down the garden path to deadlocks and race
> conditions. The non-shared approach generally is brutal enough that
> they think about the major issues or find another approach.
> 
> 	The number 1 request for read-shared locks is to implement
> n-way tree type databases ... or multiply-keyed data bases. In general
> the implementors haven't thought out the impact of their request.
[     ************ If you mean users instead of implementors, I disagree.
The purpose of Users is to keep Implementors in line, and bitch about bad
implementations.  Once these concepts are learned, they're pretty easy to
use. ]
> 
> 	Ponder for an hour or two a b-tree or b+-tree with most upper
> nodes read-share locked due to normal access traffic and transversals.
> For a transversal the top most node will be locked for the entire transversal.
> Thus the topmost node, and about 10-20% of the remaining nodes, are in
> effect live-locked (never really available for non-shared or update-shared
> access). This is a CRITICAL limitation in that a SIGNIFICANT class of data
> can not be DELETED or ADDED due to implied compaction and expansion of
> nodes. And in data bases with DATA in the nodes (not just in leaves) the
> upper nodes often may be difficult to obtain locks for update.
[ The solution to this problem is to give write lock requests a higher
priority than read locks. ]
> 
> 	The learning process one-to-one exploring this problem is several
> hours -- with common goals. The learning process in a group with diverse
> goals is difficult -- MANY people AFTER the above explanation still
> don't understand the ramifications of items 1 & 2 and still think of
> a shared lock that is both 1 & 2 at the same time. I wonder how many
> of the 88% responding have a need that can only be handled with a shared
> lock -- and have thought through HOW they would use it and what it's semantics
> would be. I would guess only a few.
> 
> 	A poll of how many folks would like a free X vs X+Y will generally
> be highly swayed to X+Y due to basic human nature.
> 
> 	What is generally needed are general semaphores (lockf) for the
> common problems -- and a kernel based transactional filesystem (database)
> for the tougher problems. The split is about 90%++ and less than 10%.
> Lockf was implemented to be both general and portable across many systems
> (including non-unix systems) -- I think lockf achieves that goal.
> To handle the remaining 10% of the application areas is significantly
> application specific or system specific.
> 
> 
> Hope this helps ... have fun
> 
> John Bass
> 
I, as one might guess, would prefer 4.2-style locks to be the standard,
as they are the fastest in operation.  During a phone conversation with
John Bass this afternoon he told me that time is not significant; the
existing lockf() mechanism on most PDP-11s and 68K machines require
200 nsec of system time and 200 nsec of "real" work.  This is based on
knowledge that there are rarely more than 3-5 processes after the "same"
thing.  I *could* change my mind...
-- 
Hokey           ..ihnp4!plus5!hokey
		  314-725-9492