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?

do góry

Do trzymania informacji o zajetych numerach (zasobach) nie potrzeba zadnej listy -
wystarczy int lub long int. Kazdy bit identyfikuje zajety zasob. Binarne sprawdzanie
zajetosci bitu. Jesli system ma bardzo malo pamieci trzeba sobie jakos radzic - lista
zjadla by cale zasoby ;-)

Do wyszukiwania wolnego miejsca - wyszukiwanie polowkowe i rolowanie bitow w prawo
lub lewo jak kto woli ;-)

On Friday, December 4, 2015 at 9:04:17 AM UTC-5, 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ć?
> 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?

do góry

W dniu 2015-12-04 o 15:04, Borneq pisze:
> Jaka struktura i algorytm wydajnie wyszuka wolny numer?

Nasuwa się struktura bitowa, choć dużo numerów, to tylko po bicie na
jeden. Gdy dużo wolnego, to szybko znajdzie wolne, gdy prawie cała
zajęta będzie musiał przeszukiwać tablicę aby znaleźć zero.
Może to zależeć od aktualnej liczy użytych:
- gdy mało użytych - wtedy lista użytych
- gdy dużo,ale mniej niż np. połowa - tablica bitowo
- gdy więcej niż połowa - lista wolnych

do góry

Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym unsigned int
lub unsigned long - to jest standardowe rozwiazanie np przy programowaniu MCUs
Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16, 8, 4
i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow i 4 rolowania
przy 64 bit long.

On Friday, December 4, 2015 at 9:19:18 AM UTC-5, Borneq wrote:
> W dniu 2015-12-04 o 15:04, Borneq pisze:
> > Jaka struktura i algorytm wydajnie wyszuka wolny numer?
>
> Nasuwa się struktura bitowa, choć dużo numerów, to tylko po bicie na
> jeden. Gdy dużo wolnego, to szybko znajdzie wolne, gdy prawie cała
> zajęta będzie musiał przeszukiwać tablicę aby znaleźć zero.
> Może to zależeć od aktualnej liczy użytych:
> - gdy mało użytych - wtedy lista użytych
> - gdy dużo,ale mniej niż np. połowa - tablica bitowo
> - gdy więcej niż połowa - lista wolnych

do góry

W dniu 2015-12-04 o 15:51, Adam M pisze:
> Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym unsigned
int lub unsigned long - to jest standardowe rozwiazanie np przy programowaniu MCUs
> Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16, 8,
4 i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow i 4 rolowania
przy 64 bit long.

Jak wykonywać te podziały? zwykle przy połowie słowa liczy się tylko to
młodsze.
czy będzie to tak a wewnątrz procedura inline szukaj_przesuwajac
używająca << maksymalnie 4 razy?
uint32_t mask
if(mask)
{
if (mask & 0x0000ffff) //16 młodszych
{
if (mask & 0x000000ff) //8 najmłodszych
{
if (mask & 0x0000000f) szukaj_przesuwajac
else szukaj_przesuwajac
}
else
{
if (mask & 0x00000f00) szukaj_przesuwajac
else szukaj_przesuwajac
}
}
else
{
if (mask & 0x00ff0000) //8 najmłodszych
{
if (mask & 0x000f0000) szukaj_przesuwajac
else szukaj_przesuwajac
}
else
{
if (mask & 0x0f000000) szukaj_przesuwajac
else szukaj_przesuwajac
}
}
}

do góry

On Friday, December 4, 2015 at 3:04:17 PM UTC+1, Borneq wrote:
> Dodatkowo potrzebne jeszcze mutexy, aby nie przydzielić dwa razy tego
> samego numeru przy pracy na wątkach.
Nie bardzo mam czas, podpowiem tylko, że nie są konieczne do tego
muteksy.

do góry

Najlepsze rozwiązanie tego problemu z jakim się spotkałem to pamiętanie największego
dotąd przyznanego numeru i posortowanej listy zwolnionych numerów.

AdamK

do góry

On Friday, December 4, 2015 at 5:31:48 PM UTC+1, Adam Klobukowski wrote:
> Najlepsze rozwiązanie tego problemu z jakim się spotkałem to pamiętanie
największego dotąd przyznanego numeru i posortowanej listy zwolnionych numerów.
>
> AdamK

Nie wierzę że nie spotkałeś się z lepszym :)

do góry

On Friday, December 4, 2015 at 11:31:48 AM UTC-5, Adam Klobukowski wrote:
> Najlepsze rozwiązanie tego problemu z jakim się spotkałem to pamiętanie
największego dotąd przyznanego numeru i posortowanej listy zwolnionych numerów.
>
> AdamK

Po pierwsze przepraszam za uzywanie angielskich zwrotow ale w pracy od kilkunastu lat
uzywam wylacznie jezyka angielskiego wiec nie znam polskich odpowiednikow niektorych
zwrotow.

Twoj pomysl bedzie dzialal dobrze tylko w systemie w ktorym task churn (duzo zadan
jest uruchamainych i szybko zamykanych w losowych odstepach czasu) jest niewielki i
nie wystepuje tzw. task attack lub inaczej task ramp-up effect (bardzo duzo zadan
jest uruchamianych bardzo szybko po sobie przy niewielkiej ilosci zadan zwalnianych -
stosunek zadan uruchamainych do zwalnianych jest bardzo niekorzystny)

do góry

On Friday, December 4, 2015 at 10:17:02 AM UTC-5, Borneq wrote:
> W dniu 2015-12-04 o 15:51, Adam M pisze:
> > Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym unsigned
int lub unsigned long - to jest standardowe rozwiazanie np przy programowaniu MCUs
> > Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16,
8, 4 i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow i 4
rolowania przy 64 bit long.
>
> Jak wykonywać te podziały? zwykle przy połowie słowa liczy się tylko to
> młodsze.
> czy będzie to tak a wewnątrz procedura inline szukaj_przesuwajac
> używająca << maksymalnie 4 razy?
> uint32_t mask
> if(mask)
> {
> if (mask & 0x0000ffff) //16 młodszych
> {
> if (mask & 0x000000ff) //8 najmłodszych
> {
> if (mask & 0x0000000f) szukaj_przesuwajac
> else szukaj_przesuwajac
> }
> else
> {
> if (mask & 0x00000f00) szukaj_przesuwajac
> else szukaj_przesuwajac
> }
> }
> else
> {
> if (mask & 0x00ff0000) //8 najmłodszych
> {
> if (mask & 0x000f0000) szukaj_przesuwajac
> else szukaj_przesuwajac
> }
> else
> {
> if (mask & 0x0f000000) szukaj_przesuwajac
> else szukaj_przesuwajac
> }
> }
> }

Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to mam byc
implementowane - czy to tylko teoretyczne dewagacje - za wyjatkiem duzych
web-serwerow i baz danych obslugujacych bardzo duze firmy (w tym przypadku sa dobrze
znane rozwiazania jak radzic sobie z problemem) ciezko mi wyobrazic sobie system
ktory uruchamia miliony watkow - nie mowiac juz o milionach zadan.

do góry