Портативное устройство хранения данных с использованием таблицы отображения адресов памяти
Предложено портативное устройство хранения данных, которое включает контроллер (2) универсальной последовательной шины (USB-контроллер), главный узел (7) управления и устройство (9) флэш-памяти И-НЕ. Главный узел (7) управления получает данные, которые должны быть записаны на логические адреса, и предписания на считывание данных с логических адресов. Он использует таблицу отображения адреса памяти, чтобы ассоциировать указанные логические адреса с физическими адресами в запоминающем устройстве (9), и записывает данные на физический адрес, соответствующий этому логическому адресу, или считывает данные с него. Указанное отображение изменяется время от времени так, чтобы разные области физического адреса ассоциировались в разное время с указанными логическими адресами. Это увеличивает скорость указанного устройства и также означает, что никакие физические адреса не выходят из строя быстро из-за постоянного ассоциирования с логическими адресами, на которые данные записываются относительно часто. 17 з.п. ф-лы, 9 ил.
Область техники
Настоящее изобретение относится к портативным устройствам хранения данных и способам использования этих устройств для сохранения и извлечения данных, записанных на них.
Уровень техники
В последние несколько лет возник большой интерес к созданию устройств хранения данных, которые содержат флэш-память и которые могут быть подсоединены к последовательной шине компьютера. Главным документом в данной области является 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(в)).
Когда главный узел управления получает предписание ЗАПИСЬ, предписывающее ему записать определенные данные на логический адрес 67, то в этом случае он идентифицирует, что логический адрес находится внутри области 0 логического адреса (поскольку область 0 логического адреса представляет собой логические адреса с 0 по 255). Отображение между логическими адресами и группами на Фиг.6(б) показывает, что соответствующей группой является группа 2. Соответствующий флаг колонки 37 не установлен, так что нет необходимости консультироваться у чистой таблицы по поводу идентификации блоков, соответствующих группе 2: указанное правило дает их как 4, 5, 6 и 7. Логический адрес 67 является, таким образом, четвертой страницей в блоке 5.
Если эта страница находится в стертом состоянии, тогда данные из предписания ЗАПИСЬ записываются на ту страницу.
Если эта страница не находится в стертом состоянии, тогда данные в предписании ЗАПИСЬ записываются на четвертую страницу второго блока группы, находящейся во главе очереди 35, и которая оказывается группой 7. Затем таблица отображения адреса памяти на Фиг.6(б) обновляется, чтобы стать Фиг.6(г) путем перемещения номера группы во главе очереди (т.е. номера 7 группы) в колонку 33 в ряду, соответствующем области 0 логического адреса, и также путем копирования флага, указывающего, что блок 7 является неправильным, в тот же самый ряд третьей колонки 37, а соответствующие данные, указывающие ряд чистой таблицы, - в новый ряд четвертой колонки 38. Любые данные, сохраненные на других страницах блоков 4, 5, 6 и 7, копируются на соответствующие страницы группы 7 (т.е. соответственные страницы блоков 24, 25, 26 и 56 соответственно).
Если позднее получено предписание ЧТЕНИЕ для адреса 67 логической памяти, главный узел 7 управления снова определяет, что оно соответствует логической области 0, и поэтому проверяет соответствующий ряд в таблице отображения адреса памяти на Фиг.6(г). На этот раз он обнаруживает в колонке 33, что соответствующая группа - это группа 7, а флаг в колонке 37 указывает, что эта группа является неправильной. Колонка 38 указывает, что эта группа находится в ряду 2 (т.е. в последнем ряду) чистой таблицы на Фиг.6(в). На этом основании главный узел управления извлекает блоки этого ряда (т.е. блоки 24, 25, 26, 56) из чистой таблицы на Фиг.6(в). Он считывает данные с четвертой страницы второго блока группы 7 (т.е. блока 25), генерирует один или более пакетов данных, закодировав эти данные, и передает этот пакет (эти пакеты) из устройства через интерфейс 3.
Если снова получено предписание записи для адреса 67 логической памяти, главный узел 7 управления снова проверяет соответствующую позицию в таблице отображения адреса памяти на Фиг.6(г). На этот раз он обнаруживает, что соответствующая группа - это группа 7, а флаг в колонке 37 указывает, что эта группа является неправильной. На этом основании главный узел управления извлекает из колонки 38 номер соответствующего ряда (т.е. 2) и получает блоки этого ряда (т.е. блоки 24, 25, 26, 56) из чистой таблицы на Фиг.6(в). Он инспектирует четвертую страницу второго блока группы 7 (т.е. блок 25), чтобы определить, сохранены ли в нем данные (которые, конечно, там сохранены, как было объяснено выше). Поэтому он перемещает все данные, сохраненные на других страницах указанной группы, на соответствующие страницы группы, которая теперь находится во главе очереди 35 (т.е. группы 4) и записывает указанные данные предписания ЗАПИСЬ на четвертую страницу второго блока этой группы. Затем он вставляет номер 4 в колонку 33 верхнего ряда, копирует (пустой) флаг, соответствующий группе 4 в колонку 37 верхнего ряда, копирует (пустые) данные, соответствующие группе 4, в колонку 38 верхнего ряда, вставляет индекс 7 в нижнюю часть секции 35 указанной таблицы (переместив другие ряды вверх на один ряд), копирует соответствующий флаг в нижний ряд колонки 37 и копирует соответствующие данные в нижний ряд колонки 38.
Отметим, что график операций, соответствующий этому процессу, является почти идентичным процессу на Фиг.4. Однако необходимо понимать, что этапы 3 и 5 являются теперь более усовершенствованными. Вместо того чтобы блок определялся только исходя из его логического адреса и таблицы отображения адреса памяти (например, на Фиг.3), он определяется путем использования таблицы отображения адреса памяти (например, на Фиг.6(б) и 6(г)) для получения соответствующей группы и определения блоков группы (исходя из правила или, если в колонке 37 таблицы отображения адреса памяти присутствует флаг, из ряда, указанного в колонке 38 чистой таблицы на Фиг.6(в)). Также на этапах 8, 9 ссылка на первый ожидающий блок в этом случае должна быть понята как ссылка на соответствующий блок первой ожидающей группы (т.е. группы наверху секции 35 таблицы отображения адреса памяти).
Это описывает, как второй вариант осуществления изобретения управляет отображением между областями логического адреса и соответственными группами блоков. Логически отдельной проблемой является проблема того, как этот вариант осуществления отображает логические адреса внутри любой заданной области логического адреса в соответственные страницы в соответствующей группе блоков.
Одной возможностью является, чтобы соответствие было так называемым «горизонтальным». Это означает, что последующие страницы блоков должны соответствовать последующим логическим адресам. Последняя страница каждого блока (за исключением последнего блока группы) соответствует логическому адресу, за которым последовательно следует логический адрес, соответствующий первой странице следующего блока группы. Таким образом, например, количество данных, которое немного больше, чем число страниц одиночного блока, будет записано в память таким образом, что начало указанных данных записывается на страницу, указанную логическим адресом, затем данные записываются на последующие страницы блока до тех пор, пока этот блок не использован полностью, затем оставшаяся часть данных записывается на первые страницы следующего блока.
Однако это не единственная возможность. В предпочтительной форме второго варианта осуществления настоящего изобретения главный узел управления может работать так, что логическое соответствие адресов страницам указанной группы блоков является «вертикальным». А именно (предполагая, ради примера, что в заданной группе существуют четыре блока) первые четыре логических адреса могут быть отображены в первые страницы каждого из блоков (т.е. первый логический адрес в первую страницу первого блока группы; второй логический адрес в первую страницу второго блока группы и так далее), следующие четыре логических адреса могут быть отображены на вторые страницы каждого из блоков (т.е. пятый логический адрес во вторую страницу первого блока группы; шестой логический адрес во вторую страницу второго блока группы и так далее).
Иначе говоря, главный узел 7 управления рассматривает наборы четырех последовательных логических адресов как соответствующие соответственно соответственным страницам соответственных блоков. Все страницы, ассоциированные с заданным набором логических адресов, имеют ту же величину сдвига, измеренную путем горизонтального подсчета вдоль страниц соответственного блока (т.е. эти страницы образуют «колонку» в пространстве физического адреса).
На Фиг.6(д) показано, что происходит, когда определенное количество данных должно быть записано в ячейку группы 2 (т.е. блоки 4, 5, 6 и 7). Логический адрес, на который записывается начало данных, имеет сдвиг на 17 по отношению к логическому адресу, который соответствует первой странице блока 4. То есть логический адрес, на который записывается начало указанных данных, расположен через 17 страниц после первой страницы указанной группы. Эти страницы подсчитываются вертикально на Фиг.6(д) (т.е. сначала сверху вниз в первой колонке страниц, затем сверху вниз в следующей колонке). Таким образом, страница со сдвигом 17 является страницей, обозначенной буквой «А».
В операции записи данные из указанной старой группы копируются в ячейки в группе 2, обозначенной заштрихованной областью 32. Затем данные в пакете записи записываются на страницы в заштрихованной области 34 (т.е. начиная с ячейки А). Затем любые данные в старом блоке, которые находятся в незаштрихованной области 36, следующей за областью 34, копируются в область 34.
Обратимся теперь к третьему варианту осуществления настоящего изобретения. Третий вариант осуществления изобретения напоминает первый вариант осуществления настоящего изобретения, но с одним (важным) отличием. В третьем варианте осуществления изобретения, следуя предписанию ЗАПИСЬ, которое заставляет изменить отображение, установленное в таблице отображения адреса памяти, и данные, содержащиеся в предписании ЗАПИСЬ, которые должны быть записаны в ячейку нового блока, которая становится ассоциированной с логическим адресом, операция копирования данных из остатка старого блока в новый блок частично приостановлена на предопределенное время, чтобы увидеть, получены ли какие-нибудь новые предписания ЗАПИСЬ в отношении той же области пространства памяти.
А именно, допустим, что получено предписание ЗАПИСЬ, указывающее, что данные А должны быть записаны на определенный логический адрес. Допустим, что тот логический адрес является областью логического адреса, в настоящее время соответствующей блоку 0. Допустим, кроме того, что указанный логический адрес соответствует странице 4 блока 0. Кроме того, допустим, что стертый блок вверху очереди 25 (на Фиг.3) является блоком 3. Фиг.7(а) показывает группу физической памяти, включающей блоки 0 и 3. То есть в блоке 0 данные, помеченные как X, сохранены на странице с 0 по 3, данные, помеченные как Y, сохранены на странице 4, данные, помеченные как Z на страницах с 5 по 7, и затем остальная часть блока находится в стертом состоянии (показанном как «0»).
В соответствии с первым вариантом осуществления изобретения это предписание ЗАПИСЬ немедленно заставило бы физическую память в блоках 0 и 3 стать, как показано на Фиг.7(б). То есть новые данные А сохраняются на странице 4, а данные Х и Z сохраняются на страницах блока 3, соответствующих их предыдущим страницам в блоке 0. Блок 0 был бы стерт (а индекс, отображающий его, находился бы внизу секции 25 на Фиг.3).
Однако в третьем варианте осуществления настоящего изобретения физическая память вместо этого вначале переписывается, как показано на Фиг.7(в). То есть данные А записываются на страницу 4 блока 3, и данные Х копируются на страницы от 0 до 3, но данные Z пока еще не копируются на страницы с 5 по 7 блока 3. Система остается в этой конфигурации на период времени, заданный таймером. Если к концу этого периода не был получен дальнейший сигнал ЗАПИСЬ в отношении логического адреса, соответствующего странице 5 блока 3, то операция записи завершается, чтобы сохранить данные, как показано на Фиг.7(б).
Однако если в течение этого периода получено новое предписание ЗАПИСЬ, которое указывает, что данные В должны быть сохранены на логический адрес, соответствующий теперь странице 5 блока 3, то эти данные В записываются на страницу 5 блока 3, сохраняя данные, как показано на Фиг.7(г). Затем таймер включается снова, чтобы установить новый период времени.
Если к концу этого периода не был получен дальнейший сигнал ЗАПИСЬ в отношении логического адреса, соответствующего странице 6 блока 3, то операция записи завершается, чтобы сохранить данные, как показано на Фиг.7(д). Однако если в течение этого периода получено новое предписание ЗАПИСЬ, которое указывает, что данные С должны быть сохранены на логический адрес, соответствующий теперь странице 6 блока 3, то эти данные В записываются на страницу 6 блока 3, и снова включается таймер.
Этот процесс может быть продолжен до тех пор, пока не будет достигнута последняя страница блока 3 или истечет период времени, за который не будет получено предписание ЗАПИСЬ, указывающее данные, которые должны быть сохранены на этой странице, следуя ячейке, указанной предыдущим предписанием ЗАПИСЬ. Отметим, что это означает, что данные А, В, ... могут быть записаны на запоминающее устройство гораздо быстрее, чем в первом варианте осуществления, поскольку необходимость копировать данные значительно сокращается. Например, во время последовательности этапов, описанных выше, данные Х необходимо скопировать только один раз, в самом начале, вне зависимости от того, сколько предписаний ЗАПИСЬ получено потом в отношении последующих страниц.
На Фиг.8 показана блок-схема, и она отличается от Фиг.4 только тем, что этапы с 8 по 10 заменены этапами с 8 по 13. На этапе 8 на Фиг.8 только страницы в старом блоке (т.е. блоке 0), находящиеся перед той страницей, в отношении которой было получено предписание ЗАПИСЬ, копируются в новый блок (т.е. блок 3), и данные в предписании ЗАПИСЬ записываются на страницу в новом блоке, соответствующую логическому адресу. На этапе 9 определяется, были ли сейчас записаны данные на последнюю страницу нового блока. Если да, то указанное устройство переходит к этапу 13. В противном случае, на этапе 10 устройство определяет, получено ли, в пределах предопределенного времени, новое предписание ЗАПИСЬ в отношении следующей по порядку страницы нового блока. Если да, то этот вариант осуществления изобретения записывает туда данные на этапе 11 и возвращается к этапу 9. Если нет, на этапе 12 данный вариант осуществления копирует остальные страницы старого блока (т.к. все страницы, если таковые остались, после последней страницы, в отношении которой было получено предписание ЗАПИСЬ). Этап 13 соответствует этапу 10 на Фиг.4: старый блок (блок 0) стирается, и таблица отображения адреса памяти обновляется.
Отметим, что если в то время, когда этот вариант осуществления находится на этапе 10, получено предписание ЧТЕНИЕ в отношении логического адреса в области логического адреса, которая в настоящее время является предметом процесса на Фиг.8, то указанное устройство должно считать данные с правильного места в физической памяти (т.е. из нового блока, если логический адрес соответствует адресам, на которые была произведена запись на этапе 8, или если логический адрес соответствует адресу, на который была произведена запись на предыдущем этапе 9, в противном случае из старого блока).
В определенных формах данного варианта осуществления указанное устройство может перейти от этапа 10 к этапу 12 также в том случае, если на этапе 10 оно установило, что получено новое предписание ЗАПИСЬ, которое предписывает запись данных на любой логический адрес, за исключением следующей по порядку страницы нового блока. В этом случае обработка нового предписания ЗАПИСЬ может начаться после того, как процесс на Фиг.4 завершен.
Отметим, что таймер обычно устанавливается на период нескольких миллисекунд, например, около 3 мс. Если устройство отключается от главного компьютера в течение предопределенного периода после получения последнего предписания ЗАПИСЬ, то существует опасность потери данных. Однако если предопределенный период устанавливается в размере миллисекунд, подобное не должно произойти, и таким образом все данные будут надежно сохранены. Отметим, что третий вариант осуществления настоящего изобретения сокращается по отношению к первому варианту осуществления в пределах предопределенного периода, стремящегося к нулю.
Обратимся теперь к четвертому варианту осуществления настоящего изобретения. Подобно третьему варианту осуществления, четвертый вариант осуществления использует таймер.
Главный узел 7 управления в этом случае включает узел распознавания образов, который получает логические адреса, извлеченные главным узлом управления из предписаний ЗАПИСЬ. Если во время определенной фазы операции узел распознавания образов отмечает, что определенные логические адреса появляются гораздо чаще, чем ожидалось бы, то он записывает этот адрес логической памяти в пространство «часто используемого логического адреса», например, установленное в ОЗУ главного узла управления. В целом, пространство часто используемого логического адреса может содержать множество таких идентифицированных логических адресов, обладающих высокой частотностью. Узел распознавания образов может быть запрограммирован для исключения логических адресов из этого пространства, когда их частотность сокращается, и/или для замены их в указанном пространстве, каждый раз, когда идентифицирован логический адрес, обладающий еще более высокой частотностью использования. Таким образом, указанное пространство непрерывно сохраняет логические адреса, которые наиболее часто повторяются в предписаниях ЗАПИСЬ.
Главный узел 7 управления поддерживает кэш ОЗУ для каждой ячейки в пространстве часто используемого адреса. После получения предписания ЗАПИСЬ в отношении одного из адресов, сохраненных в пространстве часто используемого логического адреса, главный узел управления сначала не записывает данные, содержащиеся в предписании ЗАПИСЬ, на устройство флэш-памяти. Вместо этого он записывает эти данные в соответствующий кэш. Затем главный узел 7 управления ждет в течение времени, установленного таймером. Если в течение этого времени не получено дальнейшего предписания ЗАПИСЬ (или в одной из форм этого варианта осуществления, если получен пакет в отношении другого блока), то главный узел управления записывает данные в кэш на флэш-память, в соответствии с процессом, описанным выше относительно любого из вариантов с первого по третий осуществления настоящего изобретения. Если, с другой стороны, в течение предопределенного периода времени получено другое предписание ЗАПИСЬ в отношении того же логического адреса, то главный узел управления записывает данные, содержащиеся в том предписании ЗАПИСЬ в ту же ячейку своего кэша (т.е. записывает поверх данных, которые были туда записаны по причине первого пакета записи). Затем опять включается таймер.
Таким образом, очевидно, что если указанное устройство 1 получает в отношении того же адреса логической памяти большое число предписаний ЗАПИСЬ, разделенных средней продолжительностью, которая короче, чем предопределенное время, установленное таймером, число этих предписаний ЗАПИСЬ, которые вызовут операцию записи (с большим объемом вычислений) на запоминающее устройство 9, будет низким.
На Фиг.9 показана структура части главного узла 7 управления. Главный узел 7 управления содержит секцию 51 для разделения предписания ЗАПИСЬ на логический адрес и данные, которые должны быть записаны на этот логический адрес. Логический адрес посылается на узел 53 распознавания образов, который использует его для обновления пространства 55 часто используемого адреса. Главный узел управления имеет переключатель 56, который устанавливает, находится ли логический адрес только что полученного предписания ЗАПИСЬ в пространстве 55 часто используемого адреса. Если нет, данные и логический адрес немедленно записываются на узел 57, который записывает их на флэш-память 9 в соответствии со способом первого варианта осуществления. Если так, то указанные данные записываются на кэш-память 59, и таймер в реле 61 времени приводится в действие. Если таймер в реле 61 времени достигает конца предопределенного периода и при этом не переустанавливается, данные и соответствующий логический адрес передаются переключателем 57 из кэша 59 на узел 57. Отметим, что хотя Фиг.9(а) показывает только одиночное реле 61 времени, реле 61 времени обычно содержит соответственный таймер для каждого из соответственных логических адресов в пространстве часто используемого логического адреса, и для каждого из этих логических адресов существует соответственная ячейка кэш-памяти.
Если получено предписание ЧТЕНИЕ, узел 63 определяет, является ли указанный логический адрес одним из логических адресов, сохраненных в пространстве часто используемого адреса, и если это так, определяет, работает ли соответствующий таймер. Если это так, он считывает данные из соответствующей кэш-памяти 59; в противном случае, он использует узел 67 для считывания данных из флэш-памяти 9, в соответствии с соотношением, установленным таблицей отображения адреса памяти (т.е. в соответствии со способом первого варианта осуществления). В любом случае он кодирует данные в пакет, который передается из указанного устройства через интерфейс 3.
Блок-схема этого варианта осуществления показана на Фиг.4, за исключением того, что этапы на Фиг.9(6) вставляются между этапами 2 и 3 на Фиг.4 (и осуществляются узлами 51 и 57) и этапы на Фиг.9(с) вставляются между этапами 2 и 5 на Фиг.4 (и осуществляются узлом 63). На этапах 7 и 9 данные, которые записываются на указанную страницу, являются данными в последнем предписании ЗАПИСЬ, полученном в отношении этого логического адреса.
Каждый раз, когда узел 53 перемещает логический адрес из пространства часто используемого логического адреса (т.е. обновляет узел 55), указанные данные в соответствующей ячейке кэша 59 записываются на память 9, в соответствии с этапами с 5 по 10 на Фиг.4.
В третьем и/или четвертом вариантах осуществления настоящего изобретения таймер может выполняться с возможностью установления предопределенного периода всего на несколько миллисекунд, например, около 3 мс. Если устройство отключается от главного компьютера в течение предопределенного периода после получения последнего предписания ЗАПИСЬ, то существует опасность потери данных. Однако если предопределенный период устанавливается в размере миллисекунд, подобное не должно произойти, и таким образом все данные будут надежно сохранены. Отметим, что третий и четвертый варианты осуществления настоящего изобретения каждый сокращается по отношению к первому варианту осуществления в пределах предопределенного периода, стремящегося к нулю.
Отметим, что ни один из вариантов осуществления, описанный выше, не нуждается в таблице размещения блоков (хотя возможны другие варианты осуществления, которые подобную таблицу используют).
Хотя здесь было детально описано только несколько вариантов осуществления изобретения, в пределах объема притязаний изобретения возможно множество видоизменений, как должно быть ясно специалисту в данной области техники. Например, функции второго, третьего и четвертого вариантов осуществления могут быть легко соединены в любом сочетании, и, конечно, сочетание всех описанных функций (включая вертикальное сохранение страниц групп блоков) является предпочтительным. Таким образом, возможно формирование варианта осуществления настоящего изобретения, в котором области логического адреса отражаются в соответствующие группы, составленные из множества блоков, в которых логические адреса внутри заданной области логического адреса соответствуют колонке внутри группы блоков, в которых первый сигнал таймера используется для приостановки копирования данных из старой группы в новую группу и в которых второй (необязательно другой) сигнал таймера используется для приостановки записи данных, содержащихся в предписании ЗАПИСЬ, на устройство 9 флэш-памяти.
Кроме того, в вышеуказанных вариантах осуществления изобретения используется только одно устройство флэш-памяти И-НЕ. Однако настоящее изобретение не ограничено в этом отношении, и возможно использование более чем одного устройства флэш-памяти И-НЕ, которое приводится в действие в соответствии с принципами настоящего изобретения, описанными выше. Например, каждое из устройств памяти И-НЕ может быть ассоциировано с конкретной соответственной частью пространства логического адреса, и может существовать переменное отображение для каждого устройства памяти И-НЕ между блоками того запоминающего устройства и соответственными областями соответствующей части пространства логического адреса.
Как было упомянуто выше, настоящее изобретение может быть осуществлено посредством USB-соединения - хотя оно не ограничивается в этом отношении. Предпочтительно, чтобы стандарт универсальной последовательной шины (USB), используемый USB-контроллером, был версией USB 2.0, но настоящее изобретение может быть осуществлено с любыми другими версиями USB-стандарта, такими как любые версии, которые будут внедрены в будущем.
Общая емкость памяти указанного устройства не ограничивается в пределах объема притязаний этого изобретения, но предпочтительно является, по меньшей мере, 1 мегабайт и обычнее, по меньшей мере, 10 мегабайт, по меньшей мере, 100 мегабайт или даже, по меньшей мере, 1 гигабайт.
1. Портативное устройство хранения данных, включающее
(1) интерфейс данных для передачи пакетов данных на устройство и с него,
(2) контроллер интерфейса,
(3) главный узел управления,
и (4) по меньшей мере, одно устройство флэш-памяти И-НЕ,
при этом контроллер интерфейса выполнен с возможностью пересылки данных, полученных через интерфейс, на главный узел управления,
причем главный узел управления выполнен с возможностью распознавания определенных пакетов данных в качестве закодированных предписаний ЧТЕНИЕ и других пакетов данных в качестве закодированных предписаний ЗАПИСЬ
(а) для того, чтобы по получении предписания ЧТЕНИЕ, указывающего логический адрес, получить доступ к таблице отображения адреса памяти, которая ассоциирует области логического адреса внутри пространства логической памяти с соответственными первыми областями физического адреса внутри запоминающего устройства, считывать данные с физического адреса в запоминающем устройстве, соответствующие логическому адресу в соответствии с таблицей отображения адреса, и передавать на интерфейс данных один или более пакетов данных, включая данные, которые были считаны,
и (б) для того, чтобы по получении предписания ЗАПИСЬ, указывающего логический адрес и данные, которые должны быть записаны на этот логический адрес, определить, находится ли в стертом состоянии физический адрес, соответствующий логическому адресу в соответствии с таблицей отображения адреса памяти, и
если да, то записать данные на тот физический адрес,
или если нет, то модифицировать таблицу отображения адреса для ассоциирования второй области физического адреса с областью логического адреса, содержащей логический адрес, записать данные на физический адрес, соответствующий логическому адресу в соответствии с модифицированной таблицей отображения адреса памяти, и скопировать любые данные, сохраненные в других группах первой области физического адреса в соответствующие ячейки второй области физического адреса,
где данные, определяющие таблицу отображения адреса памяти, сохраняются как данные отображения в устройстве флэш-памяти, причем главный узел управления выполнен с возможностью модифицирования данных отображения после модифицирования таблицы отображения адреса памяти,
и где главный узел управления выполнен с возможностью извлечения данных отображения с устройства флэш-памяти и генерирования таблицы отображения адреса памяти внутри ОЗУ после инициирования.
2. Устройство по п.1, в котором указанная часть данных отображения, определяющих отображение между каждой соответственной областью физического адреса и областью логического адреса, сохраняется внутри той области физического адреса.
3. Устройство по п.2, в котором данные отображения, относящиеся к заданной области физического адреса, сохраняются в секторе сохранения управляющих данных одной или более страниц области физического адреса.
4. Устройство по любому из предыдущих пунктов, в котором пространство физической памяти включает
(1) области физической памяти, ассоциированные с областями логического адреса таблицей отображения адреса памяти,
и (2) области ожидающей физической памяти, которые могут стать ассоциированными с логическими адресами под управлением главного узла управления, который модифицирует таблицу отображения адреса памяти.
5. Устройство по п.4, в котором области ожидающей физической памяти находятся в стертом состоянии.
6. Устройство по п.5, в котором пространство физической памяти дополнительно включает области резервной физической памяти, которые не могут стать ассоциированными с указанными логическими адресами под управлением главного узла управления, который модифицирует таблицу отображения адреса памяти.
7. Устройство по п.6, в котором области физического адреса являются соответственными блоками запоминающего устройства.
8. Устройство по п.6, в котором области физического адреса являются группами блоков в запоминающем устройстве, причем группы определены в соответствии с группировочной таблицей.
9. Устройство по п.8, в котором большинство групп блоков определены в соответствии с правилом, и группировочная таблица определяет группы, которые являются исключениями из этого правила.
10. Устройство по п.9, в котором таблица отображения адреса памяти содержит флаг в отношении любой области логического адреса, которая ассоциируется с одной из тех групп, которые являются исключением из указанного правила.
11. Устройство по любому из пп.8-10, в котором главный узел управления ассоциирует последовательно следующие логические адреса внутри области логического адреса с соответственными страницами в разных блоках.
12. Устройство по п.11, в котором главный узел управления ассоциирует последовательные логические адреса в наборы, при этом каждый из этих наборов логических адресов имеет число элементов, равное числу блоков в каждой группе, и для каждого заданного набора главный узел управления ассоциирует логические адреса того набора с соответствующими страницами соответственных блоков.
13. Устройство по п.12, в котором главный узел управления выполнен с возможностью, в ответ на прием первого предписания ЗАПИСЬ, выполнения предписания записи только после определения, что в течение предопределенного периода не получено второе предписание ЗАПИСЬ, подчиняясь предопределенному критерию подобия.
14. Устройство по п.13, в котором, после модификации таблицы модификации адреса памяти по отношению к заданной области логического адреса и до указанного копирования данных из первой области физического адреса в новую вторую область адреса, указанным критерием является то, относится ли второе предписание ЗАПИСЬ к логическому адресу, соответствующему ячейке внутри заданной области логического адреса тех данных, которые должны быть скопированы, и в случае, если такое предписание ЗАПИСЬ получено, оно прерывает указанную операцию копирования и вместо этого записывает данные, указанные во втором предписании ЗАПИСЬ, в указанную ячейку второй области физического адреса.
15. Устройство по п.13, в котором главный узел управления имеет доступ к кэшу данных, и в ответ первое предписание ЗАПИСЬ записывает данные в кэш данных, при этом указанным критерием является то, что второе предписание ЗАПИСЬ относится к тому же логическому адресу, что и первое предписание, причем в случае, если указанное определение является положительным, то данные, указанные во втором предписании ЗАПИСЬ, записываются в кэш данных.
16. Устройство по п.13, в котором главный узел управления имеет доступ к кэшу данных, и в ответ первое предписание ЗАПИСЬ записывает данные в кэш данных, при условии, что предписание ЗАПИСЬ относится к одному или более избранным логическим адресам, при этом указанным критерием является то, что второе предписание ЗАПИСЬ относится к тому же логическому адресу, что и первое предписание, причем в случае, если указанное определение является положительным, то данные, указанные во втором предписании ЗАПИСЬ, записываются в кэш данных.
17. Устройство по п.16, в котором существует множество указанных избранных логических адресов.
18. Устройство по п.16 или 17, дополнительно включающее узел распознавания образов, предназначенный для распознавания логических адресов, закодированных в предписаниях ЗАПИСЬ, которые возникают с относительно высокой частотностью, и для размещения указанных распознанных логических адресов в качестве указанных избранных логических адресов.
