任務管理

論述內容包括任務狀態遷移、任務控制塊、內核中各種隊列、調度演演算法和內核時鐘等內容。在內核的設計過程中，最先應考慮的是任務的狀態以及遷移時序，然後根據此狀態設計相應的隊列，如就緒隊列、等待隊列等。內核時鐘也依賴任務的狀態。可以看出，任務管理實現的核心和基礎是任務狀態和遷移時序。

4.4.1任務狀態及轉換時序

在上面的章節中，描述了任務的三種基本狀態，一般在實現時會基於這三種轉態添加新的狀態。圖4-4描述了實際實現的任務狀態轉換圖。在給定的時刻，任務的狀態一定處在這六種狀態之一，下面的論述只是對本系統實現的描述，不同的內核對這些部分的實現有很大差異，但基本原理不變。

圖4-4在描述任務狀態遷移的同時，也描述了任務的生存周期，任務的生命期從新建態時開始直到結束態時結束。在不同的操作系統中，這些狀態的實現是有差異的，有的內核還有其他狀態。新建狀態是指任務被創建的過程，在這個過程中主要工作有：為任務分配TCB和棧空間以及其他資源。當任務創建完成以後，任務就具備運行的能力了，與此同時，任務進入就緒狀態，並等待調度器為它分配運行的機會。當任務得到運行的機會，任務開始執行。處於運行態的任務會在任意時刻由運行態進入休眠態、就緒態或結束狀態。其中進入休眠態是任務的主動過程，這主要是任務調用了內核提供的休眠函數，任務在休眠狀態，如果沒有其他任務喚醒它，它將永遠休眠下去直到系統關閉，這種方式也可用於任務同步。等待狀態主要由兩種原因引起，一種是等待某事件的發生，如等待信號量；第二種為任務主動等待多少個tick。最後，任務可以將自己殺死進入結束態。

4.4.2任務控制

任務控制塊（TCB）唯一地描述了一個任務的屬性。一旦任務建立了，任務控制塊中的各個值將被賦值。任務控制塊是一個數據結構，當任務的CPU使用權被剝奪時，TCB保存了該任務的狀態和其他信息。當任務重新得到CPU使用權時，TCB能確保任務從被中斷的點絲毫不差地繼續執行。TCB全部駐留在RAM中。TCB在任務初始化的時候被建立。任務控制塊數據結構如下所示：

typedef struct task_ctrl_blk{

stk_t *pstack;

stk_t *pstk;

list_t link;

uword_t id;

uword_t prio;

uword_t slice_time;

uword_t exe_time;

word_t delay_time;

uword_t status;

list_t task_link;

}tcb_t;

其中：

·pstack：指向當前任務的棧頂。每個任務有自己的棧，尤為重要的是，每個任務的棧的容量可以是任意的。有些商業內核要求所有任務棧的容量都一樣，除非用戶寫一個複雜的介面函數來改變之。這種限制浪費了RAM，當各任務需要的棧空間不同時，也得按任務中預期棧容量需求最多的分配棧空間。pstack是TCB數據結構中唯一一個能用彙編語言來處置的變數（在任務切換段的代碼之中使用）把pstack放在數據結構的最前面，使得從彙編語言中處理這個變數時較為容易；

·pstk：指向任務的棧頂，在任務結束而回收任務棧空間時使用，這主要由內存管理部分的缺陷所引起的；

·link：用於連接任務控制塊。內核在運行時，除了任務控制塊外，系統中存在很多類型的鏈表，比如信號量鏈表。為了對這些鏈表有一個統一的操作，所以定義了list_t類型來統一這些操作。如果不使用list_t，TCB鏈表操作需要實現一組鏈表操作函數，信號量需要另外一組鏈表操作函數，這樣使程序變得冗長；

·id：任務的ID號，用於唯一標識一個任務。每個任務都有一個唯一的ID號，需要在任務創建的時候指定ID，如果指定的ID號已經存在，則此任務不能被創建；

·prio：任務的優先順序，此值範圍為0～63，值越小代表優先順序越高。內核將儘力保證高優先順序的任務優先運行，並且允許任務可以是相同的優先順序；

·slice _time：表示任務應該運行的時間片數。雖然內核保證高優先順序的任務優先得到運行的機會，但對於相同優先順序的任務來說，時間片方式是比較好的調度策略；

·exe _time：保存了任務已經運行的時間片個數。這個變數在每次系統時鐘中斷產生時被累加1，如果exe_time的值達到slice_time，則說明該任務已經運行了給定時間片的時間，這時，內核將把運行機會讓給其他的，且優先順序等於此任務的其他任務。如果此優先順序上沒有其他任務，且此任務沒有自己放棄運行機會，此任務將繼續運行；

·delay _time ：用於記錄任務等待的時間片數，每個系統時鐘中斷產生時，此值自減1，如果delay_time的值為0，說明該任務的等待時間已經超時。內核將此任務從等待隊列中刪除，並移動就緒隊列中，這樣該任務就會被調度器在適當的時候調度；

·status：指示了任務的運行狀態，目前，此值表示的含義有就緒，休眠，等待和阻塞，在任務狀態轉換圖4-4中的運行態未能表示出來，這是因為在實現時，就緒態同時也表示了運行態；

·task_link：用於將系統中所有的任務連接成循環雙鏈表。

4.4.3 ByCore中的各種隊列

在圖4-4中描述的每個狀態都對應一個或一組隊列。如處於就緒狀態中的就緒隊列，處於等待態中的等待隊列等等。

4.4.3.1 就緒隊列

就緒隊列中的任務已經得到除CPU以外的所有資源。調度器也將在它們中按照優先順序和時間片結合的策略選擇一個就緒任務獲得CPU。在實現中，任務被分成64（0～63）種優先順序，且不同的任務又會有相同優先順序。內核將相同優先順序的任務組成一個雙鏈表。為了在調度過程中能快速的檢索出最高優先順序的任務隊列，將整個就緒隊列用一個全局數組list_t ptask[MAX_PRIO]（其中MAX_PRIO=64）來作為不同優先順序就緒隊列的隊頭，如ptask 為優先順序是i的就緒隊列的隊頭。整個就緒隊列如圖4-5所示。

4.4.3.2 等待和休眠隊列

當任務處於等待或休眠態時，內核必須將該任務的TCB從就緒隊列中刪除，然後插入到等待或者休眠隊列。在當前的實現中，內核只分別維持一個等待隊列和休眠隊列，這兩個隊列不像就緒隊列按照優先順序的高低被分組，換句話說，等待隊列和休眠隊列將所有的任務TCB連成一個雙鏈表。

pdelay和psleep分別為等待隊列和休眠隊列的對頭指針。這兩個隊列的組織雖然一樣，但是它們各自隊列中的任務被激活的時機卻不同，pdelay所指隊列中的任務會被內核的tick激活，而處在psleep隊列中的任務只能由其他的任務將其喚醒。利用這兩種隊列配和信號量等任務同步、通信機制可以實現較為複雜、靈活的任務控制機制。

當任務處在等待態時，任務還可能處在另外的隊列中，這個隊列就是為等待某個信號量而組織成的隊列。這個隊列將在信號量實現的內容中論述。

4.4.4調度器實現

在整個任務管理中，任務調度無疑是系統的核心，任務調度通常由內核中的調度器實現。調度器的實現與任務運行狀態遷移，任務隊列有密切的聯繫，可以說任務運行狀態遷移和任務隊列決定了調度器的實現。調度器的主要作用是在就緒隊列中選擇優先順序最高的任務運行，如果優先順序最高的任務不止一個，則選擇隊頭的任務運行。雖然整個調度器的功能可以用上面的幾句話概括，但調度器的實現遠遠沒有那麼簡單，主要困難來源下面的原因：

1．確定調度器運行的時機；

2．中斷處理程序完了后，是執行當前任務，還是馬上調度；

3．調度器的性能；

4．調度中伴隨著任務上下文的切換，尤其對處理器架構有關的上下文，應該設計良好的介面以便移植。

以上這些基本問題都是應該考慮的，隨著內核功能的擴充和完善，調度器可能會在原先沒涉及到的地方被調用，雖然在這些新地方不要求能正確調度，但至少不能引起系統崩潰。對於實時系統來說，中斷處理程序執行完畢后，應該馬上執行調度，這是因為中斷常常伴隨著有新的任務處於就緒隊列中，在這些任務中可能會有高優先順序的任務就緒，所以在實時內核中要求必須支持在中斷後馬上進行任務調度。不管是在實時系統，還是 在其他系統中，調度器性能顯得非常重要，常常要求調度器的時間複雜度至少應該為線性，當然常數是最好的。對於不同的處理器架構，其提供的寄存器，狀態寄存器都有很大的區別，調度器應該留出良好的介面給不同的處理器，以便以後方便移植。

在實現調度器時，基本上考慮了上面的幾個基本問題。根據上兩節論述的任務狀態遷移、內核隊列等方面的內容，在byCore中實現了一個叫scheduler( )的調度程序。在scheduler( )中調用幾個與硬體相關的函數，這幾個函數主要用於實現任務硬體上下文的切換，這部分代碼用彙編完成，並且與處理器有關。在現代操作系統中，會有很少一部分使用彙編語言實現，這是因為各種處理器架構的寄存器都沒有被映射到可見的位置，也即象C這樣的高級語言不能直接對其操作，然而，在任務切換時，硬體上下文會保存到任務堆棧中，這種操作使得高級語言無能為力。

該調度程序的演演算法非常簡單，首先，在允許調度的情況下，如果有高優先順序任務就緒，則進行任務切換。任務切換會發生在兩種處理器模式下，一種是處理器處於正常的運行態，另一種發生在中斷態中。因此，內核使用兩組函數分別處理這兩種情況。在兩種處理器狀態下都有“啟動新任務”和“新舊任務切換”函數介面實現最後的任務切換工作，這兩組函數與處理器有關，並由彙編實現。在後面的內核移植一節將詳細論述這些函數介面的實現。

啟動新任務的主要功能是將任務的初始上下文複製給處理器的各個寄存器，這包括通用寄存器、堆棧指針寄存器、狀態寄存器和指令指針寄存器等。這些初始值在新任務創建時被初始化。啟動新任務發生的時機有兩種情況，第一種情況是內核初始化完畢后，啟動第一個任務；第二種情況為任務主動結束后，當前任務指針被置位NULL時。

任務切換髮生在兩個任務之間，一個是被換切換出去的任務，另一個是將要執行的任務。任務切換函數也由彙編代碼實現。它所要完成的工作主要有兩個，第一是將舊任務（被換切換出去的任務）的上下文保存到自己的棧中，第二是新任務（將要執行的任務）將保存在棧中的上下文複製到處理器的相關寄存器中。任務切換的發生時機有：

· 當前任務執行時間到；

· 當前任務被高優先順序任務搶佔；

· 當前任務休眠，或等待某事件發生。

由於任務切換與處理器關係緊密，本章只介紹與處理器無關部分的實現，與處理器有關的部分將在內核移植一章中詳細論述。

4.4.5 內核時鐘實現

在內核時鐘一節中，論述了內核時鐘的作用以及功能。但在當前實現中，根據實際的情況對內核時鐘的功能做了裁減，內核時鐘功能主要由systick( )函數實現。

4.4.6 任務管理API實現

任何內核都應該提供一組豐富的API函數供用戶使用。像UNIX、Linux、Windows這些大型操作系統提供了大量的API。當然這些API的數量、種類，用法等都會隨著系統的不同而不同。但在任務管理方面下面幾個API是必不可少的：任務創建、撤銷、休眠、等待和喚醒等操作。下面將描述各個API的實現演演算法。

4.4.6.1 任務創建

當用戶調用任務創建函數時，內核應該完成哪些工作呢？這和內核的實現方式，複雜程度密切相關。當前任務管理實現中，提供兩個任務創建函數osInitTask( )和osCreateTask( )。這兩個函數的原型如下所示：

void osInitTask(void (*pTask)()， uword_t TaskID， uword_t Prio， uword_t Time， uword_t StkSize);

void osCreateTask(void (*pTask)()， tcb_t *pTcb， uword_t TaskID， uword_t Prio， uword_t Time， stk_t *pStk， uword_t StkSize);

這兩個函數的主要區別為任務需要的TCB和棧空間是否為動態創建。osInitTask( )函數只需要傳遞任務起始地址((*pTask)())，任務ID(TaskID)，優先順序(Prio)，運行時間片(Time)和棧大小(StkSize)，任務的棧和TCB空間都為動態創建，棧和TCB空間處於系統的堆區。osCreateTask( )函數除了以上的參數外還格外需要*ptcb和*pstk兩個參數，這兩個參數分別指向任務的TCB起始地址和棧起始地址，這個函數的空間需要在編譯時制定，棧和TCB空間屬於內核區。雖然它們需要的參數不同，但它們的實現演演算法是相同的。

在描述演演算法之前需要對任務棧做簡單的論述，棧的作用是保證任務正常運行，它保存了任務中各個函數的調用軌跡和返回地址。對於處理器來說都提供一個獨立的寄存器或者其他空間保存著棧頂的位置，各種處理器架構對棧頂和棧底的定義也不相同，這主要有兩種，一是棧頂的地址值大於棧底，其二相反。第一種伴隨著棧往下增長，第二種棧往上增長。為了便於移植內核，內核應該處理這兩種情況。除了這兩種情況，棧還分為滿棧和空棧兩種，所以內核必須考慮這幾種棧方式。因此在實現中提供一組宏來應對這些情況，如下所示：

#define UP 1

#define DOWN 0

#define FULL 1

#define EMPTY 0

#define STACK DOWN

#define STACK_STYLE FULL

UP和DOWN定義了棧的增長方向，FULL和EMPTY說明了是滿棧還是空棧。最後用STACK和STACK_STYLE聯合說明真正的棧工作方式。

論述完了任務創建方面需要注意的一些問題，下面論述任務創建的演演算法。任務創建過程主要包含初始化TCB和棧區，如果調用osCreateTask( )函數，在初始化前還需要向內核申請TCB和棧空間。圖4-9為osInitTask( )函數創建新任務的流程圖。

4.4.6.2 任務撤銷

每個任務都有一個生命周期，包括任務創建、運行與撤銷。任務撤銷也可稱為在多任務系統中，任務也可以被任何用戶殺死，也可以有特殊用戶殺死。比如，殺死任務。任務撤銷的方式有很多種實現方式。一般情況下，任務可以被內核殺死。在Linux下有些任務可以被任何用戶殺死，有些則只能由root用戶殺死。在單用戶系統中，用戶任務能被內核殺死，也可以被其他用戶任務殺死，但后種情況不多見。根據實際的情況，當前對任務撤銷的實現為只有任務自己主動殺死自己。

在當前實現中，任務撤銷的函數為osKill( )，如果當前任務完成了自己的使命，可以調用該函數。osKill( )會釋放掉該任務的相關資源，如TCB和棧空間等。osKill( )只釋放掉內核分配的資源，如果任務的運行過程中申請了其他資源，應該在調用osKill( )前釋放掉這些資源。任務在創建時有兩個創建函數osInitTask( )和osCreateTask( )，osKill( )只能釋放osInitTask( )的資源，而osCreateTask( )的資源會被保留下來。這是因為osCreateTask( )所使用的空間屬於內核空間，而不屬於系統動態內存管理的堆區，這部分區域沒有相關的數據結構管理，一旦釋放系統就會崩潰。根據上面的描述可以設計出osKill( )的演演算法，該演演算法如圖4-10所示。

4.4.6.3 任務休眠與喚醒

當任務需要等待某些資源的時候，可以將自己設為休眠狀態，把運行的機會讓給其他任務，當所等待的資源或者事件發生時，任務再被喚醒繼續運行。這種方式也是解決任務同步的一種辦法，如任務A與任務B合作完成某項任務，且A完成後B才能運行，休眠與喚醒機制可以很容易地解決此問題。內核實現了兩個函數分別完成這兩項工作，他們是osSleep( )和osWakeUp( )，osSleep( )是任務的主動行為，因此不需要參數，osWakeUp( )需要一個參數TaskID，該參數指定了需喚醒任務的ID號。

當任務調用osSleep( )后，該任務的TCB從就緒隊列中刪除，並插入到休眠隊列（如圖4-6所示），然後重新調度。如果任務A需要喚醒正在休眠的任務B，那麼A可以調用osWakeUp( )函數，並傳入B的ID。osWakeUp( )就會查找休眠隊列，如果找到任務B，則將它的狀態置為就緒，並從休眠隊列刪除插入就緒隊列。

4.4.6.4 任務等待

任務等待與任務休眠的實現原理都一樣。任務在等待一段時間后再獲得運行的機會，這個時候它所等待的事件或者資源有可能不可用，這點和任務休眠是有差異的。例如任務A需要與串口I/O通信，由於串口速度相對較慢，任務A大部分時間都需要等待，如果任務A在沒有數據傳輸的時候進入等待狀態，將會顯著提高CPU利用率。

內核提供了osWait( )函數來實現此功能，該函數接受一個時間參數，該參數說明當前任務等待時間長短，該時間以系統tick為單位。當前任務調用此函數后，任務狀態被置為等待態，TCB從就緒隊列中刪除，並插入到等待隊列，最後調度scheduler( )。等待隊列與休眠隊列相同，見圖6-7所示。osWait( )函數的流程圖與osSleep( )演演算法相似，這裡不再贅述。

每次系統tick發生中斷時，內核時鐘中斷處理程序更新等待隊列上任務的等待時間域，也就是任務控制塊TCB的delay_time域作減1操作，當此域減少到0時，表示該任務的等待時間已到，這時它將從等待隊列中刪除，並插入到就緒隊列中。這些工作也是內核時鐘中斷當前唯一需要做的事情。

軟體名稱：任務管理

英文名稱：Any To Do

軟體類型：效率

軟體版本：1.28

軟體語言：英文，中文等

軟體大小：7.60 MB

軟體現價：￥40.00 （請以iTunes實時價格為準）

支持系統：需要iOS 5.0 或更高版本

支持終端：iPhone、iPod touch、iPad兼容，已針對 iPhone 5 進行優化。

《任務管理》是一款待辦事項類的效率軟體，只要輸入您的待辦事項，它就會立即快速整理，高效率地按排好您的公事與私事。它不只是協助您安排好您的任務，而且還會幫助您把每項活動安排得漂漂亮亮、井井有條。

✓ 安排好您的時間而不是您的To-Dos(待辦事項)

✓ 與Evernote同步 - “記住所有的活動”

✓ 通過Evernote與Any To Do 的iPad/ iPhone版無線同步

✓ 可以創建您的全部私事與公事To-Dos(待辦事項)列表並可單獨或同時在四個象限內查看具體內容。

✓ 可以把您的To-Dos(待辦事項)添加到您的日曆中

✓ 可以設置提醒和重複提醒

✓ 有完整的屏幕定製功能及提醒語音

✓ 可以把您的To Dos (待辦事項)發布或Tweet 到您的Facebook塗鴉牆或Twitter帳戶上

✓ Any To Do適用於英語、中文、日語、西班牙語和義大利語, 德和法國。

應用類別 :工具

應用版本 :1.0.0.0

應用大小 :1 MB

應用語言 :中文

支持平台 :WP8,WP8.1

更新日期 :2014-06-22

這是一個任務管理應用。它能幫助管理各種任務，還能為重要任務設置鬧鐘。

任務管理

將任務固定到桌面

為任務設置鬧鐘

改變任務狀態

標記重要任務

任務排序

共享任務信息。