如何理解計算機操作系統中的局部性原理？

01-06

局部性原理: CPU訪問存儲器時，無論是存取指令還是存取數據，所訪問的存儲單元都趨於聚集在一個較小的連續區域中。
這是教科書中的定義，本人第一次看，僅能從字面來理解，更深層次的理解不了，比如問一個計算機專業的同學，他說局部性原理在一定程度上解釋了緩存的存在。我就理解不了，故請知乎上的達人們說說對局部性原理的理解，萬分感謝~

試著談談自己的理解，前幾天才看完CSAPP的有關章節，很可能說得很膚淺或者謬誤

先拋開這個，談談緩存。

我們先將計算機分為數個層次：

寄存器 64位

一級緩存L1 4×64KB

二級緩存L2 4×256KB

三級緩存L3 8MB

內存 4GB

磁碟 1TB

可以看到這些層次一個比一個更大。

寄存器，既是CPU的工作台，是存放計算數據的地方

CPU要工作了，它需要數據或者地址，從哪裡來？先從一級緩存裡面找，找不到就從二級緩存裡面找，依次類推。假如CPU到磁碟才有，那麼這個數據就會存入內存，再存入三級緩存、二級緩存、一級緩存，最後存入寄存器，CPU用它來計算了。

所以說，可以這麼看， L1是寄存器的緩存，L2是L1的緩存，依次這樣下去，下面一層是上面一層的緩存。

現在來講局部性原理

CPU的工作要高速，我們希望CPU需要的數據更多的就在L1裡面，一找就找著。不希望更多的跑到下面內存乃至磁碟裡面去找，這樣會花更多的時間。所以當CPU用了一個數據，計算機會遇見性的存入其他等會兒CPU可能會用到的數據到L123內存，用到的可能性越大，就能存到越接近寄存器的層次。這也才是緩存的真正意義。那麼，計算機怎樣才能判斷一個數據接下來可能被用到？

時間局部性：如果一個信息項正在被訪問，那麼在近期它很可能還會被再次訪問。

這當然是正確的，用過的數據當然可能再次被用到。

空間局部性：在最近的將來將用到的信息很可能與現在正在使用的信息在空間地址上是臨近的。

正在使用的這個數據地址旁邊的數據，當然也是很可能被用到的。比如數組什麼的

樓上已經有答主解釋的很清楚了。我添一點。

首先要明白局部性原理能解決的是什麼問題，也就是主存容量遠遠比緩存大，CPU執行程序的時候需要使用內存塊，如果該內存塊在緩存上，那麼處理器直接從緩存上取該內存塊就行了，因為緩存的數據傳輸的速率比內存快的多。因為主存容量大，所以要取的內存塊很可能不在緩存上，因此就要把這個內存塊移到緩存上。局部性原理就是解決這個問題：

時間局部性：程序有在一段時間內多次訪問同一個數據塊的傾向，這個寫程序的都知道；

空間局部性：程序往往有訪問一個聚集空間的數據塊的傾向，參見數組的訪問；

演算法局部性：當程序反覆訪問分布在整個內存空間的數據塊時，就只能看演算法局部性。這個很難理解。我的理解是：一般人寫的程序還是以順序和分支執行的為多，一般很少有break、continue和goto指令，演算法局部性強調的是程序執行的時候訪問數據塊一般是順序訪問或者隔一個空間地按序訪問，出現訪問到這個內存塊又跑到隔老遠的一個內存塊又訪問另一個不相關的數據塊的概率是非常低的（我只是打個比方。）。當然局部性的演算法還是很多的，水也比較深。只是我一點淺薄的認識。【謝謝大家】

那麼局部性原理如何解決內存讀取到緩存上這個問題呢？

舉個例子：空間局部性，我們就可以選擇在讀取內存塊的時候將該內存塊附近的內存塊也讀進緩存中。稱為預取（prefetch）

程序局部性原理：是指程序在執行時呈現出局部性規律，即在一段時間內，整個程序的執行僅限於程序中的某一部分。相應地，執行所訪問的存儲空間也局限於某個內存區域，具體來說，局部性通常有兩種形式：時間局部性和空間局部性。

時間局部性：被引用過一次的存儲器位置在未來會被多次引用（通常在循環中）。

空間局部性：如果一個存儲器的位置被引用，那麼將來他附近的位置也會被引用。

微信公眾號碼農有道的兩篇文章是講解的很好的

《程序局部性原理介紹》

《從緩存來看局部性提高程序運行效率的原因》

StackOverflow上cpp話題的最高贊問題問的就是這個局部性原理存在的的結果

Why is it faster to process a sorted array than an unsorted array?

據說是經驗的總結，要完全理解它，需要很深的計算機體系架構的功力和編程知識！關注下，我也不是很懂。但計算機緩存的存在並不完全是因為局部性原理。事實上，硬碟上存在高速緩存要比較容易理解，因為很容易想到最近被訪問的內容再次被訪問的概率是非常大的，也很有信心保證我們理解的是正確的。但在CPU上也有高速緩存，因為粒度非常之小，所有很難明白究竟是怎麼一回事，究其原因是因為我們很難弄清其來龍去脈，看來有些高深的知識是很難科普的......