1. Пользуйтесь тегами кода. - [code] ... [/code] 2. Точно указывайте язык, название и версию компилятора (интерпретатора). 3. Название темы должно быть информативным. В описании темы указываем язык!!!
Доброго времени суток, Уважаемые Форумчане! Вот столкнулся с заданием, которое необходимо реализовать, как можно быстрей... Значит, нужно написать программу, моделирующую динамическое распределение памяти в операционной системе. В качестве модели оперативной памяти программа должна использовать байтовый массив размера не менее 256 байт. Использование других глобальных переменных в программе запрещено. В программе в обязательном порядке должны присутствовать следующие функции: а) Выделить участок заданного размера. В случае успеха вывести начальный адрес выделенного участка. Если участка подходящего для выделения не найдено, необходимо вывести диагностическое сообщение о нехватке памяти. б) Освободить ранее выделенный участок. В качестве параметра функция должна принимать начальный адрес освобождаемого участка. Ранее выделенный участок может быть освобожден только целиком (освобождение части участка не допускается). в) Получение информации о свободных/занятых участках в «оперативной памяти» (количество участков каждого типа, начальные адреса, размеры, общее количество занятой и свободной памяти). А хранить всю информацию, я должен ввиде списков блоков; алгоритм выделения- двоичное разбиение. Помогите, пожалуйста с реализацией! Возможно у кого-ибудь найдутся соответветсвующие наработки.... Что вообще из себя представляет двоичное разбиение?...
Ну вот узнаешь что-нибудь насчет двоичного разделения, поможем написать, помимо этого, все остальное выглядит не сложно, странно конечно что кроме самой 'памяти' нельзя глобальных переменных, как раз бы в глобальные еще и верхушку списка, каждый элемент которого - запись (смещение:длина_блока), не в файле же ее хранить.
Сообщение отредактировано: klem4 -
--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
Если так, то можно попробовать реализовать эмуляцию... Только уточни, это у тебя С++ или чистый С? (как-то странно будет эмулировать malloc с использованием самого malloc-а... Рекурсия, однако )
Если так, то можно попробовать реализовать эмуляцию... Только уточни, это у тебя С++ или чистый С? (как-то странно будет эмулировать malloc с использованием самого malloc-а... Рекурсия, однако )
Про рекурсию верно подмечено, но.. Суть моего задания заключается в том, чтобы использовать только массив байт (256 байт), а в этом массиве как бы организовать структуру( то есть ни каких списков, всё в массиве). Этот массив, допустим, поделим по 4 байта, в этих байтах будет храниться информация о процессе: занят, процесс, адресс, размер(под "занят" выделяется бит, 1 или 0- признак). Данные о процессе заносятся как бы в "страницу" и выделяется необходимое количесвто байт под сам процесс. Выделять же я должен память с помощью двоичного разбиения (помимо него ещё есть: первый подходящий, наиболее подходящий, наименее подходящий, но мне досталось именно ДР)... Вот вообще про двоичное разбиение ничего толком не могу прочитать.
В buddy-системах распределитель выделяет только блоки определённых размеров, и содержит несколько списков свободных блоков: по одному на каждый допустимый размер. Допустимые размеры обычно - либо степень двойки, либо последовательность Фибоначчи (пример см. ниже). Так что любой блок за исключением блока минимального размера может быть поделён на 2 меньших блока допустимого размера.
Когда распределитель получает запрос на выделение памяти, он округляет запрашиваемый размер вверх (в большую сторону), и возвращает первый блок из списка свободных блоков этого размера. Если список свободных блоков для округлённого размера пуст, распределитель разбивает блок из списка бОльшего размера, и возвращает один из кусков. Оставшийся кусок добавляется к списку блоков соответствующего размера...
Когда блоки возвращаются, возможны попытки объединить находящиеся рядом свободные блоки в блоки бОльшего допустимого размера (coalescence). Для облегчения этого размера списки свободных блоков могут храниться по возрастанию адресов. Основное преимущество buddy-систем это "дешевизна" объединения, поскольку "приятель" любого свободного блока может быть вычислены по его адресу.
(здесь картинка)
К примеру, распределитель бинарной buddy-системы может работать с размерами 16, 32, 64,... 64 kB. Он может начать с единственного блока размером в 64К. Если приложение запрашивает блок в 8К, распределитель проверит список 8-ми килобайтных свободных блоков и не найдет свободных блоков такого размера. После чего он разобьёт 64К блок на 2 блока по 32К, один из которых в свою очередь разобьёт на два 16К блока. Один из 16К будет разбит на два 8К блока. Один из 8-ми Кб блоков будет отдан запрашивающему приложению, а 3 блока размерами 8Кб 16К и 32К - будут сохранены в соответствующих списках свободных блоков. Если после этого приложение запросит блок размером 10К, распределитель округлит размер до 16К, и вернет 16-ти Кб блок из списка для этого размера, при этом 6К будут потрачены впустую.
Buddy-система Фибоначчи может использовать блоки размером 16, 32, 48, 80, 128, 208, ... байт (размер очередного блока - сумма предыдущих двух размеров). Когда разбивается блок из одного списка свободных блоков, две части добавляются к спискам двух предыдущих размеров...
Buddy-системы могут работать очень хорошо, а могут - очень плохо, в зависимости от того, как выбранные размеры соответствуют типичным запросам системы. Округление обычно ведет к значительным количествам потраченной впустую (wasted) памяти, называемой внутренней фрагментацией (internal fragmentation). Она может быть уменьшена сближением допустимых размеров для выделяемых блоков.
А теперь - от меня... Мне все-таки думается, что вот тут:
Цитата
Суть моего задания заключается в том, чтобы использовать только массив байт (256 байт), а в этом массиве как бы организовать структуру
ты очень сильно ошибаешься, ибо в таком случае если у тебя запросить блок размером в 2 байта, ты потратишь почти всю память на список свободных блоков... Не в этом твоя задача, насколько я ее вижу... А в том, чтобы создать такую структуру данных, которая могла бы выделять по запросу память и корректно оперировать списками свободных блоков, хранящимися в самой структуре. То есть, у тебя есть 256 (или больше, в задании написано минимум 256) байт "оперативной" памяти, и есть менеджер памяти, который хранит все, что тебе нужно... Занимаемая им память не касается "оперативной".
Ограничение
Цитата
Использование других глобальных переменных в программе запрещено.
обходится элементарно: нельзя глобальные - используй локальные, тем более, что С++ позволяет локально описать класс:
#include <iostream> int main() {
class A { public: A() { std::cout << "A created" << std::endl; } };
Ну, ты же понимаешь, что если написать программу вместо тебя, то это тебе ничего не даст... Помочь - можно... Что именно у тебя вызывает наибольшую сложность? Начни хоть что-нибудь делать, потом будет видно, как можно продвигаться дальше, какими средствами ты умеешь пользоваться...
Я вот набросал программку, которая умеет только выделять память и печатать списки свободных блоков (чтобы хоть как-то проконтролировать правильность выполнения), но во-первых, в ней использовались vector-ы из STL, а во-вторых, не совсем понятно вот что:
MemoryManager mm;
int X = mm.requestAlloc(26); std::cout << "Alloc result = " << X << std::endl; mm.printLists(); int Y = mm.requestAlloc(15); std::cout << "Alloc result = " << Y << std::endl; mm.printLists();
Допустим, все работает. Как именно должно происходить "возвращение" памяти в систему. Я о том, откуда MemoryManager должен знать, что X - это адрес начала блока из 32-х, а Y - адрес начала блока из 16-ти элементов? Это что, хранить кроме списка свободных блоков еще и список выделенных? Или как?
Ууу... Нет-нет-нет... Это без меня... На чистом С я давно не писал и не собираюсь... А уж тем более на таком "спагетти": сама программа - plain C, а весь ввод/вывод - C++ ные потоки... Тем более, что я у тебя еще переспросил, на каком языке тебе это надо...
Цитата
в целом нужно двигаться в этом ключе...
В целом нужно двигаться в ключе твоей методички... Прочти ее внимательно, перед тем, как пытаться организовать несколько списков свободных блоков в том же самом буфере из 256 (откуда, кстати, взялись 258 ???) байт...
Ууу... Нет-нет-нет... Это без меня... На чистом С я давно не писал и не собираюсь... А уж тем более на таком "спагетти": сама программа - plain C, а весь ввод/вывод - C++ ные потоки... Тем более, что я у тебя еще переспросил, на каком языке тебе это надо...
В целом нужно двигаться в ключе твоей методички... Прочти ее внимательно, перед тем, как пытаться организовать несколько списков свободных блоков в том же самом буфере из 256 (откуда, кстати, взялись 258 ???) байт...
Мне это можно писать хоть на Паскале. Пишу я в ДефС++ и конечно не использую всю мощь с++, но я показал конкретно суть задания. Да, я взял 258, потому что блоки у меня кратны 3... Просили моей реализации, ждали её начала- вот она...но Вас всё равно что-то не устраивает...
Устраивает меня или нет - это к делу не относится... Задание твое, тебе и карты в руки... Просто когда в задании тобой же написано:
Цитата
А хранить всю информацию, я должен ввиде списков блоков
(а не в виде карты памяти, понимаешь), но в качестве прототипа ты приводишь именно работу с картой памяти (ибо нигде у тебя ни одного байта памяти не выделяется, хотя должно, ни под списки свободных блоков, ни под список занятых блоков) - это по меньшей мере странно...
Ты понимаешь, что твою реализацию проще переписать заново, чем довести до того, что тебе нужно (судя по алгоритму метода, описанному в методичке)?
Да и вообще... Ну отвык я от С-шных конструкций. Мне проще сделать что-то вот в таком ключе:
int current = check_in; while(check_in <= greatest_index && free_list[check_in].empty()) { check_in += 1; }
if(check_in > greatest_index) { std::cout << size << "bytes of free memory was not found..." << std::endl; return -1; } else { std::cout << "current = " << current << " check_in = " << check_in << std::endl;
divideBlock(check_in, current); int ID = free_list[current].at(0).start; free_list[current].erase(free_list[current].begin());
return ID; } } }
int MemoryManager::requestFree(int id) { }
int main() { MemoryManager mm;
int X = mm.requestAlloc(26); std::cout << "Alloc result = " << X << std::endl; mm.printLists(); int Y = mm.requestAlloc(15); std::cout << "Alloc result = " << Y << std::endl; mm.printLists();
return 0; }
, чем то, что было у тебя... (фрагмент программы компилируется, выполняется, память выделяется. Осталось добавить в класс MemoryManager список занятых блоков, реализовать requestFree, и какую-нибудь менюшку, и будет законченная программа)...
(фрагмент программы компилируется, выполняется, память выделяется. Осталось добавить в класс MemoryManager список занятых блоков, реализовать requestFree, и какую-нибудь менюшку, и будет законченная программа)...
Большое спасибо ...но насладиться работой этой программы я не смог, потому что, не зная логики программы, её основных функций, очень сложно реализовать её до конца...разобрать код, написанный в таком ключе, оказалось довольно не просто для меня.
void Sliyanie(int st2, int sb) { int i=0,k; while(MyMem[i] != st2) { k=(int)pow(2,MyMem[i+sb]); MyMem[i+sb]=((int)MyMem[i+sb])+1; MyMem[i+k+sb] = 0; i = 0; cout<<"???"<<endl; }
}
int AltChe(int sb, int st2) { int i=0,j,k,l,X; for(i=0; i<32; i+=sb) { X=MyMem[i]-st2; cout<<X<<endl; getch(); if (X>0) { j=(int)(2,(int)MyMem[i]); for (i=0; i<32; i+=j) if (MyMem[i+1]!= 1) { Raz(st2,i); cout<<"razbienie"<<endl; } else cout<<"Error!"<<endl;
}
if (X=0) { k=(int)(2,(int)MyMem[i]); for (i=0; i<32; i+=k) if (MyMem[i+1]!= 1) { MyMem[i+1]= 1; cout<<"Blok is load!"<<endl; } else cout<<"BOLT"<<endl;
}
if (X<0) { l=(int)(2,(int)MyMem[i]); for (i=0; i<32; i+=l) if (MyMem[i+1]!= 1) { Sliyanie(st2,i); cout<<"sliyanie"<<endl; } else cout<<"Error!"<<endl; } } return 0; }
Взял массив 32 байта(мне показалось, что в процессе разработки программы с таким легче работать). Значит, в первом байте блока я храню степень двойки, во втором байте 1 или 0. Реализовал функции разбиения и слияния блоков, то есть в принципе двоичное разбиение как таковое есть, но как организовать единый алгоритм? Это я пытаюсь делать в функции "AltChe"...
Вобщем написал я это двоичное разбиение, с успехом его и сдал. Теперь же задание, связанное с моделированием страничной виртуальной памяти и алгоритмов свопинга. Для начала, что такое своппинг и как непосредственно он связан с оперативной памятью, реализованной в прошлом задании?
Извиняюсь перед Уважаемым Админисраором за оффтоп. Просто надоедает что люди просто не хотят думать своей головой и поработат ручками. Документации сейчас в пространстве инета проста пруд пруди. Так что Rocket, вы просто ленитесь. Помощи нужно просить в крайних случаях а не от того что не хочеться делать и искать самому((((