[發(fā)明專利]一種多核實時操作系統(tǒng)多個就緒任務快速查找及調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410042680.3
• 申請日: 2014-01-29
• 公開（公告）號: CN103729480B
• 公開（公告）日: 2017-02-01
• 發(fā)明（設計）人: 蔣建春;孟凡迪;何兵;曾素華;邱寶梅;鄧露;王開龍;陳慧玲
• 申請（專利權(quán)）人: 重慶郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 重慶華科專利事務所50123
• 代理人: 康海燕

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

本發(fā)明涉及嵌入式系統(tǒng)多核實時操作系統(tǒng)調(diào)度技術(shù)領(lǐng)域。

背景技術(shù)

隨著微電子技術(shù)的發(fā)展，對稱同構(gòu)多核處理器(SMP-symmetrical?multi-processingprocessor)被廣泛應用于嵌入式系統(tǒng)領(lǐng)域。隨著信息技術(shù)，尤其是通信技術(shù)和物聯(lián)網(wǎng)技術(shù)的發(fā)展，實時嵌入式系統(tǒng)已經(jīng)成為計算機系統(tǒng)的主流。未來實時嵌入式系統(tǒng)的一個顯著趨勢就是應用復雜度將不斷提高。例如在通信領(lǐng)域，無論實在通信基礎設施，還是在終端設備中，運算需求都在不斷提高。而這類系統(tǒng)對時間可預測性、高可信、低功耗等方面的苛刻要求也從未降低。還有車聯(lián)網(wǎng)領(lǐng)域，特別是智能車輛的發(fā)展，車輛互聯(lián)及通信是未來車聯(lián)網(wǎng)的發(fā)展趨勢。車載終端不僅需要處理車聯(lián)網(wǎng)信息、車載媒體信息，還需要實時處理車輛自身的傳感信息，如視頻監(jiān)控、控制等。要同時完成如此多的功能，滿足實時性要求，傳統(tǒng)的單核處理器已經(jīng)無法解決上述矛盾。多核處理器在一個芯片上集成多個處理核心，通過挖掘應用的任務級并行性和數(shù)據(jù)級并行性，能夠在單位功耗和體積上，提供更大的計算能力。因此，多核處理器應用于未來的實時系統(tǒng)已經(jīng)成為不可逆轉(zhuǎn)的趨勢。

隨著多核處理器的發(fā)展，對軟件開發(fā)有非常大的影響，而且核心的瓶頸在軟件上。只有與多核硬件相適應的軟件，才能真正地發(fā)揮多核的性能。多核對軟件的要求包括對多核操作系統(tǒng)的要求和對應用軟件的要求，特別是多核操作系統(tǒng)的性能。在嵌入式系統(tǒng)中,隨著多核處理器應用的日益廣泛,一些主流的嵌入式系統(tǒng)廠商也逐漸開始提供一些基于多處理器構(gòu)架的實時操作系統(tǒng)解決方案。為了充分利用處理器的性能，有很多嵌入式操作系統(tǒng)也提供了多核管理與調(diào)度的功能，如Linux、Vxworks、QNX等操作系統(tǒng)。

多核嵌入式操作系統(tǒng)構(gòu)架設計主要有兩種：一種是主從式構(gòu)架結(jié)構(gòu)，另一種是對稱式構(gòu)架結(jié)構(gòu)。主從式多核操作系統(tǒng)根據(jù)多核處理器的功能把內(nèi)核分成主核和從核，由于從核中只有局部調(diào)度器，需要向主核請求處理，任務的激活與運行需通過主核來進行調(diào)控，由主核決定任務的分配。這種結(jié)構(gòu)的操作系統(tǒng)容易造成從核在等待主核指令的過程中時間的浪費，降低了任務調(diào)度的實時性；同時這種結(jié)構(gòu)隨著處理器核的增加，要求主核管理的資源、任務調(diào)度、事件處理、通信管理等對象也增多，主核負載的增加，將導致主核不能實時有效處理這些事件，成為性能提高的瓶頸。而對稱式構(gòu)架是采用相同的結(jié)構(gòu)來設計操作系統(tǒng)，每個處理器核中訪問同一個操作系統(tǒng)內(nèi)核，特別是在內(nèi)核任務通信與同步、共享資源管理等部分。這種結(jié)構(gòu)的操作系統(tǒng)由于結(jié)構(gòu)較單一，便于系統(tǒng)設計實現(xiàn)。但是由于多個處理器訪問同一個內(nèi)核，需要互斥等待訪問內(nèi)核，降低了內(nèi)核的訪問速度。

嵌入式實時操作系統(tǒng)對調(diào)度時間、任務響應速度都有較高的要求。就緒任務，特別是實時性要求較高的任務要求較短的時間內(nèi)的得到響應和調(diào)度。這就要求調(diào)度算法具有簡單快速的特點。當前支持多核處理器的實時操作系統(tǒng)并不是很多，以Vxworks、QNX較為典型。Vxworks和QNX操作系統(tǒng)對SMP處理器的支持，采用一個操作內(nèi)核對多個處理器核進行管理，采用自旋鎖防止訪問沖突，這種結(jié)構(gòu)會造成多核處理器的訪問內(nèi)核時的互斥，降低了內(nèi)核訪問的并行性，從而降低了多核的性能。隨著處理器技術(shù)和存儲器技術(shù)的發(fā)展，存儲空間對于實時操作系統(tǒng)來說不再是主要考慮的問題。

在多核實時操作系統(tǒng)中，多就緒任務的查找在高優(yōu)先級任務的選擇方法是調(diào)度器設計的重點之一，如何快速的查找到就緒任務，觸發(fā)調(diào)度內(nèi)核的快速響應并及時調(diào)度是多核實時操作系統(tǒng)調(diào)度器設計的重點。當前支持多核的嵌入式操作系統(tǒng)大多采用主從式加隊列的方式進行的，由一個主核管理整個系統(tǒng)任務，在各個從核中建立局部隊列。主核根據(jù)從核的負載情況動態(tài)地分配任務到從核隊列中，供從核運行。這種方法只適合于一般的非實時系統(tǒng)。對于實時操作系統(tǒng)來說，需要快速響應優(yōu)先級較高的任務，盡量減少等待時間。對于當前多核實時操作系統(tǒng)的高優(yōu)先級就緒任務查找方法，雖然大多算法復雜度為O(1)。但是在查找過程中的實現(xiàn)步驟較多，隨著任務的增加，其查找時間也隨之上升。這種方法對于一個要求較高的實時系統(tǒng)來說，調(diào)度時間具有不確定性。