IES101 嵌入式系統基本軟體技術
(3)嵌入式作業系統(即時)概論(解題說明)
-----------------------------------------------------------------------------------------------------------------
3-01 ----------------------------------------------------------------------------------------------------------
觀念題
NOR /NAND Flash
當時ROM晶片主要用來儲存幾乎不需更新的程式碼，例如電腦的BIOS或機上盒(Set-top Box)的韌體。NOR Flash可以忍受一萬到一百萬次抹寫循環，它同時也是早期的可移除式快閃儲存媒體的基礎。CompactFlash本來便是以NOR Flash為基礎的，雖然它之後跳槽到成本較低的 NAND Flash。 東芝在1989年的國際固態電路學會(ISSCC)上發表了NAND Flash。NAND Flash具有較快的抹寫時間, 而且每個儲存單元的面積也較小，這讓NAND Flash相較於NOR Flash具有較高的儲存密度與較低的每位元成本。同時它的可抹除次數也高出NOR Flash十倍。然而NAND Flash 的I/O介面並沒有隨機存取外部定址匯流排，它必須以區塊性的方式進行讀取，NAND Flash典型的區塊大小是數百至數千位元。
因為多數微處理器與微控制器要求位元組等級的隨機存取，所以NAND Flash不適合取代那些用以裝載程式的ROM。從這樣的角度看來，NAND Flash比較像光碟、硬碟這類的次級儲存裝置。NAND Flash非常適合用於記憶卡之類的大量儲存裝置。第一款建立在NAND Flash基礎上的可移除式儲存媒體是SmartMedia，此後許多儲存媒體也跟著採用NAND Flash，包括MultiMediaCard、Secure Digital、Memory Stick與xD卡。
NOR Flash
從NOR Flash讀取資料的方式與從RAM讀取資料相近，只要提供資料的位址，資料匯流排就可以正確的繪出資料。基於以上原因，多數微處理器可以將NOR Flash當作原地執行(Execute in place, XIP)記憶體使用，這意味著儲存在NOR Flash上的程式不需複製到RAM就可以直接執行。由於NOR Flash沒有原生壞區管理，所以一旦儲存區塊發生毀損，軟體或驅動程式必須接手這個問題，否則可能會導致裝置發生異常。 在解鎖、抹除或寫入NOR Flash區塊時，特殊的指令會先寫入已繪測的記憶區的第一頁(Page)。接著快閃記憶晶片會提供可用的指令清單給實體驅動程式，而這些指令是由一般性快閃記憶體介面(Common Flash memory Interface, CFI)所界定的。 與用於隨機存取的ROM不同，NOR Flash也可以用在儲存裝置上；不過與NAND Flash相比，NOR Flash的寫入速度一般來說會慢很多。
NAND Flash
東芝在1989年發表了NAND Flash架構，這種記憶體的存取方式類似硬碟之類的區塊性儲存裝置，每個區塊構成幾個頁。一般來說這些頁的尺寸為512、2048或4096位元組。各個頁之間彼此會有幾個位元組的關聯性(一般而言是12~16位元組)，這些空間用於儲存偵錯與糾錯的校驗和。以下是一些典型的區塊大小與其內部包含的關連性尺寸：
- 每32個512位元組的頁包含1個16kB的關連性區塊
- 每64個2048位元組的頁包含1個128kB的關連性區塊
- 每64個4096位元組的頁包含1個256kB的關連性區塊
- 每128個4096位元組的頁包含1個512kB的關連性區塊
當寫入建立在這種「頁」的基礎上時，抹除便只能以區塊性的方法進行。NAND Flash還有一項限制就是區塊內的資料只能序列性的寫入。操作次數(Number of Operations, NOPs)則代表區扇可以被寫入的次數。目前MLC的NOPs是1；而SLC則是4。 NAND Flash也要求裝置驅動程式、軟體或分離的控制晶片進行壞區管理，例如SD卡內部便包含壞區管理與耗損平衡的電路。當一個邏輯區被高階軟體存取時，實際繪測的工作由驅動程式或控制器進行。
-----------------------------------------------------------------------------------------------------------------
3-02 ----------------------------------------------------------------------------------------------------------
保護模式protected mode
保護模式 (Protected Mode，或有時簡寫為 pmode) 是一種 80286 系列和之後的 x86 相容 CPU 操作模式。保護模式有一些新的特性，設計用來增強 多任務 和系統穩定度，像是 記憶體保護，分頁 系統，以及硬體支援的 虛擬記憶體。大部分的現今 x86 作業系統 都在保護模式下運行，包含 Linux、FreeBSD、以及 微軟 Windows 2.0 和之後版本。
另外一種 286 和其之後 CPU 的操作模式是 真實模式，一種向前相容且關閉這些特色的模式。設計用來讓新的晶片可以執行舊的軟體。依照設計的規格，所有的 x86 CPU 都是在真實模式下開機，來確保傳統作業系統的向前相容性。在任何保護模式的特色可用前，他們必須要由某些程式手動地切換到保護模式。在現今的電腦，這種切換通常是由 作業系統 在開機時候必須完成的第一件工作的一個。它也可能當 CPU 在保護模式下運行時，使用 虛擬86模式 來執行設計給真實模式的程式碼。
儘管用軟體的方式也有某些可能在真實模式的系統下使用多工，但保護模式下記憶體保護的特色，可以避免有問題的程式破壞其他工作或是 作業系統 核心所擁有的記憶體。保護模式也有中斷正在執行程式的硬體支援，可以把 execution content 交給其他工作，得以實現 先佔式多工。
大部分可以使用保護模式的 CPU 也擁有 32 位元暫存器 的特色 (例如 80386 系列和其後任何的晶片)，導入了融合保護模式而成為 32 位元處理的概念。80286 晶片雖有支援保護模式，但是仍然只有 16 位元暫存器。Windows 2.0 和之後版本中的保護模式增強稱為 "386 增強模式"，是因為他們除了保護模式外，還需要 32 位元的暫存器，並且無法在 286 上面執行 (即使 286 支援保護模式)。
-----------------------------------------------------------------------------------------------------------------
3-03 ----------------------------------------------------------------------------------------------------------
微軟利用許多更底層的Windows API函式，開發出許多封裝媒體櫃（wrapper），讓應用程式以更抽象的方式與Windows API進行互動。MFC（Microsoft Foundation Class Library）用C++ 類別來封裝Windows API的功能，因而允許用更為物件導向的方式與API進行互動
Windows API
視窗作業系統應用程式介面（Windows API），有非正式的簡稱法為WinAPI，是微軟對於Windows作業系統中可用的核心應用程式編程介面的稱法。它被設計為各種語言的程式呼叫，也是應用軟體與Windows系統最直接的互動方式。大多數驅動程式所需要的對Windows系統的更底層次存取介面，由所用版本的Windows的Native API來提供介面。
-----------------------------------------------------------------------------------------------------------------
3-04 ----------------------------------------------------------------------------------------------------------
- 行程間的通訊（IPC）
互相獨立:執行過程中不會受其他行程的影響，而各自完成自己的任務
有合作關係:透過共用資源（如資料結構、訊號機制等）的使用，來互相溝通合作以共同完成某些任務但是它們的執行結果常常會因為存取共用資源而彼此受到影響
- 行程間互相合作的好處:提升運算效能,增加使用的便利性,讓程式比較模組化
共享記憶體（Shared Memory）模式
- 同位址空間的不同執行緒之間
- 直接對全域變數作讀寫
- 不同的行程之間—不同位址空間
- 透過作業系統提供的系統呼叫（System Call），將同一塊實體記憶體空間對應到各自的記憶體空間內
- 對該記憶體空間作讀寫
- 潛在問題
- 必須使用同步機制保護，避免資料錯誤
-----------------------------------------------------------------------------------------------------------------
3-05 ----------------------------------------------------------------------------------------------------------
硬即時系統
軟即時系統
死鎖/死結 Deadlock
死鎖（Deadlock），這裡指的是行程死鎖，是一個電腦技術的名詞。它是作業系統或軟體執行的一種狀態：在多工系統下，當一個或多個行程等待系統資源，而系統資源又同時被此行程本身或者其它行程佔用，就形成了死鎖。它有一個變種是活鎖。
簡介
例如，一個行程 p1佔用了顯示器，同時又必須使用印表機，而印表機被行程p2佔用，p2又必須使用顯示器，這樣就形成了死鎖。現實生活中也有死鎖的例子，在一個十字路口，四面的汽車都在等待（靠右行），每次都是右邊的汽車先行。
Deadlock成立的四個必要條件
- Mutual exclusion(互斥)
Def：
資源在同一時間內，至多只允許一個process使用(不允許≥2個processes同時使用)
其它欲使用此resource的process必須wait，直到該process釋放resource為止
eg. printer、Disk、CPU etc.
eg. 不具mutual exclusion→Read-only File - Hold & wait(持有並等待) (Partial Allocation)
Def：
process持有部分資源且又在等待其它processes所持有的資源 - No preemption(不可強取豪奪)
Def：
process不可搶奪其它waiting process所持有的資源，除非其自願釋放 - Circular waiting(循環等待)
Def：
存在一組process
P0→P1→P2→...→Pn→P0
P0~Pn形成Circular waiting
OSC:
- Mutual Exclusion
not required for sharable resources; must hold for nonsharable resources. - Hold and Wait
must guarantee that whenever a process requests a resource, it does not hold any other resources. - Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none.
- Low resource utilization; starvation possible.
- No Preemption
- If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.
- Preempted resources are added to the list of resources for which the process is waiting.
- Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.
- Circular Wait
impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.
死鎖的預防
如果系統中只有一個行程，當然不會產生死鎖。如果每個行程僅需求一種系統資源，也不會產生死鎖。不過這只是理想狀態，在現實中是可遇不可求的。
禁止搶佔：no preemption
持有和等待：hold and wait
互斥：mutual exclusion
迴圈等待：bounded waiting
死鎖的避免
我們也可以嘗試迴避死鎖。因為在理論上，死鎖總是可能產生的，所以作業系統嘗試監視所有行程，使其沒有死鎖。
死鎖的消除
最簡單的消除死鎖的辦法是重新開機系統。更好的辦法是終止一個行程的執行。
-----------------------------------------------------------------------------------------------------------------
3-06 ----------------------------------------------------------------------------------------------------------
觀念送分題
-----------------------------------------------------------------------------------------------------------------
3-07 ----------------------------------------------------------------------------------------------------------
- 優先權反轉（Priority Inversion）
- 問題
- 低優先權的執行緒正佔用共用資源，反而讓高優先權的執行緒無法獲得CPU的執行權力，可能會讓整個系統的即時性大受影響
- 解決方法
- 優先權繼承協定（Priority-Inheritance Protocol）
- 方法
- 當高優先權的行程需要某個資源，所有正在存取該資源的行程都會暫時繼承那個較高的優先權，直到它們完成對該資源的存取為止，才再回復為原先自己的優先權
優先權倒置，又稱優先權反轉、優先權逆轉、優先權翻轉，是一種不希望發生的任務排程狀態。在該種狀態下，一個高優先權任務間接被一個低優先權任務所搶先(preemtped)，使得兩個任務的相對優先權被倒置。
這往往出現在一個高優先權任務等待存取一個被低優先權任務正在使用的臨界資源，從而阻塞了高優先權任務；同時，該低優先權任務被一個次高優先權的任務所搶先，從而無法及時地釋放該臨界資源。這種情況下，該次高優先權任務獲得執行權。
在多數個案，發生優先權倒置並不導致直接傷害──高優先權任務的延遲執行不被察覺，最終，低優先權任務釋放共享資源。雖然，亦存在很多情況優先權倒置會導致嚴重問題
舉例
在作業系統中，一般情況下，
- 行程分優先權，高優先權行程需要執行時可打斷現正在執行的低優先權行程；
- 普通的臨界資源使用方法，如果一個臨界資源被獲取了，則其它想要獲取此資源的程式被阻塞，直到此資源被釋放；
- 有三個行程（其優先權從高到低分別為T1、T2、T3），有一個臨界資源CS（T1與T3會用到）。這時，T3先執行，獲取了臨界資源CS。然後T2打斷T3。接著T1打斷T2，但由於CS已被T3獲取，因此T1被阻塞，這樣T2獲得時間片。直到T2執行完畢後，T3接著執行，其釋放CS後，T1才能獲取CS並執行。這時，我們看T1與T2，雖然T1優先權比T2高，但實際上T2優先於T1執行。這稱之為優先權逆轉。
T1---------XXX--------------------CS|||||
T2-------------|||||-------------------------
T3-----CS||||-------|||||CS-------------
-----------------------------------------------------------------------------------------------------------------
3-08 ----------------------------------------------------------------------------------------------------------
RTOS實時作業系統
即時作業系統（Real-time operating system, RTOS）又稱實時作業系統，它會按照排序執行、管理系統資源，並為開發應用程式提供一致的基礎。
RTOS的內核通常會有：
調度策略
優先順序調度、中斷調度、時間輪轉法
RTOS舉例
開放原始碼
非開放原始碼
-----------------------------------------------------------------------------------------------------------------
3-09 ----------------------------------------------------------------------------------------------------------
互斥(Mutual Exclusion)
死結(Deadlock)
互斥鎖（英語：英語：Mutual exclusion，縮寫 Mutex）是一種用於多執行緒編程中，防止兩條執行緒同時對同一公共資源（比如全域變數）進行讀寫的機制。該目的透過將代碼切片成一個一個的臨界區域（critical section）達成。臨界區域指的是一塊對公共資源進行存取的代碼，並非一種機制或是演算法。一個程式、行程、執行緒可以擁有多個臨界區域，但是並不一定會應用互斥鎖。
需要此機制的資源的例子有：旗標、佇列、計數器、中斷處理常式等用於在多條並列執行的代碼間傳遞資料、同步狀態等的資源。維護這些資源的同步、一致和完整是很困難的，因為一條執行緒可能在任何一個時刻被暫停（休眠）或者恢復（喚醒）。
例如：一段代碼（甲）正在分步修改一塊資料。這時，另一條執行緒（乙）由於一些原因被喚醒。如果乙此時去讀取甲正在修改的資料，而甲碰巧還沒有完成整個修改過程，這個時候這塊資料的狀態就處在極大的不確定狀態中，讀取到的資料當然也是有問題的。更嚴重的情況是乙也往這塊地方寫資料，這樣的一來，後果將變得不可收拾。因此，多個執行緒間共享的資料必須被保護。達到這個目的的方法，就是確保同一時間只有一個臨界區域處於執行狀態，而其他的臨界區域，無論是讀是寫，都必須被掛起並且不能獲得執行機會。
死結的預防
如果系統中只有一個行程，當然不會產生死結。如果每個行程僅需求一種系統資源，也不會產生死結。不過這只是理想狀態，在現實中是可遇不可求的。
禁止搶佔：no preemption
持有和等待：hold and wait
互斥：mutual exclusion
迴圈等待：bounded waiting
死結的避免
我們也可以嘗試迴避死結。因為在理論上，死結總是可能產生的，所以作業系統嘗試監視所有行程，使其沒有死結。
死結的消除
最簡單的消除死結的辦法是重新開機系統。更好的辦法是終止一個行程的執行。
當有執行緒進入臨界區段時，其他執行緒或是行程必須等待（例如：bounded waiting 等待法），有一些同步的機制必須在臨界區段的進入點與離開點實現，以確保這些共用資源是被互斥或的使用，例如：semaphore。
一個最簡單的實現方法就是當執行緒(Thread)進入臨界區段時，禁止改變處理器；在uni-processor系統上，可以用"禁止中斷(CLI)"來完成，避免在執行上下文交換(Context switching)的時候發生系統調用(System Call)；當離開臨界區段時，處理器回復原先的狀態。
-----------------------------------------------------------------------------------------------------------------
3-10 ----------------------------------------------------------------------------------------------------------
微軟視窗作業系統應用程式設計介面函式
The Remote Application Programming Interface (RAPI) is a Remote Procedure Call (RPC) mechanism in which the Pocket PC is the server and the PC application is the client. In other words, RAPI allows PC applications to call functions that are executed on the Pocket PC. With RAPI, the registry, file system, database, and configuration of the Pocket PC device are available to the PC application.
微軟視窗作業系統應用程式設計介面函式列表
下表是微軟視窗作業系統應用程式設計介面函式（APIs）列表：
應用程式設計介
現代
- .NET Framework, 當中包括Remoting, Assemblies, Metadata, Common Language Runtime, Common Type System, Global Assembly Cache, Microsoft Intermediate Language, Windows Forms, Windows Communication Foundation, Windows Presentation Foundation, Windows CardSpace, Windows Workflow Foundation, Windows PowerShell
- DirectX, 當中包括Direct3D, DirectDraw, DirectInput, DirectMusic, DirectPlay, DirectSetup, and DirectSound
- Graphics Device Interface (GDI) and GDI+
-----------------------------------------------------------------------------------------------------------------
3-11 ----------------------------------------------------------------------------------------------------------
即時系統Real-time system
(七)即時系統(Real Time System)
即時系統就是對於較重要的事件，必須能在一定的時間限制內作出適當反應的
系統，其和分時系統不同的是，分時系統雖然也希望反應快一些，但是它並沒有時間的限制。一般說來，即時系統分為兩種：
第一種是硬性即時系統(Hard Real-Time)，它可以保證重要的工作準時完成。要達到這項目標必須要求系統內的所有延遲都有所限制，從擷取儲存的資料到完成任何外界的要求等，都必須限制時間
第二種限制較少的「軟性即時系統(Soft Real-Time)」，在這種系統中，重要的即時任務有比其它任務更高的優先權，並且一直保有此優先權直到完成為止，
-----------------------------------------------------------------------------------------------------------------
3-12 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
3-13 ----------------------------------------------------------------------------------------------------------
FCFS:non-preemptive
RR,CE,RMS:preemptive
-----------------------------------------------------------------------------------------------------------------
3-14 --------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
3-15 --------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
- -行程（Process）
- 代表一個基本的執行單位，負責執行相關的任務
- 並不是每個作業系統都會稱執行單位為行程
- 各個系統中，執行單位會有不同的名稱與意義
- 執行緒（Thread）、工作（Task）
- 讓一個行程裡面包含許多的子執行單位，稱作執行緒（Thread）或是工作（Task），像是WinCE
- 直接將一個執行單位視為一個執行緒或是工作，像是Palm OS、µC/OS
- 以應用程式的角度看的是行程，但在核心的角度則是以工作（Task）來區分，像是Linux
執行緒thread
執行緒是計算機科學中的一個術語。指運行中的程序的調度單位。一條執行緒指的是進程中一個單一順序的控制流。也被稱為輕量進程（lightweight processes）。它是系統獨立調度和分派的基本單位。同一進程中的多條執行緒將共享該進程中的全部系統資源，比如文件描述符和信號處理等等。 一個進程可以有很多執行緒，每條執行緒並行執行不同的任務。
輕量級進程light-weight process
在計算機作業系統中,輕量級進程（LWP）是一種實現多任務的方法。與普通進程相比，LWP與其他進程共享所有（或大部分）它的邏輯地址空間和系統資源；與執行緒相比，LWP有它自己的進程標識符，並和其他進程有著父子關係；
3-07,3-08
- 競爭狀態（Race Condition）
- 防止競爭狀態發生的策略:
- 發展並行行程/執行緒存取共用資料的控制方法
- 一次只能有一個行程/執行緒存取受保護的共用資料
臨界資源（critical resource）
受保護的共用資料
臨界區間（critical section）
- 各個行程中用來存取這個臨界資源的程式區段
- 號誌（semaphore）
3-06
- 死結或飢餓
- 使用wait指令而需要進入等待狀態時，就有可能發生死結或飢餓的狀況
- 死結（Deadlock）
- 兩個或兩個以上的執行緒永無止境的循環等待另外一方所產生的結果
- 飢餓（Starvation）
- 泛指某個執行緒無止境的等待
- 例如等待的事件永遠不會發生
死鎖/死結 Deadlock
死鎖（Deadlock），這裡指的是行程死鎖，是一個電腦技術的名詞。它是作業系統或軟體執行的一種狀態：在多工系統下，當一個或多個行程等待系統資源，而系統資源又同時被此行程本身或者其它行程佔用，就形成了死鎖。它有一個變種是活鎖。
禁止搶佔：no preemption
持有和等待：hold and wait
互斥：mutual exclusion
迴圈等待：bounded waiting
沒有留言:
張貼留言