Distributed Algorithms and Applications for Allocating Resources Competed for by Process Groups

分布式资源分配是构建分布式系统的重要内容。关于这一问题已经有了大量的研究。随着计算机网络的发展，各种分布式协同应用成为必然。对于分布式协作应用，协作进程可以看作是一个组。当一个以上的组分别在网络中执行它们的工作时，属于不同组的进程可能会竞争一个资源。资源分配不慎可能会导致群体之间的僵局或群体的饥饿。为了解决这类问题，我们定义了一个新的问题--进程组资源分配问题，并给出了几种分布式求解算法。在本课题中，我们在总结前人研究成果的基础上，首次提出了一种使用无障碍压缩技术的有效分配方法，使得压缩过程不会受到影响，即等待时间比没有压缩时更长。通过该技术可以提高资源的总体利用效率。然后，我们研究了如何通过使用让步策略来减少请求资源的进程的平均等待时间。也就是说，一个进程可以取消一个保留的资源并重新保存另一个资源，以便另一个进程使用前者。此外，我们还提出了一种新的可并发执行任务的组之间资源分配的通用模型。最后，我们讨论了这些算法是否可以用于某些应用，并考虑了如何实现移动电话的信道分配算法，作为未来的任务，我们计划将改进的挤压方法和特许权方法引入到群之间的资源分配模型中。

Distributed Resource Allocation is an important for construction of distributed systems. There are a lot of researches on this problem. With the progress of computer networks, a variety of distributed cooperative applications are necessary. For distributed cooperative applications, cooperative processes can be considered as a group. When more than one group perform their works respectively in a network, processes belonging to different groups may compete for a resource. Careless allocation of resources may lead to deadlock between groups or starvation of a group. In order to solve such problem, we have define a newproblem, resource allocation to process group, and given several distributed algorithms for solving the problem. In this Project, based on research results in the past, we first proposed an efficient allocation method using unobstructed squeezing technique, such that the squeezed processes will not be affected i.e.to wait longer than without squeezing. The total efficiency of using the resources can be increased by the technique. Then we studied how to reduce the average waiting time of processes which request a resource by using a concession policy. That is, a process may cancel a reserved resource and rereserve another one, in order for another process to use the former. Moreover, we propose a new general model for resource allocation among groups which may execute a task concurrently. Finally, we discussed if those algorithms can be used for some applications, and considered how to implement an algorithm for allocating channels of mobile phones.As a future task, we plan to incorporate the developed squeezing method and concession method into the model for resource allocation among groups.