Efficient Concurrent Data Structures

高效的并发数据结构

• 批准号: RGPIN-2015-05080
• 负责人: Ellen, Faith
• 金额: $ 3.64万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=650087
• 关键词: Efficient; Concurrent; Data; Structures

A data structure is a way to organize certain information in a computer, together with methods for accessing and updating that information. Concurrent data structures are data structures that can be accessed by many processes at the same time. Libraries of concurrent data structures make the design of concurrent software substantially easier.******This research is concerned with the design of efficient, provably correct, concurrent data structures, especially ones that continue to work correctly even if processes crash while accessing them. Some of the data structures are concurrent versions of standard sequential data structures, such as search trees. Others have been defined to help processes synchronize with one another. For example, an atomic snapshot object allows a process to update one entry of an array or take a snapshot of all its entries at the same time. ******One aspect of this research is to develop ways to make the design of correct and efficient concurrent data structures easier. We have developed a technique for creating a large class of concurrent tree-based data structures and proved that any data structure created using this technique is automatically correct and fault-tolerant. We are working on extending it to other classes of concurrent data structures. A big issue for concurrent data structures is how to reclaim space that is no longer being used. We are studying ways of improving existing mechanisms and are developing new mechanisms that work well with concurrent data structures designed using our technique.******Another aspect of this research is to prove lower bounds on the amount of a resource (such as time or space) needed for specific concurrent data structures. This enables us to determine when a data structure is optimal. It can also help us find innovative ways to improve performance.**

数据结构是一种在计算机中组织某些信息的方法，以及访问和更新这些信息的方法。 并发数据结构是可以被多个进程同时访问的数据结构。 并发数据结构库使并发软件的设计变得相当容易。本研究关注的是设计高效的、可证明正确的并发数据结构，特别是那些即使进程在访问它们时崩溃也能继续正确工作的数据结构。一些数据结构是标准顺序数据结构的并发版本，例如搜索树。还定义了其他一些方法，以帮助进程彼此同步。例如，原子快照对象允许进程更新数组的一个条目或同时对其所有条目进行快照。* 本研究的一个方面是开发方法，使正确和有效的并发数据结构的设计更容易。我们已经开发出一种技术，用于创建一个大类的并发树为基础的数据结构，并证明，使用这种技术创建的任何数据结构是自动正确和容错。我们正在努力将其扩展到其他类的并发数据结构。 并发数据结构的一个大问题是如何回收不再使用的空间。我们正在研究改进现有机制的方法，并正在开发与使用我们的技术设计的并发数据结构良好工作的新机制。这项研究的另一个方面是证明特定的并发数据结构所需的资源量（如时间或空间）的下限。这使我们能够确定何时数据结构是最佳的。它还可以帮助我们找到创新的方法来提高性能。**