给出如下程序页地址流：2，3，5，2，4，0，1，2，4，6。（1）假设程序的2，3，5页已先后装入主存的

if(x[j]>x[i])

a=x[i]

x[i]=x[j]

x[j]=a

这段加上{}就好了

if(x[j]>x[i])

{

a=x[i]

x[i]=x[j]

x[j]=a

}

Cache及其命中率于块长大小的关系

Cache的命中率H主要与如下几个因素有关：程序在执行过程中的地址流分布情况；当发生Cache块失效时，所采用的替换算法；Cache的容量；在组相联映象方式中，块的大小和分组的数目；所采用的Cache预取算法等。其中，地址流的分布情况是由程序本身决定的，系统设计人员一般无能为力。块替换算法，已经在上一节中已经介绍过。Cache预取算法将在下面的另外一节中专门介绍。以下，对影响Cache命中率的另外几个因素作简单的分析。

1、Cache命中率与容量的关系

Cache的命中率随它的容量的增加而提高，它们之间的关系曲线如图5.34所示。在Cache容量比较小的时候，命中率的提高得非常快，随着Cache容量的增加，命中率提高的速度逐渐降低。当Cache容量增加到无穷大时，命中率可望达到100％，但是，这在实际上是做不到的。 图 5.34 Cache命中率与容量的关系

在一般情况下，图5.34中的关系曲线可以近似地表示为H＝1－S－0.5。因此，当Cache的容量达到一定值之后，再增加Cache容量，命中率的提高很少。

2、Cache命中率与块大小的关系

在采用组相联映象方式的Cache中，当Cache的容量一定时，块的大小对命中率的影响非常敏感。图5.35表示随着Cache块的由小到大的变化，命中率上升和下降的情况。 图 5.35 Cache命中率与块大小的关系

开始时，块大小很小，例如只有一个存储单元，这时的命中率H很低。随着块大小的增加，由于程序的空间局部性起作用，同一块中数据的利用率比较高，因此，Cache的命中率增加。这种增加趋

势在某一个最佳块大小处达到最大值。在这一点以后，命中率随着块大小的增加反而减小。 实际上，当块大小非常大时，进入Cache中的许多数据可能根本用不上。而且，随着块大小的增加，程序时间局部性的作用就会逐渐减弱。最后，当块大小等于整个Cache的容量时，命中率将趋近于零。

3、Cache命中率与组数的关系

当Cache的容量一定时，在采用组相联映象和变换方式的Cache中，分组的数目对于Cache命中率的影响是很明显的。随着组数的增加，Cache的命中率要降低。当组数不太大时，例如，512组以下，命中率的降低相当少，当组数超过一定数量时，命中率的下降非常快。

由于在组相联映象方式中，组间是采用直接映象方式的，只有组内采用全相联映象方式。当分组的数目增加时，主存中的某一块可以映象到Cache中的块数就将减少，从而导致命中率下降

程序存储器指令地址使用程序计数器PC指针，PC中存放的是下一条将要从程序存储器中取出的指令的地址。程序计数器PC变化的轨迹决定程序的流程，PC最基本的工作方式是自动加1。

在执行条件转移或无条件转移指令时，将转移的目的地址送入程序计数器，程序流向发生变化。在执行调用指令或响应中断时，将子程序的入口地址或者中断矢量地址送人PC，程序流向发生变化。

DPTR是一个16位特殊功能寄存器，主要功能是作为片外数据存储器或I／0寻址用的地址寄存器，这时会产生RD或wR控制信号，用于单片机对外扩的数据存储器或I／0的控制。数据指针DPTR也可以作为访问程序存储器时的基址寄存器，此时是寻址程序存储器中的表格、常数等单元，而不是寻址指令。

---