公开(公告)号：US07594234B1

公开(公告)日：2009-09-22

申请号：US10861729

申请日：2004-06-04

申请人： David Dice

发明人： David Dice

IPC分类号： G06F9/46

CPC分类号： G06F9/526 ,  G06F9/461

摘要： Adaptive modifications of spinning and blocking behavior in spin-then-block mutual exclusion include limiting spinning time to no more than the duration of a context switch. Also, the frequency of spinning versus blocking is limited to a desired amount based on the success rate of recent spin attempts. As an alternative, spinning is bypassed if spinning is unlikely to be successful because the owner is not progressing toward releasing the shared resource, as might occur if the owner is blocked or spinning itself. In another aspect, the duration of spinning is generally limited, but longer spinning is permitted if no other threads are ready to utilize the processor. In another aspect, if the owner of a shared resource is ready to be executed, a thread attempting to acquire ownership performs a “directed yield” of the remainder of its processing quantum to the other thread, and execution of the acquiring thread is suspended.

摘要翻译： 旋转和阻塞互斥中的旋转和阻塞行为的自适应修改包括将旋转时间限制为不超过上下文切换的持续时间。 此外，基于最近的旋转尝试的成功率，旋转与阻塞的频率被限制到期望的量。 作为替代方案，如果旋转不太可能成功，则旋转是绕过的，因为所有者不会发展为释放共享资源，如果所有者被阻塞或旋转本身可能会发生。 在另一方面，旋转的持续时间通常是有限的，但如果没有其他线程准备好利用处理器，则允许更长的旋转。 在另一方面，如果共享资源的所有者准备好被执行，则尝试获得所有权的线程向其他线程执行其处理量子剩余部分的“定向收益”，并且暂停执行获取线程。

公开(公告)号：US20090172327A1

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

申请号：US11967395

申请日：2007-12-31

申请人： Nir N. Shavit ,  David Dice

发明人： Nir N. Shavit ,  David Dice

IPC分类号： G06F12/14 ,  G06F11/14 ,  G06F9/46

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

摘要： A lock-based software transactional memory (STM) implementation may determine whether a transaction's write-set is static (e.g., known in advance not to change). If so, and if the read-set is not static, the STM implementation may execute, or attempt to execute, the transaction as a semi-static transaction. A semi-static transaction may involve obtaining, possibly after incrementing, a reference version value against which to subsequently validate that memory locations, such as read-set locations, have not been modified concurrently with the semi-static transaction. The read-set locations may be validated while locks are held for the locations to be written (e.g., the write-set locations). After committing the modifications to the write-set locations and as part of releasing the locks, versioned write-locks associated with the write-set locations may be updated to reflect the previously obtained, or newly incremented, reference version value.

摘要翻译： 基于锁的软件事务存储器（STM）实现可以确定事务的写入组是否是静态的（例如，事先知道不会改变）。 如果是这样，并且如果读取集不是静态的，则STM实现可以作为半静态事务来执行或尝试执行该事务。 半静态事务可能包括获得（可能在递增之后）参考版本值，随后验证该存储器位置（诸如读取位置）尚未与半静态事务同时修改。 在为要写入的位置（例如，写入位置）保持锁定的同时可以验证读取位置。 在对写入位置进行修改之后并且作为释放锁的一部分，可以更新与写入位置相关联的版本化的写锁定以反映先前获得的或新增加的参考版本值。

公开(公告)号：US20090125548A1

公开(公告)日：2009-05-14

申请号：US11939372

申请日：2007-11-13

申请人： Mark S. Moir ,  Yosef Lev ,  Victor M. Luchangco ,  David Dice

发明人： Mark S. Moir ,  Yosef Lev ,  Victor M. Luchangco ,  David Dice

IPC分类号： G06F17/30

CPC分类号： G06F9/52

摘要： A Scalable NonZero Indicator (SNZI) object in a concurrent computing application may include a shared data portion (e.g., a counter portion) and a shared nonzero indicator portion, and/or may be an element in a hierarchy of SNZI objects that filters changes in non-root nodes to a root node. SNZI objects may be accessed by software applications through an API that includes a query operation to return the value of the nonzero indicator, and arrive (increment) and depart (decrement) operations. Modifications of the data portion and/or the indicator portion may be performed using atomic read-modify-write type operations. Some SNZI objects may support a reset operation. A shared data object may be set to an intermediate value, or an announce bit may be set, to indicate that a modification is in progress that affects its corresponding indicator value. Another process or thread seeing this indication may “help” complete the modification before proceeding.

摘要翻译： 并发计算应用中的可扩展非零指示符（SNZI）对象可以包括共享数据部分（例如，计数器部分）和共享非零指示符部分，和/或可以是SNZI对象的层次结构中的元素， 非根节点到根节点。 软件应用程序可以通过API来访问SNZI对象，该API包括返回非零指示符值的查询操作，以及到达（递增）和离开（递减）操作。 可以使用原子读取 - 修改 - 写入类型操作来执行数据部分和/或指示符部分的修改。 一些SNZI对象可能支持复位操作。 可以将共享数据对象设置为中间值，或者可以设置通告位，以指示正在进行的修改影响其对应的指示符值。 看到此指示的另一个进程或线程可能会在进行之前“帮助”完成修改。

公开(公告)号：US20080148262A1

公开(公告)日：2008-06-19

申请号：US11640018

申请日：2006-12-15

申请人： David Dice

发明人： David Dice

IPC分类号： G06F9/46

CPC分类号： G06F9/466 ,  G06F9/3004 ,  G06F9/30087 ,  G06F9/3851 ,  G06F9/3857 ,  G06F9/3863

摘要： A system that executes a long transaction in a system with limited transactional hardware resources. During operation, the system executes the long transaction in a non transactional mode, which does not use transactional hardware resources. The system defers stores generated during the long transaction so that the stores are not committed to the architectural state of a processor until the transaction is successfully completed. If the long transaction successfully completes, the system commits the long transaction, which involves performing multiple hardware transactions to commit the deferred stores to the architectural state of the processor.

公开(公告)号：US20070198978A1

公开(公告)日：2007-08-23

申请号：US11475604

申请日：2006-06-27

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

IPC分类号： G06F9/46

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

摘要： A computer system includes multiple processing threads that execute in parallel. The multiple processing threads have access to a global environment including i) shared data utilized by the multiple processing threads, ii) a globally accessible register or buffer of version information that changes each time a respective one of the multiple processing threads modifies the shared data, and iii) respective lock information indicating whether one of the multiple processing threads has locked the shared data preventing other processing threads from modifying the shared data. To prevent data corruption, each of the processing threads aborts if a given processing thread detects a change in the version information or another processing thread has a lock on the shared data. This technique is well suited for use in applications such as processing threads that support a high number of reads with a corresponding number of fewer respective writes to shared data.

摘要翻译： 计算机系统包括并行执行的多个处理线程。 所述多个处理线程可以访问全球环境，包括i）所述多个处理线程使用的共享数据，ii）版本信息的全局可访问寄存器或缓冲器，每当所述多个处理线程的相应一个线程修改所述共享数据时， 以及iii）相应的锁定信息，指示多个处理线程中的一个是否锁定了共享数据，防止其他处理线程修改共享数据。 为了防止数据损坏，如果给定的处理线程检测到版本信息的更改或另一个处理线程对共享数据有锁定，则每个处理线程中止。 该技术非常适用于诸如处理支持大量读取的线程的应用程序，其中相应数量的对共享数据的相应数量较少。

公开(公告)号：US06289451B1

公开(公告)日：2001-09-11

申请号：US08844211

申请日：1997-04-18

申请人： David Dice

发明人： David Dice

IPC分类号： H04L900

CPC分类号： H04L63/06 ,  H04L9/0838 ,  H04L9/3236 ,  H04L63/08

摘要： A communication system includes communication devices which communicate during a communication session. During communication session establishment, the devices exchange a session key in an encrypted manner for privacy. When one device has information to transfer to the other device, the one device will append the session key to the information and apply a hash function thereto to generate a hash value, and generate a message packet for transfer to the other device that includes an information portion containing the information and a hash value portion containing the hash value. When the other device receives the message packet, it will append the session key to the information from the information portion of the packet that it receives, and generate a hash value therefrom. If the receiving device determines that the generated hash value corresponds to the hash value received in the message packet, properties of the hash function that is used to generate the hash values enable it to conclude that the message packet was not tampered with during the transfer and that it originated from the one device. The system avoids the necessity of computation-intensive encryption and decryption for message packet transfer during a communication session.

摘要翻译： 通信系统包括在通信会话期间通信的通信设备。 在通信会话建立期间，设备以加密的方式交换会话密钥以进行隐私。 当一个设备具有要传送到其他设备的信息时，一个设备将会将该会话密钥附加到该信息上，并向其中应用散列函数以产生一个散列值，并生成一个消息包，以传送到包含一个信息的另一个设备 包含该信息的部分和包含散列值的散列值部分。 当另一设备接收到消息包时，它会将会话密钥附加到来自其接收到的数据包的信息部分的信息，并从其生成散列值。 如果接收设备确定所生成的散列值对应于在消息包中接收到的散列值，则用于生成散列值的散列函数的属性使得其得出结论：在传送过程中消息包未被篡改，并且 它源于一个设备。 该系统避免了在通信会话期间消息分组传输的计算密集型加密和解密的必要性。

公开(公告)号：US5712997A

公开(公告)日：1998-01-27

申请号：US594594

申请日：1996-01-31

申请人： David Dice

发明人： David Dice

IPC分类号： G06F9/312 ,  G06F9/38 ,  G06F9/30

CPC分类号： G06F9/3865 ,  G06F9/30043 ,  G06F9/3836

摘要： A microprocessor in a computer system processes an instruction stream comprising instructions of a plurality of instruction types including an information retrieval instruction type. The microprocessor comprises a register set, a pending fault flag set, a functional unit, an information retrieval subsystem, and a control subsystem. The register set comprises a plurality of registers, each register for storing information. The pending fault flag set comprises a plurality of pending fault flags each associated with one of said registers, each pending fault flag having selected conditions including a pending fault condition and a no pending fault condition. The functional unit performs processing operations in response to information input thereto. The information retrieval subsystem initiates an information retrieval operation to retrieve of information from said information storage subsystem for storage in a register. The control subsystem controls the other elements of the microprocessor in response to the instructions in the instruction stream. In response to an instruction in the instruction stream of the information retrieval type, the control subsystem enables the information retrieval subsystem to initiate an information retrieval operation, and conditions the pending fault flag associated with said one of said registers to the pending fault condition in response to detection of a fault condition during the information retrieval operation. In response to an instruction in the instruction stream of another type, the control subsystem identifies a selected one of said registers as a source register, and enables information to be transferred from said source register to the functional unit for processing if the pending fault flag associated with said source register is in the no pending fault condition.

摘要翻译： 计算机系统中的微处理器处理包括包括信息检索指令类型的多种指令类型的指令的指令流。 微处理器包括寄存器组，未决故障标志集，功能单元，信息检索子系统和控制子系统。 寄存器组包括多个寄存器，每个寄存器用于存储信息。 待决故障标志集合包括多个等待的故障标志，每个挂起的故障标志各自与所述寄存器之一相关联，每个未决故障标志具有包括待决故障条件和无待命故障条件的选定条件。 功能单元响应输入的信息执行处理操作。 信息检索子系统启动信息检索操作以从所述信息存储子系统检索信息以存储在寄存器中。 控制子系统响应于指令流中的指令控制微处理器的其他元件。 响应于信息检索类型的指令流中的指令，控制子系统使得信息检索子系统启动信息检索操作，并且将与所述寄存器中的所述一个寄存器相关联的未决故障标志响应于待处理故障条件 在信息检索操作期间检测故障状况。 响应于另一类型的指令流中的指令，控制子系统将所选择的一个所述寄存器识别为源寄存器，并且使信息能够从所述源寄存器传送到功能单元以用于处理，如果挂起的故障标志相关联 所述源寄存器处于不等待故障状态。