Способ запоминания с двойным протоколированием и носитель данных для него

Способ запоминания с двойным протоколированием и носитель данных для него

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Настоящее изобретение относится к способу запоминания с двойным протоколированием и к носителю данных для него, по которому при использовании в качестве носителя данных для запоминания/ управления/обработки данных флэш-памяти или чего-либо подобного данные запоминаются по направлению от начальных и конечных ячеек памяти к центральной части запоминающего пространства носителя данных.

Уровень техники

В последние годы в связи с быстрым развитием информационного общества и технологий мобильных вычислений были разработаны персональные цифровые помощники (ПЦП, PDA), наладонные персональные компьютеры (НПК, HPC), сотовые телефоны, электронные книги и т.п. Кроме того, для целей хранения данных широко используется множество типов флэш-памяти, так как их очень удобно носить с собой, они обладают малым временем доступа и потребляют мало энергии.

Флэш-память имеет особенности, отличающие ее от обычной оперативной памяти (ОЗУ, RAM). Флэш-память может быть более энергонезависимой и устойчивой, чем жесткий диск. Кроме того, флэш-память может функционировать с малым энергопотреблением и имеет время доступа, такое же малое, как и оперативная память. Дополнительно, по причине ее небольших размеров, флэш-память является легко приспосабливаемой для портативных устройств.

Однако флэш-память в пять-десять раз дороже жесткого диска и имеет недостаток, заключающийся в том, что для записи новых данных в область памяти, в которой данные уже существуют, должна быть выполнена операция очистки.

Например, несмотря на то, что флэш-память стандарта 28F64 0J3A, разработанная Intel Corporation, имеет высокую скорость считывания порядка 100-150 нс, подобную скорости считывания у оперативной памяти, скорости записи и стирания у нее относительно низки. При использовании 32-байтного буфера для записи данных требуется 218 мкс и время записи модуля стираемых блоков составляет 0,8 секунды на блок.

Кроме того, размер стираемого блока, который может стираться одновременно, постоянен и равен 128 килобайт. Флэш-память может выполнять операции стирания/записи 100000 раз при комнатной температуре. Ту область флэш-памяти, которая может быть стерта за раз, называют "стираемым блоком" или "сегментом".

Флэш-память может быть классифицирована в соответствии со структурами ячеек на следующие типы: тип НЕ-ИЛИ (NOR), тип НЕ-И (NAND) и тип И (AND). Как правило, широко используется флэш-память НЕ-ИЛИ или НЕ-И. Флэш-память НЕ-ИЛИ имеет высокую скорость считывания при произвольном доступе и характеризуется простотой побитного доступа. Поэтому флэш-память НЕ-ИЛИ непосредственно связана с адресным пространством памяти и используется главным образом для хранения программ, выполняемых центральным процессором. Между тем флэш-память НЕ-И имеет относительно низкое время произвольного доступа, так что она главным образом используется для одновременного сохранения относительно больших объемов данных, таких как музыкальные файлы или файлы изображений.

Традиционные файловые системы, использующие эти типы флэш-памяти, раскрыты в патенте США № 5404485, называемом "Система Флэш-памяти", и в статье "Файловая система, основанная на Флэш-памяти", стр.155-164, опубликованной на конференции USENIX в 1995 году.

Дополнительно, обеспечивается файловая система флэш-памяти с протоколированием (JFFS), в которой к флэш-памяти применяется файловая система, структурированная протоколированием. Файловая система, структурированная протоколированием, раскрыта в патенте США № 6128630, называемом "Выпуск протокола об объеме памяти для файловых систем, структурированных протоколированием", и в патенте США № 5530850, называемом "Массив библиотек хранилища данных с файловой системой, структурированной протоколированием, которая предоставляет возможность одновременной записи и очистки памяти".

В тех случаях, когда файловая система формируется в жестком диске и данные сохраняются, структурированная протоколированием файловая система использует способ запоминания с протоколированием. Соответственно, структурированная протоколированием файловая система имеет преимущество, выражающееся в том, что версии предыдущих данных и новые измененные данные могут обслуживаться в формате протокола. Дополнительно, ошибочные данные могут быть восстановлены до предыдущих данных.

JFFS формирует и последовательно сохраняет файловую систему флэш-памяти, используя файловую систему, структурированную протоколированием.

Файловая система флэш-памяти с протоколированием (JFFS) была разработана американской компанией Axis Communications (http://developer.axis.com/software/jffs/), а файловая система флэш-памяти с двойным протоколированием (JFFS2) была разработана американской компанией RedHat (http://sources.redhat.com/jffs2) по общедоступным лицензиям (GPL) проекта по свободному распространению программного обеспечения (GNU) Фонда бесплатного программного обеспечения (FSF).

Фиг.1 представляет собой типовой вид способа запоминания JFFS2, который формирует файловую систему флэш-памяти.

На Фиг.1 показан один пример запоминания данных во флэш-памяти с использованием JFFS. В случае, если в некоторой файловой системе, например EXT2 от Linux, существует структура каталогов, элемент каталога (элемент Dir 1) запоминают для того, чтобы содержать в себе общую характеристику одного каталога, как показано на Фиг.1(a). Здесь запоминаемая информация представляет собой тип узла каталога, общую длину каталога, контроль заголовка циклическим избыточным кодом (CRC), количество родительских индексных дескрипторов файла, значение версии, контроль узла циклическим избыточным кодом, имя CRC, имя каталога и т.д.

Как показано на Фиг.1, индексный дескриптор каталога (индексный дескриптор Dir 1) запоминают после элемента каталога (элемент Dir 1). Информация, запоминаемая в индексном дескрипторе каталога (индексный дескриптор Dir 1) включает в себя тип узла, общую длину, различные виды CRC, значение версии, идентификатор пользователя, идентификатор группы, время создания, время последнего обращения, время последнего изменения и т.п.

Элемент каталога и индексный дескриптор каталога представляют собой дополнительную информацию, используемую только в файловой системе, информацию, которая для пользователя является невидимой. Ее называют "метаданными". Аналогичным образом, когда запоминается файл, содержащийся в каталоге, элемент файла (элемент Файла 1) и индексный дескриптор файла (индексный дескриптор Файла 1) запоминаются последовательно.

Каталог и файл в файловой системе рассматриваются в качестве одного и того же формата. Однако в тех случаях, когда в каталоге отсутствуют фактические данные, данные файла (данные Файла 1) запоминаются после индексного дескриптора файла (индексный дескриптор Файла 1).

Таким образом, JFFS использует способ для протоколирования каталога и файла флэш-памяти. Как показано на Фиг.1(b), в случае, если индексный дескриптор каталога (индексный дескриптор Dir 1) и индексный дескриптор файла (индексный дескриптор Файла 1) подвергаются изменению и обновлению новыми значениями, первоначальные метаданные переходят в недействительное состояние и новые данные последовательно запоминаются в ячейках памяти.

На этом этапе недействительное состояние только указывает на то, что данные являются ненужными, но фактически данные не стирает. Значения версий новых данных увеличиваются на один шаг. Поэтому, если в новых данных возникает проблема, данные легко могут быть восстановлены только в случае, если существуют данные предыдущей версии.

Таким образом, если каталог и файл обновлялись и новые данные запоминались много раз, объем флэш-памяти достигает предела. Таким образом, данные, сохраненные во флэш-памяти, должны быть стерты для обеспечения требуемого объема памяти. Так как по причине особенностей флэш-памяти данные должны стираться только модулем стираемых блоков, действительные данные (элемент Dir 1) сдвигаются так, как показано на Фиг.1(c). Тогда в случае, если стираемый блок заполнен недействительными областями памяти, операция по очистке производится стиранием одного стираемого блока, как показано на Фиг.1(d).

Вышеупомянутый процесс обеспечения нового объема памяти называют "собиранием мусора" (СМ, GC). Другими словами, в случае, когда по причине отсутствия запоминающего пространства необходимо обеспечить новый объем памяти, "собирание мусора" выполняют при помощи собирания недействительных объемов памяти и очистки стираемых блоков модулем стираемых блоков. Кроме того, пространство, по которому могут быть сохранены созданные при помощи операции очистки новые данные, называют "свободной памятью". Запоминание данных может быть продолжено при помощи обеспечения большей свободной памяти.

В случае, если в качестве носителя данных используется жесткий диск, данные могут запоминаться подобным способом. Однако в случае жесткого диска недействительные данные не сдвигаются и недействительный блок, имеющий размер стираемого блока, не создается для обеспечения объема памяти.

Однако для того, чтобы на жестком диске получить быстрый доступ к файлу, несколько частей одного и того же файла собирают и сдвигают в физически примыкающую ячейку памяти. Так как жесткий диск не должен отдельно выполнить операцию по очистке, данные запоминаются непосредственно, если запоминающее пространство, по которому запоминаются новые данные, находится в недействительном состоянии.

В случае, если выполняется способ запоминания JFFS, ячейки памяти, содержащие элементы и индексные дескрипторы файлов, сложным образом перемешиваются с данными файлов. Поэтому при формировании файловой системы при помощи соединения и монтажа флэш-памяти с операционной системой (ОС, OS) для формирования древовидной структуры каталогов весь объем флэш-памяти должен быть считан и метаданные должны быть найдены.

Та же самая проблема также возникает в случае, когда формируют файловую систему, структурированную протоколированием или файловую систему с протоколированием, используя в качестве носителя данных жесткий диск вместо флэш-памяти. Другими словами, несмотря на то, что для собирания стираемых блоков данные не должны сдвигаться, как в случае флэш-памяти, скорость выборки становится в 40-50 раз ниже, чем у флэш-памяти, по причине того, что метаданные перемешаны с данными файлов и разбросаны по всему запоминающему пространству. Кроме того, формирование файловой системы при помощи считывания всего диска, объем которого может измеряться величинами, большими, чем гигабайты, занимает очень много времени.

Для хранения и воспроизведения мультимедийных данных большого объема жесткий диск преимущественно использует файловую систему, структурированную протоколированием, или файловую систему с протоколированием. Однако выгода, как файловая система мультимедиа, ухудшается в случае, если данные не передаются с постоянной скоростью в заранее определенное время по причине перемешивания с метаданными.

Раскрытие изобретения

Соответственно, настоящее изобретение направлено на способ запоминания с двойным протоколированием, который в значительной степени устраняет одну или более проблем, возникающих из-за ограничений и недостатков предшествующего уровня техники.

Цель настоящего изобретения состоит в том, чтобы обеспечить способ запоминания с двойным протоколированием, по которому данные разделены на метаданные и общие данные файлов. Данные файлов запоминаются от начальных ячеек памяти носителя данных, а метаданные запоминаются от конечных ячеек памяти носителя данных.

Дополнительно, в способе запоминания с двойным протоколированием согласно настоящему изобретению метаданные в носителе данных запоминаются по направлению от начальной ячейки памяти к тыльной части, а данные файла запоминаются по направлению от конечной ячейки памяти к передней части.

При этом способ запоминания с двойным протоколированием может быть применен к другим данным и к другим первым и вторым видам/характеристикам данных в дополнение к метаданным и данным файлов.

Данные одного и того же вида запоминаются от начальных ячеек памяти соответствующих разделов в устройстве флэш-памяти и данные других видов запоминаются от конечных ячеек памяти к передней части.

Данные, запоминаемые от начальных ячеек памяти, будут упоминаться в качестве "данных переднего протоколирования" и данные, запоминаемые от конечных ячеек памяти, будут упоминаться в качестве "данных тыльного протоколирования".

Ячейка памяти, в которой осуществляется запоминание, будет упоминаться как "заголовок", а ячейка памяти, в которой операция стирания выполняется в тыльной части протоколирования, будет упоминаться как "хвост". Другими словами, существуют заголовок и хвост данных переднего протоколирования, а также заголовок и хвост данных тыльного протоколирования. Кроме того, по причине увеличения заголовков на обеих сторонах передних и тыльных частей передние и тыльные части встречаются друг с другом. При этом ячейка памяти, в которой передние и тыльные части встречаются друг с другом, будет упоминаться как "центральная ячейка памяти".

В случае, если в устройстве флэш-памяти запоминаемые данные вводятся в файловую систему соответствующих разделов, носителю данных требуется свободный объем для физического запоминания данных и свободный объем для запоминания метаданных, таких как элемент и индексный дескриптор файла, которые необходимы для создания данных файла.

В этом случае данные файла и метаданные могут запоминаться в переднем и тыльном протоколировании соответственно. Другими словами, данные файла и метаданные соответственно запоминаются от передней и тыльной частей носителя данных и наоборот.

Согласно способу запоминания с двойным протоколированием настоящего изобретения, когда существует намерение запомнить произвольные данные в носителе данных, операция запоминания выполняется после определения того, в какой части будут запоминаться данные. В случае обновления данных предыдущие данные признаются недействительными, а новые данные запоминаются в ячейке памяти заголовка. В случае стирания данных признаются недействительными только отмеченные данные.

Если запоминание и обновление повторяются этим способом, данные переднего протоколирования и данные тыльного протоколирования встречаются друг с другом, таким образом определяется центральная ячейка памяти. В случае, если и передняя, и тыльная части возвращаются к своим начальным ячейкам памяти, а данные продолжают обрабатываться, одна из них прибывает первой в центральную ячейку памяти. На этом и последующих этапах может быть определено, что протоколирование, прибывающее первым в центральную ячейку памяти С, имеет больший объем запоминаемых данных. Следовательно, с тем чтобы увеличить пространство для протоколирования, имеющего больший объем данных, центральная ячейка памяти С сдвигается в другую сторону.

В случае флэш-памяти цель способа запоминания с протоколированием состоит в том, чтобы должным образом задать число повторений стирания по отношению к стираемым блокам. В случае, если центральная ячейка памяти сдвигается, протоколирование, имеющее больший объем данных, увеличивается. В результате появляется возможность должным образом задать число повторений стирания по отношению к передним и тыльным частям.

Дополнительно, устройство флэш-памяти согласно настоящему изобретению включает в себя процессор для генерирования считывания и записи команд для считывания/записи данных из/в определенного адреса оперативной памяти (ОЗУ, RAM), флэш-память для обеспечения пространства для хранения данных и контроллер памяти для управления данными, запоминаемыми в памяти при помощи описанного в данном документе способа запоминания с двойным протоколированием.

Дополнительно, согласно способу запоминания с двойным протоколированием настоящего изобретения устройство флэш-памяти, разрешающее операцию считывания во время операции записи, включает в себя множество разделов. Соответствующие разделы могут выполнять операции считывания, записи и стирания вместе с другими разделами (например, независимо). Данные, запоминаемые в соответствующих разделах флэш-памяти, подразделяются на метаданные и общие данные файла. Данные файла запоминаются от начальной ячейки памяти носителя данных, то есть соответствующих разделов. Между тем метаданные запоминаются по направлению от конечных ячеек памяти к начальным ячейкам памяти соответствующих разделов.

Устройство флэш-памяти согласно настоящему изобретению, включающее в себя: многократно разделенную память; множество разделов, обеспеченных множеством разделов памяти, в которых запоминаемые данные независимо считываются, записываются или стираются; генератор подкачки зарядов для обеспечения множества уровней напряжения, необходимых для считывания, записи и стирания данных; и множество первых усилителей считывания, сформированное для операции считывания, причем операция считывания выполняется одновременно для соответствующих разделов; множество вторых усилителей считывания, включающее в себя, по меньшей мере, один усилитель считывания, сформированное для операций стирания и записи, причем операции стирания и записи выполняются одновременно для соответствующих разделов и данные запоминаются в соответствующих разделах по направлению от начальных и конечных ячеек памяти запоминающих объемов соответствующих разделов к соответствующим центральным частям.

Данные, запоминаемые в соответствующих разделах, запоминаются по направлению от начальных и конечных ячеек памяти запоминающего объема к центральной части.

Дополнительно, мобильный терминал согласно настоящему изобретению включает в себя устройство многократно разделенной флэш-памяти, множество шин и процессор, соединенный с шинами. Здесь многократно разделенная флэш-память соединена с шиной и к ней может получать доступ процессор.

Кроме того, мобильный терминал согласно настоящему изобретению включает в себя запоминающее устройство, такое как флэш-память или жесткий диск (HDD), множество шин и процессор, связанный с шинами. Здесь запоминающее устройство связано с шинами и к нему может получать доступ процессор.

Дополнительные особенности и преимущества изобретения будут сформулированы в описании, которое приведено ниже, и частично будут очевидны из описания либо могут быть изучены на практике изобретения. Задачи и другие преимущества изобретения будут реализованы и достигнуты структурой подробно указанной в написанном описании и его формуле изобретения так же, как и в приложенных чертежах.

Краткое описание чертежей

Сопроводительные чертежи, которые приложены и включены для обеспечения дополнительного понимания изобретения и составляют часть этого описания, иллюстрируют варианты осуществления изобретения и вместе с описанием служат для пояснения принципов изобретения.

На чертежах:

Фиг.1 представляет собой типовой вид способа запоминания в JFFS2, формирующей файловую систему во флэш-памяти;

Фиг.2 примерно иллюстрирует центральную ячейку памяти, которая в способе запоминания с двойным протоколированием согласно варианту осуществления настоящего изобретения определяется при встрече друг с другом заголовка данных переднего протоколирования и заголовка данных тыльного протоколирования;

Фиг.3 примерно иллюстрирует процесс определения новой центральной ячейки памяти в способе запоминания с двойным протоколированием согласно настоящему изобретению, по которому новая центральная ячейка памяти определяется при помощи сдвига центральной ячейки памяти по направлению к тыльному протоколированию в случае, когда заголовок данных тыльного протоколирования первым прибывает к центральной ячейке памяти после определения центральной ячейки памяти;

Фиг.4 представляет собой блок-схему, иллюстрирующую способ запоминания с двойным протоколированием согласно варианту осуществления настоящего изобретения;

Фиг.5 представляет собой блок-схему процесса "собирания мусора" (СМ) в качестве части способа запоминания с двойным протоколированием;

Фиг.6 представляет собой график для определения количества стираемых блоков в процессе "собирания мусора" (СМ) способа запоминания с двойным протоколированием;

Фиг.7 представляет собой схематическую блок-схему флэш-памяти, подходящей для способа запоминания с двойным протоколированием согласно варианту осуществления настоящего изобретения;

Фиг.8 представляет собой блок-схему устройства флэш-памяти согласно варианту осуществления настоящего изобретения;

Фиг.9 иллюстрирует устройство многократно разделенной флэш-памяти согласно варианту осуществления настоящего изобретения;

Фиг.10 иллюстрирует типовой мобильный терминал, использующий устройство флэш-памяти согласно настоящему изобретению.

Осуществление изобретения

В дальнейшем предпочтительные варианты осуществления настоящего изобретения будут описаны подробно в отношении сопроводительных чертежей.

Фиг.2 примерно иллюстрирует центральную ячейку памяти, которая в способе запоминания с двойным протоколированием согласно варианту осуществления настоящего изобретения определяется при встрече друг с другом заголовка данных переднего протоколирования и заголовка данных тыльного протоколирования.

На Фиг.2(a) позиционные обозначения "H1" и "T1" обозначают соответственно заголовок и хвост данных переднего протоколирования. Позиционные обозначения "H2" и "T2" обозначают соответственно заголовок и хвост данных тыльного протоколирования. Позиционное обозначение "C" обозначает центральную ячейку памяти.

В случае, если данные Data1 вводят файловую систему в соответствующие разделы, определяют, является ли вид данных данными переднего протоколирования или данными тыльного протоколирования, и этот результат затем запоминают в заголовках.

Обратившись к Фиг.2(a), увидим, что, так как данные Data1 являются данными переднего протоколирования, данные Data1 запоминают от начальной ячейки памяти носителя данных.

Фиг.2(b) иллюстрирует состояние, при котором запоминаются шесть блоков данных. Четыре блока данных Data1 - Data4 являются данными переднего протоколирования, а два блока данных - Data5 и Data6 являются данными тыльного протоколирования.

Данные Data2 и Data6 стираются. На этом этапе данные, по причине особенностей способа запоминания с протоколированием, не могут быть стерты фактически, но отображаются с недействительными состояниями.

Фиг.2(c) иллюстрирует состояние, при котором собирание мусора (СМ) выполняется по причине отсутствия в носителе данных свободного запоминающего пространства. Другими словами, так как данные Data1 являются действительными данными, данные Data1 сдвигаются к заголовку, а предыдущие данные Data1 в таком случае признаются недействительными. В случае, если объем данных Data1 и предварительно признанных недействительными данных Data2 превышает размер стираемого блока, операция стирания выполняется фактически, обеспечивая таким образом свободное пространство.

В случае флэш-памяти операция стирания выполняется фактически. Между тем в случае диска выполнение отдельной операции стирания излишне.

В случае, если обеспечено свободное пространство, хвост T1, соответствующий конечной части данных переднего протоколирования, сдвигается в ячейку памяти данных Data3. Тем же самым способом, если данные Data5 признаются недействительными и стираются после данных Data6, размер которых становится размером стираемого блока, то хвост T2 данных тыльного протоколирования также сдвигается.

Это состояние предназначено для того, чтобы сохранить новые данные Data7. Несмотря на намерение сохранить данные Data7 в переднем заголовке H1 в качестве данных переднего протоколирования, свободного пространства не хватает.

Следовательно, как показано на Фиг.2(d), запоминаются только данные D7-1. Здесь данные D7-1 соответствуют части, которая может быть запомнена. Затем передний заголовок H1 возвращается к начальной ячейке памяти и запоминаются оставшиеся данные D7-2.

Этим способом, если данные переднего протоколирования встречаются с тыльным протоколированием, оно возвращается к начальной ячейке памяти и затем запоминается. Ячейка памяти, в которой передний заголовок H1 и тыльный заголовок H2 встречаются друг с другом, назначается центральной ячейкой памяти C. На этом этапе тыльный заголовок H2 также возвращается к конечной ячейке памяти и ожидает запоминания. Другими словами, этим способом данные запоминаются в переднем и тыльном протоколировании и назначается центральная ячейка памяти.

Когда данные продолжают запоминаться при помощи этого способа, один из переднего H1 и тыльного H2 заголовков первым прибывает в центральную ячейку памяти C. В этом случае может быть определено, что протоколирование, прибывающее первым в центральную ячейку памяти С, имеет больший объем запоминаемых данных.

Следовательно, центральная ячейка памяти С сдвигается по направлению к другой стороне для того, чтобы увеличить пространство для протоколирования, прибывающего первым в центральную ячейку памяти.

Фиг.3 примерно иллюстрирует процесс определения новой центральной ячейки памяти в способе запоминания с двойным протоколированием согласно настоящему изобретению. На Фиг.3 после определения центральной ячейки памяти в случае, если заголовок данных тыльного протоколирования прибывает первым в центральную ячейку памяти, новая центральная ячейка памяти определяется при помощи сдвига центральной ячейки памяти по направлению к переднему протоколированию.

Обратившись к Фиг.3(a), увидим, что данные Data3 и Data5 признаются недействительными и данные тыльного протоколирования активно запоминаются для того, чтобы данные Data8 и Data9 были сохранены. Несмотря на намерение сохранить данные Data10, запоминающего пространства не хватает.

Другими словами, - это случай, когда данные тыльного протоколирования первыми прибывают в центральную ячейку памяти C. Здесь, так как тыльный заголовок H2 не встречается с передним заголовком H1, центральная ячейка памяти С сдвигается по направлению к передней части до тех пор, пока в передней части существует пространство, достаточное для хранения данных.

Процесс определения того, действительно ли в передней части существует достаточно много данных, выполняется при "собирании мусора", представленном на Фиг.5, которое будет описано позже.

Ради этого процесса, как показано на Фиг.3(b), передние данные D7-1 сдвигаются к переднему заголовку H1, а центральная ячейка памяти С также сдвигается по направлению к передней части.

На этом этапе, в случае флэш-памяти, модуль данных, сдвигающихся по направлению к передней части, представляет собой модуль стираемых блоков.

Причина состоит в том, что новые данные не могут быть запомнены до создания свободного пространства при помощи выполнения операции очистки после сдвига.

Здесь стираемый блок обозначает модуль памяти, который одновременно может быть стерт во флэш-памяти. Вообще, модули памяти имеют объем 128 или 256 килобайт. На этом этапе, если по отношению к стираемому блоку выполняется операция очистки, то создается свободный блок. Здесь "свободный блок" представляет собой пространство, по которому данные могут запоминаться, а "свободное пространство" означает свободный блок с заранее определенным объемом памяти.

После создания такого свободного пространства запоминают новые данные Data10.

Центральная ячейка памяти С сдвигается до тех пор, пока не встретит передний заголовок H1, либо до тех пор, пока не встретит в передней части существующее пространство, достаточное для хранения данных.

Фиг.4 представляет собой блок-схему, иллюстрирующую способ запоминания с двойным протоколированием согласно настоящему изобретению.

Другими словами, Фиг.4 иллюстрирует блок-схему способа запоминания с двойным протоколированием, такого как описанный на Фигурах 2 и 3, на которых способ включает в себя процесс запоминания данных, процесс определения центральной ячейки памяти и процесс сдвига центральной ячейки памяти.

Обратившись к Фиг.2-4, увидим, что исходные данные переднего заголовка H1, тыльного заголовка H2, переднего хвоста T1, тыльного хвоста T2 и центральной ячейки памяти С в основном установлены на нуль (S101). Они представляют собой первоначальные состояния, при которых запоминаются данные переднего протоколирования и данные тыльного протоколирования.

Запоминание данных запрашивают у файловой системы через буфер. В случае, если запрашивают запоминание данных на носитель данных в этом состоянии (S102), то при помощи собирания мусора (СМ), которое позже будет описано в отношении Фиг.5, проверяют, действительно ли объем памяти достаточен (S103).

В случае, если определено, что объем памяти носителя данных является достаточным, процесс возвращается непосредственно к блок-схеме, представленной на Фиг.4. Между тем, если будет определено, что объем памяти носителя данных является недостаточным, процесс возвратится к блок-схеме, представленной на Фиг.4, после того как пространство памяти будет обеспечено.

Затем проверяют, действительно ли центральная ячейка памяти С установлена на нуль (S104). Этот процесс выполняют для того, чтобы проверить, действительно ли центральную ячейку памяти определяют впервые. Причина этого состоит в том, что в начальном состоянии, перед определением центральной ячейки памяти С, процесс отличается от процесса в состоянии после определения центральной ячейки памяти С.

Другими словами, в случае, если центральная ячейка памяти С определена впервые, следует проверить, встречается ли заголовок одной стороны с заголовком другой стороны. Между тем, в случае, если центральная ячейка памяти С уже была определена, следует проверить то, какой заголовок первым встретится с центральной ячейкой памяти C.

В соответствии с результатом проверки на этапе S104 в случае, если центральная ячейка памяти С установлена или не установлена на нуль, соответственно проверяют то, действительно ли данные представляют собой данные переднего протоколирования (S105). Затем данные запоминаются согласно соответствующим случаям.

Предположим, что центральная ячейка памяти С установлена на нуль, новые запоминаемые данные представляют собой данные переднего протоколирования, то есть данные запоминаются от передней части носителя данных и их объем равен S.

В этом случае, если данные запоминаются, это означает, что заголовок данных переднего протоколирования теперь располагается на "H1+S". Сначала этап S106 выполняют для того, чтобы проверить, действительно ли для запоминания данных, объем которых равен "S", наличествует достаточный объем памяти.

Если заголовок H1+S запоминаемых данных переднего протоколирования не встречается с заголовком H2 данных тыльного протоколирования, то есть, если (H1+S)<H2, это означает, что объем памяти достаточен. Следовательно, данные переднего протоколирования запоминаются от ячейки памяти H1 так, чтобы заголовок данных увеличивался от предыдущей ячейки памяти H1 к ячейке памяти H1+S (S108). Это соответствует содержанию, описанному на Фигурах 2(a) и 2(b). Здесь ячейки памяти H1 и H2 представляют собой адреса, которые увеличиваются, например, на блок байтов во флэш-памяти, и объем данных S равен блоку байтов, так чтобы ими можно соответственно управлять, используя равный модуль.

Между тем, если условие (H1+S)<H2 не удовлетворяется, то есть, если заголовок H1+S данных переднего протоколирования встречается с заголовком H2 данных тыльного протоколирования, тогда из ячейки памяти H1 запоминают только сохраняемый объем (H2-H1) из числа объема данных S (S109).

В этом случае ячейка памяти H2 дополнительно определяется в качестве центральной ячейки памяти, как и на Фиг.2(d), а остающаяся часть данных [S-(H2-H1)] запоминается от начальной ячейки памяти данных переднего протоколирования.

Другими словами, как показано на этапе S109, центральная ячейка памяти С более не равна нулю, H1 становится нулем, остающаяся часть [S-(H2-H1)] данных запоминается от нуля и H1 увеличивается настолько же, насколько и [S-(H2-H1)]. Это соответствует содержанию, описанному на Фиг.2(c) и 2(d). Другими словами, H1 с Фиг.2(d) соответствует [S-(H2-H1)] и становится новой ячейкой памяти.

В случае, если запоминаемые данные являются данными тыльного протоколирования, данные запоминаются способом, который является симметричным (например, S106, S108, S109) с вышеупомянутым описанием (S107).

Дополнительно, на этапе S104 в случае, если центральная ячейка памяти С не равна нулю, следует проверить, действительно ли запоминаемые данные являются данными переднего протоколирования (S110).

Когда центральная ячейка памяти С не равна нулю, заголовок данных переднего протоколирования и заголовок данных тыльного протоколирования уже встретились друг с другом так, чтобы центральная ячейка памяти была определена. Поэтому в случае, если сохраняемые данные представляют собой данные переднего протоколирования, следует проверить, действительно ли заголовок (H1+S) превышает центральную ячейку памяти C. Это отличается от вышеприведенного описания.

На этом этапе, если заголовок H1+S данных переднего протоколирования не превышает центральную ячейку памяти C, то есть (H1+S)<C, это означает, что объем памяти достаточен (S111). Поэтому данные переднего протоколирования запоминаются от ячейки памяти H1, так чтобы заголовок данных увеличивался от предыдущей ячейки памяти H1 к ячейке памяти H1+S (S112).

Между тем, если условие (H1+S)<C не удовлетворяется, то есть если заголовок H1+S данных переднего протоколирования встречается с центральной ячейкой памяти C, от ячейки памяти H1 запоминают только сохраняемый объем (C-H1) из числа объема данных S (S114).

Этот этап выполняют для того, чтобы обеспечить достаточный объем памяти, в то время как определено, что наличествует большой объем данных переднего протоколирования. Через этот этап во флэш-памяти времена запоминания могут быть назначены должным образом.

Однако, если центральная ячейка памяти С сдвигается по направлению к тыльной части, действительные данные тыльного протоколирования сдвигают к ячейке памяти H2. На этом этапе следует проверить, действительно ли в тыльной части существует сохраняемый объем памяти (S115). Другими словами проверяется, действительно ли существует объем памяти, по которому может быть сохранена остающаяся часть [S-(C-H1)] данных S. Это соответствует содержанию, описанному на Фиг.3(b).

В случае, если в тыльной части существует сохраняемый объем, данные сдвигаются к ячейке памяти H2 настолько же, насколько и [S-(C-H1)] (S116), и в этой ячейке памяти запоминаются новые данные [S-(C-H1)]. Это может быть понято через сдвиг данных D7-1 к ячейке памяти H1, как представлено на Фиг.3(b). Несмотря на то, что Фиг.3 иллюстрирует случай, при котором центральная ячейка памяти сдвигается по направлению к передней части, его принцип эквивалентен описанному выше.

Между тем, если в тыльной части не существует сохраняемого объема, это означает, что тыльная часть заполнена данными. Следовательно, центральная ячейка памяти сдвигается к тыльной части настолько же, насколько и сохраняемая часть. Остающаяся часть возвращается к позиции "0" (то есть H1=0) и затем запоминается (S118).

В случае, если запоминаемые данные представляют собой данные тыльного протоколирования, их запоминают способом, который является симметричным (например, соответствующим S111, S112, S114-S118) вышеприведенному описанию (S113).

В случае, если процесс запоминания данных завершается, выполняют процесс собирания мусора (СМ).

Фиг.5 представляет собой блок-схему процесса собирания мусора (СМ) в качестве части способа запоминания с двойным протоколированием.

Обратившись к Фиг.5, увидим, что если запрашивается запоминание данных, то выполняют процесс собирания мусора (СМ) для проверки того, действительно ли существует свободный объем памяти, по которому данные могут запоминаться.

Запоминаемые данные существуют в буферной памяти в данный момент времени. В случае, если отсутствует свободный объем памяти, равный объему запоминаемых данных, данные сдвигаются при помощи способа с протоколированием и операцию очистки выполняют