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

Lock-Free

  • Lock-Free ≠ Wait-Free
    • Wait-Free 同步
      • 每個函式呼叫最終完成
      • 每個人都準備存取
    • Lock-free 同步
      • 一些函數呼叫最終完成
  • 下一個邏輯步驟
  • 完全消除機鎖
  • 僅使用compareAndSet()
  • 由Maged Michael發明，2003

對照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
Linked Lists: Locking, LockFree,and Beyond
concurrent-ll

Select a repo