公开(公告)号：US07669015B2

公开(公告)日：2010-02-23

申请号：US11475814

申请日：2006-06-27

申请人： David Dice ,  Ori Shalev ,  Nir N. Shavit

发明人： David Dice ,  Ori Shalev ,  Nir N. Shavit

IPC分类号： G06F12/00

CPC分类号： G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

摘要： 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.

摘要翻译： 本公开描述了使用（例如，读取，修改和写入）相同的共享数据而不会对共享数据造成损坏的多个进程中的每一个进行并行操作的独特方式。 例如，当执行相应的交易时，多个过程中的每个利用与全局计数器或时钟相关联的当前和过去的数据值来确定用于产生相应的交易结果的任何共享变量（通过另一个进程）被修改。 如果相应的进程检测到在处理期间修改了相应进程使用的共享数据，则该进程可以中止并重试事务，而不是通过将与事务相关联的本地维护的结果存储到全局共享的数据空间来导致数据损坏。

公开(公告)号：US20070239943A1

公开(公告)日：2007-10-11

申请号：US11699802

申请日：2007-01-30

申请人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

发明人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

IPC分类号： G06F12/00

CPC分类号： G06F9/466

摘要： 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.

摘要翻译： 本公开描述了多个进程中的每一个并行操作并使用相同的共享数据而不会对共享数据造成损坏的唯一方式。 例如，在提交阶段期间，相应的事务可以尝试增加全局可访问的版本信息变量并存储全局可访问版本信息变量的当前值，用于更新与经修改的数据相关联的版本信息，而不管相关联的尝试是否相应 修改全局可访问版本信息变量的事务成功。 作为替代模式，相应的事务只能读取和存储全局可访问版本信息变量的当前值，而不尝试在此类使用之前更新全局可访问版本信息变量。 在另一个应用中，并行处理环境根据交易的自我中止率实现两种上述模式的组合。

公开(公告)号：US07640402B2

公开(公告)日：2009-12-29

申请号：US11699802

申请日：2007-01-30

申请人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

发明人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

IPC分类号： G06F13/00

摘要： 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.

公开(公告)号：US08028133B2

公开(公告)日：2011-09-27

申请号：US11699802

申请日：2007-01-30

申请人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

发明人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

IPC分类号： G06F13/00

CPC分类号： G06F9/466

摘要： 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.

摘要翻译： 本公开描述了多个进程中的每一个并行操作并使用相同的共享数据而不会对共享数据造成损坏的唯一方式。 例如，在提交阶段期间，相应的事务可以尝试增加全局可访问的版本信息变量并存储全局可访问版本信息变量的当前值，用于更新与经修改的数据相关联的版本信息，而不管相关联的尝试是否相应 修改全局可访问版本信息变量的事务成功。 作为替代模式，相应的事务只能读取和存储全局可访问版本信息变量的当前值，而不尝试在此类使用之前更新全局可访问版本信息变量。 在另一个应用中，并行处理环境根据交易的自我中止率实现两种上述模式的组合。

公开(公告)号：US20080005112A1

公开(公告)日：2008-01-03

申请号：US11442870

申请日：2006-05-30

申请人： Nir N. Shavit ,  Ori Shalev

发明人： Nir N. Shavit ,  Ori Shalev

IPC分类号： G06F17/30

CPC分类号： G06F9/526

摘要： 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.

摘要翻译： 用于协调对数据对象的共享访问的方法包括在第一线程拥有数据对象上的锁定的会话期间，代表所有其他线程从多个线程的第一线程向数据对象应用修改操作。 每个修改操作对应于通过相应线程记录在与数据对象相关联的日志中的相应条目。 该方法还可以包括针对第二线程预测第二线程在数据对象上请求的特定操作的结果。 可以使用对应于尚未应用于数据对象的修改操作的日志条目来预测结果。 此外，该方法包括在会话期间以非阻塞方式从第二线程执行一个或多个其他操作，其中至少一个其他操作取决于预测结果。

公开(公告)号：US08219762B1

公开(公告)日：2012-07-10

申请号：US10918062

申请日：2004-08-13

申请人： Nir N. Shavit ,  Ori Shalev

发明人： Nir N. Shavit ,  Ori Shalev

IPC分类号： G06F12/00 ,  G06F13/00

CPC分类号： G06F12/0815

摘要： 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 “owning” process completes its operations on the memory location during the predetermination duration of time, the ownership of the memory location by the “owning” process is terminated and the memory location becomes accessible to other processes.

摘要翻译： 用于共享存储器多处理器系统的同步技术涉及在预定的有限持续时间内获取所请求的存储器位置的独占所有权。 如果“拥有”过程不可预测地延迟，则所请求的存储器位置的所有权在预定的持续时间之后到期，从而使得存储器位置可被其他进程访问，并且要求先前的“拥有”进程在其存储器位置重试其操作 。 如果“拥有”过程在时间的预定持续时间期间在存储器位置上完成其操作，则终止“拥有”过程对存储器位置的所有权，并且存储器位置对于其他进程可访问。

公开(公告)号：US08037476B1

公开(公告)日：2011-10-11

申请号：US11263439

申请日：2005-10-31

申请人： Nir N. Shavit ,  Ori Shalev

发明人： Nir N. Shavit ,  Ori Shalev

IPC分类号： G06F9/46 ,  G06F7/38 ,  G06F7/00 ,  G06F13/00

CPC分类号： G06F9/526 ,  G06F2209/522 ,  G06F2209/523

摘要： 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.

摘要翻译： 地址级基于日志的同步的方法包括尝试获取对象上的锁的线程。 如果其锁尝试失败，则线程在同步日志中记录针对共享数据对象的数据访问操作，并等待来自锁拥有线程的通知，指示所记录的操作是否成功。 如果锁定尝试成功，则锁拥有线程对共享数据对象执行数据访问操作，并在同步日志中的其他线程记录的请求之间进行仲裁，应用不与其他修改操作冲突的请求中记录的修改， 并拒绝发生冲突的请求。 主机向接受请求的日志记录线程发送成功通知，以及对请求被拒绝的日志记录线程的失败通知。

公开(公告)号：US08261024B1

公开(公告)日：2012-09-04

申请号：US11263414

申请日：2005-10-31

申请人： Nir N. Shavit ,  Ori Shalev

发明人： Nir N. Shavit ,  Ori Shalev

IPC分类号： G06F12/00 ,  G06F13/00 ,  G06F13/28

CPC分类号： G06F9/526 ,  G06F2209/522 ,  G06F2209/523

摘要： 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.

摘要翻译： 在访问共享数据对象的多个线程中，一个线程在给予共享数据对象的数据访问的给定会话期间获取“主”状态以在竞争线程的请求中进行仲裁。 在会话期间，主线程解决由其他线程访问或修改共享数据对象所产生的任何冲突，只有主线程可以在会话期间对共享数据对象应用修改。 同时，在会话期间，非主线程可以对共享数据对象执行非阻塞读操作。 在后续会话中，不同的线程可能获取主状态。

公开(公告)号：US07496726B1

公开(公告)日：2009-02-24

申请号：US11110910

申请日：2005-04-18

申请人： Daniel S. Nussbaum ,  Victor M. Luchangco ,  Mark S. Moir ,  Ori Shalev ,  Nir N. Shavit

发明人： Daniel S. Nussbaum ,  Victor M. Luchangco ,  Mark S. Moir ,  Ori Shalev ,  Nir N. Shavit

IPC分类号： G06F12/00 ,  G06F13/00 ,  G06F13/28

CPC分类号： G06F9/526 ,  G06F9/30087 ,  G06F9/466 ,  G06F9/5016

摘要： 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.

摘要翻译： 一种用于控制事务性存储器系统中冲突事务之间争用的系统。 在操作期间，系统接收到访问高速缓存行的请求，然后确定高速缓存状态中的高速缓存状态中的高速缓存行是否已被使用，该缓存状态与请求不兼容。 如果是这样，系统确定请求是否来自处于礼貌模式的处理器。 如果这是真的，系统将拒绝访问高速缓存行的请求，并继续执行现有事务。

公开(公告)号：US07412572B1

公开(公告)日：2008-08-12

申请号：US10965336

申请日：2004-10-14

申请人： Nir N. Shavit ,  Ori Shalev

发明人： Nir N. Shavit ,  Ori Shalev

IPC分类号： G06F12/00

CPC分类号： G06F9/526 ,  G06F2209/523

摘要： 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.

摘要翻译： 使用瞬态阻塞同步支持实现多位置读取，单位置写入操作。 多位置读取单位置写入操作涉及首先获取待修改的存储器位置的瞬时所有权，然后获取至少一个其他存储器位置的瞬时所有权，其内容被读取并用于首先修改存储器位置 获得了