BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-99-1624
       ENTRY:: August 26, 1999
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Non-blocking Synchronization and System Design
        TYPE:: Thesis
        TYPE:: Technical Report
      AUTHOR:: Greenwald, Michael
        DATE:: August 1999
       PAGES:: 261
    ABSTRACT:: Non-blocking synchronization (NBS) has significant advantages
               over blocking synchronization in areas of fault-tolerance,
               system structure, portability, and performance. These
               advantages gain importance with the increased use of
               parallelism and multiprocessors, and as delays increase
               relative to processor speed.

               This thesis demonstrates that non-blocking synchronization is
               practical as the sole co-ordination mechanism in systems by
               showing that careful OS design eases implementation of
               efficient NBS, by demonstrating that DCAS
               (Double-Compare-and-Swap) is the necessary and sufficient
               primitive for implementing NBS, and by demonstrating that
               efficient hardware DCAS is practical for RISC processors.

               This thesis presents high-performance non-blocking
               implementations of common data-structures sufficient to
               implement an operating system kernel. I also present more
               general algorithms: non-blocking implementations of \casn\
               and software transactional memory. Both have overhead
               proportional to the number of writes, support
               multi\--objects, and use a DCAS-based contention-reduction
               technique that is fault-tolerant and OS-independent yet
               performs as well as the best previously published techniques.
               I demonstrate that proposed OS implementations of DCAS are
               inefficient, and propose a design for efficient hardware DCAS
               specific to the R4000 but generalizable to other RISC
               processors.
       NOTES:: [Adminitrivia V1/Prg/19990826]
         END:: STAN//CS-TR-99-1624