Exploration of Lock-Based Software Transactional Memory Justin Gottschlich. M.S. Thesis, Department of Electrical and Computer Engineering, University of Colorado. November, 2007. As hardware manufacturers focus primarily on chip multi-processors (CMPs), a simplified and robust parallel programming model becomes critical for future software developments to harness the resources of these new architectures. Of the numerous solutions available, Transactional Memory (TM) shows great promise in reducing programming complexity while remaining high performing. Furthermore, transactional memory has composition characteristics which no other synchronization mechanism demonstrates. These attributes make transactional memory a potentially viable solution to the current parallel programming problem. For over a decade, software transactional memory (STM), a software-only approach to TM, was believed to be only practically implementable using non-blocking atomic primitives, such as compare-and-swap~(CAS) or load-linked and store-conditional~(LL-SC). Yet in the past two years, lock-based STM frameworks, which use a locking structure at their core, have emerged as an alternative design method for STM systems. While significant research exists on non-blocking STM solutions, little has has been done on lock-based STM. Of the few introductory efforts of lock-based STM research currently available, none attempt to broadly and deeply investigate STM from a lock-based perspective. This thesis presents a thorough examination of lock-based software transactional memory from (1) a theoretical and (2) a practical viewpoint. First, a background of three important classical synchronization mechanisms is covered to highlight the important aspects and limitations of each. Each synchronization primitive is scrunitized from varying angles ranging from critical section growth causing vertical scaling concerns to practical use within software systems. Next, software transactional memory theory and a practical application framework (DracoSTM) is presented. The TM theory and practice section covers differences between highly visible TM aspects, such as; non-blocking and lock-based systems, direct and deferred updating, validation and invalidation consistency checking, early and late conflict detection and atomic operational overhead. Third, a step-by-step analysis of the current lock-based STM criticisms is presented as well as a detailed counterargument (if necessary and possible) for each. Lock-based criticisms which also affect non-blocking systems are briefly examined here as well. Finally, a concrete performance analysis between DracoSTM, a lock-based C++ STM library and RSTM, University of Rochester's non-blocking C++ STM library is presented. [ PDF ]