2. 考研
  3. 下列程序实现了矩阵乘法。 int A[100][150]； int B[150][200]； int C[i00][200]； for(i=0；i＜100，i++) for(j=0；j＜200；j++) for(k=0；k＜150；k++)

下列程序实现了矩阵乘法。 int A[100][150]； int B[150][200]； int C[i00][200]； for(i=0；i＜100，i++) for(j=0；j＜200；j++) for(k=0；k＜150；k++)

admin2017-11-20  10
问题 下列程序实现了矩阵乘法。
int A[100][150]；
int B[150][200]；
int C[i00][200]；
for(i=0；i＜100，i++)
    for(j=0；j＜200；j++)
    for(k=0；k＜150；k++)
    C[j]+=A[k]*B[k][j]；
    假设矩阵A和矩阵B的初值已经初始化过，矩阵C初始化为0，各矩阵均以页为单位连续存放(且假定是行优先存储)。又假定一个整数占用1个字，代码以及变量i、j和k存放在其他页面里，并且存取变量i、j和k时不存在缺页问题。主存初始为空，在请求分页存储管理中，页面淘汰算法为FIFO。
作业分配10个页面，每个页面为100字，给矩阵A、B和C使用。问执行上面的程序时，缺页次数是多少?当执行完程序时，留在内存的10个页面各属于哪些矩阵?
选项
答案矩阵是按行存储的，且每页均从页面首址开始存放，则矩阵A、B、C的存储情况如表2-12所示。 [*] 程序执行中对存储器的访问顺序为读A、读B、读C和写C。由于每页可存放100个字，由表2．12可知，矩阵A占用150页、矩阵B占用300页、矩阵C占用200页。假设矩阵A占用的页面为1～150，矩阵B占用的页面为151～450，矩阵C占用的页面为451～650。其存储示意图如图2-11所示。 [*] 程序对矩阵A和C的访问是按行访问，即矩阵A和C的存放顺序与访问顺序相同。程序对矩阵B的访问是按列访问，矩阵B的存放顺序与访问顺序不一致，即访问顺序是访问某列的第1个元素后，再访问该列的第2个元素、第3个元素……并且，由于矩阵B每行必须用两页存储，所以一列第1个元素与第2个元素存储在不同的页中，也即按列顺序访问时，每次对矩阵B的访问实际上都要访问与前一页访问不同的页。 程序中的三重for循环执行的次数为100×200×150=3000000次，每次需要一次访问矩阵A、B和C。只要不跨页，每次访问矩阵A和C时无需调入新页，但每次访问矩阵B中的元素都需要调入新页。由于系统只有10个页面，所以每次访问矩阵B，被访问元素所在页面都不在内存中。 采用FIFO算法，当循环次数为n1×9+1或n2×100+1时，读A、读B与读C或写C都会出现缺页，而其他情况只有在读B时会出现缺页。 n1×9+1时的情况是由于矩阵B需要占用页面，而把矩阵A、C换出，造成下次访问矩阵A、C时出现缺页。 第9次循环结束时 A B C B B B B B B B B 此时根据FIFO，A页面被换出。 第10次循环结束时(即n1=1的情况) A B C B B B B B B B B A B C 需要访问A，根据FIFO，B页面被换出，需要访问B，C页面也被换出，最后又要访问C，C页面又被换入。 n2×100+1时的情况则是需要读A或C新的一页数据造成的缺页。 n1×9+1的取值范围为[1，10，19，28，37，…，901，…，333333×9+1] n2×100+1的取值范围为[1，101，201，…，901，…，29999×100+1] 当n2为9的倍数时，会有共同项出现，如901、1801… 这种共同项个数为[30000／9]=3333。去掉重复项后，A和C的缺页总次数为(333333+29999-3333)×2。 根据上述规律可得出缺页的次数为 [100×200×150+(333333+29999-3333)×2]次=3719998(次) 最后留在内存中的10个页面，其中1个页面属于矩阵A，8个页面属于矩阵B，1个页面属于矩阵C。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/CjRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)