學習筆記 第四章的自學歸納

并行計算導論

• 多進程服務器是指當客戶端發出請求時，服務器使用子進程來處理客戶端的請求。

• 父進程繼續等待來自其他客戶端的請求。

順序算法與并行算法

• 并行計算的優勢：探討并行計算相對于串行計算的優勢，包括加速計算速度、提高系統吞吐量、處理大規模數據等。

• 在只有一個CPU的情況下，每次只能按順序執行某算法的一個指令和步驟。但是，基于分治原則（如二叉樹查找和快速排序等）的算法經常表現出高度的并行性，可通過使用并行或并發執行來提高計算速度。并行計算是一種計算方案，它嘗試使用多個執行并行算法的處理器更快速地解決問題。

并行性與并發性

• 并行性指的是同時執行多個任務或操作的能力。在并行計算中，多個計算任務可以同時進行，每個任務由不同的處理單元執行，以提高計算效率和性能。并行性的目標是通過同時執行多個任務來加速計算過程。

• 并發性指的是多個任務或操作在相同時間段內交替執行的能力。在并發計算中，多個任務按照一定的調度策略交替執行，每個任務在某個時間片段內獲得處理器的執行時間。并發性的目標是通過任務的交替執行來提高系統的資源利用率和響應能力。

• 在單 CPU 系統中，一次只能執行一個任務。在這種情況下，不同的任務只能并發執行、即在邏輯上并行執行。在單CPU系統中，并發性是通過多任務處理來實現的。

線程

線程的原理

• 線程是某進程同一地址空間上的獨立執行單元。

線程的優點

• 線程創建和切換速度更快∶進程的上下文復雜而龐大。其復雜性主要來自管理進程映像的需要。在執行過程中，有些頁面在內存中，有些則不在內存中。操作系統內核必須使用多個頁表和多個級別的硬件輔助來跟蹤每個進程的頁面。要想創建新的進程，操作系統必須為進程分配內存并構建頁表。若要在某個進程中創建線程，操作系統不必為新的線程分配內存和創建頁表。因為線程與進程共用同一個地址空間。所以創建線程比創建進程更快。

• 線程的響應速度更快：一個進程只有一個執行路徑。當某個進程被掛起時、整個進程都將停止執行。相反，當某個線程被掛起時，同一進程中的其他線程可以繼續執行。這使得有多個線程的程序響應速度更快。

• 線程更適合并行計算∶并行計算的目標是使用多個執行路徑更快地解決問題。基于分治原則（如二叉樹查找和快速排序等）的算法經常表現出高度的并行性。可通過使用并行或并發執行來提高計算速度。這種算法通常要求執行實體共享公用數據。在進程模型中，各進程不能有效共享數據，因為它們的地址空間都不一樣。

線程的缺點

• 由于地址空間共享，線程需要來自用戶的明確同步。

• 許多庫函數可能對線程不安全。通常，任何使用全局變量或依賴于靜態內存內容的函數，線程都不安全。

• 在單CPU系統上，使用線程解決問題實際上要比使用順序程序慢。

線程管理函數

pthread_create(thread, attr, function, arg): create thread

pthread_exit(status) : terminate thread

pthread_cancel(thread) : cancel thread

pthread_attr_init(attr) : initialize thread attributes

pthread_attr_destroy(attr): destroy thread attribute

創建線程

• 使用pthread_create()函數

• pthread_id是指向pthread_t類型變量的指針。它會被操作系統內核分配的唯一線程ID填充。在POSIX中，pthread_t是一種不透明的類型。程序員應該不知道不透明對象的內容，因為它可能取決于實現情況。

• attr是指向另一種不透明數據類型的指針，它指定線程屬性，下面將對此進行更詳細的說明。

• func是要執行的新線程函數的入口地址。 arg是指向線程函數參數的指針，可寫為:void *func(void *arg)

• attr參數

線程ID

線程ID是一種不透明的數據類型，取決于實現情況。

線程終止

• 線程函數結束后，線程即終止。或者,線程可以調用函數int pthread_exit (void *status);

• 進行顯式終止，其中狀態是線程的退出狀態。通常，0退出值表示正常終止，非0值表示異常終止。

線程連接

一個線程可以等待另一個線程的終止。

線程同步

互斥量

最簡單的同步工具是鎖，它允許執行實體僅在有鎖的情況下才能繼續執行。

死鎖預防

互斥量使用封鎖協議。如果某線程不能獲取互斥量，就會被阻塞，等待互斥量解鎖后再繼續。

在實際系統中，唯一可行的方法是死鎖預防，試圖在設計并行算法時防止死鎖的發生。

條件變量

條件變量可以通過兩種方法進行初始化

• 靜態方法

• 動態方法

生產者-消費者問題

信號量

• 信號量是進程同步的一般機制

• 信號量和條件變量

屏障

• 線程連接操作允許某線程等待其他線程終止

• 在pthread中可以采用的機制是屏障以及一系列屏障函數

Linux中的線程

• 進程和線程都是由clone()系統調用創建的具有以下原型

int clone(int (fn)(void),void *child_stack,int flags,void *arg)

遇見的問題及相關解決措施

蘇格拉底挑戰