home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / CONTRIB / MBASE / MBASE50.TAR / mbase / dox / lock.dox < prev    next >
Encoding:
Text File  |  1992-10-25  |  11.2 KB  |  214 lines
  1. Relation Locking                                                  MetalBase 5.0
  2. -------------------------------------------------------------------------------
  3.  
  4.  
  5. Because MetalBase does not run on a client/server basis (there is no huge
  6. superuser-running program which performs queries when requested), processes
  7. must fight each other for access to relations.  In order to ensure database
  8. integrity, a system of locking has been implemented which provides a timing
  9. for enlarging atomic-level operations; those which should be accomplished in
  10. their entireity before another process may use the relation.  *nix-style file
  11. locking is not portable enough to be useful here, much to my dismay... many
  12. sites don't have any such ability through the standard compiler; worse, on
  13. some systems (Xenix among them), calls succeed when they don't do anything.
  14.  
  15. Version 5.0 supports two forms of locking, one of which is transparent and
  16. used by the system internally, the other being exposed to the user.  "Temporary
  17. locks" are placed by the system to enlarge the timescale of atomic operations,
  18. to ensure concurrent querying/updating will not corrupt the database.  These
  19. locks are placed on the relation automatically, during all operations--adding,
  20. updating, deleting, and querying the database, as well as in the process of
  21. allowing the user to place the more permanent exclusive locks.
  22.  
  23.  
  24. TEMPORARY LOCKS ---------------------------------------------------------------
  25.  
  26.  
  27. Temporary locks are used to give a single process control over a relation for
  28.    a short period of time; from a fraction of a second (needed at the beginning
  29.    of a service call to ensure no exclusive lock is in place) to a few seconds
  30.    or more (for the duration of an index update).  The basic algorithm relies
  31.    on the fact that each process has a unique identifier in the range 0-65535;
  32.    MetalBase 5.0 uses the process ID for this.  In essence, each relation
  33.    stamps its identifier into a specific place in the relation, and reads back
  34.    what is there--if it reads its own process ID, it continues with its work,
  35.    leaving the stamp (and thus a temporary lock) in place.
  36.  
  37. That is a far oversimplified version.  In reality, because of the way most
  38.    multi-user systems work, a scheme with only one such check will always grant
  39.    a lock to any relation; the write-our-PID followed by read-the-byte will
  40.    almost always return the PID simply because the write and read are so close
  41.    together that they are almost guaranteed to be processed in sequence,
  42.    without allowing other processes to vie for the lock.  There is also the
  43.    issue of a process having terminated, leaving a temporary lock in place; in
  44.    that case, the relation would be useless until such a lock could be cleared.
  45.    Moreover, in practice, such a scheme would give control to the same process
  46.    over and over, not allowing any other process a chance to work (in
  47.    benchmarks, three terminals running the same program to add records
  48.    constantly over 30 seconds ended up with results of the form: 1st==500
  49.    records, 2nd==2 records, 3rd==0 records).
  50.  
  51. The first problem is the granting of a temporary lock to one process at any
  52.    given time--this is done by iterating the check described above three times:
  53.  
  54.      set_hack(): read the three hack-lock positions (6 bytes)
  55.                  if our PID is in any, write a zero there and goto set_hack()
  56.                  if all three aren't zeroes, goto set_hack()
  57.                  write our PID in the third
  58.  
  59.                  read the three hack-lock positions
  60.                  if first and second aren't zeroes, goto set_hack()
  61.                  if third isn't our PID, goto set_hack()
  62.                  write our PID in the second
  63.  
  64.                  read the three hack-lock positions
  65.                  if first isn't zeroes, goto set_hack()
  66.                  if second and third aren't our PID, goto set_hack()
  67.                  write our PID in the first
  68.  
  69.                  read the three hack-lock positions
  70.                  if any of the three aren't our PID, goto set_hack()
  71.  
  72.      clr_hack(): read the three hack-lock positions (6 bytes)
  73.                  if all three aren't our PID,
  74.                     (error case 1--abort)
  75.                  write zeroes in all three
  76.  
  77. Iterating the process in this fashion shrinks the window for a race condition
  78.    to such an extent that it's negligible... and that solves the first of the
  79.    three problems.  The second would be distribution of resources; as the
  80.    example above, just letting them take their chances doesn't cut it.  To
  81.    more evenly distribute access to a relation, a hack lock, as described
  82.    above, is used to gain access to a thirty-position queue, of the form:
  83.  
  84.  elcks hacklocks  queue
  85.   [ ]   [ | | ]   [ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ]
  86.  
  87. The leftmost position in the queue is position #0, indicating a temporary lock
  88.    is in place.  Once a relation has gained control via a hack lock, it reads
  89.    the 60 bytes of queue and finds the first empty slot (denoted by a 0 PID).
  90.    It then places its own PID in that position and clears the hacklock for any
  91.    other process to use.  If the position found free is #0, it has just placed
  92.    a temporary lock and the process can go about its service.  Otherwise, the
  93.    process will enter the following loop:
  94.  
  95.              A: read queue position (CURPOS -1)
  96.                 if non-zero, go to A
  97.                 write our PID in position (CURPOS -1)
  98.                 write zero in position (CURPOS)
  99.                 CURPOS -= 1
  100.                 if (CURPOS == 0)  break -- temporary lock is in place
  101.                 otherwise, goto A
  102.  
  103. This loop works without placing hacklocks before reading because exactly one
  104.    process is guaranteed to be reading a position in the queue at any given
  105.    time, and the free space will bubble from the left to right as temporary
  106.    locks are freed.  Note that if a position in the queue can't be found to
  107.    start with, the system will return MB_BUSY.  This method ensures equal time
  108.    for equal requests, for up to thirty processes simultaneously; note that
  109.    many more processes can be run at once on a relation, but only thirty
  110.    queries will be serviced at any time.  This is an extremely reasonable
  111.    restriction.
  112.  
  113. The third and final problem with regard to locking is the most nerve-wracking;
  114.    if a process dies, leaving a lock in place, other processes will wait
  115.    forever for the lock to be cleared.  Originally, the BLAST utility was the
  116.    only way to remove these locks; pre-release 5.0 was able to detect this
  117.    condition under some circumstances, but it was too flaky to rely upon.  In
  118.    essence, since inter-process communication is a no-no for portability,
  119.    MetalBase needed a way to determine if a process were still active or not...
  120.    to that end, the temporary-lock queue has been equipped with a strobe byte
  121.    for each position:
  122.  
  123.  elcks hacklocks  queue
  124.   [ ]   [ | | ]   [ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ]
  125.                   < : : : : : : : : : : : : : : : : : : : : : : : : : : : : : >
  126.                   strobes
  127.  
  128. Whenever a process is either waiting in the queue for a turn, or when a process
  129.    has a temporary lock in place and is querying or updating the database, it
  130.    is constantly incrementing a byte found in the current lock position's
  131.    strobe... to be exact, within the queue, the strobe is changed every second;
  132.    within a query, whenever the depth is a multiple of 5; within an update,
  133.    at various locations initially followed by a call at every _balance() call.
  134.    If a process waiting in the queue finds that three seconds go by without
  135.    a strobe being changed, it determines itself justified in taking over the
  136.    position, under the assumption that the old process is dead.  Note that
  137.    this approach will not work well with DOS networks, which often bring long
  138.    lag-times which would destroy concurrency... not always, but often enough
  139.    to worry about.  IPC would be the best way to improve this, but there is
  140.    no standard which does not require superuser access and device drivers on
  141.    any *nix platform, and that's unacceptable for MB.
  142.  
  143. When jockying for a hacklock, if three seconds elapse without a request being
  144.    accepted, a process will erase all three bytes and try again.  If a process
  145.    halts with an exclusive lock in place (mb_rmv(), mb_exit() and mb_die()
  146.    remove any locks before closing, so that's not a problem--the process must
  147.    be halted by a signal or power cycle), the exclusive lock must be removed
  148.    with BLAST before the relation will be useful again.
  149.  
  150.  
  151. EXCLUSIVE (RELATION-WIDE) LOCKS -----------------------------------------------
  152.  
  153.  
  154. An exclusive lock is placed by a user using mb_lck(), and removed with mb_unl()
  155.    [these two functions were forgotten in the 4.0 release--sorry].  Once an
  156.    exclusive lock is placed, any action requested by another process will fail
  157.    with the error MB_LOCKED, until the lock is removed.
  158.  
  159. The flow for mb_lck() and mb_unl() are as follows:
  160.  
  161.    mb_lck():  set temporary lock on relation
  162.               read exclusive-lock PID
  163.               if (PID == ours)  clear temp lock; stupid--you already locked it
  164.               if (PID != 0)     clear temp lock; return MB_LOCKED by another
  165.               write our PID in the exclusive-lock byte
  166.               clear temp lock; return MB_OKAY
  167.  
  168.    mb_unl():  set temporary lock on relation
  169.               read exclusive-lock PID
  170.               if (PID == ours)
  171.                  write 0 there
  172.               clear temp lock; return MB_OKAY
  173.  
  174. This simple procedure works, because all requests of the relation must pass
  175. the following check before operating (a temporary lock must be in place before
  176. calling this routine):
  177.  
  178.    _chk_elck(): check exclusive-lock PID
  179.                 if (PID != 0 && PID != ours)  return MB_LOCKED
  180.                 return MB_OKAY
  181.  
  182. These routines are slightly more complicated in the source, because there is
  183. a bit of duality of information--each relation structure also retains flags
  184. indicating whether the relation is temp-locked and/or exclusive-locked.  There
  185. are more failure conditions because of this, which ensures that locks will
  186. not be placed when they should not be.
  187.  
  188.  
  189. EXCLUSIVE (RECORD-LEVEL) LOCKS ------------------------------------------------
  190.  
  191.  
  192. There are none in MetalBase 5.0--let me know if you need this, so I'll know
  193. what to spend my time on.  It'll be in a later version--just a matter of when.
  194.  
  195.  
  196. LOCKFILES ---------------------------------------------------------------------
  197.  
  198.  
  199. The kind of work described above--all the busyloops and so forth--really,
  200. really slow down access to a relation... the fewer things a file is doing at
  201. any given time, the more you can get accomplished.  So the locking mechanism
  202. has been moved off to a separate file, named after the relation (with the
  203. extension replaced with ".LCK") and placed in a temporary directory (see
  204. trouble.dox, under MB_TMPDIR).  This file is created every time mb_inc() is
  205. called, if it does not already exist.
  206.  
  207. There is exactly one lockfile for each relation, kept in a common temporary
  208. directory.  You can delete the lockfile at any time, as long as you're sure
  209. there is no one using the relation at the time (this would be a Bad Thing to
  210. delete if the relation is in use).  Deleting the lockfile will erase any
  211. remaining exclusive lock, and reset the number of users on the relation to
  212. zero.
  213.  
  214.