进程同步

这是一篇关于操作系统进程同步章节的笔记和知识点的思维导图，进程同步是在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。

进程同步

• 临界资源的访问
  • 进入区
  • 临界区
    • 进程中访问临界资源的代码
  • 退出区
    • 进入区和退出区：进程中实现互斥的代码
  • 剩余区
• 同步和互斥的关系
  • 同步：直接制约关系
    • 例如：生产者和消费者之间的关系
  • 互斥：间接制约关系
    • 例如：进程A，B都要使用一台打印机，A，B之间互斥的关系
    • 互斥机制
      • 空闲让进
      • 忙则等待
        • 禁止两个进程同时进入临界区
      • 有限等待
      • 让权等待
• 实现临界区互斥的基本方法
  • 软件实现方法
    • 单标志法
      • 设置一个公用变量turn=0，允许进程0使用， 进程0使用后面讲将turn=1，允许进程1使用
        • 缺点：两个进程必须交替使用
          • 违背空闲让进
    • 双标志法先检查
      • 设置flag[i]，每个进程使用前检查其他 进程有无使用临界区，之后在进入
        • 缺点：两个进程可能会同时进入临界区 并发运行时，当都没在使用临界区时， 进程1和进程2先后检查了无人使用，同时进入临界区
          • 违背忙则等待
    • 双标准法后检查
      • 先将自己的状态更改为ture，在检查有无 其他进程使用
        • 缺点：两个进程可能都无法进入临界区
          • 导致饥饿
    • peterson algorithm
      • 在flag基础上设置了变量turn，表示谦让， 每个进程先设置自己的flag，在设置turn， 若进程1的flag[2]=true且turn=2，则等待
        • 利用flag解决资源的互斥访问 利用turn解决饥饿
  • 硬件实现方法
    • 中断屏蔽方法
    • 硬件指令方法
      • TestAndSet指令
      • swap指令
      • 特点
        • 适用于任意数目的进程，简单
        • 进程等待进入临界区一直处于while循环中 耗费cpu时间，导致饥饿
        • 注意，进程不会进入阻塞态，且一个进程 退出临界区时会“唤醒”处于就绪态的进程
• 信号量
  • 整型信号量
    • 定义一个表示资源数目的整型量S
      • wait操作中，只要信号量《0，则会一直处于 循环。违背让权等待
  • 记录型信号量
    • wait，请求资源S.value--， 当S.value＜0则该进程自我阻塞
    • signal，释放资源S.value++， 当S.value＜=0，则唤醒一个进程
      • 唤醒进程和S.value已经没关系了， 每个进程在使用wait和signal方法的 最前面都已经对S.value操作过了
  • 用信号量实现前驱关系
    • 看箭头，有几个箭头设置几个信号量
• 管程
  • 管程的目的
    • 新型进程同步工具，无需程序员自己 实现互斥，可以实现进程间的同步和互斥
  • 管程的组成
    • 管程的名称
    • 局部于管程内部的共享结构数据说明
    • 对该数据结构进行操作的一组过程（函数）
    • 对共享数据设置初始值的语句
  • 管程的特征
    • 一个进程只有通过调用管程内的过程 才能进入管程访问共享资源
    • 一次只允许一个进程进入管程，且 每次只能访问一个函数
  • 条件变量
    • x.wait
      • 将进程阻塞，并插入x的等待（阻塞）队列
        • 注意：与信号量的wait操作区分， 不用进行value的判断
    • x.signal
      • 唤醒一个因x条件阻塞的进程
• 经典同步问题
  • 生产者-消费者问题
  • 读者写者问题P86
    • 针对写优先，额外设置一个w信号量
    • 针对多读者间可以一起读文件
  • 哲学家就餐问题
  • 吸烟者问题