C Параллельный сборщик мусора, как избежать блокировки основного потока

Question

Я занимаюсь разработкой параллельного сборщика мусора. Это три-маркировочный коллектор, который делает обычный белый-> серый-> черный. Когда коллектор перемещает объект из серого в черный, он опускается в объект, чтобы пометить дочерние объекты серым. В это время необходимо снять блокировку, чтобы предотвратить изменение объекта в основном потоке во время чтения объекта. Поскольку было бы безумным требованием к памяти дать каждому объекту независимую блокировку, у меня есть одна блокировка (для каждого потока, не относящегося к gc), которую необходимо заблокировать перед изменением объекта. GC будет использовать эту блокировку потоков перед чтением объекта.

Итак, сборщик мусора будет выполнять итерацию объектов из потока и снимать блокировку перед чтением потомков, а затем снимать блокировку перед следующей итерацией. Я хочу удостовериться, что GC не захватывает замок слишком много. Мне кажется, очевидным решением является «выход» сразу после снятия блокировки, чтобы основной поток мог продолжить работу, если он ожидает блокировки. Сборщик мусора не является приоритетным потоком, не имеет значения, много ли времени уходит на выполнение работы.

Однако я использую pthreads (linux), и когда я использую функцию sched_yield (), я обнаружил, что она считается вредной. Большинство результатов - аргумент о том, что он должен делать. Короче говоря, можно утверждать, что если вы используете sched_yield (), вы делаете что-то не так.

http://www.technovelty.org/code/c/sched_yield.html, кажется, предлагает альтернативу, но у меня возникают проблемы с пониманием ключевого момента алгоритма, или, в частности, как применить его к моим потребностям.

Answer 1

Что касается блокировки каждого объекта, я использовал один из подходов, чтобы ограничить требования к пространству, - иметь круговой массив блокировок (с большим, но управляемым количеством блокировок, например, 8096). , Затем вы помещаете некоторый арбитр перед ним, который связывает данный объект со следующей блокировкой в ​​массиве (или, если объект уже связан с блокировкой в ​​массиве, тогда арбитр переводит эту блокировку обратно в начало массива) ,

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

Или, возможно, лучшим подходом было бы, чтобы арбитр работал больше как менеджер ресурсов для пула блокировок, которые «проверяются» и «возвращаются». Затем, когда кто-то просит проверить блокировку, арбитр может немедленно выдать ее, если она доступна в пуле (или уже извлечена для того же экземпляра объекта), или в противном случае он должен блокировать, пока какой-то другой поток не проверит блокировку обратно. дюймы

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