# 2021q3 Homework2 (hp)
contributed by < `blue76815` >
###### tags: `linux-summer-2021`
:::warning
注意共筆書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::
[第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-summer-quiz2)
## To Do list
- [x] [Lock-Free 程式設計](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-lockfree)
- [x] [An Introduction to Lock-Free Programming](https://preshing.com/20120612/an-introduction-to-lock-free-programming/)
- [x] [Lock-Free Programming](https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf)
- [x] 閱讀論文 [Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf)
- [ ] 閱讀論文 [A Pragmatic Implementation of Non-Blocking Linked Lists](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf)
## 延伸問題:
- [ ] 解釋上述程式碼運作原理
- [ ] 指出改進空間並著手實作
- [ ] 對比 [rcu_list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu_list)，解釋同為 lock-free 演算法，跟上述 [Hazard pointer](https://en.wikipedia.org/wiki/Hazard_pointer) 手法有何異同？能否指出 [rcu_list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu_list) 實作缺陷並改進？
## 3.解釋上述程式碼運作原理
從主程式開始
```c
#define N_THREADS (64) //NNN
int main(void)
{
list_t *list = list_new();
pthread_t thr[N_THREADS];
//建立執行緒
for (size_t i = 0; i < N_THREADS; i++)
pthread_create(&thr[i], NULL, (i & 1) ? delete_thread : insert_thread,
list);
//分離執行緒
for (size_t i = 0; i < N_THREADS; i++)
pthread_join(thr[i], NULL);
//刪除執行緒
for (size_t i = 0; i < N_ELEMENTS; i++) {
for (size_t j = 0; j < tid_v_base; j++)
list_delete(list, (uintptr_t) &elements[j][i]);
}
list_destroy(list);
fprintf(stderr, "inserts = %zu, deletes = %zu\n", atomic_load(&inserts),
atomic_load(&deletes));
return 0;
}
```
主要介紹在
```c
#define N_THREADS (64) //NNN
for (size_t i = 0; i < N_THREADS; i++)
pthread_create(&thr[i], NULL, (i & 1) ? delete_thread : insert_thread,
list);
```
建立執行緒時，根據 `(i & 1) ? ` 奇偶數分配給
`delete_thread()`和`insert_thread()`函數
因為我們建立 `N_THREADS` (即 `64`) 個執行緒，
所以會有 32 個執行緒執行`delete_thread()`，32 個執行緒執行`insert_thread()`
### 3.2 `delete_thread()` 和 `insert_thread()` 函數
`insert_thread()` :用 list_insert() 插入 N_ELEMENTS(128) 筆資料
`delete_thread()` :用 list_delete() 刪除 N_ELEMENTS(128) 筆資料
```c
#define N_ELEMENTS 128
static void *insert_thread(void *arg)
{
list_t *list = (list_t *) arg;
for (size_t i = 0; i < N_ELEMENTS; i++)
(void) list_insert(list, (uintptr_t) &elements[tid()][i]);
return NULL;
}
bool list_insert(list_t *list, list_key_t key)
{
list_node_t *curr = NULL, *next = NULL;
atomic_uintptr_t *prev = NULL;
list_node_t *node = list_node_new(key);//新增節點(但是結構很特殊 待研究)
while (true) {
if (__list_find(list, &key, &prev, &curr, &next)) {//尋找節點資料然後插入 key 資料
//同時將節點的鄰居關係都更新
list_node_destroy(node);//釋放節點
list_hp_clear(list->hp);//清除 hazard point
return false;
}
// atomic 寫操作
// https://www.ibm.com/docs/en/zos/2.1.0?topic=c11-atomic-store-explicit
atomic_store_explicit(&node->next, (uintptr_t) curr,
memory_order_relaxed);
uintptr_t tmp = get_unmarked(curr);
//執行 atomic 比較和交換操作。
//若 prev 和 tmp 相同 則將 prev 資料儲存到node中
// https://www.ibm.com/docs/en/zos/2.1.0?topic=c11-atomic-compare-exchange-strong
if (atomic_compare_exchange_strong(prev, &tmp, (uintptr_t) node)) {
list_hp_clear(list->hp);//清除所有 hazard point
return true;
}
}
}
```
```c
#define N_ELEMENTS 128
static void *delete_thread(void *arg)
{
list_t *list = (list_t *) arg;
for (size_t i = 0; i < N_ELEMENTS; i++)
(void) list_delete(list, (uintptr_t) &elements[tid()][i]);
return NULL;
}
bool list_delete(list_t *list, list_key_t key)
{
list_node_t *curr, *next;
atomic_uintptr_t *prev;
while (true) {
if (!__list_find(list, &key, &prev, &curr, &next)) {
list_hp_clear(list->hp);
return false;
}
uintptr_t tmp = get_unmarked(next);
//執行 atomic 比較和交換操作。
//若 prev 和 tmp 相同 則將 prev 資料儲存到 get_marked(next) 中
if (!atomic_compare_exchange_strong(&curr->next, &tmp,
get_marked(next)))
continue;
tmp = get_unmarked(curr);
//執行 Atomic 比較和交換操作。
//若 prev 和 tmp 相同 則將 prev 資料儲存到 get_unmarked(next) 中
if (atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next))) {
list_hp_clear(list->hp);//清除所有 hazard point
list_hp_retire(list->hp, get_unmarked(curr)); //DDD
} else {
list_hp_clear(list->hp);//清除所有 hazard point
}
return true;
}
}
```
:::warning
不要將 "atomic" 翻譯為「原子」，因為現代漢語的紊亂
:notes: jserv
:::
### 3.3 `__list_find()`
在
```c
bool list_insert(list_t *list, list_key_t key)
{
.....
while (true) {
if (__list_find(list, &key, &prev, &curr, &next)) {//尋找節點資料然後插入 key
//同時將節點的鄰居關係都更新
..............
}
```
`__list_find(list, &key, &prev, &curr, &next)`
為尋找節點資料然後插入 key 資料
同時將節點的鄰居關係 `&prev` ,`&next` 都更新
對應的程式碼描述在
```c
static bool __list_find(list_t *list,
list_key_t *key,
atomic_uintptr_t **par_prev,
list_node_t **par_curr,
list_node_t **par_next)
{
while (true) {
........
if (get_unmarked_node(next) == next) { //跟資源釋放有關
if (!(get_unmarked_node(curr)->key < *key)) {
//檢查所在的節點 是在相鄰節點位址
*par_curr = curr;
*par_prev = prev;
*par_next = next;
return get_unmarked_node(curr)->key == *key; //FFF
}
prev = &get_unmarked_node(curr)->next;
(void) list_hp_protect_release(list->hp, HP_PREV,
get_unmarked(curr));
}
...............
}
*par_curr = curr;
*par_prev = prev;
*par_next = next;
return false;
}
```
---
## 4.指出改進空間並著手實作
---
## 5.對比 [rcu_list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu_list)，解釋同為 lock-free 演算法，跟上述 [Hazard pointer](https://en.wikipedia.org/wiki/Hazard_pointer) 手法有何異同？能否指出 [rcu_list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu_list) 實作缺陷並改進？
Sign in with Wallet
Connect another wallet