Try   HackMD

2016q3 Homework2 (phonebook-concurrent)

contributed <nekoneko>

資料閱讀

  • Toward Concurrency
    • 軟體開發現狀
      • The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software
      • An Introduction to Lock-Free Programming
      • Acquire and Release Semantics
      • Weak vs. Strong Memory Models
      • Concurrency Kit
    • Functional Programming
      • Why are functional languages considered a boon for multi threaded environments?
      • It’s Time to Get Good at Functional Programming
      • Don’t Be Scared Of Functional Programming
      • Functional programming in C
    • Concurrency (並行) vs. Parallelism (平行）
    • Concurrency 系列文章 (繁體中文)
      • Concurrency系列一到五
      • 冼鏡光投影片
    • Process vs. Thread vs. Coroutines
      • SMT (Simultaneous Multithreading), VMT(Vertical Multithreading)
      • setjmp, longjmp
      • switch case
    • POSIX Threads
    • thread pool
    • sorting link list

軟體開發現狀

The Free Lunch Is Over

  • 隨著CPU邁向多核和hyper threading等增加效能的性能，這兩種技術已經普遍於大多的CPU。然而，CPU的頻率因為物理現象造成的瓶頸已經到達上限。
  • Past 30 years
    • clock speed
    • execution optimization
    • cache
  • near-term future
    • hyperthreading
    • multicore
    • cache

An Introduction to Lock-Free Programming

  • What is Lock Free Program ?

Lock Free

  • Lock-Free Programming Techniques

    不懂的詞: ABA Problem, CAS, LockMUTEX

  • Atomic Read-Modify-Write
    在多執行序的情況下，對資料的讀寫使用atomic操作，保證資料的一致性

  • Compare And Swap
    atomic的實做有不同的方式，在恐龍本中提到test-and-set和compare-and-swap，兩種都是為了在多執行序的情況下，只讓一個執行序進入critical session。以下是恐龍本書中程式碼。















int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
	if (*value == expected)
		*value = new_value;
	return tempt;
}
some_other_atomic (...) {
	do {
		while (compare_and_swap(&lock,0,1) != 0) ;
		/* critical section */
		lock = 0;
		/* remainder section */
	} while (true);
}
  • ABA Problem
    這邊可以參考Wikipedia和tundegrod大大的筆記，寫的很清楚。
  • Sequential Consistency & Memory Ordering
    編譯器的優化和CPU本身亂序執行，會導致指令執行的順序與原先程式碼不同(Memory Ordering)。

搭配看影片: Memory Ordering Intro - Georgia Tech jserv

  • 有提到三種防止memory Ordering的方式。目前沒看懂之後再補。cheng hung lin

Acquire and Release Semantics

  • Memory Ordering at Compile Time
    • 四種指主要的barrier: LoadLoad, LoadStore, StoreLoad, StoreStore。
    • 本篇以兩個end-user對應一個central repository來介紹四種主要的memory barrier。
    • 文章提到四種有barrier功能的函式
      • Certain inline assembly directives in GCC, such as the PowerPC-specific asm volatile("lwsync" ::: "memory")
      • Any Win32 Interlocked operation, except on Xbox 360
      • Many operations on C++11 atomic types, such as load(std::memory_order_acquire)
      • Operations on POSIX mutexes, such as pthread_mutex_lock
  • Memory Barriers Are Like Source Control Operations
    • fense instruction, barrier instruction

Weak vs. Strong Memory Models

Concurrency Kit

Functional Programming

Why are functional languages considered a boon for multi threaded environments?

  • "there's no share state"
  • "The absence of shared state makes multithreading safe."

share state不懂，之後再補

It's Time to Get Good at Functional Programming

  • 隨著Moore's Law遇到物理上的瓶頸(熱能產生)，中央處理器轉向多核的趨勢。而FP在平行運算上的優勢因多核被受到重視。
  • 簡單介紹幾種FP語言: Scala, F#, Erlang, Haskell
    • Scala: Java語言支援，為hydrid式FP(OOP/FP)
    • F#: .Net 系列，為hydrid
    • Erlang, Haskell: 都為純FP程式語言

Don’t Be Scared Of Functional Programming

  • 以javascript為例，撰寫一份FP的programe

Functional programming in C

有看沒有懂，之後在研究cheng hung lin
這篇的下一篇為FP in C的實做，Functional programming in C – Implementation

Concurrency (並行) vs. Parallelism (平行）

  • parallelism: 像是一個工作請兩個工人來做。
  • concurrency: 像是一個工作切很多子工作，請一個工人來做。假如工人交錯每做一部份子工作，就換下一個子工作，這樣的情況就類似平行(time slicing)，但絕對不是平行。

英文太差，中文表達不好，還是沒有佷讀透其中道理。

  • Concurrency (並行) vs. Parallelism (平行）
    cheng hung lin

Concurrency 系列文章 (繁體中文)

  • 一到三篇key word: Sequential-before ,happen-before
  • 第五篇對在ReadRead, ReadWrite, WriteRead, WriteWrite中不遵守Sequential Consistency的情況舉例。另外還簡單提到Cache Coherence
  • Cache Coherence: 確保同一份資料在不同處理器的cache上保持一致，包括讀寫順序。

並行計算投影片

尾聲的部份跟主題沒關，但可以先看一下cheng hung lin

Process vs. Thread vs. Coroutines

  • Coroutines
    Coroutines are computer program components that generalize subroutines for --nonpreemptive multitasking, by allowing multiple entry points for suspending and resuming execution at certain locations.
  • [ ]SMT, VMT

coroutines

setjmp, longjmp

直接看man setjmp和man longjmp，與參考瞿同學的筆記和程式碼

  • setjmp:

    • save stack context for nonlocal goto
    • setjmp() and sigsetjmp() return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context.

  • longjmp:

    • nonlocal jump to a saved stack context
    • longjmp() restores the environment saved by the last call of setjmp(3) with the corresponding env argument.
    • longjmp() cannot cause 0 to be returned. If longjmp() is invoked with a second argument of 0, 1 will be returned instead.
      longjmp(jump_buff_*, val)是跳回最後一次呼叫setjmp(jump_buffer_*)的位置，所以說這也是為什麼會加if (r == 0) /* call other function */，避免一直回覆呼叫同一個函式後又跳回原呼叫的setjmp(jump_buff_*)，此外，longjmp是禁止以0為參數的，若傳0進去，則會在setjmp回傳1。
      例如以下就會一直循環不停。












int count;
void bufferA() {
	printf("bufferA incremnet count: %d\n", ++count);
	sleep(1);
	longjmp(bufferMain, 1);
}
int main(int argc, char *argv[]) {
	count = 0;
	setjmp(bufferMain) && printf("setjmp bufferMain!!\n");
	bufferA();
	return 0;
}

switch case

目前先跳過cheng hung lin

POSIX Threads

POSIX Thread 實例: 光線追蹤

先略cheng hung lin

POSIX thread

  • 有些pthread函式的manual找不到的話，可能是沒有裝glibc的manual

    ​$ sudo apt-get install glibc-doc

  • Common thread modules:

    • manager/worker
    • pipeline
    • peer

  • Thread Safe
    函式庫也要保證thread safe

    • [ ]Condiction variable

  • Discussion on calling pthread_exit() from main():

    • By having main() explicitly call pthread_exit() as the last thing it does, main() will block and be kept alive to support the threads it created until they are done.
    • man pthread_exit()的Notes也有提到:
      To allow other threads to continue execution, the main thread should terminate by calling pthread_exit() rather than exit(3).
    • main直接回傳(return)時，會呼叫exit()，連帶整個task都會結束(die)。若是呼叫pthread_exit()，則是把main當作task裡的其中一個thread，只會把main thread關掉，整個task仍然存在，其他衍生的thread也得以繼續執行。
    • Reference: CS360 Lecture notes – Thread #1

  • pthread_exit()

    • void pthread_exit(void *retval)
    • 在man pthread_exit()的Notes提到：
      The value pointed to by retval should not be located on the calling thread's stack, since the contents of that stack are undefined after the thread terminates.

  • stack management:

    • 使用pthread_attr_setstack/pthread_attr_getstack做stack調整，而非pthread_attr_setstackattr/pthread_attr_getstackattr。
    • man pthread_attr_setstackattr裡提到，這函式的攜帶性(portable)不足。

condition variable:

  • 恐龍本6.8章的mintor，是有加上condition variable。
  • 將thread放入condition variable x 的waiting queue，當其他thread有符合x這個condition時，喚醒xwaiting queue裡的thread。condition variable使得thread之間可以依照condition做先後相依有順序的執行，當condition符合時，可以喚醒再waiting queue裡的thread。
  • 可以避免對所有thread做**輪尋(polling)**檢查condition是否符合

thread pool

Lock free thread pool

作業

refactoring

clz 的應用: 加速記憶體管理

  • SuperMalloc
    • LD_PRELOAD

程式分析

程式檔案

  • main.c ( * )
  • calculate.c
  • file.c ( * )
  • file_align.c
  • phonebook_org.c ( * )
  • phonebook_org.h ( * )
  • phonebook_opt.c ( * )
  • phonebook_opt.h ( * )
  • debug.h ( * )
  • Makefile ( * )

打星號的部份，是編譯產生phonebook_*會使用到的檔案

其他關鍵字

  • violate
  • register
  • first-class objects

參考資料

tags: nekoneko
Last changed by 
 
Chien Hung Lin
0
237
Published on HackMD