Zaawansowane CPP/Ćwiczenia 14: Zarządzanie pamięcią

From Studia Informatyczne

Ćwiczenie 1

Przerób przykłady z wykładu.

Ćwiczenie 2

Napisz własną implementację puli pamięci opartą o listę. Zasobnik powinien być szablonem przyjmującym jako parametr typ obiektów, dla których będzie przydzielał pamięć. Wielkość puli powinna być podawana w konstruktorze. Jeśli zażądamy za dużo pamięci, to powinien zostać rzucony wyjątek std::bad_alloc. Jeśli wyczerpie się pamięć w puli, żądanie przydziału powinno rzucić std::bad_alloc:

template<typename T> linked_pool {
linked_pool(size_t n) throw(std::bad_alloc); void *allocate() throw(std::bad_alloc); /*przydziela pamięc na jeden obiekt T*/ void deallocate(void *p) throw ();
release() throw (); /*zwalnia całą pamięć z puli*/ ~linked_pool() throw() ; }

Rozwiązanie

Przykładowe rozwiązanie znajduje się w pliku linked_pool.h.

Ćwiczenie 3

W oparciu o linked_pool zaimplementuj klasę z własnymi operatorami new i delete. Zaimplementuj klasę tak, aby można było z niej dziedziczyć i w ten sposób łatwo implementować new i delete w dowolnej klasie.

Wskazówka

Zobacz implementację zliczania elementów w wykładzie 3

Rozwiązanie

Nasza klasa będzie szablonem przyjmującym jako parametr typ elementu, dla których pamięć będzie przydzielana. Ponieważ potrzebujemy jednej puli dla wszystkich obiektów danej klasy, obiekt puli będzie składową statyczną tej klasy. Musimy zdecydować jak i kiedy będzie ustalana ilość pamięci w puli: czy w czasie kompilacji, czy w czasie wykonania? Załóżmy, że chcemy ją przydzialać dynamicznie. Dlatego w klasie umieścimy wskaźnik do obiektu puli:

template<class T> class linked_pool_new {
  static linked_pool<T> *_pool;

Pamięć dla puli będzie przydzielona za pomocą statycznej funkcji:

public:
  static void request(size_t n) {
    _pool  =    new linked_pool<T>(n);
  }

która musi zostać wywołana przed stworzeniem jakichkolwiek obiektów klasy T. Operator new sprawdza ten warunek:

 void *operator new(size_t size) throw (std::bad_alloc)
   {
     if(_pool =    =   0) {
     std::cerr<<"you have to request the pool memory first"<<std::endl;
     abort();
   }
     return (void *)_pool->allocate();
   };

Całość kodu można zobaczyć w pliku linked_new.h.

Z klasy linked_pool_new korzystamy dziedzicząc z niej:

struct X : public linked_pool_new<X> {
  char big[1000000]; 
};
main() { X *x = new X; }

Ćwiczenie 4

Przerób nieznacznie alokator podany na wykładzie, tak aby jego funkcje wypisywały informacje o tym co robią. Użyj go z różnymi typami pojemników. Co możesz powiedzieć o sposobie przydziału pamięci dla różnych kontenerów?

Rozwiązanie

Przykładowy alokator oparty o funkcję malloc jest zaimplementowany w pliku mallocator.h. Funkcje allocate i deallocate są tak zdefiniowane, że wypisują informacje o rozmiarze i ilości alokowanych elementów:

 pointer allocate(size_type n, const_pointer  =    0) {
   void* p  =   malloc(n * sizeof(T));
   std::cerr<<"a "<<n<<" "<<sizeof(T)<<" "<<p<<std::endl;
   if (!p)
     throw std::bad_alloc();
   return static_cast<pointer>(p);
 }
void deallocate(pointer p, size_type n) { std::cerr<<"d "<<n<<" "<<sizeof(T)<<" "<<p<<std::endl; free(p); }

Wykonując np. instrukcje:

 std::cerr<<"vector"<<std::endl;
 std::vector<int,malloc_allocator<int> > v(4);
 std::cerr<<"deque"<<std::endl;
 std::deque<int,malloc_allocator<int> > d(4);
 std::cerr<<"list"<<std::endl; 
 std::list<int,malloc_allocator<int> > l(4);

łatwo się przekonać, że np. vector i deque alokują pamięć dla wielu elementów na raz, natomiast lista alokuje pamięć po jednym elemencie.

Ćwiczenie 5

W oparciu o linked_pool napisz własny alokator pamięci. Do jakich pojemników będzie można go stosować?.

Rozwiązanie

Z powyższego ćwiczenia widać, że prosty alokator przydzielający pamięć na pojedyncze elementy tego samego rozmiaru, będzie mogł być użyty tylko z tymi pojemnikami, które alokują pamięć pojedynczo, np. z listą. Ale właśnie takie pojemniki mogą najbardziej skorzystać z przyspieszenia swojego działania dzięki sprawniejszej alokacji i dealokacji pamięci.

Implementując alokator oparty o linked_pool znów musimy uważać na sposób przydziału pamięci dla puli. Ponieważ musimy zapewnić równoważność iteratorów, każda lista musi alokować pamięć z tej samej puli. Pula będzie więc składową statyczną alokatora. Z powodu mechanizmu rebind nie możemy jednak teraz przydzialać pamięci dla puli dynamicznie, tak jak to robiliśmy w linked_pool_new. Dlatego rozmiar puli będzie podawany jako drugi argument szablonu alokatora:

template <class T,size_t N> class      pool_allocator {
 private:
static  linked_pool<T> _pool;  

Inicjalizacja puli wygląda następująco:

template<class T,size_t N>  linked_pool<T> pool_allocator<T,N>::_pool(N);  

(składowe statyczne inicjalizowane są poza klasą). Wyrażenie rebind ma teraz postać:

template <class U> 
struct rebind { typedef pool_allocator<U,N> other; };

Całość kodu jest zamieszczona w pliku pool_allocator.h. Z tak zdefiniowanego alokatora korzysta się następująco:

std::list<int,pool_allocator<int,10000> > l;