Помощь - Поиск - Пользователи - Календарь
Полная версия: Динамическое распределение памяти
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
Rocket
Доброго времени суток, Уважаемые Форумчане! Вот столкнулся с заданием, которое необходимо реализовать, как можно быстрей... Значит, нужно написать программу, моделирующую динамическое распределение памяти в операционной системе. В качестве модели оперативной памяти программа должна использовать байтовый массив размера не менее 256 байт. Использование других глобальных переменных в программе запрещено. В программе в обязательном порядке должны присутствовать следующие функции:
а) Выделить участок заданного размера. В случае успеха вывести начальный адрес выделенного участка. Если участка подходящего для выделения не найдено, необходимо вывести диагностическое сообщение о нехватке памяти.
б) Освободить ранее выделенный участок. В качестве параметра функция должна принимать начальный адрес освобождаемого участка. Ранее выделенный участок может быть освобожден только целиком (освобождение части участка не допускается).
в) Получение информации о свободных/занятых участках в «оперативной памяти» (количество участков каждого типа, начальные адреса, размеры, общее количество занятой и свободной памяти).
А хранить всю информацию, я должен ввиде списков блоков; алгоритм выделения- двоичное разбиение.
Помогите, пожалуйста с реализацией! Возможно у кого-ибудь найдутся соответветсвующие наработки....
Что вообще из себя представляет двоичное разбиение?...
Rocket
Программистушки, ну подскажите пожалуйста с реализацией! yes2.gif Нужно сдавать- аж "трубы горят" blink.gif
klem4
Ну вот узнаешь что-нибудь насчет двоичного разделения, поможем написать, помимо этого, все остальное выглядит не сложно, странно конечно что кроме самой 'памяти' нельзя глобальных переменных, как раз бы в глобальные еще и верхушку списка, каждый элемент которого - запись (смещение:длина_блока), не в файле же ее хранить.
volvo
Насколько я понимаю, под двоичным разбиением подразумевается хранение списка свободных блоков в виде двоичного дерева поиска? См. здесь Описание стандартной стратегии распределения памяти

Если так, то можно попробовать реализовать эмуляцию... Только уточни, это у тебя С++ или чистый С? (как-то странно будет эмулировать malloc с использованием самого malloc-а... Рекурсия, однако smile.gif )
Rocket
Цитата(volvo @ 13.10.2008 23:02) *

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

Если так, то можно попробовать реализовать эмуляцию... Только уточни, это у тебя С++ или чистый С? (как-то странно будет эмулировать malloc с использованием самого malloc-а... Рекурсия, однако smile.gif )

Про рекурсию верно подмечено, но..
Суть моего задания заключается в том, чтобы использовать только массив байт (256 байт), а в этом массиве как бы организовать структуру( то есть ни каких списков, всё в массиве). Этот массив, допустим, поделим по 4 байта, в этих байтах будет храниться информация о процессе: занят, процесс, адресс, размер(под "занят" выделяется бит, 1 или 0- признак). Данные о процессе заносятся как бы в "страницу" и выделяется необходимое количесвто байт под сам процесс. Выделять же я должен память с помощью двоичного разбиения (помимо него ещё есть: первый подходящий, наиболее подходящий, наименее подходящий, но мне досталось именно ДР)... Вот вообще про двоичное разбиение ничего толком не могу прочитать.

P.S. У меня с++
volvo
Binary buddy heap ?
Rocket
Цитата(volvo @ 13.10.2008 23:48) *
Видать здесь о чём-то двоичном : ) ... короче я в тупике....
volvo
Перевод текста по ссылке:
Цитата
В 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;
}
};

A obj;
return 0;
}
Где ты здесь видел глобальные переменные? smile.gif
Rocket
Дааа...алгоритм жесть...вообще в растеренности какой-то! Да и с этими списками блоков не лучше. Мне просто необходима Ваша помощь в реализации... unsure.gif

P.S. Прилагаю непосредственно своеобразную методичку по этой работе, только право в ней не особо много полезного...
volvo
Цитата
Мне просто необходима Ваша помощь в реализации...
Ну, ты же понимаешь, что если написать программу вместо тебя, то это тебе ничего не даст... Помочь - можно... Что именно у тебя вызывает наибольшую сложность? Начни хоть что-нибудь делать, потом будет видно, как можно продвигаться дальше, какими средствами ты умеешь пользоваться...

Я вот набросал программку, которая умеет только выделять память и печатать списки свободных блоков (чтобы хоть как-то проконтролировать правильность выполнения), но во-первых, в ней использовались 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-ти элементов? Это что, хранить кроме списка свободных блоков еще и список выделенных? Или как?

В общем, ждем начала твоей реализации...
Rocket
Цитата(volvo @ 15.10.2008 19:58) *

В общем, ждем начала твоей реализации...


Вот она :


#include <iostream>
#include <cmath>
using namespace std;

char ram[258];

int get_mem(int byte)
{
int block=1;
int cx=0, result=0, j=0;

block=(int)ceil((double)byte/3);
if(block > 86) { cout <<"Error!!!" <<endl; return -1; }

for(int i=0;i<258;i=i+3)
{
switch(ram[i] | 0)
{
case 0: cx++; break;
case 128: cx=0; break;
}
if(cx==block)
{
result=i;
break;
}
if(i==255 && cx!=block)
{
cout <<"Error!!!" <<endl;
return -1;
}
}
j=result;
cx=0;
while(cx!=block)
{
ram[j]=ram[j] | 128;
//ram[j+1]=byte;
cx++;
if(cx==block) { ram[j+1]=byte; break; }
j=j-3;
}
return j;
}
//---------------------------------------------
void del_mem(int address)
{
int block, byte;

byte=ram[address+1];
block=(int)ceil((double)byte/3);
for(int i=address;i<address+block*3;i=i+3)
ram[i]=ram[i] & 0;
}
//-----------------------------------------
void inf()
{
int block=0, free_block=0;
int p, free_mem, nf_mem, i;

for(int j=0;j<258;j=j+3)
{
if((ram[j] | 0) == 0 ) free_block++;
else block++;
}

nf_mem=block*3;
free_mem=free_block*3;
cout <<"number of free blocks: " <<free_block <<endl;
cout <<"number of not free blocks: " <<block <<endl;
i=0;
while(i<258)
{
switch(ram[i] | 0)
{
case 0: i=i+3; break;
case 128: p=(int)ceil((double)ram[i+1]/3);
cout <<"address " <<i <<' ' <<"size: " <<p*3 <<endl;
i=i+p*3;
break;
}
}
cout <<"count of free memory: " <<free_mem <<" bytes" <<endl;
cout <<"count of not free memory: " <<nf_mem <<" bytes" <<endl;
}
//-----------------------------------------
int main()
{
int a, b;
char choise='0';

while(choise!=27)
{
cout <<"=====================================================" <<endl;
cout <<"1. get memory" <<endl;
cout <<"2. free memory" <<endl;
cout <<"3. information of memory" <<endl;
cout <<"exit- Esc" <<endl;
cout <<"Make your choise: ";
cin >>choise;
cout <<"=====================================================" <<endl;
switch(choise)
{
case '1': cout <<endl;
cout <<"Enter byte: ";
cin >>a;
b=get_mem(a);
break;
case '2': cout <<endl;
cout <<"Enter address: ";
cin >>a;
del_mem(a);
break;
case '3': inf();
break;
default: break;
}
}

return 0;
}


Только здесь алгоритм не двоичного разбиения реализовал, а скорее первый подходящий... Но в целом нужно двигаться в этом ключе...
volvo
Цитата
Вот она :
Ууу... Нет-нет-нет... Это без меня... На чистом С я давно не писал и не собираюсь... А уж тем более на таком "спагетти": сама программа - plain C, а весь ввод/вывод - C++ ные потоки... Тем более, что я у тебя еще переспросил, на каком языке тебе это надо...

Цитата
в целом нужно двигаться в этом ключе...
В целом нужно двигаться в ключе твоей методички... Прочти ее внимательно, перед тем, как пытаться организовать несколько списков свободных блоков в том же самом буфере из 256 (откуда, кстати, взялись 258 ???) байт...
Rocket
Цитата(volvo @ 16.10.2008 22:41) *

Ууу... Нет-нет-нет... Это без меня... На чистом С я давно не писал и не собираюсь... А уж тем более на таком "спагетти": сама программа - plain C, а весь ввод/вывод - C++ ные потоки... Тем более, что я у тебя еще переспросил, на каком языке тебе это надо...

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

Мне это можно писать хоть на Паскале. Пишу я в ДефС++ и конечно не использую всю мощь с++, но я показал конкретно суть задания. Да, я взял 258, потому что блоки у меня кратны 3...
Просили моей реализации, ждали её начала- вот она...но Вас всё равно что-то не устраивает... unsure.gif
volvo
Устраивает меня или нет - это к делу не относится... Задание твое, тебе и карты в руки... Просто когда в задании тобой же написано:
Цитата
А хранить всю информацию, я должен ввиде списков блоков
(а не в виде карты памяти, понимаешь), но в качестве прототипа ты приводишь именно работу с картой памяти (ибо нигде у тебя ни одного байта памяти не выделяется, хотя должно, ни под списки свободных блоков, ни под список занятых блоков) - это по меньшей мере странно...

Ты понимаешь, что твою реализацию проще переписать заново, чем довести до того, что тебе нужно (судя по алгоритму метода, описанному в методичке)?

Да и вообще... Ну отвык я от С-шных конструкций. Мне проще сделать что-то вот в таком ключе:

#include <iostream>
#include <vector>
#include <cmath>

const int myMemSize = 256;
unsigned char memory[myMemSize];

class MemoryManager {
int greatest_index, smallest_index;

int log2(int size) {
return static_cast<int>(log(size) / log(2));
}

int getIndexBySize(int size) {

if(size > 0 && (size & (size - 1)) > 0) {
int count = 0;
while(size > 1) {
count += 1; size >>= 1;
}
size <<= count + 1;
}
std::cout << size << std::endl;
return log2(size);
}

void addFreeBlock(int index, int start_pos) {
free_list[index].push_back(ListItem(start_pos));
}
void removeFreeBlock(int start_pos) {
}

void divideBlock(int current, int last) {
if(current <= last) return;
else {

int start_dividing = free_list[current].at(0).start;
int size_dividing = 1 << current;

free_list[current - 1].push_back(ListItem(start_dividing));
free_list[current - 1].push_back(ListItem(start_dividing + size_dividing / 2));
free_list[current].erase(free_list[current].begin());

divideBlock(current - 1, last);
}
}

public:
MemoryManager() {
greatest_index = log2(myMemSize);
smallest_index = 0;
free_list.reserve(greatest_index + 1); // 0 to greatest_index

addFreeBlock(greatest_index, 0);
}

int requestAlloc(int size);
int requestFree(int id);

void printLists() {
std::cout << "printing lists" << std::endl;
for(int i = 0; i <= greatest_index; ++i) {

std::cout << "FMB #" << i << ": ";
Vector::iterator pv;
for(pv = free_list[i].begin(); pv < free_list[i].end(); ++pv) {
std::cout << "(" << (*pv).start << ")" << " ";
}
std::cout << std::endl;
}
}

struct ListItem {
ListItem(int value): start(value)
{
}
int start;
};

typedef std::vector<ListItem> Vector;
std::vector<Vector> free_list;
};

// returns -1 when allocation errors
int MemoryManager::requestAlloc(int size)
{
int check_in = getIndexBySize(size);
std::cout << "checking FMB #" << check_in << " ("<< (1 << check_in) << ")" << std::endl;
if(free_list[check_in].empty()) {

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, и какую-нибудь менюшку, и будет законченная программа)...
Rocket
Цитата(volvo @ 18.10.2008 1:38) *
(фрагмент программы компилируется, выполняется, память выделяется. Осталось добавить в класс MemoryManager список занятых блоков, реализовать requestFree, и какую-нибудь менюшку, и будет законченная программа)...

Большое спасибо smile.gif
...но насладиться работой этой программы я не смог, потому что, не зная логики программы, её основных функций, очень сложно реализовать её до конца...разобрать код, написанный в таком ключе, оказалось довольно не просто для меня.
Rocket
Всё-таки пишу по-своему, то есть теми средствами языка, которые мне известны rolleyes.gif ...

#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;

char MyMem[32];

int stTwo(int size)
{
int k=0;
while (pow(2,k)<size)
k+=1;
return k;
}

void Raz(int st2,int sb)
{
int i=0,k;
while(MyMem[i+sb] != st2 )
{
k=(int)pow(2,MyMem[i+sb])/2;
MyMem[i+sb]=((int)MyMem[i+sb])-1;
MyMem[i+k+sb] = ((int)MyMem[i+sb]);
i = 0;
cout<<"!!!"<<endl;
}
}

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;
}

/*int Checked(int sb,int st2)
{ int i=0,j;


for(i=0; i<32; i+=sb)
{
if (MyMem[i+1]!=1)
{if (MyMem[i]==st2)
{ MyMem[i+1]=1;
cout<<"FUCK"<<endl;
j=0;
break;
}
else
{j=(int)MyMem[i];
cout<<j<<endl;
cout<<"|||"<<endl;
}}


else j=1;

}
return j;
}

void Y(int sb,int st2)
{ int ch=Checked(sb,st2);
if(ch==1)
{ cout<<"razbiebie"<<endl;
Raz(st2,0);
}

}
*/
int main()
{
int size,st2,st,i=0,sb;
char ch;
st=stTwo(32);
MyMem[0]=st;

for(int i=0;i<32;i++)
{
cout<<(int)MyMem[i]<<" ";
}
cout<<endl;
while (ch != '4')

{ cout<<endl;
cout<<"********MENU*************"<<endl;
cout<<"1. To allocate memory "<<endl;
cout<<"2. To delete memory "<<endl;
cout<<"3. To display memory "<<endl;
cout<<"4. To Exit "<<endl;
cout<<"*************************"<<endl;
cout<<endl;
cin>>ch;

switch(ch)
{
case '1':

cout<<endl;
cout<<"Enter size of blok!"<<endl;
cin>>size;
st2=stTwo(size);
sb=(int)pow(2,st2);
AltChe(sb,st2);
break;

case '2':



case '3':

for(int i=0;i<32;i++)
{
cout<<(int)MyMem[i]<<" ";
}
break;
default: break;

}


}
}



Взял массив 32 байта(мне показалось, что в процессе разработки программы с таким легче работать). Значит, в первом байте блока я храню степень двойки, во втором байте 1 или 0. Реализовал функции разбиения и слияния блоков, то есть в принципе двоичное разбиение как таковое есть, но как организовать единый алгоритм? Это я пытаюсь делать в функции "AltChe"...
Rocket
Вобщем написал я это двоичное разбиение, с успехом его и сдал. Теперь же задание, связанное с моделированием страничной виртуальной памяти и алгоритмов свопинга. Для начала, что такое своппинг и как непосредственно он связан с оперативной памятью, реализованной в прошлом задании?
Rocket
Неужели никому не известно такое страшное слово как "своппинг"? : )

p.s. пишу в этой теме, т.к. задание непосредственно связано с предыдущей работой
Гость
Память подкачки, выделяеться заранее. Используеться при нехватке ОЗУ.
Гость
Извиняюсь перед Уважаемым Админисраором за оффтоп.
Просто надоедает что люди просто не хотят думать своей головой и поработат ручками. Документации сейчас в пространстве инета проста пруд пруди. Так что Rocket, вы просто ленитесь. Помощи нужно просить в крайних случаях а не от того что не хочеться делать и искать самому((((
Lapp
Цитата(Rocket @ 8.11.2008 13:18) *
Неужели никому не известно такое страшное слово как "своппинг"? : )

Слушай, Rocket, сам набрать в Википедии слово "своппинг" и "виртуальная память" никак не можешь? Обязательно нужно, чтоб тебя послали?

Задавай конкретные вопросы. Желательно по программированию.


Добавлено через 6 мин.
Цитата(Гость @ 10.11.2008 4:36) *
Извиняюсь ...
Просто надоедает ...

2 гость:
Надо не извиняться, надо не делать того, за что считаешь нужными извиняться.
Когда тебе успело надоесть? Спрятался за маской и выступаешь с трибуны.. Сначала зарегистрируйся, потом говори на такие темы. И не здесь, а в Жалобах или Свободном..

P.S.
Мне - можно.
Rocket
Значит данная программа реализует алгоритм двоичного разбиения. Для наглядности взял массив на 32 байта (ну эт моя оперативка, в 0 байте хранится степень двойки, в 1 байте признак занят/свободен). Вроде всё отлично работало, но вдруг нашел два бага:

1. Если моя ОП разбита следующим образом:
40000000000000002000200030000000 , то есть вся свободная. Когда я хочу добавить процесс, допустим, в 30 байт (нужно выделять 32 байта), то мне не удаётся выделить память ( появляется соответсявующее сообщение).

2. Ситуация : 41000000000000002000200031000000. Я хочу выделить, допустим, 7 байт (то есть должен выделить 8 байт), по идеи два блока 20002000 должны слиться, в результате должен получиться блок 31000000, но происходит тупо вылет из программы...

Помогите пожалуйста исправить данные баги, которые, как мне кажется, вызваны одной ошибкой...
volvo
Цитата
1. Если моя ОП разбита следующим образом:
40000000000000002000200030000000 , то есть вся свободная.
А как добиться такого разбиения? Вот сразу после запуска программы память тоже вроде вся свободная, но вот в таком виде:

Цитата
********MENU*************
1. To allocate memory
2. To delete memory
3. To display memory
4. To Exit
*************************

3
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Free Memory: 32 Occupied Memory: 0
, при этом 30 байт выделяется совершенно без проблем:
Цитата
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Free Memory: 32 Occupied Memory: 0

********MENU*************
1. To allocate memory
2. To delete memory
3. To display memory
4. To Exit
*************************

1

Enter size of blok!
30
Memory is allocated!

********MENU*************
1. To allocate memory
2. To delete memory
3. To display memory
4. To Exit
*************************

3
5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Что надо делать, чтобы повторить баг?
Rocket
Цитата(volvo @ 13.11.2008 22:05) *

А как добиться такого разбиения?
Что надо делать, чтобы повторить баг?

Нужно сначало выделить блок на 16, потом на 4, потом на 8. После этого очистить данные блоки.
volvo
Так вот по алгоритму ты должен после того, как освободил память:

// Функция DelMem

while(i < 32)
{
if ((MyMem[i]==st2)&&(MyMem[i+1]==1))
{
MyMem[i+1]=0; // <--- Вот тут
cout<<"Blok is empty!"<<endl;
break;
}
i+=sb;
}
просмотреть соседний участок с только что освобожденным, если не ошибаюсь - справа от него, и если он тоже пуст - то объединить их, потом смотреть тот, что получился в результате объединения, и ЕГО соседа справа, и т.д. до тех пор, пока не встретишь непустой блок, или вся память не будет выделена одним куском, как при старте программы. А у тебя получается, что память как-бы свободна, общий размер свободных блоков достаточен для выделения памяти запрошеного размера, но память "фрагментирована", и ты не можешь выделить столько, сколько нужно (одного блока, способного полностью вместить запрошенный размер - нет)...
Rocket
Но объединять мы можем только блоки равного размера... И вообще непонятным остаётся то, почему я не могу объдинить "дефрагментированную" память именно при таком разбиении... Можно более наглядно объяснить проблему и выход из неё ?) может какую-нибудь хитрую проверку сделать? rolleyes.gif
Да...и что со вторым багом? или они связаны...
volvo
Ну смотри: вот процесс работы с твоей программой. Состояние - после выделения 16, 4, 8 байт:
Цитата
4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 2 0 0 0 3 1 0 0 0 0 0 0
Free Memory: 4 Occupied Memory: 28
Так? Так... Теперь удаляем 4 байта:
Цитата
4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 3 1 0 0 0 0 0 0
Free Memory: 8 Occupied Memory: 24
Вот видишь, память освобождена, но ты не объединил то, что освободилось только что - красный блок - с тем, что справа от него - синий, они же оба свободны, и для того, чтобы выделить этот самый "красный", ты разбил то, что сейчас цветное на 2 части !!! Вот теперь ты должен их снова объединить.

Теперь, как проверить, с какой стороны тот блок, с которым надо попытаться объединить? Просто: если начальная позиция только что освобожденного блока - степень двойки, то "связанный" с ним блок надо искать непосредственно справа, иначе - слева. Вот тебе и алгоритм:

после освобождения блока: если индекс его первого элемента - степень двойки, то смотрим блок справа, иначе - слева. Если он такого же размера и пуст - то объединяем их, и повторяем операцию поиска "соседа" до тех пор, пока не дойдем до НЕпустого блока, или пока не объединишь все блоки в один

По поводу второго бага:
Цитата
по идеи два блока 20002000 должны слиться, в результате должен получиться блок 31000000
Знаешь, я в твоей программе (с ее наворотами и хитросплетениями) не нашел того места, где ты хотя бы пытаешься объединить свободные блоки. Опять же, у тебя эти 2 блока 20002000 свободны и НЕ объединены только потому, что один из них был занят, и при его освобождении ты не посмотрел на соседа и не объединил (алгоритм - выше). Не надо "откладывать на потом", освободил - немедленно сливай...
Rocket
Так а я в принципе и не пытаюсь начинать объединять блоки, после освобождения какого-либо блока...всё равно как-то очень странно, потому в такой ситуации : 20002000300000004000000000000000 блок в 32 выделяется с легкостью...
volvo
Цитата
как-то очень странно, потому в такой ситуации : 20002000300000004000000000000000 блок в 32 выделяется с легкостью...
Хочешь, расскажу, в чем разница между выделением блока в 32 при
20002000300000004000000000000000,
и выделением блока в 32 при
40000000000000002000200030000000, и почему в первом случае память-таки выделяется, а во втором - нет? smile.gif

Потому что ты выделяешь ее некорректно... Смотри (я тут немного "похозяйничал" в твоём коде, чтоб он легче читался):
int CheckedToAlloc(int sb,int st2)
{
int k=0,i;
// Допустим. Тут ты проверяешь, нет ли свободного блока нужного размера,
// чтоб выделить память одним куском... Не оказалось, идем дальше
for(i=0; i<32; i+=sb) {
if (( MyMem[i]==st2)&& (MyMem[i+1]!=1)) return 1;
}

// А дальше происходит нечто неправильное:
// изначально k = 0
while( k < 32 ) {
// проверил, не больше ли твой первый блок того, что тебе нужно
// Нет, не больше, первый блок = 2000, идем дальше
if ((MyMem[k]>st2) && (MyMem[k+1] != 1)) {
return 1;
}
else {
// Да, вот это условие выполняется... Ибо 2000 как раз меньше чем 50...0
if((MyMem[k]<st2) && (MyMem[k+1] != 1)) {
// Вот... Вот он, корень проблемы !!!
if (
(MyMem[k] == MyMem [k+(int)pow(2,(int)MyMem[k])])
&&
(MyMem [k+1+(int)pow(2,(int)MyMem[k])] != 1 )
)
{
return 1;
}
}
}

if (MyMem[k]>st2) k+=(int)pow(2,(int)MyMem[k]);
else k+=sb;
}
}

Что ты делаешь там, где я показал? Ты проверяешь, совпадает ли размер текущего и следующего блоков, и пустые ли они, и только на основании этого делаешь вывод, есть ли память для выделения??? Неверно. Этих двух условий недостаточно. Нужно, чтобы суммарный размер этих двух блоков был не меньше, чем требуется!

Иначе у тебя и вот в таком состоянии:
Цитата
2 0 0 0 2 0 0 0 3 1 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Free Memory: 24 Occupied Memory: 8
(+16 / -16 / +8 / +8 / -8 / +4 / -4) функция CheckedToAlloc вернет единицу как признак того, что память выделить можно, а BasAlg ее "выделит" (откуда он ее взял, спрашивается? Ясно же написано: "Free Memory: 24") ... Вот поэтому я тебе и говорю: как только освободил - сливай свободные блоки, иначе твоя программа разрастётся до невероятных размеров, если ты после нахождения каждого бага будешь патчить ИМЕННО ЭТОТ баг.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.