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

[DejavuP]

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

Выделение свободной памяти по запросу часто выполняется либо по методу «наиболее подходящего», либо по методу «первого подходящего».

1. Метод «наиболее подходящего» заключается в том, что среди всех блоков, имеющих размер, не меньший требуемого, выбирается блок с наименьшим размером.

2. Метод «первого подходящего» заключается в том, что выделению подлежит первый в порядке просмотра элементов списка блок, размер которого не меньше требуемого.

Если блок, выбранный по одному из двух указанных методов имеет размер, превышающий указанный при запросе, он расщепляется
на два: первый блок имеет требуемый размер и предоставляется в ответ на запрос, второй блок - остаток - остается в списке свободной памяти. При освобождении блока смежные блоки склеиваются.
Написать программу, выполняющую:
- выделение блока свободной памяти заданного размера (результатом работы должен быть код возврата = -1, если блок такого размера выделен быть не может);
- освобождение, т.е. повторное включение в список свободной памяти блока, выделенного ранее.

[BDA]

Вам нужно сымитировать работу простого менеджера памяти. "Настоящую" динамическую память делить на блоки не надо. Как мне это видится. Нужно создать два списка. Один для свободных блоков, второй для занятых. Решить, сколько именно памяти будет имитироваться, например, 1000 байт. Каждый блок памяти описывать двумя числами (смещение; размер). Смещение считается от нуля. Поместить в список свободных блоков блок памяти (0; 1000). Теперь нужно описать две функции. Одна функция будет выделять блок памяти. Она вызывается с параметром требуемого размера свободной памяти (например, 100 байт), возвращает -1, если нельзя выделить память, или смещение выделенного блока. Внутри функции нужно пройтись по списку свободных блоков и выбрать подходящий. Подходящий блок (0; 1000) изымается из списка, затем разбивается на два блока, если имел размер больше требуемого. Первый из этих блоков (0; 100) помещается в список занятых блоков, второй блок (100; 900) в список свободных. Затем функция возвращает смещение 0 найденного блока. Вторая функция вызывается с параметром смещения блока, который надо вернуть. Теперь нужно идти по списку занятых блоков и искать блок, в который попало указанное смещение. Если блок найден, то он изымается из списка занятых, и начинается операция его возврата в список свободных. Для этого проходится список свободных блоков и производится попытка склейки только что освобожденного блока с текущим рассматриваемым блоком в списке. Если их можно склеить, то текущий блок изымается, склеивается с только что освобожденным блоком, и теперь уже для него и дальнейших свободных блоков в списке производится попытка склейки. Когда список свободных блоков пройден до конца, то склеенный блок помещается в конец.
Если совсем уж не знаете с чего начать, то напишите основную программу с вызовом 2 функций. Одна функция пусть всегда возвращает -1, а вторая просто ничего не делает. Затем понадобятся знания об организации списков в динамической памяти, хотя на первое время можно обойтись массивами фиксированного размера для упрощения. Опять же нужно отталкиваться от тех тем, которые были рассмотрены по учебе.

[DejavuP]

Сообщение от BDA

Вам нужно сымитировать работу простого менеджера памяти. "Настоящую" динамическую память делить на блоки не надо. Как мне это видится. Нужно создать два списка. Один для свободных блоков, второй для занятых. Решить, сколько именно памяти будет имитироваться, например, 1000 байт. Каждый блок памяти описывать двумя числами (смещение; размер). Смещение считается от нуля. Поместить в список свободных блоков блок памяти (0; 1000). Теперь нужно описать две функции. Одна функция будет выделять блок памяти. Она вызывается с параметром требуемого размера свободной памяти (например, 100 байт), возвращает -1, если нельзя выделить память, или смещение выделенного блока. Внутри функции нужно пройтись по списку свободных блоков и выбрать подходящий. Подходящий блок (0; 1000) изымается из списка, затем разбивается на два блока, если имел размер больше требуемого. Первый из этих блоков (0; 100) помещается в список занятых блоков, второй блок (100; 900) в список свободных. Затем функция возвращает смещение 0 найденного блока. Вторая функция вызывается с параметром смещения блока, который надо вернуть. Теперь нужно идти по списку занятых блоков и искать блок, в который попало указанное смещение. Если блок найден, то он изымается из списка занятых, и начинается операция его возврата в список свободных. Для этого проходится список свободных блоков и производится попытка склейки только что освобожденного блока с текущим рассматриваемым блоком в списке. Если их можно склеить, то текущий блок изымается, склеивается с только что освобожденным блоком, и теперь уже для него и дальнейших свободных блоков в списке производится попытка склейки. Когда список свободных блоков пройден до конца, то склеенный блок помещается в конец.
Если совсем уж не знаете с чего начать, то напишите основную программу с вызовом 2 функций. Одна функция пусть всегда возвращает -1, а вторая просто ничего не делает. Затем понадобятся знания об организации списков в динамической памяти, хотя на первое время можно обойтись массивами фиксированного размера для упрощения. Опять же нужно отталкиваться от тех тем, которые были рассмотрены по учебе.

Большое спасибо, стало яснее.