Pri skúmaní metódy ukladania dát do elektricky vymazateľnej programovateľnej pamäti iba na čítanie (EEPROM) som zistil, že problém nie je taký priamočiary, ako som si predtým myslel. Uvažujme o nasledujúcich požiadavkách:
- Uložiť posledných N meraných premenných v poradí
- Uchovať dáta po odpojení napájania
Požiadavky sa zdajú na povrchu jasné, ale majú niektoré nezamýšľané dôsledky. Uvažujme o prvej požiadavke — ukladanie daného počtu najnovších hodnôt. Zásobník aj fronta by poslúžili, keby ich kapacita bola dostatočná, čo znamená, že dáta by boli vybraté skôr, ako by ich kapacita bola naplnená. S dostatočne veľkou frontou by sme mohli vybrať všetky dáta a zahodiť všetko okrem posledných N hodnôt. So zásobníkom by to bolo ešte jednoduchšie — jednoducho vybrať požadovaný počet záznáv.
Čo keď je úložisko obmedzené? #
Problém nastáva, keď sa očakáva, že kapacita úložiska sa naplní skôr, ako budú dáta vybraté. Takéto obmedzenie nás núti začať zahodiť dáta, akonáhle k tomu dôjde. Keď je fronta alebo zásobník plný, do štruktúry nie je možné vložiť žiadne nové dáta, čo nespĺňa našu prvú požiadavku.
Čo je horšie, keď počet uložených záznámov zodpovedá kapacite úložiska, čo znamená, že fronta alebo zásobník je plný, nemali by sme žiadny spôsob, ako zistiť, aké nové sú dáta, alebo inými slovami, koľko záznámov bolo zahodených.
Vstupuje kruhová fronta #
Na prekonanie problému zahadzovania najnovších dát musí byť použitá iná dátová štruktúra — takzvaná kruhová fronta (niekedy nazývaná aj kruhové FIFO alebo rotačný buffer). Kruhová fronta má vlastnosť zahadzovania nie najnovších dát, ale najstarších dát namiesto toho, čím nám poskytuje presné riešenie spĺňajúce našu prvú požiadavku. Upozorňujem, že zdá sa, že neexistuje dátová štruktúra nazývaná kruhový zásobník, alebo aspoň nie štandardizovaná.
Na splnenie druhej požiadavky by sme museli použiť nevolatilnú pamäť. Nevolatilná pamäť uchováva svoj obsah po odpojení napájania. Najľahšie dostupná nevolatilná pamäť je EEPROM, dostupná ako samostatné čipy, ale takmer všetky mikrokontroléry, dokonca aj tie lacné, majú tiež nejakú EEPROM integrovanú medzi svojimi periférnymi zariadeniami. Ignorujme iné typy nevolatilného úložiska, najmä FRAM, pre zjednodušenie tohto článku, keďže iné typy pamäte majú rôzne ceny a dostupnosť na trhu, a čo je dôležitejšie, majú iné súbory obmedzení.
Obmedzenia EEPROM #
Hlavným obmedzením EEPROM je pomerne nízky počet cyklov prepisovania, zvyčajne od 100k do 1M prepisov na bit. Áno, hoci EEPROM zvyčajne umožňujú nejaký druh stránkového prístupu na zefektívnenie čítania a zápisu blokov dát, umožňujú manipulovať s dátami až na úroveň jedného bitu, čo sa považuje za výhodu, ale z praktických dôvodov túto vlastnosť tu tiež ignorujeme.
Ako teda prekonať obmedzený počet zápisových cyklov na EEPROM? Technika sa nazýva wear leveling. Wear leveling znamená úpravu frekvencie zápisov pre každú časť pamäte tak, aby bola virtuálne rovnaká. Inými slovami, zápis na to isté miesto znova až po tom, čo boli medzitým prepísané všetky ostatné miesta.
EEPROM a kruhový buffer #
Wear leveling poskytuje pekný symbiózu pre EEPROM a dátovú štruktúru kruhový buffer, pretože kruhový buffer nepotrebuje žiadne posúvanie dát a v podstate má wear leveling zabudovaný. Pri nových dátach jednoducho prejdite na ďalší záznam a prepíšte ho, pričom sa cyklicky vráťte na prvú pozíciu z poslednej (teda kruhový). Jednoduché, však?
No nie tak jednoduché, stále potrebujeme vedieť, ktorý záznam bol zapísaný ako posledný. Toto sa tiež nazýva head (hlava). Pozícia hlavy môže byť samozrejme uložená v RAM. Ale pri výpadku napájania by bola hlava stratená. Hoci naše dáta sú uložené v nevolatilnej pamäti, bez spôsobu, ako zistiť, ktorý záznam bol posledný, by sme nesplnili časť o poradí z našej prvej požiadavky. Upozorňujem, že kruhový buffer tiež ukladá informácie o svojom poslednom zázname, nazývanom tail (chvost), ale chvost tiež vynechávame pre zjednodušenie.
Ako teda obísť toto obmedzenie? Na nižšie uvedenom odkaze je tiež dosť užitočných informácií o kruhových bufferoch:
https://betterembsw.blogspot.com/2015/07/avoiding-eeprom-wearout.html
Prirodzený spôsob, ako uchovať pozíciu hlavy, je zapísať ju do EEPROM namiesto RAM, ale kde presne? Bez ohľadu na to, kde sa rozhodneme ju uložiť v EEPROM, bude sa opotrebovávať oveľa rýchlejšie ako ostatné záznamy kruhového bufferu, pretože toto je potrebné aktualizovať zakaždým, keď je vložený záznam. Hľadaním po internete, riešenia tohto problému sa zdajú byť nejednotné. Najznámejšie riešenie je použiť druhý kruhový buffer na ukladanie hlavy, čo znamená, že naša kapacita úložiska je teraz zmenšená, v extrémnom prípade dokonca na polovicu, ale wear leveling je dosiahnutý a obe naše požiadavky sú optimálne splnené. Dalo by sa to urobiť lepšie?
Zrušenie druhého kruhového bufferu #
Jeden konkrétny komentár na fóre AVRfreaks naznačuje možnosť zrušenia problematického druhého kruhového bufferu pri zachovaní wear levelingu pre celé úložisko.
Myšlienka spočíva v tom, že sa prepíše nielen najstarší záznam najnovšou hodnotou, ale tiež sa pridá deliaci záznam so známou prázdnou hodnotou pod ním, čím sa efektívne umiestni oddeľovač medzi hlavu a chvost. Takto, na nájdenie hlavy, stačí nájsť tento oddeľovač v kruhovom bufferi.
Detaily sú zložitejšie kvôli inicializácii a podobným veciam, takže si prečítajte diskusiu, ak vás zaujíma, ale chcel som poukázať na tento pekný malý nápad. Niekedy najgeniálnejšie riešenia nie sú tie najzrejmejšie. Musím priznať, že sa mi toto naozaj páči, hoci nie som si istý, či v tomto prístupe nie sú nejaké záludnosti. Dúfajme, že to čoskoro zistím.
Toto je 63. príspevok série #100daystooffload.