目錄

內(nèi)核進(jìn)程調(diào)度隊(duì)列的過程

一個(gè)CPU擁有一個(gè)runqueue(運(yùn)行隊(duì)列在內(nèi)存)

活動(dòng)隊(duì)列(active)

過期隊(duì)列(expired)

active指針和expired指針

重繪runqueue

linux內(nèi)核O(1)調(diào)度算法

總結(jié)

補(bǔ)充知識(shí):

封裝鏈?zhǔn)浇Y(jié)構(gòu)的目的是:

僅使用封裝鏈?zhǔn)浇Y(jié)構(gòu)可以得到全部的task_struct的信息的原理:

---

內(nèi)核進(jìn)程調(diào)度隊(duì)列的過程

上圖是Linux2.6內(nèi)核中進(jìn)程隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，之間關(guān)系也已經(jīng)給大家畫出來，方便大家理解

一個(gè)CPU擁有一個(gè)runqueue(運(yùn)行隊(duì)列在內(nèi)存)

如果有多個(gè)CPU就要考慮進(jìn)程個(gè)數(shù)的負(fù)載均衡問題?

在上圖我們可以看到,runqueue中含有兩個(gè)struct queue數(shù)據(jù)結(jié)構(gòu)? array[0]是活躍隊(duì)列和array[1]是過期隊(duì)列

struct queue隊(duì)列數(shù)據(jù)結(jié)構(gòu)包含了nr_activce? bitmap[5] queue[140]三個(gè)結(jié)構(gòu)

? ? ? ? queue隊(duì)列中的

• ? ? ? ? nr_active是哈希桶中task_struct的數(shù)量? ? ? 功能:控制是否swap(下面講了)
• ? ? ? ? bitmap[5]充當(dāng)位圖? ? ? ? ? ?功能:更快找到下一個(gè)要調(diào)度的進(jìn)程在哈希桶的哪個(gè)位置
• ????????queue[140]是一個(gè)哈希桶, 在100到139下標(biāo)中分別存儲(chǔ)鏈?zhǔn)降倪M(jìn)程PCB(task_struct) ,正好對(duì)應(yīng)了40種進(jìn)程優(yōu)先級(jí).

活動(dòng)隊(duì)列(active)

• 時(shí)間片還沒有結(jié)束的所有進(jìn)程都按照優(yōu)先級(jí)放在該隊(duì)列
• nr_active: 總共有多少個(gè)運(yùn)行狀態(tài)的進(jìn)程
• queue[140]: 一個(gè)元素就是一個(gè)進(jìn)程隊(duì)列，相同優(yōu)先級(jí)的進(jìn)程按照FIFO規(guī)則進(jìn)行排隊(duì)調(diào)度,所以，數(shù)組下標(biāo)就是優(yōu)先級(jí)！

從該結(jié)構(gòu)中，選擇下一個(gè)最合適的進(jìn)程，過程是怎么的呢？

1. 從0下表開始遍歷queue[140]

2. 找到第一個(gè)非空隊(duì)列，該隊(duì)列必定為優(yōu)先級(jí)最高的隊(duì)列

3. 拿到選中隊(duì)列的第一個(gè)進(jìn)程，開始運(yùn)行，調(diào)度完成！

4. 遍歷queue[140]時(shí)間復(fù)雜度是常數(shù)！但還是太低效了！因此設(shè)計(jì)了bitmap[5r]

• bitmap[5]:一共140個(gè)優(yōu)先級(jí)，一共140個(gè)進(jìn)程隊(duì)列，為了提高查找非空隊(duì)列的效率，就可以用5*32個(gè)比特位表示隊(duì)列是否為空，這樣，便可以大大提高查找效率

過期隊(duì)列(expired)

• 過期隊(duì)列和活動(dòng)隊(duì)列結(jié)構(gòu)一模一樣
• 過期隊(duì)列上放置的進(jìn)程，都是時(shí)間片耗盡的進(jìn)程
• 當(dāng)活動(dòng)隊(duì)列上的進(jìn)程都被處理完畢之后，對(duì)過期隊(duì)列的進(jìn)程進(jìn)行時(shí)間片重新計(jì)算

active指針和expired指針

active指針永遠(yuǎn)指向活動(dòng)隊(duì)列

expired指針永遠(yuǎn)指向過期隊(duì)列

可是活動(dòng)隊(duì)列上的進(jìn)程會(huì)越來越少，過期隊(duì)列上的進(jìn)程會(huì)越來越多，因?yàn)檫M(jìn)程時(shí)間片到期時(shí)一直都存在的。

沒關(guān)系，在合適的時(shí)候，只要能夠交換active指針和expired指針的內(nèi)容，就相當(dāng)于有具有了一批新的活動(dòng)進(jìn)程！

重繪runqueue

?下圖重新描繪了runqueue?

此時(shí)active是array[0]的首地址 ,expired?是array[1]的首地址

為什么runqueue需要兩個(gè)array呢?

1. ?runqueue只有一個(gè)array , 如果一直有優(yōu)先級(jí)高的進(jìn)程插入進(jìn)來,會(huì)導(dǎo)致優(yōu)先級(jí)低的進(jìn)程一直無法運(yùn)行,導(dǎo)致饑餓問題
2. 而兩個(gè)array可以解決問題:? 一個(gè)array結(jié)構(gòu)叫做actice隊(duì)列? ,另一個(gè)叫做expired隊(duì)列,歸定cpu只能從active隊(duì)列中,選取task_struct運(yùn)行其對(duì)應(yīng)的程序 ,?新進(jìn)程和時(shí)間片到了的進(jìn)程的task_struct?按照優(yōu)先級(jí)加在expired隊(duì)列中,等到active隊(duì)列中pcb的數(shù)量為0時(shí) ,交換兩個(gè)隊(duì)列指針(swap(&active,&expried))?省去了將pcb重新插入的步驟.

linux內(nèi)核O(1)調(diào)度算法

如何進(jìn)行快速算法調(diào)度(快速找到下一個(gè)task_struct),linux設(shè)計(jì)了一種O(1)算法

4*8*5 =140?

而bitmap[5]正好是5個(gè)int值

可以利用類似這種算法

for(int i=0; i<5 ;i++)
{if(bitmap[i] == 0) continue;//一次可檢測(cè)32個(gè)位置else(bitmap[i]!= 0){算法2查找bit位為1的精確位置}}

而算法2可以 利用?n & (n - 1)?可以清除最低位的 1 的特性，減少循環(huán)次數(shù)。找到哪個(gè)比特位為1, 就是哪個(gè)優(yōu)先級(jí)中有pcb

#include <stdio.h>int countBits(int num) 
{int count = 0;while (num) {num &= (num - 1);count++;}return count;
}int main() {int num = 29; // 二進(jìn)制表示為 11101printf("Number of 1 bits in %d is %d\n", num, countBits(num));return 0;
}

總結(jié)

在系統(tǒng)當(dāng)中查找一個(gè)最合適調(diào)度的進(jìn)程的時(shí)間復(fù)雜度是一個(gè)常數(shù)，不隨著進(jìn)程增多而導(dǎo)致時(shí)間成本增加，我們稱之為進(jìn)程調(diào)度O(1)算法!

補(bǔ)充知識(shí):

進(jìn)程的task_struct都用鏈表鏈接

task_struct可在運(yùn)行隊(duì)列 , 阻塞隊(duì)列中

linux的鏈?zhǔn)浇Y(jié)構(gòu)是雙鏈結(jié)構(gòu)

task_struct中將雙鏈結(jié)構(gòu)進(jìn)行了封裝如下圖struct node?

封裝鏈?zhǔn)浇Y(jié)構(gòu)的目的是:

如果進(jìn)程處于某個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中, 只需將task_struct中的鏈?zhǔn)浇Y(jié)構(gòu)的next和prev填充就行,?而且使得task_struct還可以同時(shí)處于多個(gè)鏈表中.

僅使用封裝鏈?zhǔn)浇Y(jié)構(gòu)可以得到全部的task_struct的信息的原理:

下圖講解了僅使用封裝鏈?zhǔn)浇Y(jié)構(gòu)可以得到全部的task_struct的信息

先得到鏈?zhǔn)浇Y(jié)構(gòu)的偏移量,再找到task_struct的首地址即可

類似使用offset(type ,x)

假設(shè)structA從0地址存儲(chǔ), 其實(shí)大概率不可能存儲(chǔ)到這 , 只是為了得到C的偏移量,再用真實(shí)C的地址來找structA?的起始地址.