Open bigwolftime opened 3 years ago
https://index1024.gitee.io/xblog/system-process-dispatcher/
一. 调度指标
周转时间
其中一个衡量调度算法性能的指标是周转时间, 定义为:
T(周转时间) = T(完成时间) - T(任务到达时间)
多个任务的平均周转时间定义为:
T(平均周转时间) = (T1(任务1周转时间) + T2(任务2周转时间) + ...) / n. n 为任务数
响应时间
一。 单 CPU 下的调度策略
使用了队列思想, 那个任务先来便运行哪个任务. 其特点是: 逻辑简单, 易于实现
假设1: 有 A,B,C 三个任务, 几乎同时到达系统, 排队的序列为: A,B,C, 假如每个任务的执行时间是 10s, 则第 0-10s 运行任务A, 11-20s 运行 任务B, 21-30s 运行任务C.
则对于每个任务, 其周转时间为(假设: 任务几乎同时到达, 开始时间为0):
A: 10 - 0 = 10 B: 20 - 0 = 20 C: 30 - 0 = 30 其平均周转时间 = (10 + 20 + 30) / 3 = 20s
但实际上每个任务所需的执行时间是不同的, 在上面的前提下, 假设2: 我们修改任务A的运行时长为 100s. 则其周转时间为:
A: 100 - 0 = 100 B: 110 - 0 = 110 C: 120 - 0 = 120 其平均周转时间 = (100 + 110 + 120) / 3 = 110s
如果我们调换一下任务的执行顺序呢? 假设3: 任务A,B,C 的运行时间为 100s, 10s, 10s, 任务到达系统的顺序为: B, C, A, 则其周转时间:
B: 10 - 0 = 10 C: 20 - 0 = 20 A: 120 - 0 = 120 平均周转时间 = (10 + 20 + 120) / 3 = 50s
可以看到差距了, 在公平的调度策略下, 不同的任务执行顺序计算得到的平均周转时间是不同的, 这个问题通常被称为护航效应, 即耗时较少的的任 务被排在了耗时较大的任务后面.
考虑到平均周转时间, 提出了 SJF(最短任务优先原则): 即先执行最短的任务, 再执行次短的任务, 以此类推.
先进先出策略的假设3部分, 就体现出了 SJF 策略, 其表现要比 FIFO 要好.
假设: 有A,B,C三个任务, 其耗时分别为: 100s, 10s, 10s, 任务A在 0s 到达, 任务B,C在 10s 到达(B 在 C 的前面), 其周转时间:
A: 100 - 0 = 100 B: 110 - 10 = 100 C: 120 - 10 = 110 平均周转时间 = (100 + 100 + 110) / 3 = 103.3s
注意: 目前并没有用考虑进程的抢占式调度, 即进程一旦开始执行, 可一直运行直到结束.
可以看出, SJF 策略同样出现了护航效应问题.
上面的讨论都是非抢占式的调度策略, 在 SJF 的基础上, 假设任务可以被抢占, 即当一个新任务到达后, 如果新任务比当前正在运行的任务耗时少, 则停止正在运行的任务并保存其上下文, 转而执行新任务.
假设: A,B,C 三个任务, 其耗时分别为: 100s, 10s, 10s, 任务A在 0s 到达, 任务B,C在 10s 到达(B在C的前面), 其周转时间:
A: 120 - 0 = 120, A在第10s被B抢占, 直到第31s才继续执行 B: 20 - 10 = 10, B在10s时刻到达后直接抢占 C: 30 - 10 = 20, C在B的后面执行 平均周转时间 = (120 + 10 + 20) / 3 = 50s
4.
参考
《操作系统导论》
https://index1024.gitee.io/xblog/system-process-dispatcher/
一. 调度指标
周转时间
其中一个衡量调度算法性能的指标是周转时间, 定义为:
T(周转时间) = T(完成时间) - T(任务到达时间)
多个任务的平均周转时间定义为:
T(平均周转时间) = (T1(任务1周转时间) + T2(任务2周转时间) + ...) / n. n 为任务数
响应时间
一。 单 CPU 下的调度策略
使用了队列思想, 那个任务先来便运行哪个任务. 其特点是: 逻辑简单, 易于实现
假设1: 有 A,B,C 三个任务, 几乎同时到达系统, 排队的序列为: A,B,C, 假如每个任务的执行时间是 10s, 则第 0-10s 运行任务A, 11-20s 运行 任务B, 21-30s 运行任务C.
则对于每个任务, 其周转时间为(假设: 任务几乎同时到达, 开始时间为0):
A: 10 - 0 = 10 B: 20 - 0 = 20 C: 30 - 0 = 30 其平均周转时间 = (10 + 20 + 30) / 3 = 20s
但实际上每个任务所需的执行时间是不同的, 在上面的前提下, 假设2: 我们修改任务A的运行时长为 100s. 则其周转时间为:
A: 100 - 0 = 100 B: 110 - 0 = 110 C: 120 - 0 = 120 其平均周转时间 = (100 + 110 + 120) / 3 = 110s
如果我们调换一下任务的执行顺序呢? 假设3: 任务A,B,C 的运行时间为 100s, 10s, 10s, 任务到达系统的顺序为: B, C, A, 则其周转时间:
B: 10 - 0 = 10 C: 20 - 0 = 20 A: 120 - 0 = 120 平均周转时间 = (10 + 20 + 120) / 3 = 50s
可以看到差距了, 在公平的调度策略下, 不同的任务执行顺序计算得到的平均周转时间是不同的, 这个问题通常被称为护航效应, 即耗时较少的的任 务被排在了耗时较大的任务后面.
考虑到平均周转时间, 提出了 SJF(最短任务优先原则): 即先执行最短的任务, 再执行次短的任务, 以此类推.
先进先出策略的假设3部分, 就体现出了 SJF 策略, 其表现要比 FIFO 要好.
假设: 有A,B,C三个任务, 其耗时分别为: 100s, 10s, 10s, 任务A在 0s 到达, 任务B,C在 10s 到达(B 在 C 的前面), 其周转时间:
A: 100 - 0 = 100 B: 110 - 10 = 100 C: 120 - 10 = 110 平均周转时间 = (100 + 100 + 110) / 3 = 103.3s
注意: 目前并没有用考虑进程的抢占式调度, 即进程一旦开始执行, 可一直运行直到结束.
可以看出, SJF 策略同样出现了护航效应问题.
上面的讨论都是非抢占式的调度策略, 在 SJF 的基础上, 假设任务可以被抢占, 即当一个新任务到达后, 如果新任务比当前正在运行的任务耗时少, 则停止正在运行的任务并保存其上下文, 转而执行新任务.
假设: A,B,C 三个任务, 其耗时分别为: 100s, 10s, 10s, 任务A在 0s 到达, 任务B,C在 10s 到达(B在C的前面), 其周转时间:
A: 120 - 0 = 120, A在第10s被B抢占, 直到第31s才继续执行 B: 20 - 10 = 10, B在10s时刻到达后直接抢占 C: 30 - 10 = 20, C在B的后面执行 平均周转时间 = (120 + 10 + 20) / 3 = 50s
4.
参考
《操作系统导论》