1.背景

<bdo id='LYOFL'><sup id='5mps9'><div id='dBNcD'><bdo id='afzmD'></bdo></div></sup></bdo>

本文主要是講解一下linux系統的cpu是怎么工作，怎么調度的。但是在整理文章的過程中，想起了本科時的電子c51單片機，就想著從原來的這些知識整理入手來讓大家更好理解。linux的cpu調度。

既然是調度，可能還是要講清楚： what, when, how. 什么是調度，什么時候發起調度，怎么調度的問題。

2. 單片機C51的中斷

2.1 C51是什么?

C51就是如下這么個簡單的小芯片，上面沒有操作系統，20管腳接地，40管腳接5伏電源，然后18和19管腳接上12M晶振就能工作了。然后以前本科的時候，用一個簡單的代碼燒錄器就能將寫好的C語言代碼寫進去，去控制這個芯片進行工作。

能實現什么效果尼？例如能讓這個管腳電壓為高(5v)，就能點亮管腳對應的二極管。

可以參考這個百科

baike.baidu.com/item/51%E5%8D%95%E7%89%87%E6%9C%BA/5344633

2.2 C51的中斷

2.2.0 中斷是什么

中斷其實就是在執行主代碼邏輯的過程中，跳出當前的代碼段，去執行一個中斷服務代碼段，執行完了然后回到跳出的位置繼續執行的過程。

中斷上下文: 代碼位置點信息, SP, CP等寄存器數據

中斷處理程序: interrupt_handler函數

2.2.1 中斷的種類

如下圖，為C51這個單片機。

可能很多人看了這個圖，會有暈不知道說的啥意思。我來總結一下，

a. 中斷其實分為外部和內部中斷，

* 外部中斷就是INT0和INT1，它的發起源是來自芯片的12和13管腳。怎么去觸發這個外部中斷尼？可以往這個管腳接一個開關，另外一段接地。按下開關，產生一個低電平，就能產生一個外部中斷了。

* 內部中斷(T0,T1,T2), 剛才說到C51單片機要外接一個12M的晶振，也就是外部的這個晶振1秒能產生12M次電平波動，然后C51會將這個電平波動次數，存儲在內部的寄存器里，然后代碼去讀取寄存器的值，當寄存器達到一定數值就會產生中斷。

2.2.2 中斷優先級

中斷優先級就是寫死了這么幾個。也就是說，如果你正在執行T1中斷的代碼，這個時候來了T0中斷，是有可能觸發二次中斷嵌套的。

C51單片機最多允許2層的中斷嵌套。

2.2.3 中斷的用處

例如我希望去實現一個功能: 定時控制一個二進制管的開和關。

以12Mhz的晶振、定時10ms為例：
51單片機為12分頻單片機，因此執行一條指令的時間是12×(1/12M) s，即計數器每1us加一。
若定時10ms，則共需要加10000次。
因此將TH0、TL0設置從（65536-10000）= 55536開始計數。55536 的16進制為0xD8F0。因此將TH0設置為0xD8,TL0 設置為0xF0。

#include <reg52.h>
#define uchar unsigned char
uchar num=0; //全局變量num
sbit led=P2^0;//p2.0口控制led燈
void main()
{
	led=1;//led初始為亮
	TMOD=0x01;
	TH0=0xD8;//高四位
 	TL0=0xF0;//低四位，延時10ms
	EA = 1;//打開總中斷
 	ET0 = 1;//T1開，定時器溢出
	 TR0 =1;//開定時器
	while(1)
	{	
		if(num==10)//亮1秒
		{
			led=0;  
		}	 
		if(num==20)//滅2秒
		{
			led=~led;
			num=0;
		}
			
	}
}
void TR0_time() interrupt 1	//定時器中斷函數
{
	TH0=0xD8;//高四位
 	TL0=0xF0;//低四位，延時10ms
   	num++;

}

代碼解讀:

我們可以看到引入了一個reg52.h的c頭文件，這個是封裝了通過匯編去讀取底層寄存器的接口，其實這些中斷的計數器都是存儲在寄存器里頭，寄存器有對應的地址的。這里不詳細展開，有興趣的朋友可以去讀一下匯編指令相關的文章。

2.3 小結

通過第二小節，我們知道了C51單片機中斷的種類、中斷優先級、中斷的寄存器，并且通過一個定時打開和關閉二極管的實例來講解了中斷的作用。

3. 從單片機中斷到Linux操作系統

首先中斷是針對單個處理核的，因為單片機是單核的，而linux的一般是多核的。

3.1 linux的中斷

這里舉一個例子:

內存缺頁中斷:

我們知道fork出來的進程，它是有獨立的內存地址空間的，但是它不是立刻產生和父進程一樣大小的物理內存空間，而且Copy on write機制。

那么當子進程訪問的內存空間，還沒有copy完畢的時候，就會主動一個內存缺頁錯誤中斷: 來進行這個物理內存的拷貝完成，再回到子進程的流程就能進行對應的內存訪問了。

3.2 中斷和進程調度

中斷描述表(interrupt descriptor table)（IDT）中記錄了中斷請求（IRQ）和中斷服務程序（ISR）的對應關系。Linux 中定義了從 0 到 256 的 IRQ 向量。

和上面的C51單片機定時中斷的基本邏輯一樣， Linux也是有個Timer中斷來驅動不斷去執行不同的邏輯。這個時間的中斷注冊到中斷描述表，是在Linux啟動的時候去做的。

那么我們來看看Linux的時間中斷處理流程:

跟隨者Linux的代碼腳印我們看看，時間中斷是怎么去執行我們最后的hello world進程的。

void update_process_times(int user_tick)
{
	scheduler_tick();
	if (IS_ENABLED(CONFIG_POSIX_TIMERS))
		run_posix_cpu_timers();
}

github.com/torvalds/linux/blob/631aa744423173bf921191ba695bbc7c1aabd9e0/kernel/time/timer.c#L2064

void scheduler_tick(void)

{
	int cpu = smp_processor_id();
	struct rq *rq = cpu_rq(cpu);
	struct task_struct *curr = rq->curr;
	curr->sched_class->task_tick(rq, curr, 0);   //  調度到哪個進程主要是看這里。
....
}

github.com/torvalds/linux/blob/93761c93e9da28d8a020777cee2a84133082b477/kernel/sched/core.c#L5498

這個sched_class是個什么東西尼？

它是定了一些接口的結構體
github.com/torvalds/linux/blob/bf57ae2165bad1cb273095a5c09708ab503cd874/kernel/sched/sched.h#L2164
linux/kernel/sched目錄下實現了若干個調度算法: stop,deadline, fair, rt, idel等調度算法，這個是根據不同類型的進程選擇不同的調度算法的
github.com/torvalds/linux/blob/bf57ae2165bad1cb273095a5c09708ab503cd874/kernel/sched/fair.c#L12375
調度算法優先級
rt > dl > stop > fair > idle

3.1.3 如何查看linux的中斷

各個cpu發生中斷類型和次數統計。

這里的TIMER就是時間中斷。

3.1.4 /proc/irq

這個是系統里注冊了多少個中斷信號源。

可以給每個中斷信號去設置指定處理的cpu。每個信號下面的目錄里smp_affinity。

3.1.5 /proc/interrupts

irq編號，每個cpu對該irq的處理次數，中斷控制器的名字，irq的名字，以及驅動程序注冊該irq時使用的名字

3.1.6 top命令

這里從top的輸出可以看到:

hi: 硬件中斷
si: 軟件中斷
PR: 進程優先級， rt表示是實時進程。至于進程優先級=20，是個什么含義，暫時不在本文展開了。
NI: 進程nice值

4. Linux的調度算法

好了，上面鋪墊了半天，終于來到了調度算法。

在前面講解了什么時候發起調度，調度的是什么實體之后，我們講解一下怎么調度，也就是該執行哪個代碼程序。因為不像C51單片機，單核、中斷數量那么小的處理。 Linux所處理的中斷會復雜很多。

其實舉個例子: 當你從鍵盤敲下Q，然后文本編輯框顯示一個Q，就是一個鍵盤的設備外部中斷到對應的中斷程序代碼執行。

如果你按下Q，半天都沒有執行這段顯示Q的中斷代碼，你在電腦前是不是會很崩潰，啊，我的天，怎么卡主了。電腦你是不是壞了。

下面來看看這個調度算法的演進流程。

4.1 調度算法的基礎

調度算法的原則
- 在1個cpu選擇最優的task來運行。例如普遍認為io-bound task需要更好的優先級
- 沒有餓死
- 調度速率
調度算法演進
- Linux 2.4: o(n)調度器
- Linux2.6較早版本: o(1)調度器
- Linux 2.6.23+: o(log n) CFS調度器

4.1 o(n) 調度算法

調度器基本架構
進程優先級:
- 2個靜態優先級，進程的生命周期內都不會改變
  - 實時優先級
    - 實時任務: 1-99
    - 普通任務: 0
  - nice優先級
    - 普通任務:0
    - 人工調整: [-20,19], 可以通過nice命令進行調整
- 動態優先級
  - time slice counter: 進程在調度過程中，

調度算法代碼邏輯

schedule邏輯

void schedule(){
  struct task_struct *next, *p;
  struct list_head *tmp;
  int this_cpu = ..., c;
  spin_lock_irq(&runqueue_lock); //Disable interrupts,
  //grab global lock.
  next = idle_task(this_cpu);
  c = -1000; //Best goodness seen so far.
  list_for_each(tmp, &runqueue_head){     // for 循環獲取每個task
  p = list_entry(tmp, struct task_struct, run_list);
  if (can_schedule(p, this_cpu)) {    // 判斷這個task是否能在這個cpu運行，因為有些任務是綁核運行的
  int weight = goodness(p);      // 計算這個任務的權重
  if(weight > c){                // 找權重最大的那個task
  c = weight;
  next = p;
 }
 }
}
spin_unlock_irq(&runqueue_lock);
switch_to(next)            // 跳轉到對應任務

goodness邏輯

int goodness(struct task_struct *p){
  if(p->policy == SCHED_NORMAL){   // 普通進程
  //Normal (i.e., non-"real-time") task
  if(p->counter == 0){        // 如果這個進程已經用完了它對應的cpu時間就直接返回0
  //Task has used all of its
  //time for this epoch!
  return 0;
  }
  return p->counter + 20 - p->nice;    // 普通進程權重計算
}else{    // 實時進程
  //"Real-time" task
  return 1000 + p->rt_priority;   // 實時進程增加了1000，使得實時進程的權重肯定大于普通進程
  //Will always be
  //greater than
  //priority of a
  //normal task
  }
}

總結
- 選擇task需要o(n)時間復雜度
- 鎖競爭: cpu從全局可運行隊列取task的時候，有鎖競爭
- 適合于單核的系統

4.2 o(1) 調度算法

架構圖

每個cpu都有一個runqueue結構體

struct runqueue{ 
spinlock_t lock; 
struct task_struct *curr; 
prio_array_t *active; 
prio_array_t *expired;}


struct prio_array{ 
unsigned int nr_active; 
struct list_head queue[MAX_PRIO]; 
unsigned long bitmap[BITMAP_SIZE];
}

工作原理

schedule代碼邏輯

void scheduler_tick(){ //Called by the timer interrupt handler.
runqueue_t *rq = this_rq();
task_t *p = current;
spin_lock(&rq->lock);
if(!--p->time_slice){  沒有時間片了
    dequeue_task(p, rq->active);
    p->prio = effective_prio(p);
    p->time_slice = task_timeslice(p); // 計算當前運行進程的剩余時間片
   if(!TASK_INTERACTIVE(p) ||    // 不是交互式進程，就放到expired隊列，就暫時不執行
    EXPIRED_STARVING(rq)){
   enqueue_task(p, rq->expired);
   }else{ //Add to end of queue.
    enqueue_task(p, rq->active);     // 否則放到active隊列尾部，
   }
}else{ //p->time_slice > 0   // 如果是普通進程，就保持在對應的active隊列進行執行
    if(TASK_INTERACTIVE(p)){
    //Probably won't need the CPU
    //for a while.
    dequeue_task(p, rq->active);
    enqueue_task(p, rq->active); //Adds to end.
   }
  }
spin_unlock(&rq->lock); //Later, timer handler calls schedule().
}

goodness
- 和o(n)調度器大同小異，就是給與實時進程一些bonus，讓他獲得更大的優先級
cpu執行
- cpu從自己的active 隊列里，根據bitmap來去queue的task來執行。
- 如果active隊列為空，則將active和expired隊列互換
- 繼續第一步

總結
- 每個cpu都有自己的調度數據結構，避免的了全局鎖
- 每一個調度優先級都有自己的數組，而且結合位圖，可以實現o(1)的取task邏輯
- TASK_INTERACTIVE(p) 和EXPIRED_STARVING(rq)) 代碼邏輯比較復雜

4.3 CFS 調度算法

目標
- 一個更加優雅的調度算法， o(1)算法有些地方實現臺奇特了。
- 這個也是Linux作者的決策
調度算法主要邏輯
- 相比于o(1)的通過隊列數組和bitmap來維護可運行task，cfs使用紅黑樹來存儲
  - 每次取最左邊的task來進行運行。
- 紅黑樹優點
  - 自均衡
  - 在寫入、刪除、搜索都能保持 o(log N)
- 紅黑樹的key是virtual runtime
  - 計算方法:
    - Nice值通過一個數組轉換為weight
```
static const int prio_to_weight[40] = { 
/* -20 */ 88761, 71755, 56483, 46273, 36291, 
/* -15 */ 29154, 23254, 18705, 14949, 11916, 
/* -10 */ 9548, 7620, 6100, 4904, 3906, 
/* -5 */ 3121, 2501, 1991, 1586, 1277, 
/* 0 */ 1024, 820, 655, 526, 423, 
/* 5 */ 335, 272, 215, 172, 137, 
/* 10 */ 110, 87, 70, 56, 45, 
/* 15 */ 36, 29, 23, 18, 15,
}
```
    - 計算vruntime公式
```
delta_exec = now - curr->exec_start; 
delta_exec_weighed = delta_exec * (NICE_0_LOAD / t->load.weight); 
curr->vruntime += delta_exec_weighted;
```
    - 結果
      - nice=0, vruntime等于它的實際cpu執行時間
      - nice<0, vruntime會小于他實際cpu執行時間
      - nice>0, vruntime會大于它的實際cpu執行時間
      - 這樣子就能實現nice越小，就越優先調度了
CFS總結
- 使用運行時間而不是時間片來衡量進程，粒度能去到納秒
- 是否比o(1)更加好？
  - 時間粒度更加細
  - o(1) 看起來比o(log n)更加快
  - vruntime會比time slice更加公平
  - cfs也有很奇怪的地方，就是一直取最左task來運行，是否會讓task失去 cache locality

5. 總結

本文首先通過C51單片機的中斷和定時二極管功能代碼實例，展示了C51的中斷作用和運行機制; 然后講解Linux的中斷系統，中斷和進程調度的關系，講解了當前Linux的幾種調度算法實現。最后深度講解了Linxu的調度算法引進過程。

1.背景

既然是調度，可能還是要講清楚： what, when, how. 什么是調度，什么時候發起調度，怎么調度的問題。

2. 單片機C51的中斷

2.1 C51是什么?

能實現什么效果尼？例如能讓這個管腳電壓為高(5v)，就能點亮管腳對應的二極管。

可以參考這個百科

baike.baidu.com/item/51%E5%8D%95%E7%89%87%E6%9C%BA/5344633

2.2 C51的中斷

2.2.0 中斷是什么

中斷其實就是在執行主代碼邏輯的過程中，跳出當前的代碼段，去執行一個中斷服務代碼段，執行完了然后回到跳出的位置繼續執行的過程。

中斷上下文: 代碼位置點信息, SP, CP等寄存器數據

中斷處理程序: interrupt_handler函數

2.2.1 中斷的種類

如下圖，為C51這個單片機。

可能很多人看了這個圖，會有暈不知道說的啥意思。我來總結一下，

a. 中斷其實分為外部和內部中斷，

2.2.2 中斷優先級

中斷優先級就是寫死了這么幾個。也就是說，如果你正在執行T1中斷的代碼，這個時候來了T0中斷，是有可能觸發二次中斷嵌套的。

C51單片機最多允許2層的中斷嵌套。

2.2.3 中斷的用處

例如我希望去實現一個功能: 定時控制一個二進制管的開和關。

#include <reg52.h>
#define uchar unsigned char
uchar num=0; //全局變量num
sbit led=P2^0;//p2.0口控制led燈
void main()
{
	led=1;//led初始為亮
	TMOD=0x01;
	TH0=0xD8;//高四位
 	TL0=0xF0;//低四位，延時10ms
	EA = 1;//打開總中斷
 	ET0 = 1;//T1開，定時器溢出
	 TR0 =1;//開定時器
	while(1)
	{	
		if(num==10)//亮1秒
		{
			led=0;  
		}	 
		if(num==20)//滅2秒
		{
			led=~led;
			num=0;
		}
			
	}
}
void TR0_time() interrupt 1	//定時器中斷函數
{
	TH0=0xD8;//高四位
 	TL0=0xF0;//低四位，延時10ms
   	num++;

}

代碼解讀:

2.3 小結

通過第二小節，我們知道了C51單片機中斷的種類、中斷優先級、中斷的寄存器，并且通過一個定時打開和關閉二極管的實例來講解了中斷的作用。

3. 從單片機中斷到Linux操作系統

首先中斷是針對單個處理核的，因為單片機是單核的，而linux的一般是多核的。

3.1 linux的中斷

這里舉一個例子:

內存缺頁中斷:

我們知道fork出來的進程，它是有獨立的內存地址空間的，但是它不是立刻產生和父進程一樣大小的物理內存空間，而且Copy on write機制。

3.2 中斷和進程調度

中斷描述表(interrupt descriptor table)（IDT）中記錄了中斷請求（IRQ）和中斷服務程序（ISR）的對應關系。Linux 中定義了從 0 到 256 的 IRQ 向量。

那么我們來看看Linux的時間中斷處理流程:

跟隨者Linux的代碼腳印我們看看，時間中斷是怎么去執行我們最后的hello world進程的。

void update_process_times(int user_tick)
{
	scheduler_tick();
	if (IS_ENABLED(CONFIG_POSIX_TIMERS))
		run_posix_cpu_timers();
}

github.com/torvalds/linux/blob/631aa744423173bf921191ba695bbc7c1aabd9e0/kernel/time/timer.c#L2064

void scheduler_tick(void)

{
	int cpu = smp_processor_id();
	struct rq *rq = cpu_rq(cpu);
	struct task_struct *curr = rq->curr;
	curr->sched_class->task_tick(rq, curr, 0);   //  調度到哪個進程主要是看這里。
....
}

github.com/torvalds/linux/blob/93761c93e9da28d8a020777cee2a84133082b477/kernel/sched/core.c#L5498

這個sched_class是個什么東西尼？

它是定了一些接口的結構體
github.com/torvalds/linux/blob/bf57ae2165bad1cb273095a5c09708ab503cd874/kernel/sched/sched.h#L2164
linux/kernel/sched目錄下實現了若干個調度算法: stop,deadline, fair, rt, idel等調度算法，這個是根據不同類型的進程選擇不同的調度算法的
github.com/torvalds/linux/blob/bf57ae2165bad1cb273095a5c09708ab503cd874/kernel/sched/fair.c#L12375
調度算法優先級
rt > dl > stop > fair > idle

3.1.3 如何查看linux的中斷

各個cpu發生中斷類型和次數統計。

這里的TIMER就是時間中斷。

3.1.4 /proc/irq

這個是系統里注冊了多少個中斷信號源。

可以給每個中斷信號去設置指定處理的cpu。每個信號下面的目錄里smp_affinity。

3.1.5 /proc/interrupts

irq編號，每個cpu對該irq的處理次數，中斷控制器的名字，irq的名字，以及驅動程序注冊該irq時使用的名字

3.1.6 top命令

這里從top的輸出可以看到:

hi: 硬件中斷
si: 軟件中斷
PR: 進程優先級， rt表示是實時進程。至于進程優先級=20，是個什么含義，暫時不在本文展開了。
NI: 進程nice值

4. Linux的調度算法

好了，上面鋪墊了半天，終于來到了調度算法。

其實舉個例子: 當你從鍵盤敲下Q，然后文本編輯框顯示一個Q，就是一個鍵盤的設備外部中斷到對應的中斷程序代碼執行。

如果你按下Q，半天都沒有執行這段顯示Q的中斷代碼，你在電腦前是不是會很崩潰，啊，我的天，怎么卡主了。電腦你是不是壞了。

下面來看看這個調度算法的演進流程。

4.1 調度算法的基礎

調度算法的原則
- 在1個cpu選擇最優的task來運行。例如普遍認為io-bound task需要更好的優先級
- 沒有餓死
- 調度速率
調度算法演進
- Linux 2.4: o(n)調度器
- Linux2.6較早版本: o(1)調度器
- Linux 2.6.23+: o(log n) CFS調度器

4.1 o(n) 調度算法

調度器基本架構
進程優先級:
- 2個靜態優先級，進程的生命周期內都不會改變
  - 實時優先級
    - 實時任務: 1-99
    - 普通任務: 0
  - nice優先級
    - 普通任務:0
    - 人工調整: [-20,19], 可以通過nice命令進行調整
- 動態優先級
  - time slice counter: 進程在調度過程中，

調度算法代碼邏輯

schedule邏輯

void schedule(){
  struct task_struct *next, *p;
  struct list_head *tmp;
  int this_cpu = ..., c;
  spin_lock_irq(&runqueue_lock); //Disable interrupts,
  //grab global lock.
  next = idle_task(this_cpu);
  c = -1000; //Best goodness seen so far.
  list_for_each(tmp, &runqueue_head){     // for 循環獲取每個task
  p = list_entry(tmp, struct task_struct, run_list);
  if (can_schedule(p, this_cpu)) {    // 判斷這個task是否能在這個cpu運行，因為有些任務是綁核運行的
  int weight = goodness(p);      // 計算這個任務的權重
  if(weight > c){                // 找權重最大的那個task
  c = weight;
  next = p;
 }
 }
}
spin_unlock_irq(&runqueue_lock);
switch_to(next)            // 跳轉到對應任務

goodness邏輯

int goodness(struct task_struct *p){
  if(p->policy == SCHED_NORMAL){   // 普通進程
  //Normal (i.e., non-"real-time") task
  if(p->counter == 0){        // 如果這個進程已經用完了它對應的cpu時間就直接返回0
  //Task has used all of its
  //time for this epoch!
  return 0;
  }
  return p->counter + 20 - p->nice;    // 普通進程權重計算
}else{    // 實時進程
  //"Real-time" task
  return 1000 + p->rt_priority;   // 實時進程增加了1000，使得實時進程的權重肯定大于普通進程
  //Will always be
  //greater than
  //priority of a
  //normal task
  }
}

總結
- 選擇task需要o(n)時間復雜度
- 鎖競爭: cpu從全局可運行隊列取task的時候，有鎖競爭
- 適合于單核的系統

4.2 o(1) 調度算法

架構圖

每個cpu都有一個runqueue結構體

struct runqueue{ 
spinlock_t lock; 
struct task_struct *curr; 
prio_array_t *active; 
prio_array_t *expired;}


struct prio_array{ 
unsigned int nr_active; 
struct list_head queue[MAX_PRIO]; 
unsigned long bitmap[BITMAP_SIZE];
}

工作原理

schedule代碼邏輯

void scheduler_tick(){ //Called by the timer interrupt handler.
runqueue_t *rq = this_rq();
task_t *p = current;
spin_lock(&rq->lock);
if(!--p->time_slice){  沒有時間片了
    dequeue_task(p, rq->active);
    p->prio = effective_prio(p);
    p->time_slice = task_timeslice(p); // 計算當前運行進程的剩余時間片
   if(!TASK_INTERACTIVE(p) ||    // 不是交互式進程，就放到expired隊列，就暫時不執行
    EXPIRED_STARVING(rq)){
   enqueue_task(p, rq->expired);
   }else{ //Add to end of queue.
    enqueue_task(p, rq->active);     // 否則放到active隊列尾部，
   }
}else{ //p->time_slice > 0   // 如果是普通進程，就保持在對應的active隊列進行執行
    if(TASK_INTERACTIVE(p)){
    //Probably won't need the CPU
    //for a while.
    dequeue_task(p, rq->active);
    enqueue_task(p, rq->active); //Adds to end.
   }
  }
spin_unlock(&rq->lock); //Later, timer handler calls schedule().
}

goodness
- 和o(n)調度器大同小異，就是給與實時進程一些bonus，讓他獲得更大的優先級
cpu執行
- cpu從自己的active 隊列里，根據bitmap來去queue的task來執行。
- 如果active隊列為空，則將active和expired隊列互換
- 繼續第一步

總結
- 每個cpu都有自己的調度數據結構，避免的了全局鎖
- 每一個調度優先級都有自己的數組，而且結合位圖，可以實現o(1)的取task邏輯
- TASK_INTERACTIVE(p) 和EXPIRED_STARVING(rq)) 代碼邏輯比較復雜

4.3 CFS 調度算法

目標
- 一個更加優雅的調度算法， o(1)算法有些地方實現臺奇特了。
- 這個也是Linux作者的決策
調度算法主要邏輯
- 相比于o(1)的通過隊列數組和bitmap來維護可運行task，cfs使用紅黑樹來存儲
  - 每次取最左邊的task來進行運行。
- 紅黑樹優點
  - 自均衡
  - 在寫入、刪除、搜索都能保持 o(log N)
- 紅黑樹的key是virtual runtime
  - 計算方法:
    - Nice值通過一個數組轉換為weight
```
static const int prio_to_weight[40] = { 
/* -20 */ 88761, 71755, 56483, 46273, 36291, 
/* -15 */ 29154, 23254, 18705, 14949, 11916, 
/* -10 */ 9548, 7620, 6100, 4904, 3906, 
/* -5 */ 3121, 2501, 1991, 1586, 1277, 
/* 0 */ 1024, 820, 655, 526, 423, 
/* 5 */ 335, 272, 215, 172, 137, 
/* 10 */ 110, 87, 70, 56, 45, 
/* 15 */ 36, 29, 23, 18, 15,
}
```
    - 計算vruntime公式
```
delta_exec = now - curr->exec_start; 
delta_exec_weighed = delta_exec * (NICE_0_LOAD / t->load.weight); 
curr->vruntime += delta_exec_weighted;
```
    - 結果
      - nice=0, vruntime等于它的實際cpu執行時間
      - nice<0, vruntime會小于他實際cpu執行時間
      - nice>0, vruntime會大于它的實際cpu執行時間
      - 這樣子就能實現nice越小，就越優先調度了
CFS總結
- 使用運行時間而不是時間片來衡量進程，粒度能去到納秒
- 是否比o(1)更加好？
  - 時間粒度更加細
  - o(1) 看起來比o(log n)更加快
  - vruntime會比time slice更加公平
  - cfs也有很奇怪的地方，就是一直取最左task來運行，是否會讓task失去 cache locality

亚欧色一区w666天堂,色情一区二区三区免费看,少妇特黄A片一区二区三区,亚洲人成网站999久久久综合,国产av熟女一区二区三区

智算服務

應用商城

定價

合作伙伴

開發者

支持與服務

了解天翼云

淺析Linux CPU調度原理

1.背景

2. 單片機C51的中斷

2.1 C51是什么?

2.2 C51的中斷

2.3 小結

3. 從單片機中斷到Linux操作系統

3.1 linux的中斷

3.2 中斷和進程調度

4. Linux的調度算法

4.1 o(n) 調度算法

4.2 o(1) 調度算法

4.3 CFS 調度算法

5. 總結

淺析Linux CPU調度原理

1.背景

2. 單片機C51的中斷

2.1 C51是什么?

2.2 C51的中斷

2.3 小結

3. 從單片機中斷到Linux操作系統

3.1 linux的中斷

3.2 中斷和進程調度

4. Linux的調度算法

4.1 o(n) 調度算法

4.2 o(1) 調度算法

4.3 CFS 調度算法

5. 總結

亚欧色一区w666天堂,色情一区二区三区免费看,少妇特黄A片一区二区三区,亚洲人成网站999久久久综合,国产av熟女一区二区三区

活動

智算服務

應用商城

定價

合作伙伴

開發者

支持與服務

了解天翼云

淺析Linux CPU調度原理

1.背景

2. 單片機C51的中斷

2.1 C51是什么?

2.2 C51的中斷

2.3 小結

3. 從單片機中斷到Linux操作系統

3.1 linux的中斷

3.2 中斷和進程調度

4. Linux的調度算法

4.1 o(n) 調度算法

4.2 o(1) 調度算法

4.3 CFS 調度算法

5. 總結

淺析Linux CPU調度原理

1.背景

2. 單片機C51的中斷

2.1 C51是什么?

2.2 C51的中斷

2.3 小結

3. 從單片機中斷到Linux操作系統

3.1 linux的中斷

3.2 中斷和進程調度

4. Linux的調度算法

4.1 o(n) 調度算法

4.2 o(1) 調度算法

4.3 CFS 調度算法

5. 總結