IES101 嵌入式系統基本軟體技術
(2)嵌入式系統軟體的的基本原理(解題說明)
Ref. 作業系統ch5_排程.ppt
Ref. 學貫EP827_嵌入式系統導論,4e_CH07_嵌入式作業系統.ppt
---------------------------------------------------------------------------------------------------------------------節錄排程(scheduling)的重要基本知識
- 一個行程在執行期間會有很多時間在等待（如：等待 I/O 完成）。
- 在單一行程或批次的系統中，當行程在等待時 CPU 是閒置的。
- 在多行程的系統中，若是某一行程變成等待的狀態，該行程會被作業系統從就緒佇列中移除，然後由排程器在就緒佇列中選出一個最適當的行程，並將 CPU 的使用權交給這個行程。
- 有 4 種行程狀態的變化，需要進行排程。
- 由執行狀態切換到等待狀態
- 由執行狀態切換到結束狀態
- 由執行狀態切換到就緒狀態
- 由等待狀態切換到就緒狀態
- 前兩種狀態為行程主動放棄執行權，而後 2 種狀態為被動的。
- 一個系統中若只有行程主動放棄執行權時才會進行重新排程的話，則這個系統的排程方法為不可搶先(non preemptability)的，反之，稱為可搶先的(preemptability)。
- 當排程器選出下一個行程後，就把工作交給分派器。
- 一個分派器會做下面幾件事：
- 內文切換
- 切換回使用者模式（排程是在管理者或核心模式進行）
- 重新回到使用者的程式，並且從適當位址重新開始執行
- 由分派器停止一個行程到開始執行另一個行程的這段時間稱為分派延遲。
- 在選擇一個排程器時有下列幾項準則：
- CPU 使用率(utilization)
- 產量(throughtput)
- 回覆時間(turnaround time)
- 等待時間(waiting time)
- 反應時間(response time)
- 根據不同的系統需求，可以使用不同的準則來選擇不同的排程器。
- 舉例來說，為了保證使用者能得到最好的服務，我們會盡量減小最大反應時間。
排程的準則通常包含：
- CPU使用率（CPU Utilization）：CPU的使用率一般可以用0到100%來表示，越高表示CPU越忙碌，我們也儘量讓CPU越忙碌越好。
- 整體成效（Throughput）：表示單位時間內CPU執行完畢的行程數量。不過，如果系統內較長的行程越多，通常單位時間內能完成的行程數量就越少，反之亦然。
- 行程所需時間（Turnaround Time）：以單一行程的角度來看，從一行程交付執行的時間點，到該行程執行完畢為止的時間。通常包括等待被載入記憶體、在佇列中等待執行的時間、在CPU的執行時間、以及等待I/O完成等的時間總和。
- 等待時間（Waiting Time）：表示每個週期在Ready Queue中等待執行的時間總和。當然，CPU排程演算法並不會影響行程等待I/O的時間，只會對在Ready Queue中等待的時間有影響。
- 回應時間（Response Time）：表示從發出一個指令的時間點，到有回應產生的時間，但不是指有實際執行結果產生的時間。對於互動式的操作模式而言，回應時間越短，使用者就越不會感到系統像是當掉一樣。
----------------------------------------------------------------------------------------------------------
- 排程方法
- 先到先做排程FIFO((First Come First Served Scheduling; FCFS))
- 最短工作優先排程(Shortest Job First; SJF)
- 優先權排程(Priority Scheduling)
- 循環分時排程(Round-Robin Scheduling; RR)
- 多層佇列排程
- 多層反饋佇列排程
先到先做排程FIFO((First Come First Served Scheduling; FCFS))
- 先到先做（FCFS）為最簡單的不可搶先排程法。
- 根據行程要求使用 CPU 的順序，來取得 CPU 的使用權。
- 所產生的平均等待時間經常都很長。
- 使用先到先做排程法時，若系統中存在一個 CPU 暴衝時間很長的行程時，則會產生護航現象。
最短工作優先排程(Shortest Job First; SJF)
- 下一次 CPU 暴衝最短的行程可優先取得 CPU 的使用權。
- 對於平均等待時間而言最短工作優先排程（SJF）為最佳的不可搶先排程法。
- 若兩個行程下一次的 CPU 暴衝時間等長的話，則可以使用 FCFS 排程方式來排程。
- SJF 在實作上有困難，因為很難知道行程下一個 CPU 暴衝時間的確實長度。
- 使用預估的方法來求得近似的值。行程下一個 CPU 暴衝時間的預估值可以設為前幾次 CPU 暴衝時間的幾何平均值。
優先權排程(Priority Scheduling)
- 排程器依行程的優先權高低來分配 CPU 的使用順序，優先權愈高的行程可優先使用 CPU。
- SJF 也可以視為是一種優先權排程法。
- 優先權的定義可以分成兩種類型：
- 內部 - 使用行程內可以測量的項目，如行程使用的記憶體大小。
- 外部 - 使用如使用者繳費的多寡等外部資訊。
- 優先權排程可以是不可搶先的或可搶先的。
- 有可能發生飢餓的現象
- 可使用老化來解決
循環分時排程(Round-Robin Scheduling; RR)
- RR 排程法的效能與時間切片的長短關係非常密切
- 太長 - 如同FCFS 排程法
- 太短 - 產生處理器分享的現象
- 使用 RR 排程法時，必須注意內文切換對效能的影響。
- 使用 RR 排程法最重要的一點就是定義時間切片的長短。一般的經驗法則是 80% 行程的 CPU 暴衝時間應該要比一個時間切片要來得短。
多層佇列排程
- 將行程分類，相同類型的行程分在同一佇列，而每一佇列都有自己的排程方法。
- 最常見的分類將行程分成
- 前景（互動）行程 - RR 排程法
- 背景（批次）行程 - FCFS 排程法
- 佇列與佇列之間還有優先權的關係，且佇列之間還需要另一個整體排程方法
- 可搶先的固定優先權排程法
- 可能會產生飢餓的現象。
多層反饋佇列排程
- 多層反饋佇列排程法允許行程在各個佇列間移動。
- CPU 暴衝時間愈長的行程就移到優先權比較低佇列中。
- 能避免飢餓的現象發生。
多處理器排程
- 若系統中的處理器皆為相同架構時，此系統稱為同質，反之，稱為異質。
- 在同質系統中，通常將所有就緒的行程都放置於同一個佇列中，等待著被分派給空閒的處理器執行。
- 共用就緒佇列的架構下形成了兩種排程方式
- 對稱式多元處理 - 各處理器自行進行排程
- 非對稱式多元處理 –由某一顆處理器來幫其他處理器進行排程
即時排程
- 提高所有工作的可排程性及可預測性，也就是保證最多工作能在所要求的時間限制下完成。
- 依照系統對時間限制所要求的程度可分為兩類：
- 硬即時系統
- 軟即時系統
- 硬即時系統須保證關鍵工作在一定的時間內能夠完，否則對系統會有負面的影響。
- 軟即時系統對時間的要求就沒有那麼嚴苛，萬一工作沒有在一定的時間內完成，它還是有部份價值
- 為了讓即時行程能馬上執行，分派延遲必須很短。
- 為了縮短分派延遲，系統呼叫必須是可以搶先的：
- 在系統呼叫中加入可搶先點。
- 讓整個核心都是可搶先的
- 整個核心中的資料結構都需要使用同步的機制來保護。
- 會產生優先權倒轉的狀況。
-----------------------------------------------------------------------------------------------------------------
2-01 ----------------------------------------------------------------------------------------------------------
- P1: 6
- P2: 8
- P3: 7
- P4: 3
- 最短工作優先排程
- 0 3 9 16
- |---|------|-------|--------|
- P4 P1 P3 P2
- (3+9+16)/4=7
-----------------------------------------------------------------------------------------------------------------
2-02 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
2-03 ----------------------------------------------------------------------------------------------------------
觀念題
-----------------------------------------------------------------------------------------------------------------
2-04 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
2-05 ----------------------------------------------------------------------------------------------------------
event-triggered feedback scheduling structure 基礎架構
feedback scheduling
time-triggered
event-triggered
Embedded System 與使用者的互動：Event-Triggered or Not？
jollen 發表於 April 7, 2007 1:16 PM
Event-Driven（或 Event-Trigger）的架構研究，通常伴隨嵌入式系統與控制的主題出現，我們以「嵌入式控制系統（Embedded Control Systems）」來泛指相關的研究主題。目前，在 embedded control system 的研究領域中，以 event-trigger 和 feedback scheduling 的技術為主；embedded control system 目前是 pervasive computing 的當紅題目。相關的研究，可在 [Feng XIA] 的網站中找到許多有用的 paper，建議可先由 "Event-Triggered Feedback Scheduling of Embedded Control Systems [1]" 此篇 paper 著手，以了解更多這方面的最新研究。
不過，我的目的並不是在了解 embedded control system 的設計理論，而是希望由相關的研究文獻中，找到一些適合「顯示與互動式」的嵌入式軟體架構。大略分享一下目前的初步研究如下。
互動是指使用者與機器的互動，而我想要的架構在於能簡化與有效設計「顯示（GUI）與互動（user interaction）」的軟體；其中，使用者的輸入或點擊（即互動），都可以表示成 event。因此，在人機界面的設計層，我們可以想辦法把整個人機界面表示成一組事件，並做細分。
根據 [1] 所提出的 event-triggered feedback scheduling structure 基礎架構，feedback scheduler 分為 event logic（time-triggered）與 scheduling algorithm（event-triggered）；其中，time-trigger 是以一段固定的時間間隔（time interval）來觸發執行，並發出 event-trigger 請求給 scheduling algorithm。另外，此架構中，real-time control tasks 共用 CPU。
根據 [1] 的說明，feedback scheduler 的目的在於有效地排程 real-time control tasks，並且根據 [1] 的摸擬與結論得到，event-driven 的架構似乎能取得較佳的 real-time control 能力。以 event-driven 的基礎來做 real-time control 或許會比較容易規劃與測試整個系統，由於，我們只需要在特定事件被觸發（驅動）後，在規定的到期時間（deadline）內做完 control tasks 的工作即可達到軟即時（soft real-time）的要求，不管到期時間是長是短（microseconds, seconds or minutes），都不必像以往的 real-time system（or time-triggered）實作，必須強迫 task 在一個標準的時間內做完，因此，較容易實作出可接受的即時系統。
更進一步，甚致可以讓不同的 control tasks 定義不同的 deadline。目前，我針對相關的 event-driven & real-time control 理論架構與觀念，正設法簡化太過複雜的理論架構，或是太過華麗不切實際的理論基礎，希望能擬出一套精簡的 event-driven 的軟體架構。此架構的原則與目的與大家分享如下：
1. 必須夠簡單、精簡，程式碼要「少」；
2. 必須易於實作；
3. 適合應用在嵌入式系統的使用者互動軟體設計上；
4. Full user-space architecture, based-on POSIX threads；
5. 可以很容易套用，縮短「行前教育」時間；
6. 設法以「definition」或「generation」方式勾勒框架（framework），而不是以程式實作（implementation）方式寫框架。
7. 特定使用在顯示與互動的嵌入式軟體，所以改用 "acceptable time" 來取代 "real-time"；希望換個 term 來區別二者的差異；
8. ...(more)
2. 必須易於實作；
3. 適合應用在嵌入式系統的使用者互動軟體設計上；
4. Full user-space architecture, based-on POSIX threads；
5. 可以很容易套用，縮短「行前教育」時間；
6. 設法以「definition」或「generation」方式勾勒框架（framework），而不是以程式實作（implementation）方式寫框架。
7. 特定使用在顯示與互動的嵌入式軟體，所以改用 "acceptable time" 來取代 "real-time"；希望換個 term 來區別二者的差異；
8. ...(more)
對於使用者互動與顯示的應用，其實比較容易設計基礎架構，但是我希望程式碼方面可以越簡化越好，所以決定 re-write 我的 prototype ;-)
參考資料
1. Feng Xia, and Youxian Sun: Event-Triggered Feedback Scheduling of Embedded Control Systems. Proc. 1st National Conference on Pervasive Computing, Kunming, China, Oct. 2005, pp.660-666.
--jollen
-----------------------------------------------------------------------------------------------------------------
2-06 ----------------------------------------------------------------------------------------------------------
中斷
|
（Interrupt）：即某裝置將其狀態改變的信號通知另一裝置，以引起立即的注意與反應的技巧。
|
- 中斷的動作類似召用（CALL）指令，其程序為：
- 但某些中斷須利用外來信號打斷 CPU 的動作，
- 並改變程式計數器的值，使其執行中斷服務常式（Interrupt Service Routine），對中斷作適當的反應，
- 且在中斷服務常式執行結束後，再轉回原先的程式繼續執行。
- 中斷服務常式為了能使被中斷的程式，只暫停一段時間，還能繼續執行，
- 這表示該程式所使用的旗號暫存器（PSW）與其它相關的暫存器必須存起來，且在中斷處理後再作還原，
- 最後再返回到中斷前所執行最後一個指令的下一指令。
- 中斷服務常式和普通的副常式（subroutine）在某些方面並不相同，它並不和某一程式連結起來，而是放在記憶體中某一塊固定的地方（絕對位置），因此，須使用絕對位址來和其他的程式聯絡。
- 由於某些中斷是由外界的事件所產生，因此它都可能發生在被中斷程式的任何一個位置，對於這種中斷，是無法傳送參數或參數位址給中斷服務常式，而必須透過雙方都能存取到的變數，來作資料的變換。
中斷向量
|
（Interrupt Vector ）：即中斷服務程式之新的 IP 與 CS 的雙字組內含值(起始位址)。
|
- 每個向量含 4 位元組，前二個位元組是新指令指標器（IP）或程式計數器（PC）位址，後二個位元組是新碼段（CS）位址，此二個位址組合而成一中斷服務常式的 20 位元位址。
- 中斷向量表最多含 256 個中斷向量，這些向量皆指向對應的中斷服務常式的進入點，其位址可含蓋 8088/86 的 1M 位元組的記憶體空間。
- 每個中斷向量皆有其相對的中斷號碼，依中斷號碼可在中斷向量表中查出相對的中斷向量。
- 將中斷號碼乘上 4 後，即可得相對的中斷向量在中斷向量表內第一個位元組的位址。
- 例如，中斷號碼 5 為中斷向量表之第 6 個向量，其第一個位元組的位址為5 * 4 = 20（14H），請參考圖2-17。
圖2-17 8088/86 之中斷度向量表
-----------------------------------------------------------------------------------------------------------------
2-07 ----------------------------------------------------------------------------------------------------------
參照2-05解題
-----------------------------------------------------------------------------------------------------------------
2-08 ----------------------------------------------------------------------------------------------------------
- 程式（Program）
- 被動的觀念
- 依據要執行的任務而撰寫出的指令與資料，定義要執行的任務
- 編譯後成為一堆二進位的機器碼，存放在檔案系統，或者與系統映像檔放在一起，本身不會有何作用
- 例如：某遊戲的圖示所關連的就是該遊戲的程式
- 行程（Process）
- 主動的觀念
- 分配到電腦的系統資源，如記憶體空間和CPU運算時間，可以主動地執行其所被賦予的任務，而這個任務則是其執行的程式所定義
- 例如：點遊戲圖示玩遊戲時，表示該遊戲的行程已經啟動執行
由程式變成行程
- 配置記憶體（RAM），將程式的程式碼和資料從檔案系統搬到配置的記憶體
- 配置記錄代表該行程的相關資訊、和行程運作會使用到的堆疊（Stack）於記憶體中，此時行程才正式準備就緒、等待取得CPU控制權來執行
- 配置其他的電腦資源
- 額外的記憶體當緩衝區（Buffer）
- I/O裝置
- 其他
- 行程（Process）
- 代表一個基本的執行單位，負責執行相關的任務
- 並不是每個作業系統都會稱執行單位為行程
- 各個系統中，執行單位會有不同的名稱與意義
- 執行緒（Thread）、工作（Task）
- 讓一個行程裡面包含許多的子執行單位，稱作執行緒（Thread）或是工作（Task），像是WinCE
- 直接將一個執行單位視為一個執行緒或是工作，像是Palm OS、µC/OS
- 以應用程式的角度看的是行程，但在核心的角度則是以工作（Task）來區分，像是Linux
本文切換（Context Switch）
- 目的
- 透過排程器的選擇機制，決定下一個擁有CPU使用權的行程之後，作業系統必須透過本文切換，完成行程切換執行的動作
- 儲存內容：目前行程的狀態（Context）
- 包括了程式計數器（Program Counter，PC）、堆疊指標（Stack Pointer，SP）及所有微處理器的其他暫存器內容
- 執行步驟
- 釋放出CPU使用權的行程，將其執行時的狀態存放到該行程的堆疊裡，包括CPU內暫存器的內含值，其中PC記錄目前程式要執行的下一行指令位址
- 將整個系統的狀態，恢復成下個要執行的行程被系統儲存下來的狀態，包含最後將儲存的PC的值，放到CPU的PC暫存器
-----------------------------------------------------------------------------------------------------------------
2-09 ----------------------------------------------------------------------------------------------------------
RedBoot可藉由串列埠或以太網埠下載並執行嵌入式應用軟體，包括嵌入式Linux與eCos。另外，RedBoot可結合GNU除錯器（GDB），在嵌入式軟體的開發與除錯階段提供除錯支援。藉由串列埠或以太網埠，RedBoot也提供互動式的命令列介面（CLI）來管理快閃記憶體映像檔（image）、映像檔下載、RedBoot組態......等功能。如果要自動安裝或自動啟始，也可以利用儲存在快閃記憶體中的啟動腳本檔（boot script），來從快閃記憶體、硬碟或TFTP伺服器載入映像檔。
-----------------------------------------------------------------------------------------------------------------
2-10 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
2-11 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
2-12 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
2-13 ----------------------------------------------------------------------------------------------------------
(A)基本上是對的
-----------------------------------------------------------------------------------------------------------------
2-14 ----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
2-15 ----------------------------------------------------------------------------------------------------------
即時系統排程演算法
- 固定式優先權排程法--Rate Monotonic Scheduling，RMS
- 動態優先權排程法－最早到期優先權排程法Earliest Deadline First Scheduling ，EDF
- 比例分配排程法
固定式優先權排程法Rate Monotonic Scheduling,RMS
- 可搶先的優先權排程演算法
- 定義
- 執行週期越短，則優先權較高
- 理由
- 執行週期越短的任務，表示其即時性需求越高，因此優先權也需要設定越高，以符合系統要求
- 假設
- 行程的執行週期p和執行期限d是相同的
- 缺點
- CPU使用率較低
動態優先權排程法－最早到期優先權排程法Earliest Deadline First Scheduling ，EDF
- 可搶先的優先權排程演算法
- 定義
- 執行期限越靠近，則相對的優先權也會調高
- 假設
- 行程的執行週期p和執行期限d是相同的
- 特點
- 只需要考慮行程的執行期限
- 每個行程的執行優先權需隨時調整
- CPU保證總使用率理論上可以達到百分之百
比例分配排程法
- 不需要指定優先權
- 方法
- 預先為所有的行程預留T個時間區塊
- 每個行程可以得到N個時間區塊，以得到它可以分配到N/T的CPU處理時間
- 再以循環式排程的方式輪流執行每個行程
例：
- 預留了100個時間區塊給三個行程P1、P2、P3
- 每個行程分配到的時間區塊依序為50、15、20
- 每個行程得到保證的CPU時間依序為50%、15%、20%
- 三個行程分配到CPU使用率總和為：50%+15%+20%=85%
- 新的行程P4要求30個時間區塊？？
- CPU使用率為：50%+15%+20%+30%=115% > 1
- NO！！由入場控制拒絕
其它常見的動態優先權排程
- 最少等待時間優先排程（least slack/laxity time first）
- 優先權調整規則為「可以等待的時間越短，則該行程的優先權越高」
- 最短剩餘工作優先排程（shortest job first）
- 優先權調整規則為「剩餘的行程執行時間越短，則該行程的優先權越高」
排程
排程或譯排班，是將任務分配至資源的過程，在計算機或生產處理中尤為重要。
排班首要面對的就是效率問題。以數學而言，排班問題通常就是最佳化問題。以航空公司為例，使用機場每個登機口皆需計時付費，「分配登機口」就是一項任務，而「登機口」就是可供利用的資源，若將登機口使用數量及時間壓到最低，亦即能節省最多的成本。
電腦
常見排程
- Take scheduling
- Least-connection scheduling
- Weighted least-connection scheduling
- Shortest expected delay scheduling
- Never queue scheduling
- Genetic Anticipatory
- Lottery Scheduling
沒有留言:
張貼留言