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

[Rocket]

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

[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]

(фрагмент программы компилируется, выполняется, память выделяется. Осталось добавить в класс MemoryManager список занятых блоков, реализовать requestFree, и какую-нибудь менюшку, и будет законченная программа)...

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

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