05. 行程排班/排程 (Process Scheduling)

行程排程(Process Scheduling)

 

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 outFIFO)
目前的process離開時,選擇在等待佇列中等待最久的process
是否會有Starvation產生:不會

假設有3process P1P2P3

進入順序P1 >P2>P3

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

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

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

進入順序改變:

P2>P3>P1

Waiting time變成 P1=6,P2=0,P3=3

Average waiting time:3

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

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

 

()

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

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

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

 

怎麼來預估Next CPU Burst?

利用exponential averaging來統計

1.假設ncpu burst,第n個cpu burst長度是

2.假設下一個CPU Burstn+1

3.在設一個變數為01

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

 

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

稱之為Shortest-remaining-time-first

 

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

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

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

是否會有Starvation產生:有可能

 

 

()

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

設立一個10~100msectime quantum,當這時間用完,不管process有沒有執行完,它都要結束,換另外一個process

所以假設有n個processready queuetime quantum是q

每一個Process得到1/n CPU Time

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

如果q很大,等於FIFO

如果q很小,context switch會變得非常頻繁,context swith10usec

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支援得時候,不是只有processScheduling, thread也要

如果在Many-to-one many-to-many modeluser-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

 

NUMA

把系統切成數個節點 (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,deadlined, 週期性的check,周期是p

(二)0 ≤ tdp

(三)頻率是 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

總共CPU時間是T

有N個要分享,N<T

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

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