操作系统概念 进程同步/Process Synchronization 第六章笔记

Posted on | In |

2017年10月24日
09:53

写在前面

本笔记仅仅是本人在上课时的一些随手记录，并不完整也不完全正确。

如有错误，请在评论中或直接联系我指正，谢谢！

原始文件下载：(mht)(pdf)

进程同步

  • 并发进程之间相互合作、互相约束
  • 利用私用信号量实现

． P4 进 程 等 待 P2 和 P3 进 程 的 结 果 ． P4 进 程 和 P2 、 P3 之 间 要 同 步 协 调 0

进程互斥(exclusion)

  • 并发进程之间互相竞争临界资源的排他性关系
  • 利用公用信号量实现互斥
  • 互斥源于资源共享，是进程之间的制约关系

0 例 如 丫 PI 使 用 打 印 机 ， P2 就 不 能 使 用

． 0 、 打 印 机 等 结 果 被 PI 一 P8 所 有 进 行 使 用 ， 需 要 排 他 使 用 一 个 使 用 时 ， 其 它 进 程 不 能 用 等 结 果 PI 和 P2 约 束 P3 、 P4 和 P5 之 日 一 束 匕 进 程 利 用 私 用 信 号 量 使 用 公 用 信 号 量 等 结 果 P6 、 P7 和 P8 之 间 束 及 其 它 、 利 用 私 用 信 号 量 公 用 信 号 量 、 私 用 信 号 量 ： 都 是 针 对 全 部 8 个 进 程 而 言

Background

Concurrent access to shared data may result in data inconsistency
Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes

生产者进程—->buffer—->消费者进程

保持数据稳定性

  • 维护一个整数计数器，追踪满缓存数量
  • 初始设为0
  • 被生产者增加，每提供一个新缓存+1
  • 被消费者减少

由于count没有在生产者和消费者之间同步，生产者和消费者进程会交替执行，而count一直被调去却未返回维护，导致生产者和消费者的寄存器中代表count的寄存器值不同

竞争条件

  • 多个进程并发访问和操作统一数据
  • 执行结果与访问发生的特定顺序有关

为避免，需要确保一段时间内只有一个进程可以操作变量，所以需要进程之间的同步与协调

临界区问题Critical Section/进程互斥

临界区：进程访问临界资源的那段代码

解决互斥方法：

  • 软件
  • 硬件

临界资源

  • 又被称为互斥资源(exclusive resources)
  • 这些系统资源每次只能被一个进程使用

临界区

  • 又被称为互斥区(exclusive section)
  • 访问临界资源的代码段

解决问题

每个进程必须在进入临界区之前寻求许可 （特别是在抢占式内核中，实现方式很有挑战性）

  • 进入区entry section
  • 退出区exit section
  • 代码中的其余部分remainder section

临界区的访问规则

互斥/mutual exclusion

当进程i正在临界区，其他进程都不能访问他们的临界区

前进Progress

如果

无进程在临界区
存在进程希望进入临界区

那么，选定的进程进入临界区

进程不能被无限推迟

有限等待Bounded Waiting

不会有饥饿现象

有空让进，无空等待，多中择一，有限等待，让权等待

基本思路

  • 在进入区检查设置一些标志
  • 进入区循环检查进行等待
  • 退出区修改标志

问题：设置什么标志，如何检查标志

算法1：单标志位

  • 设置变量turn
  • 进循环前查值（空等待）
  • 进循环后改变值

顺序：1，2，1，2，1，2…

缺点：
  进程强制轮流进入临界区，容易造成资源利用不充分

e.g:
  Pi让出临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区

算法2：双标志位（先检查）

标志数组flag[]：描述进程是否在临界区，初值均为FALSE

先检查，后修改

解决了顺序固定的问题

缺点：可能同时进入临界区
  检查对方flag之后和切换自己flag之前有一段时间，结果都检查通过。

检查和修改操作不能连续进行

算法3：双标志（先修改）

缺点：可能都无法进入临界区

实例：Peterson算法

将1与3相结合

维护两个变量，turn和flag[]

互斥被保护，进程申请可以通过，有限等待也得以满足

缺点：

  • 忙等待
  • 实现复杂，需要比较高的编程技巧（本实例仅提供双进程方案）

Process Synchronization

同步机制
  从进程管理者的角度来处理互斥同步问题

信号量

表示资源的实体，是一个与队列有关的整型变量

1
2
3
4
5
6
struct semaphore
{  
    int value;  
    pointer_PCB queue;   
    //阻塞在该信号量的各个进程的标识  
}

操作：初始化，P/V原语(Wait & signal)
不受进程调度的打断
公用信号量初值为1
私用初值为0或某个正整数

信号量取值

  • 非负：空闲资源数
  • 负：等待临界区进程数

P/V操作

P操作P(S)

申请分配一个单位的资源

V操作V(S)

释放一个单位的资源

关于…

优缺点：

  • 简单，表达能力强
  • 不够安全，使用不当会出现死锁
  • 遇到复杂同步互斥问题实现比较难

应用：实现互斥

引入mutex信号量，初值为1

同步：PV分别位于两个不同进程
互斥：在一个进程中

例1：读者、写者问题

例2：生产者、消费者问题

先检查资源数目，再检查互斥（避免死锁）

所有访问缓冲区的申请互斥
生产者消费者同步

哲学家进餐问题

Sleeping Barber