第1章 引论·
操作系统是一个程序，是一组管理计算机硬件资源的软件集合，向计算机程序提供共性服务。
- 控制计算机资源；
- 给用户提供接口或虚拟机。
OS的历史沿革·
批处理：用户提交作业成批送入计算机，由作业调度程序自动选择作业运行。涉及到Mainframe基本功能，排队论、统筹学。
批处理系统，分为联机批处理系统（作业的输入/输出由CPU来处理）和脱机批处理系统（输入/输出脱离主机控制）。 两者均有CPU空闲，均为单道程序系统
多道程序系统：多个程序同时进入内存，交替使用I/O设备和CPU。
多道程序系统的出现，标志着操作系统渐趋成熟的阶段，先后出现了作业调度管理、处理机管理、存储器管理、外部设备管理、文件系统管理等功能。
分时系统：多个用户分享使用同一台计算机。多个程序分时共享硬件和软件资源
两种典型分时系统：
-
Multics/Unix (1968/1970)
-
IBM VM 360/370 (1966/1972)
Unix、DOS、Windows、Linux（使用GNU）
分布式网络化
小结·
操作系统基本实现机制·
异常(exception): 陷阱(trap)和中断(interrupt)·
操作系统的基本类型·
- 批处理系统
- 分时系统
- 实时系统
- 混合型
操作系统的功能·
处理机管理·
核心任务：分配CPU时间 ——进程、线程管理——公平分配、保证非阻塞、按优先级分配
进程管理：程序是静态实体，进程是执行中的程序。进程的调度：创建、挂起、激活。进程间通信：同步，互斥，死锁。
存储器(内存)管理·
管理缓存、主存、磁盘等所形成的多级存储架构，为多道程序的并发提供良好的环境。
– 内存分配和存储无关性：方便用户 – 内存保护：互不干扰 – 内存扩充：虚拟存储器
设备管理·
管理输入/输出设备，屏蔽差异性，提供并发访问
– 设备无关性：逻辑设备->物理设备 – 设备分配：独享、共享和虚拟 – 设备的传输控制：中断、通道
文件系统·
将磁盘变成一个很容易使用的存储媒介提供给用户使用。 – 文件存储空间的管理 – 目录管理 – 文件读、写管理 – 文件保护 – 向用户提供接口
作业控制·
- 作业调度
- 作业控制。
- 批量型作业
- 终端型作业
第2章 系统引导·
BootLoader·
引导加载程序，是系统加电后运行的第一段软件代码，是操作系统内核运行之前运行的一段小程序
BootLoader是Booter和Loader的合写，前者要初始化系统硬件使之运行起来，至少是部分运行起来；后者将操作系统映像加载到内存中，并跳转到操作系统的代码运行。
- MIPS处理器大多用于嵌入式系统，嵌入式系统常用U-boot作为OS启动装载程序，U-Boot，全称 Universal Boot Loader；
- X86处理器通常采用LILO和GRUB。
U-Boot启动流程·
大多数BootLoader都分为stage1和stage2两大部分，U-boot也不例外。
- 依赖于cpu体系结构的代码（如设备初始化代码等）通常都放在stage1且可以用汇编语言来实现；
- stage2则通常用C语言来实现，这样可以实现复杂的功能，而且有更好的可读性和移植性。
启动及OS引导·
启动第一步——加载BIOS·
BIOS进行硬件自检以及读取启动顺序
启动第二步——读取MBR，装载MBR到内存特定地址·
启动第三步——Boot Loader，运行主引导程序·
第3章 内存管理·
3.1 多道程序的存储管理·
固定（静态）式分区分配，程序适应分区。系统初始化时将存储空间分为若干个区域，之后再将这些区域分配给用户作业。
可变（动态）式分区分配，分区适应程序。动态确定分区边界。
内外碎片造成巨大空间浪费
跟踪内存使用情况？位图表示法（分区表）和链表表示法（分区链表）。
位图表示法空间成本固定，时间成本低，容错能力差（不知道被占用的原因）。
链表表示法时间成本高，容错能力较好。
可变分区管理·
内存分配采用两张表：已分配分区表和未分配分区表。操作为分配、回收内存。
基于顺序搜索的分配算法·
基于索引搜索的动态分区分配算法·
大中型系统采用
快速适应算法（分类搜索法）·
把空闲分区按容量大小进行分类，经常用到长度的空闲区设立单独的空闲区链表。为多个空闲链表设立一张管理索引表。
伙伴系统·
介于固定分区与可变分区之间的动态分区技术
在分配存储块时将一个大的存储块分裂成两个大小相等的小块。
已分配和空闲分区大小均为2的整数次幂。每次有一个新的大小请求先看有无最靠近这个大小的幂次的分区，没有就向上查找并分裂。
3.2 程序从存储到执行·
存储分配三种方式·
- 直接指定。直接使用实际地址
- 静态分配
- 动态分配
可重定位分区分配·
定时的或在内存紧张时，移动某些已分配区中的信息，把存储空间中所有的空白区合并为一个大的连续区。
程序的链接和装入·
- 编译(compile)：由编译程序将用户源程序编译成若干个目标模块。
- 链接(linking)：由链接程序将目标模块和相应的库函数链接成可装载模块（可执行文件）。
- 装入(loading)：由装载程序将可装载模块装入内存。一般采用动态运行时装入方式
链接方式·
-
静态链接 直接将共享库中代码链接如程序代码中
-
动态链接 需要时才链接特定的模块
重定位·
在装入时对目标程序中的指令和数据地址的修改，或映射过程。
多重分区分配·
一个作业往往由相对独立的程序段和数据段组成，将这些片段分别装入到存储空间中不同的区域内的分配方式。
程序段·
一个程序本质上都是由 bss段、data段、text段三个组成的。
bss段：（bss segment）用来存放程序中未初始化的全局变量的一块内存区域。bss是英文Block Started by Symbol的简称。bss段属于静态内存分配。
data段：数据段（data segment）用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。
text段：代码段（code segment/text segment）用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读(某些架构也允许代码段为可写，即允许修改程序)。在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。
栈(stack)：存放、交换临时数据的内存区
-
用户存放程序局部变量的内存区域，（但不包括static声明的变量，static意味着在数据段中存放变量）。
-
保存/恢复调用现场。在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。
堆（heap）：存放进程运行中动态分配的内存段
- 它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）。
C语言各个段地址解析：
https://blog.csdn.net/zhengshifeng123/article/details/79756830
gcc编译与链接·
1 | gcc -o main main.c extra.c #-o 编译+链接 |
gcc调用包含的几个工具：
- cc1：预处理器和编译器
- as：汇编器
- collect2：链接器
Linux下可执行文件的格式·
ELF（Executable and Linkable Format）文件
- 可重定位（relocatable）文件，保存着代码和适当的数据，用来和其他的object文件一起来创建一个可执行文件或者是一个共享文件。
- 可执行（executable）文件，保存着一个用来执行的程序，该文件指出了exec（BA_OS）如何来创建程序进程映像
- 共享object文件，保存着代码和合适的数据，用来被下面的两个链接器链接。第一个是链接编辑器（静态链接），可以和其他的可重定位和共享object文件一起来创建object文件；第二个是动态链接器，联合一个可执行文件和其他的共享object文件来创建一个进程映象。
编译，链接，重定位，装载，运行。五个步骤完成程序的执行全流程。
3.3 页式内存管理·
程序、进程和作业·
程序—静止的，是存放在磁盘上的可执行文件
进程—动态的，包括程序和程序处理对象，是分配资源的基本单位。
-
完成操作系统功能的进程是系统进程。
-
完成用户功能的进程称为用户进程。
作业—是用户需要计算机完成的某项任务，是要求计算机所做工作的集合。
一个作业划分为多个进程来完成，一个进程又由其实体—程序和数据集合来组成。
分页式存储管理·
纯分页系统：没有页面置换功能。所有页一次性全部装入主存。
页：每个作业的地址空间分成一些大小相等的片，称之为页面或页。
存储块：主存的存储空间也分成和页面相同大小的片，称为存储块，或页框。
分页地址结构：
逻辑地址·
| 31-12 | 11-0 |
|---|---|
| 页号p | 页内偏移w |
物理地址·
| 21-12 | 11-0 |
|---|---|
| 块号 | 块内偏移d |
现代操作系统中最常用的页面大小为4KB
内存分配基本思想·
- 以页为单位进行分配，并按程序（作业）的**长度（页数）**进行分配；
- 逻辑上相邻的页，物理上不一定相邻。
数据结构·
每个进程有一个进程页表，描述该进程占用的物理页面及逻辑排列顺序。
整个系统有一个物理页面表，描述物理内存空间分配使用情况。
整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里。
地址变换—页表查找·
关于页表·
- 页表放置在内存中，记录了进程的现场信息。记录进程的内存分配情况以及实现进程运行时的动态重定位。
- 访问一个数据需要访问内存两次（页表一次，内存一次）。
- 页表的基址及长度由页表寄存器给出。
地址转换机构·
逻辑地址分为页号和页内地址两部分。先进行越界保护。之后进行页表定位：页表始址+页号*页表项长度
查询页表，读出块号。物理地址=块号+块内地址（块内地址=页内地址）
提高分页效率·
- 减少页表大小
- 提高地址映射速度
解决问题方法·
- 动态调入页表：只将需用的部分页表项调入内存
- 多级页表
二级页表：
- 一级目录：页目录表
- 二级目录：页表
参考博客：https://www.jianshu.com/p/51c2286a6268
如果是64位操作系统，内存也是4G，每个页面大小也为4KB，采用三级页表，需要字对齐，则虚拟地址应该为多少位？
首先每一级页表的所占空间大小应该都是一个页面的大小。即4KB（因为自映射机制）
又由于64位操作系统需要字对齐，所以实际上每一级目录只占用12-3=9位。
因此三级目录就需要9*3+12=39位
多级页表带来访存效率低下问题
页表快速访问机制——MMU·
CPU内部增加了一个硬件单元，称为存储管理单元MMU（Memory Management Unit）
- 页表Cache：又称为TLB，用于存放虚拟地址与相应的物理地址；
- TLB控制单元：TLB内容填充、刷新、覆盖，以及越界检查。
- 页表（遍历）查找单元：若TLB未命中，自动查找多级页表，将找到的物理地址送与TLB控制单元。（可用软件实现）
反向页表、哈希页表·
页的保护·
- 地址越界保护
- 页表中设置保护位（只读，读写，执行）
页面大小习题·
假设进程的平均大小是1MB(s=1MB)，每个页表项需要8个字节(e=8B)。页面大小设置为多少字节比较好？
答：$f§=s*e/p+p/2，求minf§$ $为4kB$
多级页表再理解·
指令给出的地址除偏移地址之外的各部分全是各级页表的页表号或页号，且都是物理页号
3.4 分段存储管理·
逻辑地址结构为：段号S+位移量W
段表记录了段与内存位置对应关系，保存在内存中。
段表基地址和长度由段表寄存器给出。访问一个字节数据/指令需要访问内存两次（段表1次，内存1次）。
先比较段号S和段表长度TL，不越界则检查段内地址d是否超过段长。
信息共享——可重入代码（纯代码Pure Code），允许多个进程同时访问，但不允许任何进程对其进行修改。
可采用分段共享，
段页式存储管理·
分段方法——分配和管理虚拟存储器
分页方法——分配和管理实存储器
3.5 虚拟存储管理（※）·
虚拟地址空间：并不真实存在，格式按字节从0开始编址所形成的空间
虚拟存储的基本原理·
- 按需装载
- 缺页调入
- 不用调出
缺页错误（ Page Fault）处理机制·
当进程执行过程中需访问的页面不在物理存储器中时，会引发发生缺页中断，进行所需页面换入，步骤如下：
- 陷入内核态，保存必要的信息（OS及用户进程状态相关的信息）。（现场保护）
- 查找出来发生页面中断的虚拟页面（进程地址空间中的页面）。这个虚拟页面的信息通常会保存在一个硬件寄存器中，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析该指令，通过分析找出发生页面中断的虚拟页面。（页面定位）
- 检查虚拟地址的有效性及安全保护位。如果发生保护错误，则杀死该进程。（权限检查）
- 查找一个空闲的页框(物理内存中的页面)，如果没有空闲页框则需要通过页面置换算法找到一个需要换出的页框。（新页面调入（1））
- 如果找的页框中的内容被修改了，则需要将修改的内容保存到磁盘上。（注：此时需要将页框置为忙状态，以防页框被其它进程抢占掉）（旧页面写回）
- 页框“干净”后，操作系统将保存在磁盘上的页面内容复制到该页框中。（新页面调入（2））此时会引起一个磁盘读写调用，发生上下文切换（在等待磁盘读写的过程中让其它进程运行）。
- 当磁盘中的页面内容全部装入页框后，向操作系统发送一个中断。操作系统更新内存中的页表项，将虚拟页面映射的页框号更新为写入的页框，并将页框标记为正常状态。（更新页表）
- 恢复缺页中断发生前的状态，将程序指针重新指向引起缺页中断的指令。（恢复现场）
- 程序重新执行引发缺页中断的指令，进行存储访问。（继续执行）缺页处理过程涉及了用户态和内核态之间的切换，虚拟地址和物理地址之间的转换（这个转换过程需要使用MMU和TLB）
3.6 页面置换·
1.最优置换 OPT·
-
需要用先验知识，无法实现，作为基准衡量其他算法效果。
-
置换掉未来最久不被使用的页
2.FIFO类算法·
先进先出 FIFO·
用一个队列维护
性能较差，因为较早调入的页往往访问频率高
Belady 现象·
FIFO容易出现
分配页面增多，缺页率反而增高
改进FIFO—Second Chance·
每个页面增加一个访问标志位，标识进入缓存队列后是否再次被访问过
如果一个页面进入后被访问，则设置标识位为1。在将要淘汰A时，将A标识位设成0，并将A移动到队列头（视为新加入的）
改进FIFO—Clock·
Second Chance的改进版，也叫最近未使用算法
使用环形队列，缺页时当前指针指向的P如果访问标记为1，则清零并移动指针到P的下一个
FIFO类算法命中率较低，实际应用较少。
FIFO算法性能比较·
3.最近最少使用 LRU算法·
核心思想：最近被访问过，将来被访问概率增高
淘汰掉最先进入队列里且被访问次数最少的页面，可采用链表实现
4.其他替换算法·
-
LRU类：LRU2， Two queues（2Q）， Multi Queue（MQ）
-
LFU类： LFU（Least Frequently Used）， LFU-Aging， LFU*-Aging， Window-LFU；
-
其它： Most Recently Used（MRU），Adaptive Replacement Cache（ARC），Working Set（WS），Working Set Clock（WSclock）
写时复制·
- 两个进程共享同一块物理内存，每个页面都被标志成了写时复制。共享的物理内存中每个页面都是只读的。
- 如果某个进程想改变某个页面时，就会与只读标记冲突，而系统在检测出页面是写时复制的，则会在内存中复制一个页面，然后进行写操作。
- 新复制的页面对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的。
3.7 页目录自映射·
第4章 进程与并发程序设计·
4.1 进程与线程·
并发与并行·
并发：两个活动都处在各自的起点到终点间的某一处。
并行：同一时间度量下同时运行在不同的处理机上
并发不一定是并行
并行性的确定—Bernstein条件·
程序并发执行出现竞争
归结为：不存在一个数据集两个进程同时需要写
进程概念·
结构特征：包含程序段，数据段，进程控制块（PCB）
一个进程应该包括：
- 程序的代码；
- 程序的数据；
- PC中的值，用来指示下一条将运行的指令；
- 一组通用的寄存器的当前值，堆、栈；
- 一组系统资源（如打开的文件）
进程状态与控制·
进程控制实现：原语——常驻内存，只在内核态下执行，指令序列连续不可分割
创建原语(fork exec)
撤销原语(kill)
进程三种基本状态·
就绪(Ready)：已获得处理机外所需资源，等待CPU的分配
执行(Running)：占用处理机资源。无进程可执行时，自动执行系统idle进程（相当于空操作）
阻塞(Blocked)：正在执行的进程，因等待某事件，暂时无法继续执行，放弃处理机处于暂停状态
挂起进程模型·
进程控制块·
- 进程标识符 （进程ID）
- 程序、数据地址
- 当前状态 系统会把相同状态的进程组成队列
- 现场保护区 需要等待时保存CPU各种状态信息
- 同步与同步机制 实现进程间互斥同步、通信所需的信号量
- 优先级
- 资源清单 拥有的除CPU外的资源记录
- 链接字 该进程所在队列中下一个进程PCB首地址
线程概念·
进程 (process task) 包含了两个概念：资源拥有者和可执行单元
可执行单元——线程(thread) 将资源与计算分离，提高并发效率
进程是资源分配的基本单位，线程是处理机调度的基本单位
线程的实现方式 ※※·
用户级线程：User level threads(ULT)·
线程在用户空间,通过library模拟的thread
内核级线程：Kernel level threads (KLT)·
kernel有好几个分身 多线程内核
混合实现方式·
使用内核级线程，将用户级线程与某些或者全部内核线程多路复用起来，形成混合的线程实现方式。
线程模型·
- Many-to-One Model 多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。
- 优点：线程管理在用户空间进行，效率高
- 缺点：一个线程被阻塞，整个进程被阻塞；多个线程不能并行运行在多处理机上
- One-to-one Model 将每个用户级线程映射到一个内核级线程
- 优点：一个进程阻塞可以让另一线程继续，并发能力强
- 缺点：每创1个用户级线程都需要创1个内核级线程，开销大
- Many-to-Many Model 将 n 个用户级线程映射到m 个内核级线程上，要求m <= n。
- 特点：集前2者之长
4.2 同步与互斥·
互斥-间接制约：多个进程不能同时进入同一组共享变量临界区域
同步-直接制约：有效地共享资源、相互合作
基于忙等的方式·
软硬件方法都不可取
Lamport面包店算法、Eisenberg算法
基于信号量的方法·
经典信号量机制·
1 | //简单表述 |
信号量必须且只能置一次初值，且只能由P/V操作来改变
物理意义·
- S.value为正时表示资源的个数
- S.value为负时表示等待进程的个数
- P操作分配资源
- V操作释放资源
应用·
1 | #互斥 初始化S=1 |
基于管程的同步与互斥·
管程：高级同步原语
把分散的临界区集中起来，为每个可共享资源设计一个专门机构来统一管理各进程对该资源的访问，这个专门机构称为管程。
管程互斥进入，由编译器进行实现、
进程间通信(Inter-Process-Comm)·
- 管道（Pipe）及命名管道（Named pipe或FIFO）
- 消息队列（Message） 两个通信原语
- send(destination, &message)
- receive(source, &message)
- 共享内存（Shared memory）
- 最有用,最快
- 同一块物理内存被映射到进程A、B各自的进程地址空间
- 共享内存可以同时读但不能同时写，则需要同步机制约束
- 信号量（Semaphore）
- 套接字（Socket）
- 信号（Signal）
4.3 经典进程同步问题·
生产者－消费者问题(the producer consumer problem)·
若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而 “消费者”进程不断读出；共享缓冲区共有 N个；任何时刻只能有一个进程可对共享缓冲区进行操作。
信号量写法·
管程写法·
读者－写者问题(the readers-writers problem)·
问题描述：对共享资源的读写操作，任一时刻 “写者”最多只允许一个，而 “读者”则允许多个，即 “读－写”互斥，“写－写”互斥，“读－读”允许
1 | //1.读者占优势算法 |
哲学家进餐问题(the dining philosophers problem)·
问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；
哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。
如何保证哲学家们的动作有序进行？如：不出现相邻者同时进餐；不出现有人永远拿不到筷子。
理发师问题·
理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子；
如果没有顾客，理发师便在理发椅上睡觉，当一个顾客到来时，叫醒理发师；
如果理发师正在理发时，又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。
吸烟者问题·
三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。
三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。
供应者将两样东西放在桌子上，允许一个吸烟者吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。
试为吸烟者和供应者编写程序解决问题。
4.4调度·
基本概念·
控制协调多个进程对CPU的竞争
调度类型·
- 高级调度：接纳多少个作业，接纳哪些作业
- 中级调度：内外存交换
- 低级调度：CPU资源角度，非抢占式和抢占式（时间片原则，优先权原则，短作业（进程）优先
设计调度算法要考虑的问题（设计要点）·
进程优先级（数）·
优先数反映了某个优先级
静态优先级、动态优先级
进程就绪队列组织·
按优先级排队方式
占用CPU的方式·
- 不可抢占式方式。一直占用处理器，直到该进程自己因调用原语操作，或等待I/O等原因进入阻塞状态，或时间片用完时才让出处理器，重新进行。
- 抢占式方式。就绪队列中一旦有优先级高于当前运行进程优先级的进程存在时，便立即进行进程调度，把处理器转给优先级高的进程
进程的分类·
分类1·
- I/O Bound（I/O密集型）
- CPU bound（CPU密集型）
分类2·
- 批处理进程（Batch Process) 编译器，科学计算
- 交互式进程（Interactive Process) Word 触控性GUI
- 实时进程（Real-time Process) 视频、音频
批处理系统的调度算法·
吞吐量、平均等待时间和平均周转时间·
批处理常用调度算法·
- 先来先服务（FCFS：First Come First Serve)。
- 按先后次序分派CPU，当前进程或作业直到执行完或阻塞才让出CPU。唤醒进程后等到当前作业或进程让出CPU。
- 利于长作业，不利于短作业
- 利于CPU密集型，不利于IO密集型
- 最短作业优先（SJF：Shortest Job First)
- 对长作业不利
- 最短剩余时间优先（SRTF：Shortest Remaining Time First）
- 短作业改进为抢占式。新就绪进程比当前进程完成时间更短，则抢占。
- 最高响应比优先（HRRF：Highest Response Ratio First）
- 响应比：$RP=1+\frac {已等待时间} {要求运行时间}$
- 既照顾了短作业，又不让长作业等太久
交互式系统·
-
时间片轮转(RR：Round Robin)
- 排队(FCFS原则)—轮转(每次就绪队列队首进程执行一个时间片)—中断(时间片结束发生中断)—抢占（暂停当前进程并移到就绪队列末尾)—出让(可以未使用完时间片就出让)
- 静态动态优先级
-
多级队列(MQ：Multi-level Queue)
- 引入多个就绪队列，并区别对待各个队列
-
多级反馈队列(MFQ： Multi-level Feedback Queue)
实时系统·
- 静态表调度Static table-driven scheduling
- 单调速率调度RMS：Rate Monotonic Scheduling
- 最早截止时间优先算法EDF：Earliest Deadline First
多处理机调度·
- 自调度
- 成组调度
- 专用处理机调度
4.5 死锁·
死锁定义：一组进程中，每个进程都无限等待被该组进程中其它进程所占有的资源，在无外力介入的条件下，将因永远分配不到资源而无法运行的现象。
发生原因
- 资源竞争
- 并行执行顺序不当
死锁发生的四个必要条件·
- 互斥条件
- 请求和占有条件
- 不可剥夺条件
- 环路等待条件
死锁预防·
- 打破互斥条件
- 打破占有且申请条件
- 打破不可剥夺条件
- 打破循环等待条件
资源分配图（RAG）算法·
有向图G的顶点为资源或进程，从资源R到进程P的边表示R已分配给P，从进程P到资源R的边表示P正因请求R而处于等待状态。
封锁进程·
是指某个进程由于请求了超过了系统中现有的未分配资源数目的资源，而被系统封锁的进程。
非封锁进程·
即没有被系统封锁的进程
资源分配图的化简方法·
假设某个RAG中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：
当Pi有请求边时，首先将其请求边变成分配边(即满足Pi的资源请求)，而一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。（反复进行）
死锁定理·
系统中某个时刻t为死锁状态的充要条件是t时刻系统的资源分配图是不可完全化简的。
在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全化简的；反之的是不可完全化简的
安全序列与安全状态·
安全状态：系统存在一个进程执行序列<p1,p2,…pn>可顺利完成（里面有一个进程需要的附加资源可以被当前系统中可用资源加上上所有进程Pj（j < i）当前占有资源之和所满足
不安全状态不一定死锁，但死锁一定不安全
安全与不安全示例·
