信号量与管程

信号量( semaphore )

  • 信号量是操作系统提供的一种协调共享资源访问的方法
    • 软件同步是平等线程间的一种同步协商机制
    • 信号量是和锁同级的一种实现同步的高级抽象方法
    • OS 是管理者，地位高于进程
    • 用信号量表示系统资源的数量

  • 早期的操作系统的主要同步机制

    • 现在很少用(但还是非常重要在计算机科学研究)
  • 信号量是一种抽象数据类型
    • 由一个整形( sem )变量和两个原子操作组成
    • P() ( Prolaag (荷兰语：尝试减少))
      • sem 减1
      • 如 sem < 0，进入等待，否则继续
    • V() ( Verhoog (荷兰语：增加))
      • sem 加1
      • 如 sem <= 0，唤醒一个等待进程
  • 信号量的特征
    • 信号量是被保护的整数变量
      • 初始化完成后，只能通过 P() 和 V() 操作修改
      • 由操作系统保证，PV 操作是原子操作
    • P() 可能阻塞，V() 不会阻塞
    • 通常假定信号量是”公平的”
      • 线程不会被无限期阻塞在 P() 操作
      • 假定信号量等待按先进先出排队
  • 信号量的实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    classSemaphore {
      int sem;
      WaitQueue q;
    }

    Semaphore::P() {
      sem --;
      if (sem < 0) {
        Add this thread t to q;
        block(p);
      }
    }

    Semaphore::V() {
      sem ++;
      if (sem <= 0) {
        Remove a thread t from q;
        wakeup(t);
      }
    }

信号量使用

  • 信号量分类：可分为两种信号量
    • 二进制信号量：资源数目为0或1
    • 资源信号量：资源数目为任何非负值
    • 两者等价：基于一个可以实现另一个
  • 信号量的使用
    • 互斥访问：临界区的互斥访问控制
    • 条件同步：线程间的事件等待

  • 用信号量实现临界区的互斥访问

    • 每类资源设置一个信号量，其初值为1

      1
      mutex = new Semaphore(1);
      1
      2
      3
      mutex->P();
      Critical Section;
      mutex->V();

    • 必须成对使用 P() 操作和 V() 操作

      • P() 操作保证互斥访问临界资源
      • V() 操作在使用后释放临界资源
      • PV 操作不能次序错误、重复或遗漏

  • 用信号量实现条件同步

    • 每个条件同步设置一个信号量，其初值为0

      1
      condition = new Semaphore(0);

生产者-消费者问题

  • 有界缓冲区的生产者-消费者问题描述
    • 一个或多个生产者在生成数据后放在一个缓冲区里
    • 单个消费者从缓冲区取出数据处理
    • 任何时刻只能有一个生产者或消费者可访问缓冲区

  • 用信号量解决生产者-消费者问题

    • 问题分析
      • 任何时刻只能有一个线程操作缓存区(互斥访问)
      • 缓冲区空时，消费者必须等待生产者(条件同步)
      • 缓冲区满时，生产和必须等待消费者(条件同步)
    • 用信号量描述每个约束
      • 二进制信号量 mutex
      • 资源信号量 fullBuffers
      • 资源信号量 emptyBuffers

    • 实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      // 初始化
      Class BoundedBuffer {
        mutex = new Semaphore(1);
        fullBuffers = new Semaphore(0);
        emptyBuffers = new Semaphore(n);
      }
      // 生产者
      BoundedBuffer::Deposit(c) {
        emptyBuffers->P();
        mutex->P();
        Add c to the buffer;
        mutex->V();
        fullBuffers->V();
      }
      // 消费者
      BoundedBuffer::Remove(c) {
        fullBuffers->P();
        mutex->P();
        Remove c from the buffer;
        mutex->V();
        emptyBuffers->V();
      }
      • 如果 P、V 操作顺序有误，会造成死锁
  • 使用信号量的困难
    • 读/开发代码比较困难
      • 程序员需要能运用信号量机制
    • 容易出错
      • 使用的信号量已经被另一个线程占用
      • 忘记释放信号量
    • 不能够处理死锁问题

管程( Moniter )

  • 管程是一种用于多线程互斥访问共享资源的程序结构
    • 采用面向对象方法，简化了线程间的同步控制
    • 任一时刻最多只有一个线程执行管程代码
    • 正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复
  • 管程的使用
    • 在对象/模块中，收集相关共享数据
    • 定义访问共享数据的方法
  • 管程的组成
    • 一个锁
      • 控制管程代码的互斥访问
    • 0 或者多个条件变量
      • 管理共享数据的并发访问

  • 条件变量( Condition Variable )

    • 条件变量是管程内的等待机制
      • 进入管程的线程因资源被占用而进入等待状态
      • 每个条件变量表示一种等待原因，对应一个等待队列
    • Wait() 操作
      • 将自己阻塞在等待队列中
      • 唤醒一个等待者或释放管程的互斥访问
    • Signal() 操作
      • 将等待队列中的一个线程唤醒
      • 如果等待队列为空，则等同空操作
    • 条件变量的实现
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      Class Condition {
        int numWaiting = 0;
        WaitQueue q;
      }

      Condition::Wait(lock) {
        numWaiting++;
        Add this thread t to q;
        release(lock)；
        schedule();	// need mutex
        require(lock);
      }

      Condition::Signal() {
        if (numWaiting > 0) {
          Remove a thread t from q;
          wakeup(t);	//need mutex
          numWaiting--;
        }
      }

  • 用管程解决生产者-消费者问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    // 初始化
    classBoundedBuffer {
      ...
      Lock lock;
      int count = 0;
      Condition notFull, notEmpty;
    }
    // 生产者
    BoundedBuffer::Deposit(c) {
      lock->Acquire();
      while (count == n)
      	notFull.Wait(&lock);
      Add c to the buffer;
      count++;
      notEmpty.Signal();
      lock->Release();
    }
    // 消费者
    BoundedBuffer::Remove(c) {
      lock->Acquire();
      while (count == 0)
      	notEmpty.Wait(&lock);
      Remove c from the buffer;
      count--;
      notFull.Signal();
      lock->Release();
    }

  • 管程条件变量的释放处理方式

    • Hansen 的连续执行效率更高，如图少了一次切换
    • Hansen 管程：主要用于真实 OS 和 Java 中
    • Hoare 管程：主要见于教材中
    • Hansen 管程与 Hoare 管程
      • 以生产者-消费者问题的生产者代码为例
        • Hansen 管程
          • 条件变量释放仅是一个提示
          • 需要重新检查条件
          • 特点：高效
        • Hoare 管程
          • 条件变量释放同时表示放弃管程访问
          • 释放后条件变量的状态可用
          • 特点：低效

经典同步问题之哲学家就餐问题

  • 问题描述
    • 5个哲学家围绕一张圆桌而坐
      • 桌子上放着5支叉子
      • 每两个哲学家之间放一支
    • 哲学家的动作包括思考和进餐
      • 进餐时需同时拿到左右两边的叉子
      • 思考时将两支叉子放回原处
    • 如何保证哲学家们的动作有序进行？
      • 如：不出现有人永远拿不到叉子
  • 方案一
    • 不正确，可能导致死锁
  • 方案二
    • 互斥访问正确，但每次只允许一人进餐
  • 方案三
    • 没有死锁，可有多人同时进餐

经典同步问题之读者-写者问题

  • 问题描述
    • 共享数据的两类使用者
      • 读者：只读取数据，不修改
      • 写者：读取和修改数据
    • 读者-写者问题描述：对共享数据的读写
      • “读 - 读”允许
        • 同一时刻，允许有多个读者同时读
      • “读 - 写”互斥
        • 没有写者时读者才能读
        • 没有读者时写者才能写
      • “写 - 写”互斥
        • 没有其他写者时写者才能写
  • 用信号量解决读者-写者问题
    • 用信号量描述每个约束
      • 信号量 WriteMutex
        • 控制读写操作的互斥
        • 初始化为1
      • 读者技术 Rcount
        • 正在进行读操作的读者数目
        • 初始化为0
      • 信号量 CountMutex
        • 控制对读者计数的互斥修改
        • 初始化为1
      • 此实现中，读者优先
  • 读者-写者问题：优先策略
    • 读者优先策略
      • 只要有读者正在读状态，后来的读者都能直接进入
      • 如读者持续不断进入，则写者就处于饥饿
    • 写者优先策略
      • 只要有写者就绪，写者应尽快执行写操作
      • 如写者持续不断就绪，则读者就处于饥饿

  • 用管程解决读者-写者问题

    • 两个基本方法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      Database::Read() {
        Wait until no writer;
        read database;
        check out - wake up waiting writers;
      }

      Database::Write() {
        Wait until no readers/writers;
        write database;
        check out - wake up waiting readers/writers;
      }

    • 管程的状态变量

    • 解决方案详情：读者
      • 这里 while() 里的条件设置的是有写者在写或有写者申请写就等待，体现的是写者优先
      • 这里 if() 里的条件设置的是最后一个读者看有没有写者，如果有写者等着，就释放
    • 解决方案详情：写者
      • 这里 while() 里的条件设置的是有写者在写或有读者在读就等待，但是如果继续有读者等着就不管了，所以体现的是写者优先
      • 这里 if() 里的条件设置的是如果有等待写的就优先唤醒，没有的话才唤醒读者

死锁和进程通信

死锁

  • 定义：由于竞争资源或者通信关系，两个或更多线程在执行中出现，永远相互等待只能由其他进程引发的事件
  • 死锁示例：单向通行桥梁
    • 桥梁只能单向通行
    • 桥的每个部分可视为一个资源
    • 可能出现死锁
      • 对向行驶车辆在桥中相遇
      • 解决办法：一个方向的车辆倒退(资源抢占和回退)
    • 可能发生饥饿
      • 由于一个方向的持续车流，另一个方向的车辆无法通过桥梁

进程访问资源的流程

  • 资源类型 R1，R2，…，Rm
    • CPU 执行时间、内存空间、I/O 设备等
  • 每类资源 Ri 有 Wi 个实例
  • 进程访问资源的流程
    • 请求/获取：申请空闲资源
    • 使用/占用：进程占用资源
    • 释放：资源状态由占有变成空闲

资源

  • 资源分类

    • 可重用资源( Reusable Resource )
      • 资源不能被删除且在任何时刻只能有一个进程使用
      • 进程释放资源后，其他进程可重用
      • 可重用资源示例
        • 硬件：处理器，I/O 通道，主和副存储器，设备等
        • 软件：文件，数据库和信号量等数据结构
      • 可能出现死锁
        • 每个进程占用一部分资源并请求其他资源
    • 消耗资源( Consumable Resource )
      • 资源创建和销毁
      • 消耗资源示例
        • 在 I/O 缓冲区的中断、信号、消息等
      • 可能出现死锁
        • 进程间相互等待接受对方的消息

  • 资源分配图

    • 描述资源和进程间的分配和占用关系的有向图
    • 两类顶点
      • 系统中的所有进程
        P = {P1，P2，…，Pn}
      • 系统中的所有资源
        R = {R1，R2，…，Rm}
    • 两类有向边
      • 资源请求边
        • 进程 Pi 请求资源 Rj ：Pi -> Rj
      • 资源分配边
        • 资源 Rj 已分配给进程 Pi ：Rj -> Pi

出现死锁的必要条件

  • 互斥
    • 任何时刻只能有一个进程使用一个资源实例
  • 持有并等待
    • 进程保持至少一个资源，并正在等待获取其他进程持有的资源
  • 非抢占
    • 资源只能在进程使用后自愿释放
  • 循环等待
    • 存在等待进程集合{P0，P1，…，PN}，
      P0 正在等待 P1 所占用的资源，
      P1 正在等待 P2 所占用的资源，…，
      PN-1 正在等待 PN 所占用的资源，
      PN 正在等待 P0 所占用的资源
  • 现学现用

死锁处理方法

  • 死锁预防( Deadlock Prevention )：确保系统永远不会进入死锁状态
  • 死锁避免( Deadlock Avoidance )：在使用前进行判断，只允许不会出现死锁的进程请求资源
  • 死锁检测和恢复( Deadlock Detection & Recovery )：在检测到运行系统进入死锁状态后，进行恢复
  • 由应用进程处理死锁
    • 通常操作系统忽略死锁：大多数操作系统(包括 UNIX )的做法

死锁预防

  • 预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件
  • 互斥：把互斥的共享资源封装成可同时访问
  • 持有并等待
    • 进程请求资源时，要求它不持有任何其他资源
    • 仅允许进程在开始执行时，一次请求所有需要的资源
    • 资源利用率低
  • 非抢占
    • 如进程请求不能立即分配的资源，则释放已占用资源
    • 只在能够同时获得所有需要资源时，才执行分配操作
  • 循环等待
    • 对资源排序，要求进程按顺序请求资源

死锁避免

  • 方法一：利用额外的先验信息，在分配资源时判断是否会出现死锁，只在不会死锁时分配资源
    • 要求进程声明需要资源的最大数目
    • 限定提供与分配的资源数量，确保满足进程的最大需求
    • 动态检查资源分配状态，确保不会出现环形等待
  • 方法二：当进程请求资源时，系统判断分配后是否处于安全状态
    • 系统处于安全状态
      • 针对所有已占用进程，存在安全序列
    • 序列 <P1，P2，…，PN> 是安全的
      • Pi 要求的资源 <= 当前可用资源 + 所有 Pj 持有资源其中 j < i
      • 如 Pi 的资源请求不能立即分配，则 Pi 等待所有 Pj ( j < i )完成
      • Pi 完成后，Pi + 1可得到所需资源，执行并释放所分配的资源
      • 最终整个序列的所有 Pi 都能获得所需资源
    • 安全状态与死锁的关系
      • 系统处于安全状态，一定没有死锁
      • 系统处于不安全状态，可能出现死锁
        • 避免死锁就是确保系统不会进入不安全状态

银行家算法( Banker’s Algorithm )

  • 银行家算法是一个避免死锁产生的算法。以银行借贷分配策略为基础，判断并保证系统处于安全状态
    • 客户在第一次申请贷款时，声明所需最大资金量，在满足所有贷款要求并完成项目时，及时归还
    • 在客户贷款数量不超过银行拥有的最大值时，银行家尽量满足客户需求
    • 类比
      • 银行家 ↔ 操作系统
      • 资金 ↔ 资源
      • 客户 ↔ 申请资源的线程
  • 银行家算法：数据结构
    • n = 线程数量，m = 资源类型数量
    • Max (总需求量)：n * m 矩阵
      • 线程 Ti 最多请求类型 Rj 的资源 Max[i, j] 个实例
    • Available (剩余空闲量)：长度为 m 的向量
      • 当前有 Available[i] 个类型 Rj 的资源实例可用
    • Allocation (已分配量)：n * m 矩阵
      • 线程 Ti 当前分配了Allocation[i, j] 个 Rj 的实例
    • Need (未来需要量)：n * m 矩阵
      • 线程 Ti 未来需要 Need[i, j] 个 Rj 资源实例
    • Need[i, j] = Max[i, j] - Allocation[i, j]

  • 银行家算法核心：安全状态判断

    1. Work 和 Finish 分别是长度为 m 和 n 的向量初始化

      1
      2
      Work = Available	//当前资源剩余空闲量
      Finish[i] = false for i : 1,2, …, n.	//线程 i 没结束

    2. 寻找线程 Ti 满足

      1
      2
      Finish[i] = false		//接下来找出 Need 比 Work 小的线程 i
      Need[i] <= Work

      没有找到满足条件的 Ti ，转4

    3. 改成 true 表示线程结束

      1
      2
      Work = Work + Allocation[i]		//线程 i 的资源需求量小于当前剩余空闲资源量，所以配置给它再回收
      Finish[i] = true

      转2

    4. 如所有线程 Ti 满足 Finish[i] == true，则系统处于安全状态

  • 银行家算法

    • 初始化
      • Requesti 线程 Ti 的资源请求向量
      • Requesti[j] 线程 Ti 请求资源 Rj 的实例

    • 循环

      1. 如果 Requesti <= Need[i]，转到步骤2。否则，拒绝资源申请，因为线程已经超过了其最大要求
      2. 如果 Requesti <= Available，转到步骤3。否则，Ti 必须等待，因为资源不可用

      3. 通过安全状态判断来确定是否分配资源给 Ti ：

        • 生成一个需要判断状态是否安全的资源分配环境
          1
          2
          3
          Available = Available - Requesti;
          Allocation[i] = Allocation[i] + Requesti;
          Need[i] = Need[i] - Requesti;

      4. 调用安全状态判断

        • 如果返回结果是安全，将资源分配给 Ti
        • 如果返回结果是不安全，系统会拒绝 Ti 的资源请求

死锁检测和恢复

  • 死锁检测简述
    • 允许系统进入死锁状态
    • 维护系统的资源分配图
    • 定期调用死锁检测算法来搜索图中是否存在死锁
    • 出现死锁时，用死锁恢复机制进行恢复
  • 死锁检测算法：数据结构
    • Available：长度为 m 的向量
      • 每种类型可用资源的数量
    • Allocation：一个 n * m 矩阵
      • 当前分配给各个进程每种类型资源的数量
      • 进程 Pi 拥有资源 Ri 的 Allocation[i, j] 个实例
  • 死锁检测算法
    1. Work 和 Finish 分别是长度为 m 和 n 的向量初始化
      • Work = Available //work 为当前空闲资源量
      • Allocation[i] > 0 时，Finish[i] = false; 否则，Finish[i] = true; //finish 为线程是否结束
    2. 寻找线程 Ti 满足
      • Finish[i] = false //线程没有结束，且此线程将需要的资源量小于当前空闲资源量
      • Requesti <= Work
        没有找到这样的 i ，转到4
    3. Work = Work + Allocation[i] //把找到的线程拥有的资源释放到当前空闲资源中
      Finish[i] = true
      转到2
    4. 如果某个 Finish[i] == false，系统处于死锁状态
      算法需要O(m*n2)操作检测系统是否处于死锁状态
  • 死锁检测算法的使用
    • 死锁检测的时间和周期选择依据
      • 死锁多久可能会发生
      • 多少进程需要被回滚
    • 资源图可能有多个循环
      • 难以分辨”造成”死锁的关键进程
  • 死锁恢复：进程终止
    • 终止所有的死锁进程
    • 一次只终止一个进程直到死锁清除
    • 终止进程的顺序应该是
      • 进程的优先级
      • 进程已运行时间以及还需运行时间
      • 进程已占用资源
      • 进程完成需要的资源
      • 终止进程数目
      • 进程是交互还是批处理
  • 死锁恢复：资源抢占
    • 选择被抢占进程
      • 最小成本目标
    • 进程回退
      • 返回到一些安全状态，重启进程到安全状态
    • 可能出现饥饿
      • 同一进程可能一直被选作被抢占者

进程通信( IPC，Inter-Process Communication )

  • 进程通信是进程进行通信和同步的机制
  • IPC 提供2个基本操作
    • 发送操作：send(message)
    • 接收操作：receive(message)
  • 进程通信流程
    • 在通信进程间建立通信链路
    • 通过 send/receive 交换信息
  • 进程链路特征
    • 物理(如：共享内存，硬件总线)
    • 逻辑(如：逻辑属性)
  • 通信方式
    • 直接通信
      • 进程必须正确的命名对方
        • send(P, message)：发送信息到进程 P
        • receive(Q, message)：从进程 Q 接受消息
      • 通信链路的属性
        • 自动建立链路
        • 一条链路恰好对应一对通信进程
        • 每对进程之间只有一个链接存在
        • 链接可以是单向的，但通常为双向的
    • 间接通信
      • 通过操作系统维护的消息队列实现进程间的消息接收和发送
        • 每个消息队列都有一个唯一的标识
        • 只有共享了相同消息队列的进程，才能够通信
      • 通信链路的属性
        • 只有共享了相同消息队列的进程，才建立连接
        • 连接可以是单向或双向
        • 消息队列可以与多个进程相关联
        • 每对进程可以共享多个消息队列
      • 通信流程
        • 创建一个新的消息队列
        • 通过消息队列发送和接收消息
        • 销毁消息队列
      • 基本通信操作
        • send(A, message)：发送消息到队列 A
        • receive(A, message)：从队列 A 接收消息
  • 阻塞与非阻塞通信
    • 进程通信可划分为阻塞(同步)或非阻塞(异步)
    • 阻塞通信
      • 阻塞发送：发送者在发送消息后进入等待，直到接受者成功收到
      • 阻塞接收：接收者在请求接收消息后进入等待，直到成功收到一个消息
    • 非阻塞通信
      • 非阻塞发送：发送者在消息发送后，可立即进行其他操作
      • 非阻塞接收：没有消息发送时，接受者在请求接收消息后，接收不到任何消息
  • 通信链路缓冲
    • 进程发送的消息在链路上可能有3种缓冲方式
      • 0容量：发送方必须等待接收方
      • 有限容量：通信链路缓冲队列满时，发送方必须等待
      • 无限容量：发送方不需要等待

信号( Signal )

  • 信号
    • 进程间的软件中断通知和处理机制
    • 如：SIGKILL，SIGSTOP，SIGCONT等
  • 信号的接收处理
    • 捕获( Catch )：执行进程指定的信号处理函数被调用
    • 忽略( Ignore )：执行操作系统指定的缺省操作
      • 例如：进程终止、进程挂起等
    • 屏蔽( Mask )：禁止进程接收和处理信号
      • 可能是暂时的(当处理同样类型的信号)
  • 不足
    • 传送的信息量小，只有一个信号类型
  • 信号的实现
  • 信号使用示例

管道( pipe )

  • 进程间基于内存文件的通信机制
    • 子进程从父进程继承文件描述符
    • 缺省文件描述符：0 stdin，1 stdout，2 stderr
  • 进程不知道(或不关心！)的另一端
    • 可能从键盘、文件、程序读取
    • 可能写入到终端、文件、程序
  • 与管道相关的系统调用
    • 读管道：read(fd, buffer, nbytes)
      • scanf() 是基于它实现的
    • 写管道：write(fd, buffer, nbytes)
      • printf() 是基于它实现的
    • 创建管道：pipe(rgfd)
      • rgfd 是2个文件描述符组成的数组
      • rgfd[0] 是读文件描述符
      • rgfd[1] 是写文件描述符
  • 管道示例
    • % ls | more
      • shell
        1. 创建管道
        2. 为 ls 创建一个进程，设置 stdout 为管道写端
        3. 为 more 创建一个进程，设置 stdin 为管道读端

消息队列

  • 消息队列是由操作系统维护的以字节序列为基本单位的间接通信机制
    • 每个消息( Message )是一个字节序列
    • 相同标识的消息组成按先进先出顺序组成一个消息队列( Message Queues )
  • 消息队列的系统调用
    • msgget ( key, flags )：获取消息队列标识
    • msgsnd ( QID, buf, size, flags )：发送消息
    • msgrcv ( QID, buf, size, type, flags )：接收消息
    • msgctl ( … )：消息队列控制

共享内存

  • 共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制
  • 进程
    • 每个进程都有私有内存地址空间
    • 每个进程的内存地址空间需明确设置共享内存段
  • 线程
    • 同一进程中的线程总是共享相同的内存地址空间
  • 优点：快捷、方便地共享数据
  • 不足：必须用额外的同步机制来协调数据访问
  • 共享内存的实现
    • 最快的方法
    • 一个进程写另外一个进程立即可见
    • 没有系统调用干预
    • 没有数据复制
    • 不提供同步：由程序员提供同步
  • 共享内存系统调用
    • shmget ( key, size, flags )：创建共享段
    • shmat ( shmid, *shmaddr, flags )：把共享段映射到进程地址空间
    • shmdt ( *shmaddr )：取消共享段到进程地址空间的映射
    • shmctl ( … )：共享段控制
    • 需要信号量等机制协调共享内存的访问冲突