Размещение с использованием связанного списка

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

Рис. 4.8. Хранение файла в виде связанного списка дисковых блоков


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

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

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

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Размещение с использованием связанного списка:

  1. Статья 801. Затраты, связанные с использованием транспортного средства
  2. Перед использованием провокационного вопроса просчитайте все риски, с ним связанные.
  3. Номер один в списке неправильных действий
  4. Статья 223. Размещение ценных бумаг без регистрацииих выпуска
  5. Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации
  6. Статья 377. Право на земельный участок при приобретении жилого дома, здания или сооружения, которые размещенные на нем
  7. Статья 231. Незаконный сбор с целью использования или использование сведений, составляющих коммерческую или банковскую тайну
  8. Статья 350. Выкуп земельных участков, других объектов недвижимого имущества, размещенных на них, частной собственности для общественных потребностей или их принудительное отчуждения по мотивам общественной необходимости
  9. 4.4.3. Согласование ответов, не связанных со стимульной ситуацией
  10. Связать ощущения со своим прошлым
  11. Связанные позитивные высказывания.