作者：杨兴强
原文来源：开点工作室（ID：kaidiancs）

一．从一个例子开始

看着Java线程执行起来的那种任性和随意，我们不免会问：是谁在主导Java线程的执行？它按照什么样的策略来调度Java线程？本文将带着这样的问题，探讨Java线程的调度机制。

程序的问题还是先从代码说起吧,下面是一个广泛引用的例子：
假设某航班有100张余票，现有10个窗口（线程）同时卖这100张票。下面程序实现了10个线程并发执行的过程。
// sched 类
// 创建多线程模拟多窗口售票，演示java线程的并发运行状况，说明java和操作系统的线程调度策略

class sched implements Runnable {
finalintTICKET_MAXNUM = 500;
// 总票数
finalintTHREAD_NUM = 10;
// 线程（售票窗口）数量
publicintcount = 0;
// 已售出票数
privateintThreadNo[];
// 第i张票的线程的序号是TicketThreadNo[i]，-1表示未售出
privateintTicketNum[];
// 记录每个线程售出的票数,说明每个线程占用的CPU时间
privateintThreadId[];
// ThreadId[i]存放第i个线程的Id号
privateintNewThreadNo;
// 将要创建的线程的序号，初值为0
double d;
// 工作变量,仅用于消耗线程的CPU时间

 public sched() {
      inti;
      ThreadNo = newint[TICKET_MAXNUM];
      for (i = 0; i < TICKET_MAXNUM; i++)
           ThreadNo[i] = -1;
      TicketNum = newint[THREAD_NUM];
      for (i = 0; i < THREAD_NUM; i++)
           TicketNum[i] = 0;
      NewThreadNo = 0;
      ThreadId = newint[THREAD_NUM];
 }

// sell()方法描述一次售票操作，synchronized 用于实现对共享变量count的互斥
 publicsynchronizedvoid sell() {
      if (count < TICKET_MAXNUM) {
           ThreadNo[count] = getNo((int)Thread.currentThread().getId());

//System.out.println(sold[count]+ "号线程售第" + count + "张票");
count++;
//delay();
}
}
// 从线程的id号得到线程的序号
privateint getNo(intid) {
int i;
for (i=0; i<THREAD_NUM; i++)
if (ThreadId[i] == id)
returni;
return -1;
}

 publicvoid run() {

//Thread.currentThread().setPriority(NewThreadNo+1);
ThreadId[NewThreadNo++] = (int)Thread.currentThread().getId();
while (count < TICKET_MAXNUM) // 只要有票，线程（窗口）就不停售票
sell();
}
// 仅用于消耗CPU时间，表示售票所用时间
privatevoid delay(){
d = 5000000;
while (d > 0)
d = d - 1;
}
// 累计并打印每个线程卖的票数
publicvoid accumulate() {
int i;
for (i=0; i<TICKET_MAXNUM; i++)
TicketNum[ThreadNo[i]]++;
for (i=0; i<THREAD_NUM; i++)
System.out.printf("%3d号线程卖：%-4d张票\n", i, TicketNum[i]);
}
}
// 主程序
publicclass jsched {
publicstaticvoid main(String[] args) {
inti;
sched t = new sched();
for (i = 0; i < t.THREAD_NUM; i++) {
new Thread(t).start();
}
while (t.count < t.TICKET_MAXNUM) //等待票都卖完
Thread.yield();
t.accumulate();
}
}
上面例子中,主线程依次创建并启动10个线程,他们执行相同的程序run()，其作用就是不停地调用sell()以售票。NewThreadNo表示新创建线程的序号，初值为0，每创建一个新线程，加1。售票时记录每张票都是由哪个线程售出的，线程序号存于ThreadNo[]中。线程Id是每个线程在Java中的唯一标识，可以通过调用Thread.currentThread().getId()获得当前线程的Id，并由此知道正在执行当前程序的线程是哪一个线程。序号为i的线程的Id存在ThreadId[i]中，该数组记录了线程序号和Id号之间的对应关系。主线程最后统计各线程分别卖了多少张票。

在并发环境下，线程之间的运行次序总是呈现某种随机性，程序的运行结果往往是不固定的。所以我们观察程序运行结果时，需要多次运行，才能总结出大概的运行规律。当然有时也许根本就没有规律。

多次运行以上程序，较典型的结果如下：
0号线程卖：100 张票
1号线程卖：0 张票
2号线程卖：0 张票
3号线程卖：0 张票
4号线程卖：0 张票
5号线程卖：0 张票
6号线程卖：0 张票
7号线程卖：0 张票
8号线程卖：0 张票
9号线程卖：0 张票

票都被线程0卖了，其他线程好像没干活，系统采用的像是先来先服务的调度原则。尽管10个线程是并发执行的，但主线程是依次创建各个线程的。当创建了线程0之后，主线程就和线程0并发执行了。所以线程0一般情况下都先于其他线程执行。但这不能说明系统采用的是先来先服务策略。由于卖票这活儿太简单，还没等其他线程开始执行，线程0就把票卖光了。这好办，只要在sell()方法中加上延迟，把delay()函数调用前面的注释去掉，即可人为增加卖票的工作量。修改后多次运行程序，较典型的结果如下：

0号线程卖：9 张票
1号线程卖：8 张票
2号线程卖：18 张票
3号线程卖：17 张票
4号线程卖：17 张票
5号线程卖：7 张票
6号线程卖：7 张票
7号线程卖：5 张票
8号线程卖：5 张票
9号线程卖：7 张票

此时各线程都参与了卖票，而且能看到他们交替执行。系统采用的又像是时间片轮转的调度策略。

然而Java的Thread类提供了设置线程优先级的方法，每个线程初始创建时会被赋予一个默认的优先级。那么线程的优先级又起到了什么作用呢？

现在我们去掉run()方法中对设置优先级的方法setPriority()的注释，该方法将10个线程的优先级分别设为1至10，这是Java支持的10个不同级别的优先级。多次运行程序，每个线程卖出的票数都不一样，较典型的运行结果如下：
......
0号线程卖：8 张票
1号线程卖：2 张票
2号线程卖：1 张票
3号线程卖：10 张票
4号线程卖：1 张票
5号线程卖：0 张票
6号线程卖：5 张票
7号线程卖：73 张票
8号线程卖：0 张票
9号线程卖：0 张票

很明显，7号线程卖了最多的票，这是因为7号线程的优先级较高。然而8、9号线程的优先级更高，却没卖一张票。从运行结果上看，优先级起了一定的作用，但并不绝对，有时甚至不被理会。

多次改变程序中线程的数量，票的数量、卖票的延迟时间、线程的优先级等各种参数，我们试图观察线程的调度方法，但仍然无法把握Java线程的调度策略。唯一可以确定的是：它像是采用了轮转法，但不是完全的轮转，因为经常有线程被轮空好几次；它像是采用了优先级的调度策略，但又不是完全按优先级的次序分配CPU，因为最高优先级的线程也常被忽略；它有时还像先来先服务的调度。

以上我们看到的Java线程的执行过程仅仅是在Windows XP平台上的运行情况。事实上，Java在不同的发展时期、不同的平台上，其线程调度的策略也是不同的。要想概括Java的线程调度方法，不是一件容易的事，还是让我们沿着Java虚拟机实现的踪迹来探寻和理解Java线程的调度方法吧。

二．早期的JVM线程调度策略

很多网站或课本上都是这样介绍java线程的调度策略的[1]：

（1）JVM使用抢占的、基于优先权的调度策略；
（2）每个线程都有优先级，JVM总是选择最高优先级的线程执行；
（3）若果两个线程具有相同的优先级，则采用FIFO的调度顺序。

在早期的java1.1中，JVM自己实现线程调度，而不依赖于底层的平台。绿色线程（用户级线程）[2]是JVM使用的唯一的线程模型（至少是在solaris平台上），其线程调度采用的应该就是上述这种调度策略。

绿色线程的执行时间由线程本身来控制，线程自身工作告一段落后，要主动告知系统切换到另一个线程上。其特点是实现简单，不需要专门的硬件支持，切换操作对线程自身来说是预先可知的。

因为绿色线程库是用户级的，并且Solaris一次只能处理一个绿色线程，即Java运行时采用多对一的线程模型，所以会导致如下问题：（1）Java应用程序不能与Solaris环境中的多线程技术互操作，就是说Solaris管理不了Java线程；（2）Java线程不能在多处理机上并行执行；（3）Java 应用不能享用操作系统提供的并发性。由于绿色线程的这些限制，在java1.2之后的版本中放弃了该模型，而采用本地线程（Native threads，是指使用操作系统本地的线程库建立和管理的线程），即将Java线程连接到本地线程上，主要由底层平台实现线程的调度[3]。

三．依托底层平台的Java线程调度策略

Java语言规范和Java虚拟机规范是Java的重要文档，可惜的是他们都没有说明Java线程的调度问题。或许从Java的角度看，线程并不是Java最基本的内容。毕竟Thread类也仅仅是Java一个特定的类而已。

终于在Java SE 8 API规范的Thread类说明中算是找到了线程调度的有关描述：每个线程有一个优先级（从1级到10级），较高优先级的线程比低优先级线程先执行[4]。程序员可以通过Thread.setPriority(int)设置线程的优先级，默认的优先级是NORM_PRIORITY。Java SE 还声明JVM可以任何方式实现线程的优先级，甚至忽略它的存在。这可以看做Java SE提供给程序员的关于线程调度的策略，恐怕就这些了。为什么后来Java关于线程调度说得这么少？是因为它不想再管这事儿了，再说就是多嘴。

我们是通过Java创建的线程，线程调度的事儿Java是脱不开的。那Java又是如何将线程调度交给底层的操作系统去做呢？下面我们将跟随JVM虚拟机底层平台上的实现，说明Java线程的调度策略。

1. Solaris平台上的JVM线程调度策略先说Solaris本身的线程调度。在第9版之前，Solaris 采用M:N的线程模型，即M个本地线程映射到N个内核级线程(LWP，LWP和内核级线程是一一对应的)上。当本地线程连接到一个LWP上时，它才有机会获得CPU使用权。虽然Solaris提供了改变LWP的优先权的系统调用，但是由于本地线程与LWP的连接是动态的、不固定的。一个本地线程过一会儿可能会连接到另一个LWP上。因而Solaris没有可靠的方法改变本地线程的优先权。

再说Java线程。既然Java底层的运行平台提供了强大的线程管理能力，Java就没有理由再自己进行线程的管理和调度了。于是JVM放弃了绿色线程的实现机制，将每个Java线程一对一映射到Solaris平台上的一个本地线程上，并将线程调度交由本地线程的调度程序。由于Java线程是与本地线程是一对一地绑在一起的，所以改变Java线程的优先权也不会有可靠地运行结果。

线程映射.jpg

尽管如此，Solaris早期版本还是尽量实现了基本的用户模式下的抢占。系统维护这一条戒律：就绪队列上任何线程的优先级必须小于等于正在运行的线程，否则，优先级最低的正在运行的线程将被剥夺运行的机会，即将其对应的LWP让给优先级高的本地线程。在如下三种情况下会发生线程的抢占：

（1）当正在运行的本地线程降低了其优先级，使其小于就绪队列中的某个线程的优先级
（2）当正在运行的本地线程增加了就绪队列中某个线程的优先级，使其高于正在运行的线程的优先级
（3）当就绪队列中新加入了一个优先级高于正在运行的线程的优先级，例如，某个高优先级的线程被唤醒。

Java线程的唤醒、优先级设置是由JVM实现的，但线程的调度（与LWP的连接）则是由本地线程库完成。操作系统（Solaris）可以依据自己的原则改变LWP的优先级，例如，通过动态优先级实现分时，这是线程库和JVM都无法干预的。

Solaris 9之后，使用了1:1的线程模型，即本地线程与LWP一对一地绑在一起，本地线程库也失去了直接干预线程调度的机会（指为本地线程选择连接LWP）。Java线程也就通过本地线程与LWP终生地一对一地绑在一起。这样可以通过改变本地线程或Java线程的优先级来影响LWP的优先级，从而影响系统的CPU调度。但具体的CPU分配策略还是Solaris做出的，JVM仅起辅助的作用。

2. Windows平台上的Java线程调度策略

在Windows下，Java线程一对一地绑定到Win32线程（相当于Solaris的native线程）上。当然Win32线程也是一对一地绑定到内核级线程上，所以Java线程的调度实际上是内核完成的。Java虚拟机可以做的是通过将Java线程的优先级映射到Win32线程的优先级上，从而影响系统的线程调度决策。

Windows内核使用了32级优先权模式来决定线程的调度顺序。优先权被分为两类：可变类优先权包含了1-15级，不可变类优先权（实时类）包含了16-31级。调度程序为每一个优先级建一个调度队列，从高优先级到低优先级队列逐个查找，直到找到一个可运行的线程。

Win32将进程（process）分为如下6个优先级类：
REALTIME_PRIORITY_CLASS
HIGH_PRIORITY_CLASS
ABOVE_NORMAL_PRIORITY_CLASS
NORMAL_PRIORITY_CLASS
BELOW_NORMAL_PRIORITY_CLASS
IDLE_PRIORITY_CLASS
为区分进程内线程的优先级，每个优先级类又包含6个相对优先级：
TIME_CRITIAL
HEGHEST
ABOVE_NORNAL
NORMAL
BELOW_NORMAL
LOWEST
IDLE
这样每个Win32线程属于某个优先级类（由该线程所属的进程决定），并具有进程内的某个相对优先级，其对应的内核级线程的优先级如下表所示：

表1.JPG

当把Java 线程绑定到Win32线程时，需要将Java线程的优先级映射到Win32线程上。Java 6在Windows的实现中将Java线程的优先级按下表所示映射到Win32线程的相对优先级上。

表2.JPG

当JVM将线程的优先级映射到Win32线程的优先级上之后，线程调度的工作就是Win32和Windows内核的事儿了。

Windows采用基于优先级的、抢占的线程调度算法。调度程序保证总是让具有最高优先级的线程运行。一个线程仅在如下四种情况下才会放弃CPU：（1）被一个更高优先级的线程抢占；（2）结束；（3）时间片到；（4）执行导致阻塞的系统调用。当线程的时间片用完后，降低其优先级；当线程从阻塞变为就绪时，增加线程的优先级；当线程很长时间没有机会运行时，系统也会提升线程的优先级。Windows区分前台和后台进程，前台进程往往获得更长的时间片。以上这些措施体现了Windows基于动态优先级、分时和抢占的CPU调度策略。调度策略很复杂，考虑了线程执行过程的各个方面，再加上系统运行环境的变化，我们很难通过线程运行过程的观察理清调度算法的全貌。在本文开头的例子说明了这一点。

由于Java线程到Windows内核线程一对一的绑定方式，所以我们看到的Java线程的运行过程实际上反映的是Windows的调度策略。

请注意，尽管Windows采用了基于优先级的调度策略，但不会出现饥饿现象。其采取的主要措施是：优先级再高的的线程也会在运行一个时间片之后放弃CPU，并且降低其优先级，从而保证了低优先级线程也有机会运行。

3. Linux中Java线程调度

同Windows一样，在Linux上Java线程一对一地映射到内核级线程上。不过Linux中是不区分进程和线程的，同一个进程中的线程可以看作是共享程度较高的一组进程。Linux也是通过优先级来实现CPU分配的，应用程序可以通过调整nice值（谦让值）来设置进程的优先级。nice值反映了线程的谦让程度，该值越高说明这个线程越有意愿把CPU让给别的线程，nice的值可以由线程自己设定。所以JVM需要实现Java线程的优先级到nice的映射，即从区间[1，10]到[19， -20]的映射。把自己线程的nice值设置高了，说明你的人品很谦让，当然使用CPU的机会就会少一点。

linux调度器实现了一个抢占的、基于优先级的调度算法，支持两种类型的进程的调度：实时进程的优先级范围为[0，99]，普通进程的优先级范围为[100，140]。

表3.jpg

进程的优先权越高，所获得的时间片就越大。每个就绪进程都有一个时间片。内核将就绪进程分为活动的（active）和过期的（expired）两类：只要进程的时间片没有耗尽，就一直有资格运行，称为活动的；当进程的时间片耗尽后，就没有资格运行了，称为过期的。调度程序总是在活动的进程中选择优先级最高的进程执行，直到所有的活动进程都耗尽了他们的时间片。当所有的活动进程都变成过期的之后，调度程序再将所有过期的进程置为活动的，并为他们分配相应的时间片，重新进行新一轮的调度。所以Linux的线程调度也不会出现饥饿现象。

在Linux上，同Windows的情况类似，Java线程的调度最终转化为了操作系统中的进程调度。

四．总结

从以上Java在不同平台上的实现来看，只有在底层平台不支持线程时，JVM才会自己实现线程的管理和调度，此时Java线程以绿色线程的方式运行。由于目前流行的操作系统都支持线程，所以JVM就没必要管线程调度的事情了。应用程序通过setPriority()方法设置的线程优先级，将映射到内核级线程的优先级，影响内核的线程调度。

目前的Java的官方文档中几乎不再介绍有关Java线程的调度算法问题，因为这确实不是Java的事儿了。尽管程序中还可以调用setPriority()，提请JVM注意线程的优先级，但你千万不要把这事儿太当真。Java中所谓的线程调度仅是底层平台线程调度的一个影子而已。

由于Java是跨平台的，因此要求Java的程序设计不能对Java线程的调度方法有任何假设，即程序运行的正确性不能依赖于线程调度的方法。所以说程序员最好不要过分关心底层平台是如何实现线程调度的，呵呵！只要知道他们是并发运行的就可以了，甚至不必在意线程的优先级，因为优先级也不靠谱。正如Joshua Bloch在他的书《Effective Java》中给出的第72条忠告：任何依赖线程调度器来达到正确性或性能要求的程序，很有可能都是不可移植的[5]。当然，世界上没有绝对的事情。

如果程序员一定要规范线程的执行顺序，应该使用线程的同步操作wait(), notify()等显式实现线程之间的同步关系，才能保证程序的正确性。

参考文献：

[1] http://lass.cs.umass.edu/~shenoy/courses/fall01/labs/talab2.html[2] https://en.wikipedia.org/wiki/Green_threads[3] http://www.sco.com/developers/java/j2sdk122-001/ReleaseNotes.html#THREADS[4] http://docs.oracle.com/javase/8/docs/api/index.html[5] Joshua Bloch，Effective java

作者系山东大学计算机学院教授