Портативное устройство хранения данных с использованием таблицы отображения адресов памяти

Портативное устройство хранения данных с использованием таблицы отображения адресов памяти

Иллюстрации

Показать все

Реферат

Область техники

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

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

В последние несколько лет возник большой интерес к созданию устройств хранения данных, которые содержат флэш-память и которые могут быть подсоединены к последовательной шине компьютера. Главным документом в данной области является WO 01/61692, который описывает моноблочное устройство, впоследствии вышедшее на рынок под товарным знаком "Thumbdrive". В одном из вариантов осуществления изобретения, описанном в этом документе, штепсельный разъем универсальной последовательной шины (USB), установленный на корпусе устройства, напрямую соединяется с USB-розеткой на компьютере, так что компьютер способен передавать данные на флэш-память и с флэш-памяти портативного устройства хранения под управлением контроллера универсальной последовательной шины (USB-контроллера). Для этого устройства были предложены различные улучшения. Например, WO 03/003282 описывает устройство, которое может быть снабжено датчиком для снятия отпечатков пальцев и в котором доступ к данным, сохраненным в этом устройстве, разрешен только в случае, когда датчик для снятия отпечатков пальцев удостоверяет подлинность пользователя, сравнивая отсканированный отпечаток пальца пользователя с предварительно заложенными в память данными. Описание обоих этих документов включено в текст данной заявки путем ссылки.

На Фиг.1 показана возможная структура подобного портативного устройства хранения. Портативное устройство хранения обозначено цифрой 1, причем корпус показан пунктирной линией. Оно включает USB-контроллер 2, который управляет USB-интерфейсом 3 (например, штепсельным USB-разъемом), который напрямую подсоединяется к USB-интерфейсу 4 (например, USB-розетке) главного компьютера 5. Данные, переданные на USB-интерфейс 3 с главного компьютера 5, проходят через USB-контроллер 2 на главный узел 7 управления. Пакеты данных бывают разных видов. Они включают пакеты данных ЗАПИСЬ, которые содержат предписания ЗАПИСЬ для записи определенного количества данных, которые являются множеством из 512 байт, на индивидуальный логический адрес. Они включают также пакеты данных ЧТЕНИЕ, которые содержат предписание ЧТЕНИЕ для считывания данных с индивидуального логического адреса. Предписание ЗАПИСЬ обычно содержит логический адрес той ячейки, в которую должна быть записана первая часть данных, указание, сколько данных должно быть записано, и затем те данные, которые должны быть записаны. Для сообщения одного предписания ЗАПИСЬ может понадобиться несколько пакетов данных. Подобным образом предписание ЧТЕНИЕ указывает логический адрес, с которого необходимо начать считывание, и указание, сколько памяти должно быть считано, начиная с того места.

Главный узел 7 управления обеспечивает выполнение этих предписаний посредством управления флэш-памятью И-НЕ 9. Главный узел 7 управления управляет флэш-памятью И-НЕ 9 посредством управляющих символов, которые передаются одной или более линиями, схематически показанными как 12. Обычно эти линии 12 включают одну линию, которая посылает сигнал ЗАПИСЬ, когда данные должны быть записаны на флэш-память 9, одну линию, которая посылает сигнал ЧТЕНИЕ, когда флэш-память должна послать данные на главный узел 7 управления, линии, которые посылают адресный сигнал, указывающий ячейку в памяти, в которую должны быть записаны данные или из которой данные должны быть считаны, и сигнал ПОДКЛЮЧЕНИЕ, который должен иметь определенное значение для флэш-памяти, чтобы приводить ее в действие.

Когда главному узлу 7 управления необходимо сохранить данные на флэш-память 9, он посылает их на нее через 8-битную шину 8, одновременно посылая команду ЗАПИСЬ, сигнал ПОДКЛЮЧЕНИЕ и адрес. Этот адрес является физическим адресом (т.е. абсолютным адресом в запоминающем устройстве 9), соответствующим указанному логическому адресу согласно отображению, сохраненному в устройстве оперативной памяти (ОЗУ) главного узла 7 управления или доступному ему. Когда в ответ на команду ЧТЕНИЕ данные передаются из указанного устройства, они проходят в пакетах по 512 байт из флэш-памяти И-НЕ 9, через 8-битную шину 8, на главный узел 7 управления. Главный узел управления посылает эти 512-байтные пакеты на USB-контроллер 2, который посылает их из устройства 1 через USB-интерфейс 3 на главный компьютер 5.

Указанное устройство обычно получает питание через USB-интерфейс 3, и таким образом, когда USB-интерфейс 3 отключен из USB-розетки компьютера, это устройство выключается. Все данные, сохраненные в ОЗУ главного узла 7 управления, пропадают.

На Фиг.2 показано пространство памяти флэш-памяти И-НЕ 9. Это устройство сконфигурировано для сохранения групп данных по 512 байт на соответствующих «страницах» 6 (отметим, что существуют другие возможности, такие как сохранение 2 килобайт на каждой странице), каждая из которых также содержит соответствующий сектор 11 сохранения управляющих данных, который сохраняет управляющие данные (обычно не более 16 байт). Указанные данные сконфигурированы в «блоки» 10 (т.е. соответствующие ряды на Фиг.2), например, с 64 страницами 6 на каждый блок 10. Традиционные флэш-памяти И-НЕ имеют три ограничения:

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

2. Заданный блок или страница имеет ограниченный жизненный цикл. Другими словами, он может быть изменен из стертого состояния в нестертое только ограниченное количество раз, например, 10 ООО раз. Это ограничивает продолжительность жизни запоминающего устройства.

3. Во флэш-памяти И-НЕ встречаются блоки, которые являются «плохими» в том смысле, что данные не могут быть надежно туда записаны.

Как было упомянуто выше, адрес в запоминающем устройстве И-НЕ 9, на который записываются данные или с которого данные считываются, определяется логическим адресом, закодированным в пакете данных, полученном через USB-интерфейс 3. Традиционно главный узел управления имеет доступ к таблице, хранящей отображение между адресами в пространстве логического адреса и ячейками в пространстве адресов физической памяти, которые расположены внутри блоков запоминающего устройства, которые не находятся в грязной таблице (т.е. «физическом адресе» внутри памяти). А именно, каждый блок отображен в соответственную область пространства логического адреса, имея число адресов, равное числу страниц. Это отображение фиксировано. Таким образом, плохие блоки не ассоциируются с какими-либо логическими адресами.

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

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

Сущность изобретения

Настоящее изобретение ставит своей целью предоставить новое и полезное портативное устройство хранения данных.

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

У этого есть ряд преимуществ.

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

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

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

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

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

Обновление отображения адреса памяти (т.е. выбор стертого второго блока для замены первого блока в указанном отображении) может быть произведено всякий раз, когда получено новое предписание ЗАПИСЬ для записи данных в ячейку физического адреса, которая не находится в стертом состоянии.

Это может быть произведено сразу по получении предписания ЗАПИСЬ. В качестве альтернативы в предпочтительном усовершенствовании настоящего изобретения, операция записи, осуществляемая главным узлом управления, основываясь на заданном предписании ЗАПИСЬ, может быть приостановлена на определенный период, и осуществлена только в случае, если в этот период не получено никаких предписаний, подходящих под предопределенный критерий подобия с первым предписанием. Подобно тому, как понятие таблицы отображения переменного адреса, рассмотренное выше, частично объясняется наблюдением, что логические адреса являются статистически коррелированными, это усовершенствование объясняется наблюдением, что зачастую предписания, полученные в течение относительно короткого периода времени, являются настолько сильно коррелированными, что они могут быть более эффективно обработаны вместе, чем отдельно, таким образом улучшая скорость и/или продолжительность жизни портативного устройства хранения данных. Это понятие приостановки операции записи, чтобы определить, будет ли получено другое корреляционное предписание ЗАПИСЬ, составляет другой независимый аспект настоящего изобретения, который может быть использован в пределах объема притязаний этого изобретения, но только не в сочетании с переменной таблицей отображения.

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

Второй такой корреляцией является то, что, как заметили авторы настоящего изобретения, зачастую главный узел управления в течение короткого промежутка времени получает пакеты, содержащие предписания ЗАПИСЬ, которые определяют точно такой же логический адрес. Вместо того чтобы немедленно обновлять отображение адреса памяти всякий раз, когда получено каждое из этих предписаний, варианты осуществления настоящего изобретения предпочтительно приостанавливают эту операцию в течение некоторого периода времени. В течение этого периода указанные данные сохраняются в кэше данных, управляемом главным узлом управления (например, его внутренней кэш-памятью ОЗУ). Если же в течение этого периода времени не получено никакого предписания, относящегося к тому же логическому адресу, тогда главный узел управления продолжает записывать данные на флэш-память, как описано выше. Однако если в течение этого периода получено предписание ЗАПИСЬ (или, в альтернативных вариантах осуществления, предписание, не относящееся к тому же логическому адресу), главный узел управления вместо этого записывает указанные данные на свою кэш-память (и обычно сбрасывает на нуль свой счетчик). Если в течение указанного периода в отношении того же логического адреса получено предписание ЧТЕНИЕ, то данные считываются из кэш-памяти, а не из устройства флэш-памяти.

По выбору, кэш-память может быть достаточно объемной, чтобы сохранять данные в отношении множества логических адресов. Это означает, что кэш-память может быть поделена на множество секций, где каждая из них предназначена для сохранения данных в отношении соответствующих логических адресов и каждая ассоциируется с соответственным таймером для измерения времени, прошедшего со момента получения предписания ЗАПИСЬ в отношении этого логического адреса.

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

Вышеизложенное описание предполагает, что существует соответственное отображение для каждого из блоков, которые должны быть ассоциированы с областями логического адреса, но для этого таблица отображения адреса памяти должна иметь, по меньшей мере, такое же количество элементов, какое число блоков доступно для сохранения данных. Альтернативой является ассоциировать области логического адреса с соответственными группами блоков. Например, указанные блоки могут быть сгруппированы в группы по (скажем) четыре блока (составляя, например, сумму 4×64=256 страниц), и области логического адреса стали бы больше в соответствующее количество раз (например, в четыре раза). Таблица отображения адреса памяти в этом случае установила бы взаимно однозначное отображение между каждой из этих групп и соответственной областью логического адреса.

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

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

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

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

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

(1) интерфейс данных для передачи пакетов данных на устройство и с него,

(2) контроллер интерфейса,

(3) главный узел управления,

и (4) по меньшей мере, одно устройство флэш-памяти И-НЕ,

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

причем главный узел управления выполнен с возможностью распознавания определенных пакетов данных в качестве закодированных предписаний ЧТЕНИЕ и других пакетов данных в качестве закодированных предписаний ЗАПИСЬ:

(а) для того, чтобы по получении предписания ЧТЕНИЕ, указывающего логический адрес, получить доступ к таблице отображения адреса памяти, которая ассоциирует области логического адреса внутри пространства логической памяти с соответственными первыми областями физического адреса внутри запоминающего устройства, считывать данные с физического адреса в запоминающем устройстве, соответствующие логическому адресу в соответствии с таблицей отображения адреса, и передавать на интерфейс данных один или более пакетов данных, включая данные, которые были считаны,

и (б) для того, чтобы по получении предписания ЗАПИСЬ, указывающего логический адрес и данные, которые должны быть записаны на этот логический адрес, определить, находится ли в стертом состоянии физический адрес, соответствующий логическому адресу в соответствии с таблицей отображения адреса памяти, и

если да, то записать данные на тот физический адрес,

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

Необходимо понимать, что в контексте данного изобретения подразумевается, что могут существовать предписания ЗАПИСЬ, содержащие данные, которые должны быть сохранены на множестве страниц, или пакеты данных ЧТЕНИЕ, которые запрашивают данные с множества страниц. Другими словами, вышеупомянутый адрес может, например, быть начальным адресом многостраничной группы области физического адреса.

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

Здесь будут описаны предпочтительные функции данного изобретения, исключительно ради пояснения, ссылаясь на следующие чертежи, из которых:

Фиг.1 показывает первую конфигурацию известного портативного устройства хранения данных;

Фиг.2 показывает область физической памяти устройства флэш-памяти И-НЕ известного устройства на Фиг.1;

Фиг.3 показывает таблицу отображения адреса памяти в первом варианте осуществления настоящего изобретения;

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

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

Фиг.6, которая состоит из Фиг.6(а)-6(д), показывает второй вариант осуществления настоящего изобретения;

Фиг.7, которая состоит из Фиг.7(а)-7(д), показывает положение физической памяти третьего варианта осуществления настоящего изобретения в соответственные периоды времени;

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

и Фиг.9, которая состоит из Фиг.9(а)-9(в), иллюстрирует четвертый вариант осуществления настоящего изобретения.

Подробное описание вариантов осуществления изобретения

Сейчас будет описан первый вариант осуществления настоящего изобретения. У него может быть такая же структура аппаратной части системы, как показано на Фиг.1, и по этой причине соответствующим элементам этого варианта осуществления изобретения будут даны те же номера позиций, что и на Фиг.1. Все показанные элементы могут быть заключены в одиночный корпус, например, в такой, на котором установлен USB-соединитель 3. USB-соединитель 3 (например, штепсельный USB-разъем) может подсоединяться напрямую к главному компьютеру (например, персональному компьютеру (ПК)) путем подключения к USB-розетке 4 главного компьютера 5. В качестве альтернативы, между ними возможно подсоединить кабель. Необходимо отметить, что настоящее устройство может обладать многими функциями, которые не показаны детально на Фиг.1, но которые известны в других портативных устройствах хранения данных, находящихся в открытом доступе, такими как защита паролем, доступ, контролируемый проверкой отпечатков пальцев, и т.д. Осуществление подобных функций будет ясно специалистам в данной области техники.

На Фиг.3 показана таблица отображения адреса памяти, используемая в первом варианте осуществления настоящего изобретения. Эта таблица сохранена в энергозависимой оперативной памяти (ОЗУ) главного узла 7 управления. В левой колонке 21 расположены индексы, помечающие области логического адреса, а в правой колонке 23 - цифры, помечающие блоки пространства физического адреса, которые однозначно отображаются в те области логического адреса. Для упрощения допускается, что число областей логического адреса равно 8 (помечено числами с 0 по 7) и что число блоков равно 16 (помечено индексами с 0 по 15). В действительности оба из этих чисел будут значительно выше. Таким образом, количество данных, которые могут быть сохранены в каждой из областей логического адреса, равно 512 байт (при условии, что таким является размер страниц), помноженным на число страниц в блоке (например, 64). Каждый ряд из правой колонки сохраняет только индекс, помечающий соответствующий блок. Число областей логического адреса соответствует числу блоков, которые будут использованы для сохранения данных в любой момент времени.

Например, из-за того, что предполагается, что в блоке находятся 64 страницы, логический адрес 67 относится к странице в области 1 логического адреса. Это происходит потому, что указанные страницы области 1 логического адреса имеют логические адреса 0, 1, ... 63 и страницы области 0 логического адреса имеют логические адреса 64, 65, ... 127, так что логический адрес 67 является четвертым адресом в области 1 логического адреса. На отображении, показанном на Фиг.3, область 1 логического адреса отображена в блок 10.

В добавление к блокам, которые отображены в области логического адреса, пространство физического адреса включает некоторое число других блоков (8 в примере, показанном выше). Эти блоки включают блоки 6, 12 и 13, которые являются резервными, и плохой блок 7, который является «плохим» (не функциональным). Таким образом, эти адреса не появляются в таблице отображения на Фиг.3 (хотя предпочтительно данный вариант осуществления также имеет таблицу грязных блоков и таблицу резервных блоков, которые могут быть использованы в традиционных способах выполнения других операций, традиционных в портативном устройстве хранения). Это оставляет некоторое число блоков (четыре в данном примере), которые доступны, чтобы стать отображенными в области логического адреса.

Эти блоки, упоминаемые как «ожидающие блоки», показаны как 25 в таблице отображения адреса памяти на Фиг.3. Эти блоки находятся в стертом состоянии. Когда блок удален из начала очереди, все другие блоки передвигаются вверх на один блок; новый блок затем вставляется в нижний ряд секции 25. Было бы удобно, если это осуществить путем приспособления четырех ячеек памяти для сохранения в каждой из них одного из индексов и для предоставления указателя, указывающего одну из этих четырех ячеек. Ячейка, на которую указывает указатель, является логически эквивалентной «верхнему ряду» секции 25. Таким образом, удаление индекса и «верхнего ряда» секции 25 и запись нового индекса в «нижний ряд» этой секции соответствует перезаписи нового индекса в ту ячейку, на которую указывает указатель, и переключению указателя способом «карусели» для указания на следующую ячейку.

Сектор 11 сохранения управляющих данных первой страницы каждого блока, который отображен в соответствующую область логического адреса, включает индекс соответствующей области логического адреса (если число битов, необходимых для сохранения этого индекса, больше, чем число битов, доступных в секторе 11 первой страницы, индекс может быть закодирован и сохранен в секторах 11 более чем одной страницы соответствующего блока). Таким образом, если питание указанного устройства отключается (так что таблица отображения адреса памяти на Фиг.3 утеряна из ОЗУ), то, когда это устройство снова подключается к питанию, главный узел 7 управления способен регенерировать таблицу отображения адреса памяти в своем ОЗУ, используя индексы, сохраненные в секторах 11 сохранения управляющих данных.

Теперь мы рассмотрим работу первого варианта осуществления настоящего изобретения, ссылаясь на блок-схему, показанную на Фиг.4. На этапе 1 происходит получение предписания, а на этапе 2 главный узел 7 управления определяет, является ли это предписание предписанием ЧТЕНИЕ или предписанием ЗАПИСЬ.

Предположим, предписание является предписанием ЧТЕНИЕ для считывания данных, начиная с логического адреса 67. На этапе 3 главный узел 7 управления использует таблицу отображения адреса памяти на Фиг.3, чтобы определить соответствующий блок, соответствующий области логического адреса, содержащей логический адрес (т.е. блок 10), и внутри этого блока страницу (страницы), соответствующие этому логическому адресу (т.е. четвертую страницу). Затем на этапе 4 осуществляется операция считывания в соответствии с известным способом: главный узел 7 управления посылает в запоминающее устройство 9 команду извлечения данных, сохраненных на четвертой странице блока 10; эти данные передаются с запоминающего устройства 9 на главный узел 7 управления посредством шины 8; главный узел управления формирует их в один или более пакетов и передает их из устройства.

Предположим, главный узел управления получает предписание ЗАПИСЬ для записи определенных данных, начиная с логического адреса 67. На этапе 5 главный узел 7 управления определяет блок и страницу, соответствующие указанному логическому адресу (как на этапе 3), а на этапе 6 главный узел управления определяет, находится ли эта страница в стертом или нестертом состоянии. Это может быть сделано, используя систему управления файлами (например, используя таблицу размещения блоков, как в прототипе, описанном выше).

Если четвертая страница блока 10 стерта, тогда главный узел 7 управления лишь посылает предписание записи на память 9, что заставляет указанную память сохранять указанные данные на четвертой странице блока 10, в соответствии с традиционными способами.

В противном случае, если четвертая страница блока 10 не стерта, тогда на этапе 8 главный узел управления предписывает запоминающему устройству скопировать в новый блок любые данные, сохраненные на первых трех страницах блока 10 и на последних 60 страницах блока 10. Этот новый блок является первым из ожидающих блоков 25, т.е. блоком 4. Затем на этапе 9 данные, включенные в предписание ЗАПИСЬ, записываются на страницу 4 блока 4. Затем на этапе 10 таблица адреса памяти обновляется в форму, показанную на Фиг.5. То есть блок 4 теперь ассоциируется с областью 1 логического адреса. Блок 10 стирается и располагается в конец очереди 25. Поскольку в очереди находятся четыре блока, блок 10 будет снова использован на четвертый раз, когда главному узлу управления предписано записать данные на страницу, которая не является стертой. Отметим, что операции на этапах с 8 по 10 могут быть осуществлены в любой другой последовательности, в соответствии с осуществлением настоящего изобретения.

Отметим, что альтернативой использованию указанным устройством системы управления файлами является пропуск этапов 6 и 7 и переход напрямую от этапа 5 к этапу 8. Другими словами, каждый раз, когда получено предписание записи, будет выполнен набор этапов с 8 по 10.

На Фиг.6 показан второй вариант осуществления настоящего изобретения. Тогда как в первом варианте осуществления изобретения каждая из 8 областей логического адреса отображена в соответствующий блок, во втором варианте осуществления изобретения каждая из областей логического адреса (по-прежнему 8 в данном примере) отображена в соответствующую группу блоков (в данном примере четырех блоков). В этом примере, число блоков равно 64, которые помечены индексом с 0 по 63. Блоки 60, 61, 62 и 63 рассматриваются как резервные. Блоки 9, 17, 18 и 27 считаются плохими. Плохие группы даны в «грязной таблице», которая показана на Фиг.6(а). Эта таблица может быть сгенерирована при первичном подключении устройства к питанию путем тестирования всех блоков и нахождения среди них плохих; следующим шагом могут быть установлены резервные блоки, убедившись, что среди них нет плохих блоков. Затем таблица плохих блоков обычно сохраняется в одном или более резервных блоков; в качестве альтернативы она может быть регенерирована каждый раз при подключении питания устройства.

На Фиг.6(б) показана таблица отображения адреса памяти. В этом случае каждая из областей логического адреса с 0 по 7 (в левой колонке 31) показана отображенной в номер группы (в средней колонке 33). Имеются 12 групп, доступных для отображения в соответственные группы областей логического адреса, и эти группы помечены соответственными групповыми индексами с 0 по 11.

Большинство групп, имея, скажем, индекс «i», составляются из набора блоков 4i-4, 4i-3, 4i-2 и 4i-1. Однако существуют блоки, которые являются исключением из этого простого правила, потому что если следовать этому правилу, то группа включала бы один или более блоков, которые являются плохими. Блоки, которые устанавливают такие группы, даны в «чистой таблице», показанной на Фиг.6(в).

Например, группа 1 - это просто первые четыре блока 0, 1, 2 и 3. Группа 2 - это второй набор четырех блоков 4, 5, 6, 7. Группа 3, однако, - это не блоки 8, 9, 10 и 11, потому что, как было сказано выше, блок 9 является плохим. Вместо этого чистая таблица на Фиг.6(в) указывает, что группа 3 составлена из блоков 8, 59, 10 и 11. Группа 4, в соответствии с обычным правилом, - это блоки 12, 13, 14, 15. Группа 5 снова является исключением из общего правила (потому что блоки 17 и 18 являются плохими) и в соответствии с чистой таблицей составлена из блоков 16, 58, 57, 19. Группа 6 снова является правильной, т.е. это блоки 20, 21, 22 и 23. Группа 7 снова является неправильной (потому что блок 27 является плохим), и в соответствии с чистой таблицей, это блоки 24, 25, 26 и 56. Группы с 8 по 11 соответствуют обычному правилу.

Таким образом, чистая таблица устанавливает членов только трех групп в этом примере: групп 3, 5 и 7. На самом деле, в более типичных вариантах осуществления настоящего изобретения доля плохих групп очень низка, так что чистая таблица намного меньше, чем таблица отображения адреса памяти. Максимальное число рядов чистой таблицы - это число плохих групп.

Чтобы указать, что группа 3 не соответствует указанному правилу, таблица отображения адреса памяти содержит флаг в третьей колонке 37, и соответствующее указание в четвертой колонке 38 на то, к какому ряду чистой таблицы на Фиг.6(в) необходимо обратиться для получения точной принадлежности указанной группы (на Фиг.6(б) значениями в четвертой колонке 38 являются соответственно 0, 1, 2, причем эти три значения помечают соответственно три ряда чистой таблицы на Фиг.6(в)).

Когда главный узел управления получает предписание ЗАПИСЬ, предписывающее ему записать определенн