OS

Intro 不需要把所有東西放進dRAM : 不是整支執行檔都會用到 Partial Loading Programmer不需要再考慮空間問題 降低每隻程式使用的空間 -> 更多程式同時執行 降低Swapping的成本 Virtual address space address從0到空間終點 Physical memory -> page frames MMU自動做位址轉換 VM空間遠大於physical memory 定址空間中允許hole的存在 : 支援動態分配(heap, stack) Demand paging Start 不會載入所有page 把所有page mark unloded Page fault 執行時access到還沒載入的page 這時才把對應的page載入 Page load 前面handle完之後繼續執行, 就像那個page一直存在 Page replacement swap到disk Swap算法 FIFO LRU : 使用過去經驗, Counter / Stack Second chance : FIFO + refernce bit (ref==0 才swap out) Enhanced second chance : 再加上dirty bit, 優先級為 $dirty < reference$ Optimal : 預測接下來最久用不到的, 使用LRU近似 Copy-on-write 每個process的shared memory都是同一份 做寫入時才會做複製 CoW -> fork(), no CoW -> vfork() Shared memory must zero out -> C裡面的global variable初始都是0 (BSS) Page replacement algorithm FIFO ...

Intro Load program : disk -> memory CPU能直接存取的只有Main memory, register Memory unit : addr + read request / write request Main memory可能需要很多CPU cycle : Stall Cache介於Memory與Register之間 記憶體管理的目標 性能 最大化利用記憶體 提升存取速度 保護 防止越界存取 保護資料 靈活性 動態分配 Responsiveness Context switch Address binding Compile-time binding Logical address -> known physical address Prehistoric / Embeded Load-time binding 程式載入memory -> 轉換physical address 靜態分配 Run-time binding 硬體支援(MMU) 動態分配 + Virtual memory -> 程式可以在任意address執行 Contiguous allocation Early method 通常拆成兩個partition : OS(通常在高address), 剩下的是Process 每個process分配到一個segment Relocation register : 防止越界存取 Base register : 最低address Limit register : 邏輯address上界 MMU 動態分配邏輯地址 破碎化問題 First-fit 或是 Best-fit Internal fragment : 分配到的chunk太大 External fragment : 總空間可以滿足request, 但是分散掉 First-fit analysis : 大約 $\frac{1}{3}$ 的memory沒辦法使用 -> 50% rule Paging Intro Process -> memory pages (4k/8k) Physical -> memory page frames (4k/8k) Page table 對每個process建映射表 Access某個address時, Page table上 Page number -> Frame number Page table base register : PTBR Page table length register : PTLR Page miss -> page fault, 從disk載入 Address translation Logical address Page number Page offset MMU自動做 logical address -> physical address 的轉換 問題 Internal fragmentation 位址轉換的overhead 透過TLB解決, 如TLB miss才去查page table (TLB為MMU的一部分) Page table占用的空間 Structure Types Sigle-level page table Multi-level page table Inverted page table : physical -> index Huge pages : larger page size Two-level paging : 對page table做paging ...

Intro 必須滿足以下所有條件 : Mutual Exclusion : 獨佔資源 Hold and wait : request不滿足時不會release現有資源 No preemption : 不能強制收回資源 Circular waiting : 存在round概念，每個process都在等別人 處理方式 Prevention 破壞mutual exclusion : 共享資源 破壞hold and wait : request之前先release Preemption : 強制收回 破壞circular waiting : 對Allocation設定線性順序 Avoidance Banker’s Algorithm 假定系統處在Safe state, 若分配後導致不安全，則拒絕 維護Available, Max, Allocation, Need, 其中 : $$ Need[i][j] = Max[i][j]-Allocation[i][j] $$ 流程如下 : Initial check $Request[i] \leq Need[i]$ $Request[i] \leq Available$ Tentative allocation 假設暫時分配如下(還沒分配) $Available = Available - Request[i]$ $Allocation[i] = Allocation[i] + Request[i]$ $Need[i] = Need[i] - Request[i]$ Safety check 搜尋安全順序 假設 $Work=Available, \quad Finish[i]=false$ 對所有process遍歷, 若滿足則 $Work = Work + Allocation[i]; Finish[i]=true$ 如果結束時所有 $Finish[i]=true$ 則系統安全 Allocate 檢查通過才會分配 Detection Single : 對RAG做拓樸排序, 如無法偵測到環則無deadlock Multiple : 檢查unsafe state (Banker’s Algo) Recovery Terminate process : 殺到沒有deadlock Preempt resource Ignore Modern OS ignore deadlock 使用者需要手動重啟Windows

Intro 多處理器處理同筆資料 同時寫入 -> 錯誤 Race condition problem 操作global的程式碼不應同步執行 Race contidion其中一解 : critical section Mutual exclusion : 同一時間只有一個task在CS Progress : 沒有task在CS -> 令其他task進入 Bounded waiting : 不讓其他task等太多次 Peterson’s solution 假設只有兩個task, 且支援atomic instruction, shared memory 概念可擴展到任意數量task Code: //Task 0 while(1) { flag[0]=1; //task0 want to enter CS turn=1; //in case task1 wants to enter CS while(flag[1] && turn==1); //wait for task1 //Critical Section flag[0]=0; } //Task 1 while(1) { flag[1]=1; turn=0; while(flag[0] && turn==0); //Critical Section flag[1]=0; } 註: flag與turn的設置不可對調，否則會產生同時在CS的情況 ...

Intro Multiprogramming : 為了獲得最大CPU使用率 CPU burst先，接著才是I/O burst 主要考慮CPU Scheduler 排程器在以下期間發揮作用 : Switches from running to waiting state Swithces from running to ready state Switches from wating to ready Terminate Preemptive & Non-Preemptive Preemptive : 排程器可以依據時間片/優先級搶佔CPU 主流，fast-responsive且資源共享 有race condition風險 Non-Preemptive : 排程只發生在指定情況(Terminate, Switch to waiting…) 只在Process釋放CPU時重新分配 設計上更簡單，但是poor-responsive Dispatcher Switch context Switch to user mode Jump to location in order to restart program Dispatch Latency Scheduling Criteria CPU utilization Throughput Turnaround time Waiting time Response time 排程演算法 FCFS First-come, first-served ...