2016q3 Homework (phonebook-concurrent)
===
contributed by <`kaizsv`>

## concurrent
[Toward Concurrent](https://hackmd.io/s/H10MXXoT)
### Lock free
根據 [An Introduction to Lock-Free Programming](http://preshing.com/20120612/an-introduction-to-lock-free-programming/)，lock-free可以解釋為，若multi-threads有共用的變數，且threads之間不會互相block，具體可以用`Atomic Read-Modify-Write Operations` `Compare-And-Swap Loops`來實作，而使用`CAS`要注意[ABA problem](https://en.wikipedia.org/wiki/ABA_problem)。

### Function programming
之前有看haskell的資料，覺得這篇很有趣[Functional programming in C](https://lucabolognese.wordpress.com/2013/01/04/functional-programming-in-c/)，雖然我還不能完全理解內容，看起來是用`GLib`及一些`Macro`做的。

補充: [FLOLAC16](http://flolac.iis.sinica.edu.tw/flolac16/)，[haskell tutorial](http://www.codedata.com.tw/social-coding/haskell-tutorial-1-helloworld/)

## phonebook
先放上原本的程式碼
### sysctl and code rewrite
先簡單的把程式碼順序對調一下，讓`#ifndef ... else ... endif`不會出現太多次，之後，老師建議可以用`sysctl`把系統中可用的threads-max找出來，就不用寫死的方式。

查一下資料，這些系統資料都放在`/proc/sys/kernel/`，直接用cat或`sysctl -a | less`可以查看許多核心參數。

我電腦的thread-max是62510，算法是`memory pages num / 4`，用簡單的function就可以取出來。但問題是append時間爆表了，圖片就不放上來了，將近1秒。

#include <sys/sysctl.h>

int get_sysctl_threads_max()
 {
 	int mib[2], threads_max;
 	size_t len;
 	mib[0] = CTL_KERN;
 	mib[1] = KERN_MAX_THREADS;
 	len = sizeof(threads_max);
 	sysctl(mib, 2, &threads_max, &len, NULL, 0);
 	return threads_max;
}

### C coroutine
[Coroutines in C](http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html)
[使用 coroutine 實做 user-level thread](http://blog.linux.org.tw/~jserv/archives/001848.html)
[Duff's device](https://en.wikipedia.org/wiki/Duff%27s_device)
另外還有一些open library，[彥寬](https://hackmd.io/s/BkN1JNQp)的筆記提到，因為要等所有的threads完成，而有些threads可能會比較慢，我的[第一份作業](https://hackmd.io/s/S1h221Ba)是用pthreads加上mutex and condition來確保所有threads完成後才執行下面的事，再研究過上面的資料後，寫了一個簡單的版本。
結果竟然變得更慢，看了那麼久的資料卻做負功，目前的task number是2。

[Simon Tatham](http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html)的作法是用C語言的switch ... case當做goto，再用static變數紀錄目前狀態。

#define cr_start()		   	\
		static int __s = 0;	\
		switch (__s) { 		\
			case 0:

#define cr_yield() 			\
		do { 				\
			__s = __LINE__; \
			return; 		\
			case __LINE__:; \
		} while (0)

#define cr_finish() \
		} 			\
		__s = 0

void task_run(char *p, task_info *task)
{

    cr_start();

    while (1) {
        task->pLast->lastName = p;
        task->pLast->pNext = task->entry_start;
        task->pLast = task->pLast->pNext;
        task->pLast->pNext = NULL;

        task->entry_start++;

        cr_yield();
    }
    cr_finish();
}

## concurrent link-list

###### tags: `assigment_6` `phonebook-concurrent`