Operation System(OS)

目錄 Char 1~3 基本概念 Char 4 Process management Char 5 Deadlock Char 6 memory management Char 7 Virtual memory Char 8 Disk management Char 9 File system Char 10 Process communication

Char 1~3 基本概念

Char1~3 基本概念 Von Neumann Process 、 Thread Types of Operating System Time sharing system Real time system Multiprocessor system Distributed system Batch system Hardware Resource Protection Privileged instruction Interrupt的種類 CPU與I/O的三種溝通方式

(Arithmetic Logic Unit) 范紐曼電腦(Von Neumann) 第一台電腦，架構有5大單元 mem CPU input CU (Control unit) ALU (Arithmetic Logic Unit) Note: register包含在cpu UNIX：多人多工 Windows：單人多工 output

基本概念 Process(行程) Heavy-weighted process，執行中的program， 為OS分配資源的對象， Code section Data section PC CPU register Stack Thread共享 Thread內含 Process(包含一個thread)

基本概念 Thread(執行緒) thread內含 thread共享 Light-weighted process，一個Process可有多個thread， thread內含 CPU register Stack PC thread共享 Code section Data section Process(包含多個thread)

練習 建立一個視窗程式，具有兩個button， button內實作一個功能「停止5秒後輸出彈跳視窗」 1個button使用thread實作此功能 1個button不使用thread實作此功能， 比較兩者的差異

基本概念 系統中存在多個processes同時執行 系統中processes執行的個數 Multiprogramming system Multiprogramming degree 系統中processes執行的個數

Types of Operating System Time sharing system 又稱Multitasking，可透過Round-Robin(RR)排班方式讓多個 processes共用1個cpu使processes並行執行 Real time system 1、Hard real time system 不能有virtual mem，對每個job的完成時間有極嚴格的限制 2、Soft real time system 不能使用aging技術，保證高先權的process會先於低優先權的process完成 RR會設quantum time

Types of Operating System Multiprocessor system 又稱Multiprocessing，一部機器有多個CPU，共享mem， processors之間採shared memory方式溝通 Distributed system 每個processor有自己的mem空間，不一定受同一個clock or OS控制，processor之間採message passing方式溝通

Types of Operating System Batch system 將相同性質且非急迫性的工作累積後才一次送至系統處理

Hardware Resource Protection OS I/O mem User program CPU

Hardware Resource Protection I/O Protection 防止user program對I/O Device不正常之使用 Memory Protection 保護monitor所在的區域不被user program更改 防止user program企圖修改其它processes所在的Memory Area CPU Protection 防止user process無限期佔用CPU而不釋放

Privileged instruction(特權指令) Def: 任何會引起系統危害的指令 e.g. I/O指令、修改mem的指令 Dual mode Monitor mode (or kernel mode) 特權指令在此mode執行 User mode 非特權指令在此mode執行

Interrupt(中斷) 中斷的種類 External interrupt Internal interrupt CPU之外的devices所引起的中斷 Interrupt e.g. I/O complete Internal interrupt CPU本身所引起的中斷 Trap e.g. 除zero、overflow Software interrupt 執行中的process若需OS提供服務時 System call e.g. INT21

Polling 、Interrupt、DMA CPU與I/O的三種溝通方式 Polling CPU主動 CPU不斷詢問device工作是否已完成 浪費polling time Interrupt Device主動 Device傳中斷要求，CPU執行ISR，完成時通知OS CPU仍需參於device與mem之間的資料傳輸 DMA DMA主動 CPU設定好DMA之後，DMA執行資料傳輸，完成時通知OS CPU不需參於device與mem之間的資料傳輸 Polling IO:教授會時常主動關心你的報告進度 Interrupt IO:你寫報告每個段落完成了再自己告訴教授 DMA:全部寫好了再通知我 並把它交給助教(DMAC)就好

Char 10 Process communication

Process communication 兩種溝通方式 (1) share memory 透過共享變數 會有data不一致的問題 須對共享變數做互斥控制 特色：對programmer負擔重，對OS負擔輕 (2) message passing 透過socket 利用send()、receive()溝通 特色：對programmer負擔輕，對OS負擔重 使用critical section

share memory方式的問題 Race condition e.g. 共享變數的結果依process執行順序的不同， 而有不同的執行結果 e.g. Data inconsistency 預期結果為0，但結果卻可能為1

Data inconsistency的解法 1、Disable interrupt 當process要對共享變數進行存取前，先發system call來Disable interrupt直到存取結束後才Enable interrupt 缺點：1、僅適用於單顆CPU的環境 2、有些OS不允許關閉所有中斷

Data inconsistency的解法 2、Critical section design 對共享變數提供互斥存取的機制

Critical section設計的方法 SW solution HW instruction Semaphore 有名的同步問題 Producer/consumer problem Reader/writer problem Dining philosopher problem Sleeping barber problem Monitor Critical region

Critical Section須滿足三個性質 Mutual exclusion 最多只允許一個process在CS內活動 Progress 1、不想進入CS的process不能阻礙別的process 進入CS 2、決定哪個process可以進入CS的時間是有限的 Bounded waiting 從process提出申請到獲准進入CS的時間是有限的

Dining philosopher problem Def: 5個哲學家5隻叉子，須拿到兩個叉子才能吃飯 會有Deadlock(死結)的問題

Deadlock解法 [法一] 只允許4個哲學家上桌 [法二] 除非可一次拿到左右叉子，否則不拿 [法三] 限制奇數哲學家「先拿左再拿右」 限制偶數哲學家「先拿右再拿左」

練習 實作兩個buttons，令共享變數v初值為0 [第一個button使用不critical section技巧] 第一個thread執行十萬次v=v+1 第二個thread執行十萬次v=v-1 [第二個button使用critical section技巧，對共享變數v做保護] 比較兩個button執行完的結果

變數宣告： 初始化臨界區間變數：

第一個button功能如下： 主程式： threads：

第二個button功能如下： 主程式： threads：

Char 4 Process management

Process 的state transition diagram Initial (New) Job queue p1 p2 p3 Long-term scheduler Ready queue p1 p2 p3 Ready 1、CPU time expire 2、interrupt 3、高優先權process插隊 I/O complete Short-term scheduler Running Wait for I/O complete Block (wait) Medium-term scheduler將之swap in 失敗結束 成功結束 Process的lifecycle Terminate Medium-term scheduler將之swap out Abort Suspend Ready Suspend Block

CPU排班決策發生的四種狀況 1、process從Running -> Block 2、process從Running -> Ready 3、process從Wait -> Ready 4、process從Running -> Terminate 自願 非自願 主動爭取 自願

三種Scheduling Long-term scheduler Short-term scheduler 從Job queue中挑選適合的process並載入到mem Short-term scheduler 從Ready queue中挑選高優的process使之取得CPU控制權 Medium-term scheduler 當mem空間不夠時，且又有其它process須額外空間時，將之swap out至disk，等有足夠mem空間時再swap in至mem

Scheduling algorithms FCFS(or FIFO) RR Priority SJF SRJF Multilevel Queue Multilevel Feedback queue

等待時間、完成時間 Waiting time (等待時間) Turnaround time (完成時間) Process在ready queue中等待獲取CPU的時間 Turnaround time (完成時間) 自process進入系統到其工作完成的時間

FCFS (FIFO) Def: 最早到的process優先取得CPU控制權 EX: 會有「Convoy Effect(護衛效應)」 即很多的process等待一個須較長CPU time才能完工的process *令Arrival Time皆為0 *Arrival order為P1、P2、P3 1、求Avg. waiting time ? 2、求Avg. Turnaround time ?

Solution 先畫Gantt chart P1 P2 P3 0 24 27 30 1、 Avg. waiting time 0 24 27 30 1、 Avg. waiting time = ( (0-0)+(24-0)+(27-0) )/3 = 51/3 =17 2、 Avg. Turnaround time = ( (24-0)+(27-0)+(30-0) )/3 = 81/3 = 27

RR (Round-Robin) Def: OS規定一個quantum time，若process未在此 EX: *Arrival time皆為0 *Arrival order為P1、P2、P3、P4 *Quantum time = 5 求Avg. waiting time ?

Solution P1 P2 P3 P4 0 5 9 14 19 22 27 28 Avg. waiting time 0 5 9 14 19 22 27 28 Avg. waiting time = ((0+(19-5)) + (5) + (9+(22-14)) + (14+(27-19))/4 = 58/4 = 14.5

Priority Def: 具有最高優先權的process優先取得CPU EX: *Arrival time皆為0 *Arrival order為P1、P2、P3、P4、P5 *採Non-preemptive priority *若priority value相同則採FIFO 求Average waiting time ?

Solution P2 P5 P1 P3 P4 0 1 6 16 18 19 Avg. waiting time 0 1 6 16 18 19 Avg. waiting time = (6 + 0 + 16 + 18 + 1)/5 = 41/5 = 8.2

SJF (Shortest Job First) Def: 最小CPU burst time的process優先取得 CPU控制權 EX: *令Arrival Time皆為0 1、求各processes的waiting time、turnaround time? 2、求Avg. waiting time ?

Solution 先畫Gantt chart P4 P1 P3 P2 0 3 9 16 24 1、 2、 Avg. waiting time 0 3 9 16 24 1、 2、 Avg. waiting time = (0+3+9+16 )/4 = 28/4 = 7 Process Waiting time Turnaround time P1 3 9 P2 16 24 P3 P4

SRJF (Shortest Remaining-time Job First) Def: 即preemptive SJF EX: 求Avg. waiting time ?

Solution 7 3 2 P1 P2 P4 P3 0 1 5 10 17 26 Avg. waiting time 3 2 P1 P2 P4 P3 0 1 5 10 17 26 Avg. waiting time = ((0+(10-1)) + (1-1) + (17-2) + (5-3))/4 = 26/4 = 6.5

Char 5 Deadlock

Deadlock Def: 系統中存在一組processes陷入彼此互相等待 身上所持有的資源，使得processes皆無法執 行下去，而造成CPU utilization大幅降低，因 而throughput下降

Starvation(餓死) Def：Process因長期無法取得完成工作所須 的所有資源，導致自身形成無限期停 滯的情況 解法：採用Aging技術(老化技術) 作法：隨process待在系統內的時間愈久逐步調 高優先權，在經過一段有限的時間後， 優先權會變最高而使得可取得空工所須 的所有資源

Starvation與Deadlock的差別 Starvation是在不公平、preemptive環境下易發生，且只有少數processes形成indefinite blocking，但其它processes仍可順利執行，另外也不一定會造成CPU utilization及throughput下降

Deadlock成立的四個必要條件 1、Mutual exclusion (互斥) 2、Hold & wait (持有並等待) 3、No preemptive (不可搶奪) 4、circular waiting (循環等待)

Mutual exclusion (互斥) Def: 對某些resource而言每次最多只允許一 個process持有並使用，其餘processes若 想使用則必須等待直到此resource被釋 放為止

Hold & wait (持有並等待) Def: process持有部份resources且又在等待被

No preemptive (不可搶奪) Def: 不可以搶奪其它processes的持有資源， 除非其它processes自願釋放這resources

Circular waiting (循環等待) Def: 系統中存在一組process如下 P1 P2 Pn ….. P1等待P2所持有的資源 P2等待P2所持有的資源 …. Pn等待P1所持有的資源

Deadlock處理的三種策略 1、Deadlock Prevention(死結預防) 2、Deadlock Avoidance(死結避免) 3、Deadlock Detection & Recovery(偵測並恢復) 保證系統不會進入死結 Throughput低 進入死結後再去解決 Throughput高

Deadlock Prevention (死結預防) 作法： [1] 打破Mutual Exclusion [2] 打破Hold & Wait 不可能 (∵互斥是某些resource與生俱有的性質) [法一]除非process可一次取得完工的所有資源才允許持有資源 [法二]允許process在執行時持有部份資源，一旦process提出其它 資源申請，則必須先釋放持有資源

Deadlock Prevention (死結預防) [3] 打破No preemption [4] 打破Circular waiting 改成preemption即可 (但會導致starvation) OS規定下列2件事 1、必須給予每個resource一個獨一無二的ID 2、process依resource ID遞增的方式提出資源申請

Deadlock Avoidance (死結避免) Banker’s Algo. Data structure Procedure Safety Algo. Safe Unsafe Deadlock 當process提出資源申請，利用Banker’s Algo判斷系統是否會進入Unsafe狀態，若會則否決此次的申請且Process須再隔一段時間才能再提出申請

Banker’s Algorithm Data structure (令有n個Processes, m種Resources) 1、資源總量 系統中各類資源的總量 2、Available[1…m] 目前系統可用的資源數量 3、Allocation[1…n, 1..m] 各process目前持有的各類資源數量 EX: A[i,j]=k 表示Pi目前持有k個Rj 4、MAX[1…n,1…m] 各process對各類資源的最大需求量 5、Need[1…n, 1…m] 各process還需要多少資源才可以完工 Need = MAX-Allocation 6、Request i [1…m] Pi目前提出的資源申請量 銀行(OS) 客戶(process)

會回傳一組safe sequence (即Schedule， Processes的執行順序 ) Banker’s Algorithm Procedure 若不成立則中止process 若不成立則process等待，直到有足夠的資源為止 若回傳”safe”則核准此次申請，否則否決此次申請 會回傳一組safe sequence (即Schedule， Processes的執行順序 )

Safety Algorithm Data structure 1、Work[1..m] 系統目前可用資源數量 2、Finish[1…n] 各Process是否完工

Safety Algorithm Procedure

Example 5個Processes P0~P4，資源總量：A(10) B(5) C(7) 一、算出Need、Available 二、若P1提出Request 1 = (1, 0, 2)，則依Banker’s Algo. 是否核淮 ?

Solution 一、 二、Banker’s Algorithm 1、check Request1 <= Need1 ∵(1,0,2) <= (1,2,2) ∴OK 2、check Request1 <= Available OK ∵(1,0,2) <= (3,3,2) ∴OK 3、Need1=Need1-Request1=(1,2,2)-(1,0,2)=(0,2,0) Allocation1=Allocation1+Request1=(2,0,0)+(1,0,2)=(3,0,2) Available=Available-Request1=(3,3,2)-(1,0,2)=(2,3,0) 4、Run Safety Algo.

Solution 二、Safety’s Algorithm 1、設定初值 Work = Available = (2,3,0) Finish=(f,f,f,f,f) 2、(1) 找到P1滿足Need1<=Work且Finish[1]=false 設定Finish[1]=true且 Work=Work+Allocation1=(2,3,0)+(3,0,2)=(5,3,2) (2) 找到P3滿足Need3<=Work且Finish[3]=false 設定Finish[3]=true且 Work=Work+Allocation3=(5,3,2)+(2,1,1)=(7,4,3) (3) 找到P0滿足Need0<=Work且Finish[0]=false 設定Finish[0]=true且 Work=Work+Allocation0=(7,4,3)+(0,1,0)=(7,5,3) (4) 找到P2滿足Need2<=Work且Finish[2]=false 設定Finish[2]=true且 Work=Work+Allocation2=(7,5,3)+(2,0,0)=(9,5,3) (0,2,0)

Solution (5) 找到P4滿足Need4<=Work且Finish[4]=false 設定Finish[4]=true且 Work=Work+Allocation4=(9,5,3)+(0,0,2)=(9,5,5) ∵Finish皆為true ∴Safe，核准P1的申請 (0,2,0) 回傳一組safe sequence 如下： P1、P3、P0、P2、P4

MFC Def: 一個微軟出的圖型化視窗程式，以C++為基礎

MFC常用的語法 字串變數 彈跳視窗 給予Edit box值 取得Edit box值 CString to int int to CString

MFC常用的語法 建立thread Thread名稱可任取 取得視窗 對視窗內的資源做操作 使用thread

Critical Section for MFC 1、宣告一個critical section全域變數mux 2、在OnInitDialog()內對critical section變數mux初始化 3、使用critical section變數mux

4、在button內執行這兩個threads

期末考重點複習 1、排程(scheduling ) 2、banker’s algorithm 2、記憶體配置策略(memory allocation schemes) 4、virtual memory

SJF (Shortest Job First) Def: 最小CPU burst time的process優先取得 CPU控制權 EX: *令Arrival Time皆為0 1、求各processes的waiting time、turnaround time? 2、求Avg. waiting time ?

Solution 先畫Gantt chart P4 P1 P3 P2 0 3 9 16 24 1、 2、 Avg. waiting time 0 3 9 16 24 1、 2、 Avg. waiting time = (0+3+9+16 )/4 = 28/4 = 7 Process Waiting time Turnaround time P1 3 9 P2 16 24 P3 P4

Memory allocation

Virtual memory

Solution 20484/4096=5….4 Page table內的第5個page存011此frame ∵frame佔3bits且offset佔12bits (∵4k) ∴physical address = 011000000000100