Подтвердить что ты не робот

Является ли распределение памяти в linux неблокируемым?

Мне любопытно узнать, является ли выделение памяти новым оператором по умолчанию неблокирующей операцией.

например.

struct Node {
    int a,b;
};

...

Node foo = new Node();

Если несколько потоков пытались создать новый Node, и если один из них был приостановлен ОС в середине распределения, заблокировал ли он другие потоки?

Причина, по которой я спрашиваю, заключается в том, что у меня была параллельная структура данных, которая создавала новые узлы. Затем я модифицировал алгоритм для повторного использования узлов. Производительность обоих алгоритмов была практически одинаковой на 24-ядерной машине. Тем не менее, я тогда создал программу вмешательства, которая выполнялась на всех ядрах системы, чтобы создать как можно больше предустановок ОС. Производительность алгоритма, создавшего новые узлы, снизилась в 5 раз по сравнению с алгоритмом, который перерабатывал узлы.

Мне любопытно узнать, почему это произошло.

Спасибо.

* Edit: указывать на код для дистрибутора памяти С++ для linux также было бы полезно. Я попытался посмотреть, прежде чем публиковать этот вопрос, но не смог найти его.

4b9b3361

ОТВЕТЫ

Ответ 1

мне кажется, если ваше приложение вмешательства использовало новый /delete (malloc/free), тогда приложение с помехами больше помешало бы тестированию без повторного использования. Но я не знаю, как выполняется ваш тест на интерференцию.

В зависимости от того, как вы перерабатываете (т.е. если вы запретите использование муфтексов pthread), ваш код рециркуляции может быть медленным (gcc atom ops будет быстрее на 40 раз при реализации утилизации).

Malloc, в некоторых вариантах в течение длительного времени, по крайней мере на некоторых платформах, знал о потоках. Используйте ключи компилятора на gcc, чтобы убедиться, что вы их получите. Новые алгоритмы поддерживают пулы небольших фрагментов памяти для каждого потока, поэтому нет или мало блокировки, если в вашем потоке имеется небольшой элемент. Я упростил это, и это зависит от того, какой malloc использует ваша система. Кроме того, если вы идете и выделяете миллионы предметов для проведения теста... ну тогда вы не увидите этого эффекта, потому что небольшие пулы элементов ограничены по размеру. Или, может быть, вы это сделаете. Я не знаю. Если вы освободили элемент сразу после выделения, вы, скорее всего, его увидите. Освобожденные мелкие предметы возвращаются в списки мелких предметов, а не в общую кучу. Хотя "то, что происходит, когда поток B освобождает элемент, выделенный потоком A", является проблемой, которая может быть или не быть рассмотрена в вашей версии malloc и не может рассматриваться без блокировки. Конечно, если вы не сразу освобождались во время большого теста, тогда поток должен был бы пополнять свой маленький список предметов много раз. Это может блокироваться, если пытается попробовать несколько потоков. Наконец, в какой-то момент ваша куча процесса будет запрашивать систему памяти кучи, которая, очевидно, может блокироваться.

Так вы используете небольшие элементы памяти? Для вашего malloc я не знаю, что бы это было мало, но если вы - 1k, что точно мало. Вы выделяете и освобождаете один за другим или выделяете тысячи узлов, а затем освобождаете тысячи узлов? Было ли ваше приложение для размещения приложений? Все это повлияет на результаты.

Как перерабатывать с атомарными ops (CAS = сравнивать и свопировать):

Сначала добавьте pNextFreeNode к вашему объекту node. Я использовал void *, вы можете использовать свой тип. Этот код предназначен для 32-битных указателей, но также работает и для 64-разрядных. Затем сделайте глобальную корзину.

void *_pRecycleHead; // global head of recycle list.

Добавить в корзину:

void *Old;
while (1) { // concurrency loop
  Old = _pRecycleHead;  // copy the state of the world. We operate on the copy
  pFreedNode->pNextFreeNode = Old; // chain the new node to the current head of recycled items
  if (CAS(&_pRecycleHead, Old, pFreedNode))  // switch head of recycled items to new node
    break; // success
}

удалить из кучи:

void *Old;
while (Old = _pRecycleHead) { // concurrency loop, only look for recycled items if the head aint null
  if (CAS(&_pRecycleHead, Old, Old->pNextFreeNode))  // switch head to head->next.
    break; // success
}
pNodeYoucanUseNow = Old;

Использование CAS означает, что операция будет успешной только в том случае, если элемент, который вы изменяете, - это старое значение, которое вы передаете. Если в нем есть гонка и другой поток, то старое значение будет отличаться. В реальной жизни эта гонка происходит очень редко. CAS только слабее медленнее, чем на самом деле, устанавливая значение, сравнимое с мьютексами.... он качается.

Удаление из кучи выше, имеет условие гонки, если вы быстро добавляете и удаляете один и тот же элемент. Мы решаем это, добавляя версию # к данным CAS'able. Если вы делаете версию # одновременно с указателем на голову переработанной кучи, вы выигрываете. Используйте союз. Не стоит ничего лишнего на 64 бит CAS.

union TRecycle {
  struct {
    int iVersion;
    void *pRecycleHead;
  } ;  // we can set these.  Note, i didn't name this struct.  You may have to if you want ANSI
  unsigned long long n64;  // we cas this
}

Примечание. Вам потребуется перейти к 128-битной структуре для 64-разрядной ОС. поэтому глобальная рециркуляция выглядит следующим образом:

TRecycle _RecycleHead;

Добавить в корзину:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  pFreedNode->pNextFreeNode = Old.pRecycleHead;  // link item to be recycled into recycle pile
  New.pRecycleHead = pFreedNode;  // make the new state
  New.iVersion++;  // adding item to list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // now if version changed...we fail
    break; // success
}

удалить из кучи:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  New.pRecycleHead = New.pRecycledHead.pNextFreeNode;  // new will skip over first item in recycle list so we can have that item.
  New.iVersion++;  // taking an item off the list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // we fail if version is different.
    break; // success
}
pNodeYouCanUseNow = Old.pRecycledHead;

Бьюсь об заклад, если вы переработаете этот путь, вы увидите увеличение уровня.

Ответ 2

В многопоточных системах malloc() и free() (и new/delete) обычно используют примитивы синхронизации, чтобы сделать их безопасными для вызова из нескольких потоков.

Эта синхронизация также влияет на производительность некоторых приложений, в частности, приложений, которые выполняют много распределения и освобождения в сильно параллельных средах. Более эффективные многопоточные распределители памяти являются активным полем исследований - см. jemalloc и tcmalloc для двух хорошо известных.

Ответ 3

Это действительно почти то же самое, что этот вопрос.

В принципе, malloc не определен как потокобезопасный, но разработчики могут добавлять реализацию, чтобы сделать его потокобезопасным. Из вашего описания это похоже на вашу конкретную версию.

Конечно, по словам Оби-Вана, "Используйте Источник, Люк". Источник malloc будет вокруг, и это обычно довольно просто читать.

@Mark, вы можете получить стандартный источник GNU libc на

$ git clone git://sourceware.org/git/glibc.git
$ cd glibc
$ git checkout --track -b glibc-2_11-branch origin/release/2.11/master

См. также здесь. Помните, что malloc находится в ручном разделе 3 - это функция библиотеки, поэтому она не будет в ваших источниках ядра. Однако вам может потребоваться прочитать в brk, sbrk, getrlimit и setrlimit и т.д., Чтобы узнать, что делает ядро.

Еще одна ссылка: проект GCC.

Хорошо, еще один (я могу остановиться в любое время): здесь страница, из которой вы можете скачать источники. Отвяжите файл, и вы должны найти его на ./malloc/malloc.c.

Ответ 4

У этого вопроса есть ряд хороших ответов: В многопоточном C/С++ malloc/new блокирует кучу при распределении памяти.

Консенсус в том, что есть блокировка. Таким образом, большое выделение или тот, который требует некоторой подкачки, может блокировать меньшее выделение в другом потоке, даже если более мелкий может завершиться, если не для более крупного распределения.

gcc new является потокобезопасным, если вы компилируете с поддержкой pthreads, но это не совсем то, что вы просите.

Я знаю, что в окнах вы можете создать свою собственную кучу, которая может быть использована для настройки памяти в начале вашей программы. Я не знаю о каких-либо вызовах linux/unix, чтобы делать подобные вещи.

Ответ 5

Короткий ответ: Нет.

Один поток может находиться в середине new node(), а другой поток также может выполнять new node(). Первая нить может быть приостановлена, а вторая - первой. Это нормально. (при условии, что ничто в вашем конструкторе не использует мьютекс)

Более длинный ответ: многопоточность - это джунгли. Небезопасный код может работать нормально в течение десятилетия, а затем не работает каждый день в течение недели. Условия гонки могут не вызвать никаких проблем на вашем компьютере, но взорвать машину клиента. Многопоточные приложения представляют собой уровень неопределенности, который требует дополнительных усилий для написания и понимания.

Итак, почему эти две программы будут работать почти одинаково в один прекрасный день и будут сильно отличаться от конкуренции cpu? Я не знаю. new не блокирует другие потоки от выполнения new, так что это не так. Я подозреваю, что с дополнительными накладными расходами на новое/удаление ОС имеет больше возможностей для выгрузки вашей программы (и, возможно, даже большей вероятности для этого). Таким образом, когда нет помех, обе программы получают CPU столько, сколько они хотят, и работают нормально - но когда процессор является дефицитным ресурсом, новая/удаленная программа набирается чаще, чем переработка. Видеть? Он платит за переработку; -)