0
Average Waiting Time
=(0+(10-3)+(14-5)+(19-7))/4=7#
3 5 7 10 14
19
23
代表process已經進入ready queue中等待，但尚未執行
Average Turnaround Time
=(10+(14-3)+(19-5)+(23-7))/4=12.75#
8p.01
自我練習
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略實作
LRU(最近最久未用) Least Recently Used
4. Time-Sharing(分時作業)
Multiprogramming的一種，各程式分配一段時間輪流 交替執行，為最普遍的執行方式(公平，簡單，效果不 錯)
Multiprogramming：電腦Memory內有2個以上互不相 關的程式可同時被執行，CPU交替執行之，使得User 產生電腦專屬執行某一程式的錯覺。
參考順序
PF 0 PF 1 PF 2 PF 3 Fault
共發生 page fault (＊)= 次
11p.01
Page Fault 代換策略實作
Optimal(取代最晚才會再用的) 效果最好理論上限，但 不可行
頁參考順序：0,1,2,3,4,2,1,5,6,7,2,3,7,4,5,6,0
Page frame=3
20p.01
Process Scheduling 程序排程
Preemptive (可插隊式)
Non-Preemptive (不可插隊式)
代表process進入CPU 中開始執行
1. FCFS 先來先做 (First Come First Serve)
Process # 1 2 3 4
Burst Time 10 4 5 4
Arrived Time 0 3 5 7
p4 p3 P2 p1 ●
● ● ●
Page Fault
＊＊ ＊＊＊
＊＊＊ ＊
＊＊ ＊
共發生 page fault (＊)= 12 次
12p.01
自我練習
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
(library)，公用程式(utility)
2p.01
計算機作業方式
1. Batch(批次)：將程式及資料事先準備好(一疊卡 片，一個.bat檔)交給電腦一次完成。
適用於周期性，時效要求低的作業。如：聯考閱卷， 稅務申報等。
2. Real Time(即時)：輸入資料後立即處理，並在 一定時限內產生輸出。(Response time ≦時限)
用於Special-Purpose電腦系統，如飛機自動導航/駕駛 系統，證卷交易系統。(事關人命，金錢交易)
3p.01
計算機作業方式
3. On-Line(線上作業) Off-Line(離線作業)
I/O設備與主機有實體連線，能立即作I/O處理，為Real time的必要條件。
變化：分散式系統中，電腦透過網路，與系統取得連 線。
參考順序 0 1 2 3 4 2 1 5 6 7 2 3 7 4 5 6 0
PF 0 0 0 0 03 34 4 4 4 4 4 4 4 4 4 54 5 5
PF 1
1 1 1 1 1 1 51 65 76 7 7 7 7 7 67 6
PF2
2 2 2 2 2 2 2 2 2 32 3 3 3 3 03
由OS控制
4p.01
計算機作業方式
5. Multiprogramming(多工程式處理)-1970’s
同時(currently)執行數個程式(以軟體方式)，各個程式 感覺是同時執行。
6. Multiprocessing(多元處理)-1970’s
同時(simultaneously)執行數個程式(以硬體方式)，格 個程式真正是同時執行。
作業系統簡介
1p.01
作業系統(Operating System)的目的
1. 方便的人機介面
命令列介面：Command line，如DOS 圖形化使用者介面：GUI (Graphic User Interface)，如
Windows XP，Mac OS等
2. 有效的管理資源
1. Memory：虛擬記憶體(virtual memory) 2. Processor：程序排程(process scheduling) 3. Device：死結 (dead lock) 4. Information：檔案(file) 5. Others：載入(loader)，鏈結(linker)，庫存程式
PaPgaegfera1me
PaPgaegfera3me
PaPgaegfera6me
CPU
PaPgaegfera9me
Main Memory
Page 1
Page 2
某
Page 3
段
程
Page 4
式
Page 5
或
Page 6
一
Page 7
段
資
Page 8
料
Page 9
Page 10
？ Page Fault
共發生 page fault (＊)= 次
13p.01
Process Management (程序管理)
Process (程序)
一段執行中的程式碼(a program in execution)
Process 的 STD (State Transition Diagram) 狀態轉換圖
Complete
優點
1. 使User的程式不受實際Memory容量的限制。 2. Memory內部程式/資料的保護。 3. Memory內部資訊的共享(sharing)。
作法
1. Demand Page(分頁)：以Mem的使用為主，將程式/資 料分成等量大小(頁)，沒有fragment(碎片)。
2. Demand Segment(分段)：以程式的保護為主，根據程 式性質，分成數個大小不同的區段(段)，有fragment (碎片)。
PF2
2 2 2 2 2 2 62 6 6 36 3 3 53 5 5
Page Fault
＊＊ ＊＊＊
＊＊＊ ＊＊＊
＊ ＊＊ ＊
共發生 page fault (＊)= 15 次
10p.01
自我練習
LRU(最近最久未用) Least Recently Used
頁參考順序：1,2,3,4,5,0,1,4,5,6,7,4,5,6,7,1,0 Page frame=4
17p.01
自我練習
Non-Preemptive (不可插隊式)
FCFS 先來先做 (First Come First Serve)
Process # 1 2 3 4
Burst Time 10 6 3 5
Arrived Time 0 3 5 7
p4 p3 P2 p1
Average Waiting Time=？
Average Turnaround Time=？
18p.01
Process Scheduling 程序排程
Non-Preemptive (不可插隊式)
SJF 最短先做 (Shortest Job First)
Process # 1 2 3 4
Burst Time 10 4 5 4
Arrived Time 0 3 5 7
6p.01
Virtual Memory虛擬記憶體
Page Fault 代換策略
1. FIFO (First In First Out)
先進先出，最直觀，效果差
2. LRU (Least Recently Used)
最近最久未用，合理
3. Optimal
最晚才會再用，最佳，理論上限
4. Random：實際上使用
Process 的排程策略
1. Non-Preemptive(不可插隊式)
1. FCFS (First Come First Serve)：先來先做 2. SJF (Shortest Job First)：最短先做
2. Preemptive(可插隊式)
3. RR (Round-Robin)：啄木鳥/Time-sharing，適用於一般電腦。 4. SRTF (Shortest Remaining Time First)：最短剩餘時間優先。
PF 0 0 0 0 30 3 3 3 53 5 5 52 2 2 2 52 5 5
PF 1
1 1 1 41 4 4 4 64 6 6 36 3 3 3 63 6
PF2
2 2 2 2 12 1 1 71 7 7 7 47 4 4 04
Page Fault
＊＊ ＊＊＊
＊＊＊ ＊＊＊
＊ ＊＊ ＊
共發生 page fault (＊)= 15 次
p4 p3 P2 p1 ●
● ● ●
Average Waiting Time
0
3 5 7 10 14 18
23
=(0+(10-3)+(18-5)+(14-7))/4=6.75#
Average Turnaround Time =(10+(14-3)+(23-5)+(18-7))/4=12.5#