OS_同步与互斥

2024-07-04：操作系统同步与互斥学习笔记

并发的进程或者程序在执行的时候会失去封闭性，也就是说如果有两个程序分别地区使用一个共享的资源，可能会导致每一次运行的结果都不一样

原因就是我们没有保护程序a和程序b都要去访问的这个共享资源x

9.1 同步互斥的基本概念

9.1.1 同步关系

相互制约的关系就是同步，同步通俗一点理解就是它们进程之间执行的时候要有一个次序

9.1.2 互斥关系

间接相互制约的关系就称为互斥关系,eg.打印机

9.1.3 临界资源

• 在一段时间内只允许一个进程访问的资源，称为临界资源（或独占资源）
• 对于临界资源的共享，各进程之间应该采用互斥方式

“生产者和消费者模型”
counter+ +

首先把变量放到寄存器里面
register1 = counter;
接下来对寄存器进行一个自增
register1 = register1 + 1;
再把结果返回到counter里
counter = register1;

counter- -

首先把变量放到寄存器里面
register2 = counter;
接下来对寄存器进行一个自减
register2 = register2 - 1;
再把结果返回到counter里
counter = register2;

解决办法：把counter当做临界资源处理，令进程互斥地访问变量counter（后面会学到同步机制）

9.1.4 临界区

不管是硬件临界资源还是软件的临界资源，多个进程必须互斥地访问

这些区本质都是代码

• 进入区
• 临界区
• 退出区
• 剩余区

9.1.5 同步机制应遵循规则

• 空闲让进

无进程处于临界区时，表明临界区资源空闲，应允许一个请求进入临界区的进程立即进入自己的临界区，有效利用资源。

• 忙则等待

已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问

• 有限等待

对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，避免陷入”等死“状态

• 让权等待

进程不能进入自己的临界区时，应立即释放处理机(CPU)，以免进程陷入”忙等“状态

9.2 软件同步机制

9.2.1 单标志法

• 设置一公用整型变量来标明是否有进程在临界中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志
• 单标志法设置一个公用整型变量turn，指示允许进入临界区的进程编号，turn=0时允许进程P0进入临界区
• turn=1时允许进程P1进入临界区，退出临界区将临界区使用权赋予另一个进程（Pi推出临界区时，令turn=j）

两个进程必须交替进入临界区，若一个进程不再进入临界区，则另一个进程也无法进入临界区，违背了“空闲让进”准则

9.2.2 双标志先检查法

双标志先检查法设置一个布尔型数组flag[2]，用来标记各个进程想进入临界区的意愿，flag[i]=true，表示Pi想进入临界区。

• Pi进入临界区前，先检查对方是否进入临界区，若想，则等待
• 否则，将flag[i]设置为true后，再进入临界区
• 当Pi退出临界区时，将flag[i]设置为false

• while循环相当于红绿灯机制
• 设置对方的flag相当于改对方的红绿灯
• 但由于两个进程都是先检查flag[先看红绿灯]，初始时均为false[均为绿灯]，所以可能两个进程同时通过红绿灯，一起进入临界区

9.2.3 双标志后检查法

双标志后检查法会检查对方的标志再设置自己的，这俩操作无法一气呵成，于是两个进程可能同时进入临界区；所以想出了后检查法，先设置自己的标志，再检查对方的标志，若对方标志位true则等待；否则进入临界区

9.2.4 peterson算法

peterson算法结合了单标志法和双标志后检查法的思想，利用flag[]解决互斥访问问题，在利用turn解决饥饿问题。

若双方都争着进入临界区，则可让进程将进入临界区的机会让给对方。
每个进程进入临界区之前，设置自己的flag标志，在设置允许进入turn标志，之后，再同时检测对方的flag和turn，以保证双方同时要求进⼊临界区时，只允许⼀个进程进入

没有做到让权等待

9.3 硬件同步机制

软件解决各个进程互斥进入临界区的问题有难度，而且有很大的局限性，所以计算机提供一些特殊的硬件指令来解决问题

9.3.1 关中断

(1) 关中断的定义

• 关中断在计算机组成原理里面接触过，它指的是去修改CPU中PSW这个寄存器里面的一位，这一位会去控制现在CPU会不会去相应中断，这个中断只能挡住可屏蔽中断，不可屏蔽中断挡不住
• 操作系统里面进程的调度都是依赖中断去实现的，比如时钟中断
• 有进程再临界区执行期间，计算机系统关中断，从而不会引发调度，也就不会有进程或线程切换

(2) 关中断的缺点

• 滥用终端会导致严重后果
• 关中断时间过长，会影响系统效率
• 关中断方法不适用于多CPU系统，在一个处理器上关中断不能防止进程在其他处理器上执行相同临界代码

9.3.2 Test-and-Set 指令(TS指令)

TS指令可以看作一个执行过程不可分割的函数过程（原语）

• lock有两种状态：
• • *lock=FALSE表示资源空闲
• • *lock=TRUE表示资源正被使用

使用TS管理临界区，要为每个临界资源设置一个lock

• 初值为FALSE，表示临界资源空闲
• 进程进入临界区之前，先用TS测试lock，如果是FALSE，则可以进入，并将TRUE值赋给lock，关闭了临界资源

9.3.3 Swap指令

称为对换指令，用于交换两个字的内容

• 为每个临界资源设置一个全局布尔变量lock，初值FALSE
• 利用上面的硬件指令完成进程互斥
• 但是这种方法也会造成访问进程不断进行测试，处于“忙等”状态，不符合“让权等待”原则

9.4 信号量机制

9.4.1 整型信号量

被定义为一个用于表示资源数目的整型量S，对于这个整型信号量的操作只有三种：初始化(赋初值)、wait(自减)、signal(自增)

• wait和signal均为原子操作，执行时不可中断
• 当一个进程在修改某信号量时，没有其他进程可以同时对该信号量进行修改

9.4.2 记录型信号量

不存在“忙等”现象的进程同步机制

• 除了一个用于代表资源数目的整型变量value外
• 还需要增加一个进程链表L，用于链接所有等待该资源的进程

• wait操作等价于P操作
• signal操作等价于V操作
• 只是两种不同的称呼，功能完全一致
• wait(A) = P(A)
• signal(B) = V(A)

(1) 利用信号量实现进程互斥

设置一个互斥信号量mutex=1,然后把各进程访问临界资源的临界区放在wait(mutex)和signal(mutex)之间

(2) 利用信号量实现进程同步

设置一个同步信号量S=0，让需要先执行的语句signal(S)，后执行的wait(S)