公开(公告)号：US6003061A

公开(公告)日：1999-12-14

申请号：US569048

申请日：1995-12-07

申请人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III ,  Steven P. Levi ,  Richard F. Rashid ,  Robert P. Fitzgerald

发明人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III ,  Steven P. Levi ,  Richard F. Rashid ,  Robert P. Fitzgerald

IPC分类号： G06F9/50 ,  G06F9/00

CPC分类号： G06F9/50 ,  G06F2209/5014

摘要： A method and system for scheduling the use of a computer system resource using a resource planner and a resource provider is provided. In a preferred embodiment, a resource is scheduled for use by a plurality of consumer entities. Each consumer entity may request the commitment of a share of the resource. The method and system utilizes representations of resource usage policy, present commitments of shares of the resource, and present commitments of specified amounts of the resource over specified period of time. The method and system first receives a request from a consumer entity for the commitment of a specified share of the resource. In response, the method and system determines whether the specified share of the resource should be committed to the requesting consumer entity. This determination is based on the representations of resource usage policy and present commitments of shares of the resource. If it is determined that the specified share of the resource should be committed to the requesting consumer entity, then the method and system modifies the representation of present commitments of shares of the resource to commit the specified share of the resource to the requesting consumer entity. The method and system then schedules the use of the resource by the plurality of consumer entity based on the modified representation of present commitments of shares of the resource.

摘要翻译： 提供了一种用于使用资源规划器和资源提供者来调度计算机系统资源的使用的方法和系统。 在优选实施例中，资源被调度为由多个消费者实体使用。 每个消费者实体可以请求资源份额的承诺。 该方法和系统利用资源使用政策的表示，资源份额的现有承诺以及指定时间内资源规定数量的承诺。 方法和系统首先从消费者实体接收对资源的指定份额的承诺的请求。 作为响应，方法和系统确定资源的指定份额是否应该提交给请求的消费者实体。 这一决定是基于资源使用政策的表示和资源份额的现有承诺。 如果确定资源的指定份额应该提交给请求的消费者实体，那么该方法和系统将修改资源共享的当前承诺的表示，以将该资源的指定份额提交给请求的消费者实体。 该方法和系统随后基于对资源份额的当前承诺的修改表示来安排多个消费者实体对资源的使用。

公开(公告)号：US5812844A

公开(公告)日：1998-09-22

申请号：US568577

申请日：1995-12-07

申请人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III ,  Steven P. Levi ,  Richard F. Rashid ,  Robert P. Fitzgerald

发明人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III ,  Steven P. Levi ,  Richard F. Rashid ,  Robert P. Fitzgerald

IPC分类号： G06F9/48 ,  G06F9/00

CPC分类号： G06F9/4887

摘要： A method and system for scheduling the execution of threads using optional time-specific constraints is provided. In a preferred embodiment, a scheduler schedules the execution of a plurality of threads each specifying either a percentage processor time scheduling constraint, indicating that a certain percentage of processor time should be dedicated to the execution of the thread, or a deadline scheduling constraint, indicating that a specified quantity of work should be done by the thread by a specified time deadline. For each thread specifying a percentage processor time scheduling constraint, the scheduler determines a restart time corresponding to the percentage processor time scheduling constraint. For each thread specifying a deadline scheduling constraint, the scheduler determines a restart time corresponding to the deadline scheduling constraint. The scheduler then utilizes the determined restart times for scheduling the threads by selecting the thread having the earliest restart time for execution.

摘要翻译： 提供了一种使用可选的时间特定约束调度线程执行的方法和系统。 在优选实施例中，调度器调度多个线程的执行，每个线程指定百分比处理器时间调度约束，指示处理器时间的一定百分比应该专用于线程的执行，或者指示最后期限调度约束 线程应在指定的时间期限内完成指定数量的工作。 对于指定百分比处理器时间调度约束的每个线程，调度器确定对应于百分比处理器时间调度约束的重新启动时间。 对于指定期限调度约束的每个线程，调度器确定对应于期限调度约束的重启时间。 调度器然后利用所确定的重新启动次数来调度线程，方法是选择具有最早执行重启时间的线程。

公开(公告)号：US06584489B1

公开(公告)日：2003-06-24

申请号：US09038759

申请日：1998-03-11

申请人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III ,  Steven P. Levi ,  Richard F. Rashid ,  Robert P. Fitzgerald

发明人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III ,  Steven P. Levi ,  Richard F. Rashid ,  Robert P. Fitzgerald

IPC分类号： G06F900

CPC分类号： G06F9/50 ,  G06F2209/5014

摘要： A method and system for scheduling the use of a computer system resource using a resource planner and a resource provider are provided. In a preferred embodiment, a resource is scheduled for use by a plurality of consumer entities. Each consumer entity may request the commitment of a share of the resource. The method and system use representations of resource usage policy, present commitments of shares of the resource, and present commitments of specified amounts of the resource over a specified period of time. The method and system first receive a request from a consumer entity for the commitment of a specified share of the resource. In response, the method and system determine whether the specified share of the resource should be committed to the requesting consumer entity. This determination is based on the representations of resource usage policy and present commitments of shares of the resource. If it is determined that the specified share of the resource should be committed to the requesting consumer entity, then the method and system modify the representation of present commitments of shares of the resource to commit the specified share of the resource to the requesting consumer entity. The method and system then schedule the use of the resource by the plurality of consumer entities based on the modified representation of present commitments of shares of the resource.

摘要翻译： 提供了一种用于使用资源规划器和资源提供者调度计算机系统资源的使用的方法和系统。 在优选实施例中，资源被调度为由多个消费者实体使用。 每个消费者实体可以请求资源份额的承诺。 资源使用政策的方法和系统使用表示，资源份额的现有承诺以及在指定时间段内指定资源量的现有承诺。 该方法和系统首先从消费者实体接收对资源的指定份额的承诺的请求。 作为响应，方法和系统确定资源的指定份额是否应该提交给请求的消费者实体。 这一决定是基于资源使用政策的表示和资源份额的现有承诺。 如果确定资源的指定份额应该提交给请求的消费者实体，则方法和系统将修改资源共享的当前承诺的表示，以将该资源的指定份额提交给请求的消费者实体。 该方法和系统随后基于对资源的份额的当前承诺的修改的表示来安排多个消费者实体的资源的使用。

公开(公告)号：US5473362A

公开(公告)日：1995-12-05

申请号：US159188

申请日：1993-11-30

申请人： Robert P. Fitzgerald ,  Joseph S. Barrera, III ,  William J. Bolosky ,  Richard P. Draves, Jr. ,  Michael B. Jones ,  Steven P. Levi ,  Nathan P. Myhrvold ,  Richard F. Rashid ,  Garth A. Gibson

发明人： Robert P. Fitzgerald ,  Joseph S. Barrera, III ,  William J. Bolosky ,  Richard P. Draves, Jr. ,  Michael B. Jones ,  Steven P. Levi ,  Nathan P. Myhrvold ,  Richard F. Rashid ,  Garth A. Gibson

IPC分类号： H04N5/907 ,  H04H20/76 ,  H04N7/173 ,  H04N21/472

CPC分类号： H04N21/47202 ,  H04N7/17318 ,  H04N7/17336

摘要： A scalable method and system for easily scheduling data transfer for a video-on-demand server system is provided. A strategy for locating available bandwidth and allocating available bandwidth to subscribers as needed is provided. The input/output bandwidth of storage devices that store data for video image sequences is modelled as a series of bandwidth units. Each bandwidth unit has sufficient capacity to service an individual subscriber during a scheduling cycle. Video image sequences or other data sequences are striped across storage devices such that data for a data sequence is forwarded to the subscriber by reading from a sequence of storage devices in consecutive time frames.

摘要翻译： 提供了一种用于轻松调度视频点播服务器系统的数据传输的可扩展方法和系统。 提供了一种用于定位可用带宽并根据需要为订户分配可用带宽的策略。 存储视频图像序列数据的存储设备的输入/输出带宽被建模为一系列带宽单位。 每个带宽单元在调度周期内具有足够的容量来服务单个用户。 视频图像序列或其他数据序列在存储设备之间被条带化，使得通过在连续的时间帧中从一系列存储设备读取来将数据序列的数据转发给用户。

公开(公告)号：US07571438B2

公开(公告)日：2009-08-04

申请号：US09909072

申请日：2001-07-18

申请人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III

发明人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III

IPC分类号： G06F9/46

CPC分类号： G06F9/5011 ,  G06F2209/5014

摘要： A resource management mechanism is provided to ensure that real-time application programs running on a single machine or set of machines exhibit predictable behavior. The resource management mechanism employs the abstraction of an activity which serves as the basis for granting resource reservations and for accounting. An activity submits a request for resources in specified amounts to a resource planner. The activity is resource self-aware so that it is aware of its resource requirements. The activity may query resource providers to obtain resource requirements for particular operations. The resource planner determines whether the activity should be granted the requested reservation by employing an internal policy. Policy is separated by mechanism so that the resource planner may implement any of a number of policies. The resource planner may choose to grant the reservation to an activity or deny the request by an activity. When denying a request, the resource planner may inform the activity of what quantity of the requested resources are currently available so that the activity may submit a modified request. The resource management mechanism includes a dynamic feedback mechanism for initiating renegotiation of resource reservations when appropriate.

公开(公告)号：US06282561B1

公开(公告)日：2001-08-28

申请号：US08568578

申请日：1995-12-07

申请人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III

发明人： Michael B. Jones ,  Paul J. Leach ,  Richard P. Draves, Jr. ,  Joseph S. Barrera, III

IPC分类号： G06F900

CPC分类号： G06F9/5011 ,  G06F2209/5014

摘要： A resource management mechanism is provided to ensure that real-time application programs running on a single machine or set of machines exhibit predictable behavior. The resource management mechanism employs the abstraction of an activity which serves as the basis for granting resource reservations and for accounting. An activity submits a request for resources in specified amounts to a resource planner. The activity is resource self-aware so that it is aware of its resource requirements. The activity may query resource providers to obtain resource requirements for particular operations. The resource planner determines whether the activity should be granted the requested reservation by employing an internal policy. Policy is separated by mechanism so that the resource planner may implement any of a number of policies. The resource planner may choose to grant the reservation to an activity or deny the request by an activity. When denying a request, the resource planner may inform the activity of what quantity of the requested resources are currently available so that the activity may submit a modified request. The resource management mechanism includes a dynamic feedback mechanism for initiating renegotiation of resource reservations when appropriate.

摘要翻译： 提供资源管理机制以确保在单个机器或机器组上运行的实时应用程序呈现出可预测的行为。 资源管理机制采用抽象的活动，作为资源预留和会计准备的基础。 活动向资源规划者提交指定数量的资源请求。 该活动是资源自我感知，以便它了解其资源需求。 该活动可以查询资源提供者以获得特定操作的资源需求。 资源计划员通过采用内部策略来确定活动是否应该被授予请求的预留。 策略由机制分隔，以便资源规划师可以实现多个策略中的任何一个。 资源规划师可以选择将活动的请求授予活动或拒绝该请求。 当拒绝请求时，资源规划者可以通知活动当前可用的所请求的资源的数量，使得活动可以提交经修改的请求。 资源管理机制包括适当时启动重新协商资源预留的动态反馈机制。

公开(公告)号：US06490612B1

公开(公告)日：2002-12-03

申请号：US09564564

申请日：2000-05-04

申请人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

发明人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

IPC分类号： G06F15173

CPC分类号： G06F9/4887

摘要： The present invention provides predictable scheduling of programs using a repeating precomputed schedule. In a preferred embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. The scheduler first selects a current node within the accessed scheduling graph. When the processor becomes available to execute threads, the scheduler advances from the current node to a new current node in accordance with a root-to-leaf traversal of the scheduling graph. After advancing to the new current node, the scheduler executes one or more threads of the activity to which the new current node is dedicated for the execution interval length associated with the new current node. In a further preferred embodiment, the scheduler allocates specific iterations through specific nodes to satisfy the constraints submitted by threads.

摘要翻译： 本发明使用重复的预先计算的进度来提供程序的可预测的调度。 在优选实施例中，调度器访问活动调度图。 活动调度图由每个表示循环执行间隔的节点组成，并且具有一个根，一个或多个叶以及从根到每个叶的至少一个路径。 每个节点在从根到叶的至少一个路径上，并且在图的遍历期间发生由每个节点表示的执行间隔的次数等于从根到叶的路径的数量，该节点 是在。 每个节点与其相关联的执行间隔长度，并且适于专用于执行单个活动的线程。 调度器首先选择所访问的调度图中的当前节点。 当处理器可用于执行线程时，调度器将根据调度图的根到叶遍历从当前节点前进到新的当前节点。 在进入新的当前节点之后，调度器执行新的当前节点专用于与新的当前节点相关联的执行间隔长度的活动的一个或多个线程。 在另一优选实施例中，调度器通过特定节点分配特定迭代以满足线程提交的约束。

公开(公告)号：US06317774B1

公开(公告)日：2001-11-13

申请号：US08781106

申请日：1997-01-09

申请人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

发明人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

IPC分类号： G06F900

CPC分类号： G06F9/4887

摘要： The present invention provides predictable scheduling of programs using a repeating precomputed schedule. In a preferred embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. The scheduler first selects a current node within the accessed scheduling graph. When the processor becomes available to execute threads, the scheduler advances from the current node to a new current node in accordance with a root-to-leaf traversal of the scheduling graph. After advancing to the new current node, the scheduler executes one or more threads of the activity to which the new current node is dedicated for the execution interval length associated with the new current node. In a further preferred embodiment, the scheduler allocates specific iterations through specific nodes to satisfy the constraints submitted by threads.

摘要翻译： 本发明使用重复的预先计算的进度来提供程序的可预测的调度。 在优选实施例中，调度器访问活动调度图。 活动调度图由每个表示循环执行间隔的节点组成，并且具有一个根，一个或多个叶以及从根到每个叶的至少一个路径。 每个节点在从根到叶的至少一个路径上，并且在图的遍历期间发生由每个节点表示的执行间隔的次数等于从根到叶的路径的数量，该节点 是在。 每个节点与其相关联的执行间隔长度，并且适于专用于执行单个活动的线程。 调度器首先选择所访问的调度图中的当前节点。 当处理器可用于执行线程时，调度器将根据调度图的根到叶遍历从当前节点前进到新的当前节点。 在进入新的当前节点之后，调度器执行新的当前节点专用于与新的当前节点相关联的执行间隔长度的活动的一个或多个线程。 在另一优选实施例中，调度器通过特定节点分配特定迭代以满足线程提交的约束。

公开(公告)号：US06792445B1

公开(公告)日：2004-09-14

申请号：US09564822

申请日：2000-05-04

申请人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

发明人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

IPC分类号： G06F900

CPC分类号： G06F9/4887

摘要： The present invention provides predictable scheduling of programs using a repeating precomputed schedule. In a preferred embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. The scheduler first selects a current node within the accessed scheduling graph. When the processor becomes available to execute threads, the scheduler advances from the current node to a new current node in accordance with a root-to-leaf traversal of the scheduling graph. After advancing to the new current node, the scheduler executes one or more threads of the activity to which the new current node is dedicated for the execution interval length associated with the new current node. In a further preferred embodiment, the scheduler allocates specific iterations through specific nodes to satisfy the constraints submitted by threads.

公开(公告)号：US06718360B1

公开(公告)日：2004-04-06

申请号：US09564881

申请日：2000-05-04

申请人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

发明人： Michael B. Jones ,  Richard P. Draves, Jr. ,  Daniela Rosu ,  Marcel-Catalin Rosu

IPC分类号： G06F900

CPC分类号： G06F9/4887

摘要： The present invention provides predictable scheduling of programs using a repeating precomputed schedule. In a preferred embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. The scheduler first selects a current node within the accessed scheduling graph. When the processor becomes available to execute threads, the scheduler advances from the current node to a new current node in accordance with a root-to-leaf traversal of the scheduling graph. After advancing to the new current node, the scheduler executes one or more threads of the activity to which the new current node is dedicated for the execution interval length associated with the new current node. In a further preferred embodiment, the scheduler allocates specific iterations through specific nodes to satisfy the constraints submitted by threads.

摘要翻译： 本发明使用重复的预先计算的进度来提供程序的可预测的调度。 在优选实施例中，调度器访问活动调度图。 活动调度图由每个表示循环执行间隔的节点组成，并且具有一个根，一个或多个叶以及从根到每个叶的至少一个路径。 每个节点在从根到叶的至少一个路径上，并且在图的遍历期间发生由每个节点表示的执行间隔的次数等于从根到叶的路径的数量，该节点 是在。 每个节点与其相关联的执行间隔长度，并且适于专用于执行单个活动的线程。 调度器首先选择所访问的调度图中的当前节点。 当处理器可用于执行线程时，调度器将根据调度图的根到叶遍历从当前节点前进到新的当前节点。 在进入新的当前节点之后，调度器执行新的当前节点专用于与新的当前节点相关联的执行间隔长度的活动的一个或多个线程。 在另一优选实施例中，调度器通过特定节点分配特定迭代以满足线程提交的约束。