CPU调度
处理器调度分为三个级别：高级(作业)调度、中级(内存)调度、低级(进程)调度。高级调度负责把作业从后被队列调度到就绪队列中；中级调度负责从内存的就绪队列或者阻塞队列中调度进程到硬盘上，以此来释放内存；低级调度负责进程在cpu上的调度。一进程在 CPU 上的一次连续执行过程称为该进程的一个 CPU 周期。一个 CPU周期是由进程自我终止的。一个进程通常有若干个长短不等的 CPU 周期。 CPU调度处理是从就绪队列中选择进程并为之分配CPU的问题。
进程调度方式包括抢占方式和非抢占方式两种。在抢占方式下，系统可强行夺走现行进程占用的 CPU，即强行分割现行进程的当前 CPU 周期。在非抢占方式下，系统不能分割当前的CPU 周期，只在一个 CPU 周期执行完后才能重新调度。 基本的调度原则是：尽量提高系统吞吐量，均衡利用资源，对所有作业给予公平服务，对高优先级作业或进程给予优先服务。
CPU调度程序
每当CPU空闲时，操作就必须从就绪队列中选择一个进程来执行。进程选择由短期调度程序（short-term scheduler）或CPU调度程序执行。调度程序从内核就绪队列中选择一个能够执行的进程，并为之分配CPU。就绪队列不必是先进先出（FIFO）队列。就绪队列可实现为FIFO队列，优先队列，树或简单的无序链表。不过从概念上来说，就绪队列内的所有进程都要排队以等待在CPU上运行。队列中的记录通常为进程控制块（PCB）。
进程组成
进程状态
进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB。当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU就暂时不能运行。系统中可能会有很多个进程都处于就绪态，当CPU空闲时，操作系统就会选择一个就绪进程，让它上处理机（CPU）运行。如果一个进程此时在CPU上运行，那么这个进程处于“运行态”。CPU会执行该进程对应的程序（执行指令序列）
在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”。当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行。当等待的事件发生时，进程从“阻塞态”回到“就绪态”。
一个进程可以执行 exit 系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。
进程调度中的队列
- 后备队列：存放系统所有的任务，没有分配资源，需要经过高级调度到就绪队列中。
- 就绪队列（Ready Queue）：存放所有已经准备好并等待执行的进程。当进程的所有前提条件都满足时，它就被放入就绪队列中等待分配 CPU 执行。
- 执行队列（Running Queue）：只存放当前正在被 CPU 执行的进程。一般来说，执行队列中只会有一个进程。
- 阻塞队列（Blocked Queue）：存放被阻塞的进程。当一个进程因为等待某个事件（如输入/输出操作）而无法继续执行时，它就会被放入阻塞队列中等待事件的发生，当事件发生时就会重新回到就绪队列中等待被调度。
- 挂起队列（Suspended Queue）：存放被挂起的进程。当系统需要为其他任务腾出资源时，会将某些进程挂起并放入挂起队列中，以释放资源。这些进程可以随时被唤醒并重新放入就绪队列中。
调度准则
不同的CPU调度算法具有不同的属性，且可能对某些进程更为有利。为了比较CPU调度算法，分析员提出了许多准则，这些准则包括如下：
CPU使用率：需要使CPU尽可能忙。从概念上讲，CPU使用率0%-100%。对于真实系统，它应从40%(轻负荷系统)~90%（重负荷系统）系统吞吐量：如果CPU忙于执行进程，那么就有工作在完成。一种测量工作量的方法称为吞吐量，它指一个时间单元内所完成进程的数量。对于长进程，吞吐量可能为每小时一个进程；对于短进程，吞吐量可能为每秒10个进程。周转时间：从一个特定进程的角度来看，一个重要准则是运行该进程需要多长时间。从进程提交到进程完成的时间称为周转时间。周转时间为所有时间段之和，包括等待进入内存，在就绪队列中等待，在CPU上执行和I/O执行。等待时间：CPU调度算法并不影响进程运行和执行I/O的时间；它只影响进程在就绪队列中等待所花的时间。等待时间为在就绪队列中等待所花费时间之和。响应时间：对于交互系统，周转时间并不是最佳准则。通常，进程能相当早就产生输出，并继续计算新结果同时输出以前的结果给用户。因此，响应时间是从提交请求到产生第一响应的时间。这种时间称为响应时间，是从开始响应所需的时间，而不是输出响应所需要的时间。周转时间通常受输出设备速度的限制。
想要得到一个满足所有用户和系统要求的调度算法几乎是不可能的。设计调度程序，一方面要满足特定系统用户的要求（如某些实时和交互进程快速响应要求），另一方面需要考虑系统整体效率（如减少整个系统进程平均周转时间），同时还要考虑调度算法的开销。
调度算法
在操作系统中存在多种调度算法，其中有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。
一、先来先服务调度（First Come First Served，FCFS）
先来先服务调度是最简单的CPU调度算法，其实现过程很容易，可采用 FIFO 队列管理。 该调度算法既可以用于作业调度也可以用于进程调度。在作业调度中，算法每次从后备队列中选择最先进入该队列的一个或多个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。
在进程调度中，FCFS每次从就绪队列中选择最先进入该队列的线程，将CPU分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放CPU。采用FCFS策略的平均等待时间通常不是最小的，且如果进程CPU区间时间变化很大，平均等待时间也会变化很大。
FCFS调度算法是非抢占式的。一旦CPU被分配给了一个进程，该进程会保持CPU直到释放CPU为止，即程序终止或是请求I/O。FCFS算法对于分时系统（每个用户需要定时地得到一定的CPU时间）是特别麻烦的。允许一个进程保持CPU时间过长将是个严重错误。
FCFS算法的特点是算法简单，但效率低下，对长作业比较有利，但对短作业不利（相比SJF和高响应比），有利于CPU繁忙型作业；而不利于I/O繁忙型作业。
二、最短作业优先调度（Shortest Job First，SJF）
短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。这一算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而最短进程优先（SJF）则是从就绪队列中选择一个估计运行时间最短的进程，将CPU分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放CPU。
这一算法将每个进程与其下一个CPU区间段相关联。当CPU为空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有相同长度，那么可以使用FCFS调度来处理。一个更为适当的表示是最短下一个CPU区间的算法，这是因为调度检查进程的下一个CPU区间的长度，而不是其总长度。
SJF算法的平均等待时间、平均周转时间最少。该算法对短作业或短进程最为有利，它可获得最短的平均周转时间。但它忽略等待时间的长短，对长作业不利，特别是在抢占方式下，可能会使长作业无限延迟。对于抢占式 SJF 进程调度，还需要考虑是按最短原则还是按剩余最短原则抢占。 理论上该方法在等待时间方面是最优的，但实际上无法预测下一个 CPU 瞬时段的长度。
SJF调度算法可证明为最佳的，这是因为对于给定的一组进程，SJF算法的平均等待时间最小。通过将最短进程移到长进程之前，短进程等待时间的减少大于长进程等待时间的增加。因而，平均等待时间减少了。
SJF算法的真正困难是如何知道下一个CPU区间的长度。对于批处理系统的长期（作业）调度，可以将用户提交作业时所指定的进程时间极限作为长度。SJF调度经常用于长期调度。
虽然SJF算法最佳，但是它不能在短期CPU调度层次上加以实现。因为没有办法知道下一个CPU区间的长度。一种方法是近似SJF调度。虽然不知道下一个CPU区间的长度，但是可以预测它。认为下一个CPU区间的长度与以前的相似。因此，通过计算下一个CPU区间长度近似值，能选择具有最短预测CPU区间的进程来进行。
三、最高优先级调度（Highest Privilege First，HPF）
HPF是让具有最高优先级的作业或进程获得优先服务。优先级通常用一个整型的优先数表示。优先级的设置可采用静态的或动态的两种方式。静态优先级是在创建进程时就已经确定好的，在整个运行期间不会改变；动态设置优先级基于某种原则会改变优先级，这可使调度更为灵活，使调度性能得到改善。HPF 调度可以是抢占式的或非抢占式的。
优先级调度可通过内部或外部方式来定义。内部定义优先级使用一些测量数据以计算进程优先级。例如，时间极限，内存要求，打开文件的数量和平均I/O区间与平均CPU区间之比都可以用于计算优先级。外部优先级是通过操作系统之外的准则来定义的，如进程重要性，用于支付使用计算机的费用类型和数量，赞助工作的单位，其他因素。
优先级调度可以是抢占或者非抢占的。当一个进程到达就绪队列时，其有优先级与当前运行进程的优先级相比较。如果新到达进程的优先级高于当前运行进程的优先级，那么抢占优先级调度算法会抢占CPU。而非抢占优先级调度算法只是将新进程加到就绪队列的头部。
优先级调度算法的一个主要问题是无穷阻塞（indefinite blocking）或饥饿(starvation)。
可以运行但缺乏CPU的进程可认为是阻塞的，它在等待CPU。优先级调度算法会使某个低优先级进程无穷等待CPU。通常，会发生两种情况，要么进程最终能运行，在系统最后为轻负荷时，要么系统最终崩溃并失去所有未完成的低优先级进程。
低优先级进程无穷等待问题的解决之一是老化（aging）。老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。SJF算法就是优先级调度的一个实例，SJF算法的优先级的CPU的占用时间。
五、时间片轮转调度（Round Robin，RR）
RR调度算法主要适用于分时系统。在这种算法中，系统将所有的就绪进程按到达时间的先后顺序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务原则。
RR调度算法每个作业给予一个运行时间片，若一个作业在规定的时间片内未运行完，则将该作业暂停并添加到就绪队列的尾部并调度另一作业(继续)运行。当所有的作业都运行完分配的一个时间片后，第一个作业才再次得到运行的机会，类似于环。RR 算法性能依赖于时间片的大小，时间片过大则退化为 FCFS算法，时间片过小时则称为“处理机共享” 。该算法是抢占性算法。 RR调度算法是专门为分时系统设计的。它类似于FCFS调度，但是增加了抢占以切换进程。定义了一个较小时间单元，称为时间片（time quantum,or time slice）。时间片通常为10-100ms。将就绪队列作为循环队列。CPU调度程序循环就绪队列，为每个进程分配一个时间片的CPU。
为了实现RR调度，将就绪队列保存为进程的FIFO队列。新进程增加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程，设置定时器在一个时间片之后中断，再分派该进程。
接下来将可能发生两种情况。进程可能只需要小于时间片的CPU区间。对于这种情况，进程本身自动释放CPU。调度程序接着处理就绪队列的下一个进程。否则，如果当前运行进程的CPU区间比时间片长，定时器会中断并产生操作系统中断，然后进程上下文切换，将进程加入到就绪队列的尾部，接着CPU调度程序会选择就绪队列中的下一个进程。
对于RR调度算法，队列中没有进程被分配超过一个时间片的CPU时间（除非它是唯一可运行的进程）。如果进程的CPU区间超过一个时间片，那么该进程会被抢占，而被放回到就绪队列。RR调度算法是可抢占的。
RR算法的性能很大程序上依赖于时间片的大小。在极端的情况下，如果时间片非常大，那么RR算法与FCFS算法一样。如果时间片很小，那么RR算法称为处理器共享，n个进程对于用户都有它自己的处理器，速度为真正处理器的1/n，那么CPU将在进程间过于频繁切换，使CPU的开销增大，而真正用于运行用户进程的时间将减少。时间片的大长短通常由以下因素确定：系统响应时间、就绪队列中的进程数和系统的处理能力。
六、多级队列调度
多级队列调度算法（multilevel queue scheduling）的基本思想是引入多个就绪队列，通过对各个队列的区别对待，达到一个综合的调度目标。在该算法中，根据作业或者进程的性质或类型的不同，将就绪队列在分成诺干个子队列，每个作业固定归入一个队列，例如系统进程，用户交互进程，批处理进程等不同的队列。不同队列可有不同的优先级，时间片长度，调度策略等等。
七、多级反馈队列调度
多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合发展，通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。例如：为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；同时，也不必实现估计进程的执行时间。
多级反馈队列调度算法的实现思想如下：
- 应设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。
- 赋予各个队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的运行时间片就越小。
- 当一个新进程进入内存后，首先将它放入第一级队列的末尾，按照FCFS原则排队等待调度。当轮到该进程执行时，如果它能在该时间片内完成，便可结束进程；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样按FCFS原则等待调度执行…...在第n级队列后，便按照时间片轮转的方式运行。
- 仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行；仅当第1 ∼ ( i − 1 ) 级队列均为空时，才会让i-1级队列中的进程运行。如果处理器正在执行第i级队列中的某进程时，又有新进程进入优先级较高的队列（第1 ∼ ( i − 1 )中的任何一个队列），则此时新进程将抢占正在执行进程的处理器资源，即由调度程序把正在运行的进程放回到第i级队列的末尾，把处理器资源分配给新到的更高优先级的进程。
多级反馈队列的优势如下：
- 终端型作业用户：短作业优先。
- 短批处理作业用户：周转时间优先。
- 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。
通常在使用多级队列调度算法时，进程进入系统时被永久地分配到一个队列。例如，如果前台进程和后台进程分别有独立队列，进程并不从队列转移到另一个队列，这是因为进程并不改变前台或后台性质。这种设置的优点是低调度开销，缺点是不够灵活。与之相反多级反馈队列调度算法（multilevel feedback queue scheduling algorithm）允许进程在队列之间移动。主要思想是根据不同CPU区间的特点以区分进程。如果进程使用过多的CPU时间，那么它会被转移到更低优先级队列。这种方案将I/O约束和交互进程留在更高优先级队列。此外，在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列。这种形式的老化阻止了饥饿的发生。
八、完全公平调度算法（CFS）
CFS即Completely Fair Scheduler，顾名思义，完全公平调度器。CFS作为主线调度器之一，也是最典型的O(1)调度器之一，在Linux2.6.23内核版本中引入，它最大的特点就是能保证任务调度的公平性。
CFS能在真实硬件上模拟出一种“公平的、精确的任务多处理CPU”。
- 公平，即对于n个正在运行的任务，当这些任务同时不断地运行时，CPU会尽可能分配给他们1/n的处理时间。CFS是一种基于加权公平排队思想的调度算法。
- 精确，指的是它采用红黑树作为调度的任务队列的数据结构。
接下来进入正餐，介绍下CFS：
- CFS使用红黑树结构，来存储要调度的任务队列。
- 每个节点代表了一个要调度的任务，节点的key即为虚拟时间（vruntime），虚拟时间由一个公式计算而来。
- key越小，也就是vruntime越小的话，红黑树对应的节点就越靠左。
- CFS scheduler每次都挑选最左边的节点作为下一个要运行的任务，这个节点是“缓存的”——由一个特殊的指针指向；不需要进行O（logn）遍历来查找。也因此，CFS搜索的时间是O(1)。
现在问题还剩下一个，vruntime具体应该怎样计算呢？
vruntime += 实际运行时间（time process run) * 1024 / 进程权重(load weight of this process)
实际运行时间很好计算，就是该程序已经运行了多久，那么进程权重应该怎样计算呢？答案是根据任务的nice值进行索引。nice值可以理解为是我们事先为任务分配的优先级，从优先级到权重的转换是通过prio_to_weight数组进行的，有40个值，根据索引来转换。
static const int prio_to_weight[40] =
{
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};假如现在我们有一个刚来的task，它的nice值是0，那么它的priority是多少呢？答案是1024。
所以此时，该任务的vruntime += 0*1024/1024 = 0，那么该任务的key也就是0，它会被放在红黑树上相应的位置。
为什么要使用nice？
假如系统此时有两个任务，nice都为0的时候，单个CPU usage = 运行时间*1024/（1024+1024） = 运行时间*0.5；也就是这两个任务平分CPU的使用，毕竟优先级一样嘛。
当我们把任务A调低一级后，也就是nice为-1，此时任务A对应的CPU usage = 运行时间*1277/（1024+1277) = 运行时间*0.55，任务B就是运行时间*1024/(1024+1277) = 运行时间*0.45.
权重数组以nice值为计算单位，每差一个nice值就会差10%的权重。也就是说，在CFS下，每调整1个单位的nice值，在理论上CPU的运行时间就会差别10%。
vruntime并不是无限小的，有一个最小值来限定。假如新进程的vruntime初值为0的话，比老进程的值小很多，那么它在相当长的时间内都会保持抢占CPU的优势，老进程就要饿死了，这显然是不公平的。
CFS是这样做的：每个CPU的运行队列cfs_rq都维护一个min_vruntime字段，记录该运行队列中所有进程的vruntime最小值，新进程的初始vruntime值就以它所在运行队列的min_vruntime为基础来设置，与老进程保持在合理的差距范围内。
对于新任务来说，vruntime = 0，这也是显而易见的，新来的任务运行时间是0嘛这个特性也是CFS算法唤醒抢占特性的由来：
CFS的唤醒抢占特性：休眠进程在唤醒时会获得vruntime的补偿，它在醒来的时候有能力抢占CPU是大概率事件，这也是CFS调度算法的本意，即保证交互式进程的响应速度，因为交互式进程等待用户输入会频繁休眠。
想象一下当你执行每一个敲击键盘、移动鼠标等交互操作的时候，对于系统来说，这就是来了个新任务->运行时间为0->vruntime为0->被放到调度任务队列红黑树的最左节点->最左节点通过一个特殊的指针指向，且该指针已被缓存。这就是CFS能很快对交互式进程做出反应的全过程。
CFS原则：
- 随着任务的执行，它的运行时间增加，因此vruntime也会变大，它会在红黑树中向右移动（想象一下这个画面）；
- 计算密集型作业将运行很长时间，因此它将移到最右侧；
- I/O密集型作业会运行很短的时间，因此它只会稍微向右移动；
- 对于更重要的任务，也就是nice值较小的（一般是小于0），他们的移动速度相对慢很多。（相对于nice = 0的任务，nice每小一级，CPU usage就会多10%，"10% effect"）虚拟时钟的滴答声更慢.
CFS的缺点：
也和唤醒抢占特性有关。CFS不能区分交互式进程和主动休眠的进程，主动休眠的进程并不要求快速响应，但也会在唤醒时获得补偿，例如通过调用sleep()、nanosleep()的方式，定时醒来完成特定任务，这有可能会导致其它更重要的应用进程被抢占，有损整体性能。
下面实现了几个简单调度算法、
#include<iostream>
using namespace std;
#include<iostream>
#include<queue>
#include<time.h>
#include<string>
//输出函数
template<class...Args>
void print(const Args&... args) noexcept
{
((cout << args),...);
fflush(stdout);
}
//简化的进程控制块
using PCB = struct Process_Control_Block
{
Process_Control_Block(int ctime,string n):cpu_time(ctime),name(n),pid(rand()% 10000){}
Process_Control_Block(const Process_Control_Block& rhs):cpu_time(rhs.cpu_time),name(rhs.name),pid(rhs.pid){}
~Process_Control_Block()noexcept{}
Process_Control_Block& operator=(const Process_Control_Block& rhs) noexcept
{
if(this != &rhs)
{
name = rhs.name;
cpu_time = rhs.cpu_time;
pid = rhs.pid;
}
return *this;
}
//占用CPU运行时间，这里是假设占用这些时间，实际的占用时间是预测
int cpu_time;
//进程名称
string name;
//进程pid，没有使用该字段
int pid;
//进程优先级,这里并没有使用该字段，默认优先级为占用cpu时间
int priority = 0;
//还有好多其他的属性如栈区，堆区，寄存器，文件描述符等等。。。就不一一列出了。。。
};
//SJF算法进程优先级比较函数，比较cpu占用时间
struct comp
{
bool operator()(const PCB* lhs,const PCB* rhs) noexcept
{
return lhs->cpu_time > rhs->cpu_time;
}
};
//就绪队列
queue<PCB*> q1,q3,q4;
priority_queue<PCB*,vector<PCB*>,comp> q2;
//指定进程数量
int count = 5;
//先来服务算法
void FCFS(queue<PCB*>& q) noexcept
{
cout << endl;
srand(time(0));
char name = 'A';
for(int i = 0;i < count;++i)
{
PCB* pt = new PCB(rand()% 30,string(1,name++));
q.push(pt);
q2.push(new PCB(*pt));
q3.push(new PCB(*pt));
q4.push(new PCB(*pt));
print("Process : ",pt->name,",pid = ",pt->pid,",need use cpu time = ",pt->cpu_time,"\n");
}
cout << endl;
cout << "FCFS algorithm" << endl;
int total_time = 0,wait_time = 0,total_wait_time = 0;
while(!q.empty())
{
PCB* pt = q.front();
q.pop();
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",pt->cpu_time,"\n");
total_time += pt->cpu_time;
wait_time += pt->cpu_time;
total_wait_time += wait_time;
delete pt;
}
print("wait total time = ",total_wait_time - wait_time,",average wait time = ",total_wait_time / count,",total wait & run time = ",total_wait_time - wait_time + total_time,"\n");
}
//最短作业优先算法
void SJF(priority_queue<PCB*,vector<PCB*>,comp>& q ) noexcept
{
cout << endl;
cout << "SJF alforithm " << endl;
int wait_time = 0,total_time = 0,total_wait_time = 0;
while(!q.empty())
{
PCB* pt = q.top();
q.pop();
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",pt->cpu_time,"\n");
total_time += pt->cpu_time;
wait_time += pt->cpu_time;
total_wait_time += wait_time;
delete pt;
}
print("total wait time = ",total_wait_time - wait_time,",average wait time = ",total_wait_time / count,",total wait & run time = ",total_wait_time - wait_time + total_time,"\n");
}
//时间片轮转算法
void RR(queue<PCB*>& q) noexcept
{
cout << endl;
cout << "RR alforithm " << endl;
int wait_time = 0,total_time = 0,total_wait_time = 0;
//设定时间片大小，和上下文切换开销大小，一般为10ms
int time_slice = 10,context_switch = 0;
while(!q.empty())
{
PCB* pt = q.front();
q.pop();
if(pt->cpu_time <= time_slice)
{
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",pt->cpu_time,"\n");
total_time += pt->cpu_time;
wait_time += pt->cpu_time;
delete pt;
}
else
{
context_switch += 10;
pt->cpu_time -= time_slice;
q.push(pt);
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",time_slice,"\n");
total_time += time_slice;
wait_time += time_slice;
}
total_wait_time += wait_time;
}
print("total wait time = ",total_wait_time - wait_time,",average wait time = ",total_wait_time / count,",total wait & run time = ",total_wait_time - wait_time + total_time,",context switch time = ",context_switch,"\n");
}
//多级反馈队列调度算法
void MFQC(queue<PCB*>& q1) noexcept
{
cout << endl;
cout << "MFQC algorithm" << endl;
//设置有3个就绪队列，时间片分别为5，10，15,优先级q1 > q2 > q3
queue<PCB*> q2,q3;
int q1_time_slice = 5,q2_time_slice = 10,q3_time_slice = 15;
int total_time = 0,wait_time = 0,total_wait_time = 0,context_switch = 0;
while(!q1.empty())
{
PCB* pt = q1.front();
q1.pop();
if(pt->cpu_time <= q1_time_slice)
{
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",pt->cpu_time,"\n");
total_time += pt->cpu_time;
wait_time += pt->cpu_time;
delete pt;
}
else
{
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",q1_time_slice,",enter queue 2","\n");
total_time += q1_time_slice;
wait_time += q1_time_slice;
q2.push(pt);
pt->cpu_time -= q1_time_slice;
context_switch += 10;
}
total_wait_time += wait_time;
}
while(!q2.empty())
{
PCB* pt = q2.front();
q2.pop();
if(pt->cpu_time <= q2_time_slice)
{
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",pt->cpu_time,"\n");
total_time += pt->cpu_time;
wait_time += pt->cpu_time;
delete pt;
}
else
{
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",q2_time_slice,",enter queue 3","\n");
total_time += q2_time_slice;
wait_time += q2_time_slice;
q3.push(pt);
pt->cpu_time -= q2_time_slice;
context_switch += 10;
}
total_wait_time += wait_time;
}
while(!q3.empty())
{
PCB* pt = q3.front();
q3.pop();
if(pt->cpu_time <= q3_time_slice)
{
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",pt->cpu_time,"\n");
total_time += pt->cpu_time;
wait_time += pt->cpu_time;
delete pt;
}
else
{
print("Process : ",pt->name,",wait time = ",wait_time,",use cpu time = ",q3_time_slice,"\n");
total_time += q3_time_slice;
wait_time += q3_time_slice;
q3.push(pt);
pt->cpu_time -= q3_time_slice;
context_switch += 10;
}
total_wait_time += wait_time;
}
print("total wait time = ",total_wait_time - wait_time,",average wait time = ",total_wait_time / count,",total wait & run time = ",total_wait_time - wait_time + total_time,",context switch time = ",context_switch,"\n");
}
int main()
{
FCFS(q1);
SJF(q2);
RR(q3);
MFQC(q4);
return 0;
}
Comments NOTHING