背景

  • 锁可以用于临界区实现互斥，但对于同步无法满足

    信号量

  • 抽象数据结构

    • 一个整型（sem），两个原子操
    • V(): sem加1，如果sem>=0, 唤醒一个等待的P
    • P(): sem减1，如果sem<0,等待，否则继续

      信号的使用

  • 信号量是被保护的变量

    • 初始化完成后，只能通过P()和V()操作来改变信号量
    • 操作必须是原子的
  • P()能够阻塞，v()不会阻塞
  • 假设信号量是“公平的”
    • 采用FIFO方式
  • 两种类型信号量
    • 二进制信号量： 可以是0或1
    • 一般/计数信号量：可取任何非负值
    • 两种相互表现（给定一个可以实现另一个）
  • 信号量可以用在2个方面
    • 互斥
    • 条件同步（调度约束）
  • 举例：buffer的写入和取出

信号的实现

  • 使用硬件源语

    • 禁用中断
    • 原子指令

      管程

  • 目的：分离互斥和条件同步的关注

  • 什么是管程
    • 一个锁：指定临界区
    • 0或者多个条件变量：等待/通知信号量用于管理并发访问共享数据
  • 方法实现

  • 实现

    • 需要维持每个条件队列
    • 线程等待的条件signal()

      经典案例

  • 读者-写者问题

    • 动机： 共享数据访问
    • 两种类型的使用者
      • 写者：读取和修改数据，互斥
      • 读者：不需要修改数据（可以同步，多人）
    • 约束
      • 当没有读者的时候，写者不能直接写数据
      • 当有写者进行写操作，其他写者和读者无法操作数据
      • 读者优先，读者可以跳过写者先完成读操作（即进入临界区不是FIFO）
      • 写者优先
  • 哲学家就餐问题