本系列是 Parallel Programming in C with MPI and OpenMP 這本書的讀書心得！

上篇前情提要：

Multiprocessor 兩種：Centralized Multiprocessor 與 Distributed Multiprocessor

Centralized Multiprocessor ：
直接把Uniprocessor做擴充！
直接把CPU掛到bus上！
不管哪一個CPU處理去連記憶體都一樣快！(有相同的Memory access time)
這種的稱為：
UMA : Uniform memory access multiprocessor
SMP : Symmetrical multiprocessor 對稱型的多處理機

這個架構在處理Cache coherence(快取一致性)的機制為 Write Invalidate Protocol，其運作的內容於上一篇詳細介紹過

Distributed Multiprocessor：

這種架構下，每一個CPU都會分到(Distributed)一塊自己主要在用的Memory (primary memory)
增加Memory頻寬，降低存取Memory的時間
如此的好處是擴充性高！增加CPU不會像UMA架構那樣，直接占用到Bus的頻寬，
而是自己就會分配到一塊主要用的記憶體空間，不會常常需要跟別人共用
這種架構稱為 :
NUMA : non-uniform memory access multiprocessor

本篇要繼續介紹這個架構下的Cache coherence問題所處理的機制：Directory-based Protocol

Directory-based Protocol

首先要來了解一下這個 protocol 用三種狀態來描述Data的狀況

分別用U,S,E 這三個代號來簡稱

Uncached ：data 的狀態目前是閒置的(沒有正在被share)所以可以放心拿去用

Shared：data 的狀態目前是被shared，也就是有其他的CPU把data copy去他的cache裡面使用，此時還是可以把data拿去用！只是要登記一下你也有在用就是了

Exclusive：這是mutual exclusive的意思，表示現在data的狀態正在被修改中，其他人不可以使用！有再用的人請把手邊那份的先丟掉，因為data要被更新了！

制定這三種狀態有什麼用途呢？

讓我們看下去～～

架構圖：

這個架構下

每個CPU都有離自己比較近的Local Memory，也有自己的cache以及一個Directory。

然後有一個變數 X 他目前的值是 7 ，directory裡面放他的狀態是 U 0 0 0

U 表示現在沒人使用，0 0 0 分別記錄了 CPU 0, CPU 1, CPU 2 這三位使用變數X的狀況都是還沒有在用的 0

當 CPU 0 要讀取 X 時，看到狀態是 0 0 0 當中的第一個bit是 0 表示 CPU 0 還沒有在用，所以會Read Miss

於是先把狀態改成 S 1 0 0 ，記錄了目前狀態是 " Shared " ，1 0 0 記錄了目前是 CPU 0 在用它！

然後 CPU 0 才能順利把data 讀出來複製到他自己的cache當中

當 CPU 2 也想要讀取 X 時，看到 1 0 0 的第三個bit是 0 也會Read Miss !

先把第三個bit改成1 -> 從剛剛的 1 0 0 變成 1 0 1 ，然後可以順利讀取到 X

此時，當 CPU 0 想要寫入新的值 6 的時候，看到狀態是 1 0 1 表示除了他自己以外，還有另一個人也在用！

發生 Write Miss !!

這時會先把正在使用 X 的人cache當中的 X 資料清掉!

再把X 的狀態改成 E 1 0 0 ，注意：此時Memory當中的資料還沒更改成新的！

這時如果還有人(CPU 1)要讀取 X 時，首先看到狀態 E 1 0 0 會先Read Miss

因為狀態是 E 1 0 0所以要用之前要先問 CPU 0 來把它改回 S 的狀態

改之前的這個時候，才會把剛剛想要更新的Data 寫回去 Memory當中

再把狀態改成 S 1 1 0 讓 CPU 1 順利拿到 X 的 data 並且確保拿到的是正確的新的資料！

故事說到這邊，可以發現這種機制是採取所謂"被動"的方式來更改(寫回Memory)！

如上例先把 CPU 0 保護措施做好，等有其他人要用的時候，才把要更新資料寫回Memory !