Как в линуксе ищется свободная память

легко.
физически есть 128 страницы памяти по 4 кб. Дальше первой цифрой обозначается физический адрес (номера страниц для упрощения), а второй виртуальный (тоже номера).

делаем malloc(16k) три раза. тебе возравщается виртуальный адрес 1, 5 и 9. В ядрёной таблице страниц для процеса имеем

1 1 первые 16 кб
2 2
3 3
4 4
5 5 вторые 16 кб
6 6
7 7
8 8
9 9 трети 16 кб
10 10
11 11
12 12

1 1 
2 2
3 3
4 4
0 5 вирт. ад. с 5 по 8 указывает на nullpage (segfault при обращении)
0 6
0 7
0 8
9 9
10 10
11 11
12 12

1 1 первая 16 кб
2 2
3 3
4 4
0 5 виртуальные адреса с 5 по 8 никуда не указывают
0 6
0 7
0 8
9 9 третья 16 кб
10 10
11 11
12 12
5 13 твои 17 кб с хвостиком.
6 14
7 15
8 16
13 17

А теперь откойте пожалуйста глаза и увидите, что заняты физические страницы от 1ой до 13й последовательно. Где фрагментация?

> теперь ты освобождаешь второй блок, т.е. виртуальные адрес с 5 по 8 включительно

А теперь откойте пожалуйста глаза и увидите, что заняты физические страницы от 1ой до 13й последовательно.

/0

а теперь внимание вопрос: вы физические и виртуальные адраса различаете?

Я — различаю. А вы?

Фрагментация же состоит в том, что у тебя в адресном пространстве процесса может быть распределено всего 1 гиг из 3-х, но при этом ты оставшиеся 2 гига не сможешь выделить никак одним куском приложению, потому что свободные диапазоны адресов будут нарезаны мелкими ломтиками.

Впрочем, не заметил слова физические в цитате. Ок. Но про них речь и не шла в треде, насколько я понимаю. Физически память можно стругать постранично как угодно.

Но ведь на практике после free() glibc не стучит ядро, значит не делает этого. На практике оно при первом malloc() забирает чуть больше 128 кбайт с помощью brk, а отдаёт только в самом конце.

Мне тоже самое сказал товарищь, не помню с кем я тогда вёл дискуссию, что, мол, я выдилил много-много страниц, а потом освободил по пол страницы. И тогда вроде память есть, но выделить её одним куском не получится. Я с ним согласен, и с вам тоже. Но дальше этот товарищь сам признался, что пример, который он привёл, на столько гипотетичен, что он и сам начал сомневаться в актуальностит этой проблемы.

Итого:

Дефрагментация физических адресов отсутсвует как явление.
Дефрагментация виртуальных адресов хоть и присутствует, но только в настолько изощрённых примерах, что фантазии позавидует любой писатель фантаст-антиутопист.

На чём я тред заканчиваю, ибо хочу домой.

s/товарищь/добрый_человек/

О, ситуация прояснилась ;) Проблема в том, что настругивание памяти - дорогущая операция. Поэтому есть всякие стратегии как сделать так, чтобы она не запускалась когда не надо. Например, выделяя вдвое больше, чем нужно. Вот это я и предлагал обсудить ;)

> Проблема в том, что настругивание памяти - дорогущая операция.

Какое именно, в каком алгоритме? Моя опять ваша не понимать.

> Какое именно, в каком алгоритме? Моя опять ваша не понимать.

настругивается ведь только когда память закончилась, ну. Повлиять напрямую на процесс настругивания мы не можем, но можем намякивать. Например, выделив под задачу заранее нужное количество памяти с умом. А если вдруг не хватит, то выделять новое количество тоже с умом, чтобы не дай бог чего не то.
А с тем куском какой есть, вытворять разные непотребства, например, выбрать подходящий алгоритм, который будет в него ужиматься. Или поверх написать еще один уровень абстракции от памяти и просить память уже у собственного планировщика (не обязательно сборщика мусора, просто еще более умного). К этому можно еще вспомнить про скорость линейного копирования и прочую муть.

> А с тем куском какой есть, вытворять разные непотребства, например, выбрать подходящий алгоритм, который будет в него ужиматься.

Если нет возможности выполнять дефрагментацию (т.е. нет возможности найти и справить все указатели или смещения, которые зависят от адресов перемещаемых кусков), то есть только один способ ужаться — стек.