Competitive analysis of on-line disk scheduling

被引：0
|
作者：
Yeh, TH [1 ]
Kuo, CM [1 ]
Lei, CL [1 ]
Yen, HC [1 ]
机构：
[1] Natl Taiwan Univ, Dept Elect Engn, Taipei 10764, Taiwan
来源：
ALGORITHMS AND COMPUTATION | 1996年 / 1178卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We give a detailed competitive analysis of a popular on-line disk scheduling algorithm, namely, LOOK. Our analysis yields a tight competitive ratio for the LOOK algorithm. By comparing and contrasting the competitive ratio of LOOK with the lower bounds of FCFS and SSTF (which are equally popular in disk scheduling), our results provide strong evidence to suggest that when the workload of disk access is heavy, LOOK outperforms SSTF and FCFS. As a by-product, our analysis also reveals (quantitatively) the role played by the degree of lookahead in disk scheduling.
引用
收藏
页码：356 / 365
页数：10
相关论文
共 50 条
  • [31] Competitive on-line switching policies
    Bar-Noy, A
    Freund, A
    Landa, S
    Naor, J
    ALGORITHMICA, 2003, 36 (03) : 225 - 247
  • [32] On competitive on-line paging with lookahead
    Breslauer, D
    THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 365 - 375
  • [33] Competitive Optimal On-Line Leasing
    R. El-Yaniv
    R. Kaniel
    N. Linial
    Algorithmica, 1999, 25 : 116 - 140
  • [34] Competitive on-line linear regression
    Vovk, V
    ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 10, 1998, 10 : 364 - 370
  • [35] Competitive on-line switching policies
    Bar-Noy, A
    Freund, A
    Landa, S
    Naor, J
    PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, : 525 - 534
  • [36] Competitive optimal on-line leasing
    El-Yaniv, R
    Kaniel, R
    Linial, N
    ALGORITHMICA, 1999, 25 (01) : 116 - 140
  • [37] Competitive On-Line Switching Policies
    Algorithmica, 2003, 36 : 225 - 247
  • [38] On-Line Booking Policies and Competitive Analysis of Medical Examination in Hospital
    Luo, Li
    Qin, Chun-rong
    Tang, Shi-jun
    Chen, Xian
    Guo, Hui-li
    JOURNAL OF APPLIED MATHEMATICS, 2014,
  • [39] Competitive analysis for the on-line fuzzy most connective path problem
    Ma, Wei-Min
    Yu, Zhi-Fang
    Wang, Ke
    PROCEEDINGS OF 2006 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2006, : 1845 - +
  • [40] ON-LINE SCHEDULING OF EMPTY CONTAINERS
    Zhang, Lele
    Wirth, Andrew
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2012, 29 (04)
12345