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

[Rocket]

Доброго времени суток, Уважаемые Форумчане! Вот столкнулся с заданием, которое необходимо реализовать, как можно быстрей... Значит, нужно написать программу, моделирующую динамическое распределение памяти в операционной системе. В качестве модели оперативной памяти программа должна использовать байтовый массив размера не менее 256 байт. Использование других глобальных переменных в программе запрещено. В программе в обязательном порядке должны присутствовать следующие функции:
а) Выделить участок заданного размера. В случае успеха вывести начальный адрес выделенного участка. Если участка подходящего для выделения не найдено, необходимо вывести диагностическое сообщение о нехватке памяти.
б) Освободить ранее выделенный участок. В качестве параметра функция должна принимать начальный адрес освобождаемого участка. Ранее выделенный участок может быть освобожден только целиком (освобождение части участка не допускается).
в) Получение информации о свободных/занятых участках в «оперативной памяти» (количество участков каждого типа, начальные адреса, размеры, общее количество занятой и свободной памяти).
А хранить всю информацию, я должен ввиде списков блоков; алгоритм выделения- двоичное разбиение.
Помогите, пожалуйста с реализацией! Возможно у кого-ибудь найдутся соответветсвующие наработки....
Что вообще из себя представляет двоичное разбиение?...

[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