[發(fā)明專利]用于分割單鏈表以供分配存儲器元素的系統(tǒng)和方法

有效

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

提出了用于管理多個無鎖列表結構中所存儲的多個存儲器元素的分配的系統(tǒng)和技術?？墒惯@些無鎖列表結構(諸如Slist)在多核處理器的操作系統(tǒng)環(huán)境中可訪問并且可在系統(tǒng)中被分割。還可在這些無鎖列表結構間對存儲器元素進行分割。當核處理器(或其它處理元素)請求向自身分配存儲器元素時，系統(tǒng)和/或方法可在無鎖列表結構間搜索可用的存儲器元素。當找到合適和/或可用的存儲器元素時，系統(tǒng)可將可用的存儲器元素分配到該發(fā)出請求的核處理器?？筛鶕线m均衡度量(諸如，維持數量基本相等的存儲器元素或避免資源的過度分配)對存儲器資源進行動態(tài)均衡。

背景

Slist是在操作系統(tǒng)中可用的LIFO(后進先出)列表的無鎖實現的數據結構。Slist通常是對用以保持分配和釋放無需保持任何旋轉鎖或其它同步原語的固定大小緩沖器的數據結構的期望選擇。Slist還可以無鎖單鏈表的形式用于大小可變的內容。在操作系統(tǒng)環(huán)境中還提供了其它能力——諸如構建在Slist上的后備列表。

然而，在一些場景中，使用Slist可能是不合期望的。舉一個例子而言，通過多個處理器訪問相同的Slist，單個Slist表頭可變成服務器上高速緩存行爭用熱點。這在本機及Hyper-V虛擬化場景中都是可縮放性瓶頸。

在另一場景中，Slist主要用作分組高速緩存或固定大小的緩沖器儲存庫。然而，存在其中必須在此類無鎖列表中維持更加復雜的數據結構或大小可能變化的資源的諸場景。為了諸如負載均衡、分組挪用、NUMA察覺以及此類其它算法需求的目的，可期望具有更多的操作而不僅僅是“入棧(Push)”和“出棧(Pop)”。這些通常通過用以管理多個Slist的另一數據結構抽象得以滿足。后備列表是一個這樣的示例。

后備列表維持固定大小緩沖器的高速緩存以供高速存儲器分配和釋放。為了處理器關聯(lián)效益，一些操作系統(tǒng)還提供每個處理器的后備列表。這些每個處理器的后備列表一般(但非必須地)被全局列表備份以在每個處理器列表為空的情況包含備份分組。可期望具有額外的資源分配以具有相當大的全局備份列表來提供單個資源池的抽象。當需求減弱時，如果存在對存儲器的需求，則這些額外的存儲器分配可被釋放。然而，在某些場景中資源不能被過度分配。對于限定其能力限度(諸如RAID控制器能處理的I/O請求的最大數目)的硬件驅動器而言尤其如此。先前算法使這些限度受Slist深度的束縛并且避免使用旋轉鎖。另外，分配和釋放的額外開銷導致存儲器碎片并消耗CPU周期。出于這些原因，可能不可使用分配多于所需數量的后備列表。

概述

下面呈現了本發(fā)明的簡化概述，以便提供此處所描述的某些方面的基本概念。此概述不是所要求保護的主題的詳盡的概述。既不是要指出所要求保護的主題的關鍵性元素，也不是要詳細描述本發(fā)明的范圍。唯一的目的是以簡化形式呈現所要求保護的主題的某些概念，作為稍后呈現的比較詳細的描述的前奏。

在一個實施例中，提出了用于管理多個無鎖列表結構中所存儲的多個存儲器元素的分配的系統(tǒng)和方法?？墒惯@些無鎖列表結構(諸如Slist)在多核處理器的操作系統(tǒng)環(huán)境中可訪問。在一些實施例中，無鎖列表結構、Slist或類似物可被嵌入其它常見數據結構(如散列、樹等)中以滿足不同的資源分配和管理需求。

一些實施例可對該多個無鎖列表結構進行分割并且在這些無鎖列表結構間對存儲器元素進行初始分割。當核處理器(或其它處理元素)請求向自身分配存儲器元素時，系統(tǒng)和/或方法可在無鎖列表結構間搜索可用的存儲器元素。當發(fā)現合適和/或可用的存儲器元素時，系統(tǒng)可將可用的存儲器元素分配到該發(fā)出請求的核處理器。

在一些實施例中，該系統(tǒng)和/或方法可根據合適均衡度量隨后在各種無鎖列表結構間動態(tài)地均衡該組存儲器元素。這種可能的度量用以在無鎖列表結構間簡單地維持數量基本相等的存儲器元素是可能的。其它度量可包括其它負載均衡考慮——可能基于運行的處理類型、可能的爭用情形或類似物(例如，諸如上述減少CPU爭用或避免對存儲器資源的過度分配)。