资源分配图

有两个集合,一个是进程集合,另一个是资源集合,如果进程i需要某资源j的一部分,则连边$i\to j$, 如果一个资源j的一部分被分配给了进程i,则连边$j\to i$,
资源分配图出现了有向环是发生了死锁的必要不充分条件。因为边只表示一部分资源的分配,而不是全部资源

死锁的必要条件

互斥、持有并等待、无抢占、循环等待

死锁预防

破坏互斥不现实,破快占用并等待不实现,因为资源无法动态预判,可能发生饥饿,破坏抢占也不现实,破坏循环等待有效,将资源排序并让进程按顺序申请。

死锁避免

判断某个资源的分配是否导致了死锁,需要系统具有额外的先验信息提供,
安全状态: 存在序列$P_1$,$P_2$…,针对每个$P_i$,$P_i$要求的资源能够由当前可用资源+所有的$P_j$持有的资源来满足$j\lt i$

银行家算法

寻找安全序列是否存在的算法。

死锁的检测

1简化资源分配图为线程等待图,如果线程等待图出现了环则发生了死锁。
2找到能结束的程序,假设他结束,然后拿走资源,循环。
杀,按照优先级杀掉死锁,剩余运行时间,占用自用资源、完成所需要的资源、需要终止的进程数量等
回滚,重启进程,这有可能导致某个进程一直被重启

IPC 进程间的通信

通信有两种模型,第一是直接通信,第二是通过内核间接通信
通信可以是阻塞或者非阻塞的
通信缓存区的大小可以是有限的或者无限的

信号

发出通知信息,软件中断和事件处理,收到信号的时候可以指定信号处理函数被调用或者依靠操作系统的默认操作,
应用程序要先注册信号处理函数,当收到信号的时候,在内核态修改应用程序的堆栈,然后跳回用户态执行,即操作系统来帮助跳转到信号处理函数执行,然后返回之前的现场

管道

1
ls | more

发送数据 shell -> ls -> 管道 -> more, 注意管道是有限的,可能会阻塞。

消息队列

管道是字节流,不是结构化数据。
Message是一个字节序列储存,Message Queues是消息数组,然后FIFO或者FILO实现。

共享内存

方便、快速、高效、但是需要同步, 将同一块物理内存映射到不同的逻辑页面.

socket

套接字