调度算法()

一、FCFS(先来先服务）

  • first-Come first-served
  • 范围：作业调度和进程调度
  • 过程：从就绪队列选择最先进入的进程，直到该进程结束或阻塞，才调度其他进程。
  • 缺点：只考虑作业等待时间，忽略了作业运行时间，往往与其他调度算法一起使用

二、SJF(短作业优先)

  • short job first
  • 范围：作业调度和进程调度
  • 过程：以作业长度计算优先级，作业越短，优先级越高。
  • 缺点：

    必须预知作业运行时间

    对长作业不利，忽略了作业等待时间

    人机无法互动

    紧迫性作业无法及时解决

  • 必须预知作业运行时间
  • 对长作业不利，忽略了作业等待时间
  • 人机无法互动
  • 紧迫性作业无法及时解决

三、高响应比优先调度(HRRN)

  • Highes Response Ratio Nex
  • 范围：作业调度和作业调度
  • 过程：

    为每个作业引入一个动态优先级，它随等待时间延长而增加(对长作业有利)
    \(优先权=\frac{等待时间+要求服务时间}{要求服务时间}\)

    优先级相当于响应比\(R_p\)
    \(R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}\)

  • 为每个作业引入一个动态优先级，它随等待时间延长而增加(对长作业有利)
    \(优先权=\frac{等待时间+要求服务时间}{要求服务时间}\)
  • 优先级相当于响应比\(R_p\)
    \(R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}\)
  • 优缺：

    既考虑了作业等待时间(FCFS)也考虑了作业运行时间(SJF)，
    等待时间相同，要求服务时间越短，优先级越高，有利于短作业
    要求服务时间相同，取决于等待时间，与FCFS类似
    每次调度之前都要做响应比\(R_p\)计算，增加了系统开销

  • 既考虑了作业等待时间(FCFS)也考虑了作业运行时间(SJF)，
  • 等待时间相同，要求服务时间越短，优先级越高，有利于短作业
  • 要求服务时间相同，取决于等待时间，与FCFS类似
  • 每次调度之前都要做响应比\(R_p\)计算，增加了系统开销

四、轮转调度(RR)

  • round robin
  • 范围：进程调度
  • 过程：

    按FCFS将进程排成就绪队列，每个进程每次运行一个时间片
    当进程结束或进程时间片结束(加入末尾)时再次调度
    时间片过长沦为FCFS,过短增加系统开销

  • 按FCFS将进程排成就绪队列，每个进程每次运行一个时间片
  • 当进程结束或进程时间片结束(加入末尾)时再次调度
  • 时间片过长沦为FCFS,过短增加系统开销

五、优先级进程调度(PSA)

  • poriority-scheduing algorithm
  • 范围：作业调度和进程调度
  • 过程：

    基于作业的紧迫程度，由外部赋予作业相应的优先级
    作业调度一般是非抢占式，不会与后来的更高优先级进程比较，会一直运行，除非结束或阻塞。
    抢占式每次将新进入就绪队列的进程优先级与当前执行进程优先级比较，如果前者大于后者，应该立即停止执行
    进行进程切换；具有相同优先级的进程按照 FCFS 调度。

  • 基于作业的紧迫程度，由外部赋予作业相应的优先级
  • 作业调度一般是非抢占式，不会与后来的更高优先级进程比较，会一直运行，除非结束或阻塞。
  • 抢占式每次将新进入就绪队列的进程优先级与当前执行进程优先级比较，如果前者大于后者，应该立即停止执行
  • 进行进程切换；具有相同优先级的进程按照 FCFS 调度。
  • 优先级

    静态：开销小，但精度不足
    动态：随等待时间延长，优先级增加

  • 静态：开销小，但精度不足
  • 动态：随等待时间延长，优先级增加

六、多级反馈队列调度(MFQ)

  • multileved feedback queue
  • 范围：进程调度
  • 过程：

    设置多个就绪队列

    在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。
    为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。

    每个队列都采用FCFS算法

    当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。
    否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。
    当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。

    按队列优先级调度

    调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。
    如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。

  • 设置多个就绪队列

    在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。
    为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。

  • 在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。
  • 为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。
  • 每个队列都采用FCFS算法

    当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。
    否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。
    当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。

  • 当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。
  • 否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。
  • 当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。
  • 按队列优先级调度

    调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。
    如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。

  • 调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。
  • 如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。
  • 优缺：不必知道进程所需运行时间，可以满足各种类型进程的需要

小结

调度算法 作业调度 进程调度
先来先服务FCFS
短作业优先SJF
优先级PSA
高响应比优先HRRN
轮转调度RR X
多级反馈队列调度MFQ X

练习

————————

一、FCFS(先来先服务）

  • first-Come first-served
  • 范围：作业调度和进程调度
  • 过程：从就绪队列选择最先进入的进程，直到该进程结束或阻塞，才调度其他进程。
  • 缺点：只考虑作业等待时间，忽略了作业运行时间，往往与其他调度算法一起使用

二、SJF(短作业优先)

  • short job first
  • 范围：作业调度和进程调度
  • 过程：以作业长度计算优先级，作业越短，优先级越高。
  • 缺点：

    必须预知作业运行时间

    对长作业不利，忽略了作业等待时间

    人机无法互动

    紧迫性作业无法及时解决

  • 必须预知作业运行时间
  • 对长作业不利，忽略了作业等待时间
  • 人机无法互动
  • 紧迫性作业无法及时解决

三、高响应比优先调度(HRRN)

  • Highes Response Ratio Nex
  • 范围：作业调度和作业调度
  • 过程：

    为每个作业引入一个动态优先级，它随等待时间延长而增加(对长作业有利)
    \(优先权=\frac{等待时间+要求服务时间}{要求服务时间}\)

    优先级相当于响应比\(R_p\)
    \(R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}\)

  • 为每个作业引入一个动态优先级，它随等待时间延长而增加(对长作业有利)
    \(优先权=\frac{等待时间+要求服务时间}{要求服务时间}\)
  • 优先级相当于响应比\(R_p\)
    \(R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}\)
  • 优缺：

    既考虑了作业等待时间(FCFS)也考虑了作业运行时间(SJF)，
    等待时间相同，要求服务时间越短，优先级越高，有利于短作业
    要求服务时间相同，取决于等待时间，与FCFS类似
    每次调度之前都要做响应比\(R_p\)计算，增加了系统开销

  • 既考虑了作业等待时间(FCFS)也考虑了作业运行时间(SJF)，
  • 等待时间相同，要求服务时间越短，优先级越高，有利于短作业
  • 要求服务时间相同，取决于等待时间，与FCFS类似
  • 每次调度之前都要做响应比\(R_p\)计算，增加了系统开销

四、轮转调度(RR)

  • round robin
  • 范围：进程调度
  • 过程：

    按FCFS将进程排成就绪队列，每个进程每次运行一个时间片
    当进程结束或进程时间片结束(加入末尾)时再次调度
    时间片过长沦为FCFS,过短增加系统开销

  • 按FCFS将进程排成就绪队列，每个进程每次运行一个时间片
  • 当进程结束或进程时间片结束(加入末尾)时再次调度
  • 时间片过长沦为FCFS,过短增加系统开销

五、优先级进程调度(PSA)

  • poriority-scheduing algorithm
  • 范围：作业调度和进程调度
  • 过程：

    基于作业的紧迫程度，由外部赋予作业相应的优先级
    作业调度一般是非抢占式，不会与后来的更高优先级进程比较，会一直运行，除非结束或阻塞。
    抢占式每次将新进入就绪队列的进程优先级与当前执行进程优先级比较，如果前者大于后者，应该立即停止执行
    进行进程切换；具有相同优先级的进程按照 FCFS 调度。

  • 基于作业的紧迫程度，由外部赋予作业相应的优先级
  • 作业调度一般是非抢占式，不会与后来的更高优先级进程比较，会一直运行，除非结束或阻塞。
  • 抢占式每次将新进入就绪队列的进程优先级与当前执行进程优先级比较，如果前者大于后者，应该立即停止执行
  • 进行进程切换；具有相同优先级的进程按照 FCFS 调度。
  • 优先级

    静态：开销小，但精度不足
    动态：随等待时间延长，优先级增加

  • 静态：开销小，但精度不足
  • 动态：随等待时间延长，优先级增加

六、多级反馈队列调度(MFQ)

  • multileved feedback queue
  • 范围：进程调度
  • 过程：

    设置多个就绪队列

    在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。
    为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。

    每个队列都采用FCFS算法

    当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。
    否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。
    当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。

    按队列优先级调度

    调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。
    如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。

  • 设置多个就绪队列

    在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。
    为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。

  • 在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。
  • 为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。
  • 每个队列都采用FCFS算法

    当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。
    否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。
    当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。

  • 当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。
  • 否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。
  • 当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。
  • 按队列优先级调度

    调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。
    如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。

  • 调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。
  • 如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。
  • 优缺：不必知道进程所需运行时间，可以满足各种类型进程的需要

小结

调度算法 作业调度 进程调度
先来先服务FCFS
短作业优先SJF
优先级PSA
高响应比优先HRRN
轮转调度RR X
多级反馈队列调度MFQ X

练习