第一篇：中科大軟院算法導(dǎo)論區(qū)間樹實(shí)驗(yàn)報(bào)告（定稿）

區(qū)間樹實(shí)驗(yàn)報(bào)告

1.區(qū)間樹的實(shí)驗(yàn)源碼見(jiàn)另外一個(gè)文件

2.區(qū)間樹實(shí)驗(yàn)分析

2.1 需求分析

基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)選擇紅黑樹，每個(gè)結(jié)點(diǎn)x 包含一個(gè)區(qū)間域int[x]，x 的關(guān)鍵字為區(qū)間的低 端點(diǎn)low[int[x]]，對(duì)樹；進(jìn)行中序遍歷就可按低端點(diǎn)的次序列出個(gè)區(qū)間，結(jié)點(diǎn)還包含一個(gè) max[x]，即以x 為根的子樹中所有區(qū)間的端點(diǎn)的最大值。如：

實(shí)驗(yàn)要求：將紅黑樹擴(kuò)展為區(qū)間樹(1)區(qū)間的端點(diǎn)為正整數(shù)，隨機(jī)生成；

(2)內(nèi)部節(jié)點(diǎn)數(shù)為n：2^4，2^6,2^8,2^10,2^12；

(3)測(cè)試插入，刪除，查找的時(shí)間并繪出曲線，運(yùn)行次數(shù)為10 次；

2.2 程序設(shè)計(jì)

區(qū)間樹的操作基本和紅黑樹的相同，在其基礎(chǔ)上增加了一個(gè)新方法： INTERVAL_SEARCH(T,i）；它用來(lái)找出樹中覆蓋區(qū)間i 的那個(gè)結(jié)點(diǎn)。如果樹中不存在，則返 回nil[T]指針。代碼如下：

ITNode* IntervalTree::Interval_Search(Interval i){ ITNode* x=root;while(x!=Nil &&!x->Overlap(i)){ // x!= nil and i doesn't overlap int[x] if(x->left!=Nil && x->left->max>=i.low)x=x->left;else x=x->right;} return x;} 區(qū)間樹的插入、刪除除了有可能改變紅黑樹性質(zhì)，還有可能改變結(jié)點(diǎn)的max 值。前者 向紅黑樹那樣處理就可以了，又

max[x] = max(high[int[x]], max[left[x]], max[right[x]])為解決后者，增加一方法Nodemax（），讓它來(lái)維護(hù)結(jié)點(diǎn)的max 值。Nodemax()如下： void ITNode::NodeMax(ITNode* xl, ITNode* xr){ Type tp=this->interval->high;if(tp < xl->max)tp=xl->max;if(tp < xr->max)tp=xr->max;this->max=tp;} 在左旋、右旋時(shí)調(diào)用此方法。

2.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)選擇紅黑樹，每個(gè)結(jié)點(diǎn)x 包含一個(gè)區(qū)間域int[x]，x 的關(guān)鍵字為區(qū)間的低 端點(diǎn)low[int[x]]，對(duì)樹；進(jìn)行中序遍歷就可按低端點(diǎn)的次序列出個(gè)區(qū)間，結(jié)點(diǎn)還包含一個(gè) max[x]，即以x 為根的子樹中所有區(qū)間的端點(diǎn)的最大.2.4 運(yùn)行結(jié)果

為了增加算法運(yùn)行時(shí)間減少誤差，search、insert、delete 的都是樹的最小關(guān)鍵字結(jié)點(diǎn)，讓查找深度盡可能的深。運(yùn)行時(shí)間如下所示，單位:us： T(us)方法

search insert delete 2^4 2.933 14.176 2.933 2^6 3.399 17.098 3.422 2^8 3.422 20.042 3.911 2^10 4.399 17.598 4.547 2^12 3.441 18.087 4.888 運(yùn)行

平

臺(tái)

：

2.5 結(jié)果分析

根據(jù)以上數(shù)據(jù)作如下t-lg(n)圖像：

有圖知當(dāng)n=2^8 時(shí)，Insert 操作數(shù)據(jù)不是很好，出去它可得如下圖：

在樹規(guī)模較小的時(shí)候, 會(huì)對(duì)n 造成比較明顯的影響, 3 條測(cè)量的曲線中, insert 與lgn 的 曲線增長(zhǎng)率最符合，但都大致以lgn 增長(zhǎng)。，在n 較小的時(shí)候, 算法執(zhí)行時(shí)間受系統(tǒng)本身配置

影響較大, 數(shù)據(jù)也不會(huì)很準(zhǔn)確, 這個(gè)也可以從表格中看出, 有一些與通常時(shí)間偏差較大的記 錄, 這個(gè)應(yīng)該和系統(tǒng)的任務(wù)調(diào)度, 和其他程序的影響有關(guān).2.6 心得體會(huì)

由于區(qū)間樹的很多操作與紅黑書相似，此程序最大難點(diǎn)在維護(hù)結(jié)點(diǎn)的max 值。應(yīng)仔細(xì)

分析左旋、右旋、插入、刪除時(shí)改變那些結(jié)點(diǎn)的max 值、如何改變結(jié)點(diǎn)的max 值，這樣編 程時(shí)會(huì)事半功倍。

區(qū)間樹與紅黑樹差別不是很大，很多操作都相似，可考慮從紅黑樹繼承，實(shí)現(xiàn)代碼重用。例如：

class ITNode: public RBTNode{ private: Type NodeMax(ITNode* x);public: Type max;//以x 為根的子樹中所有區(qū)間的端點(diǎn)最大值 Type low;Type high;ITNode(Type ilow=0, Type ihigh=0):RBTNode(ilow), low(ilow), high(ihigh){max=NodeMax(this)} };class IntervalTree : public RBTree{ public: IntervalTree(Type ilow=0, Type ihigh=0):RBTree(ilow){} void Interval_Insert(ITNode* x){RB_Insert(x);} void Interval_Insert(Type ilow, Type ihigh){Interval_Insert(new ITNode(ilow,ihigh));} void Interval_Delete(ITNode* x){RB_Delete(x);} ITNode* Interval_Search(Interval i);};

第二篇：中科大軟院嵌入式期末總結(jié)重點(diǎn)講義資料

復(fù)習(xí)提綱：（C語(yǔ)言翻譯匯編）

一、概述

1.嵌入式系統(tǒng)是“用于控制、監(jiān)視或者輔助操作機(jī)器和設(shè)備的裝置 國(guó)內(nèi)普遍認(rèn)同的嵌入式系統(tǒng)定義為：

以應(yīng)用為中心、以計(jì)算機(jī)技術(shù)為基礎(chǔ)、軟硬件可裁剪、適應(yīng)應(yīng)用系統(tǒng)對(duì)功能、可靠性、成本、體積、功耗嚴(yán)格要求的專用計(jì)算機(jī)系統(tǒng)。

2.嵌入式系統(tǒng)的幾個(gè)重要特征（簡(jiǎn)述5特征）

(1)嵌入式系統(tǒng)工業(yè)是不可壟斷的高度分散的工業(yè)

從某種意義上來(lái)說(shuō),通用計(jì)算機(jī)行業(yè)的技術(shù)是壟斷的。

嵌入式系統(tǒng)則不同,它是一個(gè)分散的工業(yè),充滿了競(jìng)爭(zhēng)、機(jī)遇與創(chuàng)新,沒(méi)有哪一個(gè)系列的處理器和操作系統(tǒng)能夠壟斷全部市場(chǎng)。（2）操作系統(tǒng)內(nèi)核小

由于嵌入式系統(tǒng)一般是應(yīng)用于小型電子裝置的，系統(tǒng)資源相對(duì)有限，所以內(nèi)核較之傳統(tǒng)的操作系統(tǒng)要小得多。

比如ENEA公司的OSE分布式系統(tǒng)，內(nèi)核只有5K，而Windows的內(nèi)核則要大得多。

（3）專用性強(qiáng)

嵌入式系統(tǒng)的個(gè)性化很強(qiáng)，其中的軟件系統(tǒng)和硬件的結(jié)合非常緊密，一般要針對(duì)硬件進(jìn)行系統(tǒng)的移植。

即使在同一品牌、同一系列的產(chǎn)品中也需要根據(jù)系統(tǒng)硬件的變化和增減不斷進(jìn)行修改。

同時(shí)針對(duì)不同的任務(wù)，往往需要對(duì)系統(tǒng)進(jìn)行較大更改，程序的編譯下載要和系統(tǒng)相結(jié)合，這種修改和通用軟件的“升級(jí)”是完全不同的概念。

（4）系統(tǒng)精簡(jiǎn)

嵌入式系統(tǒng)一般沒(méi)有系統(tǒng)軟件和應(yīng)用軟件的明顯區(qū)分，不要求其功能設(shè)計(jì)及實(shí)現(xiàn)上過(guò)于復(fù)雜，這樣一方面利于控制系統(tǒng)成本，同時(shí)也利于實(shí)現(xiàn)系統(tǒng)安全。（5）高實(shí)時(shí)性O(shè)S 這是嵌入式軟件的基本要求，而且軟件要求固態(tài)存儲(chǔ)，以提高速度。軟件代碼要求高質(zhì)量和高可靠性、實(shí)時(shí)性。

6）嵌入式軟件開發(fā)走向標(biāo)準(zhǔn)化

嵌入式系統(tǒng)的應(yīng)用程序可以沒(méi)有操作系統(tǒng)直接在芯片上運(yùn)行。

為了合理地調(diào)度多任務(wù)、利用系統(tǒng)資源、系統(tǒng)函數(shù)以及和專家?guī)旌瘮?shù)接口，用戶必須自行選配RTOS（Real－Time Operating System）開發(fā)平臺(tái)，這樣才能保證程序執(zhí)行的實(shí)時(shí)性、可靠性，并減少開發(fā)時(shí)間，保障軟件質(zhì)量。（7）嵌入式系統(tǒng)開發(fā)需要開發(fā)工具和環(huán)境

由于其本身不具備自主開發(fā)能力，即使設(shè)計(jì)完成以后，用戶通常也是不能對(duì)其中的程序功能進(jìn)行修改，必須有一套開發(fā)工具和環(huán)境才能進(jìn)行開發(fā)。

這些工具和環(huán)境一般是基于通用計(jì)算機(jī)上的軟硬件設(shè)備以及各種邏輯分析儀、混合信號(hào)示波器等。

開發(fā)時(shí)往往有主機(jī)和目標(biāo)機(jī)的概念，主機(jī)用于程序的開發(fā)，目標(biāo)機(jī)作為最后的執(zhí)行機(jī)，開發(fā)時(shí)需要交替結(jié)合進(jìn)行。（8）嵌入式系統(tǒng)運(yùn)行環(huán)境差異很大：

（9）嵌入式系統(tǒng)比通用PC系統(tǒng)資源少得多：

（10）一般的嵌入式系統(tǒng)具有低功耗、體積小、集成度高、成本低等特點(diǎn)：（11）建立完整的嵌入式系統(tǒng)的系統(tǒng)測(cè)試和可靠性評(píng)估體系，保證嵌入式系統(tǒng)高效、可靠、穩(wěn)定工作：（12）具有較長(zhǎng)的生命周期

3.嵌入式系統(tǒng)的組成（最后的圖，有印象）嵌入式硬件系統(tǒng) 嵌入式處理器 各種類型存儲(chǔ)器 模擬電路及電源 接口控制器及接插件 嵌入式軟件系統(tǒng)

實(shí)時(shí)操作系統(tǒng)（RTOS）板級(jí)支持包（BSP）

設(shè)備驅(qū)動(dòng)（Device Driver）協(xié)議棧（Protocol Stack）應(yīng)用程序（Application）

4.嵌入式系統(tǒng)的實(shí)時(shí)性

二、嵌入式系統(tǒng)設(shè)計(jì)方法、過(guò)程（2.3ppt）1.交叉開發(fā)環(huán)境、先在通用PC機(jī)上編程，然后通過(guò)交叉編譯鏈接，將程序做成目標(biāo)平臺(tái)上可以運(yùn)行的二進(jìn)制代碼格式。最后將程序下載到目標(biāo)平臺(tái)上的特定位置由目標(biāo)板上啟動(dòng)代碼運(yùn)行這段二進(jìn)制代碼。

交叉開發(fā)：在一臺(tái)通用計(jì)算機(jī)上進(jìn)行軟件的編輯編譯，然后下載到嵌入式設(shè)備中運(yùn)行調(diào)試的開發(fā)方式。

開發(fā)計(jì)算機(jī)一般稱宿 主機(jī)，嵌入式設(shè)備稱為目標(biāo)機(jī)，在宿主機(jī)上編譯好的程序，下載到目標(biāo)機(jī)上運(yùn)行。

交叉開發(fā)環(huán)境一般由運(yùn)行于宿主機(jī)上的交叉開發(fā)軟件、宿主機(jī)到目標(biāo)機(jī)的調(diào)試通道組成。

如基于ARM9、μCOS的嵌入式系統(tǒng)開發(fā)，需要安裝交叉編譯工具ADS。基于VxWorks的開發(fā)環(huán)境：Tornado 2.幾種常用的調(diào)試方法、指令集模擬器

一種利用PC機(jī)端的仿真開發(fā)軟件模擬調(diào)試的方法。

如：Skyeye 清華大學(xué)陳渝主持的自由軟件項(xiàng)目,http://004km.cn

ARM公司的ARMulator模擬器 駐留監(jiān)控軟件

駐留監(jiān)控程序運(yùn)行在目標(biāo)板上，PC機(jī)端調(diào)試軟件可通過(guò)并口、串口、網(wǎng)口與之交互，以完成程序執(zhí)行、存儲(chǔ)器及寄存器讀寫、斷點(diǎn)設(shè)置等任務(wù)

ARM公司的Angel是長(zhǎng)駐在目標(biāo)機(jī)Flash中的監(jiān)控程序 JTAG仿真器(基于JTAG的ICD(In-Circuit Debugger))

通過(guò)ARM芯片的JTAG邊界掃描口與ARM核進(jìn)行通信，不占用目

標(biāo)板的資源，是目前使用最廣泛的調(diào)試手段 在線仿真器ICE(In-Circuit Emulator)

使用仿真頭代替目標(biāo)板上的CPU，可以完全仿真ARM芯片的行為。但結(jié)構(gòu)較復(fù)雜，價(jià)格昂貴，通常用于ARM硬件開發(fā)中

（ARM-LINUX開發(fā)一般過(guò)程不要求）

三、Bootloader（3個(gè)常用）

1、什么是bootloader Bootloader，為引導(dǎo)加載程序，是嵌入式系統(tǒng)加電后運(yùn)行的第一段代碼，相當(dāng)于PC機(jī)的BIOS。

Bootloader的位置：通常固化在硬件上的某個(gè)固態(tài)存儲(chǔ)設(shè)備上，加電后自啟動(dòng)。Bootloader功能：初始化硬件設(shè)備、建立內(nèi)存空間的映射圖（有的CPU沒(méi)有內(nèi)存映射功能如 S3C44B0x），將系統(tǒng)的軟、硬件環(huán)境帶到一個(gè)合適的狀態(tài)，以便為最終調(diào)用操作系統(tǒng)內(nèi)核或用戶應(yīng)用程序準(zhǔn)備好正確的環(huán)境。

Bootloader的地址：在嵌入式系統(tǒng)中，系統(tǒng)加電復(fù)位后，幾乎所有的 CPU都從由復(fù)位地址上取指令。

2、Bootloader操作模式

兩種不同的操作模式：“啟動(dòng)加載”模式和“下載”模式。其區(qū)別對(duì)于開發(fā)人員才有意義。從最終用戶的角度看，Bootloader的作用就是用來(lái)加載操作系統(tǒng)，而并不存在所謂的啟動(dòng)加載模式與下載模式的區(qū)別。啟動(dòng)加載（Bootloading）模式

啟動(dòng)加載模式稱為“自舉”（Autonomous）模式。即Bootloader從目標(biāo)機(jī)上的某個(gè)固態(tài)存儲(chǔ)設(shè)備上將操作系統(tǒng)加載到 RAM 中運(yùn)行，整個(gè)過(guò)程并沒(méi)有用戶的介入。

啟動(dòng)加載模式是 Bootloader的正常工作模式，在嵌入式產(chǎn)品發(fā)布的時(shí)侯，Bootloader必須工作在這種模式下。

下載（Downloading）模式

下載方式：在這種模式下，目標(biāo)機(jī)上的Bootloader將通過(guò)串口連接或網(wǎng)絡(luò)連接等通信手段從主機(jī)下載文件。

下載內(nèi)容及存儲(chǔ)：主要是下載內(nèi)核映像和根文件系統(tǒng)映像等。從主機(jī)下載的文件通常首先被Bootloader保存到目標(biāo)機(jī)的RAM中，然后再被 Bootloader寫到目標(biāo)機(jī)上的FLASH 類固態(tài)存儲(chǔ)設(shè)備中。

下載模式應(yīng)用場(chǎng)合：Bootloader的這種模式通常在第一次安裝內(nèi)核與根文件系統(tǒng)時(shí)被使用；此外，以后的系統(tǒng)更新也會(huì)使用到這種工作模式。

用戶應(yīng)用接口：工作于這種模式下的Bootloader通常都會(huì)向它的終端用戶提供一個(gè)簡(jiǎn)單的命令行接口。如在RedBoot下，將出現(xiàn)“RedBoot>”提示符；在vivi Bootloader 下出現(xiàn)“vivi>”提示符。

3、Bootloader啟動(dòng)過(guò)程

Bootloader的啟動(dòng)可以分為兩個(gè)階段

1、第一階段

階段1主要包含依賴于CPU體系結(jié)構(gòu)及硬件設(shè)備的初始化等。通常都用匯編語(yǔ)言來(lái)實(shí)現(xiàn)。這個(gè)階段的任務(wù)有5：

(1)、基本的硬件設(shè)備初始化

這是 Bootloader 一開始就執(zhí)行的操作，其目的是為階段2 的執(zhí)行、以及隨后kernel 的執(zhí)行準(zhǔn)備好一些基本的硬件環(huán)境。

它通常包括以下工作：

關(guān)閉處理器內(nèi)部指令/數(shù)據(jù)cache等

關(guān)閉中斷

關(guān)閉看門狗

配置PLL 配置內(nèi)存

初始化各工作模式的堆棧

配置中斷

拷貝RW段，初始化ZI段

(2)、為階段2代碼準(zhǔn)備RAM空間

為了獲得更快的執(zhí)行速度，通常把 階段2 的代碼加載到 RAM 空間中來(lái)執(zhí)行。

準(zhǔn)備RAM空間考慮的因素：階段2代碼大小、堆棧、頁(yè)大?。?KB的倍數(shù)）、安排位置等。

(3)、拷貝階段2代碼到RAM空間

(4)、設(shè)置好堆棧

堆棧指針sp設(shè)置在1MB 的 RAM 空間的最頂端(堆棧向下生長(zhǎng))。

(5)、跳轉(zhuǎn)到階段2的C程序入口點(diǎn)

在上述一切都就緒后，就可以跳轉(zhuǎn)到 Bootloader 的 stage2 去執(zhí)行了。

2、第二階段

階段2通常用C語(yǔ)言來(lái)實(shí)現(xiàn)，以便實(shí)現(xiàn)更復(fù)雜的功能，也使程序有更好的可讀性和可移植性。這個(gè)階段的主要任務(wù)有5：

(1)、初始化本階段要使用到的硬件

至少初始化一個(gè)串口，以便和終端用戶進(jìn)行 I/O 輸出信息等。

(2)、檢測(cè)系統(tǒng)內(nèi)存映射(memory map)

所謂內(nèi)存映射，就是指在整個(gè)物理地址空間中有哪些地址范圍被分配用來(lái)作為系統(tǒng)的 RAM 單元。為后面使用RAM、運(yùn)行程序做好準(zhǔn)備。

(3)、將kernel和根文件系統(tǒng)映像從flash讀到RAM空間

(4)、為kernel設(shè)置啟動(dòng)參數(shù)

這是在調(diào)用內(nèi)核之前應(yīng)該做的準(zhǔn)備工作。Linux 2.4.x 以后的內(nèi)核都期望以標(biāo)記列表(tagged list)的形式來(lái)傳遞啟動(dòng)參數(shù)。

啟動(dòng)參數(shù)標(biāo)記列表方法：以ATAG_CORE標(biāo)記開始，以ATAG_NONE標(biāo)記結(jié)束。

在嵌入式 Linux 系統(tǒng)中，通常需要由 Boot Loader 設(shè)置的啟動(dòng)參數(shù)有：ATAG_CORE、ATAG_MEM（內(nèi)存映射）、ATAG_NONE等。

(5)、調(diào)用內(nèi)核

Bootloader調(diào)用Linux kernel的方法是直接跳轉(zhuǎn)到內(nèi)核的第一條指令處。在跳轉(zhuǎn)時(shí)必須滿足下列條件：

1)、CPU寄存器的設(shè)置：R0為0；R1為機(jī)器類型ID；R2為啟動(dòng)參數(shù)，標(biāo)記列表在RAM中的起始基地址。(機(jī)器類型參見(jiàn) linux/arch/arm/tools/mach-types目錄)2)、CPU模式： CPU必須設(shè)置為SVC模式，必須禁止中斷(IRQs和FIQs)。

3)、MMU 和 Cache的設(shè)置：MMU 必須關(guān)閉；指令 Cache 可以打開也可以關(guān)閉； 數(shù)據(jù) Cache 必須關(guān)閉。

4、有哪些常用的Bootloader Bootloader是嚴(yán)重地依賴于硬件而實(shí)現(xiàn)的。每種不同體系結(jié)構(gòu)的處理器都有不同的Bootloader。

1、vivi vivi是韓國(guó)Mizi公司開發(fā)的Bootloader，適用于ARM9處理器。

2、RedBoot

RedBoot即紅帽(Red Hat)嵌入式調(diào)試引導(dǎo)程序，是一種用于嵌入式系統(tǒng)的獨(dú)立開放源代碼引導(dǎo)/裝載器。

3、U-Boot

U-Boot（Universal Bootloader）由德國(guó)DENX小組開發(fā)，是一款目前功能較為強(qiáng)大的開源Bootloader程序，它支持多種處理器平臺(tái)，包括ARM、PowerPC、MIPS等。

四、嵌入式微處理器

1、嵌入式系統(tǒng)硬件基礎(chǔ)知識(shí)（體系結(jié)構(gòu)，指令集）1）馮·諾依曼體系結(jié)構(gòu)和哈佛體系結(jié)構(gòu) 馮·諾依曼體系結(jié)構(gòu)

地址存儲(chǔ)器CPU數(shù)據(jù)PC

數(shù)據(jù)和指令都存儲(chǔ)在一個(gè)存儲(chǔ)器中的計(jì)算機(jī)被稱為馮·諾依曼機(jī) 指令的執(zhí)行周期T 1）取指令（Instruction Fetch)：TF 2）指令譯碼（Instruction Decode）：TD 3）執(zhí)行指令（Instruction Execute）：TE 4）存儲(chǔ)（Storage）：TS 每條指令的執(zhí)行周期：T= TF+TD+TE+TS 馮·諾依曼體系結(jié)構(gòu)特點(diǎn)：

1）數(shù)據(jù)與指令都存儲(chǔ)在存儲(chǔ)器中 2）被大多數(shù)計(jì)算機(jī)所采用

3）馮諾依曼體系: 英特爾公司的8086，英特爾公司的其他中央處理器、ARM的ARM7、MIPS公司的MIPS處理器。哈佛體系結(jié)構(gòu)

地址數(shù)據(jù)存儲(chǔ)器數(shù)據(jù)地址程序存儲(chǔ)器數(shù)據(jù) CPUPC

數(shù)據(jù)和指令存儲(chǔ)在各自獨(dú)立的存儲(chǔ)器中的計(jì)算機(jī)體系結(jié)構(gòu)稱為哈佛體系結(jié)構(gòu) 哈佛體系結(jié)構(gòu)特點(diǎn)：

1）程序存儲(chǔ)器與數(shù)據(jù)存儲(chǔ)器分開 2）提供了較大的數(shù)據(jù)存儲(chǔ)器帶寬 3）適合于數(shù)字信號(hào)處理

4）大多數(shù)DSP都是哈佛結(jié)構(gòu)

5）Microchip公司的PIC16芯片、摩托羅拉公司的MC68系列、Zilog公司的Z8系列、ATMEL公司的AVR系列和ARM公司的ARM9、ARM10和ARM11。

很難在哈佛機(jī)上編寫出一個(gè)自修改程序（寫入數(shù)據(jù)值然后使用這些值作為指令的程序

2）CISC與RISC CISC：復(fù)雜指令集（Complex Instruction Set Computer）8/2原則：80%的程序只使用20%的指令 具有大量變長(zhǎng)形式的不同指令

大多數(shù)程序只使用少量的指令就能夠運(yùn)行。PUSH AX MOV AL,80H MOV AX,1090H RISC：精簡(jiǎn)指令集（Reduced Instruction Set Computer)RISC是在開發(fā)高性能微處理器過(guò)程中的一個(gè)進(jìn)步 在通道中只包含最有用的指令（少而簡(jiǎn)單）確保數(shù)據(jù)通道快速執(zhí)行每一條指令 使CPU硬件結(jié)構(gòu)設(shè)計(jì)變得更為簡(jiǎn)單

指令格式和長(zhǎng)度固定，且指令類型很少、指令功能簡(jiǎn)單、尋址方式少而簡(jiǎn)單，指令譯碼控制器采用硬布線邏輯，這樣易于流水線的實(shí)現(xiàn)，進(jìn)而獲得高性能；

由于RISC指令系統(tǒng)強(qiáng)調(diào)了對(duì)稱、均勻、簡(jiǎn)單，使得程序的優(yōu)化編譯效率更高； 大多數(shù)指令單周期完成；

分開的load-store結(jié)構(gòu)的存取指令，也只有l(wèi)oad-store結(jié)構(gòu)的存取指令訪問(wèn)存儲(chǔ)器，而數(shù)據(jù)處理指令只訪問(wèn)寄存器。而CISC處理器一般允許將存儲(chǔ)器中的數(shù)據(jù)作為數(shù)據(jù)處理指令的操作數(shù)；

3）流水線、超標(biāo)量

4）緩存

如何減少CPU與內(nèi)存之間的速度差異？（4種）

1、為什么采用高速緩存

微處理器的時(shí)鐘頻率比內(nèi)存速度提高快得多，高速緩存可以提高內(nèi)存的平均性能。

2、高速緩存的工作原理

高速緩存是一種小型、快速的存儲(chǔ)器，它保存部分主存內(nèi)容的拷貝。

5）總線和總線橋

ARM微控制器使用的是AMBA總線體系結(jié)構(gòu)

AMBA（Advanced Microcontroller Bus Architecture）是ARM公司公布的總線標(biāo)準(zhǔn)，先進(jìn)的AMBA規(guī)范定義了三種總線：

AHB總線（Advanced High-performance Bus）：用于連接高性能系統(tǒng)模塊。它支持突發(fā)數(shù)據(jù)傳輸方式及單個(gè)數(shù)據(jù)傳輸方式，所有時(shí)序 參考同一個(gè)時(shí)鐘沿。

ASB總線（Advanced System Bus）：用于連接高性能系統(tǒng)模塊，它支持突發(fā)數(shù)據(jù)傳輸模式。

APB總線（Advance Peripheral Bus）：是一個(gè)簡(jiǎn)單接口支持低性能的外圍接口。

2、ARM編程模型（2工作狀態(tài)，7種模式，重點(diǎn)）

ARM處理器的幾大特點(diǎn)如下：

小體積、低功耗、成本低、高性能；

支持Thumb（16位）/ARM（32位）雙指令集，能很好的兼容8位/16位器件； 大量使用寄存器，大多數(shù)數(shù)據(jù)操作都在寄存器中完成，指令執(zhí)行速度更快； 尋址方式靈活簡(jiǎn)單，執(zhí)行效率高； 指令長(zhǎng)度固定；

全球眾多的合作伙伴。

當(dāng)前ARM體系結(jié)構(gòu)的擴(kuò)充包括：

Thumb:16位指令集，用以改善代碼密度；

DSP：用于DSP應(yīng)用的算術(shù)運(yùn)算指令集；

Jazeller：允許直接執(zhí)行Java代碼的擴(kuò)充。

ARM7TDMI 處理器有兩種工作狀態(tài):******************* ARM-32-bit, 按字排列的ARM指令集

Thumb-16-bit, 按半字排列的Thumb指令集

測(cè)試編譯器屬哪種模式

下面這段代碼可以用來(lái)測(cè)試一下你的編譯器是大端模式還是小端模式：

short int x;

char x0,x1;

x=0x1122;

x0=((char*)&x)[0];//低地址單元

x1=((char*)&x)[1];//高地址單元

若x0=0x11,則是大端;若x0=0x22,則是小端......上面的程序還可以看出，數(shù)據(jù)尋址時(shí)，用的是低位字節(jié)的地址。

3、ARM 指令集中常用指令（尋址方式、數(shù)據(jù)處理指令、加載/存儲(chǔ)指令等）*

4、匯編語(yǔ)言與C/C++的混合編程（3種編程方式，APCS，ATPCS）

APCS（ARM Produce Call Standard）是ARM程序中子程序調(diào)用的基本規(guī)則，目的是為了使單獨(dú)編譯的C語(yǔ)言程序和匯編程序之間能夠相互調(diào)用。這些基本規(guī)則包括子程序調(diào)用過(guò)程中寄存器的使用規(guī)則、數(shù)據(jù)棧的使用規(guī)則和參數(shù)的傳遞規(guī)則。

匯編語(yǔ)言與C/C++的混合編程通常有以下幾種方式：

－ 在C/C＋＋代碼中嵌入?yún)R編指令。

－ 在匯編程序和C/C＋＋的程序之間進(jìn)行變量的互訪。

－ 匯編程序、C/C＋＋程序間的相互調(diào)用。

在以上的幾種混合編程技術(shù)中，必須遵守一定的調(diào)用規(guī)則，如物理寄存器的使用、參數(shù)的傳遞等。

一般情況：

程序的初始化部分用匯編語(yǔ)言完成，然后用C/C＋＋完成主要的編程任務(wù)，匯編程序和C/C＋＋程序之間一般沒(méi)有參數(shù)的傳遞，也沒(méi)有頻繁的 相互調(diào)用，因此，整個(gè)程序的結(jié)構(gòu)顯得相對(duì)簡(jiǎn)單，容易理解。

5、嵌入式程序設(shè)計(jì)技巧（時(shí)間換空間，8個(gè)例子）變量定義 參數(shù)傳遞 循環(huán)條件 以空間換時(shí)間 數(shù)學(xué)方法解決問(wèn)題 使用位操作 嵌入?yún)R編

五、硬件系統(tǒng)結(jié)構(gòu)

1、S3C2410存儲(chǔ)系統(tǒng)組織（8個(gè)端口，確定寬度）S3C2410X有117個(gè)輸入/輸出端口。這些端口是：

A口（GPA）：23個(gè)輸出口

B口（GPB）：11個(gè)輸入/輸出口

C口（GPC）：16個(gè)輸入/輸出口 D口（GPD）：16個(gè)輸入/輸出口 E口（GPE）：16個(gè)輸入/輸出口 F口（GPF）：8個(gè)輸入/輸出口 G口（GPG）：16個(gè)輸入/輸出口 H口（GPH）：11個(gè)輸入/輸出口

2、S3C2410的外設(shè)管理

3、I/O口的組織及一般應(yīng)用（引腳）、4、UART

S3C2410 的UART（通用異步串行口）有三個(gè)獨(dú)立的異步串行I/O 端口：UART0、UART1、UART2，每個(gè)串口都可以在中斷和DMA 兩種模式下進(jìn)行收發(fā)。UART支持的最高波特率達(dá)230.4kbps。

每個(gè)UART 包含：波特率發(fā)生器、接收器、發(fā)送器和控制單元。波特率發(fā)生器以PCLK或UCLK為時(shí)鐘源。發(fā)送器和接收器各包含1個(gè)16 字節(jié)的FIFO 寄存器和移位寄存器。

S3C2410 的3個(gè)UART都有遵從1.0規(guī)范的紅外傳輸功能，UART0、UART1有完整的握手信號(hào)，可以連接MODEM。

當(dāng)發(fā)送數(shù)據(jù)的時(shí)候，數(shù)據(jù)先寫到FIFO 然后拷貝到發(fā)送移位寄存器，然后從數(shù)據(jù)輸出端口（TxDn）依次被移位輸出。被接收的數(shù)據(jù)也同樣從接收端口（RxDn）移位輸入到移位寄存器，然后拷貝到FIFO 中。

編寫一程序，使用S3C2410X的UART2進(jìn)行串行數(shù)據(jù)收發(fā)，要求用脈沖請(qǐng)求中斷的方式、使用收/發(fā)FIFO，8個(gè)數(shù)據(jù)位、1個(gè)停止位、不校驗(yàn)，波特率為125kb/s。設(shè)Pclk為50MHz。（提示：主程序?qū)ART2初始化、引腳配置、中斷初始化等，并進(jìn)行一次發(fā)送；中斷服務(wù)程序進(jìn)行數(shù)據(jù)收發(fā)，標(biāo)簽清除中斷請(qǐng)求標(biāo)志和中斷服務(wù)標(biāo)志）

解：

（1）計(jì)算波特率除數(shù)：

由公式：

UBRDIVn=(int)（CLK/（f B*16））－ 1

這里： Pclk=50MHz，f B = 125kb/s 計(jì)算得：

UBRDIVn=25-1=24

（2）UART2控制寄存器：

線路控制寄存器： ULCON2=0 0 000 0 11=0x03 含義：非紅外、不校驗(yàn)、1個(gè)停止位、8個(gè)數(shù)據(jù)位 控制寄存器：

UCON2=0b 0 0 0 0 0 0 0 01 01=0x05 含義：選Pclk、發(fā)/收中斷脈沖請(qǐng)求、關(guān)閉接收超時(shí)中斷、允許接收錯(cuò)誤中斷、不回送、不發(fā)送暫停信號(hào)、發(fā)/收用中斷方式。

FIFO控制寄存器：UFCON2=0b 10 01 0 0 0 1=0x91 含義：發(fā)/收FIFO選8字節(jié)觸發(fā)、保留位為0、不復(fù)位發(fā)/收FIFO、使能FIFO。

（3）引腳配置

需要設(shè)置TxD2、RxD2，它們對(duì)應(yīng)GPH6、GPH7，在GPH配置寄存器GPHCON中的位置為：

0b 1 0 0

＊＊

＊＊

＊＊

＊＊

＊＊

＊＊ 方法：GPHCON= GPHCON&~(0xF<<12)|(0xA<<12)

（4）中斷寄存器設(shè)置

中斷模式寄存器：INTMOD&=~(1<<15)INT_UART2位于第15位，將UART2設(shè)置為IRQ中斷

中斷屏蔽寄存器：INTMSK&=~(1<<15)

中斷優(yōu)先級(jí)寄存器PRIORITY：

不設(shè)置，使用固定優(yōu)先級(jí)。

子中斷屏蔽寄存器：INTSUBMSK&=~(7<<6)

INT_ERR2、INT_TXD2、INT_RXD2位于子中斷屏蔽寄存器中的8、7、6位。

（5）在中斷服務(wù)程序中對(duì)寄存器的操作

清除中斷標(biāo)志寄存器相應(yīng)位：

SRCPND&=~(1<<15)

清除中斷服務(wù)寄存器相應(yīng)位：

INTPND&=~(1<<15)

5、時(shí)鐘和功耗管理（解決方案 簡(jiǎn)述2410的功耗解決方案）時(shí)鐘功能

有兩個(gè)鎖相環(huán)MPLL、UPLL(Phase-Locked Loop)產(chǎn)生系統(tǒng)所需要的不同頻率的時(shí)鐘。

（1）為CPU產(chǎn)生FCLK時(shí)鐘（2）為AHB產(chǎn)生HCLK時(shí)鐘 使用HCLK的設(shè)備：中斷控制器、存儲(chǔ)器管理器、DMA控制器、LCD控制器、FLASH控制器、USB Host（不用PLL時(shí)）、總線控制器、片外設(shè)備。

（3）為APB產(chǎn)生PCLK時(shí)鐘

使用PCLK的設(shè)備： 117個(gè)通用I/O口GPIO、ADC、5個(gè)定時(shí)器與4個(gè)PWM、3個(gè)UART、2個(gè)SPI、IIC、USB Device（不用PLL時(shí)）、RTC、WDT、SD卡接口、IIS接口

（4）為USB（Host and Device）產(chǎn)生UCLK時(shí)鐘（48MHz）

2、電源管理功能

具有4種電源管理模式：正常模式、慢時(shí)鐘模式、空閑模式、掉電模式。

（1）正常模式：

1）鎖相環(huán)工作；2）為CPU和所 有片內(nèi)外設(shè)提供時(shí)鐘。

此模式系統(tǒng)功耗最大。（2）慢時(shí)鐘模式：

鎖相環(huán)不工作，CPU等直接使用原始時(shí)鐘、或原始時(shí)鐘的分頻工作。

此模式工作時(shí)鐘頻率低而使功耗低，并且鎖相環(huán)不工作也使功耗降低。（3）空閑模式：

停止為CPU提供時(shí)鐘，CPU不工作（其外設(shè)均工作）。

退出方法：任何中斷請(qǐng)求可喚醒CPU工作，退出空閑模式。（4）斷電模式：

時(shí)鐘模塊斷電，除了喚醒電路之外所有部分均不供電。系統(tǒng)需分成兩部分供電。此模式功耗最低。必須設(shè)置有外中斷

退出方法：用中斷喚醒。（1）外部中斷EINT0---15；（2）實(shí)時(shí)鐘報(bào)警中斷。

如何降低2410的功耗

在能夠滿足功能正常的前提下，盡可能選擇低電壓工作的CPU能夠在總體功耗方面得到較好的效果。對(duì)于已經(jīng)選定的CPU來(lái)講，降低供電電壓和工作頻率，也是一條節(jié)省功率的可行之路。CPU采用內(nèi)置Flash的方式

如果可以通過(guò)選取合適的前后級(jí)芯片來(lái)避免Buffer的使用，對(duì)于能量來(lái)講是一個(gè)很大的節(jié)約。

我們可以通過(guò)控制CPU進(jìn)入不同的模式來(lái)達(dá)到省電的目的 關(guān)閉不需要的外設(shè)控制器

在適當(dāng)?shù)那闆r下使用DC-DC的電壓轉(zhuǎn)換線路，可以有效地節(jié)約能量

6、程序?qū)嵗?/p>

六、實(shí)時(shí)操作系統(tǒng)

1、實(shí)時(shí)操作系統(tǒng)概念（可重入，任務(wù)集翻轉(zhuǎn)）RTOS的基本特征： 高效的任務(wù)管理

1.支持多任務(wù)

2.優(yōu)先級(jí)管理

3.任務(wù)調(diào)度：基于優(yōu)先級(jí)的搶占式調(diào)度、時(shí)間片輪轉(zhuǎn)調(diào)度的算法

4.支持快速而確定的上下文切換 快速靈活的任務(wù)間通信

1.信號(hào)量：二進(jìn)制、互斥、計(jì)數(shù)器

2.通信機(jī)制：消息隊(duì)列、管道等 高度的可剪裁性

動(dòng)態(tài)鏈接與部件增量加載

快速有效的中斷和異常事件處理 優(yōu)化的浮點(diǎn)支持 動(dòng)態(tài)內(nèi)存管理 可重入型函數(shù)

可以被一個(gè)以上的任務(wù)調(diào)用，而不必?fù)?dān)心數(shù)據(jù)的破壞?？芍厝胄秃瘮?shù)任何時(shí)候都可以被中斷，一段時(shí)間以后又可以運(yùn)行，而相應(yīng)數(shù)據(jù)不會(huì)丟失。可重入型函數(shù)或者只使用局部變量，即變量保存在CPU寄存器中或堆棧中,或?qū)θ肿兞坑枰员Ｗo(hù)。

一個(gè)不可重入型函數(shù)的例子 int Temp;Void swap(int *x,int*y){ Temp=*x;*X=*Y;*y=Temp;} 使用以下技術(shù)之一即可使Swap()函數(shù)具有可重入性: l 把Temp定義為局部變量

l 調(diào)用Swap()函數(shù)之前關(guān)中斷，調(diào)用后再開中斷 l 用信號(hào)量禁止該函數(shù)在使用過(guò)程中被再次調(diào)用

一個(gè)可重入型函數(shù)的例子 Void swap(int *x,int*y){ int Temp;Temp=*x;*X=*Y;*y=Temp;} 優(yōu)先級(jí)反轉(zhuǎn)

多任務(wù)內(nèi)核應(yīng)允許動(dòng)態(tài)改變?nèi)蝿?wù)的優(yōu)先級(jí)以避免發(fā)生優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象。為防止發(fā)生優(yōu)先級(jí)反轉(zhuǎn),內(nèi)核能自動(dòng)變換任務(wù)的優(yōu)先級(jí),這叫做優(yōu)先級(jí)繼承(Priority inheritance)但μC/OS-Ⅱ不支持優(yōu)先級(jí)繼承,一些商業(yè)內(nèi)核有優(yōu)先級(jí)繼承功能/

2、系統(tǒng)時(shí)鐘和定時(shí)器

C/OS的性能特點(diǎn)（列舉性能特點(diǎn)）可移植性（Portable）

C/OS-II的源碼是用移植性很強(qiáng)的ANSI C寫的。

和微處理器硬件相關(guān)的那部分是用匯編語(yǔ)言寫的。匯編語(yǔ)言寫的部分已經(jīng)

C/OS-II便于移植到其他微處理器上。

匯編語(yǔ)言寫的部分只有200行左右。

C/OS-II可以在絕大多數(shù)8位、16位、32位以至64位微處理器、微控制器、數(shù)字信號(hào)處理器（DSP）上運(yùn)行。移植范例的源代碼可以從因特網(wǎng)上下載。

可裁剪（Scalable）

C/OS-II中應(yīng)用程序需要的那些系統(tǒng)服務(wù)。也就是說(shuō)某產(chǎn)品可 C/OS-II C/OS-II

C/OS-II所需的存儲(chǔ)器空間（RAM和ROM）。這種可剪裁性是靠條件編譯實(shí)現(xiàn)的。多任務(wù)

C/OS-II可以管理64個(gè)任務(wù)，然而，目前這一版本保留8個(gè)給系統(tǒng)。應(yīng)用程序最多可以有56個(gè)任務(wù) 占先式（Preemptive）可確定性

C/OS-II的函數(shù)調(diào)用與服務(wù)的執(zhí)行時(shí)間具有可確定性。任務(wù)棧

每個(gè)任務(wù)有自己?jiǎn)为?dú)的棧，C/OS-II允許每個(gè)任務(wù)有不同的棧空間，以便壓低應(yīng)用程序?qū)AM的需求。系統(tǒng)服務(wù)

C/OS-II提供很多系統(tǒng)服務(wù)，例如郵箱、消息隊(duì)列、信號(hào)量、塊大小固定的內(nèi)存的申請(qǐng)與釋放、時(shí)間相關(guān)函數(shù)等。中斷管理

中斷可以使正在執(zhí)行的任務(wù)暫時(shí)掛起，如果優(yōu)先級(jí)更高的任務(wù)被該中斷喚醒，則高優(yōu)先級(jí)的任務(wù)在中斷嵌套全部退出后立即執(zhí)行，中斷嵌套層數(shù)可達(dá)255層。

可固化（ROMable）

C/OS-II是為嵌入式應(yīng)用而設(shè)計(jì)的，這就意味著，只要讀者有固化手段（C編譯、連接、下載和固化），C/OS-II可以嵌入到讀者的產(chǎn)品中成為產(chǎn)品的一部分。

穩(wěn)定性與可靠性

3、C/OS-Ⅱ內(nèi)核(任務(wù)、任務(wù)狀態(tài)、任務(wù)控制塊、就緒表、調(diào)度、任務(wù)切換、中斷等）

C/OS-Ⅱ移植(開關(guān)中斷、類型定義、堆棧初始化、任務(wù)切換等））