Oracle America, Inc.

Sun Microsystems, Inc.

Ori Shalev

Nir N Shavit

Mark S Moir

David Dice

Daniel Nussbaum

Victor M Luchangco

From among a plurality of threads accessing a shared data object, one thread acquires a 'master' status to arbitrate among the requests of competing threads during a given session of data access to the shared data object. During the session, the master thread resolves any conflicts resulting from attempts to access or modify the shared data object by other threads, and only the master thread may apply modifications to the shared data object during the session. Meanwhile, during the session, non-master threads may perform non-blocking read operations on the shared data object. During a subsequent session, a different thread may acquire master status.

Address level synchronization of shared data

A synchronization technique for shared-memory multiprocessor systems involves acquiring exclusive ownership of a requested memory location for a predetermined, limited duration of time. If an 'owning' process is unpredictably delayed, the ownership of the requested memory location expires after the predetermined duration of time, thereby making the memory location accessible to other processes and requiring the previous 'owning' process to retry its operations on the memory location. If the &#x201c;owning&#x201d; process completes its operations on the memory location during the predetermination duration of time, the ownership of the memory location by the &#x201c;owning&#x201d; process is terminated and the memory location becomes accessible to other processes.

Computer system and method for leasing memory location to allow predictable access to memory location

A method for coordinating shared access to data objects comprises applying modification operations to a data object from a first thread of a plurality of threads on behalf of all the other threads during a session in which the first thread owns a lock on the data object. Each modification operation corresponds to a respective entry recorded in a log associated with the data object by a respective thread. The method may further comprise predicting, for a second thread, a result of a particular operation requested by the second thread on the data object. The result may be predicted using log entries corresponding to modification operations that have not yet been applied to the data object. In addition, the method includes performing one or more other operations in a non-blocking manner from the second thread during the session, where at least one other operation is dependent on the predicted result.

Predictive log synchronization

A method of address-level log-based synchronization comprises a thread attempting to acquire a lock on an object. If its lock attempt fails, a thread logs, at a synchronization log, data access operations directed at the shared data object, and waits for a notification from the lock-owning thread indicating whether the logged operations succeeded. If its lock attempt succeeds, the lock-owning thread performs data access operations on the shared data object, and arbitrates among requests logged by other threads in the synchronization log, applying the modifications logged in the requests that do not conflict with other modification operations, and rejecting the requests that conflict. The master sends a success notification to the logging threads whose requests were accepted, and a failure notification to the logging threads whose requests were rejected.

Address level log-based synchronization of shared data

The present disclosure describes a unique way for each of multiple processes to operate in parallel and use the same shared data without causing corruption to the shared data. For example, during a commit phase, a corresponding transaction can attempt to increment a globally accessible version information variable and store a current value of the globally accessible version information variable for updating version information associated with modified data regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful. As an alternative mode, a corresponding transaction can merely read and store a current value of the globally accessible version information variable without attempting to update the globally accessible version information variable before such use. In yet another application, a parallel processing environment implements a combination of both aforementioned modes depending on a self-abort rate of the transaction.

Globally incremented variable or clock based methods and apparatus to implement parallel transactions

A scalable first-in-first-out queue implementation adjusts to load on a host system. The scalable FIFO queue implementation is lock-free and linearizable, and scales to large numbers of threads. The FIFO queue implementation includes a central queue and an elimination structure for eliminating enqueue-dequeue operation pairs. The elimination mechanism tracks enqueue operations and/or dequeue operations and eliminates without synchronizing on the FIFO queue implementation.

Scalable and lock-free first-in-first-out queue implementation

Producers and consumer processes may synchronize and transfer data using a shared data structure. After locating a potential transfer location that indicates an EMPTY status, a producer may store data to be transferred in the transfer location. A producer may use a compare-and-swap (CAS) operation to store the transfer data to the transfer location. A consumer may subsequently read the transfer data from the transfer location and store, such as by using a CAS operation, a DONE status indicator in the transfer location. The producer may notice the DONE indication and may then set the status location back to EMPTY to indicate that the location is available for future transfers, by the same or a different producer. The producer may also monitor the transfer location and time out if no consumer has picked up the transfer data.

Scalable method for producer and consumer elimination

The present disclosure describes a unique way for each of multiple processes to operate in parallel using (e.g., reading, modifying, and writing to) the same shared data without causing corruption to the shared data. For example, each of multiple processes utilizes current and past data values associated with a global counter or clock for purposes of determining whether any shared variables used to produce a respective transaction outcome were modified (by another process) when executing a respective transaction. If a respective process detects that shared data used by respective process was modified during a transaction, the process can abort and retry the transaction rather than cause data corruption by storing locally maintained results associated with the transaction to a globally shared data space.

Methods and apparatus to implement parallel transactions

A system for controlling contention between conflicting transactions in a transactional memory system. During operation, the system receives a request to access a cache line and then determines if the cache line is already in use by an existing transaction in a cache state that is incompatible with the request. If so, the system determines if the request is from a processor which is in a polite mode. If this is true, the system denies the request to access the cache line and continues executing the existing transaction.

Controlling contention via transactional timers among conflicting transactions issued by processors operating in insistent or polite mode

A multiple-location read, single-location write operation is implemented using transient blocking synchronization support. The multiple-location read, single-location write operation involves first acquiring transient ownership of a memory location to be modified and then acquiring transient ownership of at least one other memory location, the contents of which are read and used to modify the memory location first acquired.

Growing community of inventors

Giv′at-Shmuel, Israel

Ori Shalev