筆者之前照着通用寫法練手寫過一個小的線程池版本，最近幾天複習了一下，發現大多數線程池實作都離不開鎖的使用，如互斥量pthread_mutex*結合條件變量pthread_cond*。衆所周知，鎖的使用對于程式性能影響較大，雖然現有的pthread_mutex*在鎖的申請與釋放方面做了較大的優化，但仔細想想，線程池的實作是可以做到無鎖化的，于是有了本文。
如上圖所示，工作隊列由主線程和工作者線程共享，主線程将任務放進工作隊列，工作者線程從工作隊列中取出任務執行。共享工作隊列的操作需在互斥量的保護下安全進行，主線程将任務放進工作隊列時若檢測到目前待執行的工作數目小于工作者線程總數，則需使用條件變量喚醒可能處于等待狀态的工作者線程。當然，還有其他地方可能也會使用到互斥量和條件變量，不再贅述。
為解決無鎖化的問題，需要避免共享資源的競争，是以将共享工作隊列加以拆分成每工作線程一個工作隊列的方式。對于主線程放入工作和工作線程取出任務的競争問題，可以采取環形隊列的方式避免。在解決了鎖機制之後，就隻剩下條件變量的問題了，條件變量本身即解決條件滿足時的線程通信問題，而信号作為一種通信方式，可以代替之，其大體程式設計範式為：
在無鎖線程池中，差別于常見線程池的地方主要在于信号與條件變量、任務排程算法、增加或減少線程數目後的任務遷移，另外還有一點就是環形隊列的實作參考了Linux核心中的kfifo實作。
(1) 信号與條件變量
信号與條件變量的差別主要在于條件變量的喚醒(signal)對于接收線程而言可以忽略，而在未設定信号處理函數的情況下信号的接收會導緻接收線程甚至整個程式的終止，是以需要線上程池産生線程之前指定信号處理函數，這樣新生的線程會繼承這個信号處理函數。多線程中信号的發送主要采用pthread_kill，為避免使用其他信号，本程式中使用了SIGUSR1。
(2) 任務排程算法
常見線程池實作的任務排程主要在作業系統一級通過線程排程實作。考慮到負載均衡，主線程放入任務時應采取合适的任務排程算法将任務放入對應的工作者線程隊列，本程式目前已實作Round-Robin和Least-Load算法。Round-Robin即輪詢式地配置設定工作，Least-Load即選擇目前具有最少工作的工作者線程放入。
(3) 任務遷移
線上程的動态增加和減少的過程中，同樣基于負載均衡的考量，涉及到現有任務的遷移問題。負載均衡算法主要基于平均工作量的思想，即統計目前時刻的總任務數目，均分至每一個線程，求出每個工作者線程應該增加或減少的工作數目，然後從頭至尾周遊，需要移出工作的線程與需要移入工作的線程執行任務遷移，互相抵消。最後若還有多出來的工作，再依次配置設定。遷入工作不存在競态，因為加入工作始終由主線程完成，而遷出工作則存在競态，因為在遷出工作的同時工作者線程可能在同時執行任務。是以需要采用原子操作加以修正，其主要思想即預取技術，大緻實作為：
(4) 環形隊列
源碼中環形隊列實作主要參考了linux核心中kfifo的實作，如下圖所示：
隊列長度為2的整次幂，out和in下标一直遞增至越界後回轉，其類型為unsigned int，即out指針一直追趕in指針，out和in映射至FiFo的對應下标處，其間的元素即為隊列元素。
以上主要是一些方案性的說明，至于具體細節的實作有興趣的讀者可以參考https://github.com/xhjcehust/LFTPool，有問題歡迎随時聯系讨論.
注:本文兩年前曾釋出在http://blog.csdn.net/xhjcehust/article/details/45844901，最近有讀者回報一些問題，也修複了一些bug，再次分享，希望更多的讀者能有收獲。
from:https://mp.weixin.qq.com/s?__biz=MzIxNzg5ODE0OA==&mid=2247483699&idx=1&sn=6b8bebc33525bddd167a90a3119b3873&chksm=97f38cf8a08405eed3783f122dba8f07ea78b42fd7c08d0011adf3ca00b9cf5140cb7a6567f7#rd