國立聯合大學 資訊管理學系 陳士杰老師 前置觀念 : 系統基礎概念

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 2 Outline On line v.s. Off line Process 硬體保護 Caching I/O Structure Deadlock

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 3 von Neumann model von Neumann model The data and program are stored as binary patterns in memory CPU

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 4 ■ On line v.s. Off-line CPU P1P1 Hard Disk Printer On-line Main Memory ①資料 1 ②資料 1 ②執行 資料 1 ③資料 2 ①結果 1 ②結果 1 ③執行 其它工作 或 ③結果 2 I/O Device

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 5 正在執行中的程式 Def: 正在執行中的程式 (A program in execution) 。 Process 主要包含有：  Code Section ( 程式碼、程式區間 )  Data Section ( 資料區間 )  Program Counter ( 程式計數器 )  CPU Register 如 : 通用暫存器、基底 ( 限制 ) 暫存器 … 。  Stack 相互 Call 來 Call 去從事遞迴工作存放返回 位址 ∵多個 Process 之間會相互 Call 來 Call 去及從事遞迴工作，用以存放返回 位址。 檔案 (File) 程式未執行時，只是一個存放在電腦硬碟中的檔案 (File) 。 Process( 行程 ) 存放於 Memory Space

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 6 Process 與 Program 的不同 ProcessProgram 主動 (Active) 被動 (Passive) 帶有 Program Counter ，用以指出 下一個指令所在 儲存於次儲存體 (e.g., Disk) 中的檔 案

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 7 行程狀態圖 (Process State Transition Diagram) 描述 Process 由 開始到結束的生命週期 (Life-Cycle) Process 在執行時會改變其狀態。而 Process STD 則是用以描述 Process 由 開始到結束的生命週期 (Life-Cycle) ，而一個 Process 在此週期中會經 歷數種狀態。 Initial 在 Initial 時，稱 Program 為 Job (J 1, J 2, J 3 ) Job Queue Ready 在 Ready 時，稱 Program 為 Process (P 1, P 2, P 3 ) Ready Queue ① Running ② Terminate ③ Abort ④ ⑤ Block (Wait) ⑥ 此時不會和其它 Process 搶 CPU 或其它 資源。 Process 此時還在 Mem. 中，但不在 Ready Queue ，所以不是 CPU 配置資源的對象， 即 Sleep in Mem. 。 ⑦

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 8 觸發此狀態圖每一個狀態轉換之行為如下： 引入 ( 或產生 ) 一個新的 Program 到電腦  要引入 ( 或產生 ) 一個新的 Program 到電腦去執行 從記憶體中挑選出一個 Process 到 CPU  要從記憶體中挑選出一個 Process 到 CPU 去執行 做完其工作  一個 Process 做完其工作時，就正常結束 發生不正常結果  一個 Process 發生不正常結果時，就中止 除零 除零 溢位 溢位 短暫中止  發生短暫中止時，會直接回到 Ready 狀態 被高優先權 Process 插隊 被高優先權 Process 插隊 中斷發生 中斷發生 CPU Time Slice Expires CPU Time Slice Expires 較長時間中止  發生較長時間中止時，會將 Process Block 住 Wait for I/O complete Wait for I/O complete Wait for resource available Wait for resource available CPUData 都在 Mem. 此 STD 是控管 CPU 這項資源，且 Data 都在 Mem. 中。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 9 Initial Ready Running Terminate Abort Block (Wait) Suspended Block (Disk) ① ② 將 Process 移到 Disk 中，即 Swap Out 的 動作。 Suspended Ready (Disk) 此時資料還 在 Disk 中。 ③ Swap In 的動作。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 10 觸發此狀態圖每一個狀態轉換之行為如下： 待在 Mem. 的時間太長 搶 Mem. 這項資源  當 Process 待在 Mem. 的時間太長 ( 被 Block 太久 ) ，或有其它高優先 權的 Process 來搶 Mem. 這項資源。  所等待的 Long-Time Event 發生，或是花費長時間的事情做完了 (e.g., Long-Time I/O complete) 。  將 Process 從 Disk 中引入 Mem. 中的 Ready Queue 。 Mem.Data 都在 Disk 此 STD 是控管 Mem. 這項資源，且 Data 都在 Disk 中。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 11 硬體保護 (Hardware Protection) 基礎設施 ( 前題 ) ：  雙模式運作 (Dual-Mode Operation)  特權指令 (Privileged Instruction)

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 12 實施 Protection 的前題 Dual-Mode 運作 系統必須提供 Dual-Mode 運作。 會引起系統危害的指令特權指令 (Privileged Instruction) 必須將會引起系統危害的指令，設定為特權指令 (Privileged Instruction) 。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 13 雙模式運作 (Dual-Mode Operation) 系統運作的狀態可分為兩種：  Monitor Mode ( 監督模式 ) O.S. 的 System Process 可以執行的狀態 O.S. 的 System Process 可以執行的狀態。在此模式下， O.S. 掌控對系 統的控制權 Supervisor ModeSystem Mode 又稱 Supervisor Mode 或 System Mode 有權利執行特權指令 (Privileged Instruction) 在此 Mode 下，才有權利執行特權指令 (Privileged Instruction)  User Mode ( 使用者模式 ) User Program 可執行時的 系統狀態 User Program 在此模式下允許被執行，即 User Program 可執行時的 系統狀態 Illegal Instruction Error 錯誤中斷 (Trap) 在此模式下，不能執行特權指令，否則會引起 “ Illegal Instruction Error ” ，產生錯誤中斷 (Trap) ， O.S. 會強迫 Process 中止

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 14 硬體對 Dual-Mode 製作的支援 模式位元 (Mode Bit) Dual-Mode 需要硬體的額外支援，即提供一個模式位元 (Mode Bit) 用以區分此兩種模式，通常  0: 表示 Monitor Mode  1: 表示 User Mode

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 15 Dual-Mode 的目的 保護作業系統不受錯誤的 User Program 之破壞，即防止 User Program 執行特權指令，造成可能的危害。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 16 特權指令的種類 I/O 指令 與記憶體管理有關的暫存器之修改指令 與 Timer 設定有關的指令 Enable/Disable 指令 系統停止 (Halt) 指令 從使用者模式改變到監督模式的指令

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 17 硬體保護 (I/O Protection) 直接使用 Hardware Device 防止 User Program 在執行時，直接使用 Hardware Device 。 透過 O.S. User Program 必須透過 O.S. 提出 Hardware Request ，再由 O.S. 控制 Hardware 運作，並將 Hardware Result 告知 User Program 。 執行流程：  發出 Hardware Request ，即 System Call ，以轉換 Modes  執行相對應的硬體服務  回傳結果給 O.S.  O.S. 再將結果回傳給 User Program

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 18 User Program O.S. 相對應的 I/O Service Routines User Mode Monitor Mode    

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 19 快取 (Caching) 最近 ( 可能是 馬上 ) 就會被再存取 快取 (Caching) 的觀念是：利用快速的記憶體來保存最近 ( 可能是 馬上 ) 就會被再存取的資料。 Caching 和 Cache Memory 不同， Caching 是動名詞，為一種處理 機制； Cache Memory 只是 Caching 的一個例子。 在硬體系統中，快取記憶體 (Cache Memory) 分為兩種：  內建在 CPU  內建在 CPU 中的 L1 快取  在 CPU 之外  在 CPU 之外，稱為 L2 快取 先從 L1 快取尋 找再從 L2 記憶體尋找最後才到主記憶體裡 (RAM) 尋找 L1 快取比 L2 快取記憶體快，所以 CPU 找尋資料時，會先從 L1 快取尋 找，找不到再從 L2 記憶體尋找，最後才到主記憶體裡 (RAM) 尋找。 所以快取記憶體愈大，電腦執行效率就愈大。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 20 節省資料收尋的時間 資料命中率 (Cache hit rate) 有多少次數能準 確找出資料 L1 、 L2 快取的設計是用來節省資料收尋的時間。然而，快 取容量加倍，並不代表速度會加倍，是跟資料命中率 (Cache hit rate) 有很大的關係，也就是有多少次數能準 確找出資料。 快取記憶體的容量 由於快取記憶體的容量有限制，所以快取記憶體的管理是 必要

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 21 I/O 結構 (I/O Structure) I/O 結構 (I/O Structure) 是討論當 User Process 發出 I/O Request 後，控制權多久會交 還給 User Process? User Process 可不可以繼續往下執行 ?  即： User Process 可不可以繼續往下執行 ? 有兩種架構 :  Synchronous I/O structure ( 同步 I/O 架構 )  Asynchronous I/O structure ( 非同步 I/O 架構 )

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 22 同步 I/O 結構 (Synchronous I/O Structure) 當 I/O 完成運作後 是當 I/O 完成運作後才會將控制權 交還給 User Process 。 只有一個 I/O 請求產生  優點：在一段時間內只有一個 I/O 請求產生。 ∴當 I/O Complete 中斷 產生時， O.S. 即知是由何種 Device 發出。 並行的 I/O 處理  缺點：不允許並行的 I/O 處理。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 23 非同步 I/O 結構 (Asynchronous I/O structure) 立刻將控制權交還給 User Process 立刻將控制權交還給 User Process ， 不需空等 I/O 運作完成。 在一段時間內可有多個 I/O Request 同時發生。 “Device Status Table” 各種 Device 的位址 使用狀況位於某 Device 的 I/O 請 求之執行狀況 O.S. 必須有一個 “Device Status Table” 以記錄各種 Device 的位址、 使用狀況和位於某 Device 的 I/O 請 求之執行狀況。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 24 裝置狀態表 (Device-Status Table) 裝置：讀卡機一號 狀態：閒置 裝置：印表機三號 狀態：忙碌 裝置：磁碟一號 狀態：閒置 裝置：磁碟二號 狀態：閒置 裝置：磁碟三號 狀態：忙碌 印表機要求 位址： 長度： 1372 磁碟三號要求 檔案： xxx 指令：讀取 位址： 長度： 磁碟三號要求 檔案： yyy 指令：寫入 位址： 長度： 500

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 25 The Deadlock Problem ( 死結問題 ) The Deadlock Problem ( 死結問題 ) 自已掌握住自已所 握有的資源不放又向該群體中的其它行程要求資源的狀況 指的是一群體中被堵塞住的所有行程，這些行程自已掌握住自已所 握有的資源不放，同時又向該群體中的其它行程要求資源的狀況。 Example  假設一個系統中有兩個資源 R 1 與 R 2 ，而且該系統產生出兩個行程 P 1 與 P 2  R 1 已配置給 P 2 ， R 2 已配置給 P 1 ，但這兩個行程在執行過程中又向對 方要求對方正在使用中的資源，因此造成系統打結。 P1P1 P2P2 R1R1 R2R2 : Process : Resource : Acquire : Hold

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 26 Deadlock Characterization ( 死結的特性 ) 當以下四個條件同時成立時，死結就會發生了：  Mutual exclusion ( 互斥 ): 不可共用的型 式一次只能有一個行程使用它 在系統中所提供的資源中，至少有一個資源必須是不可共用的型 式，也就是該資源一次只能有一個行程使用它。 等到該資源被釋放 若其它行程想要使用該資源，則必須等到該資源被釋放才能夠去 用它。  Hold and wait ( 佔用與等候 ): 已佔用至少一個資源正等候其他行程已佔用另外 資源之行程 必須存在一個已佔用至少一個資源且正等候其他行程已佔用另外 資源之行程。 等候狀態 也就是當某個行程已經取得某項系統資源，而且正在要求其它系 統資源的使用權，但該系統資源正被其它的行程所使用，此時該 行程就必須要進入等候狀態。

國立聯合大學 資訊管理學系 資料庫系統課程 ( 陳士杰 ) 27  No preemption ( 不可搶先 ): 只能在佔用它的行程在完成工作之後，才會被釋 放 系統所提供的資源只能在佔用它的行程在完成工作之後，才會被釋 放給其它行程使用。  Circular wait ( 循環式等候 ): 等候行程的集合 {P 0, P 1, ……, P n } 必須存在一等候行程的集合 {P 0, P 1, ……, P n } ，其中 P 0 等候的資 源已被 P 1 佔用， P 1 所等候的資源已被 P 2 佔用， …. ， P n-1 所等候的資源 已被 P n 佔用，而 P n 所待候的資源已被 P 0 佔用。