Проблем

Управо сам суочен са интересантним проблемом који још увек не знам да решим. Ради се о седећем:

Имам блок меморије, унутар њега елементе са заглављем и слободним простором. Уколико је задато поравнање поинтера, треба да нађем поинтер у једном од слободних простора који је поравнан на дату вредност. Другим речима, уколико имам поинтер p, и величину елемента (заглавље + слободни простор), да ли је могуће доказати да постоји такав цели број N за који ће следећа једначина да важи:

p + N * dist = M * alignment

где су
p - поинтер на први слободни простор блока
N - произвољни цели број
dist - величина елемента (заглавље + слободни простор)
M - произвољни цели број
alignment - поравнање, мора бити 2 на целобројни експонент.


----

После мало размишљања, математика би могла да буде ово:

Формулу поделим са alignment:

p / alignment + N * dist / alignment = M

Резултат дељења би могао бити:

P + Mp / alignment + N * dist / alignment = M

С обзиром да доказујем само да ли постоје такви целобројни N и M, није битно која је њихова вредност, па онда целобројну вредност P стапам са M i dobijam neki novi celobrojni broj R.

Mp / alignment + N * dist / alignment = R

Да би горња једначина била задовољена, рационални број треба да нестане, а то може само ако:

N * dist = alignment - Mp

односно

N = (alignment - Mp) / dist

Дакле уколико је остатак овог дељења 0, такви бројеви постоје:

if (mod((alignment - mod(p / alignment))/dist) == 0) -> Da
else -> NE


----
После пуно размишљања, и дискусије са Страхињом, мој закључак је да таква општа формула не постоји. На крају сам променио алгоритам за испитивање подобности датог блока и сада је овакав.

Ако су сви следећи услови испуњени, блок је подобан:

1. Све корисничке алокације унутар блока су поравнате на 2^k адресе (другим речима, првa корисничка адреса унутар блока је 2^k)
2. Тражено поравање је такође 2^k
3. Величина алокационог елемнта (кориснички простор + контролна структура) мора бити такође 2^k
4. Тражено поравање мора бити мање или једнако величини алокационог елемента.

Тако се алокација врши само ако су задовољени горе наведени услови, а све остало се одбацује и алокација се врши од општег "list allocator".