Linux排程調度筆記

一：Linux排程的四大要素

1：一段供過程執行的程序，該程序可以被多個排程執行。

2：獨立的内核堆棧。

3：排程控制快（task_struct：有了這個數據結構，排程才能成為內核調度的一個基本單位接受內核的調度。

 同時，這個結構還記錄著排程所佔用的各項資源。

4：獨立的存儲空間：即擁有專有的用戶空間，除了前面的內核空間還有用戶空間。

  線程：只有前三條，沒有第四條。內核線程：完全沒有用戶空間。用戶線程：共享用戶空間。                                                                                                      

二：Linux 排程的調度時機                                                                                                                                  

1．排程狀態轉換時： 如排程終止，睡眠等；

2．可運行隊列中增加新的排程時；

3．當前排程的時間片耗盡時；

4．排程從系統調用返回到用戶態時；

5．內核處理完中斷後，排程返回到用戶態；                                                                                                                                                                               

三：排程隊列：對隊列都有初始化、添加、刪除等功能。 

1：運行隊列：Linux系統為處於就緒態的排程的隊列，只有在這個隊列中的排程才有機會獲得CPU。

2：等待隊列：，Linux系統也為處於睡眠態的排程組建了一個隊列。

Scheduling的基本概念:

CPU Scheduling的目的-讓CPU的效能在multiprogramming的環境下提高

CPU-I/O burst輪流循環

(例如)

橫軸 CPU週期， 縱軸 頻率

可以看出大於8 millisecond的不多，代表短時間內CPU和I/O交互使用

CPU Scheduler:

主要是指Short-term scheduler

scheduling的時間點:

1.running 到 waiting

2.running 到 ready

3.waiting 到 ready

4.何時結束

其中1和4是要讓它做完成，不能中斷

其他2和3是可以被中斷的，但是要小心(1)是否有用到shared data、(2)是不是在kernel mode、(3)是否能接受interrupts

Dispatcher:

(真正在做context switch的部分、真正把CPU控制權交給scheduler選定的process)

包括:

switching context(register和program counter內容的交換)

switching to user mode

把控制權交到user program原來的program counter所指定的位址執行

context switch會產生dispatch latency-(把process停掉，儲存，控制權交給另一個process，再把原資料load回去，再開始執行，中間的過程所需要的時間。)-希望是不要太高。

Scheduling的標準:

CPU utilization-讓CPU盡量保持忙碌。

Throughput-在單位時間之內能夠完成的工作量。

Turnaround time-對每一個process，從他進入到完成所需要花費的時間。越短越好。

Waiting time-被Scheduing load裡面準備要用cpu得時間開始算，到執行結束的時間。越短越好。

Response time-在time sharing的環境中，有一個request過來，等多少時間可以Response回去的間隔。

排程方法有如下：

(一)

先進先出((First in First out，FIFO)
目前的process離開時，選擇在等待佇列中等待最久的process
是否會有Starvation產生：不會

假設有3個process P1，P2，P3

進入順序P1 >P2>P3

Burst time :P1=24，P2=3，P3=3

Waiting time : P1=0，P2=24，P3=27

Average waiting time : (P1+P2+P3)/3=17

進入順序改變:

Ｐ２＞Ｐ３＞Ｐ１

Waiting time變成　P1=６，P2=０，P3=３

Average waiting time：３

改變順序 為什麼等待時間會改變呢?

因為Convoy effect(短得等在長得後面)會讓整個平均時間變比較久。

(二)

最短process優先(Shortest Process First，SJF)- exponential averaging
選擇執行時間最短的process先執行，但此種方法必須事先知道或是估算process所需的執行時間
是否會有Starvation產生：有可能

很理想，但困難度在於，我們要如何知道他process運行的時間。

SJF基本上是一個最佳化(Optimal)的排程演算法。

怎麼來預估Next CPU Burst?

利用exponential averaging來統計

1.假設n個cpu burst，第ｎ個cpu burst長度是

2.假設下一個CPU Burst是n+1

3.在設一個變數為，01

4.Define: n+1 =+(1-)n

一般執行到某個點得時候，來了個process比現在的還短，中斷立刻先去做另一個更短的

稱之為Shortest-remaining-time-first

(三)
優先權排班方式 (Priority Scheduling)

最短的工作先做(SJF)是一般優先權排班演算法的一個特例。每一個行程都有它的優先順序。CPU將分配給具有最高優先權的行程，具有相同優先順序的行程則按照FCFS來排班。

一般來講在Priority的表示法是用整數來表示，數字越小，Prority越高。

是否會有Starvation產生：有可能

(四)

循環(Round-Robin，RR )
利用計時器固定週期產生中斷，並且將目前正在執行的process移到等待佇列中，再以FCFS方式從等待佇列中擇一process執行
是否會有Starvation產生：不會

設立一個１０～１００msec的time quantum，當這時間用完，不管process有沒有執行完，它都要結束，換另外一個process。

所以假設有ｎ個process在ready queue，time quantum是ｑ

每一個Process得到1/n CPU Time

基本上沒有一個process等到(n-1)q time unit.(就是總會輪到它)

如果ｑ很大，等於ＦＩＦＯ

如果ｑ很小，context switch會變得非常頻繁，context swith要10usec

RR Average turnaround雖然沒有SJF那麼好，但是reponse比較好，因為會輪流。

(五) Multilevel queue

把ready Queue分成兩個queue

(1)foreground queue    (需交談)

(2)background queue   (需批次處理)

Foreground需交談使用RR，background queue則是FCFS

80%時間給foreground queue  20%時間給 background queue

(六) Multilevel feedback queue

Multilevel queue在做改進

process可以在queue間移動 ，例如aging。

但他要考量的也有很多

到底有幾個queue、每個queue的演算法、什麽時候要upgrade、什麽時候要demote

是一個比較動態的排程機制。

(七)Thread Scheduling（執行緒排程）

分成user-level 和 kernel-level

因為當thread支援得時候,不是只有process要Scheduling, thread也要

如果在Many-to-one 和many-to-many model，user-level就必須經過Scheduling，這個過程稱為process-contention scope (PCS)由programmar來做

另外一個是由Kernel thread 來schedule，被稱為system-contention scope (SCS)由系統來做

(八) Multiple-Processor Scheduling

有多個CPU

可能是Homogeneous processors (同時用一顆CPU)

Asymmetric multiprocessing(非對稱式) 其中一個CPU來主導他可以存取的，Data-sharing也是由他負責，所以稱為非對稱。

Symmetric multiprocessing (SMP)

對稱式的，每一個process自己來做Scheduling

Processor affinity有著不同的關係。例如：

soft affinity

hard affinity

ＮＵＭＡ

把系統切成數個節點 (node)，每個處理器及記憶體就位在某一個節點上，當處理器存取同一個節點的記憶體時，可以有較高的存取速度；而存取其他節點的記憶體時，就需要透過節點間的資料傳遞，會耗費較多時間。

Multicore Processors

trend同一個Chip裡面

跟傳統的Multiprocessors比起，更快，更省power 。

（九）Real-Time CPU Scheduling　即時應用排程

比一般只考慮system的更複雜

一般real time system分成兩類:

Soft real-time systems跟Hard real-time systems

Soft real-time systems:

系統盡量幫忙你達到你的目標，但是不保證

Hard real-time systems:

所有的工作，都必須在deadine前完成。

在real-time裡面,根據優先順序處理事很重要的

(一)假設process時間是t,deadline是 d, 週期性的check,周期是p

(二)0 ≤ t ≤ d ≤ p

(三)頻率是 1/p

在實務上,虛擬化的環境上

一個作業系統上還有好幾個作業系統

上面有的作業系統是guest OS

每一個guest要有自己的排程方法,會產生幾個問題

(一)他不知道他自己可能沒有真正使用CPU

(二)Response time沒有原本自己單一OS控制CPU好

(三)不同OS的時間可能不一致

一般Real time中最常使用到的演算法 : Rate Montonic Scheduling

依據頻率的大小來做排程

周期越短的給越高的優先順序，周期越長的給越低的優先順序

但deadline有可能會miss掉

改善方式: Earliest Deadline First Scheduling (EDF)

誰最快到他的deadline，越高的優先順序

比較注重公平性的：Proportional Share Scheduling

總共ＣＰＵ時間是Ｔ

有Ｎ個要分享，Ｎ＜Ｔ

保證每個應用程序將收到的總處理器時間N / T

事前把我們資源比例分配好