RTLinux进程调度策略总结

实时调度策略介绍

实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，普通分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。实时任务按照可抢占优先级调度算法进行，就绪态的实时任务可以立即抢占非实时任务。

1，SCHED_FIFO：First Input First Output，优先级范围1-99（最大）

SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。

如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。

2，SCHED_RR：基于FIFO基础上的Round Robin时间片轮转，先入先出当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。将进程放在队列尾保证了所有具有相同优先级的RR任务的调度公平。

3，SCHED_DEADLINE：该调度策略采用Global Earliest Deadline First(GEDF)算法，最早要到期的任务将被以最高优先级调度和分配CPU。根据此策略调度的任务可以抢占使用SCED FIFO、SCED RR或非实时调度的任何任务。参考https://lwn.net/Articles/743740/和https://blog.csdn.net/zhuyong006/article/details/80980502

https://blog.csdn.net/xiaofeng_yan/article/details/48246101

        调度参数（ns纳秒单位）：

        runtime：任务需要CPU执行的时长，要考虑最坏/最慢情况下的最大时长，要小于deadline

        period：任务执行的周期，即两次任务开始的时间间隔

        deadline：任务必须在该时长内执行完，不大于period，是从period开始时刻计算时长

调度算法介绍

所有任务都采用Linux分时调度策略时:

Linux采用CFS（Completely Fair Scheduler）完全公平调度算法实现分时进程的CPU资源分配，注意    ：非实时线程priority（100-139）由内核动态调控，不能人为设置，可以用修改nice值（-20~19 越低的值越高的优先级，这个在计算虚拟时间的时候放在分母上），从而间接影响优先级，PRI(new) = PRI(old) + nice

1）创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。

2）将根据每个任务的nice值确定在cpu上的执行时间(counter)。

3）如果没有等待资源，则将该任务加入到就绪队列中。

4）调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择

计算结果最大的一个去运行，当这 个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在

就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。

5）此时调度程序重复上面计算过程，转到第4步。

6）当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。

所有任务都采用FIFO的调度策略时：

1）创建进程时指定采用FIFO，并设置实时优先级rt_priority(1-99)。

2）如果没有等待资源，则将该任务加入到就绪队列中。

3）调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu，该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。

4）调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒，再或被当前运行的任务唤醒，等等)，则调度程序立即在当前任务 堆栈中保存当前cpu寄存器的所有数据，重新从高优先级任务的堆栈中加载寄存器数据到cpu，此时高优先级的任务开始运行。重复第3步。

5）如果当前任务因等待资源而主动放弃cpu使用权，则该任务将从就绪队列中删除，加入等待队列，此时重复第3步。

所有任务都采用RR调度策略（轮转法调度）时：

1）创建任务时指定调度参数为RR，并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。

2）如果没有等待资源，则将该任务加入到就绪队列中。

3）调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu。,

4）如果就绪队列中的RR任务时间片为0（RR时间片是100ms），则会根据nice值设置该任务的时间片，同时将该任务放入就绪5队列的末尾。重复步骤3。

5）当前任务由于等待资源而主动退出cpu，则其加入等待队列中。重复步骤3。

所有任务都采用SCHED_DEADLINE调度策略时：

该调度策略在目前的 Linux 内核里面属于优先级最高的调度类，也就是说假设系统上面存在多个调度类，那么每次重新调度的时候，都是先从该调度类下面去找到一个可以投入运行的进程进行调度。归属于该调度类的进程其归一化优先级都是 -1，在该调度类内部不再区分多个优先级，统一归为 -1.

1）创建任务时指定调度参数为DEADLINE，设定runtime、period、deadline参数。

2）如果没有等待资源，则将该任务加入到就绪队列中。

3）调度程序遍历就绪列表，根据deadline到期时间，选择最短的任务执行

4）执行最长时间片由runtime指定，过时没有执行完也会被收回CPU资源

5）将任务加入到就绪队列中，重复步骤3

系统中既有分时调度，又有实时RR时间片轮转调度、FIFO先进先出调度和DEADLINE调度：

1）调度系统首先查看是否有DEADLINE任务将要到期，如有则会抢占CPU资源执行DEADLINE任务，即使当前CPU正在执行FIFO或RR任务。

2）RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。

3）当实时进程准备就绪后，如果当前cpu正在运行非实时进程，则实时进程立即抢占非实时进程。

    普通进程完全捞不到CPU资源也不完全对，后来LINUX增加组调度策略后，有/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runtime_us两个参数，这两个参数表示的含义是：在sched_rt_peroid_us的周期内，所有的实时进程运行时间之和不得超过sched_rt_runtime_us。 默认值为1秒和0.95秒换句话说，在1秒的周期以内，所有实时进程运行时间之和不得超过0.95秒，剩下的0.5秒钟留给普通进程。

3）RR进程和FIFO进程都采用实时优先级做为调度的权值标准，RR是FIFO的一个延伸。FIFO时，如果两个进程的优先级一样，则这两个优先级一样的进程具体执行哪一个是由其在队列中的未知决定的，这样导致一些不公正性,如果将两个优先级一样的任务的调度策略都设为RR,则保证了这两个任务可以循环执行，保证了公平。