Результат интеллектуальной деятельности: СПОСОБ УПРАВЛЕНИЯ ЗАПОМИНАЮЩИМ УСТРОЙСТВОМ, ВКЛЮЧАЮЩИМ В СЕБЯ ЭЛЕМЕНТЫ, В КОТОРЫХ ПРЕДУСМОТРЕНА ИНФОРМАЦИЯ ИДЕНТИЧНОСТИ, ОБОЗНАЧАЮЩАЯ ПРОИСХОЖДЕНИЕ УПОМЯНУТЫХ ЭЛЕМЕНТОВ

Настоящее изобретение относится к способу управления запоминающим устройством, таким как электрически стираемое программируемое постоянное запоминающее устройство (СППЗУ, EEPROM). Такое запоминающее устройство можно использовать, например, в картах с микропроцессорами.

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

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

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

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

Цель изобретения

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

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

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

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

Предпочтительно, все биты информации идентичности наивысшего элемента в иерархии имеют первое значение.

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

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

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

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

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

При обращении к приложенным чертежам:

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

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

Подробное описание изобретения

На чертежах представлено запоминающее устройство типа СППЗУ, в общем, обозначенное номером 1 ссылочной позиции.

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

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

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

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

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

Потомки элемента 0000 0000, таким образом, имеют следующую информацию идентификации соответственно: 1000 0000; 0100 0000; 0010 0000; 0001 0000; 0000 1000; 0000 0100; 0000 0010 и 0000 0001.

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

Таким образом, количество потомков, которые могут принадлежать каждому из элементов: 1000 0000; 0100 0000; 0010 0000; 0001 0000; 0000 1000; 0000 0100; 0000 0010 и 0000 0001, соответственно, составляет: 7; 6; 5; 4; 3; 2; 1 и 0.

Элемент 1000 0000 (ранг 1) имеет три потомка в данном варианте воплощения со следующей соответствующей информацией идентичности: 1100 0000; 1010 0000 и 1001 0000.

Элемент 1100 0000 (ранг 2) также имеет три потомка, со следующей соответствующей информацией идентичности: 1100 0000; 1101 0000 и 1100 1000. Элемент 1100 0000 может иметь три дополнительных потомка.

Элемент 1110 0000 (ранг 3) имеет одного потомка с информацией идентичности 1111 0000. Элемент 1110 0000 может иметь четыре других потомка.

Элемент 1100 1000 (ранг 3) также имеет три потомка, имеющих следующую соответствующую информацию идентичности: 1100 1100; 1100 1010 и 1100 1001. Количество потомков, которые может иметь каждый их этих элементов 1100 1100, 1100 1010, 1100 1001, составляет, соответственно, 2, 1 и 0.

Элемент 0000 0100 (ранг 1) имеет два потомка в этом варианте воплощения, имеющих следующую соответствующую информацию идентичности: 0000 0110 и 0000 0101.

Элемент 0000 0110 (ранг 2) имеет (и может иметь только) одного потомка с информацией идентичности 0000 0111. Элемент 0000 0101 не может иметь ни одного потомка.

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

Таким образом, при достижении элемента 0000 0111, известно, что его последовательные предшественники представляют собой элементы: 0000 0110; 0000 0100 и 0000 0000.

Если предположить, что элемент 0000 0100 имеет доступ, ограниченный авторизованными лицами, легко понять, что элемент 0000 0111 также имеет ограниченный доступ.

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

Способ в соответствии с изобретением, таким образом, позволяет воплотить формирование логических (в отличие от физических) цепочек между элементами.

На фиг.2 запоминающее устройство 1 представлено в линейном виде и включает в себя зону 5 быстрого доступа.

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

Кроме того, после удаления одного из элементов 2, например элемента 0000 0001, из запоминающего устройства 1 выполняют перегруппировку оставшихся элементов:

элементы 0000 0110 и 0100 1110 затем просто перемещают ближе к другим элементам.

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

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

В частности, информация идентичности может быть кодирована по некоторому другому количеству битов. Таким образом, в описанном примере, информация идентичности кодирована по восьми битам, но она может быть кодирована по большему количеству битов. Кроме того, наибольший элемент не обязательно должен иметь все его биты, равные одинаковому значению, при этом наибольший элемент может иметь информацию идентичности 1111 1111, и его потомки могут представлять собой 0111 1111, 1011 1111, 1101 1111, 1110 1111 и так далее.

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