Linux内核进程管理实时调度与SMP

一，实时调度器类

实时调度类有两类进程：

循环进程SCHED_RR：循环进程有时间片，随着进程的运行时间会减少。当时间片用完时又将其置为初值，并将进程置于队列末尾。先进先出SCHED_FIFO：没有时间片调度，运行后可执行任意长时间直到自己放弃CPU。实际上两类进程在相同优先级队列上都是先进先出的，只是一个有时间片一个没有时间片。

现在实时进程的调度其实就是使用之前内核的O(1)，每个优先级（总共MAX_RT_PRIO）有一个queue，并且通过一个bitmap（位数也是MAX_RT_PRIO+1）表示所有优先级队列的状态，即bitmap的第0位，表示优先级queue[0]是否有等待运行的进程，0表示没有，1表示有，所以每次调度的时候总是查找bitmap第一个非0的位，然后取出它的queue的head，它就是这次调度获得的进程。下面我们简单的解释一下，实时调度器类的周期性调度器，主调度器。

它对应的实时周期性调度器对应函数为task_tick_rt，首先更新当前进程的执行时间，检查是不是FIFO进程，如果是的话直接返回，否则是RR进程，那么就把它的时间片减1，并判断是否为0，如果不为0则直接返回，否则就重新分配时间片，并把它放到它的优先级队列的队尾，然后设置TIF_NEED_RESCHED标志。

大多数逻辑如enqueue_task_rt，dequeue_task_rt，put_prev_task_rt跟CFS差不多，只是所操作的队列不一样了（实时类只需以p->prio为索引访问queue[p->prio]），另外需要注意的就两个：pick_next_task_rt（该过程我们上面也解释了，通过bitmap及queue获得），check_preempt_curr_rt（判断是否该preempt对于实时进程唯一有效的就是优先级，显然新的进程比当前的优先级高的话，那么它就可以抢占，否则如果相等的话则因为SMP，所以有这个当前进程可能会被迁移到其它进程，具体条件当前进程可运行的cpu!=1，新进程可运行cpu==1,当前进程找到其它可用的cpu，只有这几个条件都满足了才可以让当前的进程让同等优先级的进程抢占，但它带来的开销也是很大的）

注：其实实时进程也是有组调度的，这里我们不再去分析它，并且不管CFS还是RT它们都可以对队列进行throttled的特性，这里我们也没有去分析。

二，SMP

下面我们简单介绍一下SMP的主要过程：框架周期性调度器在执行完上面所说的过程后会调用trigger_load_balance触发个SCHEDULE_SOFTIRQ软中断，该中断确保会在适当的时机执行run_rebalance_domains。该函数最终对当前CPU调用rebalance_domains判断该CPU下的每个调度域是否需要balance，如果需要最终将调用load_balance来实现负载均衡；另外内核为每个就绪队列提供一个迁移线程，用来接收迁移请求，这些请求被保存在migration_queue链表中。

load_balance函数首先查找CPU（进入这个过程的CPU已经是CPU_IDLE）所属调度域内最忙的（CPU）运行队列，然后使用move_tasks将该队列（最忙）中适当数目的进程迁移到当前CPU的运行队列里，最终move_tasks调用特定调度器类的load_balance方法。

下面两种进程在load_balance里无法完成：

• A. 进程由于亲缘性不能在当前CPU下运行
• B. 进程正在运行（成本太大）

当load_balance失败的时候（没有完成一个进程的balance），会设置最忙运行队列的active_balance及它将要迁移的目标CPU（当前CPU），然后唤醒最忙CPU的迁移线程wake_up_process(busiest->migration_thread)，那么此时最忙CPU运行的就是这个迁移线程（之前的线程不再运行），所以之前的线程现在就有可能会被迁移到目标CPU；最忙CPU运行迁移线程，当它检查到rq->active_balance则调用active_load_balance，最终分别调用特定调度器类的move_one_task函数（该函数完成的过程会比load_balance更激烈的方法，如不考虑优先级）。

调度域：多个就绪队列（CPU）组织为一个调度域，将物理上邻近或共享高速缓存的CPU群集起来，它是负载均衡的单位，在balance时应优先选择在同一个调度域内的CPU之间的迁移

在CPU（逻辑CPU）间的迁移优先（这也关系到调度域的组织）：同一个core（L1,L2），同一个物理CPU（L3），同一个NUMA节点。我们的开发机器是2个物理CPU，每个物理CPU内有4个core，每个core又虚拟出2个超线程，所以我们看到的16个CPU，其实是16个超线程，一般的NUMA初始设置是把同一个物理CPU的放在同一个NUMA节点内。这些信息可以从/proc/cpuinfo查看：processor（表示逻辑cpu，也就是超线程）；physical id（表示物理CPU ID）；core id（表示一个物理CPU内的core id，不同CPU间的core id可能一样）；siblings（表示）一个物理CPU上的超线程数；cpu cores（表示一个物理CPU的core数）