DOC PREVIEW
UT CS 395T - Software Transactional Memory

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Software Transactional MemoryNir Shavit*Dan TouitouMIT andTel-Aviv UniversityAbstractAs welearn from the literature, flexibility in choosing syn-chroni~ation operations greatly simplifies the task of de-signing highly concurrent programs.Unfortunately, ex-isting hardware is inflexible and is at best on the levelof a Load_Linked/Store_Cond itional operation on a singleword. Buildktg on the hardware based transactional syn-chronization methodology of Herlihy and Moss, we offersoflwar-e transactional memory (STM), a novel softwaremethod for supporting flexible transactional programmingof synchronization operations. STM is non-blocking, andcan be implemented on existing machines using only aLoad.Linked/Store.Conditional operation. We use STM toprovide a general highly concurrent method for translatingsequential object implementations to lock-free ones basedon implementing a k-word compare&swap STM-transaction.Empirical evidence collected on simulated multiprocessor ar-chitectures shows that the our method always outperformsall the lock-free translation methods in the style of Barnes,and outperforms Herlihy’s translation method for sufficientlylarge numbers of processors. The key to the efficiency of oursoftware-transactional approach is that unlike Barnes stylemethods, it is not based on a costly “recursive helping” pol-icy.1 IntroductionA major obstacle on the way to making multiprocessor ma-chines widely acceptable is the difficulty of programmers indesigning highly concurrent programs and data structures.Given the growing realization that unpredictable delay isan increasingly serious problem in modern multiprocessorarchitectures, we argue that conventional techniques for im-plementing concurrent objects by means of critical sectionsare unsuitable, since they limit parallelism, increase con-tention for memory and interconnect, and make the systemvulnerable to timing anomalies and processor failures. Thekey to highly concurrent programming is to decrease thenumber and size of critical sections a multiprocessor pro-gram uses (possibly eliminating critical sections altogether)Permission to make d@al/hard copies of all or part of this material forpersonal or classroom use is granted without fee provided that the copiesa~e not made or distributed for profit or commercial advantage, the copy-right notice, the title of the publication and ik date appear, and notice isgiven that copyright is by permission of the ACM, Inc. To copy otherwise,to republish, to post on servers or to redistribute to lists, requires specificpermission and/or fee.PODC 95 Ottawa Ontario CA 01995 ACM 0-89791-710-3/95/08. .$3.50lContact Author: E-mail:shanir@theory. lcs. rnit.eduTel-Aviv Universityby constructing classes of implementations that are non-blockirag [7, 15, 14]. As we learn from the literature, flexibil-ity in choosing the synchronization operations greatly sim-plifies the task of designing non-blocking concurrent pro-grams.Examples are the non-blocking data-structures ofMassalin and Pu [22] which use aCorn pare&Swap on twowords, Anderson’s [2] parallel path compression on listswhich uses a special S pi ice operation, the counting net-works of [5] which use combination ofFetch&Complementand Fetch&I nc, Israeli and Rappoport’s Heap [18] which canbe implemented using a three-wordCorn pare&Swap , andmany more.Unfortunately, most of the current or soon tobe developed architectures support operations on the level ofa Load. Linked/Store-Conditional operation for a single word,making most of these highly concurrent algorithms imprac-tical in the near future.Bershad [7] suggested to overcome the problem of provid-ing efficient programming primitives on existing machinesby employing operating system support. Herlihy and Moss[16] have proposed an ingenious hardware solution: trans-actional memory. By adding a specialized associative cacheand making several minor changes to the cache consistencyprotocols, they are able to support a flexible transactionallanguage for writing synchronization operations. Any syn-chronization operation can be written as a transaction andexecuted using an optimistic algorithm built into the consis-tency protocol. Unfortunately though, this solution isblock-ing.This paper proposes to adopt the transactional approach,but not its hardware based implementation. We introducesofiware transactional memory(STM), a novel design thatsupports flexible transactional programming of synchroniza-tion operations in software. Though we cannot aim for thesame overall performance, our software transactional mem-ory has clear advantages in terms of applicability to todaysmachines, portability among machines, and resiliency in theface of tirnhg anomalies and processor failures.We f0cu5 on implement.ati0n9 of a software transactionalmemory that support static transactions, that is, transac-tions which access a pre-determined sequence of locations.This class includes most of the known and proposed syn-chronization primitives in the literature.1.1 STM in a nutshellIn a non-faulty environment,the way to ensure the atomicityof the operations is usually based on locking or acquiring ex-clusively ownerships on the memory locations accessed by anoperation Op. If a transaction cannot capture an ownerships204it fails, and releases the ownerships already acquired. Oth-erwise, it succeeds in executingOp and frees the ownershipsacquired. To guarantee liveness, one must first eliminatedeadlocks, which for static transactions is done by acquiringthe ownerships needed in some increasing order. In order tocontinue ensuring liveness in a faulty environment, we mustmake certain that every transaction completes even if theprocess which executes it has been delayed, swapped out,or crashed. This is achieved by a “helping” methodology,forcing other transactions which are trying to capture thesame location to help the owner of this location to com-plete its own transaction. The key feature in the transac-tional approach is that in order to free a location one needonly help its single owner transaction. Moreover, one caneffectively avoid the overhead of coordination among sev-eral transactions attempting to help release a location byemploying a “reactive” helping policy which we call raon-redundant-helping.1.2 Sequential to Lock-free TranslationOne can use STM to provide a general highly concurrentmethod for translating sequential object implementationsinto non-blocking ones based on the caching approach of[6,


View Full Document

UT CS 395T - Software Transactional Memory

Documents in this Course
TERRA

TERRA

23 pages

OpenCL

OpenCL

15 pages

Byzantine

Byzantine

32 pages

Load more
Download Software Transactional Memory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Software Transactional Memory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Software Transactional Memory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?