第七章

什么是死锁：系统中有若干个进程并发执行，未申请到资源而等待，若持续则死锁。本质：相互等待形成环路。产生原因：进程执行顺序管理

资源的申请、分配、使用、释放

死锁的四个必要条件、资源分配图

死锁的预防（互斥、占有并等待、非抢占、循环等待）和避免（安全状态，资源分配图算法、银行家算法｛这个的时间复杂度？｝）的区别：分别限制申请和分配

死锁避免和死锁检测是一样的算法，但有哪些不同？比如避免着手于将来，检测是当前。另，两个算法那个更宽松

死锁恢复：代价最小－贪心算法

1 【死锁】：指两个或两个以上进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都无法推进下去

2 进程在使用资源之前必须申请，使用之后必须释放

3 如果所申请的资源正在被使用，则系统将进程推入该资源的等待队列

4 死锁的必要条件：1、【互斥】：至少有一个资源必须处于非共享模式，即一次只有一个进程使用；2、【占有并等待】：一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有3、【非抢占】：资源不能被抢占，即资源只能在进程完成任务后自动释放4、【循环等待】：有一组进程｛P0,P1,~,Pn｝，P0等待的资源被P1占有， P1等待的资源被P2占有，~，Pn等待的资源被P0占有；必须在以上4个条件同时满足才会出现死锁

5 【资源分配图】：图中用圆形表示进程，矩形表示资源，用边必须资源的分配情况或者是进程申请资源的方向；如果分配图没有缓，那么系统就没有进程死锁； 如果有环，就有可能存在死锁，不一定有！

6 处理死锁问题1、可使用协议以预防或避免死锁，确保系统不会进入死锁状态2、可允许系统进入死锁状态，然后检测它，并加以恢复3、可忽视这个问题，认为死锁不可能在系统内发生

7 只要确保至少一个必要条件不成立，就能预防死锁的发生1、互斥：一般不能通过否定互斥来预防死锁2、占有并等待：在一个进程申请其他资源之前，必须释放其现分配的所有资源3、非抢占：当一个进程处于等待时，如果其他进程申请其拥有的资源，那么该进程的资源可以被抢占； 一个进程要重新执行，她必须分配到其所申请的资源，并恢复其在等待时被抢占的资源4、循环等待：对所有的资源类型进行完全排序，且要求每个进程必须按照递增的顺序来申请资源

8 【死锁避免】：根据进程可能申请的每种资源类型实例的最大需求的事先信息，构造一个算法以确定系统绝不会进入死锁状态； 死锁避免算法动态地检测资源分配状态以确保循环等待条件不可能成立

9 【安全状态】：如果系统能按某个顺序为每个进程分配资源并能避免死锁。那么系统状态是安全的

10【安全序列】：进程顺序，如果对于每个Pi, Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj(j < i)所占有的资源，那么这一顺序称为安全序列；  如果存在安全序列，则系统是处于安全状态

11 【资源分配图算法】：在图中设三种边，“需求边”、“分配边”、“申请边”（只有当每种资源只有一个实例的时候适合）需求边：表示进程P可能在将来某个时候申请资源R，但是用虚线表示申请边：当进程P申请资源R时，需求边P->R 变成了申请边分配边：只有在将申请边P->R变成分配边R->P而不会导致资源分配图形成环时，才允许申请；当进程释放资源时，分配边变为需求边

12 【银行家算法】：当新进程进入系统时，它必须说明其可能需要的每种类型实例的最大数量； 当用户申请一组资源时，系统必须确定这些资源的分配是使系统仍然为安全状态的话就可以分配，否则进程必须等待；

13 【等待图】：是资源分配图的变种，删除所有资源类型节点，合并适当边；（仅适合于资源实例仅有一个）更确切的说是等待图中的有PI 到 PJ的边意味着进程PI在等待进程PJ释放一个PI所需要的资源；当且仅当等待图中有一个环，系统中存在死锁

14 死锁恢复的方法【进程终止】：(1)终止所有死锁进程、(2)一次只终止一个进程直到取消死锁循环为止【资源抢占】：通过抢占资源以取消死锁，逐步从进程中抢占资源给其他进程使用，直到死锁环被打开

第八章

内存管理：必须通过OS，分配内存，回收内存，进程内存的共享与保护

交换

连续内存分配（进程在内存中占据连续的存储空间）：知道起始位置、大小->；缺点：内碎片（进程<分配的大小）、外碎片（进程退出时的空洞，若小则无法利用）、不适宜实现虚拟存储器

分页（离散）：为了解决碎片、为了实现虚拟存储器

分页式系统：页、页框、两者映射即装入页表的地址映射过程

地址变换过程硬件的支持：TLB、页表、缺页中断处理、缺页异常……，软件支持：OS……

硬件设计决定分页／分段

页表结构，结合Intel Pentium

分段（离散）

分页式和请求分页式实现的区别：页表（引用位、中断位、修改位等反映页表功能）、地址交换过程、硬件的变化

1 内存是现代计算机运行的中心

2 内存由很大的一组字或字节组成，每个字或字节都有自己的地址

3 CPU根据程序计数器的值从内存中提取指令，这些指令可能会引起进一步对特定内存地址的读取和写入

4 内存单元只能看到地址流，而并不知道这些地址是怎么产生的或它们是什么地址（指令或数据）

5 CPU能直接访问的存储器只有内存和处理器内的寄存器

6 机器指令可以用内存地址作为参数，但是不能用磁盘地址； 因此，执行指令以及指令使用的数据必须在这些直接可访问的存储设备上，如果数据不在内存中，那么在CPU使用之前必须把数据移到内存中

7 要确保操作系统不被用户进程所访问，以及用户进程不被其他用户进程访问；首先要确保每个用户进程都有自己的独立的内存空间，并确保进程只访问其合法地址【基地址寄存器】：含有最小的合法物理内存地址【界限地址寄存器】：决定范围的大小只有操作系统可以通过特权指令来加载基地址寄存器和界限地址寄存器，并做出修改，不允许用户修改

8 操作系统在内核模式下执行可以无限制地访问操作系统和用户的内存

9 通常，程序以二进制可执行文件的形式存储在磁盘上； 为了执行，程序被调入内存空间

10 【输入队列】：在磁盘上等待调入内存以便执行的进程队列

11 【地址绑定】：源程序中的地址通常是用符号来表示的（如：count），编译器通常将这些符号地址绑定在可重定位的地址（如：从本模块开始的第14字节），链接程序或加载程序再将这些可重定位的地址绑定成绝对地址； 每次绑定都是从一个地址空间到另一个地址空间的映射

12 将指令和数据绑定到内存地址上有几种情况：1、编译时：在编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码； 如果将来开始地址发生了改变，那么必须重新编译代码（MS-DOS的.COM格式程序就是这种情况）2、加载时：在编译时不知道具体在内存中的地址，这时，编译器必须生成可重定位代码； 如果开始地址发生变化，只需要重新加载用户代码以引入新的地址值3、执行时：如果进程在执行时可以从一个内存段移到另一个内存段，就属于这种情况； 这种情况需要特定的硬件，绝大多数计算机操作系统采用这种办法

13 CPU所生成的地址通常称为【逻辑地址】，而内存单元所看到的地址（即加载到内存地址寄存器中的地址）通常称为【物理地址】

14 在编译事和加载时的地址绑定方法生成相同的逻辑地址和物理地址，但是在执行时绑定的是两者不一样的，通常称逻辑地址为【虚拟地址】

15 由程序所生成的所有逻辑地址的集合称为【逻辑地址空间】，相应的有【物理地址空间】

16 运行时从虚拟地址到物理地址的映射是有被称为【内存管理单元MMU】的硬件设备来完成的一种实现映射的方案：使用【重定位寄存器】，其实是前面所讲的基地址寄存器；用户进程所生成的地址在送交内存之前，都将加上重定位寄存器的值； 例如：逻辑地址为346，重定位寄存器的值是10000，则将映射到地址10346

17 用户程序绝不会看到真正的物理地址

18 【动态加载】：对于一个进程的子程序只有在被调用时才被加载，所有子程序都以可重定位的形式保存在磁盘上； 主程序装入内存并运行，当一个子程序需要调用到另一个子程序时，调用子程序首先检查另一个子程序是否已被加载，如果没有，【可重定位的链接程序】将用来加载所需要的子程序，并更新程序的地址表以反映这一变化，接着，控制传递给新加载的子程序

19 动态加载不需要操作系统提供特别的支持

20 【存根】是一小段代码，用来指出如何定位适当的内存驻留库程序，或者是如果该程序不在内存时应该如何装入库； 不管如何，存根会用子程序地址来替换自己，并开始执行子程序

21 【动态链接】：概念与动态加载相似，只是这里不是将加载延迟到运行时，而是将链接延迟到运行时； 这一特点通常用于系统库，如语言子程序库；若没有这一点，则每个程序都必须要有一份语言库的副本，这浪费了磁盘空间和内存空间； 动态链接也可以使用于库的更新； 动态链接需要操作系统的帮助；

22 【交换】：进程被换出（滚出）内存或换入（滚入）内存

23 通常一个交换出的进程需要回到它原来所占有的空间

24 交换需要【备份存储】，是快速磁盘，这必须足够大，以便容纳所有用户的内存镜像副本

25 具有动态内存需求的进程需要通过系统调用（请求内存和释放内存）来通知操作系统其内存需求变化情况

26 **************以下讨论是基于操作系统放在低内存**************************

27 【连续内存分配】：每一个进程位于一个连续的内存区域

28 MMU动态地将逻辑地址加上重定位寄存器的值后映射成物理地址，再将之送往内存单元

29 【多分区方法】：将内存分为多个固定大小的分区； 每个分区只能容纳一个进程； 因此多道程序的程度会受分区数所限制

30 在【可变分区】方案里，操作系统有一个表，用于记录哪些内存可用和哪些内存已被占用在一开始，所有的内存都可用于用户进程，因此可以作为一大块可用内存，称为【孔】； 当有新进程需要内存的时候，就为该进程查找足够大的孔， 如果找到，可以在孔内为该进程分配所需的内存，未分配的内存下次可以使用

31 内存不断的分配给进程，直到下一个进程的内存需求不能满足为止，这时没有足够大的可用孔来装入进程； 操作系统可以等到有足够的空间或者是往下扫描输入队列以确定是否有其他内存需求较小的进程可以被满足

32 当进程释放空间时，将所占有的孔与相邻的孔合并成大孔

33 从一组可用孔中选择一个孔的方法：（首次适应较佳）1、首次适应：分配第一个足够大的孔，就可停止2、最佳适应：分配最小的足够大的孔，必须查找整个表；可以产生最小的剩余孔3、最差适应：分配最大的孔，必须查找整个表；可以产生最大的剩余孔

34 【碎片】：内存之中的小空间，但已经不足以分配给进程使用了；首次适应和最佳适应方法都会有【外部碎片】

35 【50%规则】：假定有N个可分配块，那么可能有0.5N个块是外部碎片，即1/31/2的内存不能使用

36 通常将内存以固定大小的块为单元来分配，但若按这种方案，进程所分配的内存可能比所要的要大，这两个数字之差称为【内部碎片】

37 【紧缩】：解决外部碎片的问题；移动内存内容，以使所有空闲空间合并成一整块；（紧缩仅在重定位是动态并在运行时可采用）

38 【分页】：允许进程的物理地址空间可以是非连续的；（传统上，分页是由硬件支持的）

39 分页避免了将不同大小的内存块匹配到交换空间上的麻烦；

40 实现分页的基本方法涉及将物理内存分为固定大小的块，称为【帧】；而将逻辑内存也分为同样大小的块，称为【页】；当需要执行进程时，其页从备份存储中调入到可用的内存帧中； 备份存储也分为固定大小的块

41 由CPU生成的地址分为两部分：页号（P）和页偏移（d），页号作为页表（【页表】包含每页所在物理内存的基地址）的索引，基地址与页偏移组合成了物理地址，就可送交物理单元了

42 分页不会产生外部碎片，但是仍然有内部碎片；

43 分页的一个重要特点是用户视角的内存和实际的物理内存的分离

44 【帧表】：每一个条目对应着一个帧，以表示该帧是空闲还是已占用，如果占用，是被哪个占用

45 绝大多数的操作系统都为每个进程分配一个页表，页表的指针与其他寄存器的值（如指令计数器）一起存入进程控制块中，当调度程序需要启动一个进程时，它必须首先装入用户寄存器，并根据所保存的用户页表来定义正确的硬件页表值

46 【页表基寄存器PTBR】：指向存在内存中的页表

47 【转换表缓冲区TLB】：是关联的快速内存； 由键（标签）和值组成； 当关联内存根据给定定值查找时，它会同时与所有键进行比较TLB只包含页表中的一小部分条目，当CPU产生逻辑地址后，其页号提交给TLB，如果找到了页号就找到了帧号，并可用来访问内存； 如果页码不在TLB中（TLB失效），那么就需要访问页表，寻找到后将之放入TLB中，如有必要，置换出一个

48 有的TLB在每个条目中还保存地址空间标识符（ASID），可用来唯一标识进程，并为进程提供地址空间保护

49 【页表长度寄存器PTLR】：表示页表的大小； 可用于检查每个逻辑地址以验证其是否位于进程的有效范围

50 分页的优点之一在于可以【共享公共代码】

51 【可重入代码】、【纯代码】：可以共享，不能自我修改的代码，它从不会在执行期间改变

52 【向前映射页表】：地址转换由外向内（在两级或多级页表结构中，从外部页表到内部页表

53 【哈希页表】：处理超过32位地址空间的常用方法是使用哈希页表，并以虚拟页码作为哈希值；哈希页表的每一条目都包括一个链表的元素，每个元素包括：（1）虚拟页码；（2）所映射的帧号；（3）指向链表中下一个元素的指针；算法工作：虚拟地址中的虚拟页号转换到哈希表中，用虚拟页号与链表中的每一个元素的第一个域相比，如果匹配（不匹配就比下一个），那么相应的帧号（第二个域）就用来形成物理地址

54 【群集页表】：类似于哈希页表，但是每一个条目不只包括一页信息，包括多页； 因此一个页表条目可以存储多个物理页帧的映射，对于稀疏地址空间特别有用；

55 【反向页表】：对于每个真正的内存页或帧才有一个条目； 每个条目包含保存在真正内存位置的页的虚拟地址以及拥有该页的进程的信息； 整个系统只有一个；

56 【分段】：逻辑地址空间是由一组段组成的； 每个段都有名称和长度，地址指定了段名称和段内偏移；因此，用户可以通过段名称和偏移两个量来指定地址

57 【段表】：段表的每个条目都有段基地址和段界限（段的长度）

58 段表的使用：一个逻辑地址由：（1）段号（段名称）和（2）段内偏移；如果偏移合法，那么就与段基地址相加而得到所需字节在物理内存的地址； 如果不合法，会陷入操作系统

59 在pentium系统中，CPU产生逻辑地址，它被赋给分段单元； 分段单元为每个逻辑地址生成线性地址，然后线性地址交给分页单元，它接下来生成内存中的物理地址；（分段单元和分页单元相当于内存管理单元MMU）

60 进程的逻辑空间被分成两部分：第一部分最多由8K个段组成，这部分为私有，存于【本地描述符表LDT】； 第二部分最多由8K个段组成，这部分为所有进程所共享，存于【全局描述符表GDT】；LDT, GDT的每个条目为8B，包括一个段的详细信息，如基位置和段界限等；逻辑地址是由一对（选择器，偏移）组成的，其中选择器是16位的数：s 表示段号（13位）， g 表示是在GDT还是LDT（1位），p是保护信息偏移是一个32位的数，用来表示字节（或字）在段内的位置