[發明專利]減少CPU占用的多處理器上實時任務集資源預留方法

有效

• 申請號: 201310199824.1
• 申請日: 2013-05-24
• 公開（公告）號: CN103257900A
• 公開（公告）日: 2013-08-21
• 發明（設計）人: 吳以凡;趙備;高志剛;戴國駿
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 杜軍

技術領域

本發明屬于嵌入式實時操作系統技術領域，特別是涉及一種以減少CPU占用為目標的面向多處理器的實時任務集資源預留方法，以適應嵌入式多處理器平臺對節能和散熱控制的實際需要。

背景技術

現代嵌入式實時操作系統中程序的功能和復雜度不斷提升，通常由包含多個不同特性軟、硬實時任務的混雜程序集構成，互相競爭資源使用權。尤其在開放系統中，由于第三方應用程序的時間參數通常是不確定的，且可以隨時到達或離開，使得資源占用具有極大的波動性。因此，隔離實時任務以防其互相干擾成為至關重要的設計準則，而資源預留是解決該問題的重要手段之一。資源預留技術使用伺服器機制，為每個任務的計算需求預留一定量的資源（CPU占用時間），該任務在實際運行時無法獲得超過預留額度的資源。通過資源預留，硬、軟實時任務甚至非實時任務可共存于同一系統，而不會互相干擾，從而實現任務間的時間隔離。

資源預留機制在單處理器上已較為成熟。然而，漏電、功耗及散熱等物理瓶頸限制了單位面積晶體管數量的繼續增加，處理器設計由單純追求主頻提升轉向綜合考慮計算、能耗等各方面因素。多處理器在節約成本，控制功耗、電磁兼容（EMC）等方面的優勢使其成為嵌入式計算平臺的必然趨勢。在多處理器平臺上，資源預留的研究和相關技術仍處于起步階段。通常的做法是將實時操作系統中的程序以實時任務集的形式在多處理器上進行劃分，并為所得到的各任務子集預留一定量的資源（CPU占用時間），之后通過實時操作系統調度實現各任務子集的并行執行。

已有的關于并行程序在多處理器上劃分的技術，主要考慮如何獲得可行的調度方案，或者最小化總調度時長（Makespan），而并沒有考慮如何優化資源使用率。隨著嵌入式多處理器平臺在實際應用中的不斷發展，為應對節能和散熱控制的切實需要，優化計算資源利用率越來越成為系統設計的最重要因素之一。因此，對于實時任務集在多處理器上的劃分，應使其在滿足時間約束的情況下，最小化CPU占用率，這在嵌入式系統和移動設備上尤為重要。

當前，實時任務集在多處理器上優化分割的相關技術還較少。Baruah和Fisher提出一種將偶發實時任務劃分到多處理器上的方法，但并沒有考慮任務間的先后次序約束。Schranzhofer等人以最小化平均能耗為目標，提出了一種將任務劃分到多處理器平臺的方法，但并沒有考慮任務的實時性。盧宇彤等人提出了一種將并行任務分配到多核處理器的映射算法，但其主要考慮的是Cache的劃分，而沒有考慮任務間的數據通信開銷，而后者對于多處理器平臺是至關重要的。Li等人提出一種將實時事務劃分到多處理器的方法，其目標是在保證實時性的同時最小化系統工作量及處理器占用數。該方法主要針對實時數據庫中實時事務的劃分，而不是通用的實時并行程序。

將實時程序劃分到多處理器上，也即是將實時程序分割到一組可并行執行的處理單元，因此可以參考實時程序在分布式系統劃分方面的技術研究。Peng和Shin使用任務圖表示周期性實時任務，并使用分支限界法將其劃分到分布式系統上，所得的分割方案最小化任務的響應時間。Ramamritham提出一種將周期性任務劃分到分布式系統的啟發式搜索方法，并將任務優先次序、任務間通信開銷、以及任務重復度等綜合考慮。Abdelzaher和Shin考慮將大型實時程序劃分到異構分布式系統的問題，按照將處理器、實時任務分別聚類再匹配的思想，提出了一種啟發式方法，具有較好的可伸縮性。上述方法主要考慮是否能找到可行調度，或最小化任務的響應時間，普遍沒有將資源最優利用作為性能目標。

現有研究通常使用帶次序約束的子任務集來表示實時程序的內在并行性。而將一組有次序約束的任務劃分到多處理器的問題，已被證明是NP完全問題。相關研究提出的啟發式算法主要可分為兩類。一類是列表調度（List?Scheduling）方法。該類方法核心思想是：首先將任務按優先級排序，然后依次選擇優先級最高的任務放置到最合適的處理器上；另一類是基于關鍵路徑（Critical?Path）的方法。該類方法考慮任務間的通信開銷，以最小化任務圖的關鍵路徑長度為目標進行程序劃分。上述這些方法的主要目標是縮小總調度時長，而非優化資源利用率。

Buttazzo等人提出了一種優化分割方法，將帶次序約束的實時程序劃分到多核處理器上，既保證程序的實時性要求，又最小化處理器帶寬的總占用率。但該方法并未考慮任務間的數據通信開銷，在實際應用中有較大局限性，僅能在如采用共享內存的多核平臺等情況下才能使用。

發明內容