Leadership & Management

12 pages
6 views

Hybrid transactional memory

Please download to get full document.

View again

of 12
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Hybrid transactional memory
Transcript
  Hybrid Transactional Memory Sanjeev Kumar † Michael Chu ‡ Christopher J. Hughes † Partha Kundu † Anthony Nguyen †† Intel Labs, Santa Clara, CA  ‡ University of Michigan, Ann Arbor { sanjeev.kumar, christopher.j.hughes, partha.kundu, anthony.d.nguyen } @intel.com mchu@eecs.umich.edu Abstract High performance parallel programs are currently difficult to writeand debug. One major source of difficulty is protecting concurrentaccesses to shared data with an appropriate synchronization mech-anism. Locks are the most common mechanism but they have anumber of disadvantages, including possibly unnecessary serializa-tion, and possible deadlock. Transactional memory is an alternativemechanism that makes parallel programming easier. With transac-tional memory, a transaction provides atomic and serializable oper-ations on an arbitrary set of memory locations. When a transactioncommits, all operations within the transaction become visible toother threads. When it aborts, all operations in the transaction arerolled back.Transactional memory can be implemented in either hardwareor software. A straightforward hardware approach can have highperformance, but imposes strict limits on the amount of data up-dated in each transaction. A software approach removes these lim-its, but incurs high overhead. We propose a novel hybrid hardware-software transactional memory scheme that approaches the perfor-mance of a hardware scheme when resources are not exhausted andgracefully falls back to a software scheme otherwise. Categories and Subject Descriptors  D.1.3 [ Programming Tech-niques ]: Concurrent Programming – Parallel programming General Terms  Algorithms, Languages, Performance  Keywords  Transactional Memory, Transactions, ArchitectureSupport, Nonblocking 1. Introduction Parallel programming is a challenging task because parallel pro-grams that achieve good parallel speedups are difficult to write anddebug. Programmers must consider a number of issues that mayimpact the performance and correctness of parallel programs. Onemajor issue is protecting accesses to shared data by using an appro-priate synchronization mechanism, the most popular of which islocks. However, lock-based programs have a number of disadvan-tages. These disadvantages pose a high hurdle to wide-scale adop-tion of parallel programming and motivate the need for an alterna-tive synchronization mechanism.Some of the disadvantages of locks are as follows. First, lock-based modules do not compose well [4]. In addition, programmersmust keep track of the implicit association between each lock and Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a fee. PPoPP’06   March 29–31, 2006, New York, New York, USA.Copyright c  2006 ACM 1-59593-189-9/06/0003...$5.00. the data it guards. Second, locks serialize execution at critical sec-tions even when there are no conflicting data accesses. Third, pro-grammers need to balance the granularity of locks to achieve goodperformance with a reasonable increase in programming complex-ity. Additionally, while finer-grained locks may expose more paral-lelism, they can increase overhead when multiple locks need to beobtained simultaneously. Fourth, lock-based programs have to bewritten carefully to avoid deadlocks. Fifth, locks can cause priorityinversion and convoying. Finally, if one process dies while hold-ing a lock, the other processes that need the lock might get blockedforever waiting for the lock to be released.In 1993, Herlihy et al. [16] proposed transactional memory asan efficient method for programmers to implement lock-free datastructures. Transactional memory is an alternative way to protectshared data that avoids many of the problems of lock-based pro-grams. A transaction provides atomic and serializable operationson an arbitrary set of memory locations [8]. Transactional memoryborrows the notion of transactions from databases. A transaction isa code sequence that guarantees an all-or-nothing scenario. That is,if it commits, all operations within a transaction become visible toother threads. If it aborts, none of the operations are performed. Inaddition, transactional memory guarantees that a set of transactionsexecuted in concurrent threads are guaranteed to appear to be per-formed in some serial order. This makes them very intuitive from aprogrammer’s perspective.Transactional memory addresses the problems associated withlocks [14]. The benefits of transactional memory include:1.  Easier to write correct parallel programs.  Transaction-basedprograms compose naturally [13]. Also, programmers do notneed to keep track of the association between locks and data.2.  Easiertogetgood parallelperformance. Programmers do notneed to worry about the granularity of locks. Unlike locks, se-rialization of transactions depends only on whether they are ac-cessing the same data. This gives transactional memory pro-grams the benefit of fine grain locking automatically.3.  Eliminatesdeadlocks. Transactions canbe aborted at any time,for any reason. Therefore, deadlocks in parallel programs canbe avoided by aborting one or more transactions that depend oneach other and automatically restarting them.4.  Easier to maintain data in a consistent state.  A transactioncan be aborted at any point until it is committed. When atransaction is aborted, all changes made within the transactionare automatically discarded.5.  Avoidspriorityinversionandconvoying. Ifathreadexecutingatransactionblocks other threads (because theytrytoaccess thesame data), the transaction can be aborted if that transaction hasa low priority or if it is blocked on a long-latency operation.6.  Fault tolerance.  If a thread dies while executing a transaction,the transaction is automatically aborted leaving the shared datain a consistent state.Herlihy et al. srcinally proposed a hardware transactionalmemory implementation that allowed transactional (atomic andserializable) accesses to a small, bounded number of memory loca-  tions [16]. The proposal included new instructions to start, commit,and abort transactions, and instructions to transactionally accessmemory. Transactional data is stored in a transactional cache un-til commit. This cache detects conflicting accesses to transactionaldata and aborts a transaction when such conflicts occur. This ap-proach incurs low execution time overhead but has strict resourcelimits—the number of locations that can be accessed in a transac-tional way. The resource limits makes transactional memory dif-ficult to use and restricts its use to programmers who implementoptimized libraries. It cannot be used by general purpose program-mers who write modular programs.Shavit et al. [25] were the first to propose a software transac-tional memory. More recently, Herlihy et al. [15] proposed a soft-ware scheme that includes an API to make transactions availableto general-purpose programmers. The implementation employs alevel of indirection to transactional objects so that a new versioncan be atomically “swapped in” on a commit. It also requires mak-ing a copy of all transactional objects modified during a transac-tion so that they can be discarded on abort. The benefit of thisapproach is that it is implementable on current systems withoutany additional hardware and it has no resource limits. However,the execution time overhead of manipulating transactional objectsand maintaining multiple versions of transactional data is signif-icant (frequently an order of magnitude slower than locks). Thishigh overhead makes this scheme unusable in practice for generalpurpose parallel programs.There are several proposals [1, 11, 19, 22] that address the re- source limitofhardware transactional memory usingacombinationof software and hardware (Discussed in more detail in Section 6). Our approach  We propose a novel hybrid hardware-softwaretransactional memory scheme that uses a hardware mechanism aslong as transactions do not exceed resource limits and gracefullyfalls back to a software mechanism when those limitsare exceeded.This approach combines the performance benefits of a pure hard-ware scheme with the flexibility of a pure software scheme.A simple approach to supporting a hybrid scheme is to requireall concurrent transactions to use the same mode (either hardwareor software) at a given point in time. In such a scheme, all concur-rent threads would try to execute transactions in a hardware modeas long as all transactions stay within the resource limits. As soonas any transaction exceeds the limits, all threads would transition toa software mode. This na¨ıve approach is not scalable—for parallelprograms with many threads, a single long transaction can cause allthe threads in the program to incur large overheads.To enable scalability, our scheme allows each transaction to in-dependently choose an execution mode. This is challenging be-cause the hardware and software modes employ very different tech-niques to implement transactions. The fundamental difference be-tween the two modes is that the hardware mode detects data con-flicts at the cache line granularity while the software mode detectsdata conflicts at the object granularity.Our work makes the following contributions:1. We propose transactional memory hardware that is just slightlymore complex in terms of chip area and design complexity thanHerlihy et al.’s srcinal proposal [16]. Unlike the srcinal pro-posal, our proposal can efficiently support the hybrid schemedescribed in this paper. We also use a buffer to hold transac-tional data, and make extensions to the ISA for flexibility. How-ever, we rely on a standard cache coherence protocol to detectconflicts with both software and hardware transactions. Further,our hardware supports simultaneous-multithreaded processors,multiprocessor systems, and the combination of the two.2. We present a hybrid transactional memory scheme that com-bines the best of both hardware and software transactionalmemory: low performance overhead as well as access to un- Instruction Description XBA  Begin Transaction All – all memory accesses aretransactional by default XBS  Begin Transaction Select – all memory accessesare non-transactional by default XC  Commit Transaction XA  Abort Transaction LDX/STX  Transactional Load/Store (overrides thedefault) LDR/STR  Regular (Non-Transactional) Load/Store(overrides the default) SSTATE  Checkpoint the register state RSTATE  Restore the register state to the checkpointedstate XHAND  Specifies the handler to be executed if atransaction is aborted due to data conflict Table 1.  ISA Extensions for Transactional Memorybounded number of memory locations. Our scheme is based onHerlihy et al.’s software scheme [15].3. We compare the behavior of our hybrid transactional memoryscheme to fine-grained locking, and to pure software and hard-ware schemes on a set of microbenchmarks that represent somevery common scenarios where synchronization is important.We find that our hybrid scheme greatly accelerates the softwarescheme, even in the presence of a high number of conflicts. 2. Proposed Architectural Support for HybridTransactional Memory This section discusses our proposed architectural support for a hy-brid transactional memory scheme. Our scheme supports hybridtransactional memory for simultaneous-multithreaded processors,multiprocessor systems, and a combination of the two. Our pro-posed hardware is only slightly more complex than a solution for apure hardware transactional memory system.Tosupport transactional memory inhardware, applicationsmustexecute special instructions at the beginning and end of each trans-actiontoindicatetheboundaries of thetransaction. Hardwareneedsto do the following to support transactional memory: 1) store spec-ulative results produced during transactions, 2) detect conflicts be-tween transactional data accesses, and 3) allow for aborting trans-actions or atomically committing them.In this work we consider a chip multiprocessor system (CMP),where each processor is capable of running multiple threads simul-taneously. Each processor has a private L1 cache, and the proces-sors share a large L2 cache that is broken into multiple banks anddistributed across a network fabric. Our scheme is applicable totraditional multiple-chip multiprocessor systems as well. 2.1 ISA Extensions New transactional memory instructions are added to the ISA (Ta-ble 1). These instructions are based on those proposed by Herlihyet al. [16] but have been extended to make them more flexible. ThisISA extension not only enables our hybrid transactional memoryscheme but can also be used to speed up locks using techniquessimilar to those proposed recently [21, 17]. Transactions running in hardware mode assume by default thatmemory accesses during the transaction are speculative (i.e., theyuse XBA). Transactions in software mode assume by default thatmemory accesses during the transaction are not speculative (i.e.,they use XBS). In some cases it is necessary to override thesedefaults; thus, we provide memory access instructions that areexplicitly speculative (LDX/STX) or non-speculative (LDR/STR).  The SSTATE and RSTATE instructions provide fast supportfor register checkpointing—with these, register state can be rolledback to just before a transaction began in case it is aborted. Theseinstructions arerelativelycheap toimplement inmodern processorsbecause such rollback mechanisms are already incorporated forother reasons (e.g., branch misprediction recovery).Our hardware abort mechanism involves raising an exceptionwhen a conflict is detected or when the capacity or associativityof the buffer holding speculative memory state is exceeded. TheXHAND instruction allows the exception handler to be specified. 2.2 Storing Speculative Results There is a large body of work on buffering speculative memorystate [1, 3, 5, 7, 10, 11, 16, 19, 20, 21, 22, 26, 27]. The key design decisions for a transactional memory system are where to bufferspeculative memory state and how to handle buffer overflows.Most schemes involve buffering state in the data caches [1, 3, 5, 7, 11, 20, 21, 22, 26, 27], but some schemes buffer speculative state in a special buffer [16, 10]. A third option is to store speculative memory state directly in main memory (with an undo log) [19].We discuss the design tradeoffs between the first two options for atransactional memory system later (Section 2.7).For transactional memory schemes that buffer speculative mem-ory state in a finite buffer or cache, another key design decision ishow to handle buffer overflows, i.e., what should be done if the as-sociativity or capacity of the buffer or cache holding speculativedata is exceeded. Thread-level speculation systems typically stall aspeculative thread until it becomes non-speculative; however, thisapproach will not work for transactional memory because transac-tions only become non-speculative when they commit. Some trans-actional memory systems allow data to overflow into main mem-ory [1, 22], but need special support to track this spilled state. Schemes that do not include this support either need the program-mer to be aware of the transactional buffering limitations and neverexceed them [16] or need another fallback mechanism [21]. Garzaran et al. discuss the speculative buffering design space inmore detail in the context of thread-level speculation [6].Figure 1 shows a processor with four hardware contexts andour proposed hybrid transactional memory hardware support. Theprocessor has an L1 data cache in parallel with a  transactionalbuffer  , a highly associative buffer that holds speculatively accesseddata from transactions. Each entry in the transactional buffer holdsboth the latest committed version of a line (Old) and any specula-tive version it is currently working with (New), bit vectors to in-dicate which hardware contexts have speculatively read or writtenthe line (transactional read/write vectors), and the conventional tagand state information. We discuss the transactional state table later.When a previously non-speculative line is speculatively writtento, a copy is made and that copy is updated with the new data. Thebuffer makes a copy and holds both versions because that versionof the line is the only guaranteed up-to-date copy of the data in thememory system—on an abort we must be able to revert back tothat version. Further speculative writes modify the copy of the line.The state of the line indicates which version should be returnedon each access. Lines that have been speculatively read or writtenand not yet committed cannot be evicted from the transactionalbuffer for correctness reasons. Therefore, if the transactional bufferattempts to evict such a line for capacity or associativity reasons,the transaction aborts and the application is notified that the abortis due to resource limits. 2.3 Detecting Conflicts Conflicts that hardware is responsible for detecting are those thatoccur between transactions (or between a transaction and non-transactional code) when a thread writes a line that another threadhas read or written speculatively and has not yet committed, orwhen a thread reads a line that another thread has speculativelywritten and has not yet committed.To detect conflicts, we leverage ideas from Herlihy et al. [16].We use the cache coherence mechanism to enforce two policies:1) no more than one processor has permission to write to a line ata time, and 2) there can be no readers of a line if a processor haspermission to write to it. These policies ensure that if a processorhas speculatively read or written a line, it will be notified if athread on another processor wants to write the line. Likewise, if athread has speculatively written a line, it will be notified if anotherthread wants to read the line. Hardware will automatically know if simultaneously executing threads on the same processor access thesame line as long as the hardware context id is communicated tothe memory system with all loads and stores. However, hardwaremust still track which lines have been speculatively read or writtenby a thread to know if a conflict has in fact occurred.Tothisend, weprovidetwobit vectorsforeach line,withonebitper hardware context on a processor, one vector for writes ( transac-tional write vector  ) and one for reads ( transactional read vector  ).A bit is set to indicate that the thread running on the correspondinghardware context has speculatively written (or read) the line. Wealso need to track whether each thread executing on a processor iscurrently executing a transaction or not, and if so, in which modeit is executing. It could be executing in hardware (ALL) mode viaan XBA instruction (where all memory accesses are transactional),or software (SELECT) mode via an XBS instruction (where onlyselected accesses are transactional). This can be done with two bitsper hardware context (see  transactional state table  in Figure 1).This field is set at the beginning of a transaction and cleared onan abort or commit. For every access to the cache, the hardwarewill check if the thread that issued the read or write is currentlyexecuting a transaction, what mode the transaction is, and if theinstruction is explicitly speculative or non-speculative, and if ap-propriate, set the corresponding read or write vector bit. Figure 1shows the design of a processor with transactional memory sup-port. Hardware for transactional memory includes a transactionalstate table and a transactional buffer. The transactional state tableprovides an entry for each hardware context on the processor totrack the mode of transactional execution of that hardware context.The transactional buffer provides a bounded number of entries forspeculatively accessed data. Each entry buffers two versions of dataand trackswhichhardware context has speculatively reador writtenthat piece of data. 2.4 Resolving Conflicts When a conflict is detected, it must be resolved. If the conflict isbetween a transaction and non-transactional code, the transactionis aborted (we discuss the abort mechanism below). If the conflictis between two transactions, the hardware always decides in favorof the transaction currently requesting the data. This scheme re-quires no changes to the cache coherence protocol. Priorities couldbe assigned to the transactions, and the conflict resolution couldproceed strictly by priority. However, existing schemes for honor-ing priorities require significant changes to the coherence protocolto prevent deadlock  [21]. 2.5 Aborting and Committing To abort a transaction, the hardware invalidates all speculativelywrittendata inthetransactional buffer, and clearsall of the readandwrite vector bits for that hardware context. Lines that were specu-latively read, but not speculatively written will remain valid in thetransactional buffer. It also sets an exception flag in the transac-tional state table (Figure 1) for that hardware context to indicatethat the transaction has aborted. The transaction will continue to  HW context idABCx Transactional BufferTrans. write vectorTrans. read vectorStateDataTag read−onlydirtydirty 0 0 0 000000000 000 000 001111y’z z’yOld New Processor L1 Data Cache ALLSELECTInvalidInvalid Transaction state Exception flag 0000 Transactional State TableHardware for Transactional Memory Address Figure 1.  A processor with transactional memory hardware sup-port. The transactional state table and the transactional buffer con-tain states for four hardware contexts on the processor.run until it executes another load or store, or it attempts to com-mit. If the exception flag for a thread is set, the next load or store itexecutes will raise an exception. This is because we can no longerguarantee that the data seen by the thread will be consistent. Theexception will trigger a software exception handler, which is re-sponsible for any necessary clean-up, and for restarting the trans-action if desired. If a thread tries to commit a transaction with itsexception flag set, the commit will fail, and software is responsiblefor restarting the transaction if desired.Tocommit atransaction, thetransactional readand writebitsforthe corresponding hardware context are cleared from all entries inthe transactional buffer. This will atomically make all speculativelywritten lines visible to the coherence mechanism, and all specula-tively read lines invisible to the conflict detection mechanism. Thisprocess may take multiple cycles if the buffer is large enough. Toguarantee atomicity, the transactional buffer delays all requests, in-cluding coherence requests, until the commit is complete. 2.6 Example System Figure 1 shows a processor with four hardware contexts and trans-actional memory hardware support. Looking at the transactionalstate table, we see that two of the contexts (the second and fourth)are currently executing threads that are running transactions, onein SELECT mode, and one in ALL mode, and neither has its ex-ception flag set. Examining the transactional buffer, we see fromthe transactional read and write vectors that both threads in trans-actions have speculatively read line A, and thread four has specu-latively read and written line B. Additionally, line C was specula-tively written by a thread that has since committed since it is in adirty state, but has no read or write vector bits set. We now describea few possible scenarios and how the hardware would behave inthose situations. These scenarios are also applicable to threads run-ning on different processors in a multiprocessor system, althougheachprocessor would haveitsownL1cache, transaction statetable,and transactional buffer. Scenario 1:  If the fourth thread were to write to line A, thehardware would abort the second thread’s transaction, clearing itsread vector bit for that line and setting its exception flag. The writewould also need to wait for permission from the L2 cache since theline is in a read-only state. Scenario 2:  If the fourth thread were to write to line C, thecorresponding write vector bit would be set. The data in the “New”field (z’) would be copied to the “Old” field, and then the writewould happen in the “New” field since the line is already dirtyin the transactional buffer – permission from the L2 cache is notrequired. Scenario 3:  If the second thread were to read line B, the hard-warewould abort the fourth thread’s transaction, clearing the fourthbit of all read and write vectors, invalidating the speculative copyof line B, and setting the fourth thread’s exception flag. If the readwas explicitly speculative the hardware would set the second readvector bit for line B. Finally, the non-speculative version of line Bwould be returned. 2.7 Advantages and Disadvantages There are many tradeoffs in the design of hardware support fortransactional memory. Our proposal has the following key advan-tages and disadvantages compared to the clear alternatives:1. Keeping a non-speculative copy of each speculatively modi-fied line in the transactional buffer allows us to retain the stan-dard coherence protocol. If instead we kept only one versionof a line in the buffer, we would need to ensure that a non-speculative copy was in the L2 cache, which would likely re-quire changes to the coherence protocol. However, our schemecomes at the cost of additional space requirements for the trans-actional buffer.2. Keeping the read and write sets (list of speculatively accessedlines) in a highly associative buffer separate from the L1 de-creases the chances of aborting a transaction due to conflictmisses. It also allows transaction commits and aborts to happenquickly since there are only a small number of read and writevector bits to clear. However, keeping the read and write setsin the L1 cache directly would provide more space for them,and would increase the amount of cache space available to non-transactional code (since otherwise some space is reserved forthe buffer). One way to make the transactional buffer space use-ful for non-transactional code would be to make it available asa victim cache – invalid or committed lines could be replacedwith victims from L1 evictions.3. Tracking which hardware contexts have speculatively read orwrittena line using bit vectors allows for fast commit and abort.However, the hardware cost may besignificant if therearemanyhardware contexts per processor. Since we do not anticipatethis number scaling very high, we believe this cost will remainsmall. 3. Hybrid Transactional Memory In addition to the architectural support described in Section 2, ourhybrid scheme also relies on algorithmic changes to the transac-tional memory implementation. In the following sections, we de-scribe Herlihy’s pure software scheme [15] and how we extendits Transactional Memory Object to facilitate our hybrid scheme.Then, we detail how our hybrid scheme operates. 3.1 Dynamic Software Transactional Memory Herlihy et al. proposed an API, called Dynamic Software Transac-tional Memory (DSTM) [15], which eases the process for program-  Figure 2.  A  TMObject   in DSTM.mers to create and use transactions by eliminating the resource lim-itations of a purely hardware transactional memory scheme. DSTMis a pure software implementation, and thus needs no additionalhardware support from the processor. DSTM is dynamic in twoways: it allows transactional objects to be dynamically created; andthe set of objects accessed transactionally does not need to be spec-ified at the beginning of a transaction. 3.1.1 DSTM API The DSTM API requires objects for which transactional propertiesare desired to be encapsulated by wrapper objects (in  TMObject  ).To access an object within a transaction, a corresponding wrapperobject needs to be opened (using the open API call) for readingor writing before accessing it. The transaction can be terminatedby calling the commit or abort API function. Two points are worthnoting here. First, non-transactional objects retain their modifiedvalues even on transaction aborts; this allows programmers tomakeappropriate decisions when a transaction is aborted. Second, oncean object is opened, it looks like a regular object that can be passedtoother modules and legacy librariesthat arenot transaction-aware.While DSTM’s API can be a little tedious to use, type system en-hancements should simplify the use of DSTM by using a compilerto insert the API calls. 3.1.2 DSTM Implementation DSTM uses a  State  object for each dynamically started transaction.It stores the state of the transaction, which is either ACTIVE,COMMITTED, or ABORTED. All transactional objects that areopened by a transaction have pointers to the  State  object of thattransaction. This is a key feature because it allows a transaction tobe committed or aborted by a single atomic write to its  State  object.Fundamentally, DSTMrelies on two main techniques tosupporttransactions: indirection and object copying. It uses object copyingtokeep theoldversionof theobject around whileitismodifyingthecopy within a transaction. If the transaction is aborted, it discardsthe new version. If the transaction is committed, it replaces the oldversion with the new version. To allow replacing the object underthe covers, it uses indirection.DSTM employs Transactional Memory Objects ( TMObject  ) tointroduce the indirection. Figure 2 shows the fields of a  TMObject  and how they relate to the data. A  Locator   object contains threefields:  State ,  Old Object  , and  New Object  . The  State  field stores apointer to the  State  object of the last transaction that opened theobject for writing. The two  Object   fields point to old and new ver-sions of the data. There is always one current data object that isdetermined by the  State  field. If the  State  field is ACTIVE, a trans-action is currently working on the data pointed to by  New Object  .Since the transaction has not yet committed, the data pointed to by Old Object   is kept in case thetransaction isaborted. When the  State field is ABORTED, a transaction failed the commit, thus the datapointed to by  New Object   is invalid and  Old Object   points to thecurrent version. Finally, when the  State  field is COMMITTED, thedata pointed to by  New Object   is the current version. Figure 3.  Opening a committed  TMObject   in DSTM.Opening a  TMObject   for reading involves finding the currentversion of the object and recording (locally in a per-thread hashtable) the version of the object—if at commit time the version isdetected to have changed, the transaction will abort instead.Opening a  TMObject   for writing is more involved and requiresmodifying the  TMObject  . Figure 3 shows an example. Suppose Transaction 1  has already committed a version of the object in thefigure, and now  Transaction 2  wishes to open that object for writ-ing.  Transaction 2  first creates a new  Locator   object (  Locator 2 ).Then, based on the  State  field in  Locator 1 , it can set the pointersand copy data. If the  State  field is COMMITTED,  Locator 2  setsits  Old Object   pointer to the  Data  pointed to by  Locator 1 ’s  NewObject  , which is the correct version of the data. Then  Locator 2 makes a copy of the data for  Transaction 2  to modify transaction-ally. Similarly, if   Locator 1 ’s  State  field was ABORTED, the sameprocess is run except the correct version of the data is pointed toby  Locator 1 ’s  Old Object  . After  Locator 2  has been created, acompare-and-swap (CAS) operation is used to safely change the TMObject   pointer from  Locator 1  to  Locator 2 . If the CAS fails,another transaction has opened the object for writing while  Loca-tor 2  was being set up; thus, the process of setting up  Locator 2 must be repeated.When a transaction tries to open a  TMObject   for writing andfinds it in ACTIVE state (i.e., currently being modified by anothertransaction), one of these two transactions has to be aborted toresolvetheconflict.Thedecisionabout whichtransactionisabortedis made by the Contention Manager (3.2.4). A transaction can abortany transaction (including itself) by atomically replacing ACTIVEby ABORTED (using CAS) in the  State  object for that transaction.Transactions commit themselves by atomically replacing AC-TIVE with COMMITTED (using CAS) in its  State  object afterchecking to make sure that objects opened for reading are still thesame version. Committing automatically updates the current ver-sion of all objects written during the transaction (since the currentversion for any transactional object is defined by the value of the State  object to which it points). This will (eventually) abort anytransactions that opened those objects for reading.While DSTM is a simple and a pure software method to pro-vide transactional memory semantics to programmers, it comes atthe expense of requiring versioning overhead. This overhead canbecome a significant performance bottleneck, since every open forwritinginvolvesanallocation andcopy of dataanda  Locator  . How-ever, in contrast to a hardware method, DSTM allows for an un-bounded number of transactional locations.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x