今天OS課上老師提到影響缺頁次數的因素中有一個是 程序的局部性越好，越不容易缺頁，并舉了個關于雙重for循環順序的選擇問題作為例子。
我回去也查詢資料研究了一下這個問題。

何為程序的局部性(locality)

程序的局部性原理是指程序在執行時呈現出局部性規律，即在一段時間內，整個程序的執行僅限于程序中的某一部分。相應地，執行所訪問的存儲空間也局限于某個內存區域。也就是說，程序傾向于引用鄰近于其他最近引用過得數據項，或者最近引用過的數據項本身。我的理解就是：通過利用“緩存”來提高程序運行效率

程序的局部性又通常有兩種不同的形式：時間局部性(temporal locality)和空間局部性(spatial locality).

時間局部性：被引用過一次的存儲器位置在未來會被多次引用

空間局部性：如果一個存儲器的位置被引用，那么將來他附近的位置也會被引用。也就是說靠近當前正在被訪問內存的內存內容很快也會被訪問。

理論分析

先以一維數組為例，考慮對程序數據引用的局部性。

借用《深入理解計算機系統》書中的例子進行分析

sumvec函數中數組v的元素是被順序讀取的，一個接一個，按照它們存儲在存儲器中的順序。(假設地址從0開始).因此對于變量V，函數有很好的空間的局部性。因此這個函數有良好的局部性。

向上面例子中按順序、連續的對v的引用，稱為步長為1的引用模式（相對于元素大小）。同理，在一個連續的向量中，每隔k個元素對向量進行訪問，稱為步長為k的引用。一般來說，隨著步長的增加，空間局部性會下降。

再考慮二維數組

圖中函數是對一個二維數組求和(M=2,N=3)。雙重嵌套循環按照行優先的順序讀取數組的元素。因此函數具有良好的空間局部性，因為它按照數組被存儲的行優先順序來訪問這個數組，因此得到的是一個步長為1的引用模式和良好的空間局部性。從而使得程序運行效率得到提高。

但我們更換讀取順序的時候，交換i和j的循環。如下圖所示

這時候發生了巨大的變化！函數的空間局部性變得很差，因為他按照列順序來掃描數組，而不是按照行順序。因為C數組在存儲器中是按照行順序的，結果這里就得到的是步長為N的引用模式。從而使得程序效率降低。

代碼實例測試

實例

#include <stdio.h> #include <stdlib.h> #include <time.h> int main() {int a[500][500];int i,j;clock_t start, finish;double duration;start = clock();for (int k = 0; k < 1000; k++)//循環放大時間{for(i=0; i<500; i++){for(j=0; j<500; j++){a[i][j]=i;}}}finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%f seconds\n", duration );start = clock();for (int k = 0; k < 1000; k++)//循環放大時間{for(j=0; j<500; j++){for(i=0; i<500; i++){a[i][j]=i;}}}finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%f seconds\n", duration) ;return 0; }

運行結果1

可以發現當行列數相同的時候，按照行順序掃面的效率要高一些。也符合之前的理論分析.

運行結果2

當我把數組定義改為a[10][10000]的時候，測試結果如下，依舊為行順序掃描效率較高。

運行結果3

數組改為a[10000][10]后，測試結果如下，依舊為行順序掃描效率較高。

小結

通過對雙重循環不同循環順序的效率分析，初步理解了局部性原理。也就是說現代的計算機體系的存儲技術至少都用了局部存儲思想，即CPU提取內存的一個位置的數據放到cache中的同時，也會把其附近的數據也提取到cache中，如果內存以行優先存儲方式（注意這個前提！），則提取Array[0][0]位置的數據的同時，則也會順便把"Array[0][1], Array[0][2],tArray[0][3], Array[0][4]..."等數據提取出來存放在緩存中。這樣在后邊連續的幾次循環中均可以命中緩存，從而減少緩存失效，提高程序的運行效率。

參考資料

維基百科

計算機體系結構與程序性能

《深入理解計算機系統》

轉載于:https://www.cnblogs.com/glczero/p/4478274.html

總結

以上是生活随笔為你收集整理的程序局部性原理的一些思考的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。