当前位置：问答库＞考研试题

一、应用题

1． 考虑下列程序

假设矩阵A , B 的初始值已置好，矩阵C 初始为0, 各矩阵均以页为单位连续存放，又假定一

，代码以及变量i 、j 、k 放在其他页面里，并且存取变量i 、j 、k 时不个整数占用一个字（2字节）

缺页。主存初始为空，在请求分页存储管理中，页面淘汰算法为FIFO 。

（1）作业分配10个页面，每个页面为100个字，给矩阵A 、B 、C 使用。问执行上面的程序时，缺页次数是多少？当程序执行完时，留在内存的10个页面各属于哪些矩阵？

（2）当为作业分配两个页面，每个页面为500个字，给矩阵A 、B 、C 使用。问执行上面程序时，缺页次数是多少？

【答案】假设矩阵的存储是按行存储的，且每页均从页面首地址开始存放。

（1）矩阵A 占用150页，矩阵B 占用300页，矩阵C 占用200页。设矩阵A 占用的页面为1至150页，矩阵B 占用的页面为151至450页，矩阵C 占用的页面为451至650页。

程序对矩阵A 和C 的访问是按顺序访问，即从第1个元素开始依次访问矩阵中的所有元素。这样，程序对矩阵A 和C 的访问总是按矩阵在存储器内存放的顺序访问。程序对矩阵B 的访问是按列访问，即顺序访问每一元素后，再顺序访问每一列的第2个元素，如此直至访问所有的元素。这样，由于矩阵B 每行占用两页，因此每次对矩阵B 的访问都要访问与前一次不同的一页。

程序中运算式的执行次数为3000000次，每次需要依次访问矩阵A 、B 和C 。只要不跨页，每次访问矩阵A 和C 时无须调入新页，但访问矩阵B 时每次都需调入新页。这是因为矩阵B 有150行，每行都在不同的页，系统只有10个页面，所以每次访问矩阵B 时所需页面都不可能在系统中。

采用FIFO 算法，对于题中的页面访问过程，页面调度过程如下。

从上面的调度过程可以看出，当循环次数为时，读A , 读B 与读C/写C 都会发生缺页，其他情况只有读B 会发生缺页。前一种情况是由于矩阵B 所用的页面占用了所有的内存中的页面而造成的。后一种情况是由于读矩阵A 或C 时某一页面上数据已用完而读入下一页所致。根据这个规律，可以得出发生缺页的次数为

最后留在内存中的10个页面，其中1个属于矩阵A ，8个属于矩阵B ，1个属于矩阵C 。（2）若每页500个字，则矩阵A 占用30页，矩阵B 占用60页，矩阵C 占用40页。由于内存中只有两个页面，因此每次访问都会发生缺页，发生缺页的次数为

2． 下图将一组进程分为4类，假定各类进程之间采用优先级调度，每类进程内部采用时间片轮转调度。请简述PI 、P2、P3、P4、P5、P6、P7、P8进程的调度过程。

【答案】不同类进程之间采用优先级调度，而同类进程内部采用时间片轮转调度。先进行优先级4的进程调度，P1, P2, P3按时间片进行轮转；等Pl ，P2, P3均执行完，执行优先级3的进程P4, P5。同理P4, P5按时间片轮转，运行完成后调度优先级1的进程P6, P7, P8。进程P6, P7, P8按时间片轮转直至完成。

【解析】所谓多级反馈队列轮转法就是把就绪进程按优先级排成多个队列，并赋给每个队列不同的时间片，高优先级进程的时间片比低优先级进程的时间片小。调度时先选择高优先级队列的第一个进程，使其投入运行，当该进程时间片用完后，若高优先级队列中还有其他进程，则按

照轮转法依次调度执行，否则转入低一级的就绪队列。只有高优先级就绪队列为空时，才从低一级的就绪队列中调度进程执行。

二、综合题

3． 试对EDF 算法与RMS 调度算法进行比较。

【答案】（1）处理机的利用率。在利用RMS 算法时，处理机的利用率存在着一个上限。它随进程数的增加而减小，逐渐趋于最低的上限为0.693。然而对于EDF 算法，并不存在这样严格的限制，因而该算法可以达到100%的处理机利用率。事实上，对于任意一组任务，只要用静态优先级调度算法能够调度的，这一组任务也必定可用EDF 算法来调度。

（2）算法复杂度。RMS 算法比较简单，计算出的每一个进程的优先级，在任务运行期间通常不会改变。而EDF 算法的开销较大，因为它所依据的是动态优先级，它会不断地改变，每次调度时都需要先计算所有进程截止时间的大小，再从中选择最小的。

（3）调度的稳定性。RMS 算法易于保证调度的稳定性，因为RMS 算法在调度时所依

据的优先级是静态的。因此只需要赋予重要进程较高的优先级，使之在进程整个运行期间都能保证优先获得处理机。然而对于EDF 算法，由于所依据的截止时间是动态的，截止时间在运行期间不断变化，因此很难使最重要进程的截止时间得到保证。

4． 试对块索引存放方式的性能进行分析。

【答案】（1）支持随机访问

块索引存放方式虽然可以实现随机访问，但要比帧索引存放方式复杂些。

（2）磁盘碎片较大

在采取块索引存放方式时，在一个大盘块中可以存储多个帧，当盘块中的存储空间不足以装下后面一帧时，可采取两种处理方法:

a. —帧跨越两个盘块，该方法是继续装入下一帧，直到大盘块全部装满，剩余部分再装入下一个盘块。该方法的主要问题是，通常会发生再次寻道，影响播放质量。

b. 让剩余部分空闲，只要不能装下后面一帧，便让剩余的空间空着，由此会形成磁盘空间的浪费，我们把它称为内部碎片。大盘块法可能造成比小盘块法更大的碎片。

（3）块索引表小

在采取大盘块方式时，需要为每一块设置一个块索引表项。由于每一个盘块可以放多个帧，因此块索引表要比帧索引表小得多。

（4）缓冲管理复杂

在大盘块法中，虽然也可以采用双缓冲方式，但两个大缓冲需占用较多内存。由于在大盘块法中每一个大盘块都包含了多个帧，而每次仅播放一帧，因此完全不用一次将一个大盘块中的内容全部读出。对此可采用循环缓冲方式，即在系统中设置多个缓冲，每个缓冲稍大于磁盘块的大小，将这些缓冲组成循环缓冲器，整个循环缓冲器的容量应大于一帧的容量再加上一个盘块的容量。