Global Sources
電子工程專輯
 
電子工程專輯 > 記憶體/儲存
 
 
記憶體/儲存  

零星事件調度策略

上網時間: 2003年09月27日     打印版  Bookmark and Share  字型大小:  

關鍵字:CONTENT="Sporadic Event  零星事件  real-time system  即時系統  POSIX 

大多數即時作業系統均採用基於優先級的佔先調度器以使多執行緒共享單個CPU。這種調度器尤其適用於那些完全由固定周期性執行緒組成的系統,這些系統都只具有有限的外部激勵。然而,實際應用中軟體系統通常具有無限的外部激勵,因此需要進行時變運算。在這些情況下,事件可能使那些由典型RTOS調度器建構的系統陷入過載,而無法滿足關鍵時限時間(deadline)要求。

理論與實際的衝突

在我們早期的計畫中,設計組歷經數月才定義出數位交換機系統控制器的軟體架構。由於通訊交換機必須滿足嚴格的時間要求,因此我們選擇了據稱能很好地滿足即時應用的作業系統。數月之後,產品品質(QA)部門的工程師開始報告出現間歇的系統死鎖。在這些死鎖期間,用戶介面不響應鍵盤作業,而表徵處理器工作狀態的LED則一直保持為閃亮狀態。這時,韌體驅動指示燈仍然閃爍,好像沒有產生任何故障。

由於不僅處理器的LED指示核心執行狀態連續,而且具有最高優先級的心跳中斷服務程式也正常執行,因此可以推斷死鎖產生的原因是在無限循環中產生中等優先級中斷服務程式。由於故障出現是間歇的,因此找到故障根源非常困難。最初,這種問題只在一個系統中出現,但隨後在另一系統也出現同樣的問題。經過檢查,最後在電路板上發現了一條短路線,這條線使快閃記憶體的電平感應中斷請求訊號電平升高。儘管系統可執行高優先級的心跳執行緒,但無法對低優先級的鍵盤I/O訊號進行響應,因為系統需要不斷地處理中等優先級的快閃記憶體控制器中斷執行緒。

在過去幾年中,我們碰到過類似的死鎖:如大量的數據包使網路介面控制器過載、大量突發的輸入輸出字符使串列控制器過載、SCSI匯流排上連續不斷的數據使磁碟控制器過載。我們開始感到困惑:為什麼外部事件能夠如此輕易地影響到系統呢?事實上,實際應用環境通常不符合我們簡化的設計假設:因為執行緒並非嚴格周期性,我們很難構造解決抖動和過載的系統,即時作業系統只是解決這些問題的方案開始部份。圖1:簡單的單輸入╱單輸出(SISO)控制系統

優先級處理

靜態優先級佔先調度器要求設計工程師為每個執行緒分配唯一的優先級,這樣當有多個執行緒就緒時,調度器知道執行哪個執行緒。確定特定執行緒優先級的常規方法通常有幾種,而非常規方法還有很多。在這些方法中,考慮時間約束與執行緒優先級的方法遠優於那些考慮主觀測量(如執行緒重要性)與優先級的方法。

時限時間單調(DM)和速率單調(RM)算法是兩種最佳的優先級分配方法,這些方法為那些具有較短時限時間和周期的執行緒分配更高的優先級。這些方法的優點在於,如果能以任何靜態優先級算法調度系統,那麼也可以採用DM或RM算法調度系統。此外,如果這些最佳化算法不能有效地調度特定應用的執行緒,那麼其它靜態優先級分配方法也無能為力。

儘管靜態優先級佔先調度機制不能調度所有系統,設計工程師通常仍會選用該方法,商用的RTOS也提供靜態優先級佔先調度方法,因為該方法可提供比動態優先級調度方法更高的穩定性和可預測性。靜態優先級佔先調度器的實現還相對簡單,且要求的作業系統開銷最小。

數位控制

靜態優先級佔先調度尤其適用於數位控制系統,包括導航設備、家用電器、產業製造、化學處理和汽車應用。

圖1提供了一個簡單的單輸入╱單輸出(SISO)控制系統框圖。更為複雜的控制系統能以不同的速率管理多個設備,並採用多輸入╱多輸出(MIMO)控制器。

利用標準的RTOS,編程人員可以輕鬆地實現具有3個平行閉環控制執行緒的MIMO控制器,這些執行緒以不同的速率執行來控制3個不同的設備。由於這些執行緒具有明確的定義和嚴格周期性執行緒集,因此這種控制系統符合經典的速率單調分析假定,成為靜態優先級佔先調度的理想應用。

然而實際上,適用於即時應用的系統同樣也可能出現非周期性或零星外部事件。這些系統包括網路和通訊設備、多媒體播放器、醫療設備和產業控制系統,或者更一般地說,任何連接到可能存在不正常工作狀態的設備環境或在隨機間隙時間內執行的設備環境系統。例如,設備管理者可在任何不可預見時刻將產業過程從生產模式切換至安全模式,使系統在這兩種模式之間切換的執行緒就是零星執行緒。

系統過載

當事件的間隙時間比計畫的短,或者執行緒的執行間隙比計畫的長時,系統將進入過載狀態。此時,系統必須摒棄一些事件或允許一個或多個執行緒錯過其時限時間,因而使更多的關鍵執行緒按時完成。

當系統出現過載時,硬體設備可能會失效,由此產生遠遠偏離常規行為的虛假訊號。錯誤程式碼或惡意程式碼、未經正確培訓的用戶或惡意用戶、過多的外部系統都能產生過多事件,這與設計工程師的統計假設相背離。

調度策略的不同選擇使系統在產生過載時的行為具有很大差異,並且還決定了設計工程師能否預測性地描述系統在過載條件下的特性。例如,時限時間最早優先(EDF)動態優先級調度策略在過載條件下性能很差,由於EDF適用於動態配置執行緒特性,因此系統設計工程師無法預測過載條件下哪個特定執行緒將錯過時限時間。而且,超過額定界限的執行緒以後還可能導致其它執行緒錯過時限時間。

另一方面,設計工程師採用靜態優先級策略可進行可調度性分析,以保證即使在過載條件下重要執行緒不會錯過時限時間。採用可預測調度策略對於安全關鍵系統尤為重要,這些系統要求即使在過載條件下也需要保持可預測性。例如,寧願採用那些在出現過載時錯過幾次用戶介面刷新的系統,而不用那些故障時不能關閉控制閥的系統。

由於設計差的系統通常不能滿足過載條件下重要執行緒和不甚重要執行緒的約束條件,因此設計良好的系統必須有選擇地處理事件,以確保總能滿足關鍵執行緒的時限要求。POSIX的零星調度策略可以很好滿足這樣的設計要求。

零星調度策略

IEEE POSIX規格套件組描述了可攜作業系統的編程介面。1999年,POSIX工作組導入了IEEE 1003.1d,規定了附加的C語言即時擴展。該標準的13.2.4節中,除了之前標準化的輪詢(Round Robin)和FIFO策略外,還增加了零星調度器策略。POSIX工作組詳細規定了適用於處理非周期性和零星事件以及靜態優先級佔先調度條件下執行緒的零星調度策略。

除了適用於FIFO調度和輪詢調度的標準優先等級,零星調度策略的參數還包括一個次級較低優先級的背景優先級(background priority)、補充間隙(replenishment interval)、執行預算,以及在每個補充間隙中所允許的最大補充數量。此外,補充間隙和執行預算還規定了執行緒在其‘常規’優先級上的最大處理器利用率。

如果執行緒需要比其預算更高的處理器時間,那麼零星調度策略將把執行緒的優先級動態地調低至其‘背景’優先級。在這兩種優先級的任意一種下,調度器平等對待該執行緒與其它採用傳統FIFO調度策略的執行緒。例如,就緒隊列中的優先級繼承和配置保持一致,最重要的差異在於執行緒的執行時間和執行緒的優先級重分配。

透過降低執行緒的優先級,系統允許執行其它執行緒,否則零星執行緒將在正常優先級佔先。執行緒優先級的動態調整是使程式設計工程師能建構可預測系統策略的核心功能。零星執行緒的執行將佔用處理器執行時間,這樣每次執行緒被阻塞或調度器佔先時,調度器將從被佔先執行緒預算中扣除佔用的時間。圖2:執行預算的佔用和補充。

當零星執行緒被阻塞時(但未被佔先)時,零星調度器在距離該執行緒最近的去阻塞之後給新的補充事件分配一段補充周期。調度器設定執行預算量,並允許執行緒在去阻塞之後的這段補充期間也可以執行。

在單個周期內,某個執行緒可能需要與較低優先級執行緒競爭多種資源,因此可能出現多個未完成的補充事件。為了使調度器的開銷最小,POSIX規格可使設計工程師限制每個周期內未完成補充事件的數量。如果完成補充事件的數量達到最大值,那麼在這段補充周期內將不會調度額外的補充事件。

如果零星執行緒佔用了全部執行預算,那麼處理器將通知調度器,這樣調度器將調低執行緒的優先級至背景級。執行緒保持該優先級,直到出現下一個補充事件,這時調度器將恢復執行緒的正常優先級。如果因為沒有其它更高優先級的執行緒準備執行,那麼該執行緒將能在背景優先級條件下執行,這樣調度器將執行零星執行緒並且不在執行預算中扣除時間。

這些消耗和補充策略可確保在等於執行緒補充間隙的任何時間間隙內,執行緒只能執行所運算的預算時間那麼長。因此,調度器將迫使執行緒的處理器利用率符合設計工程師的期望,並滿足最佳化的速率單調靜態優先級佔先調度的假定條件。這樣可以確保即使在系統過載條件下仍能保持可預測性。

為了更好地說明這些概念,圖2描述的零星調度執行緒開始於8個單位的執行周期和12個單位的補充周期的預算。執行緒開始執行後,執行緒在阻塞之前先執行4個單位時間。調度器從預算中扣除4個單位時間,並在執行緒啟動12個周期之後調度4個單位的補充執行緒。在執行緒再次阻塞之前,執行緒將無阻塞執行3個單位時間。調度器將這3個單位周期從預算中扣除,並在執行緒去阻塞12個單位周期之後調度3個單位周期的補充執行緒。第二次去阻塞後執行一個單位周期,此時調度器將檢測到執行預算已經用完,並降低該執行緒的優先級。如果沒有更高優先級的執行緒佔先,那麼該執行緒將能以背景優先級自由執行。

由於作業系統時間訊號的解析度限制了零星調度器的精確度,因此解析度為10ms的低解析度時脈時訊號在毫秒級的執行緒周期和預算測量中很難得到好的效果。

應用實例表1:數據包接收利用以下參數。

下面我們將透過考察網路介面控制器(NIC)設備驅動器的接收執行緒,研究如何在實際應用中利用零星調度策略。

在數據封包網路中,應用程式絡透過連接到網路介面控制器(NIC)的設備驅動器進行通訊。這些控制器實現了實體介質通訊協定中的實體層和數據鏈路層,因而提供節點至節點的無差錯連接、協調不同傳輸介質並滿足在介質中傳輸數據所需的實體和電氣規格要求。網路設備驅動器至少包含一個用於接收作為中斷服務一部份的封包數據的執行緒和另一發送封包數據的執行緒。

在設計中採用多節點通訊媒體時,設計工程師首先必須進行如下假設:期望的媒體利用率、媒體頻寬、封包數據包的平均大小和最壞條件下的大小,以及發往相連系統的封包數據之間的期望間隙。根據這些假設,設計工程師就能確定適當的周期、運算間隙和封包數據接收執行緒的優先級。

在我們的設計中需要將系統連接到100Mbps的網路、接收固定大小(64位元組)的封包數據,每個封包數據包的處理時間為25ms並且每64ms接收一次封包數據。所選的NIC在每次接收封包數據時將中斷主處理器,並具有一個32個記錄的環形緩衝記憶體。我們透過使環形緩衝記憶體的佔用量低於50%來防止數據包丟失。在一定的時間限制內處理所有的封包數據包只是一個目標,但必須不引發系統過載。為確保這一點,在不得已的情況下允許系統丟棄數據包。

在表1列出的要求下,我們製作了一個周期執行緒來處理封包數據接收,並為其指定一個根據優先級推導的速率,該速率基於其1,024ms的周期特性。為保證環形緩衝記憶體的利用率低於50%,周期可設定為16×64μs,並且運算間隙為16×25μs。在我們的設計中,我們還採用了用極短中斷異常處理程式的作業系統,並在設定優先級的執行緒中執行中斷處理。

在設計中我意識到,如果入口速率超過每秒15,625個數據包,系統將進入過載狀態。為防止這種情況出現,將接收執行緒的默認FIFO策略設定為零星調度策略,由此將處理器的高優先級利用率限制在期望的最壞條件值,即39%。透過將POSIX調度參數的屬性初始化為期望的周期和執行預算,並在POSIX執行緒製作時傳遞這些屬性值,即可實現上述目標。

零星調度策略可確保系統能經受異常的突發數據包的影響,丟棄過多的輸入傳輸流,但仍然能滿足比NIC接收處理器優先級更低的關鍵執行緒的時間約束。

列表1提供了為網路驅動程式封包數據接收執行緒配置零星調度策略的POSIX C程式碼。QNX作業系統中Realtek NIC設備驅動程式的完全實現可從以下網址下載:www.embedded.com/code.htm。

可預測性

零星調度可透過將非周期性和零星的事件和執行緒打包到一個周期性架構中進行管理。這是靜態優先級佔先調度器中進行過載預處理的一種有效方法。透過採用零星調度,執行緒就能避免在過載情形下出現不期望的訊號抖動或使處理器無法處理低優先級執行緒。利用零星調度,我們就能對不可預知的系統進行預測分析。

如果希望在應用中整合零星調度處理,那麼可以基於Ada95編程語言、QNX RTOS、符合即時Java規格(RTSJ)的Java虛擬機以及幾種不同的即時Linux核心來實現。但是需要注意的是,並非所有的實現方法都完全符合POSIX 1003.1d規格。例如,RTSJ的零星調度策略既不採用C接合,也不實現補充。Ada95實現則採用了POSIX 1003.5 Ada接合。

作者:Lonnie VanZandt


顧問


Email: lonniev@ieee.org





投票數:   加入我的最愛
我來評論 - 零星事件調度策略
評論:  
*  您還能輸入[0]個字
*驗證碼:
 
論壇熱門主題 熱門下載
 •   將邁入40歲的你...存款多少了  •  深入電容觸控技術就從這個問題開始
 •  我有一個數位電源的專利...  •  磷酸鋰鐵電池一問
 •   關於設備商公司的工程師(廠商)薪資前景  •  計算諧振轉換器的同步整流MOSFET功耗損失
 •   Touch sensor & MEMS controller  •  針對智慧電表PLC通訊應用的線路驅動器
 •   下週 深圳 llC 2012 關於PCB免費工具的研討會  •  邏輯閘的應用


EE人生人氣排行
 
返回頁首