吴黎兵，于天水，何炎祥，李 飞

(1.武汉大学计算机学院，湖北武汉 430072;2.武汉大学软件工程国家重点实验室，湖北武汉 430072)

在高性能计算网格环境中，资源分布在各个不同地域和管理域中，由不同的组织拥有和操作，并且在策略和安全机制上各有不同。站点的自治性，资源的动态性和异构性需要一种有效机制来联合分配位于多个站点上的资源。资源预留可以保证任务在开始执行时获得资源，而在网格这种资源动态性很强的环境中，任务能如期执行可大大提高整个网格系统的资源利用率和系统性能。由于资源预留还可以实现网格服务的QoS保证，因而资源预留是网格资源管理中一种普遍采用的机制，也成为网格资源管理的研究热点。

目前网格资源预留机制从理论到实际应用的关键在于提高自身的处理性能，以便用尽可能小的代价，为用户提供更高QoS保证的网格服务。资源预留要求接纳控制的数据结构必须能够快速高效地查询资源的实验情况。实验表明，资源预留中有60%以上的时间用于对数据结构的处理，而这仅仅是提供最简单的预留服务，如果请求全部潜在的高级预留服务(如在扫描探测资源时间间隔时)，则与数据结构相关的处理达到总处理时间的90%［1］。可见为了最小化处理时间，对数据结构的改进是最能影响整个处理时间的，对数据结构的优化可以在较大程度上提高资源提前预留服务的处理速度。

1 现有数据结构

现有的数据结构分为基于离散时间(时隙)和基于连续时间两类。……