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

[Rocket]

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

[Rocket]

Программистушки, ну подскажите пожалуйста с реализацией! Нужно сдавать- аж "трубы горят"

[klem4]

Ну вот узнаешь что-нибудь насчет двоичного разделения, поможем написать, помимо этого, все остальное выглядит не сложно, странно конечно что кроме самой 'памяти' нельзя глобальных переменных, как раз бы в глобальные еще и верхушку списка, каждый элемент которого - запись (смещение:длина_блока), не в файле же ее хранить.

Сообщение отредактировано: klem4 - 13.10.2008 6:41

[volvo]

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

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

[Rocket]

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

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

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

P.S. У меня с++

[volvo]

Binary buddy heap ?

[Rocket]

Binary buddy heap ?

Видать здесь о чём-то двоичном : ) ... короче я в тупике....

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

Где ты здесь видел глобальные переменные?

[Rocket]

Дааа...алгоритм жесть...вообще в растеренности какой-то! Да и с этими списками блоков не лучше. Мне просто необходима Ваша помощь в реализации...

P.S. Прилагаю непосредственно своеобразную методичку по этой работе, только право в ней не особо много полезного...

Сообщение отредактировано: Rocket - 15.10.2008 20:14

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

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

Вот она :

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

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

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

Мне это можно писать хоть на Паскале. Пишу я в ДефС++ и конечно не использую всю мощь с++, но я показал конкретно суть задания. Да, я взял 258, потому что блоки у меня кратны 3...
Просили моей реализации, ждали её начала- вот она...но Вас всё равно что-то не устраивает...

[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

[Rocket]

Всё-таки пишу по-своему, то есть теми средствами языка, которые мне известны ...

#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, вы просто ленитесь. Помощи нужно просить в крайних случаях а не от того что не хочеться делать и искать самому((((