Устройство и способ обработки информации - RU2182722C2

Чертежи

Показать все 31 чертежа(ей)

Описание

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

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

Воспроизведение этого CD-R возможно с помощью обычного дисковода CD-ROM, в котором все данные записаны и подготовлены, например, на жестком диске, в результате чего CD-R, на котором делается запись, можно использовать в качестве компакт-диска (CD), записывая все данные на этот CD-R.

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

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

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

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

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

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

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

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

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

Перечень фигур
Фиг. 1 - блок-схема, изображающая всю конструкцию устройства с диском CD-R в соответствии с настоящим изобретением.

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

Фиг. 3 - условная схема, иллюстрирующая управление множеством адресных пространств при помощи диспетчера последовательности (SQM).

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

Фиг. 5 - условная схема, иллюстрирующая механизм управления при помощи В-лучевого дерева.

Фиг.6 - условное изображение, демонстрирующее таблицу соответствия путем расширения.

Фиг.7 - условное изображение, демонстрирующее таблицу узлов.

Фиг. 8 - условное изображение, поясняющее максимальное число номера блока.

Фиг. 9(А) и 9(В) - условные изображения, иллюстрирующие обновление блока данных.

Фиг.10 - блок-схема алгоритма, иллюстрирующая флэш-операцию.

Фиг.11(А)-11(D) - условные изображения, демонстрирующие логическую структуру диска CD-R.

Фиг.12 - условное изображение, демонстрирующее структуру FVD.

Фиг.13 - условное изображение, демонстрирующее структуру суперблока.

Фиг.14 - условное изображение, демонстрирующее структуру элемента списка суперблока.

Фиг. 15 - условное изображение, демонстрирующее структуру элемента подпитки.

Фиг.16 - условное изображение, демонстрирующее структуру таблицы узлов.

Фиг. 17 - условное изображение, демонстрирующее узел индексов В-лучевого дерева.

Фиг. 18 - условное изображение, демонстрирующее структуру записи индексов.

Фиг. 19 - условное изображение, демонстрирующее структуру узла листа В-лучевого дерева последовательности.

Фиг.20 - условное изображение, демонстрирующее структуру расширенной записи.

Фиг. 21 - условное изображение, демонстрирующее структуру узла листа В-лучевого дерева каталога.

Фиг. 22 - условное изображение, демонстрирующее структуру области записи каталога.

Фиг. 23 - условное изображение, демонстрирующее структуру записи каталога.

Фиг. 24 - условное изображение, демонстрирующее структуру записи каталога.

Фиг.25 - условное изображение, иллюстрирующее вид типа.

Фиг. 26 - условное изображение, демонстрирующее структуру кода каталога файлов.

Фиг. 27 - условное изображение, демонстрирующее структуру записи каталога.

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

Фиг.29 - блок-схема алгоритма, иллюстрирующая операцию "флэш всего".

Фиг. 30(А) - 30(С) - условное изображение, иллюстрирующее операцию перезаписи.

Фиг. 31 - блок-схема алгоритма, демонстрирующая процедуру обработки для контроля остающегося для записи объема носителя.

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

Сведения, подтверждающие возможность осуществления изобретения
На фиг. 1 позиция 1 обозначает устройство для CD-R диска как единое целое, содержащее устройство 4 обработки информации (процессор) для обработки данных, которые должны быть записаны на CD-R диске DISK, или данных, считываемых с CD-R диска DISK, дисплей 2, содержащий электронно-лучевую трубку или устройство жидкокристаллического дисплея для подачи обработанных данных и информации о стадии обработки, на которой находится устройство обработки информации, для пользователя, устройство 3 ввода, содержащее клавиатуру для ввода данных в устройство 4 обработки информации, а также дисковод 5 CD-R для записи данных на CD-R диск DISK и считывания их с него.

Устройство 4 обработки информации включает в себя центральный процессор (CPU) 6 для управления работой системы в целом, оперативную память (RAM) 7, постоянную память (ROM) 8, в которой хранится основная программа, необходимая для работы CPU 6, схему 9 ввода/вывода для вывода информации на дисплей 2, схему 10 ввода/вывода для приема информации из устройства 3 ввода, дисковод жесткого диска (HDD), обозначенный позицией 11, для доступа к жесткому диску, на котором записаны все программы, схему 12 интерфейса (I/F) для доступа в HDD 11, схему 13 интерфейса (I/F) для доступа в дисковод 5 CD-R. Кроме того, в дополнение к функции простой памяти RAM 7 обладает функцией кэш-памяти.

В устройстве 4 обработки информации, имеющем такую структуру, CPU 6 считывает программу файловой системы (CDRFS: файловая система записываемого компакт-диска) для CD-R через интерфейс (I/F) 12 с жесткого диска 11 на основе программы, запомненной в ROM 8, и записывает ее в RAM 7. После этого CPU 6 запускает систему, активируя CDRFS, которая считывается.

Когда данные записаны на диске CD-R DISK с помощью соответствующего запущенного устройства 1 для диска CD-R, CPU 6 преобразует данные, подготовленные пользователем, в блоки заданного формата так, что эти данные посылаются в дисковод CD-R через схему 13 интерфейса, и одновременно выдает команду записи в дисковод 5 CD-R. Дисковод 5 CD-R, который принимает эту команду, последовательно записывает принятые данные на CD-R DISK, используя единицу записи данных, называемую пакетом.

Кроме того, когда считываются данные, записанные на диске CD-R DISK, CPU 6 устройства 4 обработки информации выдает команду считывания в дисковод 5 CD-R через схему 13 интерфейса. Дисковод 5 CD-R, который принимает эту команду, обращается к диску CD-R DISK для считывания данных, которые записаны в пакете, и посылает их в RAM 7 через схему 13 интерфейса.

На фиг. 2 показана общая структура программного обеспечения SW, которое выглядит как записываемый носитель записи для пользователя. Поступающая от пользователя команда осуществить ввод через I/O интерпретируется в прикладном программном обеспечении АР и в операционной системе OS, и эта команда поступает на диспетчер файлов, FLM, файловой системы CDRFS для использования в CD-R.

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

Здесь диспетчер мнимого устройства, IMM, обеспечивает множество мнимых адресных пространств CVx (CV1, CV2, СV3,...) для диспетчера файлов, FLM, как это показано на фиг.3.

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

Другими словами, диспетчер мнимого устройства, IMM, выполнен так, что каждое мнимое адресное пространство CVx управляется ключом последовательности, SQK, и 32 разряда в верхней части ключа последовательности, SQK, присваиваются с номером последовательности, соответствующим мнимому адресному пространству CVx, a 32 разряда в нижней части представляют собой номер блока последовательности для обозначения блока BLK (фиг.3) в последовательности (мнимом адресном пространстве), обозначенном в 32 разрядах в верхней части. Следовательно, число блоков (а именно, число блоков, которое можно удерживать в мнимом адресном пространстве CVx), которыми можно управлять с помощью номера блока последовательности, составляет 2³² блоков на одно мнимое адресное пространство (одну последовательность). Каждый блок BLK составляет 2048 блоков в соответствии с форматом CD-R, так что диспетчер мнимого устройства, IMM, может управлять даже устройством, имеющим размер емкости 8 терабайт в качестве верхнего предела, как одной последовательностью (а именно, одним файлом).

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

Таким образом, если логический адрес, который прямо соответствует файлу, представленному в 64-разрядном ключе последовательности, SQK, полученном из диспетчера файлов, FLM, поступает на диспетчер мнимого устройства, IMM, то ключ последовательности, SQK, диспетчера мнимого устройства, IMM (фиг.2), обеспечивает соответствие логического адреса, представленного ключом последовательности, SQK, физическому адресу на диске CD-R путем использования способа поиска посредством разветвленного дерева, называемого В-лучевым деревом.

Другими словами, В-лучевое дерево диспетчера последовательностей, SQM, обладает структурой дерева, показанной на фиг.4, и содержит узел индексов в качестве промежуточного узла (ветви) и листовые узлы Е, F и G, имеющие расширение (EXTx), обозначающее соответствие между логическим адресом и физическим адресом.

Каждый из листовых узлов Е, F и G сохраняет один ключ последовательности, SQK, и множество ключей последовательностей, SQK, в последовательном порядке, обозначающем соотношение между логическим адресом и физическим адресом LBA, обозначенными ключом последовательности, SQK. Другими словами, расширение EXTx управляет как одной единицей строкой блоков, в которой последовательность SQK непрерывно располагается в физическом положении на диске CD-R. Расширение EXTx содержит в переднем блоке последовательность SQK и физический адрес LBA, соответствующий последовательности SQK и ее длине. Длина представляет собой номер блока непрерывного физического адреса LBA, представленный расширением EXTx, с физическим адресом, который помещен впереди него. Следовательно, например, когда расширение EXTx представлено строкой (0,0 56 5), то физический адрес LBA на диске CD-R, соответствующий ключу последовательности SQK (логический адрес) и определенный как 0,0, равен 56, и это означает, что данные, представленные этим расширением, занимают 5 блоков с физическим адресом LBA (=56), помещенным впереди на диске CD-R. 5 блоков данных, управляемых одним этим элементом EXTx, записываются в физической области, которая продолжается на диске CD-R так, чтобы можно было избежать увеличения числа расширений EXTx, которое составляет элемент таблицы преобразования адресов для логического адреса и физического адреса, путем записи данных того же файла по непрерывному физическому адресу LBA. В действительности, когда уделяется внимание высокой вероятности того, что тот же файл обрабатывается непрерывно, то блок непрерывной последовательности SQK непрерывно записывается в физическом положении на диске CD-R так, чтобы сам номер расширения ЕХТх мог быть уменьшен, что служит элементом управляющей структуры диспетчера последовательностей, SQM. Например, когда расширение равно (0,0 56 5), то данные (например, два блока), которые имеют одинаковый номер последовательности (файл), записываются непрерывно, и обеспечивается расширение ЕХТх (0,0 56 7) с тем результатом, что расширение ЕХТх в качестве управляющих данных не увеличивается.

На фиг.4 в узле D расширения, который является промежуточным узлом В-лучевого дерева, ключ последовательности, SQK, (ключ 1, ключ 2, ключ 3,...) каждой передней информации расширения каждого соответствующего листового узла Е, F или G помещен вместе с номером узла. Когда ключи последовательности (ключ 1, ключ 2, ключ 3,...) обозначены, соответствующие листовые узлы Е, F или G считываются из физического адреса на диске CD-R путем обращения к таблице узлов (фиг.5).

Следовательно, диспетчер последовательностей, SQM, производит поиск начиная с узла индексов, когда ключ последовательности, SQK, обозначен как передний ключ (ключ последовательности SQM) в диапазоне, в который включен ключ последовательности SQM. Например, когда целевой ключ последовательности SQM имеет значение между первым ключом 1 в качестве ключа последовательности и вторым ключом 2 в качестве ключа последовательности, помещенных в узле D индексов, диспетчер последовательностей, SQM, выбирает листовые узлы Е, F и G, начиная с расширения ЕХТ 11, имеющего первый ключ 1 последовательности в качестве ключа последовательности, SQK, с тем, чтобы был произведен последовательный поиск внутри листового узла. Таким образом, множество узлов расширений ЕХТх в каждом из листовых узлов Е, F и G обеспечивают возможность простого поиска физического адреса строки данных, обозначенной желаемым ключом последовательности, с помощью способа, предусматривающего использование В-лучевого дерева.

Для справок, на фиг.5 показан способ поиска посредством действительного В-лучевого дерева таким образом, что поиск физического адреса (Н, I, J,...) на целевом диске CD-R начинается с суперблока (называемого SVD), а таблица В узлов (Node Table), узел D индексов и листовые узлы Е, F и G записываются на диске CD-R. Другими словами, диспетчер последовательностей, SQM, обращается к таблице В узлов на диске CD-R, делая это на основе физического адреса таблицы В узлов, который записан в суперблоке. Одновременно, диспетчер последовательностей, SQM, создает физический адрес LBA узла индексов из номера узла таблицы В узлов, обозначенного номером корневого узла, который записан в суперблоке. Вследствие этого диспетчер последовательности, SQM, может обратиться к узлу D индексов на диске CD-R с тем, чтобы номер узла, соответствующий желаемому ключу последовательности в узле индексов, был бы таким, как описано выше в связи с фиг.4. В этом узле D индексов номер узла, соответствующий желаемому ключу последовательности, SQK, считывается так, чтобы листовые узлы Е, F и G, соответствующие этому номеру узла, могли обеспечить считывание физического адреса LBA в таблице В узлов. Как следствие, целевые листовые узлы Е, F и G могут быть считаны с диска CD-R таким образом, что в этот момент можно считывать расширение ЕХТх, соответствующее ключу последовательности, SQK. С этим расширением ЕХТх получается положение (Н, I и J) на диске CD-R в целевой строке блоков данных.

Для справок, на фиг.6 показан пример соотношения соответствия между номером последовательности и физическим адресом LBA. Эти четыре соотношения соответствия могут быть представлены одним расширением ЕХТх, выраженным номером последовательности (123456781h), LBA (1000h) и длиной. Каждые управляющие данные, составляющие В-лучевое дерево, записываются на диске CD-R, в результате чего возникает необходимость перезаписи данных наряду с обновлением их содержания. Следовательно, к блоку данных, определяющему таблицу соответствия В-лучевого дерева между логическим адресом и физическим адресом LBA, присоединяется 32-разрядный логический адрес, который называют В-лучевым деревом, для управления таблицей соответствия между логическим адресом и физическим адресом в качестве таблицы расположения, в которой логический адрес используется в качестве подписи.

На фиг.7 показан пример таблицы узлов. Из этой таблицы узлов можно увидеть, что В-лучевое дерево номера "0" узла записывается в позицию, где физический адрес LBA расположен в позиции "30". Эти данные дополняют таблицу расположения таблицы узлов. Другими словами, "номер ввода" определяет число элементов при расположении, в то время как "свободный" показывает заголовок неиспользованных элементов в расположении. Список неиспользованных элементов относится к механизму управления неиспользованными элементами при расположении. Используя указанный механизм, можно упростить повторное использование элементов расположения. Содержание последних неиспользованных элементов включает в себя подпись следующего неиспользованного элемента на месте адреса блока. В этом примере таблица 2 помещена в заголовке списка неиспользованных элементов, за которым следуют таблица 4 и таблица 1.

Таблица узлов построена так, что механизм для управления таблицей узлов исключается путем записи таблицы узлов в непрерывной области на диске CD-R. В случае, когда В-лучевое дерево изменяется и блок, который определяет В-лучевое дерево, перезаписывается, обновленная таблица узлов записывается на диске CD-R. Например, когда максимальное число номера блока В-лучевого дерева, необходимое для управления данными длиной один гигабайт, становится равным 8095 блоков, как показано на фиг.8, то можно принять, что только половина каждого узла используется, так как каждое расширение ЕХТх относится к одному блоку. Так как в таблице расположения, в которой логический адрес является подписью, требуются четыре байта, то размер таблицы составит 16 блоков, как показано в нижеприведенном уравнении:
8095 блоков• 4 байта+2•4 байта=32388 байтов=15,8 блока≈16 блоков ... (1)
В случае управления пространством, объем которого составляет один гигабайт, можно видеть, что непрерывная область, необходимая для управляющей таблицы В-лучевого дерева, составит, по большей мере, 16 блоков. В CDRFS 1 пакет, содержащий 32 блока, используется в качестве единицы записи при записи на диск CD-R. Таблица узлов, содержащая, по большей мере, 16 блоков, размещается в одном пакете. В CDRFS эта таблица узлов помещается вместе с другой управляющей информацией в последний пакет, который записан на диске CD-R во время флэш-операции, которая будет описана ниже.

Таким образом, в CDRFS механизм управления логическими и физическими адресами блока данных имеет двойственную структуру, включающую В-лучевое дерево и таблицу узлов. Причиной такой двойной структуры является то, что когда только механизм управления логическими и физическими адресами используется для простого расположения в виде таблицы узлов, то для дисплея требуется большая непрерывная область. Например, в случае управления пространством, объем которого составляет один гигабайт, как в вышеупомянутом примере, требуется 1024 блока непрерывной области, как показано в следующем уравнении:
1•2²⁰ кбайт/2 кбайт•4/2048 кбайт=1024 кбайт ... (2)
Более того, когда делается попытка управлять пространством, объем которого составляет один гигабайт, только с помощью В-лучевого дерева, то узел В-лучевого дерева обращается к физическому адресу LBA, в результате чего перезапись по этому адресу воздействует на узел другого В-лучевого дерева каждый раз, когда узел В-лучевого дерева обновляется. Следовательно, в CDRFS механизм управления логическими и физическими адресами обладает двойственной структурой, включающей в себя как В-лучевое дерево, так и таблицу узлов.

Таким образом, в диспетчере последовательности, SQM, когда физический адрес LBA с записанной последовательностью определяется из способа поиска (с использованием В-лучевого дерева), описанного в связи с фиг.4 и 5, физический адрес LBA посылается на кэш-диспетчер САМ, показанный на фиг.2 вместе с ключом последовательности, SQK.

Кэш-диспетчер САМ считывает и записывает данные блока данных, соответствующие обозначенному физическому адресу LBA, с диска CD-R через кэш-буфер, который называют кэш-блоком. Другими словами, обозначенный физический адрес LBA и ключ последовательности, SQK, подаются для перезаписи данных, при этом кэш-диспетчер САМ оценивает, присутствует ли уже в кэш-буфере блок данных, представленный обозначенным физическим адресом LBA. Здесь, когда выдается отрицательный результат, кэш-диспетчер САМ считывает данные из блока (кэш-блока) в кэш-буфере и сохраняет эти данные в блоке в кэш-буфере таким образом, что временный физический адрес (Temporary LBA) присваивается размещенному блоку данных. Таким образом, диспетчер последовательностей, SQM, может осуществить доступ к блоку данных, не зная, является ли физический адрес действительным или временным, путем управления адресом с помощью временного физического адреса (Temporary LBA).

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

В то же время, указатель данных кэш-блока, поступившего из кэш-диспетчера САМ, поступает из диспетчера последовательностей, SQM, в диспетчер файлов, FLM, для обновления данных, обозначенных пользователем. Блок данных, который перезаписан таким образом, подается в кэш-диспетчер САМ таким образом, что осуществляется управление этим блоком как обновленным блоком, который называют черновым блоком в Записываемом Кэш-Блоке, который представляет собой быстродействующую память. В этот момент черновой блок либо обновляется, либо подготавливается в кэш-буфере и еще не записывается на диск CD-R. Следовательно, когда черновой блок достигает заданного объема (32 блока), кэш-диспетчер САМ записывает черновой блок на диск CD-R DISK как один пакет с помощью дисковода.

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

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

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

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

Поэтому операция записи данных в записываемый кэш-блок на диске CD-R называется "флэш"-операцией. Флэш-операция выполняется, во-первых, когда диспетчер последовательностей, SQM, получает запрос на проведение флэш-операции от диспетчера файлов, FLM, или, во-вторых, когда диспетчер последовательностей, SQM, получает запрос на запись от кэш-диспетчера САМ.

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

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

Ниже поясняется значение числа многократно используемых блоков, необходимого для работы диспетчера последовательностей, SQM. Другими словами, когда считываются блоки последовательности, то в кэш-буфере необходимы целевые блоки данных и многократно используемые блоки для сохранения управляющей структуры В-лучевого дерева с целью проверки физического адреса, по которому эти блоки должны присутствовать. К этим блокам В-лучевого дерева не происходит обращения одновременно с их поиском, в результате чего присутствует только один многократно используемый блок. Следовательно, максимальное значение RBCmax числа многократно используемых блоков в кэш-буфере, необходимое для обработки считывания блоков последовательности, определяется следующим уравнением:
RBCmax=N+1 ... (3)
где N - число блоков данных, которые изначально должны быть считаны.

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

Кроме того, в момент формирования блока последовательности формируется расширение ЕХТх и вставляется в В-лучевое дерево. Когда имеется запрет в листовом узле, куда вставляется ЕХТх, этот листовой узел разделяют, и один блок данных формируется для нового листового узла. Помимо этого, когда формируется запрет в узле индексов, в который вставляется листовой узел, в момент вставки в узел индексов сформированного листового узла, предназначенного для разделения, формируется новый листовой узел для разделения узла индексов. В случае, когда глубина В-лучевого дерева равна 3, суммарный объем данных, которыми можно управлять, может быть представлен следующим уравнением:
170• 170/2•145/2=2095250-2 (Гбайт) ... (4)
в состоянии, в котором все узлы, кроме корневого, записаны на 1/2 в предположении, что это наименее эффективное состояние, в котором число блоков, которым управляет одно расширение ЕХТх, равно единице. Следовательно, в диске CD-R, когда объем меньше 700 мегабайт, корневой узел В-лучевого дерева, имеющего глубину 3, не разделяется, и число блоков данных, которое формируется наряду со вставкой первого расширения ЕХТх в В-лучевое дерево, будет составлять, по большей мере, 2.

Помимо этого, так как узел индексов сразу после разделения вставлен, по большей мере, на 2/3, то требуется вновь вставить, по меньшей мере, 170/3 индексов для заполнения узла индексов. Кроме того, когда соседние узлы индексов не заполнены, то узлы индексов перемещают для усреднения числа соответствующих индексов вместо проведения деления. Вследствие этого наименьшее число раз вставки узлов индексов в В-лучевое дерево, которое необходимо из-за осуществления деления узлов индексов до следующего деления, составит 170/3•2= 113. Кроме того, в случае листовых узлов необходима вставка, по меньшей мере, 145/3•2 расширений ЕХТх для проведения следующего деления таким же образом. Поэтому максимальное значение СВСmах числа блоков данных, формируемых посредством однократного обращения к формированию блока в связи с диспетчером последовательностей, SQM, будет представлено следующим уравнением:
CBCmax (N)=N+2 (N/96)/113+(N/96) ... (5)
где N - число блоков данных, изначально предполагается обновить.

С другой стороны, в случае обновления блоков данных работа является такой же, как и в случае формирования блоков, за исключением работы по удалению расширения ЕХТх. Другими словами, в случае, когда одна часть расширения ЕХТх удаляется путем управления соотношением соответствия между ключом последовательности, SQK, множества последовательных блоков и физическим адресом LBA, число расширений ЕХТх будет иногда увеличиваться на одно расширение. Например, когда присутствует расширение ЕХТх, показанное на фиг.9(А), это расширение будет заменено двумя расширениями, как показано на фиг.9(А), путем удаления блока данных из расширения для того, чтобы обновить блоки данных в ключах последовательностей с "3" по "6". Таким образом, когда одна часть уже имеющегося расширения удаляется, может существовать другое дополнительное расширение. При рассмотрении этого факта максимальное значение МВСmах числа блока данных, сформированных однократным вызовом обновления блоков в связи с диспетчером последовательностей, будет представлено следующим уравнением:
MBCmax (N)=N+2+((N+1)/96)/113+((N+1)/96), ... (6)
где N - число блоков данных, которые изначально предполагается обновить.

Кроме того, при удалении блока данных имеется возможность, в соответствии с которой листовые узлы разделяются, когда одна часть расширения удаляется. Следовательно, максимальное значение DBCmax числа блоков данных, формируемое однократным запросом удаления блоков в связи с диспетчером последовательностей, SQM, будет представлено уравнением, не зависящим от числа блока данных, которые будут удалены:
DBCmax=2 ... (7)
Кроме того, в случае, когда размер данных, обрабатываемых за однократную операцию, не определен, иногда случается так, что не требуется проведение сложных вычислений с использованием уравнений (3)-(7). Например, в случае Windows 95 (торговая марка), когда единица распределения считывается из файловой системы по команде [GetDiskInfo], можно осуществить доступ к файловой системе в этой единице распределения. Следовательно, когда предполагается, что единица распределения задана равной, например, 32 блокам, то число блоков данных, с которыми одновременно должен работать диспетчер последовательностей, будет менее одного пакета. Таким образом, число блоков будет представлено следующим уравнением:
DBCmax Перед началом работы диспетчера последовательностей, SQM, в кэш-буфере могут находиться 34 многократно используемых блока.

Далее поясняется флэш-операция записи данных в записываемом кэш-блоке на диск CD-R DISK. Как показано на фиг.10, диспетчер последовательностей, SQM, посылает (запрашивает) в кэш-диспетчер САМ запрос на сбор n пакетов записываемых кэш-блоков в кэш-буфере. Число n пакетов в этом случае зависит от настройки кэш-диспетчера САМ.

Кэш-диспетчер САМ подготавливает список блоков, которые должны быть записаны на диск CD-R DISK согласно заданному приоритету среди записываемого кэш-блока в соответствии с запросом на этапе SP1, показанном на фиг.10. Этот приоритет определяется с помощью так называемого алгоритма LRU (алгоритма удаления наиболее давно использованных элементов), в котором приоритет отдается блоку, у которого меньший доступ к целевому блоку, в результате чего выводимый кэш-блок (который должен быть записан на диске CD-R) определяется в порядке более высокого приоритета. Здесь, когда образуется вакансия в пакете, кэш-диспетчер САМ ставит некоторый фиктивный блок в соответствие свободному пространству.

Кэш-диспетчер САМ обращается к управляющей таблице кэш-памяти на этапе SP2 для получения записываемого кэш-блока, который выбирается таким образом, что список блоков, в котором записываемые кэш-блоки расположены так, что ключ последовательности, SQK, располагается в порядке, соответствующем записываемому кэш-блоку. Затем, на следующем этапе SP3 планируемый физический адрес (Contact LBA) на диске CD-R, на котором каждый блок записывается из списка блоков, присваивается как записываемому начальному физическому адресу LBA и записываемому начальному адресу LBA+1. Этот планируемый физический адрес (Contact LBA) станет действительным адресом (Real LBS), который устанавливается на диске CD-R, когда запись нормально завершится. Если запись не удается, то будет использован вышеупомянутый временный физический адрес.

Таким образом, на этапе SP3 появится высокая вероятность того, что блок той же последовательности будет расположен в непрерывной области диска CD-R путем присвоения положения записи порядку SQM, который соответствует порядку каждого записываемого кэш-блока. Следовательно, этот блок можно непрерывно считывать с диска CD-R во время считывания, в результате чего качество считывания будет повышено. Одновременно можно избежать увеличения числа элементов В-лучевого дерева, когда физический непрерывный блок той же самой последовательности (файлов) управляется одним расширением ЕХТх.

Таким образом, когда планируемый физический адрес (Contact LBA) присваивается записываемому кэш-блоку на этапе SP3, диспетчер последовательностей, SQM, получает таблицу соответствия ключа последовательности, SQK, и планируемого физического адреса (Contact LBA), присвоенного из кэш-диспетчера САМ таким образом, что В-лучевое дерево обновляется на этапе SP4. Другими словами, на этапе SP4 временный физический адрес (Temporary LBA) расширения ЕХТх, подготовленный путем присвоения временного физического адреса в момент обновления данных, заранее заменяется планируемым физическим адресом (Contact LBA; Temporary Actual address). Планируемый физический адрес (Contact LBA) присваивается ключом последовательности, SQK, для того, чтобы какое-либо расширение ЕХТх суммировалось посредством выполнения множества таких обновлений, уменьшая таким способом число расширений ЕХТх В-лучевого дерева в целом. Вследствие этого в некоторых случаях часть узлов (листовые узлы и промежуточные узлы), которые образуют В-лучевое дерево, могут быть исключены. Затем, на этапе SP5 диспетчер последовательностей, SQM, определяет, уменьшилось ли число блоков, которые образуют В-лучевое дерево. Когда на этом этапе получается утвердительный результат, то это значит, что дерево может включать в себя записываемые кэш-блоки, имеющие низкий приоритет, которые не выбраны алгоритмом LRU (алгоритмом удаления наименее давно использованных элементов) на вышеупомянутом этапе SP1, вместо уменьшенного блока. В этот момент диспетчер последовательностей, SQM, возвращает систему к вышеупомянутому этапу SP1, чтобы вновь повторить выбор записываемого кэш-блока.

Таким образом, за счет повторения обработки на этапах SP1-SP5 на этапе SP5 будет получен отрицательный результат. Кэш-диспетчер САМ переходит к этапу SP6 с тем, чтобы послать пакетные данные, содержащие множество блоков, накопленных в записываемом кэш-буфере, на диск CD-R посредством дисковода, в результате чего данные записываются на диске CD-R новой области записи в пакетной единице.

Здесь, когда формируется ошибка записи на диск CD-R, положительный результат получается на последующем этапе SP7. В этот момент диспетчер последовательности, SQM, и кэш-диспетчер САМ переходят к этапу SP8 для осуществления физического восстановления диска CD-R. Другими словами, в спецификации устройства для диска CD-R оговорено, что данные записываются в пакетной единице. В связи с пакетом, в котором формируется ошибка записи и записываемые данные прерываются, становится необходимым наполнить этот пакет фиктивными данными.

Следовательно, диспетчер последовательности, SQM, и кэш-диспетчер САМ восстанавливают неполные пакеты с помощью фиктивных данных и вновь записывают данные, которые должны быть записаны в виде пакета, с помощью фиктивных данных. В этот момент физический адрес LBA данных, которые должны быть записаны, изменяется таким образом, что диспетчер последовательности, SQM, и кэш-диспетчер САМ возвращаются к вышеупомянутому этапу SP1, на котором данные незаписанного записываемого кэш-блока вновь собираются, и новый планируемый физический адрес (Contact LBA) присваивается новому планируемому физическому адресу (Contact LBA). Между прочим, что касается пакета, где запись заканчивается прежде, чем происходит формирование ошибки, данные, включенные в пакет, уже превратилась в необновленный блок данных, называемый считываемым кэш-блоком в кэш-буфере, так что этот блок данных не становится объектом повторного сбора записываемым кэш-блоком после завершения этапа SP8. Следовательно, каждый
раз, когда успешно происходит запись пакета, данные, которые запланированы для записи (записываемый кэш-блок), уменьшаются, так что все блоки данных будут в конце концов записаны на диске CD-R.

Таким образом, на этапе SP7 кэш-диспетчер САМ изменяет записываемый кэш-блок, соответствующий кэш-буферу, превращая этот блок в считываемый кэш-блок, связанный с пакетом, в котором получен отрицательный результат (с пакетом, в котором успешно осуществлена запись). На следующем этапе SP10 обработка на этапах SP6-SP9 повторяется до тех пор, пока в результате ее не будут записаны все пакеты.

На фиг. 11 показано состояние записи данных на диск CD-R. При способе многосеансовой записи пакетов, во время множества сеансов записи (Сеанс 1, сеанс 2,...) осуществляется последовательная запись по спирали от внутренней периферии до внешней периферии диска CD-R. Изнутри от области записи защищены область калибровки мощности (РСА) и область памяти программ (РМА), так что в каждом сеансе можно записывать информацию для настройки мощности и управляющую информацию.

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

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

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

Первичный дескриптор объема, PVD, является информацией, которая записывается в 16-м блоке от заголовка сеанса. В заголовке записаны 1152 байта 16-ого блока, который является таким же, как PVD, соответствующий стандарту IS09660, и содержится информация, предназначенная для CDRFS, показанная на фиг. 11. В PVD, показанном на фиг.12, представлен Способ Поиска Суперблока, который показывает положение, где записан суперблок, использовавшийся последним (или наименее давно использовавшийся суперблок). Другими словами, этот суперблок построен таким образом, что должен записываться на диске CD-R каждый раз при завершении операции "флэш всего". При Способе Поиска Суперблока PVD можно определить самое последнее положение.

Например, в случае результата "Search Method=0" показано, что суперблок записывается на блоке, представленном блоком "Super Block LBA". Далее, в случае результата "Search Method= 1" показано, что суперблок представлен блоком "Last Accessible Block". Кроме того, в случае результата "Search Method= 2" показано, что порядковый номер суперблока, "Super Block Serial Number", записывается в максимальной позиции от суперблоков, записанных в области "Super Block Area". Между прочим, "Super Block Area" относится ко всем блокам, расположенным между блоком, представленным блоком "Start LBA" области "Super Block Area", и блоком, представленным блоком "End LBA" области "Super Block Area".

Кроме того, когда метка "File System Flag", показанная в PVD на фиг.12, соответствует 0•0001, то используется способ адресации "Addressing Method 11". Кроме того, когда метка "File System Flag", показанная в PVD на фиг.12, соответствует 0•002, то видно, что обозначение "IS09660 Volume" скрыто, так что оно не видно со стороны CDRFS. Когда метка "File System Flag", показанная в PVD на фиг.12, соответствует 0•0003, то первая дорожка сеанса записывается с помощью команды ТАО (Немедленная Запись Дорожки, Track At Once) или пакета переменной длины.

Кроме того, Размер Пакета - Packet Size, показанный в PVD на фиг.12, показывает число блоков данных пользователя в пакете фиксированной длины. Однако это поле задействуется только в случае применения способа адресации "Addressing Method 11".

Объем тома "Volume Capacity", показанный в PVD на фиг.12, показывает общее число блоков, которые могут быть записаны на диске CD-R, после его форматирования. Между прочим, это значение является эталонным значением, которое используется во время возврата информации об общем объеме диска CD-R в операционную систему.

Помимо этого, на фиг. 13 показана структура суперблока. Например, информация о том, что блок является суперблоком, записывается в первом заголовке "Super Block Header". В случае результата "Search Method=1", когда суперблок не записан в блоке "Least Accessible Block", поиск старого блока "Super Block" проводится на основе этого заголовка "Super Block Header".

Кроме того, метки "Super Block Flags" показывают, записаны ли данные, эффективные для сеанса. Таблица узлов "Node Table LBA" показывает блок, в котором записана таблица узлов. Когда размер таблицы узлов составляет два блока или более, "Node Table LBA" последовательно записывается из блока "Node Table LBA". Далее, блок "Previous Super Block" показывает положение суперблока, который был записан прежде. В случае диска CD-R данные, которые записаны прежде, не будут потеряны с этого диска. Следовательно, возможно узнать состояние прошлого тома путем слежения за блоком "Previous Super Block".

Число корневых узлов В-лучевого дерева последовательности "Sequence В star tree Root Node Number" показывают число элементов управляющей структуры В-лучевого дерева последовательности (Sequence В Star Tree), содержащее вышеупомянутое В-лучевое дерево, показанное на фиг. 5. Кроме того, число "Directory В Star Tree Root Node Number" показывает число узлов для узла В-лучевого дерева каталога, управляемого диспетчером файлов, FLM. Порядковый номер "Serial Number" обозначает последовательный номер суперблока. Между прочим, значение "Serial Number" суперблока формируется в то время, когда значение формата равно "0".

Кроме того, список суперблока "Super Block List" представляет собой таблицу, в которой в прошлом собраны 50 предыдущих суперблоков LBA "Previous Super Blocks LBA". Список суперблока "Super Block List" содержит повторение элементов списка суперблока "Super Block List Entry", показанных на фиг.14. Первый элемент списка суперблока "Super Block List" показывает суперблок, расположенный за один блок перед суперблоком, в котором помещен список "Super Block List". Когда номер прежнего суперблока меньше 50, элемент списка заполняется из соответствующего заголовка, а неиспользованный элемент списка заполняется нулем - "0".

Список меток суперблоков "Super Block Tag List" представляет собой таблицу имен меток прежних суперблоков. Указанный список "Super Block Tag List" содержит повторение элемента списка меток, как показано на фиг.15. В этой CDRFS максимальное число меток, которые могут быть связаны с одним диском CD-R, составляет 24. При этом, когда число меток меньше 24, элемент списка заполняется из заголовка, а неиспользованный элемент списка заполняется нулем - "0".

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

Далее, узел индексов является узлом, отличающимся от листового узла в управляющей структуре, содержащей В-лучевое дерево. Информация, представленная на фиг.17, записывается в узел индексов. Число записей "Number of Records" на фиг.17 показывает число записей индексов, размещенных в листовом узле. Между прочим, эта запись индексов имеет структуру, показанную на фиг. 18, и эта запись индексов сортируется в восходящем порядке ключа и заполняется, начиная с записи "Index Record [0]", для проведения записи.

Кроме того, листовой узел В-лучевого дерева последовательности является тем узлом В-лучевого дерева, в котором должно быть заключено соотношение соответствия между ключом последовательности SQM и физическим адресом LBA, и этот листовой узел В-лучевого дерева последовательности "Sequence В Star Tree Leaf Node" имеет структуру, показанную на фиг.19. Расширение ЕХТх в этом листовом узле имеет структуру, показанную на фиг.20, и сортируется в восходящем порядке для заполнения из "Extent Record [0]" для последующей записи. При этом число расширений ЕХТх в узле записывается в графе "Number of Records".

Далее, листовой узел h В-лучевого дерева каталога представляет собой узел В-лучевого дерева, в котором должно быть заключено имя файла, ключ последовательности, SQK, соотношение соответствия между именем каталога и номером каталога, информация атрибутов файла и каталога, и имеет структуру, показанную на фиг.21. В номере узла "Node Number" в этом листовом узле помещается номер "Node Number" листового узла с добавлением [0•80000000]. Число записей "Number of Records" показывает число записей каталогов, помещенных в этом листовом узле. Номера предыдущего "Previous Node Number" и следующего "Next Node Number" узлов показывают номер узла для листового узла, имеющего наименьший ключ, и листового узла, имеющего наибольший ключ. Когда имеется целевой узел, то записывается [0•ffffffff]. В графе "Total Size of Record" указываются общее число байтов смещения записей индексов "Index Records Offset" и запись каталога.

Область записи каталога "Directory Record Area" используется так, как это показано на фиг.22. Обозначение "PosX" относится к графе "Index Records Offset" и показывает положение, в котором указана запись каталога вместе со смещением байтов от заглавия области записи каталога. Между прочим, размер "PosX" занимает один байт. Кстати, значения "PosX" рассортированы в порядке ключа, поддерживаем в записи каталога, указанной этим "PosX". Значение "PosX" заполняется из заголовка и записывается.

Обозначение "RecX" составляет основную часть записи каталога. Ее положение не определено конкретно. Однако, когда используется алгоритм, адаптированный для CDRFS, то запись каталога, которая была недавно подготовлена в процессе обработки, помещается в положение, наиболее близкое к заголовку области заголовка. Когда число, помещенное в графе "Number of Records" примет значение "Nrj", область между "PosNr-1" и "PosNr-2" будет неиспользованной областью. Эта область используется для обновления и подготовки записи каталога. Между прочим, неиспользованная область используется от заголовка, и эта неиспользованная область начинается сзади в "RecX".

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

На фиг.24 показано, что номер каталога - это номер, однозначно связанный с каждым из каталогов. Каждый каталог в одном и том же самом каталоге имеет один и тот же номер каталога. Ключ "Hashed Key" относится к остатку, полученному при делении имени записи каталога с помощью функции формирования, выраженной следующим уравнением:
Р(х)=Х¹⁶+X¹²+X⁵+1 ... (9)
Этот ключ "Hashed Key" принимает одно и то же значение для разных имен. Чтобы избежать этого, в CDRFS используется последовательный номер "Sequential Number". В случае, когда запись каталога имеет равный номер каталога и равный ключ "Hashed Key", несмотря на то, что имя, отличающееся от записи каталога, которую нужно вставить, уже имеется в В-лучевом дереве, CDRFS устанавливает последовательный номер "Sequential Number" записи каталога равным номеру, получаемому путем прибавления 1 к "Sequential Number" записи каталога, которая уже имеется в В-лучевом дереве.

Кроме того, размер указывает число байтов записи каталога, включающей в себя ключ и сам этот размер. Помимо этого, Тип представляет собой поле для обозначения типа записи каталога. Существуют пять видов, как показано на фиг. 25. Далее, помимо этого, показано, что когда появляется бит 7 данного типа, происходит обращение к записи каталога из одной или более записей каталога жестких ссылок "Hard Link Directory Record".

Кстати, структуры записей "File Directory Record", "Directory Record" и "Link Directory Record" показаны на фиг.26-28.

Данные (управляющая информация), содержащие такое В-лучевое дерево, записаны в области данных пользователя (фиг. 11) вместе с данными файлов (данными пользователя) во время операции записи, называемой "флэш всего". Другими словами, суперблок содержит физический адрес LBA блока, содержащего таблицу узлов, и номер корневого узла структуры управления (фиг.5), содержащей В-лучевое дерево, и построен таким образом, что ссылка на все данные на диске CD-R, за исключением PVD, начинается с суперблока, пока не будет достигнуто содержание файла управляющей информации. Кроме того, как описано и показано выше на фиг.5, требуется таблица узлов для обращения к узлу управляющей структуры, содержащей В-лучевое дерево. Следовательно, суперблок, составляющий такую управляющую структуру, записывается во время операции "флэш всего" в последний блок на один блок раньше следующего положения записи в области пользователя. Выбор времени проведения операции "флэш всего" происходит, когда истекло заданное время и когда на диск CD-R записано данных больше, чем заданный объем. В результате управляющая информация (суперблок) записывается на диск CD-R в определенном интервале времени.

На фиг.29 показано выполнение операции "флэш всего". Диспетчер последовательностей, SQM, и кэш-диспетчер САМ вступают в процедуру обработки, начиная с этапа SP20. На этапе SP21 список готовится таким же образом, как и в случае выполнения флэш-операции, описанной выше на фиг.10 по отношению к записываемому кэш-блоку в кэш-буфере. Другими словами, диспетчер последовательностей, SQM, требует от кэш-диспетчера САМ считывать все записываемые кэш-блоки в кэш-буфере. После того, как кэш-диспетчер САМ подготовит список всех незаписанных кэш-блоков и фиктивных блоков, которые требуются, происходит обращение к таблице управления кэш, чтобы расположить ключи последовательностей, SQK, в порядке возрастания. Некоторому порядку присваивается планируемый физический адрес (Contact LBA), такой как физический адрес LBA, с которого запись начинается от заглавного блока организованного таким образом списка, и физический адрес LBA+1, с которого начинается запись.

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

Здесь нужно отметить, что для формирования блока таблицы узлов подаются последовательности "ffffffff00000000(hex)", "ffffffff00000001(hex)"...., a для формирования суперблока подается последовательность "ffffffffffffffff (hex)" в качестве ключа последовательности SQM. Таким образом, путем присоединения ключа последовательности, SQK, к таблице узлов эту таблицу узлов располагают в непрерывной области в момент операции расположения блока, а суперблок располагается в последнем блоке последнего пакета.

Впоследствии кэш-диспетчер САМ вновь формирует список для кэш-блока на этапе SP23. Другими словами, диспетчер последовательностей, SQM, требует от кэш-диспетчера САМ собрать все записываемые кэш-блоки в кэш-буфере. Когда существует блок данных, который не передавался ранее, то этот блок данных учитывают при таком сборе еще раз. После этого последовательность обработки осуществляется как обычно, например производится подготовка списка блоков кэш-диспетчером, определение физического адреса LBA и обновление В-лучевого дерева кэш-диспетчером САМ, причем на этапе SР24 заполняется каждая составная часть в суперблоке и блоке для таблицы узлов.

После этого данные записываются в пакетной единице после перехода к этапу SР25. После того, как все данные записаны, процесс переходит к этапу SP30, заканчивая тем самым операцию "флэш всего". Между прочим, поскольку этапы с SP25 по SP29 являются такими же, как этапы с SP6 по SP10, то их пояснение опущено.

Таким образом, в операции "флэш всего" наибольшее значение, такое как, например, [ffffffffffffffff (hex)], присваивается суперблоку как ключ последовательности. С другой стороны, такие большие и непрерывные значения, как [ffffffff00000000(hex)] , [ffffffff00000001(hex)] и т.п., присваиваются таблице узлов как ключ последовательности. Помимо этого, такие непрерывные значения, как [fffffffe00000000(hex)], [fffffffe00000001(hex)] и т.п., очевидно отличные от таблицы узлов, присваиваются листовым узлам как ключ последовательности, SQK.

Эти значения весьма велики по сравнению с ключами последовательности, SQK, [0000000500000000(hex)], [0000000500000002(hex)] и т.п., которые присваиваются данным блока (данным пользователя), составляющим последовательность (файл), отличный от суперблока, таблицы узлов и листового узла. Следовательно, когда выполняется флэш-операция с блоком последовательности, присвоенным таким образом, данные пользователя и управляющая информация (суперблок, таблица узлов и листовой узел) поблочно сортируются (перерасполагаются) так, что ключ последовательности, SQK, располагается в порядке возрастания. Поэтому данные пользователя и управляющая информация последовательно записываются на диск CD-R в порядке сортировки. В результате такая управляющая информация, как суперблок, таблица узлов, листовой узел и т. п. , которой присваивается ключ большой последовательности SQM, записывается в последний блок последнего пакета.

Таким образом, соотношение ссылки устанавливается только в направлении от блока, который записан на диске CD-R позже, к блоку, который был записан на диске CD-R раньше. Следовательно, как показано на фиг.30(А), когда пытаются записать данные в пакетной единице последовательно слева (от внутренней окружности диска CD-R) направо (до внешней окружности диска CD-R), соотношение ссылки устанавливается только в одном направлении так, чтобы пакетные данные b (например, суперблок), которые уже готовы к записи в новой незаписанной области, ссылаются на пакетные данные а (например, таблицей узлов), которые уже записаны в передней части физического адреса. В результате в случае, если происходит сбой в записи пакетных данных b, как показано на фиг. 30(В), то только эти пакетные данные b, на которых произошел сбой записи, могут быть перезаписаны, как показано на фиг.30(С). Поэтому в случае, когда передние пакетные данные а ссылаются на задние пакетные данные b, можно легко провести операцию перезаписи при возникновении ошибки по сравнению со случаем, когда необходимо перезаписывать информацию физического адреса задних пакетных данных b в передние пакетные данные а в соответствии с изменением положения записи задних пакетных данных b (т.е. записать передние пакетные данные а в новой незаписанной области вместе с задними пакетными данными b в случае диска CD-R).

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

Как показано на фиг.11, когда с диска CD-R, имеющего данные, записанные в формате CDRFS, происходит считывание данных с помощью в дисковода CD-R, то необходимо записать информацию о начале и информацию о конце до и после каждого сеанса. Эта операция называется замораживанием. Для выполнения этой операции замораживания необходима заданная емкость пространства на диске CD-R. Если эта емкость не может быть обеспечена, то становится трудно записать информацию об окончании. Когда диск CD-R считывается с помощью дисковода CD-ROM, то этот диск можно считывать до сеанса, в котором надежно записана предыдущая информация об окончании.

Следовательно, в CDRFS осуществляется контроль емкости неиспользованной области диска CD-R. Другими словами, свободная емкость Nfa, необходимая для проведения операции "флэш всего", выражается следующим уравнением при рассмотрении блока суперблока:
Nfa={(Nd+Nn+1+31)/32}• (32+7), ... (10)
где Nd - число незаписанных блоков данных в кэш-буфере, a Nn - число блоков в таблице узлов.

Что касается операции замораживания, то для нее область для информации о начале обеспечивается в момент, когда начинается запись для сеанса, а контролировать можно только информацию об окончании. Свободная емкость, необходимая для замораживания, составляет 1, 5•60•75= 6750 блоков согласно спецификации CD-ROM, когда имеется один сеанс. Свободная емкость для второго и последующих сеансов составляет 30•75 блоков. Следовательно, минимальное значение Nfree свободной емкости, которую необходимо обеспечить на диске CD-R, выражается следующими уравнениями:
Nfree=Nfa+6750 (1-ый сеанс) ... (11)
Nfree=Nfa+2250 (N-ый сеанс, N≥2) ... (12)
Между прочим, в этом числе не учтена возможность ошибки. Например, если предположить, что ошибка записи n-го пакета возникает е раз, то вероятность Ре ошибки записи будет определяться уравнением
Ре=e/n ... (13)
Так как в связи с однократной ошибкой записи оказывается дополнительно занятым один пакет, то при учете ошибки записи прибавляется поправка на свободную емкость Nfa и уравнения (11) и (12) превращаются в следующие уравнения:
Nfree=Nfa(1+Ре)+6750 (1-ый сеанс) ... (14)
Nfree=Nfa(1+Ре)+2250 (N-ый сеанс, N≥2) ... (15)
Таким образом, когда свободная емкость, которая больше, чем Nfree блоков, обеспечена на диске CD-R после подготовки и операции стирания блоков последовательности, то возможно проведение операции замораживания.

В CDRFS максимальное число записываемых кэш-блоков в кэш-буфере, которые вновь сформированы путем однократного вызова диспетчера последовательностей, будет равно МВСmах (Nmax), как описано выше в связи с уравнением (6). В случае, когда носитель записи, такой как диск CD-R или подобный ему, имеющий свободную емкость, равную Nfree+МВСmах (Nmax) блоков, вставляется в дисковод, то пользователю выдается предупреждение о недостаточности емкости носителя записи, чтобы запретить запись данных на носителе записи, например данных о подготовке, обновлении и стирании блоков последовательности. В этом случае CDRFS обеспечивает проведение операции замораживания.

Однако роль CDRFS в обеспечении доступа к файлу заключается в многочисленных и частых операциях обращения к блокам последовательности. Когда запрещена запись на носитель во время прекращения операции обращения к блоку последовательности, существует вероятность того, что будет утеряна целостность файловой системы. Следовательно, операция запрета записи на носитель (диск CD-R) будет выполняться в конце запроса на проведение операции из операционной системы в CDRFS. При этом, когда частота проведения операций подготовки, обновления и стирания блока последовательности, которые выполняются с помощью однократного запроса на проведение операции, поступающего в CDRFS из операционной системы OS, имеет значение Nсb, то значение, соответствующее условию свободной емкости при запрете записи на носитель записи, будет меньше, чем значение, получаемое посредством следующего уравнения:
Nfree=MBCmax (Nmax)•Ncb ... (16)
При вышеупомянутом способе контроля обеспечивается емкость для записи на диске CD-R последней информации об окончании, чтобы сохранить совместимость с диском CD-R. Наряду с этим возможен контроль части чернового блока в дополнение к емкости для информации об окончании. Другими словами, такая операция контроля выполняется каждый раз, когда данные записываются на диск CD-R в соответствии с процедурой обработки контроля, показанной фиг.31. Другими словами, CDRFS переходит к процедуре обработки контроля, начиная с этапа SP40, показанного на фиг.31, с целью подтверждения остающейся емкости на диске CD-R на этапе SP41. Иначе говоря, вся емкость для записи диска CD-R заполняется записями на диске CD-R в процессе его изготовления. Следовательно, дисковод 5 CD-R определяет всю емкость для записи целевого диска CD-R и остающуюся для записи емкость от последнего физического положения, которое записывается в данный момент. Значение остающейся для записи емкости, которая была определена, поступает в кэш-диспетчер САМ на этапе SP42. Кэш-диспетчер САМ вычитает объем данных, которые должны быть записаны в кэш-буфер, из остающейся для записи емкости, чтобы передать значение этой остающейся емкости в диспетчер последовательностей, SQM. На этапе SP43 диспетчер последовательностей, SQM, вычитает суперблок управляющей структуры (SVD) В-лучевого дерева и объем записи таблицы узлов из значения остающейся емкости, поступившего от кэш-диспетчера САМ, и передает значение остающейся емкости в диспетчер файлов, FLM. На этапе SP44 диспетчер файлов, FLM, вычитает часть допуска, необходимую для записи информации об окончании и т.п., из значения остающейся емкости, поступившего из диспетчера последовательностей, SQM.

В случае, когда остающаяся емкость, вычисленная таким образом, больше 0, то CDRFS принимает решение о возможности записи данных и переходе к этапу SP46 для продолжения процесса обработки. С другой стороны, может возникнуть отрицательный ответ на этапе SP45. Это означает, что на диске CD-R нет пространства для записи данных, подлежащих обработке. В этом случае CDRFS переходит к этапу SP47 для отображения заданного предупреждения для пользователя. Таким образом, каждый раз когда проводятся флэш-операция и операция "флэш всего" на диске CD-R, после их выполнения подтверждается наличие остающейся емкости на диске. В случае, когда решено, что после всего этого нет пространства для объема записи при обработке, то возможно заранее предотвратить продолжение обработки после того, как диск CD-R, не имеющий пространства для записи, вставлен в дисковод 5 CD-R.

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

В вышеупомянутой структуре CDRFS управляет физическим адресом LBA на диске CD-R в соответствии с ключом последовательности, SQK, который образует логический адрес в мнимом адресе. Следовательно, после того, как данные блока для обновления на диске CD-R считаны в кэш-буфере и эти данные обновлены, ключ последовательности SQM не меняется, а меняется только физический адрес и данные блока записываются в положении физического адреса LBA на диске CD-R в определенное время (во время флэш-операции и операции "флэш всего").

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

Кроме того, как описано в связи с фиг.3, множество мнимых адресных пространств CV1, CV2, СV3 присваиваются соответствующим файлам (последовательностям) таким образом, что одно мнимое адресное пространство распределяется соответственно одному файлу. В результате мнимое адресное пространство само становится файлом, так что не требуется операция для преобразования этого файла в логический адрес. Между прочим, на фиг.32 показан случай, когда мнимый адрес AV преобразуется в физический адрес AR на носителе записи с помощью блока С2 обработки последовательности. При таком способе мнимый адрес не делится для каждого файла, поэтому требуется операция для преобразования файлов в логические адреса по сравнению со случаем, показанным на фиг.3. Следовательно, в соответствии с изобретением было возможно построить файловую систему (CDRFS), соответствующую однократной записи, без ухудшения характеристик доступа по сравнению с записываемыми носителями и т. п. путем присвоения некоторого мнимого адресного пространства каждым данным, показанным на фиг.3.

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

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

Помимо этого, в случае, когда пакет формируется путем подбора чернового блока в кэш-буфере, этот черновой блок подбирается в соответствии с приоритетом, основанным на алгоритме LRU, так что планируемый физический адрес (Contact LBA) присваивается путем расположения ключа последовательности, SQK, таким образом, что каждый ключ последовательности, SQK, располагается в порядке возрастания по отношению к подобранному черновому блоку, в результате чего, когда целевой черновой блок записывается на диске CD-R, повышается вероятность того, что последовательность располагается в непрерывной области, и это создает возможность попытки улучшения характеристики считывания.

Кроме того, есть возможность гарантировать, что можно записать данные на диске CD-R, который подготавливается пользователем, путем контроля остающейся полезной емкости диска CD-R.

Между прочим, описание приведено для случая, когда диск CD-R используется в качестве носителя записи для однократной записи, хотя изобретение не ограничено этим случаем. Можно использовать носитель записи другого типа, но тоже для однократной записи.

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

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

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

Реферат

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

Формула