16. 即時作業系統 (Real-time Operating System)

Attachment大小
Microsoft Office document icon RTOS演算法.doc35 KB
  • 定義:  

  即時作業系統(Real-time operating system,RTOS),是指作業系統要在一個固定時間內,做出正確反應,以及對時序及穩定度的要求十分嚴格,它會按照排序執行、管理系統資源,並為開發應用程式提供一致的基礎。 

  即時作業系統相較一般的作業系統,最大的特色就在於「即時性」,也就是說,如有一個 process 需執行,即時作業系統會在最短時間內執行該 process ,不會有較長的延遲。這種特性保證了各個 process 的即時執行。通常都具備有最基礎的 kernel,以及外加上去的模組,像是檔案系統、網路協定堆疊和應用、裝置驅動程式……等模組。RTOS 的核心通常包括,排程器、物件、服務程式。 

  衡量一個即時作業系統堅固性的重要指標,是他從接收一個 process,到完成該 process 所需的時間,其時間的變化稱為 jitter。硬即時作業系統比軟即時作業系統有更少的 jitter。設計即時作業系統的首要標的不是高的 throughput,而是保證 process 在特定時間內完成。 

  即時作業系統可分類為「軟式(Soft)」與「硬式(Hard)」。硬即時作業系統,是指系統從命令起始到執行動作之間的中斷延遲回應特性。一般像是 Win CE 這種的軟即時作業系統,其反應時間約為 1~2ms,要達到硬即時性能的要求,其反應時間必須要在 150μs 以內;軟即時系統通常指超過期限後,系統的公用程式可容忍某段誤差時間。舉例來說,當行動電話來電時,則必須在按下按鈕時即建立連結。然而,此限制時間並非絕對,亦可有些許的延遲。 

  硬即時作業系統必須使 process 在確定的時間內完成,而軟即時作業系統能讓絕大多數 process 在確定時間內完成。

 

  • 演算法和行程排班:

 

RTOS多任務運行的實現實際上是靠CPU在許多任務之間轉換、調度。CPU只有一個,輪番服務於一系列任務中的某一個。多任務運行使CPU的利用率得到最大的發揮,並使應用程式模組化。在即時應用中,多任務化的最大特點是,開發人員可以將很複雜的應用程式層次化,而且應用程式將更容易設計與維護。  因此在多任務即時操作系統RTOS中涉及到任務調度,任務調度機制是嵌入式即時操作系統的一個重要概念,也是其核心技術。針對嵌入式即時系統任務的管理和調度的特點,在多任務即時內核結構中,多數採用的是基於優先順序的可搶佔式調度策略。系統為每一個任務分配一個優先順序,調度程式總是選擇優先順序最高的就緒任務運行。內核運行中頻繁地進行任務調度,調度速度緩慢時,會影響整個系統的回應速度和處理能力。因此,關於最高優先順序就緒任務的查找演算法是即時多任務系統的關鍵技術

 

本文給出64個優先順序任務內核的不同最高優先順序就緒任務查找演算法,通過實例詳細闡明其原理,並分析了各個演算法的優缺點

 

 

 

 

最高優先順序就緒任務查找演算法:順次檢索法  關於最高優先順序就緒任務的查找,有多種處理方法,其中最簡單最基本的方法是順次檢索。將所有的任務按照優先順序排隊,優先順序高的排在佇列前邊,優先順序低的排在佇列後邊。查找時從佇列的頭部開始,遇到的第一個就緒任務就是優先順序最高的就緒任務。假如即時系統共有n個任務,按照優先順序別的高低,順次存入數組Tb[n]中。當某一優先順序別的任務處於就緒態時,就在相應的佇列處置就緒態標誌。在系統進行任務調度的過程中,只要從佇列的頭部開始,依次查找就緒態標誌,找到的第一個具有就緒態標誌的任務就是優先順序別最高的就緒任務。該方法思路簡單,查找便利,但存在的缺點是不同優先順序任務查找時所需要的時間不同,系統中的任務數越多,且最高優先順序就緒任務越靠後,則查找速度越慢。

 

逐次比較法 

 

 可以發現,最高優先順序就緒任務是可以通過OSRdyGOSRdyT [ ]求出來的,下面介紹一種普通的逐次比較,求最高優先順序就緒任務演算法。首先,從OSRdyG的最低位往最高位比較搜索,若為1停止,最高優先順序就緒任務就在此位對應的OSRdyT [n]中;然後找到OSRdyT[n]中為1的最低位,那麼就可以確定最高優先順序就緒任務。

 

其演算法描述如下:  

 

     for(i=0;i<8;i++)      

 

 { if (OSRdyG & OSMap [i])     

 

   break;       }      

 

  for(j=0;j<8;j++)     

 

 {         

 

  if (OSRdyT [i]& OSMap [j])      

 

  break;       }      

 

  highprio=i<<3+j;  

 

顯然,用迴圈程式實現不但複雜,更重要的是執行時間是不確定的,因為有時只需一個迴圈即可,而有時需要8個迴圈,不符合即時系統的確定性原則。為了加快即時系統的執行速度,可以採用查表方法進一步改進演算法

 

 

 

 

 

查表法:

為了減少以上演算法所造成的時間損耗以及不確定性。採用查表的方法實現最高優先順序就

 

緒任務的查找,在程式中事先建立一個存儲表,保存在數組OSUnMapT [255]中,存儲值表示OSRdyGOSRdyT[n]的值相對優先順序別高三位和低三位的映射值。存儲值內容見表1。  例如,若OSRdyG的值為二進位00100100b,即0x24,則查OSUnMapT [OSRdyG]得到的值是2,它相應於OSRdyG中的第2bit2,類似地,如果OSRdyT[2]的值是二進位11000010,即0xC2,則OSUnMapT[OSRdyT [2]]的值是1,即第1bit1。於是就緒任務的最高優先順序就等於8進制21,即172*8+1)。  因此利用該表,可以用固定 的三條程式指令就計算出就緒任務最高優先順序的;計算就緒任務最高優先順序的演算法如下:  

 

       high3 =OSUnMapT [OSRdyG];                                

 

       low3 =OSUnMapT[OSRdyT [high3]];                     

 

       highprio =(high3<<3)+low3;                          

 

兩種演算法對比可知,後者是用儲存空間來換取了執行時間;而對於一個操作系統,任務調度是十分頻繁的,這一點空間相對其換取回來的寶貴CPU時間是微不足道的。可以採用這種策略,從而使其實時系統性能得到大大的提高。  對具有相同優先順序的任務可以用時間片輪轉或者先進先出方式,來搶佔CPU。然後調度程式先檢查該任務當前是否處於運行狀態,如果該任務正佔用CPU,則不進行任務調度,調度程式退出;如果沒有佔用CPU,則進行任務調度,讓找到的最高優先順序的就緒任務開始運行。

 

 

對於即時行程的排程,有許多功能更強大及更合適的方法紛紛被提出來討論。這些方法基本上都需要作業系統擁有各個行程的一些附加的資訊。一般來說,對於各個行程,作業系統需要擁有下列資訊:

 

1.備妥時間(Ready Time):行程準備好開始執行所需花費的時間。對於週期性的行程而言,備妥時間實際上是一連串事先預知的時間。對於非週期性的行程而言,備妥時間可能事先預知,或者是等到行程確實準備好之後,再通知作業系統做適當的處理。

 

2.啟始期限(Starting deadline):行程必須開始執行的時間。

 

3.完成期限(Completion deadline):行程必須完成其工作的時間。典型的即時應用程式可能會要求啟始期限,或者是完成期限,但不會同時要求兩者。

 

4.處理時間(Processing time):工作執行直到完成所需的時間。有些情況下,應用程式會提供這項資訊。有些情況下,作業系統會自動測量其指數平均值。有些情況下,作業系統不會使用這項資訊。

 

5.資源需求(Resource requirements):行程在執行時所需要的所有資源(除了處理器之外)。

 

6.優先權(Priority):提供了行程之間重要性的相對關係。迫切性的即時行程可能會提供絕對的優先權,如果無法滿足它對於期限的要求,則這個系統便無法正常運作。如果系統在任何情況下都想繼續運作(即使某個迫切性的即時行程對於期限的要求無法被滿足),則可以為迫切性與非迫切性的即時行程指定相對的優先權,提供排班機制作為排班的依據。

 

7.次行程的結構(Subtask structure):行程可以被分解為強制性的次行程及附加性的次行程。只有強制性的次行程才需要指定工作期限。

 

排班機制在考慮行程執行期限的問題時,有許多層面需要考量,例如:系統應該根據什麼條件以選擇下一個行程來執行﹑系統應該允許什麼種類的搶先機制。我們通常必須針對系統的應用場合,來決定要採用什麼樣的排班策略。

 

 

 

 

 參考資料http://murphymind.blogspot.tw/1997/06/rtos-concepts.html

  • 設計理念:
  • Thread 導向的設計

    為了降低複雜度,通常會採用 threads 導向的設計,把一個專案切分成比較易於管理的小塊(也就是 threads),而後每一個 thread 負責該應用程式的一部分。這樣的系統有助於識別 threads 之間的重要順序。也就是說,某些 threads 具有即時性的需求,必須盡量快速並且正確地回應它們。如果你的系統採用了專業的 RTOS,一定會有劃分 threads 優先權 (prioritization) 的設計。除了優先權之外,也會提供一套乾淨而且被仔細測試過的 API,有助於簡化 threads 之間的通訊。

    所以如果我們採用 RTOS 的話,就會獲得一些工具能夠:

    • 確保能夠在即時約束條件 (real-time constraints) 內執行時間關鍵 (time-critical) 部分的程式碼。或許同樣都很重要,但高優先權的 threads 所需要的即時行為,並不會受到低優先權 threads 的影響。
    • 確保易於開發和維護複雜的應用。開發和維護小的 threads,比起硬搞整套應用更為容易。此外,對於低優先權 threads 的更動也不會影響到高優先權 threads 的即時處理。
    • 能夠將整體應用程式的不同部分,分派給多個開發人員。每一個開發人員能夠擔負應用程式的一個或多個 threads,而且當他們在進行開發工作時,還會有一套乾淨的 API 能夠讓不同的 modules / threads 相互溝通。

    採用 RTOS 的話,你不但能夠創建 threads,同時也具備一些讓它們能夠彼此溝通的工具,再加上能夠確保能夠在即時約束條件內執行完畢 threads 具時間關鍵的部分工作。由於採用了 RTOS,不同 threads 之間的介面將會變得非常乾淨,在進行開發的時候你就可以省時省力。

    RTOS 如何工作?

    RTOS 的核心被稱為 kernel,並提供有一個可以透過 kernel 去創建 threads 的 API。一個 thread 就像是一個擁有自己的堆疊、並帶有 Thread 控制區塊(TCB – Thread Control Block)的函式。除了 thread 本身私有的堆疊之外,每個 TCB 也保有一部分該 thread 的狀態訊息。

    kernel 還包含有一個 scheuler,scheuler 會按照一套排程機制來執行 threads。各種 scheulers 之間主要的差異,就是如何分配執行他們所管理之各種 threads 的時間。基於優先權的 preemptive scheuler 是嵌入式 RTOS 之間最流行和普遍的 threads 調度演算法。通常情況下,相同優先權的 threads 會以 round-robin 循環的方式加以執行。

    多數內核還會利用系統時脈 (system tick) 中斷,其典型的頻率為 10ms。如果在 RTOS 中缺乏系統時鐘,仍然能夠有某種基本形式的調度,但時間相關的服務則否。這種與時間有關的服務內容包括:軟體定時器、thread 睡眠 API 呼叫、thread 時間片段、以及逾時的 API 呼叫。

    為了實現系統時脈中斷,可以透過嵌入式晶片的硬體計時器。大多數的 RTOS 有能力動態地擴增或重新設置計時器的中斷頻率,以便讓該系統進入睡眠,直到被下一個計時器期限或外部事件喚醒。例如,如果你有一個對耗能敏感的應用程式,您可能不希望每 10ms 就運行一次不必要的系統時脈處理程序。所以假設應用程式處於閒置狀態,想要把下一個定時器期限改為 1000ms。在這種情況下,計時器可以被重新規劃成 1000ms,應用程式則會進入低功耗模式。一旦在這種模式下,處理器將呈現休眠狀態,直到產生了外部事件、或是計時器的 1000ms 到期。在任一種情況之下,當處理器恢復執行時,RTOS 就會根據已經經過了多少時間來調整內部時間,並恢復 RTOS 和應用程式處理。如此一來,處理器只會在執行應用程式有事可做時進行運算。空閒期間處理器可以睡眠,並且節省電力。

     

    參考資料:http://zh.wikipedia.org/wiki/即時作業系統

    http://cms.mcuapps.com/devscenes/ds0001/

  • 硬即時和軟即時的比較:
  • 在很多的書及文獻上我們可能會看到『硬即時(hard real-time)』和『軟即時(soft real-time)』這二個名詞。不同的人會給它們不同的意義,但大致來說它們是一組相對的概念。有些人會從工作的特性上來分,例如我們常會用核能電廠和看 VCD 為例,用在核能電廠的即時作業系統如果出了差錯可能會導致嚴重的損害,然而 VCD Player 出了些差錯不過是讓使用者認清它所用的程式不夠好而已。所以前者是硬即時,後者是軟即時。

    但在大多數的狀況下,分野並不是如此的清楚。做 VCD Player 的廠商當然不希望它的 Player 老是出錯,它也會希望 Player 用一個硬即時作業系統來驅動。所以硬即時和軟即時的差別可能只是分類學上的問題而已。以下表格為統整出來的資料: 

     

     

    硬性即時作業系統

    (Hard Real-Time System)

    軟性即時系統

    (Soft Real-Time System)

    簡介

    也可稱為安全臨界系統(Safety-Critical System),有最迫切的需求,必須在特定期限之前回應事件,保證在它們的期限內完成臨界即時任務。

    跟硬性即時系統比較起來,限制的範圍比較少,簡單提供一件臨界的即時系統,將在其它的任務上接受優先權並保有優先權直到它完成。

    應用

    通常指不能有任何差錯的工作,一般而言,與安全相關的系統均屬於硬即時系統。

    例如:軍事系統、核能安控、車用電子煞車系統…等。

    比較容許差錯的工作,即時工作的執行擁有最高的優先權即可,直到執行完畢為止。

    例如:多媒體播放器…等。

    工作延遲

    所有工作都不能夠延遲

    允許少量的工作延遲,若沒有在回應時間內完成,只是造成系統的效能變差,不會影響系統的執行

    要求

    非常嚴苛

    比較寬鬆

    參考資料:

    http://pastahuang.pixnet.net/blog/post/51620470-即時作業系統是如何演進的

    http://etd.yuntech.edu.tw/dmdocuments/etd-0823111-143458.pdf

    http://blog.xuite.net/jackie.xie/bluelove/5555541

    http://www.ni.com/white-paper/3938/zht/

    http://web.ydu.edu.tw/~hjw/course/esd/9402_sw/Ch01.pdf

    http://linux.sheup.com/linux/linux5162.htm

    http://mail.tku.edu.tw/jingo/informationoverview100/ch-03.pdf

  • 案例:
  • WinCE、VxWorks、μC/OS-Ⅱ等运用较广。Linux是作为通用操作系统开发的,其内核在实时处理能力上先天不足,部分网络开发社区将其经过改造能在一定程度上成为实时操作系统。下面例舉比較其優缺點:

    1. embedded Linux, ucLinux

    優點: 系統完整, 功能強大, 支援各種 file system, TCP/IP stack, communication protocol stack, 發展工具齊全(GNU toolchain), 網路上高手多, 

    缺點: 是否歸類於 RTOS 仍有爭議, 只支援 32-bit CPU, 複雜度高, device driver 架構稍大, 移植難度較大, 編譯後的 file footprint (kernel + application) 過大, 新手較難維護, scheduling mode 較少, hard-real time scheduling 的支援度待改進.

    2. e-Cos

    優點: 發展工具齊全(GNU toolchain), 模組化程度非常好, 支援的 CPU 架構多, 複雜度較低, device driver 架構比較簡單, 移植容易, 編譯後的 file footprint 小, 有專門的公司定期更新版本.

    缺點: 支援的 file system, TCP/IP stack 和 communication protocol 較少, scheduling mode 較少, 網路上高手較少, 出問題要找專人解決時的顧問費用不低.

    3. uc/OS-II

    優點: 支援的 CPU 架構多, 系統單純, 學習容易, 書籍內容精彩, device driver 發展容易, 移植容易, 編譯後的 file footprint 非常小, 有專門的公司維護版本.

    缺點: 發展工具少( borland C/C++ only. 但可改用 GNU toolchain). 沒有 file system 和 TCP/IP stack (要自己解決), scheduling mode 較少, 網路上高手較少. 商用授權費不低.