Управление памятью с использованием битовых карт и связанного списка - PullRequest
Новая
       36

Управление памятью с использованием битовых карт и связанного списка

2 голосов
/ 12 февраля 2012

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

Может кто-нибудь помочь мне определить плюсыи минусы этих двух методов, и когда мы должны предпочесть другой.Я понял оба метода, но не могу определить ситуацию, когда я предпочитаю один из них другому.

Для дальнейшего пояснения, эти оба метода являются стандартными методами, используемыми в книгах по операционным системам.

1 Ответ

2 голосов
/ 20 декабря 2016

Связанный список

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

минусы: чтобы пройти по списку, вам нужно прочитать каждый блок! Кроме того, поддержание списка «смежным» способом обходится дорого, чтобы избежать фрагментации (подумайте о стоимости обновления списка более разумным способом, чем просто добавление каждого нового свободного блока в конце).

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

Bitmap

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

минусов: более высокие требования к памяти, поскольку вам необходим один бит на блок (~ 128 МБ для диска емкостью 1 ТБ с блоками 1 КБ).

Компромисс

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

Смотри также: https://en.wikipedia.org/wiki/Free_space_bitmap

...