问答题
某计算机采用段页式虚拟存储器，已知虚拟地址为32位，按字编址，每个段最多可以有1K页，每页为16KB，主存容量为64MB，回答以下问题：
问答题
求虚拟存储器容量。
【正确答案】虚拟存储器容量=232B=4GB。
【答案解析】
问答题
给出逻辑地址和物理地址的格式。
【正确答案】每个段最多可以有1KB=210个页，所以逻辑页号为10页。每页为16KB=214B，所以物理地址为14位。虚拟地址的段号=32-10-14=8位。这样，逻辑地址由8位段号、10位页号和14位页内偏移量组成，逻辑地址的示意图如图所示。
[*]
主存容量=64MB=226B，所以物理地址为26位，其中页号为12位，页内偏移量为14位，物理地址的示意图如图所示。
[*]
【答案解析】
问答题
求一个段表空间开销的最大值，该段对应页表的空间开销为多少?
【正确答案】段号8位，段表长度=28行，每行指出页表的起始地址(物理地址26位)和有效位等(即需要27位)，取[*]，所以段表所占空间最大值=28×4B。
页号10位，每段页表长度=210行，每行指出物理页号(12位)和有效位等(即需要13位)，取[*]，页表所占空间最大值=28×210×2B=219B。
【答案解析】
问答题
下面三个函数，以不同的空间局部性程度执行相同的操作。请对这些函数就空间局部性进行排序，并解释是如何得到排序结果的。
#define N 1000
typedef struct{
int vel[3];
int acc[3];
}point;
point p[N];
void clear1(point *p, int n)
{
int i, j;
for(i=0; i＜n; i++){
for(j=0; j＜3; j++)
p[i].vel[j]=0;
for(j=0; j＜3; j++)
p[i].acc[j]=0;
}
}
void clear2(point *p, int n)
{
int i, j;
for(i=0; i＜n; i++){
for(j=0; j＜3; j++)
p[i].vel[j]=0;
p[i].acc[j]=0;
}
}
void clear3(point *p, int n)
{
int i, j;
for(j=0; j＜n; j++){
for(i=0; i＜3; i++)
p[i].vel[j]=0;
for(i=0; i＜3; i++)
p[i].acc[j]=0;
}
}
【正确答案】解决这个问题的关键在于想象出数组是如何在存储器中排列的，然后分析引用模式。函数clear1以步长1的引用模式访问数组，因此明显地具有最好的空间局部性。函数clear2依次扫描N个结构中的每一个，但是在每个结构中，它以步长不为1的模式跳到下列相对于结构起始位置的偏移处(一个int变量所占的空间为4)：0、12、4、16、8、20。所以，clear2的空间局部性比clear1的要差。函数clear3不仅在每个结构中跳来跳去，而且还从结构跳到结构，所以clear3的空间局部性比clear2和clear1都要差。
【答案解析】
问答题
在虚拟分页存储管理的系统中，程序员编写了下面这段代码。
已知A是一个10000000×1000的稀疏矩阵，非零元素个数为8737953个。S是1000×1000的矩阵(二维数组)，所有元素初始化为0。每个页面可以容纳1024个元素。
for(i=0; i＜10000000; i++)
for(j=0; j＜999; j++)
if(A[i][j]!=0)
{
for(k=j+1; k＜1000; k++)
if(A[i，k]!=0) S[j, k]=1;
}
该程序员运行该程序后，发现严重超时，通过代码分析工具得知，A[i][k]!=0耗时异常严重。试解释原因，并写出改进后的代码。
【正确答案】A是稀疏矩阵，但该稀疏矩阵的实现方式没有给出。从代码分析工具的结果，A[i][k]!=0语句耗时严重，可以推断稀疏矩阵很可能没有按行有序存储，导致同一行的元素不在同一页中。
程序员可以重新修改稀疏矩阵的实现，但题目没有给出，无从修改。
还有种简单的改进方式就是在取A[i][k]值的时候，不从稀疏矩阵中取值。改进后的代码如下：
int temp[1000];
for(i=0; i＜10000000; i++)
{
for(j=0; j＜999; j++)
temp[j]=A[i][j];
for(j=0; j＜999; j++)
if(temp[j]!=0)
{
for(k=j+1; k＜1000; k++)
if(temp[k]!=0) S[j, k]=1;
}
}
【答案解析】
问答题
某一个计算机系统采用虚拟页式存储管理方式，当前在处理器上执行的某一个进程的页表见下表，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节编址，每页的大小为1024B。
{{B}}某一进程的页表{{/B}}
|
| 逻辑页号 |
存在位 |
引用位 |
修改位 |
页框号 |
|
| 0 |
1 |
1 |
0 |
4 |
|
| 1 |
1 |
1 |
1 |
3 |
|
| 2 |
0 |
0 |
0 |
— |
|
| 3 |
1 |
0 |
0 |
1 |
|
| 4 |
0 |
0 |
0 |
— |
|
| 5 |
1 |
0 |
1 |
5 |
|
1)将下列逻辑地址转换为物理地址，写出计算过程，对不能计算的说明其原因。
0793，1197，2099，3320，4188，5332
2)假设程序欲访问第2页，页面置换算法为改进的CLOCK算法，请问该淘汰哪页?页表如何修改?上述地址的转换结果是否改变?变成多少?
【正确答案】地址转换过程一般是先将逻辑页号取出，然后查找页表，得到页帧号，将页帧号与页内偏移量相加，即可获得物理地址，若取不到页帧号，那么该页不在内存，于是产生缺页中断，开始请求调页。若内存有足够的物理页面，那么可以再分配一个新的页面。若没有页面了，就必须在现有的页面之中找到一个页，将新的页与之置换，这个页可以是系统中的任意一页，也可以是本进程中的一页；若是系统中的一页，则这种置换方式称为全局置换；若是本进程的页面，则称为局部置换。置换时为尽可能地减少缺页中断次数，可以有多种算法来应用，本题使用的是改进的CLOCK算法，这种算法必须使用页表中的引用位和修改位，由这两位组成4种级别，没被引用和没修改的页面最先淘汰，没引用但修改了的页面其次，然后淘汰引用了但是没修改的页面，最后淘汰既引用又修改的页面，当页面的引用位和修改位相同时，随机淘汰一页。
1)根据题意，每页1024B，地址又是按字节编址，计算逻辑地址的页号和页内偏移量，合成物理地址见表1。
{{B}}表1 合成物理地址{{/B}}
|
| 逻辑地址 |
逻辑页号 |
页内偏移量 |
页帧号 |
物理地址 |
| 0793 |
0 |
793 |
4 |
4889 |
| 1197 |
1 |
173 |
3 |
3245 |
| 2099 |
2 |
51 |
|
缺页中断 |
| 3320 |
3 |
248 |
1 |
1272 |
| 4188 |
4 |
92 |
|
缺页中断 |
| 5332 |
5 |
212 |
5 |
5332 |
2)第2页不在内存，产生缺页中断，根据改进CLOCK算法，第3页为没被引用和没修改的页面，故淘汰。新页面进入，页表修改见表2。
{{B}}表2 页表修改情况{{/B}}
|
| 逻辑页号 |
存在位 |
引用位 |
修改位 |
页帧号 |
|
| 0 |
1 |
1 |
0 |
4 |
|
| 1 |
1 |
1 |
1 |
3 |
|
| 2 |
0→1 |
0→1 |
0 |
—→1 |
调入 |
| 3 |
1→0 |
0 |
0 |
1→— |
淘汰 |
| 4 |
0 |
0 |
0 |
— |
|
| 5 |
1 |
0 |
1 |
5 |
|
因为页面2调入是为了使用，所以页面2的引用位必须改为1。 地址转换见表3。
{{B}}表3 地址转换{{/B}}
|
| 逻辑地址 |
逻辑页号 |
页内偏移量 |
页帧号 |
物理地址 |
| 0793 |
0 |
793 |
4 |
4889 |
| 1197 |
1 |
173 |
3 |
3245 |
| 2099 |
2 |
51 |
1 |
1075 |
| 3320 |
3 |
248 |
— |
缺页中断 |
| 4188 |
4 |
92 |
— |
缺页中断 |
| 5332 |
5 |
212 |
5 |
5332 |
注意：页帧号与页块号是一样的，对应的英文单词是frame，指的是物理页。但页号就不一样了，对应的单词是page，指的是逻辑页。
【答案解析】