进程调度的原理和算法探析

进程的调度

进程的调度是由操作系统完成的，其目的是为了在一个进程占用CPU执行自己的操作后，选择下一个进程来占用CPU。调度发生的原因很简单，每个进程都希望能够占用CPU进行工作。因此，调度程序会进行上下文切换，并选择一个进程来执行其功能。

那么，什么时候进行调度呢？调度的原则又是什么呢？

什么时候调度进程

进程的调度可以理解为在进程的状态发生变化时进行。以下是一些进程状态的示例：

• 就绪态 -> 运行态：当一个进程被创建后，它进入就绪队列中等待执行。当操作系统从就绪队列中选择一个进程时，它进入运行态并开始执行。
• 运行态 -> 阻塞态：当一个进程执行I/O操作时，它可能会进入阻塞态，等待I/O操作完成。此时，操作系统会将当前进程放入阻塞队列，并切换到其他可运行的进程继续执行。
• 运行态 -> 结束态：当一个进程完成其任务或遇到终止指令时，它会进入结束态。操作系统会从就绪队列中选择下一个进程进行执行。

因为进程的状态发生变化时，操作系统需要考虑是否切换进程来占用CPU执行业务。因此，只要进程状态发生变化，就会触发进程调度。

以什么原则来调度进程

image

进程调度的原则主要有以下五种：

CPU利用率：调度程序应始终保持CPU处于繁忙状态运行，以提高CPU的利用率。

系统吞吐率：系统吞吐率是指在一定时间内完成的进程数量。调度程序应尽量选择能够快速完成的进程，以提高系统的吞吐率。

周转时间：指一个进程从创建到完成的总时间。调度程序应尽量减少进程的周转时间，以提高系统的效率。也可以这么理解：周转时间的计算公式为：周转时间 = 完成时间 - 创建时间；

等待时间：等待时间并不是所谓的阻塞时间，而是在就绪队列中等待被执行的时间；

响应时间：指用户发出请求后系统作出响应的时间。用户与其交互这之间所产生的消耗时间越少，响应越好；

就是一句话，进程越快越短越好；

进程调度算法

调度算法基本分为两类：非抢占式调度算法、抢占式的调度算法；

非抢占式调度算法：这个算法就是之前说的所有进程都进行排队等待，只有前面的进程都执行完了或者自己主动让出CPU，才可以轮到后面的进程执行。常见的非抢占式算法有：先来先服务（FCFS，First-Come, First-Served）和短作业优先（SJF，Shortest Job First）等。

抢占式调度算法：也就是时间片机制，每个进程都只占用CPU的一个时间片操作，执行完了就必须让出CPU使用权限给下一个进程使用。常见的抢占式算法有：轮转调度（Round Robin）、最短剩余时间优先（SRTF，Shortest Remaining Time First）和优先级调度等。

接下来我们详细看下各个调度算法的优劣：

先来先服务

这个是一种最简单的进程调度算法，所有进程按照到达时间的先后顺序排队，先到达的进程先被调度执行。这种调度算法类似于Java中的队列，采用先进先出（FIFO）的原则。

image

这种调度算法存在一个明显的问题，即如果一个进程执行时间较长，后面的进程就必须等待。

时间片轮转调度

时间片轮转调度是一种常见的进程调度算法，它将CPU时间划分为固定大小的时间片（也称为时间量），每个进程在一个时间片内执行，如果时间片用完后仍未执行完，则被移至就绪队列的末尾，等待下一轮调度。虽然解决了排队产生的问题，但是时间片如何划分呢？如果时间片过长，可能会导致资源浪费，因为某些进程可能只需要很短的时间就能执行完毕，但它们仍然会占用整个时间片。另一方面，如果时间片过短，会导致进程切换的频率增加，增加了上下文切换的开销，可能降低系统的性能。因此时间片的长度，需要有大致合理的数值。（《现代操作系统》的观点是建议时间片长度在20ms~50ms）。

image

最短作业优先

最短作业优先调度算法是一种非抢占式的调度算法，它根据进程的执行时间长短进行排队，将作业时间短的进程排在前面先执行。

image

我都不知道进程的执行时间长短的，系统咋知道的？其实系统通过预估进程的执行时间来进行调度，一般可以使用过去的历史执行时间进行估算。但是预估的准不准呢，那肯定不准，所以问题来了，预估的准确性是一个问题。如果预估不准确，可能会导致进程的等待时间增加或者执行时间不均衡。如果短时间的进程一直在排在前面执行，那么长时间的进程可能会一直等待执行的机会。

最短剩余时间优先

他是抢占式的调度算法，可以利用CPU的时间片机制，是基于最短作业优先算法的改进版本。该算法会根据进程的剩余执行时间进行排队，将剩余执行时间最短的进程优先执行。但是这个时间也是预估的而且每个进程的剩余执行时间需要进行实时监控和计算。

如果没有时间片的限制，SRTF算法会变成最短作业优先算法，因为每个进程都能从头到尾一次性执行完毕。

优先级调度

它根据进程的优先级来确定执行顺序。每个进程都有一个优先级值，通常在创建进程时由操作系统分配。如果多个进程的优先级相同，则按照先来先服务（FIFO）的方式依次执行。进程的优先级一般都已经由操作系统在创建的时候都已经设定好了的，如果硬要设置的话，可以去任务管理器看看；

image

优先级调度可以细分为抢占式和非抢占式；这个就不用说了，我单独说下抢占式，在抢占式优先级调度中，如果有高优先级的进程到达，当前正在执行的进程会被中断，让高优先级的进程先执行。

所以说他仍然有点问题，那就是低优先级的进程需要排很长时间的队才可以执行；

多级反馈队列调度

多级反馈队列调度是一种综合了优先级调度和时间片轮转调度的进程调度算法。它通过多个就绪队列按照优先级和时间片的不同来排列进程，以实现更加灵活和高效的调度，但是他并不是按照优先级依次进入就绪队列的，而是都在第一级队列开始执行，执行完就放入第二级队列，依次往下排而已，这个优先级只是单独对于就绪队列来讲的并不是进程的优先级；

image

他就兼顾了长短作业的场景，因为短作业很可能在前面的就绪队列中已经执行完了，而后面的长作业占用的CPU时间片也更长了。

这个算法类比银行办手续的场景：

image

• 银行大厅中本身三个排队队列，队列1优先级最高但是办理的时间却是最短的，这也对应着优先级越高时间片越短；
• 新来的客户都先进入队列1叫号排队，但是只办理1分钟的业务，办理不完的客户都去队列2依次排队，当队列1中的客户全办理完之后，工作人员开始处理队列2中的客户，然后依次排队，直至队列中的进程都处理完毕为止；
• 但是如果在办理其他队列的过程中又有新客户来了，则会终止当前客户的办理并重新进入对尾排队，工作人员会立马处理队列1中的客户。

可以发现，对于要办理短业务的客户来说，可以很快的轮到并解决。对于要办理长业务的客户，一下子解决不了，就可以放到下一个队列，虽然等待的时间稍微变长了，但是轮到自己的办理时间也变长了，

多级反馈队列调度算法兼顾了优先级和时间片的特点，能够适应不同类型的进程和任务。通过合理设置每个队列的优先级和时间片长度，可以根据实际情况提高系统的执行效率和响应速度。

总结

进程调度是操作系统中重要的任务之一。调度程序根据进程的状态变化，选择下一个进程来占用CPU执行任务。调度的原则包括CPU利用率、系统吞吐率、周转时间、等待时间和响应时间等。调度算法分为非抢占式和抢占式两种类型，其中常见的算法包括先来先服务、时间片轮转、最短作业优先、最短剩余时间优先、优先级调度和多级反馈队列调度。每种算法都有其优点和缺点，

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！