栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

线程与工作时间

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

线程与工作时间

有n个线程,需要执行m个作业,不考虑线程切换等因素,来执行完这些任务最快需要多少时间。
输入:
n:n个线程
m:m个任务,每个代表执行时间。
输出:最快施行时间
样例输入:3
                  1 3 2 4 5
样例输出:5

思路:
作业调度算法有FCFS以及SJF
由于同时到达一批任务,尝试用SJF的方法

名称线程1线程2线程3
S1123
S245
总时长573

发现无法达到答案所给的5,因为线程3有2的空闲时间,而线程2多处理2秒
换一种思路

名称线程1线程2线程3
S1125
S243
总时长555

由于一批作业的最短时间由不同线程工作的最长时间决定,所以从m个线程中选出总时长最短线程进行作业处理。那么该怎么选取作业呢?
根据作业时长从小打大选取(SJF)?
由第一个例子知道,短作业优先并不能带来最优结果,小线程处理完后相对于其他线程的空闲时间对总时长的影响较小
尝试从大到小选取(LJF)

名称线程1线程2线程3
S1543
S212
总时长555

再举一个例子,任务时长从1-8排列

名称线程1线程2线程3
S1876
S2345
S221
总时长131211

总时长为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))
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/319183.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号