Операционные системы. Управление ресурсами


Фиксированные разделы. - часть 4


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

Другой несложной стратегией является "самый подходящий" (best hit): просматривается весь список свободных блоков (или карта памяти) и выбирается блок, размер которого равен запросу или превышает его на минимальную величину. Хотя на первый взгляд этот метод может показаться более эффективным, он дает в среднем худшие результаты, чем "первый подходящий". Во-первых, это объясняется тем, что здесь следует обязательно просмотреть весь список или карту, во-вторых, тем, что здесь более интенсивно накапливаются внешние дыры, так как остатки от "самых подходящих" блоков оказываются маленького размера. Существенным же преимуществом этой стратегии является то, что она охраняет большие свободные блоки от "разбазаривания по мелочам".

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


Начало  Назад  Вперед



Книжный магазин