数据结构实验指导书(8)

2019-03-10 18:02

(2)设计调度算法,为每个作业分配一台可用机器; (3)给出分配方案。 3.设计思想

假设有7个作业,所需时间分别为{2,14,4,16,6,5,3},有三台机器,编号分别为ml ,m2和m3。这7个作业在三台机器上进行调度的情形如图所示,阴影区代表作业的运行区间。作业4在0到16时间被调度到机器1上运行,在这16个时间单位中,机器1完成了对作业4的处理;作业2在0到14时间被调度到机器2上处理,之后机器2在14到17时间处理作业7;在机器3上,作业5在0~6时间完成,作业6在6~11时间完成,作业3在11~15时间完成,作业1在15~17时间完成。注意到作业i只能在一台机器上从si时刻到si+ti时间完成且任何机器在同一时刻仅能处理一个作业,因此最短调度长度为17。

图 三台机器的调度示例

在上述处理中,采用了最长时间优先(LPT)的简单调度策略。在LPT算法中,作业按其所需时间的速减顺序排列,在分配一个作业时,将其分配给最先变为空闲的祝器。

下面设计宪成LPT算法的存储结构。 ·为每个机器设计数据类型: strnct harhineNode {

int ID。 //机器号 int avail; //机器可用时刻 };

·为每个作业设计数据类型: struct JobNode {

int ID ; //作盛号 int time; //处理时间 };

36

LPT算法用伪代码描述如下: 1.如果作业数n<=机器数m,则 1.1将作业i分配到机器i上;

1.2最短调度长度等于n个作业中处理时间最大值; 2.否则,重复执行以下操作,直到n个作业都被分配: 2.1将n个作业按处理时间建成一个大根堆H1; 2.2将m个机器按可用时刻建立一个小根堆H2; 2.3将堆H1的堆顶作业分配给堆H2的堆顶机器;

2.4将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入H2中; 2.5将堆HI的堆顶元素删除; 3.堆H2的堆顶元素就是最短调度时间。

思考题:关于机器的调度问题还有很多解法,请上网查找相关资料。

37


数据结构实验指导书(8).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:五年级下册劳动全册教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: