[發(fā)明專利]一種多核環(huán)境下基于數(shù)組結(jié)構(gòu)的無等待棧操作方法

有效

• 申請?zhí)枺?/td>: 201611186222.2
• 申請日: 2016-12-20
• 公開（公告）號: CN106843806B
• 公開（公告）日: 2019-04-26
• 發(fā)明（設(shè)計(jì)）人: 彭亞瓊;郝志宇;劉永繼;李大輝;崔磊
• 申請（專利權(quán)）人: 中國科學(xué)院信息工程研究所
• 主分類號: G06F9/30
• 分類號: G06F9/30;G06F9/52
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 司立彬

本發(fā)明公開了一種多核環(huán)境下基于數(shù)組結(jié)構(gòu)的無等待棧操作方法。本方法為：1)主程序初始化代表?xiàng)５娜謹(jǐn)?shù)組，即分配一個(gè)包含N個(gè)數(shù)組元素的段；2)啟動(dòng)m個(gè)線程，每個(gè)線程維護(hù)一存儲(chǔ)自己運(yùn)行狀態(tài)的變量h_i；該變量h_i包含指針next、入棧伙伴指針和出棧伙伴指針；3)利用變量h_i中的next指針，將該m個(gè)線程的運(yùn)行狀態(tài)鏈接為環(huán)狀；4)該主程序等待接收線程對棧進(jìn)行操作的請求；如果線程的操作請求為入棧請求，則執(zhí)行無等待入棧操作；如果為出棧請求，則執(zhí)行無等待出棧操作；如果銷毀請求，則該主程序首先銷毀棧，然后包括主程序在內(nèi)的所有線程結(jié)束執(zhí)行。本發(fā)明具有高并行度、低復(fù)雜度，為線程的操作提供無等待的進(jìn)度保障。

技術(shù)領(lǐng)域

本發(fā)明屬于并行算法技術(shù)領(lǐng)域，具體涉及到一種多核環(huán)境下基于數(shù)組結(jié)構(gòu)的無等待棧操作方法。

背景技術(shù)

隨著多核處理器的迅猛普及，計(jì)算機(jī)編程模式由傳統(tǒng)串行編程模式向線程級并行編程模式轉(zhuǎn)變，以發(fā)揮出與核數(shù)量的增長相一致的實(shí)際效果。共享數(shù)據(jù)結(jié)構(gòu)(例如：棧和隊(duì)列)作為線程間通信的常用手段，是多線程應(yīng)用的重要組成結(jié)構(gòu)。為了確保多線程應(yīng)用高效運(yùn)行于多核平臺(tái)，需要設(shè)計(jì)高性能的并發(fā)數(shù)據(jù)結(jié)構(gòu)。此外，進(jìn)度保障是并發(fā)數(shù)據(jù)結(jié)構(gòu)需要提供的另一大特性。并發(fā)數(shù)據(jù)結(jié)構(gòu)通常可分為阻塞和非阻塞這兩大類。如果線程對阻塞數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作，它可能首先需要等待另一個(gè)線程操作的完成。因此，阻塞數(shù)據(jù)結(jié)構(gòu)會(huì)引發(fā)諸如死鎖和優(yōu)先級反轉(zhuǎn)等問題。

非阻塞數(shù)據(jù)結(jié)構(gòu)可以確保被暫停的操作不會(huì)阻塞其它操作，從而避免上述阻塞數(shù)據(jù)結(jié)構(gòu)所帶來的問題。非阻塞數(shù)據(jù)結(jié)構(gòu)提供以下三個(gè)層次的進(jìn)度保障：

無阻礙：保障系統(tǒng)中一個(gè)孤立運(yùn)行的線程能夠在有限步驟內(nèi)完成任意操作；

無鎖：保障系統(tǒng)中若干線程能夠在有限步驟內(nèi)完成任意操作；

無等待：保障系統(tǒng)中每個(gè)線程都能夠在有限步驟內(nèi)完成任意操作。

無等待是并發(fā)數(shù)據(jù)結(jié)構(gòu)可以提供的最強(qiáng)進(jìn)度保障，該特性對于多線程應(yīng)用和操作系統(tǒng)來說彌足珍貴，尤其是當(dāng)它們運(yùn)行于高爭用環(huán)境下的時(shí)候(例如：云計(jì)算環(huán)境)。但是，無等待數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)往往比較復(fù)雜，且性能較低下。例如，當(dāng)前表現(xiàn)最好的無等待棧算法的執(zhí)行速度，甚至低于一種基于結(jié)合技術(shù)的阻塞棧算法。

發(fā)明內(nèi)容

本發(fā)明公開了一種多核環(huán)境下基于數(shù)組結(jié)構(gòu)的無等待棧操作方法，其目的在于保持高效執(zhí)行的前提下，為線程的操作提供無等待的進(jìn)度保障。棧的基本操作包括入棧、出棧、取棧頂元素、判斷空等；其中，僅入棧和出棧操作會(huì)對棧進(jìn)行修改；因此，與現(xiàn)有并行棧算法類似，本發(fā)明僅關(guān)注入棧和出棧操作；本領(lǐng)域的技術(shù)人員容易理解，本發(fā)明經(jīng)過簡單修改就能支持棧的其它操作。

本發(fā)明公開的多核環(huán)境下基于數(shù)組結(jié)構(gòu)的無等待棧操作方法總體流程如下：

(1)主程序初始化代表?xiàng)５娜謹(jǐn)?shù)組，即分配一個(gè)包含N個(gè)數(shù)組元素的段，用于后續(xù)存放入棧數(shù)據(jù)；其中，每個(gè)數(shù)組元素包含用于存儲(chǔ)入棧數(shù)據(jù)的變量val，指向入棧請求的指針push，以及指向出棧請求的指針pop，push和pop的初始值均為0；

(2)設(shè)置初始值為0的全局共享變量T和pc；其中，T為棧頂索引，pc用于指示后續(xù)出棧請求的標(biāo)識符；

(3)啟動(dòng)m個(gè)線程，每個(gè)線程th_i(i＝0,1,2,…,m-1)維護(hù)一個(gè)handle結(jié)構(gòu)類型的變量h_i來存儲(chǔ)自己的運(yùn)行狀態(tài)，該結(jié)構(gòu)還包含指針next、入棧伙伴指針和出棧伙伴指針；其中，每個(gè)線程的入棧伙伴指針和出棧伙伴指針均初始指向本線程；