### 緣由

Data 在 CPU 和 I/O device 間 transfer 的方式有三種：

>1. Programmed I/O (PIO)
>2. Interrupt — Driven I/O
>3. Direct Memory Access (DMA)

---
#### PIO


- CPU control 整個 data transfer
- CPU 需要去檢查 device 是否 ready for transfer
- transfer 通常發生在 CPU register 和 peripheral 之間，而且一次只能 feed 一個 byte 到 register
- CPU 需要持續監控 peripheral 的狀態（看 status bits），直到 I/O indicate ready for transfer (CPU wait & stays in a loop)
> → <font color = "red">造成 CPU 不必要的保持 busy</font>

---
#### Interrupt—Driven I/O

為了不要讓 CPU 不必要的保持 busy，Interrupt—Driven I/O 讓 device controller (透過 interrupt request line) 發 interrupt 來 signal CPU 說 I/O 已經 ready to transfer
> 這也代表 I/O data transfer 是由 external I/O device 來 initiate

當 CPU 收到 interrupt 時：

- 因為通常只有一個 interrupt signal pin，所以 CPU 不知道是哪個device 在發signal；且即使是有多個 pin 的 computer，這些 pin 的功能也不是拿來偵測是哪個 device 在發 interrupt，而是拿來 assign interrupt 的 priority

1. CPU 會停止 current program 的 execution
2. CPU sends interrupt acknowledge 給所有 device
3. 發 interrupt 的 device 收到 acknowledge 後，會 remove interrupt signal，且透過 data bus 把它的 vector number 送給 CPU
> - 如果有多個 device 同時在發 signal，只有最高 priority 的 device 才會 react （做這個步驟）
> - CPU 收到 interrupt 後，會根據是哪個 device 發 interrupt 分派給對應的 interrupt service routine (ISR) 來處理，因為這件事需要快速被執行，所以我們用一個 table (array) 來存指向各個 device 的 interrupt routine 的 pointer，這個 array (稱作 interrupt vector) ，被存在記憶體位址小的地方
>> 當 CPU 收到 vector number 後，就可以用這個數字（代表此 device 的 interrupt service routine 在 interrupt vector 的第幾格 （即 index））加上 interrupt base register （放 interrupt vector 的起始位置）的值，來查表找到對應 ISR 的位址


- 每個 device 有自己的 interrupt routine (install 在 OS 的某個地方)
- CS 術語中 array = vector
- interrupt service routine (ISR) = interrupt handler = interrupt handler routine


> 圖中左側螢光藍寫 2000 的格子是 interrupt base register，代表 interrupt vector 的起始位置放在 memory address 2000。
> 假設是 timer 發 interrupt，當 CPU 送 interrupt acknowledge 時， timer 就從 data bus 回傳 vector number 6，代表 timer ISR 的起始位置放在 interrupt vector 的第六格
>
>
> → $2000 + 6\times4 = 2024$
>> interrupt vector 每格放一個memory address = 32 bit = 4 byte 所以乘以四
>
> ∴ 到 memory address 2024 去讀 timer 的 ISR 放在哪
>
>
> → memory address 2024 放 18000，於是 CPU 把 timer ISR 的起始位置 18000 送到 PC，下個 clock 來時即跳去執行 timer ISR


4. transfer control 給 interrupt service routine (ISR)
5. ISR 會：
- determine interrupt 發生的原因
- 儲存有可能被更動的東西的 state
- data transfer
8. 當 ISR 做完時，會執行一個叫做 *return_from_interrupt* 的 instruction，來讓 CPU resume 到原本收到 interrupt 前正在執行的狀態

> 簡易流程圖
>


- 除了 interrupt vector 以外，另一種告訴 CPU 是那個 device 發 interrupt 的方法是用一個 register 來辨認是哪種 exception，這個 register 叫做 <font color = "snake">cause register</font> (MIPS)。
當 CPU 收到 interrupt 時，device 可以送其中一種：
- vevtor address
- status field 來放在 cause register

---
除了上述兩種 data transfer 方式，對於 large transfer 來說，讓 CPU 不斷去 check status bit 、 一次丟一個 byte (PIO) 給 controller 太浪費 CPU

∴ 乾脆直接把這個工作丟給 DMA Controller

---
### initiate DMA

host 把一個 **DMA Command Block** 寫入 Memory

DMA Command Block 包含：
> - ptr 指向 transfer 的 source
> - ptr 指向 transfer 的 destination
> - count 紀錄要 transfer 的 byte 數
>> Command Block 可能更複雜，例如包含一連串 source / destination 的不連續 address

CPU 把這個 Command Block 的位址寫給 DMA Controller

這種 scatter - gather 的 method
:::warning
allow **multiple transfers** to be executed via a **single DMA command**
:::

CPU 在把 Command Block 寫入 Memory 後，就可以去處理其他的事。

---
### Operate DMA

DMA controller 直接把 address 放到 memory bus 上
→ without the help of the main CPU

當整個 transfer 做完時， DMA 才透過發 interrupt 通知 CPU

#### Handshaking

- 發生在 DMA controller 和 device controller 之間

1. 當有一個 ==word== 的 data 已經 available 的時候，device controller 透過 <font color = "green">DMA-request</font> wire 發 signal 給 DMA
2. DMA 收到 signal 後，就會去搶 memory bus，為了：
- 把 signal 放到 <font color = "green">DMA-acknowledge</font> wire上
- 把要用的 address 放到 memory address wire 上
3. 當 device controller 收到 DMA-acknowledge signal 後，就會把一個 word 的 data transfer 到 memory，並且 remove DMA-request signal



---
### Modes of DMA Transfer

當 DMA controller 在用 bus 時，CPU 就暫時不能 access main memory，只能執行不需要 system bus 的 operation，等於說大部分的時候 CPU 都在 Blocked 的狀態
> 不過 CPU 還是可以 access Cache 裡的 data

根據 CPU 在 Block State 的時間（即 CPU 給 DMA controller system bus 的時間）可分成以下三種 modes

#### $(1)$ Burst

在 Burst mode 之下，Burst of data (全部的 data 或 burst of block containing data) transfer 完以後， bus 才還給 CPU

- 因為一次傳很大量的 data ，所以是 DMA transfer 最快的一種 mode
- 但在傳這麼大量的 data 期間，CPU 都是 Blocked

#### $(2)$ cycle stealing

##### Definition
> A method of accessing computer memory or bus <font color = "red">without interfering with the CPU</font>

因為比較慢的 I/O 會需要花一點時間來準備一個 word 的 data，所以在這段期間，CPU 就可以獲得 bus 的 control
當一個 word 準備好的時候，CPU 就會交還 bus 的 control 給 DMA controller 一個 cycle 的時間，在這個 cycle 裡，這個準備好的 word 就會被傳輸到 memory

- CPU 不會整個 transfer 的期間都在 Blocked 的狀態
- Most Efficient way
- 雖然 <font color = "red">cycle stealing 可能 slow down CPU computation</font>，但把 data transfer 丟給 DMA 做一般情況下仍然 improve performance

#### $(3)$ Interleaving

只有 CPU 不需要用到 system bus 的時候，才會把 bus 的 control 給 DMA controller

> ∴ <font color = "red">在這種 mode 下 CPU 完全不會因為 DMA 而被 blocked</font>

- 但也因此這是 DMA transfer 最慢的一種 mode

> 112 交大
> <font color = "red">DMA transfer **不會** slow down the execution of a CPU intensive program</font>
---
### 特點

- DMA 是 standard component，從手機到 mainframe 都有 DMA
- DMA 是 <font color = "red"> block transfer</font>
> DMA 傳完一個 Block 的 data 才會把 system bus 的 control 還給 CPU
- <font color = "red">CPU is not involved in the **complete** transfer</font>

- we **can** use device interrupts / <font color = "red">polling</font> to synchronize DMA transfer
> 112 交大

- DMA 適合 high-speed I/O device

---
### DMA 可能會造成的問題： Coherence Problem

如果是有 Cache 的 System，同一個 data item 可能會有兩份 copy
> 一份在 cache，一份在 memory

#### 原因

因為 DMA 是直接對 memory 發 memory request，而不是透過 Processor Cache，DMA 看到的 memory location 值和 CPU 看到的可能會不一樣

> 假設 DMA 要寫到的 memory location 在 cache，當 CPU 要去讀的時候可能就會讀到舊的值；同樣的，如果 cache 是 write-back cache，DMA 要去讀 memory 的時候更新過的值還沒有寫回 memory，DMA 也會讀錯


---
### Reference
- 恐龍 12.2.4 (p.498-500)、p.8-9
- 白算盤 6.9-4, 6.9-9~10
- [geekforgeeks: I/O Program Controlled Transfer vs DMA Transfer](https://www.geeksforgeeks.org/i-o-program-controlled-transfer-vs-dma-transfer/)
- [geekforgeeks: Modes of DMA Transfer](https://www.geeksforgeeks.org/modes-of-dma-transfer/)
- [emory uni lecture_notes](http://www.cs.emory.edu/~cheung/Courses/355/Syllabus/6-io/vector-int.html)
- [NTU DMA lecture notes](https://www.csie.ntu.edu.tw/~ktw/InfoSys/PDF_file/Direct%20Memory%20Access%20(DMA).pdf)
- [wiki DMA](https://en.wikipedia.org/wiki/Direct_memory_access)