---
# System prepended metadata

title: CS3009 作業系統 Operation System
tags: [CS, TaiwanTech]

---

# 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
