# Data Structures
## Stack / Heap
### Memory Layout


> pointer 存在 stack，實際 pointer 指向的 array 存在 heap

### 程式執行例子

來自影片：[Pointers and dynamic memory - stack vs heap](https://youtu.be/_8-ht2AKyH4?si=aTzo0jrXwdbGDn_J)

>> ``sq()``: ``Square()`` function
>> ``sos()``: ``SquareOfSum()`` function
>>
> 1. 一開始 ``main()`` 執行時，在 stack 上 create 一個 stack frame
> 2. 接著 ``main()`` 去 call ``sos()``，於是又再 create 一個 ``sos()`` 的 stack frame
> 3. 最後，``sos()`` 要執行時又 call ``sq()``，於是又有第三個 ``sq()`` 的 stack frame
> 4. ``sq()`` 執行，計算 x*x
>> ``x``也就是從 ``main()`` 傳給 ``sos()`` 的 ``a``,``b``，然後在 call ``sq()`` 時 parameter 設成的 ``a+b``
>> $\rightarrow$ ``sq()`` return (a+b)*(a+b)
>> - 當 ``sq()`` 在執行時，``sos()`` 和 ``main()`` 暫停
>> - 在 ``sq()`` return 以後，它的 stack frame 被清除
>>
> 5. 同樣的步驟一路 return 回 ``main()`` 為 ``total`` 的值
> 6. ``main()`` 做 ``printf()`` 一樣也會 create ``printf()`` 的 stack frame
> 7. ``printf()`` 執行，同時 ``main()`` 一樣暫停
> 8. ``printf()`` 執行完畢，control 回歸到 ``main()``
> 9. 因為 ``main()`` 也結束了，所以 ``main()`` 的 stack frame 也清除，此時 global variable ``total`` 也被清除

- 如果一直不斷 create stack frame (例如寫出無止境遞迴的程式)，當 stack 成長到超過一開始 OS allocate 的空間，就會產生 stack overflow，造成 program crash

### 考古
- Heap 上的 memory blocks 可以隨時 free
> 用 ``free()``
- Stack 上的 memory blocks <font color = "red">不可以</font>隨時 free
> function call 結束前

# Design / Performance
## HW
### Design Principle

1. ++Simplicity favors Regularity++
- 算術指令固定都是三個 operand
> enables higher performance at lower cost

2. ++Smaller is faster++
- registers 只有 32 個

> register 變少， code 可能變大或變小
>> - register 變少 $\rightarrow$ 每個 instruction 需要的 bit 數變少 $\rightarrow$ code 變小
>> - register 變少 $\rightarrow$ 因為 register 常常不夠用，所以要多做幾次 spilling register（把 register 內容存到 memory）$\rightarrow$ code 變大

3. ++making the common case fast++
- 把零存到 register ``$zero``
- immediate operand in immediate arithmetic
> immediate bit 變少，可存的值變小， code 可能變大或變小
>> - immediate bit 變少 $\rightarrow$ ``lui`` 要用多次 $\rightarrow$ code 變大
>> 
>> - immediate bit 變少 $\rightarrow$ 每個 instruction 需要的 bit 數變少 $\rightarrow$ code 變小

4. ++Good Design demands good Compromises++
- MIPS 保持所有 instruction 等長（因此 require several types of instruction formats）
> 選項可能會給 several types of instruction formats 也是選這個


### CPU performance

==Algorithm==
影響 IC, CPI
> 影響原本的 program 用哪些 instruction，因此影響 processor instruction
> 不同 algorithm 可能會 favor faster 或 slower instruction，就會影響 CPI （舉例來說用比較多除法指令，CPI 就會較高）

==Programming Language==
影響 IC, CPI
> 因為不同 language 的 statement 轉成 processor instruction 結果也會不同
> 不同 Programming Language 的特色不同，例如 Java 大力 support data abstraction，就會用比較多的 indirect call，CPI 就會比較高

==Compiler==
影響 IC, CPI
> Compiler 決定 program 如何 translate

==ISA==
影響 IC, CPI, <font color = "red">clock rate</font>
- ISA 影響決定 CPU performance 的每個面向

---
如果 Cache miss penalty 要花的時間不變，clock rate 變成兩倍（clock cycle time 變成 $1/2$），整體的 CPI 仍然會改變！
> 雖然 $CPI_{base}$ 不會改變，但是 $CPI_{extra}$ 會變多！因為penalty 時間不變，所以同樣時間等同的 clock 數變多

### Vector Architecture

概念：
> 一次從 memory 收集很多 data elements，把它們照順序放到一組很大的 registers 裡 (vector registers)，再用 pipelined ececution units seuqentially 對這些 registers 作用，再把結果寫回 memory

- <font color = "red">vector processors 可以大幅降低 instruction bandwidth</font> （因此也 saves energy）
- vector processor 中，如果有 ++data hazard++，每個 vector instruction 只會在一個 vector 裡的第一個 vector element stall，同個 vector 裡的其他 element 都不用 stall。也就是說，<font color = "red">pipeline 只需要 stall 一次 per vector operation</font>，而不是每個 vector element 都要 stall
- vector computer 會有 vector functional units，以及 muliple parallel pipelines（叫做<font color = "snake"> vector lanes</font>）因此，<font color = "red">vector computer 一個 clock cycle 可以產生兩個或兩個以上的 result</font>
- 只要是用 vector instruction，代表 programmer 或 compiler 認為在這個 vector 中會產生的結果是獨立的，因此 HW 不用再檢查一個 vector instruction 裡面還會不會有 data hazard；而且即使是在 vector instruction 和 vector instruction 之間，HW 每個 vector operand 也只需要檢查一次，也不用檢查每個 element
> 減少檢查次數也會 save energy
- 原本<font color = "red">因為 loop 產生的 ++control hazard++ 在 vector architecture 裡就不存在了</font>
> 假設某個 function 要 loop 十次，每次都要判斷第十次到了沒，要不要再進 loop， vector 直接就做十次了，所以沒有跳不跳的問題
- 因為 vector instruction 去 access memory 會有固定的模式，所以如果 vector 裡面的 element 都相鄰，那從一組 heavily interleaved memory banks 中去 fetch vector 就非常適合，因為<font color = "red">整個 vector 到 memory 讀取資料的 latency 只有一次，而不是這個 vector 的每個 word 都要一次（efficient use of memory bandwidth）</font>

## SW

### Process scheduling

- preemptive SJF = shortest **remaining** time first

### 最差／最佳比對

CPU 排班：
- 最佳：SJF(SRTF)
> 106 交 12.
> SJF improves <font color = "red">waiting time</font>
> (恐 p.207)

- 最差：FIFO
> FIFO 產生 Convoy effect 會造成 <font color = "red">CPU 和 I/O utiization 皆降低 </font>

==Disk==排班
$\quad \rightarrow$ <font color="red">沒有最佳也沒有最差</font>

- Disk 排班只對傳統 HD 有效，對 RAM Drive (RAM Disk) 沒效
> RAM Drive (RAM Disk)：
> 把系統一部分的 DRAM 切出來當作 storage device 來用（像是 secondary storage，但是是由 device driver 來 create）
> 為什麼需要 RAM Drive？
> 因為 I/O operation 速度很快

> 102 交 4.
- C-SCAN 比 SCAN 有更 uniform 的 waiting time

### CPU 排班

#### multilevel (feedback) queue

每個 priority 有分開的 queue
每個 queue 會分到一部分的 CPU time，這個 queue 裡的 processes 再從這部分去分

- ++multilevel queue++ priority 固定（processes 不能在 queue 間移動）
- ++multilevel feedback queue++ priority 可變（processes 可以在 queue 間移動）
> 允許 priority 變動的目的：
> 想根據 CPU burst 大小決定 priority，如果 CPU burst 太長則優先權下降，因此 ++I/O-bound++ 和 ++interactive processes++ 優先權會較高，且 time quantum 較小（priority 高的都不用用那麼久的 CPU，自然 time quantum 不用太長）

# 組合語言

## 高階語言轉組合語言
### caller / callee save


> caller 存：``$tx`` （t開頭暫存器）
> callee 存：``$sx`` （s開頭暫存器）、``$ra``、``$sp``、``$fp``

## 各種指令及特性
### branch / jump

- <font color = "red"> jump 的可跳範圍比 branch 大</font>
> jump 原本有 26 bit 的 pseudo-direct address，再加上最後面補兩個 0 ，共 28 bit
> branch 只有 16 bit constant 還分正負數，所以：
> 最多可往下跳（往 Mem 位址大） $2^{15}-1$ 個++指令++
>> Mem 位址最多加到 $PC + (20000)_{16}$
>>
> 最多可往上跳（往 Mem 位址小）$-2^{15}$ 個++指令++
>> Mem 位址最多減到 $PC - (1FFFC)_{16}$
- branch 的跳躍範圍大約等於往上／下跳 128KB
- 但 jump 跳不出 block，branch 可跳到相鄰的 block
- 如果 branch 在 0 號 block，可往上跳到 15 號 block
如果 branch 在 15 號 block，可往下跳到 0 號 block

# Arithmetic

## IEEE754

k bit 的 2’s complement可表：

==$-2^{k-1} \ \sim \ +2^{k-1} \ - 1$==

<font color = "green"> Bit數配置：</font>

[sign, exponent, fraction]
- Single: 1, 8, 23
- Double: 1, 11, 52

<font color = "green"> Bias: </font>
- Single: 127
- Double: 1023

<font color = "green">指數範圍（加完 bias）：</font>
- Single: 1 ~ 254
> 8bit 可表 0 ~ 255，扣掉全 0 全 1 即 1 ~ 254
- Double: 1 ~ 2046

:::info
指數全0、小數全0 $\quad \rightarrow$ 真的是0
指數全0、小數非0 $\quad \rightarrow$ $\pm \ denorm$
指數全1（single = 255 ; double = 2047）、小數全0 $\quad \rightarrow$ $\pm \ \infty$
指數全1、小數非0 $\quad \rightarrow$ $NaN$
> $NaN$ 用在如：除以 0 、無限大 - 無限大）
:::


> 要換成 IEEE 754 時加 bias，要換回原本的數字時再減回來

> 1 的表示法： exp 部分原本是零次方，加上 bias 後為 $127$；fraction 部分全零，加上 IEEE 754 固定的 1，即 1.000...0

## 運算 HW 實作

### ALU

main control 的 input 是 6 bit 的 opcode，但因為 R-type opcode 是 6 bit 的 0，所以 main control 無法判斷是哪個 R-type 指令在執行，所以 main control 將兩條控制信號線：

1. ALU OP 1
2. ALU OP 0

將指令分成三類：

1. lw/sw : 00
2. beq: 01
3. R-type: 10

> 兩 bit 依序為 ALU OP 1, ALU OP 0

再丟給 ALU Control，讓 ALU Control 根據這兩條 ALU OP 和 6 bit 的 function code 去判斷是哪個指令、要做什麼事，再自己產生 4 bit 的 ALU Control Line 來控制 ALU

> 為什麼要把 Control 分成兩塊，是因為一般來說電路的複雜度和 input 成比例（但並非絕對）
>> - 如果合成一塊 Control
>> $\rightarrow$ 6 bit opcode 和 6 bit function code 共 12 bit，電路複雜度 $\propto 2^{6+6} = 2^{12}$
>> - 如果像這樣用兩塊 Control
>> main control $\rightarrow$ 6 bit opcode，電路複雜度 $\propto 2^6$
>> ALU control $\rightarrow$ 2 bit ALU OP 和 6 bit function code，電路複雜度 $\propto 2^{2+6} = 2^8$
>> $\Rightarrow$ $2^6 + 2^8 < 2^{12}$

> ALU Control input 4 bit 左到右依序為：
> 1. Ainvert
> 2. Bnegate (Binvert + Cin)
> 3. OP 1
> 4. OP 0
>> 第三第四 bit 的 OP1, OP0 和 main control 丟給 ALU Control 的指的是不同的東西！

4 bit ALU Control input 推導舉例：
> slt 是 0111
>
> 因為 slt 的意思是如果 ``$rs`` 比 ``$rt`` 小，就把 ``$rd`` 設成 1
> 所以我們用``$rs``(A) 減 ``$rt``(B) 比大小
> - 因為 ``$rs``不用變號，Ainvert = 0
> - 那 ``$rt`` 的話因為要減，所以等同加負數版的 ``$rt``，首先用 Binvert 將所有 1,0 對調 (1's comp)，接著再將 Cin 設成 1，等同加 1 變成 2's comp
> $\rightarrow$ Binvert, Cin 皆為 1，合在一起看變成 Bnegate = 1
>> 實際上所有情況 Binvert 和 Cin 都是同時為 1 或同時為 0，所以乾脆用一個 bit 的 Bnegate 表示
>>
> 
> - 最後因為我們用是要設 less，所以過 11
>
> 全部依序合在一起即為 0111

### 加法
#### 32 bit ripple carry adder

-<font color = "red"> MSB full adder 如果 cin, cout 值==不同==，必有 overflow</font>

### 浮點數加法器


步驟：
1. 配合<font color = "green">指數大的</font>對齊
2. significand 相加
3. normalize，檢查是否落在合法區間（是否 overflow / underflow）
> single precision exp 範圍：<font color = "red">+127 ~ -126</font>
4. 如果 fraction 超過位數，四捨五入，四捨五入後再檢查一次是否 normalize
> 有可能因為四捨五入進位就非 normalized

---
# 各種公式整理

### Moore 定律 ／ Amdahl 定律
Moore： IC 上 transistor 的數量每兩年會倍增
Amdahl： 改善某個元件會使 performance 提升的比例會受限於不能改善的部分

### power consumption
:::success
$Power \ consumption\propto Vol^2\times clock \ rate$
:::
> 記得++電壓++要平方！

### availability

$availability \ = \ {{MTTF} \over {MTTF + MTTR}}$
> 全部時間裡，好的時間佔多少

---
# Pipeline

<font color = "snake">相同 ISA、執行相同 program</font>，兩個 CPU 分別用 5-stage pipeline，和 single-cycle implement
- 5-stage 的 **exec time 不一定比較短**
- 5-stage 的 **critical path 一定比較短**

> 106 交 2.
<font color = "red">pipeline registers 不一定等長</font>
>> 只要夠裝會存在裡面的 data 即可
>> IF/ID 是 64 bits：
>> $\rightarrow$（PC + 4）和 instruction
>> ID/EX 是 128 bits：
>> $\rightarrow$（PC + 4）、兩個 register read 出來的內容、sign extend 的結果
>> EX/MEM 是 97 bits：
>> $\rightarrow$（PC + 4）／ branch target address、ALU result、zero (1 bit)、``sw``要存進 data memory 的 register 內容
>> MEM/WB 是 64 bits：
>> $\rightarrow$ ``lw``的 write register、data memory 讀出來的內容／ALU 運算結果


### 特性、注意事項
> 108 交
- multiple-cycles-per-instruction 允許 HW 重複利用任意次，所以對比 cingle-cycle machine 或 pipeline，需要的 functional units 是最少的
- 就算 ``lw`` 的 write back reg 在 ID stage 就會經過 Reg File，這個資訊仍然要繼續保存到 WB Stage

## Hazard



- 不管多早計算 branch target address，盡可能的去 predict 是否要 branch，因為 <font color = "red">control hazard 造成的 pipeline stall 都無法避免</font>
- 只要妥善 schedule 要用相同 HW 的 instruction，再利用 stall，不管 pipeline 裡有多少 instruction 要用同個 functional unit，都不會有 structural hazard

需要 SW (Compiler) 幫忙來 remove Hazard
- Delayed Branch (Insert Safety Instructions)
> 找出不管 branch 是否成立都會執行到的 instruction，放到 delay slot 裡，分成三種方法：
>> 1. from before
>> 2. from target
>> 3. from fall through
- Load Use Data Hazard
> 因為不能只用 Forwarding 解決，一定要 insert NOP (Compiler 做)

### Hazard Detection code

> 如果 RegRd 是 0 ，即是 ``NOP``

---
# Process / Thread

## Process

### fork() / exec()

1. ``fork()``

如果用 ``fork()`` 來建立一個新的 process，就會把原本 parent process 的 virtual address space copy 一份，然後 kernel 也會 create 一組 page table 給 child，一開始 child page table 的內容也直接從 parent 的 page table copy 過來，不過所有包含在內的 page，reference count 都會增加

$\rightarrow$ <font color = "red">parent 和 child 在他們各自的 address space 共享相同的 physical pages</font>

> 不過，一種特殊情況是如果在 copy 的時候發現有某部分的 virtual memory 是被 mapped privately，則後續如果 parent / child 有對這部分的 pages 做修改，就不會 update 到對方的 address space 內容

2. ``exec()``

``exec()`` sys call run a new program within current process
更精準的說，``exec()`` 會用 call ``exec()`` 時， argument 名稱的 data file 來取代目前的 data segment（把新的 program load 到原本的 process 裡 = process image overwritten）

> 因為只是 load 一個新的 program 內容到原本的 process， process 本身沒有改變（沒有建立新的 process），所以
> <font color = "red">PID, environment, file descriptor 不變</font>
> <font color = "red">data, code, stack, heap, CPU stat, virtual memory 改變</font>，變成新 load 進來的內容

### Interprocess Communication

[IPC in shared memory 筆記](https://hackmd.io/2ZODb_RoTlikJNub2gOKfg)
[IPC in message-passing 筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/ByIbrMYPa)

## Thread

> 更詳細的 [thread 筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/BkvJ4b2wT)

> process 將它的 stack 分成好幾部分再分配給各個 thread


- <font color = "red">切換 thread 仍然要 context switch （只是比切換 process 快）</font>
- 即使只有<font color = "red">一顆 CPU 也能 concurrent</font>（有很多 thread 在做事），但是 parallelism （很多 thread 在**同時**做事）就一定要 multicore
- ==local var== 放在 stack ，所以每個 thread 對 local var 的變更<font color = "red">只會改到自己這個 thread</font>，==global var== 放在 data，所以每個 thread 對 global var 的變更<font color = "red">會影響到別的 thread</font>
> process 之間的話，對 local, global var 的改變都只會改到自己的
- JAVA 的 green thread 和 Solaris, UNIX 的 LWPs <font color = "red">由 ==user-mode thread library== schedule 而不是 kernel</font>

## Deadlock

四個條件，一個不成立就不會有 deadlock：

1. mutual exclusion
> 至少要有一個 resource 要是 nonsharable，否則例如唯讀檔案，就算有很多 threads 想要同時 open，也不會產生 deadlock

2. hold and wait
> 要防止 hold and wait 可以透過限制 thread 要求 resource 時不能擁有其他的 resource

3. no preemption
> 如果要使這個條件不成立，我們可以用的其中一種 protocol：
> 如果有 thread 手上握有 resource ，又 request 其他不能馬上 allocate 的 resource，就直接把這個 thread 手邊的 resource 全部 preempt

4. circular wait

### Banker's Algorithm

> 101 交 11.

- 如果 process 在 enter system 的時候沒有 declare ``MAX``， Banker's Algorithm 就會 fail

---
# Synchronization

## Race Condition

<font color="red">會</font>有 race condition
- many-to-one (很多 user thread map 到一個 kernel thread)
> 108 交：
> Race condition can occur in a process in which multiple user threads are associated with a kernel thread
> 別人的解釋：
> 如果沒有提供 synchronization 就會發生 race condition
>> （疑問）
>> 恐 p.167: because one thread can access the kernel at a time, multiple threads are unable to run in parallel on multicore systems

<font color="red">不會</font>有 race condition
- ==nonpreemptive kernel==

可以 multiprocessor：
- spinlock
- test_and_set()

不適合 multiprocessor：
- disable interrupt
> 只 disable process 所在的 CPU 的 interrupt，其他不同 CPU 上的 process 仍然可以存取共享變數

- <font color = "red">preemptive kernel ++不能++防止發生在 kernel 內的 C.S. problem</font>

## SW

### Peterson's solution

<font color = "red">注意：
要先表達自己有意願（把自己的 ``flag[i]`` 設 true），再把 ``turn`` 交給別人！</font>


- 用兩個共享變數 ``flag[]`` 和 ``turn``
- flag 初值設 false

Peterson's solution 保證：

1. Mutual Exclusion
> 一次只有一個 process 可以進到 C.S.
2. Progress
> 不在 C.S. 的 process 不會 block 其他 process 進入 C.S.
3. Bounded Waiting
> 每個 process 進入 C.S. 的機會是公平的
>> 101 交 3.
>> 在某個 process request 進入 C.S 到被允許進入之前，這中間的時間其他 processes 進入他們的 C.S 的次數受到限制

### mutex lock

用來保護 C.S. 防止 race condition，process 進入 C.S 前須用 ``acquire()`` 取得 lock，離開 C.S 時須用``relese()`` 釋放 lock


- mutex lock 最大的缺點就是 lock not available 時需要 <font color = "red">busy waiting on lock</font>，造成 performance 降低
- 是一種特殊的 semaphore，值只可能為 0 / 1
> 恐 p.273
> binary semaphores behave similarly to mutex locks
- 除了 protect C.S ，也可以拿來 protect shared variable

### spinlock

- <font color = "red">適合 multiprocessor</font> 且 lock 被 hold 的時間短
> 時間短的定義： 小於兩次 context switch 的時間

- 當有 process 在 C.S. 中時，其他也想進 C.S. 的 process 會不斷 loop 去 call ``acquire()``

好處：要等 lock 的 process 不用 context switch （context switch 太花時間）
>跟 non-spinlock 相比，spinlock 讓想取得 lock 的 process 可以更快取得 lock
>
缺點：當一個 CPU core 被很多 processes 共享時，busy waiting 可能會浪費 CPU cycle

- spinlock 在 multiprocessor system 也有可能會產生 deadlock
- <font color = "red">單一 processor 的系統不可以用 spinlock</font>

### monitor

- 根據 monitor 的結構，++一個時間只有一個 process 能 active in monitor++，所以 programmer 不用 explcitly code 同步的限制

## HW

### Memory Barriers

提供 instruction 使得只要 Memory 內容有更動，就要傳遞給其他的 processors，因此可以保證所有變更都可以被在不同 processors 上的 threads 看到

如果執行到 memory barrier instruction，系統就要確保目前的 ``load``、``store`` 都要先做完才能執行後面的 ``load``、``store``
> 就算有 instruction reordering 也會確保這件事


- memory barrier 是 low level instruction，通常只有 kernel 開發者才會用

### atomic operations

現代的 computer system 有些會提供特殊的 HW 指令（CPU 指令），來解決 criticaal section problem
$\rightarrow$ CPU 保證這些 instruction 是 atomically executed

- ``wait()``, ``signal()``需要 atomically executed

#### test_and_set()


- test and set <font color = "red">須 HW support</font>才能保證 atomically exec
- 可以用來 implement lock
- 可以用 atomic ``swap()`` 取代
- ==``lock``== init value = <font color = "red">False</font>
- 如果有兩個 ``test_and_set()`` instruction 同時被執行（在兩個不同的 core），就會以任意的順序 sequentially 被執行
- 可以 multiprocessor

#### compare_and_swap()


#### ll / sc
``ll``: load linked
``sc``: store conditional
> 如果 ``ll`` 中的 memory 位址在 ``sc``（memory 位址會和 ``ll`` 的相同）執行到之前有被更改， ``sc`` 就會失敗
> 單一 processor 的情況下如果有發生 context switch ``sc`` 也會失敗
> ``sc`` 會把某個 register 的內容存到 memory，且如果有成功存到 memory，就把 register 內容改成 1，失敗就改成 0

- 如果有 processor 都沒有辦法完成 ``sc`` 的情況，就會產生 deadlock （因為不斷 page fault）
- ``ll`` 和 ``sc`` 之間的 instruction 應該要越少越好，減少``sc`` 經常 fail 的機率

> 112 交
> - ``ll`` 和 ``sc`` 比 atomic swap efficient（尤其是在有很多 concurrent process 的情況下）
> $\rightarrow$ 猜測理由為 single atomic memory operation 的 challenge: require both a memory read and a write in a single uninterrupted instruction (恐龍 p.122)

---
# OS

## System Call

sys call 種類與例子
1. ==Process Control==
> ``fork()``,``exec()``, ``exit()``, ``wait()``
2. ==File Management==
> ``open()``, ``read()``, ``write()``, ``close()``
3. ==Device Management==
> ``ioctl()``, ``read()``, ``write()``
>> ``ioctl()``: 送 control commands 給 connected devices
4. ==Information Maintenance==
> ``getpid()``, ``sleep()``
5. ==Communication (IPC)==
> ``shm_open()``, ``mmap()``
>> ``shm_open()``: 建立一個 shared memory object
>> ``mmap()``: 把 file 的某個部分 map 到 process 的 virtual address space
>>
>> $\rightarrow$ 上述兩個 sys call [補充筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/SyN_XQuva)
6. ==Protection==
> ``chmod()``, ``umask()``

> 106 交 13.
- copy string 不用 system call

## Process management
### PCB

PCB 包含：
1. ==process state== (new, ready, running, waiting, ...)
2. ==PC==
3. ==CPU registers== (根據不同的 architecture 不同，例如 acc $sp ,gpr, ...)
4. ==CPU scheduling info== (process priority, ...)
5. ==Memory management info== (base / limit register, <font color = "red">page table</font>, ...)
6. ==accounting info==
7. ==I/O status info== (list of I/O devices allocated to. the process, list of open files, ...)

---
# Interrupt / Exception
## Exception

> 106 交 2.
- exceptions in a pipeline are handled like mis-predicted branches
> exception 處理：flush
>> 假設是 arithmetic overflow
>>
>> 因為是在 EX Stage 做完運算才知道 overflow，所以下個 clock 來時，flush 原本在 IF、 ID 、 EX Stage 的 instruction （後面 Stage 的指令就繼續執行完）
>> 因為原本在這三個 stage 的 instruction 下個 clock 來時，內容分別是存在：
>> IF/ID, ID/EX, EX/MEM 三個 pipeline register
>> 所以 flush 這三個 pipeline register
>> ID/EX, EX/MEM 9 根 control line 設成 0
>> IF/ID 因為未產生 control line，所以將 pipeline register 全清成 0
>>
> mis-predicted branch 處理：將 branch 後面的指令清成 NOP
>> 只要 ``$rd`` 是 0 其實就是 NOP（因為 ``$zero`` 無法被寫入）
>> 不過 MIPS 官方的 NOP 指令是 32 bit 的 0
>> 即 ``sll $zero, $zero, 0``

- 可以用 instruction detect overflow
- signed
- unsigned

---
# Memory
## Memory address (Logical / Physical)

> 102 交 15.
- physical address is the address seen by MMU
- 如果 compile time 的時候就能知道 process 會在 memory 的哪裡，就能產生 absolute code

## Main Memory
### Memory Allocation

1. First Fit: allocate 第一個找到的 hole
2. Best Fit: 找夠大的 hole 裡最小的
3. Worst Fit: 找夠大的 hole 裡最大的
> 為了讓 hole allocate 後剩下的空間最大

### Compaction

為了解決外碎，把所有可用的 memory 移到一起

> 101 交 4.
- 不是所有時候都能做 compaction，必須是<font color = "red"> relocation 是 dynamic 且在 ++exec time++</font> 做才行，如果是 static allocation，且是在 assembly 或 load time 做則不能 compaction

因為 compaction 成本太高，所以另一個++解決外碎++的方法就是 ==Paging==

### Paging


- <font color = "red">TLB 是 cache，所以需要 Tag</font>；每個 virtual page 有一個 page table entry，所以 <font color = "red"> page table 不用 Tag</font>
:::success
每個 page table entry 至少需要的 bit 數 = PPN bit 數（連 valid bit 都不用）
> 108 交 27.
:::

#### TLB

- 有些系統用 小、 fully 的 TLB，因為 fully miss rate 較低，而且因為 TLB 小，所以用 fully 也相對不會那麼貴，不過因為 TLB miss rate 高，就不能用 LRU（太貴），只能用 Random；另外，也有系統用 大、 associativity 小的 TLB
- 如果有些 Virtual address space 空間沒被使用，對應的 ++Page Table entry 是空的，這個 space overhead 可被忽略++

##### TLB Reach

<font color = "snake">TLB Reach</font>
> TLB 涵蓋的 memory 範圍，也就是透過 TLB 可以查到 Physical Memory 的哪些位址
>> 算法：
>> TLB entry 數乘上 page 大小
>>
>> $\rightarrow$ 因為 TLB 的一個 entry 可以查到某個 logical page 對應的是哪個 physical page，因此由一個 entry 可查詢的記憶體位址範圍就是一個 page 的大小

##### 增加 TLB hit ratio

增加 TLB hit ratio 的方法：

1. 增加 TLB entries 數目
> 缺點是貴又耗能
>> 在使用 TLB 時，理想情況是某個 process 的 working set 都涵蓋在 TLB 中，這樣就不用再去 access page table（比較慢）
>>
>> 但是對於一些需要花很多 memory 的 process 來說，即使我們把 TLB 的 entry 數目變成兩倍多，也可能涵蓋不了整個 working set

2. 增加一個 page 的大小
> 因為這樣的話每個 TLB entry 可以查詢的範圍變大了
> 缺點是會造成內碎
>> 為了處理內碎的問題，有些 architecture 提供多種 page size

- 兩個方法都是針對上面提過的 TLB Reach 做改善，用增加 TLB Reach 來提升 hit ratio，只不過增加 TLB entries 數目對提升 TLB Reach 較有限

#### Page Table

##### Page Fault

發生 Page Fault 後，事件的發生順序：

1. (MMU 透過 page table translate physical address 的時候，如果發現 valid bit 是 0) 發 trap 給 OS
2. 存 page fault process 的 registers, process state
> 包含 general purpose register, floating-point register, page table address register, EPC (Exception Program Counter，紀錄 exception 處理完後要從哪裡 restart), (Exception) Cause register
3. OS 用 cause register 判斷 interrupt 是 page fault
4. 去 PCB 檢查這個 page reference 是否為 legal，確認這個 page 在 secondary storage 的哪裡
> valid bit 是 0 有可能是兩種情形： 存取 invalid 的 page（這個 page 不在這個 process 的 logical address space 裡），或是存取的 page 位址是 valid，只是沒有在 memory
> <font color = "snake">Note:</font>
> 因為 TLB miss 很頻繁（TLB 很小），所以在 TLB miss 的時候 TLB miss handler 不會去檢查 reference 的 page table entry 是否 legal，OS 會直接把資料從 page table load 過來。
> 只有在 page fault 時才檢查是否 legal 可以加速 TLB miss 的處理，減少 miss penalty
5. 把這個 page 讀到某個 free frame，這個過程要經過：
a. 在 queue 裡等 read request 被 service
b. 等 seek / latency time
c. transfer 這個 page 到 free frame
> 這個步驟會從 free frame list 裡挑一個 page 來把需要的 page 讀進去，但如果沒有 free frame 了，OS 就需要去挑一個 victim page，挑的方法有不同的 techniques，例如 LRU + reference bit
>> 如果 victim page 的 dirty bit = 1，把要的 page 讀進來以前，要先把這個 frame 的內容寫回 disk
6. <font color = "red">等 transfer page 到 memory 的時候， CPU allocate 給別的 process</font>
> 這步不一定會發生
7. 從 I/O subsystem 收到 I/O complete 的 interrupt
8. 如果第六步有把 CPU 給別的 process，這時候要把那個 process 的 registers, process state 儲存
9. 判斷這個 interrupt 是從 secondary storage device 來的
10. 把 page table 該 page 的 valid bit 設成 valid（說明這個 page 現在已經在 memory 中）
11. 等 CPU 重新再 allocate 給這個 process
12. restore 原本 page fault 的這個 process 的 registers, process state，還有更新後的 page table


#### Page Fault Replacement

==OPT (MIN)==
replace 未來最久不會被用到的 page

- <font color = "red">不會有 Belady's anomaly</font>
> Belady's anomaly：給的 page 越多 page fault 比例反而提升
- 難 implement ，因為需要 future knowledge

## Virtual Memory

### Copy-on-Write

[Copy-on-Write 筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/B1jl4GR_p)

### Allocating Kernel Memory

回顧一般 process 的情況：

如果 user mode process 需要額外的 memory，我們就需要從 kernel maintain 的 free frame list 去找 free frame 來 allocate，同樣的方式不適合拿來 allocate kernel memory，主要因為這種方式的兩個特性：

1. allocate 的 frames ++不連續++，可能散佈在 physical memory 的各個地方
2. 2. 就算 user process 只需要一個 byte，仍然需要 allocate 一整個 frame，所以會有++內碎++

Q. 為什麼有這兩個特性一般的方式就不適用？

理由：

1. kernel 常常會需要要求不同大小的 memory，來因應不同大小的 kernel data structure，其中有些比一個 page 的大小還小，如果我們照一般的方式一樣 allocate 一整個 page，內碎的問題就變得很麻煩，因為 <font color = "red">kenel 的 code 和 data 不能像一般的 process 可以 paging</font>，所以 kernel 的 memory 必須謹慎利用
2. 一般的 user process 被 allocate 的 page 不一定要連續，但因為有些 HW device 需要直接 interact with physical memory，所以 kernel 的 memory 必須是連續的

因此，我們的做法是：

kernel memory 要用的 memory 從和 user process 分開的 free-memory pool allocate
要實踐這件事有兩種做法，即以下的 buddy system 和 slab allocation

#### Buddy System

Buddy System 由 <font color = "snake">power-of-2 allocator</font> 來從固定大小的 segment（由很多 physically 連續的 pages 組成）來 allocate memory，大小都是二的冪次方，例如 4KB, 8KB, 16KB...


> 假設 memory segment 是 256KB， kernel 要求 21KB，這個 segment 就會如圖中一路切下去，每次除 2，直到大小夠用且最接近
> 這個例子中就會 allocate 32KB
>> 其中 $A_L$ 和 $A_R$ 就稱作 buddies，同理 $B_L$ 和 $B_R$、$C_L$ 和 $C_R$ 也都是彼此的 buddies

##### 優點
Buddy System 的好處是相鄰的 buddies 可以很快的結合成更大的 segment，實踐這件事的方式是用一個 technique 叫做 <font color= "green">coalescing</font>
> 如果是上圖的例子，在 kernel 用完那個 32KB 的（假設是）$C_L$，$C_L$ 可以馬上跟 $C_R$ 結合，再一路這樣結合上去，變回原本的 256KB

##### 缺點

Buddy System 的缺點就是還是會有內碎
> 假設 kernel 需要 33KB，就只能 allocate 64KB

#### Slab Allocation

因為 Buddy System 還是會內碎，為了解決這個問題，allocate kernel memory 的另一種方式叫做 Slab Allocation，做法首先是：

$\rightarrow$ 把一個或多個 physically contiguous 的 pages 結合成一個 <font color= "snake">slab</font>
$\rightarrow$ 把一個或多個 slab 合成一個 <font color= "snake">cache</font>

每個 cache 對應一種 kernel data structure

> 每個 cache 裡都會有許多 <font color= "snake">objects</font> ，每個 object 就是一個該 cache 對應的 kernel data structure
> 假設圖中上方的那個 cache 是拿來放 semaphore 的，那裡面每個藍色的框框就是有用到的某個 semaphore
> 兩個 Cache 裡個自有的兩個大框框即是 slab

- Cache 裡可以放幾個 objects 由 slab 的大小決定
> 假設有一個由三個連續的 pages 合成的 12KB slab，一個 object 的大小是 2KB，那一個 slab 就可以放 6 個 object
- 一開始 cache 裡的 objects 都標示 ``free``，如果 allocate 以後就會標示 ``used``
- slab 的狀態有三種可能：
1. full: slab 裡所有的 objects 都已經被 allocated (used)
2. empty: slab 裡所有的 objects 都是 free 的
3. partial: slab 裡有些 objects free，有些 used
- allocate memory 時 slab allocator 會先挑 partial 的 slab，如果沒有再挑 free 的，都沒有的話再去連續的記憶體裡找一些 pages 再來 assign 給 cache

##### 優點
- 因為每個 slab 都會剛好分成某種 kernel data structure 的大小的 objects，所以<font color = "red">不會內碎</font>
- <font color = "red">kernel 要求 memory 的 request 可以很快就被滿足</font>
> 因為一開始就會先建好 objects，而且如果 kernel 用完某個 object 要 release，只要標示 ``free`` 就能馬上再用

### Thrashing

一個 process 在 thrashing 的定義：
$\rightarrow$ 花在 paging 的時間比執行時間還要長

> 注意座標

- 就算不是在 thrashing 的 process，page fault 的處理時間也會上升，因為 thrashing process 都在 paging device queue

>101 交 5.
>
<font color = "red">++不能++改善 thrashing</font>
- 用更快的 CPU
- 用有更多 core 的 CPU
- 用更快的 main modules
- 用更大的 paging disk

# File

[file allocation method 筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/Byp8DQ5d6)

> 98 交
- 不管 file 是如何 opened，我們都可以把所有的 I/O 視為 memory mapped ，讓 file 在 memory 中 access

## Directory
### Directory Structure
#### Single Level Directory


所有檔案都放在一起，所以名稱不能相同

#### Two Level Directory

因為 Single Level Directory 會有不同 user 檔案名稱相同就搞混的問題，所以 Two Level Directory 讓每個 user 分成不同的 directory


- 刪檔案時 OS 會限制只能搜尋 local UFD 的檔案，才不會誤刪別人的同名檔案
- 每個檔案都有一個 <font color = "snake">path name</font>，也就是從 root（MFD）到某個 leaf（該 file）

#### Tree structured Directory

將 Two Level Directory generalize，讓每個 user 都可以有自己的 subdirectory 來管理自己的 files

- create, delete directories 需要用 system call
- tree structured directory 系統中，只要知道 path name，就能 access 別的 user 的檔案
- 大部分的 implementation 中， <font color = "red">directory 也算是 file</font>，只是用特殊的形式處理
> 101 交 6.

UNIX System 中：
- [x] 算 file
$\rightarrow$ <font color = "green">device special file, directory, symbolic link, standard input(console)</font>
- [ ] 不算 file
$\rightarrow$ allocation bitmap

#### Acyclic Graph Directory

如果有不同的 programmers 想要合作處理某個 project，他們就會希望把跟這個 project 有關的檔案存在共通的 subdirectory，但是 <font color = "red">++Tree Structured Directory++ 禁止 file 或 dirctory 共享</font>，所以我們改用<font color = "red">允許 directories 共享 subdirectories 或 files 的 ++Acyclic Graph Directory++</font>

- 建立 shared file 和建立 file 的 copy 不同，建立 file 的 copy 的話如果某個擁有這份 copy 的人有做修改，另一個人不會看到
- shared file 的重點在於實際的檔案只有一份，而且如果有人對這個共享檔案做修改，其他人要馬上能看得到
> 這件事在針對 subdirectories 的共享尤其重要，如果有 user 在共享的某個 subdirectory 新增了一個 file，這個 file 也要出現在所有其他人的 shared directory 中


##### link

[link 筆記](https://hackmd.io/@pipibear/r12FFpPO6)

那麼，如何建立共享的 shared files 或 subdirectories 呢？
$\rightarrow$ 常用的方法（也是 UNIX 的方法）： link

<font color= "snake">link</font>
$\rightarrow$ 一個 (indirect) ++pointer++ 指向某個 file 或 subdirectory
- link implement 透過 absolute 或 relative path name

##### 問題

1. Aliasing Problem
++一個 file 有多個 absolute path name++
造成要尋找某個 file、累計所有檔案的數據、把所有檔案 copy 到 backup storage......，<font color = "red">需要 traverse shared structures 不止一次</font>
2. Dangling pointers
如果有人要刪掉某個 shared file，我們就直接把檔案移除，其他共享這個 file 的人，directory 裡面還留著指向這個檔案的 link，指向根本不存在的檔案，甚至如果 pointer 裡的位址含 disk address，如果這個位址因為原本的 file 刪除，之後又 allocate 給別的 file，這個 dangling pointer 就會變成指到別的檔案
> 關於 Dangling pointers 的處理，可參上方「link 筆記」連結

#### General Graph Directory


前面幾種方式中， Tree structured Directory 只要加入 link 就無法維持 tree 的性質；而 Acyclic Graph Directory 雖然好處是 traverse 比較容易，但是為了維持 performance，我們不想要在需要 search 時要 traverse 兩次

那如果 Directory 的 Graph 有 cycle，設計不良的情況下可能會 在某個 cycle infinite loop searching，為了解決這件事，我們就限制在一次 search 裡面 directories 被 access 的次數

General Graph Directory 的問題一樣跟檔案刪除有關，因為 General Graph 可以有 cycle，所以<font color = "red">如果有 cycle 的話，即使已經沒有辦法 refer 某個 directory / file， reference count 可能還不為零（$\because$ self referencing）</font>
因此我們就會需要 "garbage collection"

##### Garbage Collection

作法步驟：

1. traverse 整個 file system，mark 所有可以 access 到的東西
2. 把所有沒有標示到的東西收集到一個 free space list 中

- Garbage Collection 很耗時所以很少用
- 只有有 cycle 的 graph 才需要 Garbage Collection，<font color = "red">acyclic graph 不用 Garbage Collection</font>

---

## Log-Structured File Systems

> 101 交 2.

Log-Structured File Systems 的設計原理：
- [x] File access 的 performance 不受限於 ``read()`` 因為現代的電腦都有很大的 disk cache
- [x] Sequential 的 disk write 比 random 的快
- [x] 現代的 disk 空間都很大， real system 不會完全使用這些空間
- [x] Disk cache 不能無止境的 delay modified disk blocks 的寫入

錯的

- [ ] Disk ``read()`` 比 ``write()`` 快

# Storage


## Swap space

[Swap Space 筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/HJUBpN8Y6)

## Disk

> 102 交 4.
- 在 Disk 上做 <font color = "snake">logical formatting</font> 的意思就是在 disk 上 ++create 一個 file system++
- disk 上發生 <font color = "snake">soft error</font> 的意思是 ++某個 sector 裡的某些 data bits corruppted 但可被修復++
- OS 可以把一個 disk 上的每個 partition 視作分開的 disk

### RAID

:::success
MTTF (Mean Time To Failure): 好的時間
MTTR (Mean Time To Repair): 壞的時間（要修多久）
$\rightarrow$ MTBF(Mean Time Between Failure) = MTTF + MTTR
:::

$availability \ = \ {{MTTF} \over {MTTF + MTTR}}$
> 全部時間裡，好的時間佔多少

$\rightarrow$ RAID 用 redundancy 來 achieve high <font color = "red">reliability</font>
> 非 availability ！

RAID 4-7 的目的： 希望 independent access occur in parallel (smaller access)

#### RAID 0
$\rightarrow$ <font color = "red">no redundancy （只要有 block lost 就沒辦法 recover）</font>
$\rightarrow$ 直接把 data spread 到多個 disk（稱作 ==striping==），強制要 access 每個 disk
> striping: 把邏輯上 sequential 的 blocks 分散到不同的 disk 來提昇 performance
>
$\rightarrow$ 對 SW 來說一整個 disk set 看起來好像是只有一個 disk，所以簡化了儲存的管理
$\rightarrow$ <font color = "red"> large access 的 performance 變好</font>
$\rightarrow$ <font color = "red"> 允許 concurrent r / w </font>

#### RAID 1
$\rightarrow$ = mirroring = shadowing
$\rightarrow$ 用兩倍的 disk 數，每次寫都寫到兩個 disk

##### RAID 1+0

$\rightarrow$ 先 mirror 再 stripe

##### RAID 0+1

$\rightarrow$ 先 stripe 再 mirror


#### RAID 2
$\rightarrow$ ECC

#### RAID 3

$\rightarrow$ ==<font color = "snake">**bit**</font> - interleaved parity==
$\rightarrow$ 用一個額外的 disk 放 check info
$\rightarrow$ popular in large data (例如多媒體、scientific codes)

> disk 3 放 disk 0, 1, 2 的 parity bits

#### RAID 4


$\rightarrow$ ==<font color = "snake">**block**</font> - interleaved parity==
$\rightarrow$ 用 XOR 來計算 parity
> 偶數個 1 $\rightarrow$ parity = 0
> 奇數個 1 $\rightarrow$ parity = 1

$\rightarrow$ 可以同時 read 但不可同時 write
> 因為 write 要修改 parity disk 的內容

$\rightarrow$ 寫入時可以不用讀其他 disk 的內容
> 可透過舊的 data, parity 和新的 data 計算新的 parity
> （舊 data <font color = "green">XOR</font> 新 data）<font color = "green">XOR</font> 舊 parity

$\rightarrow$ 如果有某個 block 壞掉，需要讀所有的 disk （包含 parity disk）來 recover

#### RAID 5

$\rightarrow$ ==<font color = "snake">**distributed block**</font> - interleaved parity==
> 因為 RAID 4 的 bottleneck 是每個 write 都要更新 parity disk，有一個 disk 在寫入 parity disk 其他 disk 就要等，RAID 5 直接把 parity 分散在各個 disk 中

$\rightarrow$ RAID 5 和 RAID 4 capacity 相同，總體來說都是花一個 Disk 來存 parity

$\therefore \qquad capacity \ = (disk \ 數 - 1)\ \times \ 一個 \ disk \ 的容量$


$\rightarrow$ <font color = "red"> RAID 5 如果 parity block 沒有剛好在同個 disk 上，就可以 allow multiple writes to occur simultaneously</font>
> 例如圖中：
> 如果要寫入 Block 8，會需要用到 P2，所以會 access 到 Disk 1, 3
> 如果要再寫入 Block 5，會需要用到 P1，所以會 access 到 Disk 2, 4
> $\rightarrow$ 這兩次寫入會用到的 disk 都不同，所以可以同時進行
>> 但如果再看左圖的 RAID 4，如果一樣是要寫入 Block 5, 8，會需要用到的 P1, P2 都在同個 disk，就不能同時進行寫入

> 101 交 15.
假設 RAID-5 有六個 disk
- [x] 可以同時 read 6 個 block in parallel
- [x] 可以同時 write 3 個 block in parallel

#### RAID 6

$\rightarrow$ ==P + Q Redundancy==
$\rightarrow$ 兩個 disk 壞掉時還救的回來

## I/O
### Communication: OS & Device

Q. ++OS 如何跟 device 溝通？++
OS 跟 device 間的溝通主要透過兩種方式：

1. I/O indtructions

> OS 直接用 explicit 的 I/O indtructions 把 data 送到特定的 <font color = "snake">device registers</font>
>
> 舉例來說，8086 的 ``in`` ``out`` 就是拿來跟 device 溝通的 instruction，假設要把 data 送到某個 device，caller 就會透過 ``out`` 把 accumulator 的內容送到指定的 port（用來指名要送到的 device）
> 因為這些指令是 priveledged instructions，所以唯一能直接跟 device 溝通的只有 OS

2. Memory-mapped I/O

> 如果是 Memory-mapped I/O，硬體會讓 device registers 變成好像是記憶體的某個位置一樣，於是 OS 就可以直接用 ``load``, ``store`` 去 access 這些 registers

### DMA

[DMA 筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/HyRI8kdPp)

## NAS (Network Attached Storage)

提供 storage accross network
enables multiple users and heterogeneous client devices to retrieve data from centralized disk capacity.
- client 透過 remote procedure call (RPC) interface access
- remote procedure calls (RPCs) 透過 TCP/UDP 經 IP network （通常是同個 LAN）
- Each NAS resides on the LAN as an independent network node, defined by its own unique IP address.
- NAS 通常拿來存 unstructured data，像是 audio, video, websites, text files, Microsoft Office documents

NAS 的功用：
讓許多 users 可以遠端合作、共享資料
> With a NAS system, distributed work environments can easily access files and folders from any network-connected device.

---

# Security

> 僅整理考題看過的內容

### Spyware

<font color = "snake">Spyware</font>
- Trojan horse 的變型
> Trojan horse 和 Spyware 都是 malware
- 伴隨 user 要安裝的 program 而來（通常是 freeware / shareware program）
- 會下載廣告 display 在 user 的 system 上
- 會從 user 的系統裡拿走資料再 return 回 central site

### Buffer Overflow


因為 ``strcpy()`` 只有看到 ``\0`` 時才會停，所以會 overflow

$\rightarrow$ 比較幸運的情況是 overflow 只超過 ``buffer_size``一點點，所以不會怎樣
$\rightarrow$ 如果 overflow 得更多，可能會蓋掉別的東西，可能導致 program crash
$\rightarrow$ 最嚴重的情況是超過的非常多，把目前 function 的 stack frame 都蓋掉，因為 stack frame 的最上方是 return address，所以蓋掉的話 program 可能被 attacker 導向別的 memory 區塊，包含 attacker 控制的區塊，造成 attacker 可以用這個 process 的 ID 去 run 任意他想 run 的 code

- Buffer Overflow Attack 可以突破 firewall 的保護

### Firewall

a firewall is ++a computer, appliance, process or router that sits between the trusted and the untrusted++

- 限制 device 和 network 間的 communication
- 使用 Cloud Service 會被防火牆保護
- firewall 無法防止 attacks tunnel, travel within protocols
- firewall 無法防止 Buffer Overflow Attack
- Firewall 可以減緩 DDoS 的傷害，但不能完全防止
> DoS（左圖）DDoS（右圖）
>
> 
- spoofing is a vulnerability of firewall
> <font color = "snake">spoofing</font>
an unauthorized host pretends to be an authorized host by meeting some authorization criterion

### Port Scanning

本身不是一種 attack，而是去 detect 一個系統哪裡比較脆弱再去攻擊

> 101 交 17.

Port Scanning is a means for a cracker to detect a system's vulnerabilities to attack

### Intrusion Prevention

#### Intrusion prevention system (IPS)

IPS acts as self-modifying firewalls, passing traffic unless an intrusion is detected

#### Signature-based detection

檢查 system input 或 network traffic 看是否有特定的 behavior pattern（也就是 <font color = "snake">signature</font>）是已知為 attack 的

Signature-based detection 企圖去 characterize dangerous behavior

> 101 交 17.

- Signature-based anti-virus software <font color = "red">不能</font> detect ++mutated malware++
- Signature-based anti-virus software <font color = "red">不能</font> detect ++privacy stealing malware++

> Malware 如 Trojan Horse

#### Anomaly Detection

用許多種不同的 techniques 去 detect 系統中的 anomalous behavior

Anomaly Detection 是企圖去 characterize normal（或是 nondangerous） behaviors，detect 是否有不正常的 behavior 發生

### Cryptography

> 101 交 17.

- Cryptosystems are based on computation complexity

#### Symmetric encryption algorithm

加密和解密的 key 相同，所以 key 需要被保護

最常見的 Symmetric encryption algorithm：

<font color = "snake">DES</font>
- <font color = "snake">block cipher</font>
> 一次對一個 block 加密
> 所以如果一次對大量的 data 用同個 key 去加密就容易被攻擊
>> 相對 block cipher，另一種方式是<font color = "snake">stream cipher</font>
>> 一次對一串 bytes 或 bits 進行加密或解密

#### Asymmetric encryption algorithm

Asymmetric encryption algorithm 也就是加密、解密金鑰不同
準備要收 encrypted communication 的人會建立兩個 keys，讓其中一個（<font color = "snake">public key</font>）只要想要的人都能取得

> 101 交 9.
>
- 任何看到 public key 的人都能在短時間內知道它的內容

# Other Topics

## Cloud Computing

- Saas: 1 or more app
- PaaS: software stack
- Iaas: servers, storage

## Virtual Machine

> 102 交 3.
- 如果 guest OS 可以直接從 host OS 的一個 image file boot，那我們也可以直接 copy 這個 image file 到別的地方再 boot 另一個 guest OS

> 102 交 13.
- Java interpreter 一次 interpret 一個 java bytecode operation
- 一般 Virtual Machine 的指令可以直接在硬體上執行，只有 privileged instructions 需要被 simulated