3.4 行程

目錄

  • Process Definition
  • Program vs Process
  • Process STD
  • PCB, context switching
  • CPU Scheduling algorithm
  • Thread 執行緒

CPU Scheduling algorithms

=> 針對 STS 從 Ready Queue 挑出一 process 獲得 CPU 之挑選策略方法

  • FIFO
  • SJF
  • SRJF
  • Priority
  • RR
  • Multilevel Queue
  • Multilevel Feedback Queue
  1. FIFO First-In First-Out
    Def: 愈先到達 Ready Queue 的 process, 先獲得 CPU

  • Non-preemptive (不可搶奪)
    優點：

    • 公平性 (Fair)
    • easy to implement
    • No starvation 飢餓
      Def: 指 low priority 之 process 長期或無限期無法取得 CPU 之服務

    缺點：

    • 效益不佳 (因為 A.W.T & A.T.T 慢)
    • 會有 convoy effect (護衛效應)
      指多個 process 在 wait 一個需長時間執行之 process => 造成 A.W.T 大幅上升
    • Note:
      A.W.T: Average Waiting time
      A.T.T: Average Turnaround time (結束時間)

  • Example: CPU Scheduling algorithms 的衡量準則 (performance criteria 效能準則)
    Sol:

    1. CPU utilization -> 看 CPU 使用率
    2. CPU throughput -> 看 CPU 單位生產量
    3. Waiting time 等候時間
      Def: 自 process 交付系統到結束, 總共在 Ready Queue 等了多久
    4. Turnaround time 回覆時間
      Def: 自 process 交付系統到結束, 總共需多少時間
    5. Response time (反應)
      Def: 指 process 自交付系統到第一次獲得回應的時間 -> interactive system care about this
      Note: 1. ~ 2. 愈高愈好, 3. ~ 5.時間愈短愈好

  • Ex: 採 FIFO,

    Process CPU Burst time (CPU 花費時間) CPU arrive time
    P1 24 0
    P2 3 0
    P3 3 0
    Sol:
    A.W.T = (0 + 24 + 27) / 3 = 17
    A.T.T = (24 + 27 + 30) / 3 = 27
  1. SJF (Shortest Job First) 最短工作先做
    Def: 指所需的 CPU 時間愈短, 愈先獲得 CPU 之服務
  • Non-preemptive
    優點：
    • 效益最佳 (A.W.T & A.T.T 短)
    • No convoy effect
    • 適用於 LTS
      缺點：
    • No fair
    • 可能會有 starvation
    • 不適用於 STS (預測 process 時間耗時) -> 一般拿來當理論依據值
  1. SRJF (Shortest Remaining Time Job First) 最短剩餘時間工作先做
    Def: 同 2. , 但為 preemtpive, 且 Context Switching 較重

  • ex:

    Process CPU Burst time (CPU 花費時間) CPU arrive time
    P1 8 0
    P2 4 1
    P3 9 2
    P4 5 3
    分別採 SJF & SRJF, 求 A.W.T & A.T.T = ?
    Sol:
    1. SJF

      A.W.T = (0 - 0 + 8 - 1 + 17 - 2 + 12 - 3) / 4 = 7.75
      A.T.T = (8 - 0 + 12 - 1 + 26 - 2 + 17 - 3) / 4 = 14.25
    2. SRJF

      A.W.T = (0 - 0 + 10 - 1 + 1 - 1 + 17 - 2 + 5 - 3) / 4 = 6.5
      A.T.T = (17 - 0 + 5 - 1 + 26 - 2 + 10 - 3) / 4 = 13

  • Compare

    Preemptive (SRJF) Non-preemptive scheduling (SJF)
    Process 取得 CPU 後, 過程可能被其他 process 將 CPU 搶走 一旦 process 取得 CPU, 除非自願放棄, 否則其他process 不能搶
    適用於即時, 交談式 對 job 較公平, Reponse time 較可預期
    Context switching 重 (缺點) Context switching 輕 (優點)
    A.W.T & A.T.T 短 (優點) A.W.T & A.T.T 長 (缺點)
  1. Priority Scheduling (優先權排列法則)
    Def: priority 愈高者, 愈先取得 CPU 之服務
  • Special case:
    1. Arrive time 越短, Priority 越高 => FIFO
    2. CPU Burst time 越短, Priority 越高 => SJF
  • 又可分為：
    • Preemptive => 易造成 starvation
      • Solution: 採 “Aging Technique” (老化技術)
        Def: 指每隔一段時間逐步將 low priority 之 process 的 優先權提高
    • Non-preemptive => 當 priority 相同 => 採 FIFO
  • Ex: 採 priority 求 A.W.T & A.T.T ?
    Process CPU Burst time (CPU 花費時間) Priority (編號小, priority 高)
    P1 10 3 No.3
    P2 1 1 No.2
    P3 2 3 No.4
    P4 1 4 No.5
    P5 5 2 No.2
    Sol: 
      ![](expriority.png)  
  A.W.T = `(6 + 0 + 16 + 18 + 1) / 5 = 8.2`  
  A.T.T = `(16 + 1 + 18 + 19 + 6) / 5 = 12`
  1. Round-Robin (R.R)

  • Def: 指輪流給各 process 一固定時間

    • 時間到就得將 CPU 交由下一個 process 執行
    • 具下列特色：
      1. Fair
      2. preemptive
      3. Non-starvation

  • Special Case:

    1. CPU time slice (時間週期) 約等於無限 => FIFO
    2. CPU time slice 極小 => CPU Sharing, But Context Switching 非常重

  • Ex: 採 R.R time slice = 5, 求 A.W.T & A.T.T ?

    Process CPU Burst time (CPU 花費時間) CPU arrive time
    P1 8 0
    P2 2 3
    P3 7 6
    Sol:
    A.W.T = (0 - 0 + 7 - 5 + 5 - 3 + 10 - 6) / 3 = 8/3
    A.T.T = (10 + 7 - 3 + 17 - 6) / 3 = 25/3
  1. Multilevel Queue (多重佇列)
  • Def:
    • 將 Ready Queue 拆成多個 Queue
    • Queue 之間採 preemptive priority scheduling
    • 各 Queue 可採用自己的排班法則
  • 優點：可依 process 屬性將之放置到適當的位置
  • 缺點：此方法下, process 無法於 Queue 之間移動, 故會有 starvation 之問題
  • 圖：
  1. Multilevel Feedback Queue (多層回饋佇列)
    Def: 同 6. , 但 process 可於 Queue 之間挪動
    策略：
    1. 於下層的 process 每隔一段時間往上一層移動
    2. 於上層的 process 不需 CPU 時逐步往下層移動
  • Summary