用于存储设备的第一高速缓存和第二高速缓存中的轨道的高速缓存管理

摘要

本发明提供了一种计算机程序产品、系统和方法，用于存储设备的第一高速缓存和第二高速缓存中的轨道的高速缓存管理。第一高速缓存保持存储设备中的受输入/输出（I/O）请求支配的已修改轨道和未修改轨道。已修改轨道和未修改轨道被从第一高速缓存降级。从第一高速缓存降级的已修改轨道和未修改轨道被提升到第二高速缓存。从第二高速缓存降级的未修改轨道被丢弃。第二高速缓存中的在存储设备上的邻近物理位置处的已修改轨道被分组，并且已分组的已修改轨道从第二高速缓存降级到存储设备。

说明书

技术领域

本发明涉及一种计算机程序产品、系统和方法，用于存储设备的 第一高速缓存和第二高速缓存中的轨道的高速缓存管理。

背景技术

高速缓存管理系统在比存储所请求轨道（track）的存储设备更快 的存取存储设备（例如存储器）中缓冲存储设备中的由于读取和写入 操作而最近被存取的轨道。对更快存取高速缓冲存储器中的轨道的随 后读取请求被以比从较慢存取存储设备中返回所请求轨道更快的速度 返回，从而降低了读取延迟。高速缓存管理系统还可能在指向存储设 备的已修改轨道被写入到高速缓冲存储器中时并且在已修改轨道被向 外写入到存储设备（例如硬盘驱动器）之前，完全返回写入请求。到 存储设备的写入延迟典型地显著地长于写入到高速缓冲存储器的延 迟。因此，使用高速缓存还降低写入延迟。

高速缓存管理系统可保持链表，该链表对于存储在高速缓存中每 个轨道具有一个条目，其可包括在写入到存储设备之前缓冲在高速缓 存中的写入数据或者读取数据。在常用的最近最少使用（LRU）高速 缓存技术中，如果高速缓存中的轨道被存取，即高速缓存“命中”， 则LRU列表中的用于所存取轨道的条目被移动到列表的最近使用 （MRU）端。如果所请求的轨道不在高速缓存中，即高速缓存未命中， 则高速缓存中的其条目在列表的LRU端的轨道可被移除（或降级回到 存储设备），而用于从存储设备升级（stage）到高速缓存中的轨道数 据的条目被添加到LRU列表的MRU端。利用这种LRU高速缓存技 术，被更频繁存取的轨道很可能会留在高速缓存中，而不太频繁存取 的数据将更可能从列表的LRU端中移除，以便在高速缓存中为新存取 的轨道腾出空间。

LRU高速缓存技术试图为时间局部性优化，以便降级（destage） 不太可能被很快重写的轨道，从而最小化降级操作的数量，也就是说， 如果未被降级的写入被重写，则重写写入的降级被避免，从而节省了 将数据从高速缓存写入到磁盘的时间和努力。另一方面，也希望以利 用空间局部性的方式降级，这意味着，数据被写入到彼此最接近的存 储位置，从而以最小化存储设备写入机制和存储介质需被移动以达到 下一个存储位置以便写入的距离。

利用时间局部性和空间局部性两者的一种技术是明智写入排序 （WOW）算法。WOW算法采用循环链表或时钟，其中循环链表对 于高速缓存中缓冲的每个写入请求具有一个条目。根据相关联的写入 请求被指向的存储位置而在链表中排序条目，以利用空间局部性的好 处。此外，每个条目包括指示高速缓存中的存储位置的写入数据最近 是否已被更新的位。当用于条目的写入数据被更新时，设置用于该条 目的位。指针指向循环链表中的当前条目。使用WOW算法的任务存 取由指针寻址的条目。如果用于该条目的位指示最近已更新用于高速 缓存中的该条目的数据，则该位被设置以指示写入数据最近未被更新 且指针递增以指向下一条目，使得具有到空间上下一最接近先前写入 的存储位置的存储位置的写入数据的条目被考虑。选择条目以写入在 空间上最接近于最后写入的存储位置，并且它的位指示用于该条目的 写入数据最近未被更新。

因此，利用WOW算法，利用了空间局部性，因为待写入的下一 个条目被选择用于考虑在空间上最接近于最后降级的写入请求。此外， 利用了时间局部性，因为最近已被写入的条目将被跳过，直到指针循 环返回到跳过的条目以便考虑。

磁盘驱动器可实现考虑了写入轨道的线性和角位置的WOW算法 和其它算法，并针对两者关于当前写入头位置优化以确定最小的总服 务时间。这个过程被称为“基于寻找和旋转优化的命令重排序”。磁 盘驱动器逻辑板将分析写入请求，并基于将需要多少时间来寻找轨道 的各种圆柱和角位置以便写入以及将过去多少时间来等待数据在头下 旋转两者来确定先做哪些。

在该技术中存在对使用存储系统中的高速缓存的改进技术的需 要。

发明内容

提供了一种计算机程序产品、系统和方法，用于存储设备的第一 高速缓存和第二高速缓存中的轨道的高速缓存管理。第一高速缓存保 持存储设备中的受输入/输出（I/O）请求支配的已修改轨道和未修改 轨道。已修改轨道和未修改轨道被从第一高速缓存降级（destage）。 从第一高速缓存降级的已修改轨道和未修改轨道被提升（promote）到 第二高速缓存。从第二高速缓存降级的未修改轨道被丢弃。第二高速 缓存中的在存储设备上的邻近物理位置处的已修改轨道被分组，并且 已分组的已修改轨道被从第二高速缓存降级到存储设备。

附图说明

图1示出计算环境的实施例。

图2示出第一高速缓存管理信息的实施例。

图3示出第二高速缓存管理信息的实施例。

图4示出第一高速缓存控制块的实施例。

图5示出第二高速缓存控制块的实施例。

图6示出空间索引条目的实施例。

图7示出从第一高速缓存降级未修改轨道的操作的实施例。

图8示出从第一高速缓存降级已修改轨道的操作的实施例。

图9示出将轨道添加到第一高速缓存的操作的实施例。

图10示出将轨道提升到第二高速缓存的操作的实施例。

图11示出在第二高速缓存中释放空间的操作的实施例。

图12示出从第二高速缓存降级已修改轨道的操作的实施例。

图13示出处理对于轨道的请求以返回给读取请求的操作的实施 例。

具体实施方式

图1示出了计算环境的实施例。多个主机2a、2b...2n可通过网络 6提交输入/输出（I/O）请求到存储控制器4，以存取存储设备10中 卷8（例如逻辑单元号、逻辑设备、逻辑子系统等）处的数据。存储 控制器4包括：含有一个或多个具有单个或多个核的处理器的处理器 复合体12，第一高速缓存14，用以备份在高速缓存14中的轨道的第 一高速缓存备份设备16，以及第二高速缓存18。第一高速缓存14和 第二高速缓存18高速缓存在主机2a、2b......2n和存储设备10之间传 送的数据。第一高速缓存备份设备16可以提供第一高速缓存14中的 轨道的非易失性存储。在进一步的实施例中，第一高速缓存备份设备 16可位于与第一高速缓存14的不同的功率边界上的集群或硬件中。

存储控制器4中具有存储器20，存储器20包括存储管理器22和 高速缓存管理器24，存储管理器22用于管理在主机2a、2b...2n和存 储设备10之间传送的轨道传送，高速缓存管理器24在第一高速缓存 14、第一高速缓存备份设备16和第二高速缓存18中管理在主机2a、 2b...2n和存储设备10之间传送的数据。轨道可包括存储设备10中配 置的任何数据单元，例如轨道、逻辑块地址（LBA）等，它是轨道的 更大分组的一部分，例如卷、逻辑设备等。高速缓存管理器24保持第 一高速缓存管理信息26和第二高速缓存管理信息28以管理在第一高 速缓存14和第二高速缓存18中读取（未修改的）和写（已修改的） 轨道。第一高速缓存备份设备索引30提供到第一高速缓存备份设备 16中位置的轨道标识符的索引。

存储管理器22和高速缓存管理器24在图1中被示为加载到存储 器20并由处理器复合体12执行的程序代码。可替换地，部分或全部 的功能可以实现在存储控制器4的硬件设备中，例如在专用集成电路 （ASIC）中。

第二高速缓存18可在日志结构阵列（LSA）32中存储轨道，其中 以接收的相继顺序写入轨道，从而提供写入到第二高速缓存18的轨道 的时间排序。在LSA中，已经出现在LSA中的轨道的后来版本被写 入在LSA32的末尾。在可替换的实施例中，第二高速缓存18可以LSA 中以外的格式存储数据。

在一个实施例中，第一高速缓存14可包括随机存取存储器 （RAM），例如动态随机存取存储器（DRAM），而第二高速缓存 18可包括闪速存储器，例如固态器件，而存储设备10由一个或多个 顺序存取存储设备组成，例如硬盘驱动器和磁带。存储设备10可包括 单一的顺序存取存储设备或可包括存储设备阵列，例如完全磁盘束 （JBOD）、直接存取存储设备（DASD）、独立磁盘冗余阵列（RAID） 的阵列、虚拟化设备等。在一个实施例中，第一高速缓存14是比第二 高速缓存18更快的存取设备，而第二高速缓存18是比存储设备10更 快的存取设备。另外，第一高速缓存14可具有比第二高速缓存18更 大的每个存储单元成本，而第二高速缓存18可具有比存储设备10中 的存储设备更大的每个存储单元成本。

第一高速缓存14可以是存储器20的一部分，或者在单独的存储 器设备中实现，例如DRAM。在一个实施例中，第一高速缓存备份设 备16可包括非易失性备份存储设备（NVS），例如非易失性存储器， 例如电池供电的随机存取存储器（RAM）、静态RAM（SRAM）等。

网络6可包括存储区域网络（SAN）、局域网（LAN）、广域网 （WAN）、互联网、内联网等。

图2示出第一高速缓存管理信息26的实施例，包括：轨道索引 50，提供第一高速缓存14中的轨道索引给控制块目录52中的控制块； 未修改相继LRU列表54，提供第一高速缓存14中未修改相继轨道的 时间排序；已修改LRU列表56，提供第一高速缓存14中已修改相继 和非相继轨道的时间排序；以及未修改非相继LRU列表58，提供第 一高速缓存14中未修改非相继轨道的时间排序。

在某些实施例中，在确定第一高速缓存备份设备16满时，已修改 LRU列表56用于从第一高速缓存14降级已修改轨道，以便可以丢弃 第一高速缓存备份设备16中这些轨道的副本，从而在第一高速缓存备 份设备16中为新的已修改轨道腾出空间。

图3示出第二高速缓存管理信息28的实施例，包括：轨道索引 70，提供第二高速缓存18中的轨道索引给控制块目录72中的控制块； 未修改列表74，提供第二高速缓存18中未修改轨道的时间排序；以 及空间索引76，基于存储已修改轨道的存储设备10中的物理位置而 提供在第二高速缓存18中已修改轨道的空间排序。

LRU列表54、56、58和74都可包括根据最后一次存取识别的轨 道时排序的第一高速缓存14和第二高速缓存18中轨道的轨道ID。 LRU列表54、56、58和74具有指示最近存取的轨道的最近使用（MRU） 端以及指示最近最少使用或存取的轨道的LRU端。添加到高速缓存 14和18的轨道的轨道ID被添加到LRU列表的MRU端，并且从LRU 端存取从高速缓存14和18降级的轨道。轨道索引50和70以及空间 索引76可包括分散索引表（SIT）。可替换类型的数据结构可用于提 供高速缓存14和18中轨道的时间排序和第二高速缓存18中轨道的空 间排序。

非相继轨道可包括联机线事务处理（OLTP）轨道，其经常包括不 是完全随机且具有一些参考位置（即具有被反复存取的可能性）的小 块写入。

图4示出控制块目录52中的第一高速缓存控制块100的条目的实 施例，包括：控制块标识符（ID）102、第一高速缓存14中轨道的物 理位置的第一高速缓存位置104、指示轨道是已修改还是未修改的信 息106以及指示轨道是相继还是非相继存取的信息108。

图5示出第二高速缓存控制块目录72中的第二高速缓存控制块 120的条目的实施例，包括：控制块标识符（ID）122、轨道在LSA32 中所位于的LSA位置124以及指示轨道是已修改还是未修改的信息 126。

图6示出空间索引条目140，包括：第二高速缓存18中轨道的轨 道标识符142，以及轨道在存储设备10中所存储的物理位置144，例 如圆筒、盘片、块地址和存储设备标识符。

图7示出由高速缓存管理器24执行的操作的实施例，用以从第一 高速缓存14降级未修改轨道。当确定在第一高速缓存14中释放空间 时，可启动降级操作。当启动（在块200处）操作以确定是否从第一 高速缓存14中去除轨道从而在第一高速缓存14中释放空间时，高速 缓存管理器24基于对不同类型的未修改轨道的预期命中而确定（在块 202处）降级非相继还是相继未修改轨道。如果（在块204处）确定 降级未修改相继轨道，则高速缓存管理器24使用（在块206处）未修 改相继LRU列表54以确定要从列表的LRU端降级的未修改相继轨 道，其并未被提升到第二高速缓存18。如果（在块204处）确定降级 未修改非相继轨道，则高速缓存管理器使用未修改非相继LRU列表 58确定（在块208处）要降级的未修改非相继轨道。未修改非相继轨 道（在块210处）被提升到第二高速缓存18。

图8示出由高速缓存管理器24执行的操作的实施例，用以从第一 高速缓存14降级已修改轨道。如果在第一高速缓存备份设备16中需 要空间，高速缓存管理器24可作为预定操作的一部分而定期降级轨 道，并增加降级速率。当启动（在块250处）降级已修改轨道的操作 时，高速缓存管理器24处理（在块252处）已修改LRU列表56以确 定要从LRU列表56的LRU端降级的已修改轨道。如果（在块254 处）所确定的已修改轨道是相继的，则高速缓存管理器24写入（在块 256处）所确定的已修改相继轨道到存储设备10，从而绕过第二高速 缓存18。如果（在块254处）已修改轨道是非相继的，则高速缓存管 理器24提升（在块258处）所确定的已修改非相继轨道到第二高速缓 存18并从第一高速缓存备份设备16丢弃（在块260处）所确定的已 修改轨道的副本。

利用图7和图8的操作，非相继轨道被降级，但不被提升到第二 高速缓存18。相继已修改（写入）被直接写入到存储设备10，从而绕 过第二高速缓存。相继未修改轨道（读取）被丢弃并且不被复制到其 它位置，而从第一高速缓存14降级的未修改非相继轨道被提升到第二 高速缓存18。

图9示出可由高速缓存管理器24执行的操作的实施例，用以添加 （即提升）轨道到第一高速缓存14，该轨道可包括来自主机2a、2b...2n 的写入或已修改轨道，受读取请求支配并因此被移动到第一高速缓存 14的第二高速缓存18中的非相继轨道，或者未在高速缓存14或18 中找到并从存储设备10检索的读取所请求的数据。当接收（在块300 处）待添加至第一高速缓存14的轨道时，高速缓存管理器24为待添 加的轨道创建（在块301处）控制块100（图4），以指示第一高速缓 存14中的位置104以及该轨道是否是已修改/未修改106和相继/非相 继108。该控制块100被添加到第一高速缓存14的控制块目录52。高 速缓存管理器24添加（在块302处）条目到第一高速缓存轨道索引 50，其具有待添加的轨道的轨道ID以及到控制块目录52中所创建的 高速缓存控制块100的索引。条目被添加（在块304处）到待添加的 轨道的轨道类型的LRU列表54、56或58的MRU端。如果（在块 306处）待添加的轨道是已修改非相继轨道，则待添加的轨道还被复 制（在块308处）到第一高速缓存备份设备16，并且针对添加的轨道， 条目被添加到第一高速缓存备份设备索引30。如果（在块306处）待 添加的轨道是未修改相继轨道，则控制结束。

图10示出由高速缓存管理器24执行的操作的实施例，用以将从 第一高速缓存14降级的非相继轨道提升到第二高速缓存18。当启动 （在块350处）操作以提升轨道到第二高速缓存18时，高速缓存管理 器24添加（在块352处）正被提升到第二高速缓存18中LSA32的 轨道，并为待添加的轨道创建（在块354处）控制块120（图5），以 指示在LSA32中的轨道位置124以及轨道是否已修改/未修改126。 条目被添加（在块356处）到第二高速缓存轨道索引70中，其具有被 提升的轨道的轨道ID以及到第二高速缓存18的控制块目录72中所创 建的高速缓存控制块120的索引。如果（从块358的“否”分支）正 被提升的轨道是未修改数据，则高速缓存管理器24在未修改LRU列 表74的MRU端处指示（在块360处）被提升的轨道，例如通过添加 轨道ID到MRU端。如果（在块358处）被提升的轨道是已修改数据， 则高速缓存管理器24确定（在块362处）在存储设备10上写入已修 改被提升的轨道的物理位置，并添加（在块364处）条目到空间索引 76，以指示被提升的轨道的轨道ID142以及所确定的被提升的轨道在 存储设备10上的物理位置144。

图11示出由高速缓存管理器24执行的操作的实施例，用以在第 二高速缓存18中为待添加到第二高速缓存18的新轨道释放空间，即 从第一高速缓存14降级的轨道。当启动该操作时（在块400处），高 速缓存管理器24从未修改LRU列表74的LRU端确定（在块402处） 第二高速缓存18中未修改轨道，并且使所确定的未修改轨道无效（在 块404处），而不降级被无效的未修改轨道到存储设备10，并且还从 未修改LRU列表74去除被无效的未修改轨道。

图12示出由高速缓存管理器24所执行操作的实施例，用以将第 二高速缓存12中的已修改轨道降级到存储设备10。当启动（在块420 处）降级操作时，高速缓存管理器24使用（在块422处）空间索引 76，以确定第二高速缓存18中的已修改轨道，从而基于已修改轨道在 空间索引76中的顺序对在存储设备上的邻近物理位置处的那些已修 改轨道进行分组，例如在位置排序的空间索引76中连续条目140（图 6）处的一组轨道。所确定的已分组的已修改轨道（在块424处）被从 第二高速缓存18降级到存储设备10。

图12的操作优化到存储设备10（其包括顺序存取存储设备）的 写入操作，通过使得存储设备10在存储设备10写入表面的物理上最 邻近的物理位置处写入轨道，从而最小化存储设备10写入头的寻找量 和移动，用以将第二高速缓存18中的轨道写入到存储设备10。基于 时间因素将轨道从第一高速缓存16提升到第二高速缓存18，例如它 们在LRU列表54、56、58中的位置，而不是以针对到顺序存取存储 设备10（例如硬盘驱动器）的相继写入而优化的次序。因此，图12 的操作基于时间排序的已修改轨道在存储设备10上的空间位置而优 化这些时间排序的已修改轨道，从而优化在存储设备10处的写入。

图13示出由高速缓存管理器24所执行操作的实施例，用以从高 速缓存14和18以及存储设备10检索对于读取请求的所请求的轨迹。 处理读取请求的存储管理器22可提交请求到高速缓存管理器24以用 于所请求的轨道。当接收（在块450处）对于轨道的请求时，高速缓 存管理器24使用（在块454处）第一高速缓存轨道索引50以确定是 否所有所请求的轨道都在第一高速缓存14中。如果（在块454处）并 非所有所请求的轨道都在第一高速缓存14中，则高速缓存管理器24 使用（在块456处）第二高速缓存轨道索引70以确定在第二高速缓存 18中而不在第一高速缓存14中的任何所请求的轨道。如果（在块458 处）存在在第一高速缓存14和第二高速缓存18中都未找到的任何所 请求的轨道，则高速缓存管理器24从第二高速缓存轨道索引70中确 定（在块460处）在存储设备10中而不在第一高速缓存14和第二高 速缓存18中的任何所请求的轨道。然后高速缓存管理器24将在第二 高速缓存18和存储设备10中的任何所确定的轨道提升（在块462处） 到第一高速缓存14中。高速缓存管理器24使用（在块464处）第一 高速缓存轨道索引50以从第一高速缓存14检索所请求的轨道以便返 回给读取请求。用于所检索的轨道的条目被移动（在块466处）到包 括用于所检索的轨道的条目的LRU列表54、56、58的MRU端。利 用图13的操作，高速缓存管理器24从最高级的高速缓存14中检索所 请求的轨道，然后在进入存储设备10之前首先从第二高速缓存18检 索，因为高速缓存14和18将具有所请求的轨道的最近已修改版本。 首先在第一高速缓存14中查找最近版本，如果不在第一高速缓存14 中，则在第二高速缓存18中查找，如果不在高速缓存14、18的任一 者中，则在存储设备10中查找。

利用图13的操作，高速缓存管理器24从最高级的高速缓存14检 索所请求的轨道，然后在进入存储设备10之前首先从第二高速缓存 18检索，因为高速缓存14和18将具有所请求的轨道的最近已修改版 本。首先在第一高速缓存14中查找最新版本，如果不在第一高速缓存 14中，则在第二高速缓存18中查找，如果不在高速缓存14、18的任 一者中，则在存储设备10中查找。

所述实施例提供用于允许在主要或第一级高速缓存和存储设备之 间使用第二级高速缓存的技术，用以在最快存取第一高速缓存14具有 最昂贵的空间、每字节成本时增加高速缓存空间，而比第一高速缓存 便宜但比存储设备快的第二高速缓存可用于增加系统中的高速缓存的 数据量。当所请求的数据在高速缓存中并可从高速缓存中返回而不必 从较慢存取、成本较低的存储设备中检索时，增加较快存取高速缓存 的存储空间提高了对高速缓存的数据的存取。另外，在所述实施例中， 轨道基于第一高速缓存中的时间排序而被添加到第二高速缓存，然后 基于顺序存取存储设备中的空间物理位置而在第二高速缓存中排序， 使得降级的轨道被写入到在存储设备中邻近或连续物理位置处的轨道 组中，从而优化到存储设备的轨道写入。

所述操作可被实现为方法、装置或使用标准编程和/或工程技术来 产生软件、固件、硬件或其任意组合的计算机程序产品。因此，实施 例的个方面可采用在这里一般都可被称为“电路”、“模块”或“系 统”的完全硬件实施例、完全软件实施例（包括固件、常驻软件、微 代码等）或组合了软件和硬件方面的实施例形式。此外，实施例的各 方面可采用在具有其上体现的计算机可读程序代码的一个或多个计算 机可读介质中体现的计算机程序产品的形式。

可使用一个或多个计算机可读介质的任何组合。计算机可读介质 可以是计算机可读信号介质或计算机可读存储介质。计算机可读存储 介质可以是（例如但不限于）电子的、磁的、光学的、电磁的、红外 的或半导体系统、装置或设备或前述的任何适当组合。计算机可读存 储介质的更具体的例子（非穷尽列表）将包括以下：具有一条或多条 导线的电连接、便携式计算机磁盘、硬盘、随机存取存储器（RAM）、 只读存储器（ROM）、可擦除可编程只读存储器（EPROM或闪速存 储器）、光纤、便携式光盘只读存储器（CD-ROM）、光存储设备、 磁存储设备或前述的任何适当组合。在本文档的上下文中，计算机可 读存储介质可以是任何有形的介质，它可包含或存储由指令执行系统、 装置或设备使用或连同指令执行系统、装置或设备使用的程序。

计算机可读信号介质可包括具有在其中体现的计算机可读程序代 码的传播数据信号，例如在基带中或作为载波的部分。这种传播的信 号可采用各种形式的任一种，包括但不限于电磁的、光学的或其任何 合适的组合。计算机可读信号介质可以是除了计算机可读存储介质外 以外并可通信、传播或运输由指令执行系统、装置或设备使用或连同 指令执行系统、装置或设备使用的程序的任何计算机可读介质。

可使用任何适当的介质，包括但不限于无线、有线、光纤光缆、 射频等或前述的任何适当组合来传送在计算机可读介质上体现的程序 代码。

可以一种或多种编程语言的组合编写用于执行本发明方面的操作 的计算机程序代码，所述编程语言包括：诸如Java、Smalltalk、C++ 等面向对象的编程语言以及诸如“C”编程语言或类似编程语言的常 规过程编程语言。程序代码可完全在用户的计算机上、部分地在用户 的计算机上、作为独立的软件包、部分地在用户的计算机上并部分地 在远程计算机上或完全在远程计算机或服务器上执行。在后一种情况 中，远程计算机可通过包括局域网（LAN）或广域网（WAN）的任何 类型的网络而连接到用户的计算机上，或者可做出到外部计算机的连 接（例如使用互联网服务提供商通过互联网）。

以上参考根据发明的实施例的方法、设备（系统）和计算机程序 产品的流程图说明和/或块图描述本发明的方面。将理解的是，流程图 说明和/或框图的每个块以及流程图说明和/或框图中的块组合可由计 算机程序指令实现。这些计算机程序指令可提供给通用计算机、专用 计算机或其它可编程数据处理设备的处理器，以产生机器，使得通过 计算机或其它可编程数据处理装置的处理器执行的指令创建用于实施 流程图和/或框图块中指定的功能/动作的装置。

这些计算机程序指令还可存储在计算机可读介质中，该计算机可 读介质可以指引计算机、其它可编程数据处理装置或其它设备以特定 方式工作，使得计算机可读介质中存储的指令产生包括指令的制造物 品，该指令执行流程图和/或框图块中指定的功能/动作。

计算机程序指令还可加载到计算机、其它可编程数据处理装置或 其它设备上，以使得一系列的操作步骤在计算机、其它可编程装置或 其它设备上执行，用以产生计算机实现的过程，使得在计算机或其它 可编程装置上执行的指令提供用于实现流程图和/或框图块中指定的 功能/动作的过程。

术语“一实施例”、“实施例”、“多个实施例”、“该实施例”、 “该多个实施例”、“一个或多个实施例”、“一些实施例”和“一 个实施例”是指“本发明的一个或多个（但不是全部）实施例”，除 非另有明确规定。

术语“包含”、“包括”、“具有”及其变体的是指“包含但不 限于”，除非另有明确规定。

项目的枚举列表并不暗示任何或所有的项目是相互排斥的，除非 另有明确规定列举。

术语“一个”和“该”是指“一个或多个”，除非另有明确规定。

彼此通信的设备不需要彼此连续通信，除非另有明确规定。此外， 彼此通信的设备可直接通信或者通过一个或多个媒介间接地通信。

具有彼此通信的几个组件的实施例的描述并不暗示需要所有的这 些组件。相反，描述各种可选的组件来示出本发明的各种各样的可能 实施例。

此外，虽然以相继次序描述过程步骤、方法步骤、算法等，但是 这样的过程、方法和算法可被配置为以可替换的次序工作。换言之， 可被描述的任何步骤的序列或次序并不一定指示以该次序执行步骤的 需要。也可以任何实用的次序执行此处所述的过程步骤。此外，可以 同时执行某些步骤。

当在此处描述单个设备或物品时，将易于显而易见的是，可使用 一个以上的设备/物品（不论它们协作与否）来代替单个设备/物品。同 样，当此处描述一个以上的设备或物品时（不论它们协作与否），将 易于显而易见的是，可使用单个设备/物品来取代一个以上的设备或物 品，或者可使用不同数目的设备/物品来取代所示数目的设备或程序。 一设备的功能和/或特征可选地可由一个或多个其它设备实施，所述一 个或多个其它设备未被明确描述为具有这样的功能/特征。因此，本发 明的其它实施例不需要包括设备本身。

图7-图13示出的操作显示以某一次序发生的某些事件。在可替代 的实施例中，可以不同的次序执行某些操作，修改或删除某些操作。 此外，步骤可添加到上述逻辑，并且仍然符合所述实施例。此外，此 处所述的操作可能相继发生，或者可并行处理某些操作。更进一步地， 操作可由单个处理单元或由分布式处理单元执行。