和SCHED_RR调度策略#xff1b;普通进程则采用SCHED_NORMAL调度策略。

从…一、前序

SCHED_RR和SCHED_NORMAL而Linux支持两种类型的进程实时进程和普通进程。

实时进程可以采用SCHED_FIFO

和SCHED_RR调度策略普通进程则采用SCHED_NORMAL调度策略。

从Linux2.6.23内核版本开始普通进程采用调度策略SCHED_NORMAL的进程采用了绝对公平调度算法不再跟踪进程的睡眠时间也不区分是否为交互式进程它将所有的进程都统一对待这就是完全公平的含义。

二、CFS基本原理概述

runtime(vruntime)。

如果一个进程得以执行随着执行时间的不断增长其vruntime也将不断增大没有得到执行的进程vruntime将保持不变。

而调度器将会选择最小的vruntime那个进程来执行。

这就是所谓的“完全公平”。

不同优先级的进程其vruntime增长速度不同优先级高的进程vruntime增长得慢所以它可能得到更多的运行机会。

三、CFS算法设计核心

备注调度周期将所有处于TASK_RUNNING态进程都调度一遍的时间,在O(1)调度算法中就是运行队列中进程运行一遍的时间。

所以进程权重与分配给进程的运行时间成正比。

vruntime

如果分配给进程的运行时间等于实际运行的时间时将推到出另一vruntime计算公式。

把公式3.2中的分配给进程的运行时间

vruntime

初步结论当分配给进程的运行时间等于实际运行的时间时虽然每个进程的权重不同但是它们的

vruntime增长速度均相同与权重无关。

上文已述用vruntime来选择将要运行的进程vruntime值较小表明它以前占用cpu的时间较短受到了“不公平”对待因此下一个运行进程就是它。

如此一来既能公平选择进程又能保证高优先级进程获得较多的运行时间。

如果分配给进程的运行时间不等于实际运行的时间时CFS的思想就是让每个调度实体的vruntime增加速度不同权重越大的增加的越慢这样高优先级进程就能获得更多的cpu执行时间而vruntime值较小者也得到执行。

每一个进程或者调度组都对应一个调度的实体每一个进程都通过调度实体与CFS运行对列建立联系每次进行CFS调度的时候都会在CFS运行对列红黑树中选择一个进程vruntime值较小者。

cfs_rq代表CFS运行对列它可以找到对应的红黑树。

进程task_struct

可以找到对应的调度实体。

调度实体sched_entity对应运行对列红黑树上的一个节点。

四、CFS调度器

现代的操作系统是多任务的操作系统硬件的处理器核心和各种资源越来越多CPU也是一个资源。

为了保证进程合理的使用CPU资源则需要一个管理单元负责调度进程由管理单元来决定下一刻应该由谁使用CPU这里管理单元就是进程调度器。

调度器可以临时分配一个任务在上面执行单位是时间片。

进程调度器的任务就是合理分配CPU时间给运行的进程创造一种所有进程并行运行的错觉使得我们同时执行多个程序成为可能可以具有各种需求的用户共享CPU。

因此调度器必须在各个进程之间尽可能公平地共享CPU时间,

而同时又要考虑不同的任务优先级。

调度器的一个重要目标是有效地分配

CPU

在目前Linux内核中调度器分成两个层级在进程中被直接调用的成为通用调度器或者核心调度器它们作为一个组件和进程其它部分分开而通用调度器和进程并没有直接关系其通过第二层的具体的调度器类来直接管理进程。

具体架构如下图

4.2.1调度器类

Linux内核中实现了一个调度器类的框架其中定义了调度器应该实现的函数每一个具体的调度器类都要实现这些函数

在Linux版本中3.11.1使用了四个调度器类stop_sched_class、rt_sched_class、fair_sched_class、idle_sched_class,在最新的内核中又添加了一个调度类dl_sched_class。

每个进程必然属于一个特定的调度器类Linux会根据不同的需求实现不同的调度器类。

各个调度器类之间具备一定的层次关系即在通用调度器选择进程的时候会从最高优先级的调度器类开始选择如果通用调度器类没有可运行的进程就选择下一个调度器类的可用进程这样逐层递减。

调度器类的定义

struct

*next;//向就绪队列添加一个进程该操作发生在一个进程变成就绪态可运行态的时候。

void

(*enqueue_task)

flags);//执行enqueue_task的逆操作在一个进程由运行态转为阻塞的时候就会发生该操作。

void

(*dequeue_task)

flags);//挑选下一个可运行的进程发生在进程调度的时候struct

task_struct

#endif//当进程的调度策略发生变化时需要执行此函数void

(*set_curr_task)

queued);//建立fork系统调用和调度器之间的关联每次新进程建立后就调用该函数通知调度器void

(*task_fork)

内核学习地址Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈

周期调度器根据频率自动调用scheduler_tick函数。

其主要作用就是根据进程运行时间触发调度在进程遇到资源等待被阻塞也可以显示的调用调度器函数进行调度另外在有内核空间返回到用户空间时会判断当前是否需要调度在进程对应的thread_info结构中有一个flag该flag字段的第二位从0开始作为一个重调度标识TIF_NEED_RESCHED当被设置的时候表明此时有更高优先级的进程需要执行调度。

另外目前的内核支持内核抢占功能在适当的时机可以抢占内核的运行。

周期性调度器并不直接调度至多设置进程的重调度位TIF_NEED_RESCHED在返回用户空间的时候仍然由主调度器执行调度。

void

rq-curr;sched_clock_tick();spin_lock(rq-lock);update_rq_clock(rq);update_cpu_load(rq);curr-sched_class-task_tick(rq,

curr,

0);spin_unlock(rq-lock);perf_event_task_tick(curr,

cpu);#ifdef

idle_cpu(cpu);trigger_load_balance(rq,

cpu);

主调度器是通过schedule()函数来完成进程的选择和切换。

static

cpu;need_resched://禁止内核抢占preempt_disable();cpu

cpu_rq(cpu);rcu_note_context_switch(cpu);//保存当前进程任务prev

rq-curr;schedule_debug(prev);if

(sched_feat(HRTICK))hrtick_clear(rq);/**

Make

signal_pending_state()-signal_pending()

below*

__set_current_state(TASK_INTERRUPTIBLE)*

done

signal_wake_up().*/smp_mb__before_spinlock();raw_spin_lock_irq(rq-lock);switch_count

prev-nivcsw;/*

(unlikely(signal_pending_state(prev-state,

prev)))

(to_wakeup)try_to_wake_up_local(to_wakeup);}}switch_count

prev);if

(unlikely(!rq-nr_running))idle_balance(cpu,

rq);//通知调度器prev进程将被调度出去put_prev_task(rq,

pick_next_task(rq);//清除pre的TIF_NEED_RESCHED标志clear_tsk_need_resched(prev);rq-skip_clock_update

(likely(prev

{rq-nr_switches;//设置当前调度进程为nextrq-curr

next;*switch_count;//切换进程上下文context_switch(rq,

prev,

elseraw_spin_unlock_irq(rq-lock);post_schedule(rq);sched_preempt_enable_no_resched();if

(need_resched())goto

上下文切换主要由context_switch函数完成主要做了两件事情切换地址空间、切换寄存器域和栈空间。

整个切换过程需要加锁和关中断首先切换的是地址空间mm

mm_struct如果mm为空则表明next是内核线程内核线程没有自己独立的地址空间所以其mm为null运行的时候使用prev的active_mm即可。

如果非空则是用户进程那么可以直接切换这里调用switch_mm函数进行切换如果prev为内核线程由于其没有独立地址空间所以需要设置其active_mm为null。

最后进程切换的部分调用switch_to来切换寄存器域和栈。

switch_to是一个宏由汇编代码实现有能力者可深入学习

static

*oldmm;//进程切换准备工作加锁和关中断最后调用finish_task_switchprepare_task_switch(rq,

prev,

hypercall.*/arch_start_context_switch(prev);//如果要执行的是内核线程if

(!mm)

oldmm;atomic_inc(oldmm-mm_count);enter_lazy_tlb(oldmm,

next);}

__ARCH_WANT_UNLOCKED_CTXSWspin_release(rq-lock.dep_map,

_THIS_IP_);

#endifcontext_tracking_task_switch(prev,

next);/*

invalid.*/finish_task_switch(this_rq(),

prev);