[發明專利]在NUMA系統中提升搶鎖操作公平性的方法

在審

• 申請號: 202010634382.9
• 申請日: 2020-07-02
• 公開（公告）號: CN111782411A
• 公開（公告）日: 2020-10-16
• 發明（設計）人: 楊思博;趙冠杰;于敦山;劉靜
• 申請（專利權）人: 江蘇華創微系統有限公司;中國電子科技集團公司第十四研究所
• 主分類號: G06F9/52
• 分類號: G06F9/52
• 代理公司: 深圳紫晴專利代理事務所(普通合伙) 44646
• 代理人: 陳彩云

本發明公開了在NUMA系統中提升搶鎖操作公平性的方法，在NUMA系統中設置芯片0和芯片1，芯片0和芯片1通過片間傳輸橋進行片間互連，芯片1為芯片0的遠程芯片，芯片0為本地芯片，然后在芯片1和芯片0內均進行令牌分配、令牌裁決和形成令牌隊列。通過對條件存儲指令隨機賦予代表不同優先級的令牌，并在發生沖突時根據令牌判斷條件存儲指令的執行結果來代替通過延遲確定執行結果的方法，從而避免了隨機加入的長延遲對性能的影響，在令牌裁決中競爭失敗的請求不需要從遠程芯片返回響應，而是隨著遠程芯片的同地址請求到達本地芯片時從本地芯片返回失敗的響應，省去了響應在片間互連傳輸的延遲，提升了性能。

技術領域

本發明涉及在NUMA系統中提升搶鎖操作公平性技術領域，具體為在NUMA系統中提升搶鎖操作公平性的方法。

背景技術

在多核計算機系統中，為了保證共享資源可以被多個處理器核正確地分時復用，需要通過對自旋鎖的搶鎖操作來決定哪個核獲得對共享資源的使用權。

自旋鎖是保存在內存中的一個變量，不同類型的自旋鎖有不同的操作方式，最簡單的方式是這個變量為0表示可以獲得鎖，為1表示已經上鎖，必須等待別的核解鎖后才可以使用。

一般搶鎖的操作通過鏈接加載(load link)和條件存儲(store conditional)操作完成：

處理器核通過鏈接加載指令讀取鎖變量的當前值，同時設置一個監視器(monitor)監控是否有別的核改寫這一變量；

處理器核判斷讀取的值，如果是0，那么使用條件存儲指令嘗試寫入1，如果是1，那么返回(1)；

1、如果在監視器設置后到條件存儲指令執行前沒有其它核修改鎖的變量，則條件存儲指令執行成功，成功獲得鎖，否則返回(1)。

2、當多個核嘗試同時獲得鎖時，會產生競爭，此時只有一個核的條件存儲指令能夠成功執行從而獲得鎖而其它核會搶鎖失敗，需要重新進行搶鎖操作。

3、搶鎖操作能否成功采用的是“先到先得”的原則，但是當系統中多個核爭搶同一個鎖時，有可能這幾個核之間形成固定的模式導致其中某個核一直無法搶到鎖，此時這個核就會陷入饑餓狀態，即一直處于搶鎖狀態而無法執行后面的程序。

當多個核嘗試同時獲得鎖時，會產生競爭，此時只有一個核的條件存儲指令能夠成功執行從而獲得鎖而其它核會搶鎖失敗，需要重新進行搶鎖操作。

搶鎖操作能否成功采用的是“先到先得”的原則，但是當系統中多個核爭搶同一個鎖時，有可能這幾個核之間形成固定的模式導致其中某個核一直無法搶到鎖，此時這個核就會陷入饑餓狀態，即一直處于搶鎖狀態而無法執行后面的程序。

圖1表示了饑餓的例子，圖中三個核都要爭搶同一個自旋鎖，主要有以下幾個過程：

(1)發出鏈接加載指令，取得數據并設置互斥監視器；

(2)如果得到的數據顯示當前沒有上鎖，發出條件存儲指令嘗試獲得鎖；

(3)如果成功獲得鎖，對鎖保護的關鍵區(critical section)進行操作，操作完成后會釋放鎖；

(4)在對關鍵區完成操作后，會執行程序中的其它操作，準備下一次對關鍵區的訪問；

(5)在其它操作完成后，又會再次執行鏈接加載指令，嘗試獲得鎖并訪問關鍵區。

在圖1中核2由于延遲的問題，每次執行條件存儲指令時都被別的核搶先一步獲得鎖而導致執行失敗，導致一直處于鏈接加載-條件存儲的循環之中，始終不能執行下一步的程序，因此處于饑餓狀態。