死锁

• 定义

  • 各进程互相等待对方手里的资源, 导致各进程都阻塞, 无法向前推进的现象

• 区分

  • 死锁和饥饿

    • 都是进程无法顺利向前推进导致的现象

    • 死锁

      • 一定是"循环等待对方手里的资源"导致的, 因此如果有死锁现象, 那至少有两个或者两个以上的进程同时发生死锁. 另外发生死锁的进程一定处理堵塞

    • 饥饿

      • 可能只有一个进程发生饥饿, 发生饥饿的进程既可能是阻塞态(长期得不到的 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 = Available

          • Finish: 它表示系统是否有足够的资源分配给进程, 使之运行完成, 开始做 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

      • 地址空间最多允许 $2^{20}$ 页

    • 页表

      • 为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，它记录页面在内存中对应的物理块号，页表一般存放在内存中

      • 页表是由页表项组成的，页表项由页号和物理内存中的块号组成

      • 1 GB = $2^{30}$ B

      • 1 GB = $2^{10}$ B

    • 地址变换结构 (基本地址变换结构)

      • 变换过程计算:

        • 设页面大小为 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 间的地址变换过程如下

  • 段页式存储管理方式

    • 作业的逻辑地址分为: 段号, 页号, 页内偏移量