阴漾吧 关注:2贴子:30
  • 3回复贴,共1

【jsj_系统结构】预约表 延迟禁止表

只看楼主收藏回复

  ·根据预约表写出延迟禁止表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)


1楼2008-04-27 16:26回复
    根据预约表写出延迟禁止表F;
    [点评]数格子的游戏,如P148页图5。27(a),您分别数出每行中两个打勾之间的间隔数,然后把所有行的间隔数构成一个间隔集合,就是延迟禁止表了
    比如那个图:
    第一行:9和1
    第二行:8,3,2
    第三行:4
    第四行:5,6
    第五行:7,8

    相应减一减:9-1=8
          8-3=5,8-2=6,3-2=1
          0
          6-5=1
          8-7=1

    一共有8,6,5,1四种结果,所以禁止表={1,5,6,8}


    总共有几种间隔,间隔的总拍数是多少,除一下就行了。如(3,4)两间隔,就是(3+4)/2=2.5。


    2楼2008-04-27 16:26
    回复
      2025-05-11 19:58:28
      广告
      数格子的游戏,如P148页图5。27(a),您分别数出每行中两个打勾之间的间隔数,然后把所有行的间隔数构成一个间隔集合,就是延迟禁止表了。 
      吧主上面的这段话很寓教于乐啊。
      看了半天书都不知道什么意思,结果一看你这句话就懂了。


      3楼2009-11-09 12:08
      回复
        垃圾书说的不清不楚,还是楼主厉害,鄙视那些出书写的不清不楚的家伙,还是自考书,误人子弟。


        4楼2012-06-02 17:13
        回复