最早截止时间优先算法

来自计算思维百科
跳转至: 导航搜索
最早截止时间优先算法.png

如果计算机有很多任务排队等着被处理,哪个任务先被处理,哪个任务后处理,这个需要由操作系统决定,这就是调度。最早截止时间优先算法是实时系统CPU调度常用的调度算法之一,它的基本思想是越早完成的任务越要优先完成,这个算法并按照任务的截止时间来确定调度优先级。

基本概念

最早截止时间优先算法是根据任务的开始截止时间来确定任务的优先级。截止时间越早,其优先级越高。该算法要求在系统中保持一个实时任务就绪队列,该队列按各任务截止时间的早晚排序。具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时间时,总是选择就绪队列中的第一个任务,为之分配处理机,使之投入运行。

应用范围

该算法常常应用于多个任务的完成顺序安排

使用方法及步骤

  1. 按照任务的截止时间由早到晚排列成队列
  2. 每次执行任务总是选队列的第一个任务进行执行
  3. 根据步骤一确定的调度方式,决定是否中断当前执行的任务,执行新到达的截止时间更早的任务

应用案例

应用1- 出门办事路线规划

案例:小丽有两件事要出门才能完成,第一件事是到学院办公楼提交申请表,第二件事是去快递中心拿快递,申请表在小丽出门后1小时截止提交,快递在小丽出门后1.5小时截止提交。从小丽出门到学院办公楼和快递中心的时间分别是30分钟和40分钟,从办公楼到快递中心是40分钟,小丽怎么安排办事的顺序才能完成这两件事?(忽略交表时间和拿快递时间)

解决步骤:

  1. 由于两件事同时到达,不需要中途暂停其中一件事
  2. 第一件事截止时间比第二件事早,因此先到学院办公楼提交申请表,再去拿快递,在小丽出门后1小时10分钟可以完成两件事

这个案例中,交表和拿快递是两个进程,小丽就是操作系统,她要决定先执行哪个进程。由于交表这个进程的完成时间比拿快递的完成时间早,所以先执行交表这个进程。

可以体现的计算思维

最早截止时间优先算法根据任务的截止时间来确定优先级,保证了任务能及时得到处理和反馈,操作简单易行,体现了计算思维的优化特点。