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

1、操作系统概念习题课操作系统概念习题课 -死锁与内存管理死锁与内存管理 2016.5.12死锁死锁o 概念：概念： 多道程序环境下，多个进程可能竞争一定数多道程序环境下，多个进程可能竞争一定数量的资源。进程所申请的资源被其他等待进程量的资源。进程所申请的资源被其他等待进程占有，该进程可能无法改变其状态，成为死锁。占有，该进程可能无法改变其状态，成为死锁。p 必要条件：必要条件：资源互斥资源互斥 占有并等待占有并等待非抢占非抢占循环等待循环等待死锁死锁 明确死锁产生的四个必要条件明确死锁产生的四个必要条件 明确死锁的处理方法明确死锁的处理方法 明确死锁预防的处理方法明确死锁预防的处理方法 明确死锁

2、避免的处理方法（包括安全状态、明确死锁避免的处理方法（包括安全状态、死锁状态关系等）死锁状态关系等）死锁死锁处理方法死锁预防死锁避免死锁检测忽略互斥-通常无计可施占有并等待-静态分配非抢占-允许抢占循环等待-有序申请资源安全状态和安全队列资源分配图算法银行家算法死锁恢复终止进程资源抢占单实例 等待图多实例类似银行家检测算法的应用问题选择题选择题某系统中有三个并发进程，都需要同类资源某系统中有三个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源个，试问该系统不会发生死锁的最少资源数是数是_A.9 B.10 C.11 D.12答案：答案：B【例例】某系统采用了银行家算法，则下列叙述正

3、某系统采用了银行家算法，则下列叙述正确的是（）确的是（）A 系统处于不安全状态时一定会发生死锁系统处于不安全状态时一定会发生死锁B 系统处于不安全状态时可能会发生死锁系统处于不安全状态时可能会发生死锁C 系统处于安全状态时，可能会发生死锁系统处于安全状态时，可能会发生死锁D 系统处于安全状态时，一定会发生死锁系统处于安全状态时，一定会发生死锁【解答解答】B【例例】在下列选项中，属于解除死锁的方法是（在下列选项中，属于解除死锁的方法是（）A 剥夺资源法剥夺资源法 B 资源分配图算法资源分配图算法C 银行家算法银行家算法D 资源静态分配法资源静态分配法【解答解答】A另一种方法是另一种方法是终止进程

4、终止进程=资源抢占【例例】资源静态分配法可以预防死锁的发生，因资源静态分配法可以预防死锁的发生，因它使死锁四个条件中的（）不成立它使死锁四个条件中的（）不成立A 互斥条件互斥条件B 占有并等待占有并等待C 非抢占非抢占D 循环等待循环等待【解答解答】B【例例】下面下面4个选项中，属于处理死锁的基本方个选项中，属于处理死锁的基本方法是法是( )A 资源独占资源独占B 资源共享资源共享C 进程并发进程并发D 预防死锁预防死锁【答案答案】D【例例】在银行家算法的数据结构中，其中最大需在银行家算法的数据结构中，其中最大需求矩阵求矩阵Max,分配矩阵分配矩阵Allocation和需求矩和需求矩阵阵Nee

5、d三者之间的关系是三者之间的关系是( )A Needi,j=Allocationi,j-Maxi,jB Needi,j=Maxi,j+Allocationi,jC Needi,j=Maxi,j-Allocationi,jD Needi,j=Maxi,j*Allocationi,j【答案答案】C【例例】系统死锁可利用（系统死锁可利用（ ）来描述。）来描述。A 进程进程B 程序程序C 系统流程图系统流程图D 资源分配图资源分配图【答案答案】D【例例】按序分配资源是为了（按序分配资源是为了（ ）A 死锁的检测死锁的检测B 死锁的防止死锁的防止C 死锁的避免死锁的避免D 死锁的解除死锁的解除【答案答案

6、】B【例例】死锁的预防是根据（）而采取措施实现的死锁的预防是根据（）而采取措施实现的A 配置足够的系统资源配置足够的系统资源B 使进程的推进顺序合理使进程的推进顺序合理C 破坏死锁的四个必要条件之一破坏死锁的四个必要条件之一D 防止系统进入不安全状态防止系统进入不安全状态【解答解答】C【例例】在下列解决死锁的办法中，属于死锁预防在下列解决死锁的办法中，属于死锁预防策略的是（）策略的是（）A 化简进程的资源分配图化简进程的资源分配图B 银行家算法银行家算法C 资源的有序分配法资源的有序分配法D 死锁检测法死锁检测法【解答解答】C【例例】死锁产生的必要条件有死锁产生的必要条件有4个，要预防死锁发生

7、个，要预防死锁发生，必须破坏死锁的四个必要条件之一，但破坏（，必须破坏死锁的四个必要条件之一，但破坏（）条件是不太实际的。）条件是不太实际的。实现起来最简单的条件是（）实现起来最简单的条件是（）A 请求和保持请求和保持B互斥互斥C 不剥夺不剥夺D 环路等待环路等待【解答解答】B。因为这是由设备的固有特性决定的。因为这是由设备的固有特性决定的A 采用静态分配方法实现，在进程开始运行前，将采用静态分配方法实现，在进程开始运行前，将它需要的全部资源分配给它。在运行过程中，不它需要的全部资源分配给它。在运行过程中，不再请求。这是早期操作系统采用的方法，但资源再请求。这是早期操作系统采用的方法，但资源的

8、利用率不高。的利用率不高。【例例】通过撤消进程可进行死锁恢复，还可以采通过撤消进程可进行死锁恢复，还可以采用（）方法解除死锁用（）方法解除死锁A 阻塞进程阻塞进程B 资源剥夺资源剥夺C 提高进程优先级提高进程优先级D 降低进程优先级降低进程优先级【解答解答】B 采用资源剥夺法，将剥夺的资源分采用资源剥夺法，将剥夺的资源分配给死锁进程，以解决死锁。配给死锁进程，以解决死锁。【例例】以下关于资源分配图的描述中正确的是（以下关于资源分配图的描述中正确的是（ ）A有向边包含进程指向资源类的分配边和资源类有向边包含进程指向资源类的分配边和资源类指向进程申请边两类指向进程申请边两类B 矩阵框表示进程，其中

9、的原点表示申请同一矩阵框表示进程，其中的原点表示申请同一类资源的各个进程类资源的各个进程C 圆圈结点表示资源类圆圈结点表示资源类D 资源分配图是一个有向图，用于表示某时刻资源分配图是一个有向图，用于表示某时刻系统资源与进程之间的状态系统资源与进程之间的状态【答案答案】D 【例例】死锁的死锁的4个必要条件中，无法破坏的是（个必要条件中，无法破坏的是（ ）A 环路等待资源环路等待资源B 互斥使用资源互斥使用资源C 占有且等待资源占有且等待资源D 非抢夺式分配非抢夺式分配【答案答案】B【例例】从下面关于安全状态和非安全状态的论述中从下面关于安全状态和非安全状态的论述中，正确的论述是（），正确的论述是

10、（）A 安全状态是没有死锁的状态，非安全状态是有死安全状态是没有死锁的状态，非安全状态是有死锁的状态锁的状态B 安全状态是可能有死锁的状态，非安全状态也是安全状态是可能有死锁的状态，非安全状态也是可能有死锁的状态可能有死锁的状态C 安全状态是可能没有死锁的状态，非安全状态是安全状态是可能没有死锁的状态，非安全状态是有死锁的状态有死锁的状态D 安全状态是没有死锁的状态，非安全状态是可能安全状态是没有死锁的状态，非安全状态是可能有死锁的状态有死锁的状态【解答解答】D【例例】关于产生死锁的现象，下面的描述最准确关于产生死锁的现象，下面的描述最准确的是（）的是（）A 每个进程共享某一个资源每个进程共享

11、某一个资源B 每个进程竞争某一个资源每个进程竞争某一个资源C 每个进程等待着某一个不能得到且不可释放每个进程等待着某一个不能得到且不可释放的资源的资源D 某个进程因等待着某一个资源而无法进行下某个进程因等待着某一个资源而无法进行下去去【解答解答】C【例例】银行家算法是一种（）算法银行家算法是一种（）算法A 死锁解除死锁解除B 死锁避免死锁避免C 死锁预防死锁预防D 死锁检测死锁检测【解答解答】B【例例】下列说法正确的是（）下列说法正确的是（）A 死锁是指系统的全部进程都处于阻塞状态死锁是指系统的全部进程都处于阻塞状态B 操作系统处理死锁，只要采用预防，解除，检测，避免操作系统处理死锁，只要采用

12、预防，解除，检测，避免等方法中的一种就足够了等方法中的一种就足够了C 如果系统在所有进程运行前，一次性地将其在整个运行如果系统在所有进程运行前，一次性地将其在整个运行过程所需的全部资料分配给进程，即所谓过程所需的全部资料分配给进程，即所谓”静态分配静态分配“，是预防死锁发生的。，是预防死锁发生的。D多个进程竞争比进程数目少的资源分配情况进行安全分析多个进程竞争比进程数目少的资源分配情况进行安全分析，如果该时刻状态是安全的，则存在一个安全序列，且，如果该时刻状态是安全的，则存在一个安全序列，且这个安全序列是唯一的。这个安全序列是唯一的。【解答解答】C【例例】下列说法错误的是（）下列说法错误的是（

13、）A 产生死锁的原因可以归结为两点：竞争资源和进程推进产生死锁的原因可以归结为两点：竞争资源和进程推进顺序非法顺序非法B 用于处理死锁的方法可归结为以下四种：预防死锁；避用于处理死锁的方法可归结为以下四种：预防死锁；避免死锁；检测死锁；解除死锁免死锁；检测死锁；解除死锁C 在死锁的预防中，摒弃在死锁的预防中，摒弃”请求和保持请求和保持“条件的方法的缺条件的方法的缺点是资源严重浪费；进程延迟运行点是资源严重浪费；进程延迟运行D 当由于为进程分配资源而使系统处于不安全状态时，系统当由于为进程分配资源而使系统处于不安全状态时，系统一定会导致死锁一定会导致死锁【解答解答】AD【例例】正确的是正确的是(

14、)A 预防死锁的方法，优点是简单，易于实现且预防死锁的方法，优点是简单，易于实现且很安全，而且资源利用率高，进程也能较快很安全，而且资源利用率高，进程也能较快地进行地进行B 检测死锁能够有效地解除进程的死锁状态解检测死锁能够有效地解除进程的死锁状态解C 当由于为进程分配资源使系统处于不安全状当由于为进程分配资源使系统处于不安全状态时，系统一定会导致死锁态时，系统一定会导致死锁D 采用资源静态分配算法可以预防死锁的发生采用资源静态分配算法可以预防死锁的发生【答案答案】D【例例】假设现在有假设现在有p个进程，每个进程最多需要个进程，每个进程最多需要m个资源，并且有个资源，并且有r个资源可用，什么样

15、的条个资源可用，什么样的条件可以保证死锁不会发生。件可以保证死锁不会发生。【解答解答】如果一个进程有如果一个进程有m个资源它就能够结束，个资源它就能够结束，不会使自己陷入死锁中。因此，最差的情况是每不会使自己陷入死锁中。因此，最差的情况是每个进程有个进程有m-1个资源并且需要另外一个资源。个资源并且需要另外一个资源。如果留下有一个资源可用，那么其中某一个进程如果留下有一个资源可用，那么其中某一个进程就能够结束并释放它所有的资源，使其他进程也就能够结束并释放它所有的资源，使其他进程也能结束。所以避免死锁的条件是：能结束。所以避免死锁的条件是：r=p(m-1)+1【例例】一台计算机有一台计算机有6

16、台磁带机，由台磁带机，由n个进程竞争使用，每个进程竞争使用，每个进程可能需要两台磁带机，那么个进程可能需要两台磁带机，那么n是多少时，系统才没是多少时，系统才没有死锁的危险？有死锁的危险？【解答解答】对于三个进程，每个进程能够有两个驱动器。对于对于三个进程，每个进程能够有两个驱动器。对于4个进程，驱动器可以按照（个进程，驱动器可以按照（2，2，1，1）的方法进行）的方法进行分配，使前面两个进程先结束。分配，使前面两个进程先结束。 对于对于5个进程，可以按照（个进程，可以按照（2，1，1，1，1）的方法进）的方法进行分发，使一个进程先结束。行分发，使一个进程先结束。 对于六个进程，每个进程都拥有

17、一个磁带驱动器同时需对于六个进程，每个进程都拥有一个磁带驱动器同时需要另外一个驱动器，产生了死锁。因此，对于要另外一个驱动器，产生了死锁。因此，对于n6的系的系统来说是无锁的。统来说是无锁的。【例例】设系统中仅有一个资源类，其中共有设系统中仅有一个资源类，其中共有3个资源实例个资源实例， 使用此类资源的进程共有使用此类资源的进程共有3个，每个进程至少请求个，每个进程至少请求一个资源，它们所需资源最大量的总和为一个资源，它们所需资源最大量的总和为X，则发生死，则发生死锁的必要条件是（锁的必要条件是（X的取值）的取值）【解答解答】假设假设3个进程所需该类资源数分别是个进程所需该类资源数分别是a,b

18、,c个，因此有：个，因此有： a+b+c =X假设发生了死锁，也即当每个进程都申请了部分资源，还需最后一个假设发生了死锁，也即当每个进程都申请了部分资源，还需最后一个资源，而此时系统中已经没有了剩余资源，即：资源，而此时系统中已经没有了剩余资源，即： (a-1)+(b-1)+(c-1) 3 X = a+b+c 6 因此，如果发生死锁，则必须满足的必要条件是（因此，如果发生死锁，则必须满足的必要条件是（X 6） 【例例】假设某系统中有假设某系统中有4种资源种资源(R1,R2,R3,R4)，在某时刻系统中共有，在某时刻系统中共有5个个进程，进程进程，进程P1，P2，P3，P4，P5的最大资的最大资

19、源需求数量和此刻已分配到资源数向量分别如源需求数量和此刻已分配到资源数向量分别如下下系统中当前可用资源向量为系统中当前可用资源向量为(2,1,0,0),问问1 当前系统是否是安全的？当前系统是否是安全的？2 如果进程如果进程P3发出资源请求向量发出资源请求向量(0,1,0,0)，系，系统能否将资源分配给它？统能否将资源分配给它？【分析分析】(1)进程的最大资源需求数减去当前进程已获得的进程的最大资源需求数减去当前进程已获得的资源数就是进程仍需要的资源数，此刻各个进行的仍需资源数就是进程仍需要的资源数，此刻各个进行的仍需要资源数向量为：要资源数向量为：P1(0,0,0,0);P2(0,7,5,0

20、);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完成后完成后 (

21、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)内存

22、管理内存管理背景交换连续内存分配分页分段页表结构基本硬件地址绑定动态加载和动态链接CPU和内存，cache用户空间和内核空间基址寄存器，界限寄存器首次适应算法最佳适应算法最差适应算法循环首次适应算法碎片问题外部页表映射方法保护-有效无效位只存在内部碎片内部硬件支持TLB基本思想段表映射方法逻辑地址和物理地址非连续内存分配1.下面关于存储管理的叙述中正确的是（）下面关于存储管理的叙述中正确的是（）A. 现在操作系统中，允许用户干预内存的分配现在操作系统中，允许用户干预内存的分配B. 固定分区存储管理是针对单道系统的内存管理方案固定分区存储管理是针对单道系统的内存管理方案C. 可变分区存储管理可以

23、对作业分配不连续的内存单元可变分区存储管理可以对作业分配不连续的内存单元D. 页式存储管理中，页面大小是在硬件设计时确定的页式存储管理中，页面大小是在硬件设计时确定的【解答解答】D选择题选择题2.在存储管理中，把目标程序中的逻辑地址转换在存储管理中，把目标程序中的逻辑地址转换成主存空间的物理地址的过程称为成主存空间的物理地址的过程称为 。 A. 存储分配存储分配 B. 地址重定位地址重定位 C. 地址保护地址保护 D. 程序移动程序移动B3.作业在执行中发生了缺页中断，经操作系统处作业在执行中发生了缺页中断，经操作系统处理后，应让其执行理后，应让其执行 指令。指令。 A被中断的前一条被中断的前

24、一条 B被中断的被中断的 C被中断的后一条被中断的后一条 D启动时的第一条启动时的第一条B4.下下面面最最有有可可能能使使得得高高地地址址空空间间成成为为大大的的空空闲闲区区的的分分配配算算法法是是（ ）。 A首首次次适适应应算算法法 B最最佳佳适适应应法法 C最最坏坏适适应应法法 D循循环环首首次次适适应应法法 A5.在在几几种种基基本本的的放放置置策策略略中中，空空白白区区是是按按大大小小递递增增的的顺顺序序链链接接在在一一起起的的是是（ ）策策略略。 A首首次次匹匹配配 B最最佳佳匹匹配配 C最最坏坏匹匹配配 D以以上上三三者者B6.虚虚拟拟内内存存的的可可行行性性的的基基础础是是（ ）

25、。 A程程序序执执行行的的离离散散性性 B程程序序执执行行的的顺顺序序性性 C程程序序执执行行的的局局部部性性 D程程序序执执行行的的并并发发性性C7.分分区区管管理理要要求求对对每每一一个个作作业业都都分分配配（ ）的的内内存存单单元元。 A地地址址连连续续 B若若干干地地址址不不连连续续 C若若干干连连续续的的帧帧 D若若干干不不连连续续的的帧帧A8.分分区区管管理理和和分分页页管管理理的的主主要要区区别别是是（ ）。 A分分区区管管理理中中的的块块比比分分页页管管理理中中的的页页要要小小 B分分页页管管理理有有地地址址映映射射而而分分区区管管理理没没有有 C分分页页管管理理有有存存储储保

26、保护护而而分分区区管管理理没没有有 D分分区区管管理理要要求求一一道道程程序序存存放放在在连连续续的的空空间间内内而而分分页页管管理理没没有有这这种种要要求求D9.对对于于分分页页系系统统与与分分段段系系统统，下下列列说说法法正正确确的的是是（ ）。 A两两者者都都采采用用离离散散分分配配方方式式 B分分页页的的目目的的是是为为了了能能更更好好地地满满足足用用户户的的需需要要 C段段的的大大小小固固定定且且由由系系统统确确定定 D分分页页的的作作业业地地址址空空间间是是二二维维的的答答案案：A对对于于C：段段的的大大小小取取决决于于用用户户程程序序的的大大小小简答、计算题简答、计算题1.试比较

27、分段式和分页式存储管理方式的主要差别。试比较分段式和分页式存储管理方式的主要差别。答：它们的差别主要表现在以下几个方面：答：它们的差别主要表现在以下几个方面：（1）页面是信息的物理单位，分页是为了实现非连续分配，以便解决）页面是信息的物理单位，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要。段是信息的逻内存碎片问题，或者说分页是由于系统管理的需要。段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地实现共享，满足用户的需要。地实现共享，满足用户的需要。（2）页面的大小固定且由硬件确定页

28、面的大小固定且由硬件确定，将逻辑地址划分为页号和页内地，将逻辑地址划分为页号和页内地址是由机器硬件实现的。而址是由机器硬件实现的。而段的长度却不固定，它取决于用户所编段的长度却不固定，它取决于用户所编写的程序写的程序，通常由编译程序在对源程序进行编译时根据信息的性质，通常由编译程序在对源程序进行编译时根据信息的性质来划分。来划分。（3）分页式存储管理的作业地址空间是一维的，）分页式存储管理的作业地址空间是一维的，页偏移页偏移。分段式存储。分段式存储管理的作业地址空间是二维的，包括管理的作业地址空间是二维的，包括基地址和界限。基地址和界限。 2.在采用分页存储管理的系统中，某作业在采用分页存储管

29、理的系统中，某作业J的的逻辑地址空间为逻辑地址空间为4页（每页页（每页2KB），且已知），且已知该作业的页面映像表（即页表）如下所示。该作业的页面映像表（即页表）如下所示。试借助地址变换图（即要求画出地址变换图）求出有效逻辑地址4865所对应的物理地址。解：在本题中，一页大小为解：在本题中，一页大小为2KB，即，即2048字节，则字节，则逻辑地址逻辑地址4865的页号及的页号及页内位移为：页内位移为：页号：页号： 4865/2048=2页内位移：页内位移： 4865-2048*2=769通过页表可知页面通过页表可知页面2存放在存放在物理块物理块6中，将物理块号与中，将物理块号与逻辑地址中的页内

30、位移进逻辑地址中的页内位移进行拼接，形成物理地址，行拼接，形成物理地址，即：即：6*2048+769=130573.在一分页存储管理系统，页面大小为在一分页存储管理系统，页面大小为4KB。已知某进程。已知某进程的第的第0、1、2、3、4页依次存在内存中的页依次存在内存中的6、8、10、14、16物理块号中，现有逻辑地址为物理块号中，现有逻辑地址为12138D, 3A5CH ，分别求其所在的页号、页内相对地址、对应，分别求其所在的页号、页内相对地址、对应的物理块号以及相应的物理地址。的物理块号以及相应的物理地址。 p 解：（解：（1）已知页面大小）已知页面大小4KB=4096D，页号页号 p=I

31、NT12138/4096=2, 页内位移页内位移d=12138MOD4096=3946D 查页表可知页号查页表可知页号2对应物理块号为对应物理块号为10。 由地址转换原理可得：块内位移等于页内位移。由地址转换原理可得：块内位移等于页内位移。 故物理地址故物理地址=10*4096+3946=44906D（2）解法一：）解法一： 已知页面大小已知页面大小4KB，占，占12位，逻辑地址长度为位，逻辑地址长度为16位，故位，故高高4位为页号，低位为页号，低12位为页内位移。位为页内位移。 逻辑地址为：逻辑地址为：3A5CH=0011 1010 0101 1100B。则页号为：则页号为：3。 查页表可知

32、页号查页表可知页号3对应物理块号为对应物理块号为14。由地址转换原理可。由地址转换原理可得：块内位移等于页内位移，物理地址高得：块内位移等于页内位移，物理地址高4位为物理块号位为物理块号，低，低12位为块内位移。故物理地址为：位为块内位移。故物理地址为：1110101001011100B=EA5CH= 59996D解法二：解法二： 已知页面大小已知页面大小4KB=4096D，逻辑地址，逻辑地址3A5CH=14940D。页号。页号p=INT14940/4096=3, 页内位移页内位移d=14940MOD4096=2652D，查页表可知页号，查页表可知页号3对对应物理块号为应物理块号为14。由地址转换原理可得：块内位移等于。由地址转换原理可得：块内位移等于页内位移。页内位移。 故物理地址故物理地址=14*4096+2652=59996D=EA5CH4.若在一分页存储管理系统中，某作业的页表如下所示。若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为已知页面大小为1024字节，试将逻辑地址字节，试将逻辑地址1011，2148，4000，5012转化为相