Iyfjky

Question

I have recently started with multi-threading in Java

I have an issue solving a problem where I have got only 5 Threads ranging from T1, T2,...T5.

The task is to print numbers from 1 to 10 in the following order.

T1 -> 1
T2 -> 2
T3 -> 3
T4 -> 4
T5 -> 5
T1 -> 6
T2 -> 7
T3 -> 8
T4 -> 9
T5 -> 10

I tried solving it with this piece of code.

public static void main(String args) throws InterruptedException 
 Counter counter = new Counter();
 Thread tArray = new Thread new Thread(counter, "T1"), new Thread(counter, "T2"),
 new Thread(counter, "T3"), new Thread(counter, "T4"), new Thread(counter, "T5") ;
 for (int i = 0; i < 10; i++) 
 if (i < 5) 
 tArray[i].start();
 tArray[i].join();
 else 
 tArray[i - 5] = new Thread(counter, "T" + ((i - 5) + 1)); //Instantiating new Thread which is not allowed.
 tArray[i - 5].start();
 tArray[i - 5].join();
 
 


public class Counter implements Runnable 

 private int count = 0;

 @Override
 public synchronized void run() 
 System.out.println(Thread.currentThread().getName() + " -> " + ++count);

But since only 5 threads are allowed my solution is not accepted since I am also instantiating new Thread in the else block of the for loop.

Any help would be highly appreciated.

Actually, this is pretty much a dup of this question: stackoverflow.com/questions/12989397/â€¦ — 5 hours ago
Possible duplicate of Print 1 to 100 using 10 threads in java — 1 hour ago

score 3 · Answer 1 · 2018-09-27 13:00:06Z

_{Disclaimer: I am answering the practical counterpart of the OP's question â€” parallel processing with serial input and output. It's much more fun.}

Thinking process

I have a serial resource - System.out. No matter how I structure the code there will be explicit or implicit queueing/contention in front of it.

The best way to deal with contention is via explicit queueing (which can be observed, quantified, and addressed, opposed to when implicit queue on a mutex or a synchronized block is used).

My is a 3 step pipeline: Produceâ†’Stringizeâ†’Output.

The Stringize step can be done in parallel, providing that the ordered Output can still happen.

I start from a quick & dirty "poor man's" solution. With Java 8 this would be with CompletableFuture-s:

final Executor inputWorker = newSingleThreadExecutor();
final Executor processingPool = newFixedThreadPool(3);
final Executor outputWorker = newSingleThreadExecutor();

final int counter = -1; // this emulates a non-thread-safe information source
CompletableFuture<Void> future = completedFuture(null);
for (int i = 0; i < 10; ++i) 
 future = future // chaining of futures is essential for serializing subsequent iterations
 .thenApplyAsync(unused -> ++counter[0], inputWorker)
 .thenApplyAsync(Objects::toString, processingPool)
 .thenAcceptAsync(System.out::println, outputWorker);

future.join();

Once I have good intuition how it works I may consider industrial techniques like actors, disruptor, or something alike to improve it further.

P.S. - for completeness, one may want to have step #5 slightly differently, first create the whole computation schedule and then trigger it:

final Executor producer = newSingleThreadExecutor();
final Executor stringizer = newFixedThreadPool(3);
final Executor printer = newSingleThreadExecutor();

final int counter = -1; // this emulates a non-thread-safe information source

System.out.println("creating schedule...");
// first schedule the whole amount of work and block the execution on a single "trigger" future
final CompletableFuture<Void> trigger = new CompletableFuture<>();
CompletableFuture<Void> future = trigger;
for (int i = 0; i < 10; ++i) 
 future = future
 .thenApplyAsync(unused -> ++counter[0], producer)
 .thenApplyAsync(Objects::toString, stringizer)
 .thenAcceptAsync(System.out::println, printer);


// then pull the trigger
System.out.println("pulling the trigger...");
trigger.complete(null);
future.join();

Isn't the use of a threadpool for the stringification redundant when you're going to join() after each step? — 5 hours ago
@ohlec - I knew someone would notice! I reworked it, please read again :-) — 5 hours ago
OK, but don't you now get race conditions and lose ordering? — 4 hours ago
Ah, yes, I overlooked the part of the edit where you chain futures across for loop iterations, sorry. This is a very sensible solution. (I'm afraid it still doesn't fit the original requirements because the threads have different tasks now, though) — 4 hours ago
@ohlec - I spent a fair amount of (paid) time fixing software implemented to the requirements similar to the ones in the question, so would rather not advise in that direction :-) They should really stop teaching threads and low level primitives before teaching executors, pipelines, flow graphs, and actors. — 4 hours ago

score 2 · Answer 2 · 2018-09-27 13:04:55Z

Your current approach is not going to work. A thread can only be started once. Since you have 5 threads and each must produce two messages, with a specific interleaving, they need to be coordinated.

Hint: this will entail some kind of signalling mechanism between the threads. Look at things like primitive wait / notify signalling, Semaphore or a BlockingQueue.

(Using an ExecutorService is probably "against the rules", and you wouldn't be able to control which worker thread produces which message ... which is one of the requirements of your problem.)

Here's a solution using wait/notify and a CountDownLatch to make sure all the threads are started. (There are a few unnamed constants scattered around but there significance should be manifestly obvious.)

import java.util.concurrent.*;

public class Test 
 private static int counter = 0;
 private static final Object lock = new Object();
 private static final CountDownLatch gate = new CountDownLatch(5);

 public static class CountPrinter implements Runnable 
 private final int myIndex;

 public CountPrinter(int myIndex) 
 this.myIndex = myIndex;
 

 public void run() 
 gate.countDown();
 try 
 while (counter < 10) 
 synchronized (lock) 
 lock.wait();
 if (counter < 10 && counter % 5 == myIndex - 1) 
 counter++;
 System.out.println(Thread.currentThread().getName() +
 " -> " + counter);
 lock.notifyAll();
 
 
 
 
 catch (InterruptedException ex) 
 // Blah
 
 
 

 public static void main(String args) throws InterruptedException 
 Thread tArray = new Thread 
 new Thread(new CountPrinter(1), "T1"),
 new Thread(new CountPrinter(2), "T2"),
 new Thread(new CountPrinter(3), "T3"),
 new Thread(new CountPrinter(4), "T4"),
 new Thread(new CountPrinter(5), "T5"),
 ;

 for (int i = 0; i < 5; i++) 
 tArray[i].start();
 
 gate.await();
 synchronized (lock) 
 lock.notifyAll();
 
 for (int i = 0; i < 5; i++) 
 tArray[i].join();

(There is a subtle race condition in this solution. See if you can spot it :-) )

score 2 · Answer 3 · 2018-09-27 15:55:31Z

You need to arrange interaction between threads. The most natural way for thread interaction is setting up blocking queues which connect threads. Queues can be independent objects, or belong to particular threads.
In your case, you need to make a circle of 5 threads.

class CountPrinter extends Thread 
 String name;
 ArrayBlockingQueue<Integer> inp = new ArrayBlockingQueue<>();
 CountPrinter next;

 public void run() 
 for (;;)
 int n = inp.take();
 if (n == 11) // only 10 numbers must be printed
 next.inp.put(11);
 return;
 
 System.out.println(name+"->"+n);
 next.inp.put(n+1);
 
 
}

After creating a thread and before its start, you need to assign the fields name and next. I believe you can program this yourself.
Also, the first thread must be provided with the initial value 1.

This is much nicer than the other answers (including mine!). — 49 mins ago

Eugene 61.3k986143 · Answer 4 · 2018-09-27 13:31:52Z

Another way would be to keep two AtomicIntegers , something like this:

static class MyRunnable implements Runnable 

 private final AtomicInteger index;
 private final AtomicInteger ai;
 private final int array;
 private final int current;
 private final int next;

 public MyRunnable(AtomicInteger index, AtomicInteger ai, int array, int current, int next) 
 this.index = index;
 this.ai = ai;
 this.array = array;
 this.current = current;
 this.next = next;
 

 @Override
 public void run() 
 for (;;) 
 if (index.get() == array.length) 
 break;
 
 if (ai.get() == current) 
 System.out.println(Thread.currentThread().getName() + " " + array[index.getAndIncrement()]);
 ai.compareAndSet(current, next);

And usage would be:

public static void main(String args) 

 int array = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ;

 AtomicInteger ai = new AtomicInteger(1);
 AtomicInteger index = new AtomicInteger(0);

 Thread t1 = new Thread(new MyRunnable(index, ai, array, 1, 2), "T1");
 Thread t2 = new Thread(new MyRunnable(index, ai, array, 2, 3), "T2");
 Thread t3 = new Thread(new MyRunnable(index, ai, array, 3, 4), "T3");
 Thread t4 = new Thread(new MyRunnable(index, ai, array, 4, 5), "T4");
 Thread t5 = new Thread(new MyRunnable(index, ai, array, 5, 1), "T5");

 t1.start();
 t2.start();
 t3.start();
 t4.start();
 t5.start();

score 0 · Answer 5 · 2018-09-27 15:10:13Z

You need to allow your 5 threads to communicate so that they run in a strict sequence. Kind of like dominos falling, each thread must sit waiting until it is poked, then it does its thing and says to the next thread 'You can go now'.

But unlike dominos falling they must also pick themselves back up so they are ready for the next round, and the last domino must knock over the first domino again!

I think the best built-in for this kind of communication is the Phaser. Here is an implementation using Phasers:

import java.util.concurrent.Phaser;
import java.util.concurrent.atomic.AtomicInteger;

public final class SequencedThreads

 private static AtomicInteger count = new AtomicInteger(0);

 public static void main(String args) 
 PrintThread threads = new PrintThread[5];

 // Create our 5 threads, each with a phaser waiting on itself 
 // and the previous thread
 for(int i = 0; i < 5; i++) 
 threads[i] = new PrintThread("T" + (i + 1));
 if(i > 0)
 threads[i - 1].next = threads[i].phaser;
 

 // Join the last thread back to the first thread
 threads[4].next = threads[0].phaser;

 // Start our threads
 for(PrintThread pt : threads)
 pt.start();

 // Trigger the first thread to print
 threads[0].phaser.arriveAndDeregister();
 

 private static final class PrintThread extends Thread 
 Phaser phaser;
 Phaser next;

 public PrintThread(String name) 
 super(name);
 this.phaser = new Phaser(2);
 

 @Override
 public void run() 
 while(true) 
 // Block until we are poked
 phaser.arriveAndAwaitAdvance();
 int newCount = count.incrementAndGet();
 if(newCount > 10) 
 // We are done, but trigger the other threads to allow 
 // the JVM to exit
 next.arriveAndDeregister();
 return;
 

 System.out.println(getName() + " -> " + newCount);
 // Pick ourselves back up
 phaser.register();
 // Poke the next domino
 next.arriveAndDeregister();

score 3 · Answer 6 · 2018-09-27 13:00:06Z

_{Disclaimer: I am answering the practical counterpart of the OP's question â€” parallel processing with serial input and output. It's much more fun.}

Thinking process

I have a serial resource - System.out. No matter how I structure the code there will be explicit or implicit queueing/contention in front of it.

The best way to deal with contention is via explicit queueing (which can be observed, quantified, and addressed, opposed to when implicit queue on a mutex or a synchronized block is used).

My is a 3 step pipeline: Produceâ†’Stringizeâ†’Output.

The Stringize step can be done in parallel, providing that the ordered Output can still happen.

I start from a quick & dirty "poor man's" solution. With Java 8 this would be with CompletableFuture-s:

final Executor inputWorker = newSingleThreadExecutor();
final Executor processingPool = newFixedThreadPool(3);
final Executor outputWorker = newSingleThreadExecutor();

final int counter = -1; // this emulates a non-thread-safe information source
CompletableFuture<Void> future = completedFuture(null);
for (int i = 0; i < 10; ++i) 
 future = future // chaining of futures is essential for serializing subsequent iterations
 .thenApplyAsync(unused -> ++counter[0], inputWorker)
 .thenApplyAsync(Objects::toString, processingPool)
 .thenAcceptAsync(System.out::println, outputWorker);

future.join();

Once I have good intuition how it works I may consider industrial techniques like actors, disruptor, or something alike to improve it further.

P.S. - for completeness, one may want to have step #5 slightly differently, first create the whole computation schedule and then trigger it:

final Executor producer = newSingleThreadExecutor();
final Executor stringizer = newFixedThreadPool(3);
final Executor printer = newSingleThreadExecutor();

final int counter = -1; // this emulates a non-thread-safe information source

System.out.println("creating schedule...");
// first schedule the whole amount of work and block the execution on a single "trigger" future
final CompletableFuture<Void> trigger = new CompletableFuture<>();
CompletableFuture<Void> future = trigger;
for (int i = 0; i < 10; ++i) 
 future = future
 .thenApplyAsync(unused -> ++counter[0], producer)
 .thenApplyAsync(Objects::toString, stringizer)
 .thenAcceptAsync(System.out::println, printer);


// then pull the trigger
System.out.println("pulling the trigger...");
trigger.complete(null);
future.join();

Isn't the use of a threadpool for the stringification redundant when you're going to join() after each step? — 5 hours ago
@ohlec - I knew someone would notice! I reworked it, please read again :-) — 5 hours ago
OK, but don't you now get race conditions and lose ordering? — 4 hours ago
Ah, yes, I overlooked the part of the edit where you chain futures across for loop iterations, sorry. This is a very sensible solution. (I'm afraid it still doesn't fit the original requirements because the threads have different tasks now, though) — 4 hours ago
@ohlec - I spent a fair amount of (paid) time fixing software implemented to the requirements similar to the ones in the question, so would rather not advise in that direction :-) They should really stop teaching threads and low level primitives before teaching executors, pipelines, flow graphs, and actors. — 4 hours ago

score 2 · Answer 7 · 2018-09-27 13:04:55Z

Your current approach is not going to work. A thread can only be started once. Since you have 5 threads and each must produce two messages, with a specific interleaving, they need to be coordinated.

Hint: this will entail some kind of signalling mechanism between the threads. Look at things like primitive wait / notify signalling, Semaphore or a BlockingQueue.

(Using an ExecutorService is probably "against the rules", and you wouldn't be able to control which worker thread produces which message ... which is one of the requirements of your problem.)

Here's a solution using wait/notify and a CountDownLatch to make sure all the threads are started. (There are a few unnamed constants scattered around but there significance should be manifestly obvious.)

import java.util.concurrent.*;

public class Test 
 private static int counter = 0;
 private static final Object lock = new Object();
 private static final CountDownLatch gate = new CountDownLatch(5);

 public static class CountPrinter implements Runnable 
 private final int myIndex;

 public CountPrinter(int myIndex) 
 this.myIndex = myIndex;
 

 public void run() 
 gate.countDown();
 try 
 while (counter < 10) 
 synchronized (lock) 
 lock.wait();
 if (counter < 10 && counter % 5 == myIndex - 1) 
 counter++;
 System.out.println(Thread.currentThread().getName() +
 " -> " + counter);
 lock.notifyAll();
 
 
 
 
 catch (InterruptedException ex) 
 // Blah
 
 
 

 public static void main(String args) throws InterruptedException 
 Thread tArray = new Thread 
 new Thread(new CountPrinter(1), "T1"),
 new Thread(new CountPrinter(2), "T2"),
 new Thread(new CountPrinter(3), "T3"),
 new Thread(new CountPrinter(4), "T4"),
 new Thread(new CountPrinter(5), "T5"),
 ;

 for (int i = 0; i < 5; i++) 
 tArray[i].start();
 
 gate.await();
 synchronized (lock) 
 lock.notifyAll();
 
 for (int i = 0; i < 5; i++) 
 tArray[i].join();

(There is a subtle race condition in this solution. See if you can spot it :-) )

score 2 · Answer 8 · 2018-09-27 15:55:31Z

You need to arrange interaction between threads. The most natural way for thread interaction is setting up blocking queues which connect threads. Queues can be independent objects, or belong to particular threads.
In your case, you need to make a circle of 5 threads.

class CountPrinter extends Thread 
 String name;
 ArrayBlockingQueue<Integer> inp = new ArrayBlockingQueue<>();
 CountPrinter next;

 public void run() 
 for (;;)
 int n = inp.take();
 if (n == 11) // only 10 numbers must be printed
 next.inp.put(11);
 return;
 
 System.out.println(name+"->"+n);
 next.inp.put(n+1);
 
 
}

After creating a thread and before its start, you need to assign the fields name and next. I believe you can program this yourself.
Also, the first thread must be provided with the initial value 1.

This is much nicer than the other answers (including mine!). — 49 mins ago

Eugene 61.3k986143 · Answer 9 · 2018-09-27 13:31:52Z

Another way would be to keep two AtomicIntegers , something like this:

static class MyRunnable implements Runnable 

 private final AtomicInteger index;
 private final AtomicInteger ai;
 private final int array;
 private final int current;
 private final int next;

 public MyRunnable(AtomicInteger index, AtomicInteger ai, int array, int current, int next) 
 this.index = index;
 this.ai = ai;
 this.array = array;
 this.current = current;
 this.next = next;
 

 @Override
 public void run() 
 for (;;) 
 if (index.get() == array.length) 
 break;
 
 if (ai.get() == current) 
 System.out.println(Thread.currentThread().getName() + " " + array[index.getAndIncrement()]);
 ai.compareAndSet(current, next);

And usage would be:

public static void main(String args) 

 int array = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ;

 AtomicInteger ai = new AtomicInteger(1);
 AtomicInteger index = new AtomicInteger(0);

 Thread t1 = new Thread(new MyRunnable(index, ai, array, 1, 2), "T1");
 Thread t2 = new Thread(new MyRunnable(index, ai, array, 2, 3), "T2");
 Thread t3 = new Thread(new MyRunnable(index, ai, array, 3, 4), "T3");
 Thread t4 = new Thread(new MyRunnable(index, ai, array, 4, 5), "T4");
 Thread t5 = new Thread(new MyRunnable(index, ai, array, 5, 1), "T5");

 t1.start();
 t2.start();
 t3.start();
 t4.start();
 t5.start();

score 0 · Answer 10 · 2018-09-27 15:10:13Z

You need to allow your 5 threads to communicate so that they run in a strict sequence. Kind of like dominos falling, each thread must sit waiting until it is poked, then it does its thing and says to the next thread 'You can go now'.

But unlike dominos falling they must also pick themselves back up so they are ready for the next round, and the last domino must knock over the first domino again!

I think the best built-in for this kind of communication is the Phaser. Here is an implementation using Phasers:

import java.util.concurrent.Phaser;
import java.util.concurrent.atomic.AtomicInteger;

public final class SequencedThreads

 private static AtomicInteger count = new AtomicInteger(0);

 public static void main(String args) 
 PrintThread threads = new PrintThread[5];

 // Create our 5 threads, each with a phaser waiting on itself 
 // and the previous thread
 for(int i = 0; i < 5; i++) 
 threads[i] = new PrintThread("T" + (i + 1));
 if(i > 0)
 threads[i - 1].next = threads[i].phaser;
 

 // Join the last thread back to the first thread
 threads[4].next = threads[0].phaser;

 // Start our threads
 for(PrintThread pt : threads)
 pt.start();

 // Trigger the first thread to print
 threads[0].phaser.arriveAndDeregister();
 

 private static final class PrintThread extends Thread 
 Phaser phaser;
 Phaser next;

 public PrintThread(String name) 
 super(name);
 this.phaser = new Phaser(2);
 

 @Override
 public void run() 
 while(true) 
 // Block until we are poked
 phaser.arriveAndAwaitAdvance();
 int newCount = count.incrementAndGet();
 if(newCount > 10) 
 // We are done, but trigger the other threads to allow 
 // the JVM to exit
 next.arriveAndDeregister();
 return;
 

 System.out.println(getName() + " -> " + newCount);
 // Pick ourselves back up
 phaser.register();
 // Poke the next domino
 next.arriveAndDeregister();

Search This Blog

Iyfjky

Print integers from 1 to 10 with only 5 Threads in a specific order

5 Answers
5

Thinking process

Your Answer

Post as a guest

5 Answers
5

5 Answers
5

Thinking process

Thinking process

Thinking process

Thinking process

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

Category

Random preview

Print integers from 1 to 10 with only 5 Threads in a specific order

5 Answers 5

Thinking process

Your Answer

Sign up or log in

Post as a guest

Post as a guest

5 Answers 5

5 Answers 5

Thinking process

Thinking process

Thinking process

Thinking process

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

5 Answers
5

5 Answers
5

5 Answers
5

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor