Как файловая система в UNIX находит файлы?

Question

Предположим, что запрос сделан на ls somefile. Как файловая система в UNIX обрабатывает этот запрос с алгоритмической точки зрения? Это O (1) запрос или O (log (N)) в зависимости от файлов, скажем, начиная с текущего узла каталога, или это O (N) линейный поиск, или это комбинация в зависимости от некоторых параметров?

Answer 1

Это O (n), поскольку файловые системы должны сначала считывать их с физического носителя, но буферные кеши будут увеличиваться, что значительно, в зависимости от реализации Виртуальной файловой системы (VFS) на вашем варианте * nix. (Обратите внимание, что при первом обращении к файлу он медленнее, чем при втором выполнении той же самой команды?)

Чтобы узнать больше, прочитайте статью IBM об анатомии файловой системы Unix .

Answer 2

Это может быть O (n). Классические файловые системы Unix, основанные на старой файловой системе BSD fast school и т. П., Хранят файлы в виде номеров инодов, а их имена назначаются на уровне каталогов, а не на уровне файлов. Это позволяет вам иметь один и тот же файл в нескольких местах одновременно через жесткие ссылки. Таким образом, «каталог» в большинстве систем Unix - это просто файл, в котором перечислены имена файлов и номера узлов для всех файлов, хранящихся «в» этом каталоге.

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

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

Answer 3

Типичный поток для такой программы, как ls, будет

1. Opendir на текущем пути.
2. Readdir для текущего пути.
3. Фильтрация записей, возвращаемых OpenDir, через фильтр, предоставленный в командной строке.Таким образом, обычно O (n)

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

Answer 4

Я не могу ответить на ваш вопрос.Возможно, если вы взглянете на исходный код, вы можете ответить на свой вопрос и объяснить, как он работает.ls.c ls.h