可調度性確定方法和實時系統的製作方法

2023-10-06 08:02:04

專利名稱：可調度性確定方法和實時系統的製作方法
技術領域：
本發明涉及一種實時系統，其在多個處理器中通過實時調度執行多個周期性任務。
背景技術：
實時系統是一種通過時間約束的計算機系統，即，「任務的處理必須在設置用於該任務的時間限制內完成」。通常，對於每個任務設置的時間限制被稱作「截止時間」，由該截止時間未完成的任務處理被稱作「截止時間錯過」。在實時系統中截止時間錯過不應該出現。
該實時系統的典型實例是空中交通管制系統、工廠控制監控系統和醫療系統。例如，空中交通管制系統在飛機之間和在飛機和障礙物之間設置一個安全間隔，以便避免任何的碰撞。給出確定是否飛行器將在1秒、2秒任務處理內彼此碰撞的任務是無用的。該空中交通管制系統必須在嚴格的時間的限制之下運行。在嚴格的時間的限制之下操作一個設備，以便防止任何的截止時間錯過被稱作「實時調度」，其包括以下的二種方法1、調度方法2、實時可調度性確定方法下面將首先解釋該調度方法。由「檢測飛行器碰撞的處理」代表的任務是通過安裝在該實時系統上有限數量的處理器執行的。由於一個處理器一次僅僅可以處理一個任務，當存在多個要由該實時系統處理的任務的時候，這些任務被在有限數量的處理器之間以時間劃分共享，並且定時、處理器和要執行的任務被調度。這種方法在本說明書中將被稱作調度方法。
下面將接著解釋該實時可調度性確定方法。為了在嚴格的時間的限制之下操作該實時系統，以便防止任何的截止時間錯過，不可接受超出該系統性能的任務。由於這個緣故，當一組任務和調度方法，並且該給出的任務是通過該調度方法調度的時候，該實時系統確定是否可以觀察到所有任務的該時間的限制(是否存在截止時間錯過)，並且基於該確定結果判定由該系統接受的任務。這個確定方法將被稱作實時可調度性確定方法。
是否可以觀察到任務的時間約束取決於該任務，並且同時取決於該調度方法。當對執行任務說來是必需的總的性能比該實時系統的性能低得多的時候，在大多數情況下，不考慮該調度方法，該系統可以沒有任何截止時間錯過執行任務。與此相反，如果對執行任務說來是必需的總的性能超過該實時系統的性能，該系統不能通過任何的調度方法防止截止時間錯過。但是，當對於執行任務說來是必需的總的性能等於或者略微地低於該實時系統的性能的時候，該調度方法判定是否該系統可以沒有任何的截止時間錯過或者存在截止時間錯過執行任務。為了對付這二種情況，按照該實時可調度性確定方法，二個輸入，即，一組任務和調度方法被輸入，並且確定是否實時調度是可能的或者不可能的結果被返回。
如果一個發出新任務的請求抵達該實時系統，該系統執行以下的步驟。首先，該系統確定是否當該新任務被接受的時候，在該實時系統中處於執行之中的該新任務和所有的任務的時間的限制可以通過該調度方法(不存在截止時間錯過)觀察到。如果是這樣的話，該實時系統接受該新任務的發出。
其次，該實時系統通過使用調度方法調度在該實時系統中處於執行之中的該新任務和所有的任務，並且按照該調度的結果執行該任務。
在該調度方法中，重要的是以恰當的周期分配恰當的處理器給恰當的任務，以便不引起任何的截止時間錯過執行每個任務。通過調度用於每個任務的處理器實現沒有任何的截止時間錯過的任務執行，以便通過該時間限制完成該任務的過程。
周期性任務調度方法的具體例子是EDF(最早的截止時間開始)算法(例如，參見參考文件1)。該EDF算法是一種優先地分配處理器一個在及早的時間上及早的截止時間的任務。
一種該實時可調度性確定方法已知的例子是通過該EDF算法(例如，參見參考文件2)確定是否實時調度是可能的方法。
另一種已知的實時可調度性確定方法的例子是通過實際地使用該調度方法，並且在任務的所有周期中檢查是否不存在截止時間錯過，實質上調度任務的方法(例如，參見參考文件3)。
在參考文件2中描述的該確定方法假定，可同時地分配給一個任務的處理器的數目是一個，並且不考慮一個任務同時地需要多個處理器。某些任務同時地需要多個處理器以便提高處理的效率。因此，必須提供一種甚至當多個處理器需要同時地分配給一個任務時可利用的可調度性確定方法。此外，在參考文件2中描述的該確定方法可以確定實時調度是不可能的，雖然實時調度實際上是可能的，並且這個方法的確定精確性是低的。
通過實際上使用該調度方法和檢查是否在任務的所有周期中不存在截止時間錯過，實質上調度任務的方法花費長的計算時間用於確定，並且是不實際的。
通常地，當多個周期性任務是由多個處理器執行的時候，其不能以高速精確地確定是否實時調度是可能的。
已經提出本發明以克服常規的缺點，並且把其目的作為是提供一種可調度性確定方法，該方法能夠精確地以高速確定是否多個周期性任務可以被在多個處理器上實時調度，和使用該方法的實時系統。
J.W.S.Liu，「Real-Time Systems」，Prentice Hall，2000[參考文件2]T.P.Baker，「An Analysis of EOF Schedulability on aMultiprocessor」，FSU計算機科學技術報告TR-030202，2003[參考文件3]J.F.Hermant等等，「Real-Time Fixed and DynamicPriority Driven Scheduling Algorithms原理和經驗」，Inria技術報告，1996年。

發明內容
按照本發明的第一個方面，該實時系統包括多個處理器，用於執行多個周期性任務的作業，所述周期性任務每個具有預定的周期；將在每個任務的周期內的每個作業分配給該處理器；在分配的作業被在該處理器中執行期間計算分配的執行時間；基於該分配，確定是否該作業的每個在一個在該周期內的截止時間之前完成；當該作業的一個被確定不在該截止時間之前完成的時候，確定調度是不可能的；確定是否每個確定在該截止時間之前完成的作業的執行時間的分配收斂；和當該分配收斂的時候，確定調度是可能的。
按照本發明的第二個方面，該實時系統確定是否在所述任務的釋放時間當中，在最近的釋放時間之後存在網格時間，該網格時間的每個是一個時間點，在其上該任務的周期開始時間相互重合；當該網格時間存在並且由第二網格時間分配的作業被確定去由其截止時間完成的時候，確定調度是可能的；和當該網格時間存在並且由第二網格時間分配的一個作業被確定不由其截止時間完成的時候，確定調度是不可能的。


圖1是一個示出按照第一個實施例的實時系統結構例子的方框圖；圖2是一個用於解釋可調度性確定過程略述的圖；圖3是一個示出周期性任務的具體例子的時間圖；圖4是一個示出周期性任務的參數信息例子的表；圖5是一個示出當二個任務(任務A和B)被使用該EOF算法調度的時候的作業執行模式的圖；圖6是一個用於解釋輸入的圖；圖7是一個用於解釋按照第一個實施例的實時可調度性確定過程(第一可調度性確定過程)的流程圖；圖8是一個更詳細地示出在圖7中的該實時可調度性確定過程的流程圖；圖9是一個用於解釋按照第一個實施例的另一個實時可調度性確定過程(第一可調度性確定過程)的流程圖；圖10是一個用於解釋輸入單調性的圖形；圖11是一個示出按照第二個實施例的實時系統結構例子的方框圖；圖12是一個用於解釋網格和網格時間的時間圖；圖13是一個用於解釋按照第二個實施例的實時可調度性確定過程(第二可調度性確定過程)的流程圖；圖14是一個用於解釋按照第一個實施例的實時系統的處理操作略述的流程圖；和圖15是一個用於解釋按照第二個實施例的實時系統的處理操作略述的流程圖。
具體實施例方式
在下面將參考伴隨的附圖的若干視圖來描述本發明的優選實施例。
第一個和第二個實施例在下面將描述一種實時系統，其在多個處理器中實時調度多個周期性任務。
圖1是一個示出按照本發明第一個實施例的實時系統結構例子的方框圖。該實時系統例如是一種用作嵌入式系統的計算機系統，並且在其時間的限制之下實時執行多個任務。
該實時系統包括一個MPU(主處理單元)1、多個(在這種情況下，例如，三個)VPU(多用途處理單元)2a至2c(如果它們不需要被區別，被稱為VPU 2)、總線3、共用存儲器4、I/O(輸入/輸出)控制器5和I/O設備6。
MPU 1、VPUs 2、共用存儲器4和I/O控制器5被經由該總線3彼此相連接。
該MPU 1是一個主處理器，其控制該實時系統的操作，並且執行一個存儲在該共用存儲器4中的作業系統(OS)10。每個VPU 2是一個處理器，其在該MPU 1的管理之下執行各種各樣的處理。多個需要實時操作的任務被在該VPUs 2中執行。這些任務的每個同時地需要一個或者多個處理器。該作業系統10實時分配給每個任務一個或者多個VPUs。
該作業系統10包括一個實時可調度性確定程序10a和調度程序10b。該程序10a和10b被該MPU 1執行，以導致該計算機系統去執行實時可調度性確定功能(在下文中，也簡單地被稱為可調度性確定功能)和調度器功能。
該實時可調度性確定功能執行確定是否多個周期性任務的可調度性確定處理，該需要實時操作的該多個周期性任務可以被在該VPUs 2中通過使用例如該EDF算法來實時調度。該可調度性確定處理的每個步驟被在該可調度性確定程序10a中描述。該可調度性確定處理在該共用存儲器4中產生作業執行時間表，同時由該調度程序10b執行調度。其基於該時間表確定是否實時調度是可允許的。
如果其確定該實時調度是可允許的，該調度器功能實際上在該VPUs 2中通過使用例如該EOF算法來調度多個任務。如上所述，該EOF算法優先地分配處理器一個在及早的時間上及早截止時間的任務。一種用於執行該調度器功能(例如，一個基於其優先權調度多個任務的算法，類似該EOF算法)的算法被在該調度程序10b中描述。
當例如一個執行某個應用程式的請求被發出的時候，該可調度性確定處理被執行。例如，當檢測到一個來自該計算機系統的輸入/輸出設備(I/O設備6)(例如連接到該總線3)的請求，或者例如，由該作業系統(OS)10按照應用程式的執行檢測到一個「中斷」請求執行新的應用程式(新任務)的時候，該實時可調度性確定程序10a被該MPU執行。
圖14是一個當在圖1的該計算機系統中，例如檢測到一個執行某個應用程式(新任務)的請求的時候，用於解釋處理操作的流程圖。
如果檢測到一個執行新的應用程式(新任務)的請求(步驟S101)，新任務的參數信息包括充當該新任務的執行開始時間的該任務的釋放時間，用於周期性地執行該任務的循環時間(或者一個周期)，用於執行該任務的處理器的數目(供使用的處理器的數目)，每個循環時間要處理的作業的處理時間，和每個循環時間從處理作業開始到該處理時間的完成的允許時間(截止時間)被加載進在該共用存儲器4中用於OS 10的執行預先劃定的工作區中。因此，如圖4所示的參數信息被存儲在該工作區中，用於在新的應用程式中包含多個任務(新任務)的任務集的每個任務，和用於在運行應用程式中的多個任務。
當加載如圖4所示的該參數信息時，該MPU 1執行實時可調度性確定程序10a(步驟S102)。
如果其確定調度是對於該任務集的每個任務可允許的(在步驟S103，是)，該調度程序10b被執行，並且當調度是對於包含新任務和現有任務的該任務集進行時(步驟S104)，該任務被該VPUs 2a以2c執行。
如果包含新任務和現有任務的該任務集甚至包括一個任務，其被確定很可能產生截止時間錯過，新任務的執行被拒絕(步驟S105)，和該調度器功能在該新的應用程式中沒有調度該任務(新任務)。當該調度程序10b被執行去執行調度時，該VPUs 2a至2c在該運行應用程式中保持執行該任務(步驟S106)。這可以防止預先產生任何的截止時間錯過。
圖2是一個用於解釋該可調度性確定處理略述的圖。
該實時可調度性確定功能接收一組要調度的任務和調度算法。每個任務的任務參數信息被從對應於該任務的應用程式中加載進在該共用存儲器4中的預定的區域中，並且傳送給該OS，即，該MPU 1，其執行該實時可調度性確定程序。該實時可調度性確定功能利用該輸入信息去執行實時可調度性確定過程。該實時可調度性確定功能返回一個確定結果(實時調度是可允許的/實時調度是不可能的)給該OS。該調度器功能基於該確定結果執行調度。
下面將詳細說明在第一個和第二個實施例中的目標任務。該目標任務是一個周期性任務，並且每個任務具有參數信息，包括該釋放時間、該循環時間、供使用的處理器的數目、每個循環時間要處理的作業的處理時間，和從該循環時間開始到該作業完成的允許的時間(截止時間)。每個任務是由每個循環時間多個稱作「作業」的重複性任務執行單元組成的。
對於一個在「釋放時間(release time)」上釋放進該實時系統中的任務，在每個等於該「循環時間」的時間上，該任務的一個新的作業被釋放。當在作業釋放上存在對應於「供使用的處理器的數目」以上的空閒處理器的時候，開始該作業的執行，否則，該作業進入等待狀態。做為選擇，通過懸掛低優先級的運行作業，開始該作業的執行。在該作業釋放時間(該循環時間的開始時間)之後，通過同時地在等於「截止時間」的時間內使用在數目上等於「供使用的處理器的數目」的處理器，每個釋放的作業必須被執行一段等於「處理時間」的時間。通過將該截止時間添加給該作業釋放時間獲得的該時間(利用該時間作業的執行必須完成)將被稱作「絕對截止時間」。當存在多個任務的時候，該釋放時間、循環時間、供使用的處理器的數目、該處理時間和該截止時間可以對於每個任務改變。
圖3示出一個周期性任務的例子，該橫坐標代表時間軸，和該縱坐標代表處理器。在圖3中，一個具有釋放時間「0」、循環時間「100ms」、供使用的處理器的數目「2」、處理時間「50ms」和截止時間「80ms」的任務被在實時系統中執行，其中用於調度可利用的處理器的總數是「3」。
該任務的執行狀態是通過從該任務釋放時間開始的三個周期舉例說明的。在每個循環時間中，具有處理時間「50ms」的作業是通過使用二個處理器同時地執行的。在圖3中，在其上每個作業執行的時間(執行完成時間)落在從作業釋放時間到絕對截止時間(不存在截止時間錯過)的周期內。
下面將解釋由該調度器功能執行的調度方法。通常，當在執行的過程中作業完成或者等待執行的作業被添加的時候，該調度方法在處理器中重複在執行中管理作業的順序和等待執行的作業，在執行的過程中搜索一個空閒處理器或者掛起在作業之中低優先級的作業，並且開始執行在等待執行的作業之中最高優先級的作業。此外，作業、其定時和一個供使用的處理器被調度。
特別是，第一個和第二個實施例採用一種滿足以下條件的調度方法。讓L是在周期性任務集中的所有任務的循環時間的最小的公倍數。屆時任務i1的二個作業j1和j2和任務i2的二個作業j3和j4滿足以下的關係該作業j2的釋放時間-該作業j1的釋放時間
＝該作業j4的釋放時間-該作業j3的釋放時間＝L的整數倍數無論如何去選擇該任務i1的二個作業j1和j2，以及該任務i2的二個作業j3和j4，1、當該作業j1被優先於該作業j3執行的時候，該調度方法優先於該作業j4執行該作業j2。
2、當該作業j3被優先於該作業j1執行的時候，該調度方法優先於該作業j2執行該作業j4。
這些條件將被稱作「與任務的優先級有關的條件」。第一個和第二個實施例僅僅指向一種滿足「與任務的優先級有關的條件」的調度方法。
該EOF算法優先地執行及早截止時間的作業(絕對截止時間)。存在一種具有限制條件的EOF算法，當作業具有相同的絕對截止時間的時候，始終優先地執行的該特定任務的作業是一種滿足以上所述條件的調度方法。就不存在紛擾而言，具有該限制條件的該EOF算法簡單地被稱為一種EOF算法。該EOF算法是滿足「與任務的優先級有關的條件」的該調度方法。
下面將通過作為該調度方法示範該EOF算法描述一種確定是否可以實時調度一組任務的方法。
通過實際上使用該EOF算法和檢查是否在與任務的執行有關的「所有」循環時間中不存在截止時間錯過(檢查是否對於所有的作業不存在截止時間錯過)，實質上調度任務的方法花費長的計算時間用於確定，並且因此是不實際的。
因此，在第一個實施例中，任務實質上是通過實際地使用該EOF算法調度的，並且檢查是否不在任務的所有循環時間中，而是在「某些」及早的循環時間中存在截止時間錯過。通過使用該結果，其確定是否實時調度是可能的。
在這種情況下，雖然該實時可調度性確定程序10a是由該MPU 1執行以實質上調度一組給定的任務，當該作業是由該VPUs 2a至2c執行的時候，計算的分配作業的執行時間包括在每個循環時間中的執行開始時間和執行完成時間，並且如圖5所示的時間表被在該共享存儲器4中產生。這個過程將被稱作模擬。
該可調度性確定過程執行這個模擬，以確定是否實時調度是可能的或不可能的。
當實質上調度的作業是由該VPUs 2a至2c(處理器)執行的時候，該產生的時間表顯示在每個循環時間中分配的作業的執行時間。當作業是由多個處理器執行的時候，執行時間的分配(圖5)將被稱作一個作業執行模式(稍後描述)。
更具體地說，實時可調度性是由以下的方法確定的。在對於一組任務的模擬中，當在執行的過程中作業完成或者在等待執行的過程中新的作業被發出以增加作業的數目的時候，該EOF算法在處理器中重複在執行中管理作業的順序和等待執行的作業，在執行的過程中搜索一個空閒處理器或者掛起在作業之中低優先級的作業，並且開始執行在等待執行的過程中最高優先級的作業。此時，該實時可調度性確定方法還管理在執行的過程中在處理器中的作業，和在等待執行的過程中的作業，並且檢查二個條件1、使L是所有任務的周期的最小的公倍數，通過使用時間間隔L作為準則，該任務的執行模式收斂，和2、是否作業在執行中產生一個截止時間。
嚴格地說，在時間T上該作業執行模式的收斂指的是，以下的條件滿足所有的任務i1、當任務i的作業被在時間t(T≤t)上執行的時候，該任務i的作業也在時間t-L上執行，和2、當該任務i的作業沒有在時間t上執行的時候，該任務i的作業也沒有在時間t-L上執行。
該作業執行模式是在多個處理器中的每個任務作業的執行時間的分配，如圖5所示。注意到，圖5舉例說明一個用於一個處理器的作業執行模式。
按照該實時可調度性確定方法，當由多個處理器執行的作業不產生任何的截止時間錯過並且作業執行模式收斂的時候，其確定在收斂之後無需調度任務，實時調度是可能的。當作業產生一個截止時間錯過的時候，其確定實時調度是不可能的。
下面將解釋一種情況，其中任務A和任務B被使用該EOF算法調度，如圖4所示，任務A具有釋放時間「9.5」、循環時間「2」、供使用的處理器的數目「2」和截止時間「0.4」，和任務B具有釋放時間「0」、循環時間「5」、供使用的處理器的數目「1」、處理時間「3.8」和截止時間「5」。
圖5示出當在圖4中示出的二個任務，即，任務A和B被使用該EOF算法調度的時候的作業執行模式。注意到，圖5示出在一個處理器中每個任務的執行周期。該橫坐標代表時間，並且任務的每個執行周期是由用於每個任務的水平線表示的。第一級示出從時間「0」到時間「20」的任務A和B的執行周期，並且級示出從時間「20」到時間「40」的任務A和B的執行周期。
任務B被在時間「0」上發出，並且作業b1被在任務B的循環時間「5」中對於該處理時間「3.8」執行。在從時間「10」開始的循環時間，作業b3在該循環時間中被分成三個並且被執行。該作業b3在執行開始時間「10」上開始被執行。該作業b3被執行時間「1.5」，在時間「0.4」之後被再次執行時間「1.6」，並且在時間「0.4」之後被再次執行時間「0.7」。該作業b3的執行完成時間是「4.6」。
任務A被在時間「9.5」上發出，並且作業a1被在任務A的循環時間「2」中對於該處理時間「0.4」執行。在那之後，作業a2至a16被每個循環時間「2」對於每個該處理時間「0.4」執行。
任務A和B的循環時間的最小的公倍數L的值是「10」，並且該任務的作業執行模式在時間「20」上收斂。在時間「20」之前，該任務的作業執行模式不收斂。
例如，一旦時間「10」流逝，在任務B的釋放時間「9.5」之後，該任務的作業執行模式在時間「19.5」上不收斂，該時間「10」是任務A的周期「2」和任務B的周期「5」的最小的公倍數。
以這樣的方式，作業執行模式的收斂指的是，該作業執行模式在二個連續的時間間隔(例如，從時間「10」到「20」的第一時間間隔和從時間「20」到時間「30」的第二時間間隔)之間是相同的，在多個任務(在這種情況下，任務A和B)的釋放時間之中的最新的釋放時間(例如，任務A的釋放時間「9.5」)之後，其除以一個對應於所有任務的循環時間的最小的公倍數的時間(例如，任務A和B的循環時間的最小的公倍數「10」)。在圖5中，該作業執行模式在第一和第二時間間隔之間是相同的，並且該任務A和B的作業執行模式在第一和第二時間間隔之間的邊界上在時間「20」上收斂。
在該可調度性確定過程中，該模擬是使用類似該EOF算法的調度算法執行的，該調度算法基於每個任務的優先級分配該任務的作業給多個處理器。因此，該作業執行模式是一種當該處理器基於用於執行該任務的處理器的數目、釋放時間、循環時間、每個循環時間的截止時間、在該任務的每個循環時間中執行作業花費的時間(處理時間)和該任務的優先級，通過使用該調度算法調度在每個任務的每個循環時間中執行作業的時候，在每個處理器中的作業執行模式，其參數被對於每個任務預先設置。
作業不產生任何的截止時間錯過指的是，該作業在從開始時間(作業釋放時間)到循環時間的絕對截止時間的時間(在截止時間內)內完成，在該循環時間期間，該作業被執行。換句話說，該作業的執行完成時間落在直至該絕對截止時間的時間內。
是否該任務的作業執行模式收斂可以被通過計算在下面定義的輸入來確定。
該輸入代表一個在給定時間上未執行的任務的工作負荷(作業)。讓J是一組已經在時間T上從任務i的作業當中釋放的作業。屬於J的作業被劃分為三個類型第一個類型)一個其執行已經在時間T上完成的作業第二個類型)一個在時間T上處於執行之中的作業第三個類型)一個其執行沒有在時間T上開始的作業讓W是用於第二個和第三個類型未執行的工作負荷的總和，該任務i的輸入在時間T上被定義為W。
圖6是一個用於解釋任務A和B的輸入的圖。來自任務A的二個作業ax1和ax2和任務B的二個作業bx1和bx2，其循環時間已經在時間T上開始的作業(釋放的)的集合J是{作業ax1，ax2，作業bx1}。在該作業集合J中的作業被分類為以下。
1、一個其執行已經在時間T上完成的作業作業ax12、一個在時間T上處於執行之中的作業作業bx13、一個其執行沒有在時間T上開始的作業作業ax2在時間T上該作業ax2的未執行的工作負荷是WA，和在時間T上該作業bx1的未執行的工作負荷是WB。由此，1、在時間T上任務A的輸入WA2、在時間T上任務B的輸入WB讓R是在所有任務的釋放時間之中最新的釋放時間，並且L是所有任務的周期的最小的公倍數。因而，當在時間T(R+L≤T)上的輸入值等於在時間T-L上用於所有任務i的輸入值的時候，其被判定在時間T上輸入收斂。當輸入在時間T上收斂的時候，作業執行模式在時間T上收斂。
在圖5中，在時間「9.5」上，任務A的輸入是「0」，並且任務B的輸入是「0」。在時間「19.5」上，任務A的輸入是「0」，並且任務B的輸入是「0.1」。任務B的輸入值是不同的，並且該任務的作業執行模式在時間「19.5」上尚沒有收斂。
相反地，在時間「10」上，任務A的輸入是「0」，並且任務B的輸入是「0」。在時間「20」上，任務A的輸入是「0」，並且任務B的輸入是「0」。這些輸入值是彼此相等的，並且該任務的作業執行模式已經在時間「20」上收斂。
以這種方法，在該任務的釋放時間之中最新的釋放時間(例如，在圖5中的任務A的釋放時間「9.5」)之後，當在其循環時間已經開始的任務的循環時間中，未執行的作業在第一時間(例如，在圖5中的時間「10」)上和第二時間(例如，在圖5中的時間「20」)是相同的時候，作業執行模式可以被確定去收斂，該第一時間和第二時間具有對應於所有任務的循環時間的最小的公倍數的時間差(例如，在圖5中的時間「10」)。
下面將參考圖7的流程圖解釋一種當該調度方法是EOF算法，即，在圖14的步驟S102中的該實時可調度性確定過程的時候，確定是否可以實時調度一組任務的方法。
當檢測到例如，一個執行某個應用程式的請求(請求執行一個新任務)的時候，該可調度性確定過程被執行。在這種情況下，該可調度性確定功能確定是否對於所有的任務存在截止時間錯過，該所有的任務包括在該應用程式中的多個任務(新任務)和在運行應用程式中的多個任務。
當檢測到執行新的應用程式(新任務)的該請求的時候，開始執行該可調度性確定過程。通過使用該調度程序10b，和連續地執行來自最高優先級作業的作業，該模擬被執行去調度所有的任務，該所有的任務包括在該應用程式中的多個任務和在運行應用程式中的多個任務(步驟S201)。
如上所述，該調度算法調度作業、其定時，和通過重複在處理器中在執行中管理的作業和等待執行的作業的順序被用於執行的處理器，當在執行中的作業完成或者等待執行的作業被添加(當新的作業被釋放的時候)的時候，搜索一個空閒處理器或者掛起在執行中的作業之中低優先級的作業，並且由該處理器開始執行在等待執行的作業之中最高優先級的作業。在這種情況下，每當新的作業被按照調度釋放時，其確定在該作業釋放時間上是否輸入收斂。此外，每當處於執行之中的作業完成時，其確定是否該作業產生截止時間錯過。
更具體地說，如果在該模擬(步驟S202)的過程中新的作業被釋放，該流程前進到步驟S205，以確定在該作業釋放時間上是否輸入收斂。如果該輸入被確定不收斂，該流程返回到步驟S201，以按照調度開始執行從高優先級開始的作業的作業。也就是說，當該作業是由多個處理器執行的時候，該作業在循環時間中分配的執行時間被計算。如果處於執行之中的作業完成(步驟S202)，該流程前進到步驟S203，以基於該作業分配的執行時間，確定是否該作業產生截止時間錯過。如果不存在截止時間錯過，該流程返回到步驟S201。
在步驟S203中，如果該作業其完成的執行產生截止時間錯過，其確定實時調度是不可能的(步驟S204)，並且該可調度性確定過程完成。
如果在步驟S205中，在新的作業已經被釋放的時間(釋放時間)上輸入收斂，其確定實時調度是可能的(步驟S206)，並且該可調度性確定過程完成。
如果在步驟S205中輸入收斂，其在步驟S203確定由在該輸入收斂的時間上執行的作業不產生任何的截止時間錯過。
在步驟S203中，如果該作業的執行完成時間落在該絕對截止時間之前的時間內，即，在該作業的釋放時間(該循環時間的開始時間)之後，該作業在該作業的預定的截止時間(在該絕對截止時間之前的時間)內完成，其確定不存在截止時間錯過。如果在步驟S203是否，其確定存在截止時間錯過。
在步驟S205中，在新的作業已經被釋放的時間(作業釋放時間)上，每個任務的輸入被計算，並且從該作業釋放時間開始的該時間領先對應於所有任務的循環時間的最小的公倍數的時間。如果該任務的輸入在二個時間上彼此相等，該輸入被確定收斂，如果它們彼此是不同的，該輸入被確定不收斂。
圖8是一個更詳細地示出在圖7中示出的該可調度性確定過程操作的流程圖。
當檢測到一個執行新任務請求的時候，開始執行該可調度性確定過程。在所有任務的釋放時間之中，該所有任務包括在給定應用程式中的多個任務和在運行應用程式中的多個任務，該最早的釋放時間(最小釋放時間)和最新的釋放時間(最大釋放時間)，以及所有任務的周期的最小的公倍數被獲得，並且分別地定義為Rmin、Rmax和L(步驟S1)。
時間「T」被設置為Rmin，並且生成一個空白執行等待作業表「List」(步驟S2)。
在時間T之後首先釋放的作業i被獲得，並且其釋放時間被定義為Ti。在時間T之後其執行首先完成的作業j被獲得，並且其執行完成時間被定義為Tj(步驟S3)。然後，該流程前進到步驟S4.
在步驟S4中，如果Ti≤Tj(其指的是在該時間上，在時間T之後，被釋放的該作業i立即到達)，該流程前進到步驟S5，如果Ti＞Tj(其指的是在該時間上，該作業j完成立即到達)，該流程前進到步驟S11。
在步驟S5中，(a)該作業i被增加給該執行等待作業表List。(b)如果一個其絕對截止時間比該作業i的絕對截止時間更早的作業存在於處於執行之中的作業中，這些作業的執行被在時間Ti上掛起，該作業被增加給該執行等待作業表List，並且該流程前進到步驟S6。
在步驟S6中，一個在該執行等待作業表List中其絕對截止時間是最早的作業被定義為k，並且該流程前進到步驟21。
在步驟S7中，如果存在一個空閒處理器，其可以在時間Ti上執行該作業k，該流程前進到步驟S8，以從該執行等待作業表List中刪除該作業k，並且開始該作業k的執行(步驟S8)。在那之後，該流程返回到步驟S6。
如果在步驟S7不存在一個可以在時間Ti上執行該作業k的空閒處理器，該流程前進到步驟S9。在步驟S9，其檢查是否在該作業的釋放時間Ti上輸入收斂，在時間T之後該作業被首先釋放(步驟S9)。換句話說，當在其上該作業i已經被釋放的時候，每個任務的輸入被獲得，並且確定該時間優先於該釋放時間一個對應於所有任務的循環時間的最小的公倍數的時間。如果該任務的輸入在二個時間上彼此相等，該輸入被確定收斂，如果它們彼此是不同的，該輸入被確定不收斂。
如果該輸入收斂(在步驟S9，是)，該流程前進到步驟S10，以確定實時調度是可能的，並且該流程完成(步驟S10)。如果該輸入不收斂(在步驟S9，否)，該流程前進到步驟S9′，以更新T為Ti(步驟S9′)，並且返回到步驟S3。
如果在步驟S4Ti＞Tj，該流程前進到步驟S11。在步驟S11，其檢查是否該作業j產生一個截止時間錯過。
更具體地說，在該作業j的釋放時間之後，如果該作業j的執行完成時間落在該作業的預定的絕對截止時間之前的該時間內，其確定不存在截止時間錯過。如果該作業j通過該絕對截止時間沒有完成，其確定存在一個截止時間錯過。
如果該作業j產生一個截止時間錯過(在步驟S11，是)，該流程前進到步驟S12，以確定實時調度是不可能的，並且該流程完成(步驟S12)。如果該作業j不產生任何的截止時間錯過(在步驟S11，否)，該流程前進到步驟S11′，以更新T＝Tj(步驟S11′)，然後返回到步驟S3。
下面將參考在圖9示出的流程圖解釋在圖14的步驟S102中的另一個實時可調度性確定過程。
在圖7和8中示出的該實時可調度性確定過程中，每當按照調度釋放一個新的作業時，其確定在該作業釋放時間上是否輸入收斂。此外，每當處於執行之中的作業完成時，其確定是否該作業產生截止時間錯過。
在圖9中，每當處於執行之中的作業完成時，其確定是否該作業產生一個截止時間錯過，並且是否輸入收斂。在圖9中，與在圖7中相同的參考數字表示同樣的步驟，並且下面將僅僅解釋不同的步驟。
在圖9中，通過使用該調度程序10b，和連續地執行來自最高優先級的作業，該模擬被執行去調度經受可調度性確定的所有的任務(步驟S201)。如果在該模擬中一個新的作業被釋放(步驟S202)，該流程返回到步驟S201。
如果處於執行之中的作業在該模擬中完成(步驟S202)，流程前進到步驟S203，以確定是否該作業產生截止時間錯過。如果該作業不產生任何的截止時間錯過，該流程前進到步驟S205′，以確定是否在該作業的執行完成時間上輸入收斂。
在步驟S203中，如果該完成的作業產生截止時間錯過，其確定實時調度是不可能的(步驟S204)，並且該可調度性確定過程完成。
在步驟S205中，如果在該作業的執行完成時間上輸入收斂，其確定實時調度是可能的(步驟S206)，並且該可調度性確定過程完成。
如果在步驟S205′中輸入收斂，其在步驟S203確定由在該輸入收斂的時間上已經執行的作業不產生任何的截止時間錯過。
在步驟S203中，在該處理的作業的釋放時間(該循環時間的開始時間)之後，如果該作業在該作業(任務)預定的截止時間(在該絕對截止時間之前的時間)內完成，其確定不存在截止時間錯過。如果在步驟S203是否，其確定存在截止時間錯過。
在步驟S205′，每個任務的輸入被該作業的執行完成時間上獲得，並且確定該時間優先於該執行完成時間一個對應於所有任務的循環時間的最小的公倍數的時間。如果該任務的輸入在二個時間上彼此相等，該輸入被確定收斂，如果它們彼此是不同的，該輸入被確定不收斂。
下面將通過以下的證明描述在圖7和9中的該可調度性確定過程的有效性，即，在圖1和9中示出的該可調度性確定過程始終返回一個正確的確定結果(當一組任務可以被實際地實時調度的時候，返回一個確定結果「實時調度是可能的」，或者當一組任務可以不能被實際地實時調度的時候，返回一個確定結果「實時調度是不可能的」)。
下面將證明的是以下的二個命題。
第一個命題)當一組任務可以通過使用該調度算法實時調度的時候輸入收斂。
第二個命題)當一組任務不能通過使用該調度算法實時調度的時候存在截止時間錯過。只有當一組任務不能通過使用該調度算法實時調度時，才存在截止時間錯過。
關於這二個命題，由於第二個命題是顯而易見的，其證明將被省略，並且僅僅將證明該第一個命題。
首先，使CI(i，T)是在時間T上任務i的一個輸入，其將證明關係CI(i，T)≤CI(i，T+L)保持(輸入是單調的)。
該證明是以反證法為基礎的。假定輸入單調性不成立，並且讓T1是滿足CI(i，T+L)＜CI(i，T)最小的T，以及此時i1是i。此外，讓j1是一個在任務i1的作業之中其周期包含時間T的作業，j2是一個在任務i1的作業之中其周期包含時間T+L的作業，並且R1是該作業j1的周期開始時間(釋放時間)。那麼，該作業J2的釋放時間是R1+L。
該CI(i1，T1+L)＜CI(i1，T)保持指的是，在其期間的時間，該作業j2被在時間R1+L和時間T1+L之間執行的時間比該作業j1被在時間R1和時間T1之間執行的更短。也就是說，存在時間T3(R1≤T3≤T1)，其滿足一個條件，即，在從時間R1到時間T1的周期期間，在時間T3上該作業j1不執行，而是該作業J2在時間T3+L(假定時間T3是在滿足這個條件的時間之中「最小的」)上執行。由此，通過正確地選擇任務i3，總有一種情況，其中該任務i3的作業J3被在時間T3上執行，但是該任務i3的作業j4在時間T3+L上不執行，如圖10所示。
該作業j3被在時間T3上執行指的是，該作業j3在優先級方面比該作業j1更高。該作業j4在時間T3+L上不執行對應於1、該作業j4在優先級方面比該作業j2更低，或者2、該作業j4的執行在時間T3+L上完成。
如果該作業j4在優先級方面比該作業j2更低，如上所述的該「與任務的優先級有關的條件」被破壞。如果該作業j4的執行在時間T3+L上完成，CI(i3，T3+L)＜CI(i3，T3)必須保持，其破壞T的最小化。
由此，其證明輸入是單調的。
其將被證明是，當一組任務可以通過使用該調度算法實時調度的時候輸入收斂。
該證明是以反證法為基礎的。假定一組任務可以通過使用該調度算法被實時調度，並且輸入有時不收斂。帶有被證明的輸入單調性的輸入有時不收斂的該假設的組合揭示給定任務的輸入保持增加。這指的是遲早存在截止時間錯過，即，實時調度是不可能的，這是令人失望的。這指的是該假設是錯誤的，並且因此其可以被證明，當一組任務可以通過使用該調度算法實時調度的時候輸入收斂。
由此，在圖7和9中的該可調度性確定過程的有效性被證明。
如上所述，按照第一個實施例，當分配給多個處理器(VPUs 2a至2c)的作業是由這些處理器執行的時候，在該循環時間中分配的執行時間被使用被用於實際調度的該調度算法(調度程序10b)，通過執行該模擬來計算。然後，其通過一個該作業預定的允許時間(絕對截止時間)確定是否每個作業完成。如果在該處理器中對於作業分配(作業執行模式)的執行時間被通過該允許的時間收斂確定完成，調度被確定是可能的。如果獲得一個通過該允許的時間沒有完成的作業(其產生截止時間錯過的作業)，調度被確定是不可能的。
藉助於這種方案，在該任務的作業執行模式被確定收斂以前該模擬被執行，並且調度被確定是可能的。如果檢測到甚至一個產生截止時間錯過的作業，調度被確定是不可能的。因此，可以精確地以高速確定是否實時調度是可能的或者不可能的。
在任務的執行開始時間(釋放時間)之中最新的執行開始時間之後，可以精確地每次儘快地確定是否調度是可能的或者不可能的。
該可調度性確定過程被對於預定的時間執行。當作業執行模式不收斂，並且沒有檢測到一個產生截止時間錯過的作業的時候，一旦預定的時間流逝，其希望地確定調度是不可能的。
(第二個實施例)在第一個實施例中，該可調度性確定過程可以被沒有任何限制應用於確定的每個任務(周期性任務)。但是，當所有任務的截止時間被確定落在該任務的循環時間內的時候，存在一個時間，在其上所有任務的循環時間的開始時間彼此重合，並且上述的時間周期性地出現，在圖7的步驟S205中確定是否輸入收斂可以被省略，並且可以通過確定是否產生截止時間錯過確定是否調度是可能的或者不可能的。
圖11示出一個按照第二個實施例的實時系統結構例子。例如，該實時系統被嵌入在一個計算機系統中。在圖11中，與在圖1中相同的參考數字表示相同的部分，並且下面將僅僅描述不同的部分。在圖11中的OS 10包括對應於在圖1中的實時可調度性確定程序10a的第一可調度性確定程序10a，調度程序10b，和通過簡化第一可調度性確定程序10a準備的第二可調度性確定程序10d，和用於確定將選擇第一和第二可調度性確定程序10a和10d哪一個的確定程序10c。
由MPU 1使用該第一可調度性確定程序10a執行的該第一可調度性確定過程與在圖7或者9中是相同的。當所有任務的截止時間被確定落在任務的循環時間內，並且所有任務的循環時間的開始時間彼此周期性地重合的時候，由MPU 1使用第二可調度性確定程序10d執行的第二可調度性確定過程被執行。
當例如發出一個執行給定的應用程式的請求的時候，由MPU 1使用該確定程序10c執行的確定過程被執行。
圖15是一個當在圖11的該計算機系統中，例如檢測到一個執行給定應用程式(新任務)的請求的時候，用於解釋另一個處理操作的流程圖。在圖15中，與在圖14中相同的參考數字表示同樣的步驟，並且下面將僅僅描述不同的步驟。
在圖15中，步驟S111a至S111c替換圖14的步驟S102。
如果檢測到一個執行新任務的請求(步驟S101)，以上描述的確定過程被執行，以基於包括新任務和現有的任務的所有任務的參數信息(圖4)，檢查是否滿足以下的二個條件(S111a)。
第一個條件)每個任務的截止時間落在該任務的循環時間內。
第二個條件)存在一個時間，在其上所有任務的循環時間的開始時間彼此重合，並且上述的時間周期性地出現。
如果包括新任務和現有任務的所有的任務兩者都滿足第一和第二條件(在步驟S111a中，是)，該流程前進到步驟S111b，以執行第二可調度性確定過程(步驟S111b)。如果在步驟S111a中是否，該流程前進到步驟S111c，以執行第一可調度性確定過程(步驟S111c)。
雖然每個任務的負荷參數信息被存儲在共享存儲器4中，該MPU1執行確定過程和第一和第二可調度性確定過程。
來自步驟S103的過程與在圖14中是相同的。
第一可調度性確定過程與在圖7或者8中的是相同的，其描述將被省略，並且下面將解釋第二可調度性確定過程。
在第二可調度性確定過程中確定的一組任務滿足該第一和第二條件，如上所述。第二可調度性確定過程與第一可調度性確定過程是相同的，其中該模擬使用該調度算法(調度程序10b)實際地進行，在某個及早的周期中(不是在任務的所有周期中)檢查是否存在截止時間錯過，並且使用該檢查結果確定是否實時調度是可能的。但是，這個確定可以通過更簡單、更高速度的方法來進行，因為僅僅確定一組條件是有限的任務。
當所有任務的循環時間的開始時間周期性地彼此重合的時候，如由第二個條件給出的，在其上所有任務的循環時間的開始時間彼此重合的該時間將被稱作「網格時間」。
下面將參考圖12描述第二個條件。圖12的(a)沿著該時間軸(橫坐標)示出一個狀態，其中沒有網格時間的三個一組的任務(任務A、B和C)被在其循環時間中執行。圖12的(b)沿著該時間軸(橫坐標)示出一個狀態，其中具有網格時間的三個一組的任務(任務D、E和F)被在其循環時間中執行。
對於三個任務A、B和C的組，在三個任務的釋放時間之中最新的釋放時間之後，不存在在其上該任務的循環時間的開始時間彼此重合的時間。例如，任務B和C的循環時間同時地起始於時間T1，但是任務A的循環時間不起始於時間T1。任務A和B的循環時間同時地起始於時間T2，但是任務C的循環時間不起始於時間T2。
相反地，如圖12的(b)所示，對於三個任務D、E和F的組，在三個任務的釋放時間之中最新的釋放時間之後，存在一個在其上該任務的循環時間的開始時間彼此重合的時間(網格時間)。例如，三個任務的循環時間同時地起始於時間T3、T4和T5。在圖12的(b)中，第一網格時間是時間T3，第二網格時間是時間T4，和第三網格時間是T5。
基於此，下面將參考在圖13中示出的流程圖解釋第二可調度性確定過程。當所有任務的截止時間被確定落在該任務的周期內，並且周期性地出現一個在其上所有任務的循環時間的開始時間彼此重合的時間(網格時間)的時候，滿足一個屬性「如果作為第二網格時間不存在截止時間錯過，在第二網格時間之後，不存在截止時間錯過」。第二可調度性確定過程利用這個屬性，並且執行如圖13所示的過程。
在圖13示出的第二可調度性確定過程中，當使用該調度程序10b進行調度時，一個模擬被執行。每當處於執行之中的作業在該模擬中完成時，其檢查是否該作業產生截止時間錯過。如果直到從任務的釋放時間「0」測量的時間沒有檢測到一個產生截止時間錯過的作業，確定調度是可能的，該任務被在確定到達第二網格時間的所有任務之中首先釋放。
基於該包含在被確定的每個任務的參數信息中的釋放時間和周期，獲得在其上所有任務的循環時間的開始時間彼此重合的該時間(網格時間)，所有任務包括新任務和現有任務(步驟S51)。
當使用該調度程序10b進行調度時，該模擬被執行。在從在被確定的所有任務之中首先釋放的任務的釋放時間「0」測量的該時間達到第二網格時間以前，該模擬繼續(步驟S52和S53)。
如果在該模擬中一個新的作業被通過第二網格時間釋放(步驟S54)，該流程返回到步驟S52。如果該測量時間沒有達到第二網格時間(在步驟S52中，否)，該模擬再次繼續(步驟S53)。如果一個處於執行之中的作業完成(步驟S54)，該流程前進到步驟S55。
在步驟S55，其檢查是否該作業產生一個截止時間錯過。如果不存在截止時間錯過，該流程返回到步驟S52。
如果在步驟S55中檢測到一個產生截止時間錯過的作業，該流程前進到步驟S56，以確定實時調度是不可能的(步驟S56)。隨後不進行模擬，並且該可調度性確定過程完成。
如果一個新的作業被在該模擬中釋放(步驟S54)，並且當前的時間是第二網格時間，第二網格時間沒有檢測到一個產生截止時間錯過的作業。因此，該過程前進到步驟S57，以確定調度是可能的(步驟S57)。
如上所述，按照第二個實施例，當周期性地出現一個在其上任務的循環時間的開始時間彼此重合的網格時間的時候，如果由多個處理器執行的作業通過該作業(沒有檢測到產生截止時間錯過的作業)允許的時間(絕對截止時間)由第二網格時間完成，確定調度是可能的。如果通過第二網格時間檢測到一個沒有由其允許的時間完成的作業(其產生截止時間錯過的作業)，調度被確定是不可能的。
藉助於這種方案，當相應的任務的預定的截止時間落在該任務的預定的循環時間內，並且該任務的循環時間的開始時間周期性地彼此重合的時候，可以通過利用在網格時間之中的第二網格時間執行該模擬精確地確定是否實時調度是可能的或者不可能的，在該網格時間上該任務的循環時間的開始時間彼此重合。
當一組被確定的任務滿足條件的時候，即，相應的任務的預定的截止時間落在該任務的預定循環時間內，而且該任務具有周期性網格(其中該任務的循環時間的開始時間彼此重合的狀態)，按照第二個實施例簡化的第二可調度性確定過程被執行。如果一組被確定的任務不滿足這個條件，按照第一個實施例的該可調度性確定過程被執行，並且可以按照被確定的任務組的特徵精確地以高速確定是否調度是可能的或者不可能的。特別是，對於一組滿足以上條件的任務，可以以更高的速度確定是否調度是可能的或者不可能的。
通過實際地使用該調度算法，和檢查是否在任務的所有周期中不存在截止時間錯過，執行該模擬的常規方法花費長的計算時間用於確定，並且是不實際的。相反地，按照第一個和第二個實施例，該模擬被實際地使用該調度算法進行，檢查不是在任務的所有周期中而是在某個及早的周期中是否存在截止時間錯過，並且使用該檢查結果確定是否實時調度是可能的或者不可能的。
更具體地說，實時可調度性是由以下的方法確定的。在對於一組任務模擬的過程中，該調度方法重複在處理器中處於執行之中的管理任務的順序和等待執行的任務，當處於執行之中的任務完成或者添加等待執行的任務的時候，搜索一個空閒處理器或者掛起處於執行之中的低優先級作業，並且開始執行處於等待執行之中最高優先級的任務。此時，該實時可調度性確定方法還管理在處理器中處於執行之中的任務，和處於等待執行之中的任務，並且檢查二個條件1、使L是所有任務的周期的最小的公倍數，通過使用時間間隔L作為準則，該任務的執行模式收斂，和2、是否作業在執行中產生一個截止時間。當該任務的執行模式收斂的時候，其確定在收斂之後沒有調度任務，即，實時調度是可能的。如果一個任務產生截止時間錯過，其確定在出現截止時間錯過之後沒有調度任務，即，實時調度是不可能的。
按照第一個和第二個實施例的該實時可調度性確定方法，當給出一組周期性任務和調度方法的時候，可以通過使用該調度方法以高速精確地確定是否可以實時調度周期性任務組。
在第一個和第二個實施例中描述的本發明的方法可以通過將其作為由計算機可執行的程序存儲在，諸如磁碟(軟磁碟、硬碟等等)，光碟(CD-ROM、DVD等等)或者半導體存儲器的記錄介質中來區分。
按照本發明，其可以以高速精確地確定是否在多個處理器中可以實時調度多個周期性任務。
權利要求
1.一種在實時系統中的可調度性確定方法，該實時系統包括多個用於執行多個周期性任務的作業的處理器，所述多個周期性任務每個具有預定的周期，包括準備調度裝置，用於在每個任務的周期中給處理器分配每個作業；在由該調度裝置分配的作業被在處理器上執行期間，計算執行時間的分配；基於該分配，確定是否每個作業在截止時間之前完成；當一個作業被確定在截止時間之前沒有完成的時候，確定調度是不可能的；確定每個被確定在截止時間之前完成的作業的執行時間的分配是否收斂；和當該分配收斂的時候，確定調度是可能的。
2.根據權利要求1的方法，其中，基於所述任務的未執行作業，確定是否分配收斂來確定是否分配收斂，所述任務的未執行作業的周期起始於第一時間點和第二時間點，第一時間點和第二時間點具有對應於所述任務的周期的最小公倍數的時間差，和其中，當在第一時間點上和在第二時間點上的未執行的作業是彼此相同的時候，調度是可能的確定來確定調度是可能的。
3.根據權利要求1的方法，其中，當在二個連續的時間間隔的一個期間的分配和在二個連續的時間間隔的另一個期間的分配是彼此相同的時候，確定是否分配收斂來確定是否分配收斂，在所述任務的釋放時間當中，在最新的釋放時間之後，所述二個連續的時間間隔的每個對應於所述任務周期的最小公倍數。
4.根據權利要求1的方法，其中，該調度裝置按照每個作業的優先級，分配所述每個作業給處理器。
5.根據權利要求1的方法，其中，該調度裝置基於每個作業的截止時間，分配每個作業給處理器。
6.根據權利要求4的方法，其中，當在第一任務的二個作業之間的執行開始時間中的時間差和在第二任務的二個作業之間的執行開始時間中的時間差是所述任務周期的最小公倍數的時候，該調度裝置通過使用調度算法分配每個作業給處理器，該第一任務是所述任務的一個，該第二任務是所述任務的另一個，和在所述第一任務的二個作業之中首先執行的作業相對於在該第二任務的二個作業之中首先執行的作業優先地執行，在該第一任務的二個作業之中稍後執行的作業相對於在該第二任務的二個作業之中稍後執行的作業優先地執行。
7.一種在實時系統中的可調度性確定方法，該實時系統包括多個用於執行多個周期性任務作業的處理器，所述多個周期性任務每個具有預定的周期，包括準備調度裝置，用於在每個任務的周期中給處理器分配每個作業；在所述任務的釋放時間之中，在最近的釋放時間之後計算網格時間，所述網格時間的每個是一個時間點，在其上所述任務周期的開始時間相互重合；在由該調度裝置分配的作業被在處理器中執行期間，計算執行時間的分配；基於該分配，確定是否每個作業在該周期內的截止時間之前完成；當由該調度裝置分配的作業通過第二網格時間被確定在其截止時間之前完成的時候，確定調度是可能的；當由該調度裝置分配一個作業通過第二網格時間被確定在其截止時間之前沒有完成的時候，確定調度是不可能的。
8.一種實時系統，該實時系統包括多個用於執行多個周期性任務作業的處理器，該多個周期性任務每個具有預定的周期，包括調度裝置，用於在每個任務的一個周期中給處理器分配每個作業；計算裝置，用於在由該調度裝置分配的作業被在處理器中執行期間計算執行時間的分配；第一確定裝置，用於基於該分配，確定是否每個作業在截止時間之前完成；第二確定裝置，用於當一個作業被確定在截止時間之前沒有完成的時候，確定調度是不可能的；第三確定裝置，用於確定每個確定在截止時間之前完成的作業的執行時間的分配是否收斂；和第四確定裝置，用於當該分配收斂的時候，確定調度是可能的。
9.根據權利要求8的系統，其中，該第三確定裝置基於所述任務的未執行作業，確定該分配是否收斂，所述任務的未執行作業的周期起始於第一時間點和第二時間點，所述第一時間點和第二時間點具有對應於該任務的最小公倍數的時間差，和當在第一時間點和第二時間點上的該未執行作業是彼此相同的時候，該第四確定裝置確定調度是可能的。
10.根據權利要求8的系統，進一步包括第五確定裝置，用於確定是否在所述任務的釋放時間之中，在最近的釋放時間之後存在網格時間，所述網格時間的每個是一個時間點，在其上所述任務的周期開始時間相互重合；第六確定裝置，用於當所述網格時間存在並且由該調度裝置分配的作業通過第二網格時間被確定在其截止時間之前完成的時候，確定調度是可能的；和第七確定裝置，用於當所述網格時間存在並且由該調度裝置分配的一個作業通過第二網格時間被確定在其截止時間之前沒有完成的時候，確定調度是不可能的。
11.根據權利要求8的系統，其中，該調度裝置基於每個作業的截止時間，分配每個作業給處理器。
12.根據權利要求8的系統，其中，當在二個連續的時間間隔的一個期間的分配和在二個連續的時間間隔的另一個期間的分配是彼此相同的時候，該第四確定裝置確定該分配收斂，在該任務的釋放時間當中，在最新的釋放時間之後，所述二個連續的時間間隔的每個對應於該任務周期的最小公倍數。
13.根據權利要求8的系統，其中，該調度裝置按照每個作業的優先級，分配每個作業給處理器。
14.根據權利要求8的系統，其中，該調度裝置基於每個作業的截止時間，分配每個作業給處理器。
15.根據權利要求13的系統，其中，當在第一任務的二個作業之間的執行開始時間中的時間差和在第二任務的二個作業之間的執行開始時間中的時間差是任務周期的最小公倍數的時候，該調度裝置通過使用調度算法分配每個作業給處理器，該第一任務是所述任務中的一個，該第二任務是所述任務中的另一個，和在所述第一任務的二個作業之中首先執行的作業相對於在所述第二任務的二個作業之中首先執行的作業優先地執行，在所述第一任務的二個作業之中稍後執行的作業相對於在所述第二任務的二個作業之中稍後執行的作業優先地執行。
16.根據權利要求8的系統，其中，該調度裝置通過使用一個EOF(最早的截止時間開始)算法分配每個作業給處理器。
17.根據權利要求1的方法，其中，該調度裝置通過使用一個EOF(最早的截止時間開始)算法分配每個作業給處理器。
18.一個存儲在計算機可讀介質上的電腦程式，該計算機包括多個用於執行多個周期性任務作業的處理器，所述多個周期性任務每個具有預定的周期，該電腦程式包括第一程序指令裝置，用於命令計算機處理器去在每個任務的周期中分配每個作業給處理器；第二程序指令裝置，用於命令計算機處理器去計算在分配的作業在處理器上執行期間的執行時間的分配；第三程序指令裝置，用於命令計算機處理器去基於該分配確定是否每個作業在該周期內的截止時間之前完成；第四程序指令裝置，當該作業的一個被確定在截止時間之前沒有完成的時候，用於命令計算機處理器去確定調度是不可能的；第五程序指令裝置，用於命令計算機處理器去確定每個被確定在截止時間之前完成的作業的執行時間的分配是否收斂；和第六程序指令裝置，當分配收斂的時候，用於命令計算機處理器去確定調度是可能的。
全文摘要
一種實時系統，該實時系統包括多個用於執行多個周期性任務作業的處理器，該多個周期性任務每個具有預定的周期，在每個任務的周期內分配每個作業給該處理器，在分配的作業被在該處理器上執行期間計算分配的執行時間，基於該分配確定是否該作業的每個由一個在該周期內的截止時間完成，當該作業的一個被確定不由該截止時間完成的時候，確定調度是不可能的，確定是否每個確定去由該截止時間完成的該作業的分配的執行時間收斂，和當該分配收斂的時候，確定調度是可能的。
文檔編號G06F9/46GK1838077SQ20051010848
公開日2006年9月27日 申請日期2005年9月30日 優先權日2005年3月25日
發明者鳥井修, 前田誠司 申請人:株式會社東芝