Linux 调度器之CFS的buddy

//fair.c 
struct cfs_rq { 
    ... 
    struct sched_entity    *next; //和last差不多，只不过优先级没有next高 
    struct sched_entity    *last; //优先调度 
    struct sched_entity    *skip; //用于跳过一些任务 
    ... 
};

static void set_next_buddy(struct sched_entity *se) 
{ 
    ... 
    cfs_rq_of(se)->next = se; 
    ... 
} 
static void set_last_buddy(struct sched_entity *se) 
{ 
    ... 
    cfs_rq_of(se)->last = se; 
    ... 
} 
static void set_skip_buddy(struct sched_entity *se) 
{ 
    ... 
    cfs_rq_of(se)->skip = se; 
    ... 
} 
 
static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se) 
{ 
    ... 
    if (cfs_rq->last == se) 
        cfs_rq_of(se)->last = NULL; 
    if (cfs_rq->next == se) 
        cfs_rq_of(se)->next = NULL; 
    if (cfs_rq->skip == se) 
        cfs_rq_of(se)->skip = NULL; 
    ... 
}

static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) //fair.c 
{ 
    struct cfs_rq *cfs_rq; 
    struct sched_entity *se = &p->se; 
    int task_sleep = flags & DEQUEUE_SLEEP; 
    se = parent_entity(se); //没有使能组调度，这里返回NULL 
    ... 
    /*若没有开启对CFS的带宽控制的话，传参flags中有 DEQUEUE_SLEEP 标志就会设置，若没有使能CFS组调度，恒不会设置*/ 
    if (task_sleep && se && !throttled_hierarchy(cfs_rq)) 
        set_next_buddy(se); 
    ... 
}

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) //fair.c 
{ 
    struct sched_entity *se = &curr->se, *pse = &p->se; 
    struct cfs_rq *cfs_rq = task_cfs_rq(curr); //因为有组调度，这个和rq->cfs还不一定是同一个 
    int scale = cfs_rq->nr_running >= sched_nr_latency; //8个runnable的线程 
    int next_buddy_marked = 0; 
 
    ... 
    /* 如果开启了 NEXT_BUDDY feature，且此cfs_rq上有超过8个线程待运行，且不是fork线程后进行唤醒的，则将新换新的进程设置到next buddy 
    fork系统调用 -> _do_fork -> wake_up_new_task -> check_preempt_curr(rq, p, WF_FORK); 
    */ 
    if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) { 
        set_next_buddy(pse); 
        next_buddy_marked = 1; 
    } 
    ... 
　　/*当前任务的虚拟时间减去任务p的虚拟时间大于抢占阈值，就将任务p设置为next_buddy，以便在 pick_next_entity 时抢占当前线程*/ 
    if (wakeup_preempt_entity(se, pse) == 1) { //1.当前进程的虚拟时间比新进程多运行2ms在新进程上对应的虚拟时间 
        /* Bias pick_next to pick the sched entity that is triggering this preemption.*/ 
        //和前面的设置是互斥的 
        if (!next_buddy_marked) 
            set_next_buddy(pse); 
        goto preempt; //2.触发抢占 
    } 
    ... 
preempt: 
    /* 设置 TIF_NEED_RESCHED 标志，在下一个抢占点到来时进行抢占 */ 
    resched_curr(rq); 
 
    ... 
 
    //LAST_BUDDY默认设置的 
    //函数的最后，此cfs_rq上有大于8个runnable的任务且是任务(非任务组)，要被强占的当前任务被设置为 last_buffy 
    if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se)) 
        set_last_buddy(se); 
}

static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preempt) 
{ 
    struct sched_entity *se = &p->se; 
    set_next_buddy(se); 
    ... 
}

static struct sched_entity * pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr) 
{ 
    struct sched_entity *left = __pick_first_entity(cfs_rq); 
    struct sched_entity *se; 
 
    /*若cfs_rq上没有ready的任务，或则curr的虚拟时间比rbtree最左侧的还小*/ 
    if (!left || (curr && entity_before(curr, left))) 
        left = curr; 
 
    se = left; /* ideally we run the leftmost entity */ 
 
    /* Avoid running the skip buddy, if running something else can be done without getting too unfair. */ 
    /* 如果有其它可运行的，就避免运行这个skip buddy */ 
    if (cfs_rq->skip == se) { 
        struct sched_entity *second; 
        if (se == curr) { 
            second = __pick_first_entity(cfs_rq); //重新选一个来运行 
        } else { 
            second = __pick_next_entity(se); // se是最左侧的，这里选第二左的 
            /* 如果虚拟时间第二小的不存在 或 curr比选出来的这个虚拟时间还小，那么继续选curr */ 
            if (!second || (curr && entity_before(curr, second))) 
                second = curr; 
        } 
 
        /* 只有当选出来的second的虚拟时间比left还小2ms对应的虚拟时间以上，才取second*/ 
        if (second && wakeup_preempt_entity(second, left) < 1) 
            se = second; 
    } 
 
    /* 
     * Prefer last buddy, try to return the CPU to a preempted task. 
     */ 
    /* 若是cfs_rq->last也比left的虚拟时间也小这么多，优先选cfs_rq->last。也就是看能否选被强占的当前任务 */ 
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) 
        se = cfs_rq->last; 
 
    /* 
     * Someone really wants this to run. If it's not unfair, run it. 
     */ 
    /* 若是next的虚拟时间比rbtree最左侧的的任务还小，那么就选next，这个是最高优先级。也就是看能否选抢占当前任务的任务运行 */ 
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) 
        se = cfs_rq->next;  //这里选择了next_buddy 
 
    /*将此se从cfs_rq中清理掉，无论是否选择它，都将其清理掉，因此一次设置只起一次作用*/ 
    clear_buddies(cfs_rq, se); 
 
    return se; 
}

static int task_hot(struct task_struct *p, struct lb_env *env) 
{ 
    s64 delta; 
    ... 
    /* 
     * Buddy candidates are cache hot: 
     */ 
    /* CACHE_HOT_BUDDY默认为true */ 
    if (sched_feat(CACHE_HOT_BUDDY) && env->dst_rq->nr_running && 
            (&p->se == cfs_rq_of(&p->se)->next || &p->se == cfs_rq_of(&p->se)->last)) 
        return 1; 
 
    //默认0.5ms 
    if (sysctl_sched_migration_cost == -1) 
        return 1; 
    if (sysctl_sched_migration_cost == 0) 
        return 0; 
 
    //上次开始运行到现在的时间差值小于0.5ms就认为还是task_hot的，返回真 
    delta = rq_clock_task(env->src_rq) - p->se.exec_start; 
    //若delta小于，那就返回1,否则返回0 
    return delta < (s64)sysctl_sched_migration_cost; 
}

static void yield_task_fair(struct rq *rq) 
{ 
    struct sched_entity *se = &curr->se; 
    ... 
    set_skip_buddy(se); 
}