|
|
|
|
知识路径： > 嵌入式系统软件基础知识 > 嵌入式操作系统基础知识 > 处理器管理 > 任务调度 >
|
|
|
被考次数：4次
|
|
|
被考频率：
中频率
|
|
|
总体答错率：
42%
|
|
知识难度系数：
|
|
|
考试要求：
掌握
|
|
|
相关知识点：4个
|
|
|
|
|
为了改进FCFS算法，减少平均周转时间，人们又提出了短作业优先算法（Shortest Job First，SJF）。SJF算法的基本思路是：各个任务在开始执行前，必须事先预计好它的执行时间，然后调度算法将根据这些预计时间，从中选择用时较短的任务优先执行。SJF算法有两种实现方案：
|
|
|
|
.不可抢占方式：当前任务正在运行的时候，即使来了一个比它更短的任务，也不会被打断，只有当它运行完毕或者是被阻塞时，才会让出CPU，进行新的调度。
|
|
|
|
.可抢占方式：如果一个新的短任务到来了，而且它的运行时间要小于当前正在运行的任务的剩余时间，那么这个新任务就会抢占CPU去运行。这种方法，也称为最短剩余时间优先算法（Shortest Remaining Time First，SRTF）。
|
|
|
|
不可抢占的SJF算法如下图所示，由于任务T3的执行时间最短，所以首先被调度运行，其次是T1和T2。
|
|
|
|
|
|
|
|
可以证明，对于一批同时到达的任务，采用SJF算法将得到一个最小的平均周转时间。例如，假设有四个任务A、B、C、D，它们的运行时间分别是a、b、c和d，假设它们的到达时间是差不多的，调度顺序为A、B、C、D。那么任务A的周转时间为a，B的周转时间为a+b，C的周转时间为a+b+c，D的周转时间为a+b+c+d，因此，最后的平均周转时间为（4a+3b+2c+d）/4，从这个式子来看，显然，只有当a
|
|
|
