基于嵌入式多處理器操作系統(tǒng)任務調度的研究.pdf

1、嵌入式系統(tǒng)已經越來越多地應用在各個領域中，隨著硬件和軟件技術的發(fā)展，操作系統(tǒng)在嵌入式領域發(fā)揮著越來越重要的作用。其中大多數嵌入式系統(tǒng)都是基于單處理器環(huán)境，而隨著計算機技術的迅速發(fā)展，嵌入式系統(tǒng)也開始應用于多處理器環(huán)境。從單處理器到多處理器，從串行到并行。多處理器并行系統(tǒng)由于其高性能和可靠性，已成為新一代嵌入式系統(tǒng)發(fā)展的趨向。 在嵌入式多處理器系統(tǒng)中，任務調度問題的規(guī)模也越來越大，多線程的任務調度成為決定系統(tǒng)性能的關鍵，但是多處理

2、器系統(tǒng)中任務調度的求解是一個NP完全問題。當系統(tǒng)中的處理器和任務數目較大時，用一般的窮舉遍歷方法是不現實的。在大多數的情況下，人們尋求的只是次優(yōu)解。 本文首先研究多處理器并行環(huán)境下的各種任務調度計算模型和常用的各種任務調度算法，分析嵌入式系統(tǒng)和多處理器系統(tǒng)的結構特性。采用單芯片多處理器(CMPChipMultiProcessors)硬件架構和對稱多處理(SMPSymmetricMultiProcessing)操作系統(tǒng)模式，應用集

3、中式的調度器模型，提高處理器的總體計算能力。結合并行計算的思想，通過將任務進行先劃分后組合的方式，減少任務調度中的開銷。研究E.B.Fernandez提出的算法模型，改進原有的計算模型和調度模型，應用啟發(fā)式算法求解最小運行時間。分析單處理器環(huán)境下基本的組合分配算法和流量算法，將圖論里的深度搜索思想應用到簡化任務圖上。在流量算法中，應用最大流最小截集算法(MaxFlow/MinCut)求解任務調度問題，并在計算模型中融入疊加開銷參數。在此