同步与互斥(一)

简介: 同步与互斥(一)

一. 同步与互斥基本概念

多道程序环境下,进程并发执行,为了协调不同进程之间的相互制约关系,引入** 进程同步** 的概念。

如:计算 1+1 × 3,假设系统产生 加法进程 和 乘法进程 ,由于进程异步性,可能发生先计算加法后计算乘法;

因此需要制定一种机制 约束加法进程在乘法进程执行结束后发生。

临界资源

  • 临界资源:同一时刻仅允许一个进程使用的资源。
  • 如:许多物理设备(打印机,键盘等);被多个进程共享的变量,数据等。

临界区与临界资源:

  • **临界区:**对临界资源的访问,必须互斥进行,每个进程中,访问临界资源的代码段 称为临界区。
  • 访问临界资源的过程:
  • 进入区:检查是否可以进入临界区。如果可以进入,将设置访问临界区标志,阻止其他进程进入。
  • 临界区:访问临界资源的那段代码,又称临界段。
  • 退出区:清除访问临界区的标志。
  • 剩余区:代码中剩余的部分。


同步

  • 亦称直接制约关系,是指为完成某种任务而建立的≥2个进程,由于需要协调它们的运行次序而等待、传递信息产生的制约关系。源于进程之间的合作
  • 例如:进程A通过单缓冲向进程B提供数据。
  • 缓存区empty:B进程阻塞,A进程送入数据 唤醒进程B。
  • 缓冲区full: A进程被阻塞,进程B取走数 唤醒进程A。

互斥

  • 亦称间接制约关系。一个进程A进入临界区使用临界资源时,另一个进程必须等待。进程A退出临界区后,另一进程才允许访问临界资源。
  • 例如:仅有一台打印机的系统中,两个进程A和B。
  • 若进程A需要打印,但是打印机已经被分配给进程B,则进程A阻塞。
  • 进程B释放打印机后,唤醒进程A,从阻塞态变为就绪态。

实现临界区互斥遵循的准则:

为了禁止两个进程同时进入临界区。

  • 空闲让进:临界区空闲,让一个请求进程进入。
  • 忙则等待:已有进程进入临界区,其他请求进程必须等待。
  • 有限等待:请求的进程,保证在有限时间进入临界区,防止进程无限等待。
  • 让权等待(原则上,非必须):进程无法进入临界区,立即释放处理机,防止进程忙等待。

二. 临界区互斥实现方法

2.1 软件实现

进入区设置并检查访问临界区标志,已有进程进入临界区,则通过在进入区循环检查进行等待,进程离开后在退出区修改标记。

算法一:单标志法

设置一个公用整形变量 turn,指示允许进入临界区的进程标号。turn=N,表示允许进程 P(N) 进入临界区;进程退出临界区时,转移临界区使用权,如进程 P(i) 退出临界区,将 turn 置为 j。(i ≠ j)

特点:

  • 每次只允许一个进程进入临界区。
  • 两个进程必须交替进入临界区,若只有两个进程,进程 P(B) 不再进入临界区,则进程 P(A) 从临界区退出后,由于修改后 turn = B,(此时临界区空闲) 进程 P(A) 将不能再次进入临界区。【违背了“空闲让进”原则】


算法二:双标志先检查法

设置布尔型数组 flag[2] ,标记各个进程想进入临界区的意愿,flag[i] = true 表示进程 P(i) 想要进入临界区【i=0 或 1】

  • P(i)进入临界区之前,先检查对方是否想进入临界区;
  • 若 flag[ 1-i ] = true,则 P(i) 进程等待,否则设置 flag[ i ] = true,然后 进入临界区。
  • P(i) 退出临界区时,设置 flag[ i ] = false。


  • 优点:不需要交替进入,可以连续使用。
  • 缺点:可能存在 P(0) 和 P(1)同时进入临界区。
  • 上图中,按照 ①⑤②⑥③⑦ 执行的时候【即检查对方标记后和设置自己的标记前 可能发生进程切换】,出现两个进程都通过检查的情况,同时进入临界区。(违背“忙则等待”原则)。原因在于 检查和设置操作 不是一气呵成的。


算法三:双标志后检查法

基于算法二的机制,采用先设置后检查法,以避免算法二导致量两个进程同时进入临界区的问题。

  • P(i)进入临界区之前,先设置 flag[ i ] = true, 再检查对方是否想进入临界区;
  • 若 flag[ 1-i ] = true,则 P(i) 进程等待,否则直接进入临界区。
  • P(i) 退出临界区时,设置 flag[ i ] = false。


  • 优点:避免了两个进程同时进入临界区的问题。
  • 缺点:上图中,按照 ①⑤②⑥… 执行的时候,出现两个进程 都想要进入临界区 情况,结果都无法进入 临界区。(违背“空闲让进”原则)。

各个进程长期无法访问临界区导致“饥饿”现象。(违背“有限等待”原则)


算法四:Peterson算法

结合算法一和算法三思想,**利用 flag[ ] 解决互斥访问,利用“turn”**解决“饥饿”问题。

  • 进程进入临界区之前,先设置 flag 标志,再设置** turn 标志**【turn 标志设置为对方的,表示对方优先进入。】;
  • 接着 同时检查对方的 flag 和 turn 标志,以保证同时要求进入时候,只允许一个进入。


若检查时候出现冲突:都想要进入,则最后设置 turn 标志【发出“谦让”】的进程等待。最终 turn 指示进入临界区的进程标号。


  • 优点:P[j] 退出后,如果 P[ i ] 不想进入临界区,则设置 flag[ i ] = false(P[ i ] 不会陷入 while 循环),遵循了“空闲等待”,“忙则等待”,“有限等待”。
  • 缺点:未遵循“让权等待”原则,依然不够好

2.2 硬件实现

  • 计算机提供特殊硬件指令,允许对一个字的内容进行检测和修正,或交换两个字的内容。

中断屏蔽方法


硬件指令方法——TestAndSet 指令

硬件指令方法——Swap 指令

** 总结 **


三. 互斥锁

相关文章
|
Linux
【Linux 系统编程】wait函数详解
【Linux 系统编程】wait函数详解
812 0
|
JSON Ubuntu 搜索推荐
【Crow】一款开源C++Web框架的安装与构建
【Crow】一款开源C++Web框架的安装与构建
2788 0
|
8月前
|
Web App开发 安全 数据挖掘
TA446 组织利用 DarkSword 漏洞套件针对 iOS 的定向钓鱼攻击研究
2026年3月,俄APT组织TA446利用泄露的DarkSword iOS漏洞套件,通过伪造大西洋理事会邮件实施定向钓鱼攻击。该攻击依托PAC绕过、内核提权等0day链,实现无文件、低交互的Safari远程入侵,窃取iCloud凭证、钥匙串等敏感数据,并部署GHOSTBLADE与MAYBEROBOT载荷。研究表明,国家级漏洞工具公开化正加速高端移动威胁平民化,亟需构建终端加固、流量检测与行为监控相结合的纵深防御体系。(239字)
909 7
|
存储 人工智能 自然语言处理
构建AI智能体:十七、大模型的幻觉难题:RAG 解决AI才华横溢却胡言乱语的弊病
RAG(检索增强生成)是一种结合信息检索与大型语言模型的技术,旨在解决LLM的幻觉问题。其核心流程包括:离线处理阶段(知识库构建)和在线处理阶段(用户查询应答)。通过将外部知识源转换为向量存入数据库,当用户提问时,系统会检索相关内容并增强提示,再由LLM生成准确答案。RAG技术显著提升了AI在专业领域的可靠性,适用于智能客服、企业知识管理、内容创作等场景。尽管面临检索精度、多模态处理等挑战,RAG仍是AI实用化的重要突破方向。
1524 2
|
6月前
|
人工智能 测试技术
豆包怎么导出 Word?整理写作草稿、表格和办公内容的流程
豆包内容转Word需兼顾格式与审校:短文本可直接复制,含标题/表格/代码者推荐导出Markdown后用DeepShare等工具转换,确保结构完整;所有AI生成内容均须人工核对事实、删冗余、补案例,方可正式交付。
|
Ubuntu Linux 应用服务中间件
Linux使用cpulimit对CPU使用率进行限制
cpulimit是一款简单易用的CPU使用率限制工具,支持对特定程序或整个CPU使用率进行限制。可通过源安装(如`yum`或`apt-get`)或编译安装获取。使用时,可针对程序名、进程号或绝对路径设置CPU占用上限(如`cpulimit -e xmrig -l 60 -b`)。ROOT用户可限制所有进程,普通用户仅限于权限范围内进程。注意,CPU百分比基于实际核心数(单核100%,双核200%,依此类推)。
2214 7
|
机器学习/深度学习 人工智能 算法
乘AIGC浪潮:把握万亿级机遇
AIGC正加速从技术走向产业落地,万亿市场规模催生全链条人才需求。北京、上海政策加码,算力基建完善,2025-2027年成关键窗口期。七大核心岗位——AIGC工程师、大模型训练师、AI工程师等全面爆发,覆盖技术到应用各层级,高薪抢人成常态。工信部认证加持,职业前景广阔,人人皆可入局,抢占AI时代新风口。
959 1
Threejs创建天空和太阳
这篇文章讲解了如何使用Three.js中的Sky组件来创建真实的天空与太阳效果,包括调整天空的颜色、太阳的位置以及实现大气散射等技巧。
1219 3
|
运维 Serverless 云计算
Serverless,云计算3.0阶段
Serverless是一种云计算服务模式,让开发者只需专注于编写业务逻辑代码,无需管理底层基础设施如服务器、存储和网络。相比传统Serverful架构,Serverless降低了运维成本,提高了开发效率,并通过弹性伸缩应对流量峰谷,按实际资源消耗付费,显著降低资源浪费和费用开销。
869 5
Serverless,云计算3.0阶段
|
机器学习/深度学习 计算机视觉 iOS开发
YOLOv11改进策略【模型轻量化】| 替换骨干网络 CVPR-2024 RepViT 轻量级的Vision Transformers架构
YOLOv11改进策略【模型轻量化】| 替换骨干网络 CVPR-2024 RepViT 轻量级的Vision Transformers架构
1224 12