线程调度 Thread Scheduling

当多个线程同时运行(可以同时运行）时，需要考虑线程调度的问题。确保所有重要的线程有运行的时间，越重要的线程获得更多的运行时间。

优先级Priorities

每个线程在创建时都有一个优先级，值为0到10。当多个线程准备好运行时，VM通常会先run优先级高的。java中10是最高优先级，0是最低优先级，5是默认的。

public final void setPriority(int newPriority)

和用户交互的线程需要较高优先级，这样才能尽快响应用户。在后台计算的线程可以设置较低优先级。能够很快完成的任务可以设置较高优先级。需要耗时较长的线程可以设置较低优先级。

public void calculateDigest() {
 ListCallbackDigest cb = new ListCallbackDigest(filename);
 cb.addDigestListener(this);
 Thread t = new Thread(cb);
 //give higher priorities to the threads that do the calculating than the main program that spawns the threads
 t.setPriority(8);
 t.start();
}

一般，要尽量避免给线程设置过高的优先级，这样会增加其他低优先级线程starving的风险。

Preemption

每个虚拟机都有一个线程调度器，有两种线程调度方式： preemptive and cooperative.

A preemptive thread scheduler determines when a thread has had its fair share of CPU time, pauses that thread, and then hands off control of the CPU to a different thread.
A cooperative thread scheduler waits for the running thread to pause itself before handing off control of the CPU to a different thread.
A virtual machine that uses cooperative thread scheduling is much more susceptible to thread starvation than a virtual machine that uses preemptive thread scheduling, because one high-priority, uncooperative thread can hog an entire CPU.
一个高优先级、不协作的线程可以贪婪的占用整个cpu

The higher priority thread preempts the lower-priority thread.
较高优先级的线程会抢占低优先级的线程。

There are 10 ways a thread can pause in favor of other threads or indicate that it is ready to pause. These are:
? It can block on I/O.
? It can block on a synchronized object.
? It can yield.
? It can go to sleep.
? It can join another thread.
? It can wait on an object.
? It can finish.
? It can be preempted by a higher-priority thread.
? It can be suspended.
? It can stop.

Blocking

Blocking occurs any time a thread has to stop and wait for a resource it doesn’t have.
当一个线程必须停下来等待一个它没有的资源时就会阻塞。

网络程序中一个线程在发生IO阻塞时会自动放弃CPU的控制权。当线程进入同步方法或同步块时也会发生阻塞。
IO阻塞不会导致线程死锁，因为IO阻塞unblock的时候线程就能继续执行，或者IO阻塞抛出IOException，线程会跳出同步块。
当第一个线程等待另一个线程占有的锁，而第二个线程也在等待第一个线程占有的锁时，就会出现死锁。

Yielding

让一个线程放弃对cpu的控制的另一种方法就是显示的yield，通过调用静态方法： Thread.yield() 。这会给虚拟机发出信号：
it can run another thread if one is ready to run.
Yielding 不会释放线程占用的锁。因此，当一个线程yield时，不应该同步任何对象，否则可能造成死锁。

public void run() {
 while (true) {
 // Do the thread's work...
 Thread.yield(); //This gives other threads of the same priority the opportunity to run.
 }
}

Sleeping

Sleeping is a more powerful form of yielding.
Yielding 意味着这个线程愿意暂停，让其他相同优先级的线程有机会运行。一个sleep的线程会立刻暂停，无论其他线程是否准备好运行。
一个线程sleep后，让其他优先级较低的线程也有机会运行。 然而，一个sleep的线程会占有它获取的锁，这样其他需要这些锁的线程将会block，即使cpu可用。因此，要避免在同步方法或者同步块中sleep。

Joining threads

有时一个线程需要得到另一个线程的结果。例如当web浏览器在一个线程中加载一个HTML页面时，可能会产生几个线程去获取页面中的图片。如果img元素没有设置高度和宽度属性，主线程就需要等待所有的图片加载完后才显示整个页面。Java 提供了3个 join() 方法，允许第一个线程等待另一个线程执行完，然后继续执行第一个线程。
one thread to wait for another thread to finish before continuing.

public final void join() throws InterruptedException
public final void join(long milliseconds) throws InterruptedException
public final void join(long milliseconds, int nanoseconds) throws InterruptedException

The joining thread (i.e., the one that invokes the join() method) waits for the joined thread (i.e, the one whose join() method is invoked) to finish.

下面的代码，从一个随机生成的double数组中查找最大值、最小值以及中间值。You spawn a new thread to sort the array, then join to that thread to await its results.

double[] array = new double[10000]; // 1
for (int i = 0; i < array.length; i++) { // 2
  array[i] = Math.random(); // 3
} // 4
SortThread t = new SortThread(array); // 5
t.start(); // 6
try { // 7
 t.join(); // 8  joins the current thread to the sorting thread
 System.out.println("Minimum: " + array[0]); // 9
 System.out.println("Median: " + array[array.length/2]); // 10
 System.out.println("Maximum: " + array[array.length-1]); // 11
} catch (InterruptedException ex) { // 12
 //A thread that’s joined to another thread can be interrupted just like a sleeping thread if
 //some other thread invokes its interrupt() method
} 

例子

import javax.xml.bind.DatatypeConverter;
public class JoinDigestUserInterface {
 public static void main(String[] args) {
 ReturnDigest[] digestThreads = new ReturnDigest[args.length];
 for (int i = 0; i < args.length; i++) {
 // Calculate the digest
 digestThreads[i] = new ReturnDigest(args[i]);
 digestThreads[i].start();
 }
 for (int i = 0; i < args.length; i++) {
 try {
 digestThreads[i].join();
 // Now print the result
 StringBuffer result = new StringBuffer(args[i]);
 result.append(": ");
 byte[] digest = digestThreads[i].getDigest();
 result.append(DatatypeConverter.printHexBinary(digest));
 System.out.println(result);
 } catch (InterruptedException ex) {
 System.err.println("Thread Interrupted before completion");
 }
 }
 }
}

Joining is perhaps not as important as it was prior to Java 5. In particular, many designs that used to require join() can now more easily be implemented using an Executor and a Future instead.

Waiting on an object

一个线程可以wait一个它已经锁定的对象，当waiting时，它会释放对象上的锁，直到它被其他线程通知（notified).另一个线程改变了这个对象，并通知等待这个对象的线程。
This differs from joining in that neither the waiting nor the notifying thread has to finish before the other thread can continue.Waiting pauses execution until an object or resource reaches a certain state. Joining pauses execution until a thread finishes.

通过等待一个对象（Waiting on an object ）让一个线程暂停（pause）鲜有人知，因为这没有在线程中调用它的方法。为了等待一个特定的对象，想要暂停的线程必须先使用synchronized获取对象的锁，然后调用这个对象的wait()方法。

public final void wait() throws InterruptedException
public final void wait(long milliseconds) throws InterruptedException
public final void wait(long milliseconds, int nanoseconds)
throws InterruptedException

这几个方法在 java.lang.Object中定义，它们可以被任意类的任意对象调用。When one of these methods is invoked, the thread that invoked it releases the lock on the object it’s waiting on (though not any locks it possesses on other objects) and goes to sleep. It remains asleep until one of three things happens:
? The timeout expires.
? The thread is interrupted.
? The object is notified.

Notification occurs when some other thread invokes the notify() or notifyAll() method on the object on which the thread is waiting. Both of these methods are in the java.lang.Object class:

public final void notify()
public final void notifyAll()

必须是线程等待的对象上调用notify() notifyAll() ，而不是线程自身。 在通知一个对象前，线程必须先使用synchronized方法或块来获取对象的锁。notify() 方法会从所有等待对象的线程列表（threads waiting on the object）中随机的选择一个线程，唤醒它。 notifyAll() 则会唤醒所有等待对象的线程。
Once a waiting thread is notified, it attempts to regain the lock of the object it was waiting on. If it succeeds, execution resumes with the statement immediately following the invocation of wait(). If it fails, it blocks on the object until its lock becomes available; then execution resumes with the statement immediately following the invocation of wait().

例如，假设有一个线程从socket连接中读取一个jar。
For example, suppose one thread is reading a JAR archive from a network connection.
The first entry in the archive is the manifest file. Another thread might be interested in the contents of the manifest file even before the rest of the archive is available. The interested thread could create a custom ManifestFile object, pass a reference to this
object to the thread that would read the JAR archive, and wait on it. The thread reading the archive would first fill the ManifestFile with entries from the stream, then notify the ManifestFile, then continue reading the rest of the JAR archive. When the reader thread notified the ManifestFile, the original thread would wake up and do whatever it planned to do with the now fully prepared ManifestFile object. The first thread works something like this:

ManifestFile m = new ManifestFile();
JarThread t = new JarThread(m, in);
synchronized (m) {
t.start();
try {
m.wait();
// work with the manifest file...
} catch (InterruptedException ex) {
// handle exception...
}
}

The JarThread class works like this:

ManifestFile theManifest;
InputStream in;
public JarThread(Manifest m, InputStream in) {
theManifest = m;
this.in= in;
}
@Override
public void run() {
synchronized (theManifest) {
// read the manifest from the stream in...
theManifest.notify();
}
// read the rest of the stream...
} 

Waiting and notification are more commonly used when multiple threads want to wait on the same object.
For example, one thread may be reading a web server logfile in which each line contains one entry to be processed. Each line is placed in a java.util.List as it’s read. Several threads wait on the List to process entries as they’re added. Every time an entry is added, the waiting threads are notified using the notifyAll() method. If more than one thread is waiting on an object, notifyAll() is preferred, because there’s no way to select which thread to notify. When all threads waiting on one object are notified, all will wake up and try to get the lock on the object. However, only one can succeed immediately. That one continues; the rest are blocked until the first one releases the lock. If several threads are all waiting on the same object, a significant amount of time may pass before the last one gets its turn at the lock on the object and continues.
It’s entirely possible that the object on which the thread was waiting will once again have been placed in an unacceptable state during this time. Thus, you’ll generally put the call to wait() in a loop that checks the current state of the object. Do not assume that just because the thread was notified, the object is now in the correct state. Check it explicitly if you can’t guarantee that once the object reaches a correct state it will never again reach an incorrect state. For example, this is how the client threads waiting on the logfile entries might look:

private List entries;
public void processEntry() {
synchronized (entries) { // must synchronize on the object we wait on
while (entries.isEmpty()) {
try {
entries.wait();
// We stopped waiting because entries.size() became non-zero
// However we don't know that it's still non-zero so we
// pass through the loop again to test its state now.
} catch (InterruptedException ex) {
// If interrupted, the last entry has been processed so
return;
}
}
String entry = entries.remove(entries.size()-1);
// process this entry...
}
}

The code reading the logfile and adding entries to the list might look something like this:

public void readLogFile() {
while (true) {
String entry = log.getNextEntry();
if (entry == null) {
// There are no more entries to add to the list so
// we interrupt all threads that are still waiting.
// Otherwise, they'll wait forever.
for (Thread thread : threads) thread.interrupt();
break;
}
synchronized (entries) {
entries.add(0, entry);
entries.notifyAll();
}
}
}

Finish

The final way a thread can give up control of the CPU in an orderly fashion is by finishing.
When the run() method returns, the thread dies and other threads can take over. In network applications, this tends to occur with threads that wrap a single blocking operation, such as downloading a file from a server, so that the rest of the application won’t be blocked.
Otherwise, if your run() method is so simple that it always finishes quickly enough without blocking, there’s a very real question of whether you should spawn a thread at all. There’s a nontrivial amount of overhead for the virtual machine in setting up and
tearing down threads. If a thread is finishing in a small fraction of a second anyway, chances are it would finish even faster if you used a simple method call rather than a separate thread.