Unexplained Deadlocks

[Swiftle]

Hello,

I have an assignment for a multi thread bubble sort written in Java. It may not sound very hard but we only had 4 hours of introduction and never wrote a single line in Java before getting this. But this isn't the point :P. I have problems with what I think are deadlocks.
But first let me explain how the program should work. The user specifies the size of the array and the number of threads: even threads start from 0 odd from array.size()-1. I also have to variables (min and max) that serve as limits to the threads. It works like this: if we start from 0 and go to array.size()-1 we can be sure that after the first pass the biggest value is at array(length-1), thus the next thread that starts from 0 should only go to array.size-2. Same applies for threads that go from length-1 to 0.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

interface NumberedObject
{
	public int getId();
	public String toString();
}

class NumberedInt implements NumberedObject
{
	private int ID;		
	public NumberedInt(int i){
		ID=i;
	}		
	public String toString(){
		return "ID = " + ID;
	}

	public int getId(){
		return ID;
	}	
	public void setId(int Id){
		ID = Id;
	}
}

class Sorter extends Thread{
	private static List<NumberedObject> list, locks;
	public static int min,max;

	public Sorter(List<NumberedObject> list){
		this.list = list;
	}
	
	public static void init(List<NumberedObject> list){
		min = 0;
		max = list.size()-1;
		locks = list;
	}

	public void multiSort(){
	if(getId()%2 == 0)
		forwardSort();
	else
		backwardsSort();
	}
	
	public void run(){
		multiSort();
	}

	public void forwardSort(){
		boolean doMore = true;
		while (doMore) {
			doMore = false; 
			for (int i=min; i<max; i++) {
				synchronized(locks.get(i)){
					synchronized(locks.get(i+1)){		    
						if (list.get(i).getId() > list.get(i+1).getId()){ 
							NumberedObject temp = list.get(i); yield();
							list.set(i, list.get(i+1)); yield();
							list.set(i+1,temp); yield();
						    doMore = true; 
			   			}
					}
				}
			}
			synchronized(this){
				max--;
			}
		}
	}
	public void backwardsSort(){
		boolean doMore = true;
		while (doMore) {
			doMore = false; 
			for (int i=max; i>min; i--) {
				synchronized(locks.get(i)){
					synchronized(locks.get(i-1)){		    
						if (list.get(i).getId() < list.get(i-1).getId()){ 
							NumberedObject temp = list.get(i); yield(); 
							list.set(i, list.get(i-1)); yield();
							list.set(i-1,temp); yield();
						    doMore = true; 
			   			}
					}
				}
			}
			synchronized(this){
				min++;
			}
		}
	}	
}

public class MultiBubbles
{	
	public static void main(String [] args)
	{			
		Scanner scan = new Scanner(System.in);	
		System.out.print("Enter the size of the array: ");
		int size = scan.nextInt();	
		System.out.print("Enter the number of threads: ");
		int threads = scan.nextInt();
		List<NumberedObject> unsortedArray = new ArrayList();
	
		for(int i=0; i<size; i++){
			Random r = new Random();			
			int rand = r.nextInt()%20;
			unsortedArray.add(new NumberedInt(rand));
		}	
		
		for(int i = 0 ; i < unsortedArray.size(); ++i) 

			System.out.print(unsortedArray.get(i).getId() +" ");

		System.out.println();	
		
		Sorter.init(unsortedArray);
		Sorter [] nmbrThreads = new Sorter[threads];
		for(int i=0; i<threads; i++){
			nmbrThreads[i] = new Sorter(unsortedArray);
			nmbrThreads[i].start();
		}
		try{
			for(int i=0; i<threads; i++)
				nmbrThreads[i].join();
		}
		catch(Exception e){
		e.printStackTrace();
		}

				for(int i = 0 ; i < unsortedArray.size(); ++i) 

			System.out.print(unsortedArray.get(i).getId() +" ");

		System.out.println();	

	}
}

Here's the code. I have to points of concern. The first one is max-- and min++. These are static because I want them to be there for every thread I use, but I wonder if modifiyng them within one thread wouldn't mess up something else in another thread. I tried doing this with

synhchronized(this){
min++
}

and with just a min++ but I still get locks. The other thing I'm not sure about is whetherList<NumberedObject> list should be static or no, and if yes, then what should the constructor do?

[masijade]

Okay, lets say your locks are numbered 1 - 5 (looking at your max min loop).

Now, lets say two threads are working, one doing a forward sort and one doing a backword sort. Now, lets say the one doing the forward sort gets a lock on say lock three, and the one doing the backward sort gets a lock on lock four. Now, each of these threads (due to your "stacking" or "embedding" of locks) wants to get the lock on the lock object that the other thread already holds. Boom, deadlock.

[Swiftle]

It seems I messed up the original solution xD The "locks" array was there to prevent the deadlocks. So we would synchronize the access on the locks array which remained static as opposed to the "list" array which was mobile. The problem is that

locks = list

had locks pointing to list and did nothing to prevent the locks from occurring. What I should have done is

locks = new ArrayList(list)