# 2020q1 Homework1 (lab0)
###### tags: `linux2020`
contributed by < `StevenChen8759` >

---
## :one: 開發環境
* 系統版本

$ uname -a
Linux ubuntu 4.15.0-88-generic #88~16.04.1-Ubuntu SMP Wed Feb 12 04:19:15 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

* gcc版本

$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609

## :two: 作業要求
* ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
* 修改排序所用的比較函式，變更為 [natural sort](https://github.com/sourcefrog/natsort)，在 "simulation" 也該做對應的修改，得以反映出 [natural sort](https://github.com/sourcefrog/natsort) 的使用。
* 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2020-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理;
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward: 為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

---

## :three: 實作結果與開發過程記錄

### :camera: queue.h

* 在 *`queue_t`* 中增加指標 **`tail`** ，可在 **`O(1)`** 複雜度下實作 *`insert_tail()`*
* 在 *`queue_t`* 中增加變數 **`size`** ，可在 **`O(1)`** 複雜度下實作 *`q_size()`*
* `queue_t`結構如下所示：

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* Pointer for the tail of the queue */

    int size; /* Record the size of the queue */

} queue_t;

* `list_ele_t` 結構如下所示：

typedef struct ELE {    
    
    char *value;
    struct ELE *next;
} list_ele_t;

### :camera: queue.c
> 初步的實作中，雖測試功能皆正常，但仍有改善空間(如：大量元素操作之效能、程式碼撰寫之改善...等)，稍後章節會有詳述。[color=#a1f542]

#### :camera_with_flash: Function *`q_new()`* 實作

* 配置新的佇列空間時，因該空間的初始值可能不為0，故須設定恰當的初始值(或改用 `calloc()`)。
* 須注意 *`malloc()`* 失敗時，可能會造成 **對空指標 <s>解參考</s> 存取內含值的錯誤(Null Pointer Dereference)** ，故需額外判斷式檢查。

:::danger
傳統中文是優雅的語文，要避免粗暴的翻譯方式，"dereference" 不該逐字翻譯，而要從前後文去推敲用語。
:notes: jserv
:::

* 程式碼實作:

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));

    if (q != NULL) {
        /* Points to NULL initially */
        q->head = NULL;
        q->tail = NULL;
        q->size = 0; /* set size 0 initially */
    }

    return q;
}

#### :camera_with_flash: Function *`q_free()`* 實作
* 在釋放記憶體空間的部分，包含下列元素配置的記憶體空間:
* 佇列中元素的字串
* 串列節點之結構
* 佇列之結構
* 確實釋放所有被配置的記憶體空間，以防止 **記憶體洩漏(Memory Leak)**
* 程式碼實作:

void q_free(queue_t *q)
{
    list_ele_t *ptr;  // Declare operating pointer

    /* check if q is NULL or not */
    if (q != NULL) {
        ptr = q->head;
    } else
        return;

    /* Free list nodes and its string space*/
    while (ptr != NULL) {
        free(ptr->value);
        ptr = ptr->next;
        free(q->head);
        q->head = ptr;
    }

    free(q); /* Free queue structure space */
}

#### :camera_with_flash: Function *`q_insert_head()`* 實作
* 嚴格管制動態宣告的記憶體，以防止 **`記憶體洩漏(Memory Leak)`** 與 **`存取空指標內含值(Null Pointer Dereference)`** 等錯誤。
* 以 **`strncpy()`** 取代 **`strcpy()`** 實作字串複製， ==**以防止緩衝區溢位攻擊(Buffer Overflow Attack)**==。
* 程式碼實作:

bool q_insert_head(queue_t *q, char *s)
{
    /*  Local variable declaration */
    list_ele_t *newh;

    /* Return false while q is NULL */
    if (q == NULL)
        return false;

    /* Allocate the memory space */
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));

    /* Malloc return cases handling (allocate newh) */
    if (newh != NULL) {
        /* Allocate success case */

        /* Allocate the space of string and copy it to that space,
           including end-of-string '\0' set and null allocation check */
        newh->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));

        /* Malloc return cases handling (allocate newh->value) */
        if (newh->value != NULL) {
            /* Allocate success case(newh->value) */

            memset(newh->value, '\0', sizeof(char) * (strlen(s) + 1));
            strncpy(newh->value, s, strlen(s));
        } else {
            /* Allocate fail case(newh->value) */

            free(newh);  // Don't forget to free allocated space(newh) while
                         // failed
                         // allocation
            return false;
        }

        /* Do pointer and parameter edition (queue insert head) */
        newh->next = q->head;
        q->head = newh;
        if (q->tail == NULL)
            q->tail = newh;  // Initialize case
        q->size++;

    } else {
        return false;  // Allocate fail case(newh), return false
    }

    return true;  // All allocation correct, return true
}

#### :camera_with_flash: Function *`q_insert_tail()`* 實作
* 嚴格管制動態宣告的記憶體，以防止 **`記憶體洩漏(Memory Leak)`** 與 **`存取空指標內含值(Null Pointer Dereference)`** 等錯誤。
* 以 **`strncpy()`** 取代 **`strcpy()`** 實作字串複製， ==**以防止緩衝區溢位攻擊(Buffer Overflow Attack)**==。
* 在`tail` 插入元素的指標操作與在 `head` 插入稍有不同。
* 程式碼實作:

bool q_insert_tail(queue_t *q, char *s)
{
    /*  Local variable declaration */
    list_ele_t *newt;

    /* Return false while q is NULL */
    if (q == NULL)
        return false;

    /* Allocate the memory space iff q != null */
    newt = (list_ele_t *) malloc(sizeof(list_ele_t));

    /* Malloc returns cases handling... */
    if (newt != NULL) {
        /* Allocate the space of string and copy it to that space,
           including end-of-string '\0' set and null allocation check */
        newt->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));

        /* Return false while string space allocation failed... */
        if (newt->value != NULL) {
            memset(newt->value, '\0', sizeof(char) * (strlen(s) + 1));
            strncpy(newt->value, s, strlen(s));
        } else {
            free(newt);  // Don't forget to free allocated space while failed
                         // allocation
            return false;
        }

        /* Do pointer and parameter edition (insert tail in queue)*/
        if (q->tail == NULL) {  // Initialize case
            q->head = newt;
        } else {
            q->tail->next = newt;  // Move tail pointer
        }
        q->tail = newt;
        /* Assign newl->next to NULL to avoid illegal memory access.
           (Because malloc() inital value may not be zero!) */
        newt->next = NULL;
        q->size++;

    } else {
        return false;  // Failed to allocated newl, return false
    }

    return true;  // All correct, return true
}

#### :camera_with_flash: Function *`q_remove_head()`* 實作
* 在釋放記憶體空間的部分，包含下列元素配置的記憶體空間:
* 佇列中元素的字串
* 串列節點之結構
* 確實釋放所有被配置的記憶體空間，以防止 **`記憶體洩漏(Memory Leak)`**
* 釋放記憶體空間後，須確實操作串列內之元素，使其指向正確的節點，以避免存取的錯誤記憶體位置造成 **`分段錯誤(Segmentation Fault)`** 。
* 程式碼實作:

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* Declare operating pointer on nodes */
    list_ele_t *ptr;

    /* Reject q is NULL and q->head is NULL cases */
    if (q == NULL || q->head == NULL)
        return false;

    /* Operating Pointer Assignment */
    ptr = q->head;

    /* Copy string to *sp */
    if (sp != NULL) {
        strncpy(sp, ptr->value, bufsize);
    }

    /* Edit pointer and free node space */
    q->head = q->head->next;
    free(ptr->value);
    free(ptr);
    q->size--;
    if (q->size == 0) {
        q->tail = NULL;
    }
    return true;
}

#### :camera_with_flash: Function *`q_size()`* 實作
* 直接取出q->size，以達成 **`O(1)`** 的複雜度。
* 在存取size時，亦須防範傳入的指標值為 `NULL`。
* 程式碼實作：

int q_size(queue_t *q)
{
    if (q != NULL)
        return q->size;
    else
        return 0;
}

#### :camera_with_flash: Function *`q_reverse()`* 實作
* List Reverse的原理圖示
* 在反轉最後一個元素時，須防止空指標之操作，如下圖所示：
* 程式碼實作：

void q_reverse(queue_t *q)
{
    /* Operating pointer declaration */
    list_ele_t *prev, *curr, *nex;

    /* Reject null pointer case */
    if (q == NULL || q->head == NULL)
        return;

    /* Size is 1, return */
    if (q->size == 1)
        return;

    /* Operating pointer initialize */
    curr = q->head;
    nex = q->head->next;
    prev = NULL;

    /* Do list reverse */
    while (curr != NULL) {
        curr->next = prev;
        prev = curr;
        curr = nex;
        /* To Avoid null pointer dereference,
           Add NULL pointer judge for pointer nex */
        if (nex != NULL)
            nex = nex->next;
    }

    /* Re-assign head and tail pointer */
    q->tail = q->head;
    q->head = prev;
}

#### :camera_with_flash: Function *`q_sort()`* 實作
* Merge Sort的原理圖示
* 參考 [npes87184 的 Merge Sort 實作程式碼](https://npes87184.github.io/2015-09-12-linkedListSort/)，並作以下修改：
* 修改結構宣告，支援操作`queue.h`內定義之串列結構。
* 將數值比較的部分修改成字典順序比較，以比較兩個字串的大小。
* 以 **`strncmp()`** 取代 **`strcmp()`** 實作兩字串之字典順序比較， ==**以防止緩衝區溢位攻擊(Buffer Overflow Attack)**==。
* 主程式`q_sort()`實作

void q_sort(queue_t *q)
{
    /* Sort list by [Merge Sort] */
    list_ele_t *ptr;

    /* Reject q is NULL case  */
    if (q == NULL)
        return;

    /* Return directly while queue has only 1 element */
    if (q->size == 1)
        return;

    /* Call Sorting function */
    q->head = mergeSortList(q->head);

    /* Re-assign tail pointer */
    ptr = q->head;
    while (ptr->next != NULL) {
        ptr = ptr->next;
    }
    q->tail = ptr;
}

* `mergeSortList()` 實作

list_ele_t *mergeSortList(list_ele_t *head)
{
    // merge sort
    if (!head || !head->next)
        return head;

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    // split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    // sort each list
    list_ele_t *l1 = mergeSortList(head);
    list_ele_t *l2 = mergeSortList(fast);

    // merge sorted l1 and sorted l2
    return merge(l1, l2);
}

* `merge()` 實作

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    // int cnt = 0;
    size_t len_l1, len_l2;

    // merge with recursive
    if (!l2)
        return l1;
    if (!l1)
        return l2;

    // Fetch string length
    len_l1 = strlen(l1->value);
    len_l2 = strlen(l2->value);

    // Use maximum length
    if (len_l1 < len_l2)
        len_l1 = len_l2;

    if (strncmp(l1->value, l2->value, len_l1) <= 0) {
        // l1 is smaller than or equal to l2
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        // l1 is bigger than l2
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

---

## :four: 程式測試

### :camera: 程式功能測試 - Passed

$ make check
./qtest -v 3 -f traces/trace-eg.cmd
cmd> 
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values.  First at the head
cmd> ih dolphin
q = [dolphin]
cmd> ih bear
q = [bear dolphin]
cmd> ih gerbil
q = [gerbil bear dolphin]
cmd> # Now at the tail
cmd> it meerkat
q = [gerbil bear dolphin meerkat]
cmd> it bear
q = [gerbil bear dolphin meerkat bear]
cmd> # Reverse it
cmd> reverse
q = [bear meerkat dolphin bear gerbil]
cmd> # See how long it is
cmd> size
Queue size = 5
q = [bear meerkat dolphin bear gerbil]
cmd> # Delete queue.  Goes back to a NULL queue.
cmd> free
q = NULL
cmd> # Exit program
cmd> quit
Freeing queue

### :camera: 程式效能評測 - Almost Done
:::danger
"Talk is cheap. Show me the code."
― Linus Torvalds

不用急著說「努力」，有成果再說
:notes: jserv
:::

> 目前測試項目編號第 15 項的排序尚未通過，<s>正在努力優化中</s>(下列記憶體洩漏檢測亦同)。[color=Orange][name=Steven HH Chen][time=Tue, Mar 17, 2020 4:09 PM]

> 更新：經測試已知測資15的失敗原因是Merge Sort不斷地遞迴呼叫，造成 **`堆疊溢位(Stack Overflow)`**[color=Orange][name=Steven HH Chen][time=Wed, Mar 18, 2020 3:01 PM]

$ make test

* 目前traces測資通過情形
<font color=Green> trace-01-ops 6/6 </font>
<font color=Green> trace-02-ops 6/6 </font>
<font color=Green> trace-03-ops 6/6 </font>
<font color=Green> trace-04-ops 6/6 </font>
<font color=Green> trace-05-ops 6/5 </font>
<font color=Green> trace-06-string 6/6 </font>
<font color=Green> trace-07-robust 6/6 </font>
<font color=Green> trace-08-robust 6/6 </font>
<font color=Green> trace-09-robust 6/6 </font>
<font color=Green> trace-10-malloc 6/6 </font>
<font color=Green> trace-11-malloc 6/6 </font>
<font color=Green> trace-12-malloc 6/6 </font>
<font color=Green> trace-13-perf 6/6 </font>
<font color=Green> trace-14-perf 6/6 </font>
<font color=Red> trace-15-perf 0/6 </font>
<font color=Green> trace-16-perf 6/6 </font>
<font color=Green> trace-17-complexity 5/5 </font>
<font color=Charteruse> TOTAL 94/100 </font>

### :camera: 記憶體洩漏檢測 - Almost Done

$ make valgrind

* 目前 traces 測試項目通過情形
<font color=Green> trace-01-ops 6/6 </font>
<font color=Green> trace-02-ops 6/6 </font>
<font color=Green> trace-03-ops 6/6 </font>
<font color=Green> trace-04-ops 6/6 </font>
<font color=Green> trace-05-ops 6/5 </font>
<font color=Green> trace-06-string 6/6 </font>
<font color=Green> trace-07-robust 6/6 </font>
<font color=Green> trace-08-robust 6/6 </font>
<font color=Green> trace-09-robust 6/6 </font>
<font color=Green> trace-10-malloc 6/6 </font>
<font color=Green> trace-11-malloc 6/6 </font>
<font color=Green> trace-12-malloc 6/6 </font>
<font color=Green> trace-13-perf 6/6 </font>
<font color=Green> trace-14-perf 6/6 </font>
<font color=Red> trace-15-perf 0/6 </font>
<font color=Green> trace-16-perf 6/6 </font>
<font color=Green> trace-17-complexity 5/5 </font>
<font color=Charteruse> TOTAL 94/100 </font>

### :camera: 利用自行定義的測試項目來驗證特定功能
> Working hard now...[name=Steven HH Chen][time=Tue, Mar 17, 2020 6:49 PM][color=Orange]

---

## :five: 程式除錯與程式效能改善
:::info
以下說明在上述實作中遇到的議題，以及可以改善的空間。
:::
### :camera: 字串操作的相關議題探討

#### :camera_with_flash: 結尾字元的議題
* 根據[作業說明](https://hackmd.io/JSFDnHn0Rpe0V7d-AqLAXA?view#-%E6%94%B9%E5%AF%AB%E8%87%AA-CMU-%E8%A8%88%E7%AE%97%E6%A9%9F%E6%A6%82%E8%AB%96%E7%9A%84%E4%BD%9C%E6%A5%AD)中之的字串圖示，因字串採ASCII編碼，故在每個字串的結尾皆加入一個結尾字元`\0`，以代表字串之結尾。
* 以下的比較修正了`q_remove_head()`函式中，字串複製時未加入結尾字元 `\0` 造成之錯誤。

$ git diff 53042e 8fb1d6
diff --git a/queue.c b/queue.c
index ad3a2e4..ac7ce2e 100644
--- a/queue.c
+++ b/queue.c
@@ -167,7 +167,8 @@ bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
 
     /* Copy string to *sp */
     if (sp != NULL) {
-        strncpy(sp, ptr->value, bufsize);
+        strncpy(sp, ptr->value, (bufsize - 1));
+        *(sp + bufsize - 1) = '\0';  // Edit end-of-string
     }

#### :camera_with_flash: 減少字串長度計算函式 `strlen()` 的呼叫次數
* 在大量的元素操作情況下，strlen()會經常配合strncpy()計算字串長度而重複呼叫，有可改善的空間。
* 增加變數 `len_s` 以減少strlen()的呼叫次數。
* 以前大一計概老師教C語言時，稱此方法為 `以空間換取時間` 的策略，在記憶體空間受限的狀況下，可再探討此種實作方式是否符合系統需求。
* 改善前與改善後的插入時間比較：
> Working hard now...[name=Steven HH Chen][time=Tue, Mar 17, 2020 6:49 PM][color=Orange]

#### :camera_with_flash: 字串複製函式的效能探討
* 在近期的實現中，發現插入大量元素時，程式可能會超過`qtest` 測試程式的時間限制，進而造成測試失敗。 (測資為`trace-*-perf.cmd`)
* 但有趣的是，在程式重複執行多次後，上述的測資卻又能順利通過，推測是因為快取記憶體的機制，使該程式所用的記憶體空間之存取速度加快而通過指定測資。
> 補充：CPU計算能力亦有影響 (插入元素數: 1,000,000)
> 在Intel Core i5-5200@2.20GHz的PC下執行，時間可能超過1秒。
> 在Intel Core i5-9400@2.80GHz的PC下執行，時間約在0.16秒。
> [name=Steven HH Chen][time=Wed, Mar 18, 2020 10:17 AM][color=YellowGreen]
* 即使如此，<font color=Red>**我們不應抱持僥倖的心態**</font>，應從根本的問題來源加以探討並改善之。
:::danger
不要引用來自 `itread01.com` 的素材，因為內文授權交代不清，我們儘可能找權威 (如 Linux 或 gcc 主要開發者) 的文章，當然可找到強度高的論文更好
:notes: jserv
:::
* <s>參閱 [字串複製函式的效能實測](https://www.itread01.com/content/1547439321.html)一文</s> 以 `strncpy()` 實現的效能較 `snprintf()` 與 `memcpy()` 差，我們由此處開始著手改善。
* 改以`memcpy`實現，並使用 `./traces/*perf*` 測試。結果如下：
* 以三種實現方法，重複插入不同數量的字串`Boeing_747-400`之效能比較圖：
> Working hard now...[name=Steven HH Chen][time=Tue, Mar 17, 2020 6:49 PM][color=Orange]

### :camera: 字串排序的效能議題

#### :camera_with_flash: 測資 `trace-15-perf` 錯誤修正紀錄
* 初步執行`qtest`運行測資`trace-15-perf`，錯誤記錄如下：

$ ./qtest -v 3 -f traces/trace-15-perf.cmd
cmd> # Test performance of insert_tail, size, reverse, and sort
...
cmd> reverse
q = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
Segmentation fault (core dumped)

* 使用 `valgrind` 進行追蹤，發現此錯誤是因 `Merge Sort` 持續地進行遞迴呼叫，而造成 **`堆疊溢位 (Stack Overflow)`**。

make valgrind
...
scripts/driver.py -p /tmp/qtest.AheKgb --valgrind
...
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==6539== Stack overflow in thread #1: can't grow stack to 0xffe801000
==6539== Stack overflow in thread #1: can't grow stack to 0xffe801000
==6539== Can't extend stack to 0xffe8010a8 during signal delivery for thread 1:
==6539==   no stack segment
==6539== 
==6539== Process terminating with default action of signal 11 (SIGSEGV)
==6539==  Access not within mapped region at address 0xFFE8010A8
==6539== Stack overflow in thread #1: can't grow stack to 0xffe801000
==6539==    at 0x404ADD: merge (queue.c:249)
==6539==  If you believe this happened as a result of a stack
==6539==  overflow in your program's main thread (unlikely but
==6539==  possible), you can try to increase the size of the
==6539==  main thread stack using the --main-stacksize= flag.
==6539==  The main thread stack size used in this run was 8388608.
==6539== Stack overflow in thread #1: can't grow stack to 0xffe801000
==6539== 
==6539== Process terminating with default action of signal 11 (SIGSEGV)
==6539==  Access not within mapped region at address 0xFFE801F70
==6539== Stack overflow in thread #1: can't grow stack to 0xffe801000
==6539==    at 0x4A28680: _vgnU_freeres (in /usr/lib/valgrind/vgpreload_core-amd64-linux.so)
==6539==  If you believe this happened as a result of a stack
==6539==  overflow in your program's main thread (unlikely but
==6539==  possible), you can try to increase the size of the
==6539==  main thread stack using the --main-stacksize= flag.
==6539==  The main thread stack size used in this run was 8388608.
...
---	trace-15-perf	0/6
...
---	TOTAL		94/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.AheKgb --valgrind -t <tid>

* 解決方式：將 `Recursive Merge Sort` 改以 `Iterative Merge Sort` 實現，以解決在大量資料操作下造成的 `堆疊溢位 (Stack Overflow)` 問題。

:::danger
中英文以一個半形空白區隔，注意共筆書寫規範
:notes: jserv
:::

#### :camera_with_flash: 排序方法的效能議題
> Working hard now...[name=Steven HH Chen][time=Tue, Mar 17, 2020 6:49 PM][color=Orange]

---
## :six: 背景知識研究
> Working hard now...[name=Steven HH Chen][time=Tue, Mar 17, 2020 6:49 PM][color=Orange]

### :camera: 記憶體相關議題探討

### :camera: 基於simulation模式之時間複雜度量測原理

### :camera: Select系統呼叫的說明與使用

#### :camera_with_flash: 背景知識
* 根據 [man7.org 的說明](http://man7.org/linux/man-pages/man2/select.2.html)，`select()` 系統呼叫允許程式同時監看多個 `file descriptor`，並等待一個或多個 `file descriptor` 對應 I/O 操作的狀態變為 `ready`

#### :camera_with_flash: console.c實作分析

---

## :seven: 結論
* 在實作時，務必要注意動態記憶體的管理，因為 C 語言不像其他語言具有`垃圾回收(Garbage Collection)` 功能。
> 不要隨便提及 C++，現在的 C++ 已經很不同了
> :notes: jserv
* 在實作時，經常會碰到因存取非法記憶體位址造成的`分段錯誤(Segmentation Fault)`。若程式運作在`核心空間(Kernel Space)`(e.g.`Device Driver`)，則此類錯誤可能因此造成系統停擺，使用上須特別小心。