quiz4 紅黑樹
對照 hamt, hamt-bench
rbtree 的應用場景: mm, sched (CFS, $3.1)
rb_gen
設計實驗 ==> 檢驗 rbtree 的 locality
規模?
128 op -> 1024 op ->
barrier_cross
是怎麼執行的?看到 barrier_cross
看到 test
的說明,在實際測試時,會交錯進行插入和刪除,因此需要在測試之前進行測試前插入,以確保在刪除時 list 內部有節點可以刪除。
只要 thread 執行完測試前的插入,就會執行 barrier_cross
,並執行 b->crossing++
代表多一個 thread ,直到 b->crossing < b->count
時,就會值行 p_thread_cond_broadcase
將其他 thread 叫起來,代表所有的 thread 都已經做完測試前插入。
這裡我有個問題,就是為什麼在測試前插入時,會需要使用 barrier 來等待所有 thread 的測試前插入都執行完成?
仔細觀察程式碼可以發現,
barrier_init
會以 nthreads + 1
作為參數,並設定 b->count = n
,換句話說在 barrier_cross
的時候會等待 pthread_create
執行的數量再加上 個 thread 才會執行 pthread_cond_broadcast
。
繼續往下看到 main
可以發現
在所有 thread 都創建完後,才會再執行 barrier_cross
這時進入 barrier_cross
數量才會足夠,並把所有的 thread 叫起來開始測試,main
也會在這個時候開始計時。因此,使用 barrier 等待所有 thread 的測試前插入都執行完的原因是,為了能夠讓所有 thread 在同一個時間「起跑」。
然而,如此一來又會產生另外一個問題,因為這些 thread 事實上並不會同時執行,而是由 CPU scheduler 決定當前的資源要分給哪個 thread 執行。
在插入一定的資料到鏈結串列後,會測試 insert 和 delete 以及「某個其他的動作」 (這裡是 top(the_list)
) 的運作效能。
實際運作方式如下:
top(the_list)
list_insert
list_delete
然而,這麼做會有一個問題,因為 insert 和 delete 是交錯進行,會造成能夠測試到的範圍固定的問題。
接下來,我希望能夠設計出一種方法,利用隨機數產生接下來執行的 operation 。
大略想法如下,
設計這樣的方法有一個前題,也就是鏈結串列的容量固定。如果能夠事先估算鏈結串列的容量,則代表在接近容量滿的情況下,會再需要插入資料的可能性較低。
事實上, glibc 的 rand
正是使用此方法來實作,其中,
uintptr_t
是從什麼型態的衍生型態uintptr_t
) 轉型在 try_flag
這個函式中,第 31 行的操作如下:
為何需要在 n 前面加上 (uintptr_t)
,如果不加的話會有什麼問題?
會有 warning ?
好,我們把它拿掉直接編譯看看
這是因為 C 語言中的 bitwise 運算只能給整數型態使用,而 n 不是整數型態,所以會出錯。
我想是為了確保它 insert 時不會讓資料出錯…?
你有看過 並行程式設計: Lock-Free Programming 這篇文章了嗎?
還沒。
沒關係,那我們現在來看:
現在有一個鏈結串列,我要把 10 移走,把 20 插進來,如果先發生 remove 才發生 insert 結果就會出錯:
所以找兩個相鄰節點目的就是找出可能發生這種錯誤的地方?
沒錯,在程式中我們會用 F_FLAG 和 F_MARK 來標出即將被移除的節點和已經被移除的節點。這裡有一件值得注意的事情,看到 list_delete
這個函式,你有在裡面看到任何釋放記憶體的程式碼嗎?
沒有。
對,這個函式真正做的事情只有更新該節點的 flag ,而真正移除節點的操作則是在
Overflow detecting multiply
mmap(2)
If addr is NULL, then the kernel chooses the (page-aligned) address at which to create the mapping; this is the most portable method of creating a new mapping.
為何將
struct page_header
的page_data
改為char *page_data
會引發錯誤 => a.out: test.c:138: test_alloc_small: Assertionresult == TEST_SUCCESS' failed.
fennecJ
是不是和 Flexible array members 有關
在 simple_malloc
我們要回傳記憶體地址給使用者,若將 page_data[]
改為 *page_data
,此時 result->page_data
會是記憶體地址中的值
page_data
為 page_data[]
此時 result->page_data
相當於 &result->page_data[0]
page_data
為 *page_data
此時 result->page_data
相當於 result->page_data[0]
因此把 page_data[]
改為 *page_data
就必須將所有 result->page_data
改為 &result->page_data
才會是我們要的記憶體地址,就能避免上述錯誤,這時會發現在 free
產生錯誤
用 sizeof
去看上面兩個結構體所佔的空間,可以發現 page_data[]
空間並沒有被算進去,所以 void_to_page_header
可以直接減去結構體大小來獲取 page_header
, 也因此當我們將 page_data[]
改為 *page_data
, 就會額外去扣掉 *page_data
所佔的空間,可以在 simple_free_internal
補回多扣掉的空間來解決這個問題
alloc.c 目前的
alloc
實作能否在多執行緒的環境運作?
不行,因為沒有保護
哪些部份需要被保護?
第 15 行之前都是區域變數,不需要保護。mmap 為 MT-Safe
,因此也不需要保護。應該保護的地方為第 23~24 行,也就是更新 page header 資訊的地方。
我仔細思考這一題,我覺得這題不必特別去保護資料就可以在多執行緒運作。
realloc
和 free
以功能來說,在傳入指標相同的狀況下一定不可能在二個以上執行緒運作。因為一旦一個執行緒為先進行 free
,另一個執行緒在傳入相同指標下執行 free
就變成 double-free , realloc
重新配置空間可能會改變指標,故一個執行緒成功,另一個執行緒就會對無效的指標進行 realloc
。故考慮多執行緒的狀況下,應只需要考慮 realloc
和 free
在不同指標的情況下同時執行的狀況。
老師在檢討時提到的 alloc_internal
函式來說,在多執行緒同時執行時,mmap
同時被執行,但回傳的指標應會不同。故下面的幾行指派 struct page_header
裡的 pages
和 page_size
部份應不會造成問題,不需要保護。
不過老師有提到,若加入 free list 來充份利用空間,而不是每此配置只能以 page 為單位來配置空間,維護 free list 就需要特別保護。
yanjiew1
如果為了使用較小的空間而配置一個 page,這樣很浪費資源,我們可以配置一個 page 重複使用這個空間,那你會用什麼較不複雜的資料結構來管理?
雖然使用單向鏈結串列較省空間,但通常會使用雙向 linked list,相較於單向鏈結串列有較快的搜尋速度。
我們需要搜尋 free list 尋找符合請求的空間,所以搜尋複雜度為一個考量點。選擇使用 red-black tree 來管理 free list ,雖然搜尋速度不是最快的,重點是 worst case 的時間複雜度為 O(log n)。
sched_yield
ht_get_list
的作用本次程式碼使用 seperate chaining 的機制 (示意圖如下)以處理 hash table 中發生 collision 的問題, 其中 ht_get_list
的作用如其名稱,將回傳作為 bucket 所使用的 linked list。
Copy 主要可以分為 shallow copy 和與其相對的 deep copy,其中 shallow copy 並不完全 "複製" 出一個物件,而是複製出一個物件的參照 (如: 指標)。 例如 python 中的 copy
作法是創造一個物件並將原物件內含的物件裝入,示意圖如下。
- A shallow copy constructs a new compound object and then (to the
extent possible) inserts the same objects into it that the
original contains.
而 deep copy 相對於 shallow copy,除了複製物件本身之外也會一併複製內含的物件,新物件和就物件可以看成相同屬性的量個獨立個體,示意圖如下。 由於內容物也需要配置記憶體,所消耗資源也比 shallow copy 多上許多。
- A deep copy constructs a new compound object and then, recursively,
inserts copies into it of the objects found in the original.
在 cocurrent 的需求下,物件何時會被哪個執行序進行修改是無法得知的,使用 deep copy 可以避免其他執行序若持有該物件的參照進而在執行過程中產生 dangling pointer。
iterator 在走訪個別元素時,可能會有其他執行緒變更