Linux内核-进程调度

１.多任务

＃抢占式多任务：由调度程序来决定什么时间停止一个进程的运行

＃进程的时间片：分配给每个可运行进程的处理器时间段

２.Linux的进程调度

＃O(1)调度程序

＃反转楼梯最后期限调度算法（ＲＳＤＬ）

＃完全公平调度算法（ＣＦＳ）

３.策略

＃I/O消耗型和处理器消耗型进程：

    I/O消耗型进程：大部分时间用来提交I/O请求或等待I/O请求

    处理器消耗型进程：把时间大部分用在执行代码上。

                                 调度策略往往降低他们的调度频率，延长执行时间

＃调度策略往往要在两个矛盾中寻找平衡：

    进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）

# 进程优先级

        基于优先级的调度：根据进程的价值和对处理器时间的需求来对进程分级的想法

        调度程序总是选择时间片未用尽而且优先级高的进程先进行

#时间片：它表明进程在被抢占前所能持续运行的时间

        *任何长时间片都将导致系统交互表现欠佳

4.Linux调度算法

#调度器类：Linux调度器以模块形式提供，允许不同类型的进程选择不同的调度算法

#公平调度（CFS）：CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程

    *CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片

#最小粒度：每个进程获得的时间片底线

5.Linux调度的实现

#时间记账：所有的调度器都必须对进程运行时间进行记账

    1.时间记账：

        #调度器实体结构：CFS没有时间片的概念，但是它必须维护每个进程运行的时间记账，为了每个进程只在公平分配的处理器时间内运行

                    *调度器实体结构嵌入在进程描述符内

    2.虚拟实时：

        *vruntime变量存放进程的虚拟运行时间，该时间的计算是经过了所有可运行进程总数的标准化

        *CSF使用vruntime来记录一个程序运行了多长时间和它还应该运行多久

#进程选择：当CSF需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程

    1.挑选下一个任务：由函数_pick_next_entity()实现：

            *运行rbtree树中最左边叶子节点代表的那个进程

            *函数的返回值CFS调度选择的下一个运行进程，如果返回NULL，表示没有可运行进程，CFS调度器选择idle任务运行

    2.向树中加入进程：发生在进程变为可运行状态或者通过fork()调用第一次创建进程时

            *由enqueue_entity()实现，更新运行时间和一些统计数据，然后进行插入操作，把数据插入红黑树中

             最后rb_insert_color()更新树的自平衡相关属性

    3.从树中删除进程：发生在进程阻塞或者终止时

            *由辅助函数_dequeue_entity()完成

#调度器入口：schedule()函数，用于选择哪个进程可以运行，何时将其投入运行

    *调用pick_next_task()，会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程

#睡眠和唤醒：

    睡眠：进程把自己标记为休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程

    唤醒：进程被设置为可执行状态，从等待队列移回可执行红黑树

    1.等待队列：等待某些时间发生的进程组成的简单链表

        *休眠通过等待队列进行处理

        *内核用wake_queue_head_t来表示等待队列，可以通过DECLARE_WAITQUEUE()静态创建或init_waitqueue_head()动态创建

        过程：

            1.调用宏DEFINE_WAIT()创建一个等待队列的项

            2.调用add_wait_queue()把自己加入到队列中

            3.调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或者TASK_UNINTERRUPTIBLE

            4.如果状态被设置为TASK_INTERRUPTIBLE则信号唤醒进程（伪唤醒）

            5.当进程被唤醒时，它会检查条件是否为真，如果是，则退出循环，再次调用调用schedule()并重复

            6.当条件满足后，进程将自己设置为TASK_RUNNING，并调用finish_wait()移出等待队列

    2.唤醒：通过wake_up()函数，它会唤醒指定等待队列上的所有进程，它调用try_to_wake_up()，该函数将进程设置为TASK_RUNNING，调用enqueue_task()将此进程放入红黑树中。

            *如果被唤醒的进程优先级比当前正在执行的进程优先级高，需要设置need_resched标志

6.抢占和上下文切换：

         上下文切换就是从一个可执行进程切换到另一个可执行进程，由context_switch()负责处理

        *它完成了两项基本工作：

            1.调用swtich_mm()，把虚拟内存从上一个进程映射到新进程

            2.调用swtich_to(),从上一个进程的处理器状态切换到新进程的处理器状态（保存、恢复栈信息和寄存器信息等）

#用户抢占：在以下情况时发生：

                        1.从系统调用返回用户空间时

                        2.从终端处理程序返回用户空间时

#内核抢占：

    如何实现：为每个进程的thread_info引入preempt_count计数器。初始值为0，使用锁的时候+1，释放锁的时候-1，当为0时可执行抢占

                    从中断返回内核空间时，内核会检查need_resched和preempt_count，如果need_resched被设置，preempt_count为0，说明有一个更重要的任务需要执行并可以抢占，此时，调度程序就会被调用

    内核抢占发生在：

        #中断处理程序正在执行，且返回内核空间之前

        #内核代码再一次具有可抢占性的时候

        #如果内核中的任务显式地调用schedule()

        #如果内核中的任务阻塞（同样会调用schedule()）

7.实时调度策略

  实时调度策略：SCHED_FIFO和SCHED_RR

  非实时调度策略：SCHED_NORMAL

#SCHED_FIFO：先入先出调度算法，不使用时间片，SCHED_FIFO级进程会比SCHED_NORMAL级先得到调度

#SCHED_RR：与SCHED_FIFO大体相同，是带有时间片的SCHED_FIFO，是一种实时轮流调度算法

8.与调度相关的系统调用：

      Linux提供了一个系统调用族，用于管理与进程调度相关的参数

#与调度策略和优先级相关的系统调用：

    sched_setscheduler()：设置进程的调度策略和实时优先级

    sched_getschedular()：获取进程的调度策略和实时优先级

    sched_setparam()：设置进程的实时优先级

    sched_getparam()：获取进程的实时优先级

#与处理器绑定有关的系统调用

    Linux调度程序提供强制的处理器绑定机制

#放弃处理器时间：sched_yield()通过sched_yield()系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制