2016q3 Homework3 (mergesort-concurrent)

contributed by <ierosodin>

開發環境

作業系統 : CentOS 7

$ lscpu

Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 45
Model name: Genuine Intel® CPU @ 3.30GHz
Stepping: 5
CPU MHz: 1277.976
BogoMIPS: 6600.19
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 15360K
NUMA node0 CPU(s): 0-11

嘗試修改程式碼

list.h

配合phonebook的字典檔與應用, 在list.h中加入

typedef struct __PHONE_BOOK_ENTRY {
    char *lastName;
    struct __PHONE_BOOK_ENTRY *pNext;
    pdetail dtl;
} entry;

並在struct node中加入entry *pb_entry

main()

為了排序sort -R處理過的字典檔, 引入file.c. 利用file_align()將字典檔中的每一筆資料都填滿至MAX_LAST_NAME_SIZE. 再利用list_add()將mmap後的資料一筆一筆加到list中.

list.c

由於merge sort是進行"數字"大小的比較來排序, 所以必須先將字串轉換為數字, 這裡我是利用27進位搭配餘數, 對每一位字元做轉換, 最後產生一個數字來進行排序, 但由於val_t的range限制, 先將MAX_LAST_NAME_SIZE設定為14 (實際能儲存的數字為13, 因為fget()在取資料時, 會將enter('\n')當作一個字元). 轉換方法如下

    val_t key = 0;
    for (int i = 0; i < MAX_LAST_NAME_SIZE - 1; i++) {
        int rem = 0;
        if (map[i] != '\0')
            rem = map[i] - 96;
        else
            ;
        key += rem* pow(26, (MAX_LAST_NAME_SIZE - i - 2));
    }

    node->data = key;

效能分析

execution time : 0.317439 sec
發現最開始的list_add()花費相當多的時間
比較王紹華同學比較字串的方法
在list_add()的部分

可以明顯看出, 將整個字串轉換成一個val_t, 需要付出相當大的成本

但在merge的部分

提早轉換字串可以降低比較時間, 若是實作在phonebook, 將字串轉換為數字也可以直接使用在hash table上

lock free

一個thread pool的方法, 會使用到mutex lock, 而導致程式的執行受到影響, 如threadpool中的push與pop, lock將導致其他thread無法在同時間放入或取得task

解決辦法

<方法一>
建立THREAD_NUM個worker thread, 讓每一個thread都有自己的工作queue, 同時為了達到thread pool的優勢 (不會因為不同thread執行速度不同, 導致資源的浪費), 由main thread進行task的分配.

<方法二>
C11 atomic同步機制

-std=c11

雖然gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-4)支援-std-c11, 但是當要編譯時, 發現似乎沒有提供stdatomic.h

更新GCC

$ yum install centos-release-scl
$ yum install devtoolset-3-gcc
$ scl enable devtoolset-3 bash

CAS

compare & swap, C11實現lock free的方法
atomic_compare_exchange_weak(the_queue, &orig, next);
藉由不斷的compare, 確保給值時, 資料是最新的, 若資料被改動, 則用新的data重新執行工作

實作_Atomic

參考C11 Lock-free Stack解決lstack的mutex lock

Two different threads will never receive the same item when popping. 
No elements will ever be lost if two threads attempt to push at the same time. 
Thread will never block on a lock when accessing the stack

修改skeeto 的lstack為tqueue(LIFO -> FIFO), 並加入threadpool.c中

initialize

int tqueue_init(tqueue_t *the_queue, size_t max_size)
{
    the_queue->head.aba = ATOMIC_VAR_INIT(0);
    the_queue->head.head = ATOMIC_VAR_INIT(NULL);
    the_queue->head.tail = ATOMIC_VAR_INIT(NULL);
    the_queue->size = ATOMIC_VAR_INIT(0);

    /* Pre-allocate all nodes. */
    the_queue->task_buffer = malloc(max_size * sizeof(struct tqueue_task));
    if (the_queue->task_buffer == NULL)
        return ENOMEM;
    for (size_t i = 0; i < max_size - 1; i++)
        the_queue->task_buffer[i].next = the_queue->task_buffer + i + 1;
    the_queue->task_buffer[max_size - 1].next = NULL;
    return 0;
}

task_pop

static struct tqueue_task *pop(_Atomic struct tqueue_head *the_queue)
{
    struct tqueue_head next, orig = atomic_load(the_queue);
    do {
        if (orig.tail == NULL)
            return NULL;
        
        next.aba = orig.aba + 1;
        next.tail = orig.tail->last;
    } while (!atomic_compare_exchange_weak(the_queue, &orig, next));
    return orig.tail;
}

task_push

static void push(_Atomic struct tqueue_head *the_queue, struct tqueue_task *task)
{
    struct tqueue_head next, orig = atomic_load(the_queue);
    task->last = NULL;
    do {
        task->next = orig.head;
        next.aba = orig.aba + 1;
        next.head->last = task;
        next.head = task;
    } while (!atomic_compare_exchange_weak(the_queue, &orig, next));
}

get size

static inline size_t tqueue_size(tqueue_t *the_queue)
{
    return atomic_load(&the_queue->size);
}

編譯時出現問題! compile過了, 但在link時出現

threadpool.c:(.text+0xb2): undefined reference to `__atomic_load'
threadpool.c:(.text+0x129): undefined reference to
`__atomic_compare_exchange'

編譯環境: centos 7, gcc 4.9.2
CFLAG: -std=c11 -Wall -lm -pthread
ierosodin

參考資料

C11 Lock-free Stack
王紹華同學的共筆
atomic cppreference
atomic CAS