實時多線程調度器及調度方法
2023-10-05 15:03:14 1
專利名稱：實時多線程調度器及調度方法
技術領域：
本發明大體上是針對一種實時多線程調度器及調度方法。
背景技術：
技術的進步已產生更小且更強大的計算裝置。舉例來說，當前存在多種可攜式個人計算裝置，包括無線計算裝置，例如可攜式無線電話、個人數字助理(PDA)及尋呼裝置， 其體積小、重量輕且易於由用戶攜帶。更具體地說，可攜式無線電話(例如，蜂窩式電話及網際網路協議(IP)電話)可經由無線網絡傳送話音及數據包。此外，許多此些無線電話包括併入於其中的其它類型的裝置。舉例來說，無線電話還可包括數字靜態相機、數字攝像機、 數字記錄器及音頻文件播放器。並且，此些無線電話可處理可執行指令，包括可用以接入網際網路的軟體應用程式(例如，網絡瀏覽器應用程式)。因而，這些無線電話可包括相當大的計算能力。數位訊號處理器(DSP)、圖像處理器及其它處理裝置常常用於可攜式個人計算裝置中且結合作業系統而操作。實時作業系統(RTOS)的一個要求是嚴格的優先級調度。在單個處理器上，所述要求是應調度最高優先級可執行任務。通常，在具有多個中央處理單元 (CPU)的多線程或多處理器系統中，特定任務限於特定硬體線程或CPU，且單處理器調度器算法獨立地在每一硬體線程或CPU上運行。此方法並不滿足應調度全部最高優先級可執行任務的RTOS約束條件，且所述方法需要提前知曉何硬體線程或CPU將調度所述任務，需要知曉何硬體線程或CPU可能不可用。
發明內容
在特定實施例中，揭示一種包括在第一線程處接收中斷的方法，所述第一線程包括在第一時間在處理器處的多個執行線程中的最低優先級線程。所述方法還包括識別第二線程，所述第二線程包括在第二時間在處理器處的多個執行線程中的最低優先級線程。所述方法進一步包括將隨後中斷指向所述第二線程。在另一實施例中，揭示一種包括在一組線程中的第一線程處接收中斷的方法，所述組線程中的每一線程執行一組執行任務中的一相應任務。所述組執行任務中的每一任務及一組就緒任務中的每一任務具有一相應優先級。所述方法還包括反覆地將所述組執行任務中的最低優先級任務與所述組就緒任務中的最高優先級任務交換，直到所述組執行任務中的每一任務具有大於或等於所述組就緒任務中的每一任務的優先級的優先級。在另一實施例中，揭示一種包括多線程處理器的系統，所述多線程處理器經配置以執行多個線程，使得多個執行線程正運行最高優先級任務。所述多線程處理器經配置以調度任務，使得執行的任務具有至少與所有就緒任務中的最高優先級一樣高的優先級。在另一實施例中，揭示一種計算機可讀媒體。所述計算機可讀媒體含有可執行以致使計算機將中斷指向多個執行線程中的最低優先級線程的計算機可執行指令。所述中斷指示至少一個任務準備好被執行。所述多個執行線程中的最低優先級線程正執行最低優先
5級任務或者為閒置線程。所述多個執行線程中的最低優先級線程接收所述中斷，且起始中斷例程以從就緒任務列表中選擇最高優先級任務。所揭示實施例所提供的一個特定優點為任務是經調度的，使得在減少因中斷引起的幹擾的情況下執行最高優先級線程。因為低優先級線程接收中斷，所以引起重新調度中斷在不幹擾最高優先級線程的情況下自動地重新調度低優先級線程。另外，外部中斷將中斷最低優先級線程而不是最高優先級線程。所揭示實施例所提供的另一特定優點為在多個任務準備好執行且多個任務比一個以上運行的任務有更高優先級的情形下，低優先級運行任務以最小數目個交換且在無開銷用於其它高優先級任務運行的情況下與新的較高優先級任務交換。所揭示實施例所提供的另一特定優點為可直接將中斷處置程序線程的優先級與當前運行的線程的優先級進行比較。如果當前運行的線程具有低於中斷處置程序線程的優先級，那麼可立即調度所述中斷處置程序線程。本發明的其它方面、優點及特徵將在審閱包括以下部分的完整申請案之後變得明顯
具體實施方式
及權利要求書。
圖1為處理系統的特定說明性實施例的框圖；圖2為處理系統的另一特定說明性實施例的框圖，其展示中斷指向最低優先級執行線程；圖3為圖2的處理系統的特定說明性實施例的框圖，其展示任務交換；圖4為圖2的處理系統的特定說明性實施例的框圖，其展示另一中斷指向最低優先級執行線程；圖5為圖2的處理系統的特定說明性實施例的框圖，其展示任務從就緒任務列表移動到執行任務列表；圖6為圖2的處理系統的特定說明性實施例的框圖，其展示另一中斷指向最低優先級執行線程；圖7為圖2的處理系統的特定說明性實施例的框圖，其展示任務交換；圖8為圖2的處理系統的特定說明性實施例的框圖，其展示另一中斷指向最低優先級執行線程；圖9為圖2的處理系統的特定說明性實施例的框圖，其展示任務交換；圖IOA到圖IOC為在多線程處理器上實時調度任務的方法的第一說明性實施例的流程圖；圖11為在多線程處理器上實時調度任務的方法的第二說明性實施例的流程圖；圖12為在多線程處理器上實時調度任務的方法的第三說明性實施例的流程圖；圖13為在多線程處理器上實時調度任務的方法的第四說明性實施例的流程圖； 以及圖14為包括實時多線程調度器模塊的可攜式通信裝置的特定實施例的框圖。
具體實施方式
參看圖1，描繪處理系統的特定說明性實施例，且概括表示為100。多線程處理器 100包括經由總線接口 108耦合到指令高速緩衝存儲器110的存儲器102。多線程處理器 100還包括經由總線接口 108耦合到存儲器102的數據高速緩衝存儲器112。指令高速緩衝存儲器Iio經由總線111耦合到定序器114。在特定實例中，定序器114還可接收通用中斷116，所述通用中斷116可從中斷寄存器(未圖示)檢索。在特定實施例中，指令高速緩衝存儲器110可經由多個當前指令寄存器耦合到定序器114，所述多個當前指令寄存器可耦合到總線111並與多線程處理器100的特定線程相關聯。在特定實施例中，多線程處理器100為包括六個線程的交錯多線程處理器。在特定實施例中，總線111為六十四(64)位總線，且定序器114經配置以經由指令包從存儲器102檢索指令，所述指令包包括各自具有三十二(3 個位的長度的多個指令。總線111耦合到第一指令執行單元118、第二指令執行單元120、第三指令執行單元122 及第四指令執行單元124。每一指令執行單元118、120、122及IM可經由第二總線1 耦合到通用寄存器堆126。通用寄存器堆1 還可經由第三總線130耦合到定序器114，且耦合到數據高速緩衝存儲器112，且耦合到存儲器102。多線程處理器100還可包括監督器控制寄存器132，以存儲可由控制單元150存取的一個或一個以上優先級設定，所述控制單元150包括實時優先級調度器158及中斷控制器156，以確定何任務在處理線程中的每一者上執行。所述實時優先級調度器158可實施為軟體例程。每一處理線程可具有一個或一個以上相關聯的優先級設定，例如存儲在專用於特定線程的監督器狀態寄存器處的一個或一個以上位值。在操作期間，多線程處理器100執行多個線程，使得多個執行線程正運行最高優先級任務，其中多線程處理器100調度任務，使得所有執行任務具有至少與所有就緒任務的最高優先級一樣高的優先級。在特定實施例中，實時優先級調度器158調度任務，使得所有執行任務具有至少與所有就緒任務的最高優先級一樣高的優先級。在特定實施例中，多線程處理器100經配置以使得指向多個執行線程中的最低優先級線程的中斷不影響多個執行線程中的最高優先級線程的執行。舉例來說，中斷控制器156可經配置，以使得指向多個執行線程中的最低優先級線程的中斷不影響多個執行線程中的最高優先級線程的執行。 如本文中所使用，中斷可為停止正常執行並開始執行特殊處置程序的任何事項。中斷可表示正常程序流的任何斷開。在特定實施例中，多線程處理器100經配置以使得多個執行線程中的最低優先級線程接收中斷，且運行中斷例程以從就緒任務列表中選擇最高優先級任務。舉例來說，中斷控制器156可經配置以使得多個執行線程中的最低優先級線程接收中斷，且實時優先級調度器158可運行中斷例程以從就緒任務列表中選擇最高優先級任務。中斷邏輯可經配置以使得僅最低優先級線程能夠取得中斷。在特定實施例中，多線程處理器100經配置以使得在每一次交換任務以執行就緒任務列表中的最高優先級任務且使先前執行任務返回到就緒任務列表之後，檢查時間表以確定任何就緒任務是否具有比任何執行任務高的優先級。 舉例來說，在每一次交換任務以執行就緒任務列表中的最高優先級任務且使先前執行任務返回到就緒任務列表之後，實時優先級調度器158可檢查時間表以確定任何就緒任務是否具有比任何執行任務高的優先級。在特定實施例中，多線程處理器100經配置以使得使用執行任務與就緒任務的最小可能數目個交換來更新時間表，使得經更新的時間表使每一執行任務具有至少與就緒任務的最高優先級一樣高的優先級。舉例來說，實時優先級調度器158可經配置以使得使用執行任務與就緒任務的最小可能數目個交換來更新時間表，使得經更新的時間表使每一執行任務具有至少與就緒任務的最高優先級一樣高的優先級。參看圖2，描繪處理系統的特定說明性實施例，且概括表示為200。在特定實施例中，多線程處理器200大體上類似於圖1的多線程處理器100。多線程處理器200包括耦合到中斷控制器204的實時優先級調度器202、中斷屏蔽220、第一數據結構206及第二數據結構210。第一數據結構206包括在多個執行線程214上執行的任務的經確定優先級的執行任務列表208。所述任務由其相應的優先級標記，其中0標記最高優先級任務，1標記次最高優先級任務，等等。在特定實施例中，閒置任務具有最低優先級。第二數據結構210 包括準備好在多個執行線程214上執行的任務的經確定優先級的就緒任務列表212。中斷控制器204可經配置以將中斷指向所述多個執行線程214中的最低優先級線程，如箭頭218 所示。中斷屏蔽220可為位屏蔽以指示每一線程接收中斷的可用性。在特定實施例中，中斷屏蔽220經配置以將中斷指向多個執行線程214中的最低優先級線程，如箭頭218所示。實時優先級調度器202可經配置以將來自第二數據結構210的經確定優先級的就緒任務列表212的最高優先級任務移動到第一數據結構206的經確定優先級的執行任務列表208，以在中斷的最低優先級線程上執行最高優先級任務。實時優先級調度器202還可經配置以檢查時間表222以確定第二數據結構210中的任何就緒任務是否具有高於第一數據數據結構206中的最低優先級執行任務的優先級。檢查時間表222可包括檢驗第一數據結構206及第二數據結構210以確定第二數據結構210中的任何就緒任務是否具有高於第一數據結構206中的最低優先級執行任務的優先級。在特定實施例中，多個執行線程214中的最低優先級線程正執行來自第一數據結構206的經確定優先級的執行任務列表208的最低優先級任務。舉例來說，圖2中執行具有優先級6的任務的線程可為最低優先級線程。在操作中，多個執行線程214上正執行的具有優先級4的兩個任務中的一者可啟動或「喚醒」具有優先級2的任務，如箭頭216所示。此優先級2任務出現在第二數據結構 210的經確定優先級的就緒任務列表212上。所述中斷屏蔽220根據中斷控制器204而屏蔽掉正在除正執行優先級6任務的最低優先級線程外的多個執行線程214上執行的所有任務。響應於優先級2任務的啟動或喚醒，中斷控制器204可將中斷(如箭頭218所示)指向多個執行線程214中的最低優先級線程，所述線程正執行優先級6任務。參看圖3，實時優先級調度器202可將來自第二數據結構210的經確定優先級的就緒任務列表212的最高優先級任務(優先級2任務)移動到第一數據結構206的經確定優先級的執行任務列表208，以在中斷的最低優先級線程上執行最高優先級任務(優先級2 任務)，如箭頭300所示。在交換任務以執行來自經確定優先級的就緒任務列表212的最高優先級任務(優先級2任務)且使先前執行任務(優先級6任務)返回到經確定優先級的就緒任務列表212(如箭頭300所示)之後，實時優先級調度器202可檢查時間表222以確定第二數據結構210中的任何就緒任務是否具有高於第一數據結構206中的最低優先級執行任務的優先級。在圖3中，在箭頭300所示的任務交換之後，第二數據結構210中的就緒任務具有優先級6或優先級8，其中第一數據結構206中的最低優先級執行任務為兩個優先級4任務，所以第二數據結構210中的就緒任務全部不具有高於第一數據結構206中的最低優先級執行任務的優先級。中斷屏蔽220根據中斷控制器204而屏蔽掉在除正執行優先級4任務的最低優先級線程外的多個執行線程214上執行的所有任務。參看圖4，作為操作的另一實例，在多個執行線程214上執行的具有優先級6的任務可啟動或「喚醒」具有優先級2的任務及具有優先級4的兩個任務，如箭頭400所示。優先級2任務及兩個優先級4任務出現在第二數據結構210的經確定優先級的就緒任務列表 212上。中斷屏蔽220根據中斷控制器204而屏蔽掉在除為閒置的最低優先級線程外的多個執行線程214上執行的所有任務。響應於任務的啟動或喚醒，中斷控制器204可將中斷 (如箭頭402所示)指向多個執行線程214中的最低優先級線程。在特定實施例中，多個執行線程214中的最低優先級線程為執行閒置任務的閒置線程，所述閒置任務因其閒置狀態而被定義為在第一數據結構206的經確定優先級的執行任務列表208上具有最低優先級。參看圖5，圖4的實時優先級調度器202可將來自第二數據結構210的經確定優先級的就緒任務列表212的最高優先級任務(優先級2任務)移動到第一數據結構206的經確定優先級的執行任務列表208，以在中斷的最低優先級線程上執行最高優先級任務(優先級2任務)，如箭頭500所示。在移動來自經確定優先級的就緒任務列表212的最高優先級任務(優先級2任務)(如箭頭500所示)之後，實時優先級調度器202可檢查時間表 222以確定第二數據結構210中的任何就緒任務是否具有高於第一數據結構206中的最低優先級執行任務的優先級。在圖5中，在箭頭500所示的任務移動之後，第二數據結構210 中的就緒任務兩者具有優先級4，而第一數據結構206中的最低優先級執行任務為優先級8 任務，所以第二數據結構210中的就緒任務兩者均具有高於第一數據結構206中的最低優先級執行任務的優先級。中斷屏蔽220根據中斷控制器204而屏蔽掉在除正執行優先級8 任務的最低優先級線程外的多個執行線程214上執行的所有任務。參看圖6，兩個優先級4任務保留在第二數據結構210的經確定優先級的就緒任務列表212上。中斷屏蔽220已根據中斷控制器204而屏蔽掉在除正執行優先級8任務的最低優先級線程外的多個執行線程214上執行的所有任務。中斷控制器204可將中斷(如箭頭600所示)指向多個執行線程214中的最低優先級線程，所述線程正執行優先級8任務。參看圖7，實時優先級調度器202可將來自第二數據結構210的經確定優先級的就緒任務列表212的最高優先級任務(優先級4任務中的任一者)移動到第一數據結構206 的經確定優先級的執行任務列表208，以在中斷的最低優先級線程上執行最高優先級任務 (優先級4任務中的一者)，如箭頭700所示。在交換任務以執行來自經確定優先級的就緒任務列表212的最高優先級任務(優先級4任務中的一者)且使先前執行任務(優先級8 任務)返回到經確定優先級的就緒任務列表212(如箭頭700所示)之後，實時優先級調度器202可檢查時間表222以確定第二數據結構210中的任何就緒任務是否具有高於第一數據結構206中的最低優先級執行任務的優先級。在圖7中，在箭頭700所示的任務交換之後，第二數據結構210中的就緒任務具有優先級4及優先級8，而第一數據結構206中的最低優先級執行任務為優先級6任務，所以第二數據結構210中的就緒任務中的一者(優先級4任務)具有高於第一數據結構206中的最低優先級執行任務的優先級。中斷屏蔽220 根據中斷控制器204而屏蔽掉在除正執行優先級6任務的最低優先級線程外的多個執行線程214上執行的所有任務。參看圖8，優先級4任務連同優先級8任務一起保留在第二數據結構210的經確定
9優先級的就緒任務列表212上。中斷屏蔽220已根據中斷控制器204而屏蔽掉在除正執行優先級6任務的最低優先級線程外的多個執行線程214上執行的所有任務。響應於圖7的箭頭700所示的任務交換，中斷控制器204可將中斷(如箭頭800所示)指向多個執行線程214中的最低優先級線程，所述線程正執行優先級6任務。參看圖9，實時優先級調度器202可將來自第二數據結構210的經確定優先級的就緒任務列表212的最高優先級任務(優先級4任務)移動到第一數據結構206的經確定優先級的執行任務列表208，以在中斷的最低優先級線程上執行最高優先級任務(優先級4 任務)，如箭頭900所示。在交換任務以執行來自經確定優先級的就緒任務列表212的最高優先級任務(優先級4任務)且使先前執行任務(優先級6任務)返回到經確定優先級的就緒任務列表212(如箭頭900所示)之後，實時優先級調度器202可檢查時間表222以確定第二數據結構210中的任何就緒任務是否具有高於第一數據結構206中的最低優先級執行任務的優先級。在圖9中，在箭頭900所示的任務交換之後，第二數據結構210中的就緒任務具有優先級6及優先級8，其中第一數據結構206中的最低優先級執行任務為優先級4 任務，所以第二數據結構210中的就緒任務全部不具有高於第一數據結構206中的最低優先級執行任務的優先級。中斷屏蔽220根據中斷控制器204而屏蔽掉在除正執行優先級4 任務的最低優先級線程外的多個執行線程214上執行的所有任務。參看圖10A，描繪在多線程處理器上實時調度任務的方法的第一說明性實施例的流程圖，且概括表示為1000。在特定實施例中，方法1000實施於圖1的多線程處理器100 上。方法1000包括在1002處接收中斷及保存來自經中斷任務的上下文。方法1000還包括在1004處將一個或一個以上等待中斷的任務添加到就緒隊列。在特定實施例中，就緒隊列對應於圖2中所示的第二數據結構210，其包括準備好在多個執行線程214上執行的任務的經確定優先級的就緒任務列表212。方法1000進一步包括在1006處運行圖IOB中所示的調度器算法。方法1000還包括在1008處恢復上下文及返回到未中斷的操作。恢復上下文及返回到未中斷的操作可在稍後時間點發生，因為調度器可在返回到中斷的任務之前運行其它任務。參看圖10B，在1010處展示調度器算法。調度器算法1010包括在1012處從運行隊列中移除當前運行的任務及將所述任務添加到就緒隊列。在特定實施例中，運行隊列對應於圖2中所示的第一數據結構206，第一數據結構206包括在多個執行線程214上執行的任務的經確定優先級的執行任務列表208。調度器算法1010還包括在1014處從就緒隊列中移除最高優先級任務及將所述任務添加到運行隊列，使所述任務成為新的當前運行的任務。調度器算法1010進一步包括在1016處確定新的當前運行的任務是否為最低優先級運行任務。如果新的當前運行的任務為最低優先級運行任務，那麼在1018處，其上正運行新的當前運行的任務的線程經配置以取得中斷。如果新的當前運行的任務不是最低優先級運行任務，那麼在1020處，正運行新的當前運行的任務的線程經配置以不取得中斷。調度器算法1010進一步包括在1022處運行圖IOC中所示的調度器檢查。參看圖10C，在IOM處展示調度器檢查。調度器檢查IOM開始於1(^6。調度器檢查IOM包括在10 處確定某一線程是否經配置以取得中斷。如果無線程經配置以取得中斷，那麼在1034處，所述最低優先級線程經配置以取得中斷。調度器檢查IOM還包括在 1030處確定最低優先級運行任務是否具有低於最高優先級就緒任務的優先級。如果最低優先級運行任務具有低於最高優先級就緒任務的優先級，那麼在1036處觸發中斷以引起重新調度事件，且在1038處調度器檢查IOM結束。如果最低優先級運行任務不具有低於最高優先級就緒任務的優先級，那麼調度器檢查IOM進一步包括在1032處確定在任何任務就緒的同時是否有任何線程閒置。如果在任何任務就緒的同時有任何線程閒置，那麼在1036處觸發中斷以引起重新調度事件，且在 1038處調度器檢查IOM結束。如果在任何任務就緒的同時無線程閒置，那麼在1038處調度器檢查IOM結束。在特定實施例中，中斷控制器已經建立，使得在1036處觸發的中斷將被傳遞到最低優先級線程或閒置線程。參看圖11，描繪在多線程處理器上實時調度任務的方法的第二說明性實施例的流程圖，且概括表示為1100。在特定實施例中，方法1100實施於圖1的多線程處理器100上。 方法1100包括在1102處在第一線程處接收中斷，所述第一線程包括在第一時間在處理器處的多個執行線程中的最低優先級線程。方法1100還包括在1104處識別第二線程，所述第二線程包括在第二時間在處理器處的多個執行線程中的最低優先級線程。在特定實施例中，第二線程不同於第一線程。方法1100進一步包括在1106處將隨後中斷指向第二線程。 舉例來說，如上文所描述，中斷可被指向多個執行線程214中的最低優先級線程，如圖2的箭頭218、圖4的箭頭402、圖6的箭頭600及圖8的箭頭800所示。在特定實施例中，所述中斷指示至少一個任務準備好被執行。舉例來說，由圖2的箭頭218所示的中斷可指示優先級2任務準備好被執行，由圖4的箭頭402所示的中斷可指示優先級2任務準備好被執行，由圖6的箭頭600所示的中斷可指示優先級4任務準備好被執行，且由圖8的箭頭800 所示的中斷可指示優先級4任務準備好被執行。在特定實施例中，第一線程正執行多個執行任務中的最低優先級任務。舉例來說， 圖2的多個執行線程214中的最低優先級線程可正執行優先級6任務，圖3的最低優先級線程正執行優先級4任務，圖5及圖6的最低優先級線程可正執行優先級8任務，圖7及圖 8的最低優先級線程可正執行優先級6任務，且圖9的最低優先級線程正執行優先級4任務。在特定實施例中，第一線程為閒置線程。舉例來說，圖4的多個執行線程214中的最低優先級線程可為閒置線程。在特定實施例中，閒置線程正執行閒置任務。方法1100還包括在1108處，當第一線程接收到所述中斷時，運行中斷例程以從就緒任務列表中選擇最高優先級任務。可將來自就緒任務列表的最高優先級任務的第一優先級與來自執行任務列表的最低優先級任務的第二優先級進行比較，且僅在第一優先級高於第二優先級時才交換任務。舉例來說，在圖2中，當多個執行線程214中的最低優先級線程 (執行優先級6任務的線程)接收到中斷(如箭頭218所示)時，可運行中斷例程以從經確定優先級的就緒任務列表212中選擇最高優先級任務(優先級2任務)。方法1100進一步包括，在1110處，在交換任務以在第一線程處執行就緒任務列表中的最高優先級任務且使先前執行任務返回到就緒任務列表之後，確定就緒任務列表中的任何就緒任務是否具有高於最低優先級執行任務的優先級。舉例來說，在交換優先級2 任務與優先級6任務(如圖3的箭頭300所示)之後，可確定經確定優先級的就緒任務列表212中的具有優先級6及優先級8的就緒任務不具有高於經確定優先級的執行任務列表 208的具有優先級4的最低優先級執行任務的優先級。類似地，在交換優先級4任務與優先級8任務(如圖7的箭頭700所示)之後，可確定經確定優先級的就緒任務列表212中的具有優先級4的一個就緒任務具有高於經確定優先級的執行任務列表208中的具有優先級 6的最低優先級執行任務的優先級。在特定實施例中，方法1100可在必要時重複以檢查時間表，以通過將最低優先級執行任務與最高優先級就緒任務進行比較來確定任何額外就緒任務是否具有高於當前最低優先級執行任務的優先級。將最低優先級執行任務與最高優先級就緒任務進行比較可為確定就緒任務列表中的任何就緒任務是否具有高於最低優先級執行任務的優先級的一種方式。舉例來說，在圖3中，可通過將優先級4任務與最高優先級就緒任務(優先級6任務) 進行比較來確定無就緒任務具有高於最低優先級執行任務(優先級4任務)的優先級。類似地，在圖5中，可通過將優先級8任務與最高優先級就緒任務(優先級4任務)進行比較來確定具有優先級4的兩個就緒任務具有高於最低優先級執行任務(優先級8任務)的優先級。在特定實施例中，方法1100進一步包括確定最低優先級執行任務及使用中斷例程來將隨後中斷指向第二線程，其中第二線程正執行最低優先級執行任務。舉例來說，在交換優先級4任務與優先級8任務(如圖7的箭頭700所示)之後，可確定優先級6任務為最低優先級執行任務且中斷例程可用以將隨後中斷(如圖8的箭頭800所示)指向多個執行線程214中的正執行優先級6任務的最低優先級線程。在特定實施例中，方法1100進一步包括基於檢查時間表以確定任何就緒任務是否具有高於最低優先級執行任務的優先級的結果來選擇性地設定隨後中斷。舉例來說，可基於檢查圖7中的時間表222及確定就緒任務中的一者(具有優先級4)具有高於優先級 6任務(最低優先級執行任務)的優先級的結果來選擇性地設定隨後中斷(如圖8的箭頭 800所示)。在特定實施例中，圖2到圖9的中斷控制器204指導多個執行線程214中的除所述多個執行線程214中的最低優先級線程外的線程被屏蔽而不接收中斷。舉例來說，如圖2 到圖9中所示，中斷控制器204可指導中斷屏蔽220屏蔽掉除多個執行線程214中的最低優先級線程外的多個執行線程214，使其不接收中斷。參看圖12，描繪在多線程處理器上實時調度任務的方法的第三說明性實施例的流程圖，且概括表示為1200。在特定實施例中，方法1200實施於圖1的多線程處理器100上。 方法1200包括在1202處在一組線程中的第一線程處接收中斷，其中所述組線程中的每一線程執行一組執行任務中的一相應任務，且其中所述組執行任務中的每一任務及一組就緒任務中的每一任務具有一相應優先級。舉例來說，如圖6中所示，執行優先級8任務的線程可接收中斷，如箭頭600所示，其中多個執行線程214中的每一線程執行經確定優先級的執行任務列表208中的相應任務，且其中經確定優先級的執行任務列表208中的每一任務及經確定優先級的就緒任務列表212中的每一任務具有一相應優先級。在特定實施例中，閒置線程執行具有最低優先級的閒置任務。舉例來說，如圖4中所示，執行閒置任務的線程可接收中斷，如箭頭402所示。方法1200還包括在1204處反覆交換所述組執行任務中的最低優先級任務與所述組就緒任務中的最高優先級任務，直到所述組執行任務中的每一任務具有大於或等於所述組就緒任務中的每一任務的優先級的優先級為止。舉例來說，如圖4到圖9中所示，經確定優先級的執行任務列表208中的最低優先級任務可反覆地與經確定優先級的就緒任務列
12表212中的相應最高優先級任務交換，直到經確定優先級的執行任務列表208中的每一任務具有大於或等於經確定優先級的就緒任務列表212中的每一任務的優先級的優先級為止，如圖9中所示。在特定實施例中，反覆交換包括在1206處在交換每一執行任務與就緒任務以形成下一組執行任務及下一組就緒任務之後，確定下一組執行任務中的最低優先級任務。反覆交換的每一反覆可包括確定下一組執行任務中的最低優先級任務。舉例來說，在交換優先級4任務與優先級8任務(如圖7的箭頭700所示)之後，下一組執行任務可包括一優先級0任務、兩個優先級2任務、兩個優先級4任務及一優先級6任務，且下一組就緒任務可包括一優先級4任務及一優先級8任務，其中可將優先級6任務確定為下一組執行任務中的最低優先級任務。反覆交換進一步包括在1208處在下一組執行任務中的最低優先級任務的優先級小於下一組就緒任務中的最高優先級任務的優先級時將中斷發送到最低優先級線程以執行反覆交換的下一反覆。舉例來說，如圖8的箭頭800所示，由於優先級6任務具有低於具有下一組就緒任務的最高優先級的優先級4任務的優先級，因此可將中斷發送到優先級6任務(下一組執行任務中的最低優先級任務)以執行反覆交換的下一反覆。參看圖13，描繪在多線程處理器上實時調度任務的方法的第四說明性實施例的流程圖，且概括表示為1300。在特定實施例中，方法1300實施於圖1的多線程處理器100上。 方法1300包括在1302處將中斷指向多個執行線程中的最低優先級線程，其中所述中斷指示至少一個任務準備好被執行，其中所述多個執行線程中的最低優先級線程正執行最低優先級任務或者為閒置線程，且其中所述多個執行線程中的最低優先級線程接收中斷，並起始中斷例程以從就緒任務列表中選擇最高優先級任務。舉例來說，如圖2的箭頭218所示， 可將中斷指向多個執行線程214中的最低優先級線程，其中所述中斷可指示優先級2任務準備好被執行，其中所述最低優先級線程可正執行優先級6任務(最低優先級任務)，且其中執行優先級6任務的最低優先級線程可接收中斷，並可起始中斷例程以從經確定優先級的就緒任務列表212中選擇優先級2任務(最高優先級任務)。方法1300還包括，在1304處，在交換任務以執行來自就緒任務列表的最高優先級任務且使先前執行任務返回到就緒任務列表之後，檢查時間表以確定任何就緒任務是否具有高於任何執行任務的優先級，其中檢查所述時間表以確定任何就緒任務是否具有高於任何執行任務的優先級包括將最低優先級執行任務與最高優先級就緒任務進行比較。舉例來說，在交換優先級4任務與優先級8任務(如圖7的箭頭700所示)之後，可檢查時間表 222以通過將優先級6任務(最低優先級執行任務)與優先級4任務(最高優先級就緒任務)進行比較來確定任何就緒任務是否具有高於任何執行任務的優先級。方法1300進一步包括在1306處使用中斷例程以將隨後中斷指向多個執行線程中的正執行最低優先級任務的特定線程。舉例來說，中斷例程可用以將隨後中斷(如圖8的箭頭800所示)指向多個執行線程214中的正執行優先級6任務(最低優先級任務)的特定線程。方法1300還包括在1308處基於檢查時間表以確定任何就緒任務是否具有高於最低優先級執行任務的優先級的結果而選擇性地引起或起始隨後中斷。舉例來說，可基於檢查時間表222及確定優先級4就緒任務具有高於優先級6執行任務(最低優先級執行任務) 的優先級的結果而選擇性地引起或起始隨後中斷(如圖8的箭頭800所示)。圖14為包括實時多線程調度器模塊1464的系統1400的特定實施例的框圖。系統1400可實施於可攜式電子裝置中，且包括耦合到存儲器1432的處理器1410(例如，數位訊號處理器(DSP))。在說明性實例中，實時多線程調度器模塊1464包括圖1到圖9的系統中的任一者，根據圖10到圖13的實施例中的任一者或其任何組合來操作。實時多線程調度器模塊1464可在處理器1410中或可為單獨裝置或電路(未圖示)。在特定實施例中，數位訊號處理器可存取圖1的實時多線程調度器106。舉例來說，如圖14中所示，數位訊號處理器(DSP) 1410可存取實時多線程調度器模塊1464。相機接口 1468耦合到處理器1410且還耦合到相機，例如攝像機1470。顯示控制器1似6耦合到處理器1410且耦合到顯示裝置1似8。編碼器/解碼器(CODEC) 1434還可耦合到信號處理器1410。揚聲器1436及麥克風1438可耦合到CODEC 1434。無線接口 1440 可耦合到處理器1410且耦合到無線天線1442。實時多線程調度器模塊1464經配置以執行存儲在計算機可讀媒體(例如，存儲器 1432)處的計算機可執行指令1466，以致使實時多線程調度器模塊1464將中斷指向多個執行線程中的最低優先級線程，其中所述中斷指示至少一個任務準備好被執行，其中多個執行線程中的最低優先級線程正執行最低優先級任務或者為閒置線程，且其中所述多個執行線程中的最低優先級線程接收所述中斷，並起始中斷例程以從就緒任務列表中選擇最高優先級任務。以此方式，實時多線程調度器模塊1464可確保例如數據機任務等高優先級任務不會被例如用戶接口任務等較低優先級任務中斷。在特定實施例中，處理器1410、顯示控制器1似6、存儲器1432、CODEC 1434、無線接口 1440及相機接口 1468包括於封裝中系統或晶片上系統裝置1422中。在特定實施例中，輸入裝置1430及電力供應器1444耦合到晶片上系統裝置1422。此外，在特定實施例中，如圖14中所說明，顯示裝置1428、輸入裝置1430、揚聲器1436、麥克風1438、無線天線 1442、攝像機1470及電力供應器1444在晶片上系統裝置1422外部。然而，顯示裝置1428、 輸入裝置1430、揚聲器1436、麥克風1438、無線天線1442、攝像機1470及電力供應器1444 中的每一者可耦合到晶片上系統裝置1422的組件，例如接口或控制器。所屬領域的技術人員將進一步了解，結合本文中所揭示的實施例而描述的各種說明性邏輯塊、配置、模塊、電路及算法步驟可實施為電子硬體、計算機軟體或兩者的組合。為清晰地說明硬體與軟體的這種可互換性，上文已大體按其功能性描述了各種說明性組件、 塊、配置、模塊、電路及步驟。將此功能性實施為硬體還是軟體取決於特定應用及強加於整個系統的設計約束。所屬領域的技術人員可針對每一特定應用以不同方式實施所描述的功能性，但此些實施決策不應被解釋為會引起脫離本發明的範圍。結合本文中所揭示的實施例而描述的方法或算法的步驟可直接體現於硬體中、由處理器執行的軟體模塊中，或兩者的組合中。軟體模塊可駐存在隨機存取存儲器(RAM)、 快閃記憶體、只讀存儲器(ROM)、可編程只讀存儲器(PR0M)、可擦除可編程只讀存儲器 (EPROM)、電可擦除可編程只讀存儲器(EEPROM)、寄存器、硬碟、可裝卸盤、壓縮盤只讀存儲器(CD-ROM)，或此項技術中已知的任何其它形式的存儲媒體中。示範性存儲媒體耦合到處理器，使得所述處理器可從所述存儲媒體讀取信息及將信息寫入到所述存儲媒體。在替代方案中，存儲媒體可與處理器成一體式。所述處理器及所述存儲媒體可駐存在專用集成電路(ASIC)中。ASIC可駐存在計算裝置或用戶終端中。在替代方案中，處理器及存儲媒體可作為離散組件駐存在計算裝置或用戶終端中。
提供對所揭示實施例的先前描述以使所屬領域的技術人員能夠製作或使用所揭示的實施例。對這些實施例的各種修改對於所屬領域的技術人員來說將是顯而易見的，且本文中所界定的一般原理可在不脫離本發明的精神或範圍的情況下應用於其它實施例。因此，本發明無意限於本文中所展示的實施例，而是將被賦予與如所附權利要求書界定的原理及新穎特徵一致的最寬可能範圍。
權利要求
1.一種方法，其包含在第一線程處接收中斷，所述第一線程包含在第一時間在處理器處的多個執行線程中的最低優先級線程；識別第二線程，所述第二線程包含在第二時間在處理器處的所述多個執行線程中的最低優先級線程；以及將隨後中斷指向所述第二線程。
2.根據權利要求1所述的方法，其中所述中斷指示至少一個任務準備好被執行。
3.根據權利要求1所述的方法，其中所述第一線程正執行多個執行任務中的最低優先級任務。
4.根據權利要求1所述的方法，其中所述第一線程為閒置線程。
5.根據權利要求1所述的方法，其中所述第一線程接收所述中斷並起始中斷例程以從就緒任務列表中選擇最高優先級任務，且其中將來自所述就緒任務列表的所述最高優先級任務的第一優先級與來自執行任務列表的最低優先級任務的第二優先級進行比較，且僅在所述第一優先級高於所述第二優先級時才交換任務。
6.根據權利要求5所述的方法，其進一步包含在交換任務以在所述第一線程處執行所述最高優先級任務且使執行任務返回到所述就緒任務列表之後，確定所述就緒任務列表中的任何就緒任務是否具有高於最低優先級執行任務的優先級。
7.根據權利要求6所述的方法，其進一步包含檢查時間表以通過將所述最低優先級執行任務與最高優先級就緒任務進行比較來確定任何就緒任務是否具有高於所述最低優先級執行任務的優先級。
8.根據權利要求6所述的方法，其進一步包含確定所述最低優先級執行任務；以及使用所述中斷例程來將所述隨後中斷指向所述第二線程，其中所述第二線程正執行所述最低優先級執行任務。
9.根據權利要求8所述的方法，其進一步包含基於檢查時間表以確定任何就緒任務是否具有高於所述最低優先級執行任務的優先級的結果而選擇性地設定所述隨後中斷。
10.根據權利要求1所述的方法，其中中斷控制器指導所述多個執行線程中的除所述第一線程外的線程被屏蔽而不接收所述中斷。
11.一種方法，其包含在一組線程中的第一線程處接收中斷，其中所述組線程中的每一線程執行一組執行任務中的一相應任務，且其中所述組執行任務中的每一任務及一組就緒任務中的每一任務具有一相應優先級；以及反覆地交換所述組執行任務中的最低優先級任務與所述組就緒任務中的最高優先級任務，直到所述組執行任務中的每一任務具有大於或等於所述組就緒任務中的每一任務的優先級的優先級為止。
12.根據權利要求11所述的方法，其中所述反覆交換的每一反覆包括在交換每一執行任務與就緒任務以形成下一組執行任務及下一組就緒任務之後確定所述下一組執行任務中的最低優先級任務；以及當所述下一組執行任務中的所述最低優先級任務的優先級小於所述下一組就緒任務中的最高優先級任務的優先級時，將中斷發送到所述最低優先級線程以執行所述反覆交換的下一反覆。
13.—種系統，其包含多線程處理器，其經配置以執行多個線程，使得多個執行線程正運行最高優先級任務， 其中所述多線程處理器經配置以調度任務，使得所有執行任務均具有至少與所有就緒任務的最高優先級一樣高的優先級。
14.根據權利要求13所述的系統，其中所述多線程處理器經配置以使得指向所述多個執行線程中的最低優先級線程的中斷不影響所述多個執行線程中的最高優先級線程的執行。
15.根據權利要求13所述的系統，其中所述多線程處理器經配置以使得所述多個執行線程中的所述最低優先級線程接收中斷並啟動中斷例程以從就緒任務列表中選擇最高優先級任務。
16.根據權利要求13所述的系統，其中所述多線程處理器經配置以使得在每一次交換任務以執行就緒任務列表中的最高優先級任務且使先前執行任務返回到所述就緒任務列表之後，檢查時間表以確定任何就緒任務是否具有高於任何執行任務的優先級。
17.根據權利要求13所述的系統，其中所述多線程處理器經配置以使得使用執行任務與就緒任務的最小可能數目個交換來更新時間表，使得所述經更新的時間表使每一執行任務具有至少與所述就緒任務的最高優先級一樣高的優先級。
18.根據權利要求13所述的系統，其進一步包含第一數據結構，其包括在所述多個執行線程上執行的任務的經確定優先級的執行任務列表；以及第二數據結構，其包括準備好在所述多個執行線程上執行的任務的經確定優先級的就緒任務列表。
19.根據權利要求18所述的系統，其進一步包含中斷控制器，其經配置以將中斷指向所述多個執行線程中的最低優先級線程。
20.根據權利要求18所述的系統，其中中斷屏蔽經配置以將中斷指向所述多個執行線程中的最低優先級線程。
21.根據權利要求19所述的系統，其進一步包含調度器，其經配置以將來自所述第二數據結構的所述經確定優先級的就緒任務列表的最高優先級任務移動到所述第一數據結構的所述經確定優先級的執行任務列表以在所述經中斷的最低優先級線程上執行所述最高優先級任務，並檢查時間表以確定所述第二數據結構中的任何就緒任務是否具有高於所述第一數據結構中的最低優先級執行任務的優先級。
22.根據權利要求21所述的系統，其中所述多個執行線程中的所述最低優先級線程正執行來自所述第一數據結構的所述經確定優先級的執行任務列表的最低優先級任務。
23.根據權利要求21所述的系統，其中所述多個執行線程中的所述最低優先級線程為執行閒置任務的閒置線程，所述閒置任務在所述第一數據結構的所述經確定優先級的執行任務列表上具有最低優先級。
24.一種含有計算機可執行指令的計算機可讀媒體，所述計算機可執行指令可執行以致使計算機將中斷指向多個執行線程中的最低優先級線程，其中所述中斷指示至少一個任務準備好被執行，其中所述多個執行線程中的所述最低優先級線程正執行最低優先級任務或為閒置線程，且其中所述多個執行線程中的所述最低優先級線程接收所述中斷並起始中斷例程以從就緒任務列表中選擇最高優先級任務。
25.根據權利要求M所述的計算機可讀媒體，其中所述計算機可執行指令可進一步執行以致使所述計算機在交換任務以執行來自所述就緒任務列表的所述最高優先級任務且使執行任務返回到所述就緒任務列表之後，檢查時間表以確定任何就緒任務是否具有高於任何執行任務的優先級，其中檢查所述時間表以確定任何就緒任務是否具有高於任何執行任務的優先級包括將最低優先級執行任務與最高優先級就緒任務進行比較；使用中斷例程以將隨後中斷指向所述多個執行線程中的正執行所述最低優先級任務的特定線程；且基於檢查所述時間表以確定任何就緒任務是否具有高於所述最低優先級執行任務的優先級的結果來選擇性地引起所述隨後中斷。
全文摘要
在特定實施例中，揭示一種包括在第一線程處接收中斷的方法，所述第一線程包括在第一時間在處理器處的多個執行線程中的最低優先級線程。所述方法還包括識別第二線程，所述第二線程包括在第二時間在處理器處的多個執行線程中的最低優先級線程。所述方法進一步包括將隨後中斷指向所述第二線程。
文檔編號G06F9/44GK102341780SQ201080010974
公開日2012年2月1日 申請日期2010年3月16日 優先權日2009年3月17日
發明者盧奇安·科德雷斯庫, 埃裡克·詹姆斯·普隆迪克 申請人:高通股份有限公司