Forums

嵌入式系统的数据记录器

开始于 steven02 2 years ago21回复最新回复2年前294意见

大家好,

I 一直面临以下问题。我已经实现了一个数据记录器 即在MCU上运行的软件,该软件会定期创建快照 系统状态(系统某些数量的值)。这些快照 存储在外部闪存的循环缓冲区中。本通函 缓冲区导致最早的快照被最新的快照覆盖 期望的行为。另一个要求是 如果重新启动MCU,数据记录器也必须正常工作。到期 为此,需要一种机制来识别 外部闪存中已存储了最后一个快照。

我有 决定通过以下方式满足此要求。外部 闪存分为512个字节的扇区。所以我 将几个快照收集到一个块中,然后附加所谓的标头 在此块的开头。一开始我决定只使用8 外部闪存的扇区,因此标题包含的块号为 goes through values 1,2,9. 该算法效果很好,但仅适用于小尺寸的圆形 缓冲。如果我将循环缓冲区的大小扩展到几个 数千个块(外部闪存包含\( 2^{23} \) 部门) 我发现,创始部门继续从事下去所需的时间 MCU复位后快照的存储时间过长。所以我 一直在寻找另一种解决方案,如何找到继续发展的领域 更快地重置MCU后,将其存储在快照存储中。

有人知道吗?感谢您的任何建议。

#数据记录仪 #flash

[-]
回覆者 杰加特曼2019年3月10日

史蒂文你好

如果要使用单个扇区或几个扇区来存储对下一个写入位置的引用,则这些扇区的磨损率很高。磨损是由擦除而不是书写引起的。 (因为您必须先擦除才能覆盖。)我建议以下方法很有价值。

闪存字节的擦除值为0xFF。您可以通过将位写入零值来对其进行写入。您可以一次写入一位至零来擦除同一字节8次,而不会擦除。您可以将此想法扩展到整个部门。一次只写一位到零。您可以按扇区大小乘以8位来覆盖相同的扇区。

因此,如果将闪存大小除以扇区大小,则听起来像是512字节* 8位= 4096位。换句话说,将闪存大小除以4096,每次超过该增量大小时,仅将一位写入零。然后,在重新启动时,您将查找“位索引扇区”中的位置,并且仅需像现在一样从该点开始搜索写点。这种方法的好处是,在闪存充满的每个周期中,您只需擦除一次位查找扇区。这意味着该位查找扇区的损耗级别与闪存的其余部分完全相同。在扇区写入和更新位查找扇区的过程中,此方法还可以防止电源故障。只需先更新扇区,再写入即可。如果两者之间电源中断。您将搜索更长的时间。


问候

约翰·哈特曼


[-]
回覆者 steven022019年3月10日

你好约翰,


谢谢您的回答。我不确定我是否理解你的有趣想法。您是说我应该分配几个扇区来创建一个大位数组吗?这个大位阵列中的每一位将对应于数据记录的主缓冲区中的一个扇区。每当我写入主缓冲区时,我都会将位数组中的一位清零。可以基于大位数组中零位的数量来确定主缓冲区中的下一个空闲扇区。我的理解正确吗? 

[-]
回覆者 杰加特曼2019年3月10日

史蒂文你好

我认为您已掌握要点。

这个想法是通过使用单个扇区或两个扇区中的位数组中的零位来减少启动时的搜索空间。

假设您的闪存为2 ^ 24字节或16兆字节。  

512字节的扇区为2 ^ 9,每个字节8位为2 ^ 3,从而为您提供2 ^ 12或4096位。代表512字节扇区的4096位表示:您可以除以2 ^ 24 = 16777215/4096 = 4096或2 ^ 12。这代表8 * 512byte扇区。因此,在这种情况下,在单个扇区中使用位阵列意味着您可以查找偏移量,并且在启动时只需搜索8个扇区以获取当前的写入位置。

或者,按照自己的方式做。一位代表每个512字节的扇区。这意味着您有2 ^ 15个扇区或32767个扇区。一个扇区中有4096位可用,这意味着8个扇区为您提供了足够的位,可以在位表中直接查找您当前所在的扇区。

因此,您可以交易部门以获取启动时间。

诀窍是要认识到,如果您只想将状态从“ 1”写入状态“ 0”,就不必擦除闪存中的扇区。您基本上可以覆盖并获得所需的内容。

希望这有助于更好地解释事情。

问候

约翰 

[-]
回覆者 steven02三月11,2019

你好约翰,

我的英文不是很好。所以我试图通过下面给出的图片表达我的当前理解。 

trik_s_bitovym_polem_83527.jpg

据我正确理解的聪明的想法,它根据图片假定闪存的组织,即,一个位用于位数组,八个扇区用于辅助循环缓冲区,其余部分用于数据记录器。 

第一次使用前,位阵列扇区和创建辅助缓冲区的扇区包含所有0xFF。随着时间的流逝,数据记录器开始工作,主缓冲区中的扇区逐渐被填充。一旦主缓冲区中的一个扇区被填充,辅助通道中第一个扇区中的一个位就会被填充。缓冲区被清除。每当辅助部分中的整个第一部分。清除缓冲区bits数组中的一位。 

我的理解正确吗? 

[-]
回覆者 mr_bandit三月11,2019

也许一个例子会有所帮助。

扇区0是您的“头部扇区图”。扇区1-8是您的数据扇区。

Init正在将0xFE(1111 1110)写入扇区0,并将某种标头写入扇区1.(如果您要为每个扇区存储多个数据包,则扇区标头可能也具有相同类型的位字段对于下一个空闲(或最后填充)的数据块)

您已准备好编写数据块。扇区0 == 0xFE,它映射到扇区1(这是一个位字段,不是计数)。读取扇区1中的标头,确定要在何处写入数据块,将其写入并更新扇区标头。

您填充扇区1。将0xFC(1111 1100)写入扇区0。

在下一个数据块中,您读取扇区0 == 0xFC ==使用扇区2.将``新的''扇区标头写入扇区2。

如果有帮助,请在要使用位字段时对其进行补码。在这种情况下,扇区位图== 0xFE(1111 1110)=> 0x01 (0000 0001).

现在,您包装了整个闪光灯。您需要重新初始化扇区0位图和扇区1标头。

当您阅读闪存(转储日志)时,您会知道某个扇区是否有数据,因为扇区标题看起来正确-请使用一些数字作为标题ID(类似于0xDEAD或xBEEF或xABBA(取决于音乐品味))。另外,使用某种时间戳来初始化扇区头,以帮助使事情井井有条(无论如何,数据记录器都需要这样做)。

现在,正如jeghartman所指出的,您可以使用字节数组作为映射。扫描该阵列(应该在ram中具有镜像副本)的速度很快,可以找到起始扇区。

[-]
回覆者 mr_bandit三月11,2019

另一个把戏。

具有主扇区头和当前扇区头+数据(即整个扇区的缓冲区)的ram副本。

在新的初始化(从未引导)上,将您的扇区0映射和扇区1标头写入ram版本。将所有内容写入ram副本后,将RAM刷新到FLASH。

引导时,将扇区0读入其ram缓冲区以确保它已被初始化&&找到要写入的起始扇区。将起始扇区读入​​其ram缓冲区。

根据需要对RAM版本进行更改,然后刷新到闪存。此方法称为“直写式高速缓存“。这样可以最大程度地减少写入次数和写入时间。

根据闪存的类型(例如,您一次可以写入一个字节,还是整个扇区),可以将扇区缓冲区视为字节数组。通过ram缓冲区作为字节数组运行,从闪存读取相应的字节。如果不是==,则将ram字节写入闪存字节。

注意:将整个内存缓冲区写入闪存可能会更快。查看写入时间。还可以测量并实际测量时间。

保持“肮脏的位”。如果您向ram缓冲区写入内容,请设置脏位(实际上只是一个二进制标志)。如果您正在使用命令循环,则在循环结束时,您会知道是否需要将RAM写入闪存。

[-]
回覆者 杰加特曼三月11,2019

嗨,史蒂文。

英语也不是我的母语,所以没有问题。

您正确理解:您可以按照上一个段落中的描述进行操作。 

但是您确实只需要一个扇区大小的bit数组即可。在这种情况下,您将在已填充的主循环缓冲区中每8个扇区将另外一位写入零。在这种情况下,重新启动时,将使用零位数乘以8扇区= 4K作为搜索写指针的开始。您需要搜索以下8个扇区才能找到它。  

或者,您使用大小为8个扇区的位数组。在这种情况下,零位的数目给出了您需要在其中搜索写指针的确切扇区。

为您的实施。请记住,您可以在8位处理器上一次比较8位,也可以在32位处理器上一次比较32位。请记住,一分为二等于``右移一'',二乘等于``左移一''。

在位数组中搜索零位结束和一位开始的当前点或字节。您不必进行线性搜索。您可以取“总位数组大小”(以字节为单位),然后将其除以2,以得到数组的索引。此时比较字节如下:

如果此索引处的值==到0x00,则写点位于该索引上方。

如果此索引处的值==到0xFF,则写点位于该索引下方。

否则,您所在的字节包含从0bit到1 bit的变化。

然后接受以上比较的答案,即新的一半大小的块并再次执行该过程,找到此新的减小大小的块的中间字节,并如上所述比较其值。

根据需要重复,直到达到“其他”条件。

上面的方法类似于找到函数的根(零交叉)的Newton Rapson方法。看到

//en.wikipedia.org/wiki/Newton%27s_method

如果您不理解我的描述。

这是在启动时扫描bits数组以找到您的写索引的最快方法。

问候

约翰·哈特曼  

[-]
回覆者 轻微2019年3月10日

你好史蒂文,

我不知道我是否正确理解了您当前的设计。
所以可能是我所描述的与您所做的完全相同-
就在我脑海中,我会做以下事情-

Flash中的布局:

use_next slot_1 slot_2 slot_3 slot_4 slot_5 ... slot_n
slot_3 data_1 data_2 data_3 data_4 data_5 ... data_n

在闪存的第一个位置中,您存储了下次要写入的位置。

这样,您只需要查看闪存中的一个已知地址即可知道将数据写入何处...我无法想象更快的方法。
您的“ use_next”字段的大小必须适合您的最高“插槽数”。
您的“ slot_n”字段的大小必须适合您的内容。

如果您可以使用扇区或块或其他某种形式的闪存,或者可以一次性读取/写入的大小,则可以使其更快。 


如果我所描述的是您当前的系统,我不知道在插槽数量增加的情况下需要花费更长的时间...
我想您必须向闪存“写入”命令以设置下一个数据写入的指针。
但这对于以后的地址确实不是时间问题...

最终定义“不可接受的长时间”是有意义的-您是在说分钟/秒/毫秒/微秒吗? ;-)

阳光明媚的问候

斯蒂芬

[-]
回覆者 慕尼黑2019年3月10日
如果您使用一个或多个扇区来跟踪当前的开始/结束扇区,请务必记住,该扇区在每次充满时也需要删除,并且在擦除过程中,电源循环将丢失其数据(因此需要长时间搜索以重新建立其指针)。因此,它需要使用交换块技术或类似技术,以便在处理过程中指针永远不会丢失。
[-]
回覆者 steven022019年3月10日

你好斯蒂芬,


谢谢您的回答。我当前的实现不直接存储下一个使用的扇区。 MCU复位后,通过遍历外部闪存中的整个循环缓冲区并在标题编号中查找意外的“跳转”,来确定下一个使用的扇区。 

据我正确理解您的想法,您建议使用外部闪存中的一个扇区来存储下一个使用的扇区。因此,每当我需要存储另一个数据块时,我都会从该位置读取下一个扇区。这是对的吗?

[-]
回覆者 马修巴尔2019年3月10日

史蒂文你好

不久前,我编写了与您描述的基本上相同的Flash记录器。圆形缓冲区插槽的总数并不大,因此线性搜索最大序列号以及校验和验证足以确定加电时从何处开始写入。

对于大量缓冲区插槽,二进制搜索样式算法可以帮助您在可接受的少量时间内找到跳转位置。考虑以下示例,该示例在循环缓冲区中有16个插槽,而这些标头号在插槽0到15中:

16 17 18 19 20 21 22 23 24 25 26 27 28 13 14 15

通过查看插槽0和7(16、23)中的第一个/最后一个标题编号,您可以轻松确定标题编号中没有意外的跳转,因此您可以查看插槽8和15(24、15 ),您知道循环缓冲区的后半部分会有跳跃。

现在查看插槽8和11(24,27)中的标头编号,并且没有跳转,因此查看插槽12和15(28,15)中的标头编号,并且存在跳转。

继续直到您下降到两个插槽或少数几个可接受的插槽,然后线性扫描这些插槽以查找跳转。这应该使您接近O(logn)性能,而不是O(n)。对于4096个块,我认为您会获得类似于44个块的线性扫描的最坏情况性能:2 ^ 12 = 4096,因此要进行11个拆分才能减少到2个插槽,您必须查看两个插槽头(第一个/最后)在每个拆分中,最坏的情况是您必须查看每个拆分的两半。如果两个拆分中没有跳转,则说明拆分之间有跳转,或者标题序号完全正确(从插槽0开始)。

如果缓冲区插槽的数量为2的幂,则可能更容易实现,但这不是必需的。这样做的好处是通常与您现在所做的工作兼容,仅涉及启动搜索算法的更改。您不必为单独的主索引添加存储和处理,也不必在每次数据更新时都更新索引。

如果您要使用主索引方法,那么Johan Hartman的方案非常聪明,因为它避免了索引信息的磨损问题,并且对意外的断电不敏感。毫无疑问,这种主索引方案将为您提供比我建议的性能更快的启动搜索性能,尤其是如果您对位索引数据进行二进制搜索以获取1/0边界时。

[-]
回覆者 steven02三月11,2019

你好马修,

非常感谢您的回答。我喜欢你的主意我为缓冲区由8个扇区组成的标题准备了一系列标题号(标题号经过1,2,... 8,9),并且填充从擦除的闪存开始:

0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0

1 2 0 0 0 0 0 0

1 2 3 0 0 0 0 0 

1 2 3 4 0 0 0 0 

1 2 3 4 5 0 0 0

1 2 3 4 5 6 0 0

1 2 3 4 5 6 7 0

1 2 3 4 5 6 7 8

9 2 3 4 5 6 7 8

9 1 3 4 5 6 7 8

9 1 2 4 5 6 7 8

9 1 2 3 5 6 7 8

9 1 2 3 4 6 7 8

9 1 2 3 4 5 7 8

9 1 2 3 4 5 6 8

9 1 2 3 4 5 6 7

8 1 2 3 4 5 6 7

8 9 2 3 4 5 6 7

8 9 1 3 4 5 6 7

8 9 1 2 4 5 6 7

8 9 1 2 3 5 6 7

8 9 1 2 3 4 6 7

在这种情况下,从最后一行中的9跳到1是由正确环绕引起的“误导”跳转。我一直在寻找正确的跳跃是从4到6的跳跃。在我看来,我无法通过您描述的算法来区分误导和正确的跳跃,还是我错过了一些重要的想法?

[-]
回覆者 马修巴尔三月11,2019

有趣。不知道有什么更好的选择,我假设您正在寻找与最近写入的标头关联的环绕边界,因此您可以从那里继续写入。

我认为该算法可以与您拥有的编号方案一起使用,但是请参阅下面我单独的后续评论,我认为您的编号方案有一个调整,消除了跳过,仅保留了环绕边界。

使用现有的编号方案,您将找到所需的环绕边界和跳跃,并且必须修改算法以忽略环绕,除非它与跳跃重合。当您查看第一个/最后一个标题编号时,您有N个插槽 最后==第一+ N-1,您知道您有一个连续的标题编号块。如果该测试失败,那么我认为您有两种情况。 1) 第一的< last 这应该表明您关心的跳过动作,尤其是在 最后==第一+ N. 2) 第一的> last 在这种情况下,您肯定有一个环绕边界,并且您可能还会跳过,因此必须进行拆分和分析。如果您有除回绕和(N,N + 2)跳过以外的其他情况,则必须在第一个/最后一个测试中处理它们并分析逻辑。

这将增加一些搜索开销,但是在最坏的情况下,您应该保持O(logn)的速度运行,并且比暴力线性搜索要快得多。

如果您知道一个跳跃可能只有1个,并且跳跃始终总是显示为(N,N + 2),那么看来当您看到第一个/最后一个关系时 最后==第一+ N 您知道其中包含没有回绕的跳过,并且可以忽略拆分的另一半。

还会有其他情况,例如:

8 9 2 3 4 5 6 7

这里的环绕是跳过的兴趣。当您看到first / last = 8/3时,您将获得两个分割,其中first / last 8/9和2/3,并且跳过位于最后两个分割之间。

您也有这种情况:

9 1 3 4 5 6 7 8

当您看到first / last = 9/4时,您会得到两个分割,first / last 9/1和3/4。同样,跳过是在最后两个拆分之间。我认为这些特殊情况在某种程度上是您处理标头编号的方式的产物。

[-]
回覆者 马修巴尔三月11,2019

一想到标题号,我想有一种方法可以消除“跳过”的情况,因此您只需要检测一个非顺序的标题号边界即可。假设您有N个插槽,其中N是2的幂。让您的标头编号从0到2N-1,并且让标头编号从上次中断的地方恢复,而不是从标头编号1重新开始。假设N = 8,标头编号从0到15。

9 10 11 4 5 6 7 8

找到11/4边界,并在下一次更新后具有:

9 10 11 12 5 6 7 8

让我们假设您还有6个更新:

1 2 11 12 13 14 15 0

您现在有两个边界,2/11和15/0。在这里,您将认识到15/0边界是正常序列,请忽略它。如果您拆分了m个标头(例如first / last为13/0,m = 4)和last<首先,您可以测试一下last + 2N == first + m-1。在测试连续的报头编号时,这基本上会针对2N模的回卷进行调整,并且应适用于包含15/0边界的任何拆分。因此,您有两种情况用于顺序标头编号测试:

1)首先<上一个:上一个==第一个+ m-1

2)首先>持续时间:持续时间+ 2N ==持续时间+ m-1

如果看不到这些情况,则说明您关心的是非顺序边界。请注意,您仍然必须检测并处理边界位于两个拆分之间的情况,例如在上面的``6次更新之后''情况下,在1/2和11/12之间。

由于标题编号从0开始,因此您可以考虑将全1的标题编号用作空插槽的初始值。我认为写入/空插槽边界可能自然会落在搜索算法之外。

[-]
回覆者 steven02三月12,2019

我一直在考虑您建议的二进制搜索。我的一个想法是多次使用二进制搜索。在第一次使用期间,我将确定环绕位置,并根据此信息将标头序列分为两个子序列,以供二分查找的另一种用法。在二分查找的另一种用法中,我将确定要查找的跳转的位置。您如何看待这个想法? 

[-]
回覆者 马修巴尔三月12,2019

我认为这样会起作用。我在较早的文章中看到的``跳过''示例中看到的问题是,由于相对跳过vs.环绕距离以及相对于固定重启值1的最后一个标头编号,您需要考虑许多特殊情况这些将使搜索算法复杂化并影响性能。编码和测试将花费更长的时间,并且由于意外的特殊情况而增加了引入隐蔽错误的可能性。

如果您调整标头编号以从其中断处重新开始而不是从1重新开始,则该解决方案将变得更加容易,它使用2N标头编号(0到2N-1)来处理N个缓冲区,并从2N从1返回到0。这完全消除了标题编号的跳过,您可以找到非顺序的标题编号边界并从此处恢复编号。该边界是明确的,并且很容易与环绕边界区分开。

搜索算法是很多清洁器。如果N是2的幂,那么您将获得以下三个结果之一:

1)非顺序边界在结束/开始处(从插槽0开始写入,从最后一个插槽中的标头编号开始)

4 5 6 7 8 9 10 11(最后==第一+ m-1,其中m = N = 8)

11 12 13 14 15 0 1 2(最后+ 2N ==第一+ m-1,其中m = N = 8)

2)您向下工作到具有非顺序边界的2插槽拆分

9 10 11 4 5 6 7 8

3)您将工作分解为两个拆分,每个拆分中都没有非顺序边界,这意味着边界位于两个拆分之间

1 2 11 12 13 14 15 0

11 12 13 14 7 8 9 10

如果N为2的幂,则搜索算法非常简单。在运行搜索之前,首先对情况1)测试插槽列表。然后运行搜索,直到剩下包含边界的2槽拆分或两个都没有边界的拆分对为止。

如果您的总插槽数N不是2的幂,则工作原理几乎相同,除了您可能会以包含非顺序边界的2插槽或3插槽拆分结束。

在我看来,此标头编号方案是一个更好的答案。它消除了跳过,并为您提供了一个明确的,无顺序的边界,可以使用相当简单的二进制搜索算法来定位该边界。

[-]
回覆者 steven02三月11,2019

帖子被作者删除

[-]
回覆者 伊万诺夫2019年3月10日

您在MCU上有EEPROM区域还是带有NVRAM的外部RTC?您可以使用它们定期存储实际的扇区地址并加快搜索速度。

彼得

[-]
回覆者 CustomSarge2019年3月10日

我同意S-Light,但有一个调整:不会将一个“ use_next”位置始终用作下一个数据存储地址,而是将一个扇区用作它们的滚动缓冲区。我将缓冲区称为``索引''和``数据'',其中``索引''是指向``数据''的指针地址的缓冲区。

数据块添加了标题。这是数据输入的序数-如果为16位,则为0-65535。启动时,初始化例程会扫描``索引''缓冲区以查找最高编号-关联的地址为``use_next''。您保存“ index”,“ use_next”和“ index”的地址。

存储下一个块是:获取“ use_next”,放入数据(递增“ use_next”),获取&递增“索引”,得到&增加“索引”的地址,放入新的“索引”,追加新的“ use_next”

在设计时,确定“索引”限制。这将基于数据块大小和可用存储空间。在“索引”限制处,清除一个扇区(大多数闪存具有“扇区擦除”),重置“索引”和“索引”的地址,并存储下一个块。

索引''是唯一需要清除和重置的索引。 “数据”可以永远追尾。它确实需要扇区地址管理来进行翻转。

唯一耗时的例程是初始扫描以查找最后一个条目(最高编号)。由于初始化的结果是当前的缓冲区地址,因此缓冲区的管理仅用于启动,但是会分配地址的写周期。

-----------------------------

通过将序号附加为数据块头,可以将这些组合用于固定块。可变的块长度“可以”做到这一点,其中块为[普通],[块长],[数据块],但是初始化扫描比较棘手。

附言希望这是有道理的-STUPID文本字段抛出了用大于和小于符号括起来的所有内容-我表示标签的标准

[-]
回覆者 steven022019年3月10日

您好CustomSarge,

谢谢您的回答。据我正确理解您的想法,您建议结合使用我的方法和stefan建议的方法。因此,请使用辅助循环缓冲区(其大小较小,以便MCU复位后的初始搜索不会花费很长时间),其中包含下一个使用的扇区和包含数据记录的主缓冲区。

辅助循环缓冲区将以与我用于填充数据日志循环缓冲区的相同机制(即标头和数据)进行填充。还将根据标头值中的意外“跳转”来确定最后一个插入记录(包含下一个使用的扇区)到此缓冲区中。


MCU复位后,将根据从辅助缓冲区读取的下一个使用的扇区来填充主缓冲区,然后仅在程序运行时递增。请您告诉我我对您的想法的理解是否正确?

[-]
回覆者 CustomSarge2019年3月10日

用语言来描述这种东西很困难。我将重新处理,这假定一个固定长度的数据块:

可以使用单独的缓冲区或全部合为一体。我会一并拥护,因为它更易于编写/调试。

块放置:将数据块以其序号(第53位或其他)附加。从ram中获取[DataBuffer]地址,将块放入缓冲区中(将地址作为puts递增),将新的[DataBuffer]地址保存在ram中,递增并在ram中保存新的序数。

初始化:获取第一个缓冲区条目的序号,获取下一个缓冲区条目的序号(如果下一个.GT)。 (大于)第一个,与前一个相同,下一个与下一个进行比较。循环播放,直到下一个是.LT。以前=您是最新的。

地址管理可以采用几种方式:最简单的方法是使用二进制整数块大小(8、16、32等)。这样,扇区结束和过渡地址管理非常简单。最坏的情况是初始化运行时间是跨缓冲区大小/块大小的循环时间(即缓冲区= 1024,块= 8:128个循环)。

如果/当序数接近翻转时,清除缓冲区并将索引重置为0.您还可以在初始化时获取最新条目,将其存储,清除缓冲区,重置索引并将最新块移动到缓冲区库中。最好的方法是特定于任务的:缓冲区&区块大小,区块投放频率和数据上传等<<<)))