Synchronization in 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.