操作系统如何select在CPU中运行的下一个进程？

如果进程X花费了它的量子，调度器将被调用。 如果有其他进程具有更高或相同的动态优先级，则会发生上下文切换。 如果没有其他进程，并且当前进程仍然准备运行（没有被阻塞），那么将在没有上下文切换的情况下恢复。 有两个队列，在每个优先级active和expired ; 所以如果我们有几个相同优先级的进程，他们会一个接一个地运行。

检查https://criticalblue.com/news/wp-content/uploads/2013/12/linux_scheduler_notes_final.pdf Linux中的进程调度 – 关键蓝。 Volker Seeker – 爱丁堡大学05.12.2013（linux 3.1）

进程调度程序..有以下任务：

• •在所有正在运行的进程中平均分配CPU
• •根据需要选择合适的流程以运行下一步，考虑调度类/政策和流程优先级

• •平衡SMP系统中多个内核之间的进程

  struct task_struct *（* pick_next_task）（struct rq * rq）;

5.1调度程序入口点。其主要目标是找到下一个要运行的任务，然后将其分配给本地变量。

  next = pick_next_task(rq); ... if (likely(prev != next)) { rq->nr_switches++; /* * Pick up the highest-prio task: */ static inline struct task_struct * pick_next_task(struct rq *rq) { const struct sched_class *class; struct task_struct *p; /* * Optimization: we know that if all tasks are in * the fair class we can call that function directly: */ if (likely(rq->nr_running == rq->cfs.nr_running)) { p = fair_sched_class.pick_next_task(rq); if (likely(p)) return p; } for_each_class(class) { p = class->pick_next_task(rq); if (p) return p; } BUG(); /* the idle class will always have a runnable task */ } 

pick_next_task()也在sched.c实现。 它遍历我们的调度类列表来查找具有可运行任务的最高优先级的类（请参阅上面的调度类）。 如果找到该类，则调用调度类钩子。 由于大多数任务都是由sched_fair class来处理的，所以在函数的开始部分就实现了这个类的快捷方式。

现在schedule()检查pick_next_task()发现了一个新的任务，或者是否选择了之前运行的任务。 如果后者是这种情况，则不执行任务切换，并且当前任务只是继续运行。 如果找到新的任务（更可能的情况），通过调用context_switch()来执行实际的任务切换。 在内部， context_switch()切换到新任务的内存映射，并交换寄存器状态和堆栈。

还有https://www.cs.columbia.edu/~smb/classes/s06-4118/l13.pdf Linux调度程序，CS CU，COMS W4118，

为每个处理器有一个单独的运行队列。 每个处理器只从自己的队列中选择进程运行。 定期排队

基本调度算法：查找具有可运行进程的最高优先级队列; 找到该队列上的第一个进程; 计算其量子尺寸; 让它运行; 当它的时间到了，把它放在过期的名单上; 重复。

运行队列：

• 140个独立的队列，每个优先级一个队列
• 实际上，这个数字可以在一个给定的地方改变
• 其实两套， active和expired
• 优先级0-99为实时进程
• 正常流程优先级100-139; 通过nice（）系统调用设置的值

使用Quanta（13/40）：

• 在每次打勾时，减少当前运行过程的量
• 如果时间变为零，则过程完成
• 如果这个过程是非交互式的，把它放在过期的列表上
• 如果进程是交互式的，则将其放在当前优先级队列的末尾
• 如果没有其他的优先级，它会立即再次运行
• 当然，如果跑得太多，奖金就会下降，优先级和互动状态也会下降

避免无限期超车：

• 有两组140个队列， active和expired
• 系统只运行来自active队列的进程，并在耗尽量子时将其放在expired队列中
• 当活动队列的优先级为空时，调度器查找次最高优先级队列
• 运行所有活动队列后，交换活动队列和expired队列
• 有指向当前数组的指针; 在循环结束时，指针被切换