В C/C++ я могу выделить память в одном потоке и удалить ее в другом потоке. Тем не менее всякий раз, когда кто-то запрашивает память из кучи, распределителю кучи необходимо пройтись по куче, чтобы найти свободную область подходящего размера. Как два потока могут эффективно обращаться к одной и той же куче без повреждения кучи? (Это делается путем блокировки кучи?)
Многопоточное управление кучей
comment
С измененным тегом, так как это действительно не имеет ничего общего с каким-либо конкретным языком программирования.
- person T.E.D. schedule 29.01.2010
comment
Не совсем верно. ОС задействована только при увеличении кучи (что включает подкачку новых страниц памяти). Фактически управление кучей зависит от реализации malloc/new на C/C++.
- person doron schedule 29.01.2010
Ответы (6)
В общем, вам не нужно беспокоиться о потокобезопасности вашего распределителя памяти. Все стандартные распределители памяти, то есть поставляемые с MacOS, Windows, Linux и т. д., являются потокобезопасными. Блокировки — это стандартный способ обеспечения потокобезопасности, хотя можно написать распределитель памяти, который использует только атомарные операции, а не блокировки.
Теперь совершенно другой вопрос, масштабируются эти распределители памяти; то есть их производительность не зависит от количества потоков, выполняющих операции с памятью? В большинстве случаев ответ отрицательный; они либо замедляют работу, либо потребляют намного больше памяти. Первым масштабируемым распределителем памяти в обоих измерениях (скорости и пространства) является Hoard (который Я написал); аллокатор Mac OS X вдохновлен им — и цитирует его в документации — но Hoard работает быстрее. Есть и другие, включая tcmalloc от Google.
person
EmeryBerger
schedule
09.01.2011
Можете ли вы предоставить некоторую информацию об общей стратегии, используемой Хоардом?
- person doron; 10.01.2011
Память управляется блоками, называемыми суперблоками, которые содержат объекты одинакового размера. Каждый поток получает некоторое их количество (локальное для потока), что означает отсутствие блокировок или состязаний. Потоки мультиплексируются в кучи для каждого процессора, которые содержат суперблоки. Выделение из суперблока выполняется только одним потоком за раз, что ограничивает ложное совместное использование. Hoard ограничивает потребление памяти, перемещая практически пустые суперблоки в общую кучу по мере того, как кучи для каждого ЦП становятся пустыми, что ограничивает конкуренцию и обеспечивает асимптотически оптимальное потребление памяти. См. cs.umass.edu/~emery/hoard/asplos2000.pdf.
- person EmeryBerger; 10.01.2011
Да, «обычная» реализация кучи, поддерживающая многопоточный код, обязательно будет включать какую-то блокировку для обеспечения правильной работы. В довольно экстремальных условиях (много активности кучи) это может стать узким местом; доступны более специализированные кучи (обычно предоставляющие некую локальную куче потока), которые могут помочь в этой ситуации. Я использовал Intel TBB "масштабируемый распределитель" на хороший эффект. tcmalloc и jemalloc — другие примеры malloc, реализованные с учетом многопоточного масштабирования.
Некоторое сравнение времени между однопоточными и многопотоковыми malloc здесь.
person
timday
schedule
28.01.2010
Просто из интереса, каковы стратегии malloc для gcc и MSVC?
- person doron; 31.01.2010
Хороший вопрос. Не много знаю о CRT MSVC, но gcc обычно ассоциируется с glibc, который использует ptmalloc: en.wikipedia.org/wiki/Malloc#dlmalloc_.28the_glibc_allocator.29 . Приведенная выше ссылка на тайминги довольно хорошо показывает это масштабирование, что объясняет, почему мои собственные эксперименты с аллокатором TBB иногда улучшают ситуацию, а иногда ухудшают.
- person timday; 01.02.2010
@doron В Windows Vista и новее используется куча с низкой фрагментацией, что предположительно позволяет стандартному malloc хорошо работать в многопоточных программах.
- person ; 06.07.2012
Это вопрос об операционных системах, поэтому ответ будет зависеть от ОС.
В Windows каждый процесс получает свою собственную кучу. Это означает, что несколько потоков в одном процессе (по умолчанию) совместно используют кучу. Таким образом, ОС должна синхронизировать потоки своих вызовов выделения и освобождения, чтобы предотвратить повреждение кучи. Если вам не нравится идея возможного конфликта, который может возникнуть, вы можете обойти его с помощью Подпрограммы Heap*. Вы даже можете перегрузить malloc (в C) и new (в C++) для их вызова.
person
T.E.D.
schedule
28.01.2010
Я нашел эту ссылку.
В принципе, кучу можно разделить на арены. При запросе памяти каждая арена по очереди проверяется, не заблокирована ли она. Это означает, что разные потоки могут одновременно безопасно обращаться к разным частям кучи. С бесплатными немного сложнее, потому что каждый бесплатный должен быть освобожден с той арены, из которой он был выделен. Я предполагаю, что хорошая реализация заставит разные потоки по умолчанию использовать разные арены, чтобы попытаться минимизировать конкуренцию.
person
doron
schedule
29.01.2010
Да, обычно доступ к куче должен быть заблокирован. Каждый раз, когда у вас есть общий ресурс, этот ресурс необходимо защищать; память - это ресурс.
person
GManNickG
schedule
28.01.2010
Даже когда каждый поток управляет своей собственной памятью? Это звучит ужасно неэффективно.
- person doron; 29.01.2010
@deus: Нет, но это не та ситуация, которую вы описали. Вы сказали, что потоки разделяют память. (удаление в другой теме).
- person GManNickG; 29.01.2010
Это будет сильно зависеть от вашей платформы/ОС, но я считаю, что в большинстве систем это нормально. C/C++ не определяет потоки, поэтому по умолчанию я считаю, что ответ "куча не защищена", что у вас должна быть какая-то многопоточная защита для доступа к куче.
Однако, по крайней мере, с linux и gcc, я считаю, что включение -pthread автоматически даст вам эту защиту...
Кроме того, вот еще один связанный с этим вопрос:
Безопасность потоков нового оператора C++ в Linux и gcc 4
person
Matthew Eshleman
schedule
28.01.2010
