[發明專利]用于分割單鏈表以供分配存儲器元素的系統和方法

有效

• 申請號: 201380022199.1
• 申請日: 2013-04-19
• 公開（公告）號: CN104254839B
• 公開（公告）日: 2018-10-12
• 發明（設計）人: A·D·迪克西特;B·M·沃特斯
• 申請（專利權）人: 微軟技術許可有限責任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F12/02
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 管琦琦

1.一種用于管理一個或多個無鎖列表結構(204)中所存儲的多個存儲器元素(206)的分配的方法，所述無鎖列表結構在多核處理器的操作系統環境中可訪問，所述方法的步驟包括：

對所述一個或多個無鎖列表結構(204)進行分割；

在所述一個或多個無鎖列表結構間對所述多個存儲器元素(206)進行初始分割；

一旦請求向核處理器分配存儲器元素，就從所述一個或多個無鎖列表結構搜索可用的存儲器元素，所述搜索使用被鍵控以相應散列所述一個或多個無鎖列表結構中的每一個的自適應散列來執行；

一旦找到所述可用的存儲器元素，就把所述可用的存儲器元素(214)分配給所述核處理器；以及

根據合適的被配置為優化存儲器分配的均衡度量，在所述一個或多個無鎖列表結構間動態地均衡所述存儲器元素。

2.根據權利要求1所述的方法，其特征在于，對所述一個或多個無鎖列表結構進行分割的步驟進一步包括將所述一個或多個無鎖列表結構分割成第一數據結構。

3.根據權利要求2所述的方法，其特征在于，所述第一數據結構是組中的一者，所述組包括：散列結構(202)和動態列表交換(250)數據結構。

4.根據權利要求3所述的方法，其特征在于，根據多核處理器架構鍵控所述散列結構。

5.根據權利要求4所述的方法，其特征在于，根據處理器索引鍵控所述散列結構。

6.根據權利要求4所述的方法，其特征在于，根據NUMA節點編號鍵控所述散列結構。

7.根據權利要求3所述的方法，其特征在于，所述動態列表交換數據結構進一步包括出棧無鎖列表結構和入棧無鎖列表結構，其中所述對所述一個或多個無鎖列表結構進行分割的步驟進一步包括根據用以均衡存儲器資源的度量在所述出棧無鎖列表結構和所述入棧無鎖列表結構之間交換指針。

8.一種用于管理一個或多個無鎖列表結構(204)中所存儲的多個存儲器元素(206)的分配的系統，所述無鎖列表結構在多核處理器的操作系統環境中可訪問，所述系統包括：

多個核處理器(106)，所述核處理器被分割成一組處理器插槽(104)；一組共享存儲器(108)，所述共享存儲器可由至少一個所述處理器插槽訪問；

在至少兩個所述處理器插槽之間的通信路徑(110)；

一組一個或多個無鎖列表結構(204)，每一所述無鎖列表結構能夠存儲至少一個存儲器元素，所述一組一個或多個無鎖列表結構能夠被分割以供一請求存儲器元素分配就向所述核處理器分配所述存儲器元素；

分配模塊(202)，所述分配模塊能夠從所述多個核處理器接收對存儲器元素分配的請求；以及

其中所述分配模塊能夠根據合適的被配置為優化存儲器分配的均衡度量使用被鍵控以相應散列所述一個或多個無鎖列表結構中的每一個的自適應散列在所述一組一個或多個無鎖列表結構間動態地調整存儲器元素。

9.根據權利要求8所述的系統，其特征在于，所述分配模塊能夠在所述核處理器(106)之一上執行。

10.根據權利要求9所述的系統，其特征在于，所述合適的均衡度量是組中的一員，所述組包括：在無鎖列表結構間維持數量基本相等的存儲器元素以及避免存儲器資源的過度分配。

11.一種具有指令的計算機可讀存儲介質，當所述指令被執行時使得機器執行如權利要求1-7中任一權利要求所述的方法。

12.一種計算機系統，包括用于執行如權利要求1-7中任一權利要求所述的方法的裝置。