[已解决]操作系统选择题

Max472

有一个矩阵为100行×200列，即a[100][200]。在一个虚拟系统中，采用LRU算法。系统分给该进程5个页面来存储数据(不包含程序)，设每页可存放200个整数，该程序要对整个数组初始化，数组存储时是按行存放的。试计算下列两个程序各自的缺页次数(假定所有页都以请求方式调入)______。

程序一：

for(i=0;i＜=99;i++)
for(j=0;j＜=199;j++)
A[i][j]=i*j;

程序二：

for(i=0;j＜=199;j++)
for(i=0;i＜=99;i++)
A[i][j]=i*j;

A.100，200
B.100，20000
C.200，100
D.20000，100
答案：B

来个大神讲讲好吗？

最佳答案

月排行榜 / 总排行榜

人造人

2021-9-7 21:47:00

先看这个数组 a[100][200] 在内存中的布局
这个数组中的每一个元素都有一个唯一的地址
a[0][0] 的地址是 0
a[0][1] 的地址是 1
a[0][2] 的地址是 2
...
a[0][197] 的地址是 197
a[0][198] 的地址是 198
a[0][199] 的地址是 199
...
a[1][0] 的地址是 200
a[1][1] 的地址是 201
a[1][2] 的地址是 202
...
a[1][197] 的地址是 397
a[1][198] 的地址是 398
a[1][199] 的地址是 399
...
a[2][0] 的地址是 400
a[2][1] 的地址是 401
a[2][2] 的地址是 402
...
a[2][197] 的地址是 597
a[2][198] 的地址是 598
a[2][199] 的地址是 599
...
a[97][0] 的地址是 19400
a[97][1] 的地址是 19401
a[97][2] 的地址是 19402
...
a[97][197] 的地址是 19597
a[97][198] 的地址是 19598
a[97][199] 的地址是 19599
...
a[98][0] 的地址是 19600
a[98][1] 的地址是 19601
a[98][2] 的地址是 19602
...
a[98][197] 的地址是 19797
a[98][198] 的地址是 19798
a[98][199] 的地址是 19799
...
a[99][0] 的地址是 19800
a[99][1] 的地址是 19801
a[99][2] 的地址是 19802
...
a[99][197] 的地址是 19997
a[99][198] 的地址是 19998
a[99][199] 的地址是 19999

就是先存放 a[0][0] ~ a[0][199]，然后存放 a[1][0] ~ a[1][199]，然后是 a[2][0] ~ a[2][199]，。。。
有一个公式可以计算出某一个元素的地址
a[x][y] 的地址是 x * 200 + y
例如 a[98][2] 的地址是 98 * 200 + 2 = 19602

按照题意，一页可以储存 200 个数
就是 a[x][0] ~ a[x][199]


程序1 是这样访问数组的
a[0][0], a[0][1], a[0][2], ..., a[0][197], a[0][198], a[0][199], 
a[1][0], a[1][1], a[1][2], ..., a[1][197], a[1][198], a[1][199], 
a[2][0], a[2][1], a[2][2], ..., a[2][197], a[2][198], a[2][199], 
...
就是先访问 a[0][0] ~ a[0][199]，然后访问 a[1][0] ~ a[1][199]，然后是 a[2][0] ~ a[2][199], ...

在访问 a[0][0] 的时候，数据不存在，发生 1 次缺页，系统把 a[0][0] ~ a[0][199] 这 200 个数调入内存
之后访问 a[0][1], a[0][2], a[0][3], ..., a[0][197], a[0][198], a[0][199], 到目前为止一切正常
当访问 a[1][0] 的时候，数据不存在， 又一次缺页，系统把 a[1][0] ~ a[1][199] 这 200 个数调入内存
访问 a[2][0] ~ a[2][199] 一次缺页
这样一共是 100 次缺页
访问 a[0][0] 1 次
访问 a[1][0] 1 次
访问 a[2][0] 1 次
。。。
访问 a[97][0] 1 次
访问 a[98][0] 1 次
访问 a[99][0] 1 次
一共 100 次




程序2
访问 a[0][0] 一次缺页
然后访问的不是 a[0][1]
访问的是 a[1][0]，现在在内存中的是 a[0][0] ~ a[0][199]
a[1][0] 不在内存中，又一次缺页，系统调入 a[1][0] ~ a[1][199]
然后访问的是 a[2][0], 又一次缺页
系统调入 a[2][0] ~ a[2][199]
其实每一次缺页异常后，只用到了一个数
然后是 a[3][0] 异常
然后是 a[4][0] 异常
。。。
然后是 a[97][0] 异常
然后是 a[98][0] 异常
然后是 a[99][0] 异常
然后是 a[0][1] 这里还是异常，因为上一次载入内存的是 a[99][0] ~ a[99][199]
这一次用的是 a[0][1]，这个数据在 a[0][0] ~ a[0][199] 这一页上
第一次缺页异常的确载入了 a[0][0] ~ a[0][199]，但是系统只有 5 个页，a[0][0] ~ a[0][199] 这一页的内容早就被之前的操作覆盖了
就是程序2 访问一个数就会发生一次缺页异常
程序2 访问了 100 * 200 = 20000 次内存，发生了 20000 次异常

跳转到最佳答案楼层

人造人

先看这个数组 a[100][200] 在内存中的布局
这个数组中的每一个元素都有一个唯一的地址
a[0][0] 的地址是 0
a[0][1] 的地址是 1
a[0][2] 的地址是 2
...
a[0][197] 的地址是 197
a[0][198] 的地址是 198
a[0][199] 的地址是 199
...
a[1][0] 的地址是 200
a[1][1] 的地址是 201
a[1][2] 的地址是 202
...
a[1][197] 的地址是 397
a[1][198] 的地址是 398
a[1][199] 的地址是 399
...
a[2][0] 的地址是 400
a[2][1] 的地址是 401
a[2][2] 的地址是 402
...
a[2][197] 的地址是 597
a[2][198] 的地址是 598
a[2][199] 的地址是 599
...
a[97][0] 的地址是 19400
a[97][1] 的地址是 19401
a[97][2] 的地址是 19402
...
a[97][197] 的地址是 19597
a[97][198] 的地址是 19598
a[97][199] 的地址是 19599
...
a[98][0] 的地址是 19600
a[98][1] 的地址是 19601
a[98][2] 的地址是 19602
...
a[98][197] 的地址是 19797
a[98][198] 的地址是 19798
a[98][199] 的地址是 19799
...
a[99][0] 的地址是 19800
a[99][1] 的地址是 19801
a[99][2] 的地址是 19802
...
a[99][197] 的地址是 19997
a[99][198] 的地址是 19998
a[99][199] 的地址是 19999

就是先存放 a[0][0] ~ a[0][199]，然后存放 a[1][0] ~ a[1][199]，然后是 a[2][0] ~ a[2][199]，。。。
有一个公式可以计算出某一个元素的地址
a[x][y] 的地址是 x * 200 + y
例如 a[98][2] 的地址是 98 * 200 + 2 = 19602

按照题意，一页可以储存 200 个数
就是 a[x][0] ~ a[x][199]


程序1 是这样访问数组的
a[0][0], a[0][1], a[0][2], ..., a[0][197], a[0][198], a[0][199], 
a[1][0], a[1][1], a[1][2], ..., a[1][197], a[1][198], a[1][199], 
a[2][0], a[2][1], a[2][2], ..., a[2][197], a[2][198], a[2][199], 
...
就是先访问 a[0][0] ~ a[0][199]，然后访问 a[1][0] ~ a[1][199]，然后是 a[2][0] ~ a[2][199], ...

在访问 a[0][0] 的时候，数据不存在，发生 1 次缺页，系统把 a[0][0] ~ a[0][199] 这 200 个数调入内存
之后访问 a[0][1], a[0][2], a[0][3], ..., a[0][197], a[0][198], a[0][199], 到目前为止一切正常
当访问 a[1][0] 的时候，数据不存在， 又一次缺页，系统把 a[1][0] ~ a[1][199] 这 200 个数调入内存
访问 a[2][0] ~ a[2][199] 一次缺页
这样一共是 100 次缺页
访问 a[0][0] 1 次
访问 a[1][0] 1 次
访问 a[2][0] 1 次
。。。
访问 a[97][0] 1 次
访问 a[98][0] 1 次
访问 a[99][0] 1 次
一共 100 次




程序2
访问 a[0][0] 一次缺页
然后访问的不是 a[0][1]
访问的是 a[1][0]，现在在内存中的是 a[0][0] ~ a[0][199]
a[1][0] 不在内存中，又一次缺页，系统调入 a[1][0] ~ a[1][199]
然后访问的是 a[2][0], 又一次缺页
系统调入 a[2][0] ~ a[2][199]
其实每一次缺页异常后，只用到了一个数
然后是 a[3][0] 异常
然后是 a[4][0] 异常
。。。
然后是 a[97][0] 异常
然后是 a[98][0] 异常
然后是 a[99][0] 异常
然后是 a[0][1] 这里还是异常，因为上一次载入内存的是 a[99][0] ~ a[99][199]
这一次用的是 a[0][1]，这个数据在 a[0][0] ~ a[0][199] 这一页上
第一次缺页异常的确载入了 a[0][0] ~ a[0][199]，但是系统只有 5 个页，a[0][0] ~ a[0][199] 这一页的内容早就被之前的操作覆盖了
就是程序2 访问一个数就会发生一次缺页异常
程序2 访问了 100 * 200 = 20000 次内存，发生了 20000 次异常

Max472

人造人 发表于 2021-9-7 23:43

哦

在访问 a[0][0] 的时候，数据不存在，发生 1 次缺页，系统把 a[0][0] ~ a[0][199] 这 200 个数调入内存

之前看的都是一个数代表一页，比如，第一页，第二页，...
这题是 200 个数代表一页，我之前的想法是一页 200 个数需要调 200 次才能全部调入
但现在是 200 个数都是一页，调入此页就是调入了 200 个数

谢谢