P0 P1 P2 P3 P4 5 3 3 2 2 9 0 2 2 2 2 4 3 3 0 1 0 （0 3 0） 3 0 2 3 0 2 2 1 1 0 0 2 7 4 3 2 3 0 （7 2 3） （2 1 0） 0 2 0 6 0 0 0 1 1 4 3 1
进行安全性检查 P0 P1 P2 P3 P4 Max A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 Allocation A B C 0 3 0 3 0 2 3 0 2 2 1 1 0 0 2 Need A B C 7 2 3 0 2 0 6 0 0 0 1 1 4 3 1 Available A B C 2 1 0
可用资源Available(2,1,0)已不能满足任何进程的需要，系统进入不安全状态，故系统不能同意P0的请求，让其阻塞。
练习1：（1）3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？
解：该系统不会因为竞争该资源而死锁。因为必有1个进程可获得2个资源，顺利完成其任务，其后可释放出占用的2个资源给其他进程使用，使他们顺利完成。
练习1：（2）n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n，说明该系统不会因竞争该类资源而阻塞。
解：用Maxi、Needi和Allocationi分别表示第i个进程对该类资源的最大需求量，需求量以及已分配的量，根据题意它们满足下述条件： >0i n 若系统已因竞争该资源而进入死锁状态，则意味着已有一个以上的进程因申请不到该类资源而无限阻塞，而m个资源肯定已全部分配出去，即： n =mii=1 nnn因此： =- Need?Max?Allocation?Need?Max?Allocation?Need 这样，至少必须存在1个进程，其Needi≤0，这与题意不符，所以该系统不会因竞争该类资源而进入死锁状态。 （3）在（2）中，如果没有“每个进程都需要用该类资源”的限制，情况又如何？ 解：此时系统可能会发生死锁。假设n=4，m=3，P1的Max为0，而其余3个进程的Max都为2，则仍然满足最大需求量之和小于m+n的要求，当除了P1以外的其余3个进程各得到1个资源时，这3个进程就可能进入死锁状态。 练习2：在银行家算法中，若出现下面的资源分配情况： P0 P1 P2 P3 P4 Allocation Need Available A B C D A B C D A B C D 0 0 3 2 1 0 0 0 1 3 5 4 0 0 3 2 0 0 1 4 0 0 1 2 1 6 2 2 1 6 5 0 2 3 5 6 0 6 5 2 0 6 5 6 试问:（1）该状态是否安全？ （2）当进程P2提出请求Request（1,2,2,2）后，系统能否将资源分配给它？ （3）如果系统立即满足P2的上述请求，则系统是否立即进入死锁状态？ 解：（1）利用安全性检查算法对上面的状态进行分析，可找到一个安全序列{P0, P1,P3,P4,P2}，故系统是安全的。 （2）P2发出请求向量后，系统按银行家算法进行检查，在进行试分配后，进行安全性检查时发现：此时对于所有进程，Available不能满足任何进程的请求，故系统不进行资源分配。 （3）系统立即满足进程P2的请求后，并没有马上进入死锁状态。因为：此时其他进程并没有申请新的资源，并因得不到资源而进入阻塞状态；只有当上述的其他进程提出新的请求，并导致所有没有执行完的多个进程因得不到资源而阻塞并形成循环等待链时，系统才进入死锁状态。 第四章 例：在某系统中，采用固定分区分配管理方式，内存分区（单位字节）情况如图所示， 现有大小为1K、9K、33K、121K的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明主存浪费多大？ 0k 20k 28k 60k 180k （1） 内存分区图 os 1 2 3 4 区号 大小 1 2 3 4 8k 32k 120k 331k 起址 20k 28k 60k 180k 状态 未分配 未分配 未分配 未分配 解：根据分区说明表，给4个作业分配分区，同时修改分区说明表，其内存分配和分区说明表如下所示： 分区说明表： 内存分配图（见第四章PPT第27页） 区号 大小 1 2 3 4 8k 32k 120k 331k 起址 20k 28k 60k 180k 状态 已分配 已分配 已分配 已分配 (3)主存浪费空间=(8-1)+(32-9)+(120-33)+(331-121) =7+23+87+210=327(k) 例题 在可变分区存储管理下，按地址排列的内存空闲区为：100KB、500KB、200KB、300KB 和600KB。现有若干用户程序，其所需内存依次分别为212KB、417KB、112KB和426KB，分别用首次适应算法、最佳适应算法、最坏适应算法，将它们装入到内存的哪些空闲分区？哪个算法能最有效利用内存？ 解：采用首次适应算法 程序 空闲区 新空闲区 212KB 500KB 288KB 417KB 600KB 183KB 112KB 288KB 176KB 426KB，无法装入内存 区号 1 2 3 4 5 大小 100k 500k 200k 300k 600K 状态 未分配 未分配 未分配 未分配 未分配 解：采用最佳适应算法 区号 1 2 3 4 5 大小 100k 200k 300k 500k 600K 状态 未分配 未分配 未分配 未分配 未分配 程序 空闲区 新空闲区 212KB 300KB 88KB 417KB 500KB 83KB 112KB 200KB 88KB 426KB 600KB 174KB 类似的分析可知,最坏适应算法也不能将426KB的程序装入内存。 例题: (华中科技大学2001)某操作系统采用可变分区分配存储管理方法,用户区大小为512K且初始值为0,用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对于下列申请序列： 申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K 回答下列问题： （1）请分别画出采用首次适应算法、最佳适应算法进行内存分配和回收后的内存使用状态。 （2）如果再申请100K，针对上述两种算法会有什么结果？ 例题解答如下：见ppt 例1： 某型微机的页面大小是1KB（1024B）,现该微机正在执行的进程中有一条指令： load a,2500 请问：在内存的什么位置可以找到该逻辑地址所对应的数据？假定块号0的初始物理地址为0。 逻辑地址的分解 若逻辑地址为A,页面大小为L,则页号P和页内地址d可按下式求得： P=int(A/L) d=A mod L 举例说明 页面大小为4KB，逻辑地址为7800及5F86H，分别求它们的页号和页内偏移。 计算过程如下：load a,2500 A、页号P＝INT(逻辑地址/页面大小)＝INT(2500/1024)=2 B、页内地址d =2500 MOD 1024=452 C、查页表 假定页号2对应的物理块是块5 D、物理地址为： 块号×页大小＋页内地址＝5×1024＋452=5572 即：将5572这个物理地址里面的数据取出来放在a寄存器里 注意：本题的前提条件是块号0的初始物理地址为0，如果不 是0，该怎么办？ 练习题 1.设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块。试问逻辑地址至少应为多少位？内存空间有多大？ 2.在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096B，现有一逻辑地址为2FA6H，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？ 硬件能自动分离出页号和页内地址，但我们只能通过计算才能得到。计算时要注意： (1)逻辑地址以十六进制、八进制、二进制的形式给出 将逻辑地址转换成二进制的数； 按页的大小分离出页号和页内地址（低位部分是页内地址，高位部分是页号）； 根据题意产生页表； 将页内地址直接复制到物理地址的低位部分； 以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址的高位部分，从而形成内存物理地址。 0 1 5 10