Особый случай производителя / потребителя

Question

Я пытаюсь синхронизировать особую проблему производителя / потребителя.Это проблема:

У меня есть 2 очереди link_queue, page_queue.

Thread class ProducePages_RequireLinks (назовите это class A), как следует из названия, потребляет элементы из link_queue ипомещает произвольное количество (> = 1) страниц из каждой ссылки в page_queue.

Наоборот, основной поток class ProduceLinks_RequirePages (назовите его class B) потребляет страницы из page_queue и ставит в очередьпроизвольное количество (> = 0) ссылок в link_queue.

Теперь возможно, что class B генерирует ссылки быстрее, чем class A генерирует страницы.С другой стороны, возможно и обратное.

Как правильно синхронизировать эти потоки в Ruby 1.9.2?

Я пыталсяиспользовать мониторы в обоих, но в какой-то момент я получаю взаимоблокировки.

(Если я не смог быть точным, сообщите мне через комментарии, и я отправлю несколько примеров классов)

---

РЕДАКТИРОВАТЬ: Изображение того, что происходит:

Примеры

link_queue инициализируется с 1 элемента page_queue инициализируетсяс 0 элементами

У нас есть 4 темы class A и 1 тема class B.Каждая строка будет иметь 1 шаг.

---

Темы A.1 получают 1 ссылку (linkQ = 0), выводят 1 страницу (pageQ = 1)

Тема B захватывает 1 страницу (pageQ =0) выводит 400 ссылок (linkQ = 400)

Тема A.3 захватывает 1 ссылку (linkQ = 399) выводит 1 страницу (pageQ = 1)

Тема A.2 захватывает 1 ссылку (linkQ = 398) выводит 1 страницу (pageQ = 2)

Тема B захватывает 1 страницу (pageQ = 1) выводит 100 ссылок (linkQ = 498)

Тема A.1 захватывает 1 ссылку (linkQ = 497) выводит 1 страницу (pageQ = 2)

Тема A.4 захватывает 1 ссылку (linkQ = 496) выводит 1 страницу (pageQ = 3)

Тема B замечает, что linkQ являетсяслишком велик и ждет, пока ссылка Q <16 </p>

.,,Темы А. * продолжить работу.,,потом (linkQ = 15) и (pageQ = 484)

А теперь у нас противоположная проблема.Теперь потоки A должны ждать, пока pageQ опустится ниже определенного порога.В противном случае у нас закончится память в какой-то момент.

cheers

Answer 1

Независимо от того, используете ли вы Ruby или любой другой язык, всякий раз, когда у вас есть дизайн производителя-потребителя, который вы здесь описываете, независимо от того, являются ли производители и потребители потоками или процессами, вы должны Никогда не предполагайте, что потребители смогут «идти в ногу» с производителями. Вы должны всегда использовать ограниченные очереди. Даже использование внешних очередей, как вы упомянули в своем комментарии, не решает проблему в общем случае, поскольку внешнее хранилище, хотя и намного больше, чем ОЗУ, не бесконечно.

Стандартная библиотека Ruby имеет SizedQueue, которую вы получаете с require 'thread'. SizedQueue - потокобезопасная очередь, размер которой ограничен. Если поток производителя пытается вставить элемент в очередь, когда он уже заполнен, производитель будет блокироваться, пока потребитель не вытолкнет элемент из очереди (освободив место для нового). Это даст потребителям возможность «наверстать упущенное». Аналогичным образом, если поток потребителя пытается извлечь элемент из очереди, когда он пуст, потребитель заблокирует его, пока элемент не станет доступен.

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

Answer 2

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

Если вы создаете описанную вами систему поиска, вы попытаетесь перечислить каждую страницу в Интернете, и никакая синхронизация потоков не поможет вам поместить ее в ОЗУ.

Как насчет петель? страница ссылки на страницы b и c, страница b ссылки на страницы a и c и т. д.? Как вы описали свою проблему, каждая итерация будет расти в геометрической прогрессии. Если есть конечное число страниц, которые вы хотите обработать, то насколько оно велико? Если вы перебираете некоторый набор страниц снова и снова, следует ли вам пропускать страницы на основании того, что они были обработаны достаточно недавно?

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

Или, в качестве альтернативы, что вы пытаетесь сделать? Другой подход может быть более подходящим.