Multithreading Synchronization – Interview Question on Finding Words

multithreadingsynchronization

Is there a way this problem could benefit from a solution with multiple threads, rather than a single thread?

In an interview, I was asked to solve a problem using multiple threads. It appears to me that the multiple threads lends no benefit.

Here's the problem:

You are given a paragraph , which contain n number of words, you are
given m threads. What you need to do is , each thread should print one
word and give the control to next thread, this way each thread will
keep on printing one word , in case last thread come, it should invoke
the first thread. Printing will repeat until all the words are printed
in paragraph. Finally all threads should exit gracefully. What kind of
synchronization will use?

I strongly feel we cannot take any advantage of threads here, but believe the interviewer is trying to measure my synchronization skills. Am I missing something in this problem that would make multiple threads have value?

No need of code, just put some thoughts. I will implement by myself.

Best Answer

It sounds to me like they are leading you toward a semaphore solution. Semaphores are used to signal another thread that it's their turn. They are used much less frequently than mutexes, which I guess is why they think it's a good interview question. It's also why the example seems contrived.

Basically, you would create m semaphores. Each thread x waits on semaphore x then posts to semaphore x+1 after doing its thing. In pseudocode:

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])
Related Topic