2016q3 Homework3 (mergesort-concurrent)
---
# lock-free
## concurrent-II
### atomic_ops_if.h

bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)
type __sync_val_compare_and_swap  (type *ptr, type oldval, type newval, ...)

* pseudocode

{ if (*ptr == oldval) { *ptr = newval; return true; } else { return false; } }
{ if (*ptr == oldval) { *ptr = newval; } return oldval; }

* 這兩個函數提供原子的比較和交換，如果`*ptr == oldval`就將`newval`寫入`*ptr`
* `bool __sync_bool_compare_and_swap`在相等並寫入的情況下返回true
* `type __sync_val_compare_and_swap`返回操作之前的值。

type __sync_fetch_and_add (type *ptr, type value, ...)
type __sync_fetch_and_sub (type *ptr, type value, ...)
type __sync_fetch_and_or (type *ptr, type value, ...)
type __sync_fetch_and_and (type *ptr, type value, ...)
type __sync_fetch_and_xor (type *ptr, type value, ...)
type __sync_fetch_and_nand (type *ptr, type value, ...)

* 返回更新前的值(pseudocode)
`{ tmp = *ptr; *ptr op= value; return tmp; }`
`{ tmp = *ptr; *ptr = ~tmp & value; return tmp; } // nand`

type __sync_add_and_fetch (type *ptr, type value, ...)
type __sync_sub_and_fetch (type *ptr, type value, ...)
type __sync_or_and_fetch (type *ptr, type value, ...)
type __sync_and_and_fetch (type *ptr, type value, ...)
type __sync_xor_and_fetch (type *ptr, type value, ...)
type __sync_nand_and_fetch (type *ptr, type value, ...)

* 返回更新後的值(pseudocode)
`{ *ptr op= value; return *ptr; }`
`{ *ptr = ~*ptr & value; return *ptr; } // nand`

#### `type`可以為`1,2,4,8` `bytes`長度的`int`

int8_t / uint8_t
int16_t / uint16_t
int32_t / uint32_t
int64_t / uint64_t

### 研讀[Linked Lists: Locking, LockFree,and Beyond](http://www.cs.nyu.edu/courses/fall05/G22.2631-001/lists.slides2.pdf)
#### Lock-Free
* Lock-Free ≠ Wait-Free
* Wait-Free 同步
* 每個函式呼叫最終完成
* 每個人都準備存取
* Lock-free 同步
* 一些函數呼叫最終完成
* 下一個邏輯步驟
* 完全消除機鎖
* 僅使用`compareAndSet()`
* 由Maged Michael發明，2003
#### 對照[concurrent-ll](https://github.com/jserv/concurrent-ll)(lockfree)
##### `node_t *list_search(llist_t *the_list, val_t val, node_t **left_node);`
* 為了尋找 `pred` `curr` `succ` 三個`node`
* 程式碼裡頭實作表示為`left_node` `right_node` `right_node->next`
#### `int list_remove(llist_t *the_list, val_t val);`

if (!is_marked_ref(right_succ)) {
    if (CAS_PTR(&(right->next), right_succ,get_marked_ref(right_succ)) == right_succ) {
        FAD_U32(&(the_list->size));
        return 1;
    }

* 將`pre->next`指向`succ` 為邏輯性的刪除，並沒有free(cur)

#### `int list_add(llist_t *the_list, val_t val);`

new_elem->next = right;
if (CAS_PTR(&(left->next), right, new_elem) == right) {
    FAI_U32(&(the_list->size));
    return 1;
}

#### `int list_contains(llist_t *the_list, val_t val);`

## 實作lock-free mergesort-concurrent

參考資料
---
[5.47 Built-in functions for atomic memory access](https://gcc.gnu.org/onlinedocs/gcc-4.4.5/gcc/Atomic-Builtins.html)
[Linked Lists: Locking, LockFree,and Beyond](http://www.cs.nyu.edu/courses/fall05/G22.2631-001/lists.slides2.pdf)
[concurrent-ll](https://github.com/jserv/concurrent-ll)