有n个线程,需要执行m个作业,不考虑线程切换等因素,来执行完这些任务最快需要多少时间。
输入:
n:n个线程
m:m个任务,每个代表执行时间。
输出:最快施行时间
样例输入:3
1 3 2 4 5
样例输出:5
思路:
作业调度算法有FCFS以及SJF
由于同时到达一批任务,尝试用SJF的方法
| 名称 | 线程1 | 线程2 | 线程3 |
|---|---|---|---|
| S1 | 1 | 2 | 3 |
| S2 | 4 | 5 | |
| 总时长 | 5 | 7 | 3 |
发现无法达到答案所给的5,因为线程3有2的空闲时间,而线程2多处理2秒
换一种思路
| 名称 | 线程1 | 线程2 | 线程3 |
|---|---|---|---|
| S1 | 1 | 2 | 5 |
| S2 | 4 | 3 | |
| 总时长 | 5 | 5 | 5 |
由于一批作业的最短时间由不同线程工作的最长时间决定,所以从m个线程中选出总时长最短线程进行作业处理。那么该怎么选取作业呢?
根据作业时长从小打大选取(SJF)?
由第一个例子知道,短作业优先并不能带来最优结果,小线程处理完后相对于其他线程的空闲时间对总时长的影响较小
尝试从大到小选取(LJF)
| 名称 | 线程1 | 线程2 | 线程3 |
|---|---|---|---|
| S1 | 5 | 4 | 3 |
| S2 | 1 | 2 | |
| 总时长 | 5 | 5 | 5 |
再举一个例子,任务时长从1-8排列
| 名称 | 线程1 | 线程2 | 线程3 |
|---|---|---|---|
| S1 | 8 | 7 | 6 |
| S2 | 3 | 4 | 5 |
| S2 | 2 | 1 | |
| 总时长 | 13 | 12 | 11 |
总时长为13,说明LJF的确是作业完成的最短时间
总结:从m个线程找出总运行时长最短的线程,将作业时间最长的作业加入线程
伪代码
int getLongestTime()
{
获取m;
初始化Thread[m]=0; //线程i的总工作时长
获取Job数组以及长度;
对Job排序或建堆;
for(max in Job)
{
min=FindMin(Thread)
Thread[min]+=max
}
print(max(Thread))
}



