On 04/05/2011 18:23, Piotrek wrote:
>> W dniu 02.05.2011 20:37, f...@W...gazeta.pl pisze:
>
>>> nie mozna, nie mozna miec leakow jak sie nie alokje ani dealokuje nawet
>
>>> bita pamieci spoza statycznej puli
>
>> Ależ można, można - starczy, że pobierzesz coś z puli a potem nie
>
>> zwrócisz. W momencie gdy używasz puli jedyna różnica w porównaniu do
>
>> malloc/free/realloc to to, że tracisz czas na pisanie samemu alokatora i
>
>> ryzykujesz popełnienie w tym błędów.
>
> Mógłbyś podać jakiś możliwie krótki przykład na występowanie wycieku w
> programie bez dynamicznej alokacji? Jakoś nie mogę sobie tego wyobrazić (chyba
> że używasz pojęcia wycieku w jakimś szerszym kontekście).

Proszę bardzo, przykład życiowy i oczywisty: cache.
Mamy otóż zewnętrzny zasób, z którego dla jakiegoś klucza k możemy
otrzymać pewne dane, załóżmy mieszczące się w buforze stałej wielkości,
nazwijmy te dane rekordem. Ponieważ często żądamy tych samych rekordów,
piszemy cache trzymający ileś-tam wybranych rekordów w pamięci i
udostępniający wersję z pamięci zamiast odpytywać zasób.

Rekordy trzymane są w statycznej tablicy o zdefiniowanej stałą wielkości
N. Oprócz samych rekordów cache trzyma struktury pomcnicze; kontener
assocjacyjny (powiedzmy hash-table) pozwalający szybko sprawdzić czy
istnieje rekord dla daego klucza i jeśli tak, uzyskać namiary na niego,
oraz strukturę przechowującą wolne rekordy i pozwalającą pobrać
"następny wolny", załóżmy że to jest jakaś linked list. Obydwie te
struktury mogą być zrealizowane na statycznych tablicach.

Algorytm jest taki (dla uproszczenia jest to cache read-only działający
z założeniem, że rekodry trzymane zewnętrznie są niezmienne):

rekord pobierz(key k)
if (rekord r dla klucza k jest w hash table)
if (rekord r jest na liście wolnych elementów)
usuń r z listy wolnych elementów
inkrementuj licznik referencji na r
return r
else
if (lista wolnych elementów nie jest pusta)
pobierz i usuń pierwszy element r z listy wolnych elementów
pobierz dane dla klucza k z zewnętrznego zasobu
zamapuj k->r w hash table
return r
else
czekaj aż będą wolne elementy na liście

zwolnij (rekord r)
dekrementuj licznik referencji na r
if (licznik referencji wynosi 0)
wstaw r na koniec listy wolnych elementów

Przy pobieraniu rekordów usuwanie z listy i zliczanie referencji służy
oczywiście temu, żeby zbuforowany rekord, z którego klient akurat
korzysta, nie został w tym czasie nadpisany.

Co się w takim cache dzieje, jeśli kliencki algorytm pobiera rekordy z
cache, ale w niektórych sytuacjach "zapomina" zawołać procedurę
"zwolnij"? Otóż taki rekord pozostaje w cache po tym jak klient
przestanie z niego korzystać, kolejne próby czytania rekordu pod tym
samym kluczem odnoszą sukces (bo ten cachee pozwala wielu klientom na
raz czytać ten sam rekord), ale nigdy już nie trafia z powrotem na listę
wolnych elementów. W konsekwencji im dłużej cache będzie działał, tym
wolnych elementów na liście będzie mniej, a sam cache będzie coraz mniej
efektywny, aż w końcu wszyscy klienci próbujący pobrać kolejny rekord
zawisną czekając w nieskończoność na zaistnienie elementu na liście
wolnych, co nigdy nie nastąpi.

Jak nazwiesz taką sytuację, jeśli nie wyciekiem?