歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux綜合 >> Linux資訊 >> 更多Linux

基於Linux的實時操作系統二(組圖)

RED-Linux調度程序的框架結構如圖 2所示:
  
   圖 2 RED-Linux調度框架
   
  RED-Linux的調度程序由兩部分組成,其中Schedule Allocator初始化到來的job中的屬性值;Schedule Dispatcher根據job的屬性值選擇一個job進行執行;
  
  3.4. Linux/RK
  
  Linux/RK 由卡內基梅隆大學實時和多媒體系統實驗室所開發[RKWeb][ Oikawa98]。它是該實驗室資源內核(Resource Kernel)[Rajkumar98]思想在Linux系統中的具體實現。他們最先在RT-MACH中實現了資源內核的思想,後來又用資源內核的思想對 Linux進行了修改。資源內核的概念是網絡中資源預留思想在操作系統領域的擴展,應用程序先向操作系統請求預留資源,而操作系統內核在給應用進行資源預留,並能給應用提供有及時的、保證的資源訪問。
  
  資源內核中有兩個基本的概念:資源預留和資源集。一個資源預留代表一份計算資源,這個資源可以是CPU、內存、磁盤、網絡帶寬等。在內核中,一個資源預留有對應的描述它的數據結構,而一個資源集指一組資源預留的集合。一般情況下我們將某一個應用程序所請求的所有資源預留組合在一起組成一個資源集,這樣方便管理和分配。
  
  Linux/RK增強了普通Linux內核的功能,從而使Linux內核可以提供對於系統中各種計算資源的准入控制、資源預留和統計管理。Linux/RK由兩部分組成:普通的Linux內核以及可移植的資源內核;這兩個部分之間通過回調鉤子函數(Callback hooks)進行交互。類似於RT-Linux,為了防止Linux內核中的封中操作以及提高調度精度,Linux/RK也截取系統中的中斷,並提高了系統時鐘頻率,只有在需要的時侯才將中斷送給Linux內核。另外它使用Proc文件系統來顯示資源預留和使用的情況;
  
  3.5. Qlinux
  
  Qlinux是由AT&T、德州大學分布式多媒體計算實驗室和馬薩諸塞大學高級系統軟件實驗室聯合開發出來的一種軟實時(soft real-time)核心[QLinuxWeb]。它能夠為實時多媒體應用提供QoS支持。
  
  QLinux實現了近年來操作系統領域內一些最新的研究成果,包括:
  
  - H-SFQ資源調度算法(Hierarchical Start-time Fair Queuing)[Goyal96];
  
  - 網絡包的延遲處理技術(Lazy Receiver Processing:LRP)[Druschel96];
  
  - Cello磁盤調度算法[Shenoy98];
  
   圖 3 QLinux系統結構
   
  H- SFQ資源調度算法由由德州大學的Pawan Goyal等人提出,它采用了一種分級調度的思想,先將資源在不同的應用類別之間進行按比例分配,並在應用類別之間提供對於資源使用的隔離,同時在每一個應用類別中還可以使用不同的資源調度算法。這樣做的目的是為了在多媒體系統中提供QoS支持。
  
  LRP技術是一種新穎的設計OS網絡子系統的思想,它由Rice大學計算機系的Peter Druschel等人提出,其目的是為了解決普通Unix和類Unix系統中網絡包接收的問題。
  
  傳統的Unix系統沒有對到來的網絡包的協議處理的顯式調度,它們一般采用中斷驅動的機制。當網卡有中斷時,CPU就立刻進行一系列由網卡中斷程序啟動的包接收和協議處理操作,將最終的數據送給等待接收的進程,並喚醒該進程。但這種處理方式會影響應用程序資源調度的性能,並在系統處於過載狀態時可能會引起一些應用層任務的饑餓,降低網絡吞吐率,甚至會讓系統沒有響應。為了解決這些問題,LRP的核心思想就是每一個Socket有一個IP包的隊列,只有當上層應用程序請求數據時才進行協議處理,同時對協議處理操作以請求數據的應用的優先級進行顯式的調度。通過這種途徑增強了資源調度的公平性,能夠提供一定程度的流量隔離,同時能夠提高系統過載狀態時的吞吐量。
  
  Cello磁盤調度算法由德州大學Prashant J. Shenoy等人提出。它能夠支持多種應用類別,比如:交互式盡力而為應用、大吞吐量盡力而為應用、以及軟實時應用等類別,並公平地給各個類別的應用分配磁盤訪問帶寬。
  
  在結構上Cello磁盤調度采用的是一種兩級式的調度方式,它由多個與應用類別相關的調度器以及一個與應用類別無關的調度器組成(如圖 4所示)。
  
   圖 4 Cello磁盤調度
   



  Cello 調度算法中應用類別無關的調度器管理時間上粗粒度的磁盤的調度,而應用相關的調度器控制著小粒度上磁盤調度。如上圖中有n個應用類別,Cello使用一個應用無關的調度器C和n個類別相關的調度器,系統中有n+1個調度隊列。類別無關的調度器C決定你了何時以及多少磁盤請求被從等待隊列(pending queue)移到調度隊列(scheduled queue);類別相關的調度器Si對等待隊列中的請求進行排序,並根據調度隊列的狀態來決定磁盤請求被插入到調度隊列的什麼位置。
  
  3.6. Linux-SRT
  
  Linux -SRT是劍橋大學David Ingram的博士論文項目[SRTWeb][Ingram00],基本上是一個實驗性的東西,自從Ingram在2000年從劍橋畢業以後,該項目就再沒有人維護。跟QLinux一樣,Linux-SRT屬於軟實時的Linux。
  
  在Linux-SRT中可以給一個任務分配一定百分比的CPU時間,它通過RM算法實現了一種基於速率的調度機制來保證給所有多媒體應用的QoS需求;另外由於CPU並非唯一影響多媒體應用的資源,對於那些做圖形顯示的應用,X服務器中的資源調度也十分關鍵,所以Linux-SRT對XFree86最了擴展,讓X服務器可以對來自不同X客戶的圖形顯示請求進行優先級排序;另外為了方便用戶管理各個進程的CPU分配情況,Linux-SRT提供了一個圖形界面的程序。下面對於Linux-SRT 對於普通Linux所作的修改做一具體說明。
  
  Linux-SRT也提高了系統的定時精度。但它並沒有采用慣用的將時鐘芯片置於單次觸發模式的做法,而是簡單地修改了Linux內核中HZ的定義,將Linux的時鐘頻率由每秒100次提高到了1024。
  
  另外Linux-SRT在原有的Linux系統中的SCHED_OTHER、SCHED_FIFO、SCHED_RR這三個調度策略的基礎上,給Linux 增加了一些新的調度策略:SCHED_PAUSE、SCHED_IDLE、SCHED_QOS、SCHED_VAR;策略為SCHED_PAUSE的進程在調度時被調度程序忽略,不參與調度執行;使用SCHED_QOS調度策略的進程能夠得到有保證的CPU執行時間;使用SCHED_IDLE策略的進程優先級最低,它被分配給那些只在系統空閒時才能夠被調度執行的進程,比如一些批處理程序;SCHED_VAR是一個可變優先級的策略,它被用於解決由於臨界資源訪問時所產生的優先級倒置問題,即一個高優先級的任務等待低優先級任務占用的某種臨界資源,但低優先級任務又得不到CPU處理時間所造成的死鎖問題;這時通過該調度策略將低優先級任務的優先級置為等待資源的高優先級任務的優先級(優先級繼承)來解決死鎖問題。
  
  對於使用SCHED_QOS調度策略的實時任務,采用RM靜態優先級調度算法進行調度;另外在進行調度時,它還采用了一種雙調度策略的方案,即當一個實時任務在當前的調度周期中用完自己所有的時間片之後,在下次調度周期到來之前,並非簡單地不調度執行它,而是使用它進程屬性中的Fallback policy所定義的調度策略來調度它,讓它以該策略參與本輪的剩余時間的調度。
  
  Linux-SRT按照POSIX推薦的方式擴展了傳統的幾個用戶設置進程調度屬性的系統調度,讓用戶或者編程人員可以在後向兼容的情況下使用這些新添加的調度特性。另外為了使用的方便,它還提出了reserve的概念,一個reserve在/proc文件系統中有一個結點,它包含有關資源分配的情況;reserve獨立與進程,一個進程可以通過新增加的reserve相關的系統調用申請加入(使用)或退出一個reserve。
  
  3.7. Hard-hat Linux
  
  Hardhat Linux是MontaVista公司所發布的一款主要面向各種嵌入式應用的Linux發布[HardHatWeb][Morgan01]。Hard- hat Linux最大的貢獻在於:為了解決Linux在內核態不可被搶占的問題,它開發了一種搶占式(Preemptible)的內核,有人認為它的這種方法充其量也就是一種能夠被搶占(Preemptable)的內核。
  
  其基本思想就是讓調度程序獲得更多的執行機會,從而減少了從一個事件發生到調度程序被執行的時間間隔。可搶占內核的補丁包修改了spinlock的宏定義以及中斷返回處理代碼,當當前進程可以被"安全"地搶占並且有一個等待處理的重新調度請求,系統就會調用調度程序進行進程調度。
  
  那麼什麼情況下可以認為一個進程可以被"安全 "地搶占?最早的Linux內核代碼認為,一旦進入內核態執行,不管是由於陷入(trap)還是中斷處理,當前執行進程都不會被切換,直到內核認為可以安全地進行重新調度為止。這種思想可以使得內核代碼對一些數據結構進行操作時比較簡單,即不需要使用互斥原語(比如旋轉鎖spinlock)進行數據的修改保護就可以安全地存取數據。但隨著內核源代碼的發展,不使用保護機制的內核數據訪問代碼越來越少,所以在搶占式內核中,認為如果內核不是在一個中斷處理程序中,並且不再spinlock保護的代碼中,就認為可以"安全"地進行進程切換。
  
  搶占式內核對普通Linux內核作了如下的一些修改:
  
  搶占式內核給task strUCt數據結構增加了一個數據項:preempt_count。該數據項由宏preempt_disable()、preempt_enable ()、以及preempt_enable_no_resched()所使用。preempt_disable對preempt_count計數進行遞增, preempt_enable對preempt_count進行遞減。preempt_enable宏查看當前進程的preempt_count和 need_resched域的內容,如果 preempt_count為0並且need_resched為1,則調用preempt_schedule()函數。該函數將給當前進程的 preempt_count項增加一個很大的值(比如讓preempt_counter=preempt_counter + 0x4000000),然後調用進程調度函數schedule(),在schedule函數返回後從該進程preempt_count中再減去該值。可搶占內核也修改了schedule函數,它檢測進程的preempt_counter是否很大(這是為了屏蔽一些普通調度流程中對於搶占式調度來說是冗余的那些操作),然後執行搶占式調度。


  
  搶占式內核補丁也修改了spinlock的代碼。在spin_lock()和spin_try_lock中增加了對於preempt_disable的調用,在spin_unlock()中增加了對於preempt_enable的調用。
  
  另外搶占式內核補丁還修改了中斷返回的代碼,在其中增加了對於preempt_enable的調用。
  
  所以我們根據上面的三個修改可以看出,內核的搶占式調度發生在如下情況:在釋放spinlock時,或者當中斷返回時,如果當前執行進程的need_resched被標記,則進行搶占式調度。
  
  3.8. SILK
  
  SILK代表SCOUT In Linux Kernel,它是普林斯頓大學支持PATH調度的垂直結構操作系統SCOUT在Linux中的一個實現[SILKWeb][Bavier01]。它將SCOUT操作系統作為Linux的一個模塊來實現。
  
  SILK 系統的主要目的就是為一些網絡QoS提供支持,它支持對於網絡包處理的顯式的調度,並且這個調度是以PATH為單位進行的。PATH概念的新穎之處在於,不像傳統的基於任務的調度方式,它從另外一個角度進行系統的資源調度,即以網絡的數據流及其處理為單位進行調度。詳細來說,一個PATH由一串當數據流流經系統時進行數據處理或者數據轉換的代碼模塊組成,並且對應的數據流所消耗的資源也歸該PATH。研究表明,PATH這種體系結構特別適用於有QoS要求的分布式多媒體系統以及軟件路由設備中。下圖對於什麼是PATH作了一個圖示,它說明了一個TCP PATH:
  
   圖 5 一個TCP PATH
   
  在實現上,SILK系統將Linux系統中的網絡子系統替換成了自己的協議棧。Linux應用程序通過Socket來創建和使用PATHs,幾乎不用對應用程序本身作任何修改。
  
  圖 6說明了SILK系統的結構。在圖的左半部分,SILK模塊和網絡設備驅動、SOCKET接口層、以及包過濾接口netfilter通過標准的方式交換數據。SILK還修改了Linux任務的調度參數,以便影響Linux進程調度程序的調度決策。圖的右半部分示意了SILK中的兩個PATH。SILK模塊有自己的CPU調度器,它和Linux系統中的CPU調度器進行合作和協調。這個合作由圖中的Linux thread代表,通過執行這個線程,SILK將控制轉給Linux調度程序。
  
   圖 6 SILK系統結構示意圖
  
  SILK 在操作系統中提供了一個新的SOCKET協議族以便上層應用程序調用下層的SCOUT PATH。為了在Linux進行網絡包處理之前截獲IP包,SILK通過Linux 2.4內核的netfilter接口插入了一個netfilter hook,所有到來的IP包會被重定向到該hook上,如果SILK找到一個對應於該網絡包的PATH,就讓Linux內核丟棄該包,而由SILK對包進行處理。
  
  關於CPU調度,SILK有著自己的CPU調度程序和線程包,它們和Linux系統的調度程序並存,在有 SILK的Linux系統中,我們一般把由SILK調度的歸屬於某個PATH的處理叫做SILK線程(thread),而普通的由Linux調度程序調度的東西都叫做任務(task);SILK在一個Linux內核任務的基礎上實現它的線程調度,這個內核任務當SILK進行初始化的時候創建,並且將該內核任務的優先級設為優先級最高的實時任務,所以SILK的內核任務幾乎是只要它就緒就可以投入運行,並且只有當該內核任務主動初讓CPU時Linux系統中的其他普通任務才能夠得以運行。SILK將CPU出讓給普通的Linux任務是通過調度SILK thread中的一個叫做Linux thread的線程來實現的,該Linux thread本質上就是在SILK的調度空間中代表Linux的普通調度程序。SILK在調用Linux thread之後,代表SILK的內核任務就被Linux的進程調度程序設置為非就緒狀態,直到它運行一個其他的進程之後,高優先級得SILK內核任務就又得到 CPU。所以這種實現機制可以讓SILK在調度Linux thread時,Linux調度程序可以有機會調度一個其他的進程執行。
  
  4. 實時Linux實現方案的總結
  
  總結上述的各種實時Linux的實現,它們針對不同的設計目標,從不同的側重點解決了通用Linux操作系統對實時性支持的問題。
  
  針對Linux系統定時粒度過大的問題,一般的解決辦法都是將實時時鐘編程為單次觸發的狀態,然後利用CPU的時鐘計數寄存器提供高達CPU時鐘頻率的定時精度。像RT-Linux和Kurt-Linux采用的就是這種方法。
  
  對於Linux進程在進入內核態時不能被搶占的問題,目前的解決辦法有RED-Linux在內核函數中插入搶占點的方法,另外Hardhat也通過修改spinlock的宏定義以及中斷返回處理代碼,實現了一種可搶占的內核;
  
  對於Linux驅動程序中的封中斷的方法,RT-Linux所使用的軟件模擬中斷控制器的方法可以有效地解決這個問題;
  
  對於Linux系統中缺乏實時調度機制和調度算法的問題,目前有很多新穎的操作系統調度框架和調度算法都有Linux實現,比如RED-Linux所定義的一個通用的實時調度框架;QLinux所采用的分層式的CPU調度框架,及新穎的調度算法如H-SFQ,以及Cello磁盤調度算法等;SILK所使用的將對一個包的網絡處理抽象成PATH,然後在PATH之間進行調度。
  
  對於內核中協議處理以及中斷處理的調度,解決辦法基本上是一種延遲處理的技術,即到來的協議包在網卡中斷處理中僅僅將它拷貝到一個隊列中,只有當上層的應用程序請求數據包時才進行協議處理,並將對協議的處理時間記到對應的進程中。另外SILK對於那些網絡路由結點,由於路由等的處理並沒有對應的上層應用程序,所以SILK在內核的網絡處理之間進行明確的調度。


  
  所以,總的來說,從發展方向上來說,實時Linux的發展有如下四個思路:
  
  提供對於硬實時的支持,具體辦法有:提高時鐘精度,解決封中斷和內核態不能被搶占的問題,代表系統RT-Linux、Kurt-Linux,其實大部分實時 Linux都使用了類似與RT-Linux的提高時鐘精度和軟件中斷管理器的思想;總的來說,讓內核支持硬實時和使用傳統的Linux的豐富的系統調用之間存在著矛盾,以至於像RT-Linux就是單獨實現了一個獨立的小的硬實時操作系統;但由於軟件模擬終端控制器、提高時鐘精度、以及可搶占內核等思想的引入,這個矛盾慢慢地得到化解。
  
  提供對於實時多媒體應用的支持,舉措:引入新穎的調度算法(網絡包調度,進程調度,磁盤調度),代表系統:QLinux、Linux-SRT;
  
  引入新穎的調度框架以及資源管理思想以更好地支持網絡系統中的QoS要求,比如SILK中的垂直結構的操作系統調度的思想,QLinux中的分級調度的思想,以及RED-Linux所提出來的一個通用的調度框架和Linux/RK中所使用的資源預留的思想;
  
  方便的任務QoS管理接口函數和管理程序的實現,比如Linux/RK提出的操作系統中各種資源的資源預留的概念;Linux-SRT中為了用戶方便地使用新增加的實時調度支持而增加了API,以及提出的reserve的概念等;
  
  在實際的系統中,具體使用那種實時Linux技術,需要根據具體的系統需求而定。如果目標系統是像機床控制或者導彈飛行姿態控制這樣的硬實時系統,那基於 RT-Linux是一個不錯的方案;如果一個系統對於實時性的要求不是那麼嚴格,但又不是軟實時系統,那麼可以借鑒Kurt-Linux的想想以及一些為了提高Linux響應速度而提出的可搶占內核的想法;如果目標系統是一個像實時多媒體系統這樣的軟實時應用,或者一個希望能夠在高負載狀態下提供更好的吞吐率的服務器系統,那麼QLinux和RED-Linux的思想提供了很好的參考;如果是將Linux應用於像路由器這樣的網絡結點中,可以借鑒SILK 的實現思想。



  
  4. 實時Linux實現方案的總結
  
  總結上述的各種實時Linux的實現,它們針對不同的設計目標,從不同的側重點解決了通用Linux操作系統對實時性支持的問題。
  
  針對Linux系統定時粒度過大的問題,一般的解決辦法都是將實時時鐘編程為單次觸發的狀態,然後利用CPU的時鐘計數寄存器提供高達CPU時鐘頻率的定時精度。像RT-Linux和Kurt-Linux采用的就是這種方法。
  
  對於Linux進程在進入內核態時不能被搶占的問題,目前的解決辦法有RED-Linux在內核函數中插入搶占點的方法,另外Hardhat也通過修改spinlock的宏定義以及中斷返回處理代碼,實現了一種可搶占的內核;
  
  對於Linux驅動程序中的封中斷的方法,RT-Linux所使用的軟件模擬中斷控制器的方法可以有效地解決這個問題;
  
  對於Linux系統中缺乏實時調度機制和調度算法的問題,目前有很多新穎的操作系統調度框架和調度算法都有Linux實現,比如RED-Linux所定義的一個通用的實時調度框架;QLinux所采用的分層式的CPU調度框架,及新穎的調度算法如H-SFQ,以及Cello磁盤調度算法等;SILK所使用的將對一個包的網絡處理抽象成PATH,然後在PATH之間進行調度。
  
  對於內核中協議處理以及中斷處理的調度,解決辦法基本上是一種延遲處理的技術,即到來的協議包在網卡中斷處理中僅僅將它拷貝到一個隊列中,只有當上層的應用程序請求數據包時才進行協議處理,並將對協議的處理時間記到對應的進程中。另外SILK對於那些網絡路由結點,由於路由等的處理並沒有對應的上層應用程序,所以SILK在內核的網絡處理之間進行明確的調度。
  
  所以,總的來說,從發展方向上來說,實時Linux的發展有如下四個思路:
  
  提供對於硬實時的支持,具體辦法有:提高時鐘精度,解決封中斷和內核態不能被搶占的問題,代表系統RT-Linux、Kurt-Linux,其實大部分實時 Linux都使用了類似與RT-Linux的提高時鐘精度和軟件中斷管理器的思想;總的來說,讓內核支持硬實時和使用傳統的Linux的豐富的系統調用之間存在著矛盾,以至於像RT-Linux就是單獨實現了一個獨立的小的硬實時操作系統;但由於軟件模擬終端控制器、提高時鐘精度、以及可搶占內核等思想的引入,這個矛盾慢慢地得到化解。
  
  提供對於實時多媒體應用的支持,舉措:引入新穎的調度算法(網絡包調度,進程調度,磁盤調度),代表系統:QLinux、Linux-SRT;
  
  引入新穎的調度框架以及資源管理思想以更好地支持網絡系統中的QoS要求,比如SILK中的垂直結構的操作系統調度的思想,QLinux中的分級調度的思想,以及RED-Linux所提出來的一個通用的調度框架和Linux/RK中所使用的資源預留的思想;
  
  方便的任務QoS管理接口函數和管理程序的實現,比如Linux/RK提出的操作系統中各種資源的資源預留的概念;Linux-SRT中為了用戶方便地使用新增加的實時調度支持而增加了API,以及提出的reserve的概念等;
  
  在實際的系統中,具體使用那種實時Linux技術,需要根據具體的系統需求而定。如果目標系統是像機床控制或者導彈飛行姿態控制這樣的硬實時系統,那基於 RT-Linux是一個不錯的方案;如果一個系統對於實時性的要求不是那麼嚴格,但又不是軟實時系統,那麼可以借鑒Kurt-Linux的想想以及一些為了提高Linux響應速度而提出的可搶占內核的想法;如果目標系統是一個像實時多媒體系統這樣的軟實時應用,或者一個希望能夠在高負載狀態下提供更好的吞吐率的服務器系統,那麼QLinux和RED-Linux的思想提供了很好的參考;如果是將Linux應用於像路由器這樣的網絡結點中,可以借鑒SILK 的實現思想。



Copyright © Linux教程網 All Rights Reserved