No idea what is happening...

[Billy Bob]

I'm working on this program, and I have no idea why I'm getting this output. It's like, 33% of the time it works flawlessly, 33% it works somewhat, and the other 33% it doesn't work at all. Here's what's going on, it's a producer/consumer type thing(bag of tasks pardigm to be exact). So my Master thread is making tasks, and putting them into a Bag, just like it's suppose too. I'm putting generic Object tasks into the bag, and the Bag class has get(), put(), and done(). Get and put's code is:

public synchronized void put(Object task) {
while(available == true){
try{
wait();
}
catch(InterruptedException e){}
}
this.task = task;
available = true;
notifyAll();
}
 
public synchronized Object get() {
while(available == false){
try{
wait();
}
catch(InterruptedException e){

}
}
available = false;
notifyAll();
return task;
}

very standard. I have a Task class, which just takes in data, and performs the necessary operations on them. Here's where I think the problem is. My worker class, the one that extends thread and has the run() method in it, isin't doing what it's suppose to, I don't think. Here's the run() method:

public void run(){
                System.out.println("worker" + i);
double value = ((Task)(tasks.get())).result;
Answer r = new Answer(value);
results.put(r);
}
 

It's suppose to get a double from inside the Task currently in the task Bag, create an Answer object, and put that object into the results Bag. The output I'm getting depends on the parameters(all ints) that I give the program. It will either caclulate and print the correct answer and then end properly, calculate and print the right answer and freeze, or not print the answer and freeze. Very confused, and any help is appreciated. I also am not too sure what the done() method is suppose to be doing, just part of the requirments.....
[ October 08, 2004: Message edited by: Billy Boob ]

[Maulin Vasavada]

Hi Billy,

It would helpful if you can post your whole code (if possible).

Also, I observe that in run() you have two variables,
tasks and results. Now the code that you have synchronization in put() and get() methods belongs to what object? Tasks and Results both? Are they separate objects? Because if they are separate objects all together than get() on one object and put() on second object wouldn't be synchronized...

Also where is done() method? I don't think its API's method. Where that came from? Please clarify and see if you can post complete "relavent" code.

Regards,
Maulin

[David Harkness]

My first suggestion (though yes, please post more code) would be to tag "available" as volatile. That would be easy to test, but if this is not an assignment in implementing synchronization yourself, I'd recommend using Slot, a one-element Channel from Doug Lea's Concurrent library.

This class provides what seems to be the functionality you're coding: a single-element blocking queue:

put(task) puts an item in

it blocks if there is already an item, waiting for that item to be removed

get() takes the item out

it blocks if the Slot is empty, waiting for an item to arrive

As to why your program is hanging, if a thread calls get() when there is no task available, but no other thread calls put(task), who tells the waiting thread to stop waiting?

[Billy Bob]

Hrmmmm.... I'll try to explain better this time. First off, here is an overview of all my classes:

Master - can't change the code here, but it puts things into a task bag, and gets things out of a result bag, so there are two seperate objects(task and result) of the same type.

Worker - This takes the two Bags as parameters, plus an int as a reference for which thread it is. So I have two bags called task and result. It also contains the run method I put up above.

Task - Takes in some parameters and does the operations on them, just has a constructor and works perfectly well.

Answer - Just like the Task, just stores some information, works fine.

Bag - 2 parameters, boolean variable called available and the Object to store. Has the get and put methods mentioned above, plus the done() method is suppose to be here but I have no idea what it's suppose to do, and not really worried with it at this moment.

The master thread creates the threads, puts the tasks into worker objects, and then starts the Worker(worker.start()). The Master then puts the task into the task bag, and then it gets the results from the result bag.

The run() method in the worker class is supposed to be doing the following: it goes into the task bag and gets the value stored in the object in the bag(which is of type Task). It then creates an Answer object, and stores the value into that object. Then it's supposed to put the Answer object into a results bag(different than the task bag). So I have 2 bags, result and task. I hope this makes alot more sense. I posted all the code above that really mattered, since 2 classes are nothign but containers, and I can't change one.
[ October 08, 2004: Message edited by: Billy Boob ]

[David Harkness]

Okay, I have a few questions and clarifications from your description:

"The master thread creates the threads, puts the tasks into worker objects, and then starts the Worker(worker.start()). The Master then puts the task into the task bag, and then it gets the results from the result bag." -- I assume "puts the tasks into worker objects" should be "gives the task and result bags to the worker objects", correct?

Does each worker get its own pair of bags?

Is Bag truly intended to hold only one item at a time?

Does Master put many Tasks into each task Bag or just one?

If only one Task is put into each task bag, does Master put it into the bag before or after starting each Worker?

How do the worker threads know that there are no more tasks to be had from their bags? I suspect this is the point of the done() method.

From Worker's run() method, it looks like each Worker gets its own pair of bags with one Task in the task Bag. It grabs that task, creates an Answer, puts it into the result Bag, and terminates.

It would also be helpful to see the output from a successful run of the program to help us understand what it does.

[Billy Bob]

1. "The master thread creates the threads, puts the tasks into worker objects, and then starts the Worker(worker.start()). The Master then puts the task into the task bag, and then it gets the results from the result bag." -- I assume "puts the tasks into worker objects" should be "gives the task and result bags to the worker objects", correct? Master creates the threads and starts them, then puts Tasks into the Bag called task.


Does each worker get its own pair of bags? Each worker gets a reference to the 2 bags created in the master thread.

Is Bag truly intended to hold only one item at a time?
Yeah, I believe it is. I have 2 bags, and each one can hold one element.

Does Master put many Tasks into each task Bag or just one?
Master puts many Tasks into 1 Bag! There are only ever 2 bags, called task and result, and these are created in Master.

If only one Task is put into each task bag, does Master put it into the bag before or after starting each Worker? It starts the threads, then puts the tasks into the task bag.

How do the worker threads know that there are no more tasks to be had from their bags? I suspect this is the point of the done() method. Your guess is as good as mine.


Sorry about all this confusion, the specifications for this suck, and I can't contact anyone cause they're all on break. Not to mention, I have limited knowledge of threads since people don't like to teach them.

[Mr. C Lamont Gilbert]

I do not like synchronized methods, i prefer synchronized blocks. But I guess thats a discussion for another day.

The member variables 'available' and 'task', how many methods can manipulate these variables?

lets have the code for the done method. I assume it too is synchronized?

[Billy Bob]

Only the get and put methods can manipulate them. And as stated somewhere above, I have no idea waht done is suppose to do, and has 0 lines of code for it. I thought it was just something general, for all I know it's just suppose to printout something, but I honestlty have no idea.

[Mr. C Lamont Gilbert]

how does the bag class have methods that you can not call?

I don't understand how you are running a program without being able to see the methods of a class which you have modified?

Perhaps you could explain again what is from this 'library' which you do not have source for, and what you are creating yourself?

[Billy Bob]

I didn't say anything about not being able to call it.... I said I don't know what it's suppose to do, therefor I can not write it. I have to do everything but program Master, which I have, and sometimes it works, sometimes it kinda works, sometimes it doesn't work at all, as I stated above. Honestly, it's not that confusing, i just can't figure out why it freezes sometimes but still manages to get the correct answer, and sometimes it will even go as far as printing it out.

[Henry Wong]

First of all, the bag code looks fine. The put() and get() methods looks like it should work. Second, if the code for the master and worker is not available, we can only speculate on the problem... but here is my speculation...

I am speculating that you have a weird case of a deadlock... maybe the master is trying to put a task in the task bag, but can't because there is already a task in the task bag... that task can't be removed because all the worker are trying to write a result in the result bag, but can't because there is already a result in the result bag... that result can't be removed because the master is... yadda yadda yadda... deadlock.

Without a way to test this -- meaning you can't touch the master or worker code -- I would suggest modifying the bags. Modify them to allow more than one task/result to be placed in it. By doing this, you won't block the master or workers at any bag, so they can go on to drain the other bag.

Hope this helps,
Henry
[ October 09, 2004: Message edited by: Henry Wong ]

[Billy Bob]

^ I sent you a PM. I posted the code to the worker class earlier, it was:

  
public void run(){          
      System.out.println("worker" + i);
      double value = ((Task)(tasks.get())).result;
      Answer r = new Answer(value);
      results.put(r);
}

that's it, all there is in there. Which is why I'm thinking it's not right. The code for the master class was supplied for us, and we're not allowed to change it. It creates an array of threads, creates the threads in a for loop and starts them in there too, then right after that it does a for loop using a command line argument to put Tasks into the task bag(tasks.put(Task(yadda yadda yadda))). Then it does another for loop, that does the same number of iterations as the one above, but instead gets Answers out of the result bag(ans = (Answer)results.get();. Then it calls tasks.done() (which is located in the Bag class, and I have no code for as of now). That's all it does, there are a few System.out.prints to show what is happening, but nothign else.
[ October 09, 2004: Message edited by: Billy Boob ]

[Henry Wong]

After reviewing the code for the worker, it does not change my speculation... I think both the master and all the workers are stuck in the put() method... but... I would like to requalify that without the master code, this is still speculation... we can only go so far with this discussion.

Anyway, here is a simple case... there are 5 workers. The master will write out 10 tasks requests, then go fetches the 10 results. The first 5 calls to put() goes fine as they are recieved by the workers. The 6th task is placed in the task bag, and the master blocks on the 7th... The 5 workers calls get(), process the answer, and calls put(). One worker suceeds, the other 4 blocks, since the master has not fetch the answers yet, it is still putting the 7th task... the one worker fetches another task... the master then blocks while writing the 8th task request... the one worker then blocks when it tries to write the 2nd answer...

Basically, the master is blocking on writing the 8th task, 4 of the workers is block on writing the first answer, and the 5 worker is blocked on writing its second answer. None of the workers can return from put because the master is blocked on the 8th task, and the master can't return from put because none of the workers are calling get() anymore.

Note: this is a simple case... but it can be much more complicated, depending on what the master is doing.

I would still suggest you rewrite the bag to use a container to confirm this hypothesis.

Hope this helps,
Henry

[Billy Bob]

This is giving me a headache. I changed the way I was doing things. I noticed in the Master class that they were importing java.util.Stack and it wasn't being used, so I decided to use it. Now my bag class does this:

  
public synchronized void put(Object task) {
a.push(task);
notifyAll();
}
 
public synchronized Object get() {

while(a.empty()){
try{
wait();
}
catch(InterruptedException e){

}
}
Object b = a.pop();
notifyAll();
return b;
         }
 
public synchronized void done() {
if(a.empty())
System.out.println("done");
notifyAll();
}

and I changed my worker class to do the following

  
public synchronized void done() {
if(a.empty())
System.out.println("done");
notifyAll();
}

I really thought this would work, but now running the same tests cases as earlier, it works about 66% of the time now. It doesn't block as much as it did before, so it has to be getting stuck in the get() method, since put() now just adds it to a stack.

[Henry Wong]

Again, without the code for the master, there is only so much we can accomplish... anyway...

The bag code looks fine. There are way too many notifications being sent around, but that shouldn't be causing the problem.

I don't have a clue what is the purpose of the done() method... but that doesn't matter anyway, since you are only printing out a message.

As for getting stuck in get(), there is nothing wrong with that either. Remember that your workers need to get a value, before it can calculate, and put the result. Getting stuck in get() just means that it is simply waiting for tasks.

As for using stack, just because you saw someone import it, that is not a very efficient way of picking a collection... ... but it looks like you used it correctly.

Sorry I can't be of any more help, but unless there is some code that you are not sharing, the master would be my guess at the next likely culprit.

Henry
[ October 10, 2004: Message edited by: Henry Wong ]

[Mr. C Lamont Gilbert]

Originally posted by Billy Boob:
...I have to do everything but program Master, which I have, and sometimes it works, sometimes it kinda works, sometimes it doesn't work at all, as I stated above. Honestly, it's not that confusing, i just can't figure out why it freezes sometimes but still manages to get the correct answer, and sometimes it will even go as far as printing it out.

May I see Master? or is it a class file? The new class seems like an improvement. May I ask however, who is creating the Stack instance 'a'? And when?
[ October 10, 2004: Message edited by: CL Gilbert ]

[Billy Bob]

 
...
    Bag tasks = new Bag();
    Bag results = new Bag();
...
    Thread worker[] = new Thread[threads];
    
    for(int i = 0; i < threads; i++) {
      worker[i] = new worker(tasks, results, i);
      worker[i].start();
    }
 
    for (int i = 1; i <= n; i += step)
      tasks.put(new Task(i, Math.min(i + step - 1, n)));
 
    Answer r;
    for (int i = 1; i <= n; i += step) {
      r = (Answer) results.get();
      result = result * r.val;
    }
 
   tasks.done();
 
 

other than some print statements and declaring ints for the command line args, that's it for master. However, I"m not allowed to change any of this code. And, Bag is declaring Stack a.
[ October 10, 2004: Message edited by: Billy Boob ]

[Henry Wong]

After looking at the master, I am convinced that my theory was correct. Since the bags originally only held a single value, depending on the value of threads, n, and step, you may deadlock since the master can't complete the puts.

It also looks like the master doesn't do any checking. It gets *exactly* the same number of object that it puts. This means that your worker should put exactly the same number of objects that it gets. Or again, the master will be stuck on the get().

Having said that... everything now looks fine... I don't have a clue what is wrong. I know you aren't allow to change the master, but I suggeest you do it anyway -- to put in debugging statments. You can always remove it later. There is no trick here -- either put in debugging messages, or use a debugger to trace it.

Henry

[Mr. C Lamont Gilbert]

How do you know its deadlocking? What jvm are you using? I believe on windows a ctrl-break will cause a thread dump which should show you which thread is blocking where.

1. You do know that System.out. is not thread safe, and should be called by only a single thread at a time? If you do not synchronize you calls to System.out your output will be missing some statements and me be otherwise corrupted.

2. There is no need to use notifyAll in the done method because there is nothing to notify there.

3. The get and put methods should use notify and not notifyAll since only 1 thread can proceed at a time.

4. There MUST be same number of threads as tasks since you are only using a thread once then disposing it. If you create less threads than tasks you will deadlock. If you create more threads than tasks, you will also deadlock, but all your tasks will complete before the deadlock.

change 'threads' to 'n'.

Thread worker[] = new Thread[n];
    
    for(int i = 0; i < n; i++) {
      worker[i] = new worker(tasks, results, i);
      worker[i].start();
    }
 
    for (int i = 1; i <= n; i += step)
      tasks.put(new Task(i, Math.min(i + step - 1, n)));
 
    Answer r;
    for (int i = 1; i <= n; i += step) {
      r = (Answer) results.get();
      result = result * r.val;
    }

[ October 10, 2004: Message edited by: CL Gilbert ]

[Henry Wong]

4. There MUST be same number of threads as tasks since you are only using a thread once then disposing it. If you create less threads than tasks you will deadlock. If you create more threads than tasks, you will also deadlock, but all your tasks will complete before the deadlock.

Wow! Good call! I completely missed this one myself. For some reason, I just assumed the workers was in a while loop.

Anyway, Billy, since you can't modify the master. Put the code for the worker in a loop... of course, now you have to use the done() method to wake up the workers and get them to exit.

Henry