[發明專利]一種多核系統中多線程調度方法、裝置及設備有效
| 申請號: | 202011046367.9 | 申請日: | 2020-09-29 |
| 公開(公告)號: | CN111897647B | 公開(公告)日: | 2021-01-26 |
| 發明(設計)人: | 曹東剛;薛棟梁;麻志毅;陳曦;李克勤;梅宏 | 申請(專利權)人: | 杭州未名信科科技有限公司;浙江省北大信息技術高等研究院 |
| 主分類號: | G06F9/48 | 分類號: | G06F9/48;G06F16/22;G06F16/2458 |
| 代理公司: | 北京辰權知識產權代理有限公司 11619 | 代理人: | 劉廣達 |
| 地址: | 311200 浙江省杭州市蕭*** | 國省代碼: | 浙江;33 |
| 權利要求書: | 查看更多 | 說明書: | 查看更多 |
| 摘要: | |||
| 搜索關鍵詞: | 一種 多核 系統 多線程 調度 方法 裝置 設備 | ||
1.一種多核系統中多線程調度方法,其特征在于,所述方法包括:
根據各線程的前后依賴關系建立有向無環圖DAG圖,并根據各個核的就緒隊列中的線程創建線程運行表、同一時間片運行同一臨界區的沖突線程表及需要執行相同臨界區的線程隊列;
根據各個核的就緒隊列中線程的運行變化,更新線程運行表、沖突線程表、線程隊列及DAG圖;
在所述DAG圖有更新時,檢測所述DAG圖的入節點并將入節點的線程添加到全局就緒隊列;
根據線程運行表和沖突線程表統計所有時間片運行的線程個數,并利用線程個數和時間片數量計算多核系統的線程并行度;
若所述線程并行度小于閾值,則根據線程運行表、沖突線程表及線程隊列為全局就緒隊列中的線程分配核和時間片,以得到新分配方案;
根據新分配方案,將全局就緒隊列中的線程分配到相應核的就緒隊列中,以按照新分配方案調度運行;
其中,所述根據各個核的就緒隊列中線程的運行變化,更新線程運行表、沖突線程表、線程隊列及DAG圖,包括:
當有線程運行完包含的一個臨界區時,從該臨界區的線程隊列中刪除該線程,檢測該線程要運行的下一個臨界區,并將該線程添加到下一個臨界區的線程隊列中,并從下一個臨界區的線程隊列中的其他線程獲取與該線程沖突的線程后更新到沖突線程表中;
當有線程運行完時,該線程占用的時間片空出,從該線程所屬核包含的其他線程中選取優先級最高的線程,并將空出的時間片分配給優先級最高的線程,并在線程運行表中更新優先級最高的線程占用的時間片,若優先級最高的線程有新的線程沖突產生,則更新到沖突線程表中,同時將該線程從線程運行表、沖突線程表、線程隊列及DAG圖中刪除;
所述根據線程運行表、沖突線程表及線程隊列為全局就緒隊列中的線程分配核和時間片,以得到新分配方案,包括:
從需要執行相同臨界區的線程隊列中選取一個長度最長的線程隊列;
將線程運行表中的線程數量和全局就緒隊列中的線程數量相加得到需要分配的線程總數;
從所述線程總數與核的數目之間的商和選取的線程隊列的長度值中選取最大值作為新時間片的數量;
按照預設規則將線程運行表中記錄的各個線程占用的時間片和所屬核的信息復制到一個新建的表中;
針對全局就緒隊列中的每個線程,將該線程加到該線程要運行的第一個臨界區的線程隊列中,并從新時間片中選取一個該線程隊列中其他線程未占用的時間片分配給該線程,再選取一個核分配給該線程,所選取的核包含的該時間片還未分配線程,將該線程和分配的核和時間片添加到新建的表中;
若新時間片的數量為選取的線程隊列的長度值,則將每個核中剩余未分配的時間片分配給核中優先級最高的線程,并更新新建的表中記錄的優先級最高的線程占用的時間片,進而將新建的表中記錄的各個線程占用的時間片和所屬的核作為新分配方案。
2.根據權利要求1所述的方法,其特征在于,所述利用線程個數和時間片數量計算多核系統的線程并行度,包括:
將所述線程個數除以所述時間片數量,得到每個時間片上要運行的平均線程數,將該平均線程數作為線程并行度。
3.根據權利要求1所述的方法,其特征在于,所述按照預設規則將線程運行表中記錄的各個線程占用的時間片和所屬核的信息復制到一個新建的表中,包括:
針對線程運行表中記錄的占用一個時間片的線程,若該時間片屬于新時間片,則將該線程對應的時間片和所屬核的信息完全復制到新建的表中,否則,將該線程添加到全局就緒隊列中,以等待之后進行分配;
針對線程運行表中記錄的占用一個以上時間片的線程,若該線程在沖突線程表中有記錄,則從占用的一個以上時間片中,選取一個屬于新的時間片且與沖突線程占用的時間片不同的時間片,并將選取的時間片、該線程及所屬核的信息復制到新建的表中,并更新沖突線程表。
4.根據權利要求1所述的方法,其特征在于,所述選取一個核分配給該線程,包括:
從該線程要運行的第一個臨界區的線程隊列中其他線程所屬的核中,選取一個該時間片未分配線程的核分配給該線程;
若其他線程所屬的核包含的該時間片均分配了線程,則再從其他的核中,選取一個該時間片未分配線程的核分配給該線程。
該專利技術資料僅供研究查看技術是否侵權等信息,商用須獲得專利權人授權。該專利全部權利屬于杭州未名信科科技有限公司;浙江省北大信息技術高等研究院,未經杭州未名信科科技有限公司;浙江省北大信息技術高等研究院許可,擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作,請聯系【客服】
本文鏈接:http://www.17sss.com.cn/pat/books/202011046367.9/1.html,轉載請聲明來源鉆瓜專利網。





