Версия для печати темы

Автор: Rocket 11.10.2008 1:56

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

Автор: Rocket 13.10.2008 2:46

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

Автор: klem4 13.10.2008 10:39

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

Автор: volvo 14.10.2008 2:02

Насколько я понимаю, под двоичным разбиением подразумевается хранение списка свободных блоков в виде двоичного дерева поиска? См. здесь http://www.regatta.cs.msu.su/doc/usr/share/man/info/ru_RU/a_doc_lib/aixprggd/genprogc/sys_mem_alloc.htm#HDRA9E4A4CF217SYLV

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

Автор: Rocket 14.10.2008 2:24

Цитата(volvo @ 13.10.2008 23:02)

Насколько я понимаю, под двоичным разбиением подразумевается хранение списка свободных блоков в виде двоичного дерева поиска? См. здесь http://www.regatta.cs.msu.su/doc/usr/share/man/info/ru_RU/a_doc_lib/aixprggd/genprogc/sys_mem_alloc.htm#HDRA9E4A4CF217SYLV

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

Автор: volvo 14.10.2008 2:48

http://www.memorymanagement.org/articles/alloc.html#buddy.system ?

Автор: Rocket 14.10.2008 3:08

Цитата(volvo @ 13.10.2008 23:48)

Автор: volvo 14.10.2008 5:39

Перевод текста по ссылке:

#include <iostream>
int main() {

    class A {
    public:
        A() {
            std::cout << "A created" << std::endl;
        }
    };

    A obj;
    return 0;
}

Автор: Rocket 15.10.2008 4:03

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

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


Прикрепленные файлы
 1.doc ( 97.5 килобайт ) Кол-во скачиваний: 876

Автор: volvo 15.10.2008 22:58

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();

Автор: Rocket 17.10.2008 1:18

Цитата(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 17.10.2008 1:41

Автор: Rocket 17.10.2008 2:07

Цитата(volvo @ 16.10.2008 22:41)

Автор: volvo 18.10.2008 4:38

Устраивает меня или нет - это к делу не относится... Задание твое, тебе и карты в руки... Просто когда в задании тобой же написано:

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

Автор: Rocket 18.10.2008 7:08

Цитата(volvo @ 18.10.2008 1:38)

Автор: Rocket 18.10.2008 14:56

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

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

Автор: Rocket 4.11.2008 23:05

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

Автор: Rocket 8.11.2008 17:18

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

p.s. пишу в этой теме, т.к. задание непосредственно связано с предыдущей работой

Автор: Гость 10.11.2008 8:07

Память подкачки, выделяеться заранее. Используеться при нехватке ОЗУ.

Автор: Гость 10.11.2008 8:36

Извиняюсь перед Уважаемым Админисраором за оффтоп.
Просто надоедает что люди просто не хотят думать своей головой и поработат ручками. Документации сейчас в пространстве инета проста пруд пруди. Так что Rocket, вы просто ленитесь. Помощи нужно просить в крайних случаях а не от того что не хочеться делать и искать самому((((

Автор: Lapp 10.11.2008 8:52

Цитата(Rocket @ 8.11.2008 13:18)

Цитата(Гость @ 10.11.2008 4:36)

Автор: Rocket 14.11.2008 0:00

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

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

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

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


Прикрепленные файлы
 che.cpp ( 5.25 килобайт ) Кол-во скачиваний: 255

Автор: volvo 14.11.2008 2:05

Автор: Rocket 14.11.2008 2:55

Цитата(volvo @ 13.11.2008 22:05)

Автор: volvo 14.11.2008 4:30

Так вот по алгоритму ты должен после того, как освободил память:

// Функция 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 14.11.2008 5:12

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

Автор: volvo 14.11.2008 5:50

Ну смотри: вот процесс работы с твоей программой. Состояние - после выделения 16, 4, 8 байт:

Автор: Rocket 14.11.2008 14:42

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

Автор: volvo 14.11.2008 15:58

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