精华内容
下载资源
问答
  • 在《Linux系统进程调度——调度架构详细分析》一文已经讲解Linux内核中实现了两个调度器:主调度器和周期调度器,两者合称为通用调度器或核心调度器,也详细解释调度框架、调度类、调度实体、...
    日期内核版本架构作者内容
    2019-5-13Linux-2.6.32

    X86

    BystanderLinux进程调度

    1 绪论

    《Linux系统进程调度——调度架构详细分析》一文已经讲解Linux内核中实现了两个调度器:主调度器周期调度器,两者合称为通用调度器核心调度器,也详细解释调度框架、调度类、调度实体、调度策略等内容。

    《Linux系统进程核心调度器——主调度器schedule函数详解》一文中说明由以下两种方式分别触发激活主调度器周期调度器:

    1. 进程直接放弃CPU
    2. 通过周期性机制, 以固定的频率检测是否有必要调度

    2 周期调度器

    周期性调度器在scheduler_tick()中实现。 如果系统正在活动中, 内核会按照频率HZ自动调用该函数。 如果没有进程在等待调度,在计算机电力供应不足的情况下, 内核将关闭该调度器以减少能耗。

    2.1 如何调用scheduler_tick()

    在单处理系统上的全局时钟 中断处理程序或者多处理器系统上的本地时钟中断处理程序将调用update_process_times()来更新内核统计计数。update_process_times()主要完成以下任务:

    1. 首先调用account_process_tick(),它根据当前进程运行了多久时间和当前进程类别,选择调用account_user_time()、account_system_time(),还是account_idle_time()。
    2. 调用run_local_timers(),从而间接调用raise_softirq(),用来激活本地CPU上的TIMER_SOFTIRQ任务队列。
    3. 调用scheduler_tick(),该函数使当前进程时间片计数器减1,并检查计数器是否已经减到0。
    void update_process_times(int user_tick)
    {
    	struct task_struct *p = current;
    	int cpu = smp_processor_id();
    
    	/* Note: this timer irq context must be accounted for as well. */
    	account_process_tick(p, user_tick);
    	run_local_timers();
    	rcu_check_callbacks(cpu, user_tick);
    	printk_tick();
    	scheduler_tick();
    	run_posix_cpu_timers(p);
    }
    

    2.2 scheduler_tick()实现

    在scheduler_tick()中主要实现以下5个主要工作:

    1. 调用sched_clock_tick()以纳秒为单位将当前时间放入sched_clock_data中;
    2. 调用update_rq_clock()就绪队列时钟的更新, 实际上更新struct rq当前实例的时钟时间戳;
    3. 调用update_cpu_load()更新CPU上负载,为下一步执行调度类挑选进程做准备;
    4. 调用curr->sched_class->task_tick()内核先找到了就绪队列上当前运行的进程curr, 然后调用curr所属调度类sched_class的周期性调度方法task_tick。在Linux-2.6.32中有task_tick_rt(), task_tick_fair(), task_tick_idle()。
    5. 如果系统支持SMP则调用trigger_load_balance()定期进行堵负载均衡。

    scheduler_tick()源码如下:

    void scheduler_tick(void)
    {
        /*获取当前CPU ID*/
    	int cpu = smp_processor_id();
        /*根据CPU ID 获取当前CPU运行队列rq*/
    	struct rq *rq = cpu_rq(cpu);
        /*获取当前CPU上运行队列正在运行进程*/
    	struct task_struct *curr = rq->curr;
        /*以纳秒为单位将当前时间放入sched_clock_data中*/
    	sched_clock_tick();
    
    	spin_lock(&rq->lock);
        /*更新rq的时间.即使rq->clock变为当前时间*/  
    	update_rq_clock(rq);
         /*更新负载信息,也就是更新rq->cpu_load[]*/  
    	update_cpu_load(rq);
    /*执行当前运行进程curr的调度类的task_tick函数*/
    	curr->sched_class->task_tick(rq, curr, 0);
    	spin_unlock(&rq->lock);
         /* 与perf计数事件相关 */
    	perf_event_task_tick(curr, cpu);
    
    #ifdef CONFIG_SMP
        /*判断当前CPU是否空闲*/
    	rq->idle_at_tick = idle_cpu(cpu);
    /* 如果需要定期进行负载平衡,则触发sched_softirq */
    	trigger_load_balance(rq, cpu);
    #endif
    }
    

     

    展开全文
  • 日期 内核版本 ...在《Linux系统进程调度——调度架构详细分析》一文中详细分析了调度器运行原理及过程,本文将详细分析主调度器。 1.1Linux进程调度 内存中保存了对每个进程的唯一描述, 并通过若干...
    日期内核版本架构作者内容
    2019-3-23Linux-2.6.32

    X86

    BystanderLinux进程调度

    1.绪论

    《Linux系统进程调度——调度架构详细分析》一文中详细分析了调度器运行原理及过程,本文将详细分析主调度器。

    1.1Linux进程调度

    内存中保存了对每个进程的唯一描述, 并通过若干数据结构与其他进程连接起来。调度器面对其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个是调度策略, 另外一个是上下文切换.

    两种方法来激活调度:

    1. 进程直接放弃CPU
    2. 通过周期性机制, 以固定的频率检测是否有必要调度

    当前linux的系统由两个调度器组成:主调度器和周期性调度器(两者又统称为通用调度器(generic scheduler)或核心调度器(core scheduler))

    2.主调度器schedule()函数

    schedule就是主调度器的函数, 在内核中,如果要将CPU分配给与当前活动进程不同的另一个进程, 都会直接或间接调用主调度器函数schedule.例如down(struct semaphore *sem)函数到最后也是调用schedule。

    该函数完成如下工作:

    1. 确定当前运行队列, 并保存一个指向当前活动的task_struct指针
    2. 关闭内核抢占后完成内核调度
    3. 恢复内核抢占, 检查当前进程是否设置了重调度标志TLF_NEDD_RESCHED, 如果被其他进程设置了TIF_NEED_RESCHED标志, 则函数重新执行进行调度

    schedule函数框架如下:

    /*
     * schedule() is the main scheduler function.
     * schedule()函数主要功能就是用另外一个进程来
     * 替换当前正在执行的进程
     */
    asmlinkage void __sched schedule(void)
    {
    	struct task_struct *prev, *next;
    	unsigned long *switch_count;
    	struct rq *rq;
    	int cpu;
    
    need_resched:
    	/*
    	 * 禁用内核抢占
    	 */
    	preempt_disable();
    	
    	/*
    	 * 获取当前CPU核心ID
    	 */
    	cpu = smp_processor_id();
    	
    	/*
    	 * 通过当前CPU核心ID获取正在运行队列数据结构
    	 */
    	rq = cpu_rq(cpu);
    	
    	/*
    	 * 标记不同的state度过quiescent state,
    	 * 这个函数需要学习RCU相关知识,有兴趣同学自己学习,
    	 * RCU在linux内核中时很重要技术
    	 */
    	rcu_sched_qs(cpu);
    
    	/*
    	 * 把当前进程赋给prev
    	 */
    	prev = rq->curr;
    
    	/*
    	 * 将截止目前的上下文切换次数赋给switch_count
    	 */
    	switch_count = &prev->nivcsw;
    
    	/*
    	 * 释放大内核锁,schedule()必须要保证prev不能占中大内核锁
    	 */
    	release_kernel_lock(prev);
    need_resched_nonpreemptible:
    
    	/*
    	 * 如果禁止内核抢占,而又调用了cond_resched就会出错
    	 * 这个函数就是用来捕获该错误的
    	 */
    	schedule_debug(prev);
    
    	/*
    	 * 取消rq中hrtick_timer
    	 */
    	if (sched_feat(HRTICK))
    		hrtick_clear(rq);
    	
    	/*
    	 * 采用自旋锁,锁住rq,保护运行队列
    	 */
    	spin_lock_irq(&rq->lock);
    	
    	/*
    	 * 更新就绪队列的时钟
    	 */
    	update_rq_clock(rq);
    
    	/*
    	 * 清除prev需要调度标志TIF_NEED_RESCHED,
    	 * 避免进入就绪队列中
    	 */
    	clear_tsk_need_resched(prev);
    	/*
    	 * 检查prev状态,如果不是可运行状态,
    	 * 且prev没有在内核态被抢占。
    	 */
    	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
    		/*
    		 * 检查prev是否是阻塞挂起,且状态为TASK_INTERRUPTIBLE
    		 * 就把prev状态设置为TASK_RUNNING。
    		 */
    		if (unlikely(signal_pending_state(prev->state, prev)))
    			/*
    			 * 这里设置为TASK_RUNNING,因为prev进程中有信号需要处理,
    			 * 不能从运行对列中删除,否则信号处理不了,会影响其余进程。
    			 */
    			prev->state = TASK_RUNNING;
    		else
    			/*
    			 * 把prev从运行队列中删除
    			 */
    			deactivate_task(rq, prev, 1);
    		switch_count = &prev->nvcsw;
    	}
    	/*
    	 * 通知调度器,即将发生进程切换
    	 */
    	pre_schedule(rq, prev);
    	
    	/*
    	 * 如果运行队列中没有可运行队列,
    	 * 则从另一个运行队列迁移可运行进程到本地队列中来。
    	 */
    	if (unlikely(!rq->nr_running))
    		idle_balance(cpu, rq);
    	
    	/*
    	 * 通知调度器,即将用另一个进程替换当前进程
    	 */
    	put_prev_task(rq, prev);
    	
    	/*
    	 * 选择下一个进程
    	 */
    	next = pick_next_task(rq);
    
    	/*
    	 * 判断选择出的下一个进程是否是当前进程
    	 */
    	if (likely(prev != next)) {
    		
    		/*
    		 * 计算prev和next进程运行时间等参数
    		 */
    		sched_info_switch(prev, next);
    		
    		/*
    		 * 从调度程序调用以删除当前任务的事件,同时禁用中断
    		 * 停止每个事件并更新事件->计数中的事件值。
    		 */
    		perf_event_task_sched_out(prev, next, cpu);
    	
    		/*  
    		 * 队列切换次数更新
    		 */
    		rq->nr_switches++;
    		
    		/*  
    		 * 将next标记为队列的curr进程  
    		 */
    		rq->curr = next;
    
    		/*
    		 * 进程切换次数更新  
    		 */
    		++*switch_count;
    		/*
    		 * 进程之间上下文切换,两个进程切换就在此处发生
    		 * 两个进程切换两大部分:1.prev到next虚拟地址空间的映射,
    		 * 由于内核虚拟地址空间是不许呀切换的, 
    		 * 因此切换的主要是用户态的虚拟地址空间。
    		 * 2.保存、恢复栈信息和寄存器信息。
    		 */
    		context_switch(rq, prev, next); /* unlocks the rq */
    		/*
    		 * the context switch might have flipped the stack from under
    		 * us, hence refresh the local variables.进程切换了,刷新局部变量。
    		 */
    		cpu = smp_processor_id();
    		rq = cpu_rq(cpu);
    	} else
    		/*
    		 * 释放rq锁
    		 */
    		spin_unlock_irq(&rq->lock);
    	/*
    	 * 通知调度器,完成了进程切换
    	 */
    	post_schedule(rq);
    	/*
    	 * 重新获取大内核锁,如果获取不到则需要重新调度
    	 */
    	if (unlikely(reacquire_kernel_lock(current) < 0))
    		goto need_resched_nonpreemptible;
    	/*
    	 * 重新使能内核抢占
    	 */
    	preempt_enable_no_resched();
    	/*
      	 * 检查其余进程已经设置当前进程的TIF_NEED_RESCHED标志,
      	 * 如果设置了需要进行重新调度。
    	 */
    	if (need_resched())
    		goto need_resched;
    }

    3.schedule()函数中进程切换关键函数

    以上就是结合schedule函数实际代码进行解释,笔者能力有限进行一些浅薄的解释,以下是对一些关键函数进行讲解,

    1. idle_balance(int this_cpu, struct rq *this_rq)(点解查看),如果当前CPU运行队列无可运行进程则进入IDLE 状态,将调用idle_balance()进而调用load_balance_newidle函数实现多处理器运行队列平衡功能。
    2. pick_next_task(struct rq *rq),从CPU运行队列中选择一个进程。
    3. context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next),当pick_next_task()选择好进程后,由context_switch()进行进程切换,也就是进程上下文切换。

    3.1pick_next_task()函数

    pick_next_task()函数从调度类中选择一个进程,而在Linux中pick_next_task()不会直接操作进程而是操作调度实体。

    在Linux-2.6.32中有三个调度类优先级从高到底为:rt_sched_class,fair_sched_class,idle_sched_class。pick_next_task()将从以上三个调度类中先从调度类优先级最高sched_class_highest的rt_sched_class选择优先级最高的进程,若rt_sched_class中无可运行进程再从低优先级的fair_sched_class中选择,依次类推。

    下面对pick_next_task()函数进行源码分析:

    /*
     * Pick up the highest-prio task:
     */
    static inline struct task_struct *
    pick_next_task(struct rq *rq)
    {
    	const struct sched_class *class;
    	struct task_struct *p;
    
    	/*
    	 * Optimization: we know that if all tasks are in
    	 * the fair class we can call that function directly:
         * 根据注释可以明显看出,若可运行队列中进程数量与fair类中可运行进程
         * 数相等则直接在fair类中进行进程的挑选。是因为在Linux绝大多数进程都是
         * 普通进程数据fair类,这里减少在rt实时类中进行进程的选择减少开销。
    	 */
    	if (likely(rq->nr_running == rq->cfs.nr_running)) {
    		p = fair_sched_class.pick_next_task(rq);
    		if (likely(p))
    			return p;
    	}
        /*从优先级最高的调度类中开始选择*/
    	class = sched_class_highest;
    	for ( ; ; ) {
    		p = class->pick_next_task(rq);
    		if (p)
    			return p;
    		/*
    		 * Will never be NULL as the idle class always
    		 * returns a non-NULL p:
    		 */
            /*如果优先级最高的调度类中没有可运行进程则进行优先级较低的类中进行选择进程*/
    		class = class->next;
    	}
    }

    在Linux-2.6.32中sched_class_highest是rt_sched_class,在 \kernel \sched.c中定义。

    #define sched_class_highest (&rt_sched_class)

    在每个调度类中将会定义比它自己低优先级的调度类,为了在pick_next_task()函数中class = class->next处进行调度。

    在rt_sched_class中定义当rt_sched_class无可运行进程时就从fair_sched_class中挑选可运行进程:

    static const struct sched_class rt_sched_class = {
    	.next			= &fair_sched_class,
        ...
    };

    在fair_sched_class中定义当fair_sched_class无可运行进程时就从idle_sched_class中挑选可运行进程:

    static const struct sched_class fair_sched_class = {
    	.next			= &idle_sched_class,
        ...
    };

    在idle_sched_class中定义.next为NULL:

    static const struct sched_class idle_sched_class = {
    	/* .next is NULL */
    	/* no enqueue/yield_task for idle tasks */
        ...
    };

    如果rt_sched_class和fair_sched_class中都没有可运行的进程时将运行idle进程,如果有可运行进程则按照优先级高到低进行进程选择。

    3.2context_switch()进程上下文切换

    上下文切换,有时也称做进程切换或任务切换,是指CPU 从一个进程或线程切换到另一个进程或线程。在操作系统中,CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态:当前运行任务转为就绪(或者挂起、删除)状态,另一个被选定的就绪任务成为当前任务。上下文切换包括保存当前任务的运行环境,恢复将要运行任务的运行环境。

    在三种情况下可能会发生上下文切换:中断处理,多任务处理,用户态切换。在中断处理中,其他程序”打断”了当前正在运行的程序。当CPU接收到中断请求时,会在正在运行的程序和发起中断请求的程序之间进行一次上下文切换。在多任务处理中,CPU会在不同程序之间来回切换,每个程序都有相应的处理时间片,CPU在两个时间片的间隔中进行上下文切换。对于一些操作系统,当进行用户态切换时也会进行一次上下文切换,虽然这不是必须的。

    进程上下文切换消耗:

    1. 上下文切换通常是计算密集型的。也就是说,它需要相当可观的处理器时间,在每秒几十上百次的切换中,每次切换都需要纳秒量级的时间。所以,上下文切换对系统来说意味着消耗大量的 CPU 时间,事实上,可能是操作系统中时间消耗最大的操作。
    2. 一个线程可以运行在一个专用处理器上,也可以跨处理器。由单个处理器服务的线程都有处理器关联(Processor Affinity),这样会更加有效。在另一个处理器内核抢占和调度线程会引起缓存丢失,作为缓存丢失和过度上下文切换的结果要访问本地内存。对于要处理一些高速通信的进程或线程最好绑定CPU避免“跨核上下文切换”带来损耗。

    3.2.1context_switch()实现

    /*
     * context_switch - switch to the new MM and the new
     * thread's register state.
     */
    static inline void
    context_switch(struct rq *rq, struct task_struct *prev,
    	       struct task_struct *next)
    {
    	struct mm_struct *mm, *oldmm;
    
    	prepare_task_switch(rq, prev, next);
    	trace_sched_switch(rq, prev, next);
    	mm = next->mm;
    	oldmm = prev->active_mm;
    	/*
    	 * For paravirt, this is coupled with an exit in switch_to to
    	 * combine the page table reload and the switch backend into
    	 * one hypercall.
    	 */
    	arch_start_context_switch(prev);
    
    	if (unlikely(!mm)) {
    		next->active_mm = oldmm;
    		atomic_inc(&oldmm->mm_count);
    		enter_lazy_tlb(oldmm, next);
    	} else
    		switch_mm(oldmm, mm, next);
    
    	if (unlikely(!prev->mm)) {
    		prev->active_mm = NULL;
    		rq->prev_mm = oldmm;
    	}
    	/*
    	 * Since the runqueue lock will be released by the next
    	 * task (which is an invalid locking op but in the case
    	 * of the scheduler it's an obvious special-case), so we
    	 * do an early lockdep release here:
    	 */
    #ifndef __ARCH_WANT_UNLOCKED_CTXSW
    	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
    #endif
    
    	/* Here we just switch the register state and the stack. */
    	switch_to(prev, next, prev);
    
    	barrier();
    	/*
    	 * this_rq must be evaluated again because prev may have moved
    	 * CPUs since it called schedule(), thus the 'rq' on its stack
    	 * frame will be invalid.
    	 */
    	finish_task_switch(this_rq(), prev);
    }

    由上面代码可以看出内核的进程切换由两部分实现:

    1. 切换全局页目录以安装一个新的地址空间,由switch_mm()函数完成。
    2. 切换内核堆栈和硬件上下文。硬件上下文提供了内核执行新进程所需要的所有信息,包含CPU寄存器,由switch_to()完成。

    4结语

    本文结合代码分析了schedule函数的执行过程以及实现方式,由于context_switch()函数中的switch_mm()和switch_to()较为晦涩这里不再详细分析。有兴趣的同学可以在闲暇时间学习研究。

     

    展开全文
  • 日期 内核版本 架构 作者 GitHub ...我们前面提到linux有两种方法激活调度器:核心调度器和 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU 另一种是通过周期性的机制, 以固定的频率运行, 不时
    日期内核版本架构作者GitHubCSDN
    2016-6-29Linux-4.6X86 & armgatiemeLinuxDeviceDriversLinux进程管理与调度

    我们前面提到linux有两种方法激活调度器:核心调度器和

    • 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU

    • 另一种是通过周期性的机制, 以固定的频率运行, 不时的检测是否有必要

    因而内核提供了两个调度器主调度器周期性调度器,分别实现如上工作, 两者合在一起就组成了核心调度器(core scheduler), 也叫通用调度器(generic scheduler).

    他们都根据进程的优先级分配CPU时间, 因此这个过程就叫做优先调度, 我们将在本节主要讲解核心调度器的设计和优先调度的实现方式.

    而我们的周期性调度器以固定的频率激活负责当前进程调度类的周期性调度方法, 以保证系统的并发性

    1 前景回顾


    首先还是让我们简单回顾一下子之前的的内容

    1.1 进程调度


    内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.

    调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换.

    内核必须提供一种方法, 在各个进程之间尽可能公平地共享CPU时间, 而同时又要考虑不同的任务优先级.

    调度器的一般原理是, 按所需分配的计算能力, 向系统中每个进程提供最大的公正性, 或者从另外一个角度上说, 他试图确保没有进程被亏待.

    1.2 进程的分类


    linux把进程区分为实时进程非实时进程, 其中非实时进程进一步划分为交互式进程和批处理进程

    根据进程的不同分类Linux采用不同的调度策略.

    对于实时进程,采用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限优先调度算法|的调度策略.

    对于普通进程则采用CFS完全公平调度器进行调度

    1.3 linux调度器的演变


    字段版本
    O(n)的始调度算法linux-0.11~2.4
    O(1)调度器linux-2.5
    CFS调度器linux-2.6~至今

    1.4 Linux的调度器组成


    2个调度器

    可以用两种方法来激活调度

    • 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU

    • 另一种是通过周期性的机制, 以固定的频率运行, 不时的检测是否有必要

    因此当前linux的调度程序由两个调度器组成:主调度器周期性调度器(两者又统称为通用调度器(generic scheduler)核心调度器(core scheduler))

    并且每个调度器包括两个内容:调度框架(其实质就是两个函数框架)及调度器类

    6种调度策略

    linux内核目前实现了6中调度策略(即调度算法), 用于对不同类型的进程进行调度, 或者支持某些特殊的功能

    • SCHED_NORMAL和SCHED_BATCH调度普通的非实时进程

    • SCHED_FIFO和SCHED_RR和SCHED_DEADLINE则采用不同的调度策略调度实时进程

    • SCHED_IDLE则在系统空闲时调用idle进程.

    5个调度器类

    而依据其调度策略的不同实现了5个调度器类, 一个调度器类可以用一种种或者多种调度策略调度某一类进程, 也可以用于特殊情况或者调度特殊功能的进程.

    其所属进程的优先级顺序为

    stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

    3个调度实体

    调度器不限于调度进程, 还可以调度更大的实体, 比如实现组调度.

    这种一般性要求调度器不直接操作进程, 而是处理可调度实体, 因此需要一个通用的数据结构描述这个调度实体,即seched_entity结构, 其实际上就代表了一个调度对象,可以为一个进程,也可以为一个进程组.

    linux中针对当前可调度的实时和非实时进程, 定义了类型为seched_entity的3个调度实体

    • sched_dl_entity 采用EDF算法调度的实时调度实体

    • sched_rt_entity 采用Roound-Robin或者FIFO算法调度的实时调度实体 rt_sched_class

    • sched_entity 采用CFS算法调度的普通非实时进程的调度实体

    2 周期性调度器


    周期性调度器在scheduler_tick中实现. 如果系统正在活动中, 内核会按照频率HZ自动调用该函数. 如果没有近曾在等待调度, 那么在计算机电力供应不足的情况下, 内核将关闭该调度器以减少能耗. 这对于我们的嵌入式设备或者手机终端设备的电源管理是很重要的.

    2.1 周期性调度器主流程


    scheduler_tick函数定义在kernel/sched/core.c, L2910中, 它有两个主要任务

    1. 更新相关统计量

      管理内核中的与整个系统和各个进程的调度相关的统计量. 其间执行的主要操作是对各种计数器+1

    2. 激活负责当前进程调度类的周期性调度方法

      检查进程执行的时间是否超过了它对应的ideal_runtime,如果超过了,则告诉系统,需要启动主调度器(schedule)进行进程切换。(注意thread_info:preempt_count、thread_info:flags (TIF_NEED_RESCHED))

    /*
     * This function gets called by the timer code, with HZ frequency.
     * We call it with interrupts disabled.
     */
    
    void scheduler_tick(void)
    {
        /*  1.  获取当前cpu上的全局就绪队列rq和当前运行的进程curr  */
    
        /*  1.1 在于SMP的情况下,获得当前CPU的ID。如果不是SMP,那么就返回0  */
        int cpu = smp_processor_id();
    
        /*  1.2 获取cpu的全局就绪队列rq, 每个CPU都有一个就绪队列rq  */
        struct rq *rq = cpu_rq(cpu);
    
        /*  1.3 获取就绪队列上正在运行的进程curr  */
        struct task_struct *curr = rq->curr;
    
        sched_clock_tick();
    
        /*  2 更新rq上的统计信息, 并执行进程对应调度类的周期性的调度  */
    
        /*  加锁 */
        raw_spin_lock(&rq->lock);
    
        /*  2.1 更新rq的当前时间戳.即使rq->clock变为当前时间戳  */
        update_rq_clock(rq);
    
        /*  2.2 执行当前运行进程所在调度类的task_tick函数进行周期性调度  */
        curr->sched_class->task_tick(rq, curr, 0);
    
        /*  2.3 更新rq的负载信息,  即就绪队列的cpu_load[]数据
         *  本质是讲数组中先前存储的负荷值向后移动一个位置,
         *  将当前负荷记入数组的第一个位置 */
        update_cpu_load_active(rq);
    
    
    
        /*  2.4 更新cpu的active count活动计数
         *  主要是更新全局cpu就绪队列的calc_load_update*/
        calc_global_load_tick(rq);
    
        /* 解锁 */
        raw_spin_unlock(&rq->lock);
    
        /* 与perf计数事件相关 */
        perf_event_task_tick();
    
    #ifdef CONFIG_SMP
    
         /* 当前CPU是否空闲 */
        rq->idle_balance = idle_cpu(cpu);
    
        /* 如果到是时候进行周期性负载平衡则触发SCHED_SOFTIRQ */
        trigger_load_balance(rq);
    
    #endif
    
        rq_last_tick_reset(rq);
    }

    2.2 更新统计量


    函数描述定义
    update_rq_clock处理就绪队列时钟的更新, 本质上就是增加struct rq当前实例的时钟时间戳sched/core.c, L98
    update_cpu_load_active负责更新就绪队列的cpu_load数组, 其本质上相当于将数组中先前存储的负荷值向后移动一个位置, 将当前就绪队列的符合记入数组的第一个位置. 另外该函数还引入一些取平均值的技巧, 以确保符合数组的内容不会呈现太多的不联系跳读.kernel/sched/fair.c, L4641
    calc_global_load_tick跟新cpu的活动计数, 主要是更新全局cpu就绪队列的calc_load_updatekernel/sched/loadavg.c, L382

    2.3 激活进程所属调度类的周期性调度器


    由于调度器的模块化结构, 主体工程其实很简单, 在更新统计信息的同时, 内核将真正的调度工作委托给了特定的调度类方法

    内核先找到了就绪队列上当前运行的进程curr, 然后调用curr所属调度类sched_class的周期性调度方法task_tick

    curr->sched_class->task_tick(rq, curr, 0);

    task_tick的实现方法取决于底层的调度器类, 例如完全公平调度器会在该方法中检测是否进程已经运行了太长的时间, 以避免过长的延迟, 注意此处的做法与之前就的基于时间片的调度方法有本质区别, 旧的方法我们称之为到期的时间片, 而完全公平调度器CFS中则不存在所谓的时间片概念.

    目前我们的内核中的3个调度器类struct sched_entity, struct sched_rt_entity, 和struct sched_dl_entity dl, 我们针对当前内核中实现的调度器类分别列出其周期性调度函数task_tick

    调度器类task_tick操作task_tick函数定义
    stop_sched_classkernel/sched/stop_task.c, line 77, task_tick_stop
    dl_sched_classkernel/sched/deadline.c, line 1192, task_tick_dl
    rt_sched_class/kernel/sched/rt.c, line 2227, task_tick_rt
    fail_sched_classkernel/sched/fair.c, line 8116, task_tick_fail
    idle_sched_classkernel/sched/idle_task.c, line 53, task_tick_idle

    * 如果当前进程是完全公平队列中的进程, 则首先根据当前就绪队列中的进程数算出一个延迟时间间隔,大概每个进程分配2ms时间,然后按照该进程在队列中的总权重中占得比例,算出它该执行的时间X,如果该进程执行物理时间超过了X,则激发延迟调度;如果没有超过X,但是红黑树就绪队列中下一个进程优先级更高,即curr->vruntime-leftmost->vruntime > X,也将延迟调度

    延迟调度的真正调度过程在:schedule中实现,会按照调度类顺序和优先级挑选出一个最高优先级的进程执行

    • 如果当前进程是实时调度类中的进程:则如果该进程是SCHED_RR,则递减时间片[为HZ/10],到期,插入到队列尾部,并激发延迟调度,如果是SCHED_FIFO,则什么也不做,直到该进程执行完成

    如果当前进程希望被重新调度, 那么调度类方法会在task_struct中设置TIF_NEED_RESCHED标志, 以表示该请求, 而内核将会在接下来的适当实际完成此请求.

    3 周期性调度器的激活


    3.1 定时器周期性的激活调度器


    定时器是Linux提供的一种定时服务的机制. 它在某个特定的时间唤醒某个进程,来做一些工作.

    在低分辨率定时器的每次时钟中断完成全局统计量更新后, 每个cpu在软中断中执行一下操作

    • 更新该cpu上当前进程内核态、用户态使用时间xtime_update
    • 调用该cpu上的定时器函数
    • 启动周期性定时器(scheduler_tick)完成该cpu上任务的周期性调度工作;

    在支持动态定时器的系统中,可以关闭该调度器,从而进入深度睡眠过程;scheduler_tick查看当前进程是否运行太长时间,如果是,将进程的TIF_NEED_RESCHED置位,然后再中断返回时,调用schedule,进行进程切换操作

    //  http://lxr.free-electrons.com/source/arch/arm/kernel/time.c?v=4.6#L74
    /*
    * Kernel system timer support.
    */
    void timer_tick(void)
    {
        profile_tick(CPU_PROFILING);
        xtime_update(1);
    #ifndef CONFIG_SMP
        update_process_times(user_mode(get_irq_regs()));
    #endif
    }
    
    //  http://lxr.free-electrons.com/source/kernel/time/timer.c?v=4.6#L1409
    /*
     * Called from the timer interrupt handler to charge one tick to the current
     * process.  user_tick is 1 if the tick is user time, 0 for system.
     */
    void update_process_times(int user_tick)
    {
        struct task_struct *p = current;
    
        /* Note: this timer irq context must be accounted for as well. */
        account_process_tick(p, user_tick);
        run_local_timers();
        rcu_check_callbacks(user_tick);
    #ifdef CONFIG_IRQ_WORK
        if (in_irq())
            irq_work_tick();
    #endif
        scheduler_tick();
        run_posix_cpu_timers(p);
    }

    早期实现


    Linux初始化时, init_IRQ()函数设定8253的定时周期为10ms(一个tick值). 同样,在初始化时, time_init()用setup_irq()设置时间中断向量irq0, 中断服务程序为timer_interrupt.

    在2.4版内核及较早的版本当中, 定时器的中断处理采用底半机制, 底半处理函数的注册在start_kernel()函数中调用sechd_init(), 在这个函数中又调用init_bh(TIMER_BH, timer_bh)注册了定时器的底半处理函数. 然后系统才调用time_init( )来注册定时器的中断向量和中断处理函数.

    在中断处理函数timer_interrupt()中,主要是调用do_timer()函数完成工作。do_timer()函数的主要功能就是调用mark_bh()产生软中断,随后处理器会在合适的时候调用定时器底半处理函数timer_bh()。在timer_bh()中, 实现了更新定时器的功能. 2.4.23版的do_timer()函数代码如下(经过简略):

    void do_timer(struct pt_regs *regs)
    {
           (*(unsigned long *)&jiffies)++;
           update_process_times(user_mode(regs));
           mark_bh(TIMER_BH);
    }

    而在内核2.6版本以后,定时器中断处理采用了软中断机制而不是底半机制。时钟中断处理函数仍然为timer_interrup()-> do_timer_interrupt()-> do_timer_interrupt_hook()-> do_timer()。不过do_timer()函数的实现有所不同

    void do_timer(struct pt_regs *regs)
    {
           jiffies_64++;
           update_process_times(user_mode(regs));
           update_times();
    }

    更详细的实现linux-2.6

    Linux中断处理之时钟中断(一)

    (原创)linux内核进程调度以及定时器实现机制

    参考

    进程管理与调度5 – 进程调度、进程切换原理详解

    展开全文
  • 日期 内核版本 架构 作者 GitHub ...我们前面提到linux有两种方法激活调度器:核心调度器和 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU 另一种是通过周期性的机制, 以固定的频率运行, 不
    日期内核版本架构作者GitHubCSDN
    2016-06-30Linux-4.6X86 & armgatiemeLinuxDeviceDriversLinux进程管理与调度

    我们前面提到linux有两种方法激活调度器:核心调度器和

    • 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU

    • 另一种是通过周期性的机制, 以固定的频率运行, 不时的检测是否有必要

    因而内核提供了两个调度器主调度器周期性调度器,分别实现如上工作, 两者合在一起就组成了核心调度器(core scheduler), 也叫通用调度器(generic scheduler).

    他们都根据进程的优先级分配CPU时间, 因此这个过程就叫做优先调度, 我们将在本节主要讲解周期调度的设计和实现方式

    在内核中的许多地方, 如果要将CPU分配给与当前活动进程不同的另一个进程, 都会直接调用主调度器函数schedule, 从系统调用返回后, 内核也会检查当前进程是否设置了重调度标志TLF_NEDD_RESCHED

    1 前景回顾


    1.1 进程调度


    内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.

    调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换.

    1.2 进程的分类


    linux把进程区分为实时进程非实时进程, 其中非实时进程进一步划分为交互式进程和批处理进程

    根据进程的不同分类Linux采用不同的调度策略.

    对于实时进程,采用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限优先调度算法|的调度策略.

    1.3 linux调度器的演变


    字段版本
    O(n)的始调度算法linux-0.11~2.4
    O(1)调度器linux-2.5
    CFS调度器linux-2.6~至今

    1.4 Linux的调度器组成


    2个调度器

    可以用两种方法来激活调度

    • 一种是直接的, 比如进程打算睡眠或出于其他原因放弃CPU

    • 另一种是通过周期性的机制, 以固定的频率运行, 不时的检测是否有必要

    因此当前linux的调度程序由两个调度器组成:主调度器周期性调度器(两者又统称为通用调度器(generic scheduler)核心调度器(core scheduler))

    并且每个调度器包括两个内容:调度框架(其实质就是两个函数框架)及调度器类

    6种调度策略

    linux内核目前实现了6中调度策略(即调度算法), 用于对不同类型的进程进行调度, 或者支持某些特殊的功能

    • SCHED_NORMAL和SCHED_BATCH调度普通的非实时进程

    • SCHED_FIFO和SCHED_RR和SCHED_DEADLINE则采用不同的调度策略调度实时进程

    • SCHED_IDLE则在系统空闲时调用idle进程.

    5个调度器类

    而依据其调度策略的不同实现了5个调度器类, 一个调度器类可以用一种种或者多种调度策略调度某一类进程, 也可以用于特殊情况或者调度特殊功能的进程.

    其所属进程的优先级顺序为

    stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

    3个调度实体

    调度器不限于调度进程, 还可以调度更大的实体, 比如实现组调度.

    这种一般性要求调度器不直接操作进程, 而是处理可调度实体, 因此需要一个通用的数据结构描述这个调度实体,即seched_entity结构, 其实际上就代表了一个调度对象,可以为一个进程,也可以为一个进程组.

    linux中针对当前可调度的实时和非实时进程, 定义了类型为seched_entity的3个调度实体

    • sched_dl_entity 采用EDF算法调度的实时调度实体

    • sched_rt_entity 采用Roound-Robin或者FIFO算法调度的实时调度实体 rt_sched_class

    • sched_entity 采用CFS算法调度的普通非实时进程的调度实体

    2 主调度器


    在内核中的许多地方, 如果要将CPU分配给与当前活动进程不同的另一个进程, 都会直接调用主调度器函数schedule, 从系统调用返回后, 内核也会检查当前进程是否设置了重调度标志TLF_NEDD_RESCHED

    例如, 前述的周期性调度器的scheduler_tick就会设置该标志, 如果是这样则内核会调用schedule, 该函数假定当前活动进程一定会被另一个进程取代.

    2.1 调度函数的__sched前缀

    在详细论述schedule之前, 需要说明一下__sched前缀, 该前缀可能用于调用schedule的函数, 包括schedule本身.

    __sched前缀的声明, 在include/linux/sched.h, L416, 如下所示

    /* Attach to any functions which should be ignored in wchan output. */
    #define __sched         __attribute__((__section__(".sched.text")))

    attribute((_section(“…”)))是一个gcc的编译属性, 其目的在于将相关的函数的代码编译之后, 放到目标文件的以恶搞特定的段内, 即.sched.text中. 该信息使得内核在显示栈转储活类似信息时, 忽略所有与调度相关的调用. 由于调度哈书调用不是普通代码流程的一部分, 因此在这种情况下是没有意义的.

    用它修饰函数的方式如下

    void __sched some_function(args, ...)
    {
        ......
        schedule();
        ......
    }

    2.2 schedule函数


    2.2.1 schedule主框架


    schedule就是主调度器的函数, 在内核中的许多地方, 如果要将CPU分配给与当前活动进程不同的另一个进程, 都会直接调用主调度器函数schedule.

    该函数完成如下工作

    1. 确定当前就绪队列, 并在保存一个指向当前(仍然)活动进程的task_struct指针

    2. 检查死锁, 关闭内核抢占后调用__schedule完成内核调度

    3. 恢复内核抢占, 然后检查当前进程是否设置了重调度标志TLF_NEDD_RESCHED, 如果该进程被其他进程设置了TIF_NEED_RESCHED标志, 则函数重新执行进行调度

    该函数定义在kernel/sched/core.c, L3243, 如下所示

    asmlinkage __visible void __sched schedule(void)
    {
    
        /*  获取当前的进程  */
        struct task_struct *tsk = current;
    
        /*  避免死锁 */
        sched_submit_work(tsk);
        do {
            preempt_disable();                                  /*  关闭内核抢占  */
            __schedule(false);                                  /*  完成调度  */
            sched_preempt_enable_no_resched();                  /*  开启内核抢占  */
        } while (need_resched());   /*  如果该进程被其他进程设置了TIF_NEED_RESCHED标志,则函数重新执行进行调度    */
    }
    EXPORT_SYMBOL(schedule);

    2.2.2 sched_submit_work避免死锁


    该函数定义在kernel/sched/core.c, L3231, 如下所示

    static inline void sched_submit_work(struct task_struct *tsk)
    {
        /*  检测tsk->state是否为0 (runnable), 若为运行态时则返回,
         *   tsk_is_pi_blocked(tsk),检测tsk的死锁检测器是否为空,若非空的话就return
        if (!tsk->state || tsk_is_pi_blocked(tsk))
            return;
        /*
         * If we are going to sleep and we have plugged IO queued,
         * make sure to submit it to avoid deadlocks.
         */
        if (blk_needs_flush_plug(tsk))  /*  然后检测是否需要刷新plug队列,用来避免死锁  */
            blk_schedule_flush_plug(tsk);
    }

    2.2.3 preempt_disable和sched_preempt_enable_no_resched开关内核抢占


    内核抢占

    Linux除了内核态外还有用户态。用户程序的上下文属于用户态,系统调用和中断处理例程上下文属于内核态. 如果一个进程在用户态时被其他进程抢占了COU则成发生了用户态抢占, 而如果此时进程进入了内核态, 则内核此时代替进程执行, 如果此时发了抢占, 我们就说发生了内核抢占.

    内核抢占是Linux 2.6以后引入的一个重要的概念

    我们说:如果进程正执行内核函数时,即它在内核态运行时,允许发生内核切换(被替换的进程是正执行内核函数的进程),这个内核就是抢占的。

    抢占内核的主要特点是:一个在内核态运行的进程,当且仅当在执行内核函数期间被另外一个进程取代。

    这与用户态的抢占有本质区别.

    内核为了支撑内核抢占, 提供了很多机制和结构, 必要时候开关内核抢占也是必须的, 这些函数定义在include/linux/preempt.h, L145

    #define preempt_disable() \
    do { \
        preempt_count_inc(); \
        barrier(); \
    } while (0)
    
    #define sched_preempt_enable_no_resched() \
    do { \
        barrier(); \
        preempt_count_dec(); \
    } while (0)

    2.3 __schedule开始进程调度


    __schedule完成了真正的调度工作, 其定义在kernel/sched/core.c, L3103, 如下所示

    2.3.1 __schedule函数主框架


    static void __sched notrace __schedule(bool preempt)
    {
        struct task_struct *prev, *next;
        unsigned long *switch_count;
        struct rq *rq;
        int cpu;
    
        /*  ==1==  
            找到当前cpu上的就绪队列rq
            并将正在运行的进程curr保存到prev中  */
        cpu = smp_processor_id();
        rq = cpu_rq(cpu);
        prev = rq->curr;
    
        /*
         * do_exit() calls schedule() with preemption disabled as an exception;
         * however we must fix that up, otherwise the next task will see an
         * inconsistent (higher) preempt count.
         *
         * It also avoids the below schedule_debug() test from complaining
         * about this.
         */
        if (unlikely(prev->state == TASK_DEAD))
            preempt_enable_no_resched_notrace();
    
        /*  如果禁止内核抢占,而又调用了cond_resched就会出错
         *  这里就是用来捕获该错误的  */
        schedule_debug(prev);
    
        if (sched_feat(HRTICK))
            hrtick_clear(rq);
    
        /*  关闭本地中断  */
        local_irq_disable();
    
        /*  更新全局状态,
         *  标识当前CPU发生上下文的切换  */
        rcu_note_context_switch();
    
        /*
         * Make sure that signal_pending_state()->signal_pending() below
         * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
         * done by the caller to avoid the race with signal_wake_up().
         */
        smp_mb__before_spinlock();
        /*  锁住该队列  */
        raw_spin_lock(&rq->lock);
        lockdep_pin_lock(&rq->lock);
    
        rq->clock_skip_update <<= 1; /* promote REQ to ACT */
    
        /*  切换次数记录, 默认认为非主动调度计数(抢占)  */
        switch_count = &prev->nivcsw;
    
        /*
         *  scheduler检查prev的状态state和内核抢占表示
         *  如果prev是不可运行的, 并且在内核态没有被抢占
         *  
         *  此时当前进程不是处于运行态, 并且不是被抢占
         *  此时不能只检查抢占计数
         *  因为可能某个进程(如网卡轮询)直接调用了schedule
         *  如果不判断prev->stat就可能误认为task进程为RUNNING状态
         *  到达这里,有两种可能,一种是主动schedule, 另外一种是被抢占
         *  被抢占有两种情况, 一种是时间片到点, 一种是时间片没到点
         *  时间片到点后, 主要是置当前进程的need_resched标志
         *  接下来在时钟中断结束后, 会preempt_schedule_irq抢占调度
         *  
         *  那么我们正常应该做的是应该将进程prev从就绪队列rq中删除, 
         *  但是如果当前进程prev有非阻塞等待信号, 
         *  并且它的状态是TASK_INTERRUPTIBLE
         *  我们就不应该从就绪队列总删除它 
         *  而是配置其状态为TASK_RUNNING, 并且把他留在rq中
    
        /*  如果内核态没有被抢占, 并且内核抢占有效
            即是否同时满足以下条件:
            1  该进程处于停止状态
            2  该进程没有在内核态被抢占 */
        if (!preempt && prev->state)
        {
    
            /*  如果当前进程有非阻塞等待信号,并且它的状态是TASK_INTERRUPTIBLE  */
            if (unlikely(signal_pending_state(prev->state, prev)))
            {
                /*  将当前进程的状态设为:TASK_RUNNING  */
                prev->state = TASK_RUNNING;
            }
            else   /*  否则需要将prev进程从就绪队列中删除*/
            {
                /*  将当前进程从runqueue(运行队列)中删除  */
                deactivate_task(rq, prev, DEQUEUE_SLEEP);
    
                /*  标识当前进程不在runqueue中  */
                prev->on_rq = 0;
    
                /*
                 * If a worker went to sleep, notify and ask workqueue
                 * whether it wants to wake up a task to maintain
                 * concurrency.
                 */
                if (prev->flags & PF_WQ_WORKER) {
                    struct task_struct *to_wakeup;
    
                    to_wakeup = wq_worker_sleeping(prev);
                    if (to_wakeup)
                        try_to_wake_up_local(to_wakeup);
                }
            }
            /*  如果不是被抢占的,就累加主动切换次数  */
            switch_count = &prev->nvcsw;
        }
    
        /*  如果prev进程仍然在就绪队列上没有被删除  */
        if (task_on_rq_queued(prev))
            update_rq_clock(rq);  /*  跟新就绪队列的时钟  */
    
        /*  挑选一个优先级最高的任务将其排进队列  */
        next = pick_next_task(rq, prev);
        /*  清除pre的TIF_NEED_RESCHED标志  */
        clear_tsk_need_resched(prev);
        /*  清楚内核抢占标识  */
        clear_preempt_need_resched();
    
        rq->clock_skip_update = 0;
    
        /*  如果prev和next非同一个进程  */
        if (likely(prev != next))
        {
            rq->nr_switches++;  /*  队列切换次数更新  */
            rq->curr = next;    /*  将next标记为队列的curr进程  */
            ++*switch_count;    /* 进程切换次数更新  */
    
            trace_sched_switch(preempt, prev, next);
            /*  进程之间上下文切换    */
            rq = context_switch(rq, prev, next); /* unlocks the rq */
        }
        else    /*  如果prev和next为同一进程,则不进行进程切换  */
        {
            lockdep_unpin_lock(&rq->lock);
            raw_spin_unlock_irq(&rq->lock);
        }
    
        balance_callback(rq);
    }
    STACK_FRAME_NON_STANDARD(__schedule); /* switch_to() */

    2.3.2 pick_next_task选择抢占的进程


    内核从cpu的就绪队列中选择一个最合适的进程来抢占CPU

    next = pick_next_task(rq);

    全局的pick_next_task函数会从按照优先级遍历所有调度器类的pick_next_task函数, 去查找最优的那个进程, 当然因为大多数情况下, 系统中全是CFS调度的非实时进程, 因而linux内核也有一些优化的策略

    其执行流程如下

    • 如果当前cpu上所有的进程都是cfs调度的普通非实时进程, 则直接用cfs调度, 如果无程序可调度则调度idle进程

    • 否则从优先级最高的调度器类sched_class_highest(目前是stop_sched_class)开始依次遍历所有调度器类的pick_next_task函数, 选择最优的那个进程执行

    其定义在kernel/sched/core.c, line 3068, 如下所示

    /*
     * Pick up the highest-prio task:
     */
    static inline struct task_struct *
    pick_next_task(struct rq *rq, struct task_struct *prev)
    {
        const struct sched_class *class = &fair_sched_class;
        struct task_struct *p;
    
        /*
         * Optimization: we know that if all tasks are in
         * the fair class we can call that function directly:
         *
         * 如果待被调度的进程prev是隶属于CFS的普通非实时进程
         * 而当前cpu的全局就绪队列rq中的进程数与cfs_rq的进程数相等
         * 则说明当前cpu上的所有进程都是由cfs调度的普通非实时进程
         *
         * 那么我们选择最优进程的时候
         * 就只需要调用cfs调度器类fair_sched_class的选择函数pick_next_task
         * 就可以找到最优的那个进程p
         */
        /*  如果当前所有的进程都被cfs调度, 没有实时进程  */
        if (likely(prev->sched_class == class &&
               rq->nr_running == rq->cfs.h_nr_running))
        {
            /*  调用cfs的选择函数pick_next_task找到最优的那个进程p*/
            p = fair_sched_class.pick_next_task(rq, prev);
            /*  #define RETRY_TASK ((void *)-1UL)有被其他调度气找到合适的进程  */
            if (unlikely(p == RETRY_TASK))
                goto again; /*  则遍历所有的调度器类找到最优的进程 */
    
            /* assumes fair_sched_class->next == idle_sched_class */
            if (unlikely(!p))   /*  如果没有进程可被调度  */
                p = idle_sched_class.pick_next_task(rq, prev); /*  则调度idle进程  */
    
            return p;
        }
    
    /*  进程中所有的调度器类, 是通过next域链接域链接在一起的
     *  调度的顺序为stop -> dl -> rt -> fair -> idle 
     *  again出的循环代码会遍历他们找到一个最优的进程  */
    again:
        for_each_class(class)
        {
            p = class->pick_next_task(rq, prev);
            if (p)
            {
                if (unlikely(p == RETRY_TASK))
                    goto again;
                return p;
            }
        }
    
        BUG(); /* the idle class will always have a runnable task */
    }
    ````
    
    进程中所有的调度器类, 是通过next域链接域链接在一起的, 调度的顺序为
    
    
    
    
    
    <div class="se-preview-section-delimiter"></div>
    
    ```c
    stop -> dl -> rt -> fair -> idle

    其中for_each_class遍历所有的调度器类, 依次执行pick_next_task操作选择最优的进程

    它会从优先级最高的sched_class_highest(目前是stop_sched_class)查起, 依次按照调度器类的优先级从高到低的顺序调用调度器类对应的pick_next_task_fair函数直到查找到一个能够被调度的进程

    for_each_class定义在kernel/sched/sched.h, 如下所示

    #define sched_class_highest (&stop_sched_class)
    #define for_each_class(class) \
       for (class = sched_class_highest; class; class = class->next)
    
    extern const struct sched_class stop_sched_class;
    extern const struct sched_class dl_sched_class;
    extern const struct sched_class rt_sched_class;
    extern const struct sched_class fair_sched_class;
    extern const struct sched_class idle_sched_class;

    除了全局的pick_next_task函数, 每个调度器类都提供了pick_next_task函数用以查找对应调度器下的最优进程, 其定义如下所示

    调度器类pick_next策略pick_next_task_fair函数
    stop_sched_classkernel/sched/stop_task.c, line 121, pick_next_task_stop
    dl_sched_classkernel/sched/deadline.c, line 1782, pick_next_task_dl
    rt_sched_class取出合适的进程后, dequeue_pushable_task从pushable队列里取出来/kernel/sched/rt.c, line 1508, pick_next_task_rt
    fail_sched_classpick_next_task_fair,从红黑树里,选出vtime最小的那个进程,调用set_next_entity将其出队kernel/sched/fair.c, line 5441, pick_next_task_fail
    idle_sched_class直接调度idle进程kernel/sched/idle_task.c, line 26, pick_next_task_idle

    实际上,对于RT进程,put和pick并不操作运行队列

    对于FIFO和RR的区别,在scheduler_tick中通过curr->sched_class->task_tick进入到task_tick_rt的处理, 如果是非RR的进程则直接返回,否则递减时间片,如果时间片耗完,则需要将当前进程放到运行队列的末尾, 这个时候才操作运行队列(FIFO和RR进程,是否位于同一个plist队列?),时间片到点,会重新移动当前进程requeue_task_rt,进程会被加到队列尾,接下来set_tsk_need_resched触发调度,进程被抢占进入schedule

    问题1 : 为什么要多此一举判断所有的进程是否全是cfs调度的普通非实时进程?

    加快经常性事件, 是程序开发中一个优化的准则, 那么linux系统中最普遍的进程是什么呢? 肯定是非实时进程啊, 其调度器必然是cfs, 因此

    rev->sched_class == class && rq->nr_running == rq->cfs.h_nr_running

    这种情形发生的概率是很大的, y也就是说多数情形下, 我们的linux中进程全是cfs调度的

    而likely这个宏业表明了这点, 这也是gcc内建的一个编译选项, 它其实就是告诉编译器表达式很大的情况下为真, 编译器可以对此做出优化

    //  http://lxr.free-electrons.com/source/tools/virtio/linux/kernel.h?v=4.6#L91
     #ifndef likely
     # define likely(x)     (__builtin_expect(!!(x), 1))
     #endif
    
     #ifndef unlikely
     # define unlikely(x)   (__builtin_expect(!!(x), 0))
     #endif

    2.4 context_switch进程上下文切换


    进程上下文的切换其实是一个很复杂的过程, 我们在这里不能详述, 但是我会尽可能说明白

    具体的内容请参照

    2.4.1 进程上下文切换


    上下文切换(有时也称做进程切换任务切换)是指CPU从一个进程或线程切换到另一个进程或线程

    稍微详细描述一下,上下文切换可以认为是内核(操作系统的核心)在 CPU 上对于进程(包括线程)进行以下的活动:

    1. 挂起一个进程,将这个进程在 CPU 中的状态(上下文)存储于内存中的某处,

    2. 在内存中检索下一个进程的上下文并将其在 CPU 的寄存器中恢复

    3. 跳转到程序计数器所指向的位置(即跳转到进程被中断时的代码行),以恢复该进程

    因此上下文是指某一时间点CPU寄存器和程序计数器的内容, 广义上还包括内存中进程的虚拟地址映射信息.

    上下文切换只能发生在内核态中, 上下文切换通常是计算密集型的。也就是说,它需要相当可观的处理器时间,在每秒几十上百次的切换中,每次切换都需要纳秒量级的时间。所以,上下文切换对系统来说意味着消耗大量的 CPU 时间,事实上,可能是操作系统中时间消耗最大的操作。
    Linux相比与其他操作系统(包括其他类 Unix 系统)有很多的优点,其中有一项就是,其上下文切换和模式切换的时间消耗非常少.

    2.4.2 context_switch流程


    context_switch函数完成了进程上下文的切换, 其定义在kernel/sched/core.c#L2711

    context_switch( )函数建立next进程的地址空间。进程描述符的active_mm字段指向进程所使用的内存描述符,而mm字段指向进程所拥有的内存描述符。对于一般的进程,这两个字段有相同的地址,但是,内核线程没有它自己的地址空间而且它的 mm字段总是被设置为 NULL

    context_switch( )函数保证:如果next是一个内核线程, 它使用prev所使用的地址空间

    它主要执行如下操作

    • 调用switch_mm(), 把虚拟内存从一个进程映射切换到新进程中

    • 调用switch_to(),从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息

    由于不同架构下地址映射的机制有所区别, 而寄存器等信息弊病也是依赖于架构的, 因此switch_mm和switch_to两个函数均是体系结构相关的

    2.4.3 switch_mm切换进程虚拟地址空间


    switch_mm主要完成了进程prev到next虚拟地址空间的映射, 由于内核虚拟地址空间是不许呀切换的, 因此切换的主要是用户态的虚拟地址空间

    这个是一个体系结构相关的函数, 其实现在对应体系结构下的arch/对应体系结构/include/asm/mmu_context.h文件中, 我们下面列出了几个常见体系结构的实现

    体系结构switch_mm实现
    x86arch/x86/include/asm/mmu_context.h, line 118
    armarch/arm/include/asm/mmu_context.h, line 126
    arm64arch/arm64/include/asm/mmu_context.h, line 183

    其主要工作就是切换了进程的CR3

    控制寄存器(CR0~CR3)用于控制和确定处理器的操作模式以及当前执行任务的特性

    CR0中含有控制处理器操作模式和状态的系统控制标志;

    CR1保留不用;

    CR2含有导致页错误的线性地址;

    CR3中含有页目录表物理内存基地址,因此该寄存器也被称为页目录基地址寄存器PDBR(Page-Directory Base address Register)。

    2.4.4 switch_to切换进程堆栈和寄存器


    执行环境的切换是在switch_to()中完成的, switch_to完成最终的进程切换,它保存原进程的所有寄存器信息,恢复新进程的所有寄存器信息,并执行新的进程

    调度过程可能选择了一个新的进程, 而清理工作则是针对此前的活动进程, 请注意, 这不是发起上下文切换的那个进程, 而是系统中随机的某个其他进程, 内核必须想办法使得进程能够与context_switch例程通信, 这就可以通过switch_to宏实现. 因此switch_to函数通过3个参数提供2个变量,

    在新进程被选中时, 底层的进程切换冽程必须将此前执行的进程提供给context_switch, 由于控制流会回到陔函数的中间, 这无法用普通的函数返回值来做到, 因此提供了3个参数的宏

    /*
     * Saving eflags is important. It switches not only IOPL between tasks,
     * it also protects other tasks from NT leaking through sysenter etc.
    */
    #define switch_to(prev, next, last)
    体系结构switch_to实现
    x86arch/x86/include/asm/switch_to.h中两种实现

    定义CONFIG_X86_32宏

    未定义CONFIG_X86_32宏
    armarch/arm/include/asm/switch_to.h, line 25
    通用include/asm-generic/switch_to.h, line 25

    内核在switch_to中执行如下操作

    1. 进程切换, 即esp的切换, 由于从esp可以找到进程的描述符

    2. 硬件上下文切换, 设置ip寄存器的值, 并jmp到__switch_to函数

    3. 堆栈的切换, 即ebp的切换, ebp是栈底指针, 它确定了当前用户空间属于哪个进程

    2.5 need_resched, TIF_NEED_RESCHED标识与用户抢占


    2.5.1 need_resched标识TIF_NEED_RESCHED


    内核在即将返回用户空间时检查进程是否需要重新调度,如果设置了,就会发生调度, 这被称为用户抢占, 因此内核在thread_info的flag中设置了一个标识来标志进程是否需要重新调度, 即重新调度need_resched标识TIF_NEED_RESCHED

    并提供了一些设置可检测的函数

    函数描述定义
    set_tsk_need_resched设置指定进程中的need_resched标志include/linux/sched.h, L2920
    clear_tsk_need_resched清除指定进程中的need_resched标志include/linux/sched.h, L2926
    test_tsk_need_resched检查指定进程need_resched标志include/linux/sched.h, L2931

    而我们内核中调度时常用的need_resched()函数检查进程是否需要被重新调度其实就是通过test_tsk_need_resched实现的, 其定义如下所示

    // http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L3093
    static __always_inline bool need_resched(void)
    {
        return unlikely(tif_need_resched());
    }
    
    // http://lxr.free-electrons.com/source/include/linux/thread_info.h?v=4.6#L106
    #define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)

    2.5.2 用户抢占和内核抢占


    当内核即将返回用户空间时, 内核会检查need_resched是否设置,如果设置,则调用schedule(),此时,发生用户抢占。

    一般来说,用户抢占发生几下情况

    1. 从系统调用返回用户空间

    2. 从中断(异常)处理程序返回用户空间

    当kerne(系统调用或者中断都在kernel中)l返回用户态时,系统可以安全的执行当前的任务,或者切换到另外一个任务.

    当中断处理例程或者系统调用完成后, kernel返回用户态时, need_resched标志的值会被检查, 假如它为1, 调度器会选择一个新的任务并执行. 中断和系统调用的返回路径(return path)的实现在entry.S中(entry.S不仅包括kernel entry code,也包括kernel exit code)。

    抢占时伴随着schedule()的执行, 因此内核提供了一个TIF_NEED_RESCHED标志来表明是否要用schedule()调度一次

    根据抢占发生的时机分为用户抢占和内核抢占。

    用户抢占发生在内核即将返回到用户空间的时候。内核抢占发生在返回内核空间的时候。

    抢占类型描述抢占发生时机
    用户抢占内核在即将返回用户空间时检查进程是否设置了TIF_NEED_RESCHED标志,如果设置了,就会发生用户抢占.从系统调用或中断处理程序返回用户空间的时候
    内核抢占在不支持内核抢占的内核中,内核进程如果自己不主动停止,就会一直的运行下去。无法响应实时进程. 抢占内核虽然牺牲了上下文切换的开销, 但获得 了更大的吞吐量和响应时间

    2.6的内核添加了内核抢占,同时为了某些地方不被抢占,又添加了自旋锁. 在进程的thread_info结构中添加了preempt_count该数值为0,当进程使用一个自旋锁时就加1,释放一个自旋锁时就减1. 为0时表示内核可以抢占.
    从中断处理程序返回内核空间时,内核会检查preempt_count和TIF_NEED_RESCHED标志,如果进程设置了 TIF_NEED_RESCHED标志,并且preempt_count为0,发生内核抢占

    2. 当内核再次用于可抢占性的时候,当进程所有的自旋锁都释 放了,释放程序会检查TIF_NEED_RESCHED标志,如果设置了就会调用schedule

    3. 显示调用schedule时

    4. 内核中的进程被堵塞的时候

    3 总结


    3.1 schedule调度流程

    schedule就是主调度器的函数, 在内核中的许多地方, 如果要将CPU分配给与当前活动进程不同的另一个进程, 都会直接调用主调度器函数schedule, 该函数定义在kernel/sched/core.c, L3243, 如下所示

    该函数完成如下工作

    1. 确定当前就绪队列, 并在保存一个指向当前(仍然)活动进程的task_struct指针

    2. 检查死锁, 关闭内核抢占后调用__schedule完成内核调度

    3. 恢复内核抢占, 然后检查当前进程是否设置了重调度标志TLF_NEDD_RESCHED, 如果该进程被其他进程设置了TIF_NEED_RESCHED标志, 则函数重新执行进行调度

        do {
            preempt_disable();                                  /*  关闭内核抢占  */
            __schedule(false);                                  /*  完成调度  */
            sched_preempt_enable_no_resched();                  /*  开启内核抢占  */
        } while (need_resched());   /*  如果该进程被其他进程设置了TIF_NEED_RESCHED标志,则函数重新执行进行调度    */

    3.2 __schedule如何完成内核抢占

    1. 完成一些必要的检查, 并设置进程状态, 处理进程所在的就绪队列

    2. 调度全局的pick_next_task选择抢占的进程

      • 如果当前cpu上所有的进程都是cfs调度的普通非实时进程, 则直接用cfs调度, 如果无程序可调度则调度idle进程

      • 否则从优先级最高的调度器类sched_class_highest(目前是stop_sched_class)开始依次遍历所有调度器类的pick_next_task函数, 选择最优的那个进程执行

    3. context_switch完成进程上下文切换

      • 调用switch_mm(), 把虚拟内存从一个进程映射切换到新进程中

      • 调用switch_to(),从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息

    3.3 调度的内核抢占和用户抢占

    内核在完成调度的过程中总是先关闭内核抢占, 等待内核完成调度的工作后, 再把内核抢占开启, 如果在内核完成调度器过程中, 这时候如果发生了内核抢占, 我们的调度会被中断, 而调度却还没有完成, 这样会丢失我们调度的信息.

    而同样我们可以看到, 在调度完成后, 内核会去判断need_resched条件, 如果这个时候为真, 内核会重新进程一次调度, 此次调度由于发生在内核态因此仍然是一次内核抢占

    need_resched条件其实是判断need_resched标识TIF_NEED_RESCHED的值, 内核在thread_info的flag中设置了一个标识来标志进程是否需要重新调度, 即重新调度need_resched标识TIF_NEED_RESCHED, 内核在即将返回用户空间时会检查标识TIF_NEED_RESCHED标志进程是否需要重新调度,如果设置了,就会发生调度, 这被称为用户抢占,

    而内核抢占是通过自旋锁preempt_count实现的, 同样当内核可以进行内核抢占的时候(比如从中断处理程序返回内核空间或内核中的进程被堵塞的时候),内核会检查preempt_count和TIF_NEED_RESCHED标志,如果进程设置了 TIF_NEED_RESCHED标志,并且preempt_count为0,发生内核抢占

    展开全文
  • Linux内核之核心调度器

    千次阅读 2017-04-03 13:56:18
    在Linux中内核提供了两个调度器调度器,周期性调度器调度器是直接的, 比如进程打算睡眠或出于其他原因放弃CPU,schedule函数 周期性调度器是通过周期性的机制, 以固定的频率运行, 不时的检测是否有必要,...
  • [进程管理] linux核心调度器

    千次阅读 2011-12-27 23:37:03
    linux核心调度器主要基于两个函数实现:周期性调度器函数和主调度器函数。这些函数会根据现有进程的优先级分配CPU时间,所以也称“优先调度”  一、周期性调度器  周期性调度器是在函数scheduler_tick(void),如果...
  • 调度子系统2_核心调度器

    千次阅读 2013-12-10 20:04:09
    // 核心调度器 // 当进程决定让出cpu时调用 // 函数任务: // 1.禁止内核抢占 // 2.获取本cpu的rq // 3.取消为当前进程运行的hrtimer // 4.获取队列锁 // 5.更新队列时钟 // 6.清除当前进程need resched标志 ...
  • linux进程管理 - 核心调度器

    千次阅读 2013-07-31 16:19:41
    linux内核进程调度器基于两个函数:周期性调度器函数和主调度器函数. 周期性调度器 所谓周期性调度器就是scheduler_tick中实现。如果系统正在活动中,内核会按照HZ自动调用这个函数。实际上在每个滴答的handler中会...
  • kubernetes调度器之前已经分析过SchedulerCache、ScheduleAlgorithm、SchedulerExtender、Framework等核心数据结构,也分析了优选、调度、抢占流程的核心实现,本文是本系列目前打算的最后一章, 也是当前阶段对调度...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 264,246
精华内容 105,698
关键字:

核心调度器