Thread Queueing

[mynorka]

Hello all!

I'm writing a simple program that consists of 10 threads and a library of 5 books. Each thread checks to see if the library has any books to check out, and enters a FIFO queue if the library is empty. Otherwise the thread checks out the first book in the library, reads it (sleeps for a random amount of time) then enters a queue to return the book to the library.

After every checkout, my program prints out which thread checked out what book, and also what books remain in the library. I've ran the program a couple of times and have noticed that multiple threads have been checking out the same book, even though the book should be removed from the queue. I have code and output below. Any suggestions would be much appreciated!

The class Library contains a Queue called books which is a 5 element LinkedList, having values 1-5.

public class PatronThread extends Thread {
	public Library library = new Library();
	public boolean taken = false;
	public Queue<Thread> tQueue = new LinkedList<Thread>();
	public Queue<Thread> t2Queue = new LinkedList<Thread>(); 
 
	public PatronThread(String name) { 
		super(name); 
	}
 
	@Override
	public void run() {
		Thread t = Thread.currentThread(); 
		int maxBooks = 4, currentBooks = 0;
		int current = 0;
 
		while(currentBooks < maxBooks){
 
			try{Thread.sleep( (int) Math.random() * 1000); }
			catch (InterruptedException e){ }
 
			//Checkout book from library
 
 
			if(library.books.size() == 0){
				System.err.println(t.getName() + " entering FIFO queue to get a book. "
						+ "Library currently has " + library.books + "\n");
				tQueue.add(t);
			}
			else{
				t2Queue.add(t); 
				synchronized(this){
				current = library.books.remove();
 
				System.err.println(t.getName() + " got book " 
					  + current + ". Library now has " + library.books + "\n");
				}
				//Reading Book
				try{Thread.sleep((int) Math.random() * 1000); }
				catch (InterruptedException e) { }
 
				//Returning book
				library.books.add(current);
				System.err.println(t2Queue.remove().getName() + " entering FIFO to return book "  + 
						current + ". Library currently has books \n" 
						+ library.books + "\n");
			}
 
			currentBooks++; 
		}
	}
}

Output:
t1 got book 1. Library now has [2, 3, 4, 5]

t2 got book 1. Library now has [2, 3, 4, 5]

t3 got book 1. Library now has [2, 3, 4, 5]

t6 got book 1. Library now has [2, 3, 4, 5]

t4 got book 1. Library now has [2, 3, 4, 5]

t10 got book 1. Library now has [2, 3, 4, 5]

t8 got book 1. Library now has [2, 3, 4, 5]

t2 entering FIFO to return book 1. Library currently has books
[2, 3, 4, 5, 1]

t9 got book 1. Library now has [2, 3, 4, 5]

t1 entering FIFO to return book 1. Library currently has books
[2, 3, 4, 5, 1]

t2 got book 2. Library now has [3, 4, 5, 1]

t9 entering FIFO to return book 1. Library currently has books
[2, 3, 4, 5, 1]

[andbin]

After every checkout, my program prints out which thread checked out what book, and also what books remain in the library. I've ran the program a couple of times and have noticed that multiple threads have been checking out the same book, even though the book should be removed from the queue. I have code and output below. Any suggestions would be much appreciated!

You have not posted all the code, so it's not easy to understand the whole architecture of your application. However two things can be clearly and easily spotted in the PatronThread class.

1) You have defined the job of a thread in a Thread subclass. As you have said, you have 10 threads and this means that there are 10 instances of PatronThread class. But you have used synchronized(this){ ... } and this means that each thread acquire the lock on its instance. So there is no mutual exclusion. Your synchronized(this){ ... } is totally useless.

2) Each thread has its Library object:
public Library library = new Library();

But in theory, there should be only 1 Library object, shared between all threads. And note that the synchronization (plus eventual "blocking" behaviour) should be encapsulated in Library .... not in each "client" of Library.

[mynorka]

Here's the rest of the code

Library Class

package csu.mcdonald; 
 
import java.util.LinkedList;
 
public class Library {
	public LinkedList<Integer> books; 
 
	public Library() { 
		books = new LinkedList<Integer>(); 
		for(int i = 0; i < 0; i++)
			books.add(i); 
	}
 
	public boolean isFull() { return books.size() == 5; }
	public boolean isEmpty() { return books.size() == 0; }
}

ThreadStarter

package csu.mcdonald;
 
public class ThreadStarter {
	public static void main(String[] args){
 
		Thread t1,t2,t3,t4,t5,t6,t7,t8,t9,t10; 
 
		t1 = new PatronThread("t1"); t2 = new PatronThread("t2");
		t3 = new PatronThread("t3"); t4 = new PatronThread("t4");
		t5 = new PatronThread("t5"); t6 = new PatronThread("t6");
		t7 = new PatronThread("t7"); t8 = new PatronThread("t8");
		t9 = new PatronThread("t9"); t10 = new PatronThread("t10");
 
		t1.start(); t2.start();
		t3.start(); t4.start();
		t5.start(); t6.start();
		t7.start(); t8.start();
		t9.start(); t10.start();
 
	}
}

So, how can I only create 1 instance of Library? Also, where should I put the code for checking out and returning books?

--- Update ---

If I don't instantiate an instance of Library, then I get a NullPointerException when trying to manipulate it in PatronThread.

[andbin]

So, how can I only create 1 instance of Library? Also, where should I put the code for checking out and returning books?
If I don't instantiate an instance of Library, then I get a NullPointerException when trying to manipulate it in PatronThread.

Ok, I can give some more hints:

1) You should have only 1 instance of Library and pass this instance to all PatronThread instances (how to pass the instance is up to you, there are some possible choices).

2) All synchronization and "blocking" behaviour should be encapsulated in Library, not in "clients". From your first code we can see two conceptual operations on the library: "getting a book" and "returning the book". Thus your Library class should expose two methods:

a) A method to get a book. It should check if there is an available book. If ok should return it, removing that from the "set" of available books. All this must be "atomic". If there is no book available, it should put the requesting thread to sleep.

b) A method to return a book. It should add (again "atomically") the book to the set of available books and should awake waiting threads.

[aussiemcgr]

Research Singletons (make sure you are researching synchronized ones). If I understand you correctly, the "best" way of ensuring that only one instance of Library exists is with Singletons.
An alternative would be like andbin suggested: by creating one instance before you create the threads and then passing that object to the threads.

[Norm]

Some comments on the code:

return books.size() == 5;

Always use the >= test. Or have other code that makes sure the size never goes past 5

for(int i = 0; i < 0; i++)

What will that loop do?

[mynorka]

Could I pass an instance of Library to the PatronThread constructor? And if I do that, wouldn't it still create a separate instance of Library for each Thread?
For example:

public PatronThread(String name, Library library) {
   super(name); 
   library = new Library()
}

[Norm]

Don't use a new statement. Assign the value of the passed reference to a class instance variable so it is available to the other methods in the class.

[mynorka]

I've modified the Library class to include two methods for retrieving and returning books, however, I keep getting a IllegalMonitorStateException whenever I try and run the program

public class Library {
	public static LinkedList<Integer> books; 
	public static Queue<Thread> tQueue = new LinkedList<Thread>();
	public static int currentBook = 0; 
 
	public Library() { 
		books = new LinkedList<Integer>(); 
		for(int i = 0; i < 5; i++)
			books.add(i + 1); 
	}
 
	public static synchronized void takeBook(Thread t){
		tQueue.add(t); 
		if(books.size() == 0){
			System.err.println(t.getName() + " entering FIFO queue to get a book. "
					+ "Library currently has " + books + "\n");
			try { Thread.currentThread().wait(); } 
			catch (InterruptedException e) { } 
		}
		else{
			//Checkout book from library
			currentBook = books.remove(); 
			System.err.println(tQueue.peek().getName() + " got book " 
						+ currentBook + ". Library now has " + books + "\n");
		}
	}
 
	public static void returnBook(Thread t) { 
		System.err.println(tQueue.remove().getName() + " entering FIFO queue to return"
				+ "book " + currentBook + books.add(currentBook) + 
				". Library now has " + books);
		Thread.currentThread().notify();
	}
 
	public boolean isFull() { return books.size() >= 5; }
	public boolean isEmpty() { return books.size() <= 0; }
}

[Norm]

I keep getting a IllegalMonitorStateException

Please copy the full text of the error message and paste it here. It has important info about the error.

Did you look up the what the API doc says about that error?

[mynorka]

Here's the full text

Exception in thread "t1" java.lang.IllegalMonitorStateException
	at java.lang.Object.notify(Native Method)
	at csu.mcdonald.Library.returnBook(Library.java:34)
	at csu.mcdonald.PatronThread.run(PatronThread.java:17)
Exception in thread "t8" java.lang.IllegalMonitorStateException
	at java.lang.Object.notify(Native Method)
	at csu.mcdonald.Library.returnBook(Library.java:34)
	at csu.mcdonald.PatronThread.run(PatronThread.java:17)

[Norm]

Did you look up the what the API doc says about that error? The problem is explained there.
Java Platform SE 7

[andbin]

I've modified the Library class to include two methods for retrieving and returning books, however, I keep getting a IllegalMonitorStateException whenever I try and run the program

takeBook is synchronized and static, so the lock is on the java.lang.Class object of Library class.
But in takeBook you invoke wait/notify on the (current) Thread instance. And you are not owning the lock on this Thread object.

wait/notify must be invoked on an object on which the current thread has acquired the lock.

P.S. sorry to say that, in my opinion, you are rather far from a good objective.

P.S.2: some points:
- Library should not have those static fields and takeBook/returnBook should not be static
- takeBook should not receive a Thread and in theory should return the book
- returnBook should not receive a Thread but in theory a book
- you have not yet specified/clarified the "fairness" policy you want to have. A lock is "fair" if, under contention, the order of acquisition strictly follows the order of request. Otherwise, if non-fair, the order is not guaranteed.