经典IPC问题

Readers and Writers Problem 读者-写者问题

  • 例如，有一个飞机订票系统，有许多竞争的进程试图读写其中的数据

  • 多个进程同时读数据库是可以接受的

  • 但如果一个进程正在更新(写)数据库，则所有其他进程都不能访问数据库，即使读操作也不行

  • 画作图表示：

  • Solution:

    2. 这里的竞争条件是指会同时有多个Reader来修改这个reader变量

例题：

Sleeping Barber Problem

  • 没有顾客，理发师睡觉
  • 第一个顾客会叫醒理发师
  • 后面顾客来了之后，会坐下或者离开

Dining Philosophers Problem--哲学家就餐问题

  • 五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉，需要两把叉子才能夹住，相邻两个盘子之间放有一把叉子

  • 两个状态：吃饭和思考
  • 饿了时，分两次去取其左边和右边的叉子，每次拿一把，但不分次序
  • 得到两把则可以吃饭，后继续思考
  • 关键问题：使其不会造成死锁，即不会都在等待拿叉子

错误解法1，会造成死锁：

同时拿起左叉子，都在等待右叉子，陷入等待中

错误解法2：

一个哲学家拿了两把叉子在吃，释放了锁，但是叉子还在使用，当其他哲学家需要这两把叉子中的一把便陷入了等待

正确解法

例子

Monitor

  • 监视器是一组过程、变量和数据结构，一次只能由一个进程访问（出于互斥目的）。
  • 为了允许进程在监视器内等待，必须声明一个条件变量（condition variable）
    • 条件变量只能与操作wait 和signal 一起使用（用于同步目的）
      • x.wait():意味着调用此操作的进程被挂起，直到另一个进程调用
      • x.signal():x.signal 操作会恢复了一个挂起的进程。 如果没有进程被挂起，则信号操作无效

例子：

  • 优点：易于编程
  • 缺点：应用昂贵

Monitor和Semaphores的对比

  • 监视器中条件变量的等待和信号操作类似于计数信号量的 P 和 V 操作。
  • wait 语句可以阻塞一个进程的执行，而一个signal 语句可以导致另一个进程被解除阻塞。

不同之处：

  1. 当进程执行P操作时，它不一定会阻止该进程，因为计数信号量可能大于零。相反，当执行wait语句时，它总是阻塞进程
  2. 当任务对信号量执行V操作时，它要么取消阻止等待该信号量的任务，要么在没有要解锁的任务时增加信号量计数器。另一方面，如果一个进程在没有其他进程取消阻塞时执行signal语句，则对条件变量没有影响
  3. 信号量和监视器之间的另一个区别是，被V操作唤醒的用户可以毫不延迟地恢复执行。相反，被signal操作唤醒的用户只有在监视器解锁时才会重新启动

Message Passing

为每个进程分配一个唯一的地址,然后直接向进程发送消息

消息传递通常用于并行编程系统。

Message Passing API

消息传递适用于：

  • 同一台计算机内的进程。

  • 网络化/分布式系统中的进程

Synchronization in message passing 消息传递中的同步

  • 消息传递可能是堵塞或者不堵塞的

  • 阻塞(Blocking)被认为是同步（synchronous）的

    • 阻止发送(Blocking send)会阻止发送方，直到收到消息
    • 阻塞接收(Blocking receive)会阻塞接收器，直到消息可用

  • 非阻塞(Non-blocking)被认为是异步(asynchronous)的

    • 非阻塞发送(non-blocking send)让发送方发送消息并继续
    • 非阻塞接收(non-blocking receive)使接收器接收到有效消息或空

  • Sender:发出send后不被阻止更自然

    • 可以向多个目的地发送多条消息。
    • 但发送方通常期望收到消息确认（在接收方失败的情况下）

  • Receiver: 发出receive后不被阻塞

    • 接受者通常在继续之前需要这些信息。
    • 但如果发送方进程无法发送，则可能被无限期阻止。

  • 还有一些其他的方法：blocking send, blocking receive

  • 总结，有三种组合

    • Blocking send, Blocking receive;
    • Nonblocking send, Nonblocking receive;
    • Nonblocking send, Blocking receive – most popular

问题

Check points

  1. What is Race Condition?

  2. What is Critical Region?

  3. What is IO-bound process?

  4. What is Turnaround time?

  5. What is the drawback of the SJF algorithm?

  6. What is the advantage of RR scheduling?

  7. What is condition variable in monitor?

  8. What are the two operations in monitor