Somebody asked me this week about Java threads. In particular, they wanted to know how they were scheduled.
Now, before I go any further, I should state quite clearly that this is not my sphere of expertise; but I am perfectly capable of using Google and that being the case, the following is a summary of what I found.
The first thing to note about scheduling threads in Java is that it appears to use a very simple algorithm. The scheduler, when called to make a decision, simply picks the thread with the highest priority and lets it run. And if it were that simple, I wouldn’t be writing an article about it!
Because, in fact, what Java does is to hand off these decisions to the native operating system scheduler. Native operating system schedulers are anything but simple.
As a first cut, let’s look at the situation where you have a number of threads all with the same priority. One of them gets to run. We’ll not bother about how this first thread gets to run. It doesn’t really matter, because the important question is: “What stops it running and when it does stop, how does the scheduler pick from amongst the remaining threads all of which have the same priority?”
Well, the thread can stop running either voluntarily or it can be pre-empted by a thread of higher priority (which we’ll ignore for the purposes of this article) or it can come to the end of its time slice. This latter prevents ‘greedy’ threads from hogging the processor and is the way that nearly all current operating systems work.
Or it can terminate, of course, but we’re not concerned with that case here.
Threads stop running voluntarily due to calls to sleep(), wait() or join(). I discuss each of these below, after dealing with the way that threads are scheduled.
So now, either because of a thread yielding volutarily or because of a thread exhausting its time slice, we have a situation where the scheduler has to pick another thread to run amongst many, all with the same priority. This can be done in many different ways. For example, the next thread might be picked on a round-robin basis. In other words, the scheduler might view all the threads as being in some sort of queue and simply pick the next one in the queue.
Now, therefore, we have to worry about how threads are put into the queue. Is the queue simply ordered on a first-come, first-served basis? Or are the threads queued on the basis of how much time they’ve spent on the processor, with the least-used thread at the head? Or might they be queued on the basis of how long it has been since the last time they were given a chance to run? The Java specification has nothing to say about any of this, as far as I can tell. It just depends on the native operating system.
So what can we say for certain? We can say that threads that are available to be run and that have the same priority will be selected by the native operating system on the basis of some criterion or mixture of criteria that aim to give each thread an equal chance in life. Threads that have a higher priority will, of course, always take precedence. Just like real life, really.
But of course, in all this, we have only been talking about threads that are available to run. Some threads might not be in this state. For example, they could be waiting for IO, or they might have voluntarily exempted themselves from the pool of runnable threads. For example, they could have done everything that they usefully can until some other thread has completed some task that would allow them to carry on. You know the scenario. The glazier can’t continue until the carpenter’s finished. So the glazier goes off to get a cup of tea whilst the carpenter gets on with the job. When the carpenter’s finished, he shouts into the kitchen, “Oy! I’ve done now, you can carry on!”
Let’s put this into more technical terms. Threads can be in one of a number of states. These are the ones given in the Thread.State Java documentation:
- NEW: the thread exists, but has not yet been started
- RUNNABLE: a thread that is available to run on the processor
- BLOCKED: waiting for a monitor (lock)
- WAITING: the thread is waiting indefinitely due to a call to wait() or join()
- TIMED_WAITING: the thread is waiting for a specific time due to a call to sleep(<timeout>) or wait(<timeout>) or join(<timeout>)
- TERMINATED: the thread has completed
Only threads in the RUNNABLE state are available to the scheduler.
So a programmer can make a thread unavailable to the scheduler by calling one of the following:
There are actually some others, but these three will do for now.
Of these, sleep() is the easiest to understand. It simply takes the thread out of the pool of RUNNABLE threads for a specific period of time. When that time is over, the thread returns to the RUNNABLE state.
The method wait(), on the other hand, twiddles its thumbs until some other thread calls notifyAll(), at which point the thread will check to see if this was the event it was waiting for and, if it is, it will make itself RUNNABLE again. There is also a notify() method, but I’m ignoring that for the purposes of this article.
In contrast to wait(), the join() method waits for some other thread to finish. In other words, the event it is waiting for is the completion of another thread rather than the issuing of a notification.
As I’ve mentioned, both wait() and join() have versions that restrict the length of time that they are prepared to wait. It’s up to the programmer to decide which version of wait() or join() best suits the current purpose.
Outside of the programmer’s control is the situation where a thread is blocked on some task like IO. So if, for example, a thread is waiting to stream some data to disk, it will be in the BLOCKED state until the write is complete – and therefore it will not be in the pool of RUNNABLE threads until it stops blocking. All the java.io.* methods play nicely in this respect and yield whilst carrying out blocking IO operations.
That’s it. That’s what I’ve found out – or think that I’ve found out. If there are any mistakes and anyone knows better, I’ll be happy to hear from you and correct whatever I’ve got wrong.