0. 1.2.2. Упакованные данные

Размер самой «маленькой» переменной – 8 бит. Но для хранения некоторой информации достаточно меньшего объема (например, информацию о поле человека можно записать всего в 1 бит). Можно хранить несколько значений в одной целочисленной переменной (например – упаковать дату в 16 бит, предназначив 7 бит для года, 4 для месяца и 5 – для дня), но тогда нужно уметь записывать значения в часть переменной и извлекать их оттуда. Очевидно, что оператор присваивания в этом случае не сработает.

Пусть, например, у нас 16-разрядное число и требуемое нам значение хранится в четырех битах, с 3-го по 6-ой.

Чтобы извлечь из числа значение, следует скопировать его в промежуточную переменную (которую можно будет менять). Затем следует обнулить в ней все биты, кроме нужных (т.е. с 0 по 2 и с 7 по 15). Для обнуления можно использовать операцию И со специально подобранным числом-маской или операции сдвига. После этого следует сдвинуть разряды, используя операцию shr, вправо так, чтобы младший разряд нужного значения попал в нулевой бит (в данном примере, на 3 бита вправо). Значение выделено.

Для записи необходимо использовать следующий порядок действий. Очистить старое значение (т.е. обнулить биты 3-7, используя И уже с другой, инвертированной маской). Затем присвоить вспомогательной переменной нужное значение, сдвинуть его влево на требуемое число бит, и выполнить логическую операцию ИЛИ.

0. 1.2.3.Разработка менеджера памяти на основе битовой карты

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

Битовые карты используются некоторыми ОС для учета свободных и занятых фрагментов памяти.

В качестве единицы памяти, которой соответствует 1 бит карты, берется блок в несколько байт (4, 8, 16). При этом память выделяется и освобождается сегментами, размер которых кратен принятому размеру блока. Если объем ОП равен N байт, размер блока принят равным m байт, а карта состоит из l-битовых переменных, то необходимый размер массива, реализующего карту, можно вычислить как

k = N / (m * l).

Менеджер памяти должен реализовать следующие функции и процедуры:

1) Функцию предоставления непрерывного сегмента памяти объемом, кратным m. В качестве значения функция возвращает адрес выделенного сегмента памяти (номер его первого блока, блоки нумеруются с 0), либо -1, если непрерывного фрагмента свободной памяти требуемого объема нет. Обратите внимание, что номер первого выделенного байта не равен номеру битовой переменной в карте памяти (т.к. одна переменная в карте памяти описывает состояние нескольких блоков).

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

Функция должна пометить в карте выделенную память как занятую.

Примерное описание на языке Pascal:

function MyGetMem(var map:TBitmap; n:word):integer.

Здесь map – карта памяти; n – запрашиваемый объем памяти в байтах.

2) Процедуру освобождения сегмента памяти, кратного m. Процедура должна обнулить соответствующие биты в битовой карте.

Примерное описание:

Procedure MyFreeMem(var map:TBitmap; start,len:word).

Здесь map – карта памяти; start – адрес освобождаемого сегмента памяти (т.е. номер блока, с которого надо начать освобождение сегмента памяти); len – его длина (длина фрагмента памяти в байтах или блоках).

3) Процедуру очистки карты. Процедура должна обнулить все биты в битовой карте.

Примерное описание:

Procedure ClearMap(var map:TBitmap).

Здесь map – карта памяти.