Process Scheduling

Basic

• wating time

  • 在ready queue中等待的時間

• turnaround time

  • 進去到出來的時間

• response time

  • 第一個回應的時間

First-Come First-Served

• 先進來的先執行

• Convoy effect : 其他process等待一個執行時間很長的process

• lower CPU and device utilization

Shortest-Job-First

• 短的先執行(短的優先權高)

• 如果這些process同時進來會有最佳解

• 常用在 long-term scheduling

Shortest-Remaining-Time-First

• 剩下執行時間短的先

• 如果這些process進來的時間不固定會有最佳解

Priority

• SJF是Priority的special case

• Starvation : 低優先權的可能永遠不能執行

• Aging : 系統中的process隨著存在時間提高優先權

Round-Robin

• 如果一個process在time quantum中執行完畢

  • 繼續執行下一個ready queue中的process

• 如果一個process在time quantum中執行不完

  • context switch

• n processes with time quantum q

  • 不會等超過 (n-1)q time units

• large q : FIFO(better turnaround time)

• small q : better response time

• overhead

  • q must be large with respect to context switch

Multilevel Queue

• 透過process的 memory size 或 process priority 決定要放到哪個queue

• 每個queue有自己的scheduling algorithm

  • foreground(interactive) : RR
  • background(batch) : FCFS

• 每個queue間採用preemptive的方法

Multilevel Feedback Queue

• 每個queue也有自己的priority

• queue 0
  • 沒有執行完的會被丟到queue 1
• queue 1
  • 只有在queue 0 是空的才能執行
  • 沒有執行完的會被丟到queue 2
• queue 2
  • 只有在queue 0和queue 1是空的才能執行

---

last edit

dotMon, Jan 6, 2020 3:21 PM

HOME PAGE

tags : OS CSIE