2016年11月15日 星期二

(IES101)SEC4_嵌入式系統(即時)的作業應用設計(解題說明).docx

IES101 嵌入式系統基本軟體技術

(4)嵌入式系統(即時)的作業應用設計(解題說明)
-----------------------------------------------------------------------------------------------------------------
4-01 ----------------------------------------------------------------------------------------------------------
概念題
核心映像Kernel image


-----------------------------------------------------------------------------------------------------------------
4-02 ----------------------------------------------------------------------------------------------------------

啟動程式Bootloader

啟動程式(Boot loader)於電腦應用上是指引導作業系統啟動的程式。在普通PC上，引導程式通常分為兩部分：第一階段引導程式位於主開機紀錄，用於引導位於某個分割上的第二階段引導程式，如NTLDR、GNU GRUB等。
BIOS 開機完成後，Bootloader 就接手初始化硬體設備、建立記憶體空間的對映，以便為作業系統內核準備好正確的軟硬體環境。
-----------------------------------------------------------------------------------------------------------------
4-03 ----------------------------------------------------------------------------------------------------------
計概觀念題
-----------------------------------------------------------------------------------------------------------------
4-04 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
4-05----------------------------------------------------------------------------------------------------------

Windows CE 5.0 提供了強大的即時作業系統，並提供裝置驅動程式和OEM 配接層(OEM Adaptation Layer，OAL) 基礎結構，可以幫助研發人員快速開發具備網路、即時性、多媒體與Web 瀏覽等功能的下一代行動通訊與輕巧設備，包括PDA、工業自動化設備、醫療裝置、家用閘道器和消費性電子產品等。
以前硬體設計人員會建立低階常式集，稱為 OEM 配接層 (OAL)，而且該元件與作業系統核心是靜態連結在一起。OAL 和核心看起來是一個可執行檔 nk.exe。在 CE 6.0 中，這兩個元件現在建置成兩個不同模組：核心 (kernel.dll) 和 OEM 配接層 (nk.exe)。

Windows CE 作業系統的 BSP 包含有：
  1. bootloader
  2. 驅動
  3. OEM Adaptation Layer（OAL）
  4. 配置檔案

BSP開發板支援套裝軟體

在嵌入式系統中，Board Support Package（簡稱BSP，中譯開發板支援套裝軟體）是實作特定的支援程式碼讓所給的板來符合所給的作業系統，通常會與 bootloader 一起建置，bootloader包含最小的裝置驅動來載入作業系統與所有在板上的裝置的驅動程式。
一些供應商也提供一個根檔案系統，使用toolchain讓程式可以在嵌入式系統上執行（toolchain可能是架構支援套件的其中一部分）與裝置配置器。

-----------------------------------------------------------------------------------------------------------------
4-06 ----------------------------------------------------------------------------------------------------------

POST(Power-on self-test)加電自檢

加電自檢又稱為開機自我檢測（英文Power-on self-test，常用簡稱POST），是計算機BIOS的一個功能，在開機後會執行，針對計算機硬體如CPU、主機板、記憶體等進行檢測，結果會顯示在韌體可以控制的輸出介面，像螢幕、LED、印表機等等裝置上。
測試流程:
  1. 開機系統重置REST 啟動CPU。
  2. CPU指向BIOS自我測試的位址FFFFOH並打開CPU執行第一個指令。
  3. CPU內部暫存器的測試。
  4. CMOS 146818 SRAM檢查。
  5. ROM BIOS 檢查碼測試。
  6. 8254計時/計數器測試。
  7. 8237 DMA控制器測試。
  8. 74612頁暫存器測試。
  9. REFRESH重新整理電路測試。
  10. 8042鍵盤控制器測試。
  11. DRAM 64KB基本記憶體測試。
  12. CPU保護模式的測試。
  13. 8259中斷控制器的測試。
  14. CMOS 146818電力及檢查碼檢查。
  15. DRAM IMB以上記憶體檢查。
  16. 顯示卡測試。
  17. NMI強制中斷測試。
  18. 8254計時/計數器聲音電路測試。
  19. 8254計時/計數器計時測試。
  20. CPU保護模式SHUT DOWN測試。
  21. CPU回至真實模式 (REAL MODE)。
  22. 鍵盤滑鼠測試。
  23. 8042鍵盤控制器測試。
  24. 8259中斷控制器IRQ0至IRQ18建立。
  25. 磁碟機及介面測試。
  26. 設定並列印表機及串列RS232的介面。
  27. 檢查CMOS IC時間、日期。
  28. 檢查完成

-----------------------------------------------------------------------------------------------------------------
4-07 ----------------------------------------------------------------------------------------------------------
  • 依照系統對時間限制所要求的程度可分為兩類：
    • 硬即時系統
    • 軟即時系統
  • 硬即時系統須保證關鍵工作在一定的時間內能夠完，否則對系統會有負面的影響。
  • 軟即時系統對時間的要求就沒有那麼嚴苛，萬一工作沒有在一定的時間內完成，它還是有部份價值
  • 即時系統Real-time system: 即時系統就是對於較重要的事件，必須能在一定的時間限制內作出適當反應的系統。
  • 　　第一種是硬性即時系統(Hard Real-Time)，它可以保證重要的工作準時完成。
  • 　　第二種限制較少的「軟性即時系統(Soft Real-Time)」，在這種系統中，重要的即時任務有比其它任務更高的優先權，並且一直保有此優先權直到完成為止，
  • 所謂硬即時性能，是指系統從命令起始到執行動作之間的中斷延遲(Interrupt latency)回應特性。一般像是Win CE這種的軟即時作業系統，其反應時間約為1~2微秒，要達到硬即時性能的要求，其反應時間必須要在150μs以內。
  • 他解釋說，傳統的即時作業系統(RTOS)像是VxWorks、Nuclues都是硬即時系統，但它們都是專用且封閉的商用即時作業系統。而Linux一直以來都只能提供軟即時性能，也因此，雖然Linux在嵌入式市場中的接受度日益提升，但在汽車控制、工業控制、電信基礎建設等諸多需要硬即時性能的應用中，都無法採用Linux。

-----------------------------------------------------------------------------------------------------------------
4-08 ----------------------------------------------------------------------------------------------------------
(A)?V語意不明確:演算法的計算時間複雜度較高，演算法本身較簡單—也就是編碼coding 較容易
(B)V
(C)V
(D)X最慢的排序演算法，但程式簡單
-----------------------------------------------------------------------------------------------------------------
4-09 ----------------------------------------------------------------------------------------------------------
一個現代編譯器的主要工作流程如下： 原始碼 (source code) → 預處理器 (preprocessor) → 編譯器 (compiler) → 組譯程式 (assembler) → 目的碼 (object code) → 連結器 (Linker) → 執行檔 (executables)

-----------------------------------------------------------------------------------------------------------------
4-10 ----------------------------------------------------------------------------------------------------------
Ref. 4-04
-----------------------------------------------------------------------------------------------------------------
4-11 ----------------------------------------------------------------------------------------------------------
Ref. 4-07
Firm 穩固的; 牢固的; 結實的
-----------------------------------------------------------------------------------------------------------------
4-12 ----------------------------------------------------------------------------------------------------------
Ref. 4-07

-----------------------------------------------------------------------------------------------------------------
4-13 ----------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------
4-14 ----------------------------------------------------------------------------------------------------------
佇列（英文queue），是先進先出（FIFO, First-In-First-Out）的線性表。在具體應用中通常用鏈表或者數組來實現。隊列只允許在後端（稱為rear）進行插入操作，在前端（稱為front）進行刪除操作。
隊列的操作方式和堆疊類似，唯一的區別在於隊列只允許新數據在後端進行添加。

單鏈佇列

單鏈隊列使用鏈表作為基本數據結果，所以不存在偽溢出的問題，隊列長度也沒有限制。但插入和讀取的時間代價較高

循環佇列

循環隊列可以更簡單防止偽溢出的發生，但隊列大小是固定的。

陣列佇列

佇列是一種先進先出的資料結構，想像您在管子中放入球，最先放入的球在另一端會最先跑出來，在這邊介紹如何使用陣列來實作佇列。

解法

使用陣列來實作佇列，我們必須保留兩個旗標，假設front指向佇列的前端，rear向佇列的後端，我們每次從佇列後端加入一個資料，rear就加1指向最後一個資料，每次從佇列前端取出一個資料，front就加1指向佇列的最前端，如下圖所示：
Quene

這是最簡單的佇列實作，但是由於陣列的大小必須先決定，所以這種線性的結構有個問題，front與rear會到達陣列的後端，而這個陣列就不能再使用了，為了解決這個問題，將陣列當作環狀來使用，當front或rear到達陣列後端時，就重新從陣列前端再循環，也就是形成環狀佇列，如下圖所示：
Quene



不過陣列的容量還是受限制，所以這個陣列還是會滿的，當front = rear時，佇列就滿了；佇列的基本操作有五項：新增佇列、加入資料、顯示前端資料、取出前端資料、顯示所有的佇列元素。

-----------------------------------------------------------------------------------------------------------------
4-15 ----------------------------------------------------------------------------------------------------------
堆疊（英文：stack），也可直接稱棧。中國大陸作堆棧，在計算機科學中，是一種特殊的串列形式的資料結構，它的特殊之處在於只能允許在鏈結串列或陣列的一端（稱為堆疊頂端指標，英文為top）進行加入資料（push）和輸出資料（pop）的運算。另外堆疊也可以用一維陣列或連結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列。
由於堆疊資料結構只允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。
堆疊資料結構使用兩種基本操作：推入（push）和彈出（pop）：
  • 推入（push）
：將數據放入堆疊的頂端（陣列形式或串列形式），堆疊頂端top指標加一。
  • 彈出（pop）
：將頂端數據資料輸出（回傳），堆疊頂端資料減一。

堆疊的應用


二元樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二元樹常被用於實現二元搜尋樹和二叉堆。
二元樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二元樹的子樹有左右之分，次序不能顛倒。二元樹的第i層至多有2^{i-1}個結點；深度為k的二元樹至多有2^k-1個結點；對任何一棵二元樹T，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。
樹和二元樹的三個主要差別：
  1. 樹的結點個數至少為1，而二元樹的結點個數可以為0；
  2. 樹中結點的最大度數沒有限制，而二元樹結點的最大度數為2；
  3. 樹的結點無左、右之分，而二元樹的結點有左、右之分。
<完全二元樹和滿二元樹>
  1. 滿二元樹：一棵深度為k，且有（2的k次方）－1個節點成為滿二元樹
  2. 完全二元樹：深度為k，有n個節點的二元樹，若且唯若其每一個節點都與深度為k的滿二元樹中序號為1至n的節點對應時，稱之為完全二元樹

二元樹(Binary Tree)的類型

二元樹是一個有根樹，並且每個節點最多有2個子節點。非空的二元樹，若樹葉總數為 n0，分支度為2的總數為 n2，則 n0 = n2 + 1。
BinaryTree leaf.jpg
一棵深度為k，且有2^k-1個節點的二元樹，稱為滿二元樹（Full Binary Tree）。這種樹的特點是每一層上的節點數都是最大節點數。在一棵二元樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二元樹為完全二元樹（Complete Binary Tree）。具有n個節點的完全二元樹的深度為log_2n+1。深度為k的完全二元樹，至少有2^{k-1}個節點，至多有2^k-1個節點。
FullBT CompleteBT.jpg

訪問二元樹的方法

我們經常希望訪問樹中的每一個結點並且檢視它的值。有很多常見的順序來訪問所有的結點，而且每一種都有有用的性質。

[MMDays專欄] 由樹的前序、中序、後序走法來談資料結構

Jan 19th, 2008 by Mr. Thursday
Posted By Mr. Thursday
在以前的文章裡面有幾次有提到「演算法」(Algorithm)，可以把他想程式完成一件事情所需要的步驟，可能包含重覆某些步驟、依照條件執行部份步驟、或是從頭到尾執行固定的步驟。然而演算法通常需要資料結構的配合。不是主修計算機的讀者，也許不知道資料結構是甚麼東西，即使我說資料結構的英文是 Data Structure，可能還是沒辦法了解「資料結構」代表的意思。簡單地說，演算法是完成一件事情的步驟，那麼資料結構就是這些步驟作用的物品，譬如說刮鬍子，可能要先插插頭，準備鏡子，然後開始刮鬍子。但是如果沒有插座，沒有鏡子，沒有刮鬍刀，或是沒有鬍子，這些步驟就沒有東西可以作用了。因此演算法和資料結構，有一點點類似軟體和硬體的對應，只不過資料結構並不是完全屬於硬體的角色就是了。接下來我們就來看一下某些資料結構，尤其是樹 (tree) 的結構，以及不同的拜訪順序，產生的效果。
pre_order
上面就是一棵「樹」(tree)。所謂樹，就是由「點」(node)和「連結」(link)所組成，演算法可能就是依照不同順序來走訪這棵樹，或是根據某個規則新增樹的節點，減少樹的節點，以及這些步驟的時間複雜度等等。上面看到的還是比較特別的樹，因為每個節點只有兩個枝子 (branch)，所以是一個二元樹 (binary tree)。又因為我舉的例子，剛好三層裡面有7個節點，所以是一棵完全樹 (complete tree)。
下面就列出一棵樹的三種走法：前序、中序、以及後序。
tree_order1
圖片裡面的號碼，就代表拜訪的順序，這邊為了簡化說明，所以樹只有三個節點。最左邊是前序，也就是現在這個節點最先拜訪，自己先拜訪，在分別拜訪左手邊和右手邊的節點。中間那棵樹就是中序，也就是自己中間拜訪，先拜訪左邊，接著中間拜訪自己，最後才拜訪右手邊的節點。最右邊的那棵樹，號碼代表後序，也就是說自己最後拜訪，左手邊和右手邊的子節點都先拜訪，接著最後才拜訪自己。不知道各位讀者看到這邊是否了解三種順序的差別呢？
接下來我們要看比較多節點的樹，在這之前，我們先把上面那張圖抽象化一下：
tree_order2
上面這張圖的號碼順序，和前一張圖完全一樣，只是子節點從圓形變成了三角形。這是代表甚麼意思呢？原本在只有三個節點的樹裡面，上面那個節點，我們通常稱為「父節點」(parent node)，下面兩個節點，我們通常稱為「子節點」(child node)。如果子節點的位置，不只一個節點，而是用相同的方式，一直很多層節點長下去，就會變成一棵「子樹」(sub-tree)，而不是子節點了。這張圖的三角形，就代表是子樹 (sub-tree)的意思。
所以如果是不只三個節點的樹，拜訪的順序還是和只有三個節點的樹一樣，只不過我們遇到子樹的時候，就用遞迴 (recursive) 的概念來執行，也就是說，我們先把剛才執行到一半的東西存在腦海，然後重新來過，把我們新遇到的子節點，當成一個新的父節點來看，然後依照剛才只有三個節點的拜訪順序來判斷要先走哪一個節點。如果依照這個方法，第一張只有三個節點的圖，以及第二張用三角形代表子樹的圖，我們把子樹展開來，就會變成如下面三張圖所示，這是有7個節點的樹的前中後序的走法。
前序 (pre-order)
pre_order
中序(mid-order)
mid_order
後序(post-order)
post_order
所以到目前為止，我們提到了演算法和資料結構的關係，我們介紹了「樹」這個資料結構，我們介紹了三種拜訪樹節點的方法：前序中序後序。不過前序中序後序，和電腦的運算有甚麼樣子的關係呢？假設現在我們把節點，當成電腦裡面儲存運算元(operator)和運算子(operand)的地方，那麼下面這個四則運算的式子，就可以用一棵樹表示：
(1 + 2) * (3 + 4)
因為有先乘除，後加減的規則，所以上面的式子如果寫成
1 + 2 * 3 + 4
算出來是11，而不是正確答案21。接下來我們用二元樹來表達這個運算式(expression)
expression
我們如果用「中序」來拜訪這棵樹，就會得到下面這個算式
1 + 2 * 3 + 4
結果非常接近人類使用的運算式表示方法，但是少了一個地方，就是「括號」！這樣子會造成電腦運算的結果錯誤！因此在電腦裡面，如果不想多設計一個括號的電路，又想要把四則運算藉由走訪一棵樹來算出結果，通常無論是「前序」或是「後序」，都可以得到正確的答案，而不需要括號的協助。下面我們寫一下用前序拜訪所產生的運算式：
* + 1 2 + 3 4
後序拜訪產生的運算式
1 2 + 3 4 + *
都是不用括號，就可以得到答案的運算是表示方法。
關於前序中序後序的其他演算法和資料結構問題，有興趣的讀者可以進一步閱讀下面這本書：《C名題精選百則－使用 C語言－技巧篇》，冼鏡光著。


張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)