CN102834807B - 多处理器系统负载均衡的方法和装置 - Google Patents

Abstract

一种多处理器系统负载均衡的方法和装置涉及多处理器系统的资源分配领域，用以实现迁移到目标中央处理器(CPU)的进程在执行时，减少对远端节点存储器的访问次数或数据的拷贝量的目的。所述多处理器系统负载均衡的方法包括：确定多处理器系统中的本地CPU和目标CPU；根据所述本地CPU队列中的进程占用存储器空间的大小，进行迁移优先级的排序，其中占用存储器空间越少的进程，其迁移优先级就越高；将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU。本发明提供的方案可以适用于非一致存储器访问(NUMA)架构的多处理系统。

Description

多处理器系统负载均衡的方法和装置

技术领域

本发明涉及多处理器系统的资源分配领域，尤其涉及一种多处理器系统负载均衡的方法和装置。

背景技术

在多处理器系统中，每个CPU(Central Processing Unit，中央处理器)各自单独维护一个队列，从而会导致多个CPU之间的负载不均衡，这就需要将进程(或线程)从负载量大的CPU迁移到负载量小的CPU上，以达到负载均衡；其中进程迁移出来的CPU称为本地CPU，进程迁移进去的CPU称为目标CPU。

现有技术中提出了一种根据进程在缓存的冷热情况迁移进程，以达到负载均衡的方法，具体包括：首先，设定进程的等待时间的阈值(最大值)，所谓进程的等待时间是指判断是否迁移该进程的时刻距离该进程最近一次执行结束的时间；然后，判断本地CPU上的一进程的等待时间是否大于该阈值；若是，则认为该进程在缓存中是冷的，将该进程迁移到目标CPU上，若否，则认为该进程在缓存中是热的，不迁移该进程。在各个CPU上循环利用上述方法迁移进程，直到各CPU之间达到一定的负载均衡。

利用上述方法虽然可以达到负载均衡的效果，但也可能将一些占用存储器空间较大的进程迁移到目标CPU中，从而使得这些进程在目标CPU上执行时，需要多次访问远端节点的存储器，或者需要从远端节点的存储器中将该进程相关的大量数据拷贝到本节点的存储器中，进而影响系统的性能。

发明内容

本发明的实施例提供一种多CPU系统负载均衡的方法和装置，用以实现迁移到目标CPU的进程在执行时，减少对远端节点存储器的访问次数或数据的拷贝量的目的。

为达到上述目的，本发明的实施例采用如下技术方案：

一种多处理器系统负载均衡的方法，包括：

确定多处理器系统中的本地中央处理器CPU和目标CPU；

根据所述本地CPU队列中的进程占用存储器空间的大小，进行迁移优先级的排序；且占用存储器空间越少的进程，其迁移优先级就越高；

将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU。

一种多处理器系统负载均衡的装置，包括：

确定单元，用于确定多处理器系统中的本地中央处理器CPU和目标CPU；

排序单元，用于根据所述本地CPU队列中的进程占用存储器空间的大小，进行迁移优先级的排序；且占用存储器空间越少的进程，其迁移优先级就越高；

迁移单元，用于将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU。

本发明实施例提供的一种多处理器系统负载均衡的方法和装置，根据本地CPU队列中的进程占用存储器空间的大小，进行迁移优先级的排序，并选择本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU；由于占用存储器空间越小的进程，其迁移优先级就越高，故而就可以优先迁移本地CPU队列中占用存储器空间最小的进程到目标CPU，从而减少迁移的进程在目标CPU上执行时对远端节点存储器的访问次数或数据的拷贝量。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为实施例一提供的一种多处理器系统负载均衡的方法示意图；

图2为实施例二提供的一种多处理器系统负载均衡的方法示意图；

图3为实施例三提供的一种多处理器系统负载均衡的方法示意图；

图4为实施例三提供的另一种多处理器系统负载均衡的方法示意图；

图5为本发明实施例提供的一种多处理器系统负载均衡的装置框图；

图6为本发明实施例提供的另一种多处理器系统负载均衡的装置框图。

具体实施方式

多处理器系统是指设有至少两个CPU进行数据处理的系统。例如，NUMA(Non Uniform Memory Access Architecture，非一致存储器访问架构)系统是一种多处理器系统，且该系统的所有节点中的CPU都可以访问全部的系统物理存储器，同时一个节点的CPU访问其他不同节点存储器的延时不一样。本发明提供的方案可以适用于NUMA构架的多处理器系统。

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例一：

如图1所示，本发明实施例提供一种多处理器系统负载均衡的方法，包括：

步骤101、确定多处理器系统中的本地中央处理器CPU和目标CPU；

对于多处理器系统而言，每次时钟中断都会检测该多处理器系统中是否存在负载不均衡的情况，在多处理器系统存在负载不均衡的情况下，需要进行负载均衡处理。所述负载均衡处理是指将进程从负载量大的CPU迁移到负载量小的CPU上；其中，进程迁移出来的CPU称为本地CPU，进程迁移进去的CPU称为目标CPU；一般而言，负载量大的CPU可以作为本地CPU，负载量小的CPU可以作为目标CPU。

步骤102、根据所述本地CPU队列中的进程占用存储器空间的大小，进行迁移优先级的排序；且占用存储器空间越少的进程，其迁移优先级就越高；

所述迁移优先级用于代表进程迁移的优先顺序；也就是说，一个进程的迁移优先级越高，则该进程就越优先被迁移。

此步骤可以为，读取本地CPU队列中的所有进程占用存储器空间的大小，根据每个进程占用存储器空间的大小进行迁移优先级的排序；且占用存储器空间越少的进程，其迁移优先级就越高。

其中，所述读取本地队列中的所有进程占用存储器空间的大小可以采用如下方法：对于本地队列中的任一进程，通过查看其对应的页表属性，可以得到其占用存储器空间的大小。

步骤103、将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU。

可以循环进行上述三个步骤，直至多处理器系统达到负载均衡或者接近负载均衡或者该多处理器系统达到应用环境所要求的各个CPU的负载情况。

需要说明的是，上述各个步骤的执行主体为一种多处理器系统负载均衡的装置，该装置可以是一个基于多处理器系统的功能模块，且该功能模块可以在各个CPU中，也可以独立于各个CPU而单独设置。

本发明实施例提供的多处理器系统负载均衡的方法，将本地CPU队列中除了正在执行的进程外，占用存储器空间最小的进程迁移到目标CPU，从而可以减少所迁移的进程在目标CPU上执行时对远端节点存储器的访问次数或数据的拷贝量。

实施例二：

考虑到在某些应用环境或场景下，多处理器系统需要满足所述某些应用环境或场景的负载要求。本发明实施例提供的多处理器系统负载均衡的方法，根据多处理器系统在应用环境或场景下的负载要求，预先对迁移优先级设置阈值。

如图2所示，本发明实施例提供的多处理器系统负载均衡的方法，包括：

步骤201、确定多处理器系统中的本地CPU和目标CPU；

参考步骤101。

步骤202、根据所述本地CPU队列中的进程占用存储器空间的大小，进行迁移优先级的排序；且占用存储器空间越少的进程，其迁移优先级就越高；

此步骤的解释可以参考步骤102；另外，所述迁移优先级可以用数字表示，即用数字的大小来表示迁移优先级的顺序；在本实施例中，数字越大表示迁移优先级越高。例如，本地CPU队列中有9个进程，则可以根据这9个进程占用存储器空间的大小，用1～9来表示这9个进程的迁移优先级，且迁移优先级为9的进程为占用存储器空间最小的进程。若9个进程中有两个进程占用存储器空间的大小相同，则这两个进程的迁移优先级的次序可以颠倒；例如，若迁移优先级最高的进程占用存储器空间的大小相同，则这两个进程的迁移优先级分别记为8和9，但具体将这两个进程中的哪个进程的迁移优先级记为8、哪个进程的迁移优先级记为9，可以为随机设定，当然，也可以通过其他判断手段进一步的区分这两个进程迁移优先级的高低。

步骤203、将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程的迁移优先级和预设的阈值做比较；

根据多处理器系统的应用环境或场景，为本地CPU队列中进程的迁移优先级预先设定一阈值，即设定可迁移进程的迁移优先级的最大值。经过此步骤的比较，若所述迁移优先级最高的进程的迁移优先级大于预设的阈值；否则，则进程不迁移。

例如本实施例本地CPU队列中正在执行的进程的迁移优先级为5且预设的阈值为7，根据此步骤比较迁移优先级最高的进程的迁移优先级9和预设的阈值7，显然，9大于7，且迁移优先级为9的进程不是正在执行的进程，故进行步骤204。

步骤204、将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程，在该进程的迁移优先级大于所述预设的阈值的情况下，迁移到目标CPU。

例如，若本地CPU队列中迁移优先级最高的进程的迁移优先级为9，且该进程不是正在执行的进程，且9大于预设的阈值7，则经过此步骤将该进程迁移到目标CPU；若本地CPU队列中迁移优先级为9的进程正在执行，则除了该进程外，迁移优先级最高的进程为迁移优先级为8的进程，由于8大于预设的阈值7，故将本地CPU中迁移优先级为8的进程迁移到目标CPU。在将本地CPU中迁移优先级为8的进程迁移到目标CPU之后，判断该多处理系统是否负载均衡，若负载均衡则结束，若没有负载均衡则循环进行步骤201～204。

由于本发明实施例提供的方法根据多处理系统的应用环境或场景预先对迁移优先级设定了阈值，故可以使得多处理系统在满足应用环境或场景下各个CPU的负载要求的条件下，尽可能的达到负载均衡；由于所迁移的进程都是占用的存储器空间较小的进程，从而可以减少所迁移的进程在目标CPU上执行时对远端节点存储器的访问次数或数据的拷贝量。

实施例三：

由于进程的执行时间在一定程度上可以反映该进程占用存储器空间的大小，一般而言，进程的执行时间和该进程占用存储器空间成正向的函数关系，也就是说，进程的执行时间越长则表示该进程占用存储器空间就越大。所述进程的执行时间是指该进程从执行开始到执行结束的耗时。基于上述考虑，如图3所示，本发明实施例提供另一种多处理器系统负载均衡的方法。

步骤301、确定多处理器系统中的本地中央处理器CPU和目标CPU；

参考步骤101。

步骤302、计算本地CPU队列中各进程的执行时间；

例如，本地CPU队列中有9个进程，则利用进程执行结束时刻减去该进程执行开始时刻得到该进程执行时间的方法，或者利用定时器的方法，计算这9个进程的执行时间。

步骤303、比较各进程的执行时间的长短，进行迁移优先级的排序；且执行时间越短的进程，其迁移优先级就越高；

本实施例中可以用数字的大小来表示迁移优先级的顺序。例如此步骤可以为，比较本地CPU队列中9个进程执行时间的长短，用数字1～9来表示这9个进程的迁移优先级，即进行迁移优先级的排序。执行时间越短的进程，其迁移优先级就越高；将执行时间最短的进程的迁移优先级记为9，将执行时间最长的进程的迁移优先级记为1。

若在本地CPU队列中的9个进程的执行时间各不相同，则继续进行步骤306。

若在本地CPU队列中存在至少两个执行时间相同的进程，则所述至少两个执行时间相同的进程之间的迁移优先级顺序可以随机设定；例如，迁移优先级为5、6、7的三个进程的执行时间相同，则这三个进程的迁移优先级可以随机记为5、6、7。当然，还可以通过步骤304～305对所述至少两个执行时间相同的进程的优先级做进一步的判断。

步骤304、在本地CPU队列中若存在至少两个执行时间相同的进程，则计算所述至少两个执行时间相同的进程的等待时间；

进程的等待时间是指，从该进程在本地CPU中最后一次执行结束的时刻到进行此步骤的时刻所经过的时间；对于进程等待时间的计算可以用进行此步骤的时刻减去该进程在本地CPU中最后一次执行结束的时刻的方法，或是利用定时器的方法，当然，也不排除利用其他可以得到进程等待时间的方法。

例如，若在本地CPU中迁移优先级为5、6、7的三个进程的执行时间相同，则分别计算三者的等待时间。

步骤305、比较所述至少两个执行时间相同的进程的等待时间的长短，进行迁移优先级的排序；且等待时间越长的进程，其迁移优先级就越高。

例如，比较本地CPU中迁移优先级为5、6、7的三个进程的等待时间的长短，进行迁移优先级的排序。由于进程的等待时间越长，说明距离该进程最后一次执行结束的时间就越久，其迁移优先级就越高；相反，进程的等待时间越短，说明距离该进程最后一次执行结束的时间就越短，其迁移优先级就越低。依据此排序方法，将执行时间相同的进程进行迁移优先级的排序。

由上述各步骤可以得到在本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程。接着，若只考虑将多处理器系统负载均衡，则进行步骤3061，见图3；若考虑多处理器系统在应用环境或场景下的负载要求，则需要根据该负载要求预先对迁移优先级设置阈值，进行步骤3062，见图4。

步骤3061、将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程，迁移到目标CPU。

若此时多处理器系统负载得以均衡，则结束；若此时多处理器系统负载仍不均衡，则循环图3所示的步骤301～步骤3061直至负载均衡。

本发明实施例提供的利用进程的执行时间考量进程占用存储器空间的大小，并将本地CPU中除了正在执行的进程外执行时间最短的进程迁移至目标CPU，直至多处理器系统负载均衡，从而可以减少所迁移的进程在目标CPU上执行时对远端节点存储器的访问次数或数据的拷贝量。

步骤3062、将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程的迁移优先级和预设的阈值做比较，在该进程的迁移优先级大于所述预设的阈值的情况下，将其迁移到目标CPU。

S1、将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程的迁移优先级和预设的阈值做比较；

S2、将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程，在该进程的迁移优先级大于所述预设的阈值的情况下，迁移到目标CPU。

若此时多处理器系统负载得以均衡，则结束；若此时多处理器系统负载仍不均衡，则循环图4所示的步骤301～步骤3062使得多处理器系统在满足应用环境或场景的条件下，尽可能的达到负载均衡。

本发明实施例考虑在多处理器系统的应用环境或场景下，尽可能的达到多处理器系统的负载均衡；由于所迁移的进程都是占用的存储器空间较小的进程，从而可以减少所迁移的进程在目标CPU上执行时对远端节点存储器的访问次数或数据的拷贝量。

本发明实施例还提供了与上述多处理器系统负载均衡的方法相对应的装置，如图5所示，该装置包括：

确定单元51，用于确定多处理器系统中的本地中央处理器CPU和目标CPU；

排序单元52，用于根据所述本地CPU队列中的进程占用存储器空间的大小，进行迁移优先级的排序；且占用存储器空间越少的进程，其迁移优先级就越高；

迁移单元53，用于将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU。

本发明实施例提供的多处理器系统负载均衡的装置，将本地CPU队列中除了正在执行的进程外，占用存储器空间最小的进程迁移到目标CPU，从而可以减少所迁移的进程在目标CPU上执行时对远端节点存储器的访问次数或数据的拷贝量。

优选的，所述排序单元52包括：

第一计算子单元，用于计算本地CPU队列中各进程的执行时间；

第一比较子单元，用于比较各进程的执行时间的长短，进行迁移优先级的排序；且执行时间越短的进程，其迁移优先级就越高。

若本地CPU队列中存在至少两个执行时间相同的进程，则所述排序单元52还可以包括：

第二计算子单元，用于在本地CPU队列中存在至少两个执行时间相同的进程的情况下，计算所述至少两个执行时间相同的进程的等待时间；

第二比较子单元，用于比较所述至少两个执行时间相同的进程的等待时间的长短，进行迁移优先级的排序；且等待时间越长的进程，其迁移优先级就越高。

进一步的，若考虑某些应用环境或场景对多处理器系统的要求，则需要预先对迁移优先级设置阈值。如图6所示，上述装置还包括：

比较单元54，用于将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程的迁移优先级和预设的阈值做比较，所述迁移优先级用数字表示；此时，所述迁移单元53具体用于将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程，在该进程的迁移优先级大于所述预设的阈值的情况下，迁移到所述目标CPU。

通过设置比较单元54，就可以使得多处理器系统在满足某些应用环境或场景的负载要求的情况下，尽可能的达到负载均衡；由于所迁移的进程都是占用的存储器空间较小的进程，从而可以减少所迁移的进程在目标CPU上执行时对远端节点存储器的访问次数或数据的拷贝量。

通过以上的实施方式的描述，所属领域的技术人员可以清楚地了解到本发明可借助软件加必需的通用硬件的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在可读取的存储介质中，如计算机的软盘，硬盘或光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述的方法。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以所述权利要求的保护范围为准。

Claims (6)

1.一种多处理器系统负载均衡的方法，其特征在于，包括：

确定多处理器系统中的本地中央处理器CPU和目标CPU；

计算本地CPU队列中各进程的执行时间；

比较各进程的执行时间的长短，进行迁移优先级的排序；且执行时间越短的进程，其迁移优先级就越高；

将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU。

2.根据权利要求1所述的方法，其特征在于，还包括：将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程的迁移优先级和预设的阈值做比较；所述迁移优先级用数字表示，且数字越大迁移优先级越高；

所述将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU具体为：

将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程，在该进程的迁移优先级大于所述预设的阈值的情况下，迁移到所述目标CPU。

3.根据权利要求1或2所述的方法，其特征在于，所述方法还包括：

在本地CPU队列中若存在至少两个执行时间相同的进程，则计算所述至少两个执行时间相同的进程的等待时间；

比较所述至少两个执行时间相同的进程的等待时间的长短，进行迁移优先级的排序；且等待时间越长的进程，其迁移优先级就越高。

4.一种多处理器系统负载均衡的装置，其特征在于，包括：

确定单元，用于确定多处理器系统中的本地中央处理器CPU和目标CPU；

排序单元，包括：第一计算子单元和第一比较子单元，其中，所述第一计算子单元，用于计算本地CPU队列中各进程的执行时间；所述第一比较子单元，用于比较各进程的执行时间的长短，进行迁移优先级的排序；且执行时间越短的进程，其迁移优先级就越高；

迁移单元，用于将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程迁移到所述目标CPU。

5.根据权利要求4所述的装置，其特征在于，还包括：

比较单元，用于将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程的迁移优先级和预设的阈值做比较，所述迁移优先级用数字表示；

所述迁移单元具体用于将本地CPU队列中除了正在执行的进程外、迁移优先级最高的进程，在该进程的迁移优先级大于所述预设的阈值的情况下，迁移到所述目标CPU。

6.根据权利要求4或5所述的装置，其特征在于，所述排序单元还包括：

第二计算子单元，用于在本地CPU队列中存在至少两个执行时间相同的进程的情况下，计算所述至少两个执行时间相同的进程的等待时间；

第二比较子单元，用于比较所述至少两个执行时间相同的进程的等待时间的长短，进行迁移优先级的排序；且等待时间越长的进程，其迁移优先级就越高。