用于资源管理和资源分配的方法和系统

摘要

用于资源管理的资源信用树包括叶节点和非叶节点。非叶节点包括跟节点和内部节点。资源管理包括初始化与资源池对应的操作、利用哈希函数选择资源信用树的叶节点以及识别叶节点的可用信用的数量。资源管理还可以包括基于确定可用信用的数量小于所需的信用数量或确定叶节点的容量小于要释放到资源信用树的信用数量与可用信用的数量的和，通过反向遍历路径从叶节点遍历到第一非叶节点。资源管理还可以包括从资源信用树分配信用以及将信用释放到资源信用树。

权利要求

1.一种用于资源管理的方法，包括：初始化用于分配与资源池对应的第一数量的信用的第一操作；

利用哈希函数选择资源信用树的第一叶节点；

识别第一叶节点的可用信用的数量；

由计算机处理器确定信用的第一数量超过第一叶节点的可用信用的数量；

从第一叶节点开始，通过第一反向遍历路径遍历资源信用树到资源信用树的第一非叶节点；

在遍历资源信用树的同时，基于第一反向遍历路径中的第一多个节点计算级联信用的第一数目，其中第一反向遍历路径包括所述第一叶节点、所述第一非叶节点、和第二非叶节点；

识别第一非叶节点的可用信用的数量；

由计算机处理器确定第一非叶节点的可用信用的数量超过级联信用的第一数目；以及响应于确定第一非叶节点的可用信用的数量超过级联信用的第一数目，从第一非叶节点分配第一数量的信用。

2.如权利要求1所述的方法，其中计算级联信用的第一数目基于第一反向遍历路径中的第一多个节点的多个预定义的容量。

3.如权利要求1或权利要求2所述的方法，还包括：在从第一非叶节点分配第一数量的信用之后，将级联信用的第一数目的剩余部分转移到第一多个节点当中的多个其它节点。

4.如权利要求1或权利要求2所述的方法，还包括：初始化用于分配与资源池对应的第二数量的信用的第二操作；

从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到资源信用树的根节点；

在遍历资源信用树的同时，基于第二反向遍历路径中的第二多个节点的每一个的预定义的容量计算级联信用的第二数目，其中第二反向遍历路径包括第二叶节点和根节点；

识别根节点的可用信用的数量；

确定级联信用的第二数目超过根节点的可用信用的数量；

识别包括资源池的附加可用信用的计数的资源对象；

确定附加可用信用的计数超过级联信用的第二数目；以及在确定附加可用信用的计数超过级联信用的第二数目之后，从资源对象中获得级联信用的第二数目。

5.如权利要求1或权利要求2所述的方法，还包括：初始化用于分配与资源池对应的第二数量的信用的第二操作，其中第二操作包括优先级标记；

从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到根节点；

识别根节点的可用信用的数量；

确定信用的第二数量超过根节点的可用信用的数量；

识别包括资源池的附加可用信用的计数的资源对象；

确定信用的第二数量超过附加可用信用的计数；以及基于优先级标记并且在确定信用的第二数量超过附加可用信用的计数之后，将资源信用树中所有可用信用转移到根节点。

6.如权利要求5所述的方法，还包括：在转移所有可用信用之后，计算根节点的信用的更新的可用数量；

确定信用的第二数量超过信用的更新的可用数量；

识别资源信用树的扇形展开数量；以及在确定信用的第二数量超过信用的更新的可用数量之后，基于扇形展开数量的因子从资源信用树中移除第二多个节点。

7.如权利要求5所述的方法，还包括：在转移所有可用信用之后，计算根节点的信用的更新的可用数量；

确定信用的更新的可用数量超过信用的第二数量；以及分配第二数量的信用。

8.如权利要求1或权利要求2所述的方法，还包括：计算根节点的信用的更新的可用数量；

确定信用的更新的可用数量足以填充第二多个节点；

识别资源信用树的扇形展开数量；以及在确定信用的更新的可用数量足以填充第二多个节点之后，基于扇形展开数量的因子将第二多个节点增加到资源信用树。

9.如权利要求1或权利要求2所述的方法，还包括：初始化用于分配与资源池对应的第二数量的信用的第二操作，其中第二操作包括保留参数；

从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到第三非叶节点；

识别第三非叶节点的可用信用的数量；

确定第三非叶节点的可用信用的数量超过信用的第二数量；

识别包括资源池的附加可用信用的计数的资源对象；

确定保留参数超过附加可用信用的计数；以及响应于确定保留参数超过附加可用信用的计数，发送失败通知。

10.如权利要求1或权利要求2所述的方法，还包括：识别第一叶节点的容量；以及

基于容量的预定义的部分，将多个信用从第一非叶节点转移到第一叶节点。

11.如权利要求1或权利要求2所述的方法，还包括：初始化用于分配与资源池对应的第二数量的信用的第二操作；

利用哈希函数选择资源信用树的第二叶节点；

识别第二叶节点的可用信用的数量；

确定第二叶节点的可用信用的数量超过信用的第二数量；以及从第二叶节点分配第二数量的信用。

12.如权利要求1所述的方法，还包括：将级联信用的第一数目初始化到信用的第一数量。

13.一种用于资源管理的系统，包括：用于初始化用于分配与资源池对应的第一数量的信用的第一操作的装置；

用于利用哈希函数选择资源信用树的第一叶节点的装置；

用于识别第一叶节点的可用信用的数量的装置；

用于由计算机处理器确定信用的第一数量超过第一叶节点的可用信用的数量的装置；

用于从第一叶节点开始，通过第一反向遍历路径遍历资源信用树到资源信用树的第一非叶节点的装置；

用于在遍历资源信用树的同时，基于第一反向遍历路径中的第一多个节点计算级联信用的第一数目的装置，其中第一反向遍历路径包括所述第一叶节点、所述第一非叶节点、和第二非叶节点；

用于识别第一非叶节点的可用信用的数量的装置；

用于由计算机处理器确定第一非叶节点的可用信用的数量超过级联信用的第一数目的装置；以及用于响应于确定第一非叶节点的可用信用的数量超过级联信用的第一数目，从第一非叶节点分配第一数量的信用的装置。

14.如权利要求13所述的系统，其中计算级联信用的第一数目基于第一反向遍历路径中的第一多个节点的多个预定义的容量。

15.如权利要求13或权利要求14所述的系统，还包括：用于在从第一非叶节点分配第一数量的信用之后，将级联信用的第一数目的剩余部分转移到第一多个节点当中的多个其它节点的装置。

16.如权利要求13或权利要求14所述的系统，还包括：用于初始化用于分配与资源池对应的第二数量的信用的第二操作的装置；

用于从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到资源信用树的根节点的装置；

用于在遍历资源信用树的同时，基于第二反向遍历路径中的第二多个节点的每一个的预定义的容量计算级联信用的第二数目的装置，其中第二反向遍历路径包括第二叶节点和根节点；

用于识别根节点的可用信用的数量的装置；

用于确定级联信用的第二数目超过根节点的可用信用的数量的装置；

用于识别包括资源池的附加可用信用的计数的资源对象的装置；

用于确定附加可用信用的计数超过级联信用的第二数目的装置；以及用于在确定附加可用信用的计数超过级联信用的第二数目之后，从资源对象中获得级联信用的第二数目的装置。

17.如权利要求13或权利要求14所述的系统，还包括：用于初始化用于分配与资源池对应的第二数量的信用的第二操作的装置，其中第二操作包括优先级标记；

用于从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到根节点的装置；

用于识别根节点的可用信用的数量的装置；

用于确定信用的第二数量超过根节点的可用信用的数量的装置；

用于识别包括资源池的附加可用信用的计数的资源对象的装置；

用于确定信用的第二数量超过附加可用信用的计数的装置；以及用于基于优先级标记并且在确定信用的第二数量超过附加可用信用的计数之后，将资源信用树中所有可用信用转移到根节点的装置。

18.如权利要求17所述的系统，还包括：用于在转移所有可用信用之后，计算根节点的信用的更新的可用数量的装置；

用于确定信用的第二数量超过信用的更新的可用数量的装置；

用于识别资源信用树的扇形展开数量的装置；以及用于在确定信用的第二数量超过信用的更新的可用数量之后，基于扇形展开数量的因子从资源信用树中移除第二多个节点的装置。

19.如权利要求17所述的系统，还包括：用于在转移所有可用信用之后，计算根节点的信用的更新的可用数量的装置；

用于确定信用的更新的可用数量超过信用的第二数量的装置；以及用于分配第二数量的信用的装置。

20.如权利要求13或权利要求14所述的系统，还包括：用于计算根节点的信用的更新的可用数量的装置；

用于确定信用的更新的可用数量足以填充第二多个节点的装置；

用于识别资源信用树的扇形展开数量的装置；以及用于在确定信用的更新的可用数量足以填充第二多个节点之后，基于扇形展开数量的因子将第二多个节点增加到资源信用树的装置。

21.如权利要求13或权利要求14所述的系统，还包括：用于初始化用于分配与资源池对应的第二数量的信用的第二操作的装置，其中第二操作包括保留参数；

用于从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到第三非叶节点的装置；

用于识别第三非叶节点的可用信用的数量的装置；

用于确定第三非叶节点的可用信用的数量超过信用的第二数量的装置；

用于识别包括资源池的附加可用信用的计数的资源对象的装置；

用于确定保留参数超过附加可用信用的计数的装置；以及用于响应于确定保留参数超过附加可用信用的计数，发送失败通知的装置。

22.如权利要求13或权利要求14所述的系统，还包括：用于识别第一叶节点的容量的装置；以及用于基于容量的预定义的部分，将多个信用从第一非叶节点转移到第一叶节点的装置。

23.如权利要求13或权利要求14所述的系统，还包括：用于初始化用于分配与资源池对应的第二数量的信用的第二操作的装置；

用于利用哈希函数选择资源信用树的第二叶节点的装置；

用于识别第二叶节点的可用信用的数量的装置；

用于确定第二叶节点的可用信用的数量超过信用的第二数量的装置；以及用于从第二叶节点分配第二数量的信用的装置。

24.如权利要求13所述的系统，还包括：用于将级联信用的第一数目初始化到信用的第一数量的装置。

25.一种用于资源分配的系统，包括：第一计算机处理器；

资源信用树，包括：

多个非叶节点，包括根节点和多个内部节点；以及多个叶节点；

资源对象，包括资源池的附加可用信用的数目；

第一客户端，在第一计算机处理器上运行并包括以下功能：初始化用于分配第一数量的信用的第一操作；

利用哈希函数选择多个叶节点的第一叶节点；

从第一叶节点开始，通过第一反向遍历路径遍历资源信用树到多个非叶节点的第一非叶节点；

在遍历资源信用树的同时，基于第一反向遍历路径中的第一多个节点计算级联信用的第一数目，其中第一反向遍历路径包括所述第一叶节点、所述第一非叶节点、和第二非叶节点；

识别第一非叶节点的可用信用的数量；

确定第一非叶节点的可用信用的数量超过级联信用的第一数目；以及响应于确定第一非叶节点的可用信用的数量超过级联信用的第一数目，从第一非叶节点分配第一数量的信用。

26.如权利要求25所述的系统，还包括：第二计算机处理器；

在第二计算机处理器上运行并与第一客户端并行的第二客户端，包括以下功能：初始化用于分配与资源池对应的第二数量的信用的第二操作；以及当通过第一反向遍历路径遍历资源信用树时：从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到资源信用树的根节点。

27.如权利要求25或权利要求26所述的系统，其中第一多个叶节点的数量随多个计算机处理器的数量单调地增加。

说明书

用于资源管理和资源分配的方法和系统

技术领域

[0001] 本发明涉及用于具有有限数量的资源的系统的资源分配算法，并且具体涉及使用资源信用树的方法和系统。

背景技术

[0002] 在具有有限数量的资源的系统中，资源分配问题可能难以解决。在最坏情况下，系统可能遇到空转情况或进入死锁状态。其它不期望的结果可以包括丢弃或延迟的高优先级请求和极低效率(例如，低资源利用率，等等)。

[0003] 资源单元是可以由单个客户端(例如，线程)分配和释放的资源的任何片段。资源单元可以是系统范围共享的一组资源单元的一部分。资源单元的分配给客户端使用资源单元的权利。例如，资源单元可以是物理存储器的页、盘上交换空间的页、中央处理单元(CPU)上运行时间的一个单元、网络数据包、数据库缓冲器高速缓存中的块等等。资源分配算法可以被使用以分配和释放资源单元。资源分配算法在硬件和软件应用中的合理使用是众多并且变化的。

发明内容

[0004] 一般，在一方面，本发明涉及用于资源管理的方法。所述方法包括初始化用于分配与资源池对应的多个信用的操作、利用哈希函数选择资源信用树的叶节点、识别叶节点的可用信用的数量、以及确定信用的数量超过叶节点的可用信用的数量。所述方法还包括从叶节点开始通过反向遍历路径遍历资源信用树到资源信用树的第一非叶节点、以及在遍历资源信用树的同时基于反向遍历路径中的节点计算级联信用的数目(tally)。反向遍历路径包括叶节点、第一非叶节点、和第二非叶节点。所述方法还包括识别第一非叶节点的可用信用的数量、确定第一非叶节点的可用信用的数量超过级联信用的数目、以及响应于确定第一非叶节点的可用信用的数量超过级联信用的数目从第一非叶节点分配所述数量的信用。

[0005] 一般，在一方面，本发明涉及包括用于资源管理的指令的程序产品。所述指令包括以下功能：初始化用于释放多个信用的操作、初始化将信用级联到所述多个信用的数目、利用哈希函数选择资源信用树的叶节点、识别叶节点的容量和叶节点的可用信用的数量、计算分配的信用的数量和叶节点的可用信用的数量的总和、以及确定总和超过叶节点的容量。所述指令还包括以下功能：从叶节点开始并且基于确定总和超过叶节点的容量，通过反向遍历路径遍历资源信用到资源信用树的第一非叶节点、以及在遍历资源信用树的同时基于反向遍历路径中的节点修改级联信用的数目。反向遍历路径包括叶节点、第一非叶节点、和第二非叶节点。此外，级联信用的数目用于在遍历资源信用树的同时更新节点的至少一个的可用信用的数量。所述指令还包括以下功能：识别第一非叶节点的容量和第一非叶节点的可用信用的数量、以及基于第一非叶节点的容量和第一非叶节点的可用信用的数量将所述数目的级联信用释放到第一非叶节点。计算机程序产品的实施例可以包括存储指令的非瞬时介质。

[0006] 一般，在一方面，本发明的实施例涉及用于资源分配的系统。所述系统包括计算机处理器、资源信用树、资源对象、和客户端。资源信用树包括非叶节点和叶节点，非叶节点包括根节点和内部节点。资源对象包括资源池的附加可用信用的计数。所述客户端包括以下功能：初始化用于分配多个信用的操作、利用哈希函数选择叶节点、从叶节点开始通过反向遍历路径遍历资源信用树到第一非叶节点、以及在遍历资源信用树的同时基于反向遍历路径中的节点计算级联信用的数目。反向遍历路径包括叶节点、第一非叶节点、和第二非叶节点。所述客户端还包括以下功能：识别第一非叶节点的可用信用的数量、确定第一非叶节点的可用信用的数量超过级联信用的数目、以及响应于确定第一非叶节点的可用信用的数量超过级联信用的第一数目从第一非叶节点分配所述数量的信用。

[0007] 从以下说明书和附加的权利要求书中，本发明的其它方面将清晰。

附图说明

[0008] 图1示出根据本发明的一个或多个实施例的示意图。

[0009] 图2示出根据本发明的一个或多个实施例的资源信用树。

[0010] 图3、4A、4B、和5示出根据本发明的一个或多个实施例的流程图。

[0011] 图6A-6C示出根据本发明的一个或多个实施例的资源信用树。

[0012] 图7A和7B示出根据本发明的一个或多个实施例的示例资源信用树。

[0013] 图8示出根据本发明的一个或多个实施例的计算机系统。

具体实施方式

[0014] 现在将参考附图详细描述本发明的具体实施例。各个图中的类似的元件由类似的参考数字表示以便于一致。

[0015] 在下面具体实施方式中，阐述细节以便提供对本发明的更彻底的理解。但是，本领域普通技术人员显然可知，可以不用这些特定的细节来实践本发明。在其它实例中，没有详细描述公知的特征以避免不必要地复杂本发明。

[0016] 一般，本发明的实施例提供用于分配和/或释放与资源信用树对应的信用的方法和系统。一般，本发明的实施例启动分配操作以分配或释放与资源池对应的一个或多个信用。基于分配操作，可以在保持级联信用的数目的同时遍历资源信用树。在遍历期间，在遍历路径中用于一个或多个节点的可用信用的数量可以与级联信用的数目相比较。基于比较，需要的信用可以从资源信用树中被分配或释放。

[0017] 图1示出根据本发明的一个实施例的系统(199)。如图1所示，系统(199)具有包括资源管理引擎(100)、资源对象(110)、资源信用树(105)、资源池(115)、和一个或多个客户端(例如，客户端A(120)、客户端B(125)、客户端C(130))的多个组件。系统的组件可以安置在相同的设备上(例如，服务器、大型机、桌上个人计算机(PC)、膝上计算机、个人数字助理(PDA)、电话、移动电话、电话亭、电缆盒、和任何其它设备)或可以利用有线和/或无线分段安置在由网络(例如互联网)连接的分离的设备上。在本发明给定的实施例之内，可以存在多于一个的分离部件运行在一个设备上，以及这些组件的任何组合。

[0018] 在本发明的一个或多个实施例中，资源池(115)是资源单元的共享集合。资源池(115)可以是物理资源、软件资源、或表示为存储器中的数据结构的一个或多个共享资源的抽象。资源池(115)的示例可以包括但是不局限于一个或多个硬盘驱动器、一个或多个中央处理单元(CPU)、随机存取存储器(RAM)、文件系统、数据库、和/或能够分配一个或多个资源单元的任何共享资源。资源池(115)可以被分割为资源单元。资源池(115)中的每个资源单元可以在任何给定时间被分配给至多一个客户端。资源单元的示例可以包括但是不局限于物理存储器的页、盘上的交换空间的页、CPU运行时间的一个或多个单元、和数据库缓冲器高速缓存中的块。

[0019] 在本发明的一个或多个实施例中，信用表示使用资源池(115)中的一个或多个资源单元的专有权。例如，单个信用可以表示分配物理存储器的页、分配盘上交换空间的页、锁定存储器中的页、运行中央处理单元(CPU)时间的一个单元、发送网络数据包、分配数据库缓冲器高速缓存中的块等的权利。

[0020] 在本发明的一个或多个实施例中，资源管理引擎(100)包括用于管理信用的数据结构。具体地，在本发明的一个或多个实施例中，资源管理引擎(100)包括资源信用树(105)和资源对象(110)。资源管理引擎(100)可以可选地包括用于操作资源信用树(105)以便收缩或扩大资源信用树(105)的指令。

[0021] 在本发明的一个或多个实施例中，资源信用树(105)是与资源池(115)对应的数据结构。资源信用树(105)可以表示至少与资源池对应的可用信用的子集。在本发明的一个或多个实施例中，资源信用树(105)包括非叶节点和叶节点。在本发明的一个或多个实施例中，非叶节点包括根节点和可选地一个或多个内部节点。具体地，非叶节点可以是根节点或内部节点。资源信用树(105)中的节点可以被一个或多个边连接以使得每个节点(除根节点之外)具有仅仅一个父代。根据本发明的各个实施例，资源信用树(105)可以是二元树、k元树(对任何整数k＞2)、或不规则的树。完全二元或k元树是指其中每个非叶节点具有相等数量的子(即，分别是2和k)的资源信用树(105)。图2描述根据本发明的一个或多个实施例的资源信用树。

[0022] 图2示出根据本发明的一个或多个实施例的资源信用树(105)。在图2中，共线的点的使用指示与之前和之后的项(相对于点)相似类型的附加项可以可选地存在。如图2所示，资源信用树(105)具有包括根节点(200)、一个或多个内部节点(例如，202、204、206、208、210、212)、和一个或多个叶节点(例如，214、216、218、220、222、224、226、228)的多个组件。
在本发明的一个或多个实施例中，资源信用树中叶节点的数量与处理器的数量大致成比例。换句话说，叶节点的数量随处理器的数量单调增加。例如，叶节点的数量可以与处理器的数量成一对一关系、二对一关系等。

[0023] 资源信用树(105)中的每个节点包括信用的可用数量(Cavail)(250)、容量(Cmax)(252)、和锁定值(254)。资源信用树(105)的组件可以被存储在一个或多个存储设备上，包括但不限于一个或多个硬盘驱动器、一个或多个随机存取存储器(RAM)设备、一个或多个光存储器设备、一个或多个闪速存储设备、和/或它的任何组合。资源信用树(105)的组件可以位于相同的设备之内或可以位于由网络(例如互联网)利用有线和/或无线段连接的分离的设备上。在本发明给定的实施例之内，可以存在多于一个分离的组件位于设备上，以及这些组件的任何组合。

[0024] 资源信用树(105)的深度值是指从根节点处的零值起并向下在每个后续级别递增的树的级别。资源信用树(105)的高度值是指从树的最低级别处的零值起并向上在每个后续级别递增的树的级别。用于资源信用树(105)的高度值和深度值被指示在图2的纵轴上。

[0025] 在本发明的一个或多个实施例中，信用的可用数量(Cavail)(250)是在可用于分配的节点中的未被分配的信用的数量。资源信用树(105)中的每个节点可以具有不同的Cavail值(取决于使用率)。信用的可用数量(Cavail)(250)可以在零和容量(Cmax)(252)(包含)之间的值的范围。

[0026] 在本发明的一个或多个实施例中，容量(Cmax)(252)是可以被存储在节点中的信用的最大数量。对于树的每个级别，容量(Cmax)(252)可以是恒定的。因此，在本发明的一个或多个实施例中，在资源信用树(105)的每个级别的树创建时间限定Cmax(252)的恒定值。此外，在本发明的一个或多个实施例中，Cmax(252)的恒定值可以在每个随后级别(从高度＝0开始)处加倍。给定二元树的叶节点的容量(Cmax)，树中其它节点的容量可以是Cmax＊2^高度(节点)，其中高度(叶)＝0。对于k元树，节点的容量可以被计算为叶节点容量(Cmax)乘以k的节点在树中高度次幂的函数：Cmax＊k^高度(节点)。对于不规则的树，节点的容量可以是节点子的容量的总和。

[0027] 在本发明的一个或多个实施例中，资源信用树(105)中的每个节点包括表示节点状态的锁定值(254)。所述状态可以被锁定或解锁，并且可以包括对当前保持节点上的锁的客户端的参考。

[0028] 在本发明的一个或多个实施例中，沿着正向遍历路径或反向遍历路径遍历资源信用树(105)。正向遍历路径是在位于树的较高高度处的节点开始并在位于树的较低高度处的节点结束沿着资源信用树(105)的分支的任何连续路径。例如，在本发明的一个或多个实施例中，202→208→218→和204→212是资源信用树(105)中的正向遍历路径。反向遍历路径是在位于树的较低高度处的节点开始并在位于树的较高高度处的节点结束沿着资源信用树(105)的分支的任何连续路径。例如，在本发明的一个或多个实施例中，220→208→202和204→200是资源信用树(105)中的反向遍历路径。

[0029] 返回到图1，客户端(例如，客户端A(120)、客户端B(125))可以是需要来自于资源信用树的一个或多个信用的任何处理、线程、或实体。在本发明的一个或多个实施例中，客户端包括初始化一个或多个操作以在资源信用树(105)中分配信用(即，分配操作)的功能。分配操作是由客户端执行的用于访问由资源信用树(105)中的信用表示的一个或多个资源单元的指令的集合。分配操作可以由客户端(例如，客户端A(120)、客户端B(125)、或客户端C(130))初始化并且可以是客户端所需的信用数量(Rorig)。在本发明的一个或多个实施例中，在初始化分配操作时，客户端将级联信用(R)的数目初始化到需要的信用数量(Rorig)。
数目是在沿着遍历路径和/或资源对象(110)遍历用于在一个或多个节点之间的分布的资源信用树(105)期间维持的信用的数量。

[0030] 在本发明的一个或多个实施例中，客户端包括响应于分配需要选择资源信用树(105)的叶节点作为当前节点的功能。在本发明的一个或多个实施例中，客户端被配置为基于哈希函数选择叶节点。客户端可以使用与客户端相关联的客户端标识符作为到哈希函数的输入。客户端标识符可以由操作系统或其它实体被分配给客户端。例如，客户端标识符可以是由操作系统分配到线程的处理标识符、运行线程的硬件处理器的处理器标识符、或与线程相关联的另一个标识符。

[0031] 在本发明的一个或多个实施例中，客户端包括遍历资源信用树(105)以便响应于初始化分配操作分配多个信用的功能。客户端可以沿着反向遍历路径从选择的叶节点到目标节点(即，选择的叶节点的祖系)遍历资源信用树(105)。随着客户端沿着反向遍历路径分析节点，每个节点可以被依次锁定直到具有足够可用信用(即，大于或等于级联信用的数目)的目标节点被识别。在完成分配操作之后，客户端可以在剩余信用(来自于该数目的级联信用)沿着反向遍历路径的任何需要的分布期间或之后解锁节点。

[0032] 在本发明的一个或多个实施例中，在资源信用树(105)的遍历期间，客户端可以锁定当前节点并且然后识别当前节点的可用信用的数量(Cavail)。可用信用的数量然后可以与级联信用的数目(R)相比较。如果客户端确定可用信用的数量(Cavail)大于或等于R，则客户端可以设置Cavail等于(Cavail-R)并且然后解锁当前节点。客户端然后可以分配所需数量的信用(Rorig)并且进行沿着反向遍历路径将数目的级联信用的剩余(如果有的话)分布到一个或多个节点。图4B描述在本发明的一个或多个实施例中的分布R中的剩余的方法。

[0033] 在本发明的一个或多个实施例中，如果客户端确定当前节点的可用信用的数量(Cavail)＜R，则客户端可以更新R的值并且继续遍历资源信用树(105)。如果遍历到达资源信用树(105)的根节点并且根节点的可用信用的数量(Cavail)小于R，则客户端可以被配置为从资源对象(110)导入一个或多个信用以便完成分配操作。如果客户端确定资源对象中可用信用的计数小于级联信用(R)的数目，则分配操作可以在资源对象处被阻止。类似地，如果客户端不能访问节点因为它被锁定，则操作可以在节点处被阻止直到节点被解锁。在本发明的一个或多个实施例中，如果资源管理引擎(100)和/或客户端确定多于一个操作在节点处或外来资源对象处被阻止，则资源管理引擎和/或客户端可以根据选择阻止的操作的预定义的方法(例如，先进先出，基于优先级标记、基于需要的信用的数量(Rorig)等)解锁操作。

[0034] 在本发明一个或多个实施例中，资源对象(110)是包括资源池中可用(非分配的)信用的计数的数据结构。根据本发明的各种实施例，资源对象(110)可以包括与可用信用的计数或资源池的状态有关的任何其它信息。因此，资源对象(110)包括在给定时间点不包括在资源信用树(105)中的未分配的信用的计数。在典型实例中，资源对象(110)中的可用信用的计数明显地大于资源信用树(105)的节点内的信用的总数。在本发明的一个或多个实施例中，资源对象(110)允许系统(199)中一个或多个其它处理或模块(例如，客户端)查询可用信用的计数和/或响应于改变需求将信用分布到资源信用树(105)和从资源信用树(105)分布。

[0035] 在本发明的一个或多个实施例中，客户端包括从资源对象(110)获得一个或多个信用的功能。在资源信用树(105)的遍历期间到达根节点时，客户端可以确定级联信用的数目超过根节点的可用信用的数量(Cavail)。在这种情况下，在本发明的一个或多个实施例中，客户端可以从资源对象获得级联信用的数目。在完成分配操作之后，客户端可以根据分布剩余信用的一个或多个方法将数目的级联信用的剩余部分转移到资源信用树(105)。

[0036] 在本发明的一个或多个实施例中，客户端包括在反向遍历路径中将数目的级联信用的剩余部分分布到一个或多个节点(在遍历资源信用树(105)之后)。客户端可以被配置为识别反向遍历路径中的具有小于它相应容量的一半的可用信用数量(Cavail)(Cavail＜(Cmax/2))的每个节点。客户端可以通过从数目的级联信用(R)的剩余部分中转移信用来将这些识别的节点的可用信用数量(Cavail)增加到(Cmax/2)。在本发明的一个或多个实施例中，前述的表达式“(Cmax/2)”可以用容量(Cmax)的任何其它部分或在一些情况下用整个容量代替。特定使用情况和/或应用可以需要根据相关的性能考虑来调整此部分数量。

[0037] 在本发明的一个或多个实施例中，分配操作包括优先级标记。在本发明的一个或多个实施例中，当具有优先级标记的分配操作被在根节点处阻止时，客户端被配置为将全部信用(或任何预定义的百分比或它的部分)从资源信用树(105)中的全部节点转移到根节点。如果客户端确定根节点的可用信用的数量(Cavail)(在转移信用之后)是足够的，则分配操作被解锁并且从根节点完成。在本发明的一个或多个实施例中，如果客户端确定根节点的可用信用的数量(Cavail)(在转移信用之后)不足够完成分配操作，则客户端可以计算将资源信用树(105)中的每个叶节点填充到它的容量(Cmax)所需的信用的数量。

[0038] 如果资源管理引擎(100)和/或客户端确定根节点的可用信用的数量小于将叶节点填充到容量所需的信用数量，则资源管理引擎(100)或客户端可以收缩资源信用树(105)(即，减小大小)。在本发明的一个或多个实施例中，资源信用树(105)的大小减小资源信用树(105)的扇形展开数量的因子。用于规则资源信用树(105)的扇形展开数量的因子是每非叶节点的子的数量。资源管理引擎(100)或客户端可以基于选择节点的任何预定义的方法(例如，按百分比分配，任何树遍历算法，等等)选择用于删除/失活的节点。减小树的大小的处理可以在继续树的正常操作(分配/释放信用)的同时执行。在本发明的一个或多个实施例中，资源管理引擎(100)或客户端可以响应于优先化的分配操作而收缩资源信用树(105)直到仅仅根节点是激活的。

[0039] 在本发明的一个或多个实施例中，分配操作包括保留参数。保留参数可以是资源对象中的最小信用计数。最初，客户端可以执行资源信用树(105)的反向遍历并且识别具有足够信用以满足分配操作(例如，当节点的可用信用的数量超过级联信用的数目时)的节点。在这一点上，虽然反向遍历路径中的全部节点被锁定，但是客户端可以在没有锁定资源对象(110)的情况下检查资源对象(110)。如果客户端确定资源对象的可用信用的数目大于或等于保留参数，则客户端进行信用的分配并且根据需要转移数目的级联信用的剩余部分。如果客户端确定资源对象的可用信用的数目小于保留参数，则客户端可以确定分配操作失败。

[0040] 在本发明的一个或多个实施例中，客户端包括检测分配操作在资源对象处被阻止的功能。如果确定资源对象不具有完成与操作对应的数目的级联信用的足够的可用信用计数，则操作可以在资源对象处被阻止。在初始化将一个或多个信用释放到资源信用树(105)的操作时，客户端可以检查任何分配操作是否在资源对象(110)处被阻止。如果客户端确定一个或多个阻止的分配操作存在，则客户端可以响应于释放操作直接将信用释放到资源对象(并且绕过资源信用树(105)的遍历)。

[0041] 在本发明的一个或多个实施例中，客户端包括初始化释放(即，解除分配)一个或多个分配的信用的操作(即，释放操作)的功能。释放(即，解除分配)操作是由客户端执行以释放一个或多个先前分配的资源单元的操作。释放操作可以由客户端(例如，客户端A(120)、客户端B(125)、或客户端C(130))执行并且可以是要由客户端释放的信用的数量(Rorig)。在本发明的一个或多个实施例中，多个客户端可以同时访问资源信用树。在本发明的一个或多个实施例中，在初始化释放操作时，客户端将级联信用的数目(R)初始化到需要的信用的数量(Rorig)。

[0042] 客户端然后可以选择资源信用树的叶节点作为当前节点。如上所述，根据本发明的各种实施例，可以利用哈希函数或任何其它选择的方法执行叶节点的选择。

[0043] 在本发明的一个或多个实施例中，客户端包括遍历资源信用树(105)以便响应于初始化释放操作释放多个信用的功能。客户端可以沿着反向遍历路径从选择的叶节点到目标节点(即，选择的叶节点的祖系)遍历资源信用树(105)。随着客户端沿着反向遍历路径分析节点，每个节点可以依次被锁定、平衡、然后在进行到下一个节点之前被解锁。客户端可以继续平衡节点直到级联信用的数目(R)耗尽。

[0044] 在本发明的一个或多个实施例中，客户端包括在资源信用树(105)的反向遍历(响应于初始化释放操作执行)期间平衡当前节点的功能。首先，客户端可以识别当前节点的可用信用的数量(Cavail)。其次，客户端可以将级联信用的数目(R)增加到可用信用的数量(即，设置Cavail＝Cavail+R)。然后，客户端可以确定可用信用的数量(Cavail)是否超过当前节点的容量(Cmax)。如果客户端确定容量没有被超过，则客户端可以解锁当前节点并且结束遍历。

[0045] 如果客户端确定容量(Cmax)被超过，则客户端可以解锁当前节点并且设置R＝Cavail-(Cmax/2)且Cavail＝(Cmax/2)。如果当前节点不是根节点，则客户端可以沿着反向遍历路径继续进行遍历。如果当前节点是根节点，则客户端可以将级联信用的数目输出到资源对象。在本发明的一个或多个实施例中，在前述的公式(R＝Cavail-(Cmax/2)和Cavail＝(Cmax/2)中的表达式“(Cmax/2)”可以用容量(Cmax)的任何其它部分或在一些情况下用整个容量代替。特定使用情况和/或应用可以需要根据相关的性能考虑来调整此部分数量。

[0046] 在本发明的一个或多个实施例中，资源管理引擎(100)和/或客户端包括扩大资源信用树(105)(即，增加大小)的功能。在本发明的一个或多个实施例中，扩大资源信用树(105)可以利用释放操作执行。具体地，在资源信用树的反向遍历到达根节点时并且在数目输出到资源对象之前，可以执行扩大操作。资源管理引擎(100)和/或客户端可以被配置为作为扩大操作的一部分确定根节点中的可用信用的数量足够填充更大数量的叶节点达到容量。在本发明的一个或多个实施例中，仅仅在资源信用树从它的初始大小收缩时执行扩大操作。在做出此确定时，资源管理引擎(100)或客户端可以通过实际上反转收缩操作来扩大资源信用树(105)。

[0047] 在本发明的一个或多个实施例中，客户端基于应用和/或性能考虑选择资源信用树中叶节点的数量(N)和叶节点的容量(Cmax)。例如，当在具有多个CPU的计算设备上执行系统(199)时，客户端可以设置叶节点的数量(N)等于CPU的数量以使得N个同时运行的线程在没有竞争(假定理想的哈希函数)的情况下可以每个都访问叶节点。

[0048] 虽然在图1中未示出，但是客户端可以间接地访问资源分配树，诸如经由代理线程。例如，在分布式计算机系统中，客户端可以是在远离具有资源信用树的计算机系统的计算机系统上运行的线程。在此类情况中，客户端可以通过将请求发送到在具有资源信用树的计算机系统上运行的代理线程来执行资源分配操作和释放操作。代理线程可以执行分配和/或释放信用的步骤。

[0049] 图3示出在本发明的一个或多个实施例中用于利用一个或多个资源单元的方法的流程图。虽然在流程图中依次呈现并描述各个步骤，但是本领域的普通技术人员将理解，可以以不同的顺序执行一些或所有步骤并且可以并行执行一些或所有步骤。此外，在本发明的一个或多个实施例中，下面描述的一个或多个步骤可以被省略、重复、和/或以不同的顺序执行。因此，图3所示的步骤的具体布置不应该被认为是限制本发明的范围。

[0050] 在本发明的一个或多个实施例中，在步骤300中，客户端利用一个或多个资源单元进行初始化。可以在多个客户端当中共享一个或多个资源单元。客户端可以利用一个或多个资源单元通过开始运行用于访问资源信用树的指令进行初始化。例如，如果资源信用树是内核数据结构并且客户端是用户级应用，则客户端可以做出到操作系统内核的系统调用。在本发明的一个或多个实施例中，系统调用将运行客户端的用户级线程转换到可以访问资源信用树的内核级线程。如另一个示例，如果资源信用树是用户级数据结构，则客户端可以开始执行指令(以下讨论的)以访问资源信用树。

[0051] 在本发明的一个或多个实施例中，在步骤305中，在本发明的一个或多个实施例中，利用资源信用树分配表示可用资源单元的一个或多个信用并且锁定可用资源单元。可以执行从资源信用树分配信用，例如，如以下和在图4A和4B讨论的。通过利用资源信用树，多个客户端可以同时获得资源信用。具体地，如以下和图4A和4B中讨论的，当客户端从资源信用树中获得信用时，客户端获得一个或多个节点上的锁定。通过具有资源信用树，多个客户端可以获得不同叶节点上的锁定，并且因此可以从资源信用树中同时或半同时获得信用。此外，树结构提供如下机制：分布信用以使得如果一个叶节点被访问多于其它叶节点，则该叶节点在需要时可以从父节点获得更多信用以便继续处理信用。

[0052] 在本发明的一个或多个实施例中，在从资源信用树中获得一个或多个信用之后或作为部分，客户端从资源池中获得对于每个信用在资源单元上的锁定。因此，资源信用限制可以在资源池中的资源单元上获得的锁定的数量。锁定可以被授权到请求的客户端以使得虽然资源单元被锁定但是客户端获得使用资源单元的专有权(步骤310)。在获得锁定之后，在本发明的一个或多个实施例中，客户端使用资源单元。

[0053] 在步骤315中，在本发明的一个或多个实施例中，在完成被锁定资源单元的使用时，客户端可以释放资源单元并且关联的释放操作被初始化以将分配的信用释放到资源信用树。因此，客户端可以将与释放的资源单元对应的信用分布回到资源信用树以使得新释放的信用再一次可用于分配。可以根据用于释放信用的特定方法释放信用(例如，以下讨论的图5的方法)。类似于用于分配信用的处理，利用资源信用树和/或释放信用的相关方法可以减少两个或更多个竞争的客户端之间锁定竞争的可能性。

[0054] 图4A和4B示出用于响应于请求从资源信用树中分配一个或多个信用的方法的流程图。虽然在流程图中依次呈现并描述各个步骤，但是本领域的普通技术人员将理解，可以以不同的顺序执行一些或所有步骤并且可以并行执行一些或所有步骤。此外，在本发明的一个或多个实施例中，下面描述的一个或多个步骤可以被省略、重复、和/或以不同的顺序执行。因此，图4A和4B所示的步骤的具体布置不应该被认为是限制本发明的范围。

[0055] 在步骤400中，在本发明的一个或多个实施例中，分配操作被初始化以分配Rorig个信用。Rorig个信用的数量可以是单个信用或多个信用。作为初始化分配操作的部分，在本发明的一个或多个实施例中，级联信用的数目(R)被初始化到Rorig。在本发明的一个或多个实施例中，每个分配操作对应于遍历资源信用树的客户端。如上所述，在分布式计算机系统中，代理线程可以被使用并可以被客户端初始化以执行分配操作。因此，在代理线程代表客户端执行动作时，客户端被认为执行动作。

[0056] 在步骤402中，在本发明的一个或多个实施例中，资源信用树的叶节点被选为当前节点。叶节点可以利用哈希函数选择并且可以基于在步骤400中初始化的分配操作。客户端标识符可以被输入作为到哈希函数的输入。在本发明的一个或多个实施例中，到哈希函数的独特输入的组合可以用来选择叶节点。

[0057] 在步骤404中，在本发明的一个或多个实施例中，当前节点被锁定。锁定的节点是向锁定的线程(例如，客户端的线程)仅仅授予写特权的节点。

[0058] 在步骤406中，在本发明的一个或多个实施例中，识别当前节点的可用信用的数量(Cavail)。可用信用的数量可以是零与当前节点的容量(Cmax)(包含)之间的任何数量。

[0059] 在步骤408中，在本发明的一个或多个实施例中，确定可用信用的数量(Cavail)是否大于或等于级联信用的数目(R)。如果确定Cavail＞＝R，则处理进行到步骤420。如果确定Cavail＜R，则处理进行到步骤410。

[0060] 在步骤410中，在本发明的一个或多个实施例中，确定可用信用的数量(Cavail)是否小于当前节点的容量的一半(Cmax/2)。如果确定Cavail＜(Cmax/2)，则处理进行到步骤412。如果确定Cavail＞＝(Cmax/2)，则处理进行到步骤414。

[0061] 在步骤412中，在本发明的一个或多个实施例中，级联信用的数目被(R)设置为等于R+[(Cmax/2)-Cavail]。对于步骤410、412、432和434，如上所述相对于图1，根据本发明的各种实施例，可以使用容量(Cmax)的任何部分或整个容量来代替Cmax/2。

[0062] 在步骤414中，在本发明的一个或多个实施例中，确定当前节点是否是资源信用树的根节点。如果确定当前节点是根节点，则处理进行到步骤416。如果确定当期节点不是根节点，则处理进行到步骤418。

[0063] 在步骤416中，在本发明的一个或多个实施例中，从资源对象中导入R个信用。从资源对象导入信用可以包括将资源对象中可用信用的计数简单地减少特定量(例如，R)。在执行步骤428到438时，特定量可以被增加到根节点或临时地存储。在本发明的一个或多个实施例中，在步骤418中，当前节点的父节点被选为当前节点。

[0064] 在步骤420中，在本发明的一个或多个实施例中，可用信用的数量(Cavail)被设置等于Cavail-R。因此，在步骤426中，级联信用的数目被从当前节点减少并且它的至少一部分用于分配所需的信用数量(Rorig)。在分配所需的信用数量(Rorig)之后，在图4B中的步骤428-438中，数目的级联信用的剩余部分可以在反向遍历路径中被分配到一个或多个节点。

[0065] 在步骤422中，在本发明的一个或多个实施例中，当前节点被解锁。解锁当前节点可以包括从当前分配操作中去除专有访问。

[0066] 在步骤424和426中，在本发明的一个或多个实施例中，响应于在步骤400中初始化的分配操作分配Rorig个信用。根据本发明的各个实施例，可以在步骤422或步骤432-436之前或结合这些步骤执行分配所需的信用数量(Rorig)。

[0067] 图4B示出描述相对于图4A(以上)描述的用于响应于初始化分配操作从资源信用树中分配一个或多个信用的继续方法。

[0068] 在步骤428中，在本发明的一个或多个实施例中，确定当前节点是否是叶节点。如果确定当前节点是叶节点，则处理结束。如果确定当前节点不是叶节点，则处理进行到步骤430。

[0069] 在步骤430中，在本发明的一个或多个实施例中，在当前路径上的下一个子节点被选为当前节点。因此，在步骤428-438中资源信用树可以被正向遍历。可替换地，在本发明的一个或多个实施例中，可以并行执行一个或多个步骤428-438。

[0070] 在步骤432中，在本发明的一个或多个实施例中，确定可用信用的数量(Cavail)是否小于容量(Cmax)的一半。如果确定Cavail＜(Cmax/2)，则处理进行到步骤434。如果确定Cavail＞＝(Cmax/2)，则处理进行到步骤436。

[0071] 在本发明的一个或多个实施例中，可用信用的数量(Cavail)然后被设置等于(Cmax/2)(步骤434)。接着，在本发明的一个或多个实施例中，当前节点被解锁(步骤436)。

[0072] 在步骤438中，确定当前节点是否是资源信用树的叶节点。如果确定当前节点是叶节点，则处理结束。如果确定当前节点不是叶节点，则处理进行到步骤430。

[0073] 在本发明的一个或多个实施例中，叶节点的容量(Cmax)可以被选择为足够大以给出良好性能，但是足够小使得树高速缓存总信用的小部分F。例如，给出具有扇形展开等于4的资源信用树，资源信用树可以包括最多Cmax＊N＊(log2(N)/2+1)个信用，其中N是资源信用树中的叶节点的数量。服务器上的资源可以与CPU的数量成线性比例，因此总信用可以近似为M＊N。在本发明的一个或多个实施例中，为了确保树高速缓存小于部分F，需要下列条件：(Cmax＊N＊(log2(N)/2+1))/(M＊N)＜F。求Cmax给出Cmax＜(F＊M)/(log2(N)/2+1)。例如，考虑使用信用表示具有N＝256个CPU，每个CPU有8GB存储器以及8KB的页大小的服务器上的存储器的空闲页。使用目标部分F＝0.001，Cmax可以被选择以使得Cmax＜(.001＊(8GB/8KB))/(log2(256)/2+1)→Cmax＜200。

[0074] 图5示出用于响应于初始化释放操作将一个或多个信用释放到资源信用树的方法的流程图。虽然依次呈现并描述流程图中的各个步骤时，但是本领域的技术人员将理解，可以以不同的顺序执行一些或所有步骤并且可以并行执行一些或所有步骤。此外，在本发明的一个或多个实施例中，下面描述的一个或多个步骤可以被省略、重复、和/或以不同的顺序执行。因此，图5所示步骤的具体布置不应该被认为是限制本发明的范围。

[0075] 在步骤500中，在本发明的一个或多个实施例中，初始化释放多个信用(Rorig)的释放操作。Rorig个信用的数量可以是单个信用或多个信用。作为初始化释放操作的部分，级联信用的数目(R)被初始化为Rorig。

[0076] 在步骤502中，在本发明的一个或多个实施例中，资源信用树的叶节点被选为当前节点。叶节点可以利用哈希函数(例如，采取客户端标识符作为输入)选择并且可以基于在步骤500中初始化的释放操作。

[0077] 在本发明的一个或多个实施例中，当前节点被锁定(步骤504)并且然后当前节点的可用信用的数量(Cavail)被设置等于Cavail+R(步骤506)。

[0078] 在步骤508中，在本发明的一个或多个实施例中，确定可用信用的数量(Cavail)是否大于当前节点的容量(Cmax)。如果确定Cavail＞Cmax，则处理进行到步骤510。如果确定Cavail＜＝Cmax，则处理进行到步骤520。

[0079] 在步骤510中，在本发明的一个或多个实施例中，级联信用的数目(R)被设置等于Cavail-(Cmax/2)。如同对于以上图1讨论的，容量(Cmax)的任何部分或整个容量可以代替在步骤510和512中的Cmax/2被使用。

[0080] 接着，在本发明的一个或多个实施例中，可用信用的数量(Cavail)被设置等于(Cmax/2)(步骤512)并且然后当前节点被解锁(步骤514)。

[0081] 在步骤516中，在本发明的一个或多个实施例中，确定当前节点是否是资源信用树的根节点。如果确定当前节点是根节点，则处理进行到步骤518。如果确定当前节点不是根节点，则处理进行到步骤522。

[0082] 在步骤518中，在本发明的一个或多个实施例中，R个信用被导出到资源对象。把R个信用导出到资源对象可以包括简单地将资源对象中可用信用的计数增加R。

[0083] 接着，在本发明的一个或多个实施例中，当前节点被解锁(步骤520)并且当前节点的父节点被选为当前节点(步骤522)。

[0084] 在本发明的一个或多个实施例中，资源信用树充当累积器。具体地，累积器可以用来确定客户端或一组客户端使用资源的次数。作为累积器，信用不被从资源信用树中分配。但是，每次客户端使用资源，客户端初始化释放操作(例如，执行图5的步骤)。管理程序或代理可以利用资源信用树识别客户端使用资源的次数。在此示例中，Cavail的值实际上是累积的和。累积器可以具有多种用途，诸如累积用于多线程处理的资源使用。在此类示例中，每个线程是单独的客户端。在另一个示例中，资源信用树可以在线程在CPU上运行一个时间定量之后累积总的CPU时间的运行总计。在该示例中，每次线程运行一个时间定量，线程就将信用增加到资源信用树(例如，通过执行图5的步骤)。资源信用树维持客户端已经使用的CPU时间的时间定量的数量的计数。

[0085] 在本发明的一个或多个实施例中，资源信用树被用作参考数目器。参考数目可以被用在多种应用中以跟踪一个或多个线程所具有的对诸如文件、设备、或任何共享数据结构之类的共享实体的参考的数量。在本发明的一个或多个实施例中，当利用资源信用树作为参考数目器时，分配信用等效于增加参考，并且释放信用移除参考。

[0086] 下列部分描述本发明的各种示例。示例被包括以帮助理解本发明而不意欲限制本发明的范围。

[0087] 在第一示例中，图6A-6C示出根据本发明的一个或多个实施例的资源信用树(105)。如由图6A描述的，利用每个节点中的零信用、8叶节点、和每个叶节点处64个信用的容量(Cmax)初始化资源信用树。最初，资源对象的可用信用的数目是5000。在初始化资源信用树之后，第一线程初始化分配单个信用(Rorig＝1)的分配操作。第一线程的处理标识符(ID)被识别。第一线程使用处理ID作为到哈希函数的输入以便选择资源信用树(105)的叶节点。哈希函数选择叶节点(624)作为当前节点并且初始化级联信用(R)的数目为1(即，Rorig的值)。

[0088] 继续该示例，第一线程如下遍历资源信用树(105)：

[0089] 首先，资源管理引擎锁定当前节点(624)并且检测当前节点的可用信用的计数(Cavail)是零。资源管理引擎确定可用信用的数量小于R并且Cavail＜(Cmax/2)→0＜32。结果，级联信用的数目(R)被增加到R+[(Cmax/2)-Cavail]→1+[(64/2)-0]＝33。其次，资源管理引擎通过选择当前节点(624)的父节点(610)作为新的当前节点来在反向遍历路径中遍历到下一个节点。

[0090] 资源管理引擎然后锁定当前节点(610)并且识别当前节点的可用信用的数量(再次，Cavail＝0)并且确定可用信用的数量小于R并且Cavail＜(Cmax/2)→0＜64。结果，级联信用的数目(R)被增加到R+[(Cmax/2)-Cavail]→33+[(128/2)-0]＝97。资源管理引擎然后通过选择当前节点(610)的父节点(604)作为新的当前节点来在反向遍历路径中遍历到下一个节点。

[0091] 资源管理引擎然后锁定当前节点(604)并且识别当前节点的可用信用的数量(再次，Cavail＝0)并且确定可用信用的数量小于R并且Cavail＜(Cmax/2)→0＜128。结果，级联信用的数目(R)被增加到R+[(Cmax/2)-Cavail]→97+[(256/2)-0]＝225。资源管理引擎然后通过选择当前节点(604)的父节点(600)作为新的当前节点来在反向遍历路径中遍历到下一个节点。

[0092] 资源管理引擎然后锁定当前节点(600)并且识别当前节点的可用信用的数量(再次，Cavail＝0)并且确定可用信用的数量小于R并且Cavail＜(Cmax/2)→0＜256。结果，级联信用的数目(R)被增加到R+[(Cmax/2)-Cavail]→225+[(512/2)-0]＝481。资源管理引擎然后确定当前节点是资源信用树(105)的根节点(600)。响应于确定当前节点是根节点(600)，资源管理引擎从资源对象中导入481个信用并且资源对象的可用信用的计数被减小到5000-481＝4519。接着，信用的所需数量(Rorig＝1)被分配并且级联信用的数目的剩余部分(R＝480)在反向遍历路径中被如下分配给节点：

[0093] 资源管理引擎确定对于根节点(600)，Cavail＜(Cmax/2)。结果，资源管理设置Cavail＝(Cmax/2)＝256。根节点(600)被解锁并且资源管理引擎在反向遍历路径中选择下一个子节点作为当前节点，设置Cavail＝(Cmax/2)＝128。反向遍历路径中每个其余节点类似地被设置为它的容量的一半(Cmax/2)并且被解锁(依次)。图6B描述在级联信用的数目的剩余部分被分配给其余节点之后的资源信用树(105)。

[0094] 继续该示例，第二线程初始化分配单个信用的第二分配请求并且将级联信用的数目(R)初始化为1。第二线程的处理ID被用作到哈希函数的输入并且叶节点618被选为当前节点。在选择叶节点(618)时，资源信用树(105)被如下遍历：

[0095] 首先，第二线程锁定当前节点(618)并且检测当前节点的可用信用的计数(Cavail)是零。第二线程确定可用信用的数量小于R并且Cavail＜(Cmax/2)→0＜32。结果，级联信用的数目(R)被增加到R+[(Cmax/2)-Cavail]→1+[(64/2)-0]＝33。接着，第二线程通过选择当前节点(618)的父节点(608)作为新的当前节点来在反向遍历路径中遍历到下一个节点。

[0096] 第二线程然后锁定当前节点(608)并且识别当前节点的可用信用的数量(再次，Cavail＝0)并且确定可用信用的数量小于R并且Cavail＜(Cmax/2)→0＜64。结果，级联信用的数目(R)被增加到R+[(Cmax/2)-Cavail]→33+[(128/2)-0]＝97。第二线程然后通过选择当前节点(608)的父节点(602)作为新的当前节点来在反向遍历路径中遍历到下一个节点。

[0097] 第二线程然后锁定当前节点(602)并且识别当前节点的可用信用的数量(再次，Cavail＝0)并且确定可用信用的数量小于R并且Cavail＜(Cmax/2)→0＜128。结果，级联信用的数目(R)被增加到R+[(Cmax/2)-Cavail]→97+[(256/2)-0]＝225。第二线程然后通过选择当前节点(602)的父节点(600)作为新的当前节点来在反向遍历路径中遍历到下一个节点。结果，根节点(600)现在被选择为当前节点。

[0098] 第二线程然后锁定根节点(600)并且识别根节点的可用信用的数量(Cavail＝256)并且确定可用信用的数量大于R(256＞225)。结果，根节点的信用的可用数量(Cavail)减小了R(Cavail＝Cavail-R)(即，256-225＝31)。根节点然后被解锁并且单个请求的信用被分配给第二线程。级联信用的数目的剩余部分(225-1＝224，在分配单个信用之后)被在反向遍历路径中分配给剩余节点，如下所述：

[0099] 第二线程选择路径中的下一个子节点(602)作为当前节点并且确定Cavail＜(Cmax/2)→0＜128。结果，第二线程设置Cavail＝(Cmax/2)＝128。当前节点(602)然后被解锁并且第二线程选择反向遍历路径中的下一个子节点(608)作为当前节点并且确定Cavail＜(Cmax/2)→0＜64。结果，第二线程设置Cavail＝(Cmax/2)＝64。当前节点(608)然后被解锁并且第二线程选择反向遍历路径中的下一个子节点(618)作为当前节点并且确定Cavail＜(Cmax/2)→0＜
32。结果，第二线程设置Cavail＝(Cmax/2)＝32，并且解锁当前节点(618)。作为这一点，级联信用的数目的剩余部分被完全地分布，并且因为当前节点是叶节点，所以第二线程确定分配处理完成。图6C描述在分配处理完成之后的资源信用树(105)。

[0100] 图7A和7B示出根据本发明的一个或多个实施例的示例资源信用树。

[0101] 在第二示例中，图7A和7B示出根据本发明的一个或多个实施例的资源信用树(105)。图7A描述在接收释放请求之前资源信用树(105)的状态。如图7A描述的，资源信用树(105)在每个叶节点处具有64个信用的容量(Cmax)并且资源对象的可用信用的计数是2520。

[0102] 继续示例，第一线程初始化释放操作以从第一线程中释放单个信用(Rorig＝1)。第一线程的处理标识符(ID)被识别。处理ID被用作到哈希函数的输入以便选择资源信用树(105)的叶节点。哈希函数选择叶节点722作为当前节点并且初始化级联信用的数目(R)为1(即，Rorig的值)。

[0103] 继续示例，第一线程如下遍历资源信用树(105)：

[0104] 首先，第一线程锁定当前节点(722)并且然后识别当前节点的可用信用的数量(Cavail)。第一线程设置Cavail＝Cavail+R＝64+1＝65。第一线程然后确定Cavail＞Cmax→65＞64。基于确定Cavail＞Cmax，第一线程设置R＝Cavail-(Cmax/2)＝65-32＝33并且设置Cavail＝(Cmax/
2)＝(64/2)＝32。当前节点(722)然后被解锁并且父节点(710)被选为当前节点。

[0105] 接着，第一线程锁定当前节点(710)并且然后识别当前节点的可用信用的数量(Cavail)。第一线程设置Cavail＝Cavail+R＝128+33＝161。第一线程然后确定Cavail＞Cmax→161＞128。基于确定Cavail＞Cmax，第一线程设置R＝Cavail-(Cmax/2)＝161-(128/2)＝161-64＝97并且设置Cavail＝(Cmax/2)＝(128/2)＝64。当前节点(710)然后被解锁并且父节点(704)被选为当前节点。

[0106] 接着，第一线程锁定当前节点(704)并且然后识别当前节点的可用信用的数量(Cavail)。第一线程设置Cavail＝Cavail+R＝245+97＝342。第一线程然后确定Cavail＞Cmax→342＞245。基于确定Cavail＞Cmax，第一线程设置R＝Cavail-(Cmax/2)＝342-(256/2)＝342-128＝214并且设置Cavail＝(Cmax/2)＝(256/2)＝128。当前节点(704)然后被解锁并且父节点(700)(即，根节点)被选为当前节点。

[0107] 接着，第一线程锁定根节点(700)并且然后识别根节点的可用信用的数量(Cavail)。第一线程设置Cavail＝Cavail+R＝500+214＝714。第一线程然后确定Cavail＞Cmax→714＞512。
基于确定Cavail＞Cmax，第一线程设置R＝Cavail-(Cmax/2)＝714-(512/2)＝714-256＝458并且设置Cavail＝(Cmax/2)＝(512/2)＝256。根节点(700)然后被解锁并且级联信用的数目被导出到资源对象。因此，资源对象的可用信用的计数被增加到2520+458＝2978，如由图7B描述的。

[0108] 本发明的实施例可以在实质上任何类型的计算机上执行，不管被使用的平台如何。例如，如图8所示，计算机系统(800)包括一个或多个处理器(802)(诸如中央处理单元(CPU)、集成电路、硬件处理器、等等)、相关的存储器(804)(例如，RAM、高速缓存存储器、闪速存储器、等等)、存储装置(806)(例如，硬盘、诸如光盘驱动器或数字视频盘(DVD)驱动器之类的光驱动器、闪速存储器棒、等等)、和当今的计算机的许多其他元件和典型功能(未示出)。计算机系统(800)还可以包括输入装置，诸如键盘(808)、鼠标(810)、或麦克风(未示出)。此外，计算机系统(800)可以包括输出装置，诸如监视器(812)(例如，液晶显示器(LCD)、等离子体显示器、或阴极射线管(CRT)监视器)。计算机系统(800)可以经由网络接口连接(未示出)被连接到网络(814)(例如，局域网(LAN)、诸如互联网之类的广域网(WAN)、或任何其它类型网络)。现在或将来，多个不同类型的计算机系统存在并且前述的输入和输出装置可以采取其它形式。一般说来，计算机系统(800)至少包括为实践本发明的实施例所必需的最少处理、输入、和/或输出装置。

[0109] 此外，在本发明的一个或多个实施例中，前述计算机系统(800)的一个或多个元件可以位于远程位置并且通过网络被连接到其他元件。此外，本发明的实施例可以在具有多个节点的分布式系统上执行，其中本发明的每个部分(例如，以上讨论的图1所述的资源对象(110)，资源信用树(105)等等)可以位于分布式系统内的不同节点上。在本发明的一个实施例中，节点对应于计算机系统。可替换地，节点可以对应于具有相关物理存储器的处理器。节点可以可替换地对应于处理器或具有共享存储器和/或资源的处理器的微核。计算机程序产品可以具有可以在计算机系统的一个或多个处理器上运行以执行如这里描述的资源管理的方法的指令。所述指令可以以计算机可读代码的形式执行本发明的实施例。以计算机可读程序代码的形式执行本发明的实施例的软件指令可以被临时地或永久地存储在非瞬时计算机可读存储介质上，诸如光盘(CD)、磁盘、磁带、存储器、或任何其它有形的计算机可读存储设备。

[0110] 在本发明的一个或多个实施例中，通过利用资源信用树分配和释放资源，可以增加资源利用、减小同时运行的线程之间的竞争、和/或降低用于请求的操作的延迟。

[0111] 另外，在本发明的一个或多个实施例中，通过响应于波动的需求增加和/或减小资源信用树的大小，可以执行资源信用树的动态负载平衡。资源信用树中信用的连续再分布也可以改善树中的信用平衡并且改善资源分配和解除分配操作的性能。

[0112] 在下面数个条款中阐述这里描述的主题的各方面：

[0113] 1.一种用于资源管理的方法，包括：

[0114] 初始化用于分配与资源池对应的第一数量的信用的第一操作；

[0115] 利用哈希函数选择资源信用树的第一叶节点；

[0116] 识别第一叶节点的可用信用的数量；

[0117] 由计算机处理器确定信用的第一数量超过第一叶节点的可用信用的数量；

[0118] 从第一叶节点开始，通过第一反向遍历路径遍历资源信用树到资源信用树的第一非叶节点；

[0119] 在遍历资源信用树的同时，基于第一反向遍历路径中的第一多个节点计算级联信用的第一数目，其中第一反向遍历路径包括第一叶节点、第一非叶节点、和第二非叶节点；

[0120] 识别第一非叶节点的可用信用的数量；

[0121] 由计算机处理器确定第一非叶节点的可用信用的数量超过级联信用的第一数目；以及

[0122] 响应于确定第一非叶节点的可用信用的数量超过级联信用的第一数目，从第一非叶节点分配第一数量的信用。

[0123] 2.如条款1所述的方法，其中计算级联信用的第一数目基于第一反向遍历路径中的第一多个节点的多个预定义的容量。

[0124] 3.如条款1或者条款2所述的方法，还包括：

[0125] 在从第一非叶节点分配第一数量的信用之后，将级联信用的第一数目的剩余部分转移到第一多个节点当中的多个其它节点。

[0126] 4.如前述条款中任何一个所述的方法，还包括：

[0127] 初始化用于分配与资源池对应的第二数量的信用的第二操作；

[0128] 从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到资源信用树的根节点；

[0129] 在遍历资源信用树的同时，基于第二反向遍历路径中的第二多个节点的每一个的预定义的容量计算级联信用的第二数目，其中第二反向遍历路径包括第二叶节点和根节点；

[0130] 识别根节点的可用信用的数量；

[0131] 确定级联信用的第二数目超过根节点的可用信用的数量；

[0132] 识别包括资源池的附加可用信用的计数的资源对象；

[0133] 确定附加可用信用的计数超过级联信用的第二数目；以及

[0134] 在确定附加可用信用的计数超过级联信用的第二数目之后，从资源对象中获得级联信用的第二数目。

[0135] 5.如前述条款1到3中任何一个所述的方法，还包括：

[0136] 初始化用于分配与资源池对应的第二数量的信用的第二操作，其中第二操作包括优先级标记；

[0137] 从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到根节点；

[0138] 识别根节点的可用信用的数量；

[0139] 确定信用的第二数量超过根节点的可用信用的数量；

[0140] 识别包括资源池的附加可用信用的计数的资源对象；

[0141] 确定信用的第二数量超过附加可用信用的计数；以及

[0142] 基于优先级标记并且在确定信用的第二数量超过附加可用信用的计数之后，将资源信用树中所有可用信用转移到根节点。

[0143] 6.如条款5所述的方法，还包括：

[0144] 在转移所有可用信用之后，计算根节点的信用的更新的可用数量；

[0145] 确定信用的第二数量超过信用的更新的可用数量；

[0146] 识别资源信用树的扇形展开数量；以及

[0147] 在确定信用的第二数量超过信用的更新的可用数量之后，基于扇形展开数量的因子从资源信用树中移除第二多个节点。

[0148] 7.如条款5所述的方法，还包括：

[0149] 在转移所有可用信用之后，计算根节点的信用的更新的可用数量；

[0150] 确定信用的更新的可用数量超过信用的第二数量；以及

[0151] 分配第二数量的信用。

[0152] 8.如前述条款中任何一个所述的方法，还包括：

[0153] 计算根节点的信用的更新的可用数量；

[0154] 确定信用的更新的可用数量足以填充第二多个节点；

[0155] 识别资源信用树的扇形展开数量；以及

[0156] 在确定信用的更新的可用数量足以填充第二多个节点之后，基于扇形展开数量的因子将第二多个节点增加到资源信用树。

[0157] 9.如前述条款1到3中任何一个所述的方法，还包括：

[0158] 初始化用于分配与资源池对应的第二数量的信用的第二操作，其中第二操作包括保留参数；

[0159] 从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到第三非叶节点；

[0160] 识别第三非叶节点的可用信用的数量；

[0161] 确定第三非叶节点的可用信用的数量超过信用的第二数量；

[0162] 识别包括资源池的附加可用信用的计数的资源对象；

[0163] 确定保留参数超过附加可用信用的计数；以及

[0164] 响应于确定保留参数超过附加可用信用的计数，发送失败通知。

[0165] 10.如前述条款中任何一个所述的方法，还包括：

[0166] 识别第一非叶节点的容量；以及

[0167] 基于容量的预定义的部分，将多个信用从第一非叶节点转移到第一叶节点。

[0168] 11.如前述条款1到3中任何一个所述的方法，还包括：

[0169] 初始化用于分配与资源池对应的第二数量的信用的第二操作；

[0170] 利用哈希函数选择资源信用树的第二叶节点；

[0171] 识别第二叶节点的可用信用的数量；

[0172] 确定第二叶节点的可用信用的数量超过信用的第二数量；以及

[0173] 从第二叶节点分配第二数量的信用。

[0174] 12.如条款1所述的方法，还包括：

[0175] 将级联信用的第一数目初始化到信用的第一数量。

[0176] 13.一种计算机程序产品，包括用于资源管理的多个指令，所述多个指令包括以下功能：

[0177] 初始化用于释放第一数量的信用的第一操作；

[0178] 将级联信用的第一数目初始化到信用的第一数量；

[0179] 利用哈希函数选择资源信用树的叶节点；

[0180] 识别叶节点的容量和叶节点的可用信用的数量；

[0181] 计算分配的信用的数量与叶节点的可用信用的数量的第一总和；

[0182] 确定第一总和超过叶节点的容量；

[0183] 从叶节点处开始并且基于确定第一总和超过叶节点的容量，通过反向遍历路径遍历资源信用树到资源信用树的第一非叶节点；

[0184] 在遍历资源信用树的同时，基于反向遍历路径中的多个节点修改级联信用的第一数目，其中反向遍历路径包括叶节点、第一非叶节点、和第二非叶节点，并且其中级联信用的第一数目用于在遍历资源信用树的同时更新多个节点中的至少一个的可用信用的数量；

[0185] 识别第一非叶节点的容量和第一非叶节点的可用信用的数量；以及

[0186] 基于第一非叶节点的容量和第一非叶节点的可用信用的数量，将级联信用的第一数目释放到第一非叶节点。

[0187] 14.如条款13所述的计算机程序产品，其中第一数量的信用对应于第一多个分配的资源单元，并且其中第一数量的信用和第一多个分配的资源单元被分配给客户端。

[0188] 15.如条款13或条款14所述的计算机程序产品，其中所述多个指令还包括以下功能：

[0189] 初始化用于释放与第二多个分配的资源单元对应的第二数量的信用的第二操作；

[0190] 将级联信用的第二数目初始化到信用的第二数量；

[0191] 确定级联信用的第二数目超过反向遍历路径上的每个节点的容量的阈值部分；

[0192] 识别包括资源池的附加可用信用的计数的资源对象；

[0193] 响应于确定级联信用的第二数目超过反向遍历路径上的每个节点的容量的阈值级别，将分配的信用的第二数目释放到资源对象。

[0194] 16.如条款13或条款14所述的计算机程序产品，其中所述多个指令还包括以下功能：

[0195] 初始化用于释放与第二多个分配的资源单元对应的第二数量的信用的第二操作；

[0196] 识别包括资源池的附加可用信用的计数的资源对象；

[0197] 确定用于分配第三数量的信用的第三操作被在资源对象处阻止，其中信用的第三数量被具有不足以完成第三操作的附加可用信用的计数的资源对象阻止；以及

[0198] 响应于确定第三操作被阻止，将第二数量的分配的信用释放到资源对象。

[0199] 17.如条款13或条款14所述的计算机程序产品，其中第一数量的信用对应于由客户端使用的多个资源单元，其中资源信用树是跟踪使用的资源单元的总数的累积器，并且其中代理访问资源信用树以识别使用的资源单元的总数。

[0200] 18.如条款13到17中任何一个所述的计算机程序产品，包括存储所述多个指令的非瞬时计算机可读介质。

[0201] 19.一种用于资源分配的系统，包括：

[0202] 第一计算机处理器；

[0203] 资源信用树，包括：

[0204] 多个非叶节点，包括根节点和多个内部节点；以及

[0205] 多个叶节点；

[0206] 资源对象，包括资源池的附加可用信用的数目；

[0207] 第一客户端，在第一计算机处理器上运行并包括以下功能：

[0208] 初始化用于分配第一数量的信用的第一操作；

[0209] 利用哈希函数选择多个叶节点的第一叶节点；

[0210] 从第一叶节点开始，通过第一反向遍历路径遍历资源信用树到多个非叶节点的第一非叶节点；

[0211] 在遍历资源信用树的同时，基于第一反向遍历路径中的第一多个节点计算级联信用的第一数目，其中第一反向遍历路径包括第一叶节点、第一非叶节点、和第二非叶节点；

[0212] 识别第一非叶节点的可用信用的数量；

[0213] 确定第一非叶节点的可用信用的数量超过级联信用的第一数目；以及

[0214] 响应于确定第一非叶节点的可用信用的数量超过级联信用的第一数目，从第一非叶节点分配第一数量的信用。

[0215] 20.如条款19所述的系统，还包括：

[0216] 第二计算机处理器；

[0217] 第二客户端，在第二计算机处理器上并与第一客户端并行地运行，包括以下功能：

[0218] 初始化用于分配与资源池对应的第二数量的信用的第二操作；以及

[0219] 在通过第一反向遍历路径遍历资源信用树的同时：

[0220] 从第二叶节点开始，通过第二反向遍历路径遍历资源信用树到资源信用树的根节点。

[0221] 21.如条款18或条款19所述的系统，其中第一多个叶节点的数量随多个计算机处理器的数量单调地增加。

[0222] 虽然已经参考有限数量的实施例描述了本发明，但是已经受益于此公开的本领域技术人员将理解，可以设计不脱离这里公开的本发明的范围的其它实施例。因此，本发明的范围应当仅仅由所附的权利要求书限定。