讲座视频 - 串行通信 - FIFO

[音乐播放] 大家好，我是 Jon Valvano。 这节课我们将介绍通信。在通信问题部分，我们首先来讨论一下 一种叫做先入先出队列的 重要数据结构。 我们现在要做的是，创建该缓冲器， 以便在数据流过系统时 存储数据。 这是一个非常重要的数据结构， 一般用于复杂的系统，具体来说 是通信系统。 接下来，我们将讨论一些定理 和一些性能指标。 现在，我们开始吧。 好的，这个先入先出队列 是一个缓冲器，对吧？ 它会存储数据。 我们将会在能产生数据的 系统中使用该缓冲器。 这个系统可能是一个输入设备， 也可能是一个软件。 在另一个流程中，会使用或销毁 数据。 它会处理这些数据，然后这些数据就没用了。 我们要做的是，在数据从生成器 传输到使用器时，将其临时存储在 此 FIFO 中。 在执行放置操作时，我会将其放在列表的末尾。 在执行获取操作时，我会从列表的 开始位置进行获取。 通过这种方式，该结构便成为了保序结构。 它的优点是，我可以对两个流程的执行 过程进行解耦。 所以，我可以生成几个，使用一个，然后再生成 几个，再使用几个。 通过这种方式，便无须再以锁步方式 运行生成器和使用器。 我可以对在整个系统中流式传输的数据进行缓冲。 这将是一个非常重要的结构。 下面，让我来演示一下它是如何运作的。 这个系统会有很多实现结构， 这个是最简单的结构之一，但它是一个缓冲器。 我为它分配了固定大小的空间。 这是一个有限缓冲器。 这个 10 单元缓冲器可存储最多 9 个数据片段。 我不会让它一直走到 10，因为那样 会更简单。 但我将会使用两个指标。 一个告诉我最早的数据的位置。 GetI 将会指向最早的数据所在的点， 即这条线的开头， 它告诉我下一个要获取的数据是哪个。 第二个指标叫做 PutI， 该指标指向这条线的末尾， 即我接下来要放置数据的空白点。 在这个特殊的例子中，如果 PutI 等于 GetI， 则表明该 FIFO 是空的。 让我来演示一下， 我将会把五个东西放进 FIFO， 然后取出五个东西， 我们来看看这个操作是如何实现的。 首先，我将会把数据放在 PutI 以前所在的位置。 所以，这便是进入这个地方的全部数据。 然后，我将会把它存储在 PutI 所在的位置， 然后使 PutI 递增。 下一个数据，我将会放在这里。 所以，如果我再次调用，第二个数据便会 出现在这里，且 PutI 递增。 然后是第三次调用。 这是第一个。 这是第二个。 这是第三个，也是最新的一个。 但是，现在我需要将 PutI 绕回到开头位置， 因为这是一个有限缓冲器，需要重复使用数据。 然后，我放置第四个数据。 这是最早的数据。 这是最新的，对吧？ 这便是我放入的数据。 每次放置后，我都会将数据存储在 PutI 所在的位置， 并使 PutI 递增。 很明显，我将会把下一个放在这里。 因此，这是第一个、第二个、第三个、第四个和 第五个。 在这个特定队列中，GetI 指向最早的数据， PutI 则指向我将会放置 下一个东西的位置。 让我们调用 Get 五次，看看会发生什么。 同样，当我调用 Get 时，Get 会获取该数据。 所以，这个数据会被删除， 我将会读取 Get 处的数据并使 Get 递增。 我将会获取下一个。 也就是这个。 我读取 Get 处的数据并使 Get 递增。 在取出这个后，我需要 将 Get 指针绕回开头位置。 如果您记得，这是 -- 我放入了这五个东西，并且已经删除了 第 1 个、第 2 个和第 3 个，所以现在 最早的数据是第四个。 所以这个会被删除。 同样，我会第四次调用 Get。 现在，GetI 递增，然后我会再次 调用 Get，对吧？ 这个会被删除。 现在，GetI 又重新指向 PutI， 表明该 FIFO 实际上是空的。 虽然现在与开始时的 情况不再一样，但是，如果 PutI 在函数开始时等于GetI，便表明 FIFO 实际上是空的。 好的，这里的几个流程图 从根本上解释了我刚刚在 Put 开始时执行的操作。 换句话说，它可以存储 0 到 9 个单元。 如果有 9 个单元，我将会操作失败。 如果有 0 至 8 个单元，那么我将会 将数据存储在 PutI 处，使其递增并在需要时绕回。 同样，对于 Get，FIFO 中可以有 0 至 9 个单元。 如果 PutI 等于 GetI，则表明没有单元， 我将会返回清空错误。 如果有 1 至 9 个单元，我将会 从 Get 处读取，使 Get 递增，在需要时绕回， 并返回成功的结果。 所以，系统有许多实现方式， 但这是相当简单的一个。 让我们来讨论一下一个有趣的定理，利特尔定理。 让我们以桥为例讨论一下，好吧？ 假设 FIFO 就是我们所说的这座桥。 汽车将会通过这座桥，对吧？ 我们将会定义 N -- 存在的汽车的总数， 也就是数据包的总数。 我们会在桥上的FIFO 中存储 N 减 1 个 数据包，并有一个处理中的数据包。 因此，系统中总共有 N 个数据包。 如果我们考虑每秒钟的数据包到达率， 或者也可以想成每秒的汽车到达率， 然后我们使用利特尔定理来定义平均到达率， 也就是数据包的平均 响应时间。 相当于，如果汽车驶往桥的前面， 要用多少秒 才能通过这座桥？ 如果我知道数据包进入我的系统的到达率， 而且知道桥上的汽车总数，也就是， FIFO 中的单元总数 再加上 1 个处理中的单元， 那么，我便可以使用利特尔定理来评估 N、λ 和 R 之间的关系。 例如，R 等于系统中的 数据包数量，也就是 FIFO 中的单元数量加 1， 除以进入系统的数据的到达率。 这样，便可以确定系统的平均 响应时间。 从这个角度来看，队列是我们处理 数据流问题时的一个有趣的 处理和研究对象。 综上所述，我们使用 FIFO 在 生成器和使用器之间暂时存储数据。 我们了解了利特尔定理。 这是从实验 18 中得到的一些数据，基本上， 我所做的便是定期测量FIFO 的大小，对吧？ 我执行了很多次，因此您可以 看到成千上万的测量数据。 在本实验中，不存在 FIFO 中的 数据包的数量超过 24 个的情况。 因此，我们可以看到，在这个特定的 FIFO 实施中， 或者说 这个特定的生成器和使用器用例中， 如果我选择大小为 24 的 FIFO，那么永远都不会出现失败的情况。 这便是在实验中绘制这个直方图的 好处之一，因为您可以了解 怎样才能确保FIFO 永远不被填满。 希望您喜欢本次实验。 这是一个非常重要的实验， 介绍了通信的概念以及数据 如何在系统中流动。 祝您学习愉快！ [音乐播放]