Zaawansowane CPP/Ćwiczenia 14: Zarządzanie pamięcią: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 28 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
'''Zadanie 1 '''  Przerób przykłady z wykładu.
+
{{cwiczenie|1||
  
'''Zadanie 2 '''  Napisz własną implementację zasobnika pamięci
+
Przerób przykłady z wykładu.  
(memory pool). Zasobnik powinien być szablonem przyjmującym jako
+
}}
parametr typ obiektów dla których będzie przydzialał pamięc. Wielkość
+
{{cwiczenie|2||
puli powina być podawana w konstruktorze.
 
  
  <nowiki>template<typename T> linked_pool {
+
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 <tt>std::bad_alloc</tt>.  Jeśli
 +
wyczerpie się pamięć w puli, żądanie przydziału powinno rzucić
 +
<tt>std::bad_alloc</tt>:
 +
 
 +
template<typename T> linked_pool {<br>
 +
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 ();<br>
 +
release() throw ();        /*zwalnia całą pamięć z puli*/
 +
~linked_pool() throw() ;
 +
}
 +
}}
  
linked_pool(size_t n);
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
void *allocate() throw(); /*przydziela pamięc na jeden obiket T*/
+
Przykładowe rozwiązanie znajduje się w pliku  [[media:Linked_pool.h | linked_pool.h]].
void deallocate(void p) throw ();
+
</div></div>
  
release()throw ();
+
{{cwiczenie|3||
  
&nbsp;linked_pool();
+
W oparciu o <code><nowiki>linked_pool</nowiki></code> zaimplementuj klasę
 +
z własnymi operatorami <code><nowiki>new</nowiki></code> i <code><nowiki>delete</nowiki></code>. Zaimplementuj klasę
 +
tak, aby można było z niej dziedziczyć i w ten sposób łatwo
 +
implementować <code><nowiki>new</nowiki></code> i <code><nowiki>delete</nowiki></code> w dowolnej klasie.
 +
}}
  
}
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
</nowiki>
+
Zobacz implementację zliczania elementów w [[Zaawansowane CPP/Wykład 3: Szablony II|wykładzie 3]]
 +
</div></div>
  
Jeśli zarządamy za dużo pamięci, to
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
powinien zostać zwrócony wskaźnik zerowy.
+
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;
  
'''Zadanie 3 '''  W oparciu o <code><nowiki>linked_pool</nowiki></code> napisz własne
+
Pamięć dla puli będzie przydzielona za pomocą statycznej funkcji:
operatory <code><nowiki>new</nowiki></code> i <code><nowiki>delete</nowiki></code>. Napisz klasę która, będzie  
 
implementowała te operatory i która będzie można dziedziczyć.
 
  
'''Wskazówka ''' Zobacz implementację zliczanie elementów w wykładzie 3.
+
  public:
 +
  static void request(size_t n) {
 +
    _pool <nowiki> =</nowiki>    new linked_pool<T>(n);
 +
  }
  
'''Zadanie 4 '''  Przerób nieznacznie alokator podany na wykładzie, tak  
+
która musi zostać wywołana przed stworzeniem jakichkolwiek obiektów
aby jego funkcje wypisywały inforacje o tym co robią. Użyj go z różnymi typami  
+
klasy <tt>T</tt>. Operator <tt>new</tt> sprawdza ten warunek:
pojemników. Co możesz powiedzieć o sposobie przydziału pamięci dla róznych
+
 
 +
  void *operator new(size_t size) throw (std::bad_alloc)
 +
    {
 +
      if(_pool<nowiki> =</nowiki>  <nowiki> =</nowiki>  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 [[media:Linked_new.h | linked_new.h]]. 
 +
 
 +
Z klasy <tt>linked_pool_new</tt> korzystamy dziedzicząc z niej:
 +
 
 +
struct X : public linked_pool_new<X> {
 +
  char big[1000000];
 +
};<br>
 +
main() {
 +
  X *x <nowiki> =</nowiki>    new X;
 +
}
 +
</div></div>
 +
 
 +
{{cwiczenie|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?
 
kontenerów?
 +
}}
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
Przykładowy alokator oparty o funkcję <tt>malloc</tt> jest
 +
zaimplementowany w pliku [[media:Mallocator.h | mallocator.h]].  Funkcje <tt>allocate</tt> i <tt>deallocate</tt> są tak
 +
zdefiniowane, że wypisują informacje o rozmiarze i ilości alokowanych
 +
elementów:
 +
 +
  pointer allocate(size_type n, const_pointer <nowiki> =</nowiki>    0) {
 +
    void* p <nowiki> =</nowiki>  malloc(n * sizeof(T));
 +
    std::cerr<<"a "<<n<<" "<<sizeof(T)<<" "<<p<<std::endl;
 +
    if (!p)
 +
      throw std::bad_alloc();
 +
    return static_cast<pointer>(p);
 +
  }<br>
 +
  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. <tt>vector</tt> i <tt>deque</tt> alokują pamięć dla
 +
wielu elementów na raz, natomiast lista alokuje pamięć po jednym elemencie.
 +
</div></div>
 +
 +
{{cwiczenie|5||
  
'''Zadanie 5 '''  W oparciu o <code><nowiki>linked_pool</nowiki></code> napisz własny alokator pamięci.
+
W oparciu o <code><nowiki>linked_pool</nowiki></code> napisz własny alokator pamięci.
 
Do jakich pojemników będzie można go stosować?.
 
Do jakich pojemników będzie można go stosować?.
 +
}}
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
 +
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 <tt>linked_pool</tt> 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 <tt>rebind</tt> nie możemy jednak teraz przydzialać pamięci dla puli dynamicznie, tak jak to robiliśmy w <tt>linked_pool_new</tt>. 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 <tt>rebind</tt> ma teraz postać:
 +
 +
template <class U>
 +
struct rebind { typedef pool_allocator<nowiki><U,N></nowiki> other; };
 +
 +
Całość kodu jest zamieszczona w pliku [[media:Pool_allocator.h | pool_allocator.h]]. Z tak zdefiniowanego alokatora korzysta się następująco:
 +
 +
std::list<int,pool_allocator<int,10000> > l;
 +
</div></div>

Aktualna wersja na dzień 10:51, 2 paź 2006

Ć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

Ć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
Rozwiązanie

Ć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

Ć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