2

一連のログ エントリをフラッシュ メモリ デバイスの循環バッファに保存したいと考えています。

フラッシュ デバイスにはオンボード ウェア レベリングがないため、ロギング コードで処理する必要があります。循環バッファーは実装の一部としてこれを行いますが、整数オーバーフローの問題に悩まされています。

私がやろうとしているのは、フラッシュ領域を次のような領域に分割することです:

char index;
char checksum;
char logdata[512-(sizeof(char)*2))];

Index = 0xFF は「消去」を意味します。したがって、ID の範囲は 0x00 から 0xFE (ゼロから 254) です。つまり、インクリメント ルールは次のとおりです。

id = (last_id + 1) % 255

フラッシュが始まると、次のようになります (ID のみを表示)。

FF FF FF FF FF

最初の空のブロック (インデックス ゼロ) を選択し、最初のログ エントリに書き込みます。

00 FF FF FF FF

これは、エントリが消去されなくなるまで続きます。

00 01 02 03 04

番号が最も小さいブロックを選択したら、それを消去して新しいデータで上書きします。

05 01 02 03 04

しかし、8 ビット ID がオーバーフローすると、悪いことが起こります。

FA FB FC FD FE
00 FB FC FD FE  (OK)
01 FB FC FD FE  (Not OK - should have overwritten "FB"!)
02 FB FC FD FE  (Stuck writing the first block over and over)

これは、最初のブロックがすべての書き込みに使用されていることを意味し、回避したい「不均一な書き込み」シナリオに戻ります。私がやりたいことは、この場合は「FB」である最も古いブロックを見つけることです。

これが私が現時点で持っているコードです（Pythonで）：

buf = [0xFF]*5

for i in range(260):
    note = ""

    slot = None

    # Find first erased slot
    for x in range(len(buf)):
        if buf[x] == 0xFF:
            slot = x
            break

    if slot is None:
        # No erased slots, find lowest numbered slot
        n = 0xFF
        for x in range(len(buf)):
            if buf[x] < n:
                n = buf[x]
                slot = x

    # Debug output
    print ''.join(["%02X " % x for x in buf])

    # Write new block
    buf[slot] = i % 255

整数オーバーフローのケースを正しく処理するにはどうすればよいですか?

4

2 に答える 2

0

これを回避する方法は 2 つあります。

1 つ目はキューの容量を同じに保ちますが、容量を 255 未満にする必要があります。

アイデアは、現在の状態とまったく同じように書くことですが、最小の数を探すのではなく、最初にシーケンスの不連続性、つまりセル間の差が 1 ではない点を探します。あなたの最初の状況を取る：

FA FB FC FD FE
00 FB FC FD FE  (discontinuous at fe->fa, use fa)
00 01 FC FD FE  (discontinuous at 00->fb, use fb)
00 01 02 FD FE  (discontinuous at 01->fc, use fc)

255 未満にする必要がある理由は、これほど大きくなると、各サイクルで数値が正確に 1 回循環するため、不連続性がなくなるからです。

もう 1 つの方法は、ff何があっても次の空きスロットを示すために特別なマーカーを使用することです。

これが機能する方法は、エントリにレコードを書き込むたびに、次のエントリも書き込みますが、ffマーカーを使用することです。

次に入力する次のエントリを見つけるには、単純に最初のff. 起動段階では、複数のffマーカーがあり、最初のマーカーを選択するだけですが、それらが使い果たされると、書き込みごとに別のマーカーが提供されます。

ff ff ff ff ff ff
00 ff ff ff ff ff
00 01 ff ff ff ff
00 01 02 ff ff ff
00 01 02 03 ff ff
00 01 02 03 04 ff
ff 01 02 03 04 05
06 ff 02 03 04 05

これにより、循環バッファーの容量が 1 つ減少し、元のスキームの 2 倍の読み取りが発生するため、書き込みを最小限に抑えるには上記の最初のスキームをお勧めします。

ただし、より大きなバッファー (254 要素を超える) が必要な場合は、これが実現する 1 つの方法です。

于 2015-01-21T07:23:40.820 に答える
0

そのループは、最も小さい番号のスロットを見つけています。00、01、および 02 はすべて FB 未満です。そのため、最初のロールオーバー後、常に最初のスロットが再利用されます。

より良い設計が必要です。次の使用可能なスロットを常に参照する循環バッファー インデックスを維持することもできます。

于 2013-09-09T13:49:17.233 に答える