CN101057220A

CN101057220A - 用于管理存储器空间的系统和方法

Info

Publication number: CN101057220A
Application number: CNA2005800387102A
Authority: CN
Inventors: C·M·奥特罗帕里茨; J·范埃恩德霍芬
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 2004-11-11
Filing date: 2005-11-04
Publication date: 2007-10-17
Also published as: JP2008520023A; US20090083508A1; WO2006051454A1; EP1815334A1

Abstract

为了提供一种用于管理存储器空间(22)的系统(100)(其中有可能最大化被提供给每个所执行的任务(50，60)的存储器空间(22))，本发明提出通过如下方式把所述存储器空间(22)分配给对应的任务(50，60)：根据所确定的存储器空间(22)的需求把所述存储器空间分配给对应的任务；以及根据至少一个对应的处理预算把所述存储器空间分配给对应的任务，该处理预算由至少一个处理预算预留装置(12)指定给每个任务(50，60)。所述系统包括：至少一个中央处理单元(10)，其用于执行至少一个第一任务(50)和至少一个第二任务(60)；至少一个存储器单元(20)，特别是至少一个高速缓存，其与该中央处理单元(10)相连接并且包括所述存储器空间(22)，该存储器空间被细分成至少一个第一存储器空间(52) (特别是至少一个第一高速缓存空间)以及至少一个第二存储器空间(62)(特别是至少一个第二高速缓存空间)；至少一个确定装置(30)，其用于确定第一任务(50)和/或第二任务(60)是否需要所述存储器空间(22)；以及至少一个分配装置(40)，其用于把所述存储器空间(22)分配给对应的任务，特别是用于把第一存储器空间(52)分配给第一任务(50)并且把第二存储器空间(62)分配给第二任务(60)。

Description

用于管理存储器空间的系统和方法

本发明涉及一种根据权利要求1的前文的系统以及一种根据权利要求7的前文的方法。

软件中的媒体处理允许消费者终端变得开放且灵活。与此同时，由于成本价格方面的巨大压力，消费者终端的资源严重受到限制。为了能够与专用硬件解决方案竞争，软件中的媒体处理必须以很高的平均资源利用率非常经济地使用可用资源，同时保持消费者终端的典型品质(比如鲁棒性)，并且满足由高质量数字音频和视频处理所施加的严格的定时要求。在这方面，一个很重要的实际情况是对于存储器空间的管理。

存储器分层结构(例如高速缓存)的效率和性能对于在所谓的芯片上系统(SoC)上运行的多媒体应用的性能而言尤其关键。因此，存在许多旨在减少高速缓存错失或者错失延迟的高速缓存调度技术。对于在单一处理单元上运行的单一应用，传统的高速缓存已经被设计得工作良好。

例如，现有技术文献EP 0 442 474 A2、US 6 427 195 B1或US 2002/0184445 A1涉及锁定和/或保障高速缓存空间以便由单一任务/线程/应用(此后称作“任务”)来使用的机制。根据这些现有技术文献，在一个任务的寿命期间保障所保留的高速缓存空间。

在传统的系统中，并发执行的多个应用共享高速缓存。这些并发应用影响彼此的性能，这是由于它们会把彼此的数据冲刷出高速缓存。此外，不同类型的软件结构和存储器使用将受益于不同的高速缓存组织。

可以从不同的角度提高高速缓存效率，例如通过：

-更好的高速缓存组织：取决于存储器存取模式，特定的分配将更为高效(例子：在不同的存储器组上的连续数据单元)，或者

-改进的替换和分配技术。

在所提出的各种替换和分配技术当中，其中的某些技术使用预算编制(或者预留)的概念。一个给定的应用/任务/线程可以排他地对高速缓存的特定部分进行存取，并且将不会受到其他应用的干扰，所述其他应用也将具有其自身的高速缓存片段。

在下列文章中给出了作为空间预算的所述预算编制的例子：

-“Compositional memory systems for multimedia communicatingtasks(用于多媒体通信任务的复合存储器系统)”(Anca Molnos，Internal Natlab底稿)，以及

-“CQoS：A Framework for Enabling QoS in Shared Caches ofCMP Platforms(CQoS：用于在CMP平台的共享高速缓存中实现QoS的框架)”(Ravi Iyer，Hillsboro，Oregon，2004年，Proceedings ofthe 18th annual international conference on Supercomputing，第257至266页，ISBN：1-58113-839-3)。

空间预算编制通过改进高速缓存的可预测性而改进了应用性能。此外，空间预算编制实现了软件子系统的可复合性。然而，在资源受限的系统中，高速缓存还是稀缺资源；这意味着当一个应用请求高速缓存预算时，有可能无法获得该高速缓存空间。一般来说，应用将不会接收到所要求的那么多高速缓存空间，从而导致了性能惩罚。

从现有技术文献US 2003/0101084 A1中获知，当一个任务不使用高速缓存空间时释放该高速缓存空间。然而，如果该任务将需要该数据(即存储器空间)，那么这种方案可能导致非常低的性能。

从上述缺陷和缺点出发并且考虑到所讨论的现有技术，本发明的一个目的是进一步开发出一种在技术领域部分中描述的那种系统和方法，从而使得被提供给每个所执行的任务的存储器空间得到最大化。

本发明的所述目的是如下实现的：

-根据所确定的存储器空间要求把存储器空间分配给对应的任务；以及

-根据至少一个对应的处理预算把存储器空间分配给对应的任务，该处理预算可以由至少一个处理预算预留装置指定给每个任务。

在对应的从属权利要求中公开了本发明的有利实施例和适宜改进。

本发明主要基于下面的概念：

-把时间添加到存储器预算中，特别是添加到高速缓存预算中；或者

-把时间添加到存储器预留中，特别是添加到高速缓存预留中，从而提供了一种使用预算的时间高速缓存管理技术。

换句话说，本发明引入时间以作为存储器空间预留、特别是高速缓存空间预留的一个参数。该时间被耦合到所述处理预算。这样，总体存储器利用率、特别是总体高速缓存利用率得到最大化。

此外，当把存储器空间预留(例如高速缓存空间预留)的时间参数与所述处理预留相关联时，系统性能也得到改进。

根据本发明的一个优选实施例，在一个具有中央处理单元(CPU)资源管理器的系统中，第一任务(例如第一线程或第一应用)和/或第二任务(例如第二线程或第二应用)或者各任务/线程/应用的集合接收受保障并且强制的CPU预算。因此，一旦该预算被耗尽，相应的一个或多个任务将不执行，直到该预算再次得到补充。

该信息可以被用来：

-释放由这些任务使用的存储器空间，特别是高速缓存空间；以及

-使得所述空间可用于确实需要存储器空间的其他任务。

这种机制导致更为有效的存储器空间利用率，特别是更为有效的高速缓存空间利用率。对于具有CPU预算并且正被执行的任务有了更多的可用存储器空间。

本发明的另一个本质特征在于，当所述任务确实将不需要所述存储器空间时才发生释放该存储器空间，从而不会导致任何惩罚。因此，所述系统所能够提供给所述任务或应用或线程的存储器空间(特别是高速缓存预算)得到最大化。

根据本发明的一个优选实施例，所述存储器空间可以是一个高速缓存，该高速缓存存储整个系统存储器的仅仅一部分的数据拷贝。此外，根据本发明的一种有利的实现方式，所述存储器空间可以是第二级高速缓存，多个中央处理单元(CPU)共享对该第二级高速缓存的存取。

这种第二级高速缓存(或次级高速缓存或二级高速缓存)通常

-被设置在第一级高速缓存(或主高速缓存或一级高速缓存)与主存储器之间；并且

-通过至少一条外部总线连接到中央处理单元(CPU)。

与所述第二级高速缓存不同，所述主高速缓存通常与CPU位于相同的集成电路(IC)上。

本发明还涉及：

-一种电视机，其包括至少一个如上所述的系统，并且/或者根据如上所述的方法工作；以及

-一种机顶盒，其包括至少一个如上所述的系统，并且/或者根据如上所述的方法工作。

根据本发明的一个有利实施例，所述方法基本上包括以下步骤：

-执行第一任务和/或第二任务；

-确定第一任务和/或第二任务是否需要存储器空间；

-给对应的任务分配存储器空间，特别是

-把第一存储器空间分配给第一任务；以及

-把第二存储器空间分配给第二任务，

该方法可以附加地包括以下步骤：

-如果处理预算被耗尽则补充所述处理预算，其中在所述补充期间不执行相应的任务；

-确定补充对应的处理预算所需要的时间，特别是

-确定所述任务的至少其中之一的执行时间或繁忙周期；以及/或者

-确定所述任务的至少其中之一的不执行时间；以及

-把被指定给不执行的任务的存储器空间分配给至少一个可执行任务并且持续所确定的补充时间。

优选地，所述存储器空间

-被排他地分配给第一任务；以及/或者

-被部分地分配给第一任务，并且被部分地分配给第二任务；以及/或者

-被排他地分配给第二任务。

一般来说，本发明可以被使用在包含高速缓存的任何产品中，其中在所述高速缓存中存在中央处理单元(CPU)预留机制。

特别地，本发明最后涉及对于任何数字系统使用至少一个如上所述的系统和/或如上所述的方法，在所述数字系统中，多个应用被并发执行并且共享存储器空间，例如对于以下情况使用上述系统和/或上述方法：

-多媒体应用，特别是运行在至少一个芯片上系统(SoC)上的多媒体应用；以及/或者

-类似于根据权利要求5的数字电视机的消费者终端，特别是高质量视频系统，或者根据权利要求6的机顶盒。

正如上面已经讨论的那样，存在几种以有利的方式具体实现以及改进本发明的教导的选项。为此，参照分别从属于权利要求1和权利要求7的各条权利要求；下面参照一个优选实施例并且参照附图以举例的方式更加详细地解释本发明的其他改进、特征和优点，在附图中：

图1示意性地示出了根据本发明的方法工作的根据本发明的系统的一个实施例；

图2概略地示出了根据现有技术的高速缓存管理；

图3概略地示出了根据本发明的高速缓存管理；

图4示意性地示出了包括图1的系统并且根据图3的高速缓存管理操作的电视机；以及

图5示意性地示出了包括图1的系统并且根据图3的高速缓存管理操作的机顶盒。

相同的附图标记被用于表示图1到图5中的相应部件。

图1示意性地示出了根据本发明的系统100的一个实施例的最重要的各部件。该系统100包括用于执行第一任务50和第二任务60的中央处理单元10(与图3对照)。该中央处理单元10与一个存储器单元相连接，即与高速缓存20相连接。

为了把高速缓存空间22分配给第一任务50和/或第二任务60，特别是把第一高速缓存空间52分配给第一任务50并且把第二高速缓存空间62分配给第二任务60，所述系统100包括一个高速缓存预留机制，其具有分配装置40。

为了把至少一个对应的处理预算指定给每个任务50、60，所述系统100包括一个处理预算预留装置12，其例如是中央处理单元(CPU)预留系统。该处理预算预留装置12可以优选地以至少一个软件算法的形式来实现，该软件算法在该相同的CPU 10上执行，或者在该系统100中的一个或多个其他可用CPU上执行。为了进行正确的操作，该软件必须依赖于某些硬件设施，比如至少一个能够中断所述任务50和60在CPU 10上的正常执行的定时器。

一旦所述处理预算被耗尽，相应的任务50、60将不被执行，直到其处理预算在一个时间周期的末尾70被再次补充。相应地，第一任务50的处理预算确定所述第一任务50的预算繁忙时间54，并且第二任务60的处理预算确定所述第二任务60的预算繁忙时间64。

可以以远小于所述任务的寿命的粒度获得所述系统100的处理预算并且/或者对所述处理预算进行控制。举例来说，相对于一个任务的几个小时的寿命，5毫秒的处理预算每10毫秒重复一次。

所述任务50、60只有在其预算繁忙时间54、64期间才需要存储器空间22。为了确定第一任务50和/或第二任务60是否需要存储器空间22，所述系统100包括一个确定装置30。该高速缓存空间确定装置30可以被实现为至少一个软件算法。

为了说明本发明的特征，图2示出了根据现有技术的高速缓存管理。在图2中的上部示出了第一任务50随时间t的任务执行56以及第二任务60随时间t的任务执行66。

在图2中的下部，在垂直轴上示出了高速缓存空间22，并且时间t在水平轴上延伸。从而在图2中的下部示出了对应于第一任务50的高速缓存预留52以及对应于第二任务60的高速缓存预留62。如图2中所示，在现有技术系统中，第一任务50保持其高速缓存预留直到一个时间周期的末尾70，即使第一任务50将不使用该高速缓存也是如此。

与现有技术不同，在图3中示出了根据本发明的高速缓存管理。根据图3，通过如下方式动态地使用所述高速缓存预留机制：

-当第一任务50和/或第二任务60需要高速缓存空间22时预留该高速缓存空间22；以及

-当第一任务50和/或第二任务60不需要该高速缓存空间22时释放该高速缓存空间22。

与前面的工作(对照图2)的不同之处在于“当所述任务需要高速缓存空间”的定义。在传统的系统(对照图2)中，任务50、60在其寿命期间都需要高速缓存空间22。然而，根据本发明(对照图3)，对于高速缓存空间22的需求与处理预算可用性相关联。为此，所述高速缓存预留机制或者高速缓存预留系统耦合到所述中央处理单元(CPU)预留系统。图3示出了一个直观的例子：

第一任务50和第二任务60在相同的中央处理单元(CPU)10上执行，并且这些任务50、60当中的每一个以相同的粒度接收该CPU 10的百分之五十，例如每40毫秒中的20毫秒。当第一任务50完成了其预算54时，高速缓存中的所述空间被安全地释放，并且完全可用于另一个任务60。

换句话说，如果第一任务50已经消耗了其所有的处理预算，则释放被分配给第一任务50的第一高速缓存空间52，并且在所述周期的剩余部分内将其分配给第二任务62。结果，任务62将由于在所述周期的剩余部分内(即直到所述预算在时间70被补充)使用百分之百的高速缓存而更加高效地运行。因此，任务50、60都能够使用百分之百的高速缓存22。

在通常的情况下，想要知道任务50、60已经完成了其预算并且在一段时间内将不执行并不容易。然而，如果还提供了处理预算(如本发明所提出的那样)，则可以精确地计算任务50、60何时开始执行以及何时将完成执行。

根据本发明，可以计算最坏情况下的繁忙周期，即最早的起始时间以及最迟的结束时间。通过计算最坏情况下的繁忙周期，分离的繁忙周期可以被用来最大化高速缓存预算划拨。在图3中示出了如何释放由第一任务50使用的高速缓存空间52，以便由第二任务60使用。图3上部的垂直箭头示出了预算划拨14。

图4以示意性的方式示出了电视(TV)机200的最重要的各部件，其包括如上所述的系统100。在图4中，天线202接收电视信号。该天线202例如还可以是圆盘式卫星电视天线、有线电视线缆或者能够接收电视信号的任何其他设备。接收器204接收该信号。除了接收器204之外，该电视机200包括一个可编程组件206，其例如是可编程集成电路。该可编程组件206包括所述系统100。电视屏幕210显示图像，所述图像由接收器204接收并且由可编程组件206、系统100以及通常包括在电视机中的其他部件(这里为清楚起见没有示出)处理。

图5以示意性的方式示出了包括所述系统100的机顶盒300的最重要的各部件。该机顶盒300接收由天线202发送的信号。电视机200可以显示由该机顶盒300与所述系统100一起从所接收信号产生的输出信号。

本发明的上面描述的实现方式有可能实现一种多任务系统，其中当切换到新任务时完全释放所述高速缓存空间，从而全部两个或多个任务具有百分之百的高速缓存。所述高速缓存预留被耦合到所述中央处理单元(CPU)预留系统。

上面描述的方法管理在多个任务50、60之间共享的高速缓存空间20。该方法同样适用于包含多个CPU 10的系统100。在这种多CPU系统100中，典型地存在一个共享的高速缓存以作为所述存储器分层结构的一部分，可以以相同的优点管理该高速缓存以用于任务共享。

附图标记列表

100 用于管理存储器空间的系统

10 中央处理单元，特别是多个中央处理单元

12 处理预算预留装置，特别是中央处理单元预留装置

14 预算划拨

20 存储器单元，特别是高速缓存单元

22 存储器空间，特别是高速缓存空间

30 确定装置

40 分配装置

50 第一任务

52 第一存储器空间，特别被分配给第一任务50

54 第一任务50的执行时间或繁忙周期或预算繁忙时间

56 第一任务50的任务执行

60 第二任务

62 第二存储器空间，特别被分配给第二任务60

64 第二任务60的执行时间或繁忙周期或预算繁忙时间

66 第二任务60的任务执行

70 时间周期的末尾，特别是补充时间的末尾

200 电视机

202 天线

204 接收器

206 可编程组件，例如可编程集成电路(IC)

210 电视屏幕

300 机顶盒

t 时间或时间周期

Claims

1、一种用于管理存储器空间(22)的系统(100)，该系统包括：

-至少一个中央处理单元(10)，其用于执行至少一个第一任务(50)和至少一个第二任务(60)；

-至少一个存储器单元(20)，特别是至少一个高速缓存，其中该存储器单元

-与该中央处理单元(10)相连接；并且

-包括所述存储器空间(22)，该存储器空间被细分成

-至少一个第一存储器空间(52)，特别是至少一个第一高速缓存空间；以及

-至少一个第二存储器空间(62)，特别是至少一个第二高速缓存空间；

-至少一个确定装置(30)，其用于确定第一任务(50)和/或第二任务(60)是否需要所述存储器空间(22)；以及

-至少一个分配装置(40)，其用于把所述存储器空间(22)分配给对应的任务，特别是用于

-把第一存储器空间(52)分配给第一任务(50)；以及

-把第二存储器空间(62)分配给第二任务(60)，

其特征在于，所述存储器空间(22)通过如下方式被分配给对应的任务(50，60)：

-根据所确定的存储器空间(22)的需求把所述存储器空间分配给对应的任务；以及

-根据至少一个对应的处理预算把所述存储器空间分配给对应的任务，该处理预算由至少一个处理预算预留装置(12)指定给每个任务(50，60)。

2、根据权利要求1的系统，其特征在于：

-一旦所述处理预算被耗尽，相应的任务(50，60)将不被执行，直到其处理预算被再次补充，特别是直到所述处理预算周期的末尾(70)；

-所述确定装置(30)被设计成确定直到对应的处理预算的随后的补充所需要的时间，特别是

-用于确定所述任务的至少其中之一的执行时间或繁忙周期；以及/或者

-用于确定所述任务(50，60)的至少其中之一的不执行时间；以及

-所述分配装置(40)被设计成把被指定给不执行的任务的所述存储器空间(22)分配给至少一个可执行任务(50，60)，特别是直到所确定的处理预算周期的末尾(70)。

3、根据权利要求1或2的系统，其特征在于，所述任务(50，60)的寿命长于其对应的处理预算的粒度。

4、根据权利要求1至3的至少其中之一的系统，其特征在于：

-所述存储器空间(22)被排他地分配给第一任务(50)；以及/或者

-所述存储器空间(22)被部分地分配给第一任务(50)并且被部分地分配给第二任务(60)；以及/或者

-所述存储器空间(22)被排他地分配给第二任务(60)；以及/或者

-所述存储器空间(22)是被设计成存储所述整个系统存储器的至少一部分的数据拷贝的高速缓存；以及/或者

-所述存储器空间(22)是由多个中央处理单元(10)共享存取的第二级高速缓存。

5、一种包括根据权利要求1至4的至少其中之一的系统的电视机(200)。

6、一种包括根据权利要求1至5的至少其中之一的系统的机顶盒(300)。

7、一种用于管理存储器空间(22)的方法，特别是用于调度至少一个第一任务(50)和至少一个第二任务(60)，该方法包括以下步骤：

-执行第一任务(50)和/或第二任务(60)；

-确定第一任务(50)和/或第二任务(60)是否需要存储器空间(22)；

-给对应的任务(50，60)分配所述存储器空间(22)，特别是

-把第一存储器空间(52)分配给第一任务，该第一存储器空间例如是第一高速缓存空间；以及

-把第二存储器空间(62)分配给第二任务，该第二存储器空间例如是第二高速缓存空间，

-根据至少一个对应的处理预算把所述存储器空间分配给对应的任务，该处理预算被指定给每个任务(50，60)。

8、根据权利要求7的方法，其特征在于以下的附加步骤：

-如果所述处理预算被耗尽则补充所述处理预算，其中相应的任务(50，60)不被执行，直到对所述处理预算的随后的补充为止，特别是直到所述处理预算周期的末尾(70)；

-确定补充对应的处理预算所需要的时间，特别是

-确定所述任务(50，60)的至少其中之一的执行时间或繁忙周期(54，64)；以及/或者

-确定所述任务(50，60)的至少其中之一的不执行时间；以及

-把被指定给不执行的任务的存储器空间(22)分配给至少一个可执行任务(50，60)，特别是直到所确定的处理预算周期的末尾(70)。

9、根据权利要求7或8的方法，其特征在于：

-所述存储器空间(22)被排他地分配给第一任务(50)；以及/或者

-所述存储器空间(22)被排他地分配给第二任务(60)。

10、对于任何数字系统使用至少一个根据权利要求1至4的至少其中之一的系统(100)和/或根据权利要求7至9的至少其中之一的方法，在所述数字系统中，多个应用被并发执行并且共享存储器空间(22)，例如对于以下情况使用所述系统和/或所述方法：

-类似于根据权利要求5的数字电视机(200)的消费者终端，特别是高质量视频系统，或者根据权利要求6的机顶盒(300)。