【分布式理论9】分布式协同:分布式系统进程互斥与互斥算法

文章目录

    • 一、互斥问题及分布式系统的特性
    • 二、分布式互斥算法
      • 1. 集中互斥算法
        • 调用流程
        • 优缺点
      • 2. 基于许可的互斥算法(Lamport 算法)
        • 调用流程
        • 优缺点
      • 3. 令牌环互斥算法
        • 调用流程
        • 优缺点
    • 三、三种算法对比

在分布式系统中,多个应用服务可能会同时访问同一个资源,导致互斥问题的出现。例如,在分布式数据库环境中,多个事务可能同时尝试对同一行数据加锁,导致锁争抢,影响系统性能。为了避免互斥现象,并保证数据的一致性,引入了分布式锁机制。而支撑分布式锁的理论基础,就是分布式互斥算法。

一、互斥问题及分布式系统的特性

以现实生活中的例子来类比,假设有两个小孩想玩同一个玩具,但玩具只能由一个小孩使用,另一个小孩必须等待。这种情况类似于计算机系统中的互斥问题:

  • 共享资源(玩具)只能由一个进程访问。
  • 竞争该资源的进程必须遵循一定的顺序。
  • 若资源被占用,其他进程必须等待。

在单机环境下,进程互斥问题可以通过线程同步等方式解决。但在分布式系统中,由于各个进程部署在不同的服务器上,互斥问题变得更为复杂,必须考虑以下特性:

  1. 互联网特性:分布式系统中的服务器通过网络连接,网络延迟、丢包等问题可能影响互斥操作。
  2. 没有统一时钟:不同服务器的时钟不同步,导致进程无法准确判断资源请求的先后顺序
  3. 服务器和网络可能故障:当某个服务器或进程发生故障,其他服务器需要感知并进行相应处理。

 

二、分布式互斥算法

针对分布式系统的互斥问题,研究者提出了不同的互斥算法。这些算法适用于不同的场景,例如,某些算法适合小规模系统,而另一些则更适用于高并发环境。主要包括:

1. 集中互斥算法

集中互斥算法的核心思想是引入一个全局协调者(类似于老师管理玩具的使用),由协调者统一管理资源访问请求。

在这里插入图片描述

调用流程
  1. 进程向协调者发送资源访问请求。
  2. 协调者根据请求时间戳排队,并允许最先请求的进程访问资源。
  3. 进程访问资源后,向协调者发送释放通知。
  4. 协调者允许下一个进程访问资源。

在这里插入图片描述

优缺点
  • 优点:实现简单,协调者能有效控制资源的访问。
  • 缺点
    • 协调者可能成为系统瓶颈,影响性能。
    • 协调者的单点故障会导致系统不可用。

 

2. 基于许可的互斥算法(Lamport 算法)

在集中互斥算法中是通过协调者记录先后顺序的,而在 Lamport 算法中,每个节点进程都会维护一个逻辑时钟,当系统启动时,所有节点上的进程都会对这个时钟进行初始化,每当节点进程向其他节点进程发起临界资源访问申请的时候,就会将这个逻辑时间戳加 1。

即该算法不依赖单个协调者,而是由各个进程相互协商资源访问权。

 

调用流程
  1. 进程向所有其他进程发送资源访问请求(REQUEST)。
  2. 其他进程收到请求后,将其加入本地队列,并根据逻辑时钟更新顺序。
  3. 当请求进程收到所有进程的许可(REPLY)后,即可访问资源。
  4. 访问完成后,进程向所有等待的进程发送释放消息(RELEASE),其他进程更新队列。

在这里插入图片描述

 

优缺点
  • 优点
    • 解决了分布式系统时钟不同步的问题。
    • 适用于进程较少的场景。
  • 缺点
    • 需要进行大量消息传输,通信开销较大。
    • 资源请求多时,系统响应可能变慢。

 

3. 令牌环互斥算法

令牌环算法类似于小孩们围成一圈,轮流传递一个令牌(Token),拿到令牌的孩子才能玩玩具。

如下图令牌环互斥算法中的所有节点进程构成一个环结构,每个节点进程都有一个唯一 ID 作为标识,且都会记录对应前驱节点和后继节点的地址。

令牌作为访问临界资源的许可证,会按照一定方向(顺时针、逆时针)在节点进程之间传递,收到令牌的节点进程有权访问临界资源,访问完成后将令牌传送给下一个进程;若拿到令牌的节点进程不需要访问临界资源,则直接把令牌传递给下一个节点进程。
在这里插入图片描述

调用流程
  1. 进程形成一个逻辑环,并按固定方向传递令牌。
  2. 持有令牌的进程可以访问资源。
  3. 访问完成后,进程将令牌传递给下一个进程。
  4. 若进程不需要访问资源,则直接传递令牌。
优缺点
  • 优点
    • 令牌唯一,避免竞争冲突。
    • 进程不会长时间等待,保证公平性。
  • 缺点
    • 令牌丢失时,系统需要恢复令牌,增加复杂度。
    • 进程数量变化时,需要重构令牌环。
    • 即使没有进程访问资源,令牌仍在传递,造成资源浪费。

 

三、三种算法对比

算法优点缺点适用场景消息复杂度故障恢复能力
集中互斥算法实现简单,便于管理协调者可能成为瓶颈,单点故障风险高进程数量较少,资源访问请求不频繁低(协调者故障导致不可用)
基于许可的算法无单点故障,保证公平性通信开销大,进程数量多时性能下降进程较少,通信代价可接受的场景中(进程故障会影响队列排序)
令牌环算法令牌唯一,访问公平令牌丢失影响系统,进程变化需重构环资源访问频繁,系统规模较小中(需要令牌恢复机制)

在实际应用中,分布式锁(如 Zookeeper、Redis 分布式锁)通常结合了这些算法的思想,以提高系统的性能和可靠性。选择合适的互斥方案,可以有效提升分布式系统的稳定性和数据一致性。

 

参考:
《分布式原理与实践-崔皓》

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/967868.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【车载项目】 systemui下拉负一屏界面,通过语音输入:“中文模式/英文模式“,会闪现一下负一屏下层的画面

1、背景 【操作步骤】负一屏界面,语音输入:“中文模式/英文模式” 【预期结果】显示正常 【实际结果】 会闪现一下负一屏下层的文字 【发生概率】必现 systemui下拉负一屏界面,通过语音输入:“中文模式/英文模式”,会…

CSS 渐变效果详解——线性渐变与径向渐变

在现代前端开发中,CSS 渐变被广泛应用于网页背景、按钮、图形等元素的渲染。相较于使用图片,实现渐变可以减少资源请求,同时也更灵活。今天我们主要介绍两种常用的渐变类型:线性渐变(Linear Gradient)与径向…

【愚公系列】《Python网络爬虫从入门到精通》001-初识网络爬虫

标题详情作者简介愚公搬代码头衔华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,CSDN商业化专家,阿里云专家博主,阿里云签约作者,腾讯云优秀博主&…

如何借鉴GitHub开源项目进行LabVIEW开发

在设备开发过程中,许多开发者选择借鉴GitHub等平台上的开源项目,特别是当目标程序没有LabVIEW版本时。比如,在本例中,我们看到一个开源的Micro-Manager项目,它主要使用Java、C、Python等编程语言。对于LabVIEW开发者来…

大前端之前端开发接口测试工具postman的使用方法-简单get接口请求测试的使用方法-简单教学一看就会-以实际例子来说明-优雅草卓伊凡

大前端之前端开发接口测试工具postman的使用方法-简单get接口请求测试的使用方法-简单教学一看就会-以实际例子来说明-优雅草卓伊凡 背景 前端开发接口请求,调试,联调,接入数据,前端必不可少工具,postman是一个非常好…

CSS3+动画

浏览器内核以及其前缀 css标准中各个属性都要经历从草案到推荐的过程,css3中的属性进展都不一样,浏览器厂商在标准尚未明确的情况下提前支持会有风险,浏览器厂商对新属性的支持情况也不同,所有会加厂商前缀加以区分。如果某个属性…

Docker Compose介绍及安装使用MongoDB数据库详解

在现代容器化应用部署中,Docker Compose是一种非常实用的工具,它允许我们通过一个docker-compose.yml文件来定义和运行多容器应用程序。然而,除了Docker之外,Podman也提供了类似的工具——Podman Compose,它允许我们在…

防火墙是什么?详解网络安全的关键守护者

当今信息化时代,企业和个人在享受数字生活带来的便利时,也不可避免地面对各种潜在的风险。防火墙作为网络安全体系中的核心组件,就像一道牢不可破的防线,保护着我们的数据和隐私不受外界威胁的侵害。那么防火墙是什么?…

畅游Diffusion数字人(16):由音乐驱动跳舞视频生成

畅游Diffusion数字人(0):专栏文章导航 前言:从Pose到跳舞视频生成的工作非常多,但是还没有直接从音乐驱动生成的工作。最近字节跳动提出了MuseDance,无需复杂的动作引导输入(如姿势或深度序列),从而使不同专业水平的用户都能轻松进行灵活且富有创意的视频生成。 目录 贡…

机器学习常用包matplotlib篇(一)简单图像绘制

前言 Matplotlib 是支持 Python 语言的开源绘图库,简单且完善。 一、环境配置 1.环境设置 在 Notebook 环境绘图时,需先运行 %matplotlib inline 命令,将绘制图形嵌入当前页面。在桌面环境绘图,无需上述命令,而是在…

深入理解指针初阶:从概念到实践

一、引言 在 C 语言的学习旅程中,指针无疑是一座必须翻越的高峰。它强大而灵活,掌握指针,能让我们更高效地操作内存,编写出更优化的代码。但指针也常常让初学者望而生畏,觉得它复杂难懂。别担心,本文将用通…

如何利用DeepSeek开源模型打造OA系统专属AI助手

利用DeepSeek开源模型打造OA系统专属AI助手,可以显著提升办公效率,增强信息检索和管理能力。 注册与登录DeepSeek平台 访问DeepSeek官网 访问DeepSeek的官方网站DeepSeek。使用电子邮件或手机号码注册账号并登录。 获取API Key 登录DeepSeek平台&am…

jupyter notebook中3种读图片的方法_与_图片翻转(上下翻转,左右翻转,上下左右翻转)

已有图片cat.jpg 相对于代码的位置,可以用./cat.jpg进行读取。 下面是3种读图片的方法。 1.python读图片-pillow 图片文件不适合用open去读取 用open读图片,易引发UnicodeDecodeError: gbk codec cant decode byte 0xff in position 0: illegal multib…

软考高级《系统架构设计师》知识点(一)

计算机硬件 校验码 码距:就单个编码A:00而言,其码距为1,因为其只需要改变一位就变成另一个编码。在两个编码中,从A码到B码转换所需要改变的位数称为码距,如A:00要转换为B:11,码距为2。一般来说,…

【原创精品】基于Springboot3+Vue3的学习计划管理系统

大家好,我是武哥,最近给大家手撸了一个基于SpringBoot3Vue3的学习计划管理系统,可用于毕业设计、课程设计、练手学习,系统全部原创,如有遇到网上抄袭站长的,欢迎联系博主~ 项目演示视频 https://www.bili…

从零到一:我的元宵灯谜小程序诞生记

缘起:一碗汤圆引发的灵感 去年元宵节,我正捧着热腾腾的汤圆刷朋友圈,满屏都是"转发锦鲤求灯谜答案"的动态。看着大家对着手机手忙脚乱地切换浏览器查答案,我突然拍案而起:为什么不做一个能即时猜灯谜的微信…

RAG 在智能答疑中的探索

一、背景 得物开放平台是一个把得物能力进行开放,同时提供给开发者提供 公告、应用控制台、权限包申请、业务文档等功能的平台。 面向商家:通过接入商家自研系统。可以实现自动化库存、订单、对账等管理。 面向ISV :接入得物开放平台&#…

Flutter编译问题记录

问题: 运行出现以下报错 Launching lib/main.dart on macOS in debug mode... Warning: CocoaPods not installed. Skipping pod install. CocoaPods is a package manager for iOS or macOS platform code. Without CocoaPods, plugins will not work on iOS or …

长安汽车发布“北斗天枢2.0”计划,深蓝汽车普及全民智驾

2月9日,长安汽车智能化战略“北斗天枢2.0”计划暨深蓝汽车全场景智能驾驶解决方案发布会在重庆盛大召开。此次发布会标志着长安汽车正式迈入智能化战略的新纪元,携手众多“中国智驾合伙人”,共同开启全民智驾元年。 发布会上,长安…

Java--集合(理论)

目录 一、collection collection常用方法 1.List(可以存在重复元素) 迭代器 迭代器的概念 注意事项 例子 1.ArrayList 特点 2.LinkedLIst 特点 3.Vector 特点 2.Set(无重复元素) 1.HashSet 特点 2.Linkedhashset&…