Towards a Study of Synchronization: Abstractions, Implementations, and Translations

尽管有各种各样的同步问题及其广泛的解决方案，但关于同步的性质和分类的一些基本问题仍然没有得到回答。这是因为观察到，任何同步都必然涉及参与进程之间的某种仲裁。提出了作为仲裁基础的程序“排名”的概念，并确定了一个计算程序排名的基本机制，称为“排名器”。为了执行任何类型的仲裁，由排序器模块计算的等级应满足某些要求。通过识别这些属性，可以为排序器模块获得四个不同的规范；这四个排序器形成一个层次结构。基于同步问题与可用于解决该问题的最弱排序器之间的对应关系，得到了同步问题的分类。这个分类包含了文献中提出的另一个分类。将考虑在不同架构上实现排名器的问题，该项目旨在设计跨不同架构转换程序的算法。

In spite of the wide variety of synchronization problems and their broad-ranging solutions, some fundamental questions regarding the nature and classification of synchronization have remained unanswered. Led by the observation that any synchronization necessarily involves some kind of arbitration among the participating processes. The notion of the "rank" of a process that serves as the basis for arbitration has been formulated, and an underlying mechanism, called the "ranker", that computes the ranks for the processes has been identified. In order to carry out any kind of arbitration, the ranks that are computed by the ranker module should satisfy certain requirements. By identifying these properties, four different specifications are obtained for the ranker module; these four rankers form a hierarchy. Based on the correspondence between a synchronization problem and the weakest ranker that can be used to solve it, a classificiation of synchronization problems is obtained. This classification subsumes the other classification proposed in the literature. The problem of implementing rankers on various architectures will be considered and the project intends to devise algorithms for translating programs across different architectures.