作業系統L5－行程排班

CPU-I/O分割

• 簡介:CPU分割後接著IO分割

CPU排班程式

• 短程排班程式(Short-term scheduler):就緒佇列選出形成配置CPU給他，包含轉換內容(context switch)，轉換成使用者模式
• CPU排班決策時刻
  • 執行->等待(不可搶先nonpreemptive)
  • 執行->就緒(可搶先preemptive)
  • 等待->就緒(可搶先preemptive)
  • 形成終止(不可搶先nonpreemptive)
• 分派潛伏期(dispatchlatency):分派程式用來停止一個行程，並開始另一個行程所用的時間
• 排班原則
  • CPU使用率(CPU Utilization)
  • 產量(Throughput)
  • 回復時間(Turnaround Time)
  • 等候時間(Waiting Time)
  • 反應時間(Response Time)

排班演算法

先來先做(FCFS)

• 等待時間:P1= 0; P2= 24; P3 = 27
• 平均等待時間:(0 + 24 + 27)/3 = 17
• 護送現象(convoyeffect) :短行程在長行程前面

最短工作先做(SJF)

• 平均等待時間= (3 + 16 + 9 + 0) / 4 = 7
• 分割時間:預估接近前一次的長度
• 
  
  
• 平均等待時間= [(10-1)+(1-1)+(17-2)+(5-3)]/4=26/4=6.5

優先權排班

• 每個行程都有優先權數字(越小=>越高優先權)
• 飢餓(Starvation):低優先權行程可能永遠無法執行
• 老化(Aging):隨著時間提高優先權
  
  
• 平均等待時間=8.2

依序循環(Round Robin, RR)

• 簡介:每個行程分一小段時間量(time quantum)q，用完行程會被搶先，加到就緒佇列的尾端
  
  
• 多層佇列
  • 簡介:分為多個獨立佇列，EX前景 背景
    

執行緒排班

• 行程競爭範圍(process-contentionscope, PCS)
• 系統競爭範圍(system-contentionscope, SCS)

多處理器

• 同質處理器(Homogeneous Processors):考慮所有處理器都相同
  • 非對稱多元處理(Asymmetric Multiprocessing):一個主處理器負責排班決定、I/O處理、其它系統活動，其他只執行使用者程式碼
  • 對稱多元處理(Symmetric Multiprocessing):每一個處理器自行排班
• 處理器親和性
  • 軟性親和性(soft affinity):保持一個行程在相同處理器上執行，但不保證它會永遠這麼做
  • 硬性親和性(hard affinity):指定處理器能夠執行特定行程
• 非均勻記憶體存取(non-uniform memory access
  • 
• 負載平衡(Load balancing ):試著讓工作量平均分布
  • 推轉移(Push migration):將過度負載CPU的行程推到其它CPU
  • 拉轉移(Pull migration):閒置處理器從忙碌處理器拉任務
• 利用記憶體停滯:另一個硬體執行緒在記憶體存取發生時執行
  • 

即時CPU排班(Real-time System)

• 軟即時系統:對於非常即時的行程排班沒有提供保證
• 硬即時系統–任務必須在指定的限期內被服務
• 中斷潛伏期(Interrupt Latency):中斷到達到開始執行中斷服務常式的時間
  • 
• 分派潛伏期(Dispatch Latency):停止目前行程並且啟動另一個行程的排班時間
  • 

單調速率排班演算法

單調速率排班而延誤截止期限

• 簡介:根據行程週期的反比設定優先權
• P1週期是50，P2週期是80，P1被設定優先權高於P2，P1處理時間25，P2處理時間35
  

最早截止期限優先排班(EDF)

• 簡介:優先權是根據截止期限設定
• P1週期是50，P2週期是80，P1被設定優先權高於P2，P1處理時間25，P2處理時間35