Результат интеллектуальной деятельности: СПОСОБ УСОВЕРШЕНСТВОВАНИЯ ВЫПОЛНЕНИЯ ОПЕРАЦИИ ОБРАТНО СОВМЕСТИМОЙ АГРЕГАТНОЙ ФАЙЛОВОЙ СИСТЕМЫ И СООТВЕТСТВЕННОЕ УСТРОЙСТВО

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

В настоящее время широко используются домашние («квартирные») шлюзы, соединяющие домашнюю сеть конечного пользователя с сетью Интернет. Домашний шлюз обычно предоставляет услуги широкополосной связи по цифровой абонентской линии (DSL) и телефонной связи, известной как обычная аналоговая телефонная связь (POTS), и содержит кроме того возможность проводной передачи, например стандарта Ethernet, и беспроводной передачи (стандарта Wi-Fi) для домашней сети. Для предоставления услуг домашний шлюз включает в себя микропроцессорную систему (центральный процессор, CPU), исполняющую Unix-подобную операционную систему.

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

Ключевым принципом файловых систем является то, что они имеют фиксированный интерфейс прикладного программирования (API), который обеспечивает возможность функциональной совместимости файловых систем различных видов. Для приложения, использующего файловую систему, формат файловой системы, например FAT32, NTFS, Ext3, …, не имеет значения, и приложение также не должно заботиться об этом. Для Unix-подобных операционных систем API файловой системы соответствует стандарту интерфейса переносимой операционной системы (POSIX), являющемуся семейством стандартов, определенных Институтом инженеров по электротехнике и радиоэлектронике (IEEE).

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

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

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

Поскольку файловые системы являются резидентными в привилегированном пространстве системного ядра, они не могут пользоваться какими-либо библиотеками. По существу, осуществление реализации файловой системы является весьма усложненным. Например, управление памятью является намного более трудным в пространстве системного ядра, чем таковое в пространстве пользователя. Чтобы устранить это ограничение, файловые системы также могут реализовываться в пространстве пользователя. Одним примером реализации для предоставления возможности реализации файловой системы в пространстве пользователя является «файловая система пространства пользователя» (FUSE). FUSE является загружаемым модулем ядра для Unix-подобных операционных систем компьютера. Она содержит драйвер 4 ядра FUSE, который действует подобно обычной файловой системе 5, и библиотеку 6 FUSE для обмена информацией между файловой системой 3 в пространстве пользователя и драйвером 4 ядра FUSE, как проиллюстрировано на Фиг.2. Реализация файловой системы, находящаяся в пространстве пользователя, отвечает за осуществление реализации интерфейса файловой системы. FUSE позволяет, следовательно, исполнение кода файловой системы в пространстве пользователя, тогда как драйвер 4 ядра FUSE обеспечивает мост к ядру операционной системы.

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

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

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

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

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

b.1) подсчет элементов в каталоге

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

count:= 0

dir_handle:= opendir('/foo/bar')

while ( readdir(dir_handle) )

{

count:= count + 1

}

closedir(dir_handle)

Если в каталоге /foo/bar находятся n элементов, то количеством системных вызовов, активируемых согласно этому фрагменту кода, будет 2+n. Если /foo/bar является каталогом в файловой системе, реализованной в пространстве пользователя, то это приведет к 2(2+n) переключателям контекста.

b.2) подсчет элементов всех непосредственных подкаталогов в каталоге

Этот пример может показаться непосредственным результатом предшествующего примера, но, как будет пояснено в разделе d.2, он будет решен немного по-другому. Хотя это может выглядеть искусственной проблемой, у этого примера есть реальный вариант использования (например, действие BrowseDirectChildren UPnP AV (просмотр непосредственных потомков)).

function dirsize(path)

{

count:= 0

dir_handle:= opendir(path)

while ( readdir(dir_handle) )

{

count:= count + 1

}

closedir(dir_handle)

return count

}

…

dir_handle:= opendir ('/foo/bar' )

while ( dir_entry:= readdir(dir_handle) )

{

if ( is_dir(dir_entry) )

{

count:= dirsize(dir_entry->name)

print "Directory ", dir_entry->name, " has ", count, " elements"

}

}

closedir(dir_handle)

Если /foo/bar имеет n подкаталогов, причем каждый подкаталог с наличием m_i элементов, то эта порция псевдокода активирует 2+n+ системных вызовов. Если /foo/bar снова находится в файловой системе в пространстве пользователя, то это приведет к 2(2+n+ ) переключателям контекста.

b.3) считывание элементов каталога со смещения/считывание полного каталога фрагментами

function readdir_offset_limit(path, skip, items)

{

done = true

skip_count:= 0

dir_handle:= opendir(path)

while ( readdir(dir_handle) && skip_count < skip )

{

skip_count:= skip_count + 1

}

items_count:= 0

while ( readdir(dir_handle) && items_count < items )

{

items count:= items_count + 1

…/* делать что-либо с результатом */

done:= false

}

closedir(dir_handle)

return done

}

…

skip:= 0

while ( readdir_offset_limit('/foo/bar', skip, N) )

{

skip:= skip + N

}

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

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

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

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

КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

Фиг.1 - файловая система, содержащая операционную систему и приложения, исполняющиеся на микропроцессорной системе, и

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

ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

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

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

Для примеров, которые ранее приведены в разделе b, возможное соглашение описывается в этом разделе.

d.1) подсчет элементов в каталоге

Возможное соглашение состоит в том, что каждый каталог в виртуальной файловой системе делает доступным файл с числом элементов каталога (подкаталогов, файлов, символьных ссылок) в качестве содержимого. Логическим именем для такого файла может быть "size" (размер), "childcount" (количество потомков), "dirsize" (размер каталога),... Задача, описанная в разделе b.1, затем может быть решена с помощью следующей порции псевдокода:

file_handle:= open( '/foo/bar@size' )

count:= read(file_handle)

close(file_handle)

Это иллюстрирует, что задача теперь может быть решена только с 3 системными вызовами, независимо от числа элементов в каталоге. В нотации "большого O" можно сказать, что задача была сведена от O(n) к O(1) по отношению к числу системных вызовов. Полагая, что реализация файловой системы имеет эту информацию, то есть число элементов в /foo/bar, в своем распоряжении, то предложение имеет в целом сложность O(1).

d.2) подсчет элементов всех непосредственных подкаталогов в каталоге

Возможным соглашением для подсчета элементов для всех непосредственных подкаталогов в каталоге является файл, который содержит на каждой строке имя подкаталога, разделитель последовательности символов и число элементов в подкаталоге. Логическим именем для такого файла может быть "content" (содержимое), "dircontent" (содержимое каталога), "data" (данные), "subsize" (подразмер), ….

file_handle:= open ( '/ foo/bar@content' )

content:= read( file_handle )

close(file_handle)

parse(content)

Можно допустить, что каталог /foo/bar имеет 3 подкаталога, dir_a, dir_b и dir_c, с соответственно 3, 2 и 5 элементами каталога. Тогда файл /foo/bar@content, например, может иметь следующее содержимое:

dir_a=3

dir_b=2

dir_c=5

По сравнению с исходной задачей в разделе b.2, задача снова была сведена от O(n) к O(1). Это поясняет, почему эта задача отличается от предшествующей, изложенной в разделе b.2. Без файла @content задача будет более простой, но она будет все еще иметь сложность O(n), как проиллюстрировано в следующей порции псевдокода:

dir_handle:= opendir('/foo/bar' )

while ( dir_entry:= readdir(dir_handle) )

{

if ( is_dir(dir_entry) )

{

file_handle:= open(dir_entry->name + "@content")

count:= read( file_handle )

close( file_handle )

print "Каталог", dir_entry->name, " содержит", count, " элементов"

}

}

closedir(dir_handle)

d.3) считывание элементов каталога со смещения/считывание всего каталога фрагментами

Возможное соглашение считывать ограниченное число элементов с заданного смещения в каталоге состоит в том, чтобы иметь доступный виртуальный файл с переменным именем файла, которое указывает смещение и граничные параметры (например, dir_2_10, чтобы считывать элементы 2-10). Этот файл затем может просто содержать имена соответствующих элементов. Логическим именем для такого файла может быть "dir_<from>_<to>" (каталог <от> <до>), "content_<from>_<to>" (содержимое <от> <до>), "items_<from>_<to>" (элементы <от> <до>)…. Это иллюстрируется в следующей порции псевдокода:

from:= 0

to:= N

while ( file_handle:= open('/foo/bar@dir_$ from_$ to') )

{

content:= read( file_handle )

close(file_handle)

from:= from + N

to:= to + N

}

Тогда как исходная задача имела сложность O(n2), она теперь сведена к O(n/N). В худшем случае, где размером N фрагмента является 1, сложность составляет O(n). В лучшем случае, где N имеет значение, по меньшей мере, n, сложностью снова является O(1). Эта лучшая рабочая характеристика будет достигаться, если нет ограничений по памяти, так что N может быть большим, или если каталоги имеют небольшое число элементов большую часть времени (малые значения n).

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

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

• имена файлов с расширением пути, подобно проиллюстрированным в примерах

в этой реализации специальные виртуальные файлы реализуются в той же файловой системе (например, если /foo/bar является путем для каталога, то путь /foo/bar@content представляет виртуальный файл). Единственный недостаток состоит в том, что длина пути является ограниченной, поэтому не всегда является возможным расширить путь.

• дублирующая файловая система с виртуальными файлами

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

• расширяемая подключаемая файловая система

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

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

•/foo/bar@size

•/foo/bar@content

•/foo/bar@content_1_10

Однако, для файловых систем POSIX, не имеется символа или последовательности символов, которые не могут входить в имена путей, кроме символа-разделителя пути непосредственно ('/').

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

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

Изобретение имеет следующие преимущества:

- минимизируется число системных вызовов, активируемых для извлечения данных из файловой системы,

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

- новые системные вызовы не требуются,

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

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

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

- изобретение является в целом применимым, даже если только три возможных приложения описываются в документе,

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

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

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