Presents an efficient distributed online algorithm for scheduling jobs that are created dynamically, subject to resource constraints that require that certain pairs of jobs not run concurrently. The focus is on the response time of the system to each job, i.e. the length of the time interval that starts when the job is created or assigned to a processor and ends at the instant the execution of the job begins. The goal is to provide guarantees on the response time to each job j in terms of the density of arrivals of jobs that conflict with j. The model is completely asynchronous and includes various resource allocation problems that have been studied extensively, including the dining philosophers problem and its generalizations to arbitrary networks. In these versions of the problem, the resource requirements of each new job j determines an upper bound delta /sub j/ on the number of jobs that can exist concurrently in the system and conflict with j. Given such upper bounds, no scheduling algorithm can guarantee a response time better than delta /sub j/ times the maximum execution or message transmission time. A simple algorithm that guarantees response time that is essentially polynomial in delta /sub j/ is presented. It is based on the notion of a distribution queue and has a compact implementation.
展开▼
机译:提出了一种高效的分布式在线算法,用于调度动态创建的作业,但要遵循资源约束,这些约束要求某些作业对不能同时运行。重点是系统对每个作业的响应时间,即时间间隔的长度,该时间间隔是在创建作业或将其分配给处理器时开始,并在作业开始执行的瞬间结束。目的是根据与j冲突的作业的到达密度来保证对每个作业j的响应时间。该模型是完全异步的,并且包括已广泛研究的各种资源分配问题,包括餐饮哲学家问题及其对任意网络的推广。在问题的这些版本中,每个新作业j的资源需求确定了系统中可以同时存在并与j冲突的作业数量的上限delta / sub j /。给定这样的上限,没有调度算法可以保证响应时间比delta / sub j /乘以最大执行时间或消息传输时间要好。提出了一种简单的算法,该算法可确保响应时间基本上是delta / sub j /中的多项式。它基于分发队列的概念,并具有紧凑的实现。
展开▼