On 04.12.2015 15:04, Borneq wrote:
> Każdy zasób określony jest przez numer z zakresu <a,b), bez miany
> ogólności możemy przyjąć że zakres jest <0,n) gdzie n=b-a.
> N jest duże, np. dwa miliony, więc nie ma obaw że zabraknie zasobów, n
> to ilość ile może być zasobów JEDNOCZEŚNIE. Ale gdy zwolnimy jakiś
> zasób, jego numer może zostać przydzielony znowu.
> Choć duże n, to może się skończyć, gdy będziemy przydzielać, zwalniać i
> zwiększać k.
> Są dwie strategie: albo przydzielać zawsze najniższy wolny numer, albo
> cały czas inkrementować k, przydzielać najwyższy numer, aż gdy k
> osiągnie n, wtedy zawinie się od początku. Jak jest lepiej?
> Jaka struktura? Czy trzymać listę raczej wolnych czy raczej zajętych
> numerów? Gdy będzie mało wykorzystane, oszczędniej trzymać raczej listę
> zajętych, ale listę wolnych może lepiej szukać?


Rozumoem, że nie chodzi o obiekt w pamięci. Bo jeśli tak,
to można to zrobić jeszcze sprytniej.

Pomysł wstępny:
Stos wolnych. Gdy wątek pobiera zasób, zabier go jednocześnie
ze stosu. Gdy zwalnie, wsadza numer na samą górę.

Wszystko w czasie stałym.

Modyfikacja: kolejka fifo w cyklicznym buforze (wielkosći N+1).
Pobierasz z jednej strony, oddajesz po drugiej.

Ale nie zawsze warto, jeśli ostatnio używane zasób jest
z jakiś posobów lepszy (co siedzi w buforach) to pierwsza
wersja lepsza.


No, chyba, że zasobem są stałej wielkośći fragmenty pamięći
(obiekty po kilka(set) bajtów). Wtedy robie się to inaczej.

pzdr
bartekltg