Лекция №3. Управление памятью

1. Понятие основной памяти ЭВМ, ее отличия от вторичной памяти. Запоминающие устройства компьютера разделяют, как минимум, на два уровня: основную (главную, оперативную, физическую) и вторичную (внешнюю) память.

Основная память представляет собой упорядоченный массив однобайтовых ячеек, каждая из которых имеет свой уникальный адрес (номер).

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

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

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

2. Основные функции управления памятью.

Чтобы обеспечить эффективный контроль использования памяти, ОС должна выполнять следующие функции:

n отображение адресного пространства процесса на конкретные области физической памяти;

n распределение памяти между процессами;

n контроль доступа к адресным пространствам процессов;

n выгрузка процессов (целиком или частично) во внешнюю память, когда в оперативной памяти недостаточно места;

n учет свободной и занятой памяти.

3. Принцип сегментной организации памяти. Аппаратная организация памяти в виде линейного набора ячеек не соответствует представлениям программиста о том, как организовано хранение программ и данных.

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

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

Сегмент – область памяти определенного назначения, внутри которой поддерживается линейная адресация.

Сегменты содержат процедуры, массивы, стек или скалярные величины, но обычно не содержат информацию смешанного типа.

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

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

4. Определение внутренней фрагментации. Внутренняя фрагментация – потеря части памяти, выделенной процессу, но не используемой им.

Фрагментация возникает потому, что процесс не полностью занимает выделенный ему раздел или потому, что некоторые разделы слишком малы для выполняемых пользовательских программ.

5. Определение внешней фрагментации.

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

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

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

6. Определение свопинга. Swapping– перемещение процессов из главной памяти на диск и обратно целиком.

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

Paging– частичная выгрузка процессов на диск (осуществляется в системах со страничной организацией).

7. Перечислить стратегии размещения процессов в памяти в схеме с переменными разделами.

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

Рис. 8.6.Динамика распределения памяти между процессами (серым цветом показана неиспользуемая память)

В какой раздел помещать процесс? Наиболее распространены три стратегии.

· Стратегия первого подходящего (First fit). Процесс помещается в первый подходящий по размеру раздел.

· Стратегия наиболее подходящего (Best fit). Процесс помещается в тот раздел, где после его загрузки останется меньше всего свободного места.

· Стратегия наименее подходящего (Worst fit). При помещении в самый большой раздел в нем остается достаточно места для возможного размещения еще одного процесса.

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

8. Принцип страничной организации памяти.

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

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

Логический адрес в страничной системе – упорядоченная пара (p,d), где p – номер страницы в виртуальной памяти, а d – смещение в рамках страницы p, на которой размещается адресуемый элемент. Заметим, что разбиение адресного пространства на страницы осуществляется вычислительной системой незаметно для программиста. Поэтому адрес является двумерным лишь с точки зрения операционной системы, а с точки зрения программиста адресное пространство процесса остается линейным.

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

Интерпретация логического адреса показана на рис. 8.7. Если выполняемый процесс обращается к логическому адресу v = (p,d), механизм отображения ищет номер страницы p в таблице страниц и определяет, что эта страница находится в страничном кадре p', формируя реальный адрес из p' и d.

Рис. 8.7.Связь логического и физического адресов при страничной организации памяти

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

9. Отличие страничной и сегментной организации памяти.

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

10. Принцип сегментно-страничной организации памяти.

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

Рис. 8.9.Упрощенная схема формирования физического адреса при сегментно-страничной организации памяти

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

11. Связывание адресов при сегментно-страничной организации памяти. Логические и физические адресные пространства ни по организации, ни по размеру не соответствуют друг другу. Максимальный размер логического адресного пространства обычно определяется разрядностью процессора (например, 2³²) и в современных системах значительно превышает размер физического адресного пространства.

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

Такое отображение адресов называют трансляцией (привязкой) адреса или связыванием адресов

12. Принцип организации виртуальной памяти.

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

1. Занимаемая процессом память разбивается на страницы.

2. Логический адрес (логическая страница), к которому обращается процесс, динамически транслируется в физический адрес (физическую страницу).

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

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

13. Преимущества использования виртуальной памяти.

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

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

· Поскольку появляется возможность частичного помещения программы (процесса) в память и гибкого перераспределения памяти между программами, можно разместить в памяти больше программ, что увеличивает загрузку процессора и пропускную способность системы.

· Объем ввода-вывода для выгрузки части программы на диск может быть меньше, чем в варианте классического свопинга, в итоге каждая программа будет работать быстрее.

14. Политики управления памятью.!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Политика выборки (fetch policy) –
в какой момент следует переписать страницу из вторичной памяти в первичную.

Политика размещения (placement policy) - в какой участок первичной памяти поместить поступающую страницу

Политика замещения (replacement policy) - какую страницу нужно вытолкнуть во внешнюю память, чтобы освободить место

15. Структура таблицы страниц виртуальной памяти.

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

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

Виртуальный адрес состоит из виртуального номера страницы и смещения. Номер записи в таблице страниц соответствует номеру виртуальной страницы.

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

Кроме того запись в таблице страниц содержит информацию об атрибутах страницы:

n биты присутствия;

n бит защиты (например, 0 – read/write, 1 – read only...);

n бит модификации (устанавливается, если содержимое страницы модифицировано, и позволяет контролировать необходимость перезаписи страницы на диск);

n бит ссылки (помогает выделить малоиспользуемые страницы);

n бит, разрешающий кэширование;

n …

16. Организация многоуровневых таблиц страниц виртуальной памяти.

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

Наиболее распространенный способ разбиения страниц на части – организация так называемой многоуровневой таблицы страниц. Для примера рассмотрим двухуровневую таблицу с размером страниц 4 Кбайт, реализованную в 32-разрядной архитектуре Intel.

Таблица, состоящая из 2²⁰ строк, разбивается на 2¹⁰ таблиц второго уровня по 2¹⁰ строк. Эти таблицы второго уровня объединены в общую структуру при помощи одной таблицы первого уровня, состоящей из 2¹⁰ строк.

32-разрядный адрес делится на 10-разрядное поле p1, 10-разрядное поле p2 и 12-разрядное смещение d. Поле p1 указывает на нужную строку в таблице первого уровня, поле p2 – второго, а поле d локализует нужный байт внутри указанного страничного кадра.

17. Принципы функционирования ассоциативной памяти.

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

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

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

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

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

Рассмотрим функционирование менеджера памяти при наличии ассоциативной памяти.

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

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

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

Предположим, например, что для определения адреса в случае кэш-промаха через таблицу страниц необходимо 100 нс, а для определения адреса в случае кэш-попадания через ассоциативную память – 20 нс. С 90% hit ratio среднее время определения адреса – 0,9x20+0,1x100 = 28 нс.

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

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

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

18. Понятия трешинга

Хотя теоретически возможно уменьшить число кадров процесса до минимума, существует какое-то число активно используемых страниц, без которого процесс часто генерирует page faults (страничные нарушения). Высокая частота страничных нарушений называется трешинг (thrashing, иногда употребляется русский термин "пробуксовка", см. рис. 10.3). Процесс находится в состоянии трешинга, если при его работе больше времени уходит на подкачку страниц, нежели на выполнение команд. Такого рода критическая ситуация возникает вне зависимости от конкретных алгоритмов замещения.

Рис. 10.3.Частота page faults в зависимости от количества кадров, выделенных процессу

19. Определение рабочего множества страниц памяти процесса.

Рабочее множество W(t,T) – это набор страниц (P₁, P₂, ... P_n), активно использующихся вместе, который позволяет процессу в момент времени t в течение некоторого периода T работать, избегая большого количества page faults.

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

Если процессу выделять меньше кадров, чем ему требуется для поддержки рабочего множества, он будет находиться в состоянии трешинга.

1. Принцип локальности. Если в период времени (t-T, t) программа обращалась к страницам W(t,T), то при надлежащем выборе T с большой вероятностью эта программа будет обращаться к тем же страницам в период времени (t, t+T). Другими словами, принцип локальности утверждает, что если не слишком далеко заглядывать в будущее, то можно достаточно точно его прогнозировать исходя из прошлого. Понятно, что с течением времени рабочий набор процесса может изменяться (как по составу страниц, так и по их числу).

Лекция №4. Файловые системы

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

2. Основные функции файловой системы.

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

Функции

1. Идентификация файлов

2. Распределение внешней памяти между файлами

3. Обеспечение надежности и отказоустойчивости

4. Обеспечение защиты от НСД (несанкционированный доступ)

5. Обеспечение совместного доступа к файлам

6. Обеспечение высокой производительности

3. Схема физического устройства жесткого диска.

4. Из каких компонентов состоит физической адрес ячейки памяти на жестком диске?

Память процессора логически организована в виде линейного адресного пространства как одномерный массив байт (рис. 1.2.), каждый из которых имеет 20 – битовый физический адрес в диапазоне 00000h – FFFFFh (здесь и далее представляются в шестнадцатеричной системе счисления, признаком которой служит буква h в конце числа). Любые две смежных байта в памяти могут рассматриваться как 16 – битовое число. Младший байт имеет меньший адрес, старший – больший. Адресом слова считается адрес его младшего байта (располагается по меньшему адресу). Таким образом, любой физический адрес является одновременно адресом байта и адресом слова. Нумерация бит в каждом байте (слове) выполняется начиная с младшего разряда от 0 до 7 (от 0 до 15). Каждый байт (слово) может содержать число от 0 до 255 (от 0 до 65535) в беззнаковом представлении и от –128 до +127 (от –32768 до +32767) – при представлении в дополнительном коде.

Физический адрес формируется процессором для обращения к внешней памяти. Физическое пространство памяти в 1мБайт представляется как набор сегментов. Сегмент состоит из смежных ячеек памяти и является независимой и отдельно адресуемой единицей памяти емкостью 64 КБайта (рис. l.3). Начальные адреса четырех сегментов, выбранных в качестве текущих, записываются в сегментные регистры процесcopa CS, DS, SS и ES, тем самым фиксируются текущие сегменты кода (программы), данных (операндов), стека и допол­нительных данных. Для обращения к командам и данным, на­ходящимся в других сегментах, необходимо изменять содер­жимое сегментных регистров, что позволяет использовать все пространство памяти.

В сегментном регистре хранятся 16 старших разрядов 20-битового начального адреса сегмента. Четыре младших разря­да принимаются равными нулю и дописываются слева к со­держимому сегментного регистра при вычислении физических адресов ячеек памяти. Поэтому начальные адреса ячеек всег­да кратны 16. Поскольку других ограничений на размещение сегментов в памяти нет, сегменты могут быть соседними (смежными), частично или полностью перекрывающимися. Фи­зическая ячейка памяти может принадлежать одному или не­скольким сегментам одновременно.

5. Чем отличается сектор от блока с точки зрения файловых систем.

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

6. Из чего состоит Master Boot Record?

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

7. Как используется Master Boot Record при загрузке ОС? Загрузка - многоступенчатый процесс. Большинство ПК сегодня инициализируют системные устройства прошивкой, называемой BIOS (Basic Input/Output System). BIOS содержится внутри CMOS (Ceramic Metal Oxide Semiconductor (полупроводник)), который выполняется при старте системы. После инициализации системных устройств BIOS ищет загрузчик в MBR первого устройства хранения (жесткий диск, твердотельный накопитель, CD/DVD диск, USB диск...) или на первом разделе устройства. Затем он передает управление этому загрузчику. Тот, в свою очередь, считывает таблицу разделов и готовится к загрузке операционной системы. Среди загрузчиков GNU/Linux особо выделяются GRUB и LILO.

8. Из каких основных логических подсистем состоит файловая система? Логическая подсистема управления файлами

Базовая подсистема управления файлами

Система ввода-вывода

Оборудование

(Моё: 1. Оборудование(контролер диска, физические блоки диска – треки, сектора, цилиндры)
Магнитные диски с подвижными головками — магнитные поверхности, между которыми двигаются магнитные головки. Шаг движения головки является дискретным, и каждому её положению соответствует цилиндр магнитного диска. Цилиндры делятся на дорожки (треки), а каждая дорожка размечается на одно и то же количество блоков (секторов) таким образом, что в каждый блок можно записать максимально одно и то же число байтов. Так, для обмена с магнитным диском на уровне аппаратуры нужно указать номер цилиндра, номер поверхности, номер блока на соответствующей дорожке и число байтов, которое нужно записать или прочитать от начала этого блока. Таким образом, можно получить доступ к любому блоку в любой момент (прямой доступ к файлам). Физические блоки дисков можно записать в виде: диск 3, цилиндр 14.

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

3. Логические блоки(разделы диска, логические диски)
Логические блоки имеют свой номер от 1 до N. Размер логических блоков совпадает или является кратным размеру физического.

4. Базисная подсистема управления файлами(Алгоритмы выделения блоков дисков, менеджер свободного пространства, системные вызовы для работы с дескрипторами, таблицы открытых файлов, монтирование файловых систем)

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

9. Достоинства и недостатки выделения дискового пространства в виде связного списка. Внешняя фрагментация - основная проблема рассмотренного выше метода - может быть устранена за счет представления файла в виде связного списка блоков диска. Запись в директории содержит указатель на первый и последний блоки файла (иногда в качестве варианта используется специальный знак конца файла - EOF). Каждый блок содержит указатель на следующий блок (см. рис. 12.2).

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

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

Связное выделение имеет, однако, несколько существенных недостатков.

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

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

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

Поэтому метод связного списка обычно в чистом виде не используется.

10. Как организуется хранение файлов методом «таблица отображения файлов»?

Одним из вариантов предыдущего способа является хранение указателей не в дисковых блоках, а в индексной таблице в памяти, которая называется таблицей отображения файлов ( FAT - file allocation table ) (см. рис. 12.3). Этой схемы придерживаются многие ОС (MS-DOS, OS/2, MS Windows и др.)

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

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

Рис. 12.3.Метод связного списка с использованием таблицы в оперативной памяти

11. Как организуется хранение файлов методом «индексные узлы»?

Наиболее распространенный метод выделения файлу блоков диска - связать с каждым файлом небольшую таблицу, называемую индексным узлом ( i-node ), которая перечисляет атрибуты и дисковые адреса блоков файла (см. рис 12.4). Запись в директории, относящаяся к файлу, содержит адрес индексного блока. По мере заполнения файла указатели на блоки диска в индексном узле принимают осмысленные значения.

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

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

Рис. 12.4.Структура индексного узла

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

12. Методы управления свободным дисковым пространством «Битовый вектор», «Связный список».