Threadx第二章

• 1.调度算法
  • 1.1决策模式
  • 1.2先来先服务FCFS
  • 1.3最短进程优先SPN
  • 1.4最短剩余时间优先（SRT）
  • 1.5轮转RR
  • 1.6高响应比优先HRRN
  • 1.7优先权队列

1.调度算法

1.1决策模式

决策模式说明选择的函数在执行的瞬间的处理方式，我们通常分成以下类别：

• 抢占式： 当前正在运行的进程可以被打断，并转移到就绪态。

• 非抢占式：一旦进入运行状态，就不会终止直到运行结束。

  对于一个调度算法能否被抢占，是对进程执行顺序有的很大的影响的。

1.2先来先服务FCFS

先来先服务是最简单的策略，也成为先进先出FIFO。首先它是一个非抢占的。如字面的意思，它根据进程到达时间决定先运行哪一个进程。

这里给出一个实际的例子。以表格的形式表现出在FIFO策略下各进程的情况

进程	到达时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

简单说就是依次执行完成，从时间轴上来看：

以表格的形式展现：

其中开始时间是上一个进程的结束时间

结束时间=开始时间+服务/执行时间

周转周期=结束时间-到达时间

带权周转时间=周转时间/服务时间

1.3最短进程优先SPN

也称最短作业优先（Short Job First,SJF）。它也是一个非抢占的。是根据服务的时间经行选择。在这里要注意下到达时间的顺序。比如实例中单纯以大小来排序的话是E-A-C-D-B,但正确的排序一定是A-B为开头。以时间为顺序：

例子中A运行结束时间为3，这时只有B进程等待。所以A运行结束后直接运行B。B结束后时间点到9，CDE都在等待。这个时候就选择服务时间最少的E，然后是较少的C，最后是D。以表格的形式展示：

1.4最短剩余时间优先（SRT）

SRT是针对SPN增加了抢占机制的版本，就好比例子中B运行时间非常长，在这期间其他所有的进程都在等待，如果将其中断，先处理所需时间少的，运行效率会有显著提升。一定要先明确SRT是抢占的。先给出时间为顺序的图：

1. A先运行至2.B到达等待。
2. A运行到3结束，B开始运行。
3. B开始运行，运行到4时，C进程到达，且C只需要4，此时B还需要5。所以先运行C，B继续等待。
4. C运行时间点到达6时，D到达，D需要5，进入等待，排在B后。
5. C运行结束，此时时间点是8，E到达，运行时间只要2，小于等待的BD，直接运行。
6. C运行结束，B开始运行。
7. B运行结束，D开始运行。

以表格的形式展现：

1.5轮转RR

轮转也称时间片技术（time slicing，SL），对于轮转法，最重要的是时间片的长度。轮转算法以一个周期（q）产生中断，当中断发生时，当前运行的程序置于就绪队列（队尾）中，然后基于FCFS选择下一个就绪作业运行。在这里我们以时间片q=1举例。

【例】进程A、B、C、D需要运行时间分别为20ms、10ms、15ms、5ms，均在0时刻达。到达的先后次序为A、B、C、D。如果时间片分别为1ms和5ms

分析:在掌握了时间片轮调度算法的基础上，我们可以用一个执行时间图来形象的表示进程执行的情况，如下：

1.6高响应比优先HRRN

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度，该算法是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

响应比的变化规律可描述为：

响应比=（等待时间+服务时间）/服务时间

根据公式可知：

当作业的等待时间相同时，则要求服务时间越短，其响应比越高，有利于短作业。

当要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。

对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。克服了饥饿状态，兼顾了长作业。

1.7优先权队列

根据需求，需要对客户请求赋予一定优先级别，并且每个客户执行时间很难预先估计，采用FPPS方式实现比较容易接受。

采用一种改进方法：

1. 所有客户请求都包含一定优先级别,所有请求位于一个全局队列当中。
2. 当一个客户达到运行上限，则将该客户对应所有请求优先级别调整到最低（阻塞状态），相当于逻辑上将队列放置到一个阻塞队列中。
3. 每次只从队列中去非阻塞客户的、最高优先级别的请求处理。
4. 如果队列中没有非阻塞的客户，则等待。
5. 当客户释放资源，则会将队列中所有对应该客户端的请求有限级别恢复成阻塞之前。

几个关键点：

1. 优先权数越低则级别越大。（许多地方都这样实现）

2. 优先权队列使用堆方式实现非常常见。（一个是排序算法复杂度低，一个是调整堆的代价小，一个是动态性强）

3. 队列中任务如果处于阻塞，应当调整相应客户到低优先级，这样相当于“阻塞”了当前客户，而不影响其它同优先级客户的调度运行。（同样许多地方如此做）

   对于调度算法不仅仅只有这几个，还有好多，在实际实现中，经常是几种方案综合实现。例如windows将多级队列，优先权队列，时间片轮转，以及先进进出方式进行综合，每种优先权任务位于不同队列，高优先权采用时间片轮转方式调度，低优先权采用先进进出方式调度。有时根据任务等待或者执行程度会调整优先权队列中元素的优先权。

   对于我们的ThreadX采用的优先权队，时间片轮轮转这两个，所以以上知识只要掌握这两点。以上知识转载CSDN网站，感谢CSDN的用户做出的贡献。

参考网址:http://blog.chinaunix.net/uid-9525959-id-3527532.html

参考网址:https://blog.csdn.net/xieminyao123/article/details/79116985

-------------本文结束感谢您的阅读-------------

赏

谢谢你请我吃糖果