2016q3 Homework2 (phonebook-concurrent)

contributed by <f5120125>

tags: `sysprog`

開發環境

Ubuntu 14.04 LTS

CPU: Intel® Core™ i5 CPU 650 @ 3.20GHz × 4
Mem: 8 GiB
Cache:
L1d cache: 32 KB
L1i cache: 32 KB
L2 cache: 256 KB
L3 cache: 4096 KB

Concurrency

Concurrency(並行性) 不為 Parallelism (平行性) [1][2][3]
- 實作threads主要是為了達到Concurrency：
  再一條時間軸上, threads間有所重疊, 因此藉由共享code section, data section, task上能夠運用的資源達到有效利用CPU, 達到vitual paralellism
- 實作processes主要是為了達到Parallelism：
  再同一時間, 有多個tasks需處理，利用多個CPU去處理達到平行化
Sequenced Before
- threads間執行順序的不確定性, 得需知道求值順序
Happens-Before
- 前一個操作的效果在後一個操作執行之前必須要visible
- 只關注是否看起來有這樣的效果，從外界看起來，就像是先執行某一行A，再執行其接著的下一行B
- 關鍵在於只要A的效果在B執行之前，對於B可見就可以了，實際上怎麼執行的並不需要深究

案例分析 Phonebook-concurrent

此程式延續之前作業, 修改為thread版本來提升效能

Preliminaries

Macro 的使用
- #if...#else...#endif
- #ifdef MACRO_NAME...#endif, #ifndef MACRO_NAME...#endif
- #if defined( MACRO_NAME )...#endif
- #include IMPL
Thread management
- pthread_create()
- pthread_join()
- pthread_exit()
Map file into memory
- mmap()
- munmap()
File alignment

1. Macro 的使用

在phonebook_opt.h中定義了一個macro： OPT , 主要功能是拿來判斷main.c 中哪裡是原來版本或是執行緒版本該執行的

example



#if OPT
/*do sommthing*/
#endif



#ifdef OPT
/*do something*/
#endif



#if defined(OPT) && OPT
/*do something*/
#endif

2. Thread management

pthread_create()


int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                   void *(*start_routine)(void *), void *arg);

◆第一個參數

unique Thread ID

◆第二個參數

用於指定不同 thread的attributes, 通常為傳入NULL, 代表是default attribute

◆第三個參數

void * 為 generic pointer, 主要功用
- 儲存任何型態的address
- typecast成任何型態












void *somePtr;
int *integerPtr = 10;
int *anotherIntPtr;

somePtr = &integerPtr;/*儲存int型態的address*/

//error occur !!
printf("%d\n", (int)(*somPtr));/*不能使用`*`去存取值*/

anotherIntPtr = (int*)somePtr;/*typecast成(int*)型態*/
printf("%d\n", *anotherIntPtr);

(*start_routine) 為 function pointer, 其所能傳入的參數型態為 void *

◆第四個參數

start_routine要用到的參數, 若是start_routine有許多參數, 可以傳入一個structure

pthread_join()


int pthread_join(pthread_t thread, void **retval);

◆第一個參數

unique Thread ID

◆第二個參數

用於

pthread_exit()

3. Map file into memory

MMAP

SYNOPSIS


#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

mmap() 將檔案映射到一個 virtual memory address 上面，藉由直接對 memory address 修改的方式不用經過buffer，減少資料load到緩衝區的overhead，快速的記憶體存取可以提高對檔案 IO 的效率

Blocking VS Non-blocking I/O

Blocking I/O
允許 sleep/awaken 動作的 process，基本動作：
- 當 process 進行 read 動作但是資料尚未就緒時，process 必須被 block 住 (sleep)，而當有資料進來時就需要立即被喚醒 (awaken)，就算資料仍不完整也是
- 當 process 進行 write 動作但是 buffer 沒有空間時，process 也必須被 block 住，而且必須被放到跟 read 動作不同的 wait queue 中去等待 wake-up (buffer 騰出空間寫入)
Non-blocking I/O
- 讀不到資料或寫不進 buffer 時，他會送出 retry 的動作，再試一次

參考觀念

記憶體映射函數 mmap 的使用方法

addr : 要 map 到的記憶體位置
- 如果 addr 為 NULL，kernel 將在建立的 mapping 地址中自行選擇，這是建立新的 mapping 最簡單的方法。
- 如果 addr 不是NULL，mapping 會在附近的 page boundary 建立，並將新 mapping 地址傳回。
length: 要 mapping 的長度，它會從 fd + offset 的位置開始 mapping 檔案。
prot: 要保護的記憶體保護 mapping
不能跟 open mode 衝突
- PROT_EXEC 可能執行
- PROT_READ 可能讀取
- PROT_WRITE 可能寫入
- PROT_NONE 可能不能存取
flags: 選擇 map file 能不能被其他程式看到
- MAP_SHARED 分享此 mapping
- MAP_PRIVATE 建立一個私有 copy-on-write mapping
fd: 用系統函式 open 打開的檔案位置，open mode 可以選擇檔案的讀寫屬性，不能跟 prot 有衝突。
offset: 從檔案的哪裡開始 mapping，offset 必須是 page size 的倍數，可以用 sysconf(_SC_PAGE_SIZE) 取得。

munmap

munmap() 用來取消參數 start 所指的映射記憶體起始地址，參數 length 則是欲取消的記憶體大小。當行程結束或利用 exec 相關函數來執行其他程式時，映射記憶體會自動解除，但關閉對應的文件描述詞時不會解除映射。

C語言munmap()函數：解除内存映射

4. File alignment

5. 檢查aligned file是否和原輸入一樣

check.c











































#include <stdio.h>
#include <sys/stat.h>//stat, stat(paath, struct stat)
#include <sys/mman.h>//mmap()
#include <fcntl.h>//open(file_name, )
#include <stdbool.h>

#define MAX 16
#define ORIG_FILE_PATH "./dictionary/words.txt"
#define ALIGNMENT_FILE "align.txt"

off_t getFileSize( char *path);

int main(){
	bool consistency=true;
	char orig_buff[MAX];
	char align_buff[MAX];
	FILE *orig_fp = fopen(ORIG_FILE_PATH, "r");
	FILE *align_fp = fopen(ALIGNMENT_FILE, "r");

	int fd = open(ALIGNMENT_FILE, O_RDONLY | O_NONBLOCK);
	off_t new_file_size = getFileSize(ALIGNMENT_FILE);
	char *map = mmap(NULL, new_file_size, PROT_READ, MAP_SHARED, fd, 0);
	char *tmp=map;

	while( fgets(orig_buff, sizeof(orig_buff), orig_fp) ){
		if( strncmp(orig_buff, tmp, sizeof(orig_buff)) != 0){
			consistency=false;
			break;
		}
		tmp+=MAX;
	}
	if(consistency)
		printf("Files are consistent\n");
	else
		printf("Files are not the same\n");
	return 0;
}

off_t getFileSize( char *path){
	struct stat file_stat;
	stat(path, &file_stat);
	return file_stat.st_size;
}

執行結果

檢查完aligned file和原本words.txt檔後, 確認檔案一樣

 Performance counter stats for './phonebook_opt' (100 runs):

           841,854      cache-misses              #   66.507 % of all cache refs      ( +-  1.05% )
         1,265,807      cache-references                                              ( +-  0.65% )
       172,850,372      instructions              #    0.76  insns per cycle          ( +-  0.07% )
       226,345,721      cycles                                                        ( +-  0.88% )

       0.090487839 seconds time elapsed                                          ( +-  2.76% )

cc -Wall -std=gnu99 calculate.c -o calculate
./calculate
hua@hua-ubuntu:~/Desktop/sysprog-class/homework2/phonebook-concurrent$ ./check 
Files are consistent

Code Refactoring

整理程式碼
- 變重新命名
- 整理Macro
程式的改進
- findName()的改進

original

下列程式碼為append完後, 將threads間的linked-list合併在一起
- 改進方向可以考慮對每個thread做findName()










    entry *etmp;
    pHead = pHead->pNext;
    for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = argsPtr[i]->entryHead->pNext;
        } else {
            etmp->pNext = argsPtr[i]->entryHead->pNext;
        }
        etmp = argsPtr[i]->entryTail;
    }

原本程式執行結果

image alt

合併pthread_create()和pthread_join()的分析

執行結果

create 和 join合併到同一個for loop

threaded_findName()

執行結果

image alt

Thread Pool

參考觀念

Thread 缺陷
- 建立太多執行緒，會浪費一定資源，並且有些執行緒未被充份使用
- 銷毀太多執行緒，會導致之後浪費時間再次創建它們
- 建立執行緒太慢，導致效能變差
- 銷毀執行緒太慢，導致其它執行緒沒有資源
Thread Pool 功能
- 管控 Thread 的產生與回收
- 分發 Thread 處理 request
- 處理 request 的 queue

C 的 Thread Pool 筆記
 github source code














typedef struct {
    void (*function)(void *);
    void *argument;
} threadpool_task_t;
//Thread Pool 需要 job/task 讓 Thread 知道他們要做什麼事情

threadpool_t *threadpool_create(int thread_count, int queue_size, int flags);
//傳入 thread 的數量，queue 的大小，回傳 threadpool 型態是 threadpool_t

int threadpool_add(threadpool_t *pool, void (*routine)(void *), void *arg, int flags);	
//傳入 threadpool，要執行的 function 位置，要傳入的參數

int threadpool_destroy(threadpool_t *pool, int flags);
//傳入 threadpool，會把 threadpool 的空間 free 掉

Lock-free Thread Pool

Thread Pool VS Lock-Free Thread Pool

Thread Pool

共享 workqueue 的操作必須在 mutex 的保護下安全進行。
Lock-Free Thread
- 解決 lock 機制：
  解決 lock-free 必須避免共享資源的競爭，因此將共享 workqueue 拆分成每個 worker thread 一個 workqueue。
  對於 main thread 放入工作和 worker thread 取出任務的競爭問題，可以採取 ring-buffer 的方式避免。
- condition variable 問題：
  condition variable 解決執行緒之間的通訊。
  semaphore 作為一種通信方式，可以代替之。

高效線程池之無鎖化實現

















void *tpool_init(int num_threads)
//初始化時決定要用哪種方式進行 put work，選用 `ring-buffer` 的方式將 worker 加入queue

static int wait_for_thread_registration(int num_expected)
//確保所有執行緒都在準備中

int tpool_add_work(void *pool, void(*routine)(void *), void *arg)
//配合 `dispatch` 加入 task 到 work queue 中

static void *tpool_thread(void *arg)
//給 worker task，沒有用到 mutex_lock

static tpool_work_t *get_work_concurrently(thread_t *thread)
//利用 CAS 讓每個執行緒拿到自己的 task，確保從 work queue 出來時，遞減 `out` 的變數同步

void tpool_destroy(void *pool, int finish);
//判斷所有的 queue 是不是空的，確保所有 worker 完成工作

CAS
以具有 atomic 特性的計算操作來達成。








bool CAS(T* addr, T exp, T val) 
{ 
    if (*addr == exp) {  
        *addr = val;  
        return true; 
    } 
    return false; 
}

github source code

實做測試

$ git clone https://github.com/xhjcehust/LFTPool
$ cd LFTPool/
$ make
$ ./testtpool

2016q3 Homework2 (phonebook-concurrent)

tags: sysprog

開發環境

Ubuntu 14.04 LTS

Concurrency

Concurrency(並行性) 不為 Parallelism (平行性) [1][2][3]

實作threads主要是為了達到Concurrency：

實作processes主要是為了達到Parallelism：

Sequenced Before

Happens-Before

案例分析 Phonebook-concurrent

Preliminaries

1. Macro 的使用

example

2. Thread management

pthread_create()

◆第一個參數

◆第二個參數

◆第三個參數

◆第四個參數

pthread_join()

◆第一個參數

◆第二個參數

pthread_exit()

3. Map file into memory

MMAP

munmap

4. File alignment

5. 檢查aligned file是否和原輸入一樣

check.c

執行結果

Code Refactoring

original

原本程式執行結果

合併pthread_create()和pthread_join()的分析

執行結果

threaded_findName()

執行結果

Thread Pool

Lock-free Thread Pool

Thread Pool VS Lock-Free Thread Pool

實做測試

tags: `sysprog`