Multithreading - Why does one thread do all the work?

Question

I multiply two matrices using two streams (however, the program is also written to scale, so I could use three, four, etc.). Each thread calculates / does the work for one row (or column) of the final matrix. If one thread does work on a row, the other (s) should not work on that row. He / they should go to the next available line.

First of all, I'm not sure if I implemented this problem correctly. If you can see a better way, please let me know.

Secondly, the way I did it, every time I test it (with different matrix sizes - even huge ones), only one thread works. That is, every time the same thread gets access to the synchronized block of the run () method. Other threads introduce the run () method, but why only one thread always gets a lock and does all the work?

This is my startup method:

public void run() { System.out.println(Thread.currentThread().getName()); while (i < number of columns in final matrix) { synchronized (this) { if (i < number of columns in final matrix) { for (int j = 0; j < Main.B[0].length; j++) { for (int k = 0; k < Main.A[0].length; k++) { Main.C[i][j] += Main.A[i][k] * Main.B[k][j]; } } i++; } } } } 

This is the code in my driver class that creates threads and runs the program:

 MyRunnable r = new MyRunnable(); Thread thread1 = new Thread(r); Thread thread2 = new Thread(r); thread1.start(); thread2.start(); try { thread1.join(); thread2.join(); } catch (InterruptedException ie) { System.out.println("\nThe following error occurred: " + ie); } } 

I think my question is double - is my approach correct for the problem? If so, (and if not), why does one thread always locks and does all the work? I checked the program with 6 threads on 20x20 matrices, and only one thread always works.

Answer 1

Like some of the suggested comments, the problem is locking (i.e., in the synchronized(this) ). Synchronization is performed on this , which in your case is the only instance of MyRunnable , therefore, while one thread does work inside the synchronized block, all other threads will wait until the operation is completed. Thus, only one thread does the real work at a time.

Here's how to solve the problem. Since you need your threads to work on different lines in parallel, this work should not be synchronized by locking (since locking means the opposite: only one thread can do the work at a time). What you need to synchronize is the part in which each thread determines which line it will run on.

Here is an example of pseudo code:

 public void run(){ int workRow; synchronized(this){ workRow = findNextUnprosessedRow(); } for(int i=0; i<matrix[workRow].length; i++){ //do the work } } 

Please note that the actual work is intentionally not synchronized for the reasons mentioned above.

The way you use threads is correct, so there is no problem with this, however I would suggest you take a look at the Java concurrency API: Thread Pools . Here is an example of how to use it in your context:

 //Creates a pool of 5 concurrent thread workers ExecutorService es = Executores.newFixedThreadPool(5); //List of results for each row computation task List<Future<Void>> results = new ArrayList<Future<Void>>(); try{ for(int row=0; row<matrix.length; row++){ final int workRow = row; //The main part. You can submit Callable or Runnable // tasks to the ExecutorService, and it will run them // for you in the number of threads you have allocated. // If you put more than 5 tasks, they will just patiently // wait for a task to finish and release a thread, then run. Future<Void> task = es.submit(new Callable<Void>(){ @Override public Void call(){ for(int col=0; col<matrix[workRow].length; col++){ //do something for each column of workRow } return null; } }); //Store the work task in the list. results.add(task); } }finally{ //Make sure thread-pool is shutdown and all worker //threads are released. es.shutdown(); } for(Future<Void> task : results){ try{ //This will wait for threads to finish. // ie same as Thread.join() task.get(); }catch(ExecutionException e){ //One of the tasks threw an exception! throw new RuntimeException(e); } } 

This approach is much cleaner because the distribution of work is done mainly by thread (external to the loop) and therefore there is no need to synchronize it.

You also get some bonuses when working with thread pools:

• He takes great care of all exceptions during the calculations in each thread. When working with bare threads, as in your approach, it is easy to “lose” the exception.

• Streams are combined. That is, they are automatically reused, so you don’t have to worry about the cost of spawning new threads. This is especially useful in your case, since you will need to spawn a stream in a row in your matrix, which can be quite large, I suspect.

• The tasks presented by ExecutorService are wrapped in a useful Future<Result> object, which is most useful when each calculation task actually returns some kind of result. In your case, if you need to sum all the values ​​in the matrix, then each calculation task can return the sum for the row. Then you just need to take stock.

Got some time, but hope he clears some things.

Answer 2

Your problem is that you are synchronizing the entire region with synchronized(this) . This means that only one thread at a time can enter the loop performing the calculation. Of course, this may mean that several threads can calculate different parts, but not several threads at once simultaneously. It also means that your "parallel" solution is not faster than a single thread.

If you want to do parallel computing, see Parallel Matrix Multiplication in Java 6 and the Fork Registration Matrix in Java , which should cover the topic

Answer 3

Scheduling threads depends on the particular implementation of the virtual machine. In some implementations, the thread will continue to run until it in some way blocks or is not superseded by the thread with a higher priority. In your case, all threads have the same priority, so the first thread that goes into the synchronized block is never blocked, it does not receive priority. Some planners implement priority aging, so the hunger flow will eventually increase with priority, but you may not work long enough for it to have an effect.

Add a call to Thread.yield() immediately after the end of the synchronized block. This tells the scheduler to select a new thread to start (possibly the same, but possibly another).

Answer 4

Your launch function has a first thread to force the lock to do all the work on the string, while maintaining the lock. For the next line, perhaps another thread will get a lock, but it will block all other threads until it is done.

What I would do is to have an array of logical numbers that matches the number of lines, and use them to request the task of processing each individual line. It will be something like the following pseudocode:

 //before creating the threads, pre-fill BoolList with trues function run() { while (true) { lock(BoolList) { //find first true value and set it to false //if no true found, return } //do the actual math of multiplying the row we claimed above } } 

Also keep in mind that the overhead of creating a new thread is sufficient so that the multithreading of this program would only cost large matrices.

Answer 5

As already noted in his comment by mru , the problem is that all string calculations are performed inside the "synchronized (this)" block. Because of this, all threads will wait for processing of one line before the start of the next, and the same thread that always gets a lock is probably the result of optimization, since you largely do single-threaded calculations. You might consider setting only the decision about which row is processed inside the synchronized block:

 int rowToProcess; synchronized (this) { if (i < number of columns in final matrix){ rowToProcess = i; i++; } else return; }