3.4：死锁与进程通信

死锁

• 由于竞争资源或者通信关系，两个或更多线程在执行中出现相互等待的事件

• 多数操作系统是忽略死锁的，死锁就交给应用进程处理了

出现死锁的必要条件

• 互斥（可共享的不会发生死锁）

• 持有并等待（占有资源，并且等待别的资源）

• 非抢占（不会被抢）

• 循环等待

死锁的解决方法

死锁预防

• 互斥：把互斥的共享资源封装成可同时访问

• 持有并等待：进程在开始执行时一次请求所有需要的资源，但资源利用率低

• 非抢占：只在能够同时获得所有需要资源时，才执行分配操作

• 循环等待：对资源排序，要求进程按顺序请求资源，但资源利用率低

死锁避免（先判断安不安全再分配）——银行家算法

• 核心：剩余量必须大于未来需求量才分配

• Max(总需求量) = n x m 矩阵

  Available(剩余空闲量) 长度为 m 的向量
  Allocation(已分配量) = n x m 矩阵
  Need(未来需要量) = n x m 矩阵
  Need[i, j] = Max[i, j] - Allocation[i, j]
  if（所有的线程需求量<=剩余量） 则安全
  else if （存在关键路径使得线程可以全部走完）  则安全
  else 不安全

死锁检测

时间复杂度O(n^2 x m) 开销大，因此实际操作系统不管死锁

初始化 Work 和 Finish:
Work = Available // work为当前资源剩余量
Allocation[i] > 0时 Finish[i] = false 否则为 true // 线程是否完成

寻找线程Ti满足:
Finish[i] = false // 线程没有结束 且 此线程需要的资源量小于剩余资源量
Requesti <= Work

若没有找到 则跳到步骤4
将找到的线程拥有的资源释放回当前空闲资源
Work = Work + Allocation[i]
Finish[i] = true
跳到步骤2

检查所有线程的 Finish 若有一个为 false 则系统处于死锁状态

释放某些核心锁，解开死锁

进程通信概念（IPC）

• 间接通信：通过系统维护的消息队列

• 直接通信：两个进程必须同时存在才能进行通讯

• 阻塞与非阻塞通信：进程通信可划分为阻塞(同步)通信与非阻塞(异步)通信

• 通信链路缓冲

  • 0容量： 发送方必须等待接收方(必须有接收方)

  • 有限容量：通信链路缓冲队列满时 发送方必须等待

  • 无限容量：发送方不需要等待

进程通信的实现方法

信号

• 进程间的软件中断通知和处理机制(SIGKILL SIGSTOP SIGCONT)

• 信号的接受处理

  • 捕获(Catch) 执行进程指定的信号处理函数被调用

  • 忽略(Ignore) 执行操作系统指定的缺省处理(进程终止，进程挂起)

  • 屏蔽(Mask) 禁止进程接受和处理信号(可能是暂时的，当处理同样类型的信号)

• 不足：传送的信息量小，只有一个信号类型

• 信号的实现

管道

• 进程间基于内存文件的通信机制 进程不知道也不关心另一端

  • 子进程从父进程继承文件描述符

  • 缺省文件描述符0 stdin, 1 stdout, 2 stderr

• 管道相关系统调用

  • 读管道 read() scanf() 是基于它实现的

  • 写管道 write() printf() 是基于它实现的

  • 创建管道 pipe(rgfd)

    • rgfd是2个文件描述符组成的数组

    • rgfd[0] 是读文件描述符

    • rgfd[1] 是写文件描述符

消息队列

因为消息队列独立于创建它的进程，需要有系统调用完成消息队列的创建和销毁

• msgget()：获取消息队列标识

• msgsnd()：发送消息

• msgrcv()：接收消息

• msgctl()：消息队列控制

共享内存

• 为了保证数据的完整性需要信号量等机制协调共享内存的访问冲突

• shmget()：创建共享段

• shmat()：把共享段映射到进程地址空间

• shmdt()：取消共享段到进程地址空间的映射

• shmctl()：共享段的控制