论文部分内容阅读
摘 要：随着网络和分布式计算的日益发展，应用程序及其处理的数据的规模也在不断增加。如何保证分布式计算环境下，往往不同的计算任务使用不同的计算资源，如何提高服务器集群整体的吞吐率和运行效率，是构建此类应用时面临的较为棘手的问题。使用对不同计算资源进行分别处理的方法，设计并实现一种高效的多队列线程池，针对分布式计算环境做进一步的改进，并对其进行性能分析。这种方法已经应用到某协同计算平台的实现中，并取得了很好的效果。
关键词：分布式计算 线程池 多线程 任务迁移 优先级队列
中图分类号：TP393.05 文献标识码：A 文章编号：1007-3973（2013）004-095-04
1 引言
随着网络和分布式计算的发展，应用程序程序及其处理的数据的规模也在不断增加，单个应用节点已经很难快速处理海量的数据。很多大型应用都采用分布式模式来处理其业务逻辑和数据信息。在这种情况下，每时每刻都有大量的请求到达应用服务器等待处理。如何在客户请求数量迅速增长的情况下，保持高效的吞吐率并让每个客户得到满意的服务性能，是一个亟待解决的问题。
线程池技术的出现为这一类问题提供了解决方法。由于线程是比进程更轻巧的程序调度单位，因而比进程更少耗费资源。另外，由于线程池中始终保证了一定数量的工作线程的存在，因此服务器端尽可能地减少了创建和销毁对象的次数，特别是一些很耗费资源的对象的创建和销毁。
然而传统的线程池技术使用唯一的工作队列来保存需要处理的任务，导致了对于竞争不同计算资源的可并行处理的任务之间不能进行有效的调度，从而影响了系统的吞吐率和服务器集群整体的运行性能。
在本文实现所处的分布式计算环境下，为了提高服务器集群的并发度，设计并实现了一种多队列线程池，采用了对不同计算资源分别进行处理的方式，将需要使用不同计算资源的任务发送到不同的任务队列上。保证了对于不同计算资源的并行处理，极大地保证了服务器集群整体的运行性能和应用服务器的吞吐率。
本文按如下方式组织：第2节介绍线程池技术的基本原理；第3节介绍多队列线程池的设计和实现；第4节是性能测试数据和分析；最后是全文的小结。
2 传统线程池技术基本原理与不足
2.1 传统线程池技术原理
在传统的线程池技术出现之前，应用服务器往往需要对每个任务创建一个线程，并由这个线程负责该任务的执行。这种方法导致了大量线程的产生，比如当应用服务器上客户端提交了数量庞大的运行时间较短、各自独立的任务时，服务器端将不断创建和销毁大量的线程，这势必会造成系统资源的耗尽。
传统线程池技术使用共用工作队列的方法，解决了上述每个任务都创建线程的方法带来的问题。传统线程池技术使用一个共用的工作队列和一个线程池来利用底层的硬件提供的并发性，对计算任务进行处理。如图1所示，服务器应用使用一个共用的工作队列来存放从客户端提交的计算任务。线程池中所有的工作线程，从共用的工作队列中检索任务并执行任务直至完成。如果工作队列中没有任务的话，线程就阻塞在队列上。代码1提供了一个传统的使用共同工作队列的线程池的简单实现。
图1 共用工作队列线程池
代码1. 共用工作队列线程池简单实现
/* 定义共用的工作队列和线程池来执行客户端提交的任务 */
public class SimpleWorkQueue {
private final PoolWorker[] threads；
private final BlockingDeque queue；
public SimpleWorkQueue（int nThreads）
{
queue = new LinkedBlockingDeque（）；
threads = new PoolWorker[nThreads]；
for （int i=0； i<="" span="">
threads[i] = new PoolWorker（）；
threads[i].start（）；
}
}
/* 内部工作线程类，用来执行远程任务 */
private class PoolWorker extends Thread {
/*
* 方法从工作队列中检索任务并开始执行任务
* 如果队列中没有任务的话线程将等待
*/
public void run（） {
while （！stopNow） {
try {
Runnable r = （Runnable） queue.takeLast（）；
r.run（）；
} catch （ java.lang.Throwable e） { }
}
}
}
}
2.2 传统线程池技术的不足
（1）工作线程之间的竞争。
由图1我们可以看出，线程池中一定数量的工作线程，共同竞争共用工作队列上的任务。这就需要在工作队列的实现时，考虑各个工作线程之间的同步机制，为工作队列设计带锁的数据结构是一种解决方法。但是这无疑增加了编程的复杂度和系统运行期死锁的概率。因此传统的线程池技术并不能避免或者隔离线程池中多个工作线程之间的竞争。
（2）不能定义任务优先级。
由于系统共用一个工作队列，因此由客户端提交的计算任务不能定义任务的优先级。所有计算任务将被统一的在工作队列中排队，按照先来先服务的方法进行调度执行。此时，即使客户端有优先级级别较高的计算任务需要执行，也只能排队等待工作队列中排在前面的计算任务先执行完毕，才能够调度执行。这势必会造成客户端响应的延迟和用户使用的友好性。 3 多队列线程池设计与实现
3.1 多队列线程池基本原理与实现
如图2所示，我们设计了一种每个工作线程一个工作队列（queue-per-thread）的方法--以此来隔离工作线程之间的竞争，并针对使用不同计算任务和具有不同优先级的任务在不同的工作队列中进行排队。如图2所示。
图2 queue-per-thread线程池
在这一方法中，每个线程都有自己的工作队列，一般情况下一个工作线程只能从自己的队列而不能从任何的其他队列中检索任务。该方法隔离了检索任务时的竞争，因为这种情况下不存在其他要和它争夺任务的线程。这一做法保证了如果工作队列中有任务存在的话，线程就不会进入睡眠状态，这样就有效地利用到了应用服务器的多核CPU等硬件资源。
代码2展示了如何很容易地从共用工作队列方法迁移到每个线程一个队列方法上，只需对代码1展示的代码做几处修改就可以了。在代码2中，构造函数在启动时初始化了多个队列（等于线程的数目），每个线程都维护一个名为thread_id的ID。接着，thread_id被用来隔离竞争，其帮助每个线程从自己的队列中检索任务。
代码2. queue-per-thread线程池实现代码
/* 修改成多个队列的初始化*/
for （int i=0； i（）；
}
...
......
/* 任务检索的修改 */
r = （Runnable） queue[thread_id].takeLast（）；
3.2 优先级队列及队列间任务迁移
虽然每个线程一个队列这种方法极大地减少了竞争，但它并不能保证优先级高的任务首先执行完毕，并且不能保证底层的多核在所有时候都能够被有效利用。例如，如果有一两个队列比其他队列先变空了的话会有什么事情发生呢？这是一种常见的情况，在这种情况下，只有少数的线程在执行任务，而其他的线程（队列已空的线程）则在等待新任务的到来。这种情况是可能发生的，理由如下：
（1）调度算法的不可预测性。
（2）传入计算任务的不可预测性（优先级别和执行时间的长短）
我们为解决上述问题设计了一种任务迁移的方法。首先，我们设置了不同任务队列的优先级，使得具有不同优先级的任务将被提交到不同优先级的队列中。其次，我们设计了不同优先级的任务队列之间的任务迁移策略。这分为两种情况：（1）当一个线程发现有比自己的队列更高优先级的任务队列中有任务时，工作迁移方法让该线程从较高优先级队列中迁移工作。这种做法确保了较高优先级的任务队列比较低优先级的队列首先执行完毕。（2）当线程发现自己的任务队列变空时，工作迁移方法将让该线程从较低优先级队列中迁移工作。这种做法保证了线程（对应CPU核数）每时每刻都是忙碌的。图3展示了这两种场景，当线程2发现有较高优先级的队列（队列1）中存在任务时，将从线程1的队列中获取了一个工作任务。当线程1发现自己的任务队列为空，将从线程2的优先级较低的任务队列中迁移工作。
为了防止任务迁移过程中可能产生过多的竞争，我们使用一个双端队列来作为任务队列的实现，理由如下：
（1）只有工作线程才能访问它自己的双端队列的头端，因此双端队列的头端永远也不会存在竞争。
（2）双端队列的尾端只有在线程已经运行完所有的工作时才会访问到，因此任何线程的双端队列的尾端也都很少有竞争出现。
图3 任务迁移策略
代码3说明了如何从其他的队列中获取工作任务，只需要对每个线程一个队列方法做几处修改就可以了。这种情况下，每个线程都调用pollLast（）而不是takeLast（）方法来从队列中获取任务，从而保证了当队列中没有任务时，工作线程不会在自己的队列上阻塞。一旦线程发现有别它的队列较高优先级的队列中存在计算任务的话，它就通过调用该线程队列的pollFirst（）来从其他队列中获取工作任务。并且当线程发现自己的队列为空时，就使用同样的方法从较低优先级任务队列中获取任务。
清单3. 实现工作迁移
/* 查找比thread_id小的具有较高优先级队列中是否存在任务，并从中获取一个 */
r = （Runnable）transportWorkFromHigh（thread_id）；
/* 执行自己的任务队列中的任务*/
if（null == r） {
r = （Runnable） queue[thread_id].pollLast（）；
}
if（null == r） {
/*查找比thread_id大的具有较低优先级队列中是否存在任务，并从中获取一个 */
r = transportWorkFromLow（thread_id）；
}
/* 从较高优先级队列中获取任务的方法 */
Runnable transportWorkFromHigh （int index） {
for （int i=0； i<=index； i++） {
Object o = queue[i].pollFirst（）；
if（o！=null） {
return （Runnable） o；
}
}
return null；
}
/* 从较低优先级队列中获取任务的方法 */
Runnable transportWorkFromLow （int index） { for （int i=index+1； i<=queue.length（）； i++） {
Object o = queue[i].pollFirst（）；
if（o！=null） {
return （Runnable） o；
}
}
return null；
}
4 性能测试分析
为了验证带工作迁移的多队列线程池的性能，我们设计了一个小型的测试方案并记录了测试结果。这一测试的基本工作是创建大量的10x10矩阵乘法运算任务（为了测试方便，将所有的任务优先级设为相同）并使用基本线程池及带工作迁移的多队列线程池来执行它们。
我们在实验室的工作站机器上对上述方法进行了测试，结果非常乐观。该机器为台式机，处理器是Intel Core i7-2600，该CPU为四核八线程处理器，运行的是Windows操作系统，内存为4G，Java虚拟机内存设置为 1024M。根据测试结果我们发现，根据负载情况的不同，带工作迁移的多队列线程池的性能比传统的线程池提高了12%到18.4%，如图4所示。
正如图4所展示的那样，我们从1千万到5千万改变任务的数目，并以秒为单位来衡量性能。实验的结果清楚地证明，传统线程池技术产生了数量庞大的竞争，这些竞争可通过创建多队列和工作任务迁移等手段来消除。
5 结语
本文说明了传统线程池技术使用共用工作队列所涉及的竞争，然后设计并实现了一种带任务迁移的多队列线程池来解决上述问题。文章还通过一个简单的测试来说明了这种新的方法与传统的线程池技术相比，提高了应用的整体性能。
参考文献：
[1]张垠坡.线程池技术在并发服务器中的应用[J].计算机与数字工程，2012（7）：153-156.
[2]王华.线程池技术研究与应用[J].计算机应用研究，2005（11）：141-142.
[3]李刚，金蓓弘.基于线程的并发控制技术研究与应用[J].计算机工程，2007，30（14）：43-45.
[4]Java theory and practice：Thread pools and work queues，by Brian Goetz.
[5]A dynamic-sized nonblocking work stealing deque，by Danny Hendler，Yossi Lev，Mark Moir，and Nir Shavit.
[6]Blocking doubly ended queue，Java documentation.
关键词：分布式计算 线程池 多线程 任务迁移 优先级队列
中图分类号：TP393.05 文献标识码：A 文章编号：1007-3973（2013）004-095-04
1 引言
随着网络和分布式计算的发展，应用程序程序及其处理的数据的规模也在不断增加，单个应用节点已经很难快速处理海量的数据。很多大型应用都采用分布式模式来处理其业务逻辑和数据信息。在这种情况下，每时每刻都有大量的请求到达应用服务器等待处理。如何在客户请求数量迅速增长的情况下，保持高效的吞吐率并让每个客户得到满意的服务性能，是一个亟待解决的问题。
线程池技术的出现为这一类问题提供了解决方法。由于线程是比进程更轻巧的程序调度单位，因而比进程更少耗费资源。另外，由于线程池中始终保证了一定数量的工作线程的存在，因此服务器端尽可能地减少了创建和销毁对象的次数，特别是一些很耗费资源的对象的创建和销毁。
然而传统的线程池技术使用唯一的工作队列来保存需要处理的任务，导致了对于竞争不同计算资源的可并行处理的任务之间不能进行有效的调度，从而影响了系统的吞吐率和服务器集群整体的运行性能。
在本文实现所处的分布式计算环境下，为了提高服务器集群的并发度，设计并实现了一种多队列线程池，采用了对不同计算资源分别进行处理的方式，将需要使用不同计算资源的任务发送到不同的任务队列上。保证了对于不同计算资源的并行处理，极大地保证了服务器集群整体的运行性能和应用服务器的吞吐率。
本文按如下方式组织：第2节介绍线程池技术的基本原理；第3节介绍多队列线程池的设计和实现；第4节是性能测试数据和分析；最后是全文的小结。
2 传统线程池技术基本原理与不足
2.1 传统线程池技术原理
在传统的线程池技术出现之前，应用服务器往往需要对每个任务创建一个线程，并由这个线程负责该任务的执行。这种方法导致了大量线程的产生，比如当应用服务器上客户端提交了数量庞大的运行时间较短、各自独立的任务时，服务器端将不断创建和销毁大量的线程，这势必会造成系统资源的耗尽。
传统线程池技术使用共用工作队列的方法，解决了上述每个任务都创建线程的方法带来的问题。传统线程池技术使用一个共用的工作队列和一个线程池来利用底层的硬件提供的并发性，对计算任务进行处理。如图1所示，服务器应用使用一个共用的工作队列来存放从客户端提交的计算任务。线程池中所有的工作线程，从共用的工作队列中检索任务并执行任务直至完成。如果工作队列中没有任务的话，线程就阻塞在队列上。代码1提供了一个传统的使用共同工作队列的线程池的简单实现。
图1 共用工作队列线程池
代码1. 共用工作队列线程池简单实现
/* 定义共用的工作队列和线程池来执行客户端提交的任务 */
public class SimpleWorkQueue {
private final PoolWorker[] threads；
private final BlockingDeque queue；
public SimpleWorkQueue（int nThreads）
{
queue = new LinkedBlockingDeque（）；
threads = new PoolWorker[nThreads]；
for （int i=0； i<="" span="">
threads[i] = new PoolWorker（）；
threads[i].start（）；
}
}
/* 内部工作线程类，用来执行远程任务 */
private class PoolWorker extends Thread {
/*
* 方法从工作队列中检索任务并开始执行任务
* 如果队列中没有任务的话线程将等待
*/
public void run（） {
while （！stopNow） {
try {
Runnable r = （Runnable） queue.takeLast（）；
r.run（）；
} catch （ java.lang.Throwable e） { }
}
}
}
}
2.2 传统线程池技术的不足
（1）工作线程之间的竞争。
由图1我们可以看出，线程池中一定数量的工作线程，共同竞争共用工作队列上的任务。这就需要在工作队列的实现时，考虑各个工作线程之间的同步机制，为工作队列设计带锁的数据结构是一种解决方法。但是这无疑增加了编程的复杂度和系统运行期死锁的概率。因此传统的线程池技术并不能避免或者隔离线程池中多个工作线程之间的竞争。
（2）不能定义任务优先级。
由于系统共用一个工作队列，因此由客户端提交的计算任务不能定义任务的优先级。所有计算任务将被统一的在工作队列中排队，按照先来先服务的方法进行调度执行。此时，即使客户端有优先级级别较高的计算任务需要执行，也只能排队等待工作队列中排在前面的计算任务先执行完毕，才能够调度执行。这势必会造成客户端响应的延迟和用户使用的友好性。 3 多队列线程池设计与实现
3.1 多队列线程池基本原理与实现
如图2所示，我们设计了一种每个工作线程一个工作队列（queue-per-thread）的方法--以此来隔离工作线程之间的竞争，并针对使用不同计算任务和具有不同优先级的任务在不同的工作队列中进行排队。如图2所示。
图2 queue-per-thread线程池
在这一方法中，每个线程都有自己的工作队列，一般情况下一个工作线程只能从自己的队列而不能从任何的其他队列中检索任务。该方法隔离了检索任务时的竞争，因为这种情况下不存在其他要和它争夺任务的线程。这一做法保证了如果工作队列中有任务存在的话，线程就不会进入睡眠状态，这样就有效地利用到了应用服务器的多核CPU等硬件资源。
代码2展示了如何很容易地从共用工作队列方法迁移到每个线程一个队列方法上，只需对代码1展示的代码做几处修改就可以了。在代码2中，构造函数在启动时初始化了多个队列（等于线程的数目），每个线程都维护一个名为thread_id的ID。接着，thread_id被用来隔离竞争，其帮助每个线程从自己的队列中检索任务。
代码2. queue-per-thread线程池实现代码
/* 修改成多个队列的初始化*/
for （int i=0； i（）；
}
...
......
/* 任务检索的修改 */
r = （Runnable） queue[thread_id].takeLast（）；
3.2 优先级队列及队列间任务迁移
虽然每个线程一个队列这种方法极大地减少了竞争，但它并不能保证优先级高的任务首先执行完毕，并且不能保证底层的多核在所有时候都能够被有效利用。例如，如果有一两个队列比其他队列先变空了的话会有什么事情发生呢？这是一种常见的情况，在这种情况下，只有少数的线程在执行任务，而其他的线程（队列已空的线程）则在等待新任务的到来。这种情况是可能发生的，理由如下：
（1）调度算法的不可预测性。
（2）传入计算任务的不可预测性（优先级别和执行时间的长短）
我们为解决上述问题设计了一种任务迁移的方法。首先，我们设置了不同任务队列的优先级，使得具有不同优先级的任务将被提交到不同优先级的队列中。其次，我们设计了不同优先级的任务队列之间的任务迁移策略。这分为两种情况：（1）当一个线程发现有比自己的队列更高优先级的任务队列中有任务时，工作迁移方法让该线程从较高优先级队列中迁移工作。这种做法确保了较高优先级的任务队列比较低优先级的队列首先执行完毕。（2）当线程发现自己的任务队列变空时，工作迁移方法将让该线程从较低优先级队列中迁移工作。这种做法保证了线程（对应CPU核数）每时每刻都是忙碌的。图3展示了这两种场景，当线程2发现有较高优先级的队列（队列1）中存在任务时，将从线程1的队列中获取了一个工作任务。当线程1发现自己的任务队列为空，将从线程2的优先级较低的任务队列中迁移工作。
为了防止任务迁移过程中可能产生过多的竞争，我们使用一个双端队列来作为任务队列的实现，理由如下：
（1）只有工作线程才能访问它自己的双端队列的头端，因此双端队列的头端永远也不会存在竞争。
（2）双端队列的尾端只有在线程已经运行完所有的工作时才会访问到，因此任何线程的双端队列的尾端也都很少有竞争出现。
图3 任务迁移策略
代码3说明了如何从其他的队列中获取工作任务，只需要对每个线程一个队列方法做几处修改就可以了。这种情况下，每个线程都调用pollLast（）而不是takeLast（）方法来从队列中获取任务，从而保证了当队列中没有任务时，工作线程不会在自己的队列上阻塞。一旦线程发现有别它的队列较高优先级的队列中存在计算任务的话，它就通过调用该线程队列的pollFirst（）来从其他队列中获取工作任务。并且当线程发现自己的队列为空时，就使用同样的方法从较低优先级任务队列中获取任务。
清单3. 实现工作迁移
/* 查找比thread_id小的具有较高优先级队列中是否存在任务，并从中获取一个 */
r = （Runnable）transportWorkFromHigh（thread_id）；
/* 执行自己的任务队列中的任务*/
if（null == r） {
r = （Runnable） queue[thread_id].pollLast（）；
}
if（null == r） {
/*查找比thread_id大的具有较低优先级队列中是否存在任务，并从中获取一个 */
r = transportWorkFromLow（thread_id）；
}
/* 从较高优先级队列中获取任务的方法 */
Runnable transportWorkFromHigh （int index） {
for （int i=0； i<=index； i++） {
Object o = queue[i].pollFirst（）；
if（o！=null） {
return （Runnable） o；
}
}
return null；
}
/* 从较低优先级队列中获取任务的方法 */
Runnable transportWorkFromLow （int index） { for （int i=index+1； i<=queue.length（）； i++） {
Object o = queue[i].pollFirst（）；
if（o！=null） {
return （Runnable） o；
}
}
return null；
}
4 性能测试分析
为了验证带工作迁移的多队列线程池的性能，我们设计了一个小型的测试方案并记录了测试结果。这一测试的基本工作是创建大量的10x10矩阵乘法运算任务（为了测试方便，将所有的任务优先级设为相同）并使用基本线程池及带工作迁移的多队列线程池来执行它们。
我们在实验室的工作站机器上对上述方法进行了测试，结果非常乐观。该机器为台式机，处理器是Intel Core i7-2600，该CPU为四核八线程处理器，运行的是Windows操作系统，内存为4G，Java虚拟机内存设置为 1024M。根据测试结果我们发现，根据负载情况的不同，带工作迁移的多队列线程池的性能比传统的线程池提高了12%到18.4%，如图4所示。
正如图4所展示的那样，我们从1千万到5千万改变任务的数目，并以秒为单位来衡量性能。实验的结果清楚地证明，传统线程池技术产生了数量庞大的竞争，这些竞争可通过创建多队列和工作任务迁移等手段来消除。
5 结语
本文说明了传统线程池技术使用共用工作队列所涉及的竞争，然后设计并实现了一种带任务迁移的多队列线程池来解决上述问题。文章还通过一个简单的测试来说明了这种新的方法与传统的线程池技术相比，提高了应用的整体性能。
参考文献：
[1]张垠坡.线程池技术在并发服务器中的应用[J].计算机与数字工程，2012（7）：153-156.
[2]王华.线程池技术研究与应用[J].计算机应用研究，2005（11）：141-142.
[3]李刚，金蓓弘.基于线程的并发控制技术研究与应用[J].计算机工程，2007，30（14）：43-45.
[4]Java theory and practice：Thread pools and work queues，by Brian Goetz.
[5]A dynamic-sized nonblocking work stealing deque，by Danny Hendler，Yossi Lev，Mark Moir，and Nir Shavit.
[6]Blocking doubly ended queue，Java documentation.