Архитектура Unix
. Алгоритм назначения новых индексов
Рисунок 4.12. Алгоритм назначения новых индексов
| алгоритм ialloc /* выделение индекса */ входная информация: файловая система выходная информация: заблокированный индекс { выполнить { если (суперблок заблокирован) { приостановиться (пока суперблок не освободится); продолжить; /* цикл с условием продолжения */ } если (список индексов в суперблоке пуст) { заблокировать суперблок; выбрать запомненный индекс для поиска свободных индексов; искать на диске свободные индексы до тех пор, пока суперблок не заполнится, или пока не будут най- дены все свободные индексы (алгоритмы bread и brelse); снять блокировку с суперблока; возобновить выполнение процесса (как только супер- блок освободится); если (на диске отсутствуют свободные индексы) возвратить (нет индексов); запомнить индекс с наибольшим номером среди най- денных для последующих поисков свободных индек- сов; } /* список индексов в суперблоке не пуст */ выбрать номер индекса из списка индексов в супербло- ке; получить индекс (алгоритм iget); если (индекс после всего этого не свободен) /* !!! */ { переписать индекс на диск; освободить индекс (алгоритм iput); продолжить; /* цикл с условием продолжения */ } /* индекс свободен */ инициализировать индекс; переписать индекс на диск; уменьшить счетчик свободных индексов в файловой сис- теме; возвратить (индекс); } } |
На Рисунке 4.12 приведен алгоритм ialloc назначения новых индексов. По причинам, о которых пойдет речь ниже, ядро сначала проверяет, не заблокировал ли какой-либо процесс своим обращением список свободных индексов в суперблоке. Если список номеров индексов в суперблоке не пуст, ядро назначает номер следующего индекса, выделяет для вновь назначенного дискового индекса свободный индекс в памяти, используя алгоритм iget (читая индекс с диска, если необходимо), копирует дисковый индекс в память, инициализирует поля в индексе и возвращает индекс заблокированным. Затем ядро корректирует дисковый индекс, указывая, что к индексу произошло обращение. Ненулевое значение поля типа файла говорит о том, что дисковый индекс назначен. В простейшем случае с индексом все в порядке, но в условиях конкуренции делается необходимым проведение дополнительных проверок, на чем мы еще кратко остановимся. Грубо говоря, конкуренция возникает, когда несколько процессов вносят изменения в общие информационные структуры, так что результат зависит от очередности выполнения процессов, пусть даже все процессы будут подчиняться протоколу блокировки. Здесь предполагается, например, что процесс мог бы получить уже используемый индекс. Конкуренция связана с проблемой взаимного исключения, описанной в главе 2, с одним замечанием: различные схемы блокировки решают проблему взаимного исключения, но не могут сами по себе решить все проблемы конкуренции.
Если список свободных индексов в суперблоке пуст, ядро просматривает диск и помещает в суперблок как можно больше номеров свободных индексов. При этом ядро блок за блоком считывает индексы с диска и наполняет список номеров индексов в суперблоке до отказа, запоминая индекс с номером, наибольшим среди найденных. Назовем этот индекс "запомненным"; это последний индекс, записанный в суперблок. В следующий раз, когда ядро будет искать на диске свободные индексы, оно использует запомненный индекс в качестве стартовой точки, благодаря чему гарантируется, что ядру не придется зря тратить время на считывание дисковых блоков, в которых свободные индексы наверняка отсутствуют. После формирования нового набора номеров свободных индексов ядро запускает алгоритм назначения индекса с самого начала. Всякий раз, когда ядро назначает дисковый индекс, оно уменьшает значение счетчика свободных индексов, записанное в суперблоке.
Рассмотрим две пары массивов номеров свободных индексов (Рисунок 4.13). Если список свободных индексов в суперблоке имеет вид первого массива на Рисунке 4.13(а) при назначении индекса ядром, то значение указателя на следующий номер индекса уменьшается до 18 и выбирается индекс с номером 48. Если же список выглядит как первый массив на Рисунке 4.13(б), ядро заметит, что массив пуст и обратится в поисках свободных индексов к диску, при этом поиск будет производиться, начиная с индекса с номером 470, который был ранее запомнен. Когда ядро заполнит список свободных индексов в суперблоке до отказа, оно запомнит последний индекс в качестве начальной точки для последующих просмотров диска. Ядро производит назначение файлу только что выбранного с диска индекса (под номером 471 на рисунке) и продолжает прерванную обработку.
