1/1/00 (sent 1/2/00) Steve: Well, there went all the Y2K horror predictions. I was using the international Y2K coordination site, and the whole time it showed nothing, nothing, nothing. In fact, we got a call from Berlin at 5:30 pm Dec 31, 12:31 am Jan 1 Berlin time, and the news was: lights are still on. The reason for this e-mail, however, is to ask about my random walk Java program. I got it to work, but I want to know if there are better ways to do some of the things I did. So I have a series of questions, starting with a description of the work I got done. The project is an applet RandomWalk that starts up 8 (or any number) of threads. Each thread carries out a random walk in the plane, painting its own color as it goes. The applet has a suspend boolean for each thread, and has buttons to toggle this boolean. Whether or not the thread waits depends on the boolean. Initially, this was a single file, using suspend() and resume(). It didn't work reliably, hanging fairly often. I converted to requests for painting a point by a given thread (identified by my own thread number 0, 1, ...). The requests were put into a queue. After generating a request, I called repaint(). Then repaint() would remove as many reqests as there were and do a fillOval to paint them. After each insertion into the queue, I called repaint(), so there were equal numbers of these. In one temporary run I monitored the number of requests removed from the queue during paint() and got data like the following, for different lengths of runs: Number of requests removed at one time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ================================================================= 1 172 4 1 0 0 0 0 0 0 0 0 0 0 0 8 2381 67 4 1 0 0 0 0 0 0 0 0 0 0 19 8133 408 55 22 9 9 3 2 0 0 0 0 0 0 1 4547 3 1 0 0 0 0 0 0 0 0 0 0 0 1 754 18 0 1 0 0 0 0 0 0 0 0 0 0 227 36930 847 345 182 78 42 19 6 1 1 0 0 0 0 61 32098 879 61 17 4 3 0 0 0 1 0 0 0 0 4194 412181 46800 10982 4526 2517 1460 690 285 110 59 25 14 9 1 You get the picture: highly variable data, mostly just one request removed, sometimes none, sometimes many. For me the interesting part is that there are more removals than calls to paint(). Some of the calls to repaint() must overlap and be answered (when the system gets around to it) by a single call to paint(). Does this sound right? (QUESTION 1.) ------------------------------------------------------- This version still hung often, just like before. I converted to the use of wait() and notify(), mimicing D&D. This didn't work right, since notify() sometimes started up the wrong thread. (I didn't ever test or figure out if D&D's code had this problem.) So a switch from notify() to notifyAll() (following the advice of Gosling) worked. I now had a working random walk program that so far has never once failed or hung or had any other problem (on a variety of Java virtual machines, including M-M-M-Microsoft). Next I wanted to convert the queue to a separate class. (Even I can figure out it should be a separate object.) I made up a separate Queue class with its own main function. (Gosling recommends this, and it seems like a very good idea for testing. You just leave the main there afterwards.) So now I have two files: an applet RandomWalk and a class Queue. My queue used an array of "entry"s which are an Entry class with essentially just 3 integers. Eventually I figured out that I needed a completely separate Entry class, so that RandomWalk and Queue would be using the same Entry. (I got these three to work fine, just like before.) In this case do you think I have to have a separate class for the type of object that my queue wants to return? (QUESTION 2. Of course I picture that I could just use an array of 3 integers.) --------------------------------------------------------------- So far pretty simple. Now I wanted a separate Walk class (extending Thread) for each of the random walks. This separation introduced all manner of problems. After reflection, the problems seem mainly to involve communication between separate classes, and especially communication between a thread and the process that created it. I eventually found a fix for every problem, but mostly I want to know if there are better ways. I started with Walk and a minimal separate class creating two Walk threads and doing increasingly complicated things. This was good strategy: I was making so many kinds of errors that I don't think I could ever have gotten it to work without finding conceptual (and other) errors one at a time. So I had random walks going that would spit out (using System.out.print) numbers for locations to paint. Now I wanted to add the queue. It became clear to me that somehow the Walk thread and the RandomWalk applet must reference the same queue. I had a lot of trouble thinking of a solution: Inside the RandomWalk class: // At the top level: public Queue q = new Queue(500); // queue in sep class // Inside start(), when I instantiate each Walk class: walk[i] = new Walk(400, 100, 200, 200, 400, q); (I'm passing a reference to my queue to each thread in the thread's constructor.) Inside the Walk class: private Queue q; // separate queue, for paint requests public Walk(int hc, int dc, int tc, int xc, int yc, Queue qc) { h = hc; d = dc; t = tc; x = xc; y = yc; q = qc; threadNum = num++; } (In this way the local variable q is a reference to the same queue that RandomWalk is using.) Is there an easier/better way to get these two classes to agree on the same queue? (QUESTION 3.) ------------------------------------------------------------- Now inside the actionPerformed of RandomWalk, in response a user button to suspend/resume a thread, I can call a method in the proper thread to set or reset a local suspend variable in the Walk method. That seems straightforward. I can also do a notifyAll() from RandomWalk to the proper thread to get it out of its wait state. But inside Walk, after generating a point, I wanted to insert into the queue and then call repaint(), as before. This is a question of communication back from the thread to the parent of the thread. The only solution I could imagine was to start _another_ thread inside RandomWalk that would call repaint() every 0.2 seconds (or whatever). So at fixed intervals I call repaint(), and then in paint() remove all pending requests from the queue to paint a point. Is there any other way to do this? (QUESTION 4. I sort of understand your double buffering concept, and it seems essentially the same at this, at least in terms of communication between threads and the parent (or lack thereof), though with double buffering the threads and the parent need a common screen into which the threads will add points for painting, and which will be painted periodically.) --------------------------------------------------------- My final problem involved something that was not an essential component. In my original code, the rate at which a thread produced new random points was inversely proportional to the number of active threads. So I wanted each Thread to know (when it chose to ask) how many threads were currently active. I used the same trick as with the queue, creating a separate class ActiveThreads from within the RandomWalk class, and then passing a reference to this class to each Walk thread as it is created. Inside RandomWalk: private ActiveThreads a = new ActiveThreads(); walk[i] = new Walk(400, 100, 200, 200, 400, q, a); Inside Walk: private ActiveThreads a; // tell # of active threads public Walk(int hc, int dc, int tc, int xc, int yc, Queue qc, ActiveThreads ac) { h = hc; d = dc; t = tc; x = xc; y = yc; q = qc; a = ac; threadNum = num++; } int act = a.getActiveThreads(); I think that in another solution I could use a method within Walk, called from RandomWalk, that would inform each thread each time there was a change to the number of threads. (Doesn't sound as good.) Again, is there some other way to do this? (QUESTION 5. Hmmm. Static variable for number of threads within Walk?) WHeh! Well, that's all. You don't need to answer all this if you don't want to. -- Neal ---------------------------------------------------- From srobbins@cs.utsa.edu Sun Jan 2 17:52:58 2000 Date: Sun, 2 Jan 2000 17:54:18 -0600 From: srobbins@cs.utsa.edu (Steven Robbins) To: wagner@jazz.cs.utsa.edu Subject: Random Walk I will try to hit all of your questions and add a few comments. I asume you have a copy of your original email Q1: yes (number of calls to paint and repaint) Q2: An array is OK, but an object is better since the three quantities are really different type of things even though they are all ints. Q3: Passing the queue is good. An alternative (but I don't like it) is to make the Queue class static which means there is only one copy and you would not have to pass it to anything. This sort of makes the Queue class like a "global variable" and that is why I don't like it. Q4: If the thread is to call repaint, one way to do this is to pass the Applet at a parameter. A better way would be to use an interface with a Display method. The Applet would implement this interface. Q5: The static variable nu in Walk is fine. Walk could have a static methow which returns this value to any object that needs is. Other comments: The 500 for the queue size is rather arbitrary. If you used a Vector instead of an array, you would not have to predetermine a size or do any modulo arithmetic. The Vector class allows you to put something in or take out of an arbitray location. You only need to do beginnign or end. The convention is to use all uppercase variables only for constants (declared with final). Thus your QSIZE should be qSize or something like that. The standard for changing boolean variables is to have a pair of methods: void setX(boolean val) and boolean getX(); Thus, your setSuspend and resetSuspend should be one method: void setSuspend(boolean val) which sets the suspend variable to val. Need to go pick up pizza. Any more questions? Steve