2016q3 Homework3(mergesort-concurrent)

# 2016q3 Homework3(mergesort-concurrent) contributed by <`janetwei`> ## 開發環境 `$ lscpu` ``` Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 61 Model name: Intel(R) Core(TM) i5-5250U CPU @ 1.60GHz Stepping: 4 CPU MHz: 826.875 CPU max MHz: 2700.0000 CPU min MHz: 500.0000 BogoMIPS: 3199.68 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 3072K NUMA node0 CPU(s): 0-3 ``` 取得程式碼並測試： ```shell $ (for i in {1..8}; do echo $RANDOM; done) | ./sort 4 8 input unsorted data line-by-line sorted results: [3834] [8984] [14871] [17285] [26343] [28804] [31445] [31581] ``` ## file ### list.h * intptr_t 整數型態的宣告（用在指標）,接受前一個指標傳過來的值,而且並將值回傳比較是否相同 Optional: These typedefs may not be defined in some library implementations.* [source](http://www.cnblogs.com/Anker/p/3438480.html) 數據類型特别是int相關的類型在不同位數機器的平台下長度不同,為了保證平台的通用性，程序中儘量不要使用long类型=>因此推測是為了相容不同平台所使用的 * uint32_t 32位元無符號數據類型為什麼不直接寫unsigned int？為了平台的相容性,unsughed int的寬度不定，直接寫出明確大小定義,將來要轉換平台的時候只要加一些條件編譯式即可。參考資料: [除了功能正確以外](http://novus.pixnet.net/blog/post/31639681) ### list.c * `int list_add(llist_t *list, val_t val)` 插入val到list,原本的程式永遠回傳的都是0,把他改成回傳list的長度=>`return list->size;` * `node_t *list_nth(llist_t *list, uint32_t idx)` 得到list中第idx個node,所以我將名稱改為 `node_t *list_getnode(llist_t *list, uint32_t idx)` 命名籠統因此參考老師給的[java.util.LinkedList](https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html)而將命名改為 `node_t *list_get(llist_t *list, uint32_t idx)` `while (idx--)` 當idx--後大於0,回傳true,反之則回傳false >> `list_getnode` 的命名太籠統又不簡潔，請用更好的命名和程式註解。可參見 Java 的 [java.util.LinkedList](https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html) [name=jserv] >>好的[name=魏孜昀] * 在`static node_t *node_new(val_t val, node_t *next)` 這個function中有使用malloc（）這個system call,卻沒有free,所以加上兩個function `void node_free(node_t *the_node)` `void list_free(llist_t *the_list)` ### threadpool.h * `void (*func)(void *);` pointer to function`void func(void *arg);`,not poiner to this function call * `int task_free(task_t *the_task);` 因為這裡回傳0並沒有什麼意義,所以我改成void不用回傳 `void task_free(task_t *the_task);` 大部份的function都是宣告int,但是沒有回傳0的意義,所以我都改成void ### threadpool.c * `int tqueue_init(tqueue_t *the_queue)` 設定初始條件 `pthread_mutex_init(&(the_queue->mutex),NULL);` `pthread_cond_init(&(the_queue->cond), NULL);` 是pthread內建的初始公式 * `int tqueue_push(tqueue_t *the_queue, task_t *task);` 將一個task插到執行序的第一個,因為回傳值0無意義,因此改成void ### main.c 1.merge_list()這個函式主要將數字由小到大排列 2.merge_sort()這個函式主要將輸入的數字分成兩半 3.merge()這個函式第一個進來的 thread 會檢查 tmp_list 是不是空的，若有則暫存自己的list，如果沒有則malloc() ### 輸入phonebook資料檔 * file.c 因為要輸入phonbook的資料檔,所以要引入file.c來處理資料,因為phonebook-concurrent的function `file_align(char *org, char *mod, int pad);`有錯誤 1.遺漏處理在pad=strlen(rbuf)時的資料 2.若strlen(rbuf)大於wbuf,就會有後方部份資料遺失將程式碼改成 ```C while (fgets(rbuf, sizeof(rbuf), fd0)) { memset(wbuf, '\0', pad); if ((suffix = (pad - strlen(rbuf))) >= 0) { strcpy(wbuf, rbuf); fwrite(wbuf, pad, 1, fd1); } else fwrite(rbuf, sizeof(rbuf), 1, fd1); } ``` * list.h 因為要配合phonebook的使用,因此要將phonebook.opt.h中的宣告加入list.h ```C typedef struct __PHONE_BOOK_ENTRY { char *lastName; struct __PHONE_BOOK_ENTRY *pNext; pdetail dtl; } entry; entry *findName(char lastname[], entry *pHead); ``` 並在node_t加入`entry *pb_entry;` ```C typedef struct node { val_t data; struct node *next; entry *pb_entry; } node_t; ``` * list.c & main.c 因為phonebook中的資料是字串,而mergesort的資料是用數字比對,因此要將字串轉為數字去比對,但是還仍未實作出來 ### 參考資料 [LanKuDot2的共筆](https://hackmd.io/s/S1ezGhIA) [ierosodin的共筆](https://hackmd.io/s/HyXCDd_R) ## 閱讀筆記 ### Modern Microprocessors A 90-Minute Guide! - More Than Just Megahertz Processor performance circa 1997. ``` SPECint95 SPECfp95 195 MHz MIPS R10000 11.0 17.0 400 MHz Alpha 21164 12.3 17.2 300 MHz UltraSPARC 12.1 15.5 300 MHz Pentium II 11.6 8.8 300 MHz PowerPC G3 14.8 11.4 135 MHz POWER2 6.2 17.6 ``` there's more to it than just clock speed – it's all about how much work gets done in each clock cycle. - Pipelining & Instruction-Level Parallelism ![](https://i.imgur.com/jtorHkp.png) ![](https://i.imgur.com/esZDtMD.png) - Deeper Pipelines – Superpipelining - Multiple Issue – Superscalar

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.