Динамическое распределение памяти, c++ Опции

[Lapp]

Неужели никому не известно такое страшное слово как "своппинг"? : )

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

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


Добавлено через 6 мин.

Извиняюсь ...
Просто надоедает ...

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]

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

Нужно сначало выделить блок на 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;
 }

просмотреть соседний участок с только что освобожденным, если не ошибаюсь - справа от него, и если он тоже пуст - то объединить их, потом смотреть тот, что получился в результате объединения, и ЕГО соседа справа, и т.д. до тех пор, пока не встретишь непустой блок, или вся память не будет выделена одним куском, как при старте программы. А у тебя получается, что память как-бы свободна, общий размер свободных блоков достаточен для выделения памяти запрошеного размера, но память "фрагментирована", и ты не можешь выделить столько, сколько нужно (одного блока, способного полностью вместить запрошенный размер - нет)...

Сообщение отредактировано: volvo - 14.11.2008 0:32

[Rocket]

Но объединять мы можем только блоки равного размера... И вообще непонятным остаётся то, почему я не могу объдинить "дефрагментированную" память именно при таком разбиении... Можно более наглядно объяснить проблему и выход из неё ?) может какую-нибудь хитрую проверку сделать?
Да...и что со вторым багом? или они связаны...

Сообщение отредактировано: volvo - 14.01.2009 0:33

[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 - 14.01.2009 0:33

[volvo]

как-то очень странно, потому в такой ситуации : 20002000300000004000000000000000 блок в 32 выделяется с легкостью...

Хочешь, расскажу, в чем разница между выделением блока в 32 при
20002000300000004000000000000000,
и выделением блока в 32 при
40000000000000002000200030000000, и почему в первом случае память-таки выделяется, а во втором - нет?

Потому что ты выделяешь ее некорректно... Смотри (я тут немного "похозяйничал" в твоём коде, чтоб он легче читался):

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") ... Вот поэтому я тебе и говорю: как только освободил - сливай свободные блоки, иначе твоя программа разрастётся до невероятных размеров, если ты после нахождения каждого бага будешь патчить ИМЕННО ЭТОТ баг.

Сообщение отредактировано: volvo - 14.11.2008 12:00