'print numbers in sorted order using 3 threads which print different ranges

This question was asked in ElectronicArts interview.

There are 3 threads. First thread prints 1 to 10 numbers. Second thread prints numbers from 11 to 20. and third thread prints from 21 to 30. Now all three threads are running. However numbers are printed in irregular order like 1, 11, 2, 21, 12 etc.

If I want numbers to be printed in sorted order like 1, 2, ... what should I do with these threads?

c++multithreading


Solution 1:[1]

use a shared condition object the threads can suspend on. The condition can be in either of 3 states: 0, 1, 2. The condition is initialized with state 0. The 1-10 thread is associated with state 0, the 11-20 one is associated with state 1, the last thread is associated with state 2. Each thread, when started, checks the condition and suspends on it if condition's state differs from the one the thread is associated with. Only one thread at a time will be allowed to run and print its range. When a thread has printed its range, it increments the condition's state, wakes the threads waiting on it and terminates. This should solve the problem.

If threads are not allowed to suspend, then have them polling on the shared object representing the "ordered scheduling" of the 3 threads.

Another approach could be to chain the threads: have the second thread to block until the first terminates, and the third one to block until the second one is done. This solution requires no shared objects, but each thread needs to know its predecessor

Solution 2:[2]

Seems like a natural for a barrier. Three processes, two barriers (call them barrier10 and barrier20).

Process 1:

Print 1-10
Wait on barrier10
Wait on barrier20
Exit

Process 2:

Wait on barrier10
Print 11-20
Wait on barrier20
Exit

Process 3:

Wait on barrier10
Wait on barrier20
Print 21-30
Exit

Solution 3:[3]

Maybe a single static method that is used by all three threads to print their numbers should lock, check already printed numbers, and if its number is ready to be printed, print and move on, otherwise unlock and yield.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Ian Ross
Solution 3 Chris Hawkins

Related Questions