CS3009 作業系統 Operation System

# CS3009 作業系統 Operation System Textbook: Operating System Concepts Abraham Instructor: 鄭欣明 Shin-Ming Cheng ###### tags: `TaiwanTech`, `CS` ## Ch1 * 作業系統是中間的媒介 * 將使用者需求轉譯成對硬體資源的取用 * 提升硬體使用效率 * 硬體－作業系統－應用程式－使用者 * resource allocator * control program * Interrupt Handling * polling: 一個一個確認對方 * vectored: 讓對方來中斷自己 ## Ch2 * system call: API * 安全、簡便 vs 效率 ## Ch3 * Process 程序 * text (program code) * data (global data) * heap * stack * PCB (Process Control Block) * State * new: 創建中，現在幾乎都可省略 * ready: 準備好執行（以前會避免ready的process太多） * waiting: 中斷保留，PCB的program counter紀錄執行位置 * thread 執行緒 * 一個Process中，共用text與data，但各自有stack和heap * Scheduling * Long-term scheduler * 每幾秒每幾分鐘執行一次，只能服務很少數量的程序，棄用 * degree of multiprogramming * Short-term scheduler * 以milliseconds為單位 * Medium-term scheduler * swapping: 記憶體滿時可能會將一些Process放進硬碟（PCB還在），未來再重新拿回記憶體中處理（所以記憶體滿載硬碟會開始轉） * Process Creation and Termination * fork: children process會完全複製parent process的所有資訊（新建PID） * zombie: * orphan: parent已終止，沒有wait() * 親屬關係避免記憶體被不知道沒有被清掉的程序佔據 ## Ch5 * IO等待與CPU運算速率不成比例 * Medium Term: swap * CPU Scheduler decision 發生時機 * running to waiting (nonpreemptive) * running to ready (preemptive) * waiting to ready (preemptive) * terminate (nonpreemptive) * SJF 純理論、不實際 * Real-time scheduling * 確保工作不被拖延 * soft real-time: 儘量在指定時間前完成 * hard real-time: 保證在指定時間前完成 * Priority-based scheduling * soft real-time版本支援preemptive * hard real-time必定確保達成死線 * 不行直接不服務 * Rate Montonic * 越頻繁要求的給越高的Prio * Missed Deadlines: $U=\sum_{i=1}{n}\dfrac{C_i}{T_i}\leq n(2^{1/n}......)$ * Earliest Deadline First * 理論最佳解（實際上應該要考慮中斷成本） * Linux Scheduling * 分多層的Prio * 在同一層待太久會自動提升 * nice value: 越高越後面、越低越前 ## Synchronization * 跨程序共用資料的同步問題 * race condition * 多個程序共用一個需要預期順序執行的資源 * 反言之設計共用資源應該要不論如何都具一致性 * CTF: 故意用錯誤的CPU排程時將會暴露出此類程式的漏洞 * Critical Section * 對共用資源讀寫的段落 * 各自保護 * 不能取決於Scheduling policy * Mutual Exclusion 僅限一程序執行 * 不同程序共用同一資源的Critical Section，只有一個能執行 * 進去與出來時必定有一個值來確保 * 如果用共用變數來確保Critical Section，那如何確保共用的變數？（套套邏輯，暫且不論） * Progress 必能選出一個程序 * 只有沒在執行其餘部分的程序能參與競爭 * 寫在entry和exit決定 * 決定必定能在有限時間解決 * Bound Waiting 每個程序必能執行 * 一個程序一定能在有限時間內進入CS * Algo 1 * 當優先權不在手上就一直空loop * 當執行完就將優先權丟給別人 * 不滿足progress: 對面不丟出優先權就永遠進不去 * 不滿足progress也就不滿足BW * Algo 2 * 設自己為是 * 看別人的狀態，是則等待，否則自己執行 * 自己執行完再將自己設為否 * 不滿足progress: 必須確保前兩行一起執行，否則會互相乾瞪眼（還是回到schedule問題） * Peterson's Combined Solution (2 processes) * 把兩個結合，把Algo 1的「turn設為對面」設在Algo 2的第一步與第二部之間 * 如果CPU替指令reorder最佳化可能會出事 * Lock * 作業系統提供的Library * 硬體支援 * Memory barrier * `memory_barrier()` * 告知指令reorder發生 * Hardware Instruction (atomic instruction) * `test_and_set` * 第一個進去的人鎖門 * 有Bound Waiting問題（反覆都是第一個人進去，不夠幸運的選不到） * `compare_and_swap` * Atomic Variables * `increment(&sequence)` * 從解決變數被interrupt解決問題 * 可以用`compare_and_swap`實作 * N processes solution * Bakery Algorithm * 設計抽籤比大小 * (a, b) < (c, d) * a < c OR (a = c AND b < d) * 先比抽號，再比process ID * 可能多個 process 同號，但 process ID 能確保總能輪流 * `test_and_set` w/ Bound Waiting * Mutex Lock (mutual exclusion lock) * 軟體工具，檢查開關 * `acquire()` and `release()` * busy waiting: 一直反覆確認Mutex Lock(Spinlock) * 同一個區塊只能有一個，同一個process上鎖與解鎖 * Semaphore * 軟體工具，檢查<=0 * `wait()` and `signal()` * 可以用來控制程序執行順序 * counting * 數值範圍沒有特定限制 * binary * 只有 0 和 1 * 只有一個process * 基本上和 mutex 一樣 * busy waiting * 優化 busy waiting: 給予串接 process 的能力，放置 waiting queue * `sleep()` in `wait()`, `wakeup()` in `signal()` * deadlock: 錯誤設置的 semaphore 加上執行順序導致卡死 * starvation: 無上限的 waiting * Priority 順序被介入 * Priority Inherirance: 把semephore中的優先級提升到與waiting中最高的一個一樣 * 資源的同步，可以有多個 process 進入，可以由不同 process 處理 * Monitor * 高階程式語言結構 * count 變成 private member，需要accessor介面 * 串接entry queue * 解決 dining philosophers problem * `pickup(i)` and `putdown(i)` * 發現自己現在不能動就釋放資源給別人 * **Q: 如何用 Semophore 實作 Monitor？** * **Q: 如何用 Monitor 實作 Critical section problem？** * 除非做過，建議跳過 ## Deadlocks * Bridge Crossing Problem * 必須有一方退讓 * 但誰讓？ * 大多數OS不處理 * System Model * 使用者 * 資源 * instance * process使用資源的流程 * Request * Use * Release * 用graph來表示 * no cycle: no deadlock * cycle: 進一步分析 * Handling * Prevention * 讓 preevtive 必然發生 * 讓 mutual exclusion 不存在（？？？ * Hold and Wait 一次只能拿一種東西 * No Preemption（？？？ * 沒有 circular waiting（？？？ * Avoidance: 逃開會進入 deadlock 的狀況 * 有更多資訊、紀錄系統狀態 * request 演算法避免unsafe * 管太多 * Deadlock 不發生太浪費資源，發生時糾錯才是現代解法 ## Memory-Management * main memory 是 CPU 唯一可以直接存取的記憶體 * 硬體查表取得資料 * Memory Protection * page: * invalid bit * point to same memory (share) * structure * 4 KB page table -> 4 MB memory * two-level * not enough?(64bit) more level * hash * page number 去 hash * hash 可以辨認資料傳輸間是否被竄改 * hash key 重複就 linked-list * inverted page table * 用一個超級大的page table讓所有process共用 * pid做indentify * 不能sharing ## Virtual-Memory Management * 只管理虛擬(page table)的資訊，不管對應方式或實體位置 * 專注於定址位置 * 不能保證實體記憶體容量確實到虛擬記憶體的量 * 需要仔細控管實體使用量 * 沒有必要的東西就不放到記憶體（不然就放在二級儲存體就好 * 降低I/O，降低記憶體空間，反應變快 * 遇到還沒load的東西？ * page table需要重新設計，區分不存在的page與在disk裡的page * lazy swapper 不用就不load、用完就丟出去的swapper * Valid-Invalid Bit * 確認這個page在不在記憶體 * Page Fault * 確認address合法性 * 找不到memory時找出disk位置然後load進frame並存到page table * 如果沒有free frame就要搞一個出來 * cost很高但不能不做（常態的40倍 * 盡量share，新增的page越少越好 * Free-Frame List * 存值的瞬間才清空原本的值 * 可以創造更多free frame * Page Replacement * 挑選一個最不可能再次發生Page Fault的踢掉 * Algorithm * 先列出接下來有哪些page被reference * FIFO: 最短Loading time，常常白做工，某些情況下增加frame反而導致fault rate上升 * Optimal: 最久以後用的踢掉，關鍵是如何預測 ## Mass-Storage * Mass-Storage: disk * logical blocks: 軟體層傳輸最小單位 * disk 排程 * ceek time: 約略就是 seek distance * bandwidth: 傳輸總量 * FCFS: 先來後到 * SSTF: 最短距離，一直有新請求時會導致比較遠區域的請求永遠沒執行到，常見 * SCAN: 選一個方向，觸底折返，讀取時間不平均 * C-SCAN: 單向繞圈 * SCAN系對於重負載系統有用 * C-LOOK: 不到底只到最後一個請求，不到頭只到第一個請求 * 也適合當作預設 * NVM scheduling * 沒有讀取頭 * 一次會讀一個block，可以安排資料儲存位置增加效率 * 要分兩個步驟寫入（垃圾收集管理可用空間） * Detection and Correction * parity bit * CRC * ECC * Management * physical formatting: 切分 disk 的 sector，通常是 512 bytes * Partition: OS 的分割 * root partition: dual boot * 在 boot 時 mounted * logical formatting: 文件系統 * OS 在硬碟有獨立區塊 * Swap-Space Management * DRAM不夠用時用Disk來頂 * 一直複寫一份到disk裡以防萬一？ * 真的發生不夠用時才寫到disk * 整個process放到disk * 動態區塊放到disk * 存取 * 本機存取可用光纖技術 * NAS * 網路上的檔案系統 * iSCSI協定 * Cloud * 不開完整檔案介面，需要藉由API * Storage Array * 擴充容量 * 擴充效率 * 儲存平行化 * 額外controller * Storage Area Network 常用 * RAID * 原本沒有打算提除錯能力而只有偵錯 * Solaris(Suns) 提出 ZFS 除錯格式 * 多個disk(多餘的空間)換得可靠性 * 擴充冗餘 * level 0: 沒有可靠性，就只是把資料平行分配到多個硬碟 * level 1: mirror，備份，兩倍寫入時間（要寫兩次），兩倍的空間要求 * 0+1 or 1+0 * level 2: 資料做 ECC encode，如 7,4 hamming code * level 3: sector 做 single parity bit * level 4: 把 parity 放在專門的 disk，回復比較慢，但有機會比較強 * level 5: 把 parity 平均放在各個 disk（不會放自己 disk 的驗證） * level 6: 兩組 parity chk，要多兩顆 disk * Snapshot: 備份目前工作狀態 ## I/O Systems * 種類繁多差異大 * 必然具備的通用訊號 * port: 硬體連接節點 * bus: 資料傳輸協定 * controller: 控制以上兩項，可能有自己的處理器與記憶體 * 光纖: 速度快但控制複雜，需要 host-bus adapter, HBA * 設備通常有四個 1-4 bytes 暫存器 data-in, data-out, status, control * polling: host 週期性向 device 主動要資料 * 讀取 device 暫存器 * 下對應指令 * 將 ready bit設為1 * controller設定busy bit * controller清除busy bit, errorbut, commend-ready bit * CPU排程不知什麼時候可以切回來 * Interrupts: 由 device 告知 CPU 工作完成 * Mask概念遮蔽特定中斷 * Kernel IO * Scheduling * Buffering: device傳輸資料存至記憶體緩衝 ## CH15 * NFS * 每層資料夾都要做遠端查詢 * 讀寫做buffer與cache，改動一次寫入遠端 --- ## 虛擬化 * qemu 架構（軟體） * 幫助虛擬化開源套件 * 類 VM，模擬 PCB * 把服務拆成不同 container（docker） * 不需要資源時可以回收部署 * 韌體模擬的問題 * 靜態分析誤報率高 * 只有虛擬，沒有真正的硬體設備，如何讀取不存在的東西 * 攻擊類型 * OWASP * 已存在於密碼表的密碼、預設密碼 * 非必要服務 * 未關閉的API（如Debug API） * 缺乏更新 * 不安全或過時組件 * 資料庫 * 資料加密 * 實體設備埠 * firmadyne * 動態模擬分析韌體 * 集成類工具 * 存取外圍設備時回傳 0 * 如何修改可以更像是真實設備？ * 只能使用他提供的kernal，沒辦法把真實環境的kernal丟進去用 * 實作流程 * 使用爬蟲／FTP取得韌體檔案 * 用 binwalk 提取 * 使用 firmadyne