Распределитель Мак-Кьюзика—Кэрелса

Маршалл Кирк Мак-Кьюзик и Майкл Дж. Кэрелс разработали усовершенствованный метод выделения памяти, который был реализован во многих вариантах системы UNIX, в том числе 4.4BSD и Digital UNIX. Методика позволяет избавиться от потерь в тех случаях, когда размер запрашиваемого участка памяти равен некоторой степени двойки. В нем также была произведена оптимизация перебора в цикле. Такие действия теперь нужно производить только в том случае, если на момент компиляции неизвестен размер выделенного участка.

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

Распределитель Мак-Кьюзика—Кэрелса страницами использует дополнительный массив kmemsizes[]. Каждая страница может находиться в одном из трех перечисленных состояний.
♦ Быть свободной. В этом случае соответствующий элемент массива kmemsizes[] содержит указатель на элемент, описывающий следующую свободную страницу.
♦ Быть разбитой на буферы определенного размера. Элемент массива содержит размер буфера.
♦ Являться частью буфера, объединяющего сразу несколько страниц. Элемент массива указывает на первую страницу буфера, в которой находятся данные о его длине.

Так как длина всех буферов одной страницы одинакова, нет нужды хранить в заголовках выделенных буферов указатель на список свободных буферов. Процедура free() находит страницу путем маскирования младших разрядов адреса буфера и обнаружения размера буфера в соответствующем элементе массива kmemsizes[]. Отсутствие заголовка в выделенных буферах позволяет экономить память при удовлетворении запросов с потребностью в памяти, кратной некоторой степени числа 2.

Если вы увлекаетесь не только программированием, но и хотите быть в курсе всех новинок Apple, то на http://iok.com.ua/blog вы найдете много интересного. Здесь вы узнаете какой смартфон лучше выбрать – iPhone6S или iPhone 6S Plus, цены на них и многое другое. Заходите – не пожалеете!

Оставить комментарий:

XHTML: Вы можете использовать теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>