先来先服务(First Come First Seved, FCFS)

  • 每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程 退出或被阻塞，才会继续从队列中选择第一个进程接着运行
  • 当一个⻓作业先运行了，那么后面的短作业等待的时间就会很⻓，不利 于短作业

最短作业优先(Shortest Job First, SJF)

  • 优先选择运行时 间最短的进程来运行，这有助于提高系统的吞吐量
  • 对⻓作业不利

高响应比优先 (Highest Response Ratio Next, HRRN)

时间片轮转(Round Robin, RR)

  • 每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配 给另外一个进程； 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

多级反馈队列(Multilevel Feedback Queue)

  • 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
  • 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列;
  • 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
  • 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
  • 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

linux进程调度算法

演化过程

  1. 早期的进程调度器：早期的Linux内核使用的进程调度器是一个非常简单的轮询调度器。当进程被唤醒时，它被添加到调度队列的末尾。当进程的时间片用完后，它被移动到队列的头部。
  2. 2.2内核进程调度器：在2.2内核中，进程调度器被重写，引入了优先级调度算法。每个进程都被赋予一个优先级，优先级越高的进程获得更多的CPU时间。在这个版本的内核中，进程的优先级是根据进程的进程状态、时间片和其他因素动态计算的。通过轮询执行复杂度为O(n)
  3. O(1)进程调度器：O(1)进程调度器是在2.4内核中引入的。它使用了一个基于时间戳的调度算法，使得调度器能够快速地选择下一个要执行的进程。O(1)调度器还引入了一个“反馈优先级”机制，以确保长时间运行的进程不会占用CPU时间过多。
  4. CFS进程调度器：CFS（Completely Fair Scheduler）进程调度器是在2.6.23内核中引入的。CFS调度器使用了红黑树来维护进程的调度队列，使得进程的查找和调度变得更加高效。CFS调度器还引入了一个权重机制，以确保进程能够按照它们的优先级获得适当的CPU时间。

O(n)进程调度器

  • 调度器定义了一个 runqueue 的运行队列，将进程的状态变为 Running 的都会添加到此运行队列中，但是不管是实时进程，还是普通进程都会添加到这个运行队列中。当需要从运行队列中选择一个合适的任务(通过优先级确定执行顺序)时，就需要从队列的头遍历到尾部，这个时间复杂度是O(n)

O(1)进程调度器

  • 因为时间复杂度为O(1)而得名

具体流程

  1. 存在两个bitmap(长度都是140,对应140个优先级,越低优先级越高),如果对应bit是1表示相应优先级队列有任务,还有一个数组,长度为140,元素为不同优先级的运行队列头

    优先级通过静态优先级(创建时候指定)和动态优先级确定,动态优先级由其是IO密集型(优先级高)还是计算密集型综合得到

  2. 优先从高优先级队列执行,当时间片消耗完,加入expired 数组中

  3. 睡眠加入等待队列,睡醒再加入运行队列

  4. 当所有进程的时间片消耗完了,所有进程都在expired 数组了,只需要交换expired数组和active数组就OK

CFS

  • CFS的思想就是让每个调度实体（没有组调度的情形下就是进程，以后就说进程了）的vruntime互相追赶，而每个调度实体的vruntime增加速度不同，权重越大的增加的越慢，这样就能获得更多的cpu执行时间。

具体调度流程

  1. 首先进程调度器先给TASK_RUNNING状态的进程分配时间片

  2. 时间片大小的计算通过分配给进程的运行时间 = 调度周期 * 进程权重 / 所有进程权重之和,权重和nice值相关

    调度周期就是将所有处于TASK_RUNNING态进程都调度一遍的时间,差不多相当于O(1)调度算法中运行队列和过期队列切换一次的时间

  3. 将进程插入红黑树中,插入的key为vruntime,val为进程的信息

  4. vruntime的计算方法为vruntime = 实际运行时间 * 1024 / 进程权重

  5. 调度时候选择vruntime最小(即红黑树最左边)运行

  6. 当进程被唤醒或者通过fork()创建进程时,加入红黑树,

  7. 当进程进入休眠状态,会放到等待队列中,满足条件后会重新加入红黑树中