博客

算法规则

昨天本人做有关交叉存储的冲突判断题，感觉如果按照传统的做题方法一个个看，容易漏判一些冲突项而导致失分；如果直接画甘特图，费时间，又容易画错。因此，想了很久，也试了很久，终于想到并逐步完善了一种交叉存储器检测冲突的算法，算法的执行过程中可以有序地找出冲突项，在算法结束后，又可以立即得出访问模块序列的总时间，可谓一举两得。我不太清楚是否有人之前想到过这种方法，如果有，或者是有更简单的方法，请私信我，谢谢。这个算法思想类似字符串匹配中的 KMP 算法，但放心，要比 KMP 简单得多。

由于考试一般考察四体交叉存储器，因此这里默认模块数为 4，现列出该算法规则如下：

• 访问序列由数字和空位组成，为方便起见，数字和空位我们统一称为元素。
• 算法开始时，在序列的头部和尾部各添 3 个空位。
• 设置一个滑动组，该滑动组
  
  必须
  
  为四个元素（可以全是数字，亦可部分数字部分空位）。从序列头部开始，依次往后移，一直移到序列尾部，滑动组不足四个元素为止。
• 若发现滑动组四个元素中有一对重复项（即两个重复项），则在后一个重复项的
  
  前面
  
  添加一个空位。如果是两对，则每对后一个重复项的
  
  前面
  
  添加一个空位。
• 滑动组移到序列尾部，算法结束，删去序列的头部和尾部的 3 个空位，得到最终序列结果。

看起来很繁琐，别急，我们马上来先看一个简单的例子，我将使用括号表示滑动组：

例 1

【例 1】访问一个四体交叉存储器的模块序列为：3,2,1,3,2。

【解】

从最终结果可以看出，访问完模块 3,2,1 后，因为下一个要访问的模块 3 还未恢复结束，因此会停止一个 r 的时间等待其恢复。同时，我们在算法执行过程中也知道了哪两个项会冲突（冲突项已加粗）：

3

2 1 _

3

2。还可以得知，处理器访问这个序列所用的时间为 6r。

所以从这个例子想跟大家说的是：这个算法

用一个数字表示一个访存周期，而用一个空位表示处理器等待存储体恢复的一个周期。并且，得到的总元素个数，就是我们想要知道的访问时间。

这个例子还是比较简单的，现稍微修改一下题目，来看看算法又会有怎样的表现：

例 2

【例 2】访问一个四体交叉存储器的模块序列为：3,1,2,3,2。

【解】

从最终结果可以看出，访问完模块 3,1,2 后，因为下一个要访问的模块 3 还未恢复结束，因此会停止一个 r 的时间等待其恢复；类似地，当第二次访问完模块 3 后，由于模块 2 还未恢复结束，因此也需要等待一个 r 的时间。同时，我们在算法执行过程中也知道了哪两个项会冲突（冲突项已加粗）：

3

1 2 _

3

_ 2 和 3 1

2

_ 3 _

2

。还可以得知，处理器访问这个序列所用的时间为 7r。

下面是一个极端的例子，用以说明为何需要在序列前后添置三个空位，同时我们也将看到序列中多个连续空位的产生：

例 3

【例 3】访问一个四体交叉存储器的模块序列为：1,1,2,2,3。

【解】

显然，处理器访问这个序列所需时间为 11r。

从这个例子中我们可以看到，如果序列头部不加三个空位，而是直接开始滑动的话，那么就会出现“1 _ 1 2 _ _ _ 2 3”的情况，这是不对的。

最后再来看一个更加长的例子：

例 4

【例 4】访问模块号的顺序：3，1，2，3，0，2，1，3，1，2，0，2。

【解】（我们直接跳过没有冲突的步骤，只列出发生冲突的步骤）

显然，处理器访问这个序列所需时间为 17r。

在做题的时候，你可以只写出冲突的步骤，不冲突的步骤没有必要写出来。有的时候，你甚至可以一眼看出要加多少个空位。OK，那么就暂时写到这了。