OS 第一次期中重點整理
==================
[課程網頁](https://www.cs.ccu.edu.tw/~shiwulo/course/2019-os/)
[投影片](https://www.dropbox.com/sh/1bcsvtq6r74qv5l/AAAdz4bHDoO1XAZW_J6JyxiBa?dl=0)
[論壇](https://groups.google.com/forum/?hl=zh-Hant#!categories/ccu_csie_os)
[Github](https://github.com/shiwulo/osdi2019)
## ch01 作業系統概論

### ch01.01-為什麼需要OS。
好用、又增加硬體效率。
{%youtube VMut5VkMej4%}

- 可程式化

    digraph pro{
        {rank=same;file->RAM[label="_write"] RAM->exe}
    }

- 不同程式間的 copy & paste

### ch01.02-為什麼介紹Linux
{%youtube RTf_G_9VAUI%}

### ch01.03-雙模式執行與硬體多工
{%youtube KFODd4R2eFg%}


| kernel mode | user mode |
| ------------------------------------------ | ------------ |
| 可以存取硬碟 | 不可存取硬碟 |
| 可控制 I/O | 不能控制 I/O</br>藉由 syscall 跟 kernel 要 |
| 可以隨時分配資源 | 需要跟 kernel 要資源 |

- 切換模式非常耗時

### ch01.05-記憶體分為kernel space與user space。
設定記憶體可以從哪個模式執行
{%youtube q8dsPCQIz9U%}

| user space | kernel space |
| ------------------- | ------------ |
| 當下Task所佔用的RAM | DRAM |
| 2G(32-bit) | 2G(32-bit) |

- kernel 實際只佔約30M
- Tasks 間無法存取彼此的 user space
- 只有 kernel 能改變權限、I/O，且擁有所有存取權

digraph G{
    hello[label=<<table><tr><td><b>hello_world.exe  </b></td><td port="h">"hello world"</td></tr></table>> xlabel="user space"]
    
    hello:h->kernel[label="access" color=green fontcolor=green]
    kernel->hello:h[label="pointer" style=dashed]
    null[label="I/O device"]
    kernel->null[color=red label="_puts" xlabel="\"hello world\"" fontcolor=red]
}

<div style="text-align:center;">

:arrow_up_small: hello_world.exe 為例
</div>

### ch01.06-記憶體的管理單位。
固定大小的page和不固定大小的segment
{%youtube -uNlurd0vww%}

| page | segment |
| ------------------------------------- | ------------ |
| 1page = 4k</br>1 huge page = 2M or 1G | 大小不一定 |
| 貴 | 便宜 |
| 較慢 | 較快 |
| 可交換位置 | 不可交換位置 |
| 一般硬體 | 嵌入式系統 |
| 動態配置 | 無須動態配置 |

- 1page = 4k, 1 huge page = 2M or 1G
- Linux 預設使用 huge page 較有效率
- AMD 可以動態掃描記憶體的page形成huge page

### ch01.07-dual mode & system call。
硬體提供privileged mode給核心使用，讓所有應用程式透過核心才能存取真實的硬體
{%youtube Fp-rTdk4-ts%}

- 所有 syscall 組語進入點(RIP)一樣
- 儲存軟體目前的狀態
- 呼叫 system call
- 大部分會判斷權限，如果 uid=0(superuser) 就不用
- 程式一開始執行只配置 16 k，不夠跟 kernel 發 signal，一次分配 1page(4k)，最多成長到8M
- 設計系統時，先假設不會出錯，以穩定為主。
- 行程切換不一定要存完整狀態，如 getpid() 速度很快就不用。

:::danger
1. 配置 16.5 k 會 segment fault。
2. 程式記得清空堆疊，以免洩漏 kernel 資料。
:::
### ch01.08-system call & signal。
signal會打斷system call的執行，怎麼處理？為什麼要這樣設計？
{%youtube Mb6lZ8U3Jx4%}

- Linux 一般使用者 uid>1000
- syscall 時遇到 signal
- 不理會
- 處理 signal ，自動重做 system call
- sigaction() 可以跨平台
### ch01.09-Linux的核心「monolithic kernel」
Linux的核心是「monolithic kernel」，放在核心的東西，使用kernel提供的功能只要function call的代價。放在核心外的需要切換模式
{%youtube G64RpFIo1SE%}

| monolithic | micro |
| ------------------- | ------------------------------------ |
| 大部分在kernel mode | 大部分在user mode |
| 效率高 | 效率低 |
| kernel 較肥 | kernel 較瘦 |
| 減少 function call | 需仰賴 context switch 或 mode change |
| Linux、BSD | Minix、L4、Android |

- root 權限太高?

### ch01.10-Linux核心的插件kernel module
Linux或許很小，但不是為核心。Linux核心的插件叫kernel module，執行於kernel mode
{%youtube UozsQKRM9EI%}

| context switch | mode change |
| -------------- | ----------- |
| user process $\leftrightarrow$ user process | user process $\leftrightarrow^{system\_call}$kernel mode |

digraph G{
    usb[label="ext4 fs" xlabel="USB STICK"]
    net[label="network"]
    os[label="kernel"]
    mod[label="ext4 module"]
    nmod[label="network module"]
    {rank=same; usb->os->mod[color="red"]}
    mod->usb[label="read" color=green]
    net->os->nmod[color=red]
    nmod->net[color=green]
}

$ lsmod # 列出目前的 kernel module

### ch01.11-主記憶體的使用
DRAM開著不用還是耗掉，所以用完它，但怎樣用呢？
{%youtube IUca4xfrpVs%}

- 理論上 OS 應該把 RAM 全部用光
- Cache Memory
- 先搬進可能會用到的
- 主 RAM 的快取
- Buffer Memory
- DMA
- Program memory

$ free -h # 讀取記憶體狀態

### ch01.12-記憶體及儲存裝置的一致性
從記憶體回存到硬碟，讀寫的效能及重要性，考量是否有電池、熱插拔
{%youtube mXvtk825Z0Y%}

- 正確性$\Rightarrow$ write > read
- sync
- fsync
- fdatasync
- 效能性$\Rightarrow$ read > write
### ch01.13-Linux的基本檔案權限管理
rwx,rwx,rwx到ACL，root不是真實世界的神
{%youtube fPBzoDszDh8%}

- ACL
- ext4和btrfs都支援
- getacl
- setacl
- 權限來源
- 執行者
- ls
- 檔案擁有者
- passwd

### ch01.14-I/O子系統，周邊控制
對I/O下命令，memory-mapped I/O及port-mapped I/O
{%youtube K-jrhRkTEuk%}

digraph G{
    向周邊下命令->RAM和周邊裝置資料傳輸->向CPU報告完成
}

- Memory-mapped I/O
- device register、RAM map to CPU memory space
- 利用裝置或控制暫存器的小晶片

- Port-mapped I/O
- x86
- 指令慢

### ch01.15-I/O子系統傳輸資料
用DMA傳資料，通常CPU cache的資料是最新的，但DMA造成CPU中的cache的資料比較舊！
{%youtube ERU4Cqtozwk%}


- 不會用CPU傳輸資料
- 太貴
- 太快
- flush
- cache $\Rightarrow$ DRAM
- 用硬體解決
### ch01.16-CPU與DMA爭奪記憶體的存取權
因為DRAM通常只有一個讀寫阜，CPU與DMA競爭記憶體的讀寫權
{%youtube _U7vR7A7m0w%}


- cpu 與 dma 爭奪記憶體存取權
- dma 每次傳輸少量資料
- 效率低
- 提昇I/O效能
- cpu idle
- 每個裝置有自己的 DMA
- 底層的記憶體盡量不要用
- 太小
- 有DMA要傳輸無法傳
- I/O MMU
- 虛擬化
- 限定裝置存取RAM
- DDIO
- 直接寫到 cache
- Intel 規定最多用掉 20% cache

### ch01.17-通知處理器-中斷的硬體概念
通知處理器的方法，使用中斷，新的PCI有2048個中斷。
{%youtube aaoldKnkb_s%}

CPU上真的有一根針腳叫做INT，輸入「1」就會啟動中斷。
{%youtube LSv8xnxV9EY%}

- 2048種中斷訊號
- 15條線來編碼
- 硬體呼叫固定地址(ISR)開始執行驅動程式

### ch01.19-中斷的軟體處理機制。
中斷有一點像是signal，處理完中斷以後，不能影響應用程式（如：excel、powerpoint）的正常執行
{%youtube uUTje9nJG0A%}

- 在 ISR 執行的東西越少越好
### ch01.20-處理中斷的函數陣列。
依照中斷編號呼叫相對應的function。但實際上不是Ｃ函數，而是程式碼，ISR的起始和結束通常要用組語撰寫
{%youtube YiosW2QATPk%}

- IVT 儲存各個 interrupt 的 ISR
- CPU 一次處理一種中斷
- 中斷編碼小的優先
### ch01.21-中斷盡量短
{%youtube 9RNfUkqKGPg%}

- 同號中斷不會被同號中斷
- 經過ISR後由kernel thread ==ksoftirqd==(有#core個)處理
- ksoftirqd 最多能寫32個驅動程式
- ISR不能呼叫任何會造成wait(context switch)、sleep的函數
- 如果要的話，包起來放到work-queue
### ch01.21.5-bottom half
裝置驅動程式的主要部分，不需要立即處理的部份
{%youtube P8S7Rt2cLgM%}

- 效能: softirq > tasklet > work-queue
- 易寫: softirq < tasklet < work-queue
- work-queue 保證在同個 CPU
### ch01.22-解釋interrupt context。
相對於task context的觀念，在interrupt context中有些函數不能呼叫，例如：任何會造成context switch
{%youtube x79Y7VmUtUs%}

- buttom half 多由 kernel thread 呼叫
- 在 ISR loading 不重時，可以直接由 ISR 做 function call
### ch01.23-解釋bottom和top half間如何對應。
我們希望將ISR盡可能地縮短。讓裝置驅動程式「大部分」執行於bottom half
{%youtube -f4Dg3bZu_I%}

$ ps -e | grep softirq

- func對應到data，包成一個mapping的資料結構，放到list，等待呼叫ksoftirqd
- 只有高速裝置會掛 softirq
- 網卡
- 硬碟
### ch01.24-polling和中斷互有優缺點
慢速裝置和OS想要自行控制資料進入系統速度時，使用polling（附帶提競技滑鼠）
{%youtube wYHpg1ihjGg%}


- 網路量大時切換 polling
- 滑鼠、鍵盤用 polling

### ch01.25-buffering及kernel bypass。
buffering可以讓撰寫程式和裝置的驅動獨立開來
{%youtube cx47z5q9oBE%}


- kernel bypass
- DMA直接到user space
- read本身會形成中斷訊號
### ch01.26-Linux中process和thread
Linux中process和thread都是task。產生thread呼叫clone，產生process呼叫fork。這二者背後都是do_fork()
{%youtube -sYUweuDOyE%}

- Linux 裡都是 task

| process | thread |
| ------- | -------------- |
| fork | clone |
| | thread間共用大部分資源 |

- kernel thread 沒有 user space 部分的記憶體，所有 syscall 都在 kernel 內完成

### ch01.27--scheduler。
UNIX最通常的目標是提升系統效率，現在CPU排成器還要顧及使用者體驗和省電等等議題
{%youtube QJnooN3GhlU%}

- OS scheduler 做不到
- CPU scheduler 優先權提高
- I/O頻繁
- 運算量少
### ch01.28-檔案系統
檔案系統，硬碟隨機存取速度不快，相較於flash是很成熟的技術。快閃記憶體貴，隨機存取佳。檔案系統除了顧及效率還要顧及可管理性
{%youtube _jZJt6-l8fY%}

### ch01.29-對稱式多處理器與SMT
SMT將一顆處理器模擬成二顆，可以增加CPU內部資源（如加法器、浮點）的使用率，進而提升效能
{%youtube SfmKE2MCSoc%}

- SMT
- 增加CPU使用率
- 需要多個 task 才有效
### ch01.30-Single-ISA heterogeneous multi-core
兼顧效能與省電的設計，大小核心的設計，二種核心使用同樣的指令集。差別在效能與省電
{%youtube 2WX1lj7SIT0%}


### ch01.31-多核心技術繼續帶來效能的改進
{%youtube I4GZtyZPFCI%}

### ch01.32-UMA、NUMA
記憶體陣列，可以使用多個bank增加記憶體頻寬，如果每一個bank可以獨立控制，甚至還可能同時增加頻寬和降低延遲
{%youtube MvKruCzBN6k%}

### ch01.99-Linux裝置驅動架構
{%youtube Vz_AyEHNQDE%}

- softirq
- 高速裝置或不可延遲
- 硬碟
- 網卡
- 可重載
- tasklet
- 不用考慮 race condition
- workqueue
- 記得考慮 race condition


### ch01.33-啟動作業系統。
為什麼無法直接由disk啟動呢？BIOS（ROM）有什麼樣的特性？因此我們一定需要用BIOS（ROM）
{%youtube Zpdx6lCuCeQ%}

- OS沒辦法存在硬碟
- 因為需要驅動
- ROM
- bios
- 韌體
- bytes addressable
- 沒電可儲存
- UEFI
- 看得懂 FAT
- loader
- OS 載入前，CPU不打開cache

## ch02 作業系統結構
### ch02.01-作業系統的目的。
對使用者來說是讓硬體更好用，對設計師而言，能提高系統使用率
{%youtube RVoNtsqVagY%}

- OS 必須有除錯能力
- ptrace
- core dump
- 可以由 gdb 載入
- kernel debug
- kgdb
- kdb
- htop
- CPU
- DRAM
- I/O
### ch02.02-作業系統的使用者介面。
圖形化介面適合一般使用者，但文字介面較精準並且批次、穩定性高
{%youtube QGL0L6hW0AU%}

### ch02.03-系統呼叫的定義與Linux的實現。
這裡的system call專指kernel對外export的部分。
{%youtube NW5IEbM_JZk%}

### ch02.04-system call的overhead
system call的overhead，可能地降低方式。如果不會發生ctx-sw可以少存一點。如果所需的資料沒機密性，就放在user mode
{%youtube qkhjPmnrSHc%}


- vDSO
- 是動態的
- 避免駭客
- 放不隱私的資料
- rttsc
- 可讓時間精準至耐秒
- 就由固定暫存器每毫秒+1
- 每秒鐘至多做1000次時間更新
### ch02.05-kernel module
Linux的kernel類似插件（plugins），執行於kernel mode。而micro kernel的「元件」則是執行於user mode
{%youtube QYVAla8yLos%}

- lsmod
- kernel module
- 包含驅動程式
- 驅動程式可靜態編譯到kernel，也可動態載入
### ch02.06-Linux用C寫物件導向。
struct內有function pointer和property，此外可用container of實現繼承或interface
{%youtube n1Pv4J8__lg%}


### ch02.07-Layered approach的優缺點。
這個方法在OS上會引起雞生蛋、蛋生雞的問題
{%youtube d-ho5J1WZ_M%}


### ch02.08-硬體抽象層
抽象層式讓軟體系統可以抽換掉底層或上層的做法。硬體抽象層將操作方式和操作策略區方開來。不過Android的硬體抽象層居然是在Linux kernel的上方！
{%youtube QL576c4ch2A%}

- Linux kernel
- GPL licence
- Hardware Asstraction Layer
- 不 open source
- Library
- Apache licence

- HAL
- 希望達到 kernel 內沒有 Assembly
- 讓kernel做軟體的事
### ch02.09-正確唸法（期中考送分題，必考）

## 928 行程與執行緒
### 928-1-01-孔子對作業系統的巨大貢獻
{%youtube BkDn36Kg46E%}

### 928-1-02-task從生到死
{%youtube mVzMMVzA5WA%}


### 928-1-03-task control block
task control block就是OS對這個task的紀錄
{%youtube _giK_1JKnWM%}


### 928-1-04-三層排程器及切換
{%youtube W5NiGpwUc9s%}

- Short-term scheduler
- running queue
- ready queue
- 等CPU
- waiting queue
- 等I/O、signal
- mid-term scheculer
- 先把執行少的task放進disk
- 以免RAM越要越多
- 因為虛擬記憶體很慢
- long-term scheculer
- 可能要wait很久


### 928-1-05-task分類成IO及CPU
{%youtube hS-dhtAShRA%}

- I/O-bound process
- I/O time >> CPU time
- ftp
- CPU-bound process
- CPU time >> I/O time
- image processing
### 928-1-06-建立行程，fork與clone
{%youtube hUidKvcAAUQ%}

- pid
- 0
- idle process
- 優先權最低
- 讓CPU sleep
- 省電
- 1
- 開機第一個 user space process
- daemon
- fork 和 vfork 差不多快，但 vfork 會先暫停父進程的資料結構給子進程用，所以大量fork時他較快


### 928-1-07-行程的結束
行程結束變殭屍。Linux會釋放掉這個行程的所有資源，只留下task_struct
{%youtube 3tVl2e1HbRA%}

- zombie
- kill -9 pid
- init(pid=1)
### 928-1-08-行程間通訊的基本分類
{%youtube AeAl_dsn-8Y%}

- IPC
- copy-paste
- 同步
- 模組化設計
- 直接傳遞
- signal
- OS建立傳輸通道
- 單向
- 雙向
- 間接傳遞
- FIFO
- mkfifo
- pipe
- 無 buffer
- 有 buffer
- 多通道
- 多接收

### 928-1-09-行程間溝通方法，直接或間接
{%youtube JJEfntIoMKE%}

- shared memory
- mmap

- kernel 自己定址儲存
### 928-1-10-重要的生產消費問題。
透過queue來解決生產與消費者問題。這裡給的方法是很棒的。但只適用於一個生產者與一個效費者
{%youtube 0XQAfLYfQkg%}


### 928-1-11-執行緒的動機和「考古與展望」
{%youtube Pxmp7OyJLJ8%}

- thread
- 共享同一個code記憶體位址
- 可以藉由address存取彼此的堆疊
### 928-2-01-scheduler的分類。
OS kernel是否可以將正在執行的task中斷掉，然後把CPU交給另外一個行程？
{%youtube ZlcqWNoV9qo%}

- task
- 正在使用 CPU
- 在等待
- mutex
- I/O
- semaphore

- OS scheduler
- preemptive OS
- 規定時間到，task要把CPU控制權交由OS重新分配
- I/O完成時歸還資源給OS
- 可以兼顧優先權
- preemptive kernel
- non-preemptive kernel
- non-preemptive OS
- 當task放棄CPU使用權，os才會交給其他task

| process | thread |
| ------- | ------ |
| 幾乎不共用任何資源 | 幾乎共用所有資源 |

### 928-2-02-課外補充，協調式多工的極致。
Netware用200MHz的處理器就可以設計出上百人使用的檔案伺服器
{%youtube _eRfyvd36Fw%}

### 928-2-03-Preemptive OS
Preemptive OS分二種，差別在核心模式是否可以立即ctx-sw，立即ctx-sw可以更符合優先權的設定，但效能（throughput）會低一些
{%youtube wwOig7K9aXA%}

- preemptive OS

digraph preemptive{
    {rank=same; task1 task2 task3}
    timer->task1[label="monitor" style=dashed]
    timer->OS[label="interrupt" color=red]
    task1->OS[dir=both label="CPU控制權" color=green]
    OS->{task2, task3}[color=green]
}

- non-preemptive kernel
- context switch 只會發生在 kernel mode 切換到 user mode
- task 執行於 kernel mode ，優先權無限大
- preemptive kernel
- 如果沒有拿 lock，task 執行在 kernel mode 可能會發生 context switch

### 928-2-04-如何定量分析scheduler的好壞（理論上）
{%youtube L9ITbn847ZM%}

- 一些平常部會用到的暫存器（如：浮點運算器），不用做context switch，需要時直接跟os要
### 928-2-05-對簡單演算法的分析及啟發，如何預測接下來的CPU burst的長度
{%youtube pCw9-qXBAZ0%}

### 928-2-06-傳統UNIX排程的重點

### 928-2-07-Linux 2.4排程方法的架構，如何處理多核心？如何對multithread及multicore進行優化
{%youtube 03ITqN-Nbhg%}

### 928-2-08-Linux 2.4如何提高IO性能。
利用epoc的概念，藉由「上個週期的表現」預測接下來。time slice長度與優先權是相關的。沒用完的time要對折
{%youtube 7CZtKM1qubQ%}

- 優先權高的task,time slice 也高

（重點整理47）
### 928-3-01-2.6排程器的架構，從架構上解決run queue是效能瓶頸的問題
{%youtube kqh3Zu851L0%}

- task migration
- 解決run queue負載不平衡
- a $\Rightarrow$ b
1. lock a
2. b acess a
- avoid deadlock
- b lock a
- a lock b
- 互等表白 == 等不到
### 928-3-02-O(1)的資料結構
{%youtube befVMbpPCj0%}

### 928-3-03-O(1)的演算法
{%youtube k8k7p7cNqdw%}

### 928-3-04-複雜度為什麼是o(1)，及優缺點
{%youtube C9VFbl_KscQ%}

### 928-3-05-CFS中優先權的意義。
優先權越高，在相同時間內拿到的cpu越多次。注意：每個task拿到「一次cpu」的時間相同。
{%youtube k3R-wzfb2X0%}

### 928-3-06-CFS要怎樣設定time slice。
CFS依照使用者希望的response設定time slice而不是針對I/O進行優化
{%youtube CBqmXhIGu8c%}

### 928-4-01-CFS的CPU排程部分。
給所有task執行一樣的時間，然後每個task的vruntime增幅不一樣，低優先權的增幅大。高優先權的增幅小
{%youtube HcscXtpbGKc%}

### 928-4-02-CFS怎樣優化IO。
從I/O回來的task給予一個比min-vruntime還有小一點點的數字
{%youtube pxaaKSSwemc%}

### 928-4-03-新進的task如何設定vruntime，就是把vruntime設定為當時的最小值。fork bomb就是密集的fork，造成系統當住
{%youtube n9luoR_lQBw%}

### 928-4-04-跳脫vruntime談CFS，低優先權的每次重新排隊從最後面，高優先權的的可以從中間開始
{%youtube NvJf9ZQb-TM%}

## ch05 多核心演算法
### ch05-01-為什麼要同步？
如果不同步的話，或有「重複寫」的問題
{%youtube WHdNLHxQUkc%}


- 一致性問題

- semaphore 適用於需要等比較久的
- 等 I/O
- 等 child process
- 在同一 cpu
### ch05-02-什麼是正確，簡單來說就是平行化版本和單核心版本的結果要一樣，race condition就是執行結果的順序與事件（如執行）順序相關
{%youtube ha2p_XRr1k4%}

### ch05-03-滿足CS的三條件
滿足CS的三條件，及制訂這三個條件的原因為何
{%youtube CRtu0JmhMcY%}

### ch05-04-Peterson's solution的前提。
對記憶體的讀取和寫入都是atomic operation
{%youtube hvKgjfGSLT4%}

- atomic operation
- load
- store
- 執行於不同cpu不會因為各自cache memory address不同，而讀取寫入不同的結果
### ch05-05-race condition的詳細解釋
{%youtube F9SkB_eYjXU%}

### x86-Arch-01-為什麼要了解計算機結構。CPU執行一個指令和同時執行10個指令對軟體來說使用率都是100%，但透過perf可以知道目前一次執行多少指令。並且為何每週期的
{%youtube L3uCtaRRPHg%}

### x86-Arch-02-為什麼要分成front-和beck-end。在古老時代使用組合語言寫程式，並且記憶體較貴，但精簡指令集更易於硬體優化，因此x86在前端將指令編譯成精簡指令
{%youtube tMsS7HdzpEM%}

### x86-Arch-介紹fron-end，使用virt. addr.存取x86指令，並且使用分支預測和堆疊引擎分別對if-else和函數的return進行優化
{%youtube -_Xy3ooM438%}

### x86-Arch-04-backend，當指令所需要的資料準備好，並且運算器（如加法器）剛好閒置，就可以執行該道指令，這是out of order execution。實體暫存器數量較邏輯暫存器
{%youtube EDTUxdPGTYE%}

### x86-Arch-05-在data cache的部分，load和store各自有buffer因此這二個指令通常不是atomic，L2 cache可能會外接core-to-core的通訊
{%youtube nCjMPBOqYoA%}

### ch05.06-Peterson's solution，這裡是做程式碼的解說，並需要想像，這樣的程式是會平行執行的，例如二個執行緒。必須假設load和store是atomic
{%youtube Nqk6yz1Mhdo%}

### ch05.07-證明，bounded waiting最難證明，重點在於重新執行一次的人，會執行「讓」的程式碼，而另外一個人一直在等待，不會再「讓」
{%youtube CbEBGF4PD5E%}

### ch05.08-對調turn與flag，這個結果很「嘿嘿」，會錯。因此在實現時必須限制處理器和編譯器的優化
{%youtube kqICBdLl0hM%}


### ch05.09-對調以後，證明會出錯。說明在原本證明哪個地方在對調後不滿足
{%youtube vR64rlanglI%}

### ch05.10-使用C11實現，在這裡我們使用最簡單的atomic operation，不考慮memory order方面的優化
{%youtube _tKtSg4TUUs%}

### ch05.11-Peterson's solution的小結論。
50個字。50個字。50個字。50個字。50個字。50個字。50個字。50個字。50個字。
{%youtube wYgy7acodFo%}

- semaphore
- 還沒進入cs前，可以作無意義的運算來測試能不能進cs
- 需要等很久的會要先讓別人
### ch05.12-semaphore與spinlock的不同。
semaphore在鎖不到資源的時候會ctx-sw
{%youtube _VHlKUGt7BA%}

### ch05.13-使用銀行轉帳當範例，沒有同步會如何。嘿嘿，這是哪家銀行，這麼佛心
{%youtube BxzPotJu92c%}

### ch05.14-只使用一顆處理器實現銀行轉帳問題，在這一連串的例子中我們可以發現，只有一顆處理器速度最快。但如果overhead降低，處理器非常多，那麼平行化還是比較
{%youtube OrXl7aMQXpo%}

### ch05.15-使用直觀方法解決轉帳的同步問題，如果沒有使用atomic直接寫Peterson's solution結果往往是錯的
{%youtube 28g4Hfo7Eo4%}

### ch05.16-幾乎是對的，以Peterson's solution為基礎。其中一個while我打錯字
{%youtube 8e6DmsEII7Q%}

### ch05.17-二個atomic operation會是對的嗎？在這個例子中有一個是對的，一個是錯的。但在大部分情況下通常一連串的atomic還是會有race condition
{%youtube sgKC6IAa64w%}

### ch05.18-semaphore的定義
「0」代表沒有人可以進去critical section（CS），「-x」代表有x個人在等。「+x」代表可以有x個人同時進去。
{%youtube YYt87HZwNEc%}

### ch05.19-在Kernel如何實現semaphore。
大致上就是自己把自己放入waiting queue，呼叫scheduler，醒來時檢查一下為什麼醒來（timeout? 真的等到？）
{%youtube rNlqt4fL0NM%}

### ch05.20-真的只是練習，用semaphore解決「生產者、消費者」問題。這個解法最大的問題在於semaphore的速度很慢，用了三個semaphoe會「很」拉低速度。
{%youtube t_6N_wBmP7w%}

### ch05.21-介紹readers-writers問題。
在計算機中，大部分只會對變數進行讀取，少數人會寫入，因此對讀取做優化是很有意義的。如果「會讀又會寫」，那就是「寫」
{%youtube 3bKTl7RMii4%}

### ch05.22-mutex
mutex不只是0-1-sem，semaphore中引入了一個重要的觀念「誰，目前鎖定lock」，根據「誰」做一些額外的事情
{%youtube Z_zujjTktos%}

### ch05.23-使用古老的 "test_n_set"。
基於歷史原因，CPU都會支援這樣的指令，但在多核心的情況下，這個指令的效率很差。
{%youtube 9I1OMdNZkoU%}


- atomic 只要更新大家都看得見
### ch05.24-使用較新的方式 test+test_n_set
即atomic_compare_exchange()，這是C11的規範喔
{%youtube A3RRalkSTzw%}

### ch05.25-用新的方法，多個CPU轉帳更快
{%youtube gAk7m-0WGDI%}

### ch05.26-介紹一下小技巧。在compare_exchange()前面，自己寫一個回圈不斷的檢查lock的值
{%youtube HXTidoPOvek%}

### ch05.27-『本週作業』活用compare_exchange。
在「Lock」中放入行員的編號。假設行員的員工編號一定不會有「0」
{%youtube 9azoWaTd6ag%}

### ch05.28-什麼是test+test_n_set
{%youtube GsDc1EU-sNU%}

### ch05.29-spinlock只能用在共享記憶體系統，例如是「nonuniform memory access」（高階電腦）、「uniform memory access」(多數電腦架構）
{%youtube bTiBZu2tVIs%}

### ch05.30-CPU內部core之間的溝通結構。
有可能是格狀網路、樹狀、環狀、crossbar、不規則形狀。core間的溝通速度和結構有關
{%youtube 3I-mpaIn4b4%}

### ch05.31-cache coherence，重點在核心可以直接對其他核心溝通，不需要透過記憶體。因此spinlock在設計的時候要考慮溝通成本
{%youtube EmvCg0M-XTI%}

### ch05.32-所有會存取記憶體的裝置都需要加入「一致性協定」，確保所有裝置看到的「內容」是一樣的，現在最新的內容不見得在cache或者DRAM
{%youtube 3yxy0opmw40%}

### ch05.33-硬體如何實現atomic op，鎖定的越細「代價」越高，但平行度也越高，當core的數量很多時，我們寧願選擇「代價高」但「平行度也高」的方法。
{%youtube adisD8eNC6g%}

### ch05.34-更詳細的說明test_n_set和test+test_n_set。主要的原因是前者會不斷的更新「lock」，後者則是當「lock」發生改變，試著去搶lock（設定為「1」）
{%youtube uiDu2qXk_kA%}

### ch05.35-spinlock的設計及使用的「心法」。
1. 先改變鎖的狀態，再檢查。
2. 硬體支援同時檢查和鎖上。如果「搶先」（preempt）是單方向，可以透過disable，但注意方向

{%youtube TqpPoPZ04Co%}

## ch0x.1.1-期中總複習
{%youtube X4hPphLb9E4%}

## 10.31
{%youtube 4KR0E2YFozw%}

## 重點整理
### 1. 什麼是 dual mode operation
> 由CPU提供的雙模式執行
> kernel mode : 可以對硬體 ==（RAM、控制暫存器）== 做任何變更
> user mode : 只能對被 kernel 分配到的有限硬體做變更，如==有限的RAM==和==普通運算所需的暫存器==
> [name=張聖岳][time=Mon, Nov 4, 2019 10:12 AM]
### 2. 為什麼需要 dual mode
> 對Hardware重要的resources實施protection，把可能引起危害的一些機器指令，設為priveleged instruction，如此可防止user program直接使用這些指令，避免user program執行這些指令對系統或其它user造成危害
> [name=張聖岳][time=Mon, Nov 4, 2019 10:14 AM]
### 3. 記憶體與 CPU 怎樣設定權限
> CPU將連續的記憶體（AMD可以動態配置）分成==一個個page(4k)或者較大的huge page或者不定大小的segment==的單位，每個單位都有一個==屬性==說明這是屬於kernel space還是user space
> kernel space ： 只有在 CPU 執行於 kernel mode 可以存取
> user space ： 只有在 CPU 執行於 kernel mode 或 user mode 時能存取
> [name=張聖岳][time=Mon, Nov 4, 2019 10:24 AM]
### 4. 只有 kernel 可以存取硬體，如何實現 system call 使得「核心這個函數庫」只有一個進入點
> 當user mode 發出 system call，
> syscall 組語的前置作業有讓OS初始化==RIP(通常是 system call 的進入點)== 和切換到user mode
> kernel space 只有一份核心函數庫，由 kernel 協調user space與暫存器的相關參數，再呼叫核心函式庫。
> [name=張聖岳][time=Mon, Nov 4, 2019 10:32 AM]
### 5. signal 對 system call 的影響為何
> 當system call遇到signal會有兩種狀況
> 1. 忽略signal。但遇到fatal error需要kill process時不能忽略
> 2. 先處理signal 再 restart
>
> [name=張聖岳][time=Mon, Nov 4, 2019 11:56 AM]
### 6. 能否從 context switch 和 mode change 說明 monolithic kernel 的優點
> monolithic kernel 大部份的功能設計於kernel mode，有效地減少context switch和mode change的overhead時間，模組間的溝通成本僅為function call
> [name=張聖岳][time=Mon, Nov 4, 2019 1:51 PM]
### 7. 主記憶體的三個用途
> - cache memory
> - disk和SSD內容
> - fs的metadata
> - buffer memory
> - I/O 資料轉換
> - CPU速度>周邊裝置
> - program memory
> - 分配給程式的記憶體
> - malloc
> - mmap
> - 執行檔必須載入主記憶體
>
> [name=張聖岳][time=Mon, Nov 4, 2019 1:57 PM]
### 8. 將系統中所有的資源映射成「檔案」
### 9. 對檔案有完整的權限
### 10. 例如：能否說明藉由這些機制，如何限制「印表機」的使用量？
> 將印表機驅動執行權限設定為使用者，cpu time 先檢查這個log檔，I/O時將每個使用者列印的資訊依照UID紀錄到log檔
> [name=張聖岳][time=Mon, Nov 4, 2019 2:12 PM]
### 11. Port I/O和memory mapped I/O各自是什麼？
> Memory mapped I/O的特點是DRAM和I/O device共享同一個內存地址，cpu可以藉由存取某個DRAM地址來存取I/O
> Port I/O則是DRAM和I/O device獨立開，藉由綁定某個port和指令來存取I/O device
> [name=張聖岳][time=Mon, Nov 4, 2019 2:34 PM]
### 12. 目前memory mapped I/O是主流，請自行上網找一下MM i/o的優勢
> MM I/O只需要找到mapped的記憶體，較快且擴展性較高
> PM I/O如果要擴展，可能需要動到處理器巨集
> [name=張聖岳][time=Mon, Nov 4, 2019 2:16 PM]
### 13. 為什麼要用DMA
> 因為用CPU傳輸成本比較高，資料搬移只需要幾個簡單的計數器，交由DMA以讓CPU可以去做更複雜的運算。
> [name=張聖岳][time=Mon, Nov 4, 2019 2:39 PM]
### 14. 為什麼硬碟裡面要有DRAM
> - 拿來做cache用
> - 成本較SRAM低
>
> [name=張聖岳][time=Mon, Nov 4, 2019 2:39 PM]
### 15. DMA有burst mode、stealing mode優缺點是什麼，自己上網找
> DMA控制器可以在burst mode和stealing mode佔用bus，這段時間CPU處於停止狀態
> 好處是比較不會有資料不一致的問題
> 壞處是傳輸較慢
> [name=張聖岳][time=Mon, Nov 4, 2019 3:23 PM]
### 16. 記憶體一致性問題，在這個地方首次出現
> - (DEV$\Rightarrow$CPU)用cache coherence演算法自動將DMA傳輸更新到cache
> - 清空cache以確保讀到的資料從主記憶體開始讀
> - (CPU$\Rightarrow$DEV) CPU直接寫到記憶體（write-through或noncacheable）
> [name=張聖岳][time=Mon, Nov 4, 2019 3:01 PM]
### 17. 中斷是啥，用流程來解釋
> DMA做完時用中斷通知CPU
> ```graphviz
> digraph interrupt{
> {rank=same
> DRAM[label="Memory System"]
> IO[label="I/O device"]
> }
> CPU->DRAM->IO[label=DMA dir=both]
> IO->CPU[label=interrupt]
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 3:34 PM]
### 18. Polling和中斷各有優缺點，舉個例子
> kernel 之於 interrupt 是被動的，適合需要立即做讀寫的高速裝置，如硬碟、網卡
> 相較而言，kernel對於polling是主動的，可以視負載情況調整頻率，適合滑鼠、鍵盤等的低速裝置會在短時間做出大量變更的裝置
> [name=張聖岳][time=Mon, Nov 4, 2019 3:45 PM]
> 網卡在高負載下不會變成polling嗎？
> [name=劉庭聿][time=Mon,Nov 4,2019 3:49 PM]
> > 會是interrupt+polling，也可能切換polling
> > polling可以搭interrupt的便車
> > 應該是適合的case做調整
> > 一般來說，網卡需要做高速處理
> > 切換polling應該是為了避免阻塞
> > [name=張聖岳][time=Mon, Nov 4, 2019 3:49 PM]
### 19. 為什麼要把驅動程式分成top half（中斷）和bottom half（kernel thread）
> top half 在執行時對使用者沒有反應，如果有重要的東西進來可以丟給kernel thread，kernel 會回傳給使用者合理的回應。
> [name=劉庭聿][time=Mon,Nov 4,2019 3:49 PM]
### 20. 巢狀中斷有何好處
> 可優先執行高速裝置的中斷。
> [name=張聖岳][time=Mon, Nov 4, 2019 3:53 PM]
### 21. 什麼SMT，主要優點是啥
> 在處理器上模擬n個處理器，cost是logical register 增加n倍，但可以更有效利用處理器的function unit 提升效能。
> [name=劉庭聿][time=Mon,Nov 4,2019 3:55 PM]
### 22. 什麼是bigLittle，主要優點是啥
> 有高效能和低耗能的核心供OS調換，兼顧省電與效能
> [name=張聖岳][time=Mon, Nov 4, 2019 3:55 PM]
### 23. 8條記憶體，組成二個獨立通道（NUMA），和8條記憶體組成超寬的通道（UMA）有什麼樣的不同？
> UMA:只有一套記憶體插槽，如果核心數增加的話，記憶體頻寬會是效能瓶頸
> NUMA:擁有多套記憶體插槽，同時拉高頻寬，又可以獨立控制。
> [name=劉庭聿][time=Mon,Nov 4,2019 3:58 PM]
### 24. 為什麼要有BIOS（firmware、ROM）
> 因為作業系統載入時，需要先做init的daemon，來喚醒驅動程式。
> [name=張聖岳][time=Mon, Nov 4, 2019 3:56 PM]
### 25. 為什麼CPU一開始的時候沒有啟動cache memory，必須手動啟動？
> 一開始不知道哪些位只屬於I/O哪些屬於主記憶體，如果這時候打開Cache Memory，CPU讀寫都在Cache，無法初始化裝置。
> [name=劉庭聿][time=Mon,Nov 4,2019 4:00 PM]
### 26. 稍微背一下，怎樣從組語在螢幕上印出"世界好"
>```cpp=
> char *hello = "世界好";
> long len=strlen(hello)+1;
> __asm__ volatile
> (
> "mov $1, %%rax\n" // write system call number
> "mov $2, %%rdi\n" // fileno: stderr
> "mov %1, %%rsi\n" // buffer
> "mov %2, %%rdx\n" // len
> "syscall\n"
> "mov %%rax, %0"
> : "=m"(ret)
> : "g"(hello),"g"(len)
> : "rax", "rbx", "rcx", "rdx");
>```
>[name=劉庭聿][time=Mon, Nov 4, 2019 3:42 PM]
### 27. 什麼是vdso，用例子、流程說明
> 如果system call不會牽扯到安全性，可以將部分資訊寫在user space，讓程式能夠以function call的方式取得。
> 第一次，產生syscall，libc 紀錄 function 的值
> 第二次，libc直接回傳
>[name=劉庭聿][time=Mon, Nov 4, 2019 3:46 PM]
### 28. 哪些東西可以用vdso實現？
> _vdso_time、_vdso_getcpu、getpid
>[name=劉庭聿][time=Mon, Nov 4, 2019 3:46 PM]
### 29. 用流程說明：trap and emulate的VM技巧
> 假設Guest OS,Guest app都執行在user mode
> 當Guest OS, Guest app都執行於「真實」user mode。
> privilege instruction會切換到「真實」的kernel mode。
> Virtual machine模擬出該指令對virtual machine該有的影響。
> 
> [name=劉庭聿][time=Mon, Nov 4, 2019 4:03 PM]
### 30. 解釋一下為什麼guest OS能支援VM最好(hint:balloon device)
> 先增加OS記憶體壓力，促使OS釋放不需要的記憶體
> [name=劉庭聿][time=Mon, Nov 4, 2019 4:03 PM]
### 31. 為什麼要有ASLR，舉例說明（return to libc）
> 為了避免惡意程式入侵，libc內有一個system函數，因為這個函數可以執行bash，如果沒有ASLR，server很容易被入侵
> <font color="red">如果沒有ASLR，常用函數會被放在固定地方，所以駭客只需要讓return address指向那裡就可以執行，用stack overflow塞就行</font>
> [name=劉庭聿][time=Mon, Nov 4, 2019 9:47 PM]
### 33. 想像一下，如果沒有ASLR，系統可以做什麼樣的優化
> 可以將常用函數庫放在同一個位置，呼叫的時候不需要context switch，不需要切換常用函數庫，可以提高執行效率。
> [name=劉庭聿][time=Mon, Nov 4, 2019 9:48 PM]
### 34. Linux中，context switch在哪邊？
> context switch 在kernel mode
> [name=劉庭聿][time=Mon, Nov 4, 2019 9:50 PM]
### 35. Linux中的waiting queue分成二種，說明這二種在signal上的差異
> 分為可中斷與不可中斷
> 可中斷：可被signal中斷，中斷完必須重新執行
> 不可中斷：不可被signal中斷，但是還是可以中斷 ex.kill(9)。
> [name=劉庭聿][time=Mon, Nov 4, 2019 9:57 PM]
### 36. I/O vs. CPU bound
> I/O-bound process:做I/O的時間遠高於CPU的process，如ftp。
> CPU-bound process:做CPU運算的時間遠高於I/O的process，如影像處理。
> [name=張聖岳][time=Mon, Nov 4, 2019 4:00 PM]
### 37. 傳統UNIX設定I/O的優先權較高，為什麼
> 希望CPU可以馬下完指令讓I/O開始動作
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:04 PM]
### 38. 能否舉例說明，設定CPU bound較高造成什樣的結果
> 會做完所有process的CPU才開始作I/O
> [name=張聖岳][time=Mon, Nov 4, 2019 4:01 PM]
### 39. Thread比process的context switch有效率，其主要原因為何？
> Thread間幾乎共用所有資源，尤其是記憶體，且可以互相存取堆疊
> [name=張聖岳][time=Mon, Nov 4, 2019 4:02 PM]
### 40. 在Linux的核心資料結構中，thread大概長成什麼樣子？
>
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:04 PM]
### 41. Nonpreemptive OS vs. preemptive OS vs. preemptive kernel
> Nonpreemptive OS：task執行完自願釋放CPU，OS才能把使用權給其它task
> preemptive OS：當task執行太久，OS會把CPU控制權交給下一個task
> preemptive kernel：task執行在kernel mode有可能還沒完成就context switch
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:09 PM]
>
> preemptive kernel：task執行在kernel mode，如果沒有做 ==lock== 的 task，context switch 可能在執行時會發生
> [name=張聖岳][time=Wed, Nov 6, 2019 12:31 PM]

### 42. 舉一個流程或應用程式，詳細說明在什麼樣的情況下Nonpreemptive OS的效能比較好
> 所有的程式都沒有bug，程式使用完CPU都把CPU釋放出來，使用過久自覺性的釋放CPU。 ex.netware
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:10 PM]
### 43. 怎樣預測一個行程接下來的執行時間？
> 依照task以前的執行時間，預測這次使用這次使用CPU的時間
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:11 PM]
>
> 紀錄前一回合的時間，在依據cpu執行n次的時間與上一次的時間進行權重加總
> 如: $T_{n+1} = \alpha t_n + (1-\alpha) T_n$
> Linux 的 $\alpha$ 預設為 $\dfrac{1}{2}$
> [name=張聖岳]][time=Wed, Nov 6, 2019 5:27 PM]
### 44. 怎樣設定round robin的time slice的長度，使得回應時間好，而且I/O也很棒？
> 設定為：大多數的task 可以在一回合（time slice）的時間內「變為等待」。
> time quantum 設定為 8
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:12 PM]
### 45. 說明2.4的多核心架構中，為什麼效率低
> 多個CPU共用一個run queue，當有task需要使用的時候必須鎖run queue，scheduler每次都要對所有task算好寶寶指數（goodness），形成效能瓶頸。
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:13 PM]
### 46. 稍微解釋一下，在Linux中的priority（nice）和真正的priority的不同
> 我不知道這題ＱＱ
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:13 PM]
>
> Linux 優先權分成140個等級（0~140）
> - (0~99) real-time priority
> - (100~139) nice value
>
> 使用者可以設定 nice value （-20~+19）
> 這個nice value會被OS參考，考量核心、mult-thread、bound、省電、效能的特性，最後得出的 dynamic priority 才是真正的 priority。
> [name=張聖岳][time=Wed, Nov 6, 2019 7:48 PM]
### 47. 2.4如何提高I/O效能
> 將執行時間分成很多的epoch，當沒有task時就切換到下個epoch，切到下個epoch時，添加所有task 的time slice。
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:14 PM]
> 當在runable queue的task的time slice已經都要用光時，為了避免CPU idle,要切換到下一個epoch,重新發分配優先權
> 公式： $timeSlice_{new} = timeSlice_{old}/2 + baseTimeSlice[nice]$
> 這樣可以讓原本還在工作的task優先權不低於新的
> [name=張聖岳][time=Wed, Nov 6, 2019 8:03 PM]
### 48. 為什麼上個世代所累積的CPUtime要打對折？打0.7折可以嗎？
> 為了要讓每次回來的time slice變小，0.7折應該可以
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:15 PM]
### 49. 說明2.6的多核心排程的架構上的優勢
> 每個CPU都有自己的run queue。因為在自己的run queue挑，不會因為運算增加，task 增加時間複雜度也增加。
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:32 PM]
### 50. Linux所稱的「fully preemptable kernel」是啥意思？
> 整個kernel都是preemptable，如果有lock，只有那一區間是nonpreemptable，等到unlock之後，又會回到preemptable。
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:33 PM]
### 51. 怎樣達到O(1)
> 原本是O(lgn)經過硬體優化達到O(1)
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:34 PM]
>> heap的search不是O(n)嗎?
>> [name=張聖岳][time=Wed, Nov 6, 2019 10:56 PM]
>
> 因為優先權只有140個等級,所以可以進行優化。
> 兩個linked-list陣列（大小140）,一個存CPU執行完的一個CPU未執行完的task
> CPU未執行完的優先權高的開始執行,優先權一致用run-robbin排程(O(1))
> 完成存入完成的陣列等I/O,會重新計算優先權（重點整理52）
> 做完I/O再直接swap指標
> $\Rightarrow 140\times O(1)+3=O(1)$
> [name=張聖岳][time=Wed, Nov 6, 2019 10:57 PM]
### 52. 怎樣對I/O進行優化
> 利用sleeptime進行優化，interactivity of a task=1/sleeptime（對I/O-bound有利），等待時間越久提升越多，最高提升到5
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:36 PM]
### 53. CFS的優點是啥（可以從網路上查查看）
> 每次都檢查如果當前行程不在黑紅樹的左側，就被替換掉，在高負載的伺服器上，通過調整能夠得到更好得排程效能。
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:39 PM]
### 54. CFS怎樣優化I/O
> 設定I/O vruntime為min_vruntime-Δ，Δ>0，Δ數值越大，優先權越高
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:40 PM]
### 55. 在CFS中可以提高task的優先權，讓他絕對高過I/O嗎
> 不能，提高的優先權有限。
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:41 PM]
> return 回 CPU 的I/O優先權高於當下的task
> [name=張聖岳][time=Wed, Nov 6, 2019 11:45 PM]
### 56. 什麼是race condition
> 兩個以上的行程共用一個資源時，再進行存取時因為順序不同，導致結果不一致
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:43 PM]
> 結果與順序成高度相關，造成結果一致性錯誤。
> [name=張聖岳][time=Thu, Nov 7, 2019 12:33 AM]
### 57. 說出一種解決race codtion的解法（詳細）
> 使用critical section的概念，critical section是操作共通資料結構的程式碼。需要滿足三個條件，分別為：mutual exclusion, progress, bounded waiting
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:48 PM]
### 58. Critical section要滿足哪三個條件
> mutual exclusion
> progress
> bounded waiting
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:48 PM]
### 59. 對這三個條件的「必要原因」進行說明
> mutual exclusio(互斥執行)：如果有一個task在critical condition，其他的不能進去
> progress：如果當下沒有task在critical section，則讓想進去的task進去
> bounded waitong：如果有task想進去critical section，不能讓他等太多次。不能只有只有特定的task進入crirical section。
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:53 PM]
### 60. 有辦法把程式碼給上註解嗎？
>```cpp=
>while(1) //p0 想一直進入cs
>{
> flag[0] = true; //p0 想進去cs
> turn = 1; //如果p1也想進去cs，讓p1先
> while(flag[1] = true && turn = 1) ;
> //如果p1優先權較大，且也想進入cs，就做出wait
> /* cs */
> flag[0] = false; // 離開cs，表示p0 不需要待在cs
>}
>```
> [name=劉庭聿][time=Mon, Nov 4, 2019 10:54 PM]
### 61. 有辦法說明如果不使用C11的話，那邊可能會錯嗎？
> 在flag[0], turn 的地方會有錯誤
> [name=劉庭聿][time=Mon, Nov 4, 2019 11:01 PM]
>
> C11版本以前，不支援autoic operation，記憶體優化時可能會把程式碼位置對調
> [name=張聖岳][time=Thu, Nov 7, 2019 1:17 AM]
### 62. 解釋讀寫問題
> reader：只能讀取
> writer：能夠讀取跟存取
> 能夠同時有多個reader讀取同一資料結構
> reader跟writer不能同時存取同一資料結構
> 同時不可以超過兩個writer存取同一資料結構
> [name=劉庭聿][time=Mon, Nov 4, 2019 11:24 PM]
### 63. 說明semaphore的定義，在使用上的「語意」
>wait/lock
>```cpp=
> wait(S)
> {
> while(S <= 0);
> S--;
> }
>```
>spin/unlock
>```cpp=
> signal(S)
> {
> S++;
> }
> ```
> [name=劉庭聿][time=Tues, Nov 5, 2019 2:00 AM]
>
> 當p想進入cs，會呼叫wait(),預計佔用一個lock,所以當前lock$\leq$ 0時,需要等待要unlock的執行緒發signal來釋放lock
> [name=張聖岳][time=Thu, Nov 7, 2019 1:49 AM]
### 64. 在實作上，為什麼semaphore會有queue？
> 等待裝置、資源
> [name=劉庭聿][time=Tues, Nov 5, 2019 1:57 AM]
### 65. Semaphore和spinlock的差異？
> semaphore：lock失敗會觸發context switch，context switch會耗費CPUtime ==(sleep)==
> spinlock：lock失敗會loop等待。loop過久也會浪費CPU time ==(busy waiting)==
> <font color="purple">spinlock缺點：如果有人拿到lock，但是被context switch，其他人還是會繼續等。</font>
> [name=劉庭聿][time=Tues, Nov 5, 2019 2:00 AM]
### 66. 反正mutex和semaphore的差別很大
>
> | mutex | semaphore |
> | ---- | --------- |
> | 只有一個lock | 有#MAX_LOCK |
> | 保證同一變數不會被兩執行續同時更動 | 保證執行緒間的同步 |
> [name=張聖岳][time=Thu, Nov 7, 2019 2:18 AM]
### 67. 能說明mutex基於owner觀念所延伸出的優化
> owner 的概念是可以知道是被哪個core鎖住，可以衍伸出幾個優化
> 這裡列三個
> 1. 優先權繼承
> - 當L進程被lock住，還在做讀寫，優先權更高的H進程進來了。
> - L可以暫時繼承H的優先權
> 2. 巢狀鎖定
> - 可以選擇支援或者不支援
> - 可能在L被lock住時，又有另一個程式區段需要lock L
> 3. 自適應鎖(adapted mutex)
> - p與q競爭mutex，p想要mutex
> - 情況
> - p、q在不同處理器
> - q還在workqueue(還在做I/O)，p sleep(不等)
> - q不在workqueue(在做運算了),p buzy waiting(等)
> - p、q在同一處理器，p sleep(不等)
>
> [name=張聖岳][time=Tue, Nov 5, 2019 9:39 AM]
### 68. 所有存取記憶體的「執行體」必須做「一致性」
### 69. 設計spinlock的基本心法為何？
> 1. 先改變鎖的狀態，再檢查。
> 2. 硬體支援同時檢查和鎖上。如果「搶先」（preempt）是單方向，可以透過disable，但注意方
>
> [name=張聖岳][time=Tue, Nov 5, 2019 2:11 PM]
### 70. 說明「禮義廉恥」的定義？為何此為國小之共同校訓？
### 71. 當只有「X」可以preempt「Y」要製造「平價」的critical section，請問要怎樣做？
> Y disable X，為了避免Y在cs時被X搶先
> [name=張聖岳][time=Thu, Nov 7, 2019 2:49 AM]

## 考古
### 中正，獨孤派作業系統，2018，期中考
共 25 題，每題四分
#### 1. 現代化的作業系統的安全性相當的依賴硬體所提供的支援。CPU 執行於二種模式 kernel mode 與 user mode，記憶體則分為 user space 及 kernel space。1) 請以表格畫出存取權。 2) 請大致描述一下，user mode application 如何存取 kernel 所提供的系統呼叫。（hint：系統的進入點是？模式切換？一起？） 3) kernel 如何切換回 user mode？（接下來要執行的程式碼？模式切換？一起？）
1.
> | | user space | kernel space |
> | -------- | -------- | -------- |
> | user mode| |V|
> | kernel mode|V|V
2.
> x64：user mode切換到kenel mode是利用syscall組語
> syscall：同時做兩件事，設定RIP與切換到kernel mode
3.
> x64：kernel mode切會到user mode利用sysret
> OS會將返回位址放在特定的地方
> sysret：同時做兩件事，返回user mode程式碼位置，切換到user mode
> [name=劉庭聿][time=Tues, Nov 5, 2019 2:17 AM]
#### 2. Linux 提供的 system call 大部分是 blocking system call，如果某一支程式執行一個 blocking system call，並且已經於 kernel mode「等待某個事件」發生（例如：read 等待 I/O 完成），請問 Linux 如何處理 signal（例如：ctr-c）（hint：二種方式）
> 不處裡signal：繼續完成system call，等到system call結束之後再來處理signal
> 處理signal：該system call 失敗，通常作業系統等到處理完signal在重新執行system call
> [name=劉庭聿][time=Tues, Nov 5, 2019 2:17 AM]
#### 3. 請比較這二個名詞：1) context switch 2) mode change。請說明這觸發這二者的發生原因。再說明這二者哪一個的overhead 比較高。（hint：可以考慮 cache 所造成的影響）
> context switch：原本執行於process A，轉換到 process B
> mode change：process A原本執行於user mode，但是呼叫了但是呼叫了syscall，切換到kernel mode
> context switch overhead較高，因為context switch要切換cache。
> [name=劉庭聿][time=Tues, Nov 5, 2019 2:21 AM]
#### 4. 請說明 memory-mapped I/O 和 port-mapped I/O 的不同。（hint：可以用範例程式碼說明「或」圖示說明「或」說明二者的定址空間的差異）
> memory-mapped I/O
> 
> 將周邊暫存器記憶體映射到CPU的memory space
>
> port-mapped I/O
> 
> 使用特殊指令，將資料傳輸到特定的特定的port，port 和memory space 是分開定址空間
> [name=劉庭聿][time=Tues, Nov 5, 2019 11:12 PM]
#### 5. Ron 博士覺得下面這張圖很具有代表性， bufcache、bufRAM、bufdisk，這三者的資料應該要保持一致性。 1)請問在硬碟中為何要加上 bufdisk？當 disk 上的 µc（micro controller）將資料透過 DMA 傳輸到 DRAM 後 bufRAM、bufdisk 的資料就一致了。2) 處理器核心（core）存取 bufcache 請提出一個方法可以保證 core 可以讀到最新的資料（換句話說：必須保證 bufcache、bufRAM 的資料一致性）。（hint：有數種解決方式，比較直覺的是：直接用「☐ ☐ 解決」）
> 為了要讓Disk出來的資料可以加速，不拖慢bus的速度
>DEV->CPU：使用硬體解決，硬體會自動將DMA的資料更新到cache
>CPU->DEV：CPU在該記憶體區段時直接寫穿，直達裝置記憶體
> [name=劉庭聿][time=Tues, Nov 5, 2019 2:27 AM]
#### 6. 請畫出大約的流程圖說明中斷的處理流程，你的圖上面必須包含中斷向量表、interrupt service routine。並說明第#號中斷，怎樣找到它的 interrupt service routine。
> 
> 1.Device發出3號中斷
> 2.查詢中斷向量表
> 3.執行ISR
> [name=劉庭聿][time=Tues, Nov 5, 2019 11:15 PM]
#### 7. 請問 CPU 可以直接存取的最大的「儲存體是什麼」？為什麼 CPU 沒辦法直接用 disk 開機？（hint：這二者幾乎互相為答案 ^_^）
> CPU能直接控制DRAM跟ROM因為他們是byte addressable，CPU只要在address bus放要讀取的位置就可以讀取到資料。
> Disk是屬於block device，需要下達命令告訴磁碟要取的block，在寫到軟體指定的位置。
> 所以沒有軟體驅動的情況下，CPU無法直接存取disk
> [name=劉庭聿][time=Tues, Nov 5, 2019 11:24 PM]
#### 8. vDSO是Linux所提供的快速系統呼叫的方式。請問vDSO可以從user program直接存取、執行嗎？以clock_gettime()為例，說明 vDSO 的基本想法：1. 哪些東西可以用 vDSO 實現，2. kernel 怎樣保證使用者存取到的都是新的資料（hint：1. 我想 clock_gettime 本身就是 hint，clock_gettime 有何特別之處？ 2. 反正 kernel 本來就要定期更新系統時間，所以不如就...）
> 1.clock time 不是隱私資訊，不會牽扯到安全性
> 2.資料存放在vvar內，而且kernel本來就會定期更新系統時間，所以就順便更新user space。
> [name=劉庭聿][time=Tues, Nov 5, 2019 11:34 PM]
#### 9. virtual machine 中有一個技巧稱之為「trap-and-emulate」，請問哪些指令可以用這個技巧執行？（hint：guest OS和 guest APP 都執行於 user mode，只有 host OS 執行於 kernel mode，...）
> 特權指令
> [name=劉庭聿][time=Tues, Nov 5, 2019 11:36 PM]
#### 10. 請問 KVM 中的 balloon device 是用來協調什麼的？（hint：三杯水的故事）
> memory
> [name=劉庭聿][time=Tues, Nov 5, 2019 11:36 PM]
#### 11. 這一題上課沒教，授課老師也不確定答案，但如果是你，你要怎樣設計呢？</br>gcc -pg的功能可以在函數的開始位址插入特別的程式碼（例如：在Linux kernel中，插入「call function_trace_call()」），但這樣只能追蹤函數的進入點，但如果只是這樣，無法追蹤函數的「離開點」，如下圖 ftrace 可以追蹤到函數的進入點和離開點。你覺得 ftrace 怎樣辦到的？（Ron 博士覺得可以從 stack 下手，但要怎樣下手呢？）
>

#### 12. 如下圖，請說明 cooperative OS 和 preemptable OS 分別要在哪些時機點呼叫 scheduler？請填寫 cooperative OS和 preemptable OS 各會在哪些時間點呼叫 scheduler 的代號（複選）。
> cooperative os：1,2
> preemptable os：1,2,3,4,5
> [name=劉庭聿][time=Tues, Nov 5, 2019 11:44 PM]
#### 13. Linux kernel 2.4 讓所有的 CPU 共用同一個 runqueue，每次 CPU 要挑選 task 的時候，必須根據「適不適合」，對所有的 task 打分數。因為所有的 CPU 共用一個 runqueue，因此當一個 CPU 正在打分數時，其他 CPU 就必須「等待」。2.6 核心以後（不管是 O(1)或 CFS）都採用「一個更有效的架構」，讓 scheduler 變得更快。請說明新架構的優點（hint：就架構的缺點，所有 CPU 要對所有 task 打分數➔慢，每次打分數還要看這個 task 跟這顆 CPU 的交情怎樣➔慢，大家都鎖住同一個 runqeue➔慢）
> 每個CPU有自己的Run queue
> 當task從active 移到 expired 就會計算動態優先權
> 不需要Affinity
> active：放還沒用完的task
> expired：放用完的task
> put：cpu覺得自己的loading太重，給另一個
> pull：cpu覺得loading太輕，跟別人拿
> [name=劉庭聿][time=Tues, Nov 6, 2019 12:52 PM]
#### 14. 請用下圖說明 Linux kernel 2.4 怎樣讓 I/O bound 的 task 獲得更高的優先權（hint：2.4 中，time slice 大，就代表優先權高，因此...回填...有人有剩，有人沒剩...，所以補上以後...）
> 回填所有task的time slice，因為I/O還有上一個epoch沒執行完的time slice，回填之後time slice較高
> [name=劉庭聿][time=Tues, Nov 6, 2019 12:59 AM]
#### 15. Linux O(1) scheduler 比 2.4 好的地方就在於「打分數的方式」，2.4 的演算法即時每次打出來的分數都差不多，但每次都要重新打分數。請問 O(1) scheduler 做了什麼樣的改進，讓 scheduler 的效率有效的提升（hint：active array、expired array，sleep_time）
> active：存放time quantum還沒用完的task
> expired：存放time quantum用完的task
> active -> expirted打一次分數，分數依照上一回合的sleep_time
> [name=劉庭聿][time=Tues, Nov 6, 2019 1:02 PM]
#### 16. 「授課老師認為」CFS 最特別的地方是在「回填 time quantum」的部分。請問在 CFS 中，一個高優先權的 task 除了可以拿到更多的 CPU time 以外，還有什麼樣的好處（hint：這個好處就是 round robin 演算法的目標）
> 更好得respones time
> 執行密度高
> [name=劉庭聿][time=Tues, Nov 6, 2019 1:04 PM]
#### 17. 考慮 CFS，共三個 task 稱之為 a、b、c，這三個 task 分別可以拿到 1/2、1/4、1/4 的 CPU time，請以甘特圖畫出這三個 task 的執行過程（從時間 0 畫到時間 8）。假設一開始所有 task 的 vruntime 都為 0，如果 vruntime 相同時，優先權等級為 a>b>c</br>（hint: ）

#### 18. CFS 怎樣讓 I/O-bound task 拿到比較高的優先權？（hint：大家的 vruntime 會不斷的增加，所以從 waiting queue 回來的 task 要怎樣設定 vruntime？）
> min_vruntime是目前task最小的，將I/O bound設為vruntime或是vruntime-Δ
> [name=劉庭聿][time=Tues, Nov 5, 2019 2:34 AM]
#### 19. 在 2.4 scheduler 演算法中，如果一個 task 不斷地睡覺，那麼他會一直累積 time slice，而 time slice 越大，優先權也越大，要怎樣避免有人撰寫一個「睡大覺-醒來不幹正事-睡大覺-醒來不幹正事...」的程式，擾亂系統執行。（hint：1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ⋯ = 1）
> timeSlicenew=timeSliceold/2 +baseTimeSlice[nice]
> [name=劉庭聿][time=Tues, Nov 6, 2019 1:52 AM]
#### 20. 二個 CPU 分別為 CPU1 及 CPU2 各自對 global 做「加 1」，其 x86 組合語言相當於「① 載入 global 到 AX 暫存器、② 對 AX 做加 1、③ 將 AX 存回 global」，共三個步驟。請安排這二個 CPU 的指令執行順序，讓 global 的值為 2。（hint：錯開）
> 先執行其中一個CPU在執行另一個。
> [name=劉庭聿][time=Tues, Nov 6, 2019 1:55 AM]
#### 21. 請定義 race condition（hint：順序、時序、事件等...不一樣）
> 兩個以上的行程共用一資源，進行存取時因為執行順序不同，導致結果不一致。
> [name=劉庭聿][time=Tues, Nov 6, 2019 1:59 AM]
#### 22. Critical section 是解決 race condition 的方法之一，其想法就是讓存取共通資料的程式碼錯開執行。critical section 須滿足三個條件，分別是：mutual exclusion、progress、bounded waiting。如果我們不考慮 progress 和 bounded waiting的情況下，你是否可以給一個「簡單」的方法解決 mutual exclusion？（hint：一路綠燈）
> 讓一個程序一直執行，並且禁止另一個執行。
> [name=劉庭聿][time=Tues, Nov 6, 2019 2:01 AM]
#### 23. 下面是一個錯誤的 Peterson’s solution，其中有二行對調。請證明這個方法是錯誤的（hint：給一個 P0 及 P1 都能夠進入 CS 的例子）
> 
> 
> 
> [name=劉庭聿][time=Tues, Nov 6, 2019 1:52 AM]
#### 24. 下面是某同學實現的 Peterson’s solution 中的 P0 部分，但這樣實現是錯誤的。請舉一個實際的例子說明這樣的程式碼經過編譯器最佳化之後會發生錯誤。（hint：while（即：9 行）前設定 turn=1（即：8 行）；而 while 的控制變數又包含了 turn，所以編譯器可能會怎樣做呢？）
> 要使用atomic_store
> ```c=
> while(1)
> {
> if (flag0 != 1) jmp = true;
> flag0 = 1;
> trun = 1;
> if(jmp == true)goto out:
> out:
> }
> ```
> [name=劉庭聿][time=Tues, Nov 6, 2019 2:12 AM]
#### 25. 請比較楊過和令狐沖在獨孤劍法上的造詣。

###### tags: `OS`