contributed by <CheHsuan
>
sequeced-before
就是一種對同一個thread下,求值順序關係的描述
happens-before
前一個操作的效果在後一個操作執行之前必須要可見
synchronized-with
就是跨thread版本的happens-before,使用同步來達成
Memory Consistency Models
只要結果正確,實際程式怎樣編譯,怎樣run都沒有關係
Sequential Consistency
1.對於每個獨立的處理單元,執行時都維持程式的順序(Program Order)
2.整個程式以某種順序在所有處理器上執行
在網路上看到用成語來形容concurrency和parallelism,我覺得蠻貼切的
concurency是一心二用,parallelism是一目十行
在單核心CPU機器中,multi-threading無法達到parallelism,而只有concurrency
在多核心CPU機器中,concurrency通常具有parrallel特性
先把沒使用過的用法man一下
mmap()
pthread_setconcurrency()
dprintf()
mmap()是將檔案映射到一個virtual memory address上面,藉由直接對memory address修改的方式提高對檔案IO的效率(減少資料load到緩衝區的overhead)
在mmap()裡面flag這個參數可填入不同的數值,分別有
重要:如果要使用這個方式產生虛擬記憶體空間,一定要搭配MAP_PRIVATE flag,不然mmap()會發出error!
e.g.:
for example 的縮寫是 "e.g.",不是 "ex" jserv
When allocating blocks of memory larger than MMAP_THRESHOLD bytes, the glibc malloc() implementation allocates the memory as a private anonymous mapping using mmap(2). MMAP_THRESHOLD is 128 kB by default, but is adjustable using mallopt(3).
在malloc的manual裏面有提到,當如果要宣告的空間超過default值128kB時,會使用mmap()來取得記憶體空間
雖然code沒有使用到msync(),但是我還是想紀錄一下,當我們使用mmap()將file映射到我們的process的address space裡面時,針對裡面的記憶體位址做修改時,並不會馬上同步回硬碟的檔案上,在msync()的manual裏面有提到Without use of this call there is no guarantee that changes are written back before munmap(2) is called.,也就是說直到呼叫munmap()之前,所做的更改不保證會馬上寫回disk而是只在記憶體的範疇。
而使用msyn()也有三種flags,分別是MS_ASYNC、MS_SYNC和MS_INVALIDATE,其中的MS_ASYNC和MS_SYNC為互斥,MS_ASYNC是說會將更新的要求排到scheduler上,而call完會直接return,而MS_SYNC則是會等到真正完成IO後,才會return,而MS_INVALIDATE則是更新目前在memory的資料,這個flag通常是用在也有其他人或process也在對同一份檔案做IO然後需要同步。
試著將
main.c
的 mmap() 參數變更,從MAP_SHARED
換成MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS
再對照執行時間的變化。注意,因為時間縮短很多,現在 gnuplot 的 Y 軸和測試標的 (也就是我們在意的append
) 也該一併變更。參照之前的 compute-pi 和 clz 的統計方法,計算出append()
時間的分佈 jserv
OKOK!不過發現第一次看完還是不太懂manual的解說QQ,還要再查林哲亘
再來分析程式碼架構。
一開始程式必須先呼叫file_align(),該函式會將原本的words.txt轉換成align.txt,該文字檔裡的格式是lastName加上\n
再補\0
到共16bytes,在程式碼內這邊的時間成本沒有加上去
接下來,要記算出file的大小,這邊應該可以用第一次fgets時所得知的行數來計算出align.txt大小
再來是將檔案(align.txt)memory mapping到記憶體空間裡,這邊使用mmap()
宣告一個可以放所有entry的空間,在這邊吳彥寬同學有提到,malloc是需要成本的,因此這邊用一次malloc()大空間取代多次malloc()小空間
再來就是分配每個thread的任務,完成後開始啟動multi-thread將last name放入到entry裡
最後則是把每個thread的linked list串回來成一條,這邊我覺得可以直接在append()時將指標指到下一個entry,這樣一來,就可以節省合併起來的時間。
這邊應該改成while
提出 bug-fix 時,應該一併列出你的 Git commit (附上網址,一次修正一個問題) jserv
MAP_SHARED
先針對fork下來的專案編譯並跑一次測試,結果如上
MAP_PRIVATE
目前MAP_FIXED和MAP_ANONYMOUS有問題,有assertion
已找出失敗原因
這是很重要的發現,請思考 mmap 在 multi-threaded 環境下,該怎麼設定。設定
MAP_SHARED
之後再觀察,然後記得手冊。交叉閱讀 Linux Device Drivers (2nd Edition) 的 Chapter 13 mmap and DMA jserv
OK,會補在上面林哲亘
在執行時間上,不同的mapping flag對執行時間好像沒有太大的影響,考量到我們針對此份檔案並沒有做寫入的行為,也沒有其他的process也在修改這份檔案,讓kernel需要做同步,因此執行時間上並沒有顯著的差異
如何證明你說「執行時間上並沒有顯著的差異」這句話?已經實驗多個檔案透過 mmap 存取了嗎?不要憑感覺說話 jserv
老師我不太懂您的意思耶,是指用更多不同的檔案然後用mmap去實驗,還是說不同類型的檔案,那有沒有要加入其他process去存取,要有write行為嘛?
這是用time指令去取出sys時間,並各跑100次的實驗結果,我會想做這個實驗的考量是說,如果MAP_SHARED和MAP_PRIVATE如果會有顯著差異的話,那最主要應該是在kernel space執行時間的差別(因為記憶體的資料要和檔案做sync)。不過看起來還是大致落在同一個範圍內。
(因為time指令是針對一個執行檔,所以量測的sys時間是還會包含append以外的操作)
移除append後的merge
很神奇的,findname時間大概減少了40%的時間,我根本沒有改findname的方法