src/mcas/README

   1  The Lock-Free Library
   2  =====================
   3
   4
   5 1. Building
   6 -----------
   7 Edit the Makefile and set ARCH to the appropriate value.
   8 Type 'make'.
   9
  10
  11 2. What you get
  12 ---------------
  13 'stm_fraser.c' is an object-based STM with the programming API defined
  14 in 'stm.h'. 'mcas.c' is an implementation of multi-word
  15 compare-and-swap.
  16
  17 These are used to build a number of search structures: skip lists,
  18 binary search trees, and red-black trees. The executables are named as
  19 follows:
  20
  21  bst_lock_fraser      --- BST implementation using per-node locks.
  22                           No locking for read operations.
  23  bst_lock_kung        --- BST implementation using per-node locks.
  24                           No locking for read operations.
  25  bst_lock_manber      --- BST implementation using per-node locks.
  26                           No locking for read operations.
  27  bst_mcas             --- BST implementation based on MCAS.
  28
  29  rb_lock_concurrentwriters --- Red-black trees with concurrent writers.
  30                                Based on MCS multi-reader locks.
  31  rb_lock_serialisedwriters --- Red-black trees with serialised writers.
  32                                Based on MCS multi-reader locks.
  33  rb_lock_mutex        --- Red-black trees with concurrent writers, and
  34                           no locking for read operations. Very fast!
  35  rb_stm_fraser        --- Red-black trees using Fraser's STM.
  36  rb_stm_herlihy       --- Red-black trees using Herlihy et al's STM.
  37  rb_stm_lock          --- Red-black trees using 2-phase-locking STM.
  38
  39  skip_lock_perlist    --- Skip lists with a single global lock.
  40                           No locking for read operations.
  41  skip_lock_pernode    --- Skip lists with a lock per node.
  42                           No locking for read operations.
  43  skip_lock_perpointer --- Skip lists with a lock per pointer.
  44                           No locking for read operations.
  45  skip_cas             --- Skip lists built directly from CAS.
  46  skip_mcas            --- Skip lists based on MCAS.
  47  skip_stm_fraser      --- Skip lists using Fraser's STM.
  48  skip_stm_herlihy     --- Skip lists using Herlihy et al's STM.
  49  skip_stm_lock        --- Skip lists using 2-phase-locking STM.
  50
  51 Each executable is run as:
  52  <executable> <num_threads> <read_proportion> <key power>
  53
  54 'executable' is one of the above implementations.
  55
  56 'num_threads' indicates the degree of parallelism.
  57
  58 'read_proportion' determines what proportion of the random workload is
  59 lookups as opposed to updates or removals. The proportion is out of 256.
  60
  61 'key_power' indicates the key range. Key range is 2 ^ 'key_power'.
  62 Since updates and removals are equally probable, the mean set size
  63 will be 2 ^ ('key power' - 1).
  64
  65
  66 3. Verifying correctness
  67 ------------------------
  68 To check that each implementation correctly behaves as a 'set' ought
  69 to, you can define DO_WRITE_LOG in 'set_harness.c'. This will cause
  70 each implementation to produce a log describing each operation that
  71 was executed, and its result.
  72
  73 This can be run through 'replay' which will serach for a linearisable
  74 schedule.
  75
  76
  77 4. Distribution license
  78 -----------------------
  79 The license is GPL. See the file COPYING for details.
  80
  81
  82  -- Keir Fraser, 25th September 2003
  83
  84
  85 ****
  86
  87 This software has been released by its original author, Keir Fraser,
  88 with permission from his advisors, under a BSD license.  For details,
  89 please see README.LICENSE.
  90
  91  -- Matt Benjamin, 07/24/2009