Skip to main content

11 调度

调度策略与调度类​

实时进程：需要尽快执行返回结果。

普通进程：按照正常流程完成，优先级没实时进程高。

调度策略：优先级是一个数值，实时进程优先级范围是 0～99，普通进程优先级范围是 100～139。数值越小优先级越高。

实时调度策略​

SCHED_FIFO：高优先级的进程可以抢占低优先级的进程，相同优先级的进程遵循先来先得。

SCHED_RR：轮流调度算法，采用时间片，相同优先级的任务当用完时间片会被放到队列尾部，以保证公平性，而高优先级的任务也是可以抢占低优先级的任务。

SCHED_DEADLINE：按照任务的 deadline 进行调度，选择其 deadline 距离当前时间点最近的那个任务，并调度它执行。

普通调度策略​

SCHED_NORMAL：普通进程。

SCHED_BATCH：后台进程，几乎不需要和前端进行交互。

SCHED_IDLE：空闲时才跑的进程。

完全公平调度算法​

CFS， Completely Fair Scheduling 完全公平调度。CFS 为每一个进程安排一个虚拟运行时间 vruntime，正在运行的进程随着时间的增长 vruntime 不断增大，没有得到执行的进程 vruntime 不变。

虚拟运行时间 vruntime += 实际运行时间 delta_exec * NICE_0_LOAD/ 权重

调度队列与调度实体​

vruntime 经常在变，变了再插入这个数据结构，需要重新排序，使用红黑树平衡查询和快速更新。

调度类工作方式​

在队列上操作任务，第一个成员变量是指针，指向下一个调度类。

调度时从优先级最高的调度类到优先级低的调度类依次执行，对于每种调度类有自己的实现。

  • enqueue_task 向就绪队列中添加一个进程，当某个进程进入可运行状态时，调用这个函数；dequeue_task 将一个进程从就绪队列中删除；
  • pick_next_task 选择接下来要运行的进程；
  • put_prev_task 用另一个进程代替当前运行的进程；
  • set_curr_task 用于修改调度策略；
  • task_tick 每次周期性时钟到的时候，这个函数被调用，可能触发调度。

主动调度​

  • Btrfs 等待一个写入
  • Tap 网络设备等待一个读取

schedule 函数的调用过程

  1. 取出任务队列 rq，task_struct *prev 指向这个 CPU 的任务队列上面正在运行的进程 curr
  2. 获取下一个任务，task_struct *next 指向下一个任务
  3. 当选出的继任者和前任不同，进行上下文切换，继任者进程正式进入运行

进程上下文切换​

  1. 切换进程空间，即虚拟内存
  2. 切换寄存器和 CPU 上下文

进程切换的时候，如果每个寄存器都切换，需要全量保存，全量切换动作太大。将某个进程的 thread_struct 里面的寄存器的值，写入到 CPU 的 TR 指向的 tss_struct，对于 CPU 来讲就完成了切换。指令指针的保存与恢复。

指令指针的保存与恢复​

  • 用户栈, 切换进程内存空间时切换
  • 用户栈顶指针, 内核栈 pt_regs 中弹出
  • 用户指令指针, 从内核栈 pt_regs 中弹出
  • 内核栈, 由切换的 task_struct 中的 stack 指针指向
  • 内核栈顶指针, __switch_to_asm 函数切换(保存在 thread 中)
  • 内核指令指针寄存器: 进程调度最终都会调用 __schedule, 因此在让出(从当前进程)和取得(从其他进程) CPU 时, 该指针都指向同一个代码位置

抢占式调度​

当一个进程执行太长时间，取出当前 CPU 的运行队列，得到这个队列上当前正在运行中的进程的 task_struct，调用这个 task_struct 的调度类的 task_tick 函数。如果当前运行的进程是普通进程，调度类为 fair_sched_class，调用的处理时钟的函数为 task_tick_fair。

当一个进程被唤醒的时候，当被唤醒的进程优先级高于 CPU 上的当前进程，就会触发抢占。

抢占的时机​

用户态的抢占时机​

  • 从系统调用中返回的那个时刻
  • 从中断中返回的那个时刻

内核态的抢占时机​

  • 调用 preempt_disable() 关闭抢占，当再次打开的时候
  • 遇到中断的情况，当中断返回的时候，返回的仍然是内核态