操作系统-习题课-死锁、内存管理FF.ppt

操作系统概念习题课 死锁与内存管理 2016 5 12 死锁 概念 多道程序环境下 多个进程可能竞争一定数量的资源 进程所申请的资源被其他等待进程占有 该进程可能无法改变其状态 成为死锁 必要条件 资源互斥占有并等待非抢占循环等待 死锁 明确死锁产生的四个必要条件明确死锁的处理方法明确死锁预防的处理方法明确死锁避免的处理方法 包括安全状态 死锁状态关系等 死锁 处理方法 死锁预防 死锁避免 死锁检测 忽略 互斥 通常无计可施 占有并等待 静态分配 非抢占 允许抢占 循环等待 有序申请资源 安全状态和安全队列 资源分配图算法 银行家算法 死锁恢复 终止进程 资源抢占 单实例 等待图 多实例 类似银行家 检测算法的应用问题 选择题 某系统中有三个并发进程 都需要同类资源4个 试问该系统不会发生死锁的最少资源数是 A 9B 10C 11D 12 答案 B 例 某系统采用了银行家算法 则下列叙述正确的是 A系统处于不安全状态时一定会发生死锁B系统处于不安全状态时可能会发生死锁C系统处于安全状态时 可能会发生死锁D系统处于安全状态时 一定会发生死锁 解答 B 例 在下列选项中 属于解除死锁的方法是 A剥夺资源法B资源分配图算法C银行家算法D资源静态分配法 解答 A另一种方法是终止进程 资源抢占 例 资源静态分配法可以预防死锁的发生 因它使死锁四个条件中的 不成立A互斥条件B占有并等待C非抢占D循环等待 解答 B 例 下面4个选项中 属于处理死锁的基本方法是 A资源独占B资源共享C进程并发D预防死锁 答案 D 例 在银行家算法的数据结构中 其中最大需求矩阵Max 分配矩阵Allocation和需求矩阵Need三者之间的关系是 ANeed i j Allocation i j Max i j BNeed i j Max i j Allocation i j CNeed i j Max i j Allocation i j DNeed i j Max i j Allocation i j 答案 C 例 系统死锁可利用 来描述 A进程B程序C系统流程图D资源分配图 答案 D 例 按序分配资源是为了 A死锁的检测B死锁的防止C死锁的避免D死锁的解除 答案 B 例 死锁的预防是根据 而采取措施实现的A配置足够的系统资源B使进程的推进顺序合理C破坏死锁的四个必要条件之一D防止系统进入不安全状态 解答 C 例 在下列解决死锁的办法中 属于死锁预防策略的是 A化简进程的资源分配图B银行家算法C资源的有序分配法D死锁检测法 解答 C 例 死锁产生的必要条件有4个 要预防死锁发生 必须破坏死锁的四个必要条件之一 但破坏 条件是不太实际的 实现起来最简单的条件是 A请求和保持B互斥C不剥夺D环路等待 解答 B 因为这是由设备的固有特性决定的A采用静态分配方法实现 在进程开始运行前 将它需要的全部资源分配给它 在运行过程中 不再请求 这是早期操作系统采用的方法 但资源的利用率不高 例 通过撤消进程可进行死锁恢复 还可以采用 方法解除死锁A阻塞进程B资源剥夺C提高进程优先级D降低进程优先级 解答 B采用资源剥夺法 将剥夺的资源分配给死锁进程 以解决死锁 例 以下关于资源分配图的描述中正确的是 A有向边包含进程指向资源类的分配边和资源类指向进程申请边两类B矩阵框表示进程 其中的原点表示申请同一类资源的各个进程C圆圈结点表示资源类D资源分配图是一个有向图 用于表示某时刻系统资源与进程之间的状态 答案 D 例 死锁的4个必要条件中 无法破坏的是 A环路等待资源B互斥使用资源C占有且等待资源D非抢夺式分配 答案 B 例 从下面关于安全状态和非安全状态的论述中 正确的论述是 A安全状态是没有死锁的状态 非安全状态是有死锁的状态B安全状态是可能有死锁的状态 非安全状态也是可能有死锁的状态C安全状态是可能没有死锁的状态 非安全状态是有死锁的状态D安全状态是没有死锁的状态 非安全状态是可能有死锁的状态 解答 D 例 关于产生死锁的现象 下面的描述最准确的是 A每个进程共享某一个资源B每个进程竞争某一个资源C每个进程等待着某一个不能得到且不可释放的资源D某个进程因等待着某一个资源而无法进行下去 解答 C 例 银行家算法是一种 算法A死锁解除B死锁避免C死锁预防D死锁检测 解答 B 例 下列说法正确的是 A死锁是指系统的全部进程都处于阻塞状态B操作系统处理死锁 只要采用预防 解除 检测 避免等方法中的一种就足够了C如果系统在所有进程运行前 一次性地将其在整个运行过程所需的全部资料分配给进程 即所谓 静态分配 是预防死锁发生的 D多个进程竞争比进程数目少的资源分配情况进行安全分析 如果该时刻状态是安全的 则存在一个安全序列 且这个安全序列是唯一的 解答 C 例 下列说法错误的是 A产生死锁的原因可以归结为两点 竞争资源和进程推进顺序非法B用于处理死锁的方法可归结为以下四种 预防死锁 避免死锁 检测死锁 解除死锁C在死锁的预防中 摒弃 请求和保持 条件的方法的缺点是资源严重浪费 进程延迟运行D当由于为进程分配资源而使系统处于不安全状态时 系统一定会导致死锁 解答 AD 例 正确的是 A预防死锁的方法 优点是简单 易于实现且很安全 而且资源利用率高 进程也能较快地进行B检测死锁能够有效地解除进程的死锁状态解C当由于为进程分配资源使系统处于不安全状态时 系统一定会导致死锁D采用资源静态分配算法可以预防死锁的发生 答案 D 例 假设现在有p个进程 每个进程最多需要m个资源 并且有r个资源可用 什么样的条件可以保证死锁不会发生 解答 如果一个进程有m个资源它就能够结束 不会使自己陷入死锁中 因此 最差的情况是每个进程有m 1个资源并且需要另外一个资源 如果留下有一个资源可用 那么其中某一个进程就能够结束并释放它所有的资源 使其他进程也能结束 所以避免死锁的条件是 r p m 1 1 例 一台计算机有6台磁带机 由n个进程竞争使用 每个进程可能需要两台磁带机 那么n是多少时 系统才没有死锁的危险 解答 对于三个进程 每个进程能够有两个驱动器 对于4个进程 驱动器可以按照 2 2 1 1 的方法进行分配 使前面两个进程先结束 对于5个进程 可以按照 2 1 1 1 1 的方法进行分发 使一个进程先结束 对于六个进程 每个进程都拥有一个磁带驱动器同时需要另外一个驱动器 产生了死锁 因此 对于n 6的系统来说是无锁的 例 设系统中仅有一个资源类 其中共有3个资源实例 使用此类资源的进程共有3个 每个进程至少请求一个资源 它们所需资源最大量的总和为X 则发生死锁的必要条件是 X的取值 解答 假设3个进程所需该类资源数分别是a b c个 因此有 a b c X假设发生了死锁 也即当每个进程都申请了部分资源 还需最后一个资源 而此时系统中已经没有了剩余资源 即 a 1 b 1 c 1 3X a b c 6因此 如果发生死锁 则必须满足的必要条件是 X 6 例 假设某系统中有4种资源 R1 R2 R3 R4 在某时刻系统中共有5个进程 进程P1 P2 P3 P4 P5的最大资源需求数量和此刻已分配到资源数向量分别如下系统中当前可用资源向量为 2 1 0 0 问1当前系统是否是安全的 2如果进程P3发出资源请求向量 0 1 0 0 系统能否将资源分配给它 分析 1 进程的最大资源需求数减去当前进程已获得的资源数就是进程仍需要的资源数 此刻各个进行的仍需要资源数向量为 P1 0 0 0 0 P2 0 7 5 0 P3 6 6 2 2 P4 2 0 0 2 P5 0 3 2 0 而系统的可用资源向量为 2 1 0 0 这时存在如下执行序列 使进程顺序执行完毕 状态安全进程可用资源数P1完成后 2 1 1 2 P4完成后 4 4 6 6 P5完成后 4 7 9 8 P2完成后 6 7 9 8 P3完成后 6 7 1 12 满足资源需求的进程执行序列为 进程名可用资源数P1完成后 2 0 1 2 P4完成后 4 3 6 6 P5完成后 4 6 9 8 此时可用资源不能满足P2 P3的需求 即此时系统状态是不安全的 将拒绝资源请求 此时系统可用资源为 2 0 0 0 各进程仍需要资源向量为 P1 0 0 0 0 P2 0 7 5 0 P3 6 5 2 2 P4 2 0 0 2 P5 0 3 2 0 在P3发出资源请求 0 1 0 0 后 假设系统把资源分配给P3 则各进程已分配资源数为 P1 0 0 1 2 P2 2 0 0 0 P3 0 1 3 4 P4 2 3 5 4 P5 0 3 3 2 1 2 内存管理 背景 交换 连续内存分配 分页 分段 页表结构 基本硬件 地址绑定 动态加载和动态链接 CPU和内存 cache 用户空间和内核空间 基址寄存器 界限寄存器 首次适应算法 最佳适应算法 最差适应算法 循环首次适应算法 碎片问题 外部 页表映射方法 保护 有效无效位 只存在内部碎片 内部 硬件支持TLB 基本思想 段表映射方法 逻辑地址和物理地址 非连续内存分配 1 下面关于存储管理的叙述中正确的是 A 现在操作系统中 允许用户干预内存的分配B 固定分区存储管理是针对单道系统的内存管理方案C 可变分区存储管理可以对作业分配不连续的内存单元D 页式存储管理中 页面大小是在硬件设计时确定的 解答 D 选择题 2 在存储管理中 把目标程序中的逻辑地址转换成主存空间的物理地址的过程称为 A 存储分配B 地址重定位C 地址保护D 程序移动B3 作业在执行中发生了缺页中断 经操作系统处理后 应让其执行指令 A 被中断的前一条B 被中断的C 被中断的后一条D 启动时的第一条B 4 下面最有可能使得高地址空间成为大的空闲区的分配算法是 A 首次适应算法B 最佳适应法C 最坏适应法D 循环首次适应法A 5 在几种基本的放置策略中 空白区是按大小递增的顺序链接在一起的是 策略 A 首次匹配B 最佳匹配C 最坏匹配D 以上三者B 6 虚拟内存的可行性的基础是 A 程序执行的离散性B 程序执行的顺序性C 程序执行的局部性D 程序执行的并发性C 7 分区管理要求对每一个作业都分配 的内存单元 A 地址连续B 若干地址不连续C 若干连续的帧D 若干不连续的帧A8 分区管理和分页管理的主要区别是 A 分区管理中的块比分页管理中的页要小B 分页管理有地址映射而分区管理没有C 分页管理有存储保护而分区管理没有D 分区管理要求一道程序存放在连续的空间内而分页管理没有这种要求D 9 对于分页系统与分段系统 下列说法正确的是 A 两者都采用离散分配方式B 分页的目的是为了能更好地满足用户的需要C 段的大小固定且由系统确定D 分页的作业地址空间是二维的答案 A对于C 段的大小取决于用户程序的大小 简答 计算题 1 试比较分段式和分页式存储管理方式的主要差别 答 它们的差别主要表现在以下几个方面 1 页面是信息的物理单位 分页是为了实现非连续分配 以便解决内存碎片问题 或者说分页是由于系统管理的需要 段是信息的逻辑单位 它含有一组意义相对完整的信息 分段的目的是为了更好地实现共享 满足用户的需要 2 页面的大小固定且由硬件确定 将逻辑地址划分为页号和页内地址是由机器硬件实现的 而段的长度却不固定 它取决于用户所编写的程序 通常由编译程序在对源程序进行编译时根据信息的性质来划分 3 分页式存储管理的作业地址空间是一维的 页偏移 分段式存储管理的作业地址空间是二维的 包括基地址和界限 2 在采用分页存储管理的系统中 某作业J的逻辑地址空间为4页 每页2KB 且已知该作业的页面映像表 即页表 如下所示 试借助地址变换图 即要求画出地址变换图 求出有效逻辑地址4865所对应的物理地址 解 在本题中 一页大小为2KB 即2048字节 则逻辑地址4865的页号及页内位移为 页号 4865 2048 2页内位移 4865 2048 2 769通过页表可知页面2存放在物理块6中 将物理块号与逻辑地址中的页内位移进行拼接 形成物理地址 即 6 2048 769 13057 3 在一分页存储管理系统 页面大小为4KB 已知某进程的第0 1 2 3 4页依次存在内存中的6 8 10 14 16物理块号中 现有逻辑地址为12138D 3A5CH 分别求其所在的页号 页内相对地址 对应的物理块号以及相应的物理地址 解 1 已知页面大小4KB 4096D 页号p INT 12138 4096 2 页内位移d 12138MOD4096 3946D查页表可知页号2对应物理块号为10 由地址转换原理可得 块内位移等于页内位移 故物理地址 10 4096 3946 44906D 2 解法一 已知页面大小4KB 占12位 逻辑地址长度为16位 故高4位为页号 低12位为页内位移 逻辑地址为 3A5CH 0011101001011100B 则页号为 3 查页表可知页号3对应物理块号为14 由地址转换原理可得 块内位移等于页内位移 物理地址高4位为物理块号 低12位为块内位移 故物理地址为 1110101001011100B EA5CH 59996D解法二 已知页面大小4KB 4096D 逻辑地址3A5CH 14940D 页号p INT 14940 4096 3 页内位移d 14940MOD4096 2652D 查页表可知页号3对应物理块号为14 由地址转换原理可得 块内位移等于页内位移 故物理地址 14 4096 2652 59996D EA5CH 4 若在一分页存储管理系统中 某作业的页表如下所示 已知页面大小为1024字节 试将逻辑地址1011 2148 4000 5012转化为相应的物理地址 解 本题中 为了描述方便 设页号为p 页内位移为d 则 1 对于逻辑地址1011 p int 1011 1024 0 d 1011mod1024 1011 查页表第0页在第2块 所以物理地址为1024 2 1011 3059 2 对于逻辑地址2148 p int 2148 1024 2 d 2148mod1024 100 查页表第2页在第1块 所以物理地址为1024 100 1124 3 对于逻辑地址4