精选优质文档-倾情为你奉上实验三 一个任务调度问题1. 问题描述:在单处理器上具有期限和惩罚的单位时间任务调度问题.2. 算法原理:考虑一个给定的调度. 我们说一个任务在调度迟了, 如果它在规定的时间之后完成; 否则, 这个任务在该调度中是早的. 一个任意的调度总可以安排成早任务优先的形式, 其中早的任务总是在迟的任务之前. 为了搞清这一点, 请注意如果某个早任务a(i)跟在某个迟任务a(j)之后, 就可以交换a(i)和a(j)的位置, 并不影响a(i)是早的a(j)是迟的状态.类似的,任意一个调度可以安排成一个规范形式, 其中早的任务先于迟的任务, 且按期限单调递增顺序对早任务进行调度. 为了做到这一点, 将调度安排成早任务优先形式. 然而, 只要在该调度中有两个分别完成于时间k和k+1的早任务a(i)和a(j) 使得d(j)d(i), 就交换a(i)和a(j)的位置. 因为在交换前任务j是早的, k+1=d(j) . 所以k+1d(j) , 则a(i)在交换之后任然是早的. 任务a(j) 被已到了调度中的更前位置,故它在交换后任然是早的.
