Synchronization in Concurrent Algorithms

并发算法中的同步

• 批准号: 8901966
• 负责人: Arthur Bernstein
• 金额: $ 17.78万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-09-01 至 1992-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8901966&HistoricalAwards=false
• 关键词: Synchronization; Concurrent; Algorithms

The objective of the research is to investigate synchronization in concurrent - perhaps distributed - algorithms. Such algorithms involve a number of independent tasks, or transactions, which synchronize with one another periodically. Unfortunately, synchronization impairs performance since tasks must wait for one another. Techniques for improving performance by reducing synchronization will be investigated and the structure of an asynchronous algorithm as it relates to synchronization will be modelled. A major cause for synchronization is the need for concurrent tasks to access shared data. Data is frequently characterized by integrity constraints and it is generally required that these be true in all states viewed by the tasks. The research divides into three related problems. The use of semantics to remove the requirement that updates to shared data be performed atomically will be investigated. A strategy for decomposing updates into smaller units which can be interleaved with the execution of other tasks, hence reducing synchronization delays while maintaining integrity constraints is being studied. The tradeoff between increased concurrency and integrity constraint violation is under study. Relaxing synchronization to the extent of permitting violations but not allowing the state of the data to deviate too far from one in which the constraints hold is being studied. Once again the emphasis is on improving the performance of asynchronous algorithms which access shared data. Finally, the structure of an asynchronous algorithm as it relates to synchronization will be studied to see whether algorithms can be compared on the basis of the amount of synchronization involved.

本研究的目的是研究并发--也许是分布式--算法的同步。这样的算法涉及多个独立的任务或事务，这些任务或事务定期彼此同步。遗憾的是，同步会降低性能，因为任务必须相互等待。将研究通过减少同步来提高性能的技术，并对与同步相关的异步算法的结构进行建模。同步的一个主要原因是需要并发任务来访问共享数据。数据通常以完整性约束为特征，通常要求这些约束在任务查看的所有状态下都是正确的。本研究分为三个相关问题。将研究如何使用语义来消除对共享数据的更新必须以原子方式执行的要求。正在研究一种将更新分解成可以与其他任务的执行交织在一起的较小单元的策略，从而在保持完整性约束的同时减少同步延迟。增加的并发性和违反完整性约束之间的权衡正在研究中。将同步放宽到允许违规的程度，但不允许数据状态偏离正在研究的约束所在的状态太远。重点再次放在提高访问共享数据的异步算法的性能上。最后，将研究与同步相关的异步算法的结构，以查看是否可以根据所涉及的同步量来比较算法。