owned this note
owned this note
Published
Linked with GitHub
2016q3 Homework3 (mergesort-concurrent)
===
contributed by <`ruby0109`>
[第20組共筆](https://hackmd.io/MwNg7AHArAhhAsBaYAmeBTR95UwI3QDMVEBjUmATijygEZSIAGOoA===?both)
## Refactoring
* 參考[駝峰式大小寫](https://zh.wikipedia.org/wiki/%E9%A7%9D%E5%B3%B0%E5%BC%8F%E5%A4%A7%E5%B0%8F%E5%AF%AB)-比如將thread_count改成ThrdCount
* 把the_pool 改成pool
* 加入註解更清楚-有些變數和函式應該更清楚的說明
* cut_func
* 裡面的_list和list改寫成Llist和Rlist比較清楚
* left 和right list在註解寫反了
# I have a Mergesort~ I have a phonebook~
* 參考[andy19950同學的共筆](https://hackmd.io/s/rJ6m3IvC)
* 由於Mergesort原本是排序int類型的資料, 考慮到phonebook是輸入lastName, 改為char *
* list.h
typedef intptr_t val_t 改成 typedef char *val_t
typedef struct node {
val_t data;
struct node *next;
} node_t;
改成
typedef struct node {
==char== data[MAX_LAST_NAME_SIZE];
struct node *next;
} node_t;
* 輸入改成phonebook的words.txt檔
```clike=
/* check file opening*/
fp = fopen(InputFile,"r");
if(!fp){
printf("Cannot open the file\n");
return -1;
}
/* Read the File*/
while(fgets(line,MAX_LAST_NAME_SIZE,fp)){
line[strlen(len)-1] = '\0';
list_add(the_list,line);
/* Get the quantity of the data*/
DataCount++;
}
```
* 接下來的問題是, 要如何比較兩個character array的大小呢？
* 參考[How to sort an array of string alphabetically (case sensitive, nonstandard collation)](http://stackoverflow.com/questions/12646734/how-to-sort-an-array-of-string-alphabetically-case-sensitive-nonstandard-colla) 裡面自訂排序或是開頭大小寫的排序方法
* 在phonebook 的lastName 中, 理應開頭都是大寫
* 因此用strcmp比對：
在MergeList(llist_t *a, llist_t *b)中更改
```clike=
/* If a->head->data smaller than or equel to b->head->data, return 1*/
int cmp = (strcmp(a->head->data, b->head->data) <= 0) ;
llist_t *small = (llist_t *)((intptr_t) a * cmp +
(intptr_t) b * (1-cmp));
```
* 最後把結果輸出到一個檔案中
```clike=
void list_print(llist_t *list)
{
node_t *cur = list->head;
FILE *output;
output = fopen("sorted.txt","a");
while (cur) {
fprintf(output, " %s\n", cur->data);
cur = cur->next;
}
fclose(output);
}
```
* 記得程式執行時先
$ uniq words.txt | sort -R > input.txt
之後再用./sort [ThrdCount] [InputFile]
## 均勻分佈亂數與測試
### 均勻分佈亂數
* 參考[How can I shuffle the lines of a text file on the Unix command line or in a shell script?](http://stackoverflow.com/questions/2153882/how-can-i-shuffle-the-lines-of-a-text-file-on-the-unix-command-line-or-in-a-shel)與
::: info
‘-R’
‘--random-sort’
‘--sort=random’
Sort by hashing the input keys and then sorting the hash values. Choose the hash function at random, ensuring that it is free of collisions so that differing keys have differing hash values. This is like a random permutation of the inputs (see shuf invocation), except that keys with the same value sort together.
If multiple random sort fields are specified, the same random hash function is used for all fields. To use different random hash functions for different fields, you can invoke sort more than once.
The choice of hash function is affected by the --random-source option.
:::
* sort -R 是先用Hash functon把內容轉成Hash value再去sort, 所以若有一樣的line就會有不均勻的分佈
* $ uniq words.txt | sort -R > input.txt 中的unique會把一樣的資料合併成一個, 可是在phonebook很可能會有lastName相同可是其他資料不相同的情況, 因此這樣的作法可能會不符合實際的需求。
* shuf 參考[Why does the command shuf file > file leave an empty file, but similar commands do not?](http://unix.stackexchange.com/questions/110490/why-does-the-command-shuf-file-file-leave-an-empty-file-but-similar-commands) 較好, 指令如下：
* cat words.txt | shuf > input.txt
> 不太知道自動測試是測試亂數分佈均不均勻還是程式執行時間？
> [name=雨妏][color=red]
### 正確性測試
* 因為寫的程式是要讓跑出來的檔案跟原本的檔案相同, 所以可以用
$ diff 參數 檔案 檔案
這個linux指令來看兩個檔案是否相同
* 輸入
＄ diff --brief 檔案 檔案
* 一開始會顯示不相同, 不過是因為輸出檔案的字前面有加空格, 去掉之後就會相同
## Monitor 與 boss/worker thread 介紹
* Monitor - 為什麼pthread_cond_wait要unlock mutex
* 參考[Monitor (synchronization)](https://en.wikipedia.org/wiki/Monitor_(synchronization))
* 普通我們用mutex這種thread佔據lock的方式保護critical section(mutual exclusion)
* 可是當threads運作還要考量到不同情況時（比如queue中有沒有task）, mutex會耗費CPU的資源, 因為一直在loop中
* Monitor除了mutex還有condition variable, 讓等待的threads sleep 減少CPU不必要的工作,
condition variable:
* Wait(c,m) c是condition variable ;m是 mutex
1.Atomically
* 釋出mutex lock
* 把threads從c的ready queue移到wait queue
* sleep this thread
2.當signal發生, 會再自動重新拿回mutex lock
* Signal
* 把1個或多個thread從wait queue拿到ready queue
* Broadcast
* 用在a thread waiting for the wrong condition might be woken up and then immediately go back to sleep without waking up a thread waiting for the correct condition that just became true.
* boss/worker model理解
* 參考[Chapter 2 - Designing Threaded Programs](http://maxim.int.ru/bookshelf/PthreadsProgram/htm/r_19.html)
如下圖：
* boss :
* 接收request（程式的input）
* create worker threads
* assigns task 給這些 worker threads
* 需要時會等待worker threads 結束
* Worker thread:
* 等待boss的wake-up sign（運作方式包含剛才的monitor）
* 在一開始就先create 所有thread可以縮短run-time - 如thread pool
* 要減少boss和worker thread的溝通頻率（boss不應該被worker blocked）> 減少owrker間相依性
* 理解Thread Pool
* 可以先參考[C 的 Thread Pool 筆記](http://swind.code-life.info/posts/c-thread-pool.html)中提到的[threadpool-mbrossard](https://github.com/mbrossard/threadpool)程式碼
* 基礎觀念:
* "使用thread pool" 比 "每運作一個task就產生一個thread" 好
* 在 thread pool 中的 thread 從 task queue 中拿一個 task 來執行，執行結束後再去 task queue 中拿另一個 task 來執行( [ Wikipedia](https://en.wikipedia.org/wiki/Thread_pool)原文:The threads in the pool take tasks off the queue, perform them, then return to the queue for their next task.)
* * 程式運作：
先來看wiki 使用thread pool處理Task的圖
再來看程式的struct, 首先threadpool中會紀錄兩個array, 一個是threads另一個是task queue。
```clike
struct threadpool_t {
pthread_mutex_t lock;
pthread_cond_t notify;
pthread_t *threads;//放置所有thread空間的指標
threadpool_task_t *queue;//放置所有task空間的指標
int thread_count;
int queue_size;
int head;
int tail;
int count;
int shutdown;
int started;
};
```
threads的struct是pthread_t;
task queue的struct則是由funciton和argument組成
```clike
typedef struct {
void (*function)(void *);
void *argument;
} threadpool_task_t;
```
再來看執行的流程圖
```flow
st=>start: threadpool_create
決定好thread的數量和task queue的最大值
e=>end: Thread pool destroy
op=>operation: thread開始執行(threadpool_thread)
op2=>operation: thread搶mutex lock
cond=>condition: 某個thread搶到之後
裡面是否有task？
op7=>operation:
op3=>operation: 從task queue拿task之後離開,
unlock
op4=>operation: 下一個thread進來
op5=>operation: pthread_cond_wait 等待threadpool_add的訊號,
同時unlock, 讓其他thread進來一起等待
op6=>operation: threadpool_add pthread_cond_signal新增task,
剛剛搶到lock的thread開始工作
st->op->op2->cond
cond(yes)->op7->op3->op4->e
cond(no)->op5->op6->op3->e
```
## 程式碼理解
以下是我的理解，有錯請指正～
先了解Mergesort的運作方式, 從main.c 的Launch the first task中可以看到包含 cut_func 和我們要排序的list被放入pool給task的queue中。
* cut_func:
* 重複做把list拆解成左右兩個sublist, 再把包含sublist和cut_func的task放到queue中, 很像recursion。
* 直到cut_func運作的條件判斷Llist->size > 1不再成立
* 或是cut_count < max_cut不再成立
* 開始做merge(merge_sort(Llist)) >> 給main thread做
* cut_count < max_cut
* cut_count是data_context.cut_ThrdCount
* max_cut 是thread 的數量或是data 的數量(如果data比thread多, 那就是thread的數量;反之data)
* 理解如下：
thread 會進入if 中 ThrdCount-1次, 之後就是各自再從merge_sort繼續往下切並merge 回來, 以ThrdCount 4 為例, max_cut 是3
```graphviz
digraph hierarchy {
nodesep=1.0 // increases the separation between nodes
node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=Blue, style=dashed] //All the lines look like this
最初的list由Thread1切->{Thread2切 Thread3切}
Thread2切->{thread2繼續切 thread2繼續切2}
Thread3切->{thread3繼續切 thread3繼續切2}
}
```
以35萬筆來說會切18次
* merge_sort : 讓threads 切到list->size < 2再做merge。
>雖然修了進兩學期的課, 可是看程式碼的速度仍然很慢。我發現自己有時候對程式沒有理解就困在一個不知道在做什麼的參數很久。這一次嘗試先從程式的大架構去理解，在慢慢剖析各個參數或是小函式的功用。
* Makefile
* -rdynamic ：看了一些資料可是不太懂
在GCC Manual中
:::info
-rdynamic
Pass the flag -export-dynamic to the ELF linker, on targets that support it. This instructs the linker to add all symbols, not only used ones, to the dynamic symbol table. This option is needed for some uses of dlopen or to allow obtaining backtraces from within a program.
:::
參考[How to get more detailed backtrace [duplicate]](http://stackoverflow.com/questions/5945775/how-to-get-more-detailed-backtrace)才知道原來是obtaining backtraces需要用的。因為沒有很了解bracktrace, 去查資料找到老師的[Who Call Me?](http://blog.linux.org.tw/~jserv/archives/002054.html), 用程式找funciton返回位址和依據返回位址查函式名稱。不過在這裡是為了給GNU Debugger(GDB)做backtrace。
## 管理worker thread與 lock- free實作
以下是在理解程式碼的過程中, 發現可以改善的地方病一步步改善。
### 加上monitor
* 突然發現這個程式雖然有initial cond, 但只有用到mutex, 也就是當沒有task時, thread會一直耗費CPU的資源。 可以照之前老師在phonebook貼的[How to synchronize manager/worker pthreads without a join?](http://stackoverflow.com/questions/12282393/how-to-synchronize-manager-worker-pthreads-without-a-join)來添加monitor
* 參考[threadpool-mbrossard](https://github.com/mbrossard/threadpool)的想法
* task_run 加上pthread_cond_wait
```clike=
static void *task_run(void *data)
{
(void) data;
while (1) {
/* Threads snatch the lock*/
pthread_mutex_lock(&(pool->queue->mutex));
/* If the task queue is empty then unlock,
and let other threads come in to be swapped to the wait queue.
When signal comes, threads wake up and own the lock one by one*/
while( pool->queue->size == 0){
pthread_cond_wait(&(pool->queue->cond), &(pool->queue->mutex));
}
if (pool->queue->size == 0) break;
/* Thread grab the task*/
task_t *_task = tqueue_pop(pool->queue);
/* Unlock */
pthread_mutex_unlock(&(pool->queue->mutex));
if (_task) {
if (!_task->func) {
tqueue_push(pool->queue, _task);
break;
} else {
_task->func(_task->arg);
free(_task);
}
}
}
pthread_exit(NULL);
}
```
* tqueue_push 加上pthread_cond_signal
```clike=
int tqueue_push(tqueue_t *queue, task_t *task)
{
pthread_mutex_lock(&(queue->mutex));
task->prev = NULL;
task->next = queue->tail;
if (queue->tail)
queue->tail->prev = task;
queue->tail = task;
if (queue->size++ == 0)
queue->head = task;
pthread_cond_signal(&(queue->cond));
pthread_mutex_unlock(&(queue->mutex));
return 0;
}
```
* tpool_free
```clike=
int tpool_free(tpool_t *pool)
{
pthread_cond_broadcast(&(pool->queue->cond));
pthread_mutex_unlock(&(pool->queue->mutex));
.
.
.
}
```
* 結果：
發現時間似乎是錯的, 其他人的共筆都是約0.5左右。
回去看程式碼才發現應該要把
clock_gettime(CLOCK_REALTIME, &end);
放在tpool_free(pool);的後面，否則只是紀錄到main thread 的時間而沒有整體的
* 改完之後：
好開心ˊˇˋ
原本threads數越高, 時間就會飆漲, 改完之後就完全不會了!!!
原因應該是因為monitor可以讓threads在wait queue中sleep，所以不會耗費到CPU的時間～
* merge裡面的data_context lock似乎沒有作用
* 刪掉後程式運作正常也正確
* tqueue_size 在這個程式沒有用到也不需要
### Lock-free實作
* 先來了解一下lock-free是什麼, 參考wiki的[Non-blocking algorithm](https://en.wikipedia.org/wiki/Non-blocking_algorithm)與 [An Introduction to Lock-Free Programming](http://preshing.com/20120612/an-introduction-to-lock-free-programming/)
* lock-free利用atomic read-modify-write，如compare and swap (CAS)來省去lock可能產生的等待時間和lock衍生出的問題
* compare-and-swap (CAS)
* 是一個atomic operation
* 比較某個記憶體區塊的內容和一個給予的值是否相同, 如果相同就會把記憶體區塊的內容改成另一個新的值。
* 如果是一些比較弱的結構, 可以不用atomic operation, 比如single-reader single-writer ring buffer FIFO, with a size which evenly divides the overflow of one of the available unsigned integer types, 可以用 memory barrier 做到lock-free。
> 在wiki看到上面這段, 本來想說試試看memory barrier做lock free, 可是找不太到有沒有其他人這樣做的
> [name=Ruby][color=lightblue]
* [lock-freedom](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-freedom)還沒有很能體會
* 參考[concurrent-ll](https://github.com/jserv/concurrent-ll)怎麼作lock-free
* 在linked list concurrent參考[linked list](http://www.slideshare.net/anniyappa/linked-lists-28793865)
* Harris' algorithm, 參考與圖片來源[A Pragmatic Implementation of Non-Blocking Linked-Lists by TL Harris](https://timharris.uk/papers/2001-disc.pdf):
* 原本lock-free用一個CAS來做node deletion可能會發生問題
如上圖所示, 如果想要刪掉10, 可是20也在同時加進去時, 20會遺失, 因為CAS在選擇30之後, 沒有辦法偵測或預防10和30間的變化。
* 解法：
* 在刪掉10的過程用兩個CAS
* 一個CAS 先mark 10 的next指標 ( logically deleted )
* 一個CAS 再刪掉10 ( physically deleted )
* 所以在刪掉10的過程中, 若要加入20, 加入20的過程會偵測到10已經被logically deleted, 因此會對10做physically deleted之後再重新加入。
* 後面的code看不是很懂, 回來先看concurrent-ll怎麼implement
* 在我們mergesort thread pool的實作裡面, task queue是最主要的共享資源, 也是lock free要控制的structure。在控制task queue時因為只有用到add 和delete （tqueue_push和 tqueue_pop）所以參考concurrent-ll會針對list_add和list_remove。
* 發現mergesort-concurrent其實不會有CAS deletion的問題, 因為我們是FIFO, push和pop會在兩端。
* 用單一個 CAS 試試看
* 在concurrent-ll用的CAS是
:::info
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.
The “bool” version returns true if the comparison is successful and newval was written. The “val” version returns the contents of *ptr before the operation.
:::
* 目標：拿掉tqueue_push和tqueue_pop的lock
* 首先思考怎拿掉原本的monitor,
* 原本的task queue架構如下：
* 一開始想了很多種方式, 還不小心不知道在做什麼把linked list改掉了。
* 需要barrier signal thread work
* 我的想法是在task run 那邊設簡單的barrier, 然後在tqueue_push的地方一樣有pthread_cond_signal
```clike=
static void *task_run(void *data)
{
(void) data;
while (1) {
/* Barrier to wait before tasks in queue*/
pthread_mutex_lock(&(pool->queue->mutex));
while( pool->queue->size == 0) {
pthread_cond_wait(&(pool->queue->cond), &(pool->queue->mutex));
}
pthread_mutex_unlock(&(pool->queue->mutex));
```
* 在tqueue_pop中要有判斷queue->size, 因為可能在裡面的時候被改變
* 阿阿...胡思亂想試了好多方法, 後來還是在原本原本的的double linked list加上CAS。只是改了好久好久的code, 可是還是沒有出來QAQQ
```clike=
task_t *tqueue_pop(tqueue_t *queue)
{
task_t *head, *headprev;
while(1) {
head = queue->head;
headprev = head->prev;
if(head){
if( CAS_PTR(&(queue->head),head,headprev) != head) break;
FAD_U32(&(queue->size));
if(headprev) headprev->next = NULL;
} else {
queue->tail=NULL;
}
return head;
}
}
int tqueue_push(tqueue_t *queue, task_t *task)
{
while(1) {
task->prev = NULL;
task->next = queue->tail;
if(CAS_PTR(&(queue->tail),task->next,task) == task->next){
FAI_U32(&(queue->size));
CAS_PTR(&(queue->head),NULL,task);
if(task->next) task->next->prev = task;
pthread_cond_signal(&(queue->cond));
return 0;
}
}
}
```
現在的error如下：
:::warning
==5293== Thread 2:
==5293== Invalid write of size 8
==5293== at 0x4015B3: tqueue_push (threadpool.c:108)
==5293== by 0x401AD1: merge (main.c:94)
==5293== by 0x401C8C: cut_func (main.c:135)
==5293== by 0x401D73: task_run (main.c:163)
==5293== by 0x4E3F183: start_thread (pthread_create.c:312)
==5293== by 0x514F37C: clone (clone.S:111)
==5293== Address 0xc98bc88 is 24 bytes inside a block of size 32 free'd
==5293== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5293== by 0x401D7F: task_run (main.c:164)
==5293== by 0x4E3F183: start_thread (pthread_create.c:312)
==5293== by 0x514F37C: clone (clone.S:111)
==5293==
==5293== Thread 1:
==5293== Invalid read of size 8
==5293== at 0x4015F5: tqueue_free (threadpool.c:119)
==5293== by 0x4017CB: tpool_free (threadpool.c:151)
==5293== by 0x401F40: main (main.c:231)
==5293== Address 0xc98bde0 is 16 bytes inside a block of size 32 free'd
==5293== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5293== by 0x40160B: tqueue_free (threadpool.c:120)
==5293== by 0x4017CB: tpool_free (threadpool.c:151)
==5293== by 0x401F40: main (main.c:231)
==5293==
==5293== Invalid free() / delete / delete[] / realloc()
==5293== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5293== by 0x40160B: tqueue_free (threadpool.c:120)
==5293== by 0x4017CB: tpool_free (threadpool.c:151)
==5293== by 0x401F40: main (main.c:231)
==5293== Address 0xc98bdd0 is 0 bytes inside a block of size 32 free'd
==5293== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5293== by 0x40160B: tqueue_free (threadpool.c:120)
==5293== by 0x4017CB: tpool_free (threadpool.c:151)
==5293== by 0x401F40: main (main.c:231)
==5293==
==5293==
==5293== More than 10000000 total errors detected. I'm not reporting any more.
==5293== Final error counts will be inaccurate. Go fix your program!
==5293== Rerun with --error-limit=no to disable this cutoff. Note
==5293== that errors may occur in your program without prior warning from
==5293== Valgrind, because errors are no longer being displayed.
:::
詢問老師之後, 發現可以參考之前[Toward Concurrency](https://hackmd.io/s/H10MXXoT)中提到的[Hungry Bird](https://github.com/jserv/hungry-birds)lock-free實作的方式
重新改過code之後:
```clike=
task_t *tqueue_pop(tqueue_t *queue)
{
task_t *head;
head = queue->head;
if(head){
/* The situation head equal to tail, which means only one node in queue. */
if(CAS_PTR(&(queue->tail), head, NULL) == head){
/* Check whether the head is still the same*/
if(CAS_PTR(&(queue->head), head, NULL) == head) {
FAD_U32(&(queue->size));
return head;
} else {
return NULL;
}
} else {
if(CAS_PTR(&(queue->head->prev->next), head, NULL)){
CAS_PTR(&(queue->head), head, head->prev);
FAD_U32(&(queue->size));
return head;
}
}
}
return head;
}
```
```clike=
int tqueue_push(tqueue_t *queue, task_t *task)
{
task->prev = NULL;
task->next = queue->tail;
if(CAS_PTR(&(queue->tail), NULL, task) == NULL){
CAS_PTR(&(queue->head),NULL,task);
} else {
CAS_PTR(&(queue->tail->prev), NULL, task);
CAS_PTR(&(queue->tail), task->next, task);
}
FAI_U32(&(queue->size));
pthread_cond_signal(&(queue->cond));
return 0;
}
```
執行的時候有時候會有錯誤, 可是不知道怎麼修改或用什麼工具來看比較好><
跑得時間：
lock free好像沒有快很多
為什麼呢？
* 用mutrace下去看
```
mutrace: Showing 3 most contended mutexes:
Mutex # Locked Changed Cont. tot.Time[ms] avg.Time[ms] max.Time[ms] Flags
0 23 21 2 0.012 0.001 0.002 M!.--.
1 20 9 2 0.004 0.000 0.001 M-.--.
2 7 4 0 0.001 0.000 0.000 M-.--.
||||||
/|||||
Object: M = Mutex, W = RWLock /||||
State: x = dead, ! = inconsistent /|||
Use: R = used in realtime thread /||
Mutex Type: r = RECURSIVE, e = ERRRORCHECK, a = ADAPTIVE /|
Mutex Protocol: i = INHERIT, p = PROTECT /
RWLock Kind: r = PREFER_READER, w = PREFER_WRITER, W = PREFER_WRITER_NONREC
mutrace: Note that the flags column R is only valid in --track-rt mode!
mutrace: Total runtime is 313.921 ms.
mutrace: Results for SMP with 4 processors.
mutrace: WARNING: 40 inconsistent mutex uses detected. Results might not be reliable.
mutrace: Fix your program first!
```
* 不同task queue結構對效能的影響：
* 解法：
* 參考之前的threadpool, 用一個ring來儲存task, 不過這樣要一開始就給一個task queue大小並多加判別有沒有滿的機制
* 以下的處理都參考[threadpool-mbrossard](https://github.com/mbrossard/threadpool)
* 首先改tqueue的想法
* 在pool initialize的時候先給定tqueue的大小
* 考量thread的數目介於1~128間, 我把queue size設256
* tpool_t 中的count名稱容易混淆, 改成thrdCount
* 若要用成一個ring, queue要變成一個array,
* 把tpool和tqueue structure合在一起
* 用array的index(pool->head和pool->tail)來控制ring的head和tail
* structure 改完之後先來看執行時間有沒有什麼變化:
似乎有下降一些些
## 其他學習筆記
* 學習Bash
* 參考[第十章、認識與學習BASH](http://linux.vbird.org/linux_basic/0320bash.php)
* 什麼是shell?
* 透過shell我們可以跟kernel溝通
* shell 有不同版本, 在Linux是Bourne Again SHell (簡稱 bash)
* 我的電腦的shell
::: info
/bin/sh
/bin/dash
/bin/bash
/bin/rbash
:::
* Bash shell功能
* ~/.bash_history 追蹤指令紀錄
* 命令與檔案補全功能
* [Tab] 接在一串指令的第一個字的後面：命令補全
* [Tab] 接在一串指令的第二個字以後時：檔案補齊
* 若安裝 bash-completion 軟體，則在某些指令後面使用 [tab] 按鍵時，可以進行『選項/參數的補齊』功能
* 命令別名設定功能： (alias)
* shell scripts
* 變數
* echo
* $ : PID
ex. $echo $$
可以知道shell的PID
* ？ : 上個指令的回傳值
* env 看環境變數
* set 看自訂變數
* export： 自訂變數轉成環境變數
* 子程序僅會繼承父程序的環境變數， 子程序不會繼承父程序的自訂變數
* 有一些基本觀念後來看[第十二章、學習 Shell Scripts](http://linux.vbird.org/linux_basic/0340bashshell-scripts.php)
* shell script 不適合處理大量資訊, 因為常常去呼叫外部的函式庫, 且使用的 CPU 資源較多，造成主機資源的分配不良。
* Condition Variable 觀念釐清
* [Chapter 4 Programming with Synchronization Objects](https://docs.oracle.com/cd/E19683-01/806-6867/6jfpgdcnd/index.html)
* [Monitor (synchronization)](https://en.wikipedia.org/wiki/Monitor_(synchronization))
* [Condition Variable](https://computing.llnl.gov/tutorials/pthreads/#ConditionVariables)
* [Advantages of using condition variables over mutex](http://stackoverflow.com/questions/4742196/advantages-of-using-condition-variables-over-mutex)
* [Lecture 3, Unit 1: Introduction to condition variables and monitors](https://www.youtube.com/watch?v=xCNhhwVQ4Y8)
* [Using Condition Variables](https://docs.oracle.com/cd/E19455-01/806-5257/6je9h032r/index.html)
:::info
待整理
this classic example shows why it often certainly makes sense to have multiple condition variables using the same mutex. A mutex used by one or more condition variables (one or more monitors) may also be shared with code that does not use condition variables (and which simply acquires/releases it without any wait/signal operations), if those critical sections do not happen to require waiting for a certain condition on the concurrent data.
:::
* Worker
* [Chapter 2 - Designing Threaded Programs](http://maxim.int.ru/bookshelf/PthreadsProgram/htm/r_19.html)
* 其他筆記
* root / user 切換： su - 與exit
* /boot 空間不足：
sudo apt-get purge linux-image-3.5.0-38-generic
## 待做紀錄
* mutrace
* pipeline
* compiler
###### tags: `Course` `Ruby` `2016Autumn` `HW3` `mergesort-concurrent`
Google Drive
Gist
Clipboard
Sign in with Wallet
