調度場演算法
『壹』 在分析調度演算法中,為什麼對不同就緒隊列中的進程規定使用不同長度的時間片
這是因為各個就緒隊列的優先順序不一樣，優先順序越高的隊列時間片長度越小，優先順序越低的隊列時間片越長。這樣做的目的是讓那些短而高優先順序的作業迅速完成，而又讓大的作業又能夠處理完成。舉個例子：
假設有3個作業同時到達CPU，需要處理，都在申請CPU資源。其中JOB1需要2個時間片，而JOB2需要100個時間片，JOB3需要1個時間片。如果各個反饋隊列選取的時間片都相同(比如4個時間片)，那麼JOB1和JOB3因作業短回浪費掉CPU資源。而如果按優先順序不同的反饋隊列給予不同的時間片(比如最高優先順序1個時間片，次優級2個時間片....)，那麼將不會有任何時間片的浪費。
你可能會問，那我把各個優先順序的時間片設置為很小，那豈不是就不會浪費CPU資源了？不對，因為時間片太小，那麼對於大作業需要頻繁切換CPU保存現場情況，那麼時間開銷仍然較大，而給各個優先順序不同的時間片就能解決這個問題了。
一般來說，優先順序不同的反饋隊列的時間片是按指數形式遞增的。
『貳』 求一份兒c語言優先順序調度演算法要求如下
#include "string.h"
#define n 10 /*假定系統中可容納的作業數量為n*/
typedef struct jcb
{char name[4]; /*作業名*/
int length; /*作業長度，所需主存大小*/
int printer; /*作業執行所需列印機的數量*/
int tape; /*作業執行所需磁帶機的數量*/
int runtime; /*作業估計執行時間*/
int waittime; /*作業在系統中的等待時間*/
int next; /*指向下一個作業控制塊的指針*/
}JCB; /*作業控制塊類型定義*/
int head; /*作業隊列頭指針定義*/
int tape,printer;
long memory;
JCB jobtable[n]; /*作業表*/
int jobcount=0; /*系統內現有作業數量*/
shele( )
/*作業調度函數*/
{float xk,k;
int p,q,s,t;
do
{p=head;
q=s=-1;
k=0;
while(p!=-1)
{ if(jobtable[p].length<=memory&&jobtable[p].tape<=tape&&jobtable[p].printer<=printer)
{ /*系統可用資源是否滿足作業需求*/
xk=(float)(jobtable[p].waittime)/jobtable[p].runtime;
if(q==0||xk>k) /*滿足條件的第一個作業或者作業q的響應比小於作業p的響應比*/
{k=xk; /*記錄響應比*/
q=p;
t=s;
}/*if*/
}/*if*/
s=p;
p=jobtable[p].next; /*指針p後移*/
}/*while*/
if(q!=-1)
{ if(t==-1) /*是作業隊列的第一個*/
head=jobtable[head].next;
else
jobtable[t].next=jobtable[q].next;
/*為作業q分配資源：分配主存空間；分配磁帶機;分配列印機*/
memory=memory-jobtable[q].length;
tape=tape-jobtable[q].tape;
printer=printer-jobtable[q].printer;
printf("選中作業的作業名：%s\n",jobtable[q].name);
}
}while(q!=-1);
}/*作業調度函數結束*/
main( )
{char name[4];
int size,tcount,pcount,wtime,rtime;
int p;
/*系統數據初始化*/
memory=65536;
tape=4;
printer=2;
head=-1;
printf("輸入作業相關數據(以作業大小為負數停止輸入)：\n");
/*輸入數據，建立作業隊列*/
printf("輸入作業名、作業大小、磁帶機數、列印機數、等待時間、估計執行時間\n");
scanf("%s%d%d %d %d %d",name,&size,&tcount,&pcount,&wtime,&rtime);
while(size!=-1)
{/*創建JCB*/
if(jobcount<n)p=jobcount;
else { printf("無法再創建作業\n");
break;
}
jobcount++;
/*填寫該作業相關內容*/
strcpy(jobtable[p].name,name);
jobtable[p].length=size;
jobtable[p].printer=pcount;
jobtable[p].tape=tcount;
jobtable[p].runtime=rtime;
jobtable[p].waittime=wtime;
/*掛入作業隊列隊首*/
jobtable[p].next=head;
head=p;
/* 輸入一個作業數據*/
printf("輸入作業名、作業大小、磁帶機數、列印機數、等待時間、估計執行時間\n");
scanf("%s%d%d%d%d%d",name,&size,&tcount,&pcount,&wtime,&rtime);
}/*while*/
shele( ); /*進行作業調度*/
}/*main( )函數結束*/
『叄』 調度場演算法怎麼正確處理負號和減號
兩種情況
如果開頭第一個符號是符號，那麼後面那個數就是一個負數，比如-3+1，開頭是符號，掃描到第二個3的時候就記作-3
連續兩個符號，比如3+-4，可以看到加號和減號連在一起了，所以記後面的4為-4,
『肆』 演算法問題，求解6個球隊比賽的調度方法，使得所有的隊能在最短的時間內相互之間完成比賽
首先確定還需要最少的比賽星期數--可由已經比賽最少的D來確定，因為等D的比賽完至少需要四周。
然後，盡可能在前幾周使比賽場數達到最大--3場。下面以A為例分析，其他等同。用圖來表示比賽情況：比賽過的兩隊用線連接。
第一周：因為A只剩下DEF沒有比賽，所以A在第一周內的比賽可能有：AD-BC、AD-BE-CF、AE-BC-DF、AF-DC-BE。按照字母表排序（通常程序也是這么來的），選擇AD-BE-CF。畫圖。
第二周：A還有EF沒有比過，故有AE-BC-DF，其他的可能就只有AE一場，故排除。畫圖。
第三周：AF-CD。從這周開始就有輪空了。畫圖。
第四周：只剩下DE了。。。到此結束~
3.P.S.其實可以從ABCDEF中任何一個隊來這樣分析，我想到了就是：按照字母順序開始分析；按照每周比賽完之後還剩餘比賽場數最大開始分析（一直是D）；還有剩餘比賽場數最少等等
覺得思路都差不多了
『伍』 大家企業中lvs都是用什麼調度演算法
看原理，適用什麼場合吧。畢竟調度演算法有10種之多。一般是rr/wrr/wlc/lc什麼的。
『陸』 機場中對特種車輛調度用什麼演算法
是的，飛行控制區駕駛法例，民航法的要求。區域機場的要求，行駛路線，速度，位置和遇到飛機活動停止和產量有嚴格的要求，內場車輛必須掛民航地區管理局頒發的牌照，並使用標准警告燈。
『柒』 嵌入式實時操作系統調度演算法的發展現狀
肖文鵬
碩士研究生, 北京理工大學計算機系
2003 年 9 月
隨著信息化技術的發展和數字化產品的普及，以計算機技術、晶元技術和軟體技術為核心的嵌入式系統再度成為當前研究和應用的熱點，通信、計算機、消費電子技術（3C）合一的趨勢正在逐步形成，無所不在的網路和無所不在的計算（everything connecting, everywhere computing）正在將人類帶入一個嶄新的信息社會。
一、嵌入式系統
嵌入式系統是以應用為中心，以計算機技術為基礎，並且軟硬體是可裁剪的，適用於對功能、可靠性、成本、體積、功耗等有嚴格要求的專用計算機系統。嵌入式系統最典型的特點是與人們的日常生活緊密相關，任何一個普通人都可能擁有各類形形色色運用了嵌入式技術的電子產品，小到MP3、PDA等微型數字化設備，大到信息家電、智能電器、車載GIS，各種新型嵌入式設備在數量上已經遠遠超過了通用計算機。這也難怪美國著名未來學家尼葛洛龐帝在1999年1月訪華時就預言，4~5年後嵌入式智能工具將成為繼PC機和Internet之後計算機工業最偉大的發明。
1.1 歷史與現狀
雖然嵌入式系統是近幾年才開始真正風靡起來的，但事實上嵌入式這個概念卻很早就已經存在了，從上個世紀70年代單片機的出現到今天各種嵌入式微處理器、微控制器的廣泛應用，嵌入式系統少說也有了近30年的歷史。縱觀嵌入式系統的發展歷程，大致經歷了以下四個階段：
*
無操作系統階段
嵌入式系統最初的應用是基於單片機的，大多以可編程控制器的形式出現，具有監測、伺服、設備指示等功能，通常應用於各類工業控制和飛機、導彈等武器裝備中，一般沒有操作系統的支持，只能通過匯編語言對系統進行直接控制，運行結束後再清除內存。這些裝置雖然已經初步具備了嵌入式的應用特點，但僅僅只是使用8位的CPU晶元來執行一些單線程的程序，因此嚴格地說還談不上"系統"的概念。
這一階段嵌入式系統的主要特點是：系統結構和功能相對單一，處理效率較低，存儲容量較小，幾乎沒有用戶介面。由於這種嵌入式系統使用簡便、價格低廉，因而曾經在工業控制領域中得到了非常廣泛的應用，但卻無法滿足現今對執行效率、存儲容量都有較高要求的信息家電等場合的需要。
*
簡單操作系統階段
20世紀80年代，隨著微電子工藝水平的提高，IC製造商開始把嵌入式應用中所需要的微處理器、I/O介面、串列介面以及RAM、ROM等部件統統集成到一片VLSI中，製造出面向I/O設計的微控制器，並一舉成為嵌入式系統領域中異軍突起的新秀。與此同時，嵌入式系統的程序員也開始基於一些簡單的"操作系統"開發嵌入式應用軟體，大大縮短了開發周期、提高了開發效率。
這一階段嵌入式系統的主要特點是：出現了大量高可靠、低功耗的嵌入式CPU（如Power PC等），各種簡單的嵌入式操作系統開始出現並得到迅速發展。此時的嵌入式操作系統雖然還比較簡單，但已經初步具有了一定的兼容性和擴展性，內核精巧且效率高，主要用來控制系統負載以及監控應用程序的運行。
*
實時操作系統階段
20世紀90年代，在分布控制、柔性製造、數字化通信和信息家電等巨大需求的牽引下，嵌入式系統進一步飛速發展，而面向實時信號處理演算法的DSP產品則向著高速度、高精度、低功耗的方向發展。隨著硬體實時性要求的提高，嵌入式系統的軟體規模也不斷擴大，逐漸形成了實時多任務操作系統（RTOS），並開始成為嵌入式系統的主流。
這一階段嵌入式系統的主要特點是：操作系統的實時性得到了很大改善，已經能夠運行在各種不同類型的微處理器上，具有高度的模塊化和擴展性。此時的嵌入式操作系統已經具備了文件和目錄管理、設備管理、多任務、網路、圖形用戶界面（GUI）等功能，並提供了大量的應用程序介面（API），從而使得應用軟體的開發變得更加簡單。
*
面向Internet階段
21世紀無疑將是一個網路的時代，將嵌入式系統應用到各種網路環境中去的呼聲自然也越來越高。目前大多數嵌入式系統還孤立於Internet之外，隨著Internet的進一步發展，以及Internet技術與信息家電、工業控制技術等的結合日益緊密，嵌入式設備與Internet的結合才是嵌入式技術的真正未來。
信息時代和數字時代的到來，為嵌入式系統的發展帶來了巨大的機遇，同時也對嵌入式系統廠商提出了新的挑戰。目前，嵌入式技術與Internet技術的結合正在推動著嵌入式技術的飛速發展，嵌入式系統的研究和應用產生了如下新的顯著變化：
1. 新的微處理器層出不窮，嵌入式操作系統自身結構的設計更加便於移植，能夠在短時間內支持更多的微處理器。
2. 嵌入式系統的開發成了一項系統工程，開發廠商不僅要提供嵌入式軟硬體系統本身，同時還要提供強大的硬體開發工具和軟體支持包。
3. 通用計算機上使用的新技術、新觀念開始逐步移植到嵌入式系統中，如嵌入式資料庫、移動代理、實時CORBA等，嵌入式軟體平台得到進一步完善。
4. 各類嵌入式linux操作系統迅速發展，由於具有源代碼開放、系統內核小、執行效率高、網路結構完整等特點，很適合信息家電等嵌入式系統的需要，目前已經形成了能與Windows CE、Palm OS等嵌入式操作系統進行有力競爭的局面。
5. 網路化、信息化的要求隨著Internet技術的成熟和帶寬的提高而日益突出，以往功能單一的設備如電話、手機、冰箱、微波爐等功能不再單一，結構變得更加復雜，網路互聯成為必然趨勢。
6. 精簡系統內核，優化關鍵演算法，降低功耗和軟硬體成本。
7. 提供更加友好的多媒體人機交互界面。
1.2 體系結構
根據國際電氣和電子工程師協會（IEEE）的定義，嵌入式系統是"控制、監視或者輔助設備、機器和車間運行的裝置"（devices used to control, monitor, or assist the operation of equipment, machinery or plants）。一般而言，整個嵌入式系統的體系結構可以分成四個部分：嵌入式處理器、嵌入式外圍設備、嵌入式操作系統和嵌入式應用軟體，如圖1所示。
圖1 嵌入式系統的組成
*
嵌入式處理器
嵌入式系統的核心是各種類型的嵌入式處理器，嵌入式處理器與通用處理器最大的不同點在於，嵌入式CPU大多工作在為特定用戶群所專門設計的系統中，它將通用CPU中許多由板卡完成的任務集成到晶元內部，從而有利於嵌入式系統在設計時趨於小型化，同時還具有很高的效率和可靠性。
嵌入式處理器的體系結構經歷了從CISC（復雜指令集）至RISC（精簡指令集）和Compact RISC的轉變，位數則由4位、8位、16位、32位逐步發展到64位。目前常用的嵌入式處理器可分為低端的嵌入式微控制器（Micro Controller Unit，MCU）、中高端的嵌入式微處理器（Embedded Micro Processor Unit，EMPU）、用於計算機通信領域的嵌入式DSP處理器（Embedded Digital Signal Processor，EDSP）和高度集成的嵌入式片上系統（System On Chip，SOC）。
目前幾乎每個半導體製造商都生產嵌入式處理器，並且越來越多的公司開始擁有自主的處理器設計部門，據不完全統計，全世界嵌入式處理器已經超過1000多種，流行的體系結構有30多個系列，其中以ARM、PowerPC、MC 68000、MIPS等使用得最為廣泛。
*
嵌入式外圍設備
在嵌入系統硬體系統中，除了中心控制部件（MCU、DSP、EMPU、SOC）以外，用於完成存儲、通信、調試、顯示等輔助功能的其他部件，事實上都可以算作嵌入式外圍設備。目前常用的嵌入式外圍設備按功能可以分為存儲設備、通信設備和顯示設備三類。
存儲設備主要用於各類數據的存儲，常用的有靜態易失型存儲器（RAM、SRAM）、動態存儲器（DRAM）和非易失型存儲器（ROM、EPROM、EEPROM、FLASH）三種，其中FLASH憑借其可擦寫次數多、存儲速度快、存儲容量大、價格便宜等優點，在嵌入式領域內得到了廣泛應用。
目前存在的絕大多數通信設備都可以直接在嵌入式系統中應用，包括RS-232介面（串列通信介面）、SPI（串列外圍設備介面）、IrDA（紅外線介面）、I2C（現場匯流排）、USB（通用串列匯流排介面）、Ethernet（乙太網介面）等。
由於嵌入式應用場合的特殊性，通常使用的是陰極射線管（CRT）、液晶顯示器（LCD）和觸摸板（Touch Panel）等外圍顯示設備。
*
嵌入式操作系統
為了使嵌入式系統的開發更加方便和快捷，需要有專門負責管理存儲器分配、中斷處理、任務調度等功能的軟體模塊，這就是嵌入式操作系統。嵌入式操作系統是用來支持嵌入式應用的系統軟體，是嵌入式系統極為重要的組成部分，通常包括與硬體相關的底層驅動程序、系統內核、設備驅動介面、通信協議、圖形用戶界面（GUI）等。嵌入式操作系統具有通用操作系統的基本特點，如能夠有效管理復雜的系統資源，能夠對硬體進行抽象，能夠提供庫函數、驅動程序、開發工具集等。但與通用操作系統相比較，嵌入式操作系統在系統實時性、硬體依賴性、軟體固化性以及應用專用性等方面，具有更加鮮明的特點。
嵌入式操作系統根據應用場合可以分為兩大類：一類是面向消費電子產品的非實時系統，這類設備包括個人數字助理（PDA）、行動電話、機頂盒（STB）等；另一類則是面向控制、通信、醫療等領域的實時操作系統，如WindRiver公司的VxWorks、QNX系統軟體公司的QNX等。實時系統（Real Time System）是一種能夠在指定或者確定時間內完成系統功能，並且對外部和內部事件在同步或者非同步時間內能做出及時響應的系統。在實時系統中，操作的正確性不僅依賴於邏輯設計的正確程度，而且與這些操作進行的時間有關，也就是說，實時系統對邏輯和時序的要求非常嚴格，如果邏輯和時序控制出現偏差將會產生嚴重後果。
實時系統主要通過三個性能指標來衡量系統的實時性，即響應時間（Response Time）、生存時間（Survival Time）和吞吐量（Throughput）：
o 響應時間 是實時系統從識別出一個外部事件到做出響應的時間；
o 生存時間 是數據的有效等待時間，數據只有在這段時間內才是有效的；
o 吞吐量 是在給定的時間內系統能夠處理的事件總數，吞吐量通常比平均響應時間的倒數要小一點。
實時系統根據響應時間可以分為弱實時系統、一般實時系統和強實時系統三種。弱實時系統在設計時的宗旨是使各個任務運行得越快越好，但沒有嚴格限定某一任務必須在多長時間內完成，弱實時系統更多關注的是程序運行結果的正確與否，以及系統安全性能等其他方面，對任務執行時間的要求相對來講較為寬松，一般響應時間可以是數十秒或者更長。一般實時系統是弱實時系統和強實時系統的一種折衷，它的響應時間可以在秒的數量級上，廣泛應用於消費電子設備中。強實時系統則要求各個任務不僅要保證執行過程和結果的正確性，同時還要保證在限定的時間內完成任務，響應時間通常要求在毫秒甚至微秒的數量級上，這對涉及到醫療、安全、軍事的軟硬體系統來說是至關重要的。
時限（deadline）是實時系統中的一個重要概念，指的是對任務截止時間的要求，根據時限對系統性能的影響程度，實時系統又可以分為軟實時系統（soft real-time-system）和硬實時系統（hard real-time-system）。軟實時指的是雖然對系統響應時間有所限定，但如果系統響應時間不能滿足要求，並不會導致系統產生致命的錯誤或者崩潰；硬實時則指的是對系統響應時間有嚴格的限定，如果系統響應時間不能滿足要求，就會引起系統產生致命的錯誤或者崩潰。如果一個任務在時限到達之時尚未完成，對軟實時系統來說還是可以容忍的，最多隻會降低系統性能，但對硬實時系統來說則是無法接受的，因為這樣帶來的後果根本無法預測，甚至可能是災難性的。在目前實際運用的實時系統中，通常允許軟硬兩種實時性同時存在，其中一些事件沒有時限要求，另外一些事件的時限要求是軟實時的，而對系統產生關鍵影響的那些事件的時限要求則是硬實時的。
*
嵌入式應用軟體
嵌入式應用軟體是針對特定應用領域，基於某一固定的硬體平台，用來達到用戶預期目標的計算機軟體，由於用戶任務可能有時間和精度上的要求，因此有些嵌入式應用軟體需要特定嵌入式操作系統的支持。嵌入式應用軟體和普通應用軟體有一定的區別，它不僅要求其准確性、安全性和穩定性等方面能夠滿足實際應用的需要，而且還要盡可能地進行優化，以減少對系統資源的消耗，降低硬體成本。
1.3 關鍵問題
嵌入式系統是將先進的計算機技術、半導體技術以及電子技術與特定行業的具體應用相結合的產物，因此必然是一個技術密集、資金密集、高度分散、不斷創新的知識集成系統，嵌入式系統的開發充滿了競爭、機遇與創新，需要解決好如下一些關鍵問題：
1. 內核精巧 嵌入式系統的應用領域一般都是小型電子裝置，系統資源相對有限，因此對內核的要求相當高，較之傳統的操作系統來講要小得多，例如ENEA公司推出的OSE分布式嵌入式系統，整個內核只有5KB。
2. 面向應用 嵌入式系統通常是面向用戶、面向產品、面向特定應用的。嵌入式系統中的CPU大多工作在為特定用戶群定製的環境中，具有低耗、體積小、集成度高等特點，在進行軟硬體設計時必須突出效率、去除冗餘，針對用戶的具體需求對系統進行合理的配置，方能達到理想的性能。
3. 系統精簡 嵌入式系統中的系統軟體和應用軟體通常沒有明顯的區別，不要求其功能及實現上過於復雜，這樣一方面有利於控制系統成本，另一方面也有利於保證系統安全。
4. 性能優化 嵌入式系統通常都要求有一定的實時性保障，為了提高執行速度和系統性能，嵌入式系統中的軟體一般都固化在存儲晶元或者處理器的內部存儲器件當中，而不是存貯在磁碟等外部載體中。由於嵌入式系統的運算速度和存儲容量存在一定程度上的限制，而且大部分系統都必須有較高的實時性保證，因此對軟體質量（特別是可靠性方面）有著較高的要求。
5. 專業開發 嵌入式系統本身並不具備自主開發能力，用戶不能直接在其上進行二次開發。當系統完成之後，用戶如果需要修改其中某個程序的功能，必須藉助一套完整的開發工具和環境。嵌入式系統中專用的開發工具和環境通常是基於通用計算機上的軟硬體設備，以及各種邏輯分析儀、混合信號示波器等。
二、嵌入式Linux
Linux從1991年問世到現在，短短的十幾年時間已經發展成為功能強大、設計完善的操作系統之一，不僅可以與各種傳統的商業操作系統分庭抗爭，在新興的嵌入式操作系統領域內也獲得了飛速發展。嵌入式Linux（Embedded Linux）是指對標准Linux經過小型化裁剪處理之後，能夠固化在容量只有幾K或者幾M位元組的存儲器晶元或者單片機中，適合於特定嵌入式應用場合的專用Linux操作系統。
2.1 優勢
嵌入式Linux的開發和研究是操作系統領域中的一個熱點，目前已經開發成功的嵌入式系統中，大約有一半使用的是Linux。Linux之所以能在嵌入式系統市場上取得如此輝煌的成果，與其自身的優良特性是分不開的。
*
廣泛的硬體支持
Linux能夠支持x86、ARM、MIPS、ALPHA、PowerPC等多種體系結構，目前已經成功移植到數十種硬體平台，幾乎能夠運行在所有流行的CPU上。Linux有著異常豐富的驅動程序資源，支持各種主流硬體設備和最新硬體技術，甚至可以在沒有存儲管理單元（MMU）的處理器上運行，這些都進一步促進了Linux在嵌入式系統中的應用。
*
內核高效穩定
Linux內核的高效和穩定已經在各個領域內得到了大量事實的驗證，Linux的內核設計非常精巧，分成進程調度、內存管理、進程間通信、虛擬文件系統和網路介面五大部分，其獨特的模塊機制可以根據用戶的需要，實時地將某些模塊插入到內核或從內核中移走。這些特性使得Linux系統內核可以裁剪得非常小巧，很適合於嵌入式系統的需要。
*
開放源碼，軟體豐富
Linux是開放源代碼的自由操作系統，它為用戶提供了最大限度的自由度，由於嵌入式系統千差萬別，往往需要針對具體的應用進行修改和優化，因而獲得源代碼就變得至關重要了。Linux的軟體資源十分豐富，每一種通用程序在Linux上幾乎都可以找到，並且數量還在不斷增加。在Linux上開發嵌入式應用軟體一般不用從頭做起，而是可以選擇一個類似的自由軟體做為原型，在其上進行二次開發。
*
優秀的開發工具
開發嵌入式系統的關鍵是需要有一套完善的開發和調試工具。傳統的嵌入式開發調試工具是在線模擬器（In-Circuit Emulator，ICE），它通過取代目標板的微處理器，給目標程序提供一個完整的模擬環境，從而使開發者能夠非常清楚地了解到程序在目標板上的工作狀態，便於監視和調試程序。在線模擬器的價格非常昂貴，而且只適合做非常底層的調試，如果使用的是嵌入式Linux，一旦軟硬體能夠支持正常的串口功能時，即使不用在線模擬器也可以很好地進行開發和調試工作，從而節省了一筆不小的開發費用。嵌入式Linux為開發者提供了一套完整的工具鏈（Tool Chain），它利用GNU的gcc做編譯器，用gdb、kgdb、xgdb做調試工具，能夠很方便地實現從操作系統到應用軟體各個級別的調試。
*
完善的網路通信和文件管理機制
Linux至誕生之日起就與Internet密不可分，支持所有標準的Internet網路協議，並且很容易移植到嵌入式系統當中。此外，Linux還支持ext2、fat16、fat32、romfs等文件系統，這些都為開發嵌入式系統應用打下了很好的基礎。
2.2 挑戰
目前，嵌入式Linux系統的研發熱潮正在蓬勃興起，並且占據了很大的市場份額，除了一些傳統的Linux公司（如RedHat、MontaVista等）正在從事嵌入式Linux的開發和應用之外，IBM、Intel、Motorola等著名企業也開始進行嵌入式Linux的研究。雖然前景一片燦爛，但就目前而言，嵌入式Linux的研究成果與市場的真正要求仍有一段差距，要開發出真正成熟的嵌入式Linux系統，還需要從以下幾個方面做出努力。
*
提高系統實時性
Linux雖然已經被成功地應用到了PDA、行動電話、車載電視、機頂盒、網路微波爐等各種嵌入式設備上，但在醫療、航空、交通、工業控制等對實時性要求非常嚴格的場合中還無法直接應用，原因在於現有的Linux是一個通用的操作系統，雖然它也採用了許多技術來加快系統的運行和響應速度，並且符合POSIX 1003.1b標准，但從本質上來說並不是一個嵌入式實時操作系統。Linux的內核調度策略基本上是沿用UNIX系統的，將它直接應用於嵌入式實時環境會有許多缺陷，如在運行內核線程時中斷被關閉，分時調度策略存在時間上的不確定性，以及缺乏高精度的計時器等等。正因如此，利用Linux作為底層操作系統，在其上進行實時化改造，從而構建出一個具有實時處理能力的嵌入式系統，是現在日益流行的解決方案。
*
改善內核結構
Linux內核採用的是整體式結構（Monolithic），整個內核是一個單獨的、非常大的程序，這樣雖然能夠使系統的各個部分直接溝通，有效地縮短任務之間的切換時間，提高系統響應速度，但與嵌入式系統存儲容量小、資源有限的特點不相符合。嵌入式系統經常採用的是另一種稱為微內核（Microkernel）的體系結構，即內核本身只提供一些最基本的操作系統功能，如任務調度、內存管理、中斷處理等，而類似於文件系統和網路協議等附加功能則運行在用戶空間中，並且可以根據實際需要進行取捨。Microkernel的執行效率雖然比不上Monolithic，但卻大大減小了內核的體積，便於維護和移植，更能滿足嵌入式系統的要求。可以考慮將Linux內核部分改造成Microkernel，使Linux在具有很高性能的同時，又能滿足嵌入式系統體積小的要求。
*
完善集成開發平台
引入嵌入式Linux系統集成開發平台，是嵌入式Linux進一步發展和應用的內在要求。傳統上的嵌入式系統都是面向具體應用場合的，軟體和硬體之間必須緊密配合，但隨著嵌入式系統規模的不斷擴大和應用領域的不斷擴展，嵌入式操作系統的出現就成了一種必然，因為只有這樣才能促成嵌入式系統朝層次化和模塊化的方向發展。很顯然，嵌入式集成開發平台也是符合上述發展趨勢的，一個優秀的嵌入式集成開發環境能夠提供比較完備的模擬功能，可以實現嵌入式應用軟體和嵌入式硬體的同步開發，從而擺脫了"嵌入式應用軟體的開發依賴於嵌入式硬體的開發，並且以嵌入式硬體的開發為前提"的不利局面。一個完整的嵌入式集成開發平台通常包括編譯器、連接器、調試器、跟蹤器、優化器和集成用戶界面，目前Linux在基於圖形界面的特定系統定製平台的研究上，與Windows CE等商業嵌入式操作系統相比還有很大差距，整體集成開發環境有待提高和完善。
三、關鍵技術
嵌入式系統是一種根據特定用途所專門開發的系統，它只完成預期要完成的功能，因此其開發過程和開發環境同傳統的軟體開發相比有著顯著的不同。
3.1 開發流程
在嵌入式系統的應用開發中，整個系統的開發過程如圖2所示：
圖2 嵌入式系統的開發流程
嵌入式系統發展到今天，對應於各種微處理器的硬體平台一般都是通用的、固定的、成熟的，這就大大減少了由硬體系統引入錯誤的機會。此外，由於嵌入式操作系統屏蔽了底層硬體的復雜性，使得開發者通過操作系統提供的API函數就可以完成大部分工作，因此大大簡化了開發過程，提高了系統的穩定性。嵌入式系統的開發者現在已經從反復進行硬體平台設計的過程中解脫出來，從而可以將主要精力放在滿足特定的需求上。
嵌入式系統通常是一個資源受限的系統，因此直接在嵌入式系統的硬體平台上編寫軟體比較困難，有時候甚至是不可能的。目前一般採用的解決辦法是首先在通用計算機上編寫程序，然後通過交叉編譯生成目標平台上可以運行的二進制代碼格式，最後再下載到目標平台上的特定位置上運行。
需要交叉開發環境（Cross Development Environment）的支持是嵌入式應用軟體開發時的一個顯著特點，交叉開發環境是指編譯、鏈接和調試嵌入式應用軟體的環境，它與運行嵌入式應用軟體的環境有所不同，通常採用宿主機／目標機模式，如圖3所示。
圖3 交叉開發環境
宿主機（Host）是一台通用計算機（如PC機或者工作站），它通過串口或者乙太網介面與目標機通信。宿主機的軟硬體資源比較豐富，不但包括功能強大的操作系統（如Windows和Linux），而且還有各種各樣優秀的開發工具（如WindRiver的Tornado、Microsoft的Embedded Visual C++等），能夠大大提高嵌入式應用軟體的開發速度和效率。
目標機（Target）一般在嵌入式應用軟體開發期間使用，用來區別與嵌入式系統通信的宿主機，它可以是嵌入式應用軟體的實際運行環境，也可以是能夠替代實際運行環境的模擬系統，但軟硬體資源通常都比較有限。嵌入式系統的交叉開發環境一般包括交叉編譯器、交叉調試器和系統模擬器，其中交叉編譯器用於在宿主機上生成能在目標機上運行的代碼，而交叉調試器和系統模擬器則用於在宿主機與目標機間完成嵌入式軟體的調試。在採用宿主機／目標機模式開發嵌入式應用軟體時，首先利用宿主機上豐富的資源和良好的開發環境開發和模擬調試目標機上的軟體，然後通過串口或者以網路將交叉編譯生成的目標代碼傳輸並裝載到目標機上，並在監控程序或者操作系統的支持下利用交叉調試器進行分析和調試，最後目標機在特定環境下脫離宿主機單獨運行。
建立交叉開發環境是進行嵌入式軟體開發的第一步，目前常用的交叉開發環境主要有開放和商業兩種類型。開放的交叉開發環境的典型代表是GNU工具鏈、目前已經能夠支持x86、ARM、MIPS、PowerPC等多種處理器。商業的交叉開發環境則主要有Metrowerks CodeWarrior、ARM Software Development Toolkit、SDS Cross compiler、WindRiver Tornado、Microsoft Embedded Visual C++等。
3.2 交叉編譯和鏈接
在完成嵌入式軟體的編碼之後，需要進行編譯和鏈接以生成可執行代碼，由於開發過程大多是在使用Intel公司x86系列CPU的通用計算機上進行的，而目標環境的處理器晶元卻大多為ARM、MIPS、PowerPC、DragonBall等系列的微處理器，這就要求在建立好的交叉開發環境中進行交叉編譯和鏈接。
交叉編譯器和交叉鏈接器是能夠在宿主機上運行，並且能夠生成在目標機上直接運行的二進制代碼的編譯器和鏈接器。例如在基於ARM體系結構的gcc交叉開發環境中，arm-linux-gcc是交叉編譯器，arm-linux-ld是交叉鏈接器。通常情況下，並不是每一種體系結構的嵌入式微處理器都只對應於一種交叉編譯器和交叉鏈接器，比如對於M68K體系結構的gcc交叉開發環境而言，就對應於多種不同的編譯器和鏈接器。如果使用的是COFF格式的可執行文件，那麼在編譯Linux內核時需要使用m68k-coff-gcc和m68k-coff-ld，而在編譯應用程序時則需要使用m68k-coff-pic-gcc和m68k-coff-pic-ld。
嵌入式系統在鏈接過程中通常都要求使用較小的函數庫，以便最後產生的可執行代碼能夠盡可能地小，因此實際運用時一般使用經過特殊處理的函數庫。對於嵌入式L
『捌』 求一段c語言計算程序代碼，要能正確處理裡面運算符的優先計算順序和圓括弧的優先順序。
看來這個問題還沒有搞定啊，我來幫你搞定吧，稍等~
好了，現在搞定，發給你吧~
為了你方便看，就寫在一個cpp文件里了，比較長，三百多行。我已經編譯通過，也做了簡單測試，沒詳細測，如果有bug，你就自己改一下吧。表達式輸入完了之後直接回車，就出結果了，跟平時輸入字元串一樣。
/**********************************************
算術表達式求值的算符優先順序演算法
利用棧來實現括弧匹配和表達式求值
演算法的詳細說明，請查看清華大學出版社《數據結構》，嚴蔚敏&吳偉民著，3.3節
***********************************************/
#include<stdlib.h>
#include<stdio.h>
#include<ctype.h>
#defineSTACK_INIT_SIZE100//存儲空間初始分配量
#defineSTACKINCREMENT10//存儲空間分配增量
#defineOK0
#defineERROR127
//定義一個順序棧
typedefstruct
{
int*base;//在棧構造之前和銷毀之後，base的值為NULL
int*top;//棧頂指針
intstacksize;//當前已分配的存儲空間,以元素為單位
}SqStack;intInitStack(SqStack*S)
{
//構造一個空棧
S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(SqStack));
if(NULL==S->base)
{//內存分配失敗
returnERROR;
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
returnOK;
}
charGetTop(SqStack*S,char*element)
{
//若棧不空，取棧頂元素,用element返回
if(S->base==S->top)
{
returnERROR;
}
*element=*(S->top-1);
return*element;
}
intPush(SqStack*S,intelement)
{
//插入元素element為新的棧頂元素
if((S->top-S->base)>S->stacksize)
{//棧滿，追加空間
S->base=(int*)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SqStack));
if(NULL==S->base)
{
returnERROR;
}
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=element;
returnOK;
}
intPop(SqStack*S,int*element)
{
//若棧不為空，則刪除棧頂元素，用element返回其值
if(S->top==S->base)
{
returnERROR;
}
*element=*(--S->top);
returnOK;
}
intPopOPTR(SqStack*S,char*element)
{
if(S->top==S->base)
{
returnERROR;
}
*element=*(--S->top);
returnOK;
}
//判斷字元c是否在集合OP中
intInOP(charc,charOP[7])
{
for(inti=0;i<7;i++)
{
if(c==OP[i])
{
returnOK;
}
}
returnERROR;
}
//判斷運算符的優先順序
intCompare(inta,intb)
{
if('+'==a)
{
switch(b)
{
case'+':
return'>';
case'-':
return'>';
case'*':
return'<';
case'/':
return'<';
case'(':
return'<';
case')':
return'>';
case' ':
return'>';
}
}
if('-'==a)
{
switch(b)
{
case'+':
return'>';
case'-':
return'>';
case'*':
return'<';
case'/':
return'<';
case'(':
return'<';
case')':
return'>';
case' ':
return'>';
}
}
if('*'==a)
{
switch(b)
{
case'+':
return'>';
case'-':
return'>';
case'*':
return'>';
case'/':
return'>';
case'(':
return'<';
case')':
return'>';
case' ':
return'>';
}
}
if('/'==a)
{
switch(b)
{
case'+':
return'>';
case'-':
return'>';
case'*':
return'>';
case'/':
return'>';
case'(':
return'<';
case')':
return'>';
case' ':
return'>';
}
}
if('('==a)
{
switch(b)
{
case'+':
return'<';
case'-':
return'<';
case'*':
return'<';
case'/':
return'<';
case'(':
return'<';
case')':
return'=';
}
}
if(')'==a)
{
switch(b)
{
case'+':
return'>';
case'-':
return'>';
case'*':
return'>';
case'/':
return'>';
case')':
return'>';
case' ':
return'>';
}
}
if(' '==a)
{
switch(b)
{
case'+':
return'<';
case'-':
return'<';
case'*':
return'<';
case'/':
return'<';
case'(':
return'<';
case' ':
return'=';
}
}
returnERROR;
}
//簡單計算
intCalculate(intleft,charoper,intright)
{
intresult=0;
switch(oper)
{
case'+':
result=left+right;
break;
case'-':
result=left-right;
break;
case'*':
result=left*right;
break;
case'/':
result=left/right;
break;
}
returnresult;
}
/**********************************************
算術表達式求值的算符優先順序演算法，設OPTR和OPND分別為運算符棧和運算數棧
OP為運算符集合
**********************************************/
intmain()
{
SqStackOPTR,OPND;
intelement=0;
charOPTR_element;
intleftNum,rightNum;
charinput;//獲取輸入
charOP[7]={'+','-','*','/','(',')',' '};
InitStack(&OPTR);
Push(&OPTR,' ');
InitStack(&OPND);
printf("請輸入表達式 ");
input=getchar();
while(' '!=input||' '!=GetTop(&OPTR,&OPTR_element))
{
inttemp=0;
if(isdigit(input))
{//如果是數字
ungetc(input,stdin);//返回給輸入流
scanf("%d",&temp);
Push(&OPND,temp);//數字就進OPND棧
input=getchar();
continue;
}
if(OK==InOP(input,OP))
{
GetTop(&OPTR,&OPTR_element);
switch(Compare(OPTR_element,input))
{
case'<'://棧頂元素優先順序低
Push(&OPTR,input);//運算符進OPTR棧
input=getchar();
break;
case'='://脫括弧
PopOPTR(&OPTR,&OPTR_element);
input=getchar();
break;
case'>'://退棧，並將運算結果入棧
PopOPTR(&OPTR,&OPTR_element);
Pop(&OPND,&rightNum);
Pop(&OPND,&leftNum);
Push(&OPND,Calculate(leftNum,OPTR_element,rightNum));
break;
default:
printf("表達式括弧不匹配 ");
returnERROR;
}//switch
}//if
else
{
printf("表達式內有未知字元,即將退出 ");
returnERROR;
}
}//while
intvalue;
Pop(&OPND,&value);
printf("結果=%d ",value);
returnOK;
}//end