IPC

inter process communication

Race Condition

2 process want to eat same cake

概念

• 多个进程访问共享的数据，最终的结果取决于进程运行的时序

how to avoid

• mutual exclusion

  互斥访问

• critical region

  • 对共享内存进行访问的程序片段
  • 对关键区提出某种机制避免race condition

• 好的解决方案的原则

  • no 2 processes may be simultaneously inside their critical regions
  • 不应对cpu的速度和数量作出任何假设
  • 临界区外的进程不得阻塞其他进程
  • 不得使进程无限期的等待进入临界区

解决方案

Mutual Exclusion with Busy waiting

• 概念

  • 当一个进程要进入关键区的时候，检查是否可以进入，不能进入就继续检查

• 实现

  • 屏蔽中断（Disable interrupt）

    • 同步顺序执行
    • 多CPU失效，违背第二条原则

  • 锁变量（Lock Variables）

    • 严格轮换法（Strict Alternation）

    • Peterson‘s solution

      • 相比严格轮换法，引入了一定的随机性

    • TSL指令

      • 需要硬件的帮助

• 缺点

  • 浪费CPU时间
  • 优先级问题

Sleep & Wakeup

• 概念

  • 当进程发现自己无法进入关键区时，就sleep，等到它被正要离开关键区的进程wake up

• 栗子

  • Consumer和Producer

• 实现

  • Semaphore（信号量）

    • 类比

      • Traffic Light

    • 操作（PV操作）

      • up

        每次加1会唤醒一个因为down操作陷入睡眠的进程

        • samaphore++

      • down

        如果samaphore<1，调用down方法的进程会陷入睡眠

        • samaphore–

    • 数量大小的含义

      • 资源数
      • 同一个资源可以进入关键区的进程的数量

    • 特点

      • 当一个进程结束的时候，其所创建的samaphore对象不会销毁

    • 存在位置

      • 内核空间

        如果放在用户空间，进程退出时samaphore会销毁

    • 缺陷

      • 从用户空间到切换到内核空间需要付出时间代价
      • 容易死锁

  • Mutex

    • 地位

      • simplified Samaphore

    • 取值

      • 0
      • 1

    • 状态

      • lock
      • unlock

    • 一般用途

      • 单进程里的多线程防止互斥访问

    • 存储位置

      • 用户空间

    • 和semapahore的区别

      • 进程和线程
      • 存储位置

  • Monitor

    • 在pv操作上的一层包装，目的是防止deadlock

    • 栗子

      • java里的synchronized

Message Passing

Barrier