# 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(R) 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中加入
```C
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'`)當作一個字元). 轉換方法如下
```C
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()`花費相當多的時間
比較[王紹華同學](https://hackmd.io/EzCmBYEMEYGMAYC0BOAZpAbI8BmWkUM9EMATUgDmguACMKBWW2IA)比較字串的方法
在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的分配.
```graphviz
digraph hierarchy {
nodesep=0.2 // increases the separation between nodes
node [color=black,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=black, style=dashed] // All the lines look like this
Main_Thread->Work_Queue1->Worker_Thread_1 Main_Thread->Work_Queue2->Worker_Thread_2 Main_Thread->Work_Queue3->Worker_Thread_3
}
```
<方法二>
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](http://nullprogram.com/blog/2014/09/02/)解決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](https://github.com/skeeto/lstack) 的lstack為tqueue(LIFO -> FIFO), 並加入threadpool.c中
initialize
```clike
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
```clike
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
```clike
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
```clike
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
>> [name=ierosodin]
## 參考資料
[C11 Lock-free Stack](http://nullprogram.com/blog/2014/09/02/)
[王紹華同學的共筆](https://hackmd.io/EzCmBYEMEYGMAYC0BOAZpAbI8BmWkUM9EMATUgDmguACMKBWW2IA)
[atomic cppreference](http://en.cppreference.com/w/c/atomic)
[atomic CAS](http://preshing.com/20150402/you-can-do-any-kind-of-atomic-read-modify-write-operation/)
Sign in with Wallet
Connect another wallet