中斷與異常 - ianchen0119/AwesomeCS GitHub Wiki

想知道我們在使用滑鼠操作電腦時作業系統在背後做了什麼事情嗎？又或者為什麼我們在寫Ｃ語言時，老師總是會說要盡量避免多餘的 I/O 操作呢？這些問題的答案我們可以在作業系統中得到解答。本篇將針對這個部分探討作業系統的異常與處理。

眼尖的讀者一定會發現: 我在先前的文章已經探討過中斷與異常的議題了，為何本篇又提到了一次？

答: 我們先前是以 RISC-V 處理器的角度去看待中斷以及異常的，而本篇我們針對作業系統端去看待該議題，用不同的角度看同樣的事情時往往會產生新的認知！

先備知識

在閱讀本篇文章之前，請確保你已經暸解什麼是 User mode 以及 Kernel Mode。若你還不知道，可以參考【文科生都能懂的小黑馬作業系統教室】(4) (Ch1)特權指令與系統保謢。

認識中斷

在電腦科學中，中斷是指處理器接收到來自硬體或軟體的訊號，提示發生了某個事件，應該被注意，這種情況就稱為中斷。通常，在接收到來自外圍硬體的非同步訊號，或來自軟體的同步訊號之後，處理器將會進行相應的硬體／軟體處理。發出這樣的訊號稱為進行中斷請求 (IRQ)。 -- wikipedia

What is PIC?

考慮到效能問題，在實務上都會有額外的控制器先將中斷的請求做預處理。等到處理完成後，若處理器沒有關閉 Interrupt 的功能，處理器才會真正執行中斷。而這個特別的控制器就稱為 PIC。一個 PIC 可以處理 8 個輸入中斷，在現今的系統上都會有兩個 PIC 做中斷處理，不過，第二個 PIC 需要接在第一個 PIC 上做分流，所以這樣子做能夠處理 8 + 8 - 1 = 15 個中斷請求，並且中斷請求 (IRQ) 是有優先順序的，IRQ 0 最大，IRQ 15 最小。

筆者已經在 RISC-V::中斷與異常處理 -- 異常篇談過處理器是如何做到拒絕受理中斷請求的，詳情請點開連結並參考 mstatus register 的部分。此外，若想看更多有關 PIC 的介紹，可以參考 PIC 中斷控制器一文獲得更多資訊。

回顧：同步與異步異常

在先前的 RISC-V::中斷與異常處理 -- 異常篇已經談過異常的種類，本篇我們用作業系統方的角度來看同步異常與異步異常的差別在哪。我們都知道，異常主要分兩大類：

異步異常
同步異常

對作業系統而言，I/O 裝置的中斷請求都可以被歸類在異步異常中，像是使用者在操作滑鼠或是鍵盤時，經由 PIC 處理後便會產生中斷請求。這種由外部產生的中斷我們都可以將其歸類成異步異常。反之，若是由執行中的 Program 造成的異常中斷，我們可以將其歸類在同步異常中。

比起異步異常，同步異常是比較容易除錯的。我們可以透過處理器內部的暫存器回去查找有問題的指令位址，再根據 offset 推算錯誤的程式並回推起因。

Interrupts and exceptions

異步異常會經由 PIC 確認後再查詢中斷向量表 (Vector Table)，並從記憶體載入相關的 Interrupt Handler 做相對應的處理。此外，我們可以在 stackoverflow 中的文章知道在 RISC-V 處理器中，中斷處理程序會由 mtvec register 負責紀錄。

根據上圖，我們可以知道 Interrupt response time 是由多個時間組成:

Interrupt latency 在現實中，Interrupt latency 可能受處理器設計、中斷控制器、中斷屏蔽和操作系統的中斷處理方法的影響。
Processing time 在這裡的 Processing time 是指進入中斷後執行相應程式的時間（包含 Context switch ），主要回由設計者的演算法以及處理器效能決定。不過，在這個部分也有可能被其他因素影響，像是：被其他（權限更高）或是本身 Interrupt 中斷。

因此，在一個好的作業系統設計中，開發者會盡量壓縮每個 Interrupt 的 Response Time，以確保執行權可以盡快的回到上層的 IRQ 或是 User space 的應用當中。

系統實務面

上面提到：為了提高系統的效率，中斷程式執行的時間應儘可能的縮短。我們知道在 CPU 沒有關閉中斷的狀況下，當前執行的中斷或是程序是能夠被優先權更高的中斷給搶斷的，這樣一來，原本的中斷就會等待中斷處理完成才能繼續，進而導致事件的響應速度低落。為了避免上面的狀況發生，各個作業系統都有不同的解決辦法。其中，Linux 設計了一些機制，值得我們參考。

再談 Interrupt Handler

以網路通訊為例，若我們丟失 TCP 封包，我們需要等待正確的封包再次回傳到電腦中。這段時間可能長達數秒，若我們一直停留在同一個 Interrupt Handler 會造成作業系統的效能低落。反之，若我們長時間不處理也會有封包遺失的風險 (網卡的 Buffer 滿了以後前面的資料被覆蓋掉)。為此，許多作業系統都會將 Interrupt Handler 拆分為兩大塊：

Top Half
Bottom Half

其設計概念是將基本的硬體操作放在 Top Half，等到前半段結束後再接 CPU Interrupt 做 Enable，進入 Bottom Half 的階段，這也代表該階段是能被更高優先權的中斷搶斷的。

Nested Interrupt

剛剛在說明 Interrupt 中的 Processing time 時就有提到：

不過，在這個部分也有可能被其他因素影響，像是：被其他（權限更高）或是本身 Interrupt 中斷。

所以在計算 Worst case 時也需要考量當前正在處理的所有中斷的時間，因為在 Interrupt 沒有被屏蔽的情況下，更高優先權的中斷將搶占現有中斷的執行權限。為了避免 stack overflow，IRQ 無法被自己或是權限更低的 IRQ 搶斷，在 IRQ 數量為 15 的系統上，Worst case 就是每個 IRQ 都被較高一級的 IRQ 搶斷，等到最高級的 IRQ 處理完畢後再層層返回並處理較低層級 IRQ 的 bottom half。

補充： QNX 是搭載在黑莓機上的作業系統，其核心採用 Microkernel 的設計，在其官方提供的規格書中也有提到 Nested Interrupt 的狀況。

Bottom Half

在 Linux 作業系統中，使用了三種機制去實現 Bottom Half ：

softirq 參考 Linux的中断处理机制 [四] - softirq(1)。
tasklet 參考 Linux 内核中的下半部机制之 tasklet 。
workqueue 參考任务工厂 - Linux 中的 workqueue 机制 [一]。

同步問題

若在多個 Interrupt Handler 以及多個 Daemon Task 中有 Shared-memory，我們就有可能會需要處理同步問題，如果不處理可能會導致記憶體的資料被重複寫入，造成程式結果不符合預期。筆者列舉了幾個 Case 並提出解決辦法：

IRQ 之間共享記憶體假設 IRQ 1 以及 IRQ 2 共享記憶體，為避免同步問題，將另外一個 IRQ 給 Disable 即可。
IRQ 與 Daemon Task 共享記憶體將 IRQ 給 Disable。

Daemon Task 之間共享記憶體使用 semaphore :

Can do increments and decrements of semaphore value

Semaphore can be initialized to any value

Thread blocks if semaphore value is less than or equal to zero when a decrement is attempted

As soon as semaphore value is greater than zero, one of the blocked threads wakes up and continues

no guarantees as to which thread this might be

-- 並行和多執行緒程式設計講座

sem_t semaphore;
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_wait(sem_t *sem);
int sem_post(sem_t *sem);

sem_t empty, full;
void producer(char* buf) {
   int in = 0;
   for(;;) {
    sem_wait(&empty); 
    buf[in] = getChar();
    in = (in + 1) % MAX_SIZE;
    sem_post(&full);
   }
}	

void consumer(char* buf) {
   int out = 0;
   for(;;) {
    sem_wait(&full);
    useChar(buf[out]);
    out = (out + 1) % MAX_SIZE;
    sem_post(&empty);
   }
}

總結

礙於篇幅問題，無法對並行程式設計做更多的介紹，筆者在這邊整理了一些素材供讀者們參考：

Reference

維基百科
交通大學 OCW
Jserv 線上講座