Есть ли способ, которым эта проблема могла бы выиграть от решения с несколькими потоками, а не с одним потоком?
В одном из интервью мне было предложено решить проблему, используя несколько потоков. Мне кажется, что несколько потоков не приносит никакой пользы.
Вот проблема:
Вам дан абзац, содержащий n слов, вам дано m тем. То, что вам нужно сделать, это то, что каждый поток должен напечатать одно слово и передать управление следующему потоку, таким образом, каждый поток будет продолжать печатать одно слово, в случае, если последний поток придет, он должен вызвать первый поток. Печать будет повторяться, пока все слова не будут напечатаны в абзаце. Наконец все потоки должны выходить изящно. Какой тип синхронизации будет использовать?
Я твердо убежден, что мы не можем использовать какие-либо темы здесь, но полагаю, что интервьюер пытается измерить мои навыки синхронизации. Я что-то упустил в этой проблеме, что сделало бы несколько потоков иметь значение?
Не нужно кода, просто подумайте. Я буду реализовывать самостоятельно.
Ответы:
Мне кажется, что они ведут вас к семафорному решению. Семафоры используются для обозначения другого потока, что это их очередь. Они используются гораздо реже, чем мьютексы, и я думаю, поэтому они считают, что это хороший вопрос для интервью. Это также, почему пример кажется надуманным.
По сути, вы бы создали
m
семафоры. Каждый потокx
ожидает семафора, аx
затем отправляет его в семафорx+1
после выполнения своей задачи. В псевдокоде:источник
На мой взгляд, это невероятный вопрос для собеседования - по крайней мере, предполагая, что (1) кандидат должен иметь глубокие знания о потоках, и (2) интервьюер также обладает глубокими знаниями и использует этот вопрос для проверки кандидата. Всегда возможно, что интервьюер искал конкретный, узкий ответ, но компетентный интервьюер должен искать следующее:
Последний пункт, на мой взгляд, самый важный. Опять же, исходя из моего опыта, становится значительно сложнее отлаживать многопоточный код, если многопоточность смешана с логикой приложения (просто посмотрите на все вопросы о Swing в SO для примеров). Я считаю, что лучший многопоточный код написан как автономный однопоточный код с четко определенными передачами.
Имея это в виду, мой подход должен дать каждому потоку две очереди: одну для ввода, одну для вывода. Поток блокируется при чтении входной очереди, забирает первое слово из строки и передает остаток строки в свою выходную очередь. Некоторые из особенностей этого подхода:
Тем не менее, есть еще много серых областей, которые компетентный интервьюер может исследовать:
Наконец, если у вас есть опыт параллельного программирования, вы можете поговорить о некоторых фреймворках (например, Akka для Java / Scala), которые уже следуют этой модели.
источник
Вопросы на собеседовании иногда представляют собой хитрые вопросы, призванные заставить вас задуматься о проблеме, которую вы пытаетесь решить. Задание вопросов по вопросу является неотъемлемой частью подхода к любой проблеме, будь то в реальном мире или на собеседовании. В Интернете есть несколько видеороликов о том, как подходить к вопросам в технических интервью (особенно обратите внимание на Google и, возможно, Microsoft).
Приближение к собеседованиям с таким образцом мышления приведет вас к взрыву любого интервью для любой компании, на которую стоит работать.
Если вы не думаете, что вы многого выиграете (если что-нибудь из потоков), скажите им об этом. Скажите им, почему вы не думаете, что есть какая-то выгода. Поговорите с ними. Технические интервью предназначены для открытой дискуссионной площадки. Вы можете узнать что-то о том, как это может быть полезно. Не просто слепо продвигайтесь вперед, пытаясь реализовать то, что сказал вам ваш интервьюер.
источник
Сначала токенизируйте абзац с соответствующими разделителями и добавьте слова в очередь.
Создайте N потоков и сохраните их в пуле потоков.
Переберите пул потоков, запустите поток и дождитесь
его присоединения. И начните следующий поток, как только закончится первый, и так далее.
Каждый поток должен просто опросить очередь и распечатать ее.
Как только все потоки используются в пуле потоков, начните с начала пула.
источник
Как вы сказали, я не думаю, что этот сценарий сильно выигрывает, если вообще использует многопоточность. Скорее всего, это медленнее, чем однопоточная реализация.
Тем не менее, мой ответ будет состоять в том, чтобы каждый поток в узком цикле пытался получить доступ к блокировке, которая контролирует доступ к индексу массива слов. Каждый поток захватывает блокировку, получает индекс, получает соответствующее слово из массива, печатает его, увеличивает индекс и снимает блокировку. Потоки завершаются, когда индекс находится в конце массива.
Что-то вроде этого:
Я думаю, что это должно обеспечить выполнение одного потока за другим, но порядок потоков не гарантируется. Мне любопытно услышать и другие решения.
источник
Используйте API-интерфейсы ожидания / сигнала для решения этой проблемы.
Допустим, первый поток выбирает 1 слово, а остальные отдыхают, все потоки ожидают сигнала. 1-й поток печатает 1-е слово и генерирует сигнал в следующий поток, а затем 2-й поток печатает второе слово и генерирует сигнал в 3-й поток и так далее.
источник
[Используемые здесь термины могут быть специфическими для потоков POSIX]
Должна быть возможность использовать мьютекс FIFO, чтобы решить эту проблему.
Где использовать:
Предположим, два потока T1 и T2 пытаются выполнить критический раздел. Обе не имеют ничего общего за пределами этой критической секции и удерживают замки в течение достаточного времени. Таким образом, T1 может блокировать, выполнять и разблокировать и сигнализировать T2 для активации. Но прежде чем T2 сможет пробудиться и получить блокировку, T1 повторно запрашивает блокировку и выполнение. Таким образом, T2, возможно, придется ждать очень долго, прежде чем он действительно получит блокировку или может не быть.
Как это работает / Как реализовать:
Есть мьютекс, чтобы заблокировать. Инициализируйте специфичные для потока данные (TSD) для каждого потока для узла, содержащего идентификатор потока и семафор. Кроме того, есть две переменные - собственные (ИСТИНА или ЛОЖЬ или -1), владелец (идентификатор потока владельца). Кроме того, сохраните очередь официантов и указатель waiterLast, указывающий на последний узел в очереди официантов.
операция блокировки:
операция разблокировки:
источник
Интересный вопрос. Вот мое решение в Java, использующее SynchronousQueue для создания канала рандеву между потоками:
источник
Я бы сказал, что на этот вопрос очень сложно ответить, потому что он просит лучшего способа сделать что-то совершенно глупое. Мой мозг просто так не работает. Он не может найти решения для глупых вопросов. Мой мозг сразу сказал бы, что в этих условиях использование нескольких потоков бессмысленно, поэтому я бы использовал один поток.
Затем я бы попросил их задать реальный вопрос о потоке или дать реальный пример серьезной работы с потоками.
источник