Как реализована функция fseek() в файловой системе?

Question

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

Мне интересно, насколько эффективно вставлять данные в середине файла. Предположим, у меня есть файл с данными 1 МБ, а затем я вставляю что-то со смещением 512 КБ. Насколько эффективно это можно сравнить с добавлением моих данных в конце файла? Просто чтобы сделать полный пример, скажем, я хочу вставить 16 Кбайт данных.

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

Answer 1

(отказ от ответственности: Я хочу, чтобы просто добавить некоторые намеки на эту интересную дискуссию) ИМХО есть некоторые вещи, которые следует принимать во внимание:

1) FSEEK не является основной службой системы, а функция библиотеки. Чтобы оценить его производительность, мы должны рассмотреть, как реализуется библиотека потока файлов. В общем случае библиотека ввода-вывода файлов добавляет слой буферизации в пространстве пользователя, поэтому производительность fseek может быть совершенно иной, если целевая позиция находится внутри или за пределами текущего буфера. Кроме того, системные службы, которые использует библиотека I/O, могут сильно различаться. То есть в некоторых системах библиотека, по возможности, широко использует картографирование файловой памяти.

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

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

Есть комментарии?

Answer 2

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

Answer 3

Предположим, что в качестве примера предположим ext2 FS и ОС Linux. Я не думаю, что будет значительная разница в производительности между вставкой и добавлением. В обоих случаях необходимо считывать список файлов и таблицу смещения, соответствующий сектор диска отображается в память, данные обновляются и в какой-то более поздней момент записываются обратно на диск. В этом примере большая разница в производительности будет хорошей временной и пространственной локальностью при доступе к частям файла, поскольку это уменьшит количество комбайнов load/store.

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

Answer 4

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

Answer 5

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

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

Когда возникает fseek(..), там woul d было много чрезмерно, косвенно, ядро ​​делегировало задачу чтения с диска, в зависимости от того, насколько фрагментирован файл, это может быть теоретически «повсюду», что может быть значительным над головой с точки зрения необходимости, с точки зрения пользователя, то есть кода С, делающего fseek(...), он может рассеиваться повсюду, чтобы собрать данные в «один непрерывный вид данных», и впредь, вставляя в в середине файла (помните, что на этом этапе ядро ​​должно было бы отрегулировать местоположение/смещения в фактическом диске для данных) будет считаться медленнее, чем добавление к концу файла.

Причина в том, что ядро ​​«знает», что было последним смещением, и просто стереть маркер EOF и вставить больше данных, за кулисами, ядро, необходимо выделить еще один блок памяти для дисковый буфер с отрегулированным смещением к месту на диске после маркера EOF, как только добавление данных будет завершено.

Answer 6

Одно из наблюдений, которое я сделал около fseek на Solaris, заключается в том, что каждый вызов его сбрасывает буфер чтения FILE. Следующее чтение будет всегда читать полный блок (по умолчанию 8K). Поэтому, если у вас есть много произвольного доступа с небольшими чтениями, это хорошая идея сделать это небуферизованным (setvbuf с буфером NULL) или даже использовать прямые syscalls (lseek + read или даже лучше pread, который является только 1 syscall вместо 2). Я полагаю, что подобное поведение будет похоже на другие ОС.