同步与互斥

同步互斥问题

• 生产者消费者问题——进程关系为“生产资源—消费资源”

• 理发师问题——进程关系为“服务——被服务”

  • 顾客是资源
  • 理发师消耗资源

• 读者写者问题——同类进程不互斥，异类进程互斥

• 哲学家进餐问题——只有一类进程，每个进程需要同时拥有多种资源才能运行

  • 不同类型的资源需要判断资源与资源的制约条件

• 生产者消费者步骤

  1. 有几类进程

     • 每类进程对应一个函数

  2. 在函数内部用中文描述进程动作

     • 只做一次，不加while循环
     • 不断重复，加while循环（while（1）{}）
       • 可能会有n个进程同时循环进行判断，即n个消费者

  3. 分析每个动作之前是否需要获取资源（P操作）

     • 只要有P操作必有V操作
     • 每写一个P就要检查在其他地方是否有对应的V
     • 注意区分临界区与资源
     • 互斥操作夹在最内部
     • 注意隐含的互斥条件，如访问缓冲区P（mutex）
       • 注意好共享缓冲区

  4. 所有PV操作写完后在定义信号量（Semaphore）

     • 注意信号量初值
       • 定义完信号量后，再思考每个信号量的初值
       • 写好注释

  5. 检查代码是否正确

     • 多个P连续出现时，是否有可能产生死锁
     • 即注意P操作的顺序是否合理
       • 一对PV操作连续出现，中间无其他操作，则不会死锁
     • 注意好死锁产生的四个必要条件

  6. 读题检查是否符合题意

• 前驱后继关系

  • 每一个箭头是一个同步信号量（前V后P），初始值为0

• 哲学家进餐问题

  • 关键点是限制并行

    • 解决循环等待问题

  1. 限制申请资源的顺序（不通用）

     • 规定单号先取左筷子，双号先取右筷子

  2. 限制并发进程数（通用，但并发度不高）

     • 规定统一时间只能有一个哲学家进餐（即禁止并行）
       • 也就是至多四名同时取筷子

  3. 让进程一口气获得所有资源，再开始运行（通用，并发度高，最优解）

     • 只有左右两边都可用时，才允许进餐
       • 本质为互斥的获取所有资源，当获取完后才释放临界区