关于缓冲区（环）的问题

“如果您发现架构的开发成本过高，请考虑错误的架构会给您带来多少费用”

-我不记得确切的来源

有一次，“很久以前，在一个遥远的银河系中”，我购买了查尔斯·韦瑟利的精彩著作《程序员的练习曲》，在该书的引言中，作者证实了在开始独立编程之前需要研究教育实例和任务的必要性。 我强烈建议您找到这本书，阅读序言（不要停下来阅读本书的其余部分，并解决书中给出的问题），因为我无法更好地证明这种做法的必要性。 即使您遵循我的建议，并且在阅读本书时获得了很多知识和实践技能，您仍可以返回并阅读本文，因为它专门讨论其他几个问题。 而且，如果您不遵循我的建议，那么您应该继续努力。

不久前，在我骂我的文章中，我表达了对一个家用RTOS的看法，我提到在著名的mcucpp库（在某些方面，绝对是很棒的）中环形缓冲区的实现并不理想。 我将尝试解释我的观点，并设想理想的（尽可能在现实世界中）实现。 注意-提供给您注意的文本在“未完成”中放置了相当长的时间，然后出现了这样一个方便的案例。

我们正在继续开发用于与外围设备一起使用的库，并且我们下一步将进行内存管理和缓冲（是的，我们仍在继续进行准备操作，但是没有任何方式）。 组织缓冲的需求从何而来？它是哪种动物？ 事实上，外围设备的很大一部分速度有限，与以另一种方式启动传输过程相比，创建另一部分信息要花费一定的时间，有时甚至是非常重要的时间。 当然，在该时间过去之前，不能进行下一个发送，因此不能开始。

我们有一个经典的案例，即读写器对具有不同的速度。 根本不可能以一般的方式解决此问题，因为“请求流比服务流小得多但不为零，队列大小趋于无穷大”，从根本上讲无穷大是不可能的。 但是问题的一种特殊情况是，当我们有本地的请求突发时，但是平均而言，服务流能够应付负载，就可以解决足够容量的缓冲存储器。 让我们注意“足够的容量”这一短语，我们稍后将学习如何计算它，只要这对我们来说从根本上可行就足够了。

当然，是否绝对需要缓冲存储器。 对于传输的信息，您可以使用阻止记录，但是对于接收到的信息，情况有些糟糕，如果您未在顶级协议中采取适当的措施（魔术表达式xon / xoff不是从头开始的），则必须在处理之前将其添加到某处。在任何情况下，通常都会导致传输速率的明显限制。 外围设备中也有内部缓冲区的硬件实现（至少对于一个元素而言），但这并非总是如此，并且缓冲区大小从上面严格限制。

因此，我们仍将实现程序缓冲区，使用FIFO方法（即队列）来组织这样的缓冲区是很自然的事情，而队列又最好在具有两个指针的环形缓冲区上实现。 当我写“ best”时，这并不意味着其他实现（例如，参考队列）是不可能的，或者具有致命的缺陷而不是致命的。 这种表达方式仅意味着实现不会太复杂和相当有效，尽管其他人可能对此具有不可否认的优势，因为DarZaNeBy，他们必须为此付出代价。

由于您的MK模型不太可能具有这种通用设备的硬件实现（单个外围模块可以具有自己的环形缓冲区，但与本文的主题无关），我们将不得不在线性存储器中创建环形缓冲区（实现向量，实际上，它是可寻址内存中唯一的自然对象），为此，将需要一个缓冲区索引（甚至可能是两个索引，但稍后会更多）。 我认为，带有两个指针（索引）的循环缓冲区是在向量上实现队列的唯一可接受的方法，但是对此问题有不同的观点，我亲眼看到了一种“ x1 = x2; x2 = x3; ... x8 =新符号“，如果您愿意，我不会考虑这种异国情调。 给定的片段可能有权在特定的，非常有限的情况下存在，这一事实通常不能使它接受。

我们将考虑用于组织指针的程序模块的正确实现，并且首先要注意定义中的第一个单词。 正确代码和错误代码之间的区别不仅是因为正确代码不包含错误，尽管这是绝对必要的。 即使是无法完全理解其功能的代码，也可能是不正确的，如果它是无法理解的，或者存在一个选项，它的含义并不太清楚，但是运行得更快，或者执行得很快，但是编写得更清楚，因此正确性的概念在某种程度上是相对的。 我们继续考虑我们的缓冲区实现示例，这将使我们能够证明不同正确度之间的差异。

在本质上，首先要进行进一步讨论。 我的意思是您的编译器始终以非零（-O2）otpimization级别打开，因此我们不必考虑较小的改进，例如1）前缀修改与后缀，或者2）使用上一个操作的结果，或者3）增量与加法之间的差异单位等等-我们假设编译器会为我们做很多事情。 当然，这不是一个严格的假设，但是否则我们将不得不陷入汇编程序的肠子，而在我们这个时代，汇编器并不是主流。

让我提醒您，我们被指示实现环形缓冲区的索引（指针），也就是说，我们需要创建一个变量的行为，该变量的行为从一系列初始值到一些final值依次执行 。 立即假设初始值为零，否则我们将立即不得不编写或多或少正确的代码，这与教育目标相矛盾，我们不着急，最后一个是Max。

变量的此行为可以使用以下构造实现：

volatile int Counter = 0; Counter = (++Counter) % (Max+1); 

正是这样的代码，我们可以在很多情况下（经常）看到。 出问题了–首先，一段时间（从执行增量操作到分配结果），我们的变量将大于最大允许值，如果此时发生中断，需要考虑该变量的值，那么我个人会预测我不假定结果。 因此，我们重写程序：

 int Counter=0; Counter = (Counter + 1) % (Max + 1); 

我们已经消除了一个错误，并且代码（在下文中，我将表示代码“可执行”是指由编译器生成的可执行代码）并没有变得更长且不再执行（实际上，它执行得更快，但这仅是因为在第一个版本中volatile一词在这种情况下是完全多余的），并没有变得不太清晰（相反，甚至更加清晰，但这是一个品味问题）。

关于volatile的必要说明-如果我们要避免导致优化执行不正确的代码优化，并且在这种特殊情况下（当变量的值在模块范围内没有变化并且其中没有顺序条目时），则需要使用此伪指令）完全多余。 我强烈建议您在godbolt.org上查看两个选项的生成代码。 为什么不应该滥用volatile伪指令，与static关键字不同，建议尽可能使用它。 好吧，首先，我们禁止优化，也就是说，代码绝对不会变得更快（很可能会变得更大或更慢，但是我们更喜欢严格的表述）。 其次，在这种特殊情况下，该词具有误导性，因为相对于我们的程序，计数器的值绝不会在我们的控制范围之外变化。 在读取其值的程序中（即，在环形缓冲区本身的实现中），您可以将计数器视为模块外部可变的，这是有问题的，因此该属性根本不适用于计数器。 如果一个变量在不同模块中的解释不同，则我们的服务应该合并，如果我们正在讨论组织一个关键部分，例如，在执行事务或原子操作时，则该指令根本不给出任何内容。

我们返回代码，发现程序仍然是错误的-怎么回事-事实是它不是我们所需要的（请参阅任务说明），而是其他内容（计算除法的余数），仅是结果匹配。 好吧，我们这样认为（我认为不是，但是代码的作者肯定如此），结果是一致的，实际上，在一般情况下，它们并不一致，我们只是很幸运地知道变量的范围（正值）。 此外，代码执行过程比完成过程要长，因为充其量我们只有一个整数除法运算（如果它是我们体系结构命令的一部分），并且它绝不会在一个处理器周期内执行（典型值为10个周期）对于8位架构），在最坏的情况下，我们将看到来自标准库的除法过程调用（如果是短除法的话），那么执行时间将是数十个时钟周期。

因此，为什么仍然会经常遇到这种完全错误的方法。 在听众那里，他们告诉我，使用Max +1的值（是2的幂），编译器将猜测而不是除法运算，将按位乘法运算放在相应的掩码（等于Max）上，这将很快执行并且一切都会很好。

如果不适合以下情况，我将同意这一说法并采取这种方法：

• 这仅适用于在编译阶段静态定义的Mach，
• 仅在启用优化后才会发生这种情况，
• 只有当马赫达到这个条件时，
• 并非所有主要类型都发生这种情况。

而且，在这种特殊情况下（当变量定义为符号时），除了将掩码乘以（逻辑）的命令外，还会生成一个比较命令，该命令带有零和一个负值分支，尽管该分支永远不会属于我们的范围它会被执行，它将占用内存中的空间（如果是可替换功能，则将需要数次），并且需要花费一些时间来执行比较操作，如果您不相信它，那么我们将再次前往指定的站点并亲自进行查看。 另一个支持未签名红衣主教的论点，我最近专门讨论了整个职位。

因此，如果要使用带掩码的逻辑乘法（通过优化余数的计算获得），则应相应地重写模块：

 typedef uint8_t Counter_t; typedef int8_t sCounter_t; static inline Counter_t NextCounter(const Counter_t Counter) { #if IS_POWER2(Max + 1) return (Counter + 1) & Max #else return (Counter + 1) % (Max + 1); #endif }; 

在此版本中，所有内容都是完全清楚且可控制的，并且都是真实的（尽管仍然存在许多缺点，但现在很明显并且没有被掩盖），因此它是正确的，尽管它是更正确的，我们现在将寻找它们。 我认为主要的缺点是违反了KISS原则，因为按除法使用余数运算会完全忽略该原则。 因此，我们现在将一击消除所有缺点（不必担心它们的命运，它们将重生100,500次，因为并非所有Arduino程序员都读过我的文章）。

但首先，侧面会略有偏差。 我们如何实现刚刚使用的2的幂（二进制数可以表示为{0} 1 {0}）的校验


以及如何实现以二进制表示数字为单位{0} 1 {1}的正确序列的验证-一个选项很明显

 #define IsRightSequence(N) IsPower2 ((N) + 1) 

第二个是微不足道的

 #define IsRightSequence(N) ( (((N) + 1) & (N)) == 0) 

注意：我不禁想起一个宏伟的定理：“一个超越度的超越数总是超越的，除非相反是显而易见的或微不足道的。”

以及如何验证数字是单位序列{0} 1 {1} {0}

 #define IsSequence(N) IsPower2( (N) ^ ((N) << 1)) 

最后-如何选择一个数字的最低有效位（我不知道为什么这是必要的，但会派上用场）

 #define LowerBit(N) ((((N) - 1) ^ (N)) & (N)). 

但是他想出了可以派上用场的东西

 #define IsRightSequence(N) (IsSequence(N) && (LowerBit(N) == 1)) 

一个奇怪的发现-这些宏不是很正确，事实证明0既是2的幂，又是正确的序列（当然也是一个序列），这有点奇怪。 但是，所有这些对象中的1是非常正确的，因此看来零是需要单独考虑的。 这些宏的另一个有趣特性是，我们不对参数的长度做任何假设，也就是说，它们可以与任何基数类型一起正常工作。

有一本很棒的书，《程序员的技巧》，在这里您可以找到提到的宏以及许多其他同样有趣和有启发性的任务，我强烈建议您阅读它，尤其是因为其中没有太多字母。

但是回到我们的环形缓冲区索引。 我们提供了正确的解决方案，但承诺更加正确，这意味着我们的最后一个解决方案存在缺陷（谁会对此表示怀疑）。 其中一个-缓冲区的长度应在编译阶段静态确定，第二个-如果长度不成功，则执行时间非常长，并且在较小的程序段中仍然存在一定数量的错误，这使我们想起一个笑话，用4个错误写``更多''一词。 我们将消除它们（稍后将保留一些），为此，最后，我们将写出原始问题的解决方案，如下所示：

 static inline Counter_t NextCounter(const Counter_t Counter) { if ((Counter + 1) > Max) { return 0; } else { return Counter + 1; }; }; 

（正如您已经了解的那样，我是埃及方括号的支持者，因此无需采取任何措施）。

让我们注意一个事实，我们只是用选定的编程语言从自然语言中重写了问题的状况，因此事实证明它非常清晰易懂。 是否有可能改进它-毫无疑问，仅从代码性能的角度来看，因为此解决方案根本没有其他缺点（没有明显的缺点，实际上是，我们将成功消除它们）。

让我们评估该解决方案的计算复杂性-始终加1（1）和比较（2），然后赋值零（1）（很少）或加（1）（几乎总是）-这给出1 + 2 + 1 +Δ〜4基本操作和零内存。 一个好的编译器在正确的模式下可能会进行某些优化，并减少代码执行时间，但最好是显式地进行。 这是以下选项：

 static inline Counter_t NextCouner(const Counter_t Counter) { register sCounter_t Tmp; Tmp = (Counter + 1); if (Tmp > Max) { Tmp = 0; }; return Tmp; }; 

我们评估复杂性-始终进行加法和比较，很少分配零-大约3次操作和1个存储元素。 实际上，先前的版本还具有一个存储元素（隐式），因此我们在一个基本操作中获得了净收益。 此外，以前的版本还有两个缺点-1）违反了DRY原理（计算增加了两倍），并且2）拥有多个出口点，这不好。 我们也没有失去了解，也就是说，我们设法一枪杀死了一群兔子，我们也没有花任何弹药，这只是芒特豪森男爵风格的一个故事。

请注意，我没有使用if ( (Tmp = Counter + 1) > Max)构造，尽管它包含了向编译器的明确指令，以尽量避免进行多余的传输。 这是最公然的形式，我只是不喜欢赋值运算符返回的值，并尝试避免使用它。 我无法解释这种强烈感觉的原因，据弗洛伊德说，这很可能是儿童时期的心理创伤。 现代编译器完全有能力自行进行简单的优化，此外，我还添加了一个寄存器限定符，以便使我的版本和正确的代码（从C语言的角度来看）匹配。 但是，我完全不限制您使用似乎更适合您的方法的自由。

我们不断改进，因为对完美无止境，而我们尚未达到完美。 为了实现这一目标，我们对原始问题进行了一些重新表述，只保留了变量的要求在值的范围内，而没有指出变化的方向。 这种方法使您可以如下重写程序

 static inline Counter_t NextCouner(const Counter_t Counter) { register Counter_t Tmp; Tmp = (Counter - 1); if (Tmp < 0) { Tmp = ; }; return Tmp; }; 

乍一看，没有什么太大的变化，但是，尽管如此，我们仍能及时获得收益。 当然，并不是由于减少一的操作比增加一的操作更快（尽管我听过类似的说法），而是由于比较的特殊性。 如果在以前的版本中，我将比较视为2个基本运算（首先我们减去然后做出决定），那么在这种情况下，将先前运算的结果直接用于做出决定，而比较则采用一个基本运算，这导致始终执行两个运算并分配一个（很少）并且我们保存了一个操作（不丢失任何内容），俗话说，“琐事，但很好。” 最终的解决方案是否理想-不幸的是，没有。 就速度而言，它略逊于带有遮罩的解决方案（它仅需要2个基本操作），这也许是它的唯一缺点。

有一个更快的解决方案-仅增加（减少）计数器值，而无需执行其他任何操作，但是只有在最大值与可接受类型中最具代表性的值一致时，才有可能。 对于一个8位计数器（即uint8_t类型），它将为255，那么我们只需编写Counter = Counter + 1并相信我的话，编写Counter + = 1或++ Counter是完全可选的，尽管很多他们会写，而且绝对正确。 如果我们不认真考虑需要保存字符的版本（因为第一个选项最长），那么这毫无意义，至少如果我们正在编写用于ARM或AVR架构的程序（对于我刚才没有检查过的其他程序，我怀疑结果会是相同）在GCC编译器下（作者理解他们是在集成编程环境的编辑器中编写程序，这只是过去计算机大而内存小的一次演讲革命），并且在任何级别都启用了优化功能，因为 给定的代码将完全相同。

如果启用了相应的模式，那么现代编译器在优化方面非常非常先进，并且会生成非常好的代码。 尽管我准备同意这样的语言构造不会造成任何损害，并且在某些条件下可能有用，但是我唯一要注意的是，应明确避免使用Counter ++表达式（当然，在这种情况下），因为它打算用于完全不同的情况，并且可能引起较慢的代码，尽管是可选的。

另一个问题是256元素的缓冲区并不总是可以接受的，但是如果您有足够的内存，那为什么不可以。 通过此实现，如果您可以将缓冲区与页面边界对齐，则可以通过消除从索引到索引的移动来非常快速地访问元素（union关键字将告诉您该功能的实现，我不会为了避免学习而带来它坏），但这已经是一个非常非常具体的决定，并且对建筑有着很强的依恋感，这在最糟糕的意义上非常接近技巧，这不是我们的风格。

当然，没有人禁止我们根据最大（和最小值，因为许多方法根本无法使用非零最小值）计数器值来调用该方法或该方法，因此我已经提出了这种解决方案的基本原理，因此我们将以此为练习。

好吧，总而言之，总结一下-我们将使用环索引将工作的不同实现组合在一起，并评估它们的属性。

括号中的第二行显示了该实现可用的缓冲区大小值（不超过256个）的数量，但是我们的意思是大小为0的缓冲区对我们不感兴趣。

从该表中可以看出，DarZaNeBy（我最喜欢的表达方式，您可能已经注意到了），而优势是以劣势为代价而购买的，唯一可以明确地说的是，通过验证递增的竞争者以通过验证递减的形式拥有更成功的竞争者，因此不会进入下一轮在任何情况下都不会。

需要注意的是-有些编程语言根本不需要考虑索引的实现，而只是可以使用间隔类型。 不幸的是，我无法将这些结构的实现称为最佳代码，因为这些结构（和这些语言）并非旨在在运行时进行优化，但这很遗憾。

因此，我们选择了正确的模块（内联函数的好名字）来使用索引，现在我们准备开始实现环形缓冲区本身。

对于初学者来说，我们应该确定我们到底要从该程序对象获得什么。 绝对有必要能够将数据元素放入缓冲区中并提取它-两种主要方法，一种getter和setter。 从理论上讲，可以想象没有这些方法之一，甚至没有这两种方法的缓冲区（几乎完全可以从理论上想象），但是这种实现方式的实用价值是一个大问题。 接下来的必要功能-检查信息-可以实现为单独的方法，也可以实现为通过读取返回的特殊值（或属性）。 通常，他们更喜欢第一种方法，因为事实证明它更容易理解且不太昂贵。
但是检查缓冲区的完整性已经是一个很大的问题-此操作将需要额外的时间，尽管没有人强迫我们使用它，但它总是会花费在记录上-顺其自然。 我们不需要缓冲区中的任何其他内容，请记住这句话，以备将来使用。

返回执行。 我们需要一个存储队列元素的位置和两个索引-一个用于写入缓冲区，另一个用于读取缓冲区。 我们如何精确地获得这个位置（以及这些指针）是一个单独讨论的主题，现在，让我们将这一刻放在括号中，并相信我们只是拥有它们。 有些人（包括我尊重的“我为数学家编程”一书的作者，我建议阅读）也使用填充的位计数器，但是我们不会这样做，我将尝试说明为什么这是邪恶的。

首先，关于索引-我们立即注意到它们是索引，而不是指针，尽管有时我允许自己这样称呼。 ( ), ( )- , , , . ( 256 ), , , ( , 8 , , 4- ), , , ( , ).


, , . , ( , , ), — .

— ( ), . : 1) , 2) , . , , , . , , . ( ) , — . — , .

(«, ») , . — 1) , 2) ( , ) 3) , , 4) 256 , 5) ( ), . , , , , .

, (, , ), 1 . :

 #define NeedOverflowControl YES typedef uint8_t Data_t; static Data_t BufferData[Max]; static Counter_t BufferWriteCounter=0, BufferReadCounter=BufferWriteCounter; void BufferWrite(const data_t Data) { BufferData[BuffWriteCounter] = Data; register counter_t Tmp = NextCount(BufferWriteCounter); #if (NeedOverflowControl == YES) if (Tmp == BufferReadCounter) {BufferOverflow();} else #endif { BufferWriteCounter = Tmp; } }; 

, , … , :

  inline int BufferIsEmpty(void) { return ( BufferReadCounter == BufferWriteCounter ); }; inline int BufferIsFull(void) { return ( BufferReadCounter == NextCounter(BufferWriteCounter) ); }; #define DataSizeIsSmaller (sizeof(data_t) < sizeof(counter_t)) data_t BufferRead(void) { #if DataSizeIsSmaller register data_t Tmp = BufferData[BufferReadCounter]; #else register counter_t Tmp = BufferReadCounter; #endif BufferReadCounter = NextCount(BufferReadCounter); #if DataSizeIsSmaller return Tmp; #else return BufferData[Tmp]; #endif }; 

, ( ) — , , , — , . , , , .

, , — , , , .

, ( )

1) ( — , , — , , ).
(, , )

2) — , .

:

3) 4) , (« »). — , , ( N N+1 ) , ?

3) ,

4) .

— « », - , — . 3, ( ), , .

— , ( , ),

5) — , , , , — , .

— , , .

, , , , , , , , , , , . , 4 , , . MRSW (Multi-Reader Single-Writer) «The Art of Mulpiprocessor Programming» ( , ) ( ) . — , , .

MRMW , «» (, , « » ). , , , , . , , , (, , — , , , ), .

, ( ) , . , , , , , , , .

 typedef uint8_t data_t; static data_t BufferData[Max]; static counter_t BufferWriteCounter=0, BufferReadCounter=WriteCounter; static int8_t BufferHaveData = 0; void BufferWrite(const data_t Data) { if ((BufferWriteCounter == BufferReadCounter) && (BufferHaveDataFlag == 1)) {BufferOverflow();} else { BufferData[BufferWriteCounter] = Data; BufferHaveDataFlag = 1; BufferWriteCounter = NextCounter(BufferWriteCounter); }; }; inline int BufferIsEmpty(void) { return ((BufferReadCounter==BufferWriteCounter) && (BufferHaveDataFlag == 0));}; data_t BufferRead(void) { register counter_t Tmp; Tmp = BufferReadCounter; BufferReadCounter = NextCount(BufferReadCounter); if (BufferReadCount == BufferWriteCounter) { BufferHaveDataFlag = 1; }; return BufferData[Tmp]; }; 

, , , , , .

, ( 0 1, , , ), , , , , , ( ), , ,


, , 0 1, . , , , 0 1. , , , , BufferFullFlag , BufferIsNotEmptyFlag . , KISS , , , , , « ».

, , .

, , .

PS , , :

1. — (, , ), — , , , , .
2. .
3. .
4. 2 .
6. , ( ) , , .
7. ,
   
   

    return ((_writeCount - Atomic::Fetch(&_readCount)) & (size_type)~(_mask)) != 0; 

   
   — , , ,
   
   

    size_type(~(_mask)) 

   
   .

PPS , .