·根据预约表写出延迟禁止表F;
数格子的游戏,如P148页图5。27(a),您分别数出每行中两个打勾之间的间隔数,然后把所有行的间隔数构成一个间隔集合,就是延迟禁止表了。
·由延迟禁止表形成冲突向量C
如上例:先写出第一个任务的初始冲突向量C0为10110001(注意倒着写,第1拍在最低位!!!),在为O的拍位选一个空位让第二个任务进入,写出第二个冲突向量C1(10110001);再由将第一个冲突向量C0右移一位(00101100),与C1按位"或",形成新的冲突向量C1'(10111101),这个向量指的是第一个任务和第二个任务流水执行时未禁止的拍数,也就是说第三个任务在第2和第7拍进入时不会与第一和第二个任务发生冲突,以此类推,一直写到没有新的向量为止。
·由所有的向量图画出状态图
麻烦,你先写出第一个冲突向量,然后分别写出所有可能进入的拍数,如上例,你必须按上步方法写出第2,3,4,7拍时进入的冲突向量表,然后下一步......,然后画图,连线处写上拍数
·由状态图形成最佳调度方案
在上步形成的状态图中连线拍数分别求出平均间隔拍数,找出最小平均间隔拍数。
[例]P158习题5 .9
[解]
·延迟禁止表F={1,3,4,8}(第一行间隔8,第二行间隔1,第三行间隔1,3,4,然后间隔都为1,合并)
·冲突向量为C:10001101(写一个8位两进制数,根据禁止表倒着写)
·画出状态图(如图,当第二个任务在第二拍进入时,冲突向量C1为10101111,又分为两种情况:当第三个任务在第5拍进入时,冲突向量C2等于C0,当第三个任务在第7拍进入时,冲突向量C2也等于C0),这时你就可以画出最右边的三条线。以此类推,画出所有连线,这题倒也简单,一共有两个冲突向量,比例子好多了。)
·写出各种方案的平均延迟表:
(2,7)4.5 (2,5)3.5 (6,7)6.5 (6,5)5.5 (5)5 (7)7
{从第一个向量出发,找出所有回路,把回路上的拍数按顺序写下来,并求出这些拍数的平均数}
·最小延迟调度方案为(2,5)
数格子的游戏,如P148页图5。27(a),您分别数出每行中两个打勾之间的间隔数,然后把所有行的间隔数构成一个间隔集合,就是延迟禁止表了。
·由延迟禁止表形成冲突向量C
如上例:先写出第一个任务的初始冲突向量C0为10110001(注意倒着写,第1拍在最低位!!!),在为O的拍位选一个空位让第二个任务进入,写出第二个冲突向量C1(10110001);再由将第一个冲突向量C0右移一位(00101100),与C1按位"或",形成新的冲突向量C1'(10111101),这个向量指的是第一个任务和第二个任务流水执行时未禁止的拍数,也就是说第三个任务在第2和第7拍进入时不会与第一和第二个任务发生冲突,以此类推,一直写到没有新的向量为止。
·由所有的向量图画出状态图
麻烦,你先写出第一个冲突向量,然后分别写出所有可能进入的拍数,如上例,你必须按上步方法写出第2,3,4,7拍时进入的冲突向量表,然后下一步......,然后画图,连线处写上拍数
·由状态图形成最佳调度方案
在上步形成的状态图中连线拍数分别求出平均间隔拍数,找出最小平均间隔拍数。
[例]P158习题5 .9
[解]
·延迟禁止表F={1,3,4,8}(第一行间隔8,第二行间隔1,第三行间隔1,3,4,然后间隔都为1,合并)
·冲突向量为C:10001101(写一个8位两进制数,根据禁止表倒着写)
·画出状态图(如图,当第二个任务在第二拍进入时,冲突向量C1为10101111,又分为两种情况:当第三个任务在第5拍进入时,冲突向量C2等于C0,当第三个任务在第7拍进入时,冲突向量C2也等于C0),这时你就可以画出最右边的三条线。以此类推,画出所有连线,这题倒也简单,一共有两个冲突向量,比例子好多了。)
·写出各种方案的平均延迟表:
(2,7)4.5 (2,5)3.5 (6,7)6.5 (6,5)5.5 (5)5 (7)7
{从第一个向量出发,找出所有回路,把回路上的拍数按顺序写下来,并求出这些拍数的平均数}
·最小延迟调度方案为(2,5)