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 条
  • [1] Competitive analysis of on-line disk scheduling
    Yeh, TH
    Kuo, CM
    Lei, CL
    Yen, HC
    THEORY OF COMPUTING SYSTEMS, 1998, 31 (05) : 491 - 506
  • [2] Competitive Analysis of On-Line Disk Scheduling
    Theory of Computing Systems, 1998, 31 : 491 - 506
  • [3] Competitive on-line scheduling with level of service
    Chang, EC
    Yap, C
    JOURNAL OF SCHEDULING, 2003, 6 (03) : 251 - 267
  • [4] Competitive On-Line Scheduling with Level of Service
    Ee-Chien Chang
    Chee Yap
    Journal of Scheduling, 2003, 6 : 251 - 267
  • [5] Competitive on-line scheduling of imprecise computations
    Baruah, SK
    Hickey, ME
    IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (09) : 1027 - 1032
  • [6] Competitive algorithm for on-line multiprocessor scheduling
    Xie, Dongqing
    Ji, Jie
    Zhao, Yu
    Hunan Daxue Xuebao/Journal of Hunan University Natural Sciences, 25 (04): : 100 - 102
  • [7] Competitive analysis of on-line algorithms for on-demand data broadcast scheduling
    Mao, WZ
    I-SPAN 2000: INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES ALGORITHMS AND NETWORKS, PROCEEDINGS, 2000, : 292 - 296
  • [8] Scheduling for on-line taxi problem on a real line and competitive algorithms
    Xin, CL
    Ma, WM
    PROCEEDINGS OF THE 2004 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2004, : 3078 - 3083
  • [9] A Framework for Automated Competitive Analysis of On-line Scheduling of Firm-Deadline Tasks
    Chatterjee, Krishnendu
    Pavlogiannis, Andreas
    Koessler, Alexander
    Schmid, Ulrich
    2014 IEEE 35TH REAL-TIME SYSTEMS SYMPOSIUM (RTSS 2014), 2014, : 118 - 127
  • [10] Competitive on-line scheduling of continuous-media streams
    Garofalakis, M
    Ioannidis, Y
    Özden, B
    Silberschatz, A
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 64 (02) : 219 - 248
12345