原帖地址如下：
[url=http://bbs.]http://bbs.[/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运行结果