scheduling - Jokacer/Learn GitHub Wiki

  多任务操作系统能同时并发的交互执行多个进程，无论在单处理器机器还是在多处理器机器上都可以通过调度实现进程的并发进行。多任务系统可分为：抢占式多任务(preemptive multitasking)和非抢占式多任务(cooperative mutitasking)。抢占式多任务系统由调度系统决定什么时候停止一个进程的运行并执行其他进程;非抢占式多任务只能由进程自己主动停止执行，这有可能使得某个进程独占资源导致系统崩溃。现在绝大多数系统设计采用的是抢占式多任务。

进程创建

  进程创建首先需要在新的地址空间创建进程，读入可执行文件，最后开始执行，Unix将创建进进程的操作分解到两个函数去执行：fork()和exec()，fork()拷贝当前进程创建一个子进程，exec()读取可执行文件并将其载入地址空间开始运行。

fork()

  fork()-->clone()-->do_fork()-->copy_process()

  1. 调用dup_task_struct()为新进程创建内核栈、thread_info结构和task_struct
  2. 检查子进程创建后的资源限制
  3. 子进程设置进程描述符，状态设置为TASK_UNINTERRUPTIBLE以保证不会投入使用
  4. 调用alloc_pid()为新进程分配一个有效PID
  5. 根据clone()的参数标志拷贝或共享文件、文件系统信息、进程地址空间和命名空间等
  6. 返回指向子进程的指针

  若copy_process()返回成功，则将新创建的子进程唤醒并投入使用。

唤醒

  唤醒操作通过wake_up()函数进行会唤醒指定的等待队列上的所有进程，调用try_to_wake_up()函数，该函数负责将进程设置为TASK_RUNNING状态，调用enqueue_task()将进程放入红黑树中，若被唤醒的进程优先级高于当前执行的进程的优先级，则需要设置need_resched标志。

进程调度

  进程可被分为I/O消耗型（进程的大部分时间在提交或等待I/O请求）和处理器消耗型（大部分时间在执行代码），调度策略通常需要在响应时间短和高吞吐量之间寻找一个平衡。

进程优先级

  通常调度算法是优先运行高优先级的进程，相同优先级进程进行轮转调度。Linux采用两种优先级范围：

  1. nice值，范围式-20到19，默认值为0,nice值越大优先级越低，可通过ps -el查看其NI项。
  2. 实时优先级，默认范围式0到99，值越大优先级越高，实时进程的优先级都高于普通进程，即实时优先级和nice优先级互不相交。

CFS

  Linux使用新的CFS(Completely Fair Scheduler，完全公平调度算法)，根据新的可运行进程消耗了多少处理器使用比来判断是否将其投入运行，若其消耗的使用比比当前进程小，则立即投入运行。   举个例子，一个系统有两个可运行进程：一个文字编辑程序和一个视频编码程序，用户总希望文字编辑响应迅速，而对视频编码程序的运行没有太严格的时间要求，我们希望在使用文本编辑程序的时候能将其立即唤醒，在不使用时可以运行视频处理程序，此时如果使用时间片轮循则不是个好选择，Linux分配给两个程序一个给定的处理器使用比，比如两个程序是系统仅有的运行程序，且具有相同的nice值，那么处理器分配的使用比都是50%，文本编辑器更多的时间是用于等待用户输入，因此用不到处理器的50%，那么视频解码将有机会使用超过50%的处理器时间，当文本编辑程序被唤醒时CFS发现其使用比为50%，但是真实使用的却很少，那么为了公平起见，会立即抢占视频解码程序并立即将文本编辑器投入使用，处理完用户输入后又进入休眠状态将处理器还给视频编辑器，由于文本编辑器消耗的处理器时间小于给定的50%，所以CFS总能毫不犹豫的将其立即投入使用。   CFS是针对普通进程的调度类，在Linux中被称为SCHED_NORMAL,根据优先级将处理器按使用比重分配给进程而不是按照时间片分配，这样的方式可动态的切换频率。

vruntime

  vruntime变量存放虚拟运行时间，vruntime = 实际运行时间 * 1024 / 进程权重 ，每个进程的虚拟运行时间都是相同的，则CFS使用vruntime记录一个进程运行了多久以及还能运行多久。

进程选择

  在进行进程选择时CFS总会选择vruntime最小的那一个进程进行执行，CFS采用红黑树来组织可运行程序并利用其迅速找到最小的vruntime的进程，树中最左边的叶子节点是vruntime最小的节点，为了不每次都遍历树，采用一个rb_left字段将最左的叶子节点缓存下来，当一个任务被唤醒时便会将进程插入红黑树中，并维护rb_left缓存的值。

实时调度策略

  Linux提供两种实时调度策略：SCHED_FIFO和SCHED_RR，普通调度策略则是SCHED_NORMAL。   SCHED_FIFO实现简单的先入先出的调度算法，不使用时间片，处于可运行状态的SCHED_FIFO级进程都比SCHED_NORMAL级的进程先得到调度，除非更高级的SCHED_FIFO或者SCHED_RR任务抢占SCHED_FIFO任务，不然只有等待该进程自己释放处理器;同等级的SCHED_FIFO进程会轮流进行，但也只有他们自愿让出处理器时才会退出。   SCHED_RR和SCHED_FIFO差不多，只是带有时间片，但是时间片值用来重新调度同一优先级的进程，即使SCHED_RR时间片耗尽也不会被低优先级的进程抢占。

进程终结

  当进程调用exit()系统调用时或者接受到它既不能处理也不能忽略的信号或者异常时也可能被动终结，反正系统终结大部分靠do_exit()来完成。

  1. 将task_struct标志成员设置为PF_EXITING.
  2. 调用del_timer_sync()删除任一内核定时器。
  3. 如果BSD的进程记账功能式开启的，调用acct_update_integrals()输出记账信息。
  4. 调用exit_mm()函数，释放进程占有的mm_struct。
  5. 调用sem_exit()函数，释放进程的信号量。
  6. 调用exit_files()和exit_fs()，分别递减文件描述符和文件系统数据的引用计数。
  7. 把存放task_struct的exit_code成员中的任务退出码置为exit()提供的退出码。
  8. 调用exit_notify()向父进程发信号，给子进程重新找父进程，新的父进程为进程组中其他进程或者init进程。并把进程状态置为EXIT_ZOMBIE。
  9. do_exit()调用schedule()切换到新的进程。因为处于EXIT_ZOMBIE状态的进程不会再被调度，所以这是进程执行的最后一段代码 以上为释放资源的过程，进程不可运行并处于EXIT_ZOMBIE退出状态，目前依然还存在与内存中的目的就是向父进程提供信息。在父进程通知内核它并不关系这些信息后则将其最后的占用资源释放掉。