天河网站建设多少钱,王占军,微信群发布网站建设,云开发网站一、概述决定何时、如何选择一个新进程运行的这组规则叫做#xff1a;调度策略(scheduling policy)。Linux的调度是基于分时技术(time sharing)#xff1a;多个进程以“时间多路复用”方式运行#xff0c;因为CPU的时间呗分成“片”(slice)#xff0c;给每个可运行进程分配…一、概述决定何时、如何选择一个新进程运行的这组规则叫做调度策略(scheduling policy)。Linux的调度是基于分时技术(time sharing)多个进程以“时间多路复用”方式运行因为CPU的时间呗分成“片”(slice)给每个可运行进程分配一片。如果当前运行进程的时间片或时限(quantum)到期时该进程还没有运行完毕进程切换就会发生。调度策略也是根据进程的优先级对它们进行分类。在Linux中进程优先级是动态的在较长时间内没有运行的进程会动态提升它们的优先级相反地对于在CPU上运行较长时间的进程会降低它们的优先级来惩罚它们。所以实现调度的工具是调度器(scheduler)调度的对象是进程(process)调度的方法是调度策略(包括调度算法)。二、CPU调度器这里主要讲了cpu调度器的工作内容和目的多个task会共享CPU资源那如何进行任务切换选择呢当前运行的task中止当前运行的task sleep(wait event)新task创建或者sleep的task唤醒了当前运行的task的时间片用完那调度器的目标是什么公平调度各个task基于task的优先级来分配时间片task的respnse时间短高throughput(task执行成功)在多个cpu间负载均衡低功耗调度器代码运行开销低调度器会和工作在一些框架、服务器、PC、嵌入式/手机中。三、O(1)调度器在2.6.23(2007)以前Linux调度器使用的是O(1)调度器调度器分140个优先级等级0-99是RT task100-139是User task每个cpu的runqueue有2个数组ActiveExpaired每个数组都有140个entry对应每个优先级每个entry是一条FIFO队列结构的链表140位的bitmap用来检测每个优先级list时间片会根据task的优先级进行分配运行时间expaire的task会从Active数组移动到Expaired数组当Active数组为空时就交换2个数组。即将Expaired数组变为ActiveActive(此时为空)变为Expairedtask的入rq和出rq以及next task的选择都是在固定时间内完成最后在O(1)调度器已经被CFS替代。四、当前调度器架构在kernel 2.6.23(2007)后由Ingo Molnar引入在调度的class中还存在调度policy不同的调度class高优先级的越早执行task可以在cpu、调度policy、调度class间进行迁移4.1 调度class由struce sched_class结构体实现structsched_class {const struct sched_class *next;void (*enqueue_task) (struct rq *rq, struct task_struct *p, intflags);void (*dequeue_task) (struct rq *rq, struct task_struct *p, intflags);...struct task_struct * (*pick_next_task) (struct rq *rq, struct task_struct *prev, struct rq_flags *rf);...};内核中一共有5中调度class优先级从高到低STOP DL RT CFS IDLE他们通过链表实现并链接起来的。4.2 主调度函数Schedule()内核中进程调度最主要的实现是Schedule()函数。它完成如下工作选取下一个runnable的task并将task放在cpu上运行按class优先级搜索task来运行最先从STOP class开始轮询搜索for_each_class()实现方式pick_next_task()again:for_each_class(class) {p class-pick_next_task(rq, prev, rf);if(p) {if (unlikely(p RETRY_TASK))gotoagain;returnp;}}/*The idle class should always have a runnable task:*/BUG();4.3 调度class与policy在不同的调度class下可能会有不同的调度policy实现● Stop○ No policy● Deadline○ SCHED_DEADLINE● Real Time○ SCHED_FIFO○ SCHED_RR● Fair○ SCHED_NORMAL○ SCHED_BATCH○ SCHED_IDLE● Idle○ No policy不同的class代表不同的调度优先级不同的policy同样也意味着不同的调度方式。4.4 调度classSTOPSTOP类型的class有如下特点是最高优先级的class(但是这个class不开放给系统user使用的)只能在smp系统上可用(stop_machine()在单核处理器下不可用)------括号内的具体没怎么理解可以抢占所有task并任何事件都不能抢占它实现方式是停止运行的其他所有task而在cpu上运行一个特定的函数没有调度policy属于stop class的per cpu内核线程migration/N ------“N”为cpu core number在以下情况下使用task迁移、CPU hotplug、RCU、ftrace、cloclevents等4.5 调度classDeadline(DL)Deadline类型的class有如下特点在kernel 3.14(2013)由Dario Faggioli Juri Lelli引入在系统中属于可以使用的最高优先级的class调度policy为SCHED_DEADLINE由红黑树结构实现(自平衡树)在以下情况下使用周期性的实时task例如视频编解码4.6 调度Real-time(RT)Real-time类型的class有如下特点符合POSIX标准要求task优先级范围0-99优先级在kernel和userspace中相反0在kernel中代表最高优先级而在userspace中代表最低优先级相同优先级下的调度policySCHED_FIFOSCHED_RR默认时间片长度为100ms由链表实现在以下情况下使用latency敏感的task例如IRQ threads4.7 调度CFS(Completely Fair Scheduler)CFS类型的class有如下特点由Ingo Molnar引入调度policySCHED_NORMAL普通taskSCHED_BATCH批处理 task(batch task非交互型)SCHED_IDLE低优先级task由红黑树结构实现跟踪task的虚拟运行时间(vruntimetask拥有的运行时间)虚拟运行时间(vruntime)最短的task最优先运行task的优先级作为权重会影响虚拟运行时间的计算(vruntime)权重越大虚拟运行时间(vruntime)计算时的增量就越小task的优先级计算120nice值(nice范围-20 ~ 19)用于所有其他类型的task例如shell4.7 调度IdleIdle类型的class有如下特点最低优先级的调度class没有调度policy属于idle class的per cpu内核线程(idle)swapper/N ------“N”为cpu core numberidle线程仅会在没有其他task的情况下在cpu上运行idle线程可以让cpu进入低功耗状态五、Runqueue每个CPU都由一个struct rq的实例每个”rq“包含了DL、RT、CFS的runqueueRunnable的task会被压入上面提到的那些runqueue中在struct rq中由很多其他的信息和状态structrq {...structcfs_rq cfs;structrt_rq rt;structdl_rq dl;...}
