OS-CH4-Thread Management
Thread 為了讓同一程式可以同時處理不同工作。 是輕量級的Process OS 分配 CPU Time的基本單位 私有的組成包含 : Thread ID PC Register Set Stack 同一個Process 共享此Process的 (global)code/data section、OS Resource、… (考選) 表格 Private（每個 thread 自己有） Shared with other threads of the same process（同一 process 內其他 threads 共用） Program Counter (PC) Code section (text section) CPU Register Set Data section（global data / global variables） Stack Heap(指標) Local Variables Other OS resources（open files, signals, I/O resources, etc.） Thre...
OS-CH4-CPU Scheduling
Scheduling Critiiria and Goal CPU utilization : Process execution time / CPU Total Time CPU Total Time : Process exec Time Context Switch Time Idle Throughput : 單位時間內完成的工作數目 Turnaround Time : process 進入到工作完成的時間 = finished time - arrival time Waiting Time : Process 待在Ready Queue 等待時間 = Turnaround Time - Cpu Burst Time - I/O op. TIme Response Time : 系統產生第一個回應時間 I/O Bound / CPU Bound I/O Bound process : 大部分時間花在I/O 多、短 CPU ex : DBMS,成績計算,外部search CPU-Bound process : 大部分時間花在處理 ...
OS-CH4-Process Management
Process ManagementProcess ConceptProcess : 執行中的程式 Memory Layout的內容 Text Section (Code Section):Program Code Stack : Prameter、Return Address、Local Variable Data Section : Global Variable Heap : 記憶體在Run time動態分配 執行的一些 Status Data Current activity : PC、PProcrssor registers 。通常在PCB紀錄(OS負責管理在Kernel Memory Area) 123456789101112131415161718由低位址 → 高位址：High Address┌─────────────────────┐│ argc, argv │├─────────────────────┤│ Stack ↓ │ ← local variable、parameter、return add...
資料結構 - 各種資料結構優點
各種資料結構優點整理1. Array優點 可以透過 index 直接存取元素 Random Access 很快 記憶體連續，效率高 適合已知大小、常做查詢的資料 時間複雜度 Access: O(1) Search: O(n) Insert/Delete: O(n) 適合 頻繁用 index 查資料 Heap Matrix Dynamic Programming table 一句話記憶 Array：查位置很快，插刪較慢 2. Linked List優點 不需要連續記憶體 插入、刪除方便 不需要搬動其他元素 大小可以動態改變 時間複雜度 Access: O(n) Search: O(n) Insert/Delete: 已知位置：O(1) 找位置：O(n) 適合 常做插入、刪除 資料數量經常改變 一句話記憶 Linked List：插刪方便，但不能直接跳到某個位置 3. Stack特性LIFO Last In First Out 後進先出 優點 Push / Pop 都很快 適合處理「最近加入的資料」 很適合遞迴、括號匹配、Expression 時間複雜度 P...
資料結構-Heap、Disjoint Sets
Heap MAX heap complete binary tree 父點要 大於 左右子點 Root為最大值 min heap 適合用Array保存 (因為compelete) Heap 優點 : Heap 適合實作 Priority Queue，可以在 O(1) 時間取得最大/最小值，且插入與刪除只需 O(logn)，並可用 Array 有效率地儲存。 Heap 操作 中文意思 時間複雜度 為什麼 Insert X 插入元素 (O(log n)) 插入最後，再往上調整，最多走樹高 Delete-Max 刪除最大值 (O(log n)) 刪 Root 後，要向下 Heapify Heapify / Adjust 調整 Heap (O(log n)) 最差從 Root 一路調到 Leaf Find-Max 找最大值 (O(1)) Max-Heap 最大值就在 Root Build a Heap (Bottom-Up) 建立 Heap (O(n)) ⭐ Bottom-Up Heapify Decrease Key（Min-Heap） 降低...
OS-CH1-3 題目注意
第一章 到 第三章 題目提醒 Bootstrap program 存在 ROM 中 ROM : 唯讀記憶體 : 資料寫入後就不能隨便更改，關機後資料也不會消失。 Flash memory is another form of electronic disk. 不是所有系統都同時有 CLI and GUI MultiProcessor 優點 產能上升 Economy of scale 增加Reliability 不保證提高 CPU utilization Major Version of UNIX 支持 Soft Real Time System Hard Real Time 依賴 RAM、ROM，避免使用Secondary Storage(Disk、Paging、Virtual Memory) Industrial control 使用 Hard-real-Time masked interrupt , 如果有正在處理的仍然會先通知 CPU , 但不會先處理 DMA 不適用 character Devices(Keyboard、Mouse)，一次只有幾 B...
OS-CH3
System call 為User Process 與 Kernel 的溝通介面 System call 經常利用 Trap(Software Interrupt) 進入 Kernel System call 通常被 CPU 視為software interrupt User -> Trap -> Kernel mode -> OS Service -> Return User 現代系統會透過**Application Programming Interface(API)**來呼叫System Call 好處 : program portability 更方便使用 Run Time Environment (RTE) 程式執行時需要的環境 (Compiler Libraries Loader…) 提供 System call Interface Program -> API -> RTE -> System call ID -> Kernel -> OS Service -> Return Flow U...
OS-Hardware Resource Protection
基礎建設Dual Mode operation為了安全區分兩種系統運作模式 the execution of OS code user-defined code User Mode 不允許執行特權指令 Kernel mode 又叫做 supervisor mode、 system mode、priviledged mode、monitor mode(現已removed) 可RUN Priviledged instruction、system call 需要額外HW:Mode bits 去操控 mode OS要求服務要轉成 Kernel mode系統一開機設為Kernel mode -> OS load and start 使用者應用程式 in user modeTrap 、 interrupt 、 system call 可轉為 Kernel mode Privileged instruction可能引起重大危害的指令 -> 設為特權指令只允許Kernel mode 跑如果在User mode 則視為 illegal and traps it to ...
(計算機組織) 計算機組織摘要-Register
MIPS 暫存器架構筆記 所有暫存器都是 32 bits 2. CPU 暫存器分類 CPU 內的暫存器可以分成兩大類： (1) General-Purpose Register, GPR (一般目的暫存器) 一般用途暫存器，用來存放一般資料、運算元、參數等。 例子有： $s0 ~ $s7 $t0 ~ $t9 $a0 ~ $a3 還有其他暫存器 可整理成： $s 系列：通常用來放需要保留的資料 $t 系列：通常用來放暫時資料 $a 系列：通常用來放函式參數 (2) Special-Purpose Register, SPR (特殊目的暫存器) 特殊用途暫存器，用來支援 CPU 的特定功能。 Hi (乘積左半餘數) Lo (乘積右半商數) PC 其用途： Hi / Lo：通常和乘法、除法運算結果有關 PC (Program Counter)：存放下一個要執行的指令位址 3. CPU CPU 有一組 Registers（編號 $0 到 $31） CPU 內有 Arithmetic unit（算術單元） CPU 內有 Multiply divide 單元...
(線性代數) 判斷是否可以對角化
矩陣是否可以對角化的判斷對 (n \times n) 矩陣 (A) 來說， A \text{ 可對角化 } \iff A \text{ 有 } n \text{ 個線性獨立的特徵向量}也就是說，若可以找到可逆矩陣 (P) 與對角矩陣 (D)，使得 A = PDP^{-1}則 (A) 可對角化。 常用判斷方法方法 1：有 (n) 個互異特徵值如果 (A) 有 (n) 個互不相同的特徵值，那麼 (A) 一定可對角化。 方法 2：比較代數重數與幾何重數對每個特徵值 (\lambda)： 代數重數 (algebraic multiplicity)：(\lambda) 在 characteristic polynomial 中出現的次數 幾何重數 (geometric multiplicity)：對應 eigenspace 的維度 \dim \ker(A-\lambda I) 判斷條件為： A \text{ 可對角化 } \iff \text{對每個特徵值 } \lambda,\ \text{幾何重數}=\text{代數重數}而且所有 eigenspace 維度加總必須...