作業系統簡介

作業系統(Operating System)的目的 方便的人機介面 命令列介面：Command line，如DOS 圖形化使用者介面：GUI (Graphic User Interface)，如Windows XP，Mac OS等 有效的管理資源 Memory：虛擬記憶體(virtual memory) Processor：程序排程(process scheduling) Device：死結 (dead lock) Information：檔案(file) Others：載入(loader)，鏈結(linker)，庫存程式(library)，公用程式(utility)

計算機作業方式 Batch(批次)：將程式及資料事先準備好(一疊卡片，一個.bat檔)交給電腦一次完成。 適用於周期性，時效要求低的作業。如：聯考閱卷，稅務申報等。 Real Time(即時)：輸入資料後立即處理，並在一定時限內產生輸出。(Response time ≦時限) 用於Special-Purpose電腦系統，如飛機自動導航/駕駛系統，證卷交易系統。(事關人命，金錢交易)

計算機作業方式 On-Line(線上作業)  Off-Line(離線作業) Time-Sharing(分時作業) I/O設備與主機有實體連線，能立即作I/O處理，為Real time的必要條件。 變化：分散式系統中，電腦透過網路，與系統取得連線。 Time-Sharing(分時作業) Multiprogramming的一種，各程式分配一段時間輪流交替執行，為最普遍的執行方式(公平，簡單，效果不錯) Multiprogramming：電腦Memory內有2個以上互不相關的程式可同時被執行，CPU交替執行之，使得User產生電腦專屬執行某一程式的錯覺。 由OS控制

計算機作業方式 Multiprogramming(多工程式處理)-1970’s Multiprocessing(多元處理)-1970’s 同時(currently)執行數個程式(以軟體方式)，各個程式感覺是同時執行。 Multiprocessing(多元處理)-1970’s 同時(simultaneously)執行數個程式(以硬體方式)，格個程式真正是同時執行。 Multitasking(多工處理)-1980’s 電腦Memory內有2個以上屬於同一程式的工作(task)可被同時執行。 Task：執行一個特定功能的一段程序(副程式) Multithreading(多序執行)-1990’s 如Java

Virtual Memory虛擬記憶體 優點 作法 使User的程式不受實際Memory容量的限制。 Memory內部程式/資料的保護。 Memory內部資訊的共享(sharing)。 作法 Demand Page(分頁)：以Mem的使用為主，將程式/資料分成等量大小(頁)，沒有fragment(碎片)。 Demand Segment(分段)：以程式的保護為主，根據程式性質，分成數個大小不同的區段(段)，有fragment (碎片)。

Virtual Memory虛擬記憶體 Page Fault 代換策略 FIFO (First In First Out) 先進先出，最直觀，效果差 LRU (Least Recently Used) 最近最久未用，合理 Optimal 最晚才會再用，最佳，理論上限 Random：實際上使用 Hard Disk Page 1 Page 2 某段程式或一段資料 Page 3 Page 4 Page 5 Page 6 Page 7 Page 8 Page 9 Main Memory Page frame Page 1 Page 10 Page 3 Page frame Page 6 Page frame ？ Page Fault CPU Page 9 Page frame 例：CPU需要順序(頁參考順序)：1,3,6,9,10,4,7…

Page Fault 代換策略實作 FIFO(先進先出) 頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0 Page frame=3 參考順序 1 2 3 4 5 6 7 PF 0 PF 1 PF2 Page Fault 3 3 3 3 5 3 5 5 5 2 2 2 2 5 2 5 5 1 1 1 4 1 4 4 4 6 4 6 6 3 6 3 3 3 6 3 6 2 2 2 2 1 2 1 1 7 1 7 7 7 4 7 4 4 4 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ 共發生 page fault (＊)= 次 15

自我練習 FIFO(先進先出) 頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0 Page frame=4 PF 0 PF 1 PF 2 PF 3 Fault 共發生 page fault (＊)= 次

Page Fault 代換策略實作 LRU(最近最久未用) Least Recently Used 頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0 Page frame=3 參考順序 1 2 3 4 5 6 7 PF 0 PF 1 PF2 Page Fault 3 3 3 3 1 1 1 1 7 7 7 7 7 7 7 6 6 1 1 1 4 1 4 4 5 4 5 5 2 5 2 2 4 2 4 4 4 2 2 2 2 2 2 2 6 6 6 3 6 3 3 5 3 5 5 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ 共發生 page fault (＊)= 次 15

自我練習 LRU(最近最久未用) Least Recently Used 頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0 Page frame=4 參考順序 PF 0 PF 1 PF 2 PF 3 Fault 共發生 page fault (＊)= 次

Page Fault 代換策略實作 Optimal(取代最晚才會再用的) 效果最好理論上限，但不可行 頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0 Page frame=3 參考順序 1 2 3 4 5 6 7 PF 0 PF 1 PF2 Page Fault 3 3 4 4 4 4 4 4 4 4 4 4 5 4 5 5 1 1 1 1 1 1 5 1 6 5 6 7 7 7 7 7 7 6 7 6 2 2 2 2 2 2 2 2 2 3 2 3 3 3 3 3 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ 共發生 page fault (＊)= 次 12

自我練習 Optimal(取代最晚才會再用的) 頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0 Page frame=4 參考順序 PF 0 PF 1 PF 2 PF 3 Fault 共發生 page fault (＊)= 次

Process Management (程序管理) 一段執行中的程式碼(a program in execution) Process 的 STD (State Transition Diagram) 狀態轉換圖 Complete Disk Memory RUN Time out User1 submit Job1 Job Queue   User2 submit Job2 Ready Jn…J3,J2,J1 … 等I/O完成 Usern submit Jobn Pn…P3,P2,P1  Ready Queue WAIT I/O已完成 ：Long-term scheduler (長程排程器) ：Short-term scheduler (短程排程器) ：Medium-term scheduler (中程排程器)

Process Management (程序管理) Process Scheduler (程序排程器)的目標System Balance (系統平衡) 程序大致可分為 I/O bound：大多數時間在做I/O，如Word。 CPU bound：大多數時間在跑CPU，如TV game。 Scheduler(排程器)為使CPU，I/O同時忙碌，故以I/O bound process(程序)為優先選擇。

Process Management (程序管理) Non-Preemptive(不可插隊式) FCFS (First Come First Serve)：先來先做 SJF (Shortest Job First)：最短先做 Preemptive(可插隊式) RR (Round-Robin)：啄木鳥/Time-sharing，適用於一般電腦。 SRTF (Shortest Remaining Time First)：最短剩餘時間優先。 解釋名詞： Average Turnaround Time：平均迴轉時間 程序從進入ready queue後，到全部完成的平均時間。 Average Waiting Time：平均等待時間 程序從進入ready queue後，到全部完成的平均等待時間。

Process Scheduling 程序排程 代表process進入CPU中開始執行 Non-Preemptive (不可插隊式) FCFS 先來先做 (First Come First Serve) Process # Burst Time Arrived Time 1 10 2 4 3 5 7 p4 p3 P2 p1 ● ● ● ● 3 5 7 10 14 19 23 Average Waiting Time 代表process已經進入ready queue中等待，但尚未執行 =(0+(10-3)+(14-5)+(19-7))/4=7# Average Turnaround Time =(10+(14-3)+(19-5)+(23-7))/4=12.75#

自我練習 Non-Preemptive (不可插隊式) FCFS 先來先做 (First Come First Serve) Process # Burst Time Arrived Time 1 10 2 6 3 5 4 7 p4 p3 P2 p1 Average Waiting Time=？ Average Turnaround Time=？

Process Scheduling 程序排程 Non-Preemptive (不可插隊式) SJF 最短先做 (Shortest Job First) Process # Burst Time Arrived Time 1 10 2 4 3 5 7 p4 p3 P2 p1 ● ● ● ● 3 5 7 10 14 18 23 Average Waiting Time =(0+(10-3)+(18-5)+(14-7))/4=6.75# Average Turnaround Time =(10+(14-3)+(23-5)+(18-7))/4=12.5#

自我練習 Non-Preemptive (不可插隊式) SJF 最短先做 (Shortest Job First) Process # Burst Time Arrived Time 1 10 2 6 3 5 4 7 p4 p3 P2 p1 Average Waiting Time=？ Average Turnaround Time=？

Process Scheduling 程序排程 Preemptive (可插隊式) SRTF 剩餘最短時間先做 (Shortest Remaining Time First) Process # Burst Time Arrived Time 1 10 2 4 3 5 7 p4 p3 P2 p1 ● ● ● ● 3 5 7 11 16 23 Average Waiting Time =((16-3)+0+(11-5)+0)/4=4.75# Average Turnaround Time =((23-0)+(7-3)+(16-5)+(11-7))/4=10.5#

自我練習 Preemptive (可插隊式) SRTF 剩餘最短時間先做 (Shortest Remaining Time First) Process # Burst Time Arrived Time 1 10 2 6 3 5 4 7 p4 p3 P2 p1 Average Waiting Time=？ Average Turnaround Time=？

Process Scheduling 程序排程 Preemptive (可插隊式) RR 啄木鳥 (Round-robin) Average Waiting Time =(12+(1+4)+(3+6+4)+(5+4))/4=9.75# Time slice(時間間隔)=2 Process # Burst Time Arrived Time 1 10 2 4 3 5 7 Average Turnaround Time =((22+(12-3)+(23-5)+(20-7))/4=15.5# p4 p3 P2 p1 ● ● ● ● 2 3 4 5 6 7 8 10 12 14 16 18 20 22 23

自我練習 Preemptive (可插隊式) RR 啄木鳥 (Round-robin) Average Waiting Time=？ Process # Burst Time Arrived Time 1 10 2 6 3 5 4 7 p4 p3 P2 p1 Average Waiting Time=？ Average Turnaround Time=？

Device Management (設備管理) Dedicated(專屬)：如printer, tape Shared(共用)：如Memory, Disk Race Condition(競賽現象) 當O.S安排程式使用資源的次序不當所產生的錯誤現象。 (將專屬的Device當成共用的Device使用，就會產生Race Condition) 如：將一台printer當成共用Device，2個以上的程式同時要求列印時，會產生什麼狀況？ 解決之道： 程式中加入“要求printer”及“釋放”指令 對專屬Device做Mutual Exclusion(互相排斥)控制

Device Management (設備管理) printer Process 1 Process 2  等     要求printer 要求tape P1 P2     要求tape 要求printer   等  釋放tape tape 釋放tape   釋放printer 釋放printer    Dead lock (死結)

Dead lock (死結) Dead lock 發生之四大必要條件(缺一不可) Dead lock 的解決 Mutual Exclusion (互斥) Hold & Wait (持有並等待) Non-preemptive (不可強佔) Circuit Waiting (循環等待) Dead lock 的解決 Prevention (預防) 釜底抽薪 破除任一必要條件，使Dead lock 不可能發生。 Avoidance (避免) 步步為營 O.S分配資源時，先判斷是否導致Dead lock發生。 Detection & Recovery (偵測及復原) 見機行事 Dead lock發生後，犧牲某一方釋放資源，打開Dead lock。 鴕鳥法 不解決 關電源重新開機。

其他系統之管理 程式在執行前所需要的步驟： Source code程式碼 Compiler 編譯程式 Object code Linker 鏈結程式 Execution code Loader 載入程式 CPU

Logical/virtual address 其他系統之管理 Logical/virtual address .Obj .exe S1 S2 call scanf mov x,ax 1 2 3  S1 S2 call 20001 mov 35301,ax 1 2 3  主程式 … … 程式段 Main ( ) {int x; scanf(“%d”,&x); } 程式段 … … … Compiler Linker … … … 20000  定位  鏈結 20000 a 20001 scanf( ) 20001 … 資料段 … 25100 x a 30001 25101 … 資料段 … x 35101 … 定位：決定程式各模組之位置關係 鏈結：解決程式跨段參考的問題

其他系統之管理 執行 … … … … … … … … … … … … 重定位：根據實際載入位址，調整指令或資料的位址 載入：載入程式  memory 其他系統之管理 A.exe .exe Physical/real address B.exe S1 S2 call 20001 mov 35301,ax 1 2 3  S1 S2 call 120001 mov 135301,ax 100000 100001 100002  … … 程式段 程式段 … … 執行 Linker Loader … …  定位  鏈結 20000  重定位(改位址)  載入(copy) 120000 scanf( ) 20001 scanf( ) 120001 … … 25100 125100 a a 25101 125101 資料段 … 資料段 … x x 35101 135101 … … 重定位：根據實際載入位址，調整指令或資料的位址 載入：載入程式