如果在单处理器上,有 n 个运行时间分别为 t1,t2,t3, …, tn的已知作业,请考 虑它们的调度问题。这些作业可以按任意顺序执行,一次只能执行一个作业。 要求: (1)安排一个调度计划,使得所有的作业在系统中花费的时间最少 (一个作业在系统中花费的时间是该作业用于等待的时间和用于运行的时间的总和。) 思路:按照作业运行时间递增的顺序进行调度(运行时间一样,按照id递增的顺序进行调度 为该问题设计一个贪婪算法; (2)分析该贪婪算法是否总是能产生最优解?
时间: 2024-01-24 15:19:19 浏览: 20
贪婪算法的设计思路如下:
1. 将所有作业按照运行时间递增的顺序排序,如果有运行时间相同的作业,则按照 ID 递增的顺序排列。
2. 从排序后的作业列表中取出第一个作业,将其放入系统中运行。
3. 对于后面的每个作业,计算其在系统中等待的时间。等待时间 = 前面所有作业的运行时间之和。
4. 选择等待时间最短的作业,将其放入系统中运行。
5. 重复步骤 3 和步骤 4,直到所有作业都被放入系统中运行。
该贪婪算法可以得到一个近似最优解,但不一定总是最优解。因为该算法只考虑了当前作业在等待时间上的贡献,而没有考虑后续作业的影响。例如,在某些情况下,等待时间短的作业可能会占用资源,导致后续作业的等待时间变长,从而降低整体的效率。因此,该贪婪算法不能保证总是能产生最优解。
相关问题
现有3个同时到达的作业J1、J2和J3,它们的执行时间分别为t1、t2和t3,且t1
我理解你的问题是有三个同时到达的作业 J1、J2 和 J3,它们的执行时间分别为 t1、t2 和 t3,且 t1 < t2 < t3。此时如何安排它们的执行顺序可以最小化它们的平均等待时间?
如果采用先来先服务(FCFS)调度算法,即按照作业到达的先后顺序依次执行,它们的平均等待时间为:
(AWT) = ((0 + t1) + (t1 + t2) + (t1 + t2 + t3)) / 3 = (2t1 + 2t2 + t3) / 3
而如果采用最短作业优先(SJF)调度算法,即按照作业执行时间从短到长排序依次执行,它们的平均等待时间为:
(AWT) = ((0 + t1) + (t1 + t2) + (t2 + t1 + t3)) / 3 = (2t1 + 2t2 + t3) / 3
可以发现,无论采用哪种调度算法,它们的平均等待时间都是一样的,即 (2t1 + 2t2 + t3) / 3。因此,这三个作业的执行顺序并不会影响它们的平均等待时间。
现有3个同时到达的作业J1、J2、J3,它们的执行时间分别是 T1、T2和T3,且T1<T2<T3。若系统按单道方式运行且采用短作业 优先调度算法,则平均周转时间是( )。
根据短作业优先调度算法的定义,每次选择执行时间最短的作业先运行。因此,首先执行J1,然后是J2,最后是J3。因此,平均周转时间可以如下计算:
平均周转时间 = (完成时间J1 - 到达时间J1) + (完成时间J2 - 到达时间J2) + (完成时间J3 - 到达时间J3) / 作业数
完成时间J1 = 到达时间J1 + 执行时间T1 = T1
完成时间J2 = 完成时间J1 + 执行时间T2 = T1 + T2
完成时间J3 = 完成时间J2 + 执行时间T3 = T1 + T2 + T3
因此,
平均周转时间 = (T1 - 0) + (T1 + T2 - 0) + (T1 + T2 + T3 - 0) / 3
= (3T1 + 2T2 + T3)/3
因此,平均周转时间是(3T1 + 2T2 + T3)/3。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)