linux內(nèi)核調(diào)度程序很先進(jìn)很強(qiáng)大，管理你的LINUX上跑的大量的亂七八糟的進(jìn)程，同時(shí)還保持著對(duì)用戶操作的高靈敏響應(yīng)，如果可能，為什么不把這種思想放到自己的應(yīng)用程序里呢？或者，有沒有可能更好的實(shí)現(xiàn)自己的應(yīng)用，使得操作系統(tǒng)能夠以自己的意志來分配資源給自己的進(jìn)程？
帶著這兩個(gè)問題來看看KERNEL。首先回顧上我們開發(fā)應(yīng)用程序，基本上就兩種類型，1、IO消耗型：比如hadoop上的trunk服務(wù)，很明顯它的消耗主要在IO上，包括網(wǎng)絡(luò)IO磁盤IO等等。2、CPU消耗型，比如mapreduce或者其他的需要對(duì)大量數(shù)據(jù)進(jìn)行計(jì)算處理的組件，就象對(duì)高清視頻壓縮成適合手機(jī)觀看分辨率的進(jìn)程，他們的消耗主要在CPU上。當(dāng)兩類進(jìn)程都在一臺(tái)SERVER上運(yùn)行時(shí)，操作系統(tǒng)會(huì)如何調(diào)度它們呢？現(xiàn)在的服務(wù)器都是SMP多核的，那么一個(gè)進(jìn)程在多CPU時(shí)會(huì)來回切換嗎？如果我有一個(gè)程序，既有IO消耗又有CPU消耗，怎么讓多核更好的調(diào)度我的程序呢？
又多了幾個(gè)問題。來看看內(nèi)核調(diào)度程序吧，我們先從它的優(yōu)先隊(duì)列談起吧。調(diào)度程序代碼就在內(nèi)核源碼的kernel/sched.c的schedule函數(shù)中。
首先看下面的優(yōu)先級(jí)隊(duì)列，每一個(gè)runqueue都有。runqueue是什么？下面會(huì)詳細(xì)說下，現(xiàn)在大家可以理解為，內(nèi)核為每一顆CPU分配了一個(gè)runqueue，用于維護(hù)這顆CPU可以運(yùn)行的進(jìn)程。runqueue里，有幾個(gè)成員是prio_array類型，這個(gè)東東就是優(yōu)先隊(duì)列，先看看它的定義：
struct prio_array {
unsigned int nr_active; 表示等待執(zhí)行的進(jìn)程總數(shù)
unsigned long bitmap[BITMAP_SIZE]; 一個(gè)unsigned long在內(nèi)核中只有32位哈，大家要跟64位OS上的C程序中的long區(qū)分開，那個(gè)是64位的。那么這個(gè)bitmap是干什么的呢？它是用位的方式，表示某個(gè)優(yōu)先級(jí)上有沒有待處理的隊(duì)列，是實(shí)現(xiàn)快速找到最高待處理優(yōu)先進(jìn)程的關(guān)鍵。如果我定義了四種優(yōu)先級(jí)，我只需要四位就能表示某個(gè)優(yōu)先級(jí)上有沒有進(jìn)程要運(yùn)行，例如優(yōu)先級(jí)是2和3上有進(jìn)程，那么就應(yīng)該是0110.......非常省空間，效率也快，不是嗎？
struct list_head queue[MAX_PRIO]; 與上面的bitmap是對(duì)應(yīng)的，它存儲(chǔ)所有等待運(yùn)行的進(jìn)程。
};
看看BITMAP_SIZE是怎么算出來的：#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
那么，LINUX默認(rèn)配置（如果你用默認(rèn)選項(xiàng)編譯內(nèi)核的話）MAX_PRIO是140，就是說一共內(nèi)核對(duì)進(jìn)程一共定義了140種優(yōu)先級(jí)。等待某個(gè)CPU來處理的進(jìn)程中，可能包含許多種優(yōu)先級(jí)的進(jìn)程，但，LINUX是個(gè)搶占式調(diào)度算法的操作系統(tǒng)，就是說，需要調(diào)度時(shí)一定是找到最高優(yōu)先級(jí)的進(jìn)程執(zhí)行。上面的BITMAP_SIZE值根據(jù)MAX_PRIO算出來為5，那么bitmap實(shí)際是32*5=160位，這樣就包含了MAX_PRIO的140位。優(yōu)先級(jí)隊(duì)列是怎么使用的？看2649行代碼：idx = sched_find_first_bit(array->bitmap);這個(gè)方法就用來快速的找到優(yōu)先級(jí)最高的隊(duì)列。看看它的實(shí)現(xiàn)可以方便我們理解這個(gè)優(yōu)先級(jí)位的設(shè)計(jì)：
static inline int sched_find_first_bit(unsigned long *b)
{
if (unlikely(b[0]))
return __ffs(b[0]);
if (unlikely(b[1]))
return __ffs(b[1]) + 32;
if (unlikely(b[2]))
return __ffs(b[2]) + 64;
if (b[3])
return __ffs(b[3]) + 96;
return __ffs(b[4]) + 128;
}
那么__ffs是干什么的？
static inline int __ffs(int x)
{
int r = 0;
if (!x)
return 0;
if (!(x & 0xffff)) {
x >>= 16;
r += 16;
}
if (!(x & 0xff)) {
x >>= 8;
r += 8;
}
if (!(x & 0xf)) {
x >>= 4;
r += 4;
}
if (!(x & 3)) {
x >>= 2;
r += 2;
}
if (!(x & 1)) {
x >>= 1;
r += 1;
}
return r;
}
sched_find_first_bit返回值就是最高優(yōu)先級(jí)所在隊(duì)列的序號(hào)，與queue是對(duì)應(yīng)使用的哈，queue = array->queue + idx;這樣就取到了要處理的進(jìn)程隊(duì)列。這個(gè)設(shè)計(jì)在查找優(yōu)先級(jí)時(shí)是非常快的，非常值得我們學(xué)習(xí)。
需要C/C++ Linux服務(wù)器架構(gòu)師學(xué)習(xí)資料私信“資料”（資料包括C/C++，Linux，golang技術(shù)，Nginx，ZeroMQ，MySQL，redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協(xié)程，DPDK，ffmpeg等），免費(fèi)分享
好，優(yōu)先級(jí)隊(duì)列搞明白了，現(xiàn)在來看看runqueue，每個(gè)runqueue包含三個(gè)優(yōu)先級(jí)隊(duì)列。
struct runqueue {
spinlock_t lock; 這是個(gè)自旋鎖，nginx里解決驚群現(xiàn)象時(shí)也是用這個(gè)。與普通鎖的區(qū)別就是，使用普通鎖時(shí)，你去試圖拿一把鎖，結(jié)果發(fā)現(xiàn)已經(jīng)被別人拿走了，你就在那睡覺，等別人鎖用完了叫你起來。所以如果有一個(gè)人拿住鎖了，一百個(gè)人都在門前睡覺等。當(dāng)之前的人用完鎖回來后，會(huì)叫醒所有100個(gè)等鎖的人，然后這些人開始互相搶，搶到的人拿鎖進(jìn)去，其他的人繼續(xù)等。自旋鎖不同，當(dāng)他去拿鎖發(fā)現(xiàn)鎖被別人拿走了，他在那不睡覺的等，稍打個(gè)盹就看看自己主動(dòng)看看鎖有沒有還回來。大家比較出優(yōu)劣了嗎？
/*
* nr_running and cpu_load should be in the same cacheline because
* remote CPUs use both these fields when doing load calculation.
*/
unsigned long nr_running;
#ifdef CONFIG_SMP
unsigned long cpu_load;
#endif
unsigned long long nr_switches;
/*
* This is part of a global counter where only the total sum
* over all CPUs matters. A task can increase this counter on
* one CPU and if it got migrated afterwards it may decrease
* it on another CPU. Always updated under the runqueue lock:
*/
unsigned long nr_uninterruptible;
unsigned long expired_timestamp;
unsigned long long timestamp_last_tick;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];上面說了半天的優(yōu)先級(jí)隊(duì)列在這里，但是在runqueue里，為什么不只一個(gè)呢？這個(gè)在下面講。
int best_expired_prio;
atomic_t nr_iowait;
... ...
};
LINUX是一個(gè)時(shí)間多路復(fù)用的系統(tǒng)，就是說，通過把CPU執(zhí)行時(shí)間分成許多片，再分配給進(jìn)程們使用，造成即使單CPU系統(tǒng)，也貌似允許多個(gè)任務(wù)在同時(shí)執(zhí)行。那么，時(shí)間片大小假設(shè)為100ms，過短過長(zhǎng)，過長(zhǎng)了有些不靈敏，過短了，連切換進(jìn)程時(shí)可能都要消耗幾毫秒的時(shí)間。分給100個(gè)進(jìn)程執(zhí)行，在所有進(jìn)程都用完自己的時(shí)間片后，需要重新給所有的進(jìn)程重新分配時(shí)間片，怎么分配呢？for循環(huán)遍歷所有的run狀態(tài)進(jìn)程，重設(shè)時(shí)間片？這個(gè)性能無(wú)法容忍！太慢了，跟當(dāng)前系統(tǒng)進(jìn)程數(shù)相關(guān)。那么2.6內(nèi)核怎么做的呢？它用了上面提到的兩個(gè)優(yōu)先級(jí)隊(duì)列active和expired，顧名思義，active是還有時(shí)間片的進(jìn)程隊(duì)列，而expired是時(shí)間片耗盡必須重新分配時(shí)間片的進(jìn)程隊(duì)列。
這么設(shè)計(jì)的好處就是不用再循環(huán)一遍所有進(jìn)程重設(shè)時(shí)間片了，看看調(diào)度函數(shù)是怎么玩的：
array = rq->active;
if (unlikely(!array->nr_active)) {
/*
* Switch the active and expired arrays.
*/
schedstat_inc(rq, sched_switch);
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
rq->best_expired_prio = MAX_PRIO;
} else
schedstat_inc(rq, sched_noswitch);
當(dāng)所有運(yùn)行進(jìn)程的時(shí)間片都用完時(shí)，就把a(bǔ)ctive和expired隊(duì)列互換指針，沒有遍歷哦，而時(shí)間片耗盡的進(jìn)程在出acitve隊(duì)列入expired隊(duì)列時(shí)，已經(jīng)單獨(dú)的重新分配好新時(shí)間片了。
再看一下schedule(void)調(diào)度函數(shù)，當(dāng)某個(gè)進(jìn)程休眠或者被搶占時(shí)，系統(tǒng)就開始調(diào)試schedule(void)決定接下來運(yùn)行哪個(gè)進(jìn)程。上面說過的東東都在這個(gè)函數(shù)里有體現(xiàn)哈。
asmlinkage void __sched schedule(void)
{
long *switch_count;
task_t *prev, *next;
runqueue_t *rq;
prio_array_t *array;
struct list_head *queue;
unsigned long long now;
unsigned long run_time;
int cpu, idx;
/*
* Test if we are atomic. Since do_exit() needs to call into
* schedule() atomically, we ignore that path for now.
* Otherwise, whine if we are scheduling when we should not be.
*/
if (likely(!(current->exit_state & (EXIT_DEAD | EXIT_ZOMBIE)))) {先看看當(dāng)前運(yùn)行進(jìn)程的狀態(tài)
if (unlikely(in_atomic())) {
printk(KERN_ERR "scheduling while atomic: "
"%s/0x%08x/%dn",
current->comm, preempt_count(), current->pid);
dump_stack();
}
}
profile_hit(SCHED_PROFILING, __builtin_return_address(0));
need_resched:
preempt_disable();
prev = current;
release_kernel_lock(prev);
need_resched_nonpreemptible:
rq = this_rq(); 這行找到這個(gè)CPU對(duì)應(yīng)的runqueue，再次強(qiáng)調(diào)，每個(gè)CPU有一個(gè)自己的runqueue
/*
* The idle thread is not allowed to schedule!
* Remove this check after it has been exercised a bit.
*/
if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) {
printk(KERN_ERR "bad: scheduling from the idle thread!n");
dump_stack();
}
schedstat_inc(rq, sched_cnt);
now = sched_clock();
if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))
run_time = now - prev->timestamp;
else
run_time = NS_MAX_SLEEP_AVG;
/*
* Tasks with interactive credits get charged less run_time
* at high sleep_avg to delay them losing their interactive
* status
*/
if (HIGH_CREDIT(prev))
run_time /= (CURRENT_BONUS(prev) ? : 1);
spin_lock_irq(&rq->lock);
if (unlikely(current->flags & PF_DEAD))
current->state = EXIT_DEAD;
/*
* if entering off of a kernel preemption go straight
* to picking the next task.
*/
switch_count = &prev->nivcsw;
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
switch_count = &prev->nvcsw;
if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
unlikely(signal_pending(prev))))
prev->state = TASK_RUNNING;
else {
if (prev->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
deactivate_task(prev, rq);
}
}
cpu = smp_processor_id();
if (unlikely(!rq->nr_running)) {
go_idle:
idle_balance(cpu, rq);
if (!rq->nr_running) {
next = rq->idle;
rq->expired_timestamp = 0;
wake_sleeping_dependent(cpu, rq);
/*
* wake_sleeping_dependent() might have released
* the runqueue, so break out if we got new
* tasks meanwhile:
*/
if (!rq->nr_running)
goto switch_tasks;
}
} else {
if (dependent_sleeper(cpu, rq)) {
next = rq->idle;
goto switch_tasks;
}
/*
* dependent_sleeper() releases and reacquires the runqueue
* lock, hence go into the idle loop if the rq went
* empty meanwhile:
*/
if (unlikely(!rq->nr_running))
goto go_idle;
}
array = rq->active;
if (unlikely(!array->nr_active)) { 上面說過的，需要重新計(jì)算時(shí)間片時(shí)，就用已經(jīng)計(jì)算好的expired隊(duì)列了
/*
* Switch the active and expired arrays.
*/
schedstat_inc(rq, sched_switch);
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
rq->best_expired_prio = MAX_PRIO;
} else
schedstat_inc(rq, sched_noswitch);
idx = sched_find_first_bit(array->bitmap); 找到優(yōu)先級(jí)最高的隊(duì)列
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
if (!rt_task(next) && next->activated > 0) {
unsigned long long delta = now - next->timestamp;
if (next->activated == 1)
delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
array = next->array;
dequeue_task(next, array);
recalc_task_prio(next, next->timestamp + delta);
enqueue_task(next, array);
}
next->activated = 0;
switch_tasks:
if (next == rq->idle)
schedstat_inc(rq, sched_goidle);
prefetch(next);
clear_tsk_need_resched(prev);
rcu_qsctr_inc(task_cpu(prev));
prev->sleep_avg -= run_time;
if ((long)prev->sleep_avg <= 0) {
prev->sleep_avg = 0;
if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))
prev->interactive_credit--;
}
prev->timestamp = prev->last_ran = now;
sched_info_switch(prev, next);
if (likely(prev != next)) { 表面現(xiàn)在正在執(zhí)行的進(jìn)程，不是選出來的優(yōu)先級(jí)最高的進(jìn)程
next->timestamp = now;
rq->nr_switches++;
rq->curr = next;
++*switch_count;
prepare_arch_switch(rq, next);
prev = context_switch(rq, prev, next); 所以需要完成進(jìn)程上下文切換，把之前的進(jìn)程信息CACHE住
barrier();
finish_task_switch(prev);
} else
spin_unlock_irq(&rq->lock);
prev = current;
if (unlikely(reacquire_kernel_lock(prev) < 0))
goto need_resched_nonpreemptible;
preempt_enable_no_resched();
if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
goto need_resched;
}
當(dāng)然，在我們程序中，也可以通過執(zhí)行以下系統(tǒng)調(diào)用來改變自己進(jìn)程的優(yōu)先級(jí)。nice系統(tǒng)調(diào)用可以改變某個(gè)進(jìn)程的基本優(yōu)先級(jí)，setpriority可以改變一組進(jìn)程的優(yōu)先級(jí)。
