Try   HackMD

2016q3 Homework2 (phonebook-concurrent)

contributed by <a530788140>

POSIX Threads 學習

thread 是什麼？

  • Thread 通常被稱做輕量級的行程（Lightweight process；LWP）
  • Mach microkernel 作業系統中同一個task 的所有 thread 共享該 task 所擁有的系統資源。
  • UNIX 的一個 process 可以看成是一個只有一個 thread 的 Mach task。
  • 對 CPU 而言，產生一個 thread 是一件相對簡單的工作。
  • 共享系統資源的 thread 跟獨佔系統資源的 process 比起來，thread 是也是相當節省記憶體的。

建立thread

  pthread_t         a_thread;
  pthread_attr_t    a_thread_attribute;
  void              thread_function(void *argument);
  char              *some_argument;
  
  pthread_create( &a_thread, a_thread_attribute, (void *)&thread_function, 
               (void *) &some_argument);

timming delay 來達成thread間的同步是錯誤的，因為 thread 間的緊密耦合（tightly coupled）特性很容易讓我們使用一些不精確的方法來達成其間的同步處理，如果要讓thread 停頓可以使用pthread_delay_np （np 表示 not portable）函式。

在 POSIX Thread 中，_np 表示 not portable jserv

Thread 同步問題

mutex 和 condition variable

  • POSIX 提供了兩組用來使 thread 同步的基本指令： mutex 和 condition variable。
  • mutex 指的是一組用來控制共享資源存取的一組函數。
  • thread 使用一些在pthreadcreate 之前定義或在其所呼叫的函數中定義的變數來完成其工作，並將他的成果經由整體變數合併。對這些大家都可以存取的變數，我們必須加以控制。
  • mutex 一般用在解決 race condition 問題，但是 mutex 並不是一個很強的機制，因為他只有兩個狀態：locked 和 unlocked。
  • POSIX 定義的條件變數（condition variable）將 mutex 的功能加以延伸，能夠做到讓某一個 thread 能暫停，並等待另一個 thread 的信號（signal）。
pthread_mutex_init()

pthread_mutex_lock() //需先lock mutex，看看buffer 中是否有資料，若有資料則將其取出

請不要活在「腦補」的世界中，再次詳細閱讀 man page: pthread_mutex_lock jserv
已修改 謝謝老師提醒儂偉

pthread_mutex_lock()    //用來鎖定thread，直到mutex變為可用狀態
pthread_mutex_unlock()
pthread_mutex_destroy() //釋放 mutex

使用 Semaphores 達成協調工作(解決 spin-lock 問題)

Semaphore 相關的運算
semaphore_init()	   //使用 semaphore 前必須呼叫 init 函數,初始值均為 1
semaphore_up()		   //遞增 semaphore
semaphore_down()          //運算將在 semaphore 值小於或等於零時暫停
semaphore_destroy()	   //釋放semaphore
semaphore_decrement()

使用注意事項

  • 編譯使用 pthread 的程式，必須引入相關的標頭檔 (一般是 <pthread.h>)
  • 連結 pthread library cc hello_world.c -o hello_world -lpthread
  • 使用 semaphore 則額外引入標頭檔。

注意: 有兩個完全不同的 semaphore 實作，一個是 System V semaphore，另一個是 POSIX semaphore，請參閱討論 What are the trade-offs between using a System V and a Posix semaphore? jserv
謝謝老師提醒儂偉

Differences between System V and Posix semaphores

由Semaphores in Linux這個網站所列出的主要差異，並整理出來下列幾項

  • System V 與 POSIX 區別於System V可以控制the semaphore count數量的增加或減少，但在POSIX，the semaphore count只能加1或減1。
  • System V 可以去改變semaphores原始權限的子集，而POSIX不被允許更改semaphores的權限。
  • 從用戶角度來看，semaphores的初始化和建立是 atomic 在POSIX。
  • 但從使用角度來看，POSIX的可擴展性比System V 高很多，由於POSIX直接使用未命名semaphores。
  • 當建立semaphore object時，System V 建立一個semaphores "array"，但POSIX 只建立單一semaphores。因此，System V在建立semaphore時"memory footprint-wise"的成本是比POSIX更高的。所以有人說POSIX性能是比System V更好。
  • POSIX為 "process-wide semaphores" 機制而不是 "system-wide semaphores" 機制
  • POSIX提供；non-persistent semaphores； 機制，也就是說當一個開發者忘記關閉"semaphore" ，會在"process exit"時被清除。

MMAP

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset);
int munmap(void *addr, size_t length);
  • mmap()建立新的mapping在呼叫行程的定址空間，新mapping的開始定址空間被指定在 *addr。

尊重我們的傳統文化，請用台灣慣用術語。process = 行程; call = 呼叫; virtual memory = 虛擬記憶體; address space = 定址空間; file = 檔案; access = 存取; return = 傳回; create = 建立; jserv
已修改,以後會多加注意儂偉

  • length參數為指定mapping的長度。
  • 如果addr為NULL，kernel將在建立的mapping地址中選擇，這是建立新的mapping最簡單的方法。
  • 如果addr不是NULL，在LINUX,mapping會在附近的page boundary建立，並將新mapping地址傳回。
  • prot參數描述了需要保護的記憶體保護mapping(必須不能跟打開傳回模式衝突)
    • PROT_EXEC 可能執行
    • PROT_READ 可能讀取
    • PROT_WRITE 可能寫入
    • PROT_NONE 可能不能存取
  • flag參數用來確定更新mapping是否被有其他行程mapping同個區域，這些狀態由下列flag值來確定：
    • MAP_SHARED 分享此mapping
    • MAP_PRIVATE 建立一個私有copy-on-write mapping。

實作threadpool

參考mbrossard 完整的 ThreadPool 原始碼
新增phonebook_threadpool來與opt做比較
並在main裡新增了下列程式碼





































#if defined THREADPOOL
#define QUEUE 256
    extern threadpool_t *pool;
    extern pthread_mutex_t lock;

    pthread_mutex_init(&lock, NULL);
    assert((pool = threadpool_create(THREAD_NUM, QUEUE, 0)) != NULL);
    append_a **app = (append_a **) malloc(sizeof(append_a *) * THREAD_NUM);
    for (int i = 0; i < THREAD_NUM; i++)
        app[i] = new_append_a(map + MAX_LAST_NAME_SIZE * i, map + fs, i,
                              THREAD_NUM, entry_pool + i);
    for (int i = 0; i < THREAD_NUM; i++) {
        threadpool_add(pool, &append, (void *) app[i] , 0);
    }

    entry *etmp;
    pHead = pHead->pNext;
    for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = app[i]->pHead->pNext;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        } else {
            etmp->pNext = app[i]->pHead->pNext;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        }

        etmp = app[i]->pLast;
        dprintf("Connect %d tail string %s %p\n", i,
                app[i]->pLast->lastName, app[i]->ptr);
        dprintf("round %d\n", i);
    }
    clock_gettime(CLOCK_REALTIME, &end);
    cpu_time1 = diff_in_second(start, end);
    assert(threadpool_destroy(pool, 0) == 0);

遇到問題 findname一直失敗，待解決儂偉

使用GDB






















[New Thread 0x7ffff6a96700 (LWP 4518)]
[New Thread 0x7ffff6295700 (LWP 4519)]
[New Thread 0x7ffff5a94700 (LWP 4520)]
[New Thread 0x7ffff5293700 (LWP 4521)]
[Thread 0x7ffff5293700 (LWP 4521) exited]
[Thread 0x7ffff6295700 (LWP 4519) exited]
[Thread 0x7ffff5a94700 (LWP 4520) exited]
[Thread 0x7ffff6a96700 (LWP 4518) exited]

Breakpoint 1, main (argc=1, argv=0x7fffffffde68) at main.c:106
106	    pHead = pHead->pNext;
(gdb) p entry_pool[2]->lastName 
$1 = 0x0
(gdb) p entry_pool[3]->lastName 
$2 = 0x0
(gdb) p entry_pool[4]->lastName 
$3 = 0x7ffff729a040 "aaaaaaaa\n"
(gdb) p entry_pool[5]->lastName 
$4 = 0x0
(gdb) p entry_pool[8]->lastName 
$5 = 0x7ffff729a080 "aaaaaahhhhh\n"

發現只有app[0]的thread有執行,待解決儂偉

assert(threadpool_destroy(pool, 1) == 0);

將上面0改成1，解決Thread未完成被shutdown的問題

與原始OPT做比較

THREAD = 4

THREAD = 4

THREAD = 8

THREAD = 16

THREAD = 32

發現apped的速度反而變慢，可是當我THREAD數量增加時，threadpool的速度會增加，但OPT卻下降儂偉

最後統計圖

cache-misses 比較圖

發現在Thread=8時cache-misses最高，但還在思考原因，待有人可以討論和解答。儂偉

重新學習Git Commit

由於上禮拜被老師指出這方面的缺失，並且根據老師給的資料重新學習

  • 使用$git log --oneline -5可以查詢commit資訊
  • 根據How to Write a Git Commit Message網站，一開始就指出內容需要保持簡潔和一致性
  • git提交訊息是為了傳遞開發者對相關程式更改，並且這些更改的差異能正確提提供給其他開發者
  • 一個長期專案的生產力，其中間取決於其可維護性和維護者寫的日誌

了解到了寫好git commit的重要性儂偉

  • 為了創造一個有用的版本歷史紀錄，一個團隊需定義至少下面3點達成一致：
    • Style： Markup syntax, wrap margins, grammar, capitalization, punctuation等，刪除一些不確定性，並讓其盡可能簡單，最終會產生非常一致的日誌。
    • Content： commit內容需要包含哪些訊息，或不應該包含？
    • Metadata： 要如何發佈被引用的tracking IDs，pull request numbers等。

參考資料

Last changed by 
 
a530788140
0
1296
Published on HackMD