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

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

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

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