[讨论]二维数组与缺页中断率问题的解决
原帖地址如下：[url=http://bbs.bc-cn.net/thread-189536-1-1]http://bbs.bc-cn.net/thread-189536-1-1[/url]
这个问题我查了相关资料，并得到一些人的指点，现在把相关内容贴下来，大家参考。多多讨论～～～
关于页面调度：
实现虚拟存储器能给用户提供一个容量很大的存储器，但当主存空间已装满而又要装入新页时，必须按一定的算法把已在主存的一些页调出去，这个工作称页面调度。所以，页面调度算法实际上就是用来确定应该淘汰哪页的算法。算法的选择是很重要的，选用了一个不适合的算法，就会出现这样的现象：刚被淘汰的页面又立即要用，因而又要把它调入，而调入不久再被淘汰，淘汰不久再被调入。如此反复，使得整个系统的页面调度非常频繁以至于大部时间都在来回调度上。这种现象叫做“抖动”，又称“颠簸”，一个好的调度算法应减少和避免抖动现象。
为了衡量调度算法的优劣，我们考虑在固定空间的前提下来讨论各种页面调度算法。这一类算法是假定每道作业都给固定数时的主存空间，即每道作业占用的主存块数不允许页面调度算法加以改变。在 这样的假定下，怎样来衡量一个算法的好坏呢？我们先来叙述一个理论算法。假定作业p共计n页，而系统分配给它的主存块只有m块（m,n均为正整数，且１≤m≤n），即最多只能容纳m页。如果作业p在运行中成功的访问次数为s（即所访问的页在主存中）， 不成功的访问次数为F（即缺页中断次数），则总的访问次数Ａ为：
A = S + F
又定义：
f = F / A
则称f为缺页中断率。
影响缺页中断率f的因素有：
分配给作业的主存块数。分配给作业的主存块数多，则缺页中断就低，反之，缺页中断率就高。
页面的大小，如果划分的页面大，则缺页中断就低，否则缺页中断率就高。
页面调度算法。
作业本身的程序编制方法。程序编制的方法不同，对缺页中断的次数有很大影响。
例如：有一个程序要将128×128的数组置初值“0”。现假定分给这个程序的主存块数只有一块，页面的尺寸为每页128个字，数组中的元素每一行存放在一页中，开始时第一页在主存。若程序如下编制：
Var A: array[1..128] of array [1..128] of
integer;
for j := 1 to 128
do for i := 1 to 128
do A[i][j]:=0
则每执行一次Ａ[i][j] :＝０就要产生一次缺页中断，于是总共要产生（128×128－1）次缺页中断。
如果重新编制这个程序如下：
Var A: array[1..128] of
array[1..128] of
integer;
for i := 1 to128
do for j := 1 to 128
do A[i][j] := 0
那么总共只产生（128－1）次缺页中断。
显然，虚拟存储器的效率与程序的局部化程度密切相关。程序的局部化有两种：时间局部化和空间局部化。
时间局部化是指一旦某个位置──数据指令──被访问了，它常常很快又要再次被访问。这可借助于循环、经常用到的变量和也要用到。这可以尽量采用顺序的指令串、线性的数据结构（例如，数组或常用的变量彼此相近放置）来实现。
局部化的程度因程序而异，一般说，总希望编出的程序具有较高的局部化程度。这样，程序执行时可经常集中在几个页面上进行访问，减少缺页中断率。
同样存储容量与缺页中断次数的关系页很大。从原理上说，提供虚拟存储器以后，每个作业只要能分到一块主存储空间就可以执行，从表面上看，这增加了可同时运行的作业个数，但实际上是低效率的。试验表明当主存容量增大到一定程度，缺页中断次数的减少就不明显了。大多数程序都有一个特定点，在这个特定点以后再增加主存容量收效就不大，这个特定点，在这个特定点是随程序而变的，试验分析表明，对每个程序来说，要使其有效的工作，它在主存中的页面数应不低于它的总页面数的一半。所以，如果一个作业总共有n页那么只有当主存至少有n/2块空间时才让它进入主存执行，这样可以使系统获得高效率。
注：以上两个程序段的对应c语言格式为：（以第一个为例）
int A[128][128];
for(j=0;j<128;++j)
for(i=0;i<128;++i)
A[i][j]=0;
关于极光测试的程序段执行时间不同问题：
（以下内容百年不亮提供）
[size=2]
这种小的数据不会引起操作系统页面调度的，数据大了就有可能。编译后汇编代码是一样的。
5: #define n 4
6: int main()
7: {
0040B750 push ebp
0040B751 mov ebp,esp
0040B753 sub esp,8Ch
0040B759 push ebx
0040B75A push esi
0040B75B push edi
0040B75C lea edi,[ebp-8Ch]
0040B762 mov ecx,23h
0040B767 mov eax,0CCCCCCCCh
0040B76C rep stos dword ptr [edi]
8:
9: int a[n][n];
10: int i,j,k=0;
0040B76E mov dword ptr [ebp-4Ch],0
11:
12: //程序段一,以下称A
13: for(i=0;i<n;++i)
0040B775 mov dword ptr [ebp-44h],0
0040B77C jmp main+37h (0040b787)
0040B77E mov eax,dword ptr [ebp-44h]
0040B781 add eax,1
0040B784 mov dword ptr [ebp-44h],eax
0040B787 cmp dword ptr [ebp-44h],4
0040B78B jge main+6Ch (0040b7bc)
14: for(j=0;j<n;++j)
0040B78D mov dword ptr [ebp-48h],0
0040B794 jmp main+4Fh (0040b79f)
0040B796 mov ecx,dword ptr [ebp-48h]
0040B799 add ecx,1
0040B79C mov dword ptr [ebp-48h],ecx
0040B79F cmp dword ptr [ebp-48h],4
0040B7A3 jge main+6Ah (0040b7ba)
15: a[i][j]=k;
0040B7A5 mov edx,dword ptr [ebp-44h]
0040B7A8 shl edx,4
0040B7AB lea eax,[ebp+edx-40h]
0040B7AF mov ecx,dword ptr [ebp-48h]
0040B7B2 mov edx,dword ptr [ebp-4Ch]
0040B7B5 mov dword ptr [eax+ecx*4],edx
0040B7B8 jmp main+46h (0040b796)
0040B7BA jmp main+2Eh (0040b77e)
16: //程序段二,以下称B
17: for(j=0;j<n;++j)
0040B7BC mov dword ptr [ebp-48h],0
0040B7C3 jmp main+7Eh (0040b7ce)
0040B7C5 mov eax,dword ptr [ebp-48h]
0040B7C8 add eax,1
0040B7CB mov dword ptr [ebp-48h],eax
0040B7CE cmp dword ptr [ebp-48h],4
0040B7D2 jge main+0B3h (0040b803)
18: for(i=0;i<n;++i)
0040B7D4 mov dword ptr [ebp-44h],0
0040B7DB jmp main+96h (0040b7e6)
0040B7DD mov ecx,dword ptr [ebp-44h]
0040B7E0 add ecx,1
0040B7E3 mov dword ptr [ebp-44h],ecx
0040B7E6 cmp dword ptr [ebp-44h],4
0040B7EA jge main+0B1h (0040b801)
19: a[i][j]=k;
0040B7EC mov edx,dword ptr [ebp-44h]
0040B7EF shl edx,4
0040B7F2 lea eax,[ebp+edx-40h]
0040B7F6 mov ecx,dword ptr [ebp-48h]
0040B7F9 mov edx,dword ptr [ebp-4Ch]
0040B7FC mov dword ptr [eax+ecx*4],edx
0040B7FF jmp main+8Dh (0040b7dd)
0040B801 jmp main+75h (0040b7c5)
20:
21: return 0;
0040B803 xor eax,eax
22: }
0040B805 pop edi
0040B806 pop esi
0040B807 pop ebx
0040B808 mov esp,ebp
0040B80A pop ebp
0040B80B ret
连续访问和隔几个访问有什么区别？都是从首地址开始计算偏移的，这一句就是访问mov dword ptr [eax+ecx*4],edx；对于一个4列的二维数组访问a[i][j]都是用a+16*i+4*j进行访问的，意思就是访问每一个元素都要计算一次a+16*i+4*j的值，计算这个值之前你是加了i的值还是加j对这句a+16*i+4*j的计算没有影响，所以在没有缺页中断的情况下这两段代码的执行时间是相同的。至于你说的“程序段B的寻址时间显然是A的两倍多”完全没有道理，你是怎么测算出来的？计算程序运行时间的问题你可以问飞燕，她做oj对这个有经验。测试代码时间要将代码连续运行很多次以减小计时误差，还要保证操作系统负载不变，因为现在的系统都是分时的，时间片轮换调度，所以计时的时候要保证程序的占用cpu时间和等待时间不变。我直接回答你的问题吧：
Q:既然汇编代码是一样的那这两个程序段的执行效果也是一样的咯？
A:寻址代码是一样的，但因为访问次序不同，所以不好说执行效果一样。一个是按行访问，一个是按列，比如说对于a[0][1]这个元素，一个是第二个访问，一个是第五个访问，但是两种方式下计算地址a+16*i+4*j都是一样的，访问时间也是一样的。
[size=2]
Q:可即便是这样的程序段不至于引起页面调度，至少寻址是不同的吧？
A:看汇编就知道寻址是相同的。即使你不懂汇编也应该知道a[i][j]的寻址是a+16*i+4*j来计算地址的。行地址a+16*i加行内偏移4*j。
Q:程序段B的寻址时间显然是A的两倍多呀？
A:显然是你的数据不正确，应该是你的测算方法不对。
补充一点，你对比这两段程序：
1：for(i=0;i<n;++i)
2： for(j=0;j<n;++j)
3： a[i][j]=k;
4：for(j=0;j<n;++j)
5： for(i=0;i<n;++i)
6： a[i][j]=k;
执行时间：1和5相同，2和4相同，所以(1,2)的嵌套和（4，5）的嵌套也相同，3和6不用说也相同。从那里可以看出区别？
不知道永远的极光如何来测试这两个程序段？可否把你的代码贴一下～谢过～
[/size][/size]
----------------解决方案--------------------------------------------------------
程序代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#define MAX 100
#define C 10000
int main(void)
{
int i,j,k;
int table[MAX][MAX];
clock_t start, end;
start = clock();
for(k=0;k<C;k++)
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
table[i][j]=0;
end = clock();
printf("%lf\n", (double)(end - start) / CLOCKS_PER_SEC);
start = clock();
for(k=0;k<C;k++)
for(j=0;j<MAX;j++)
for(i=0;i<MAX;i++)
table[i][j]=0;
end = clock();
printf("%lf\n", (double)(end - start) / CLOCKS_PER_SEC);
getch();
return 0;
}
VC6.0运行结果#include <stdlib.h>
#include <time.h>
#include <conio.h>
#define MAX 100
#define C 10000
int main(void)
{
int i,j,k;
int table[MAX][MAX];
clock_t start, end;
start = clock();
for(k=0;k<C;k++)
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
table[i][j]=0;
end = clock();
printf("%lf\n", (double)(end - start) / CLOCKS_PER_SEC);
start = clock();
for(k=0;k<C;k++)
for(j=0;j<MAX;j++)
for(i=0;i<MAX;i++)
table[i][j]=0;
end = clock();
printf("%lf\n", (double)(end - start) / CLOCKS_PER_SEC);
getch();
return 0;
}
1.046000
1.594000
1.594000
----------------解决方案--------------------------------------------------------