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


         

На представлен алгоритм выделения пространства


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


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

алгоритм malloc /* алгоритм выделения пространства с ис- пользованием карты памяти */ входная информация: (1) адрес /* указывает на тип ис- пользуемой карты */ (2) требуемое число единиц ресурса выходная информация: адрес - в случае успешного завершения 0 - в противном случае { для (каждой строки карты) { если (требуемое число единиц ресурса располагается в строке карты) { если (требуемое число == числу единиц в строке) удалить строку из карты; в противном случае отрегулировать стартовый адрес в строке; вернуть (первоначальный адрес строки); } } вернуть (0); }
Рисунок 9.2. Алгоритм выделения пространства с помощью карт памяти

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


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



Содержание  Назад  Вперед