Patent Publication Number: US-7711909-B1

Title: Read sharing using global conflict indication and semi-transparent reading in a transactional memory space

Description:
BACKGROUND 
   The present invention relates to implementations of transactional memory. More specifically, the present invention relates to validating transactional operations in accordance with a global indication of read-write conflicts in a transactional memory space while supporting semi-transparent shared reading of the transactional memory space. 
   Current multi-processor architectures do not support synchronization primitives that can atomically access multiple memory locations. However, software transactional memory implementations have been proposed to provide atomic access to multiple memory locations in a multiple processor environment. Transactional memory may be implemented with software transactional memory or a hybrid of hardware and software transactional memory. Regardless of whether the transactional memory is implemented with software transactional memory or software transactional memory that uses hardware transactional memory support, current implementations do not allow concurrent transactions to read common memory locations without causing each other to abort if one of the transactions modifies one of the common memory locations. 
   Most software transactional memory algorithms utilize an ownership mechanism, which guarantees that a transaction “owns” a memory location in order to safely update it without conflicting with other transactions. While multiple transactions are typically prevented from accessing a memory location for write purposes to avoid corruption of data, multiple transactions are typically permitted to simultaneously read from the same location without aborting each other. Allowing multiple transactions to read a same location without aborting each other is referred to as read sharing. In addition to supporting read sharing, implementations should guarantee the atomicity of a transaction. Before a transaction can commit, it must determine that no other transaction has modified a location that it accesses; this is called “validation.” In many cases, it is necessary to repeatedly validate a transactional read during execution of a transaction to avoid incorrect behavior as a result of observing inconsistent data. 
   There are two techniques typically employed that enable read sharing in current software transactional memory algorithms: 1) transparent reading and 2) non-transparent reading. These techniques typically employ structures, referred to as ownership records, to indicate ownership of memory locations represented with the ownership record. With “transparent reading,” a transaction does not acquire ownership on a location before reading it but instead records identifiers of the ownership records that represent locations read by the transaction. In software transactional memory, implementations that use transparent reading (also known as “invisible reading”), a transaction which modifies a memory location is not aware of the currently executing transactions that have read or are reading this location. For a transaction to verify that previously read locations have not changed during execution of the transaction (i.e., validate the reading of the locations), the transaction rereads the ownership records. If the transaction has read locations represented by numerous ownership records, then the validation procedure of rereading all of the ownership records will be expensive. The validation procedure is utilized to avoid incorrect behavior like infinite loops and divide by zero, due to inconsistent read values. 
   With “non-transparent reading” (also known as “visible reading”), transactions that read locations do not iterate over the locations or representative ownership records to validate their read accesses. Instead, a transaction that modifies a location can determine the identity of each concurrent transaction that has read the location (e.g., with a linked list of references for the reader transactions) and explicitly aborts each of those transactions. Aborting all of the reader transactions is significantly expensive. In addition, maintaining and managing the list of reader transactions introduces complexity and is often expensive. 
   SUMMARY 
   It has been discovered that globally indicating read-write conflicts and semi-transparent read sharing in a transactional memory space allows for more expedient validation. Semi-transparent read sharing with global indication of read-write conflicts reduces validation time for transactions. Without being aware of particular transactions, a transaction can determine that a read-write conflict will occur with some transaction. The transactions that began execution prior to the modification are responsible for determining whether the write results in inconsistent data, and aborting themselves accordingly. Those transactions that reach a validation point without the occurrence of any read-write conflicts during their execution can validate quickly. If a read-write conflict occurs prior to a transaction reaching a validation point, then the transaction performs a validation operation that includes determining whether the write has polluted its particular readings. Hence, transactions are provided a quick avenue for validation without substantial overhead of tracking particular transactions that read locations. 
   These and other aspects of the described invention will be better described with reference to the Description of the Drawing(s) and accompanying Figures. 

   
     BRIEF DESCRIPTION OF THE DRAWING(S) 
       FIG. 1  is an exemplary diagram that depicts semi-transparent read sharing of memory locations in an environment with concurrently executing transactions. 
       FIG. 2  depicts an exemplary timeline for the operations of the transactions of  FIG. 1 . 
       FIG. 3  depicts an exemplary flowchart for a transaction reading and validating. 
       FIG. 4  depicts a flowchart for a transaction to indicate a read-write conflict if appropriate. 
       FIG. 5  depicts an exemplary ownership record. 
       FIGS. 6A-6B  depict implementations of semi-transparent reading with ownership records.  FIG. 6A  is an exemplary depiction of a transaction semi-transparently reading a location and updating an ownership record.  FIG. 6B  is an exemplary depiction of a transaction utilizing semi-transparent reading with an ownership record to avoid aborting transactions. 
       FIG. 7  depicts an exemplary computer system according to realizations of the invention. 
   

   The use of the same reference symbols in different drawings indicates similar or identical items. 
   DESCRIPTION OF THE DRAWING(S) 
   The description that follows includes exemplary systems, methods, techniques, instruction sequences and computer program products that embody techniques of the present invention. However, it is understood that the described invention may be practiced without these specific details. For instance, particular procedures are described with reference to a compare-and-swap type operation, although other operations may be utilized to check consistency of one or more values atomically. Also, exemplary illustrations refer to an ownership record, although various structures and mechanisms can be employed to track reading transactions semi-transparently. In other instances, well-known protocols, structures and techniques have not been shown in detail in order not to obscure the invention. 
   A transaction is a collection of operations to be executed atomically. Semi-transparent read sharing facilitates a reduced validation process and minimal overhead. In semi-transparent read sharing, a modifying transaction is aware that there are some active reading transactions that have read or are currently reading from the location to be modified, but the modifier transaction is not aware of the exact identities of the active reading transactions. Knowledge that some active reading transactions has read or is reading the location to be modified is sufficient for the modifier transaction to correctly predict that the modification will cause a read-write conflict. The modifier transaction globally indicates that the read-write conflict has occurred or will occur. Hence, the modifier transaction is able to notify all active transaction that a read-write conflict has occurred that may corrupt their data, without being aware of their particular identities and without the accompanying complexity of maintaining their particular identities. Moreover, the modifier transaction is not responsible for aborting all of the transactions affected by the modification. Instead, those reading transactions that determine they are affected by the read-write conflicts are responsible for aborting themselves to avoid using inconsistent data. With the global indication of a read-write conflict, transactions are able to quickly validate their reads if a read-write conflict has not occurred during execution of the transaction. Otherwise, the transactions expend resources iterating over all of the locations or representations of locations read by the transaction. Hence, the cost of validating in an environment with multiple concurrently executing transactions is significantly reduced with the quicker validation as well as reduced complexity with management of less information 
     FIG. 1  is an exemplary diagram that depicts semi-transparent read sharing of memory locations in an environment with concurrently executing transactions. Transactions  101 A- 101 C access memory locations  105 A- 105 D. The memory locations  105 A- 105 D are respectively locations A-D. The transaction  101 A (TXN 1 ) reads memory locations  105 A and  105 D. The transaction  101 A also writes to memory location  105 C. The transaction  101 B (TXN 2 ) reads memory locations  105 A,  105 B, and  105 D. The transaction  101 C (TXN 3 ) writes to the memory location  105 C. 
     FIG. 2  depicts an exemplary timeline for the operations of the transactions of  FIG. 1 . Timelines  201 ,  203 , and  205  respectively indicate occurrence of operations for the transactions  101 A- 101 C. According to the exemplary timelines, transactions  101 A and  101 B read memory location  105 A concurrently. The transaction  101 A writes to the memory location  105 C while the transaction  101 B reads memory location B. The transactions  105 A and  105 B then concurrently read from memory location  105 D. Subsequent to the transactions  101 A- 101 B reading the memory location  105 D, the transaction  101 C writes to the memory location  105 D. 
   Referring to  FIG. 1 , transaction  101 C updates a global indication of read-write conflicts  105  to indicate the read-write conflict with transactions  101 A and  101 B caused by the modification to the memory location  105 D. Since none of the transactions read the memory location  105 C, the transaction  101 A has no read-write conflicts to indicate. 
     FIG. 3  depicts an exemplary flowchart for a transaction reading and validating. At block  301 , a read operation is encountered for one or more locations by an active transaction. At block  303 , the active transaction indicates that the locations are being read without identifying itself. For example, transaction  101 A updates a flag or increments a counter for the memory location  105 A, perhaps stored in the memory location  105 A. If memory locations  105 A and  105 D are collectively represented with a structure, then the transaction increments a counter for the structure. At block  305 , the active transaction reads the locations. A validation process begins at block  307 . Although not illustrated, a number of operations may occur between blocks  305  and  307  (e.g., reading and/or writing to other memory locations, performing calculations, etc.). At block  307 , it is determined, by checking a global indication of read-write conflicts, whether any read-write conflicts have occurred since the locations were read by the active transaction. If conflicts have occurred, then control flows to block  309 . If no conflicts have occurred, then control flows to block  315 . 
   At block  315 , the active transaction continues to execute, or perhaps commits. Since there have been no occurrences of read-write conflicts, a transaction can be confident that locations read by the active transaction have not been modified. For example, if transaction  101 B begins validating prior to the write performed by the transaction  101 C, then the transaction  101 B will quickly validate since there have been no read-write conflicts. 
   At block  309 , it is determined if any of the read-write conflicts that have occurred affect the validating transaction. If the validating transaction is not affected by the read-write conflicts, then control flows to block  315 . If the validating transaction is affected by the read-write conflicts that have occurred, then control flows to block  311 . At block  311 , the validating transaction aborts itself. For example, if the transaction  101 B begins validation after the write by transaction  101 C, the transaction  101 B iterates over memory locations  105 A,  105 B, and  105 D (assuming they are not collectively represented). When the transaction  101 B inspects the memory location  105 D (or its representation), then the transaction  101 B will discover that the transaction  101 C has write ownership and has or will modify the memory location  105 D. Hence, the previous read of the memory location  105 D by the transaction  101 C is stale or corrupt. 
     FIG. 4  depicts a flowchart for a transaction to indicate a read-write conflict if appropriate. At block  401 , a transaction encounters a write operation for one or more locations. At block  403 , it is determined if any other active transactions have read the location to be modified. If the modifying transaction determines that other transactions have read the location to be modified, then control flows to block  405 . If the modifying transaction determines that no other transactions have read the location to be modified, then control flows to block  407 . 
   At block  405 , the modifying transaction globally indicates occurrence of a read-write conflict. Control flows from block  405  to block  407 . 
   At block  407 , the transaction modifies the one or more locations. 
   Referring to  FIG. 1 , the transaction  101 A writes to the memory location  105 C without updating the global indication of read-write conflicts  103 . The transaction  101 C, however, determines that some transactions have read the memory location  105 D, although the transaction  101 C is not aware which transactions have read the memory location  105 D. Therefore, the transaction  101 C updates the global read-write conflicts indication  103  to indicate occurrence of a read-write conflict. 
   While the flow diagram shows a particular order of operations performed by certain realizations of the invention, it should be understood that such order is exemplary (e.g., alternative realizations may perform the operations in a different order, combine certain operations, overlap certain operations, perform certain operations in parallel, etc.). 
   Although the indications of write ownership and indications that some transactions have read a memory location may be embedded within the memory location being read or modified, implementations may utilize representative structures. For example, ownership records may be associated with one or more memory locations. Write ownership is acquired over the ownership record, and hence the locations associated with the ownership record. In addition, the indication of reading transactions may be incorporated into ownership records. 
     FIG. 5  depicts an exemplary ownership record. A memory location  501 B is represented by an ownership record  503 A. A memory location  501 C is represented by an ownership record  503 C. An ownership record  503 B represents memory locations  501 A and  501 D. Exemplary details of the ownership record  503 B are depicted. Details of the ownership records  503 A and  503 C are not depicted, but are similar to the ownership record  503 B, if not the same. The ownership record  503 B is depicted as including a writer field  509 , and a read-counter field  511 . The writer field  509  indicates a transaction that most recently held or currently holds write ownership over the ownership record. The transaction may write to any one or more of the memory locations represented by the ownership record. The read-counter  511  indicates a number of transactions that have read at least one of the memory locations represented by the ownership record  503 B. Whether a transaction reads A, D, or both A and D, the transaction will increment the read-counter  511 . To access an ownership record, a transaction utilizes the address of the location to be modified. For example, a transaction applies a hash function to the target address of a write operation. The hash of the address is used to locate the corresponding ownership record. In another example, the ownership records are collectively maintained as a data structure with each entry incorporating an identifier for the particular record. The ownership record depicted in  FIG. 5  is meant to aid in understanding the invention and not meant to be limiting upon the invention. Implementations may utilize other structures or mechanisms for semi-transparent reading. For example,  FIG. 5  depicts an array, although a hash table may be implemented with each entry keyed off a hash of the represented memory location(s). In addition, instead of a writer identifier, an ownership record may indicate a time value. Furthermore, the functionality for maintaining an ownership record may be modularized in any of a variety of ways. For example, separate processes may be responsible for maintaining each of the fields of the ownership record. 
     FIGS. 6A-6B  depict implementations of semi-transparent reading with ownership records.  FIG. 6A  is an exemplary depiction of a transaction semi-transparently reading a location and updating an ownership record. A transaction  607  (TXN 2 ) reads memory locations  605 A and  605 D. The memory locations  605 A and  605 D are respectively represented by ownership records  603 A and  603 B. Prior to reading the memory location  605 A, the transaction  607  records the identity of the previous writer (TXN 0 ) and increments the read-counter in the ownership record  603 A from 2 to 3. Although the example describes recording a writer identifier, other techniques may be utilized, such as recording a previously written timestamp. Instead of recording the writer field, the transaction may keep a snapshot of the ownership record right after the read-counter update. The ownership record  603 A now indicates that three transactions have read or are reading at least one of the memory locations represented by the ownership record  603 A. Likewise, prior to reading the memory location  605 D, the transaction  607  records the identity of the previous writer and increments the read-counter in the ownership record  603 B from 0 to 1. At this point, the transaction  607  is the only transaction reading the memory location  605 D. When the transaction  607  attempts to validate, if a read-write conflict has occurred, then the transaction  607  will read the current values in the writer fields of the ownership records  603 A and  603 B and compare them against the previously recorded values of the writer fields. If there has been any change, then the transaction  607  aborts. Otherwise, the transaction continues to execute or commits. Upon termination of the transaction  607  (i.e., whether the transaction  607  commits or aborts), the transaction  607  decrements the read-counter in the ownership records  603 A and  603 B. With the global read-write conflict counter, a transaction can validate all locations it has read by simply checking that the global read-write conflict counter has not changed since the transaction began. In the common case, the global read-write conflict counter will not have changed, so the overhead associated with rereading all of the memory locations or representations of the memory locations (the long validation procedure) can be avoided. If the counter has changed, this does not mean the transaction must abort, simply that it must use the long validation procedure. Furthermore, the transaction can use the new value of the global read-write conflict counter to allow future validation in the same transaction to quickly validate. 
   The following is example pseudo-code for a validate procedure. 
   Validate( ) 
   { 
   if (&lt;Transactoin status&gt;==Aborted)
         return false       

   else {
         currentRWCounter=read global RWConflictsNum&gt;;   if (&lt;Transaction snapshot of RWConflictsNum&gt;==currentRWCounter) return true   else {
           &lt;Transaction snapshot of RWConflictsNum&gt;==currentRWCounter;   bool readValid=VerifyReads( );   if (!readValid)&lt;Set transaction status to Aborted&gt;;   return readsValid;   
           }
 
}
       

   In the above code, a global read-write conflict indicator is implemented as the shared variable RWConflictsNum. As illustrated by the pseudo-code, the transaction re-reads the global read-write conflict indicator (unless its status is already aborted in which case it just returns false), and returns true if the value read is the same as its old snapshot of the counter. Otherwise, it saves the new value as its old snapshot of the counter, and validates the read using the long validation procedure, as described above. This technique guarantees that transactions do not need to do the long validation procedure if there were no read-write conflicts between the last time the transaction read the shared counter and the validation time. The exemplary code can simply return true in such cases because a transaction causing a validation process to fail must first change the shared RWConflictsNum counter value. Therefore, if the counter was not changed, the long read validation procedure can be safely skipped. The RWConflictsNum counter is subject to the ABA problem, and therefore it should be assured that it is of sufficient size. Also, bounded timestamps may be utilized to avoid the ABA problem. 
     FIG. 6B  is an exemplary depiction of a transaction utilizing semi-transparent reading with an ownership record to avoid aborting transactions. At a time  1 , a transaction  611  (TXN 1 ) identifies itself in the ownership record  603 A. For example, the transaction  611  writes a transaction identifier, a hash of a transaction identifier, etc., into the writer field of the ownership record  603 A. Although examples have been described that write the identity of the writer into the ownership record, other techniques may be utilized to indicate modification of the memory location or acquisition of write ownership. For example, the writing transaction may write a timestamp into the field instead of a transaction identifier. At a time  2 , the transaction  607  accesses the read-counter field of the ownership record to determine if the write operation will cause a read-write conflict. Since the read-counter indicates a 3, then a read-write conflict will be caused by the write operation. A non-zero read-counter indicates that a read-write conflict will occur, unless the writing transaction has incremented the read-counter to read the memory location as part of its own read operation (i.e., a read-counter of 1, indicates that the writing transaction is the only transaction that has read the memory location(s) to be modified). If the writing transaction has incremented the read-counter, then it ignores itself (no read-write conflict with itself) and does not update the global read-write conflict counter. Hence, at a time  3 , the transaction  611  increments a global read-write conflict counter  601 . At a time  4 , the transaction  611  writes to the memory location  605 A. 
   In the above description, a reading transaction is responsible for decrementing the read-counter when it terminates, and a writing transaction acquires write ownership for an ownership record by writing its identifier in the ownership record. In another technique, a writing transaction resets the read-counter when it acquires the write ownership as well as writing its identifier into the ownership record. A reading transaction, however, decrements the read-counter only if no writing transaction acquired ownership since the reading transaction incremented the read-counter. If multiple writing transactions acquire write ownership on the same ownership record, one after the other, then only the first writer increments the global read-write conflict counter. Only the first writing transaction will increment the global read-write conflict counter, because the read-counter remains zero until a new reading transaction increments the read-counter. Hence, the frequency of modifying a global conflict indicator is reduced. 
   Semi-transparent reading may consume extra overhead for conflicting write operations due to the compare-and-swap (CAS) operation employed when changing the shared RWConflictsNum counter. While this extra cost will probably be negligible compared to the benefit of the quick validate procedure in transactions that perform a relatively large number of reads, the extra cost might slow down short transactions that do not use the Validate function frequently. Note however, that the new technique can live together safely with the old transparent reads technique, as long as the two types of transactions do not share the same ownership records. Hence, in large systems, which use a software transactional memory mechanism for multiple types of data structures, semi-transparent reading may be employed for the data structures which might benefit from it. Furthermore, this overhead exists only if there is someone concurrently reading from the location being modified, and therefore usually there is also a benefit in that case. 
   With semi-transparent reading, a double benefit can be gained if a writing transaction waits some time before getting the write ownership on an ownership record, which has already been read or is being read by other transactions. Implementing the writing transaction to wait, not only might save the abortion (and therefore the retrying) of the conflicting reading transactions, but it might also prevent performance of some long validation procedures by non-conflicting reading transactions (since getting write ownership of an unowned ownership record does not change the global counter). 
   The described invention may be provided as a computer program product, or software, that may include a machine-readable medium having stored thereon instructions, which may be used to program a computer system (or other electronic devices) to perform a process according to the present invention. A machine readable medium includes any mechanism for storing or transmitting information in a form (e.g., software, processing application) readable by a machine (e.g., a computer). The machine-readable medium may include, but is not limited to, magnetic storage medium (e.g., floppy diskette); optical storage medium (e.g., CD-ROM); magneto-optical storage medium; read only memory (ROM); random access memory (RAM); erasable programmable memory (e.g., EPROM and EEPROM); flash memory; electrical, optical, acoustical or other form of propagated signal (e.g., carrier waves, infrared signals, digital signals, etc.); or other types of medium suitable for storing electronic instructions. 
     FIG. 7  depicts an exemplary computer system according to realizations of the invention. A computer system  700  includes a processor unit  701  (possibly including multiple processors, a single threaded processor, a multi-threaded processor, a multi-core processor, etc.). The computer system  700  also includes a system memory  707 A- 707 F (e.g., one or more of cache, SRAM DRAM, RDRAM, EDO RAM, DDR RAM, EEPROM, etc.), a system bus  703  (e.g., LDT, PCI, ISA, etc.), a network interface  705  (e.g., an ATM interface, an Ethernet interface, a Frame Relay interface, etc.), and a storage device(s)  709 A- 709 D (e.g., optical storage, magnetic storage, etc.). Realizations of the invention may include fewer or additional components not illustrated in  FIG. 7  (e.g., video cards, audio cards, additional network interfaces, peripheral devices, etc.). The processor unit  701 , the storage device(s)  709 A- 709 D, the network interface  705 , and the system memory  707 A- 707 F are coupled to the system bus  703 . The system memory  707 A- 707 F embodies a transactional memory that implements semi-transparent reading. The transaction memory may be implemented with hardware transactional memory, software transactional memory, or a hybrid of hardware and software transactional memory. An exemplary description of software transactional memory can be found in published U.S. patent application Ser. No. 10/621,072 entitled “SOFTWARE TRANSACTIONAL MEMORY FOR DYNAMICALLY SIZABLE SHARED DATA STRUCTURES,” naming as inventors Mark S. Moir, Victor Luchangco, and Maurice Herlihy, filed on Jul. 16, 2003. An exemplary description of hybrid transactional memory can be found in published U.S. patent application Ser. No. 10/915,502 entitled “HYBRID HARDWARE/SOFTWARE TRANSACTIONAL MEMORY,” naming as an inventor Mark S. Moir, filed on Aug. 10, 2004. 
   While the invention has been described with reference to various realizations, it will be understood that these realizations are illustrative and that the scope of the invention is not limited to them. Many variations, modifications, additions, and improvements are possible. More generally, realizations in accordance with the present invention have been described in the context of particular realizations. Functionality may be separated or combined in blocks differently in various realizations of the invention or described with different terminology. These and other variations, modifications, additions, and improvements may fall within the scope of the invention as defined in the claims that follow.