是否有EEPROM的微控制器磨损平衡一般的算法？ [英] Is there a general algorithm for microcontroller EEPROM wear leveling?
问题描述
我工作的一个Arduino库，将最大限度地AVR的EEPROM的寿命。这需要你想存储变量的数量和没有休息。这是我的尝试，这并不适用于所有情况。
I'm working on an Arduino library that will maximize the life of the AVR's EEPROM. It takes the number of variables you want to store and does the rest. This is my attempt, which does not work in all cases.
爱特梅尔说，每个存储单元的额定电流为100,000次写/擦除周期。他们还提供应用笔记，其中介绍了如何执行耗损均衡。下面是应用笔记摘要。
Atmel says each memory cell is rated for 100,000 write/erase cycles. They also provide an application note, which describes how to perform wear levelling. Here is a summary of the application note.
通过在两个内存地址写的交替，我们可以增加擦/写20万次。三个内存地址给你30万擦/写周期等。自动执行此过程，一个状态缓冲区用于跟踪何处下一写入应。状态缓冲区也必须是相同的长度的参数缓冲器，因为磨损均衡，必须在其上，以及进行。既然我们不能存储下一个写的指数，我们递增状态缓冲器相应的索引。
By alternating writes across two memory addresses, we can increase the erase/write to 200,000 cycles. Three memory addresses gives you 300,000 erase/write cycles and so on. To automate this process, a status buffer is used to keep track of where the next write should be. The status buffer must also be the same length as the parameter buffer because wear leveling must be performed on it as well. Since we can't store the index of the next write we increment the corresponding index in the status buffer.
下面是一个例子。
<------------------- EEPROM -------------------->
0 N
-------------------------------------------------
Parameter Buffer | Status Buffer |
-------------------------------------------------
Initial state.
[ 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 ]
First write is a 7. The corresponding position
in the status buffer is changed to previous value + 1.
Both buffers are circular.
[ 7 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 ]
A second value, 4, is written to the parameter buffer
and the second element in the status buffer becomes
the previous element, 1 in this case, plus 1.
[ 7 | 4 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 ]
And so on
[ 7 | 4 | 9 | 0 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 ]
要确定进行下一次写，我们来看看两者的差别。如果previous元素+ 1不等于下一个元素然后就是在那里进行下一次写操作。例如：
To determine where the next write should occur, we look at the difference between elements. If the previous element + 1 does NOT equal the next element then that is where the next write should occur. For example:
Compute the differences by starting at the first
element in the status buffer and wrapping around.
General algo: previous element + 1 = current element
1st element: 0 + 1 = 1 = 1st element (move on)
2nd element: 1 + 1 = 2 = 2nd element (move on)
3rd element: 2 + 1 = 3 = 3rd element (move on)
4th element: 3 + 1 = 4 != 4th element (next write occurs here)
[ 7 | 4 | 9 | 0 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 ]
^ ^
| |
Another edge case to consider is when the incrementing values
wrap around at 256 because we are writing bytes. With the
following buffer we know the next write is at the 3rd element
because 255 + 1 = 0 != 250 assuming we are using byte arithmetic.
[ x | x | x | x | x | x | 254 | 255 | 250 | 251 | 252 | 253 ]
^
|
After we write at element 3 the status buffer is incremented
to the next value using byte arithmetic and looks like this.
255 + 1 = 0 (wrap around)
0 + 1 != 251 (next write is here)
[ x | x | x | x | x | x | 254 | 255 | 0 | 251 | 252 | 253 ]
^
|
以上这些例子说明如何延长EEPROM的寿命为一个变量。对于多变量可想而知分割的EEPROM成具有相同数据结构的多个段，但较小的缓冲区。
These examples above show how to extend the life of the EEPROM for one variable. For multiple variables imagine segmenting the EEPROM into multiple segments with the same data structure, but smaller buffers.
我有工作code什么上述我。我的问题是，当缓冲区长度> = 256这是发生了什么。
I have working code for what I described above. My problem is the algorithm does not work when the buffer length >= 256. Here is what happens
Buffer length of 256. The last zero is from
the initial state of the buffer. At every index
previous element + 1 == next element. No way to
know where the next write should be.
<-------------- Status Buffer ------------>
[ 1 | 2 | ... | 253 | 254 | 255 | 0 ]
A similar problem occurs when the buffer length
is greater than 256. A lookup for a read will think
the next element is at the first 0 when it should be at
255.
<-------------------- Status Buffer ------------------>
[ 1 | 2 | ... | 253 | 254 | 255 | 0 | 0 | 0 ]
问题
我该如何解决上述问题？有没有更好的方法来跟踪在那里的下一个元素应该写？
Question
How can I solve the above problem? Is there a better way to track where the next element should be written?
推荐答案
有关一般EEPROM寿命延长的几点思考：
Some thoughts about general EEPROM lifetime extension:
-
EEPROM单元通常以两步操作写入（由硬件）：首先，所述单元被擦除，即，有效地全部设置为1（0b11111111 = 0xff的），要被写入则位（只有那些0）被实际写入。位只能通过一个实际的写操作被设置为0。改变从0到1位需要全细胞被擦除，然后重新写入新的值。
EEPROM cells are usually written (by the hardware) in a two step operation: first, the cell is erased, that is, set to all ones (0b11111111 = 0xff), then the bits to be written (effectively only those that are 0) are actually written. Bits can only be set to 0 by an actual write operation. Changing a bit from 0 to 1 requires the whole cell to be erased and then re-writing the new value.
如果EEPROM单元已经包含将要写入的相同的值 - 其可以是对数据的或多或少的情况下为（重新）写 - 就没有必要写至细胞可言，减少磨损对于写操作0一可能要检查的内容，以决定该细胞是否需要在所有的，而不是老是写了一个新的价值给它写它。
If an EEPROM cell already contains the same value that is to be written to it - which may be the case for more or less of the data to be (re-)written - there is no need to write to the cell at all, reducing wear for that write operation to 0. One might want to check the cells content to decide if it needs to be written at all instead of always writing a new value to it.
上面引出的方法，其中一个小区中的写入前仅擦除，如果有任何的新值，其中所存储的值具有0位（即，如果<$ 1的位的组合C $ C>储值和放大器;！=的NewValue的NewValue ）。有没有必要删除单元格，如果没有0 - 新值所需> 1位过渡（储值和放大器;的NewValue ==的NewValue ）。
The combination of the above leads to an approach where a cell is only erased before a write, if there are any 1 bits in the new value where the stored value has a 0 bit (that is, if StoredValue & NewValue != NewValue). There is no need to erase the cell if there are no 0 -> 1 bit transitions required for the new value (StoredValue & NewValue == NewValue).
AVR具有擦除和写入单独的指令，分别EEPROM单元，支持上述的机制。
The AVR provides separate instructions for erasing and writing to, respectively, an EEPROM cell to support the mechanisms mentioned above.
数据传输到EEPROM的最坏情况下的速度会表演时当然下降的读 - 比较 - 擦除 - 写，而不是仅仅擦除 - 写操作。然而，这具有以完全跳过这可能降低的相对速度罚一些/大多数细胞擦除写操作的可能性。
The worst-case speed of a data transfer to EEPROM will of course drop when performing a read-compare-erase-write instead of just an erase-write operation. However, this has the potential to completely skip erase-write operations for some/most cells which may reduce the relative speed penalty.
有关您的present问题，想想以上几点：为什么不使用单位来存储你的下一个写入位置
For your present problem, think about the above points: Why not use single bits to store your next write position?
例如：
状态缓冲区被初始化为全1：
Status buffer is initialized to all ones:
Bit number: 0123 4567 89AB CDEF
Value: 1111 1111 1111 1111
访问EEPROM中的值之前，要在状态缓冲区中的第1位。该位再$ P $数psents你（圆形）参数缓冲区的当前头的地址。
Before accessing a value in EEPROM, find the first 1 bit in your status buffer. The number of that bit represents the address of the current "head" of your (circular) parameter buffer.
每次提前参数缓冲器，在你的状态缓冲区下位设置为0：
Each time you advance the parameter buffer, set the next bit in your status buffer to 0:
Bit number: 0123 4567 89AB CDEF
Value: 0111 1111 1111 1111
然后
Value: 0011 1111 1111 1111
然后
Value: 0001 1111 1111 1111
等。
这是可以做到的没有擦除整个细胞，只会因而穿的每一次更新您的状态缓冲的单个位 - 如果写入的数据只有一个0位了。结果
要打开，例如，一个存储值 0111 来的新值 0011 要写入的数据应该是 1011 （数据=（为newValue XOR属性oldValue）XOR 0xFF的），剩下的所有位除了单一不变，我们其实是想改变。
This can be done without erasing the whole cell and will thus only "wear" a single bit of your status buffer for every update - if the data written has only a single 0 bit, too.
To turn, for instance, a stored value of 0111 to the new value 0011 the data to write should be 1011 (data = ( newValue XOR oldValue ) XOR 0xff), leaving all bits untouched except for the single one we actually want to change.
一旦状态缓冲耗尽（全0）是完全抹去，而这一切又重新开始。
Once the status buffer is exhausted (all 0) it is erased in full, and it all starts over again.
有一个明确的加分在这里，只有状态的单个位需要每个参数的缓冲区，相比爱特梅尔应用手册仅消耗1/8的存储的单元进行维护。 <击>此外，寻找下一个写入位置也将因为只有在状态缓冲器被需要的读操作的1/8更快（编辑：事实并非如此，因为EEPROM读来几乎零成本的表现-wise，而所需的位移可能需要一些几十个周期）。
A definite plus here is that only a single bit of status needs to be maintained per unit of the parameter buffer, which consumes only 1/8 of the memory compared to the Atmel application note. Besides, finding the next write location will also be much faster since only 1/8 of the read operations on the status buffer will be needed. ( Not true because EEPROM reads come at almost zero cost performance-wise, while the required bit-shifting may take some dozens of cycles.)
另要注意，虽然：你是否认为这是使用256+参数缓冲装置实际上有用吗？与处理时，例如，1024字节的总可用EEPROM的装置上的单位将变得相当小。 - 100000周期乘以256是写操作相当庞大的数目，如果大型的一些似乎是必需的，但可能是不应该被用于此目的不惜一切不对劲的算法或EEPROM。作为替代方案，外部 NVRAM 会在某些情况下是不错的选择。
Another note, though: Do you think it is actually useful to use 256+ parameter buffer units? The units would become quite small when dealing with, for example, 1024 bytes of total available EEPROM on the device. - And 100000 cycles multiplied by 256 is quite a huge number of write operations and if that large a number seems to be required, there probably is something wrong in the algorithm or EEPROM should not be used for the purpose at all. As an alternative, external NVRAM would be a good choice in some scenarios.
访问时间可能是一个方面也在这里：当试图查找并与一个256字节的状态缓冲区参数缓冲区中读取的，也就是说，3个字节大小的元素， 256 （+ 3）读操作可在最坏的情况下需要 - 一个巨大的开销
Access time may be an aspect here, too: When trying to look up and read an element of, say, 3 bytes size in the parameter buffer with a 256 byte status buffer, 256 (+3) read operations will be needed in the worst case - a tremendous overhead!
有大约EEPROM单元的运作一个很能说明问题的文件，计有该怎么和 - 为什么恶化：
There is a very illustrative document about the workings of EEPROM cells, inlcuding the how-and-why of deterioration:
<一个href=\"http://www.st.com/st-web-ui/static/active/jp/resource/technical/document/application_note/CD00042024.pdf\"相对=nofollow>意法半导体：如何设计人员可以充分利用意法半导体的串口
EEPROM的，应用笔记AN2014
这篇关于是否有EEPROM的微控制器磨损平衡一般的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
