Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf

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

тройку имя ключа/адрес по цепочке/ длина списка, изме­

Метод первый

1.Занести бит уничтожения записи

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

Метод второй

1.Занести бит уничтожения записи

2.Декодировать каждый ключ по справочнику, изменить адреса записи ДА в соответственных инвертированных списках н уменьшить длину списка на единицу

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

нахождения предыдущих записей по спискам ключей

170

Т а б л и ц а 8-6 Удаление ключей (инвертированный список)

1.Декодировать і-н ключ по справочнику инвертированного списка

переменной длины

3. Повторить пп. 1 и 2 для всех удаляемых из записи ключей

4.Если в файле записей имеются ключи, „достать" запись и уда­ лить их

В табл . 8-6 представлена процедура обновления д л я удаления ключей, подобная процедуре добавления клю­ чей, за исключением того, что переменная длина инвер­ тированного списка, из которого данный ключ д о л ж е н быть вычеркнут, всегда уменьшается и поэтому перефор­ мированный список может быть записан на ту ж е самую д о р о ж к у З У П Д (см. второй этап процедуры у д а л е н и я ) . Первый и второй этапы повторяются д л я всех ключей,

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

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

В табл . 8-7 описывается в общих чертах процедура добавления ключей к инвертированной списковой систе­

171

Т а б л и ц а 8-7 Давление ключей (инвертированный список)

1. Декодировать і-іі ключ по справочнику инвертированного спи­ ска переменной длины

2.Вставить в список адрес записи ДА, в которой ключ должен быть добавлен

3.Увеличить длину списка на единицу

4.Повторить пп. J—3 для всех добавляемых ключей

5. Прочесть запись по адресу ДА и добавить к ней новые ключи

6.Вновь занести на диск модифицированную запись в соответст­ вии с процедурой модификации неключевых данных

ла, если ключи присутствуют внутри записи. Тогда за­

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

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

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

выборке из запоминающего устройства, то список деко­ дируемых адресов следует отсортировать.

172

8-3. ОПЕРАТИВНОЕ ОБНОВЛЕНИЕ СЕКТОРОВ

Если указатели ф а й л а в справочнике обозначают секто­ ра (или по крайне мере списки внутри секторов) в систе­ мах с секторным разбиением, любое обновление спра­ вочника требуется только при перемещении записи за

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

8-4. ИСПОЛЬЗОВАНИЕ СВОБОДНОГО МЕСТА ПАМЯТИ

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

порядку зоны свободного пространства памяти либо ло­

1 73