針對 Arm 架構的多工處理實作

contributed by < jserv, Oscar Shiang >

討論紀錄

多工處理

multitasking (多工處理，繁體和簡體對應的詞彙有些落差，見國家教育研究院: multitasking) 是作業系統核心一項重要的機制，依據不同層次，我們可初略將多工處理區分為以下三類:

1. 循序式程式 (sequential program)
   • 循序的觀念即程式碼的執行遵守一定的流程，且無時間限制的概念。
   • 循序式程式易於理解，因為時間的演變與程式的執行同一方向，也就是在一特定時間，僅有一項工作在進行。另外，資料的傳遞也只遵循一個方向，因此資料的保護十分容易達成（不會發生資料競爭的狀況）
   • 然而，這類型的程式無法對時間作完全掌控。另外，由於所有的工作均擠在同一流程中，對軟體的維護與擴充較無彈性。
2. 前景/背景式程式 (foreground / background program)
   • 若電腦硬體具備時鐘中斷 (timer interrupt) 的能力，則可對循序式程式進行修改。所謂的前景程式，即是中斷到來時，系統所執行的中斷處理 (interrupt service routine; ISR)。其餘的程式碼則統稱為背景程式。
   • 值得留意的是資料的一致性 (data consistency)。例如若中斷在使用者修改控制器參數的途中到來，則可能計算出不正確的控制訊號。因此對前景與背景共用的資料區必需加以保護。
3. 多工程式 (multi-tasking program)
   • 多工程式設計與並行程式 (concurrent programming) 或多重程式 (multi-programming) 若干觀念有所重疊 (但彼此互不隸屬，詳見 Difference between Multiprogramming, multitasking, multithreading and multiprocessing)。
   • 並行程式設計在硬體並行處理系統中不可或缺，也就是系統中若包含多個 CPU 或不對等 (heterogeneous) 的執行單元時，必須將工作分散至各執行單元同時執行。
   • 於是，我們可想見若各子工作完全獨立，則系統將可達到其最高效率，但子工作完全獨立是幾乎不可能滿足 —— 通常的各執行單元之間仍需溝通資訊，或共用系統資源 (如記憶體、I/O 等)。

並行程式設計的觀念對單一 CPU 的軟體設計來說，同一時間只執行一個工作，但利用高速切換的操作，使程式巨觀上看似多個工作同時在進行。下圖展示這個觀念:

Save as SVGSave as PNGView SourceView Compiled VegaOpen in Vega Editor

Save as SVGSave as PNGView SourceView Compiled VegaOpen in Vega Editor

橫軸是各工作實際佔用 CPU 的時間

從設計軟體的角度而言，多工程式與循序式與前景/背景式程式，有著顯著差異:

1. 系統設計者完全以工作的性質來區分程式，不在遵循程式執行順序的限制;
2. 各工作佔用系統資源的情況，可進行嚴密地管理與時間的分配;

多工程式設計對多數人來說，較難適應，因為人們從需要眼觀四面、耳聽八方的狩獵生活，進入重視分工的農耕生活後，已習慣在同一時間執行一個工作。然而就工作規劃而言，多工程式設計卻高度接近人類的思考方式：人在制定工作目標時，先對目標進行工作分類，並定義各工作的範圍與內容，不過工作的執行並不一定遵循固定的順序，比方說，打字完成列印時，通常會進行其他工作，待列印完後在校正是否列印正確。不難發現，循序式程式設計其實和人類的思考模式相左，而符合「人性」的機制反而是多工機制。

分時多工作業系統的起源

1963 年麻省理工學院的科學記者採訪當時計算中心，並與 Fernando J. Corbató 教授對話，後者是世界上第一個分時多工作業系統 Compatible Time-Sharing System (CTSS) 的主導設計者，Corbató 教授在 CTSS 獲得巨大成功後，帶領 MIT 團隊，和通用電氣 (GE) 及貝爾實驗室發展 Multics 作業系統，許多慣例和概念一路從 CTSS, Multics，到後來汲取前者經驗而重新打造的 UNIX 作業系統。

在這部短片中，Corbató 教授談及過往批次處理系統的限制，並快速回顧電腦運作原理及如何實作分時多工、依據優先權進行排程等等，是此，電腦猶如電話交換機，同時為多個使用者所操作，每位使用者都能依據需求使用終端機，存取到運算和儲存資源，不會和其他使用系統的人有所衝突。可留意到，Corbató 教授在訪談中提到 Supervisory program。

工作 (task) 與執行緒 (thread)

工作與執行緒通常是互通的觀念，均代表著一台電腦執行時的對象。某些作業系統如 Microsoft Windows，對工作與執行緒進行不同的解釋，但在 Linux 核心，工作和行程 (process) 及執行緒之間卻沒有顯著分野，在特定的狀況下，彼此甚至可互相轉換。

詳見 Linux 核心設計: 不僅是個執行單元的 Process

在多個 CPU 的環境中，並行處理的具體作法即是將一個循序執行的程式打散在個別 CPU 中，而每一 CPU 所執行的部份稱為一個執行緒。因此某個目標的達成，可能需要執行多個工作，而每個工作 (可能是個完整的程式) 被分隔出多個執行緒。這即是多工多執行緒系統（multi-tasking multi-threading systems)。因為工作的規劃是以人為導向，而執行緒則視情況，以 CPU 或當時電腦資源的分配情況為導向。如此一來，CPU 在不同工作中的切換可更有效率。因為核心直接面對 CPU，於是操作的對象應是執行緒。

工作切換

多工作業系統核心其中一項關鍵功能是，切換工作時必須保證被停止的工作可在未來繼續執行。從程式的角度而言，即系統必須記錄被停止的程式下一次執行時的位址 (address)，同時必須將 CPU 回復到被停止時的狀態，及保證該工作擁有的資料區不受污染或破壞 (corruption)。這些動作統稱為工作切換或內文切換 (context switch)。內文切換是多工作業系統的一項負擔 (overhead)，系統的反應速度，與內文切換的效率高度相關。

排程器

英國作家 Douglas Adams 在《The Hitchhiker's Guide to the Galaxy》(銀河便車指南) 一書提到:

"Time is an illusion. Lunchtime doubly so."

若時間是真實的，我們就必須跟他周旋，譬如用各種活動或工作塞滿時間，反過來說若時間不存在的，我們就可好整以暇。這句話恰好可解釋排程器運作原理。

排程器 (scheduler) 又稱分派器 (dispatcher)，其功能是決定下一個 CPU 所要執行的工作。排程的演算法很多種，其中經典的演算法包含優先順序式 (priority scheduling) 與時間分割式 (round-robin scheduling 或 time slicing)。特別針對即時系統 (real-time system; RTS)，優先順序式排程是相當重要的特徵，通常硬即時 (hard real-time) 的工作，其優先順序較高。時間分割式的排程法，則針對重要性相同的工作，以切割 CPU 的執行時間來達到並行處理的幻覺 (illusion )。

以下圖的 (a) 來說，若工作一的執行時間很長，則可能使整個系統處在一個沒有效率的等待狀況。而若對 CPU 的執行時間做切割 (如下圖 (b))，則各項工作從巨觀上均能分配到一定的資源與時間。

Save as SVGSave as PNGView SourceView Compiled VegaOpen in Vega Editor

Save as SVGSave as PNGView SourceView Compiled VegaOpen in Vega Editor

上圖 (b) 中的各段 CPU 時間即稱時間切割 (time slice)。CPU 的時間切割可是很小的單位，由系統硬體能力決定。通常各工作均以分配到幾個時間切割來執行。如一個切割是一毫秒 (ms)，則工作一可能分配到 10 個切割，工作二分配到 8 個切割等。而時間切割的分配也並非總是靜態的 (static)，系統可針對不同的狀況在執行時對分割做動態 (dynamic) 改變。

同樣地，優先順序式的排程也可採動態的方式，甚至有可適應優先順序排程 (adaptive priority scheduling)，其主要目的均在解決資源分配的公平性與避免系統產生死結 (deadlock) 的情況。然而，排程規則一旦越複雜，系統的負擔往往也就越重。

搶佔式與非強取式核心

搶佔式 ((preemptive) 與非搶佔式 (non-preemptive) 核心的差別，在於工作本身對 CPU 使用權的交出是強制達成，抑或是自願性的 (voluntary)。在非搶佔式的作業系統中，各工作的程式碼中必須包含交出 CPU 使用權的動作，為達並行的需求，該動作的頻率必須夠高，否則會讓使用者感受到明顯的等待。非搶佔式多工又稱作合作式多工 (cooperative multitasking)，即各項工作間互相合作將 CPU 使用權，不定期交出。這種作法有下列幾項好處：

1. 一般來說，實作較單純，驗證系統行為也容易;
2. 工作中可使用非再進入程式碼 (non-reentrnt code)，換言之，每個工作不需擔心在程式未執行完畢時又重新進入。因此該工作本身所用的記憶區不會有被污染 (corruption) 的可能;
3. 對系統共用記憶區的保護動作可減至最少，因為每一工作在未使用完記憶區時不會放棄 CPU ，無須擔心會被其他工作在半途中修改;

非搶佔式的核心最致命的問題，在於反應能力 (responsibleness)。當一個優先順序較高的工作準備就緒，必須等待優先順序較低的工作放棄 CPU，才可執行。因此非搶佔式的核心很難估計其反應速度，無法滿足許多即時系統應用的需求。

搶佔式的核心則不同，優先順序高的工作可打斷正在執行、優先順序較低的工作，從而拿到 CPU 使用權。下圖展現非搶佔式與搶佔式核心的行為差異。

Save as SVGSave as PNGView SourceView Compiled VegaOpen in Vega Editor

Save as SVGSave as PNGView SourceView Compiled VegaOpen in Vega Editor

假設系統內有三個工作，工作 1, 2, 3 的優先順序為

$Tas{k}_1>Tas{k}_2>Tas{k}_3$，假設工作 2 正在執行。由上圖 (a) 所示，當工作 2 執行到中途時 (A) ，排程器被觸發 (B)，使得工作 1 與工作 3 排定執行。由於是非搶佔式的作法，必須等待工作 2 自動放棄 CPU 使用權 (C) 時，才能去執行工作 1 與 3 (D 與 E)。而搶佔式核心則不然（上圖 (b)），當工作 1 就緒時，工作 2 由於優先順序較低，將被迫放棄 CPU 而交由工作 1 使用。由這個比較可知時間分割式的排程法 (time slicing)，必須使用搶佔式的核心方可落實。

搶佔式核心的最大優點是系統的反應速度快，對即時的應用是不可或缺的特徵，但其核心設計都比非搶佔式複雜許多，考量因素也多，大幅增加實作的難度。同時，它必須注意各程式碼的再進入性 (reentrancy) 與保護共用資料區等。

程式之可再進入性

一個可再進入 (reentrancy) 的函式是可被多個工作同時呼叫，而不會有資料不一致的問題。簡單來說，一個可再進入的函式，會避免在函式中使用任何共享記憶區 (global memory)，所有的變數與資料均存在呼叫者的資料區或函式本身的堆疊區 (stack memory)。對常見的 C 編譯器來說，被呼叫 (callee) 之函式再返回之前，不會更動到呼叫者 (caller) 端的堆疊區。因此，即使該函式被不同的工作同時呼叫，由於在不同的堆疊區執行，互相之間是完全獨立的。

詳見 你所不知道的 C 語言：函式呼叫篇

裝置驅動程式 (device driver) 通常要實作為可再進入的，例如驅動儲存設備的程式很可能同時為數項工作呼叫。

工作間的訊息傳遞

在多工作業系統中，工作間的訊息傳遞 (Inter Process Communication, IPC) 除了透過共用變數 (即 global variable)，另外可用訊息佇列 (message queue)。使用共用變數需要避免資料受污染，因此要透過 mutex, semaphore, spinlock 等同步機制來確保資料一致。

管路 (pipe) 的設計概念，可對應到一個 FIFO (First-In, First-Out) 的佇列 (queue)，傳送端不斷地送資料進入管路的尾端，接收端則不斷地從管路的頭端取出資料。管路中的資料緩衝區 (buffer) 是個環狀資料結構，只要頭端與尾端的指標不重複，就可保證資料不會被覆蓋 (overwrite)。

訊息埠 (message port) 在每個工作或執行緒僅可設立一個，它的作用就如同執行緒的郵箱一般，提供與外界通訊的管道。訊息埠是利用一個訊息封包 (message packet) 來傳遞訊息，訊息封包中要註明送信者與收件者的辨識碼 (identification，簡稱 ID)，透過通訊管理程式 (郵局) 將信件交遞到收件者的訊息埠中。

相對於管路，訊息埠是個需具名 (named) 的傳送管道，在訊息封包中必須填入收件者的 ID，如同寄信要寫收件人住址一般；管路則是不具名 (anonymous) 的祕密管道，只要兩個工作都能夠存取到管路即可。訊息埠藉由物件導向程式對訊息封包的遺傳機制，也同樣可達到不限型別的資料傳送。

藉由 ARMMultiTasking 學習 Arm 架構的多工實作機制

ARMMultiTasking 針對下列 Arm 架構提供多執行緒切換程式碼，並提供極好的模擬驗證環境:

• Armv7A: 如 Cortex A-15)
• Thumb: 如 Armv7E-M, Cortex-M4
• AArch64: 如 Armv8A, Cortex A-57

這裡我們用 AArch64 (64 位元的 Arm 架構) 作為探討對象。

首先自 Arm 網站取得預先編譯的 GNU Toolchain，注意要選 "AArch64 ELF bare-metal target (aarch64-none-elf)"。

下載後嘗試解壓縮:

$ tar Jxvf gcc-arm-9.2-2019.12-x86_64-aarch64-none-elf.tar.xz
$ cd gcc-arm-9.2-2019.12-x86_64-aarch64-none-elf/bin/
$ export PATH=`pwd`:$PATH
$ cd /tmp

檢查 GNU Toolchain 是否正確安裝:

$ aarch64-none-elf-gcc --version | head -1

預期可見下列輸出:

aarch64-none-elf-gcc (GNU Toolchain for the A-profile Architecture 9.2-2019.12 (arm-9.10)) 9.2.1 20191025

接著安裝必要的模擬器和建構工具，以 Ubuntu Linux 為例:

$ sudo apt install qemu-system-arm cmake ccache

取得 ARMMultiTasking 原始程式碼並建構:

$ git clone https://github.com/DavidSpickett/ARMMultiTasking
$ cd ARMMultiTasking
$ cmake . -DBUILD_PLATFORM=aarch64
$ make

測試工具用到 lit，安裝方式:

$ pip install lit

執行測試:

$ lit demos

預期可見以下輸出:

-- Testing: 24 tests, 8 workers --
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: exyielding (1 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: cancel (2 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: args (3 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: exit (4 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: conditionvariables (5 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: alloc (6 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: fibres (7 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: file (8 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: generated (9 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: message (10 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: mutexes (11 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: parentchild (12 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: loadbinary (13 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: permissions (14 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: loadpiebinary (15 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: loadbinaries (16 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: selfyield (17 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: signalhandling (18 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: printthreadname (19 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: spawn (20 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: stackcheck (21 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: timer (22 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: trace (23 of 24)
PASS: aarch64_O3_SANITIZERS_OFF_LTO_OFF :: yielding (24 of 24)

Testing Time: 0.58s
  Expected Passes    : 24

ARMMultiTasking 提供極佳的互動式 shell，可執行以下命令以啟動:

$ make run_shell

預期可見以下:

---------------------
----- AMT Shell -----
---------------------
$ 

嘗試輸入以下命令:

echo Hello World
run ps

預期可見以下輸出:

|-----------|
| Thread 0
|-----------|
| Name      | shell
| State     | suspended (2)
| Child     | run (1)
|-----------|
|-----------|
| Thread 1
|-----------|
| Name      | run
| State     | suspended (2)
| Child     | ps (2)
|-----------|
|-----------|
| Thread 2
|-----------|
| Name      | ps
| State     | suspended (2)
|-----------|

輸入 help 命令可見更多，查看 ls 命令的輸出，可見到若干執行檔，可用 run 命令啟動，例如 run task，隨後再用 ps 命令觀察。

AMT 是 ARMMultiTasking 的簡稱，設計文件可參見 AMT Kernel design notes，摘錄其設計目標:

• Learn about kernel and OS concepts
• Make a "real" but compact project to experiment with toolchains and testing utilities.
• Pass all tests with as wide a set of compiler checks as possible
• Adding a new platform should be easy and rebasing that port should be conflict free as much as possible.
• Implementing "libc" user space features sometimes