[發明專利]一種多核環境下基于數組結構的無等待棧操作方法

有效

• 申請號: 201611186222.2
• 申請日: 2016-12-20
• 公開（公告）號: CN106843806B
• 公開（公告）日: 2019-04-26
• 發明（設計）人: 彭亞瓊;郝志宇;劉永繼;李大輝;崔磊
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F9/30
• 分類號: G06F9/30;G06F9/52
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 司立彬

1.一種多核環境下基于數組結構的無等待棧操作方法，其步驟為：

1)主程序初始化代表棧的全局數組，即分配一個包含N個數組元素的段；其中，每個數組元素包含用于存儲入棧數據的變量val，指向入棧請求的指針push，以及指向出棧請求的指針pop；初始化兩全局共享變量T、pc；其中，T為棧頂索引，pc為指示出棧請求的標識符；

2)啟動m個線程，每個線程th_i維護一存儲自己運行狀態的變量h_i；該變量h_i包含指針next、入棧伙伴指針和出?；锇橹羔?；其中，線程th_i的入棧伙伴指針和出?；锇橹羔樉跏贾赶蚓€程th_i；

3)利用變量h_i中的next指針，將該m個線程的運行狀態鏈接為環狀；

4)該主程序等待接收線程對棧進行操作的請求；當線程th_i對棧進行操作時，如果該線程th_i的操作請求為入棧請求，則該線程th_i執行無等待入棧操作；如果該線程th_i的操作請求為出棧請求，則該線程th_i執行無等待出棧操作；如果該線程th_i的操作請求為棧的銷毀請求，則該主程序首先銷毀棧，然后包括主程序在內的所有線程結束執行；

其中，所述無等待入棧操作為：首先利用比較并交換原子操作，嘗試將入棧數據直接存入棧頂元素的val變量，當存入失敗的次數超過給定閾值P后，會在本線程的運行狀態中公布本次入棧請求；其它線程會在執行無等待出棧操作時，嘗試為該入棧請求指定合適的入棧位置，以協助該入棧請求的完成；

所述無等待出棧操作為：首先讀取棧頂索引，然后從該索引所指的位置開始，朝索引值遞減的方向依次嘗試從相應元素出棧，當出棧失敗的次數超過給定閾值P后，

會在本線程的運行狀態中公布本次出棧請求；其它線程會在執行無等待出棧操作時，

嘗試為該出棧請求指定合適的出棧位置，以協助該出棧請求的完成。

2.如權利要求1所述的方法，其特征在于，該線程th_i執行無等待入棧操作的具體實現方法為：

a)對棧頂索引T進行原子加一，獲取入棧位置索引i；設置變量push_failures，用于記錄將入棧數據v存入全局數組失敗的次數；

b)如果全局數組的當前長度小于i+1，則通過分配多個包含N個數組元素的段，將全局數組的長度擴展為不小于i+1；在全局數組中查找索引為i的元素，并將變量c設置為該元素，然后嘗試將入棧數據v存入元素c的變量val；其中，索引為i的元素指全局數組中第i+1個元素；

c)判斷入棧數據v是否被成功存入元素c的變量val，如果是，則結束本次入棧操作；否則，執行push_failures＝push_failures+1；判斷當前push_failures值是否大于閾值P，如果是，則該線程th_i的運行狀態中公布本次入棧請求r，并將入棧請求r的標識符設置為入棧位置索引i的當前值，執行步驟d)；否則，執行步驟a)；

d)對棧頂索引T進行原子加一，獲取入棧位置索引i；如果全局數組的當前長度小于i+1，則通過分配多個包含N個數組元素的段，將全局數組的長度擴展為不小于i+1；在全局數組中查找索引為i的元素，并將變量c設置為該元素，如果能夠將元素c的指向入棧請求的指針push改為指向該入棧請求r，則將元素c指定為該入棧請求r的入棧位置，否則判斷該入棧請求r是否已有指定元素進行入棧，如果是，則將入棧數據v存入該入棧請求r被指定的入棧元素的val變量中，結束本次入棧操作；如果該入棧請求r沒有指定元素進行入棧，則重復步驟d)。