1. 概述

主要视角是, 考虑要多久才能轮到某个进程的运行, (称之为targeted preemption latency) 而不是每个进程分配多少份的时间片.

对单个进程 达到 时间段t1内被至少调度一次到, 对所有的进程都达到的话, 就是, 时间段t1内所有进程都跑一遍. the interval during which every runnable task should run at least once. 这个时间段t1我们成为 one latency period.

本文仅讨论SCHEDNORMAL. 且没有使能CONFIGFAIRGROUPSCHED. 内核版本3.10.

2. 时间的计算

等了多久, 具体如何量化?
每次计算时间, 若是逐个给每个TASK_RUNNING进程计算, 这样势必低效, 所以, 实现上, 不应该是逐个进程判断等待的时间.
当前的实现是, 记录各进程运行所占用的时间, 运行占用时间的另一面, 就是 没有运行. 一个进程运行时间久, 其他进程没有运行或者等待的时间就久. 故可以仅记录运行时间来反应等待时间, 这个运行的时间记为vruntime.

2.1 vruntime

virtual run time, 运行时间经加权后的数据, 加权方法为

updatecurr -> _updatecurr -> calcdelta_fair

如何处理overflow问题? ...

2.2 何时统计

统计已使用的时间, 由update_curr()完成. 调用路径有:

1. 最常见的是周期性的时钟中断, schedulertick -> curr->schedclass->tasktick(...); => tasktickfair -> entitytick -> update_curr
2. 其他的本文不讨论.

3. 策略/机制

3.1 分配多少合适

若分配的太少, 则频繁上下文切换, 引起不必要overhead, 故给每个进程运行的时间不宜太短, 所以, 定义了sysctl_sched_min_granularity, 这样, 想要在sysctl_sched_latency内被调度一遍的话, 那么 想要运行的进程的量 <= sched_nr_latency. >= sysctl_sched_latency的话, sysctl_sched_latency这个延迟就无法保证.

所以, 如果系统有nrrunning个进程, 那么, 每个进程分配到的时间为: sysctlschedlatency × nrrunning/schednrlatency

实际计算时, 还要结合优先级, 代码在 sched_slice()

timeslices in CFS are of variable length.

3.2 何时轮到下一个

如何知道 进程运行得差不多了, 该轮到下一个进程了?

scheduler_tick
|--curr->sched_class->task_tick(...);  => task_tick_fair
|   |--entity_tick
|   |   |--update_curr
|   |   |--check_preempt_tick
|   |   |   |-- if (delta_exec > ideal_runtime) resched_task

​这里没有看到不让运行.
linux-3.10.86/kernel/sched/core.c __schedule()上方的注释, 调用__schedule的时机包括

• return from syscall or exception to user-space
• ...略, 不讨论...

linux-3.10.86/arch/arm/kernel/entry-common.S

ENTRY(ret_to_user)
ret_slow_syscall:
    disable_irq             @ disable interrupts
ENTRY(ret_to_user_from_irq)
    @entry-header.S中  tsk .req    r9      @ current thread_info
    ldr r1, [tsk, #TI_FLAGS]
    @#define _TIF_WORK_MASK     (_TIF_NEED_RESCHED | _TIF_SIGPENDING | _TIF_NOTIFY_RESUME)
    tst r1, #_TIF_WORK_MASK
    bne work_pending


work_pending:
    mov r0, sp              @ 'regs'
    mov r2, why             @ 'syscall'
    bl  do_work_pending

linux-3.10.86/arch/arm/kernel/signal.c

do_work_pending
{
    if (likely(thread_flags & _TIF_NEED_RESCHED)) {
        schedule();
    }
    ...
}

linux-3.10.86/kernel/sched/core.c

__schedule
{

    if (prev->state && ...){  //不满足

    }

    put_prev_task
    pick_next_task
    clear_tsk_need_resched
    context_switch
}

这里挑选其他进程, 然后启动之.

4 数据结构

Each CPU has its own run queue (struct rq).

正在运行的进程 并不在红黑树上:
see _schedule -> picknexttask -> picknexttaskfair -> setnextentity -> _dequeueentity

何处调整 树上node的位置?
答:在重新放入红黑树时调整位置, 重新放回红黑树是为了后续被调度到: putprevtask -> putprevtaskfair -> putpreventity -> if (prev->onrq) _enqueueentity

这样处理的优点:
运行的进程并不在树上, 这样 update_curr时, 也就不必调整在树上的位置.

本文地址: https://awakening-fong.github.io/posts/scheduler/scheduler_00_implementation

转载请注明出处: https://awakening-fong.github.io