[發明專利]一種RTOS上的SMP的實時任務調度方法

有效

• 申請號: 201710750443.6
• 申請日: 2017-08-28
• 公開（公告）號: CN107562527B
• 公開（公告）日: 2020-12-18
• 發明（設計）人: 韓輝;徐貴洲;焦進星
• 申請（專利權）人: 北京翼輝信息技術有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京東方匯眾知識產權代理事務所(普通合伙) 11296
• 代理人: 張淑賢

本發明屬于計算機領域，具體涉及一種RTOS上的SMP的實時任務調度算法。一種RTOS上的SMP的實時任務調度算法，包括：S1當實時操作系統中斷完全退出或發生可能引發任務就緒或當前任務休眠的系統調用時，如果CPU?CORE的當前任務休眠，切換當前任務的工作狀態，然后進入步驟S2；S2獲取需要運行的任務，并進入步驟S3；S3任務調度。本發明公開的一種RTOS上的SMP的實時任務調度算法與“優先級位圖”算法相比，使用全局就緒表加CPU?CORE本地就緒表的辦法解決了在SMP上無法達到調度時間為O(1)的硬實時問題，增加了對多核的支持，并使用核間中斷通知調度的方法實現了負載均衡的解決方案。

技術領域

本發明屬于計算機領域，具體涉及一種RTOS上的SMP的實時任務調度方法。

背景技術

RTOS，即實時操作系統，是指當外界事件或數據產生時，能夠接受并以足夠快的速度予以處理，其處理的結果又能在規定的時間之內來控制生產過程或對處理系統做出快速響應，并控制所有實時任務協調一致運行的操作系統。提供及時響應和高可靠性是其主要特點。在實時操作系統中必然存在著若干個實時任務，這些任務通常與某些個外部設備相關，能反應或控制相應的外部設備，因而帶有某種程度的緊迫性。根據其緊迫性的程度，人為地給這些任務定一個優先級，任務的緊迫性程度越高，則其優先級越高。

實時操作系統需要從所有任務中選擇一個處于就緒態的優先級最高的任務出來運行，選擇算法就是其調度算法。

為了保證實時性，實時操作系統的調度算法的時間復雜度必須是O(1)，即與參與調度的任務數目、CPU負載無關，是一個常數。否則任務調度的時間就不是一個確定的值，就無法保證在一定時間限制內完成特定功能，就無法稱之為實時操作系統。

一般的實時操作系統都采用一種稱為“優先級位圖”的算法來作為其調度算法，這種“優先級位圖”算法有一個特點，就是通過時間復雜度為O(1)的位圖查找算法查找出優先級位圖中標記的最高優先級的就緒態任務。

但在SMP(對稱多處理器)的機器上，這種“優先級位圖”算法就不能采用了，因為SMP的機器能同時運行多個處于就緒態的任務，實時操作系統的調度算法不僅要選出一組(處理器邏輯核心個數的)高優先級的就緒態任務，還需要處理SMP上的負載均衡等問題。

因此，如何在SMP的機器上實現一種調度時間為O(1)的硬實時負載均衡多核任務調度算法，成為目前亟待解決的問題。

發明內容

本發明的目的是：提供了一種RTOS上SMP的實時任務調度方法，能夠實現調度時間為O(1)的硬實時負載均衡多核任務調度。

技術方案：一種RTOS上的SMP的實時任務調度方法，包括：

S1當實時操作系統中斷完全退出或發生可能引發任務就緒或當前任務休眠的系統調用時，如果CPU-CORE的當前任務休眠，切換當前任務的工作狀態，然后進入步驟S2；

S2獲取需要運行的任務，并進入步驟S3；

S3任務調度。

進一步地，步驟S2包括以下步驟：

S201判斷CPU-CORE當前任務能否調度，若CPU-CORE當前任務能調度，進入步驟S202，反之，則進入步驟S3；

S202判斷CPU-CORE當前任務是否產生優先級卷繞，若CPU-CORE當前任務產生優先級卷繞，進入步驟S203；反之，進入步驟S3；

S203判斷CPU-CORE是否有候選任務，若CPU-CORE沒有候選任務，進入步驟S204，若CPU-CORE有候選任務，進入步驟S205；

S204更新CPU-CORE候選任務，然后進入步驟S210；