《云数据管理：挑战与机遇》2.1.3　互斥和仲裁集

互斥和仲裁集

互斥是并发进程访问共享资源时涉及的一个基本概念。互斥是操作系统中的一个重要操作，后来也被扩展到数据库中。互斥可以按照如下方式进行定义：给定一个进程集合和一个单独的资源，开发一种协议，该协议可以确保在同一时间，一个资源只能被一个进程进行排他性访问。针对集中式系统和分布式系统都已经提出了多种解决方案。针对分布式互斥问题的一种简单的集中式解决方案可以设计如下：指定一个进程为协调者，当进程需要访问资源时，发送一个请求消息给协调者。协调者维护一个等待请求队列。当协调者接收一个请求消息时，检查该队列是否为空，如果队列为空，协调者就为请求客户端发送一个回复消息，请求客户端就可以访问共享资源。否则，请求消息就被添加到等待请求队列中。进程在共享资源上执行完成以后，向协调者发送一个释放消息。接收到释放消息以后，协调者从队列中移除请求，然后为其他等待的请求检查队列。该协议已经被Lamport[1978]扩展成分布式协议，很多其他研究人员对该协议进行了优化。

该基本协议的普遍应用需要系统中所有进程的参与。为了克服障碍，Gifford提出了仲裁集的概念。比较重要的发现是任意两个请求都应该有一个共同的进程来充当仲裁者。假定进程pi(pj)从集合qi(qj)中请求许可，其中qi和qi是仲裁集，也可以是系统中所有进程的子集。qi和qj的交集不能为空。例如，包括系统中大部分进程的集合就可以构成一个仲裁集。使用仲裁集，而非系统中的所有进程，基本协议仍然有效，但是有可能出现死锁[Maekawa, 1985]。图2-4a展示了一个包含7个进程的系统，任意一个大于等于4的集合和另外一个大于等于4的集合一定相交，即对于任意两个仲裁集， 每一个仲裁集都包含大部分站点，它们的交集一定是非空的。

在数据库中，仲裁集的概念可以理解成基本的读、写操作，读操作不需要互斥。然而，多个读操作虽然可以并发执行，但是，针对数据的写操作仍需要互斥访问。因此，设计了两种仲裁集：读仲裁集和写仲裁集，其中，两个写仲裁集之间的交集不能为空，一个读仲裁集和一个写仲裁集之间的交集也不能为空，针对两个读仲裁集的交集没有强制性要求。图2-4b展示了一个包含6个进程的系统，写仲裁集是大小为4的任意集合，读仲裁集是大小为3的任意集合。需要注意的是，任意读仲裁集和写仲裁集必须相交，任意两个写仲裁集也必须相交。但是，读仲裁集之间不一定相交，因此，多个读操作可以并行执行。

a）互斥仲裁集                                                          b）读写仲裁集