同步与互斥(一)

一. 同步与互斥基本概念

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

如:计算 1+1 × 3,假设系统产生 加法进程 和 乘法进程 ,由于进程异步性,可能发生先计算加法后计算乘法;
因此需要制定一种机制 约束加法进程在乘法进程执行结束后发生。

临界资源

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

临界区与临界资源:

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

联想截图_20240720160150.png

同步

  • 亦称直接制约关系,是指为完成某种任务而建立的≥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) 将不能再次进入临界区。【违背了“空闲让进”原则

联想截图_20240720180129.png

算法二:双标志先检查法

设置布尔型数组 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

联想截图_20240720180257.png

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

算法三:双标志后检查法

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

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

联想截图_20240720180413.png

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

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

算法四:Peterson算法

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

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

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

联想截图_20240720180925.png
联想截图_20240720181213.png联想截图_20240720181253.png

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

2.2 硬件实现

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

中断屏蔽方法

联想截图_20240720182218.png

硬件指令方法——TestAndSet 指令

联想截图_20240720182306.png

硬件指令方法——Swap 指令

联想截图_20240720182439.png
** 总结 **
联想截图_20240720182451.png

三. 互斥锁

联想截图_20240720182826.png
联想截图_20240720182749.png

相关推荐

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 20:34:04       138 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 20:34:04       152 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 20:34:04       128 阅读
  4. Python语言-面向对象

    2024-07-20 20:34:04       140 阅读

热门阅读

  1. CentOS7中的yum命令不可用,网络不可达

    2024-07-20 20:34:04       24 阅读
  2. HTML5的离线存储

    2024-07-20 20:34:04       25 阅读
  3. 牛客周赛51:小红走矩阵(二分+bfs)

    2024-07-20 20:34:04       29 阅读
  4. 设计模式--外观模式

    2024-07-20 20:34:04       26 阅读
  5. Kylin Cube Designer:数据洞察的魔法画布

    2024-07-20 20:34:04       21 阅读
  6. opencv读写路径包含中文的文件

    2024-07-20 20:34:04       27 阅读
  7. 探索Web世界:WebKit的地理位置API

    2024-07-20 20:34:04       31 阅读
  8. OpenCV从基础到入门(基于python)

    2024-07-20 20:34:04       23 阅读
  9. 运维 | Linux 系统中 MySQL 的安装与使用记录

    2024-07-20 20:34:04       24 阅读
  10. GPT-4o 与 GPT-4o Mini:两者的区别和特点

    2024-07-20 20:34:04       30 阅读