Размещение с помощью связанного списка, использующего таблицу в памяти

Оба недостатка размещения с помощью связанных списков могут быть устранены за счет изъятия слова указателя из каждого дискового блока и помещения его в таблицу в памяти. На рис. 4.9 показано, как выглядит таблица для примера, приведенного на рис.
4.8. На обоих рисунках показаны два файла. Файл A использует в указанном порядке дисковые блоки 4, 7, 2, 10 и 12, а файл B — блоки 6, 3, 11 и 14. Используя таблицу, показанную на рис. 4.9, можно пройти всю цепочку от начального блока 4 до самого конца. То же самое можно проделать начиная с блока 6. Обе цепочки заканчиваются специальным маркером (например, -1), который не является допустимым номером блока. Такая таблица, находящаяся в оперативной памяти, называется FAT (File Allocation Table — таблица размещения файлов).

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

Основным недостатком этого метода является то, что для его работы вся таблица должна постоянно находиться в памяти. Для 1-терабайтного диска, имеющего блоки размером 1 Кбайт, потребовалась бы таблица из 1 млрд записей, по одной для каждого из 1 млрд дисковых блоков. Каждая запись должна состоять как минимум из 3 байт. Для ускорения поиска размер записей должен быть увеличен до 4 байт. Таким образом, таблица будет постоянно занимать 3 Гбайт или 2,4 Гбайт оперативной памяти в зависимости от того, как оптимизирована система, под экономию пространства или под экономию времени, что с практической точки зрения выглядит не слишком привлекательно. Становится очевидным, что идея FAT плохо масштабируется на диски

Рис. 4.9. Размещение с помощью связанного списка, использующего таблицу размещения файлов в оперативной памяти


больших размеров. Изначально это была файловая система MS-DOS, но она до сих пор полностью поддерживается всеми версиями Windows.

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

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

  1. 9.11. С ПОМОЩЬЮ ПАМЯТИ
  2. 7. Чтобы связать с прошлым нынешнее чувство беспомощности, используйте одно из следующих указаний:
  3. 3. Чтобы связать с прошлым нынешнее чувство неуверенности, используйте одно из следующих указаний:
  4. 2. Чтобы связать с прошлым нынешнее чувство заброшенности, используйте одно из следующих указаний:
  5. 4. Чтобы связать с прошлым нынешнее чувство бессилия” используйте одно из следующих указаний:
  6. 5. Чтобы связать с прошлым нынешнее чувство неудовлетворенности, используйте одно из следующих указаний:
  7. 6. Чтобы связать с прошлым нынешнее чувство обескураженности, используйте одно из следующих указаний:
  8. 11. Чтобы связать с прошлым нынешнее чувство безнадежности, используйте одно из следующих указаний:
  9. 1. Чтобы связать с прошлым нынешнее чувство обману-тости, используйте одно из следующих указаний:
  10. 8. Чтобы связать с прошлым нынешнее ощущение своей неполноценности” используйте одно из следующих указаний:
  11. 10. Чтобы связать с прошлым нынешнее ощущение обой-денности, используйте одно из следующих указаний:
  12. 12. Чтобы связать с прошлым нынешнее чувство своей не-достойности, используйте одно из следующих указаний:
  13. 9. Чтобы связать с прошлым нынешнее чувство лишенности чего-то важного, используйте одно из следующих указаний:
  14. Статья 400. Посягательство на жизнь защитника или представителя лица в связи с деятельностью, связанной с оказанием правовой помощи
  15. Таблица 2 Таблица баллов лучей мандалы
  16. Номер один в списке неправильных действий
  17. Статья 223. Размещение ценных бумаг без регистрацииих выпуска
  18. Статья 377. Право на земельный участок при приобретении жилого дома, здания или сооружения, которые размещенные на нем