《操作系统原理》
答：分析：由于每个主存块可以存放128个数组元素，只有一个内存块可以用来存放数组信息，数组中的元素按行编址。
对于第一个程序，数组访问顺序是：A[1,1],A[2,1],A[3,1], ??,A[128,1] A[1,2],A[2,2],A[3,2], ??,A[128,2] ???.
若采用LRU页面调度算法时，两个程序各会产生多少次缺页中断？
分析：由于每个主存块可以存放128个数组元素，只有一个内存块可以用来存放数组信息，数组中的元素按行编址。
对于第一个程序，数组访问顺序是：A[1,1],A[2,1],A[3,1], ??,A[128,1] A[1,2],A[2,2],A[3,2], ??,A[128,2] ???. A[1,128],A[2,128],A[3,128], ??,A[128,128]
显然，数组的存放顺序（按行）与访问顺序（按列）不一致，每访问一个数组元素遇到一次缺页中断。如果采用LRU算法，会产生128×128次缺页中断
对于第二个程序，数组访问顺序为：A[1,1],A[1,2],A[1,3], ??,A[1,128] A[2,1],A[2,2],A[2,3], ??,A[2,128] ???.
A[128,1],A[128,2],A[128,3], ??,A[128,128] 显然，数组的存放顺序（按行）与访问顺序（按行）一致，每访问一行数组元素遇到一次缺页中断。如果采用LRU算法，会产生128次缺页中断
解：采用LRU算法时，程序（1）会产生128×128次缺页中断，程序（2）会产生128次缺页中断。
6、某系统采用请求分页存储管理方案，其逻辑地址有20位，页内地址占11位，页号占9位。有一个4页的作业其逻辑页号0，1，2，3分别装入了存储空间的4，7，5，8块。
- 45 -
《操作系统原理》
（1）作业的虚存地址空间有多大？ （2）系统的页面大小为多少？
（3）逻辑地址5000对应的物理地址是多少？
解：（1）作业的虚存地址空间为：2=1MB （2）系统的页面大小为：2=2KB
（3）逻辑地址5000分解成页号P和页内地址W为：P=2，W=904，其对应的物理地址为 5×2KB+904=10KB+904=11144
分析：逻辑地址结构为20位，而页内地址占11位，页号占9位，所以作业的虚存地址空间为2=1MB，系统的页面大小为2=2KB。把逻辑地址5000分解为页号和页内地址：5000 mod 2K, 得到页号为2，页内偏移为904，查页表，页号2 对应的物理块号为5，从而可以求出对应的物理地址。
7、有一个多道程序设计系统，采用可变分区方式管理主存中的用户空间，且允许移动已在主存中的作业。设用户空间为200K，主存空间的分配算法为最先适应分配算法，现有如表所示作业采用先来先服务进行调度。 作业名 进入“输入井”时间 A B C D 8:30 8:40 8:50 9:00 40 30 50 20 40K 120K 180K 80K 8:30 8:40 10:00 9:10 8:30 9:10 10:00 9:40 9:10 9:40 10:50 10:00 40 60 120 60 需计算时间（分钟） 主存要求 装入主存时间 开始执行时间 执行结束时间 周转时间（分钟） 20
11
11
20
（1）按上述要求填充表中的空白处
(2)计算四个作业的平均周转时间(40+60+120+60)/4=70
- 46 -
《操作系统原理》
答： 作业名 进入“输入井”时间 A B C D
8、在页式虚拟存储管理的计算机系统中，运行一共有9页的作业，且作业在主存中分配到4块主存空间，作业执行时访问页面的顺序为8、0、2、3、0、4、0、5、3、4、0、4、3、2、3、0、2、8和0。请列出采用FIFO和LRU调度算法时页面装入调出的情况，并计算采用两种调度算法时发生缺页中断的次数分别是多少？
答：FIFO： 是否缺页 内存中包含的页面 8 8 8 8 0 0 0 2 2 3 4 0 2 3 4 5 2 3 4 5 0 3 4 3 5 5 0 0 2 2 3 8 0 2 8 0 2 3 0 4 0 5 3 4 0 4 3 2 3 0 2 8 0 * * * * * * * * * * 8:30 8:40 8:50 9:00 40 30 50 20 40K 120K 180K 80K 8:30 8:40 10:00 9:10 8:30 9:10 10:00 9:40 9:10 9:40 10:50 10:00 40 60 120 60 需计算时间（分钟） 主存要求 装入主存时间 开始执行时间 执行结束时间 周转时间（分钟） 产生10次缺页中断 LRU： 是否缺页 内存中8 8 8 8 4 4 - 47 -
8 0 2 3 0 4 0 5 3 4 0 4 3 2 3 0 2 8 0 * * * * * * * * 4 8 《操作系统原理》
包含的页面 0 0 0 2 2 3 0 2 3 0 5 3 0 2 3 0 2 3 产生8次缺页中断
9、有一个多道程序设计系统，采用不允许移动的可变分区方式管理主存中的用户空间，设用户空间为100K，主存空间的分配算法为最先适应分配算法，现有作业如下表所示：
作业名 进入“输入需计算时主存井”时间 间（分钟） 要求 A B C D E 8:06 8:18 8:30 9:00 9:10
（1）假设所有作业都是计算型作业且忽略系统调度时间。请分别写出采用“先来先服务算法”和“短作业优先算法”选中作业执行的次序及它们的平均周转时间，并把各作业被装入主存时间、占用处理器开始执行的时间，执行结束时间和周转时间列表表示出来。 （2）简述作业的先来先服务调度算法和短作业优先算法各有什么特点。
答：1）采用“先来先服务算法”：
作业名 装入主存的时间 A B D C 8:06 8:18 9:00 9:14 8:06 8:46 9:14 9:39 8:46 9:14 9:39 10:01 开始执行时间 执行结束时间 周转时间（分钟） 40 56 39 91 40 28 22 25 10 15K 60K 40K 10K 30K - 48 -
《操作系统原理》
E 9:14 10:01 10:11 61 所以，作业的执行顺序为A、B、D、C、E。作业的平均周转时间为：（40+56+39+91+61）/5=57.4分钟。 采用“短作业优先算法”：
作业名 装入主存的时间 A B D E C 8:06 8:18 9:00 9:14 9:14 8:06 8:46 9:14 9:39 9:49 8:46 9:14 9:39 9:49 10:11 开始执行时间 执行结束时间 周转时间（分钟） 40 56 39 39 101 所以，作业的执行顺序为A、B、D、E、C。作业的平均周转时间为：（40+56+39+39+101）/5=55分钟。
先来先服务算法具有一定的公平性，容易实现。但当计算时间长的作业先进入“输入井”而被选中执行时，就可能使计算时间短的作业长时间等待，从而使计算时间短的作业周转时间变长，因此平均周转时间也变长，降低了系统的吞吐能力。
采用短作业优先算法，能使平均周转时间最短。由于系统可以不断接受新作业进入输入井，如果新进入的作业估计的计算时间比较短，则会使进入输入井时间较早但计算时间长的作业等待时间过长，会令用户不满。由于该算法是以用户估计的计算时间为标准，所以要避免用户为了使自己的作业优先被处理而故意将计算时间估计得短一些。
- 49 -