[發明專利]一種高速緩存友好的用戶級線程調度方法

有效

• 申請號: 201910745905.4
• 申請日: 2019-08-13
• 公開（公告）號: CN110597606B
• 公開（公告）日: 2022-02-18
• 發明（設計）人: 吳繼鵬
• 申請（專利權）人: 中國電子科技集團公司第二十八研究所
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 胡建華;于瀚文

本發明提供了一種高速緩存友好的用戶級線程調度方法，所述方法是一種將用戶級線程映射到物理線程的用戶級線程調度方法。每個物理線程對應一個存放由任務派生的子任務容器對象池Arena，與一個用于存放用戶通過外部接口新增任務的容器Buffer，物理線程優先執行對象池Arena中的本地任務，在執行完后不陷入睡眠，而是主動竊取其他物理線程對象池Arena中的任務，若不存在對象池Arena中的任務則執行Buffer中的新任務。該方法的新穎之處在于將無鎖任務容器與內存池、FreeList統一在一個數據結構中，避免了頻繁的任務構造函數調用，此外還將所有任務固定分配在相鄰且Aligned的內存區域，因此可更有效地利用CPU高速緩存。

技術領域

本發明涉及一種高速緩存友好的用戶級線程調度方法。

背景技術

用戶級線程池是新興服務端語言中廣泛采用的語言特性，如goroutine。相比傳統線程，它并不會提升性能，但能更好地將程序邏輯與物理線程約束之間的耦合消除，從而產生更靈活的超高并發的編程范式。

傳統線程池的一個典型實現方式是若干個工作線程從一個共享的任務隊列中取出任務再執行。

傳統線程池的缺陷之一是一個線程執行完畢后會陷入睡眠，等到線程池的主線程分配任務給它，這個陷入睡眠再獲取任務的過程對并發性能造成了不必要的損失。因此在此之上衍生出了一種更有效的work-stealing算法。每個工作線程維護獨立的任務隊列，一旦執行完自己的任務，不會陷入睡眠，而是主動從其他工作線程竊取任務。傳統線程池的另一個缺陷是任務生成的子任務進入唯一共享隊列的并發性能差。 Work-stealing算法中每個物理線程擁有獨立的任務隊列，這個任務隊列用特殊的無鎖數據結構實現，能夠高并發地加入、取出新的子任務。

傳統線程池的缺陷之三是子任務執行順序與線性執行順序不符，cache(CPU高速緩存)的temporal locality(時序局部性)較差(越新生成的子任務越應該優先執行，而非相反)。Work-stealing算法同樣通過優先取新生子任務的方式更好的利用了cache 的temporal locality。

現有的Work-stealing算法在實踐中仍存在以下問題：

1、子任務遞歸產生的場景下，頻繁地創建、銷毀任務存在較高的內存分配與任務對象構造開銷。

2、任務對象的物理內存布局可能是相對零散的，且不一定是cache-line aligned(緩存行對齊)的。因此導致cache效率不佳。

發明內容

發明目的：本發明所要解決的技術問題是針對現有技術的不足，提供一種高速緩存友好的用戶級線程調度方法，所述方法是一種將用戶級線程映射到物理線程的用戶級線程調度方法。每個物理線程對應一個用戶級線程容器，物理線程按照一定順序進行任務執行，本發明具體包括如下步驟：

步驟1，線程池初始化；

步驟2，線程池運行，進行用戶級線程調度。

步驟1包括如下步驟：

步驟1-1，根據cpu數目確定工作線程Worker數目，每個工作線程Worker對應一個物理線程，工作線程Worker中包含對象池Arena；

步驟1-2，初始化每個工作線程Worker的對象池Arena(對象池內含預先構造好的用戶級任務對象)，預先構造對象池Arena中的FixSizedTask，FixSizedTask是內存中固定大小的用戶級任務的具體實現的抽象，對用戶不可見，屬于底層實現的一個組件；