王道操作系统笔记（四）———— 进程同步与互斥

---

一、同步与互斥的概念

  异步性 是指各并发执行的进程以各自独立的、不可预知的速度向前推进。进程具有 异步性 的特征因此操作系统要提供 进程同步机制 来解决异步问题。此外有些资源 一个时间段内只允许一个进程访问操作系统要使得进程 互斥的访问 来该资源。

1.1 同步与互斥的基本概念

• 进程同步
  同步亦称 直接制约关系。进程同步 是指在某些时刻为完成某种任务而使得多个进程协调工作而产生的 制约关系。如管道通信中一定是先写在读

• 进程互斥
  互斥亦称 间接制约关系。进程互斥 是指当一个进程访问某临界资源时另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束释放该资源之后另一个进程才能去访问临界资源。如访问打印机

---

1.2 临界资源与共享资源

• 临界资源
  将一次只允许一个进程使用 的资源称为 临界资源。许多物理设备都属于临界资源如打印机、摄像头。

  临界资源的访问过程分成 4 个部分
   ① 进入区负责检查是否可进入临界区若可进入需要上锁。
   ② 临界区进程中访问临界资源的那段代码又称临界段。
   ③ 退出区负责解锁。
   ④ 剩余区代码中其余部分。

• 共享资源
  将一次允许多个进程同时使用 的资源称为 共享资源。如输出一行字符。
  进程之间往往 宏观 上同时共享使用该资源而 微观 上交替使用。

• 两种资源共享方式
  资源共享方式有两种分别是互斥共享方式 、 同时共享方式。其中互斥共享方式 对应 临界资源同时共享方式 对应 共享资源 。
  互斥共享方式一个时间段内 只允许一个进程 访问。
  同时共享方式允许一个时间段内 可由多个进程 “同时” 访问。

• 常见的临界资源与共享资源
  临界资源打印机、共享变量、共享缓冲区、公用队列。
  共享资源磁盘、非共享变量、可重入的代码。

  共享变量 x 初值等于 1现假设 x 值代表可用资源数量(如打印机)当 x = 0 时进程处于阻塞态。
  正常的执行顺序是①②③④⑤⑥。当执行到 ④ 时x=0进程B处于阻塞态不会去和A争抢打印机。
  有问题的执行顺序①②④⑤③⑥。当执行到 ④ 时由于进程A没有存变量因此进程B也会申请到打印机的使用权这会导致打印出错。
  
  综上共享变量 是 临界资源非共享变量(如常量) 是 共享资源。

• 同步机制要遵循的原则

  为了实现对临界资源的互斥访问同时保证系统整体性能需要遵循以下原则
   ① 空闲让进临界区空闲时可以允许一个请求进入临界区的进程立即进入临界区
   ② 忙则等待当已有进程进入临界区时其他试图进入临界区的进程必须等待
   ③ 有限等待对请求访问的进程应保证能在有限时间内进入临界区保证不会饥饿
   ④ 让权等待当进程不能进入临界区时应立即释放处理机防止进程忙等待。

---

1.3 独占设备与共享设备

独占设备 对应 临界资源共享设备 对应 共享资源 。

• 独占设备一个时间段只能分配给一个进程如打印机。
• 共享设备一个时间段可同时分配给多个进程如磁盘。各进程往往是宏观上同时共享使用设备而微观上交替使用。

磁盘是共享设备但在每个时刻至多能由一个作业启动它。
解析共享设备某时间段内可由昨个用户进行访问但在某一时刻只能有一个作业可以访问。


---

二、实现临界区互斥的基本方法

2.1 软件实现方法

2.1.1 单标志法

  算法基本思想设置一个 公用变量 turn用于指示被允许 进入临界区的进程编号即若 turn = 0则允许 P0 进程进入临界区。算法可保证同一时刻只允许一个进程进入临界区但两个进程必须交替进入临界区。

  存在问题若某个进程不再进入临界区则另一个进程也无法进入临界区即 每个进程进入临界区的权限只能被另一个进程赋予违背 “空闲让进” 原则。

---

2.1.2 双标志先检查法

  算法基本思想设置 一个布尔型数组 flag[]数组中各个元素用来标记各进程想 进入临界区的意愿比如 flag[0] = ture 意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有其他进程想进入临界区如果没有则把自身对应的标志 flag[i] 设为 true之后开始访问临界区。

  存在问题若按照 ①⑤②⑥…. 的顺序执行P0 和 P1 将会同时访问临界区违背 “忙则等待” 原则。原因在于进入区的 检查 和 上锁 两个处理不是 一气呵成 先检查后上锁在 检查后 和 上锁前 可能发生进程切换。

---

2.1.3 双标志后检查法

  算法基本思想双标志先检查法的改版与前一个算法不同采用 先上锁后检查来避免上述问题。

  存在问题若按照 ①⑤②⑥…. 的顺序执行P0 和 P1 将都无法进入临界区。因此双标志后检查法虽然 解决了 “忙则等待” 的问题但是 又违背了 “空闲让进”和“有限等待” 原则会因各进程都长期无法访问临界资源而产生 饥饿 现象。两个进程都争着想进入临界区但是谁也不让谁最后谁都无法进入临界区。

---

2.1.4 Peterson 算法

  算法基本思想结合双标志法、单标志法的思想。如果双方都争着想进入临界区那可以让进程尝试 孔融让梨(谦让)做一个有礼貌的进程。进程在进入区要做的步骤 ① 主动争取 ② 主动谦让 ③ 检查对方是否也想使用且最后一次是不是自己说了客气话

  存在问题Peterson 算法用软件方法解决了进程互斥问题 遵循 “空闲让进”、“忙则等待”、“有限等待” 三个原则但是依然 未遵循 “让权等待” 的原则。

---

2.1.5 软件实现方法总结

---

2.2 硬件实现方法

硬件实现方法实际上以硬件的方式将检查和上锁绑在一起。

2.2.1 中断屏蔽法

  中断屏蔽法利用 “开/关中断指令” 实现其与原语的实现思想相同即在某进程开始访问临界区到结束访问为止都不允许被中断也就不能发生进程切换因此也不可能发生两个进程同时访问临界区的情况。

优点 简单、高效
缺点 不适用于多处理机。只适用于 OS内核进程不适用于用户进程。因为开/关中断指令只能运行在内核态这组指令如果能让用户随意使用会很危险

注意区分原语与原子操作
① 原语是一种特殊程序执行中不可中断由开/关中断指令实现。
② 原子操作是一种执行过程执行期间一气呵成不可中断。

---

2.2.2 硬件指令法

  TestAndSet 指令简称 TS 指令也称 TestAndSetLock 指令或 TSL 指令。TSL指令是 原子操作执行过程中不可被中断。 以下是用C语言描述的逻辑

相比软件实现方法TSL 指令把 上锁和检查操作 用硬件的方式变成了一气呵成的 原子操作 。
优点 实现简单无需像软件实现方法那样严格检查是否会有逻辑漏洞。适用于多处理机环境。
缺点 不满足 “让权等待” 原则暂时无法进入临界区的进程会占用CPU并循环执行TSL指令从而导致 忙等。

---

  Swap 指令也称 Exchange 指令或简称 XCHG 指令。Swap 指令是 原子操作其用硬件实现的执行的过程不允许被中断只能一气呵成。以下是用C语言描述的逻辑

逻辑上来看 Swap 和 TSL 并无太大区别都是先记录下此时临界区是否已经被上锁记录在 old 变量上再将上锁标记 lock 设置为 true最后检查 old如果 old 为 false 则说明之前没有别的进程对临界区上锁则可跳出循环进入临界区。Swap 指令优点缺点和TSL指令相同。

---

2.2.3 硬件实现方法总结

---

2.2.4 补充互斥锁

  解决 临界区 最简单的工具就是 互斥锁 (mutex lock)。一个进程在进入临界区时应 获得锁在退出临界区时 释放锁 。函数 acquire() 获得锁而函数 release()释放锁。
  每个互斥锁有一个布尔变量 available表示锁是否可用。如果锁是可用的调用 acqiure()会成功且锁不再可用。当一个进程试图获取不可用的锁时会被阻塞直到锁被释放。acquire() 或 release() 的执行必须是 原子操作因此 互斥锁通常采用硬件机制来实现。

优点 等待期间不用切换进程上下文多处理器系统中若上锁的时间短则等待代价很低。当多个进程共享同一 CPU时就浪费了CPU 周期。因此互斥锁通常用于多处理器系统一个线程可以在一个处理器上等待而不影响其他线程的执行并快速释放临界区。

缺点不满足 “让权等待” 原则。当有一个进程在临界区中任何其他进程在进入临界区时必须连续循环调用 acquire()因此会发生 忙等待。

---

四、信号量

  用户进程可以通过使用操作系统提供的 一对原语 来对 信号量 进行操作从而很方便的实现了进程互斥、进程同步。信号量其实就是一个变量 可以用一个信号量来表示系统中某种资源的数量比如系统中只有一台打印机就可以设置一个初值为 1 的信号量。
  一对原语wait(S) 原语和 signal(S) 原语可以把原语理解为函数函数名分别为 wait 和 signal括号里的信号量 S 其实就是函数调用时传入的一个参数。wait(S) 原语和 signal(S) 原语也可记为P(S)、V(S)。

4.1 整型信号量

整型信号量被定义为一个用于标识资源数目的整型信号量。wait(S)、signal(S)可描述为

wait(S) 原语“检查”和“上锁”一气呵成避免了并发、异步导致的问题。以申请使用打印机举例

存在的问题 不满足 “让权等待” 原则会发生 忙等。

信号量机制与中断屏蔽法的区别
① 中断屏蔽法关中断、临界区、开中断整个执行过程是一个原子操作。
② 信号量机制wait(S)与signal(S)是两个原子操作。

注由于PV操作是原语原语是由特权指令开关中断实现因此也不适合与用户级线程。

---

4.2 记录型信号量

  记录型信号量不存在 忙等 现象的进程同步机制。除需要一个用于代表资源数目的整型信号量 value 以外再增加一个 进程链表 L用于链接所有等待该资源的进程。

例某计算机系统中有1台打印机则可在初始化信号量 S 时将 S.value 的值设为 1队列 S.L 设置为空。

① CPU 为 P0 服务S.value --值为 0P0开始使用打印机。
② CPU 为 P1 服务S.value --值为 -1无资源执行 block 原语( wait原语 )。阻塞队列( P1 )S.value = -1 说明有1个进程在等待资源。
③ CPU 为 P2 服务S.value --值为 -2无资源执行 block 原语。阻塞队列( P1→P2 )S.value = -2 说明有2个进程在等待资源。
④ CPU 为 P0 服务S.value ++S.value = -1 ≤ 0说明有进程在等待该资源。因此应调用 wakeup 原语(signal原语)唤醒等待队列中的第一个进程P1将释放资源给 P1P1从阻塞态变为就绪态等待被 CPU 服务(CPU顺序执行)。阻塞队列( P2 )
⑤ CPU 为 P1 服务P1 使用完打印机S.value ++S.value = 0调用 wakeup 原语唤醒 P2。阻塞队列()。
⑥ CPU 为 P2 服务 P2是用完打印机S.value ++S.value = 1。

注考试中出现 P(S)、V(S) 的操作除非特别说明否则默认 S 为记录型信号量。

---

4.3 信号量实现进程同步、互斥与前驱关系

4.3.1 实现进程同步

  设 S 为实现进程 P1、P2 互斥的信号量由于只允许一个进程进入临界区所以 S 的初值应设为 1。然后把临界区置于 P(S) 和 V(S) 之间进入区之前申请资源P操作退出区之前释放资源 V操作 即可实现两个进程对临界资源的互斥访问。

用信号量实现进程互斥
① 分析并发进程的关键活动划定临界区如对临界资源打印机的访问就应放在临界区
② 设置互斥信号量 mutex初值为 1即可用资源数为1理解为进入临界区的名额
③ 在进入区 P(mutex) —— 申请资源
④ 在退出区 V(mutex) —— 释放资源

注对 不同的临界资源 需要设置 不同的互斥信号量 P、V操作必须成对出现。

---

4.3.2 实现进程同步

  设 S 为实现进程 P1、P2 同步的信号量S 的初值应设为 0。只有当前一个进程释放资源后( V操作 )后一个进程才可申请资源 P操作。

用信号量实现进程同步
① 分析什么地方需要实现同步关系即必须保证一前一后在两个进程中)
② 设置同步信号量 S初始为 0
③ 在 “前操作” 之后执行 V(S)
④ 在 “后操作” 之前执行 P(S)

---

4.3.3 实现前驱关系多级同步

前驱关系本质上是 多级同步 的问题每一对前驱关系都需要保证 一前一后 的操作。

下图是一个前驱图其中 S1, S2, S3, … ,S6 是进程 P1, P2, P3,…, P6 中的程序段这些程序段要求按如下前驱图所示的顺序来执行
① 要为每一对前驱关系各设置一个同步信号量
② 在“前操作”之后对相应的同步信号量执行 V 操作
③ 在“后操作”之前对相应的同步信号量执行 P 操作

   

---

4.3.4 同步、互斥和前驱关系总结★

注互斥信号量初值一般为1同步信号量的初始值要看对应资源的初始值是多少。