论文标题
具有一般服务时间的冗余系统的有效调度
Efficient scheduling in redundancy systems with general service times
论文作者
论文摘要
我们表征了调度策略对具有取消结算冗余的嵌套系统中平均响应时间的影响。我们不仅考虑了冗余政策，例如FCF和ROS，还考虑表格$π$ 1- $π$ 2的冗余 - 感知政策，其中$π$ 1在工作类别中判断（例如，最少冗余（LRF）（LRF）（LRF），最不冗余（LRF），大多数nofactectionfirst（MRF）和$ $ $ 2的分类。假设作业具有独立且相同分布的（I.I.D.）副本，我们将证明以下内容：（i）当作业具有指数服务时间时，LRF策略的表现优于任何其他策略。 （ii）当服务时间是新的 - 比使用时，MRF-FCF的表现优于LRF-FCFS，因为服务时间的可变性会无限地增长。 （iii）当服务时间比新次使用时，LRF-ROS（MRF-ROS）在两个服务器系统中的表现优于LRF-FCF（分别MRF-FCFS）。声明（iii）还会成立，当作业大小遵循一般分布并具有相同的副本（所有作业副本的大小都相同）。此外，我们通过仿真显示，对于大量的冗余系统，与冗余政策相比，冗余感知政策可以大大改善平均响应时间。我们还探讨了冗余对稳定区域的影响。
We characterize the impact of scheduling policies on the mean response time in nested systems with cancel-on-complete redundancy. We consider not only redundancy-oblivious policies, such as FCFS and ROS, but also redundancy-aware policies of the form $Π$ 1 -- $Π$ 2 , where $Π$ 1 discriminates among job classes (e.g., least-redundant-first (LRF), most-redundantfirst (MRF)) and $Π$ 2 discriminates among jobs of the same class. Assuming that jobs have independent and identically distributed (i.i.d.) copies, we prove the following: (i) When jobs have exponential service times, LRF policies outperform any other policy. (ii) When service times are New-Worse-than-Used, MRF-FCFS outperforms LRF-FCFS as the variability of the service time grows infinitely large. (iii) When service times are New-Better-than-Used, LRF-ROS (resp. MRF-ROS) outperforms LRF-FCFS (resp. MRF-FCFS) in a two-server system. Statement (iii) also holds when job sizes follow a general distribution and have identical copies (all the copies of a job have the same size). Moreover, we show via simulation that, for a large class of redundancy systems, redundancy-aware policies can considerably improve the mean response time compared to redundancy-oblivious policies. We also explore the effect of redundancy on the stability region.
