國防科學技術大學碩士學位論文VxWorksSMP內核調度、信號量和中斷機制的設計與實現姓名:任強申請學位級別:碩士專業:計算機技術指導教師:吳家鑄20091001國防科學技術大學研究牛院:稃碩十學位論文摘要隨著集成電路工藝的不斷進步以及處理器體系結構的發展,同構多核處理器在嵌入式領域中得到了廣泛的應用。但是,與硬件的飛速發展相比,同構多核處理器的基礎軟件特別是嵌入式操作系統研究卻比較落后。同構多核處理器的嵌入式操作系統的開發難度大,丌發效率低。本文首先對對稱多處理架構進行分析,剖析了架構與架構的區別,并對架構的先進技術做了簡要說明。詳細分析了系統,為系統的設計提供了參考。深入分析了內核的運行機制,主要是對內核的整體結構、任務調度模塊、信號量模塊、中斷管理模塊進行了詳細分析,明確了模塊之間的調用關系,為后面的多核化設計打好基礎。本文在對各個模塊設計過程中面臨的關鍵問題進行分析的基礎上,針對架構特點,提出了支持架構的內核機制的設計方案,給出了合理的解決思路。在任務調度方面,提出了基于全局隊列的任務分配算法,該算法較好實現了任務調度,調度開銷跟就緒任務個數無關,在系統負載重的情況下也能平滑工作,提高了實時性和可預測性;在同步互斥機制方面,提出了自旋鎖機制來實現新的信號量機制,該機制較好的實現了的同步與互斥,解決了死鎖等問題,使內核的同步互斥更加簡單高效;在中斷管理方面,提出了中斷動態路由算法,該算法允許多個核同時處理不同的中斷請求,相對于單核系統,減少了中斷延時,提高了系統的響應性。本文在模擬器測試平臺上驗證了基于全局隊列的調度算法、自旋鎖、中斷算法功能的正確性,并與單核版本的內核機制運行效果做了對比,得到了滿意的結果。基于架構的調度、信號量、中斷機制的設計及其初步實現,對當前嵌入式操作系統支持多核技術的發展具有一定的現實意義和理論意義。主題詞:,,調度,信號量,中斷第頁同防科學技術人學研究生院.科碩十學倚論文,?,.,?.,,..,,,,.?.,.?,;,..,,.,?,,.,,,,...,?,?.:,,,,第頁國防科學技術大學研究牛院一:稃碩十學位論文表目錄表.任務狀態說明表.能夠被調用的函數..第頁國防科學技術人學研究生院樣碩十學位論文圖目錄圖.經典的多核處理器結構?圖.典型雙處理器的結構圖?圖.工作原理?圖.工作原理?圖..的任務就緒隊列??.圖..的任務就緒隊列圖.使用鎖來防止優先級反轉?圖.系統中的中斷分發示意圖圖.內核總體處理流程圖?.圖.內核核心函數及其封裝的關系圖.任務的狀態轉換圖.基于優先級的任務搶占圖.指令所處的層次.圖.微內核的搶占過程圖.優先級被反轉?圖.優先級被反轉?圖.局部調度帶來的多次任務切換圖.查找未分配處理器核的線程.圖.模塊的選取過程圖.獲取信號量的流程?..圖.釋放信號量的流程?.圖.等待信號量的任務隊列??.圖.中斷服務程序的連接?圖.中斷請求與處理器核綁定策略造成中斷延時過大?圖.中斷動念路由算法圖.多核系統中斷控制器的框圖?圖.實現中斷動態路由算法的中斷處理過程圖.任務調度算法初始化測試??.圖.任務調度算法有效性測試圖.任務調度算法正確性測試圖.改造前系統信號量機制測試?圖.改造后系統信號量機制測試?第頁國防科學技術大學研究生院一:樣碩十學何論文圖.算法運:半均時、日的比較圖.算法運行值的比較??.第頁獨創性聲明本人聲明所呈交的學位論文是我本人在導師指導下進行的研究工作及取得的研究成果.盡我所知,除了文中特別加以標注和致謝的地方外,論文中不包含其他人已經發表和撰寫過的研究成果,也不包含為獲得國防科學技術大學或其它教育機構的學位或證書而使用過的材料.與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意.學位論文題目:蘭三鱉墨墨壁凼趑凋廑:焦曼量壟生斷扭劍數遮讓生塞理日期:學位論文作者簽名:??每齷,年月呂日學位論文版權使用授權書本人完全了解國防科學技術大學有關保留,使用學位論文的規定.本人授權國防科學技術大學可以保留并向國家有關部門或機構送交論文的復印件和電子文檔。允許論文被查閱和借閱;可以將學位論文的全部或部分內容編入有關數據庫進行檢索,可以采用影印.縮印或掃描等復制手段保存,匯編學位論文.保密學位論文在解密后適用本授權書.學位論文題目:蘭墜壘璺螋應撻通廑:焦曼量塑主匭扭劍數遮進復塞理.日期:。年倫月了日日期:。年月日國防科學技術人學研究生院科碩十學位論文第一章弟一早緒論三百匕.課題研究的背景近幾年,國內自主知識產權的處理器得到了迅速的發展,比如年,清華大學自主研發了位微處理器芯片;年位龍芯增強型處理器芯片通過科技部驗收。但是,這些處理器并沒有得到廣泛的應用。主要的一個制約因素是在各個應用領域,這些處理器都沒有得到相應的成熟操作系統的支持。在嵌入式應用領域,國內自主產權處理器就缺乏優秀的嵌入式操作系統如的支持。嵌入式操作系統是一種支持嵌入式系統應用的操作系統軟件。它是嵌入式系統包括硬、軟件系統極為重要的組成部分,通常包括與硬件相關的底層驅動軟件、系統內核、設備驅動接口、通信協議、圖形界面、標準化瀏覽器等。嵌入式操作系統具有通用操作系統的基本特點,如能夠有效管理越來越復雜的系統資源;能夠把硬件虛擬化,使得開發人員從繁忙的驅動程序移植和維護中解脫出來;能夠提供庫函數、標準設備驅動程序以及工具集等。與通用操作系統相比較,嵌入式操作系統在系統實時高效性、硬件的相關依賴性、軟件固態化以及應用的專用性等方面具有較為突出的特點【】。操作系統是美國公司于年設計開發的一種嵌入式實時操作系統,,是嵌入式開發環境的關鍵組成部分。良好的持續發展能力、高性能的內核以及友好的用戶開發環境和軟件支持,使其在嵌入式實時操作系統領域占據一席之地。它因良好的可靠性和卓越的實時性被廣泛地應用在通信、軍事、航空、航天等高精尖技術及實時性要求極高的領域中,如衛星通訊、軍事演習、彈道制導、飛機導航等【】。隨著現代應用對計算機性能要求的不斷提高,單核處理器性能的提升已經滿足不了需求。對于單核處理器來說,提高性能的主要途徑便是優化邏輯結構、擴大緩存以及提高芯片頻率。但芯片的邏輯架構一般有、年的生命周期,一旦設計穩定就很難從根本上對其做出改變,這樣擴大緩存容量和提高頻率就成為單核處理器提升性能的主要手段。提高緩存容量雖然能夠小幅的提高性能,但付出的代價相當高:處理器的緩存都是使用靜態隨機存儲器件,速度極快、可晶體管利用率很低,容量緩存就與要消耗萬左右的晶體管??我們可以看到,無論在、還是處理器中,二級緩存占據的芯片面積普遍超過%,如果不斷提升緩存容量,無疑將對芯片的制造成本與芯片面積三次方成正比帶來嚴重的影響。與之類似,提高工作頻率能夠一定程度上提高芯片的性能,但會導致運行功耗大增,現在芯片運行在風冷條件之下已經第頁國防科學技術大學石究牛院:稃碩十學位論文接近極限【。的出現就很好的解決了硬件系統性能提升的瓶頸問題。所謂就是緊耦合共享內存對稱式多處理器,在系統中,由一種操作系統控制所有處理器,該操作系統可協調每個相似的處理器上同時發生的活動。由于這些緊耦合處理器所訪問的是一個公共內存區,所以它們必須通過一種基于低延時共享內存的通信機制來實現相互之的同步。那么基于單核版本的能不能對,尤其是調度機制方面提供高效的管理機制呢,答案是否定的【】。改變了傳統的單機版多任務、基于優先權的編程模式,這體現在允許多個線程被并行執行,而這是建立在單個操作系統運行于擁有多個核的處理器,或運行于多個處理器相互連接成為擁有多個處理單元的邏輯處理器背景上的。我們常說在某個非的多任務環境中,多個線程可以“同時運行”,可實際上處理器一次只能執行一個線程??處理器依靠操作系統任務調度器以及中斷機制來運行不同的線程。由于這一差異,除非在代碼的設計和執行即將系統作為立足點,否則從傳統的多任務系統向系統轉移代碼是行不通的。正因為單核版本的不能應用于的硬件平臺上,所以我們要對內核的各個模塊進行重新設計,本文著重對.版本的內核機制進行分析,在此基礎上對如何支持進行了設計。.國內外研究現狀在多核處理器如火如荼地發展,硬件制造商不斷推出新產品之際,相應的操作系統和應用程序開發卻已經滯后。多核處理器的優勢只有在軟件能夠充分利用其特性時,才能體現出來。桌面系統業界各大主要操作系統廠商已經推出相應的操作系統,例如、和發行版,以及。其中有些操作系統還將包括支持專門應公司的用的優化程序,以充分發揮多核的優勢,從而改善一系列應用的性能。在嵌入式操作系統方面,多核處理器的應用相對緩慢,其中支持多核處理器的嵌入式實時操作系統主要有公司的、軟件系統有限公司的、以及由發展而來的等少數操作系統。硬件平臺的發展對嵌入式實時操作系統提出了新的挑戰,因此,對于支持架構的嵌入式操作系統的研究也成為當今的熱點。文獻【研究了架構下的任務調度問題。它重點強調在多處理器片上系統中,的利用對于系統性能的提高和降低功耗具有重要意義。它假設將一個循環拆成多個線程,然后計算拆分后的線程的共享程度,將有共享數據的線程先后調度在同一個核上,而將不共享數據的線程調度到不同的核。此方法不僅充分利用了的第頁國防科學技術入學研究生院科碩十學位論文性能,而且利,了多核的并二計算能力。在系統性能方面,文獻提出,二級緩存的不命中要比一級緩存不命中和流水線的沖突造成更大的影響。它指出,通過合理的調度來減少線程對二級緩存的訪問,可以提高系統的吞吐量。在降低功耗方面,文獻【】提出了一個結構??一個極端細粒度的線程結構,通過在編譯時顯示地標記方式來實現并行執行。它認為某些程序利用在順序執行的處理器上執行比程序直接在亂序執行的處理器上執行消耗更少的能耗。等人提出了一個調度算法,此算法通過調節多個處理器核的頻率和電壓方法,達到同時滿足時間和能耗的要求的目的。文獻【討論了在任務時間約束的情況下如何降低系統的功耗,提出了兩個新穎的實時循環調度算法和。為了能更好的支持硬件平臺的應用,各大嵌入式操作系統廠商都分別推出了支持硬件平臺的操作系統,并對其進行了有針對性的升級,尤其是在調度算法和同步機制的改進方面比較大。目前支持的操作系統中,的技術比較成熟。年來自美國嵌入式操作系統開發聯盟的.提出了基于總線鎖的多核調度算法,該算法解決了系統和系統中總線搶占的問題,也對以后多核操作系統中的信號量機制的研究起到了重要的推動作用【叭。中國航空計算技術研究所在年提出了一種基于實時性考慮的對稱多處理機任務調度策略的設計,這也填補了國內對于在嵌入式領域應用創新的空白。這也為以后的我國近幾年載人航天工程中的嵌入式操作系統的改造和個性化提供了理論基礎。本課題組年提出的針對子任務排隊問題的調度算法以及中斷分配策略算法【】也為架構下的優化提供了有效的途徑。.本文主要工作任何一個采用模式進行多核化改造的操作系統,它的實現都必須解決以下三個主要問題:系統完整性、性能和外部編程模型】。系統完整性意味著正確協調好處理器核間的并行活動,從而避免危害到內核的數據結構。在保證系統完整性的基礎上,系統應盡可能地獲得最大的性能。外部編程模型決定了系統調用接口對應用程序的影響。如果系統調用接口與原操作系統的系統調用接口不一致,那么許多為原操作系統編寫的應用程序就得改寫。因為重新編寫程序的代價很高,所以大多數支持的操作系統的實現都選擇了保持原有的接口不變的實現策略。由于第頁國防科學技術人學研究生院‘:程碩十學位論文是一個實時操作系統,兇此多核化的設計還必須考慮實寸性和叮預測性。為此本文深入研究了.操作系統的內核源代碼。以模塊為單位對內核源代碼進行分析。通過對每個模塊的修改歷史、所使用數據結構、主要函數流程、函數接口進行詳細分析,明確了模塊之間的調用關系【。詳細的描述內核的工作流程和運轉機制;在此基礎上,對內核部分模塊進行了設計和修改以支持;設計完畢后,編譯操作系統境像文件在本課題所基于的硬件平臺上進行測試驗證。在實現對的支持過程中,本文主要做了以下工作:、在任務調度管理機制方面,本文提出并實現了基于全局隊列的任務分配算法。、在內核的同步互斥機制方面,本文提出并實現了基于兩種自旋鎖的信號量機制。、在中斷管理方面,本文提出并實現了了中斷動態路由算法。在外部編程模型方面,本文選擇了保持原有的接口不變的實現策略,盡可能地兼容原有應用程序。最后,本文在一個基于開發的同構多核處理器的模擬器上對系統的下確性和性能進行了測試驗證。.論文結構全文共分為六章,各章內容如下:第一章緒論對嵌入式操作系統和做概要性介紹,并對的發展做了詳細介紹。在此基礎上,引出了本文研究的目的、內容和要求,說明了研究背景。第二章對稱多處理技術綜述介紹了與本文設計研究內容相關的一些技術背景內容,包括架構的需求背景和關鍵技術,以及架構與的比較介紹。此外,本章也分析了系統實現原理,為后續對的研究與實現做鋪摯。最后對架構的先進技術進行概述。第三章內核調度與信號量機制設計深入分析了內核的調度機制和信號量機制。明確提出了在架構下內核的調度機制和信號量機制所面臨的問題,并根據需要對內核調度機制和信號量機制進行設計,最后給出內核調度機制和信號量機制的代碼實現。第四章內核中斷機制設計笫頁國防科學技術人學研究生院門卑碩學位論文深入分析了內核的中斷機制。明確提出了在架構卜.內核的中斷管理機制所面臨的問題,并根據需要對內核中斷管理機制進行設計,最后給出內核中斷管理機制的代碼實現。第五章測試驗證在指令模擬器上測試了基于全局隊列的調度算法、自旋鎖、中斷動態路由算法功能的正確性,并與單核版本的內核機制運行效果做了對比。第六章結束語對本文研究的內容進行總結,并對需要繼續開展的工作進行了陳述。第頁國防科學技術大學研究牛院:科碩十學位論文第二章對稱多處理技術綜述在設計系統之前,我們首先要對“對稱多處理技術”進行深入研究。搞清對稱多處理架構的設計原理,并結合非對稱多處理器架構找出其設計特點,這是后面針對架構進行設計與實現的前提條件。并且,對其他實現架構比較成熟的嵌入式操作系統如的設計原理進行分析,為后面針對此架構進行設計與實現提供了思路。.對稱多處理架構概述摩爾定律【】是指在單個硅芯片中集成的晶體管數目每至個月大約翻一番。幾十年來,處理器生產廠商一直在提高時鐘頻率這條跑道上競爭,各行業對計算能力的需求推動了處理器計算能力的提高,而摩爾定律在過去數十年罩展現出驚人的準確性。然而,最近幾年來處理器的功耗和節能問題愈來愈成為人們關注的焦點。僅靠提高主頻來改進處理器性能的做法遇到了瓶頸,因為主頻的提高導致處理器的功耗和發熱量劇增,反過來制約了處理器性能的進一步提高。于是,人們開始把研究重點轉向將多個執行內核集成到單個芯片上,通過任務在處理器核上并行運行的方式來提高,從而提高性能。一直以來,人們通過各項手段來提高系統的并行處理能力,以此達到提高整體性能的目的。年,為了提高線程的并行能力,單芯片多處理器體系結構被提出【,也就是平時所說的多核技術。所謂,是指在一個芯片上集成多個微處理器核從實質上說,每個微處理器核都是一個相對簡單的單線程微處理器,而且這多個核之間聯系非常緊密,甚至共享一級緩存或二級緩存,核間通過高速總線連接在一起,如圖.所示。如果中的多個微處理器核是同構的,則可以看作是的一種實現形式。在此之前,為了提高計算機的并行處理能力,文獻【中首次提出了對稱多處理結構,。卿蛹政/‘、//‘斗。;。/∑圖.經典的多核處理器結構第頁同防科學技術人學研究乍院:稗碩十學何論文“對稱多處理”是指在一個計算機上匯集了一組處理器多處理器,各處理器之間共享內存子系統以及總線結構。它是相對非對稱多處理技術而言的、應用十分廣泛的并行技術。在這種架構中,一臺電腦不再由單個處理器組成,而同時由多個處理器運行一種操作系統,并共享內存和計算機的其他資源。雖然同時使用多個處理器,但是從管理的角度來看,它們的表現就像一臺單機一樣。系統將任務隊列對稱地分布于多個處理器之上,從而極大地提高了整個系統的數據處理能力。所有的處理器都可以平等地訪問內存、/和外部中斷。在對稱多處理系統中,系統資源被系統中所有處理器共享,工作負載能夠均勻地分配到所有可用處理器之上。本文的目標測試平臺指令模擬器就是同構多核結構的。圖.就是一個典型的雙處理器的結構。囝申申圖.典型雙處理器的結構圖.對稱多處理與非對稱多處理的區別目『,支持多核體系的操作系統模式主要有兩種:對稱多處理.,模式和非對稱多處理.,模式。這兩種方式在操作系統的占有,程序和數據區的分配等方面有很大的不同。系統是實現各處理器對存儲器和所有設備的共享;各需實現操作系統內的重要協作,以防止對共享資源的并行存取。在配置中,各操作系統大多會對硬件資源進行劃分,以便合作僅限于使用共享存儲器的情況。由于合作程度不同,系統有時被稱作“緊耦合多處理’’系統,而則被稱為“松耦合多處理”系統。第頁圍防科學技術大學研究生院科碩十學位論文:瀠弓.執行縷.執仃操作系統、、刀瞳.執::垂’:;.植\/譴,執行;:譴寫.執打卜\/譴寫.執打:讒譬.執、‖卜/:罅.扭÷譴’、執;完全共享內存\圖.作原理假設我們的處理器采用的是操作系統。在如圖.所示在配置中,各處理器共享整個物理存儲器空間。該存儲器被用來存儲單一鏡像;該存儲器亦被用來存儲在系統運行過程中創建的實時進程或稱用戶任務。由于系統的兩個處理器都有可能讀出、寫入或執行任何存儲單元,兩個處理器中的任一個都能執行各項內核任務或用戶任務所屬任務。卜\墟寫,執打:/、/讀寫,執行卜、.讀寫.執/、/.:讀寫,執行/卜:讀寫部分共享內存讀寫‖\圖.上作原理而在如圖.在配置中,每個處理器存儲有一份操作系統鏡像,且該鏡像只能被擁有它的處理器存取。由于這一點,.不可能執行?存儲器內的內核任務,反之亦然。相同的情況亦適用于用戶任務;例如,當.創建某個用戶任務時,該用戶任務.只能被創建它的操作系統讀取和執行。在配置中,存儲器會被部分共享;這種共享通常僅限于數據讀出和寫入,這與在兩個操作系統間進行信息傳遞的情況相同。.實現原理從.版本開始增加對于的支持,最初的實現較為簡單,以后隨著版本更新,的實現也逐步趨于完善。支持的的逐步完善過程中所積累的經驗及成果,無論在理論上還是實踐上,都為本文的研究工作提供了很好的借鑒作用。因此,深入分析系統的實現原理,對后續的研究與實現能夠提供理論支持和實踐依據。第頁國防科。字:技術人學彬究生院稃碩十學位論文.以,.的內核,是在用戶級實現,內核本身并/能兇有多個處理器核而得到加速。而在.內核以后,在內核級實現,使用多處理器核可以加快內核的處理速度。目前的.有以下優點:采用時間復雜度為的調度算法【,調度器開銷恒定,與當前系統負載無關,實時性能更好;鎖粒度大幅度減小;優化了計算密集型的批處理作業的調度;系統負載重的情況下,調度器也能發揮良好的性能。這些使得系統性能和實時性都有了很大的改善。下面將對支持的關鍵模塊及技術進行分析。..調度機制.的調度機制的特點主要有兩個:內核不可搶占以及調度算法簡單高效。在.中,內核是不可搶占的,即進程在內核態執行時,它不能被任意掛起,也不能被另一個進程代替,除非進程自己放棄處理器。一個最典型的例子就是內核進程中如果出現死循環并且進程不調用進行任務切換,系統就會失去響應。此時盡管各種中斷包括時鐘中斷仍然在響應,但卻不會發生調度,其他進程包括內核進程都沒有機會運行。操作系統內核中負責進程調度的具體函數是,它按照不同的調度策略對實時進程和非實時進程進行不同的調度處理。它主要完成兩項工作:遍歷就緒隊列中的所有進程,調用函數計算每一個進程的權值,從中選擇權值最大的進程投入運行。如果整個運行隊列中的所有進程的時問片都耗盡,重新分配時間片。的進程用結構體表示。如圖.所示,系統中的所有進程被組織到以初始化任務為表頭的雙向鏈表中,該鏈表是全系統唯一的,每個處理器核都分別對應了一個,它們的指針被組織到宏訪問這些數組中,調度器通過也在其中,但除外,調度器總是從中選取最適合調度的進程投入運行。圖..的任務就緒隊列由于所有處理器核共享一個運行隊列,需要使用一個運行隊列鎖來保證互斥訪問,因此,在系統中,一個核處理器從運行隊列選擇任務就會阻止其他第頁為表頭的鏈表記錄了所有處于就緒態的進程當前正在運行的進程進程。以.國防科學技術人學研究生院‘科碩十學何論文核操作這個隊列。結果足,空閑處理器核需要等待這個處理器核釋放運行隊列鎖,這樣會造成效率的降低。.在.的基礎上做出了很大的改進,它能夠更好地發揮的性能。首先,它改變了.中多個處理器核共享一個運行隊列的做法,而是每個處理器核都有自己的運行隊列,這樣就允許同一時刻多個處理器核進行任務調度,而且系統根據所有處理器核的負載進行負載平衡。負載平衡程序由函數實現,只要當前的就緒隊列為空,它就會被調用,此外,在系統空閑時每隔毫秒調用一次,而其他情況下每隔毫秒調用一次,以便重新分配任務負載,維持核間的負載平衡。但是由于負載平衡程序的執行開銷較大,而且執行時間具有不確定性,所以一定程度上影響了的實時性和可預測性。其次,.內核使用了新的調度算法,其時間復雜度為。新調度器在高負載的情況下執行得非常出色,并在有多個處理器核時能夠很好地擴展。在.的調度器中,時間片重算算法【】要求在所有的進程都用盡它們的時間片后,新的時間片才會被重新計算和分配。這樣就造成一些弊端:①可能會耗費相當長的時間。最壞情況下,在有個進程的系統中,其時間復雜度可能達到;②由于在重算過程中要對任務隊/鎖來保證互斥訪問,因此加劇了對鎖的競爭,影響的效率;③時問片重算的時機是不確定的。這影響了系統的實時性。此外,當空閑處理器核開始執行那些時問片尚未用盡的、處于等待狀態的進程時,有可能導致進程在處理器之間“跳躍。當一個高優先級進程或交互式進程發生跳躍時,整個系統的性能就會受到影響。新調度器解決上述問題的方法是,基于每個處理器核來分布時間片,并取消全局同步和重算循環。新調度器讓每個核維護兩個優先級數組,即活動數組和過期數組。活動數組中包含所有映射到當前核且時間片尚未用盡的任務,過期數組中包含時間片已經用盡的所有任務的有序列表。當一個任務用完自己的時間片后,就會被重新計算并賦予新的時間片,然后從活動數組中刪除,插入到過期數組中。如果所有活動任務的時間片都已用盡,那么指向這兩個數組的指針互換,包含時間片用盡的任務的過期數組成為活動數組,而已變為空的活動數組就成為新的過期數組。為了使調度效率更高,內核使用了一個位圖來輔助查找運行隊列中優先級最高的進程,對它支持的每一種體系結構都提供了對應的快速查找算法,以保證對位圖的快速查找。提供該功能的函數叫,它會在個位的字個優先級中查找哪一位的優先級最高。查找時間并不依賴于活動任務的個數,而是依賴于優先級的數量。第頁國防科學技術人學研究生院‘:程碩十學位論文的滔功效組躺過絳救組寅時經務的優先綴翊戶任務魄優先綴廠圖..的任務就緒隊列..信號量機制讀寫鎖眾所周知,為了保護共享數據,需要一些同步互斥機制,如讀寫鎖。讀寫鎖的引入是為了增加內核的并發能力。只要沒有內核控制路徑對數據結構進行修改,讀寫鎖就允許多個內核控制路徑同時讀取同一個數據結構。如果一個內核控制路徑想對這結構進行寫操作,那么它必須獲得讀寫鎖的寫鎖,寫鎖授權獨占訪問這個資源。它使用起來非常簡單,而且是一種很有效的同步機制,在系統和系統中得到廣泛的使用。但是,隨著計算機硬件的快速發展,獲得這種鎖的開銷相對于處理器的速度在成倍地增加。原因很簡單,處理器的速度與訪問內存的速度差距越來越大,而這種鎖使用了原子操作指令,它需要原子地訪問內存,也就說獲得鎖的開銷與訪存速度相關。另外,在大部分非架構上獲取鎖使用了內存柵,這會導致處理器流水線停滯或刷新,因此它的開銷相對于處理器速度而言就更大。讀.拷貝.更新...內核引進了新的鎖機制..。顧名思義,就是讀一拷貝.更新。允許多個讀者和寫者并發執行,對于被保護的共享數據結構,讀者不需要獲得任何鎖就可以訪問它,但寫者在訪問它時首先拷貝一個副本,然后對副本進行修改,最后使用一個回調機制在適當的時機把指向原來數據的指針重新指向新的被修改的數據。這個時機就是所有引用該數據的處理器核都退出對共享數據的操作。并沒有使用鎖,也就是它不使用被所有處理器核共享的鎖或者計數器,這與讀寫鎖有很大區別,所以死鎖問題就不需要考慮了。盡管相對于讀寫鎖具有更大的優勢,但是這個優勢是基于以下兩個限制第頁國防科學技術大學研究生院:稃碩十學何論文的:首先,只保護被動態分配并通過指針引川的數拋結構;其次,在被保護的臨界區中,任何內核控制路徑都不能休眠。這也就要求讀者在被切換出處理器核以及開始到用戶態執行之前要執行放棄對共享數據結構的引用。對于,由于讀者幾乎不做任何事情來防止競爭條件的出現,所以寫者的同步丌銷比較大,它需要延遲數據結構的釋放,復制被修改的數據結構,它也必須使用某種鎖機制同步與其并行的其它寫者的修改操作。讀者通過調用釋放或修改的時機。有一個專門的垃圾收集器來探測讀者的信號,一旦所有的讀者都已經發送信號告知它們都不再使用被保護的數據結構,垃圾收集器就調用回調函數完成最后的數據釋放或修改操作。與的不同之處是:它既允許多個讀者同時訪問被保護的數據,又允許多個讀者和多個寫者同時訪問被保護的數據注意:是否可以有多個寫者并行訪問取決于寫者之間使用的同步機制。讀者沒有任何同步丌銷,而寫者的同步丌銷則取決于使用的寫者間同步機制。但不能替代,因為如果寫者比較多時,對讀者的性能提高不能彌補寫者導致的損失。在應用方面,這種鎖機制的使用范圍比較窄,只適用于讀多寫少的情況,主要應用在網絡層和虛擬文件系統中,如網絡路由表的查詢更新、設備狀態表的維護、數據結構的延遲釋放以及/設備的維護等。鎖過去的版一般都采用比較單純的讀寫鎖來實現臨界區機制,然而讀寫鎖是沒有優先級繼承功能的,這樣就有可能發生優先級反轉現象:如圖.,任務優先級為:,任務發出系統調用,訪問臨界區時,任務也發出了訪問要求。這時任務只能等待。此時如果優先級比高的任務進入就緒狀態,則就搶占,而此時由于迎執行比任務優先級低的任務,任務需要等待更長的時間,響應延時也就加大。為了縮短延時時間,軟件公司用鎖替換了讀寫鎖,從而實現了優先級繼承功能。如圖.,對于任務正訪問的臨界區,如果優先級較高的任務想要訪問,功能將把任務的優先級提高至與任務相同。由此避免因任務的搶占而發生的優先級反轉現象,同時減少任務的響應延時;而且在掛起任務的這段時間,可以去運行其他任務,這也提高了運行效率。第頁函數提供一個信號給寫者以便寫者能夠確定數據可以被安全地.同防科學技術人學,刪二院『科碩。學位論文?”,“‘?’”?一?‖呷一●:崢嗍牌/。強一篇.黜。創使鎖米防憂先絨反轉中斷機制傳統的單核處理器都采用中斷控制器。一般向言,的作用是提供多個外部中斷源與單一處理器之問的連接。如果結構『還是采用中斷控制器.那就只能靜態地把所有的外部中斷源劃分成苦干組,分別把每一組都連接到一個,而則與處理器核有一對一勺連接。然而,這樣就達不到動態地分配中斷請求的目的。因此,為處理器設訓了一種更為通用的中斷控制器,稱為“高級可編程中斷控制器”縮寫成。另一方面,考慮到核問中斷請求的需要,每個處理器核實際卜都需要有個自己的,因為一個核常常要有目標地向系統中的其他核發出中斷請求。所以,就在每個核內部集成了一個本地,成為簡稱。但是,在上,主板上有一個至少一個,有的主板有多個,用來更好地分發中斷信號全局的,它負責接收外設的中斷信號,再分發到處理器撥上,這個全局的被稱作?,如圖.所樂。幽.系統中的中斷分發示意圖?最大的作用在于中斷分發.它根據其內部的第頁國防科學技術人學研究生院一:稃碩十學何論文表,格式化出‘條中斷消息,發送劍某個或多個處理器核的上,再由通知處理器核進行處理。目前典型的.具有個中斷管腳,每個管腳對應一個,表項。與普不同的是,.的管腳沒有優先通的級,也就是說,連接在管腳上的設備是平等的。但這并不意味著多系統中沒有硬件優先級。設備的中斷優先級由它對應的中斷向量決定的,.將優先級控制的功能放到中。當.某個管腳接收到中斷信號后,會根據該管腳對應的,格式化出一條中斷消息,發送給某個或多個處理器核的。.支持多種中斷分發策略。可以通過對中字段進行設置,實現某個中斷請求由固定的單個或多個處理器核進行處理。或者使用優先級策略,每個處理器核都有自己的優先級,.會把中斷請求分發到優先級最低的處理器核上。用戶可以通過對.進行編程從而實現策略的選擇以及一些特殊的需求。在系統上,除了處理處理器核異常、外部設備中斷之外,還要處理核間中斷。當一個處理器核想對另一個處理器核發送中斷信號時,就在自己的的寄存器,中斷命令寄存器中存放其中斷向量和目標核擁有的的標識,觸發中斷。核間中斷信號經由總線傳遞到目標,目標就向自己所屬的核發送一個中斷。.架構先進技術概述對多線程程序能夠提供較高的性能,但是對于單線程應用的性能反而不高。采用硬件動態提取線程是一種辦法,但編譯器要擔負起自動并行化的工作,即將串行程序自動的轉換為等價的多線程并行代碼,使用戶不擔心迭代空間劃分、數據共享、線程調度和同步等細節。更重要的是多線程優化編譯技術包括線程并發機制的實現、線程調度、線程級前瞻執行等技術,多核之間的任務調度是充分利用多處理器性能的關鍵。為滿足實時處理的要求,均衡各處理器負載,需要研究的任務調度機制有分布式實時任務調度算法,動態任務遷移技術等。..分布式實時任務調度算法近年來,單芯片多核心處理器.,體系結構的研究已逐漸成熟,在一些并行系統中已開始采用多核處理器,例如最新的高性能集群服務器就是采用了多核處理器的一種并行系統。在單芯片多核心系統中,用戶任務數一般都多于處理器數、這將導致它們互相爭奪處理器。另外,系統任務也同樣需要使用處理器。這就要求任務調度程序按一定的策略,動態地把處理器分配給第頁國防科學技術人學研究生院科碩十學位論文處十就緒隊列葉的某一個任務,以使之執行。其設計策略也嚴格遵照分御式的原則。盡管目前對單芯片多核心處理器上的分布式實時任務調度技術開展了一些研究,然而并沒有明確的針對單芯片多核心系統中實時任務調度的標準和規范。基于單芯片多核心處理器系統的分布式實時任務調度技術還是一個不成熟的領域,還需要我們不斷的研究和探索。..動態任務遷移技術動態任務遷移技術是單芯片多核心系統調度機制研究的一個熱點,指的是任務在多核環境下的重定位,主要用于解決在特殊環境下某個運算核心失效的問題。多核系統通過動態任務遷移技術可以極大的提高系統的容錯能力與可靠性。與分布式實時任務調度技術一樣,動態任務遷移技術的研究同樣也很不完備,有很廣闊的研究前景。.本章小結本章介紹了與本文設計研究內容相關的一些技術背景內容,包括架構的需求背景和關鍵技術,以及架構與的比較介紹。此外,本章也分析了系統實現原理,包括任務的調度和同步機制以及中斷機制。對實現原理的分析為后續的研究與實現提供了重要的參考。最后對架構的先進技術進行概述。第頁國防科學技術人學研究生院。程碩學位論文內核調度與信號量機制設計第三章在對實時操作系統內核機制進行多核化設計與實現之前,我們必須對的整體結構及本文需要設計的模塊進行深入的分析。深入分析及理解的實現原理是多核化研究與實現得以順利進行的前提條件,這也為的多核化設計作理論上的準備。因此,本章將對的體系結構進行剖析,深入分析內核的結構和任務調度以及信號量模塊。并根據其實現原理對內核調度模塊以及信號量模塊進行多核化的設計與實現。.內核結構內核是其運行環境的核心,包括多任務內核、任務搶占調度、任務間通信和中斷處理機制等,整個內核的運轉流程任務視角如圖.所示。在系統丌始的時候,由任務管理模塊創建了一些任務,然后調度模塊負責調度任務到處理器上,任務丌始執行。任務執行時,可能直接執行完畢,退出;也可能訪問和處理資源,之后可能繼續執行,也可能被阻塞,進而引起任務調度模塊重新調度任務執行;任務可能通過任務管理模塊創建或銷毀任務;也可能有外部中斷和時鐘中斷發生,導致任務調度模塊重新進行調度;同時,任務也可能處理或產生中斷和異常。圖.內核總體處理流程圖實時性強是操作系統非常突出的一個特點。為了提高系統的實時性,大多數操作系統都提供了各種機制,如可搶占的內核、中斷的后半段處理等。第頁刊坊科學技術大學研究牛院:群碩十學何論文為了提島實時性,構造成了一個帶自‘微內核的層次結構。在計算機的早期,操作系統大部分是一個統一的實體。在這樣的系統中,提供不同功能的模塊是獨立考慮的,如處理器管理、內存管理、文件管理等,較少考慮模塊間的關系。這樣的操作系統結構清晰,構造簡單,但是由于操作系統本身很復雜,在這種大粒度的操作系統中難以劃分可搶占部分和不可搶占部分的邊界,難以避免有冗余的操作在操作系統的不可搶占部分中執行,造成系統的實時性比較差,不適合實時應用環境。而帶有微內核的層次結構的操作系統則較好的解決了這個問題。在這樣的操作系統中,以內核作為層次結構的起點,每一層功能對較低層進行封裝。內核僅需要包含最重要的操作指令,提供高層軟件與下層硬件的抽象層,形成操作系統其它部分所需的最小操作集。這樣就可以比較容易的精確確定可搶占部分與不可搶占部分的邊界,減少了需要在內核不可搶占部分執行的操作,有利于實現更快的內核搶占,提高系統的實時性。的內核就是這樣的一個有利于構造層次結構的微內核,它由、、、、、、、、等庫組成的。庫有底層的最基本、最核心的函數,也有在最基本最核心函數上進行封裝給應用程序提供的調用。內核中主要函數及其封裝的關系如圖.所示。圖中箭頭表示封裝和調用關系。在這樣的內核中,容易實現很強的實時性;而對內核高層次的封裝則使得用戶在開發的應用程序時,只需要調用頂層的函數,不必關心底層的實現,程序設計也很方便。./\\。√\上上事、§..///。“““Ⅳ?。艘●?、、~\?\../斛\\、一糾????一贏?蕊一:圖.內核核心函數及其封裝的關系.任務調度機制設計第頁Ⅲ防科學拄術人學研究生院欄碩十學位論文...任務狀態的轉換和上下文切換,、目讎≯、/一\一嚏/“,圈.任務的狀態轉換在任務的整個,存周期,任務的狀態小斷的轉換,如圖所示。各種狀態的含義見表所示四。表任務狀態說明狀態說明執打任務“宵處理器資撐運行,可“看作種特殊的就緒志。就緒任并僅等待處理器資源阻塞任務田等待獨一?資源而不能被闌度運行唾眠處睡眠狀態捧起任務剛剛創建戚是罔為調試的原因被擇起既處睡眠義被豐起的狀態既處阻塞義被拌起的狀態帶超時的阻塞狀卷十帶超時,義處阻塞,同時被掛起的狀態在狀態轉換圖中,箭頭表示任務被創建,進入狀態。箭頭袤示任務被或轍活,進入就緒態。箭頭表示任務因為調試蟓兇被掛起。箭頭表示在執行些代碼以后,去獲取獨占資源并且獨占資源已經被其它任務占用,任務轉向了阻塞態,比如會觸發這個狀態轉換。在占用獨占資源的任務釋放獨占資源后,任務可能獲符了該資源,就會從阻塞態轉換到就緒卷,如箭頭所示。箭頭標識了一個從就緒忐到睡眠悉的轉換,如會觸發這種變化。箭頭說明任務從睡眠態轉到了就緒態.出現這種狀態轉換的原倒是睡眠時問到或者調用了曬數。箭頭表示了一個從阻塞忐轉換到掛起態的變化.箭頭表示了從睡眠態到掛起志的轉換,第頁囝防科學技術人學研究生院:釋碩十學位論文這兩種轉換和箭頭的轉換一樣,鄙是任務兇為調試原兇被掛起。箭頭和箭頭表示任務被解除了掛起。每當任務從就緒念轉換到執行態,就會發生上下文切換。所謂上下文切換,是指改變的上下文信息。的上下文信息包括、、通用寄存器等。上下文進行切換時,主要完成兩項工作:第一,將目前執行任務的上下文保存進任務的;第二,將新的任務的上下文從任務的移到的相應寄存器中。上下文切換有同步切換和異步切換兩種。同步上下文切換的原因是在任務執行過程中發生的,如任務阻塞、延時、掛起等;當有中斷到來時發生異步上下文切換。...基于優先級的搶占式調度是一種強實時操作系統,但和當前其它成熟的操作系統一樣,并不是“硬實時”的操作系統。所謂“硬實時”是指當某種事件發生時,系統必須在預定時間之內,或者說在限期之前做出反應,否則就會造成災難性的后果。具有這一特征的操作系統要做到對于所提交的每一項作業及其時間要求,或者做出承諾,或者立即拒絕以使提交者可以考慮采取其他措施,對于做出的承諾則保證其實現。提交給硬實時系統的作業也可以是不帶時間要求的,但是對這些作業的承諾當然也就不包含時間的因素,那將當作后臺作業來對待瞄】。并沒有使用基于時間限的調度算法,也就是不接受任何作業提交的時間要求。為了提高實時性,目前采用的方法都是優先級搶占式調度,使得高優先級的任務的到優先執行。這樣,在一定計算資源前提下,通過恰當的任務劃分和設定任務優先級可以滿足實時性的要求。的內核實現基于優先級的搶占式調度。內核劃分優先級為級~。優先級為最高優先級,優先級為最低。當任務被創建時,系統根據給定值分配任務優先級。優先級也可以是動態的,它們能在系統運行時被用戶使用系統調用來加以改變,但不能在運行時被操作系統所改變。沒有處于阻塞、掛起或者睡眠態的最高優先級任務占有處理器資源運行。內核一旦發現隊列中有一個比現在運行的任務的優先級高的任務在運行,就立即保存當前任務的上下文,切換到高優先級的任務運行,這個過程稱為任務搶占。系統調用和中斷如時鐘中斷都會導致任務搶占的發生,圖.示意了任