Вопрос о многопоточном синхронизации: найдите n слов по заданным m темам

23

Есть ли способ, которым эта проблема могла бы выиграть от решения с несколькими потоками, а не с одним потоком?


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

Вот проблема:

Вам дан абзац, содержащий n слов, вам дано m тем. То, что вам нужно сделать, это то, что каждый поток должен напечатать одно слово и передать управление следующему потоку, таким образом, каждый поток будет продолжать печатать одно слово, в случае, если последний поток придет, он должен вызвать первый поток. Печать будет повторяться, пока все слова не будут напечатаны в абзаце. Наконец все потоки должны выходить изящно. Какой тип синхронизации будет использовать?

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

Не нужно кода, просто подумайте. Я буду реализовывать самостоятельно.

rplusg
источник
Добавление тега C ++, вероятно, не сильно поможет здесь. Эти вопросы здесь являются более концептуальными вещами, которые выходят за рамки любого конкретного языка.
Чао
Доверься своим чувствам. Я понимаю, к чему они стремятся, но мне никогда не нравились вопросы об интервью, которые настолько отличаются от того, как вы должны решить проблему в реальном мире.
G_P
16
@rplusg - я был бы гораздо более впечатлен интервьюером, который указал, что решение сериализует проблему и просто добавляет накладные расходы потока без фактической параллельной обработки. Интервьюер всегда может настаивать, чтобы вы ответили на вопрос в том виде, в котором его попросили
Дэвид Харкнесс
если «каждый поток должен напечатать одно слово и передать управление следующему потоку», это звучит как последовательная работа, то есть один поток ожидает завершения предыдущего, и это похоже на передачу реле. почему бы просто не сделать его однопоточным приложением в этом случае?
амфибия
1
я понял @Blrfl. вроде как мне нужно убедиться, что вы знаете, как использовать инструмент X, но слишком ленивы или неряшливы, чтобы разработать подлинный сценарий сценария использования приложения, который действительно гарантирует использование этого инструмента, поэтому я просто взял все, что было под рукой, и проколол мой пример в это небрежно. честно говоря, если бы меня об этом спросили во время интервью, я бы вызвал его на это и, вероятно, не хотел бы работать с кем-то небрежным и наполовину таким
амфибия

Ответы:

22

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

По сути, вы бы создали mсемафоры. Каждый поток xожидает семафора, а xзатем отправляет его в семафор x+1после выполнения своей задачи. В псевдокоде:

loop:
    wait(semaphore[x])
    if no more words:
        post(semaphore[(x+1) % m])
        exit
    print word
    increment current word pointer
    post(semaphore[(x+1) % m])
Карл Билефельдт
источник
Спасибо за награду. Мне потребовалось некоторое время, чтобы понять, что над ним будет сказано, кто его дал.
kdgregory
Извините за мое невежество, можете ли вы подробнее рассказать о том, как это решение является правильным? это какой-то новый модный тип семафоров? Однако я уверен, что этот вопрос решается с помощью решения ожидания / уведомления [который используют семафоры].
AJed
Это просто массив стандартных семафоров. Ничего особенного в них нет. Уведомление называется «пост» в некоторых реализациях.
Карл Билефельдт
@KarlBielefeldt Хорошо, если каждый поток x будет ожидать семафора x, тогда все потоки будут заблокированы, и ничего не произойдет. Если wait (sem) на самом деле приобретает (sem) - тогда они попадут одновременно и исключения не будет. Пока не появятся дополнительные разъяснения, я считаю, что в этом псевдокоде что-то не так, и это не должно быть лучшим ответом.
AJed
Это просто показывает цикл для каждого потока. Код установки должен был бы опубликовать первый семафор, чтобы начать работу.
Карл Билефельдт
23

На мой взгляд, это невероятный вопрос для собеседования - по крайней мере, предполагая, что (1) кандидат должен иметь глубокие знания о потоках, и (2) интервьюер также обладает глубокими знаниями и использует этот вопрос для проверки кандидата. Всегда возможно, что интервьюер искал конкретный, узкий ответ, но компетентный интервьюер должен искать следующее:

  • Способность отличать абстрактные концепции от конкретной реализации. Я добавляю это прежде всего как мета-комментарий к некоторым комментариям. Нет, обрабатывать один список слов таким способом не имеет смысла. Тем не менее, важна абстрактная концепция конвейера операций, который может охватывать несколько машин с разными возможностями.
  • По моему опыту (почти 30 лет распределенных, многопроцессных и многопоточных приложений) распределение работы - не самая сложная часть. Сбор результатов и координация независимых процессов - это то место, где возникает большинство ошибок потоков (опять же, по моему опыту). Разобрав проблему до простой цепочки, интервьюер может увидеть, насколько хорошо кандидат думает о координации. Кроме того, интервьюер имеет возможность задавать всевозможные дополнительные вопросы, например: «Хорошо, что, если каждый поток должен отправить свое слово в другой поток для реконструкции».
  • Думает ли кандидат о том, как модель памяти процессора может повлиять на реализацию? Если результаты одной операции никогда не сбрасываются из кэша L1, это ошибка, даже если нет явного параллелизма.
  • Отделяет ли кандидат многопоточность от логики приложения?

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

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

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

Тем не менее, есть еще много серых областей, которые компетентный интервьюер может исследовать:

  • «Хорошо, но мы смотрим, что вы знаете о примитивах параллелизма. Можете ли вы создать очередь блокировки?» Ваш первый ответ, конечно, должен заключаться в том, что вы будете использовать предварительно построенную очередь блокировки с выбранной вами платформы. Однако, если вы понимаете потоки, вы можете создать реализацию очереди длиной до дюжины строк кода, используя любые примитивы синхронизации, которые поддерживает ваша платформа.
  • «Что делать, если один шаг в этом процессе занимает очень много времени?» Вам следует подумать о том, хотите ли вы ограниченную или неограниченную очередь вывода, как вы можете обрабатывать ошибки и как повлиять на общую пропускную способность, если у вас есть задержка.
  • Как эффективно поставить в очередь исходную строку. Не обязательно проблема, если вы имеете дело с очередями в памяти, но может быть проблемой, если вы перемещаетесь между машинами. Вы также можете изучить оболочки, доступные только для чтения, поверх основного неизменяемого байтового массива.

Наконец, если у вас есть опыт параллельного программирования, вы можете поговорить о некоторых фреймворках (например, Akka для Java / Scala), которые уже следуют этой модели.

kdgregory
источник
Вся эта заметка о кеше L1 процессора действительно заинтриговала меня. Проголосовал.
Марк ДиМилло
Я недавно использовал projectReactor с Spring 5. Это позволяет мне писать независимый от потока код.
Кундан Бора
16

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

"Просто попытайся ответить и убирайся отсюда ..."

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

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

Демиан Брехт
источник
3
Я отклонил этот ответ (хотя он получил 4 ответа), потому что он не отвечает на заданный вопрос.
Роберт Харви
1
@RobertHarvey: Иногда люди задают неправильные вопросы . У ОП плохой настрой на проведение технических собеседований, и этот ответ был попыткой помочь поставить его / ее на правильный путь.
Демиан Брехт
1
@RobertHarvey Я искренне верю, что это правильный ответ на вопрос. Ключевое слово здесь - «вопрос об интервью», который упоминается в заголовке и в тексте вопроса. На такой вопрос это правильный ответ. Если бы вопрос был только «У меня есть m потоков и параграф из n слов, и я хочу сделать это и то с ними, какой подход лучше», тогда да, этот ответ не был бы уместен для вопроса. Как это я думаю, это здорово. Перефразируя: я разбомбил довольно много вопросов на собеседовании, потому что я не последовал совету, данному здесь
Shivan Dragon
@RobertHarvey отвечает на связанный с этим вопрос, отрицательное голосование ничего не дало.
Марк ДиМилло
0
  • Сначала токенизируйте абзац с соответствующими разделителями и добавьте слова в очередь.

  • Создайте N потоков и сохраните их в пуле потоков.

  • Переберите пул потоков, запустите поток и дождитесь
    его присоединения. И начните следующий поток, как только закончится первый, и так далее.

  • Каждый поток должен просто опросить очередь и распечатать ее.

  • Как только все потоки используются в пуле потоков, начните с начала пула.

java_mouse
источник
0

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

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

Что-то вроде этого:

while(true)
{
    lock(index)
    {
        if(index >= array.length())
          break;
        Console.WriteLine(array[index]);
        index++;
    }
}

Я думаю, что это должно обеспечить выполнение одного потока за другим, но порядок потоков не гарантируется. Мне любопытно услышать и другие решения.

ConditionRacer
источник
-1

Используйте API-интерфейсы ожидания / сигнала для решения этой проблемы.

Допустим, первый поток выбирает 1 слово, а остальные отдыхают, все потоки ожидают сигнала. 1-й поток печатает 1-е слово и генерирует сигнал в следующий поток, а затем 2-й поток печатает второе слово и генерирует сигнал в 3-й поток и так далее.

#include <iostream>
#include <fstream>
#include <pthread.h>
#include <signal.h>
pthread_cond_t cond[5] = {PTHREAD_COND_INITIALIZER,};
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

using namespace std;

string gstr;

void* thread1(void*)
{
    do {
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[0],&mutex);
    cout <<"thread1 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread2(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[1],&mutex);
    cout <<"thread2 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread3(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[2],&mutex);
    cout <<"thread3 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread4(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[3],&mutex);
    cout <<"thread4 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread5(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[4],&mutex);
    cout <<"thread5 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

int main()
{
    pthread_t t[5];
    void* (*fun[5])(void*);
    fun[0]=thread1;
    fun[1]=thread2;
    fun[2]=thread3;
    fun[3]=thread4;
    fun[4]=thread5;

    for (int i =0 ; i < 5; ++i)
    {
        pthread_create(&t[i],NULL,fun[i],NULL);
    }
    ifstream in;
    in.open("paragraph.txt");
    int i=0;
    while(in >> gstr)
    {

        pthread_cond_signal(&cond[i++]);
        if(i == 5)
            i=0;
        usleep(10);
    }
    for (int i =0 ; i < 5; ++i)
    {
        int ret = pthread_cancel(t[i]);
        if(ret != 0)
            perror("pthread_cancel:");
        else
            cout <<"canceled\n";
    }
    pthread_exit(NULL);
}
Shashank
источник
-1

[Используемые здесь термины могут быть специфическими для потоков POSIX]

Должна быть возможность использовать мьютекс FIFO, чтобы решить эту проблему.

Где использовать:

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

Как это работает / Как реализовать:

Есть мьютекс, чтобы заблокировать. Инициализируйте специфичные для потока данные (TSD) для каждого потока для узла, содержащего идентификатор потока и семафор. Кроме того, есть две переменные - собственные (ИСТИНА или ЛОЖЬ или -1), владелец (идентификатор потока владельца). Кроме того, сохраните очередь официантов и указатель waiterLast, указывающий на последний узел в очереди официантов.

операция блокировки:

node = get_thread_specific_data(node_key);
lock(mutex);
    if(!owned)
    {
        owned = true;
        owner = self;
        return success;
    }

    node->next = nullptr;
    if(waiters_queue == null) waiters_queue = node;
    else waiters_last->next = node;

    waiters_last = node;
unlock(mutex);
sem_wait(node->semaphore);

lock(mutex);
    if(owned != -1) abort();
    owned = true;
    owner = self;
    waiters_queue = waiters_queue->next;
 unlock(mutex);

операция разблокировки:

lock(mutex);
    owner = null;
    if(waiters_queue == null)
    {
        owned = false;
        return success;
    }
    owned = -1;
    sem_post(waiters_queue->semaphore);
unlock(mutex);
user2615724
источник
-1

Интересный вопрос. Вот мое решение в Java, использующее SynchronousQueue для создания канала рандеву между потоками:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.SynchronousQueue;

public class FindNWordsGivenMThreads {

    private static final int NUMBER_OF_WORDS = 100;
    private static final int NUMBER_OF_THREADS = 5;
    private static final Stack<String> POISON_PILL = new Stack<String>();

    public static void main(String[] args) throws Exception {
        new FindNWordsGivenMThreads().run();
    }

    private void run() throws Exception {
        final Stack<String> words = loadWords();
        SynchronousQueue<Stack<String>> init = new SynchronousQueue<Stack<String>>();
        createProcessors(init);
        init.put(words);
    }

    private void createProcessors(SynchronousQueue<Stack<String>> init) {
        List<Processor> processors = new ArrayList<Processor>();

        for (int i = 0; i < NUMBER_OF_THREADS; i++) {

            SynchronousQueue in;
            SynchronousQueue out;

            if (i == 0) {
                in = init;
            } else {
                in = processors.get(i - 1).getOut();
            }

            if (i == (NUMBER_OF_THREADS - 1)) {
                out = init;
            } else {
                out = new SynchronousQueue();
            }

            Processor processor = new Processor("Thread-" + i, in, out);
            processors.add(processor);
            processor.start();

        }

    }

    class Processor extends Thread {

        private SynchronousQueue<Stack<String>> in;
        private SynchronousQueue<Stack<String>> out;

        Processor(String name, SynchronousQueue in, SynchronousQueue out) {
            super(name);
            this.in = in;
            this.out = out;
        }

        @Override
        public void run() {

            while (true) {

                Stack<String> stack = null;
                try {
                    stack = in.take();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                if (stack.empty() || stack == POISON_PILL) {
                    System.out.println(Thread.currentThread().getName() + " Done!");
                    out.offer(POISON_PILL);
                    break;
                }

                System.out.println(Thread.currentThread().getName() + " " + stack.pop());
                out.offer(stack);
            }
        }

        public SynchronousQueue getOut() {
            return out;
        }
    }

    private Stack<String> loadWords() throws Exception {

        Stack<String> words = new Stack<String>();

        BufferedReader reader = new BufferedReader(new FileReader(new File("/usr/share/dict/words")));
        String line;
        while ((line = reader.readLine()) != null) {
            words.push(line);
            if (words.size() == NUMBER_OF_WORDS) {
                break;
            }
        }
        return words;
    }
}
Sid
источник
-2

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

Затем я бы попросил их задать реальный вопрос о потоке или дать реальный пример серьезной работы с потоками.

gnasher729
источник