死锁定义各进程互相等待对方手里的资源, 导致各进程都阻塞, 无法向前推进的现象区分死锁和饥饿都是进程无法顺利向前推进导致的现象死锁一定是循环等待对方手里的资源导致的, 因此如果有死锁现象, 那至少有两个或者两个以上的进程同时发生死锁. 另外发生死锁的进程一定处理堵塞饥饿可能只有一个进程发生饥饿, 发生饥饿的进程既可能是阻塞态(长期得不到的 I/O设备), 也可能是就绪态 (长期得不到处理机)产生死锁的必要条件 (必须同时满足以下四个条件, 不然死锁不会发生)互斥条件只有对必须互斥使用的资源的争抢才会导致死锁请求和保持条件进程已经保持了至少一个资源, 但又提出了新的资源请求, 而该资源又被其他进程占有, 此时请求进程被阻塞, 但又对自己已有的资源保持不变循环等待条件存在一种进程资源的循环等待链, 链中每一个进程已获得的资源同时被下一个进程所请求注意: 发生死锁时一定有循环等待, 但是发生循环等待时未必死锁不剥夺条件进程所获得的资源在未使用完之前, 不能由其他进程强行夺走, 只能主动释放死锁预防静态策略(预防死锁)破坏死锁产生的四个必要条件中的一个或几个动态策略(避免死锁)用某种方法防止系统进入不安全的状态, 从而避免死锁 (银行家算法)死锁的检测和解除允许死锁的发生, 不过操作系统会负责检测出死锁的产生, 然后采取某种措施解除死锁破坏互斥条件如果把只能互斥使用的资源改造成允许共享使用, 则系统不会进入死锁状态比如 SPOOLing 技术, 操作系统可以采用 SPOOLing 技术把独占设备在逻辑上改造成共享设备缺点并不是所有资源都可以改造成可共享使用的资源, 并且为了系统安全, 很多地方还必须保护这种互斥性, 因此很多时候都无法破坏互斥条件破坏不剥夺条件当某个进程请求新的资源得不到满足时, 它必须立即释放保持的所有资源, 待以后需要时再重新申请, 也就是说, 即使某些资源尚未使用完, 也需要主动释放, 从而破坏了不可剥夺条件缺点实现起来比较复杂释放已获得的资源可能造成前一阶段工作的失效, 因此这种方法一般只适用于易保存和恢复状态的资源反复地申请和释放资源会增加系统开销, 降低系统吞吐量这种破坏意味着只要暂时得不到某个资源, 之前获得的那些资源都需要放弃, 以后再重新申请, 如果一直发生这样的情况, 就会导致进程饥饿破坏请求和保持条件可以采取静态分配的方法, 即进程在运行前一次申请完它所需要的全部资源, 该进程就不会再请求别的任意资源了该策略实现起来简单, 但也有明显的缺点: 有些资源可能只需要用很短的时间, 因此如果进程的整个运行期间都一直保持着所有资源, 就会造成严重的资源浪费, 资源利用率极低, 另外, 该策略也有可能导致某些进程饥饿破坏循环等待条件方法对系统的所有资源类型进行线性排序 (顺序资源分配法)首先给系统中的资源编号, 规定每个进程必须按编号递增的顺序请求资源, 同类资源 (即编号相同的资源) 一次申请完毕原理分析一个进程只有已占有小编号的资源时, 才有资格申请更大编号的资源该策略的缺点为系统中各类资源规定的序号必须相对稳定, 这限制了新类型设备的增加尽管在为资源的类型分配序号时, 已经考虑到了大多数作业在实际使用这些资源时的顺序, 但也经常会发生作业使用各类资源的顺序与系统规定的顺序不同的情况, 造成对资源的浪费为了方便用户, 系统对用户在编程时所施加的限制条件应尽量少, 然而这种按规定次序申请资源的方式必然会限制用户进行简单, 自主的编程死锁的避免 (属于事先预防策略)是在资源动态分配过程中, 防止系统进入不安全的状态, 以避免发生死锁系统安全状态在避免死锁方法中, 把系统的状态分为安全状态和不安全状态安全序列指的是如果系统按照这种序列分配资源, 则每个进程都能顺利完成, 只要能找出一个安全序列, 系统就是安全状态, 当然, 安全状态可能有多个银行家算法核心算法在进程提出资源申请时, 先预判此次分配是否会导致系统进入不安全状态, 如果会进入不安全状态, 就暂时不答应这次请求, 让该进程先阻塞等待数据结构可利用资源向量 available长度为 m 的一维数组, Available 表示还有多少可用资源最大需求矩阵 Max表示各进程对资源的最大需求数, n * m 矩阵分配矩阵 Allocation表示已经给各进程分配了多少资源, n * m 矩阵需求矩阵 Need矩阵表示各进程最多还需要多少资源, Max - Allocation Need算法步骤设 Request 是进程 Pi 的请求向量如果 Requesti[j]K表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后系统按下述步骤进行检查:①如果 Requesti[ j ] ≤ Need[ i, j ] 便转向步骤②; 否则认为出错因为它所需要的资源数已超过它所宣布的最大值如果Requesti[j]≤Available[j]便转向步骤③; 否则表示尚无足够资源Pi 须等待系统试探着把资源分配给进程Pi并修改下面数据结构中的数值: Available[j] Available[j] - Requesti[j], Allocation[i,j] Allocation[i,j] Requesti[j], Need[ij] Need[i,j] - Requesti[j]系统执行安全性算法检查此次资源分配后系统是否处于安全状态。若安全才正式将资源分配给进程Pi以完成本次分配否则将本次的试探分配作废恢复原来的资源分配状态让进程Pi 等待安全性算法设置两个向量工作向量 Work,它表示系统可提供给进程继续运行所需的各类资源数目, 它含有 m 个元素, 在执行安全算法开始时, Work AvailableFinish: 它表示系统是否有足够的资源分配给进程, 使之运行完成, 开始做 Finish[i] false; 当有足够资源分配给进程时, 再令 Finish[i] true从进程集合中找到一个能满足下述条件的进程Finish[i] false;Need[i, j] Work[j]若找到, 则执行下一步, 否则执行下下步当进程 Pi 获得资源后, 可顺利执行, 直至完成, 并释放出分配给它的资源, 故应执行Work[j] Work[j] Allocation[i,j];Finish[i] true如果所有进程的 Finish[i] true 都满足, 则表示系统处于安全状态, 否则, 系统处于不安全状态安全算法举例假定系统中有5个进程 {Po,P,P2,P3,P4} 和3类资源 {A,B,C}各类资源的数量分别为10、5、7在 t0 时刻的资源分配情况如图1所示t0 时刻的安全性: 利用安全性算法对 t0 时刻的资源分配情况进行分析可知, 在 t0 时刻存在着一个安全序列 {p0, p1, p2, p3, p4}, 故系统是安全的p1 请求资源: p1 发出请求向量 Request1(1, 0, 2), 系统按银行家算法进行检查Request(1,0,2) ≤ Need(1, 2, 2)Request(1,0,2) ≤ Available(3, 3, 2)系统先假定可为 p1 分配资源, 并修改 Available, Allocation1, Need1 向量, 由此形成的资源变化情况如图1 的圆括号所示再利用安全性算法检查此时系统是否安全, 如图3所示由此进行的安全性检查得知, 可以找到一个安全序列 {p1, p3, p4, p2, p0}, 因此, 系统是安全的, 可以立即将 p1 所申请的资源分配给它p4 请求资源: p4 发出请求向量 Request4(3, 3, 0), 系统按银行家算法进行检查Request4(3,3,0) ≤ Need4(4,3,1)Request4(3,3,0) Available(2,3,0)让 P4等待p0 请求资源: P0 发出请求向量 Request0(0, 2, 0), 系统按银行家算法进行检查Requesto(0,2,0) Needo(7,4,3)Requesto(0,2,0) ≤ Available(2,3,0)系统暂时先假定可为 p0 分配资源并修改有关数据如 图4 所示进行安全检查: 可用资源 Available(2, 1, 0) 已不能满足任何进程的需要, 故系统进入不安全状态, 此时系统不分配资源死锁的检测与解除如果系统中既不采用预防死锁也不采用避免死锁的措施, 系统很有可能发生死锁, 这种情况下, 系统应当提供两个算法死锁检测算法用于检测系统状态, 以确定系统中是否发生了死锁, 为了能对死锁进行检测, 在系统中必须用某种数据结构来保存资源的请求和分配信息提供某种算法, 利用上述信息来检测系统是否进入死锁状态资源分配图两种结点进程结点资源结点 (可能有多个)两种边进程结点 -- 资源结点: 代表一个进程结点请求一类资源资源结点 -- 进程结点: 代表这类资源已经分配给了指向的进程结点死锁定理如果某时刻系统的资源分配图是不可简化的, 那么此时系统死锁死锁解除算法当简化死锁检测算法分配图之后, 还连着边的进程就是死锁进程解除死锁的主要方法资源剥夺法将某种死锁进程锁占有的资源剥夺并分配给其他进程撤销进程法强制撤销部分死锁进程或者全部死锁进程, 简单粗暴但是付出的代价较大内存管理内存管理的概念概念操作系统对内存的划分和动态分配就是内存管理的概念功能内存空间的分配和回收由操作系统完成对主存的分配和回收, 对编程人员透明地址转换使逻辑地址转换为真实的物理地址内存空间的扩充利用虚拟存储技术或者自动覆盖技术, 从逻辑上扩充内存存储保护保证各道作业在各自的存储空间内运行, 互不干扰覆盖与交换背景这两个技术是在多道程序环境下扩充内存的两种方方法覆盖思想将程序分为多个段 (多个模块)常用的段常驻内存, 不常用的段在需要时调入内存操作将内存划分为一个固定区和若干个覆盖区, 固定区存放用户程序经常活跃的部分, 调入后就不再调出(除非运行结束), 其余部分按调用关系分段, 将即将访问的段放在覆盖区, 需要用到时调入内存, 用不到时调出内存, 其他放在外存, 在需要调用前, 系统将其调入覆盖区, 替换原有的段, 必须由程序员声明覆盖结构, 操作系统完成自动覆盖缺点对用户不透明, 增加了用户编程负担, 覆盖技术只用于早期的操作系统中交换思想把处于等待状态的进程或者被CPU剥夺运行权限的进程从内存移出到外存, 这一过程称为移出把准备好竞争CPU的进程从外存移到内存, 这一过程称为换入暂时换出外存等待的进程状态为挂起状态(挂起态)挂起态又可以进一步细分为就绪挂起, 阻塞挂起两种状态连续分配存储管理方式单一连续分配内存系统区通常位于内存的低地址部分, 用于存放操作系统系统区用户区用于存放用户进程相关数据特点内存中只能有一道用户程序, 用户程序独占这个用户区空间优点实现简单无外部碎片可以采用覆盖技术扩充内存缺点只能用于单用户, 单任务的操作系统中有内部碎片存储器利用率极低固定分区分配概述是最简单的一种多道程序存储管理方式, 它将用户内存空间划分为若干个固定大小的区域, 每个分区只装入一道作业方法分区大小相等缺乏灵活性, 只适合用一台计算机控制多个相同对象的场合分区大小不等增加了灵活性, 可以满足不同大小的进程需求为便于内存分配, 通常将分区按大小排队, 建立一张分区说明表优点实现简单, 无外部碎片缺点当用户程序太大时, 可能所有的分区都不能满足需求, 此时不得不采用覆盖技术来解决, 但又会降低性能会产生内部碎片, 内存利用率低例题分区分配内存管理方式的主要保护措施是界地址保护分区管理要求对每个作业都分配连续地址的内存单元动态分区分配概述又称可变分区分配, 是一种动态划分内存的分区方法这种分配方式不会预先划分内存分区, 而是在进程装入内存时, 根据进程大小动态地建立分区, 系统分区的大小和数目是可变的两种常用的数据结构空闲分区表空闲分区链动态分区分配算法首次适应(FirstFit)算法空闲分区以地址递增的次序链接。分配内存时顺序查找找到大小能满足要求的第一个空闲分区最佳适应(Best Fit)算法空闲分区按容量递增的方式形成分区链找到第一个能满足要求的空闲分区, 即最小空闲分区, 可以产生最小的内存空间分区最坏适应(WorstFi)算法又称最大适应(Largest Fit)算法空闲分区以容量递减的次序链接找到第-个能满足要求的空闲分区即挑选出最大的分区邻近适应(NextFi)算法又称循环首次适应算法由首次适应算法演变而成。不同之处是, 分配内存时从上次查找结束的位置开始继续查找表格算法算法思想分区排列顺序优点缺点首次适应从头到尾找适合的分区空闲分区以地址递增次序排列综合看性能最好。算法开销小回收分区后一般不需要对空闲分区队列重新排序最佳适应优先使用更小的分区以保留更多大分区空闲分区以容量递增次序排列会有更多的大分区被保留下来更能满足大进程需求会产生很多太小的、难以利用的碎片算法开销大回收分区后可能需要对空闲分区队列重新排序最坏适应优先使用更大的分区以防止产生太小的不可用的碎片空闲分区以容量递减次序排列可以减少难以利用的小碎片大分区容易被用完不利于大进程算法开销大(原因同上)临近适应由首次适应演变而来每次从上次查找结束位置开始查找空闲分区以地址递增次序排列(可排列成循环链表)不用每次都从低地址小分区开始检索。算法开销小(原因同首次适应算法)会使高地址的大分区也被用完非连续分配存储管理方式分页存储管理方式思想把内存分为一个个相等的小分区再按照分区大小把进程拆分成一个个小部分分页存储管理不会产生外部碎片概念进程中的块称为页内存中的块称为页框(Page Frame, 或页帧)外存也以同样的单位进行划分称为块进程在执行时需要申请主存空间, 即腰围每个页面分配主存中的可用页框, 这就产生了页和页框的一一对应页面大小应该适中, 应为2的整数幂地址结构位范围字段名称31 … 12页号 $ P $11 … 0页内偏移量 $ W $地址长度为32位每页大小为4kb地址空间最多允许220{2^{20}}220页页表为了便于在内存中找到进程的每个页面所对应的物理块系统为每个进程建立一张页表它记录页面在内存中对应的物理块号页表一般存放在内存中页表是由页表项组成的页表项由页号和物理内存中的块号组成1 GB 230{2^{30}}230B1 GB 210{2^{10}}210B地址变换结构 (基本地址变换结构)变换过程计算:设页面大小为 L逻辑地址 A 到物理地址 E 的变换过程如下(逻辑地址、页号、每页的长度都是十进制数):I. 计算页号 P (P A / L)和页内偏移量 W (W A % L)II. 比较页号P和页表长度 M若 P M则产生越界中断否则继续执行III. 页表中页号P对应的 页表项地址页表始址F 页号P x 页表项长度取出该页表项内容b即为物理块号IV.计算 E b x L W, 用得到的物理地址 E 去访问内存地址变换机构 (具有快表的地址变换机构)分段存储管理方式分段其逻辑地址由段号 S 与段内偏移量 W 两部分组成段表每个段表项对应进程的一段段表项记录该段在内存中的始址和长度段号, 段长, 本段在主存的始址地址变换机构在系统中设置了段表寄存器用于存放 段表始址 F 和 段表长度 M, 从 逻辑地址A 到 物理地址E 间的地址变换过程如下段页式存储管理方式作业的逻辑地址分为: 段号, 页号, 页内偏移量