知识库

进程同步与通信-操作系统高级课程第四讲

6分钟阅读

进程同步及通信（操作系统高级课程 第四讲）

北京大学软件与微电子学院无锡基地 2009 春季学期《操作系统高级》课程第四讲讲义，王平、陈向群、张齐勋主讲。系统梳理了进程/线程同步互斥机制与进程间通信方式，是理解 OS 并发控制的经典教学材料。

一、进程同步机制

1. 进程间的联系

  • 直接作用：进程间联系是有意识安排的，如一个进程依赖另一进程的消息 —— 即”同步”（synchronism）：多进程事件存在时序关系，需相互合作。进程运行到某点要求伙伴进程提供消息，未获得前进入等待态，获得后唤醒进入就绪态。
  • 间接作用：通过共享对象等中介产生关联（无意识安排）—— 即”互斥”：多进程竞争共享资源。
    • 临界资源：一次只允许一个进程使用的资源
    • 临界区：不同进程中操作共享数据结构的程序片段集合

2. 临界区使用原则（四条）

  1. 有空让进 —— 无进程在临界区时，任何有权进程可进入
  2. 无空等待 —— 不允许两个以上进程同时进入
  3. 有限等待 —— 进入请求应在有限时间内满足
  4. 让权等待 —— 等待进程应放弃 CPU

3. 互斥的软件解法（平等协商，前提：任何进程无权停止其它进程、相对运行速度无硬性规定）

  • 解法(1)：free 标志位（有竞争问题）
  • 解法(2)：turn 轮转标志
  • 解法(3)：pturn/qturn 双标志（存在死循环风险）
  • 解法(4)：Dekker 算法 —— 双标志 + turn 枚举仲裁
  • 解法(5)：Peterson 算法

4. 硬件解法

  • TS（Test and Set）指令：while TS(&lock); 临界区 lock=false;
  • Swap（exchange）指令：do Swap(&lock,key) while(key); 原子交换实现互斥

二、信号量与 PV 操作（管理者方案）

  • 1965 年 Dijkstra 提出；P=proberen（测试）、V=verhogen（增）为荷兰语。
  • 信号量数据结构：{ int value; pointer_PCB queue; }
  • P 操作：value-1；若 <0，置等待态并挂入 s.queue 后重新调度
  • V 操作：value+1；若 ≤0，唤醒 s.queue 中一个进程置就绪态
  • P、V 是原语（atomic action）：不可分割、不可中断，通过关中断实现
  • 同步机制四要求：描述能力、可以实现、效率高、使用方便

经典问题

  1. 生产者-消费者：S1 初值 1（空位）、S2 初值 0（有货）；多缓冲区版本用 i=(i+1)%n 循环；k 缓冲区 m 生产者 n 消费者时加 mutex（或每缓冲区独立 mutex1/mutex2）。
  2. 读者-写者（第一类，读者优先）：readcount 计数 + mutex + w 信号量；第一个读者 P(w)、最后一个读者 V(w)。
  3. 哲学家就餐：朴素双筷子取法会死锁。防死锁措施：
    • 最多允许 4 人同时入座
    • 左右筷子都可用才一次拿双筷
    • 奇偶编号差异化取筷顺序
    • 状态机方案：THINKING/HUNGRY/EATING 三态 + test(i) 检查邻居是否 EATING，一次拿两只筷子

三、进程间通信（高级通信原语）

  • PV 只能传简单信号 = 低级通信原语；传大量信息需高级通信 = IPC。
  • 三种方式：
    1. 共享内存：设公共内存，一组写一组读（需解决同步互斥）
    2. 共享文件/管道（Pipe）：基于文件系统，以打开的共享文件作缓冲介质
    3. 消息传递：send/receive 两个高级原语
  • 消息缓冲机制：OS 空间设一组有界缓冲区；send 产生自愿性中断→OS 分配空缓冲→消息 copy 进缓冲→挂到接收进程消息链链尾；receive 时从消息链取缓冲→copy 到接收进程空间→收回缓冲。
  • 消息缓冲区结构：消息长度 / 消息正文 / 发送者 / 消息队列指针。
  • Send 实现用 s-b(初值 n, 空缓冲数)、s-m(初值 0, 消息数)、b-mutex、m-mutex 四个信号量协作。

四、实例与作业

  • UNIX 同步/通信机制：管道、消息、共享内存、信号量、信号。
  • 作业亮点：推广消息缓冲（k 缓冲 m 发 n 收）、写者优先读者写者问题、队尾唤醒的 PV 变体辨析、睡眠理发师问题、总结 Solaris/Linux 进程线程同步通信机制。

关联

关系图谱