PRAM模型应用于同步机制的研究

发布时间：2018-05-08 05:35

本文选题：分布式互斥 + 令牌　；参考：《南京邮电大学》2014年硕士论文

【摘要】：随着网络技术的不断发展，分布式系统得到了广泛的研究与应用。分布式系统采用并行计算模型。PRAM模型作为并行模型的一种，本文主要就PRAM模型应用于分布式同步机制的问题进行研究。同步问题是分布式系统设计时的关键问题，它保证并发进程正确的访问临界资源。由于分布式系统中网络带宽有限，且临界资源的数目是固定的，因此研究设计网络负载轻、临界资源利用率高的分布式同步算法具有重要的意义。本文首先介绍了一些分布式典型算法，并分析比较了它们的优缺点。基于此提出一种新的基于令牌的同步算法，新的算法中引入了优先级和选举算法的概念，令牌不再按照逻辑环的顺序循环传递，，而是根据节点优先级传递，降低了同步延迟。分布式算法中，本文详细介绍了Maekawa算法。Maekawa算法首次提出了仲裁集的概念，利用不同的仲裁集内存在相同的节点，可以使得请求消息能够通过不同的集合快速寻找到令牌持有者。最后，本文将旅行商问题映射到网络通信的问题上，利用蚁群算法找出网络通信的最优化路线，能有效的提高进程间的通信效率。
[Abstract]:With the development of network technology, distributed system has been widely studied and applied. The parallel computing model, pram model, is used as a parallel model in distributed system. This paper mainly studies the application of PRAM model to distributed synchronization mechanism. Synchronization is a key problem in the design of distributed systems, which ensures that concurrent processes access critical resources correctly. Because the network bandwidth is limited and the number of critical resources is fixed in distributed systems, it is of great significance to study and design distributed synchronization algorithms with light network load and high critical resource utilization. In this paper, some typical distributed algorithms are introduced, and their advantages and disadvantages are analyzed and compared. Based on this, a new token based synchronization algorithm is proposed. In the new algorithm, the concepts of priority and election algorithm are introduced. The token is no longer transferred in the order of logical loop, but according to the node priority, the synchronization delay is reduced. In the distributed algorithm, Maekawa algorithm. Maekawa algorithm is the first time to introduce the concept of arbitration set. Using the same nodes in different arbitration sets, request messages can quickly find the token holder through different sets. Finally, this paper maps the traveling salesman problem to the problem of network communication, and uses ant colony algorithm to find out the optimal route of network communication, which can effectively improve the communication efficiency between processes.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP338.8

【相似文献】