Моделирование менеджера памяти

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

Все вроде понятно. Прикинул в голове где очередь запихать, где список, где что. По интерфейсу пока рано, но то же понятно. Непонятно это:

поиск по всему списку и выбирает наименьший по размеру подходящий свободный фрагмент. Затем этот участок делится на 2 части

как мы задаем этот список? перечитал условие 10 раз и не вижу по какому принципу должен быть построен этот список. Это , как я понял, один из главных вопросов. Надо смоделировать память, но как? Список и все ячейки одинакового размера (в байтах)? Тогда зачем вопрос о наименьшем подходящем (так и о наибольшем, это тоже нужно реализовать)? Вот этот пункт мешает начать. Может кто-то подскажет?

Добавлено через 12 часов 12 минут
Вопрос в догонку.

В задаче сказано смоделировать процесс выделения памяти. То есть не нужно выделять память на самом деле, достаточно указать количество выдел. памяти тем же целым числом. Так?

То есть необходимо выделить 500 байт, просто впишем значение 500 в какое-то поле. Правильно? Потом займем 100 байт. Опять же просто числом. Так ведь?

Добавлено через 19 минут
Перечитал еще раз задание. Еще есть примечание.

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

То есть что в итоге?
Класс Задача, класс менеджер памяти (связный список с количеством элементов, выделенных в начале) и класс или методы у класса менеджер памяти, которые свяжут эти 2 класса. Так? Отзовитесь

0

создай 2 класса:
1. TMemoryManager
2. TProcessManager

1-ый класс будет распределять память и выводить карту памяти
2-ой класс будет управлять задачами и "запускать" их, запрашивая для них память у экземпляра TMemoryManager.

Добавлено через 51 минуту
В TMemoryManager используй структуру данных для ведения занятых/свободных диапазонов памяти. Занятые диапазоны должны быть связаны с задачами для которых была запрошена память.
Какую именно структуру использовать - решай сам, в зависимости от курса обучения. Возможно что преподаватель хочет чтобы ты использовал конкретную структуру данных.

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

Также реализует "выполнение" задач, т.е. , запрашивает память для текущей задачи из очереди, по истечении времени задачи (после успешного размещении ее в памяти) - удаляет её из памяти.

Задачу можно выделить в отдельный класс или структуру.


Есть вопросы по реализации?

0

Kitayets,
примерно понял, что вы предлагаете.

у меня была идея такая.
сделать класс задача и сделать класс менеджер, который будет работать с задачами, не очень понял как они должны взаимодействовать.
в вашем случае не понял как будут взаимодействовать Tmemory и Tproccess манагеры.
и все таки считаю, что должен быть связный список (или вы что-то другое предложите - получше? блин
в общем не очень понимаю как ваши шестеренки должны крутить друг друга

вот ваш класс мемориманагер - это просто класс с одним элементом (структурой данных) так ведь?
то есть у нас будет 1 экземпляр класса, потом еще 1, потом еще. так ведь?

0

у классов TProcessManager и TMemoryManager должно быть по одному экземпляру.

как это работает:
1. сначала создаётся экземпляр TMemoryManager (инициализируется кол-вом доступной памяти)
2. создаётся экземпляр TProcessManager - ему в конструкторе, или через set метод передаётся ссылка на экземпляр TMemoryManager
3. далее создаются задачи (имя, необх. кол-во памяти, время выполнения), они (ссылки на экземпляры) передаются экземпляру TProcessManager (например через метод addTask).
4. экземпляр классса TProcessManager добавляет задачу в список (очередь) на выполнение.
5. далее вызывается метод экземпляра классса TProcessManager Processing, после которого он выполняет выбор первой задачи из очереди, запрашивает память у MemoryManager, если память выделилась, то переносит задачу в список выполняемых, засекает время. Добавляет следующую задачу и т.д. Если запрос памяти выдал ошибку, то задача "опускается" в очереди, ниже задачи с меньшим необходимым кол-вом памяти, если таких задач нет, то processManager перестаёт запускать задачи до того, как не выполнится хотя бы одна задача, запущенная ранее.

Метод Processing периодически вызывается через промежутки времени (tick), каждый раз проверяя не закончилось ли время выполнения какой-нибудь задачи из списка выполняемых, ели закончилось, то задача переносится в список выполненных и вызывается метод освобождения памяти этой задачи у экземпляра TMemoryManager.

0

Kitayets,
processmanager более менее понятно.
как представить memorymanger?
список? список из ячеек, кол-во которых равно кол-ву выделенной памяти? или как? или список, сначала 1 элемент, размером с кол-во выдел. памяти, затем выделяется второй элемент, у первого вычитается размер второго и т.д. вот это неочень понятно.

0

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

в твоём же случае, я бы не стал реализовывать страничную память, а использовал бы модель, когда для процесса можно выделить только непрерывную область памяти. Для этого взял бы обычный TList или TStringList, а может быть и 2 списка (один для свободных диапазонов, другой для занятых).

например 2 TStringList, один freeMemory, другой usedMemory. в этих списках бы хранил диапазоны, в следующем виде:
для свободной памяти (freeMemory) каждая запись вида:
<начало диапазона>=<размер>, т.е при старте программы, когда вся память свободна, и её доступный размер 16 килобайт, то в этом списке будет одна запись вида:
'0=16384',
для занятой памяти (usedMemory) использовал бы записи вида:
<имя задачи>=<диапазон памяти старт-стоп>, например для задачи Job1 размером в один килобайт и распределённой с нулевого адреса:
'Job1=0-1023'.

Записи в таком виде удобны тем, что к правой части строки (после знака '=') можно обращаться через индексированное свойство values, например чтобы получить диапазон задачи job1 нужно просто выполнить код:

range: string;
...
range:=usedMemory.values['job1'];

далее range разложить на стартовый и конечный адреса.

Список с freeMamory - сортируем по размеру диапазона (есть такая возможность - определить для списка свою процедуру сортировки).

Выделение памяти - простая задача, берём необходимый для задачи объём памяти и ищем минимально допустимы диапазон, пересоздаём запись (или вообще удаляем, если объёмы совпали) изменяя стартовый адрес и остаток памяти, а в списке usedMemory создаём запись с выделенным диапазоном.

При удалении задачи - освобождение памяти несколько сложнее, т.к. тут надо проверить границы диапазона освобождаемой памяти и если на границах расположен[ы] свободные блоки то их нужно объединить.

Как вывести карту памяти - я думаю ты и сам понимаешь - пройтись по 2-м спискам и вывести диапазоны. Единственно тут нужно соблюсти порядок по стартовым адресам диапазонов, чтобы лучше воспринималось.

Можно, наверно, обойтись и одним списком.

0

Хм. Спасибо за советы.
Честно говоря мало чего понял из того, что вы объясняли. + Ваши идеи какие-то странные. Муторные что ли. Мудреные как-то. Без обид! Но взял во внимание идею с 2мя списками (в обещем-то почти получилась). Спасибо
Задал вопрос в другой теме по поводу одной фичи, решу, и финишная прямая будет.

Иерархия такая.

TMemBlock; // поля: старт, стоп, ид_задачи
TTask; // атрибуты и уник_ид

TProcessManager
--DoneList // TObjectList // эл-ты - TTask
--WaitingList // TObjectList // эл-ты - TTask
--OnIdleList // TObjectList // эл-ты - TTask
--HighPriorityList // TObjectList // эл-ты - TTask

TMemoryManager
--FreeList // TObjectList // эл-ты - TMemBlock
--UsedList // TObjectList // эл-ты - TMemBlock

Манагеры содержат интерфейсы по работе друг с другом. Обычно ПрокМанагер работает с МемМанагер.
Код приводить не буду пока что. Самому интересно, что вышло.
Хотя если нужно, кину.

0

можешь скинуть что у тебя получилось, сама сижу над таким заданием и пока не совсем понимаю как это сделать.

0

melkaya3010, Спусть полтора года кому-то понравилось.

Боюсь, что не найду этой лабы. Обычно никому ничего не нужно было))

0

меня только недавно заинтересовал этот вопрос)))) ну что ж, очень жаль....

0

melkaya3010, Вложение 401975

0

VladSharikov, вложение не существует, если что...

1

lab3.rar

UI, и правда. Потрите, пожалуйста, то сообщение.

0

спасибо большое))) не думала что ты его найдешь)))

0

melkaya3010, я всеравно не помню как оно делалось.

смотри выше как, если нужно. я не помню уже.

0

да я уже разобралась как и что, она мне очень помогла))))

0