操作系统例题

1、存储管理习题存储管理习题例例1 1.某系统采用动态分区管理技术。某时刻在内存某系统采用动态分区管理技术。某时刻在内存有三个空闲区，它们的首地址和大小分别是：空有三个空闲区，它们的首地址和大小分别是：空闲区闲区1（100KB，10KB），空闲），空闲2（200KB，30KB），空闲区），空闲区3（300KB，15KB），现有如），现有如下作业序列：作业下作业序列：作业1需要需要15KB，作业，作业2需求需求16KB，作业作业3需求需求10KB。要求：。要求：（1）画出该时刻内存分配图。）画出该时刻内存分配图。（2）用首次适应算法和最佳适应算法画出此时的）用首次适应算法和最佳适应算法画出此时的自由

2、主存队列结构。自由主存队列结构。（1）将作业序列装入主存之前，内存的分配图如下所示：10KB30KB15KB100KB110KB-1200KB230KB-1300KB315KB-1（2）首次适应算法的自由主存队列结构为：10KB30KB15KB链首指针100KB200KB300KB（2）最佳适应算法的自由主存队列结构为：10KB15KB30KB链首指针100KB300KB200KB例例2 2.在分页系统中地址结构长度为在分页系统中地址结构长度为16位位,页面页面大小为大小为2K,作业地址空间为作业地址空间为6K,该作业的各该作业的各页依次存放在页依次存放在2、3、6号物理块中，相对地号物理块中

3、，相对地址址2500处有一条指令处有一条指令store 1,4500，请给，请给出该作业的页表和该指令的物理单元以及出该作业的页表和该指令的物理单元以及数据存放的物理单元。数据存放的物理单元。答案答案 页面大小为页面大小为2K，即，即2048字节；作业地址空间字节；作业地址空间6K，则占用，则占用页数为页数为3，编号为，编号为0、1、2，依次存放在，依次存放在2、3、6号物理块号物理块中，作业页表如下：中，作业页表如下： 相对地址为相对地址为2500字节，应在第字节，应在第2500/2048=1号页面，余号页面，余数数452即为页内位移，所以对应的物理块号为即为页内位移，所以对应的物理块号为3

4、，得到物，得到物理地址为理地址为2048*3+452=6596；相对地址；相对地址4500/2048=2号号页面，页内位移为页面，页内位移为404，对应的物理块号为，对应的物理块号为6，得到物理，得到物理地址为地址为2048*6+404=12692。021326例例3 3.某操作系统的存储管理采用页式管理系统，某操作系统的存储管理采用页式管理系统，系统的物理地址空间大小为系统的物理地址空间大小为32K，页的大小，页的大小是是4K。假定某进程的大小为。假定某进程的大小为32页，请回答页，请回答如下问题：如下问题：（1）写出逻辑地址的格式。）写出逻辑地址的格式。（2）如果不考虑权限位，该进程的页表

5、有多）如果不考虑权限位，该进程的页表有多少项？每项至少多少位？少项？每项至少多少位？答案答案 页面大小是页面大小是4K，即，即212，进程大小是，进程大小是32页，页，即即25。（1）逻辑地址应有）逻辑地址应有17位，其中位，其中011位是页位是页内位移，内位移，1216位是页号。位是页号。（2）该进程页表有）该进程页表有32项，每项项，每项5位。位。例例4 4.对一个将页表放在内存中的分页系统：对一个将页表放在内存中的分页系统：（1）如果访问内存需要）如果访问内存需要（2）如果增加一个快表，且假定在快表中找到）如果增加一个快表，且假定在快表中找到页表项的概率高达页表项的概率高达90%，则有效

6、访问时间表又，则有效访问时间表又是多少（假定查找快表需花的时间为是多少（假定查找快表需花的时间为0）？）？s2.0答案答案 每次访问数据时，若不使用快表，则需要两次访每次访问数据时，若不使用快表，则需要两次访问内存，即先从内存的页表中读出页对应的块号，问内存，即先从内存的页表中读出页对应的块号，然后再根据形成的物理地址去存取数据；使用快然后再根据形成的物理地址去存取数据；使用快表时，若能从快表中直接找到对应的页表项，则表时，若能从快表中直接找到对应的页表项，则可立即形成物理地址去访问相应的数据，否则，可立即形成物理地址去访问相应的数据，否则，仍需两次访问内存。仍需两次访问内存。（1）有效访问时

7、间为：）有效访问时间为：（2）有效访问时间为：）有效访问时间为：s4 . 02 . 02s22. 02 . 02)9 . 01 (2 . 09 . 0例例5 5.在分页存储管理系统中，逻辑地址的长度在分页存储管理系统中，逻辑地址的长度为为16位，页面大小为位，页面大小为4096字节，现有一逻字节，现有一逻辑地址为辑地址为2F6AH，且，且0、1、2页依次存放在页依次存放在物理块物理块5、10、11中，问相应的物理地址是中，问相应的物理地址是多少？多少？答案答案分析：在分页存储管理系统中进行地址转换时，地址变换机构将自动把逻辑地分析：在分页存储管理系统中进行地址转换时，地址变换机构将自动把逻辑地

8、址转化为页号和页内地址，如果页号不小于页表长度，则产生越界中断；否则址转化为页号和页内地址，如果页号不小于页表长度，则产生越界中断；否则便以页号为索引去检索页表，从中得到对应的块号，并把块号和页内位移分别便以页号为索引去检索页表，从中得到对应的块号，并把块号和页内位移分别送入物理地址寄存器的块号和块内位移字段中，形成物理地址。送入物理地址寄存器的块号和块内位移字段中，形成物理地址。答案：由分析所给条件可知，分页存储管理系统的逻辑地址结构如下图：答案：由分析所给条件可知，分页存储管理系统的逻辑地址结构如下图：逻辑地址逻辑地址2F6AH的二进制表示如下：的二进制表示如下： 0010 1111011

9、01010 页号页号 页内位移页内位移由此可知逻辑地址由此可知逻辑地址2F6AH的页号为的页号为2，小于页表长度，小于页表长度3，没有越界，该页存放在，没有越界，该页存放在第第11个物理块中，用十六进制表示块号为个物理块中，用十六进制表示块号为B，所以物理地址为，所以物理地址为BF6AH。页号页号页内位移页内位移0111215例例7 7.某虚拟存储器的用户空间共有某虚拟存储器的用户空间共有32个页面，个页面，每页每页1KB，主存，主存16KB。假定某时刻系统为。假定某时刻系统为用户的第用户的第0、1、2、3页分别分配的物理块页分别分配的物理块号为号为5、10、4、7，试将虚拟地址，试将虚拟地址

10、0A5C和和093C变换为物理地址。变换为物理地址。答案答案 虚拟地址为虚拟地址为0A5C，对应的二进制数为：，对应的二进制数为：0000 1010 0101 1100。其中，页内偏移量占。其中，页内偏移量占10位地址位地址码，为码，为25C。因第页存储在号块中，其基地。因第页存储在号块中，其基地址为址为：0001 0000 0000 0000,这样，虚拟地址为这样，虚拟地址为十六进制的十六进制的125C。 虚拟地址为虚拟地址为093C，对应的二进制数为：，对应的二进制数为：0000 1001 0011 1100。其中，页内偏移量占。其中，页内偏移量占10位地址位地址码，为码，为13C。因第。

11、因第2号页存储在号页存储在4号块中，其基地号块中，其基地址为：址为：0001 0000 0000 0000， 010001 0011 1100。这样，虚拟地址为十六进制的。这样，虚拟地址为十六进制的113C。例例8 8.在采用页式存储管理的系统中，某作业在采用页式存储管理的系统中，某作业J的逻辑地址空的逻辑地址空间为间为4页（每页页（每页2048字节），且已知该作业的页面映像表字节），且已知该作业的页面映像表（即页表）如下：（即页表）如下： 试借助地址变换（要求画出地址变换图）求出有效逻辑地试借助地址变换（要求画出地址变换图）求出有效逻辑地址址4865所对应的物理地址。所对应的物理地址。页号页

12、号块号块号02142638分析与解答分析与解答 逻辑地址逻辑地址4865指的是指的是2号页中偏移地址为号页中偏移地址为769的存的存储单元（储单元（4865-4096=769）。而内存）。而内存6号块的起始号块的起始地址是地址是12288（2048*6），因此对应的物理地址为），因此对应的物理地址为13057（12288+769）。地址变换图如下：）。地址变换图如下：页表始址页表始址 页表长度页表长度页号页号偏移地址偏移地址02142638+页表寄存器逻辑地址页表物理地址13057122882769例例9 9.设一段表如图所示设一段表如图所示 那么，逻辑地址（那么，逻辑地址（2，88）对应的物

13、理地址）对应的物理地址是多少？逻辑地址（是多少？逻辑地址（4，100）所对应的物理地）所对应的物理地址是多少？址是多少？段号段号基地址基地址 段长段长02196001230014290100313275804195296分析与解答分析与解答(1)2号段所占的内存空间基地址是号段所占的内存空间基地址是90，段内地址是，段内地址是88，因此访存的物理，因此访存的物理地址应当是二者相加：地址应当是二者相加：90+88=178。(2)在分段存储管理系统中，段的长度是不固定的。因此段表内需要登记在分段存储管理系统中，段的长度是不固定的。因此段表内需要登记各段的实际长度，用以检查各段的实际长度，用以检查C

14、PU产生的访存地址是否超界。题中第产生的访存地址是否超界。题中第2部部分给出的段内地址是分给出的段内地址是100，而段的长度是，而段的长度是96，因此将，因此将产生越界中断产生越界中断，无，无任何物理地址产生。任何物理地址产生。段号段号基地址基地址段长段长02196001230014290100313275804195296段表始址段表始址段表长度段表长度段号段号段内地址段内地址+段表寄存器越界中断逻辑地址9017888例例10 10.某页式存储管理系统中，地址寄存器长度为某页式存储管理系统中，地址寄存器长度为24位，其中页号占位，其中页号占14位，则主存的分块大小应位，则主存的分块大小应该是

15、多少字节？程序最多占有多少页？该是多少字节？程序最多占有多少页？分析与解答分析与解答 主存的分块大小占主存的分块大小占10位，应为位，应为1K个字节，即个字节，即210。 程序最多可以占有程序最多可以占有16K个页，即个页，即214。页号页号位移量位移量091023逻辑地址 在分页机制中，需要将用户的线性地址空间划分成二维地址空间。让地址的高位部分作为页号，低位部分作为分块的大小，也称位移量。例例11 11.某虚拟存储器的用户空间共有某虚拟存储器的用户空间共有32个页面，个页面，每页每页1K，主存，主存16K。假定某时刻系统为用。假定某时刻系统为用户的第户的第0、1、2、3页分配的物理块号为页

16、分配的物理块号为5、10、4、7，而该用户作业的长度为，而该用户作业的长度为6页，试页，试将十六进制的虚拟地址将十六进制的虚拟地址0A5C转换成物理地转换成物理地址。址。分析与解题分析与解题 逻辑地址有逻辑地址有15位，其中高位，其中高5位为页号，低位为页号，低10位为页位为页内地址；物理地址有内地址；物理地址有14位，位，其中高其中高4位为块号，低位为块号，低10位为块内地址。位为块内地址。 逻辑地址逻辑地址(0A5C)16的页号的页号为为(00010)2，即，即2，故页号，故页号合法。从页表中找到对应合法。从页表中找到对应的内存块号为的内存块号为4，即，即(0100)2;与页内地址与页内地

17、址(10 0101 1100)2拼接形成物理拼接形成物理地址地址(010010 0101 1100)2,即即(125C)16。 0001010 0101 11000100100101 1100逻辑地址05A1CC52物理地址 125C页号2块号4页内地址页内地址 25C块内地址块内地址 25C例例12 在一个使用交换技术在一个使用交换技术(Swapping)的系统中的系统中,按地按地址从低到高排列的内存空间长度是址从低到高排列的内存空间长度是:10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。对。对于下列顺序段的请求于下列顺序段的请求： （1）12KB （2）10KB

18、（3）15KB （4）18KB （5）12KB 分别使用首次适配、最佳适配、最差适配和下次分别使用首次适配、最佳适配、最差适配和下次适配算法说明空间的使用情况，并说明对暂时不适配算法说明空间的使用情况，并说明对暂时不能分配情况的处理方法。能分配情况的处理方法。分析与解题分析与解题首次适配：首次适配：（1）12KB：2#区区 （2） 10KB：0#区区 （3） 15KB：3#区区 （4） 18KB：失败：失败 （5） 12KB：6#区区 最佳适配：最佳适配：1）12KB：6#区区 （2） 10KB：0#区区 （3） 15KB：7#区区 （4） 18KB： 3#区区 （5） 12KB：2#区区 最

19、差适配：最差适配：1）12KB：2#区区 （2） 10KB：3#区区 （3） 15KB：7#区区 （4） 18KB：失败：失败 （5） 12KB：6#区区 下次适配：下次适配：1）12KB：2#区区 （2） 10KB：3#区区 （3） 15KB：7#区区 （4） 18KB：失败：失败 （5） 12KB：6#区区 上述算法中，只有最佳适配算法是分配成功的，其他上述算法中，只有最佳适配算法是分配成功的，其他3种算法都在第种算法都在第4段请求（段请求（18KB）出现时分配失败。）出现时分配失败。当出现暂时不能分配的情况时，系统可以采用拼接技术，将内存中的当出现暂时不能分配的情况时，系统可以采用拼接技

20、术，将内存中的进程移动到存储器的一端，使夹杂于其间的空闲小空间移动到另一端，进程移动到存储器的一端，使夹杂于其间的空闲小空间移动到另一端，形成一个较大的可用空间，以满足用户的需求。形成一个较大的可用空间，以满足用户的需求。例例13 13.某页式存储管理系统中，地址寄存器长某页式存储管理系统中，地址寄存器长度度24位，其中页号占位，其中页号占14位，则主存的分块位，则主存的分块大小应该是（大小应该是（ ）字节，程序最多占有（）字节，程序最多占有（ ）页。页。 A. 210 B. 10 C.14 D. 214 E. 24 F. 224 分析与解答分析与解答 本题的考核要点是内存分页管理机制，主要涉

21、及本题的考核要点是内存分页管理机制，主要涉及页面长度的划分方法。我们知道，在分页机制中，页面长度的划分方法。我们知道，在分页机制中，需要将用户的线性地址空间划分成二维地址空间。需要将用户的线性地址空间划分成二维地址空间。让地址的高位部分作为页号，低位部分作为分块让地址的高位部分作为页号，低位部分作为分块的大小，也称位移量，见下图所示。的大小，也称位移量，见下图所示。 主存的分块大小占主存的分块大小占10位，应为位，应为1K个字节，即个字节，即210。因此，第1个选项是A，程序最多可以占有程序最多可以占有16K个个页，即页，即214，第2个选项是D。页号位移量231090 例例14 14.假设一

22、个分页存储管理系统具有快表，假设一个分页存储管理系统具有快表，多数活动页表项都可以存在其中。如果页多数活动页表项都可以存在其中。如果页表放在内存中，内存访问时间是表放在内存中，内存访问时间是1s, 若快若快表的命中率是表的命中率是85%，则有效存取时间为多，则有效存取时间为多少？若快表的命中率为少？若快表的命中率为50%，那么有效存，那么有效存取时间为多少？取时间为多少？分析与解答分析与解答 本题的考核要点是内存分页存储管理中，本题的考核要点是内存分页存储管理中，具有快表机制的访问过程，涉及的内容有：具有快表机制的访问过程，涉及的内容有： 1）当快表的命中率是）当快表的命中率是85%时，有效存

23、取时时，有效存取时间为：间为： 0.851+(1-0.85) (1+1)=1.15m 2）当快表的命中率是）当快表的命中率是50%时，有效存取时时，有效存取时间为：间为： 0.51+(1-0. 5) (1+1)=1. 5m例例15 15.在可变式分区分配方案中，某在可变式分区分配方案中，某 一作业完一作业完成后系统收回其主存空间，并与相邻空闲成后系统收回其主存空间，并与相邻空闲区合并，为区合并，为此需修改空闲区表，造成空闲需修改空闲区表，造成空闲数减数减1的情况是（的情况是（ ）。）。 A.无上邻空闲区，也无下邻空闲区无上邻空闲区，也无下邻空闲区 B.有上邻空闲区，但无下邻空闲区有上邻空闲区，

24、但无下邻空闲区 C.有下邻空闲区，但无上邻空闲区有下邻空闲区，但无上邻空闲区 D.有上邻空闲区，也有下邻空闲区有上邻空闲区，也有下邻空闲区分析与解答分析与解答 本题的考核要点是可变分区管理系统的空闲分区回收问题。本题的考核要点是可变分区管理系统的空闲分区回收问题。当用户归还一个空闲分区后，系统在挂入空闲分区链表时当用户归还一个空闲分区后，系统在挂入空闲分区链表时需要将相邻空闲分区合并，形成一个大的空闲分区，需要将相邻空闲分区合并，形成一个大的空闲分区，因此涉及的内容有： 1）无上邻空闲区，也无下邻空闲区的情况下，系统将回无上邻空闲区，也无下邻空闲区的情况下，系统将回收的空闲分区挂入空闲链表，使

25、空闲分区总数增加收的空闲分区挂入空闲链表，使空闲分区总数增加1。 2）有上邻空闲区，但无下邻空闲区的情况下，系统将回）有上邻空闲区，但无下邻空闲区的情况下，系统将回收的空闲分区并入上邻分区中，使空闲分区总数不增不减。收的空闲分区并入上邻分区中，使空闲分区总数不增不减。 3）有下邻空闲区，但无上邻空闲区的情况下，系统将回）有下邻空闲区，但无上邻空闲区的情况下，系统将回收的空闲分区并入下邻分区中，使空闲分区总数不增不减。收的空闲分区并入下邻分区中，使空闲分区总数不增不减。 4）有上邻空闲区，也有下邻空闲区的情况下，系统将回）有上邻空闲区，也有下邻空闲区的情况下，系统将回收的空闲分区与上收的空闲分区

26、与上/下邻分区合并为一个大分区，使空闲下邻分区合并为一个大分区，使空闲分区总数减分区总数减1。例例16 16.在一个请求分页存储管理系统中，一个在一个请求分页存储管理系统中，一个作业的页面走向为作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块，当分配给该作业的物理块数分别为数分别为3、4时，试计算采用下述页面淘时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。中没有页面），并比较所得结果。（1）最佳置换淘汰算法）最佳置换淘汰算法（2）先进先出淘汰算法）先进先出淘汰算法（3）最近最久

27、未使用淘汰算法）最近最久未使用淘汰算法题解题解 （1）根据所给页面走向，使用最佳页面淘汰算）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下所示。法时，页面置换情况如下所示。走向走向 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 4 4 2 2块块2 3 3 3 3 3 1块块3 2 1 5 5 5 缺页缺页 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺缺页率：7/12（A）题解题解走向走向 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 4 4 1块块2 3 3 3 3 3块块3 2 2 2 2块块4 1 5 5缺页缺页 缺缺 缺缺 缺缺 缺缺 缺

28、缺 缺缺缺页率：6/12（B）题解题解 （2）根据所给页面走向，使用先进先出页面淘）根据所给页面走向，使用先进先出页面淘汰算法时，页面置换情况如下所示。汰算法时，页面置换情况如下所示。走向走向 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 1 1 1 5 5 5 块块2 3 3 3 4 4 4 2 2块块3 2 2 2 3 3 3 1 缺页缺页 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺缺页率：9/12（A）题解题解走向走向 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 4 5 5 5 5 5 5 块块2 3 3 3 3 4 4 4 4 5块块

29、3 2 2 2 2 3 3 3 3 块块4 1 1 1 1 2 2 2 缺页缺页 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺缺页率：10/12（B）由上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而使缺页率上升，这种异常现象称为Belady现象。题解题解 （3）根据所给页面走向，使用最近最久未使用）根据所给页面走向，使用最近最久未使用页面淘汰算法时，页面置换情况如下所示。页面淘汰算法时，页面置换情况如下所示。走向走向 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 1 1 1 5 2 2 2 块块2 3 3 3 4 4 4 4 1 1块块3 2 2 2 3 3 3 3 5 缺页缺页 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺缺页率：10/12（A）题解题解走向走向 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 4 4 4 4 5 块块2 3 3 3 3 3 3 3块块3 2 2 5 5 1 1 块块4 1 1 2 2 2 缺页缺页 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺 缺缺缺页率：8/12（B）由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率。例例17 17.有一页式系统有一页式系统,其页表存放在主存中其页表存放在主存中. (1)如果