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ć?
Dodatkowo potrzebne jeszcze mutexy, aby nie przydzielić dwa razy tego
samego numeru przy pracy na wątkach.
Jaka struktura i algorytm wydajnie wyszuka wolny numer?