Морис Бах - Архитектура операционной системы UNIX

На Рисунке 9.2 представлен алгоритм выделения пространства с помощью карт памяти (malloc). Ядро просматривает карту в поисках первой строки, содержащей количество единиц ресурса, достаточное для удовлетворения запроса. Если запрос покрывает все количество единиц, содержащееся в строке, ядро удаляет строку и уплотняет карту (то есть в карте становится на одну строку меньше). В противном случае ядро переустанавливает адрес и число оставшихся единиц в строке в соответствии с числом единиц, выделенных по запросу. На Рисунке 9.3 показано, как меняется вид карты памяти для устройства выгрузки после выделения 100, 50 и вновь 100 единиц ресурса. В конечном итоге карта памяти принимает вид, показывающий, что первые 250 единиц ресурса выделены по запросам, и что теперь остались свободными 9750 единиц, начиная с адреса 251.

Рисунок 9.1. Первоначальный вид карты памяти для устройства выгрузки

алгоритм malloc /* алгоритм выделения пространства с использованием карты памяти */

входная информация:

(1) адрес /* указывает на тип используемой карты */

(2) требуемое число единиц ресурса

выходная информация:

адрес — в случае успешного завершения

0 — в противном случае

{

for (каждой строки карты) {

if (требуемое число единиц ресурса располагается в строке карты) {

if (требуемое число == числу единиц в строке)

удалить строку из карты;

else отрегулировать стартовый адрес в строке;

return (первоначальный адрес строки);

}

}

return (0);

}

Рисунок 9.2. Алгоритм выделения пространства с помощью карт памяти

Освобождая ресурсы, ядро ищет для них соответствующее место в карте по адресу. При этом возможны три случая:

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

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

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

Рисунок 9.3. Выделение пространства на устройстве выгрузки

Возвращаясь к предыдущему примеру, отметим, что если ядро освобождает 50 единиц ресурса, начиная с адреса 101, в карте памяти появится новая строка, поскольку освободившиеся ресурсы имеют адреса, не соприкасающиеся с адресами существующих строк карты. Если же затем ядро освободит 100 единиц ресурса, начиная с адреса 1, первая строка карты будет расширена, поскольку освободившиеся ресурсы имеют адрес, смежный с адресом первой строки. Эволюция состояний карты памяти для данного случая показана на Рисунке 9.4.

Предположим, что ядру был сделан запрос на выделение 200 единиц (блоков) пространства устройства выгрузки. Поскольку первая строка карты содержит информацию только о 150 единицах, ядро привлекает для удовлетворения запроса информацию из второй строки (см. Рисунок 9.5). Наконец, предположим, что ядро освобождает 350 единиц пространства, начиная с адреса 151. Несмотря на то, что эти 350 единиц были выделены ядром в разное время, не существует причины, по которой ядро не могло бы освободить их все сразу. Ядро узнает о том, что освободившиеся ресурсы полностью закрывают разрыв между первой и второй строками карты, и вместо прежних двух создает одну строку, в которую включает и освободившиеся ресурсы.

Рисунок 9.4. Освобождение пространства на устройстве выгрузки