【操作系统】第十一章
来源：操作系统_清华大学(向勇、陈渝)
1.死锁问题
死锁：一组阻塞的进程（两个或多个），持有一种资源，等待获取另一个进程所占有的资源，而导致谁都无法执行。
一组阻塞的进程持有一种资源等待获取另一个进程所占有的一个资源。
例子：系统有2个磁带驱动器，P1和P2各有一个，都需要另外一个。
由于进程的并发执行引起了死锁。
2.系统模型
死锁模型：
1.资源类型：比如CPU cycles , memory space , I/O devices，某个进程运行中的共享变量
2.资源个数可以有n个
3.每个进程可以怎么使用资源：
request/get ——-free resource
use/hold ————requested/used resource, other processes cannot get
release ———–free resource
可重复使用的资源：
1.在一个时间只能一个进程使用，且不能被删除。OS避免杀死拥有资源的进程。
2.进程使用资源后要释放，让其他进程重用
3.有物理资源（cpu， I/O通道，主和副存储器），也有抽象的资源（设备和数据结构，如文件，数据库和信号量）
4.如果每个进程拥有一个资源并请求其他资源，可能导致死锁
怎么使用资源？
1.创建，销毁—内存管理单元
2.I/O缓冲区的中断，信号，消息，信息
3.如果接受信息阻塞可能会发生死锁
4.少见的组合事件可能会引起死锁
如何表述资源的分配？
资源分配图，利用顶点V和边E的集合表示资源
V有两种
P={P1, P2…Pn } 所有进程
R={R1, R2… Rm} 所有资源类型
Requesting/claiming edge –directed edge Pi→Rj
Assignment/holding edge –directed edge Rj→Pi
左图没有死锁，右图死锁，死锁会有闭环出现
但有闭环出现不一定会死锁，因为资源是循环的
如果不包含闭环—>没有死锁
如果包括闭环，且每个资源类只有一个实例-→死锁 ；否则，不会。
3.死锁特征
死锁的特征 : 四个的必要条件
1.互斥（在一个时间只能有一个进程使用资源）
2.持有并等待（进程保持至少一个资源正在等待获取其他进程持有的额外资源）
3.无抢占，一个资源只能被进程自愿释放，进程已经完成了它的任务之后
4.循环等待，形成闭环
4.死锁处理方法
死锁处理方法：
1.死锁预防dead-lock prevention
2.死锁避免 deadlock avoidance
3.死锁检测 deadlock Detection
4.死锁恢复 Recovery from Deadlock
死锁处理办法：
1.确保系统永远不会进入死锁状态。
2.运行系统进入死锁状态，然后恢复。
3.忽略这个问题，假设系统中从来没有发生死锁；用于大多数操作系统，包括UNIX。
5.死锁预防和死锁避免
限制申请方式：
1.互斥 共享资源不是必须的，必须占用非共享资源。
2.占用并等待 必须保证当一个进程请求的资源，它不持有任何其他资源。
需要进程请求并分配所有资源，它开始执行之前或允许进程请求资源仅当进程没有资源。
资源利用率低；可能发生饥饿。
死锁预防dead-lock prevention ，只要打破死锁出现的条件，想到死锁的四个必要条件。
1.互斥—占用非共享资源 会增加不确定性 不推荐
2.占用并等待—保证当一个进程请求资源时，不持有任何其他的资源，all or nothing 需要进程请求并分配其所有资源，资源利用率低，可能饥饿
3.无抢占—允许抢占占有某些资源的进程 ， 如果进程占有某些资源，并请求其它不能被立即分配的资源，则释放当前正占有的资源，被抢占资源添加到资源列表中，只有当它能够获得旧的资源以及它请求新的资源，进程可以得到执行
4.循环等待—对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请，会出现资源利用不够
6.银行家算法
7.死锁检测和死锁恢复
死锁检测deadlock detection
死锁恢复recovery from deadlock：
1.通过杀死所有死锁进程，
2.在一个时间内终止一个进程直到死锁消除等方式完成，都干扰了进程的正常运行，都有强制性。
8.IPC概述
IPC: inter process communication 进程间通信
IPC：
1.进程通信的机制及同步
2.不使用共享变量的进程通信
IPC facility 提供2个操作：
1.send(message) - 消息大小固定/可变
2.receive (message)
如果P和Q想通信，需要：
1.在它们之间建立通信链路
2.通过send/receive交换消息
通信链路的实现
物理（例如，共享内存，硬件总线）
逻辑（如逻辑属性）
进程要相互独立，但另一方面也要相互协作
发送消息，接收消息
左侧进程A和B是间接的通信，右侧是直接通信
直接通信（为了实现直接通信，要有发送和接收的ID ）：
1.进程必须正确的命名对方：
send(P,message) 发送信息到进程P
receive(Q,message)从进程Q接受消息
2.通信链路的属性
自动建立链路
一条链路恰好对应一个通信进程
每对进程之间只有一个链路存在
链路可以是单向，但通常为双向的
间接通信（为了实现间接通信，要发送到共享区，发送方和接收方都不关注具体的另一方是谁 ）：
1.定向从消息队列接收消息
每个消息队列都有一个唯一的ID
只有他们共享了一个消息队列，进程才能通信
2.通信链路的属性
只有进程共享一个共同的消息队列，才建立链路
链接可以与许多进程相关联
每对进程可以共享多个通信链路
连接可以是单向或者双向
间接通信：
操作：1.创建一个新的消息队列 2.通过消息队列发送和接收消息 3.销毁消息队列
9.信号、管道、消息队列和共享内存
队列的消息被附加到链路的3种方式：
1.0容量—0 messages 发送方必须等待接收方
2.有限容量—n messages 的有限长度，发送方在队列满的时候要等待
3.无限容量—无限长度，理想状况，不用等
ipc常用手段：信号，管道，消息队列，共享内存
信号：
硬件中断interrupt，信号是软件中断，通知有事件要处理
应用程序会catch，默认，停下来处理信号，特殊处理函数。
管道：用于数据交换，与信号不同。理解为内存中的一个buffer
消息队列：
管道必须有父进程，数据是字节流，没有数据结构。消息队列可以多个不相干的进程来传递数据，而且message作为一个字节序列存储，message quenues是消息数组。是一个有意义的结构化。
共享内存：
直接的方式。不用系统调用send&receive，数据量最大，最快。
开始要创建共享区域。方便，高效，没有多余的拷贝。
每个进程都有私有地址空间，其中明确地设置了共享内存段。同一块物理内存映射到不同的地址空间中去。页表。。。
但必须同步数据访问。写的时候要上锁。同步互斥。
Linux Unix中常见
Socket机制。