个人网站asp,做网站运营的简历,微信开放平台帐号,wordpress 侧边栏短代码文章目录 一、互斥问题及分布式系统的特性二、分布式互斥算法1. 集中互斥算法调用流程优缺点 2. 基于许可的互斥算法#xff08;Lamport 算法#xff09;调用流程优缺点 3. 令牌环互斥算法调用流程优缺点 三、三种算法对比 在分布式系统中#xff0c;多个应用服务可能会同时… 文章目录 一、互斥问题及分布式系统的特性二、分布式互斥算法1. 集中互斥算法调用流程优缺点 2. 基于许可的互斥算法Lamport 算法调用流程优缺点 3. 令牌环互斥算法调用流程优缺点 三、三种算法对比 在分布式系统中多个应用服务可能会同时访问同一个资源导致互斥问题的出现。例如在分布式数据库环境中多个事务可能同时尝试对同一行数据加锁导致锁争抢影响系统性能。为了避免互斥现象并保证数据的一致性引入了分布式锁机制。而支撑分布式锁的理论基础就是分布式互斥算法。
一、互斥问题及分布式系统的特性
以现实生活中的例子来类比假设有两个小孩想玩同一个玩具但玩具只能由一个小孩使用另一个小孩必须等待。这种情况类似于计算机系统中的互斥问题
共享资源玩具只能由一个进程访问。竞争该资源的进程必须遵循一定的顺序。若资源被占用其他进程必须等待。
在单机环境下进程互斥问题可以通过线程同步等方式解决。但在分布式系统中由于各个进程部署在不同的服务器上互斥问题变得更为复杂必须考虑以下特性
互联网特性分布式系统中的服务器通过网络连接网络延迟、丢包等问题可能影响互斥操作。没有统一时钟不同服务器的时钟不同步导致进程无法准确判断资源请求的先后顺序。服务器和网络可能故障当某个服务器或进程发生故障其他服务器需要感知并进行相应处理。 二、分布式互斥算法
针对分布式系统的互斥问题研究者提出了不同的互斥算法。这些算法适用于不同的场景例如某些算法适合小规模系统而另一些则更适用于高并发环境。主要包括
1. 集中互斥算法
集中互斥算法的核心思想是引入一个全局协调者类似于老师管理玩具的使用由协调者统一管理资源访问请求。 调用流程
进程向协调者发送资源访问请求。协调者根据请求时间戳排队并允许最先请求的进程访问资源。进程访问资源后向协调者发送释放通知。协调者允许下一个进程访问资源。 优缺点
优点实现简单协调者能有效控制资源的访问。缺点 协调者可能成为系统瓶颈影响性能。协调者的单点故障会导致系统不可用。 2. 基于许可的互斥算法Lamport 算法
在集中互斥算法中是通过协调者记录先后顺序的而在 Lamport 算法中每个节点进程都会维护一个逻辑时钟当系统启动时所有节点上的进程都会对这个时钟进行初始化每当节点进程向其他节点进程发起临界资源访问申请的时候就会将这个逻辑时间戳加 1。
即该算法不依赖单个协调者而是由各个进程相互协商资源访问权。 调用流程 进程向所有其他进程发送资源访问请求REQUEST。其他进程收到请求后将其加入本地队列并根据逻辑时钟更新顺序。当请求进程收到所有进程的许可REPLY后即可访问资源。访问完成后进程向所有等待的进程发送释放消息RELEASE其他进程更新队列。 优缺点
优点 解决了分布式系统时钟不同步的问题。适用于进程较少的场景。 缺点 需要进行大量消息传输通信开销较大。资源请求多时系统响应可能变慢。 3. 令牌环互斥算法
令牌环算法类似于小孩们围成一圈轮流传递一个令牌Token拿到令牌的孩子才能玩玩具。
如下图令牌环互斥算法中的所有节点进程构成一个环结构每个节点进程都有一个唯一 ID 作为标识且都会记录对应前驱节点和后继节点的地址。
令牌作为访问临界资源的许可证会按照一定方向顺时针、逆时针在节点进程之间传递收到令牌的节点进程有权访问临界资源访问完成后将令牌传送给下一个进程若拿到令牌的节点进程不需要访问临界资源则直接把令牌传递给下一个节点进程。
调用流程
进程形成一个逻辑环并按固定方向传递令牌。持有令牌的进程可以访问资源。访问完成后进程将令牌传递给下一个进程。若进程不需要访问资源则直接传递令牌。
优缺点
优点 令牌唯一避免竞争冲突。进程不会长时间等待保证公平性。 缺点 令牌丢失时系统需要恢复令牌增加复杂度。进程数量变化时需要重构令牌环。即使没有进程访问资源令牌仍在传递造成资源浪费。 三、三种算法对比
算法优点缺点适用场景消息复杂度故障恢复能力集中互斥算法实现简单便于管理协调者可能成为瓶颈单点故障风险高进程数量较少资源访问请求不频繁低低协调者故障导致不可用基于许可的算法无单点故障保证公平性通信开销大进程数量多时性能下降进程较少通信代价可接受的场景高中进程故障会影响队列排序令牌环算法令牌唯一访问公平令牌丢失影响系统进程变化需重构环资源访问频繁系统规模较小低中需要令牌恢复机制
在实际应用中分布式锁如 Zookeeper、Redis 分布式锁通常结合了这些算法的思想以提高系统的性能和可靠性。选择合适的互斥方案可以有效提升分布式系统的稳定性和数据一致性。 参考 《分布式原理与实践-崔皓》
